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