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_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH
00027 # define MLN_MORPHO_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH
00028
00029 # include <vector>
00030 # include <mln/core/concept/image.hh>
00031 # include <mln/core/concept/neighborhood.hh>
00032 # include <mln/data/fill.hh>
00033 # include <mln/data/compare.hh>
00034 # include <mln/data/sort_psites.hh>
00035
00036
00037 namespace mln
00038 {
00039
00040 namespace morpho
00041 {
00042
00043 namespace reconstruction
00044 {
00045
00046 namespace by_erosion
00047 {
00048
00049
00050 template <typename I, typename J, typename N>
00051 mln_concrete(I)
00052 union_find(const Image<I>& f, const Image<J>& g,
00053 const Neighborhood<N>& nbh);
00054
00055
00056 # ifndef MLN_INCLUDE_ONLY
00057
00058
00059
00060
00061 namespace internal
00062 {
00063
00064 template <typename I, typename J, typename N>
00065 inline
00066 void
00067 union_find_tests(const Image<I>& f_, const Image<J>& g_,
00068 const Neighborhood<N>& nbh_)
00069 {
00070 const I& f = exact(f_);
00071 const J& g = exact(g_);
00072 const N& nbh = exact(nbh_);
00073
00074 mln_precondition(f.is_valid());
00075 mln_precondition(g.is_valid());
00076 mln_precondition(nbh.is_valid());
00077
00078 mln_precondition(f.domain() == g.domain());
00079 mln_precondition(f >= g);
00080
00081
00082
00083
00084 (void) f;
00085 (void) g;
00086 (void) nbh;
00087 }
00088
00089
00090
00091 template <typename Par>
00092 inline
00093 mln_site(Par) find_root(Par& parent, mln_site(Par) x)
00094 {
00095 if (parent(x) == x)
00096 return x;
00097 else
00098 return parent(x) = find_root(parent, parent(x));
00099 }
00100
00101
00102 }
00103
00104
00105
00106
00107 namespace impl
00108 {
00109
00110 namespace generic
00111 {
00112
00113 template <typename I, typename J, typename N>
00114 inline
00115 mln_concrete(I)
00116 union_find(const Image<I>& f_, const Image<J>& g_,
00117 const Neighborhood<N>& nbh_)
00118 {
00119 trace::entering("morpho::reconstruction::by_erosion::impl::generic::union_find");
00120
00121 const I& f = exact(f_);
00122 const J& g = exact(g_);
00123 const N& nbh = exact(nbh_);
00124
00125 internal::union_find_tests(f, g, nbh);
00126
00127 typedef mln_site(I) P;
00128 typedef mln_value(I) V;
00129
00130
00131 p_array<P> s;
00132 mln_ch_value(I, bool) deja_vu;
00133 mln_ch_value(I, P) parent;
00134 mln_concrete(I) output;
00135
00136
00137 {
00138 initialize(output, f);
00139 data::fill(output, f);
00140 initialize(parent, f);
00141 initialize(deja_vu, f);
00142 data::fill(deja_vu, false);
00143
00144 s = data::sort_psites_increasing(g);
00145 }
00146
00147
00148 {
00149 for (unsigned i = 0; i < s.nsites(); ++i)
00150 {
00151 P p = s[i];
00152 parent(p) = p;
00153 mln_niter(N) n(nbh, p);
00154 for_all(n)
00155 {
00156
00157
00158
00159
00160
00161 if (f.domain().has(n) && deja_vu(n))
00162 {
00163
00164 P r = internal::find_root(parent, n);
00165 if (r != p)
00166 {
00167 if (g(r) == g(p) || g(p) <= output(r))
00168 {
00169 parent(r) = p;
00170 if (output(r) < output(p))
00171 output(p) = output(r);
00172 }
00173 else
00174 output(p) = mln_min(V);
00175 }
00176 }
00177 }
00178 deja_vu(p) = true;
00179 }
00180 }
00181
00182
00183 {
00184 for (int i = s.nsites() - 1; i >= 0; --i)
00185 {
00186 P p = s[i];
00187 if (parent(p) == p)
00188 {
00189 if (output(p) == mln_min(V))
00190 output(p) = g(p);
00191 }
00192 else
00193 output(p) = output(parent(p));
00194 }
00195 }
00196
00197 mln_postcondition(output >= f);
00198 mln_postcondition(output >= g);
00199
00200 trace::exiting("morpho::reconstruction::by_erosion::impl::generic::union_find");
00201 return output;
00202 }
00203
00204 }
00205
00206 }
00207
00208
00209
00210
00211 namespace internal
00212 {
00213
00214 template <typename I, typename J, typename N>
00215 inline
00216 mln_concrete(I)
00217 union_find_dispatch(trait::image::kind::logic,
00218 const Image<I>& f, const Image<J>& g,
00219 const Neighborhood<N>& nbh)
00220 {
00221
00222 }
00223
00224 template <typename I, typename J, typename N>
00225 inline
00226 mln_concrete(I)
00227 union_find_dispatch(trait::image::kind::any,
00228 const Image<I>& f, const Image<J>& g,
00229 const Neighborhood<N>& nbh)
00230 {
00231 return impl::generic::union_find(f, g, nbh);
00232 }
00233
00234 template <typename I, typename J, typename N>
00235 inline
00236 mln_concrete(I)
00237 union_find_dispatch(const Image<I>& f, const Image<J>& g,
00238 const Neighborhood<N>& nbh)
00239 {
00240 return union_find_dispatch(mln_trait_image_kind(I)(),
00241 f, g, nbh);
00242 }
00243
00244 }
00245
00246
00247
00248
00249 template <typename I, typename J, typename N>
00250 inline
00251 mln_concrete(I)
00252 union_find(const Image<I>& f, const Image<J>& g,
00253 const Neighborhood<N>& nbh)
00254 {
00255 trace::entering("morpho::reconstruction::by_erosion::union_find");
00256
00257 internal::union_find_tests(f, g, nbh);
00258
00259 mln_concrete(I) output;
00260 output = internal::union_find_dispatch(f, g, nbh);
00261
00262 trace::exiting("morpho::reconstruction::by_erosion::union_find");
00263 return output;
00264 }
00265
00266 # endif // ! MLN_INCLUDE_ONLY
00267
00268 }
00269
00270 }
00271
00272 }
00273
00274 }
00275
00276
00277 #endif // ! MLN_MORPHO_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH