* tests/topo/skeleton/breadth_first_thinning.cc, * tests/topo/skeleton/breadth_first_thinning_constrained.cc, * tests/topo/skeleton/priority_driven_thinning.cc, * tests/topo/skeleton/priority_driven_thinning_constrained.cc: New. * tests/topo/skeleton/Makefile.am (check_PROGRAMS): Add breadth_first_thinning, breadth_first_thinning_constrained, priority_driven_thinning and priority_driven_thinning_constrained. (breadth_first_thinning_SOURCES) (breadth_first_thinning_constrained_SOURCES) (priority_driven_thinning_SOURCES) (priority_driven_thinning_constrained_SOURCES): New. (MOSTLYCLEANFILES): Add breadth_first_thinning-small.pbm, breadth_first_thinning_constrained-small.pbm, priority_driven_thinning-small.pbm and priority_driven_thinning_constrained-small.pbm. --- milena/ChangeLog | 22 +++++ milena/tests/topo/skeleton/Makefile.am | 20 ++++- .../skeleton/breadth_first_thinning.cc} | 55 ++++++----- .../skeleton/breadth_first_thinning_constrained.cc | 69 +++++++------- .../topo/skeleton/priority_driven_thinning.cc | 90 +++++++++++++++++++ .../priority_driven_thinning_constrained.cc | 94 ++++++++++++++++++++ 6 files changed, 289 insertions(+), 61 deletions(-) copy milena/tests/{labeling/foreground.cc => topo/skeleton/breadth_first_thinning.cc} (54%) copy scribo/src/primitive/find/find_pattern_lines.cc => milena/tests/topo/skeleton/breadth_first_thinning_constrained.cc (50%) create mode 100644 milena/tests/topo/skeleton/priority_driven_thinning.cc create mode 100644 milena/tests/topo/skeleton/priority_driven_thinning_constrained.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index b41024f..e3b6019 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,27 @@ 2010-09-15 Roland Levillain <roland@lrde.epita.fr> + Exercise breadth-first and priority-driven thinnings. + + * tests/topo/skeleton/breadth_first_thinning.cc, + * tests/topo/skeleton/breadth_first_thinning_constrained.cc, + * tests/topo/skeleton/priority_driven_thinning.cc, + * tests/topo/skeleton/priority_driven_thinning_constrained.cc: + New. + * tests/topo/skeleton/Makefile.am (check_PROGRAMS): Add + breadth_first_thinning, breadth_first_thinning_constrained, + priority_driven_thinning and priority_driven_thinning_constrained. + (breadth_first_thinning_SOURCES) + (breadth_first_thinning_constrained_SOURCES) + (priority_driven_thinning_SOURCES) + (priority_driven_thinning_constrained_SOURCES): + New. + (MOSTLYCLEANFILES): Add breadth_first_thinning-small.pbm, + breadth_first_thinning_constrained-small.pbm, + priority_driven_thinning-small.pbm and + priority_driven_thinning_constrained-small.pbm. + +2010-09-15 Roland Levillain <roland@lrde.epita.fr> + New skeletonization algorithm: priority-driven thinning. * mln/topo/skeleton/priority_driven_thinning.hh: New. diff --git a/milena/tests/topo/skeleton/Makefile.am b/milena/tests/topo/skeleton/Makefile.am index 0e60ff6..eb64238 100644 --- a/milena/tests/topo/skeleton/Makefile.am +++ b/milena/tests/topo/skeleton/Makefile.am @@ -1,4 +1,4 @@ -# Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE). +# Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE). # # This file is part of Olena. # @@ -17,10 +17,26 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ + breadth_first_thinning \ + breadth_first_thinning_constrained \ crest \ - is_simple_point + is_simple_point \ + priority_driven_thinning \ + priority_driven_thinning_constrained +breadth_first_thinning_SOURCES = breadth_first_thinning.cc +breadth_first_thinning_constrained_SOURCES = \ + breadth_first_thinning_constrained.cc crest_SOURCES = crest.cc is_simple_point_SOURCES = is_simple_point.cc +priority_driven_thinning_SOURCES = priority_driven_thinning.cc +priority_driven_thinning_constrained_SOURCES = \ + priority_driven_thinning_constrained.cc TESTS = $(check_PROGRAMS) + +MOSTLYCLEANFILES = \ + breadth_first_thinning-small.pbm \ + breadth_first_thinning_constrained-small.pbm \ + priority_driven_thinning-small.pbm \ + priority_driven_thinning_constrained-small.pbm diff --git a/milena/tests/labeling/foreground.cc b/milena/tests/topo/skeleton/breadth_first_thinning.cc similarity index 54% copy from milena/tests/labeling/foreground.cc copy to milena/tests/topo/skeleton/breadth_first_thinning.cc index acdecb6..e77421a 100644 --- a/milena/tests/labeling/foreground.cc +++ b/milena/tests/topo/skeleton/breadth_first_thinning.cc @@ -1,5 +1,4 @@ -// Copyright (C) 2007, 2008, 2009 EPITA Research and Development -// Laboratory (LRDE) +// Copyright (C) 2010 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -24,12 +23,19 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. +/// \file +/// \brief Testing the computation of a skeleton of a 2D image using +/// an (unconstrained) breadth-first thinning. + #include <mln/core/image/image2d.hh> -#include <mln/core/var.hh> -#include <mln/io/pbm/load.hh> #include <mln/core/alias/neighb2d.hh> -#include <mln/data/compare.hh> -#include <mln/labeling/foreground.hh> + +#include <mln/topo/skeleton/breadth_first_thinning.hh> + +#include <mln/topo/is_simple_point2d.hh> +#include <mln/topo/detach_point.hh> + +#include <mln/io/pbm/all.hh> #include "tests/data.hh" @@ -39,29 +45,28 @@ int main() using namespace mln; typedef image2d<bool> I; - neighb2d nbh = c4(); + typedef neighb2d N; - I pic = io::pbm::load(MLN_IMG_DIR "/picasso.pbm"); - image2d<unsigned> out, ref; + // Add a border of (at least) 1 pixel, to a guarantee a meaningful + // result of the computation of connectivity numbers (called within + // is_simple_2d); indeed, this computation always expects each pixel + // to have 8 neighboring sites. + border::thickness = 1; - unsigned n; - out = labeling::foreground(pic, nbh, n); // Calls the fastest 'video' - // version. - mln_assertion(n == 33); + I input = io::pbm::load(MLN_IMG_DIR "/small.pbm"); - { - // Note that labeling::foreground actually is labeling::value - // which calls canvas::labeling_video and its generic dispatch - // leads to canvas::impl::generic::labeling. + // FIXME: Use a dual neighborhood instead? - labeling::impl::value_functor<I> f(pic, true); + // Foreground neighborhood. + neighb2d nbh_fg = c4(); + // Background neighborhood. + neighb2d nbh_bg = c8(); - unsigned n_; - ref = canvas::labeling::impl::generic::labeling(pic, nbh, n_, - pic.domain(), - f); - mln_invariant(n_ == n); - mln_invariant(ref == out); - } + // Simplicity criterion functor. + topo::is_simple_point2d<I, N> is_simple(nbh_fg, nbh_bg); + I output = topo::skeleton::breadth_first_thinning(input, nbh_fg, + is_simple, + topo::detach_point); + io::pbm::save(output, "breadth_first_thinning-small.pbm"); } diff --git a/scribo/src/primitive/find/find_pattern_lines.cc b/milena/tests/topo/skeleton/breadth_first_thinning_constrained.cc similarity index 50% copy from scribo/src/primitive/find/find_pattern_lines.cc copy to milena/tests/topo/skeleton/breadth_first_thinning_constrained.cc index 3d8a98f..8ec213a 100644 --- a/scribo/src/primitive/find/find_pattern_lines.cc +++ b/milena/tests/topo/skeleton/breadth_first_thinning_constrained.cc @@ -1,4 +1,4 @@ -// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2010 EPITA Research and Development Laboratory (LRDE) // // This file is part of Olena. // @@ -23,53 +23,54 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. +/// \file +/// \brief Testing the computation of a skeleton of a 2D image using +/// an breadth-first thinning preserving end points. + #include <mln/core/image/image2d.hh> -#include <mln/value/label_16.hh> -#include <mln/value/rgb8.hh> #include <mln/core/alias/neighb2d.hh> -#include <mln/io/pbm/all.hh> -#include <mln/io/ppm/save.hh> -#include <mln/data/convert.hh> -#include <mln/debug/superpose.hh> -#include <scribo/debug/usage.hh> +#include <mln/topo/skeleton/breadth_first_thinning.hh> -#include <scribo/core/object_image.hh> -#include <scribo/primitive/extract/lines_h_pattern.hh> -#include <scribo/primitive/extract/lines_v_pattern.hh> +#include <mln/topo/is_simple_point2d.hh> +#include <mln/topo/detach_point.hh> +#include <mln/topo/is_not_end_point.hh> -const char *args_desc[][2] = -{ - { "input.pbm", "A binary image." }, - { "length", " Minimum line length." }, - {0, 0} -}; +#include <mln/io/pbm/all.hh> +#include "tests/data.hh" -int main(int argc, char *argv[]) + +int main() { using namespace mln; - if (argc != 4) - return scribo::debug::usage(argv, - "Extract discontinued horizontal and vertical lines", - "input.pbm length output.ppm", - args_desc, - "A color image. Horizontal lines are in red and vertical lines in green."); + typedef image2d<bool> I; + typedef neighb2d N; - trace::entering("main"); + // Add a border of (at least) 1 pixel, to a guarantee a meaningful + // result of the computation of connectivity numbers (called within + // is_simple_2d); indeed, this computation always expects each pixel + // to have 8 neighboring sites. + border::thickness = 1; - typedef image2d<bool> I; - I input; - io::pbm::load(input, argv[1]); + I input = io::pbm::load(MLN_IMG_DIR "/small.pbm"); - I hlines = scribo::primitive::extract::lines_h_pattern(input, atoi(argv[2]), 3); - I vlines = scribo::primitive::extract::lines_v_pattern(input, atoi(argv[2]), 3); + // FIXME: Use a dual neighborhood instead? - image2d<value::rgb8> out = debug::superpose(input, hlines, literal::red); - out = debug::superpose(out, vlines, literal::green); + // Foreground neighborhood. + neighb2d nbh_fg = c4(); + // Background neighborhood. + neighb2d nbh_bg = c8(); - io::ppm::save(out, argv[3]); + // Simplicity criterion functor. + topo::is_simple_point2d<I, N> is_simple(nbh_fg, nbh_bg); + // Constraint: do not collapse end points. + topo::is_not_end_point<I, N> constraint(nbh_fg, input); - trace::exiting("main"); + I output = topo::skeleton::breadth_first_thinning(input, nbh_fg, + is_simple, + topo::detach_point, + constraint); + io::pbm::save(output, "breadth_first_thinning_constrained-small.pbm"); } diff --git a/milena/tests/topo/skeleton/priority_driven_thinning.cc b/milena/tests/topo/skeleton/priority_driven_thinning.cc new file mode 100644 index 0000000..36470d1 --- /dev/null +++ b/milena/tests/topo/skeleton/priority_driven_thinning.cc @@ -0,0 +1,90 @@ +// Copyright (C) 2010 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// \brief Testing the computation of a skeleton of a 2D image using +/// an (unconstrained) priority-driven thinning. + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/topo/skeleton/priority_driven_thinning.hh> + +#include <mln/topo/is_simple_point2d.hh> +#include <mln/topo/detach_point.hh> + +#include <mln/logical/not.hh> +#include <mln/arith/revert.hh> +#include <mln/transform/distance_geodesic.hh> + +#include <mln/io/pbm/all.hh> + +#include "tests/data.hh" + + +int main() +{ + using namespace mln; + + typedef image2d<bool> I; + typedef neighb2d N; + + // Add a border of (at least) 1 pixel, to a guarantee a meaningful + // result of the computation of connectivity numbers (called within + // is_simple_2d); indeed, this computation always expects each pixel + // to have 8 neighboring sites. + border::thickness = 1; + + I input = io::pbm::load(MLN_IMG_DIR "/small.pbm"); + + // FIXME: Use a dual neighborhood instead? + + // Foreground neighborhood. + neighb2d nbh_fg = c4(); + // Background neighborhood. + neighb2d nbh_bg = c8(); + + // Simplicity criterion functor. + topo::is_simple_point2d<I, N> is_simple(nbh_fg, nbh_bg); + + // Distance type. + typedef value::int_u8 D; + // Distance map type. + typedef image2d<D> M; + + // Compute a distance map on the objects (foreground) of the image, + // instead of the (usual) background. + M dmap = transform::distance_geodesic(logical::not_(input), nbh_fg, + mln_max(D)); + // Create a priority function (actually, an image) using the inverse + // of the distance map. + M priority = arith::revert(dmap); + + I output = topo::skeleton::priority_driven_thinning(input, nbh_fg, + is_simple, + topo::detach_point, + priority); + io::pbm::save(output, "priority_driven_thinning-small.pbm"); +} diff --git a/milena/tests/topo/skeleton/priority_driven_thinning_constrained.cc b/milena/tests/topo/skeleton/priority_driven_thinning_constrained.cc new file mode 100644 index 0000000..822d5cd --- /dev/null +++ b/milena/tests/topo/skeleton/priority_driven_thinning_constrained.cc @@ -0,0 +1,94 @@ +// Copyright (C) 2010 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// \brief Testing the computation of a skeleton of a 2D image using +/// an priority-driven thinning preserving end points. + +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> + +#include <mln/topo/skeleton/priority_driven_thinning.hh> + +#include <mln/topo/is_simple_point2d.hh> +#include <mln/topo/detach_point.hh> +#include <mln/topo/is_not_end_point.hh> + +#include <mln/logical/not.hh> +#include <mln/arith/revert.hh> +#include <mln/transform/distance_geodesic.hh> + +#include <mln/io/pbm/all.hh> + +#include "tests/data.hh" + + +int main() +{ + using namespace mln; + + typedef image2d<bool> I; + typedef neighb2d N; + + // Add a border of (at least) 1 pixel, to a guarantee a meaningful + // result of the computation of connectivity numbers (called within + // is_simple_2d); indeed, this computation always expects each pixel + // to have 8 neighboring sites. + border::thickness = 1; + + I input = io::pbm::load(MLN_IMG_DIR "/small.pbm"); + + // FIXME: Use a dual neighborhood instead? + + // Foreground neighborhood. + neighb2d nbh_fg = c4(); + // Background neighborhood. + neighb2d nbh_bg = c8(); + + // Simplicity criterion functor. + topo::is_simple_point2d<I, N> is_simple(nbh_fg, nbh_bg); + // Constraint: do not collapse end points. + topo::is_not_end_point<I, N> constraint(nbh_fg, input); + + // Distance type. + typedef value::int_u8 D; + // Distance map type. + typedef image2d<D> M; + + // Compute a distance map on the objects (foreground) of the image, + // instead of the (usual) background. + M dmap = transform::distance_geodesic(logical::not_(input), nbh_fg, + mln_max(D)); + // Create a priority function (actually, an image) using the inverse + // of the distance map. + M priority = arith::revert(dmap); + + I output = topo::skeleton::priority_driven_thinning(input, nbh_fg, + is_simple, + topo::detach_point, + priority, + constraint); + io::pbm::save(output, "priority_driven_thinning_constrained-small.pbm"); +} -- 1.5.6.5