[Olena-patches] 916: Add elementary cc_tarjan on Binary image.

Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; Add elementary cc_tarjan on Binary image. * tests/algorithms/cc_tarjan.cc: New. * tests/algorithms/Makefile.am: Updated for check. * oln/morpho/cc_tarjan.hh: New. * oln/morpho/cc_tarjan.cc: Remove. * oln/level/apply.hh: . oln/morpho/cc_tarjan.hh | 99 ++++++++++++++++++++++++++++++------------ tests/algorithms/Makefile.am | 4 + tests/algorithms/cc_tarjan.cc | 45 +++++++++++++++++++ 3 files changed, 119 insertions(+), 29 deletions(-) Index: tests/algorithms/cc_tarjan.cc --- tests/algorithms/cc_tarjan.cc (revision 0) +++ tests/algorithms/cc_tarjan.cc (revision 0) @@ -0,0 +1,45 @@ +#include <oln/core/2d/image2d.hh> +#include <oln/core/2d/window2d.hh> +#include <oln/core/2d/neighb2d.hh> + +#include <oln/morpho/cc_tarjan.hh> + +#include <oln/debug/print.hh> + + +template <typename I> +void set(I& ima, + int i, + int j) +{ + oln_point(I) p(i, j); + ima(p) = true; +} + +int main() +{ + using namespace oln; + typedef image2d<bool> I; + I ima(3, 3); + + set(ima, 0, 0); + set(ima, 0, 1); + set(ima, 0, 2); + + set(ima, 2, 0); + set(ima, 2, 1); + set(ima, 2, 2); + + I out = morpho::cc_tarjan(ima + c4); + +// for (unsigned i; i < 3; i++) +// for (unsigned j; j < 3; j++) +// { +// if (i == 0) +// assert(ima(i, j) == 1); +// if (i == 1) +// assert(ima(i, j) == 0); +// if (i == 2) +// assert(ima(i, j) == 2); +// } +} Index: tests/algorithms/Makefile.am --- tests/algorithms/Makefile.am (revision 915) +++ tests/algorithms/Makefile.am (working copy) @@ -24,10 +24,12 @@ check_PROGRAMS = \ fill \ - basic_morpho + basic_morpho \ + cc_tarjan # Algorithms. fill_SOURCES = fill.cc basic_morpho_SOURCES = basic_morpho.cc +cc_tarjan_SOURCES = cc_tarjan.cc TESTS = $(check_PROGRAMS) Index: oln/morpho/cc_tarjan.hh --- oln/morpho/cc_tarjan.hh (revision 912) +++ oln/morpho/cc_tarjan.hh (working copy) @@ -28,6 +28,8 @@ #ifndef OLN_MORPHO_DILATION_HH # define OLN_MORPHO_DILATION_HH +#include <oln/debug/print.hh> + namespace oln { @@ -35,70 +37,111 @@ { template <typename I> - oln_point(I) find_root(const oln_point(I)& x) + oln_point(I) find_root(I& ima, + const oln_point(I)& x, + oln_plain_value(I, oln_point(I))& parent) { - if (parent[x] != x) + std::cout << "enter_root( " << parent(x) << "," << x << " )" << std::endl; + + if (parent(x) != x) { - parent[x] = find_root(parent[x]); + parent(x) = find_root(ima, parent(x), parent); return parent(x); } return x; + + std::cout << "leave_root" << std::endl; } template <typename I> - void do_union(const oln_point(I)& n, + void do_union(I& ima, + const oln_point(I)& n, const oln_point(I)& p, - const oln_plain_value(I, oln_point(I))& parent) + oln_plain_value(I, oln_point(I))& parent) { - oln_point(I) r = find_root(n); + oln_point(I) r = find_root(ima, n, parent); if (r != p) parent(r) = p; } template <typename I> - oln_plain_value(I, unsigned) - cc_tarjan(const Binary_Image<I>& input) + void first_pass(const I& input, + oln_plain_value(I, oln_point(I))& parent, + oln_plain(I)& is_processed) { - oln_plain_value(I, unsigned) output; - prepare(output, with, input); - - oln_plain_value(I, oln_point(I)) parent; - prepare(parent, with, input); - - // Init - unsigned current_label = 0; - oln_plain(I) is_processed; - prepare(is_processed, with, input); - oln_piter(I) p(input.points()); - for_all(p) - is_processed(p) = false; // FIXME : built with. - - - // Fist pass - oln_piter(I) p(input.points()); + oln_bkd_piter(I) p(input.points()); for_all(p) { + if ( input(p) ) + { + parent(p) = p; oln_niter(I) n(p, input); for_all(n) { + if ( input(n) ) + { if ( is_processed(n) ) - do_union(n, p, parent); + { + do_union(input ,n, p, parent); + std::cout << "union ("<< p << ") -> parent :" << std::endl; + debug::print(parent); + } + } } is_processed(p) = true; } + } + std::cout << "pass 1" << std::endl; + } + template <typename I> + void second_pass(const I& input, + oln_plain_value(I, oln_point(I))& parent, + oln_plain_value(I, unsigned)& output) + { + unsigned current_label = 0; // Second pass - oln_piter(I) p2(input.points()); - for_all(p2) + oln_fwd_piter(I) p(input.points()); + for_all(p) + { + if ( input(p) ) { if ( parent(p) == p ) output(p) = ++current_label; else output(p) = output(parent(p)); + std::cout << "output :" << std::endl; + debug::print(output); + } } } + template <typename I> + oln_plain_value(I, unsigned) + cc_tarjan(const Image_with_Nbh<I>& input) + { + oln_plain_value(I, unsigned) output; + prepare(output, with, input); + + oln_plain_value(I, oln_point(I)) parent; + prepare(parent, with, input); + + // Init + oln_plain(I) is_processed; + prepare(is_processed, with, input); + oln_piter(I) p1(input.points()); + for_all(p1) + is_processed(p1) = false; // FIXME : built with. + + first_pass(input, parent, is_processed); + + second_pass(input, parent, output); + + ::oln::debug::print(parent); + return output; + } + } // end of namespace oln::morpho } // end of namespace oln Index: oln/level/apply.hh