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_MORPHO_WATERSHED_FLOODING_HH 00027 # define MLN_MORPHO_WATERSHED_FLOODING_HH 00028 00040 00041 # include <mln/trait/ch_value.hh> 00042 00043 # include <mln/morpho/includes.hh> 00044 # include <mln/literal/zero.hh> 00045 # include <mln/labeling/regional_minima.hh> 00046 00047 # include <mln/core/site_set/p_queue_fast.hh> 00048 # include <mln/core/site_set/p_priority.hh> 00049 00050 # include <mln/extension/adjust_fill.hh> 00051 00052 00053 namespace mln 00054 { 00055 00056 namespace morpho 00057 { 00058 00059 namespace watershed 00060 { 00061 00073 00074 template <typename L, typename I, typename N> 00075 mln_ch_value(I, L) 00076 flooding(const Image<I>& input, const Neighborhood<N>& nbh, 00077 L& n_basins); 00078 00095 template <typename L, typename I, typename N> 00096 mln_ch_value(I, L) 00097 flooding(const Image<I>& input, const Neighborhood<N>& nbh); 00098 00099 00100 00101 # ifndef MLN_INCLUDE_ONLY 00102 00103 00104 // Implementations. 00105 00106 namespace impl 00107 { 00108 00109 namespace generic 00110 { 00111 00112 template <typename L, typename I, typename N> 00113 mln_ch_value(I, L) 00114 flooding(const Image<I>& input_, const Neighborhood<N>& nbh_, 00115 L& n_basins) 00116 { 00117 trace::entering("morpho::watershed::impl::generic::flooding"); 00118 /* FIXME: Ensure the input image has scalar values. */ 00119 00120 const I input = exact(input_); 00121 const N nbh = exact(nbh_); 00122 00123 typedef L marker; 00124 const marker unmarked = literal::zero; 00125 00126 typedef mln_value(I) V; 00127 const V max = mln_max(V); 00128 00129 // Initialize the output with the markers (minima components). 00130 mln_ch_value(I, marker) output = 00131 labeling::regional_minima (input, nbh, n_basins); 00132 00133 typedef mln_psite(I) psite; 00134 00135 // Ordered queue. 00136 typedef p_queue_fast<psite> Q; 00137 p_priority<V, Q> queue; 00138 00139 // In_queue structure to avoid processing sites several times. 00140 mln_ch_value(I, bool) in_queue; 00141 initialize(in_queue, input); 00142 data::fill(in_queue, false); 00143 00144 // Insert every neighbor P of every marked area in a 00145 // hierarchical queue, with a priority level corresponding to 00146 // the grey level input(P). 00147 mln_piter(I) p(output.domain()); 00148 mln_niter(N) n(nbh, p); 00149 for_all(p) 00150 if (output(p) == unmarked) 00151 for_all(n) 00152 if (output.domain().has(n) && output(n) != unmarked) 00153 { 00154 queue.push(max - input(p), p); 00155 in_queue(p) = true; 00156 break; 00157 } 00158 00159 /* Until the queue is empty, extract a psite P from the 00160 hierarchical queue, at the highest priority level, that is, 00161 the lowest level. */ 00162 while (! queue.is_empty()) 00163 { 00164 psite p = queue.front(); 00165 queue.pop(); 00166 00167 // Last seen marker adjacent to P. 00168 marker adjacent_marker = unmarked; 00169 // Has P a single adjacent marker? 00170 bool single_adjacent_marker_p = true; 00171 mln_niter(N) n(nbh, p); 00172 for_all(n) 00173 if (output.domain().has(n) && output(n) != unmarked) 00174 { 00175 if (adjacent_marker == unmarked) 00176 { 00177 adjacent_marker = output(n); 00178 single_adjacent_marker_p = true; 00179 } 00180 else 00181 if (adjacent_marker != output(n)) 00182 { 00183 single_adjacent_marker_p = false; 00184 break; 00185 } 00186 } 00187 /* If the neighborhood of P contains only psites with the 00188 same label, then P is marked with this label, and its 00189 neighbors that are not yet marked are put into the 00190 hierarchical queue. */ 00191 if (single_adjacent_marker_p) 00192 { 00193 output(p) = adjacent_marker; 00194 for_all(n) 00195 if (output.domain().has(n) && output(n) == unmarked 00196 && ! in_queue(n)) 00197 { 00198 queue.push(max - input(n), n); 00199 in_queue(n) = true; 00200 } 00201 } 00202 } 00203 00204 trace::exiting("morpho::watershed::impl::generic::flooding"); 00205 return output; 00206 } 00207 00208 } // end of namespace mln::morpho::watershed::impl::generic 00209 00210 00211 00212 // Fastest version. 00213 00214 template <typename I, typename N, typename L> 00215 mln_ch_value(I, L) 00216 flooding_fastest(const Image<I>& input_, const Neighborhood<N>& nbh_, 00217 L& n_basins) 00218 { 00219 trace::entering("morpho::watershed::impl::flooding_fastest"); 00220 /* FIXME: Ensure the input image has scalar values. */ 00221 00222 const I input = exact(input_); 00223 const N nbh = exact(nbh_); 00224 00225 typedef L marker; 00226 const marker unmarked = literal::zero; 00227 00228 typedef mln_value(I) V; 00229 const V max = mln_max(V); 00230 00231 extension::adjust_fill(input, nbh, max); 00232 00233 // Initialize the output with the markers (minima components). 00234 typedef mln_ch_value(I, L) O; 00235 O output = labeling::regional_minima(input, nbh, n_basins); 00236 extension::fill(output, unmarked); 00237 00238 // Ordered queue. 00239 typedef p_queue_fast<unsigned> Q; 00240 p_priority<V, Q> queue; 00241 00242 // FIXME: With typedef std::pair<V, unsigned> VU; 00243 // std::priority_queue<VU> queue; 00244 // we do not get the same results!!! 00245 00246 // In_queue structure to avoid processing sites several times. 00247 mln_ch_value(I, bool) in_queue; 00248 initialize(in_queue, input); 00249 data::fill(in_queue, false); 00250 extension::fill(in_queue, true); 00251 00252 // Insert every neighbor P of every marked area in a 00253 // hierarchical queue, with a priority level corresponding to 00254 // the grey level input(P). 00255 mln_pixter(const O) p_out(output); 00256 mln_nixter(const O, N) n_out(p_out, nbh); 00257 for_all(p_out) 00258 if (p_out.val() == unmarked) 00259 for_all(n_out) 00260 if (n_out.val() != unmarked) 00261 { 00262 unsigned po = p_out.offset(); 00263 queue.push(max - input.element(po), po); 00264 in_queue.element(po) = true; 00265 break; 00266 } 00267 00268 /* Until the queue is empty, extract a psite P from the 00269 hierarchical queue, at the highest priority level, that is, 00270 the lowest level. */ 00271 util::array<int> dp = offsets_wrt(input, nbh); 00272 const unsigned n_nbhs = dp.nelements(); 00273 while (! queue.is_empty()) 00274 { 00275 unsigned p = queue.front(); 00276 queue.pop(); 00277 00278 // Last seen marker adjacent to P. 00279 marker adjacent_marker = unmarked; 00280 // Has P a single adjacent marker? 00281 bool single_adjacent_marker_p = true; 00282 for (unsigned i = 0; i < n_nbhs; ++i) 00283 { 00284 unsigned n = p + dp[i]; 00285 // In the border, output is unmarked so N is ignored. 00286 if (output.element(n) != unmarked) 00287 { 00288 if (adjacent_marker == unmarked) 00289 { 00290 adjacent_marker = output.element(n); 00291 single_adjacent_marker_p = true; 00292 } 00293 else 00294 if (adjacent_marker != output.element(n)) 00295 { 00296 single_adjacent_marker_p = false; 00297 break; 00298 } 00299 } 00300 } 00301 /* If the neighborhood of P contains only psites with the 00302 same label, then P is marked with this label, and its 00303 neighbors that are not yet marked are put into the 00304 hierarchical queue. */ 00305 if (single_adjacent_marker_p) 00306 { 00307 output.element(p) = adjacent_marker; 00308 for (unsigned i = 0; i < n_nbhs; ++i) 00309 { 00310 unsigned n = p + dp[i]; 00311 if (output.element(n) == unmarked 00312 // In the border, in_queue is true so N is ignored. 00313 && ! in_queue.element(n)) 00314 { 00315 queue.push(max - input.element(n), n); 00316 in_queue.element(n) = true; 00317 } 00318 } 00319 } 00320 } 00321 00322 trace::exiting("morpho::watershed::impl::flooding_fastest"); 00323 return output; 00324 } 00325 00326 00327 } // end of namespace mln::morpho::watershed::impl 00328 00329 00330 00331 // Dispatch. 00332 00333 namespace internal 00334 { 00335 00336 template <typename I, typename N, typename L> 00337 inline 00338 mln_ch_value(I, L) 00339 flooding_dispatch(metal::false_, 00340 const Image<I>& input, const Neighborhood<N>& nbh, 00341 L& n_basins) 00342 { 00343 return impl::generic::flooding(input, nbh, n_basins); 00344 } 00345 00346 00347 template <typename I, typename N, typename L> 00348 inline 00349 mln_ch_value(I, L) 00350 flooding_dispatch(metal::true_, 00351 const Image<I>& input, const Neighborhood<N>& nbh, 00352 L& n_basins) 00353 { 00354 return impl::flooding_fastest(input, nbh, n_basins); 00355 } 00356 00357 template <typename I, typename N, typename L> 00358 inline 00359 mln_ch_value(I, L) 00360 flooding_dispatch(const Image<I>& input, const Neighborhood<N>& nbh, 00361 L& n_basins) 00362 { 00363 enum { 00364 test = mlc_equal(mln_trait_image_speed(I), 00365 trait::image::speed::fastest)::value 00366 && 00367 mln_is_simple_neighborhood(N)::value 00368 }; 00369 return flooding_dispatch(metal::bool_<test>(), 00370 input, nbh, n_basins); 00371 } 00372 00373 } // end of namespace mln::morpho::watershed::internal 00374 00375 00376 // Facades. 00377 00378 template <typename L, typename I, typename N> 00379 inline 00380 mln_ch_value(I, L) 00381 flooding(const Image<I>& input, const Neighborhood<N>& nbh, L& n_basins) 00382 { 00383 trace::entering("morpho::watershed::flooding"); 00384 00385 // FIXME: internal::flooding_tests(input, nbh, n_basins); 00386 00387 mln_ch_value(I, L) output = 00388 internal::flooding_dispatch(input, nbh, n_basins); 00389 00390 trace::exiting("morpho::watershed::flooding"); 00391 return output; 00392 } 00393 00394 template <typename L, typename I, typename N> 00395 mln_ch_value(I, L) 00396 flooding(const Image<I>& input, const Neighborhood<N>& nbh) 00397 { 00398 L nbasins; 00399 return flooding<L>(input, nbh, nbasins); 00400 } 00401 00402 # endif // ! MLN_INCLUDE_ONLY 00403 00404 } // end of namespace mln::morpho::watershed 00405 00406 } // end of namespace mln::morpho 00407 00408 } // end of namespace mln 00409 00410 00411 #endif // ! MLN_MORPHO_WATERSHED_FLOODING_HH