Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2008, 2009 EPITA Research and Development Laboratory 00002 // (LRDE) 00003 // 00004 // This file is part of Olena. 00005 // 00006 // Olena is free software: you can redistribute it and/or modify it under 00007 // the terms of the GNU General Public License as published by the Free 00008 // Software Foundation, version 2 of the License. 00009 // 00010 // Olena is distributed in the hope that it will be useful, 00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 // General Public License for more details. 00014 // 00015 // You should have received a copy of the GNU General Public License 00016 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00017 // 00018 // As a special exception, you may use this file as part of a free 00019 // software project without restriction. Specifically, if other files 00020 // instantiate templates or use macros or inline functions from this 00021 // file, or you compile this file and link it with other files to produce 00022 // an executable, this file does not by itself cause the resulting 00023 // executable to be covered by the GNU General Public License. This 00024 // exception does not however invalidate any other reasons why the 00025 // executable file might be covered by the GNU General Public License. 00026 00027 #ifndef MLN_CANVAS_DISTANCE_GEODESIC_HH 00028 # define MLN_CANVAS_DISTANCE_GEODESIC_HH 00029 00033 00034 # include <mln/core/concept/image.hh> 00035 # include <mln/core/concept/neighborhood.hh> 00036 # include <mln/core/routine/duplicate.hh> 00037 00038 # include <mln/core/site_set/p_queue_fast.hh> 00039 # include <queue> 00040 00041 # include <mln/data/fill.hh> 00042 # include <mln/extension/adjust_fill.hh> 00043 00044 00045 namespace mln 00046 { 00047 00048 namespace canvas 00049 { 00050 00052 template <typename I, typename N, typename D, 00053 typename F> 00054 mln_ch_value(I, D) 00055 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, 00056 D max, F& functor); 00057 00058 00059 00060 # ifndef MLN_INCLUDE_ONLY 00061 00062 00063 // Tests. 00064 00065 namespace internal 00066 { 00067 00068 template <typename I, typename N, typename D, 00069 typename F> 00070 void 00071 distance_geodesic_tests(const Image<I>& input_, 00072 const Neighborhood<N>& nbh_, D max, 00073 F& functor) 00074 { 00075 const I& input = exact(input_); 00076 const N& nbh = exact(nbh_); 00077 00078 mln_precondition(input.is_valid()); 00079 mln_precondition(nbh.is_valid()); 00080 00081 (void) input; 00082 (void) nbh; 00083 (void) max; 00084 (void) functor; 00085 } 00086 00087 00088 } // of namespace mln::canvas::internal 00089 00090 00091 00092 // Implementations. 00093 00094 namespace impl 00095 { 00096 00097 namespace generic 00098 { 00099 00100 template <typename I, typename N, typename D, 00101 typename F> 00102 mln_ch_value(I, D) 00103 distance_geodesic(const Image<I>& input_, const Neighborhood<N>& nbh_, 00104 D max, F& functor) 00105 { 00106 trace::entering("canvas::impl::generic::distance_geodesic"); 00107 00108 const I& input = exact(input_); 00109 const N& nbh = exact(nbh_); 00110 00111 internal::distance_geodesic_tests(input, nbh, max, functor); 00112 00113 mln_precondition(input.is_valid()); 00114 mln_precondition(nbh.is_valid()); 00115 00116 mln_ch_value(I, D) dmap; // Distance map is aux data. 00117 initialize(dmap, input); 00118 00119 typedef mln_site(I) P; 00120 p_queue_fast<P> q; 00121 00122 // Initialization. 00123 { 00124 functor.init(input); // <-- init 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))) // <-- inqueue_p_wrt_input_p 00131 { 00132 functor.init_p(p); // <-- init_p 00133 dmap(p) = 0; 00134 for_all(n) 00135 if (input.domain().has(n) && 00136 functor.inqueue_p_wrt_input_n(input(n))) // <-- inqueue_p_wrt_input_n 00137 { 00138 q.push(p); 00139 break; 00140 } 00141 } 00142 } 00143 00144 // Propagation. 00145 { 00146 P p; 00147 mln_niter(N) n(nbh, p); 00148 while (! q.is_empty()) 00149 { 00150 p = q.pop_front(); 00151 if (dmap(p) == max) 00152 { 00153 // Saturation so stop. 00154 q.clear(); 00155 break; 00156 } 00157 for_all(n) 00158 if (input.domain().has(n) && dmap(n) == max) 00159 { 00160 dmap(n) = dmap(p) + 1; 00161 functor.process(p, n); // <- process 00162 q.push(n); 00163 } 00164 } 00165 } 00166 00167 trace::exiting("canvas::impl::generic::distance_geodesic"); 00168 return dmap; 00169 } 00170 00171 } // of namespace mln::canvas::impl::generic 00172 00173 00174 00175 // Fastest version. 00176 00177 template <typename I, typename N, typename D, 00178 typename F> 00179 mln_ch_value(I, D) 00180 distance_geodesic_fastest(const Image<I>& input_, 00181 const Neighborhood<N>& nbh_, 00182 D max, 00183 F& functor) 00184 { 00185 trace::entering("canvas::impl::distance_geodesic_fastest"); 00186 00187 const I& input = exact(input_); 00188 const N& nbh = exact(nbh_); 00189 00190 internal::distance_geodesic_tests(input, nbh, max, functor); 00191 00192 extension::adjust(input, nbh); 00193 00194 mln_ch_value(I, D) dmap; // Distance map is aux data. 00195 initialize(dmap, input); 00196 00197 std::queue<unsigned> q; 00198 00199 // Initialization. 00200 { 00201 functor.init_(input); // <-- init 00202 data::fill(dmap, max); 00203 // For the extension to be ignored: 00204 extension::fill(input, true); 00205 extension::fill(dmap, D(0)); 00206 00207 mln_pixter(const I) p(input); 00208 mln_nixter(const I, N) n(p, nbh); 00209 for_all(p) 00210 if (functor.inqueue_p_wrt_input_p_(p.val())) // <-- inqueue_p_wrt_input_p 00211 { 00212 functor.init_p_(p); // <-- init_p 00213 dmap.element(p.offset()) = 0; 00214 for_all(n) 00215 if (functor.inqueue_p_wrt_input_n_(n.val())) // <-- inqueue_p_wrt_input_n 00216 { 00217 q.push(p.offset()); 00218 break; 00219 } 00220 } 00221 } 00222 00223 // Propagation. 00224 { 00225 unsigned p; 00226 00227 util::array<int> dp = offsets_wrt(input, nbh); 00228 const unsigned n_nbhs = dp.nelements(); 00229 00230 while (! q.empty()) 00231 { 00232 p = q.front(); 00233 q.pop(); 00234 if (dmap.element(p) == max) 00235 // Saturation so stop. 00236 break; 00237 for (unsigned i = 0; i < n_nbhs; ++i) 00238 { 00239 unsigned n = p + dp[i]; 00240 if (dmap.element(n) == max) 00241 { 00242 dmap.element(n) = dmap.element(p) + 1; 00243 functor.process_(p, n); // <- process 00244 q.push(n); 00245 } 00246 } 00247 } 00248 } 00249 00250 trace::exiting("canvas::impl::distance_geodesic_fastest"); 00251 return dmap; 00252 } 00253 00254 00255 } // of namespace mln::canvas::impl 00256 00257 00258 00259 // Dispatch. 00260 00261 namespace internal 00262 { 00263 00264 template <typename I, typename N, typename D, 00265 typename F> 00266 inline 00267 mln_ch_value(I, D) 00268 distance_geodesic_dispatch(metal::false_, 00269 const Image<I>& input, 00270 const Neighborhood<N>& nbh, D max, 00271 F& functor) 00272 { 00273 return impl::generic::distance_geodesic(input, nbh, max, 00274 functor); 00275 } 00276 00277 template <typename I, typename N, typename D, 00278 typename F> 00279 inline 00280 mln_ch_value(I, D) 00281 distance_geodesic_dispatch(metal::true_, 00282 const Image<I>& input, 00283 const Neighborhood<N>& nbh, D max, 00284 F& functor) 00285 { 00286 return impl::distance_geodesic_fastest(input, nbh, max, functor); 00287 // return impl::generic::distance_geodesic(input, nbh, max, 00288 // functor); 00289 } 00290 00291 template <typename I, typename N, typename D, 00292 typename F> 00293 inline 00294 mln_ch_value(I, D) 00295 distance_geodesic_dispatch(const Image<I>& input, 00296 const Neighborhood<N>& nbh, D max, 00297 F& functor) 00298 { 00299 enum { 00300 test = mlc_equal(mln_trait_image_speed(I), 00301 trait::image::speed::fastest)::value 00302 && 00303 mln_is_simple_neighborhood(N)::value 00304 }; 00305 return distance_geodesic_dispatch(metal::bool_<test>(), 00306 input, nbh, max, 00307 functor); 00308 } 00309 00310 00311 } // of namespace mln::canvas::internal 00312 00313 00314 00315 // Facade. 00316 00317 template <typename I, typename N, typename D, 00318 typename F> 00319 inline 00320 mln_ch_value(I, D) 00321 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh, 00322 D max, F& functor) 00323 { 00324 trace::entering("canvas::distance_geodesic"); 00325 00326 internal::distance_geodesic_tests(input, nbh, max, functor); 00327 00328 mln_ch_value(I,D) output; 00329 output = internal::distance_geodesic_dispatch(input, nbh, max, functor); 00330 00331 trace::exiting("canvas::distance_geodesic"); 00332 return output; 00333 } 00334 00335 00336 # endif // ! MLN_INCLUDE_ONLY 00337 00338 } // end of namespace mln::canvas 00339 00340 } // end of namespace mln 00341 00342 00343 #endif // ! MLN_CANVAS_DISTANCE_GEODESIC_HH