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