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_DILATION_UNION_FIND_HH
00028 # define MLN_MORPHO_RECONSTRUCTION_BY_DILATION_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_dilation
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_dilation::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
00133 typedef mln_site(I) P;
00134 typedef mln_value(I) V;
00135
00136
00137 p_array<P> s;
00138 mln_ch_value(I, bool) deja_vu;
00139 mln_ch_value(I, P) parent;
00140 mln_concrete(I) output;
00141
00142
00143 {
00144 initialize(output, f);
00145 data::fill(output, f);
00146 initialize(parent, f);
00147 initialize(deja_vu, f);
00148 data::fill(deja_vu, false);
00149
00150 s = data::sort_psites_decreasing(g);
00151 }
00152
00153
00154 {
00155 for (unsigned i = 0; i < s.nsites(); ++i)
00156 {
00157 P p = s[i];
00158 parent(p) = p;
00159 mln_niter(N) n(nbh, p);
00160 for_all(n)
00161 {
00162
00163
00164
00165
00166
00167 if (f.domain().has(n) && deja_vu(n))
00168 {
00169
00170 P r = internal::find_root(parent, n);
00171 if (r != p)
00172 {
00173 if (g(r) == g(p) || g(p) >= output(r))
00174 {
00175 parent(r) = p;
00176 if (output(r) > output(p))
00177 output(p) = output(r);
00178 }
00179 else
00180 output(p) = mln_max(V);
00181 }
00182 }
00183 }
00184 deja_vu(p) = true;
00185 }
00186 }
00187
00188
00189 {
00190 for (int i = s.nsites() - 1; i >= 0; --i)
00191 {
00192 P p = s[i];
00193 if (parent(p) == p)
00194 {
00195 if (output(p) == mln_max(V))
00196 output(p) = g(p);
00197 }
00198 else
00199 output(p) = output(parent(p));
00200 }
00201 }
00202
00203 mln_postcondition(output >= f);
00204 mln_postcondition(output <= g);
00205
00206 trace::exiting("morpho::reconstruction::by_dilation::impl::generic::union_find");
00207 return output;
00208 }
00209
00210
00211 }
00212
00213 }
00214
00215
00216
00217
00218 namespace internal
00219 {
00220
00221 template <typename I, typename J, typename N>
00222 inline
00223 mln_concrete(I)
00224 union_find_dispatch(trait::image::kind::logic,
00225 const Image<I>& f, const Image<J>& g,
00226 const Neighborhood<N>& nbh)
00227 {
00228
00229 std::cerr
00230 << __FILE__ << ":" << __LINE__ << ": error:\n"
00231 "mln::morpho::reconstruction::by_dilation::internal::\n"
00232 " union_find_dispatch(mln::trait::image::kind::logic,\n"
00233 " const mln::Image<I>&,\n"
00234 " const mln::Image<J>&,\n"
00235 " const mln::Neighborhood<N>&)\n"
00236 "not implemented."
00237 << std::endl;
00238 std::abort();
00239 }
00240
00241 template <typename I, typename J, typename N>
00242 inline
00243 mln_concrete(I)
00244 union_find_dispatch(trait::image::kind::any,
00245 const Image<I>& f, const Image<J>& g,
00246 const Neighborhood<N>& nbh)
00247 {
00248 return impl::generic::union_find(f, g, nbh);
00249 }
00250
00251 template <typename I, typename J, typename N>
00252 inline
00253 mln_concrete(I)
00254 union_find_dispatch(const Image<I>& f, const Image<J>& g,
00255 const Neighborhood<N>& nbh)
00256 {
00257 return union_find_dispatch(mln_trait_image_kind(I)(),
00258 f, g, nbh);
00259 }
00260
00261 }
00262
00263
00264
00265
00266 template <typename I, typename J, typename N>
00267 inline
00268 mln_concrete(I)
00269 union_find(const Image<I>& f, const Image<J>& g,
00270 const Neighborhood<N>& nbh)
00271 {
00272 trace::entering("morpho::reconstruction::by_dilation::union_find");
00273
00274 internal::union_find_tests(f, g, nbh);
00275
00276 mln_concrete(I) output;
00277 output = internal::union_find_dispatch(f, g, nbh);
00278
00279 trace::exiting("morpho::reconstruction::by_dilation::union_find");
00280 return output;
00281 }
00282
00283 # endif // ! MLN_INCLUDE_ONLY
00284
00285 }
00286
00287 }
00288
00289 }
00290
00291 }
00292
00293
00294 #endif // ! MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH