00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00029
00030 #include <mln/core/image/image2d.hh>
00031 #include <mln/core/alias/neighb2d.hh>
00032 #include <mln/value/int_u8.hh>
00033 #include <mln/io/pgm/load.hh>
00034
00035 #include <mln/labeling/level.hh>
00036 #include <mln/util/timer.hh>
00037
00038
00039 namespace mln
00040 {
00041
00042
00043 namespace old_canvas
00044 {
00045
00046 template <typename F>
00047 struct labeling
00048 {
00049
00050 F& f;
00051
00052 typedef typename F::I I;
00053 typedef typename F::N N;
00054 typedef typename F::L L;
00055 typedef typename F::S S;
00056
00057
00058 typedef mln_psite(I) psite;
00059
00060
00061 mln_ch_value(I, bool) deja_vu;
00062 mln_ch_value(I, psite) parent;
00063
00064
00065 mln_ch_value(I, L) output;
00066 L nlabels;
00067 bool status;
00068
00069
00070 labeling(F& f);
00071
00072 void init();
00073
00074 void pass_1();
00075
00076 void pass_2();
00077
00078
00079
00080
00081 void make_set(const psite& p);
00082
00083 bool is_root(const psite& p) const;
00084
00085 psite find_root(const psite& x);
00086
00087 void do_union(const psite& n, const psite& p);
00088
00089 };
00090
00091
00092 template <typename F>
00093 labeling<F>::labeling(F& f)
00094 : f(f)
00095 {
00096 trace::entering("canvas::labeling");
00097
00098 init();
00099 f.init();
00100 pass_1();
00101 pass_2();
00102
00103 trace::exiting("canvas::labeling");
00104 }
00105
00106 template <typename F>
00107 void
00108 labeling<F>::init()
00109 {
00110 initialize(deja_vu, f.input);
00111 mln::data::fill(deja_vu, false);
00112 initialize(parent, f.input);
00113 initialize(output, f.input);
00114 mln::data::fill(output, L(literal::zero));
00115 nlabels = 0;
00116 }
00117
00118 template <typename F>
00119 void
00120 labeling<F>::pass_1()
00121 {
00122 mln_fwd_piter(S) p(f.s);
00123 mln_niter(N) n(f.nbh, p);
00124 for_all(p) if (f.handles(p))
00125 {
00126 make_set(p);
00127 for_all(n)
00128 if (f.input.domain().has(n) && deja_vu(n))
00129 {
00130 if (f.equiv(n, p))
00131 do_union(n, p);
00132 else
00133 f.do_no_union(n, p);
00134 }
00135 deja_vu(p) = true;
00136 }
00137 }
00138
00139 template <typename F>
00140 void
00141 labeling<F>::pass_2()
00142 {
00143 mln_bkd_piter(S) p(f.s);
00144 for_all(p) if (f.handles(p))
00145 {
00146 if (is_root(p))
00147 {
00148 if (f.labels(p))
00149 {
00150 if (nlabels == mln_max(L))
00151 {
00152 status = false;
00153 return;
00154 }
00155 output(p) = ++nlabels;
00156 }
00157 }
00158 else
00159 output(p) = output(parent(p));
00160 }
00161 status = true;
00162 }
00163
00164 template <typename F>
00165 void
00166 labeling<F>::make_set(const psite& p)
00167 {
00168 parent(p) = p;
00169 f.init_attr(p);
00170 }
00171
00172 template <typename F>
00173 bool
00174 labeling<F>::is_root(const psite& p) const
00175 {
00176 return parent(p) == p;
00177 }
00178
00179 template <typename F>
00180 typename labeling<F>::psite
00181 labeling<F>::find_root(const psite& x)
00182 {
00183 if (parent(x) == x)
00184 return x;
00185 else
00186 return parent(x) = find_root(parent(x));
00187 }
00188
00189 template <typename F>
00190 void
00191 labeling<F>::do_union(const psite& n, const psite& p)
00192 {
00193 psite r = find_root(n);
00194 if (r != p)
00195 {
00196 parent(r) = p;
00197 f.merge_attr(r, p);
00198 }
00199 }
00200
00201
00202 }
00203
00204
00205
00206 namespace old_labeling
00207 {
00208
00209
00210 template <typename I_, typename N_, typename L_>
00211 struct level_functor
00212 {
00213 typedef mln_psite(I_) P;
00214
00215
00216
00217 typedef I_ I;
00218 typedef N_ N;
00219 typedef L_ L;
00220 typedef mln_pset(I) S;
00221
00222 const I& input;
00223 const N& nbh;
00224 const S& s;
00225
00226 bool handles(const P& p) const { return input(p) == val; }
00227 bool equiv(const P& n, const P&) const { return input(n) == val; }
00228
00229 void init() {}
00230 bool labels(const P&) const { return true; }
00231 void do_no_union(const P&, const P&) {}
00232 void init_attr(const P&) {}
00233 void merge_attr(const P&, const P&) {}
00234
00235
00236
00237 const mln_value(I_)& val;
00238
00239 level_functor(const I& input, const mln_value(I)& val, const N& nbh)
00240 : input(input),
00241 nbh(nbh),
00242 s(input.domain()),
00243 val(val)
00244 {}
00245 };
00246
00247
00248
00249 template <typename I, typename N, typename L>
00250 mln_ch_value(I, L)
00251 level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh,
00252 L& nlabels)
00253 {
00254 trace::entering("labeling::value");
00255
00256 typedef level_functor<I,N,L> F;
00257 F f(exact(input), val, exact(nbh));
00258 old_canvas::labeling<F> run(f);
00259
00260 nlabels = run.nlabels;
00261
00262 trace::exiting("labeling::value");
00263 return run.output;
00264 }
00265
00266 }
00267
00268 }
00269
00270
00271
00272
00273 int main()
00274 {
00275 using namespace mln;
00276 using value::int_u8;
00277
00278 image2d<int_u8> lena;
00279 io::pgm::load(lena, "../../img/lena.pgm");
00280
00281 {
00282 util::timer t;
00283 t.start();
00284 unsigned n;
00285 for (unsigned l = 0; l <= 255; ++l)
00286 old_labeling::value(lena, l, c4(), n);
00287 std::cout << "canvas as class: " << t.read() << std::endl;
00288 }
00289
00290 {
00291 util::timer t;
00292 t.start();
00293 unsigned n;
00294 for (unsigned l = 0; l <= 255; ++l)
00295 labeling::impl::generic::data(lena, l, c4(), n);
00296 std::cout << "canvas as proc.: " << t.read() << std::endl;
00297 }
00298
00299 }