[Olena-patches] 975: Fix Reconstruction. Draft canvas unionfind. .

https://svn.lrde.epita.fr/svn/oln/trunk/olena criteres ? - contrat sur les attributs. - implementation par defaut. - fragmentation du code / lisibilite. - temps d'execution. - temps de compilation. - simplicite. - coherance. - clarte des messages d'erreurs. v0: procedure -ecriture difficile et longue -pas forcement plus rapide qu'avec un canevas v1: donnees tenues +performant +tres lisible -function obligatoirement parametree v2: donnees tenues sauf image -moins coherent que v1 +la function peut ne pas etre parametree v3: donnee passe en argument dans une classe. -peu elegant -lent ? ... v4: heritage +performant +principe naturelle en poo +function peut etre tres specifique (pas de parametre) -fragmentation du code si classe de factorisation -lisibilite bof (code perdu parmis les appelles d'implementation) +permet d'imposer des attributs CODE: ------------------------------------------- #include <oln/core/2d/image2d.hh> #include <oln/core/2d/neighb2d.hh> #include <oln/canvas/two_pass.hh> #include <oln/morpho/cc_tarjan_v ? .hh> int main() { using namespace oln; unsigned N = 1024; image2d<bool> img(N, N); float tmp; for (unsigned i = 0; i < N; i++) for (unsigned j = 0; j < N; j++) { tmp = 5 * cos(i) * cos(j); img.at(i, j) = (tmp > 0) ? tmp : 0; } morpho::cc_tarjan(img + c4); } ------------------------------------------- Without Options : ----------------- test_v0: compile: 16.357s execution: 1m27.001s test_v1 compile: 16.229s execution: 1m14.485s test_v2 compile: 16.485s execution: 1m20.421s test_v4 compile: 16.377s execution: 1m13.705s -O3 -DNDEBUG : -------------- test_v0 compile: 1m5.236s execution: 1.732s test_v1 compile: 1m7.844s execution: 1.560s test_v2 compile: 1m7.528s execution: 1.724s test_v4 compile: 1m7.624s execution: 1.560s -O2 -DNDEBUG : -------------- test_v0 compile: 1m3.108s execution: 4.196s test_v1 compile: 1m7.872s execution: 3.856s test_v2 compile: 1m9.240s execution: 4.328s test_v4 compile: 1m8.360s execution: 3.720s -O1 -DNDEBUG : -------------- test_v0 compile: 21.301s execution: 4.692s test_v1 compile: 22.145s execution: 4.336s test_v2 compile: 22.185s execution: 4.604s test_v4 compile: 22.069s execution: 4.620s --------------- version procedurale plus lente !?? Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Fix Reconstruction. Draft canvas unionfind. . * oln/morpho/binary_reconstruction_v0.hh: . * oln/morpho/cc_tarjan_v4.hh: . * oln/morpho/cc_tarjan_v1.hh: . * oln/level/local_sup.hh: . * oln/level/local_inf.hh: . * oln/canvas/union_find.hh: . * oln/canvas/two_pass.hh: . canvas/two_pass.hh | 104 ++++++++++++++++++++++++++++++------- canvas/union_find.hh | 27 ++++++--- level/local_inf.hh | 18 +++--- level/local_sup.hh | 18 +++--- morpho/binary_reconstruction_v0.hh | 40 +++++++------- morpho/cc_tarjan_v1.hh | 5 - morpho/cc_tarjan_v4.hh | 76 ++++++++++++--------------- 7 files changed, 181 insertions(+), 107 deletions(-) Index: oln/morpho/binary_reconstruction_v0.hh --- oln/morpho/binary_reconstruction_v0.hh (revision 974) +++ oln/morpho/binary_reconstruction_v0.hh (working copy) @@ -33,6 +33,7 @@ # include <oln/accumulator/max.hh> # include <oln/level/clone.hh> # include <oln/level/fill.hh> +# include <oln/level/compare.hh> # include <oln/level/local_inf.hh> # include <oln/level/local_sup.hh> @@ -52,18 +53,6 @@ namespace impl { - template <typename I> - bool - stability(const Image_with_Nbh<I>& marker, - oln_plain(I)& tmp) - { - oln_piter(I) p(marker.points()); - for_all(p) - if (marker(p) != tmp(p)) - return false; - return true; - } - template <typename I, typename J> oln_plain(I) binary_reconstruction_loop(const Image_with_Nbh<I>& marker, @@ -88,19 +77,32 @@ } template <typename I , typename J> - void // FIXME : Slow impl. + oln_plain(I) binary_reconstruction_(const Image_with_Nbh<I>& marker, const Binary_Image<J>& mask) { - oln_plain(I) tmp = level::clone(marker); + accumulator::max_<oln_value(I)> max; + oln_plain(I) + output = level::clone(marker), + memo; - while ( not stability(marker, tmp) ) + do { - level::fill(inplace(exact(marker).image()), tmp); - tmp = binary_reconstruction_loop(marker, mask); - } + memo = level::clone(output); - level::fill(inplace(exact(marker).image()), tmp); + // first pass + oln_fwd_piter(I) p1(marker.points()); + for_all(p1) + output(p1) = level::local_sup(max, output, p1) and mask(p1); + + // second pass + oln_bkd_piter(I) p2(marker.points()); + for_all(p2) + output(p2) = level::local_inf(max, output, p2) and mask(p2); + + } while (output != memo); + + return output; } } // end of namespace oln::morpho::impl Index: oln/morpho/cc_tarjan_v4.hh --- oln/morpho/cc_tarjan_v4.hh (revision 974) +++ oln/morpho/cc_tarjan_v4.hh (working copy) @@ -29,10 +29,9 @@ # define OLN_MORPHO_CC_TARJAN_HH # include <oln/core/concept/image.hh> -# include <oln/core/internal/f_ch_value.hh> - # include <oln/canvas/two_pass.hh> # include <oln/level/fill.hh> +# include <oln/core/internal/f_ch_value.hh> namespace oln { @@ -40,8 +39,6 @@ namespace morpho { - // Fwd declaration. - template <typename I> oln_plain_value(I, unsigned) cc_tarjan(const Image_with_Nbh<I>& f); @@ -50,95 +47,95 @@ namespace impl { - template <typename I> - struct cc_tarjan_ : public canvas::v4::two_pass<I> + struct cc_tarjan_ : public canvas::v4::two_pass<I, cc_tarjan_<I> > { typedef oln_point(I) point; + const I& f; + oln_plain_value(I, unsigned) output; oln_plain_value(I, bool) is_processed; oln_plain_value(I, point) parent; + unsigned nlabels; - cc_tarjan_(const I& img) + cc_tarjan_(const I& f) + : canvas::v4::two_pass<I, cc_tarjan_<I> >(f), + f(f) { } - void init() + void impl_init() { - prepare(is_processed, with, this.f); - prepare(output, with, this.f); - prepare(parent, with, this.f); + prepare(is_processed, with, f); + prepare(output, with, f); + prepare(parent, with, f); level::fill(inplace(is_processed), false); + nlabels = 0; } - void first_pass_body(const point& p) + void impl_first_pass_body(const point& p) { parent(p) = p; - if ( f(p) ) + if (f(p) == true) { - oln_niter(I) n(this.f, p); + oln_niter(I) n(f, p); for_all(n) { - if ( this.f(n) == true and is_processed(n) ) - do_union(this.f, n, p); + if ( f(n) == true and is_processed(n) ) + do_union(n, p); } is_processed(p) = true; } - } - void second_pass_body(const point& p) + void impl_second_pass_body(const point& p) { - unsigned current_label = 0; - if ( this.f(p) == true and parent(p) == p ) - output(p) = ++current_label; + if (f(p) == true) + { + if (parent(p) == p) + output(p) = ++nlabels; else output(p) = output(parent(p)); } + else + output(p) = 0; // bg label + } - void final() + void impl_final() { } - // auxiliary methods - point find_root(const I& ima, - const point& x) + point find_root(const point& x) // FIXME: or w/o const&? { - if (parent(x) != x) - { - parent(x) = find_root(ima, parent(x)); - return parent(x); - } + if (parent(x) == x) return x; + else + return parent(x) = find_root(parent(x)); } - void do_union(const I& ima, - const point& n, + void do_union(const point& n, const point& p) { - point r = find_root(ima, n); + point r = find_root(n); if (r != p) parent(r) = p; } - }; } // end of namespace oln::morpho::impl -// Facades. - template <typename I> oln_plain_value(I, unsigned) cc_tarjan(const Image_with_Nbh<I>& f) { - impl::cc_tarjan_<I> f_cc_tarjan(exact(f)); + impl::cc_tarjan_<I> cc(exact(f)); - f_cc_tarjan.run(); + cc.run(); - return f_cc_tarjan.output; + return cc.output; } # endif // ! OLN_INCLUDE_ONLY @@ -147,5 +144,4 @@ } // end of namespace oln - #endif // ! OLN_MORPHO_CC_TARJAN_HH Index: oln/morpho/cc_tarjan_v1.hh --- oln/morpho/cc_tarjan_v1.hh (revision 974) +++ oln/morpho/cc_tarjan_v1.hh (working copy) @@ -54,8 +54,7 @@ namespace impl { - template <typename I> // FIXME : template< op_<I, extended_by, N>, - // typename I, Typename N> ? + template <typename I> struct cc_tarjan_ { typedef oln_point(I) point; @@ -129,7 +128,7 @@ { point r = find_root(n); if (r != p) - parent(r) = p5A5A; + parent(r) = p; } }; Index: oln/level/local_sup.hh --- oln/level/local_sup.hh (revision 974) +++ oln/level/local_sup.hh (working copy) @@ -68,9 +68,9 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n > p) + if (n < p) f(input(n)); return f.value(); } @@ -86,9 +86,9 @@ f.init_with(input(p)); if (f.value() == true) return true; - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n > p) + if (n < p) { f(input(n)); // FIXME: Change to f.take(input(n))? if (f.value() == true) @@ -106,9 +106,9 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n > p) + if (n < p) { f(input(n)); // FIXME: Change to f.take(input(n))? if (f.value() == false) @@ -135,7 +135,7 @@ f.init_with(input(p)); oln_qiter(W) q(win, p); for_all(q) - if (q > p) + if (q < p) if (input.owns_(q)) f(input(q)); return f.value(); @@ -155,7 +155,7 @@ return true; oln_qiter(W) q(win, p); for_all(q) - if (q > p) + if (q < p) { if (input.owns_(q)) f(input(q)); @@ -177,7 +177,7 @@ f.init_with(input(p)); oln_qiter(W) q(win, p); for_all(q) - if (q > p) + if (q < p) { if (input.owns_(q)) f(input(q)); Index: oln/level/local_inf.hh --- oln/level/local_inf.hh (revision 974) +++ oln/level/local_inf.hh (working copy) @@ -68,9 +68,9 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n < p) + if (n > p) f(input(n)); return f.value(); } @@ -86,9 +86,9 @@ f.init_with(input(p)); if (f.value() == true) return true; - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n < p) + if (n > p) { f(input(n)); // FIXME: Change to f.take(input(n))? if (f.value() == true) @@ -106,9 +106,9 @@ const oln_point(I)& p) { f.init_with(input(p)); - oln_niter(I) n(p, input); + oln_niter(I) n(input, p); for_all(n) - if (n < p) + if (n > p) { f(input(n)); // FIXME: Change to f.take(input(n))? if (f.value() == false) @@ -135,7 +135,7 @@ f.init_with(input(p)); oln_qiter(W) q(win, p); for_all(q) - if (q < p) + if (q > p) if (input.owns_(q)) f(input(q)); return f.value(); @@ -155,7 +155,7 @@ return true; oln_qiter(W) q(win, p); for_all(q) - if (q < p) + if (q > p) { if (input.owns_(q)) f(input(q)); @@ -177,7 +177,7 @@ f.init_with(input(p)); oln_qiter(W) q(win, p); for_all(q) - if (q < p) + if (q > p) { if (input.owns_(q)) f(input(q)); Index: oln/canvas/union_find.hh --- oln/canvas/union_find.hh (revision 974) +++ oln/canvas/union_find.hh (working copy) @@ -43,15 +43,24 @@ oln_bkd_piter(I) p1(fun.f.points()); for_all(p1) { - fun.parent(p1) = p1; - if (fun.f(p) == true) + if (fun.is_in_I(p1)) { - oln_niter(I) n(f, p); + fun.make_set(p); + oln_niter(I) n(fun.f.points(), p); for_all(n) { + if ( fun.p_in_D_upper_or_equal(p1) ) + { if (is_processed(n)) - if (f.condition_bck(p1, n)) - fun.first_pass_body(p1); + fun.first_pass_body1(p1); + } + else + if ( fun.p_in_Do(p1) ) + fun.is_processed(p1) = false; + else ( fun.p_in_D_lower_or_equal(p1) ) + { + fun.first_pass_body2(p1); + } } } } @@ -60,10 +69,12 @@ oln_fwd_piter(I) p2(fun.f.points()); for_all(p2) { - if (fun.f(p2) == true) - if (fun.condition_fwd(p2)) + if (fun.is_in_I(p2)) { - fun.second_pass_body(p2); + if (fun.is_root(p2)) + fun.set_output_value(p2); + else + fun.output(p) = fun.output(fun.parent(p)) ; //bg label } } Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 974) +++ oln/canvas/two_pass.hh (working copy) @@ -25,11 +25,15 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#include <oln/core/concept/image.hh> - #ifndef OLN_CANVAS_TWO_PASS_HH # define OLN_CANVAS_TWO_PASS_HH +# include <oln/core/concept/image.hh> + + +namespace oln +{ + namespace canvas { @@ -39,7 +43,7 @@ typename I> // Data owned by f. void two_pass(F<I>& fun) { -// mlc::assert_< mlc_is_a(I, Image) >::check(); + mlc::assert_< mlc_is_a(I, Image) >::check(); fun.init(); @@ -62,7 +66,7 @@ template <typename F, typename I> void two_pass(F& fun, I f) { -// mlc::assert_< mlc_is_a(I, Image) >::check(); + mlc::assert_< mlc_is_a(I, Image) >::check(); fun.init(f); @@ -83,9 +87,9 @@ namespace v3 // Auxiliar data given as argument. { template <typename F, typename I, typename A> - void two_pass(F fun, I f, A& aux) + void two_pass(F& fun, I& f, A& aux) { -// mlc::assert_< mlc_is_a(I, Image) >::check(); + mlc::assert_< mlc_is_a(I, Image) >::check(); f.init(f, aux); @@ -106,51 +110,113 @@ namespace v4 // Via Inheritance. { + template <typename I, typename Exact> + struct two_pass : public virtual Any<Exact> + { + void init() + { + exact(this)->impl_init(); + } + + void first_pass_body(const oln_point(I)& p) + { + exact(this)->impl_first_pass_body(p); + } + + void second_pass_body(const oln_point(I)& p) + { + exact(this)->impl_second_pass_body(p); + } + + void final() + { + exact(this)->impl_final(); + } + + // Concrete method. + void run() + { + init(); + + // first pass + for_all(p1) + first_pass_body(p1); + + // second pass + + for_all(p2) + second_pass_body(p2); + + final(); + } + + + protected: + + // Ctor. + two_pass(const Image<I>& f) : + p1(f.points()), + p2(f.points()) + { + } - template <typename Exact> + oln_bkd_piter(I) p1; + oln_fwd_piter(I) p2; + + }; + } + + + namespace v5 + { + template<typename I, typename Exact> struct two_pass { + const I& f; + void init() { - this->exact().impl_init(); + assert(0 && "'void init()' not implemented."); } void final() { - this->exact().impl_final(); + assert(0 && "'void final()' not implemented."); } - void first_pass_body(const oln_point(I)& p) + void first_pass_body(const oln_point(I)&) { - this->exact().impl_first_pass_body(p); + assert(0 && "'void first_pass_body(const oln_point(I)& p)' not implemented."); } - void second_pass_body(const oln_point(I)& p) + void second_pass_body(const oln_point(I)&) { - this->exact().impl_second_pass_body(p); + assert(0 && "'void second_pass_body(const oln_point(I)& p)' not implemented."); } void run() { - init(f); + init(); // first pass - oln_bkd_piter(typename Exact::I) p1(f.points()); + oln_bkd_piter(I) p1(f.points()); for_all(p1) first_pass_body(p1); // second pass - oln_fwd_piter(typename Exact::I) p2(f.points()); + oln_fwd_piter(I) p2(f.points()); for_all(p2) second_pass_body(p2); - final(f); + typename Exact::final(); } }; - } + } // end of namespace v5 -} + } // end of namespace morpho + +} // end of namespace oln #endif // ! OLN_CANVAS_TWO_PASS_HH