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_GEODESIC_HH
00027 # define MLN_CANVAS_DISTANCE_GEODESIC_HH
00028
00032
00033 # include <mln/core/concept/image.hh>
00034 # include <mln/core/concept/neighborhood.hh>
00035 # include <mln/core/routine/duplicate.hh>
00036
00037 # include <mln/core/site_set/p_queue_fast.hh>
00038 # include <queue>
00039
00040 # include <mln/data/fill.hh>
00041 # include <mln/extension/adjust_fill.hh>
00042
00043
00044 namespace mln
00045 {
00046
00047 namespace canvas
00048 {
00049
00051 template <typename I, typename N, typename D,
00052 typename F>
00053 mln_ch_value(I, D)
00054 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, 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, typename N, typename D,
00068 typename F>
00069 void
00070 distance_geodesic_tests(const Image<I>& input_, const Neighborhood<N>& nbh_, D max,
00071 F& functor)
00072 {
00073 const I& input = exact(input_);
00074 const N& nbh = exact(nbh_);
00075
00076 mln_precondition(input.is_valid());
00077 mln_precondition(nbh.is_valid());
00078
00079 (void) input;
00080 (void) nbh;
00081 (void) max;
00082 (void) functor;
00083 }
00084
00085
00086 }
00087
00088
00089
00090
00091
00092 namespace impl
00093 {
00094
00095 namespace generic
00096 {
00097
00098 template <typename I, typename N, typename D,
00099 typename F>
00100 mln_ch_value(I, D)
00101 distance_geodesic(const Image<I>& input_, const Neighborhood<N>& nbh_, D max,
00102 F& functor)
00103 {
00104 trace::entering("canvas::impl::generic::distance_geodesic");
00105
00106 const I& input = exact(input_);
00107 const N& nbh = exact(nbh_);
00108
00109 internal::distance_geodesic_tests(input, nbh, max, functor);
00110
00111 mln_precondition(input.is_valid());
00112 mln_precondition(nbh.is_valid());
00113
00114 mln_ch_value(I, D) dmap;
00115 initialize(dmap, input);
00116
00117 typedef mln_site(I) P;
00118 p_queue_fast<P> q;
00119
00120
00121 {
00122 trace::entering("initialization");
00123
00124 functor.init(input);
00125 data::fill(dmap, max);
00126
00127 mln_piter(I) p(input.domain());
00128 mln_niter(N) n(nbh, p);
00129 for_all(p)
00130 if (functor.inqueue_p_wrt_input_p(input(p)))
00131 {
00132 functor.init_p(p);
00133 dmap(p) = 0;
00134 for_all(n)
00135 if (input.domain().has(n) &&
00136 functor.inqueue_p_wrt_input_n(input(n)))
00137 {
00138 q.push(p);
00139 break;
00140 }
00141 }
00142 trace::exiting("initialization");
00143 }
00144
00145
00146 {
00147 trace::entering("propagation");
00148 P p;
00149 mln_niter(N) n(nbh, p);
00150 while (! q.is_empty())
00151 {
00152 p = q.pop_front();
00153 if (dmap(p) == max)
00154 {
00155
00156 q.clear();
00157 break;
00158 }
00159 for_all(n)
00160 if (input.domain().has(n) && dmap(n) == max)
00161 {
00162 dmap(n) = dmap(p) + 1;
00163 functor.process(p, n);
00164 q.push(n);
00165 }
00166 }
00167 trace::exiting("propagation");
00168 }
00169
00170 trace::exiting("canvas::impl::generic::distance_geodesic");
00171 return dmap;
00172 }
00173
00174 }
00175
00176
00177
00178
00179
00180 template <typename I, typename N, typename D,
00181 typename F>
00182 mln_ch_value(I, D)
00183 distance_geodesic_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, D max,
00184 F& functor)
00185 {
00186 trace::entering("canvas::impl::distance_geodesic_fastest");
00187
00188 const I& input = exact(input_);
00189 const N& nbh = exact(nbh_);
00190
00191 internal::distance_geodesic_tests(input, nbh, max, functor);
00192
00193 extension::adjust(input, nbh);
00194
00195 mln_ch_value(I, D) dmap;
00196 initialize(dmap, input);
00197
00198 std::queue<unsigned> q;
00199
00200
00201 {
00202 trace::entering("initialization");
00203
00204 functor.init_(input);
00205 data::fill(dmap, max);
00206
00207 extension::fill(input, true);
00208 extension::fill(dmap, D(0));
00209
00210 mln_pixter(const I) p(input);
00211 mln_nixter(const I, N) n(p, nbh);
00212 for_all(p)
00213 if (functor.inqueue_p_wrt_input_p_(p.val()))
00214 {
00215 functor.init_p_(p);
00216 dmap.element(p.offset()) = 0;
00217 for_all(n)
00218 if (functor.inqueue_p_wrt_input_n_(n.val()))
00219 {
00220 q.push(p.offset());
00221 break;
00222 }
00223 }
00224
00225 trace::exiting("initialization");
00226 }
00227
00228
00229 {
00230 trace::entering("propagation");
00231 unsigned p;
00232
00233 util::array<int> dp = offsets_wrt(input, nbh);
00234 const unsigned n_nbhs = dp.nelements();
00235
00236 while (! q.empty())
00237 {
00238 p = q.front();
00239 q.pop();
00240 if (dmap.element(p) == max)
00241
00242 break;
00243 for (unsigned i = 0; i < n_nbhs; ++i)
00244 {
00245 unsigned n = p + dp[i];
00246 if (dmap.element(n) == max)
00247 {
00248 dmap.element(n) = dmap.element(p) + 1;
00249 functor.process_(p, n);
00250 q.push(n);
00251 }
00252 }
00253 }
00254 trace::exiting("propagation");
00255 }
00256
00257 trace::exiting("canvas::impl::distance_geodesic_fastest");
00258 return dmap;
00259 }
00260
00261
00262 }
00263
00264
00265
00266
00267
00268 namespace internal
00269 {
00270
00271 template <typename I, typename N, typename D,
00272 typename F>
00273 inline
00274 mln_ch_value(I, D)
00275 distance_geodesic_dispatch(metal::false_,
00276 const Image<I>& input, const Neighborhood<N>& nbh, D max,
00277 F& functor)
00278 {
00279 return impl::generic::distance_geodesic(input, nbh, max,
00280 functor);
00281 }
00282
00283 template <typename I, typename N, typename D,
00284 typename F>
00285 inline
00286 mln_ch_value(I, D)
00287 distance_geodesic_dispatch(metal::true_,
00288 const Image<I>& input, const Neighborhood<N>& nbh, D max,
00289 F& functor)
00290 {
00291 return impl::distance_geodesic_fastest(input, nbh, max, functor);
00292
00293
00294 }
00295
00296 template <typename I, typename N, typename D,
00297 typename F>
00298 inline
00299 mln_ch_value(I, D)
00300 distance_geodesic_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, D max,
00301 F& functor)
00302 {
00303 enum {
00304 test = mlc_equal(mln_trait_image_speed(I),
00305 trait::image::speed::fastest)::value
00306 &&
00307 mln_is_simple_neighborhood(N)::value
00308 };
00309 return distance_geodesic_dispatch(metal::bool_<test>(),
00310 input, nbh, max,
00311 functor);
00312 }
00313
00314
00315 }
00316
00317
00318
00319
00320
00321 template <typename I, typename N, typename D,
00322 typename F>
00323 inline
00324 mln_ch_value(I, D)
00325 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, D max,
00326 F& functor)
00327 {
00328 trace::entering("canvas::distance_geodesic");
00329
00330 internal::distance_geodesic_tests(input, nbh, max, functor);
00331
00332 mln_ch_value(I,D) output;
00333 output = internal::distance_geodesic_dispatch(input, nbh, max, functor);
00334
00335 trace::exiting("canvas::distance_geodesic");
00336 return output;
00337 }
00338
00339
00340 # endif // ! MLN_INCLUDE_ONLY
00341
00342 }
00343
00344 }
00345
00346
00347 #endif // ! MLN_CANVAS_DISTANCE_GEODESIC_HH