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_GENERIC_HH
00027 # define MLN_CANVAS_LABELING_GENERIC_HH
00028
00033
00034 # include <mln/core/concept/image.hh>
00035 # include <mln/core/concept/neighborhood.hh>
00036 # include <mln/core/concept/site_set.hh>
00037
00038 # include <mln/data/fill.hh>
00039
00040 namespace mln
00041 {
00042
00043 namespace canvas
00044 {
00045
00046 namespace labeling
00047 {
00048
00049 namespace impl
00050 {
00051
00052 namespace generic
00053 {
00054
00057
00058 template <typename I, typename N, typename L,
00059 typename S, typename F>
00060 mln_ch_value(I, L)
00061 labeling(const Image<I>& input_, const Neighborhood<N>& nbh_,
00062 L& nlabels, const Site_Set<S>& s_, F& f);
00063
00064
00065 # ifndef MLN_INCLUDE_ONLY
00066
00067 template <typename I>
00068 static inline
00069 mln_psite(I)
00070 find_root(I& parent, const mln_psite(I)& x)
00071 {
00072 if (parent(x) == x)
00073 return x;
00074 else
00075 return parent(x) = find_root(parent, parent(x));
00076 }
00077
00078
00079
00080 template <typename I, typename N, typename L,
00081 typename S, typename F>
00082 mln_ch_value(I, L)
00083 labeling(const Image<I>& input_, const Neighborhood<N>& nbh_,
00084 L& nlabels, const Site_Set<S>& s_, F& f)
00085 {
00086 trace::entering("canvas::labeling::impl::generic::labeling");
00087
00088
00089
00090 const I& input = exact(input_);
00091 const N& nbh = exact(nbh_);
00092 const S& s = exact(s_);
00093
00094
00095 typedef mln_psite(I) P;
00096
00097
00098 mln_ch_value(I, bool) deja_vu;
00099 mln_ch_value(I, P) parent;
00100
00101
00102 mln_ch_value(I, L) output;
00103 bool status;
00104
00105
00106 {
00107 initialize(deja_vu, input);
00108 mln::data::fill(deja_vu, false);
00109
00110 initialize(parent, input);
00111
00112 initialize(output, input);
00113 mln::data::fill(output, L(literal::zero));
00114 nlabels = 0;
00115
00116 f.init();
00117 }
00118
00119
00120 {
00121 mln_bkd_piter(S) p(s);
00122 mln_niter(N) n(nbh, p);
00123 for_all(p) if (f.handles(p))
00124 {
00125
00126 parent(p) = p;
00127 f.init_attr(p);
00128
00129 for_all(n)
00130 if (input.domain().has(n) && deja_vu(n))
00131 {
00132 if (f.equiv(n, p))
00133 {
00134
00135 P r = find_root(parent, n);
00136 if (r != p)
00137 {
00138 parent(r) = p;
00139 f.merge_attr(r, p);
00140 }
00141 }
00142 else
00143 f.do_no_union(n, p);
00144 }
00145 deja_vu(p) = true;
00146 }
00147 }
00148
00149
00150 {
00151 mln_fwd_piter(S) p(s);
00152 for_all(p) if (f.handles(p))
00153 {
00154 if (parent(p) == p)
00155 {
00156 if (f.labels(p))
00157 {
00158 if (nlabels == mln_max(L))
00159 {
00160 status = false;
00161 trace::warning("labeling aborted! Too many labels \
00162 for this label type: nlabels > \
00163 max(label_type).");
00164
00165 return output;
00166 }
00167 output(p) = ++nlabels;
00168 }
00169 }
00170 else
00171 output(p) = output(parent(p));
00172 }
00173 status = true;
00174 }
00175
00176 trace::exiting("canvas::labeling::impl::generic::labeling");
00177 return output;
00178 }
00179
00180 # endif // ! MLN_INCLUDE_ONLY
00181
00182 }
00183
00184 }
00185
00186 }
00187
00188 }
00189
00190 }
00191
00192
00193 #endif // ! MLN_CANVAS_LABELING_GENERIC_HH