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_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 }
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
00110 util::hqueues<P, V>& hqueues;
00111 const E& extend;
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 {
00146 unsigned i = 0;
00147 while (hm[i] == 0)
00148 ++i;
00149 hmin = hm.vset()[i];
00150 }
00151
00152
00153 for (unsigned i = 0; i < hm.nvalues(); ++i)
00154 hm[i] += hf[i];
00155
00156
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
00167
00168
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 }
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 {
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)
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 {
00224 args.parent(args.node_at_level[p_idx]) = p;
00225 args.node_at_level[p_idx] = p;
00226
00227 }
00228 args.parent(p) = args.node_at_level[p_idx];
00229 }
00230
00231
00232
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
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
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
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
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
00309 mln_concrete(I) fext;
00310 mln_ch_value(I, P) parent;
00311 p_array<mln_psite(I)> s;
00312
00313
00314 fext = geom::translate(m, dp.to_vec(), f, d);
00315 initialize(parent, fext);
00316 s.reserve(geom::nsites(fext));
00317
00318
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
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];
00342
00343
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);
00350 for_all(p)
00351 {
00352 P x = p;
00353 P q = parent(p);
00354
00355
00356
00357
00358
00359
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 }
00396
00397 # endif // ! MLN_INCLUDE_ONLY
00398
00399 }
00400
00401 }
00402
00403 }
00404
00405 #endif // !MLN_MORPHO_TREE_COMPUTE_PARENT_DUAL_HQUEUE_HH
00406
00407
00408