Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 00025 00029 00030 #include <mln/core/image/image2d.hh> 00031 #include <mln/core/alias/neighb2d.hh> 00032 #include <mln/value/int_u8.hh> 00033 #include <mln/io/pgm/load.hh> 00034 00035 #include <mln/labeling/level.hh> 00036 #include <mln/util/timer.hh> 00037 00038 00039 namespace mln 00040 { 00041 00042 00043 namespace old_canvas 00044 { 00045 00046 template <typename F> 00047 struct labeling 00048 { 00049 // Functor. 00050 F& f; 00051 00052 typedef typename F::I I; 00053 typedef typename F::N N; 00054 typedef typename F::L L; 00055 typedef typename F::S S; 00056 00057 // Local type. 00058 typedef mln_psite(I) psite; 00059 00060 // Auxiliary data. 00061 mln_ch_value(I, bool) deja_vu; 00062 mln_ch_value(I, psite) parent; 00063 00064 // Output. 00065 mln_ch_value(I, L) output; 00066 L nlabels; 00067 bool status; 00068 00069 // Ctor. 00070 labeling(F& f); 00071 00072 void init(); 00073 00074 void pass_1(); 00075 00076 void pass_2(); 00077 00078 00079 // Auxiliary methods. 00080 00081 void make_set(const psite& p); 00082 00083 bool is_root(const psite& p) const; 00084 00085 psite find_root(const psite& x); 00086 00087 void do_union(const psite& n, const psite& p); 00088 00089 }; 00090 00091 00092 template <typename F> 00093 labeling<F>::labeling(F& f) 00094 : f(f) 00095 { 00096 trace::entering("canvas::labeling"); 00097 00098 init(); 00099 f.init(); // Client initialization. 00100 pass_1(); 00101 pass_2(); 00102 00103 trace::exiting("canvas::labeling"); 00104 } 00105 00106 template <typename F> 00107 void 00108 labeling<F>::init() 00109 { 00110 initialize(deja_vu, f.input); 00111 mln::data::fill(deja_vu, false); 00112 initialize(parent, f.input); 00113 initialize(output, f.input); 00114 mln::data::fill(output, L(literal::zero)); 00115 nlabels = 0; 00116 } 00117 00118 template <typename F> 00119 void 00120 labeling<F>::pass_1() 00121 { 00122 mln_fwd_piter(S) p(f.s); 00123 mln_niter(N) n(f.nbh, p); 00124 for_all(p) if (f.handles(p)) 00125 { 00126 make_set(p); 00127 for_all(n) 00128 if (f.input.domain().has(n) && deja_vu(n)) 00129 { 00130 if (f.equiv(n, p)) 00131 do_union(n, p); 00132 else 00133 f.do_no_union(n, p); 00134 } 00135 deja_vu(p) = true; 00136 } 00137 } 00138 00139 template <typename F> 00140 void 00141 labeling<F>::pass_2() 00142 { 00143 mln_bkd_piter(S) p(f.s); 00144 for_all(p) if (f.handles(p)) 00145 { 00146 if (is_root(p)) 00147 { 00148 if (f.labels(p)) 00149 { 00150 if (nlabels == mln_max(L)) 00151 { 00152 status = false; 00153 return; 00154 } 00155 output(p) = ++nlabels; 00156 } 00157 } 00158 else 00159 output(p) = output(parent(p)); 00160 } 00161 status = true; 00162 } 00163 00164 template <typename F> 00165 void 00166 labeling<F>::make_set(const psite& p) 00167 { 00168 parent(p) = p; 00169 f.init_attr(p); 00170 } 00171 00172 template <typename F> 00173 bool 00174 labeling<F>::is_root(const psite& p) const 00175 { 00176 return parent(p) == p; 00177 } 00178 00179 template <typename F> 00180 typename labeling<F>::psite 00181 labeling<F>::find_root(const psite& x) 00182 { 00183 if (parent(x) == x) 00184 return x; 00185 else 00186 return parent(x) = find_root(parent(x)); 00187 } 00188 00189 template <typename F> 00190 void 00191 labeling<F>::do_union(const psite& n, const psite& p) 00192 { 00193 psite r = find_root(n); 00194 if (r != p) 00195 { 00196 parent(r) = p; 00197 f.merge_attr(r, p); 00198 } 00199 } 00200 00201 00202 } // end of namespace mln::old_canvas 00203 00204 00205 00206 namespace old_labeling 00207 { 00208 00209 00210 template <typename I_, typename N_, typename L_> 00211 struct level_functor 00212 { 00213 typedef mln_psite(I_) P; 00214 00215 // requirements from mln::canvas::labeling: 00216 00217 typedef I_ I; 00218 typedef N_ N; 00219 typedef L_ L; 00220 typedef mln_pset(I) S; 00221 00222 const I& input; 00223 const N& nbh; 00224 const S& s; 00225 00226 bool handles(const P& p) const { return input(p) == val; } 00227 bool equiv(const P& n, const P&) const { return input(n) == val; } 00228 00229 void init() {} 00230 bool labels(const P&) const { return true; } 00231 void do_no_union(const P&, const P&) {} 00232 void init_attr(const P&) {} 00233 void merge_attr(const P&, const P&) {} 00234 00235 // end of requirements 00236 00237 const mln_value(I_)& val; 00238 00239 level_functor(const I& input, const mln_value(I)& val, const N& nbh) 00240 : input(input), 00241 nbh(nbh), 00242 s(input.domain()), 00243 val(val) 00244 {} 00245 }; 00246 00247 00248 00249 template <typename I, typename N, typename L> 00250 mln_ch_value(I, L) 00251 level(const Image<I>& input, const mln_value(I)& val, const Neighborhood<N>& nbh, 00252 L& nlabels) 00253 { 00254 trace::entering("labeling::value"); 00255 00256 typedef level_functor<I,N,L> F; 00257 F f(exact(input), val, exact(nbh)); 00258 old_canvas::labeling<F> run(f); 00259 00260 nlabels = run.nlabels; 00261 00262 trace::exiting("labeling::value"); 00263 return run.output; 00264 } 00265 00266 } // end of namespace mln::old_labeling 00267 00268 } // end of namespace mln 00269 00270 00271 00272 00273 int main() 00274 { 00275 using namespace mln; 00276 using value::int_u8; 00277 00278 image2d<int_u8> lena; 00279 io::pgm::load(lena, "../../img/lena.pgm"); 00280 00281 { 00282 util::timer t; 00283 t.start(); 00284 unsigned n; 00285 for (unsigned l = 0; l <= 255; ++l) 00286 old_labeling::value(lena, l, c4(), n); 00287 std::cout << "canvas as class: " << t.read() << std::endl; 00288 } 00289 00290 { 00291 util::timer t; 00292 t.start(); 00293 unsigned n; 00294 for (unsigned l = 0; l <= 255; ++l) 00295 labeling::impl::generic::data(lena, l, c4(), n); 00296 std::cout << "canvas as proc.: " << t.read() << std::endl; 00297 } 00298 00299 }