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_DISTANCE_FRONT_HH
00027 # define MLN_CANVAS_DISTANCE_FRONT_HH
00028
00032
00033 # include <vector>
00034 # include <mln/core/concept/image.hh>
00035 # include <mln/core/concept/neighborhood.hh>
00036 # include <mln/core/concept/weighted_window.hh>
00037 # include <mln/data/fill.hh>
00038 # include <mln/accu/stat/max.hh>
00039 # include <mln/extension/adjust_fill.hh>
00040
00041
00042 namespace mln
00043 {
00044
00045 namespace canvas
00046 {
00047
00049 template <typename I,
00050 typename N, typename W, typename D,
00051 typename F>
00052 mln_ch_value(I, D)
00053 distance_front(const Image<I>& input,
00054 const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win, D max,
00055 F& functor);
00056
00057
00058
00059 # ifndef MLN_INCLUDE_ONLY
00060
00061
00062
00063
00064 namespace internal
00065 {
00066
00067 template <typename I,
00068 typename N, typename W, typename D,
00069 typename F>
00070 void
00071 distance_front_tests(const Image<I>& input_,
00072 const Neighborhood<N>& nbh_,
00073 const Weighted_Window<W>& w_win_,
00074 D max,
00075 F& functor)
00076 {
00077 const I& input = exact(input_);
00078 const N& nbh = exact(nbh_);
00079 const W& w_win = exact(w_win_);
00080
00081 mln_precondition(input.is_valid());
00082 mln_precondition(nbh.is_valid());
00083
00084 (void) input;
00085 (void) nbh;
00086 (void) max;
00087 (void) functor;
00088 (void) w_win;
00089 }
00090
00091
00092 }
00093
00094
00095
00096
00097
00098 namespace impl
00099 {
00100
00101 namespace generic
00102 {
00103
00104 template <typename I,
00105 typename N, typename W, typename D,
00106 typename F>
00107 mln_ch_value(I, D)
00108 distance_front(const Image<I>& input_,
00109 const Neighborhood<N>& nbh_,
00110 const Weighted_Window<W>& w_win_,
00111 D max,
00112 F& functor)
00113 {
00114 trace::entering("canvas::impl::generic::distance_front");
00115
00116 const I& input = exact(input_);
00117 const N& nbh = exact(nbh_);
00118 const W& w_win = exact(w_win_);
00119
00120 mln_precondition(input.is_valid());
00121 mln_precondition(w_win.is_valid());
00122
00123 typedef mln_site(I) P;
00124 typedef std::vector<P> bucket_t;
00125
00126
00127 mln_ch_value(I, D) dmap;
00128 initialize(dmap, input);
00129 data::fill(dmap, max);
00130
00131
00132 unsigned mod;
00133 {
00134 accu::stat::max<unsigned> m;
00135 for (unsigned i = 0; i < w_win.size(); ++i)
00136 m.take(w_win.w(i));
00137 mod = unsigned(m) + 1;
00138 }
00139
00140
00141 std::vector<bucket_t> bucket(mod);
00142 unsigned bucket_size = 0;
00143
00144
00145 {
00146 functor.init(input);
00147 mln_piter(I) p(input.domain());
00148 mln_niter(N) n(nbh, p);
00149 for_all(p)
00150 if (functor.inqueue_p_wrt_input_p(input(p)))
00151 {
00152 dmap(p) = 0;
00153 for_all(n)
00154 if (input.domain().has(n) &&
00155 functor.inqueue_p_wrt_input_n(input(n)))
00156 {
00157 bucket[0].push_back(p);
00158 ++bucket_size;
00159 break;
00160 }
00161 }
00162 }
00163
00164
00165 {
00166 P p;
00167 mln_qiter(W) q(w_win, p);
00168 for (unsigned d = 0; bucket_size != 0; ++d)
00169 {
00170 bucket_t& bucket_d = bucket[d % mod];
00171 for (unsigned i = 0; i < bucket_d.size(); ++i)
00172 {
00173 p = bucket_d[i];
00174
00175 if (dmap(p) == max)
00176 {
00177
00178 bucket_size = bucket_d.size();
00179 break;
00180 }
00181
00182 if (dmap(p) < d)
00183
00184 continue;
00185
00186 for_all(q)
00187 if (dmap.domain().has(q) && dmap(q) > d)
00188 {
00189 unsigned d_ = d + q.w();
00190 if (d_ < dmap(q))
00191 {
00192 dmap(q) = d_;
00193 functor.process(p, q);
00194 bucket[d_ % mod].push_back(q);
00195 ++bucket_size;
00196 }
00197 }
00198 }
00199 bucket_size -= bucket_d.size();
00200 bucket_d.clear();
00201 }
00202 }
00203
00204 trace::exiting("canvas::impl::generic::distance_front");
00205 return dmap;
00206 }
00207
00208 }
00209
00210
00211
00212
00213
00214 template <typename I,
00215 typename N, typename W, typename D,
00216 typename F>
00217 mln_ch_value(I, D)
00218 distance_front_fastest(const Image<I>& input_,
00219 const Neighborhood<N>& nbh_,
00220 const Weighted_Window<W>& w_win_,
00221 D max, F& functor)
00222 {
00223 trace::entering("canvas::impl::distance_front_fastest");
00224
00225 const I& input = exact(input_);
00226 const N& nbh = exact(nbh_);
00227 const W& w_win = exact(w_win_);
00228
00229 mln_precondition(input.is_valid());
00230 mln_precondition(w_win.is_valid());
00231
00232
00233 extension::adjust(input, w_win);
00234 const unsigned n_ws = w_win.size();
00235 util::array<int> dp = offsets_wrt(input, w_win.win());
00236 mln_invariant(dp.nelements() == n_ws);
00237
00238
00239 mln_ch_value(I, D) dmap;
00240 initialize(dmap, input);
00241 data::fill(dmap, max);
00242
00243
00244 unsigned mod;
00245 {
00246 accu::stat::max<unsigned> m;
00247 for (unsigned i = 0; i < w_win.size(); ++i)
00248 m.take(w_win.w(i));
00249 mod = unsigned(m) + 1;
00250 }
00251
00252
00253 typedef std::vector<unsigned> bucket_t;
00254 std::vector<bucket_t> bucket(mod);
00255 unsigned bucket_size = 0;
00256
00257
00258 {
00259 functor.init_(input);
00260
00261
00262 extension::fill(input, true);
00263 extension::fill(dmap, D(0));
00264
00265 mln_pixter(const I) p(input);
00266 mln_nixter(const I, N) n(p, nbh);
00267 for_all(p)
00268 if (functor.inqueue_p_wrt_input_p_(p.val()))
00269 {
00270 dmap.element(p.offset()) = 0;
00271 for_all(n)
00272 if (functor.inqueue_p_wrt_input_n_(n.val()))
00273 {
00274 bucket[0].push_back(p.offset());
00275 ++bucket_size;
00276 break;
00277 }
00278 }
00279 }
00280
00281
00282 {
00283 unsigned p;
00284
00285 for (unsigned d = 0; bucket_size != 0; ++d)
00286 {
00287 bucket_t& bucket_d = bucket[d % mod];
00288 for (unsigned i = 0; i < bucket_d.size(); ++i)
00289 {
00290 p = bucket_d[i];
00291
00292 if (dmap.element(p) == max)
00293 {
00294
00295 bucket_size = bucket_d.size();
00296 break;
00297 }
00298
00299 if (dmap.element(p) < d)
00300
00301 continue;
00302
00303 for (unsigned i = 0; i < n_ws; ++i)
00304 {
00305 unsigned q = p + dp[i];
00306 if (dmap.element(q) > d)
00307 {
00308 unsigned d_ = d + w_win.w(i);
00309 if (d_ < dmap.element(q))
00310 {
00311 dmap.element(q) = d_;
00312 functor.process_(p, q);
00313 bucket[d_ % mod].push_back(q);
00314 ++bucket_size;
00315 }
00316 }
00317 }
00318 }
00319 bucket_size -= bucket_d.size();
00320 bucket_d.clear();
00321 }
00322 }
00323
00324 trace::exiting("canvas::impl::distance_front_fastest");
00325 return dmap;
00326 }
00327
00328
00329 }
00330
00331
00332
00333
00334
00335 namespace internal
00336 {
00337
00338 template <typename I,
00339 typename N, typename W, typename D,
00340 typename F>
00341 inline
00342 mln_ch_value(I, D)
00343 distance_front_dispatch(metal::false_,
00344 const Image<I>& input,
00345 const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win,
00346 D max, F& functor)
00347 {
00348 return impl::generic::distance_front(input, nbh, max, w_win, functor);
00349 }
00350
00351 template <typename I,
00352 typename N, typename W, typename D,
00353 typename F>
00354 inline
00355 mln_ch_value(I, D)
00356 distance_front_dispatch(metal::true_,
00357 const Image<I>& input,
00358 const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win,
00359 D max, F& functor)
00360 {
00361 return impl::distance_front_fastest(input, nbh, w_win, max, functor);
00362 }
00363
00364 template <typename I,
00365 typename N, typename W, typename D,
00366 typename F>
00367 inline
00368 mln_ch_value(I, D)
00369 distance_front_dispatch(const Image<I>& input,
00370 const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win,
00371 D max, F& functor)
00372 {
00373 enum {
00374 test = mlc_equal(mln_trait_image_speed(I),
00375 trait::image::speed::fastest)::value
00376 &&
00377 mln_is_simple_neighborhood(N)::value
00378 &&
00379 mln_is_simple_weighted_window(W)::value
00380 };
00381 return distance_front_dispatch(metal::bool_<test>(),
00382 input, nbh, w_win, max, functor);
00383 }
00384
00385
00386 }
00387
00388
00389
00390
00391
00392 template <typename I,
00393 typename N, typename W, typename D,
00394 typename F>
00395 inline
00396 mln_ch_value(I, D)
00397 distance_front(const Image<I>& input,
00398 const Neighborhood<N>& nbh, const Weighted_Window<W>& w_win,
00399 D max, F& functor)
00400 {
00401 trace::entering("canvas::distance_front");
00402
00403 internal::distance_front_tests(input, nbh, w_win, max, functor);
00404
00405 mln_ch_value(I,D) output;
00406 output = internal::distance_front_dispatch(input, nbh, w_win, max, functor);
00407
00408 trace::exiting("canvas::distance_front");
00409 return output;
00410 }
00411
00412
00413 # endif // ! MLN_INCLUDE_ONLY
00414
00415 }
00416
00417 }
00418
00419
00420 #endif // ! MLN_CANVAS_DISTANCE_FRONT_HH