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
00026 #ifndef MLN_CANVAS_LABELING_HH
00027 # define MLN_CANVAS_LABELING_HH
00028
00035
00036 # include <mln/core/concept/image.hh>
00037 # include <mln/data/fill.hh>
00038 # include <mln/literal/zero.hh>
00039 # include <mln/convert/to_upper_window.hh>
00040 # include <mln/extension/adjust_fill.hh>
00041
00042 # include <mln/data/sort_psites.hh>
00043 # include <mln/data/sort_offsets.hh>
00044
00045
00046 namespace mln
00047 {
00048
00049 namespace canvas
00050 {
00051
00052 template <typename I, typename N, typename L,
00053 typename F>
00054 mln_ch_value(I, L)
00055 labeling_video(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00056 F& functor);
00057
00058
00059 template <typename I, typename N, typename L,
00060 typename F>
00061 mln_ch_value(I, L)
00062 labeling_sorted(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00063 F& functor, bool increasing);
00064
00065
00066
00067
00068 # ifndef MLN_INCLUDE_ONLY
00069
00070
00071
00072 namespace internal
00073 {
00074
00075 template <typename I, typename N, typename L,
00076 typename F>
00077 void
00078 labeling_tests(const Image<I>& input_, const Neighborhood<N>& nbh_, const L& nlabels,
00079 const F& f)
00080 {
00081 const I& input = exact(input_);
00082 const N& nbh = exact(nbh_);
00083
00084 mln_precondition(input.is_valid());
00085
00086
00087 (void) input;
00088 (void) nbh;
00089 (void) nlabels;
00090 (void) f;
00091 }
00092
00093 }
00094
00095
00096
00097
00098
00099 namespace impl
00100 {
00101
00102 namespace generic
00103 {
00104
00105 template <typename I>
00106 static inline
00107 mln_psite(I)
00108 find_root(I& parent, const mln_psite(I)& x)
00109 {
00110 if (parent(x) == x)
00111 return x;
00112 else
00113 return parent(x) = find_root(parent, parent(x));
00114 }
00115
00116 template <typename I, typename N, typename L,
00117 typename S, typename F>
00118 mln_ch_value(I, L)
00119 labeling(const Image<I>& input_, const Neighborhood<N>& nbh_, L& nlabels,
00120 const Site_Set<S>& s_, F& f)
00121 {
00122 trace::entering("canvas::impl::generic::labeling");
00123
00124
00125
00126 const I& input = exact(input_);
00127 const N& nbh = exact(nbh_);
00128 const S& s = exact(s_);
00129
00130
00131 typedef mln_psite(I) P;
00132
00133
00134 mln_ch_value(I, bool) deja_vu;
00135 mln_ch_value(I, P) parent;
00136
00137
00138 mln_ch_value(I, L) output;
00139 bool status;
00140
00141
00142 {
00143 initialize(deja_vu, input);
00144 mln::data::fill(deja_vu, false);
00145
00146 initialize(parent, input);
00147
00148 initialize(output, input);
00149 mln::data::fill(output, L(literal::zero));
00150 nlabels = 0;
00151
00152 f.init();
00153 }
00154
00155
00156 {
00157 mln_bkd_piter(S) p(s);
00158 mln_niter(N) n(nbh, p);
00159 for_all(p) if (f.handles(p))
00160 {
00161
00162 parent(p) = p;
00163 f.init_attr(p);
00164
00165 for_all(n)
00166 if (input.domain().has(n) && deja_vu(n))
00167 {
00168 if (f.equiv(n, p))
00169 {
00170
00171 P r = find_root(parent, n);
00172 if (r != p)
00173 {
00174 parent(r) = p;
00175 f.merge_attr(r, p);
00176 }
00177 }
00178 else
00179 f.do_no_union(n, p);
00180 }
00181 deja_vu(p) = true;
00182 }
00183 }
00184
00185
00186 {
00187 mln_fwd_piter(S) p(s);
00188 for_all(p) if (f.handles(p))
00189 {
00190 if (parent(p) == p)
00191 {
00192 if (f.labels(p))
00193 {
00194 if (nlabels == mln_max(L))
00195 {
00196 status = false;
00197 trace::warning("labeling aborted! Too many labels \
00198 for this label type: nlabels > \
00199 max(label_type).");
00200
00201 return output;
00202 }
00203 output(p) = ++nlabels;
00204 }
00205 }
00206 else
00207 output(p) = output(parent(p));
00208 }
00209 status = true;
00210 }
00211
00212 trace::exiting("canvas::impl::generic::labeling");
00213 return output;
00214 }
00215
00216 }
00217
00218
00219
00220
00221
00222 template <typename I>
00223 static inline
00224 unsigned
00225 find_root_fastest(I& parent, unsigned x)
00226 {
00227 if (parent.element(x) == x)
00228 return x;
00229 else
00230 return parent.element(x) = find_root_fastest(parent, parent.element(x));
00231 }
00232
00233
00234 template <typename I, typename N, typename L,
00235 typename F>
00236 mln_ch_value(I, L)
00237 labeling_video_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_,
00238 L& nlabels, F& f)
00239 {
00240 trace::entering("canvas::impl::labeling_video_fastest");
00241
00242
00243
00244 const I& input = exact(input_);
00245 const N& nbh = exact(nbh_);
00246
00247 extension::adjust(input, nbh);
00248
00249
00250 mln_ch_value(I, bool) deja_vu;
00251 mln_ch_value(I, unsigned) parent;
00252
00253
00254 mln_ch_value(I, L) output;
00255 bool status;
00256
00257
00258 {
00259 initialize(deja_vu, input);
00260 mln::data::fill(deja_vu, true);
00261 extension::fill(deja_vu, false);
00262
00263 initialize(parent, input);
00264
00265 initialize(output, input);
00266 mln::data::fill(output, L(literal::zero));
00267 nlabels = 0;
00268
00269 f.init_();
00270 }
00271
00272
00273 {
00274 util::array<int> dp = positive_offsets_wrt(input, nbh);
00275 const unsigned n_nbhs = dp.nelements();
00276
00277 mln_bkd_pixter(const I) px(input);
00278 for_all(px)
00279 {
00280 unsigned p = px.offset();
00281 if (! f.handles_(p))
00282 continue;
00283
00284
00285 parent.element(p) = p;
00286 f.init_attr_(p);
00287 for (unsigned i = 0; i < n_nbhs; ++i)
00288 {
00289 unsigned n = p + dp[i];
00290 if (deja_vu.element(n))
00291 {
00292 if (f.equiv_(n, p))
00293 {
00294
00295 unsigned r = find_root_fastest(parent, n);
00296 if (r != p)
00297 {
00298 parent.element(r) = p;
00299 f.merge_attr_(r, p);
00300 }
00301 }
00302 else
00303 f.do_no_union_(n, p);
00304 }
00305 }
00306 }
00307 }
00308
00309
00310 {
00311 mln_fwd_pixter(const I) px(input);
00312 for_all(px)
00313 {
00314 unsigned p = px.offset();
00315 if (! f.handles_(p))
00316 continue;
00317 if (parent.element(p) == p)
00318 {
00319 if (f.labels_(p))
00320 {
00321 if (nlabels == mln_max(L))
00322 {
00323 status = false;
00324 trace::warning("labeling aborted! Too many labels for \
00325 this label type: nlabels > \
00326 max(label_type).");
00327 return output;
00328 }
00329 output.element(p) = ++nlabels;
00330 }
00331 }
00332 else
00333 output.element(p) = output.element(parent.element(p));
00334 }
00335 status = true;
00336 }
00337
00338 trace::exiting("canvas::impl::labeling_video_fastest");
00339 return output;
00340 }
00341
00342
00343
00344
00345
00346 template <typename I, typename N, typename L,
00347 typename S, typename F>
00348 mln_ch_value(I, L)
00349 labeling_sorted_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, L& nlabels,
00350 const S& s, F& f)
00351 {
00352 trace::entering("canvas::impl::labeling_sorted_fastest");
00353
00354
00355
00356 const I& input = exact(input_);
00357 const N& nbh = exact(nbh_);
00358
00359 extension::adjust(input, nbh);
00360
00361
00362 typedef mln_psite(I) P;
00363
00364
00365 mln_ch_value(I, bool) deja_vu;
00366 mln_ch_value(I, unsigned) parent;
00367
00368
00369 mln_ch_value(I, L) output;
00370 bool status;
00371
00372
00373 {
00374 initialize(deja_vu, input);
00375 mln::data::fill(deja_vu, false);
00376 extension::fill(deja_vu, false);
00377
00378 initialize(parent, input);
00379
00380 initialize(output, input);
00381 mln::data::fill(output, L(literal::zero));
00382 nlabels = 0;
00383
00384 f.init_();
00385 }
00386
00387 util::array<int> dp = offsets_wrt(input, nbh);
00388 const unsigned n_nbhs = dp.nelements();
00389
00390 const unsigned n_points = s.nelements();
00391
00392
00393 {
00394 for (int i = n_points - 1; i >=0; --i)
00395 {
00396 unsigned p = s[i];
00397 if (! f.handles_(p))
00398 continue;
00399
00400
00401 parent.element(p) = p;
00402 f.init_attr_(p);
00403
00404 for (unsigned j = 0; j < n_nbhs; ++j)
00405 {
00406 unsigned n = p + dp[j];
00407 if (! deja_vu.element(n))
00408 continue;
00409
00410 if (f.equiv_(n, p))
00411 {
00412
00413 unsigned r = find_root_fastest(parent, n);
00414 if (r != p)
00415 {
00416 parent.element(r) = p;
00417 f.merge_attr_(r, p);
00418 }
00419 }
00420 else
00421 f.do_no_union_(n, p);
00422 }
00423 deja_vu.element(p) = true;
00424 }
00425 }
00426
00427
00428 {
00429 for (unsigned i = 0; i < n_points; ++i)
00430 {
00431 unsigned p = s[i];
00432 if (! f.handles_(p))
00433 continue;
00434
00435 if (parent.element(p) == p)
00436 {
00437 if (f.labels_(p))
00438 {
00439 if (nlabels == mln_max(L))
00440 {
00441 status = false;
00442 trace::warning("labeling aborted! Too many labels \
00443 for this label type: nlabels > \
00444 max(label_type).");
00445 return output;
00446 }
00447 output.element(p) = ++nlabels;
00448 }
00449 }
00450 else
00451 output.element(p) = output.element(parent.element(p));
00452 }
00453 status = true;
00454 }
00455
00456 trace::exiting("canvas::impl::labeling_sorted_fastest");
00457 return output;
00458 }
00459
00460 }
00461
00462
00463
00464
00465
00466 namespace internal
00467 {
00468
00469
00470
00471 template <typename I, typename N, typename L,
00472 typename F>
00473 inline
00474 mln_ch_value(I, L)
00475 labeling_video_dispatch(metal::false_,
00476 const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00477 F& functor)
00478 {
00479 return impl::generic::labeling(input, nbh, nlabels, exact(input).domain(),
00480 functor);
00481 }
00482
00483 template <typename I, typename N, typename L,
00484 typename F>
00485 inline
00486 mln_ch_value(I, L)
00487 labeling_video_dispatch(metal::true_,
00488 const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00489 F& functor)
00490 {
00491 return impl::labeling_video_fastest(input, nbh, nlabels, functor);
00492 }
00493
00494 template <typename I, typename N, typename L,
00495 typename F>
00496 inline
00497 mln_ch_value(I, L)
00498 labeling_video_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00499 F& functor)
00500 {
00501 enum {
00502 test = mlc_equal(mln_trait_image_speed(I),
00503 trait::image::speed::fastest)::value
00504 &&
00505 mln_is_simple_neighborhood(N)::value
00506 };
00507 return labeling_video_dispatch(metal::bool_<test>(),
00508 input, nbh, nlabels,
00509 functor);
00510 }
00511
00512
00513
00514
00515 template <typename I, typename N, typename L, typename F>
00516 inline
00517 mln_ch_value(I, L)
00518 labeling_sorted_dispatch(metal::false_,
00519 const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00520 F& functor, bool increasing)
00521 {
00522 p_array<mln_psite(I)> s =
00523 increasing ?
00524 data::sort_psites_increasing(input) :
00525 data::sort_psites_decreasing(input);
00526 return impl::generic::labeling(input, nbh, nlabels, s,
00527 functor);
00528 }
00529
00530 template <typename I, typename N, typename L, typename F>
00531 inline
00532 mln_ch_value(I, L)
00533 labeling_sorted_dispatch(metal::true_,
00534 const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00535 F& functor, bool increasing)
00536 {
00537 util::array<unsigned> s =
00538 increasing ?
00539 data::sort_offsets_increasing(input) :
00540 data::sort_offsets_decreasing(input);
00541 return impl::labeling_sorted_fastest(input, nbh, nlabels, s,
00542 functor);
00543 }
00544
00545 template <typename I, typename N, typename L, typename F>
00546 inline
00547 mln_ch_value(I, L)
00548 labeling_sorted_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00549 F& functor, bool increasing)
00550 {
00551 enum {
00552 test = mlc_equal(mln_trait_image_speed(I),
00553 trait::image::speed::fastest)::value
00554 &&
00555 mln_is_simple_neighborhood(N)::value
00556 };
00557 return labeling_sorted_dispatch(metal::bool_<test>(),
00558 input, nbh, nlabels,
00559 functor, increasing);
00560 }
00561
00562
00563 }
00564
00565
00566
00567
00568
00569
00570 template <typename I, typename N, typename L,
00571 typename F>
00572 inline
00573 mln_ch_value(I, L)
00574 labeling_video(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00575 F& functor)
00576 {
00577 trace::entering("canvas::labeling_video");
00578
00579 internal::labeling_tests(input, nbh, nlabels, functor);
00580
00581 mln_ch_value(I, L) output;
00582 output = internal::labeling_video_dispatch(input, nbh, nlabels,
00583 functor);
00584
00585 trace::exiting("canvas::labeling_video");
00586 return output;
00587 }
00588
00589
00590 template <typename I, typename N, typename L,
00591 typename F>
00592 inline
00593 mln_ch_value(I, L)
00594 labeling_sorted(const Image<I>& input, const Neighborhood<N>& nbh, L& nlabels,
00595 F& functor, bool increasing)
00596 {
00597 trace::entering("canvas::labeling_sorted");
00598
00599 internal::labeling_tests(input, nbh, nlabels, functor);
00600
00601 mln_ch_value(I, L) output;
00602 output = internal::labeling_sorted_dispatch(input, nbh, nlabels,
00603 functor, increasing);
00604
00605 trace::exiting("canvas::labeling_sorted");
00606 return output;
00607 }
00608
00609 # endif // ! MLN_INCLUDE_ONLY
00610
00611 }
00612
00613 }
00614
00615
00616 #endif // ! MLN_CANVAS_LABELING_HH