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_SORTED_HH
00027 # define MLN_CANVAS_LABELING_SORTED_HH
00028
00032
00033
00034 # include <mln/core/concept/image.hh>
00035 # include <mln/data/fill.hh>
00036 # include <mln/literal/zero.hh>
00037 # include <mln/extension/adjust_fill.hh>
00038
00039 # include <mln/data/sort_psites.hh>
00040 # include <mln/data/sort_offsets.hh>
00041
00042 # include <mln/canvas/labeling/generic.hh>
00043 # include <mln/canvas/labeling/internal/tests.hh>
00044 # include <mln/canvas/labeling/internal/find_root_fastest.hh>
00045
00046
00047
00048 namespace mln
00049 {
00050
00051 namespace canvas
00052 {
00053
00054 namespace labeling
00055 {
00056
00057 template <typename I, typename N, typename L, typename F>
00058 inline
00059 mln_ch_value(I, L)
00060 sorted(const Image<I>& input, const Neighborhood<N>& nbh,
00061 L& nlabels, F& functor, bool increasing);
00062
00063
00064 # ifndef MLN_INCLUDE_ONLY
00065
00066
00067
00068
00069 namespace impl
00070 {
00071
00072
00073
00074 template <typename I, typename N, typename L,
00075 typename S, typename F>
00076 mln_ch_value(I, L)
00077 sorted_fastest(const Image<I>& input_,
00078 const Neighborhood<N>& nbh_, L& nlabels,
00079 const S& s, F& f)
00080 {
00081 trace::entering("canvas::impl::labeling::sorted_fastest");
00082
00083
00084
00085 const I& input = exact(input_);
00086 const N& nbh = exact(nbh_);
00087
00088 extension::adjust(input, nbh);
00089
00090
00091 typedef mln_psite(I) P;
00092
00093
00094 mln_ch_value(I, bool) deja_vu;
00095 mln_ch_value(I, unsigned) parent;
00096
00097
00098 mln_ch_value(I, L) output;
00099 bool status;
00100
00101
00102 {
00103 initialize(deja_vu, input);
00104 mln::data::fill(deja_vu, false);
00105 extension::fill(deja_vu, false);
00106
00107 initialize(parent, input);
00108
00109 initialize(output, input);
00110 mln::data::fill(output, L(literal::zero));
00111 nlabels = 0;
00112
00113 f.init_();
00114 }
00115
00116 util::array<int> dp = offsets_wrt(input, nbh);
00117 const unsigned n_nbhs = dp.nelements();
00118
00119 const unsigned n_points = s.nelements();
00120
00121
00122 {
00123 for (int i = n_points - 1; i >=0; --i)
00124 {
00125 unsigned p = s[i];
00126 if (! f.handles_(p))
00127 continue;
00128
00129
00130 parent.element(p) = p;
00131 f.init_attr_(p);
00132
00133 for (unsigned j = 0; j < n_nbhs; ++j)
00134 {
00135 unsigned n = p + dp[j];
00136 if (! deja_vu.element(n))
00137 continue;
00138
00139 if (f.equiv_(n, p))
00140 {
00141
00142 unsigned r = internal::find_root_fastest(parent, n);
00143 if (r != p)
00144 {
00145 parent.element(r) = p;
00146 f.merge_attr_(r, p);
00147 }
00148 }
00149 else
00150 f.do_no_union_(n, p);
00151 }
00152 deja_vu.element(p) = true;
00153 }
00154 }
00155
00156
00157 {
00158 for (unsigned i = 0; i < n_points; ++i)
00159 {
00160 unsigned p = s[i];
00161 if (! f.handles_(p))
00162 continue;
00163
00164 if (parent.element(p) == p)
00165 {
00166 if (f.labels_(p))
00167 {
00168 if (nlabels == mln_max(L))
00169 {
00170 status = false;
00171 trace::warning("labeling aborted! Too many labels \
00172 for this label type: nlabels > \
00173 max(label_type).");
00174 return output;
00175 }
00176 output.element(p) = ++nlabels;
00177 }
00178 }
00179 else
00180 output.element(p) = output.element(parent.element(p));
00181 }
00182 status = true;
00183 }
00184
00185 trace::exiting("canvas::impl::labeling::sorted_fastest");
00186 return output;
00187 }
00188
00189 }
00190
00191
00192
00193
00194 namespace internal
00195 {
00196
00197 template <typename I, typename N, typename L, typename F>
00198 inline
00199 mln_ch_value(I, L)
00200 sorted_dispatch(metal::false_,
00201 const Image<I>& input,
00202 const Neighborhood<N>& nbh, L& nlabels,
00203 F& functor, bool increasing)
00204 {
00205 p_array<mln_psite(I)> s =
00206 increasing ?
00207 data::sort_psites_increasing(input) :
00208 data::sort_psites_decreasing(input);
00209 return impl::generic::labeling(input, nbh, nlabels, s,
00210 functor);
00211 }
00212
00213 template <typename I, typename N, typename L, typename F>
00214 inline
00215 mln_ch_value(I, L)
00216 sorted_dispatch(metal::true_,
00217 const Image<I>& input,
00218 const Neighborhood<N>& nbh, L& nlabels,
00219 F& functor, bool increasing)
00220 {
00221 util::array<unsigned> s =
00222 increasing ?
00223 data::sort_offsets_increasing(input) :
00224 data::sort_offsets_decreasing(input);
00225 return impl::sorted_fastest(input, nbh, nlabels, s,
00226 functor);
00227 }
00228
00229 template <typename I, typename N, typename L, typename F>
00230 inline
00231 mln_ch_value(I, L)
00232 sorted_dispatch(const Image<I>& input,
00233 const Neighborhood<N>& nbh, L& nlabels,
00234 F& functor, bool increasing)
00235 {
00236 enum {
00237 test = mlc_equal(mln_trait_image_speed(I),
00238 trait::image::speed::fastest)::value
00239 &&
00240 mln_is_simple_neighborhood(N)::value
00241 };
00242 return sorted_dispatch(metal::bool_<test>(),
00243 input, nbh, nlabels,
00244 functor, increasing);
00245 }
00246
00247
00248 }
00249
00250
00251
00252
00253
00254
00255 template <typename I, typename N, typename L, typename F>
00256 inline
00257 mln_ch_value(I, L)
00258 sorted(const Image<I>& input, const Neighborhood<N>& nbh,
00259 L& nlabels, F& functor, bool increasing)
00260 {
00261 trace::entering("canvas::labeling::sorted");
00262
00263 internal::labeling_tests(input, nbh, nlabels, functor);
00264
00265 mln_ch_value(I, L) output;
00266 output = internal::sorted_dispatch(input, nbh, nlabels,
00267 functor, increasing);
00268
00269 trace::exiting("canvas::labeling::sorted");
00270 return output;
00271 }
00272
00273
00274 # endif // ! MLN_INCLUDE_ONLY
00275
00276 }
00277
00278 }
00279
00280 }
00281
00282
00283 #endif // ! MLN_CANVAS_LABELING_SORTED_HH