Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2007, 2008, 2009, 2010 EPITA Research and Development 00002 // Laboratory (LRDE) 00003 // 00004 // This file is part of Olena. 00005 // 00006 // Olena is free software: you can redistribute it and/or modify it under 00007 // the terms of the GNU General Public License as published by the Free 00008 // Software Foundation, version 2 of the License. 00009 // 00010 // Olena is distributed in the hope that it will be useful, 00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 // General Public License for more details. 00014 // 00015 // You should have received a copy of the GNU General Public License 00016 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00017 // 00018 // As a special exception, you may use this file as part of a free 00019 // software project without restriction. Specifically, if other files 00020 // instantiate templates or use macros or inline functions from this 00021 // file, or you compile this file and link it with other files to produce 00022 // an executable, this file does not by itself cause the resulting 00023 // executable to be covered by the GNU General Public License. This 00024 // exception does not however invalidate any other reasons why the 00025 // executable file might be covered by the GNU General Public License. 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 // Tests. 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()); // FIXME: Relax? 00084 mln_precondition(f <= g); 00085 00086 // mlc_equal(mln_value(I), mln_value(J))::check(); // FIXME: Too strong! 00087 // FIXME: Also check that we have a total ordering for values. 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 } // end of namespace mln::morpho::reconstruction::by_dilation::internal 00108 00109 00110 // Implementations. 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 // Auxiliary data. 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 // Initialization. 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 // First pass. 00154 { 00155 for (unsigned i = 0; i < s.nsites(); ++i) 00156 { 00157 P p = s[i]; 00158 parent(p) = p; // Make-Set. 00159 mln_niter(N) n(nbh, p); 00160 for_all(n) 00161 { 00162 // if (f.domain().has(n)) 00163 // mln_invariant(deja_vu(n) 00164 // == 00165 // (g(n) > g(p) || (g(n) == g(p) 00166 // && util::ord_strict(n, p)))); 00167 if (f.domain().has(n) && deja_vu(n)) 00168 { 00169 // Do-Union. 00170 P r = internal::find_root(parent, n); 00171 if (r != p) 00172 { 00173 if (g(r) == g(p) || g(p) >= output(r)) // Equivalence test. 00174 { 00175 parent(r) = p; 00176 if (output(r) > output(p)) 00177 output(p) = output(r); // Increasing criterion. 00178 } 00179 else 00180 output(p) = mln_max(V); 00181 } 00182 } 00183 } 00184 deja_vu(p) = true; 00185 } 00186 } 00187 00188 // Second pass. 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 } // end of namespace mln::morpho::reconstruction::by_dilation::impl::generic 00212 00213 } // end of namespace mln::morpho::reconstruction::by_dilation::impl 00214 00215 00216 // Dispatch. 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 (void) f; 00229 (void) g; 00230 (void) nbh; 00231 00232 // FIXME: Not yet implemented. 00233 std::cerr 00234 << __FILE__ << ":" << __LINE__ << ": error:\n" 00235 "mln::morpho::reconstruction::by_dilation::internal::\n" 00236 " union_find_dispatch(mln::trait::image::kind::logic,\n" 00237 " const mln::Image<I>&,\n" 00238 " const mln::Image<J>&,\n" 00239 " const mln::Neighborhood<N>&)\n" 00240 "not implemented." 00241 << std::endl; 00242 std::abort(); 00243 } 00244 00245 template <typename I, typename J, typename N> 00246 inline 00247 mln_concrete(I) 00248 union_find_dispatch(trait::image::kind::any, 00249 const Image<I>& f, const Image<J>& g, 00250 const Neighborhood<N>& nbh) 00251 { 00252 return impl::generic::union_find(f, g, nbh); 00253 } 00254 00255 template <typename I, typename J, typename N> 00256 inline 00257 mln_concrete(I) 00258 union_find_dispatch(const Image<I>& f, const Image<J>& g, 00259 const Neighborhood<N>& nbh) 00260 { 00261 return union_find_dispatch(mln_trait_image_kind(I)(), 00262 f, g, nbh); 00263 } 00264 00265 } // end of namespace mln::morpho::reconstruction::by_dilation::internal 00266 00267 00268 // Facade. 00269 00270 template <typename I, typename J, typename N> 00271 inline 00272 mln_concrete(I) 00273 union_find(const Image<I>& f, const Image<J>& g, 00274 const Neighborhood<N>& nbh) 00275 { 00276 trace::entering("morpho::reconstruction::by_dilation::union_find"); 00277 00278 internal::union_find_tests(f, g, nbh); 00279 00280 mln_concrete(I) output; 00281 output = internal::union_find_dispatch(f, g, nbh); 00282 00283 trace::exiting("morpho::reconstruction::by_dilation::union_find"); 00284 return output; 00285 } 00286 00287 # endif // ! MLN_INCLUDE_ONLY 00288 00289 } // end of namespace mln::morpho::reconstruction::by_dilation 00290 00291 } // end of namespace mln::morpho::reconstruction 00292 00293 } // end of namespace mln::morpho 00294 00295 } // end of namespace mln 00296 00297 00298 #endif // ! MLN_MORPHO_RECONSTRUCTION_BY_DILATION_UNION_FIND_HH