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_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 // 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_erosion::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_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 // Auxiliary data. 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 // Initialization. 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 // First pass. 00153 { 00154 for (unsigned i = 0; i < s.nsites(); ++i) 00155 { 00156 P p = s[i]; 00157 parent(p) = p; // Make-Set. 00158 mln_niter(N) n(nbh, p); 00159 for_all(n) 00160 { 00161 // if (f.domain().has(n)) 00162 // mln_invariant(deja_vu(n) 00163 // == 00164 // (g(n) > g(p) || (g(n) == g(p) 00165 // && util::ord_strict(n, p)))); 00166 if (f.domain().has(n) && deja_vu(n)) 00167 { 00168 // Do-Union. 00169 P r = internal::find_root(parent, n); 00170 if (r != p) 00171 { 00172 if (g(r) == g(p) || g(p) <= output(r)) // Equivalence test. 00173 { 00174 parent(r) = p; 00175 if (output(r) < output(p)) 00176 output(p) = output(r); // Increasing criterion. 00177 } 00178 else 00179 output(p) = mln_min(V); 00180 } 00181 } 00182 } 00183 deja_vu(p) = true; 00184 } 00185 } 00186 00187 // Second pass. 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 } // end of namespace mln::morpho::reconstruction::by_erosion::impl::generic 00210 00211 } // end of namespace mln::morpho::reconstruction::by_erosion::impl 00212 00213 00214 // Dispatch. 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 // FIXME: Not yet implemented. 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 } // end of namespace mln::morpho::reconstruction::by_erosion::internal 00260 00261 00262 // Facade. 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 } // end of namespace mln::morpho::reconstruction::by_erosion 00284 00285 } // end of namespace mln::morpho::reconstruction 00286 00287 } // end of namespace mln::morpho 00288 00289 } // end of namespace mln 00290 00291 00292 #endif // ! MLN_MORPHO_RECONSTRUCTION_BY_EROSION_UNION_FIND_HH