Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 // Tests. 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 } // of namespace mln::canvas::internal 00093 00094 00095 00096 // Implementations. 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 // Distance map. 00127 mln_ch_value(I, D) dmap; 00128 initialize(dmap, input); 00129 data::fill(dmap, max); 00130 00131 // Mod determination. 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 // Aux data. 00141 std::vector<bucket_t> bucket(mod); 00142 unsigned bucket_size = 0; 00143 00144 // Initialization. 00145 { 00146 functor.init(input); // <-- init 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))) // <-- inqueue_p_wrt_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))) // <-- inqueue_p_wrt_input_n 00156 { 00157 bucket[0].push_back(p); 00158 ++bucket_size; 00159 break; 00160 } 00161 } 00162 } // end of Initialization. 00163 00164 // Propagation. 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 // Saturation so stop. 00178 bucket_size = bucket_d.size(); // So at end bucket_size == 0. 00179 break; 00180 } 00181 00182 if (dmap(p) < d) 00183 // p has already been processed, having a distance less than d. 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); // <- process 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 } // end of Propagation. 00203 00204 trace::exiting("canvas::impl::generic::distance_front"); 00205 return dmap; 00206 } 00207 00208 } // of namespace mln::canvas::impl::generic 00209 00210 00211 00212 // Fastest version. 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 // Handling w_win. 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 // Distance map. 00239 mln_ch_value(I, D) dmap; 00240 initialize(dmap, input); 00241 data::fill(dmap, max); 00242 00243 // Mod determination. 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 // Aux data. 00253 typedef std::vector<unsigned> bucket_t; 00254 std::vector<bucket_t> bucket(mod); 00255 unsigned bucket_size = 0; 00256 00257 // Initialization. 00258 { 00259 functor.init_(input); // <-- init 00260 00261 // For the extension to be ignored: 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())) // <-- inqueue_p_wrt_input_p 00269 { 00270 dmap.element(p.offset()) = 0; 00271 for_all(n) 00272 if (functor.inqueue_p_wrt_input_n_(n.val())) // <-- inqueue_p_wrt_input_n 00273 { 00274 bucket[0].push_back(p.offset()); 00275 ++bucket_size; 00276 break; 00277 } 00278 } 00279 } // end of Initialization. 00280 00281 // Propagation. 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 // Saturation so stop. 00295 bucket_size = bucket_d.size(); // So at end bucket_size == 0. 00296 break; 00297 } 00298 00299 if (dmap.element(p) < d) 00300 // p has already been processed, having a distance less than d. 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); // <- process 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 } // end of Propagation. 00323 00324 trace::exiting("canvas::impl::distance_front_fastest"); 00325 return dmap; 00326 } 00327 00328 00329 } // of namespace mln::canvas::impl 00330 00331 00332 00333 // Dispatch. 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, w_win, max, 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 } // of namespace mln::canvas::internal 00387 00388 00389 00390 // Facade. 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 } // end of namespace mln::canvas 00416 00417 } // end of namespace mln 00418 00419 00420 #endif // ! MLN_CANVAS_DISTANCE_FRONT_HH