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_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH 00027 # define MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH 00028 00045 00046 # include <mln/data/sort_psites.hh> 00047 # include <mln/data/fill.hh> 00048 00049 # include <mln/geom/nsites.hh> 00050 # include <mln/geom/translate.hh> 00051 00052 # include <mln/morpho/tree/data.hh> 00053 00054 # include <mln/util/hqueues.hh> 00055 # include <mln/util/ord.hh> 00056 00057 # include <mln/value/value_array.hh> 00058 # include <mln/value/set.hh> 00059 00060 # include <mln/util/timer.hh> 00061 00062 namespace mln 00063 { 00064 00065 namespace morpho 00066 { 00067 00068 namespace tree 00069 { 00070 00071 namespace impl 00072 { 00073 00082 template <typename I, typename N> 00083 inline 00084 data<I, p_array<mln_psite(I)> > 00085 dual_hqueue(const Image<I>& f, 00086 const Image<I>& m, 00087 const Neighborhood<N>& nbh); 00088 00089 } // end of namespace mln::morpho::tree::impl 00090 00091 00092 # ifndef MLN_INCLUDE_ONLY 00093 00094 namespace internal 00095 { 00096 00097 template <typename I, typename N, class E> 00098 struct shared_flood_args 00099 { 00100 typedef mln_psite(I) P; 00101 typedef mln_value(I) V; 00102 typedef p_array<P> S; 00103 00104 const I& f; 00105 const I& m; 00106 const N& nbh; 00107 mln_ch_value(I, P)& parent; 00108 00109 // Aux data 00110 util::hqueues<P, V>& hqueues; 00111 const E& extend; // site -> site functor. 00112 value::value_array<V, bool> is_node_at_level; 00113 value::value_array<V, P> node_at_level; 00114 mln_ch_value(I, bool) deja_vu; 00115 const value::set<V>& vset; 00116 00117 shared_flood_args(const I& f_, 00118 const I& m_, 00119 const N& neigb_, 00120 mln_ch_value(I, P)& parent_, 00121 util::hqueues<mln_psite(I), V>& hqueues_, 00122 const E& extend_) 00123 : f (f_), 00124 m (m_), 00125 nbh (neigb_), 00126 parent (parent_), 00127 hqueues (hqueues_), 00128 extend (extend_), 00129 is_node_at_level (false), 00130 vset (hqueues.vset()) 00131 { 00132 initialize(deja_vu, f); 00133 mln::data::fill(deja_vu, false); 00134 } 00135 }; 00136 00137 template <typename I> 00138 inline 00139 histo::array<mln_value(I)> 00140 compute_histo(const I& f, const I& m, mln_value(I)& hmin, mln_psite(I)& pmin) 00141 { 00142 histo::array<mln_value(I)> hm = histo::compute(m); 00143 const histo::array<mln_value(I)> hf = histo::compute(f); 00144 00145 { // Retrieve hmin. 00146 unsigned i = 0; 00147 while (hm[i] == 0) 00148 ++i; 00149 hmin = hm.vset()[i]; 00150 } 00151 00152 // Merge histograms. 00153 for (unsigned i = 0; i < hm.nvalues(); ++i) 00154 hm[i] += hf[i]; 00155 00156 // Retrieve pmin. 00157 mln_piter(I) p(m.domain()); 00158 for (p.start(); m(p) != hmin; p.next()) 00159 ; 00160 mln_assertion(p.is_valid()); 00161 pmin = p; 00162 00163 return hm; 00164 } 00165 00166 // Site -> site functor: give for all p in Domain(f), its 00167 // equivalence in the extended domain. 00168 // TODO: make it generic. It works only on boxed domain. 00169 template <typename I> 00170 struct extend 00171 { 00172 extend(const mln_psite(I)::delta& dp) 00173 : dp_ (dp) 00174 { 00175 } 00176 00177 mln_psite(I) operator() (const mln_psite(I)& p) const 00178 { 00179 return p + dp_; 00180 } 00181 00182 private: 00183 const mln_psite(I)::delta dp_; 00184 }; 00185 00186 } // end of namespace mln::morpho::tree::internal 00187 00188 namespace impl 00189 { 00190 00191 template <typename I, typename N, typename E> 00192 unsigned 00193 flood(internal::shared_flood_args<I, N, E>& args, const unsigned h_idx) 00194 { 00195 mln_assertion(args.is_node_at_level[h_idx]); 00196 00197 while (!args.hqueues[h_idx].empty()) 00198 { 00199 mln_psite(I) p = args.hqueues[h_idx].pop_front(); 00200 unsigned p_idx = args.vset.index_of(args.f(p)); 00201 00202 if (p_idx != h_idx) 00203 { // Intensity mismatch: irregular case. 00204 mln_psite(I) pext = args.extend(p); 00205 args.parent(pext) = args.node_at_level[h_idx]; 00206 00207 if (p_idx > h_idx) // Singleton with parent at h. 00208 args.parent(p) = args.node_at_level[h_idx]; 00209 else 00210 { 00211 if (!args.is_node_at_level[p_idx]) 00212 { 00213 args.is_node_at_level[p_idx] = true; 00214 args.node_at_level[p_idx] = p; 00215 } 00216 } 00217 } 00218 00219 if (p_idx <= h_idx) 00220 { 00221 if (!args.f.domain().has(args.node_at_level[p_idx]) || 00222 util::ord_strict(p, args.node_at_level[p_idx])) 00223 { // Regular case but a representative provided by the extension. 00224 args.parent(args.node_at_level[p_idx]) = p; 00225 args.node_at_level[p_idx] = p; 00226 //args.parent(p) = p; 00227 } 00228 args.parent(p) = args.node_at_level[p_idx]; 00229 } 00230 00231 00232 // Process the neighbors 00233 mln_niter(N) n(args.nbh, p); 00234 for_all(n) 00235 if (args.f.domain().has(n) && !args.deja_vu(n)) 00236 { 00237 unsigned mn = args.vset.index_of(args.m(n)); 00238 unsigned fn = args.vset.index_of(args.f(n)); 00239 args.hqueues[mn].push(n); 00240 args.deja_vu(n) = true; 00241 00242 mln_psite(I) ext = args.extend(n); 00243 // Create a node at c. 00244 { 00245 mln_psite(I) node = (fn == mn) ? n : ext; 00246 if (!args.is_node_at_level[mn]) 00247 { 00248 args.is_node_at_level[mn] = true; 00249 args.node_at_level[mn] = node; 00250 } 00251 } 00252 00253 while (mn > h_idx) 00254 mn = flood(args, mn); 00255 } 00256 } 00257 00258 // Retrieve dad. 00259 args.is_node_at_level[h_idx] = false; 00260 unsigned c = h_idx; 00261 while (c > 0 && !args.is_node_at_level[c]) 00262 --c; 00263 00264 mln_psite(I) x = args.node_at_level[h_idx]; 00265 if (c > 0) 00266 args.parent(x) = args.node_at_level[c]; 00267 else 00268 args.parent(x) = x; 00269 00270 return c; 00271 } 00272 00273 template <typename I, typename N> 00274 inline 00275 data< I, p_array<mln_psite(I)> > 00276 dual_hqueue(const Image<I>& f_, 00277 const Image<I>& m_, 00278 const Neighborhood<N>& neibh_) 00279 { 00280 trace::entering("mln::morpho::tree::impl::dual_hqueue"); 00281 00282 const I& f = exact(f_); 00283 const I& m = exact(m_); 00284 const N& nbh = exact(neibh_); 00285 00286 typedef mln_psite(I) P; 00287 typedef p_array<mln_psite(I)> S; 00288 00289 util::timer tm; 00290 tm.start(); 00291 00292 // Histo. 00293 mln_psite(I) pmin; 00294 mln_value(I) hmin; 00295 const histo::array<mln_value(I)> histo = internal::compute_histo(f, m, hmin, pmin); 00296 util::hqueues<P, mln_value(I)> hqueues(histo); 00297 00298 mln_psite(I)::delta dp(literal::zero); 00299 mln_domain(I) d_ext = f.domain(); 00300 mln_domain(I) d = f.domain(); 00301 00302 // Extend the domain. 00303 dp[0] = d.pmax()[0] - d.pmin()[0] + 1; 00304 d.pmax() += dp; 00305 d_ext.pmin() += dp; 00306 d_ext.pmax() += dp; 00307 00308 // Data. 00309 mln_concrete(I) fext; 00310 mln_ch_value(I, P) parent; 00311 p_array<mln_psite(I)> s; 00312 00313 // Initialization. 00314 fext = geom::translate(m, dp.to_vec(), f, d); 00315 initialize(parent, fext); 00316 s.reserve(geom::nsites(fext)); 00317 00318 // Process. 00319 internal::extend<I> extend(dp); 00320 internal::shared_flood_args< I, N, internal::extend<I> > 00321 args(f, m, nbh, parent, hqueues, extend); 00322 00323 unsigned r = args.vset.index_of(hmin); 00324 args.deja_vu(pmin) = true; 00325 args.hqueues[r].push(pmin); 00326 args.node_at_level[r] = (f(pmin) == hmin) ? pmin : extend(pmin); 00327 args.is_node_at_level[r] = true; 00328 flood(args, r); 00329 00330 // Attach the nodes under hmin. 00331 unsigned i = r; 00332 do 00333 { 00334 if (args.is_node_at_level[i]) 00335 { 00336 parent(args.node_at_level[r]) = args.node_at_level[i]; 00337 r = i; 00338 } 00339 } 00340 while (i-- > 0); 00341 parent(args.node_at_level[r]) = args.node_at_level[r]; //root 00342 00343 // Canonization and make tree site set. 00344 { 00345 mln_ch_value(I, bool) deja_vu(d_ext); 00346 mln::data::fill(deja_vu, false); 00347 00348 p_array<mln_psite(I)> s_f = mln::data::sort_psites_increasing(f); 00349 mln_fwd_piter(S) p(s_f); // Forward. 00350 for_all(p) 00351 { 00352 P x = p; 00353 P q = parent(p); 00354 00355 // Case: l: m <---- m <---- f 00356 // Or 00357 // Case l1: m <----- f impossible. 00358 // | 00359 // l2: m 00360 mln_assertion(!(d_ext.has(q) && fext(p) == fext(q) && d_ext.has(parent(q)) && q != parent(q))); 00361 00362 while (d_ext.has(q) && !deja_vu(q) && (fext(q) != fext(parent(q)) || q == parent(q))) 00363 { 00364 s.append(q); 00365 deja_vu(q) = true; 00366 x = q; 00367 q = parent(q); 00368 } 00369 00370 if (d_ext.has(q) && fext(q) == fext(parent(q)) && q != parent(q)) 00371 { 00372 q = (parent(x) = parent(q)); 00373 mln_assertion(f.domain().has(q)); 00374 } 00375 00376 if (fext(q) == fext(parent(q))) 00377 parent(x) = parent(q); 00378 00379 s.append(p); 00380 00381 mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); 00382 } 00383 00384 } 00385 00386 std::cout << "Construction de l'arbre en " << tm << " s." << std::endl; 00387 00388 data<I, S> tree(fext, parent, s); 00389 00390 trace::exiting("mln::morpho::tree::impl::dual_hqueue"); 00391 00392 return tree; 00393 } 00394 00395 } // end of namespace mln::morpho::tree::impl 00396 00397 # endif // ! MLN_INCLUDE_ONLY 00398 00399 } // end of namespace mln::morpho::tree 00400 00401 } // end of namespace mln::morpho 00402 00403 } // end of namespace mln 00404 00405 #endif // !MLN_MORPHO_TREE_COMPUTE_PARENT_DUAL_HQUEUE_HH 00406 00407 00408