- Olena-patches

4561: configure.ac: Update configuration of scribo/src subdirectories.
by Guillaume Lazzara 28 Sep '09

28 Sep '09

--- ChangeLog | 4 ++++ configure.ac | 9 ++++++--- 2 files changed, 10 insertions(+), 3 deletions(-) diff --git a/ChangeLog b/ChangeLog index cfca396..151e554 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,7 @@ +2009-09-28 Guillaume Lazzara <z(a)lrde.epita.fr> + + * configure.ac: Update configuration of scribo/src subdirectories. + 2009-09-24 Roland Levillain <roland(a)lrde.epita.fr> * configure.ac: Configure diff --git a/configure.ac b/configure.ac index e325477..7d17329 100644 --- a/configure.ac +++ b/configure.ac @@ -213,13 +213,16 @@ AC_CONFIG_FILES([ scribo/demo/Makefile scribo/src/Makefile scribo/src/binarization/Makefile - scribo/src/extract/Makefile - scribo/src/extract/primitive/Makefile scribo/src/filter/Makefile + scribo/src/misc/Makefile + scribo/src/multi_scale/Makefile scribo/src/preprocessing/Makefile + scribo/src/primitive/Makefile + scribo/src/primitive/extract/Makefile + scribo/src/primitive/find/Makefile + scribo/src/primitive/group/Makefile scribo/src/table/Makefile scribo/src/text/Makefile - scribo/src/text/grouping/Makefile ]) AC_CONFIG_FILES([scribo/tests/data.hh]) -- 1.5.6.5

1 0

4560: Add a first draft of a multi-scale process.
by Guillaume Lazzara 28 Sep '09

28 Sep '09

* src/multi_scale/Makefile.am, * src/multi_scale/find_lines.cc: New. --- scribo/ChangeLog | 7 ++ scribo/src/multi_scale/Makefile.am | 26 +++++ scribo/src/multi_scale/find_lines.cc | 179 ++++++++++++++++++++++++++++++++++ 3 files changed, 212 insertions(+), 0 deletions(-) create mode 100644 scribo/src/multi_scale/Makefile.am create mode 100644 scribo/src/multi_scale/find_lines.cc diff --git a/scribo/ChangeLog b/scribo/ChangeLog index ff13b41..85c59a7 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,12 @@ 2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Add a first draft of a multi-scale process. + + * src/multi_scale/Makefile.am, + * src/multi_scale/find_lines.cc: New. + +2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Cleanup scribo/src directory. * src/text/Makefile.am, diff --git a/scribo/src/multi_scale/Makefile.am b/scribo/src/multi_scale/Makefile.am new file mode 100644 index 0000000..f3dfb42 --- /dev/null +++ b/scribo/src/multi_scale/Makefile.am @@ -0,0 +1,26 @@ +# Copyright (C) 2009 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/>. +# + +## Process this file through Automake to create Makefile.in. + +include $(top_srcdir)/scribo/scribo.mk + +bin_PROGRAMS = \ + find_lines + +find_lines_SOURCES = find_lines.cc + diff --git a/scribo/src/multi_scale/find_lines.cc b/scribo/src/multi_scale/find_lines.cc new file mode 100644 index 0000000..f91c2da --- /dev/null +++ b/scribo/src/multi_scale/find_lines.cc @@ -0,0 +1,179 @@ +// Copyright (C) 2009 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. + +#include <mln/core/alias/neighb2d.hh> +#include <mln/core/image/image2d.hh> +#include <mln/data/convert.hh> +#include <mln/debug/superpose.hh> +#include <mln/io/pbm/all.hh> +#include <mln/io/ppm/save.hh> +#include <mln/pw/all.hh> +#include <mln/subsampling/subsampling.hh> +#include <mln/value/label_16.hh> +#include <mln/value/rgb8.hh> + +#include <mln/world/binary_2d/enlarge.hh> + +#include <scribo/debug/usage.hh> + +#include <scribo/core/object_image.hh> +#include <scribo/primitive/extract/lines_h_pattern.hh> +#include <scribo/primitive/extract/lines_v_pattern.hh> + +#include <scribo/filter/objects_h_thin.hh> +#include <scribo/filter/objects_v_thin.hh> + +#include <sandbox/theo/Rd/sequential.hh> + +#include <mln/morpho/erosion.hh> + +const char *args_desc[][2] = +{ + { "input.pbm", "A binary image." }, + { "length", " Minimum line length." }, + {0, 0} +}; + + +namespace mln +{ + + template <typename I> + mln_concrete(I) + process(const I& input, const std::string& filename, + unsigned length, unsigned delta, unsigned ratio) + { + I hlines = scribo::primitive::extract::lines_h_pattern(input, + length, + delta); + + value::label_16 nhlines; + hlines = scribo::filter::objects_v_thin(hlines, c8(), + nhlines, delta * ratio); + +// I vlines = scribo::primitive::extract::lines_v_pattern(input, +// length, +// delta); + + +// value::label_16 nvlines; +// vlines = scribo::filter::objects_h_thin(vlines, c8(), +// nvlines, delta * ratio); + +// image2d<value::rgb8> out = debug::superpose(input, hlines, literal::red); +// out = debug::superpose(out, vlines, literal::green); +// io::ppm::save(out, filename); + + return hlines; + } + + + template <typename I> + mln_concrete(I) + merge_results(const I& input, + const I& out, const I& out_sub2x, const I& out_sub4x) + { + mln_concrete(I) output; + initialize(output, input); + + + + return output; + } + + +} // end of namespace mln + + + +int main(int argc, char *argv[]) +{ + using namespace mln; + + if (argc != 4) + return scribo::debug::usage(argv, + "Extract discontinued horizontal and vertical lines (multi-scale version)", + "input.pbm length output.ppm", + args_desc, + "A color image. Horizontal lines are in red and vertical lines in green."); + + trace::entering("main"); + + typedef image2d<bool> I; + dpoint2d none(0, 0); + + I input; + io::pbm::load(input, argv[1]); + + + // 1/1 + std::cout << "1/1" << std::endl; + 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); + + image2d<value::rgb8> out = debug::superpose(input, hlines, literal::red); +// out = debug::superpose(out, vlines, literal::green); + io::ppm::save(out, "out_1_1.ppm"); + +// I out = process(input, "out_1_1.ppm", atoi(argv[2]), 3); + + + + // 1/2 + std::cout << "1/2" << std::endl; + I input_sub2x = mln::subsampling::subsampling(input, none, 2); + I out_sub2 = process(input_sub2x, "out_1_2.ppm", atoi(argv[2]), 3, 2); + + + +// // 1/4 +// std::cout << "1/4" << std::endl; +// I input_sub4x = mln::subsampling::subsampling(input, none, 4); +// I out_sub4 = process(input_sub4x, "out_1_4.ppm", atoi(argv[2]), 3, 4); + + +// out_sub4 = world::binary_2d::enlarge(out_sub4, 2); + out_sub2 = world::binary_2d::enlarge(out_sub2, 1); + +// io::ppm::save(merge_results(input, out, out_sub2, out_sub4), argv[2]); + + I tmp = morpho::Rd::sequential(hlines, input, c8()); + io::pbm::save(tmp, "rd.pbm"); + I tmp_sub2 = morpho::Rd::sequential(out_sub2, input, c8()); + io::pbm::save(tmp_sub2, "rd_sub2.pbm"); + + out = debug::superpose(input, tmp_sub2, literal::red); + out = debug::superpose(out, tmp, literal::red); + io::ppm::save(out, "out.ppm"); + + trace::exiting("main"); +} -- 1.5.6.5

1 0

4559: Cleanup scribo/src directory.
by Guillaume Lazzara 28 Sep '09

28 Sep '09

* src/text/Makefile.am, * src/Makefile.am, * src/filter/Makefile.am, * src/table/Makefile.am, * src/preprocessing/Makefile.am: Add new targets. * src/dmap.cc, * src/extract/Makefile.am, * src/extract/Makefile.am, * src/extract/primitive/Makefile.am, * src/extract/primitive/Makefile.am, * src/extract/primitive/extract_discontinued_hlines.cc, * src/extract/primitive/extract_discontinued_lines.cc, * src/extract/primitive/extract_discontinued_vlines.cc, * src/extract/primitive/extract_thick_hlines.cc, * src/extract/primitive/extract_thick_vlines.cc, * src/extract/primitive/find_discontinued_lines.cc, * src/extract/primitive/find_pattern_lines.cc, * src/extract/primitive/find_single_lines.cc, * src/extract/primitive/find_thick_and_single_lines.cc, * src/extract/primitive/find_thick_lines.cc, * src/filter/large_objects.cc, * src/filter/small_objects.cc, * src/filter/thick_objects.cc, * src/filter/thin_objects.cc, * src/morpho.cc, * src/negate.cc, * src/preprocess.cc, * src/recognition.cc, * src/rectangularity.cc, * src/superpose.cc, * src/table_rebuild_opening.cc, * src/table_rebuild_rank.cc, * src/text/grouping/Makefile.am, * src/text/grouping/group_from_double_link.cc, * src/text/grouping/group_from_double_link_filter_non_aligned.cc, * src/text/grouping/group_from_double_several_links.cc, * src/text/grouping/group_from_graph.cc, * src/text/grouping/group_from_several_graph.cc, * src/text/grouping/group_from_several_left_links.cc, * src/text/grouping/group_from_single_link.cc: Move ... * src/filter/objects_large.cc, * src/filter/objects_small.cc, * src/filter/objects_thick.cc, * src/filter/objects_thin.cc, * src/misc/Makefile.am, * src/misc/dmap.cc, * src/misc/morpho.cc, * src/misc/negate.cc, * src/misc/rectangularity.cc, * src/misc/superpose.cc, * src/preprocessing/preprocess.cc, * src/primitive/Makefile.am, * src/primitive/extract/Makefile.am, * src/primitive/extract/extract_discontinued_hlines.cc, * src/primitive/extract/extract_discontinued_lines.cc, * src/primitive/extract/extract_discontinued_vlines.cc, * src/primitive/extract/extract_thick_hlines.cc, * src/primitive/extract/extract_thick_vlines.cc, * src/primitive/find/Makefile.am, * src/primitive/find/find_discontinued_lines.cc, * src/primitive/find/find_pattern_lines.cc, * src/primitive/find/find_single_lines.cc, * src/primitive/find/find_thick_and_single_lines.cc, * src/primitive/find/find_thick_lines.cc, * src/primitive/group/Makefile.am, * src/primitive/group/group_from_double_link.cc, * src/primitive/group/group_from_double_link_filter_non_aligned.cc, * src/primitive/group/group_from_double_several_links.cc, * src/primitive/group/group_from_graph.cc, * src/primitive/group/group_from_rag.cc, * src/primitive/group/group_from_several_graph.cc, * src/primitive/group/group_from_several_left_links.cc, * src/primitive/group/group_from_single_link.cc, * src/table/rebuild_opening.cc, * src/table/rebuild_rank.cc, * src/text/recognition.cc: ... here. * src/table_old.cc: Remove. --- scribo/ChangeLog | 85 ++++++++++++++++++++ scribo/src/Makefile.am | 44 +++------- scribo/src/filter/Makefile.am | 16 ++-- .../filter/{large_objects.cc => objects_large.cc} | 0 .../filter/{small_objects.cc => objects_small.cc} | 0 .../filter/{thick_objects.cc => objects_thick.cc} | 0 .../filter/{thin_objects.cc => objects_thin.cc} | 0 scribo/src/{table => misc}/Makefile.am | 14 +++- scribo/src/{ => misc}/dmap.cc | 0 scribo/src/{ => misc}/morpho.cc | 0 scribo/src/{ => misc}/negate.cc | 0 scribo/src/{ => misc}/rectangularity.cc | 0 scribo/src/{ => misc}/superpose.cc | 0 scribo/src/preprocessing/Makefile.am | 2 + scribo/src/{ => preprocessing}/preprocess.cc | 0 scribo/src/{extract => primitive}/Makefile.am | 4 +- .../primitive => primitive/extract}/Makefile.am | 13 +--- .../extract}/extract_discontinued_hlines.cc | 0 .../extract}/extract_discontinued_lines.cc | 0 .../extract}/extract_discontinued_vlines.cc | 0 .../extract}/extract_thick_hlines.cc | 0 .../extract}/extract_thick_vlines.cc | 0 .../primitive => primitive/find}/Makefile.am | 10 --- .../find}/find_discontinued_lines.cc | 22 ++++- .../find}/find_pattern_lines.cc | 4 +- .../find}/find_single_lines.cc | 0 .../find}/find_thick_and_single_lines.cc | 0 .../find}/find_thick_lines.cc | 0 .../{text/grouping => primitive/group}/Makefile.am | 0 .../group}/group_from_double_link.cc | 0 .../group_from_double_link_filter_non_aligned.cc | 0 .../group}/group_from_double_several_links.cc | 0 .../group}/group_from_graph.cc | 0 .../grouping => primitive/group}/group_from_rag.cc | 0 .../group}/group_from_several_graph.cc | 0 .../group}/group_from_several_left_links.cc | 0 .../group}/group_from_single_link.cc | 0 scribo/src/table/Makefile.am | 8 ++- .../rebuild_opening.cc} | 0 .../rebuild_rank.cc} | 0 scribo/src/table_old.cc | 63 --------------- scribo/src/text/Makefile.am | 21 ++++- scribo/src/{ => text}/recognition.cc | 0 scribo/src/thin_bboxes.cc | 66 --------------- 44 files changed, 166 insertions(+), 206 deletions(-) rename scribo/src/filter/{large_objects.cc => objects_large.cc} (100%) rename scribo/src/filter/{small_objects.cc => objects_small.cc} (100%) rename scribo/src/filter/{thick_objects.cc => objects_thick.cc} (100%) rename scribo/src/filter/{thin_objects.cc => objects_thin.cc} (100%) copy scribo/src/{table => misc}/Makefile.am (74%) rename scribo/src/{ => misc}/dmap.cc (100%) rename scribo/src/{ => misc}/morpho.cc (100%) rename scribo/src/{ => misc}/negate.cc (100%) rename scribo/src/{ => misc}/rectangularity.cc (100%) rename scribo/src/{ => misc}/superpose.cc (100%) rename scribo/src/{ => preprocessing}/preprocess.cc (100%) rename scribo/src/{extract => primitive}/Makefile.am (95%) copy scribo/src/{extract/primitive => primitive/extract}/Makefile.am (73%) rename scribo/src/{extract/primitive => primitive/extract}/extract_discontinued_hlines.cc (100%) rename scribo/src/{extract/primitive => primitive/extract}/extract_discontinued_lines.cc (100%) rename scribo/src/{extract/primitive => primitive/extract}/extract_discontinued_vlines.cc (100%) rename scribo/src/{extract/primitive => primitive/extract}/extract_thick_hlines.cc (100%) rename scribo/src/{extract/primitive => primitive/extract}/extract_thick_vlines.cc (100%) rename scribo/src/{extract/primitive => primitive/find}/Makefile.am (71%) rename scribo/src/{extract/primitive => primitive/find}/find_discontinued_lines.cc (81%) rename scribo/src/{extract/primitive => primitive/find}/find_pattern_lines.cc (98%) rename scribo/src/{extract/primitive => primitive/find}/find_single_lines.cc (100%) rename scribo/src/{extract/primitive => primitive/find}/find_thick_and_single_lines.cc (100%) rename scribo/src/{extract/primitive => primitive/find}/find_thick_lines.cc (100%) rename scribo/src/{text/grouping => primitive/group}/Makefile.am (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_double_link.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_double_link_filter_non_aligned.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_double_several_links.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_graph.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_rag.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_several_graph.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_several_left_links.cc (100%) rename scribo/src/{text/grouping => primitive/group}/group_from_single_link.cc (100%) rename scribo/src/{table_rebuild_opening.cc => table/rebuild_opening.cc} (100%) rename scribo/src/{table_rebuild_rank.cc => table/rebuild_rank.cc} (100%) delete mode 100644 scribo/src/table_old.cc rename scribo/src/{ => text}/recognition.cc (100%) delete mode 100644 scribo/src/thin_bboxes.cc diff --git a/scribo/ChangeLog b/scribo/ChangeLog index ffd15fa..ff13b41 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,90 @@ 2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Cleanup scribo/src directory. + + * src/text/Makefile.am, + * src/Makefile.am, + * src/filter/Makefile.am, + * src/table/Makefile.am, + * src/preprocessing/Makefile.am: Add new targets. + + * src/dmap.cc, + * src/extract/Makefile.am, + * src/extract/Makefile.am, + * src/extract/primitive/Makefile.am, + * src/extract/primitive/Makefile.am, + * src/extract/primitive/extract_discontinued_hlines.cc, + * src/extract/primitive/extract_discontinued_lines.cc, + * src/extract/primitive/extract_discontinued_vlines.cc, + * src/extract/primitive/extract_thick_hlines.cc, + * src/extract/primitive/extract_thick_vlines.cc, + * src/extract/primitive/find_discontinued_lines.cc, + * src/extract/primitive/find_pattern_lines.cc, + * src/extract/primitive/find_single_lines.cc, + * src/extract/primitive/find_thick_and_single_lines.cc, + * src/extract/primitive/find_thick_lines.cc, + * src/filter/large_objects.cc, + * src/filter/small_objects.cc, + * src/filter/thick_objects.cc, + * src/filter/thin_objects.cc, + * src/morpho.cc, + * src/negate.cc, + * src/preprocess.cc, + * src/recognition.cc, + * src/rectangularity.cc, + * src/superpose.cc, + * src/table_rebuild_opening.cc, + * src/table_rebuild_rank.cc, + * src/text/grouping/Makefile.am, + * src/text/grouping/group_from_double_link.cc, + * src/text/grouping/group_from_double_link_filter_non_aligned.cc, + * src/text/grouping/group_from_double_several_links.cc, + * src/text/grouping/group_from_graph.cc, + * src/text/grouping/group_from_several_graph.cc, + * src/text/grouping/group_from_several_left_links.cc, + * src/text/grouping/group_from_single_link.cc: Move ... + + * src/filter/objects_large.cc, + * src/filter/objects_small.cc, + * src/filter/objects_thick.cc, + * src/filter/objects_thin.cc, + * src/misc/Makefile.am, + * src/misc/dmap.cc, + * src/misc/morpho.cc, + * src/misc/negate.cc, + * src/misc/rectangularity.cc, + * src/misc/superpose.cc, + * src/preprocessing/preprocess.cc, + * src/primitive/Makefile.am, + * src/primitive/extract/Makefile.am, + * src/primitive/extract/extract_discontinued_hlines.cc, + * src/primitive/extract/extract_discontinued_lines.cc, + * src/primitive/extract/extract_discontinued_vlines.cc, + * src/primitive/extract/extract_thick_hlines.cc, + * src/primitive/extract/extract_thick_vlines.cc, + * src/primitive/find/Makefile.am, + * src/primitive/find/find_discontinued_lines.cc, + * src/primitive/find/find_pattern_lines.cc, + * src/primitive/find/find_single_lines.cc, + * src/primitive/find/find_thick_and_single_lines.cc, + * src/primitive/find/find_thick_lines.cc, + * src/primitive/group/Makefile.am, + * src/primitive/group/group_from_double_link.cc, + * src/primitive/group/group_from_double_link_filter_non_aligned.cc, + * src/primitive/group/group_from_double_several_links.cc, + * src/primitive/group/group_from_graph.cc, + * src/primitive/group/group_from_rag.cc, + * src/primitive/group/group_from_several_graph.cc, + * src/primitive/group/group_from_several_left_links.cc, + * src/primitive/group/group_from_single_link.cc, + * src/table/rebuild_opening.cc, + * src/table/rebuild_rank.cc, + * src/text/recognition.cc: ... here. + + * src/table_old.cc: Remove. + +2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Add new filters in Scribo. * filter/objects_h_thin.hh, diff --git a/scribo/src/Makefile.am b/scribo/src/Makefile.am index de051a4..aa82499 100644 --- a/scribo/src/Makefile.am +++ b/scribo/src/Makefile.am @@ -21,64 +21,48 @@ include $(top_srcdir)/scribo/scribo.mk SUBDIRS = \ binarization \ - extract \ + primitive \ filter \ + misc \ + multi_scale \ preprocessing \ table \ text bin_PROGRAMS = \ - dmap \ - morpho \ - negate \ - preprocess \ - rectangularity \ - superpose \ - table_rebuild_opening \ - table_rebuild_rank \ text_in_photo \ text_in_photo_ppm \ - text_in_photo_invert \ - thin_bboxes + text_in_photo_invert -dmap_SOURCES = dmap.cc -morpho_SOURCES = morpho.cc -negate_SOURCES = negate.cc -preprocess_SOURCES = preprocess.cc -rectangularity_SOURCES = rectangularity.cc -superpose_SOURCES = superpose.cc -table_rebuild_opening_SOURCES = table_rebuild_opening.cc -table_rebuild_rank_SOURCES = table_rebuild_rank.cc text_in_photo_SOURCES = text_in_photo.cc text_in_photo_ppm_SOURCES = text_in_photo_ppm.cc text_in_photo_invert_SOURCES = text_in_photo_invert.cc -thin_bboxes_SOURCES = thin_bboxes.cc if HAVE_TESSERACT if HAVE_TIFF - bin_PROGRAMS += recognition - recognition_SOURCES = recognition.cc - recognition_CPPFLAGS = $(AM_CPPFLAGS) \ + bin_PROGRAMS += text_in_doc + text_in_doc_SOURCES = text_in_doc.cc + text_in_doc_CPPFLAGS = $(AM_CPPFLAGS) \ $(TESSERACT_CPPFLAGS) \ $(TIFF_CPPFLAGS) - recognition_LDFLAGS = $(AM_LDFLAGS) \ + text_in_doc_LDFLAGS = $(AM_LDFLAGS) \ $(TESSERACT_LDFLAGS) \ $(TIFF_LDFLAGS) \ - -lpthread + -lpthread -lhpdf - bin_PROGRAMS += text_in_doc - text_in_doc_SOURCES = text_in_doc.cc - text_in_doc_CPPFLAGS = $(AM_CPPFLAGS) \ + bin_PROGRAMS += text_in_doc_ppm + text_in_doc_ppm_SOURCES = text_in_doc_ppm.cc + text_in_doc_ppm_CPPFLAGS = $(AM_CPPFLAGS) \ $(TESSERACT_CPPFLAGS) \ $(TIFF_CPPFLAGS) - text_in_doc_LDFLAGS = $(AM_LDFLAGS) \ + text_in_doc_ppm_LDFLAGS = $(AM_LDFLAGS) \ $(TESSERACT_LDFLAGS) \ $(TIFF_LDFLAGS) \ - -lpthread + -lpthread -lhpdf endif HAVE_TIFF endif HAVE_TESSERACT diff --git a/scribo/src/filter/Makefile.am b/scribo/src/filter/Makefile.am index 2a00108..e8a2b9c 100644 --- a/scribo/src/filter/Makefile.am +++ b/scribo/src/filter/Makefile.am @@ -20,12 +20,12 @@ include $(top_srcdir)/scribo/scribo.mk bin_PROGRAMS = \ - large_objects \ - small_objects \ - thick_objects \ - thin_objects + objects_large \ + objects_small \ + objects_thick \ + objects_thin -large_objects_SOURCES = large_objects.cc -small_objects_SOURCES = small_objects.cc -thick_objects_SOURCES = thick_objects.cc -thin_objects_SOURCES = thin_objects.cc +objects_large_SOURCES = objects_large.cc +objects_small_SOURCES = objects_small.cc +objects_thick_SOURCES = objects_thick.cc +objects_thin_SOURCES = objects_thin.cc diff --git a/scribo/src/filter/large_objects.cc b/scribo/src/filter/objects_large.cc similarity index 100% rename from scribo/src/filter/large_objects.cc rename to scribo/src/filter/objects_large.cc diff --git a/scribo/src/filter/small_objects.cc b/scribo/src/filter/objects_small.cc similarity index 100% rename from scribo/src/filter/small_objects.cc rename to scribo/src/filter/objects_small.cc diff --git a/scribo/src/filter/thick_objects.cc b/scribo/src/filter/objects_thick.cc similarity index 100% rename from scribo/src/filter/thick_objects.cc rename to scribo/src/filter/objects_thick.cc diff --git a/scribo/src/filter/thin_objects.cc b/scribo/src/filter/objects_thin.cc similarity index 100% rename from scribo/src/filter/thin_objects.cc rename to scribo/src/filter/objects_thin.cc diff --git a/scribo/src/table/Makefile.am b/scribo/src/misc/Makefile.am similarity index 74% copy from scribo/src/table/Makefile.am copy to scribo/src/misc/Makefile.am index f18880f..dc64bb9 100644 --- a/scribo/src/table/Makefile.am +++ b/scribo/src/misc/Makefile.am @@ -20,9 +20,15 @@ include $(top_srcdir)/scribo/scribo.mk bin_PROGRAMS = \ - erase \ - extract + dmap \ + morpho \ + negate \ + rectangularity \ + superpose -erase_SOURCES = erase.cc -extract_SOURCES = extract.cc +dmap_SOURCES = dmap.cc +morpho_SOURCES = morpho.cc +negate_SOURCES = negate.cc +rectangularity_SOURCES = rectangularity.cc +superpose_SOURCES = superpose.cc diff --git a/scribo/src/dmap.cc b/scribo/src/misc/dmap.cc similarity index 100% rename from scribo/src/dmap.cc rename to scribo/src/misc/dmap.cc diff --git a/scribo/src/morpho.cc b/scribo/src/misc/morpho.cc similarity index 100% rename from scribo/src/morpho.cc rename to scribo/src/misc/morpho.cc diff --git a/scribo/src/negate.cc b/scribo/src/misc/negate.cc similarity index 100% rename from scribo/src/negate.cc rename to scribo/src/misc/negate.cc diff --git a/scribo/src/rectangularity.cc b/scribo/src/misc/rectangularity.cc similarity index 100% rename from scribo/src/rectangularity.cc rename to scribo/src/misc/rectangularity.cc diff --git a/scribo/src/superpose.cc b/scribo/src/misc/superpose.cc similarity index 100% rename from scribo/src/superpose.cc rename to scribo/src/misc/superpose.cc diff --git a/scribo/src/preprocessing/Makefile.am b/scribo/src/preprocessing/Makefile.am index af6db48..8c1cd80 100644 --- a/scribo/src/preprocessing/Makefile.am +++ b/scribo/src/preprocessing/Makefile.am @@ -20,8 +20,10 @@ include $(top_srcdir)/scribo/scribo.mk bin_PROGRAMS = \ + preprocess \ split_bg_fg \ unskew +preprocess_SOURCES = preprocess.cc split_bg_fg_SOURCES = split_bg_fg.cc unskew_SOURCES = unskew.cc diff --git a/scribo/src/preprocess.cc b/scribo/src/preprocessing/preprocess.cc similarity index 100% rename from scribo/src/preprocess.cc rename to scribo/src/preprocessing/preprocess.cc diff --git a/scribo/src/extract/Makefile.am b/scribo/src/primitive/Makefile.am similarity index 95% rename from scribo/src/extract/Makefile.am rename to scribo/src/primitive/Makefile.am index a11d464..44d9434 100644 --- a/scribo/src/extract/Makefile.am +++ b/scribo/src/primitive/Makefile.am @@ -20,4 +20,6 @@ include $(top_srcdir)/scribo/scribo.mk SUBDIRS = \ - primitive + extract \ + find \ + group diff --git a/scribo/src/extract/primitive/Makefile.am b/scribo/src/primitive/extract/Makefile.am similarity index 73% copy from scribo/src/extract/primitive/Makefile.am copy to scribo/src/primitive/extract/Makefile.am index c4ebeaf..636abc3 100644 --- a/scribo/src/extract/primitive/Makefile.am +++ b/scribo/src/primitive/extract/Makefile.am @@ -25,22 +25,11 @@ bin_PROGRAMS = \ extract_discontinued_vlines \ extract_discontinued_hlines \ extract_thick_vlines \ - extract_thick_hlines \ - find_discontinued_lines \ - find_pattern_lines \ - find_single_lines \ - find_thick_lines \ - find_thick_and_single_lines + extract_thick_hlines extract_discontinued_lines_SOURCES = extract_discontinued_lines.cc extract_discontinued_vlines_SOURCES = extract_discontinued_vlines.cc extract_discontinued_hlines_SOURCES = extract_discontinued_hlines.cc extract_thick_vlines_SOURCES = extract_thick_vlines.cc extract_thick_hlines_SOURCES = extract_thick_hlines.cc -find_discontinued_lines_SOURCES = find_discontinued_lines.cc -find_pattern_lines_SOURCES = find_pattern_lines.cc -find_single_lines_SOURCES = find_single_lines.cc -find_thick_lines_SOURCES = find_thick_lines.cc -find_thick_and_single_lines_SOURCES = find_thick_and_single_lines.cc - diff --git a/scribo/src/extract/primitive/extract_discontinued_hlines.cc b/scribo/src/primitive/extract/extract_discontinued_hlines.cc similarity index 100% rename from scribo/src/extract/primitive/extract_discontinued_hlines.cc rename to scribo/src/primitive/extract/extract_discontinued_hlines.cc diff --git a/scribo/src/extract/primitive/extract_discontinued_lines.cc b/scribo/src/primitive/extract/extract_discontinued_lines.cc similarity index 100% rename from scribo/src/extract/primitive/extract_discontinued_lines.cc rename to scribo/src/primitive/extract/extract_discontinued_lines.cc diff --git a/scribo/src/extract/primitive/extract_discontinued_vlines.cc b/scribo/src/primitive/extract/extract_discontinued_vlines.cc similarity index 100% rename from scribo/src/extract/primitive/extract_discontinued_vlines.cc rename to scribo/src/primitive/extract/extract_discontinued_vlines.cc diff --git a/scribo/src/extract/primitive/extract_thick_hlines.cc b/scribo/src/primitive/extract/extract_thick_hlines.cc similarity index 100% rename from scribo/src/extract/primitive/extract_thick_hlines.cc rename to scribo/src/primitive/extract/extract_thick_hlines.cc diff --git a/scribo/src/extract/primitive/extract_thick_vlines.cc b/scribo/src/primitive/extract/extract_thick_vlines.cc similarity index 100% rename from scribo/src/extract/primitive/extract_thick_vlines.cc rename to scribo/src/primitive/extract/extract_thick_vlines.cc diff --git a/scribo/src/extract/primitive/Makefile.am b/scribo/src/primitive/find/Makefile.am similarity index 71% rename from scribo/src/extract/primitive/Makefile.am rename to scribo/src/primitive/find/Makefile.am index c4ebeaf..93a3920 100644 --- a/scribo/src/extract/primitive/Makefile.am +++ b/scribo/src/primitive/find/Makefile.am @@ -21,22 +21,12 @@ include $(top_srcdir)/scribo/scribo.mk bin_PROGRAMS = \ - extract_discontinued_lines \ - extract_discontinued_vlines \ - extract_discontinued_hlines \ - extract_thick_vlines \ - extract_thick_hlines \ find_discontinued_lines \ find_pattern_lines \ find_single_lines \ find_thick_lines \ find_thick_and_single_lines -extract_discontinued_lines_SOURCES = extract_discontinued_lines.cc -extract_discontinued_vlines_SOURCES = extract_discontinued_vlines.cc -extract_discontinued_hlines_SOURCES = extract_discontinued_hlines.cc -extract_thick_vlines_SOURCES = extract_thick_vlines.cc -extract_thick_hlines_SOURCES = extract_thick_hlines.cc find_discontinued_lines_SOURCES = find_discontinued_lines.cc find_pattern_lines_SOURCES = find_pattern_lines.cc find_single_lines_SOURCES = find_single_lines.cc diff --git a/scribo/src/extract/primitive/find_discontinued_lines.cc b/scribo/src/primitive/find/find_discontinued_lines.cc similarity index 81% rename from scribo/src/extract/primitive/find_discontinued_lines.cc rename to scribo/src/primitive/find/find_discontinued_lines.cc index eaf2d59..1ed77e3 100644 --- a/scribo/src/extract/primitive/find_discontinued_lines.cc +++ b/scribo/src/primitive/find/find_discontinued_lines.cc @@ -35,8 +35,8 @@ #include <scribo/debug/usage.hh> #include <scribo/core/object_image.hh> -#include <scribo/primitive/extract/lines_h_pattern.hh> -#include <scribo/primitive/extract/lines_v_pattern.hh> +#include <scribo/primitive/extract/lines_h_discontinued.hh> +#include <scribo/primitive/extract/lines_v_discontinued.hh> const char *args_desc[][2] = { @@ -63,8 +63,22 @@ int main(int argc, char *argv[]) I input; io::pbm::load(input, argv[1]); - I hlines = scribo::primitive::extract::lines_h_pattern(input, atoi(argv[2])); - I vlines = scribo::primitive::extract::lines_v_pattern(input, atoi(argv[2])); + value::label_16 + nhlines, + nvlines; + + typedef image2d<value::label_16> L; + object_image(L) + hlines = scribo::primitive::extract::lines_h_discontinued(input, + c8(), + nhlines, + atoi(argv[2]), + 8), + vlines = scribo::primitive::extract::lines_v_discontinued(input, + c8(), + nvlines, + atoi(argv[2]), + 8); image2d<value::rgb8> out = debug::superpose(input, hlines, literal::red); out = debug::superpose(out, vlines, literal::green); diff --git a/scribo/src/extract/primitive/find_pattern_lines.cc b/scribo/src/primitive/find/find_pattern_lines.cc similarity index 98% rename from scribo/src/extract/primitive/find_pattern_lines.cc rename to scribo/src/primitive/find/find_pattern_lines.cc index eaf2d59..3d8a98f 100644 --- a/scribo/src/extract/primitive/find_pattern_lines.cc +++ b/scribo/src/primitive/find/find_pattern_lines.cc @@ -63,8 +63,8 @@ int main(int argc, char *argv[]) I input; io::pbm::load(input, argv[1]); - I hlines = scribo::primitive::extract::lines_h_pattern(input, atoi(argv[2])); - I vlines = scribo::primitive::extract::lines_v_pattern(input, atoi(argv[2])); + 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); image2d<value::rgb8> out = debug::superpose(input, hlines, literal::red); out = debug::superpose(out, vlines, literal::green); diff --git a/scribo/src/extract/primitive/find_single_lines.cc b/scribo/src/primitive/find/find_single_lines.cc similarity index 100% rename from scribo/src/extract/primitive/find_single_lines.cc rename to scribo/src/primitive/find/find_single_lines.cc diff --git a/scribo/src/extract/primitive/find_thick_and_single_lines.cc b/scribo/src/primitive/find/find_thick_and_single_lines.cc similarity index 100% rename from scribo/src/extract/primitive/find_thick_and_single_lines.cc rename to scribo/src/primitive/find/find_thick_and_single_lines.cc diff --git a/scribo/src/extract/primitive/find_thick_lines.cc b/scribo/src/primitive/find/find_thick_lines.cc similarity index 100% rename from scribo/src/extract/primitive/find_thick_lines.cc rename to scribo/src/primitive/find/find_thick_lines.cc diff --git a/scribo/src/text/grouping/Makefile.am b/scribo/src/primitive/group/Makefile.am similarity index 100% rename from scribo/src/text/grouping/Makefile.am rename to scribo/src/primitive/group/Makefile.am diff --git a/scribo/src/text/grouping/group_from_double_link.cc b/scribo/src/primitive/group/group_from_double_link.cc similarity index 100% rename from scribo/src/text/grouping/group_from_double_link.cc rename to scribo/src/primitive/group/group_from_double_link.cc diff --git a/scribo/src/text/grouping/group_from_double_link_filter_non_aligned.cc b/scribo/src/primitive/group/group_from_double_link_filter_non_aligned.cc similarity index 100% rename from scribo/src/text/grouping/group_from_double_link_filter_non_aligned.cc rename to scribo/src/primitive/group/group_from_double_link_filter_non_aligned.cc diff --git a/scribo/src/text/grouping/group_from_double_several_links.cc b/scribo/src/primitive/group/group_from_double_several_links.cc similarity index 100% rename from scribo/src/text/grouping/group_from_double_several_links.cc rename to scribo/src/primitive/group/group_from_double_several_links.cc diff --git a/scribo/src/text/grouping/group_from_graph.cc b/scribo/src/primitive/group/group_from_graph.cc similarity index 100% rename from scribo/src/text/grouping/group_from_graph.cc rename to scribo/src/primitive/group/group_from_graph.cc diff --git a/scribo/src/text/grouping/group_from_rag.cc b/scribo/src/primitive/group/group_from_rag.cc similarity index 100% rename from scribo/src/text/grouping/group_from_rag.cc rename to scribo/src/primitive/group/group_from_rag.cc diff --git a/scribo/src/text/grouping/group_from_several_graph.cc b/scribo/src/primitive/group/group_from_several_graph.cc similarity index 100% rename from scribo/src/text/grouping/group_from_several_graph.cc rename to scribo/src/primitive/group/group_from_several_graph.cc diff --git a/scribo/src/text/grouping/group_from_several_left_links.cc b/scribo/src/primitive/group/group_from_several_left_links.cc similarity index 100% rename from scribo/src/text/grouping/group_from_several_left_links.cc rename to scribo/src/primitive/group/group_from_several_left_links.cc diff --git a/scribo/src/text/grouping/group_from_single_link.cc b/scribo/src/primitive/group/group_from_single_link.cc similarity index 100% rename from scribo/src/text/grouping/group_from_single_link.cc rename to scribo/src/primitive/group/group_from_single_link.cc diff --git a/scribo/src/table/Makefile.am b/scribo/src/table/Makefile.am index f18880f..334d5f9 100644 --- a/scribo/src/table/Makefile.am +++ b/scribo/src/table/Makefile.am @@ -21,8 +21,12 @@ include $(top_srcdir)/scribo/scribo.mk bin_PROGRAMS = \ erase \ - extract + extract \ + rebuild_opening \ + rebuild_rank + erase_SOURCES = erase.cc extract_SOURCES = extract.cc - +rebuild_opening_SOURCES = rebuild_opening.cc +rebuild_rank_SOURCES = rebuild_rank.cc diff --git a/scribo/src/table_rebuild_opening.cc b/scribo/src/table/rebuild_opening.cc similarity index 100% rename from scribo/src/table_rebuild_opening.cc rename to scribo/src/table/rebuild_opening.cc diff --git a/scribo/src/table_rebuild_rank.cc b/scribo/src/table/rebuild_rank.cc similarity index 100% rename from scribo/src/table_rebuild_rank.cc rename to scribo/src/table/rebuild_rank.cc diff --git a/scribo/src/table_old.cc b/scribo/src/table_old.cc deleted file mode 100644 index 29ec1ec..0000000 --- a/scribo/src/table_old.cc +++ /dev/null @@ -1,63 +0,0 @@ -// Copyright (C) 2008, 2009 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. - -#include "demat.old.hh" - -int main(int argc, char*argv[]) -{ - using namespace mln; - using value::int_u8; - - if (argc < 2) - { - std::cout << argv[0] << " <in.pbm> <out.pgm> <l> <bbox_larger> <bbox_distance> <min_comp_nsites>" << std::endl - << std::endl << std::endl - << std::endl - << "==========" - << std::endl << std::endl - << "<in.pbm> B/W inverted input image." - << std::endl << std::endl -/* << "<out.ppm> RGB8 output image." - << std::endl << std::endl - << "<l> Line length" - << std::endl << std::endl - << "<bbox_distance> Maximum distance between character bounding boxes. Used for bbox grouping." - << std::endl << std::endl - << "<min_comp_nsites> Minimum site count of a character/text component." - << std::endl - << " If a component have a site count lesser than this value, it is erased." - << std::endl << std::endl - << std::endl*/ - << "==========" - << std::endl << std::endl - << "HINT: compile with -DNOUT to avoid debug images." - << std::endl << std::endl; - return 1; - } - - scribo::demat_table(argv); - - return 0; -} diff --git a/scribo/src/text/Makefile.am b/scribo/src/text/Makefile.am index 6b174ef..b84e0dd 100644 --- a/scribo/src/text/Makefile.am +++ b/scribo/src/text/Makefile.am @@ -19,11 +19,24 @@ include $(top_srcdir)/scribo/scribo.mk -SUBDIRS = grouping - - bin_PROGRAMS = \ cleantxt -cleantxt_SOURCES = cleantxt.cc \ No newline at end of file +cleantxt_SOURCES = cleantxt.cc + + +if HAVE_TESSERACT +if HAVE_TIFF + + bin_PROGRAMS += recognition + recognition_SOURCES = recognition.cc + recognition_CPPFLAGS = $(AM_CPPFLAGS) \ + $(TESSERACT_CPPFLAGS) \ + $(TIFF_CPPFLAGS) + recognition_LDFLAGS = $(AM_LDFLAGS) \ + $(TESSERACT_LDFLAGS) \ + $(TIFF_LDFLAGS) \ + -lpthread +endif HAVE_TIFF +endif HAVE_TESSERACT diff --git a/scribo/src/recognition.cc b/scribo/src/text/recognition.cc similarity index 100% rename from scribo/src/recognition.cc rename to scribo/src/text/recognition.cc diff --git a/scribo/src/thin_bboxes.cc b/scribo/src/thin_bboxes.cc deleted file mode 100644 index 39c658a..0000000 --- a/scribo/src/thin_bboxes.cc +++ /dev/null @@ -1,66 +0,0 @@ -// Copyright (C) 2009 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. - -#include <mln/core/image/image2d.hh> -#include <mln/core/alias/neighb2d.hh> - -#include <mln/literal/colors.hh> - -#include <mln/value/label_16.hh> - -#include <mln/io/pbm/load.hh> - - -#include <scribo/text/extract_lines.hh> -#include <scribo/filter/objects_thin.hh> - -int usage(const char *name) -{ - std::cout << "Usage: " << name << " <input.pbm> " << std::endl; - return 1; -} - -int main(int argc, char *argv[]) -{ - using namespace mln; - - if (argc < 1) - return usage(argv[0]); - - scribo::make::internal::debug_filename_prefix = "objects_thin"; - - image2d<bool> input; - io::pbm::load(input, argv[1]); - - value::label_16 nlines; - typedef object_image(image2d<value::label_16>) text_t; - text_t lines = scribo::text::extract_lines(input, c8(), nlines); - - text_t filtered_lines = scribo::filter::objects_thin(lines, 5); - - scribo::debug::save_bboxes_image(input, filtered_lines.bboxes(), - literal::red, - scribo::make::debug_filename("thickness_filter")); -} -- 1.5.6.5

1 0

4558: Add new filters in Scribo.
by Guillaume Lazzara 28 Sep '09

28 Sep '09

* filter/objects_h_thin.hh, * filter/objects_v_thin.hh: New objects filters. --- scribo/ChangeLog | 7 ++ scribo/filter/objects_h_thin.hh | 192 +++++++++++++++++++++++++++++++++++++++ scribo/filter/objects_v_thin.hh | 192 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 391 insertions(+), 0 deletions(-) create mode 100644 scribo/filter/objects_h_thin.hh create mode 100644 scribo/filter/objects_v_thin.hh diff --git a/scribo/ChangeLog b/scribo/ChangeLog index 226b82d..ffd15fa 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,12 @@ 2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Add new filters in Scribo. + + * filter/objects_h_thin.hh, + * filter/objects_v_thin.hh: New objects filters. + +2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + Small fixes in Scribo. * binarization/sauvola.hh: Fix an invalid precondition. diff --git a/scribo/filter/objects_h_thin.hh b/scribo/filter/objects_h_thin.hh new file mode 100644 index 0000000..2b098ac --- /dev/null +++ b/scribo/filter/objects_h_thin.hh @@ -0,0 +1,192 @@ +// Copyright (C) 2009 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. + +#ifndef SCRIBO_FILTER_OBJECTS_H_THIN_HH +# define SCRIBO_FILTER_OBJECTS_H_THIN_HH + +/// \file +/// +/// Remove too thin objects. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> + +# include <mln/util/array.hh> + +# include <scribo/core/object_image.hh> +# include <scribo/primitive/extract/objects.hh> + +namespace scribo +{ + + namespace filter + { + + using namespace mln; + + /// Remove objects thinner or equal to \p min_thickness. + /// + /// \param[in] input_ a binary image. + /// \param[in] nbh_ a neighborhood used in labeling algorithms. + /// \param[in] label_type the label type used for labeling. + /// \param[in] min_thickness the minimum thickness value. + /// + /// \result A binary image without h_thin objects. + // + template <typename I, typename N, typename V> + inline + mln_concrete(I) + objects_h_thin(const Image& input_, + const Neighborhood<N>& nbh_, + const V& label_type, + unsigned min_thickness); + + /// Remove lines of text thinner or equal to \p min_thickness. + /// + /// \param[in] objects An object image. + /// \param[in] min_thickness the minimum thickness value. + /// + /// \result An object image without too thin vertical objects. + // + template <typename L> + inline + object_image(L) + objects_h_thin(const object_image(L)& text, + unsigned min_thickness); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + + /// Filter Functor. + /// Return false for all objects which are too large. + template <typename L> + struct objects_h_thin_filter + : Function_v2b< objects_h_thin_filter<L> > + { + typedef accu::shape::bbox<mln_psite(L)> box_accu_t; + + /// Constructor + /// + /// \param[in] objects object bounding boxes. + /// \param[in] min_thickness the minimum of vertical thickness + /// allowed. + // + objects_h_thin_filter(const object_image(L)& objects, + unsigned min_thickness) + : objects_(objects), min_thickness_(min_thickness) + { + } + + + /// Return false if the objects is thinner than + /// \p min_thickness_. + /// + /// \param[in] l An image value. + // + bool operator()(const mln_value(L)& l) const + { + if (l == literal::zero) + return true; + return objects_.bbox(l).ncols() > min_thickness_; + } + + /// Component bounding boxes. + object_image(L) objects_; + + /// The minimum vertical thickness. + unsigned min_thickness_; + }; + + + } // end of namespace scribo::filter::internal + + + template <typename I, typename N, typename V> + inline + mln_concrete(I) + objects_h_thin(const Image& input_, + const Neighborhood<N>& nbh_, + const V& label_type, + unsigned min_thickness) + { + trace::entering("scribo::filter::objects_h_thin"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + mln_precondition(input.is_valid()); + mln_precondition(nbh.is_valid()); + + V nlabels; + typedef mln_ch_value(I,V) lbl_t; + object_image(lbl_t) objects + = primitive::extract::objects(input, nbh, nlabels); + + typedef internal::objects_h_thin_filter<lbl_t> func_t; + func_t fv2b(objects, min_thickness); + objects.relabel(fv2b); + + mln_concrete(I) output = duplicate(input); + data::fill((output | pw::value(objects) == pw::cst(literal::zero)).rw(), + false); + + trace::exiting("scribo::filter::objects_h_thin"); + return output; + } + + + template <typename L> + inline + object_image(L) + objects_h_thin(const object_image(L)& objects, + unsigned min_thickness) + { + trace::entering("scribo::filter::objects_h_thin"); + + mln_precondition(objects.is_valid()); + + typedef internal::objects_h_thin_filter<L> func_t; + func_t is_not_too_h_thin(objects, min_thickness); + + object_image(L) output; + output.init_from_(objects); + output.relabel(is_not_too_h_thin); + + trace::exiting("scribo::filter::objects_h_thin"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::filter + +} // end of namespace scribo + + +#endif // ! SCRIBO_FILTER_OBJECTS_H_THIN_HH diff --git a/scribo/filter/objects_v_thin.hh b/scribo/filter/objects_v_thin.hh new file mode 100644 index 0000000..bcf6726 --- /dev/null +++ b/scribo/filter/objects_v_thin.hh @@ -0,0 +1,192 @@ +// Copyright (C) 2009 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. + +#ifndef SCRIBO_FILTER_OBJECTS_V_THIN_HH +# define SCRIBO_FILTER_OBJECTS_V_THIN_HH + +/// \file +/// +/// Remove too thin objects. + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/neighborhood.hh> + +# include <mln/util/array.hh> + +# include <scribo/core/object_image.hh> +# include <scribo/primitive/extract/objects.hh> + +namespace scribo +{ + + namespace filter + { + + using namespace mln; + + /// Remove objects thinner or equal to \p min_thickness. + /// + /// \param[in] input_ a binary image. + /// \param[in] nbh_ a neighborhood used in labeling algorithms. + /// \param[in] label_type the label type used for labeling. + /// \param[in] min_thickness the minimum thickness value. + /// + /// \result A binary image without v_thin objects. + // + template <typename I, typename N, typename V> + inline + mln_concrete(I) + objects_v_thin(const Image& input_, + const Neighborhood<N>& nbh_, + const V& label_type, + unsigned min_thickness); + + /// Remove lines of text thinner or equal to \p min_thickness. + /// + /// \param[in] objects An object image. + /// \param[in] min_thickness the minimum thickness value. + /// + /// \result An object image without too thin vertical objects. + // + template <typename L> + inline + object_image(L) + objects_v_thin(const object_image(L)& text, + unsigned min_thickness); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + + /// Filter Functor. + /// Return false for all objects which are too large. + template <typename L> + struct objects_v_thin_filter + : Function_v2b< objects_v_thin_filter<L> > + { + typedef accu::shape::bbox<mln_psite(L)> box_accu_t; + + /// Constructor + /// + /// \param[in] objects object bounding boxes. + /// \param[in] min_thickness the minimum of vertical thickness + /// allowed. + // + objects_v_thin_filter(const object_image(L)& objects, + unsigned min_thickness) + : objects_(objects), min_thickness_(min_thickness) + { + } + + + /// Return false if the objects is thinner than + /// \p min_thickness_. + /// + /// \param[in] l An image value. + // + bool operator()(const mln_value(L)& l) const + { + if (l == literal::zero) + return true; + return objects_.bbox(l).nrows() > min_thickness_; + } + + /// Component bounding boxes. + object_image(L) objects_; + + /// The minimum vertical thickness. + unsigned min_thickness_; + }; + + + } // end of namespace scribo::filter::internal + + + template <typename I, typename N, typename V> + inline + mln_concrete(I) + objects_v_thin(const Image& input_, + const Neighborhood<N>& nbh_, + const V& label_type, + unsigned min_thickness) + { + trace::entering("scribo::filter::objects_v_thin"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + mln_precondition(input.is_valid()); + mln_precondition(nbh.is_valid()); + + V nlabels; + typedef mln_ch_value(I,V) lbl_t; + object_image(lbl_t) objects + = primitive::extract::objects(input, nbh, nlabels); + + typedef internal::objects_v_thin_filter<lbl_t> func_t; + func_t fv2b(objects, min_thickness); + objects.relabel(fv2b); + + mln_concrete(I) output = duplicate(input); + data::fill((output | pw::value(objects) == pw::cst(literal::zero)).rw(), + false); + + trace::exiting("scribo::filter::objects_v_thin"); + return output; + } + + + template <typename L> + inline + object_image(L) + objects_v_thin(const object_image(L)& objects, + unsigned min_thickness) + { + trace::entering("scribo::filter::objects_v_thin"); + + mln_precondition(objects.is_valid()); + + typedef internal::objects_v_thin_filter<L> func_t; + func_t is_not_too_v_thin(objects, min_thickness); + + object_image(L) output; + output.init_from_(objects); + output.relabel(is_not_too_v_thin); + + trace::exiting("scribo::filter::objects_v_thin"); + return output; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::filter + +} // end of namespace scribo + + +#endif // ! SCRIBO_FILTER_OBJECTS_V_THIN_HH -- 1.5.6.5

1 0

4557: Small fixes in Scribo.
by Guillaume Lazzara 28 Sep '09

28 Sep '09

* binarization/sauvola.hh: Fix an invalid precondition. * filter/objects_size_ratio.hh: Add a "using namespace". * primitive/extract/lines_h_pattern.hh, * primitive/extract/lines_v_pattern.hh: Add a parameter. * primitive/extract/lines_pattern.hh: Add a todo. * tests/unit_test/unit-tests.mk: Regen. --- scribo/ChangeLog | 15 +++++++++++ scribo/binarization/sauvola.hh | 2 +- scribo/filter/objects_size_ratio.hh | 2 +- scribo/primitive/extract/lines_h_pattern.hh | 37 +++++++++++++++++--------- scribo/primitive/extract/lines_pattern.hh | 2 + scribo/primitive/extract/lines_v_pattern.hh | 21 +++++++++++---- scribo/tests/unit_test/unit-tests.mk | 8 ++++++ 7 files changed, 66 insertions(+), 21 deletions(-) diff --git a/scribo/ChangeLog b/scribo/ChangeLog index 5a27a1e..226b82d 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,3 +1,18 @@ +2009-09-28 Guillaume Lazzara <lazzara(a)lrde.epita.fr> + + Small fixes in Scribo. + + * binarization/sauvola.hh: Fix an invalid precondition. + + * filter/objects_size_ratio.hh: Add a "using namespace". + + * primitive/extract/lines_h_pattern.hh, + * primitive/extract/lines_v_pattern.hh: Add a parameter. + + * primitive/extract/lines_pattern.hh: Add a todo. + + * tests/unit_test/unit-tests.mk: Regen. + 2009-09-28 Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix typo. diff --git a/scribo/binarization/sauvola.hh b/scribo/binarization/sauvola.hh index 9b719e1..b9f78f8 100644 --- a/scribo/binarization/sauvola.hh +++ b/scribo/binarization/sauvola.hh @@ -310,7 +310,7 @@ namespace scribo { trace::entering("scribo::binarization::sauvola"); - mln_precondition(I::dim == 2); + mln_precondition(mln_site_(I)::dim == 2); mln_precondition(exact(input).is_valid()); typedef mln_value(I) value_t; diff --git a/scribo/filter/objects_size_ratio.hh b/scribo/filter/objects_size_ratio.hh index 7a68f7f..cd12b2e 100644 --- a/scribo/filter/objects_size_ratio.hh +++ b/scribo/filter/objects_size_ratio.hh @@ -40,7 +40,7 @@ namespace scribo namespace filter { - + using namespace mln; template <typename L> object_image(L) diff --git a/scribo/primitive/extract/lines_h_pattern.hh b/scribo/primitive/extract/lines_h_pattern.hh index 7716ac5..fa1823d 100644 --- a/scribo/primitive/extract/lines_h_pattern.hh +++ b/scribo/primitive/extract/lines_h_pattern.hh @@ -54,37 +54,48 @@ namespace scribo /// /// \param[in] input A binary image. /// \param[in] length The minimum line length. + /// \param[in] delta Distance between the object pixel and the + /// background pixel. /// /// \result An image of horizontal lines. // template <typename I> mln_concrete(I) - lines_h_pattern(const Image& input, unsigned length); + lines_h_pattern(const Image& input, unsigned length, unsigned delta); # ifndef MLN_INCLUDE_ONLY template <typename I> mln_concrete(I) - lines_h_pattern(const Image& input, unsigned length) + lines_h_pattern(const Image& input, unsigned length, unsigned delta) { mlc_is(mln_value(I), bool)::check(); mln_precondition(exact(input).is_valid()); mln_precondition(length % 2 == 1); - bool win_def[7][1] = { {1}, - {0}, - {0}, - {0}, - {0}, - {0}, - {1} }; - - window2d win; - convert::from_to(win_def, win); +// bool win_def[7][1] = { {1}, +// {0}, +// {0}, +// {0}, +// {0}, +// {0}, +// {1} }; + +// window2d win; +// convert::from_to(win_def, win); + + // FIXME: not generic. + window2d win; + mln_deduce(I, site, dpsite) + dp1(-delta, 0), + dp2( delta, 0); + win.insert(dp1); + win.insert(dp2); //FIXME: Add reconstruction instead of this arbitrary dilation. - win::hline2d hwin(length/2 + 2); + win::hline2d hwin(length/2 + 2); +// win::hline2d hwin(length); return morpho::dilation(lines_pattern(input, length, 1, win), hwin); // return lines_pattern(input, length, 1, win); } diff --git a/scribo/primitive/extract/lines_pattern.hh b/scribo/primitive/extract/lines_pattern.hh index cd2b558..6a69a4a 100644 --- a/scribo/primitive/extract/lines_pattern.hh +++ b/scribo/primitive/extract/lines_pattern.hh @@ -29,6 +29,8 @@ /// \file /// /// Extract lines matching a specific pattern. +/// +/// \todo Make a more generic canvas. # include <mln/core/concept/image.hh> # include <mln/core/alias/window2d.hh> diff --git a/scribo/primitive/extract/lines_v_pattern.hh b/scribo/primitive/extract/lines_v_pattern.hh index 29f4a54..ccd21c5 100644 --- a/scribo/primitive/extract/lines_v_pattern.hh +++ b/scribo/primitive/extract/lines_v_pattern.hh @@ -60,7 +60,7 @@ namespace scribo // template <typename I> mln_concrete(I) - lines_v_pattern(const Image& input, unsigned length); + lines_v_pattern(const Image& input, unsigned length, unsigned delta); # ifndef MLN_INCLUDE_ONLY @@ -68,17 +68,26 @@ namespace scribo template <typename I> mln_concrete(I) - lines_v_pattern(const Image& input, unsigned length) + lines_v_pattern(const Image& input, unsigned length, unsigned delta) { mln_precondition(length % 2 == 1); - bool win_def[1][7] = { { 1, 0, 0, 0, 0, 0, 1 } }; +// bool win_def[1][7] = { { 1, 0, 0, 0, 0, 0, 1 } }; - window2d win; - convert::from_to(win_def, win); +// window2d win; +// convert::from_to(win_def, win); + + // FIXME: not generic. + window2d win; + mln_deduce(I, site, dpsite) + dp1(0, -delta), + dp2(0, delta); + win.insert(dp1); + win.insert(dp2); //FIXME: Add reconstruction instead of this arbitrary dilation. - win::vline2d vwin(length/2 + 2); + win::vline2d vwin(length/2 + 2); +// win::vline2d vwin(length); return morpho::dilation(lines_pattern(input, length, 0, win), vwin); // return lines_pattern(input, length, 0, win); } diff --git a/scribo/tests/unit_test/unit-tests.mk b/scribo/tests/unit_test/unit-tests.mk index 6b44ef9..953f02a 100644 --- a/scribo/tests/unit_test/unit-tests.mk +++ b/scribo/tests/unit_test/unit-tests.mk @@ -26,6 +26,7 @@ scribo_filter_all \ scribo_filter_common_object_groups_photo \ scribo_filter_common_object_links_photo \ scribo_filter_common_objects_photo \ +scribo_filter_object_groups_size_ratio \ scribo_filter_object_groups_small \ scribo_filter_object_groups_v_thickness \ scribo_filter_object_links_bbox_h_ratio \ @@ -37,10 +38,13 @@ scribo_filter_object_links_non_aligned \ scribo_filter_object_links_non_aligned_simple \ scribo_filter_object_links_non_h_aligned \ scribo_filter_object_links_non_v_aligned \ +scribo_filter_objects_h_thin \ scribo_filter_objects_large \ +scribo_filter_objects_size_ratio \ scribo_filter_objects_small \ scribo_filter_objects_thick \ scribo_filter_objects_thin \ +scribo_filter_objects_v_thin \ scribo_fun_v2b_objects_small_filter \ scribo_make_all \ scribo_make_debug_filename \ @@ -136,6 +140,7 @@ scribo_filter_all_SOURCES = scribo_filter_all.cc scribo_filter_common_object_groups_photo_SOURCES = scribo_filter_common_object_groups_photo.cc scribo_filter_common_object_links_photo_SOURCES = scribo_filter_common_object_links_photo.cc scribo_filter_common_objects_photo_SOURCES = scribo_filter_common_objects_photo.cc +scribo_filter_object_groups_size_ratio_SOURCES = scribo_filter_object_groups_size_ratio.cc scribo_filter_object_groups_small_SOURCES = scribo_filter_object_groups_small.cc scribo_filter_object_groups_v_thickness_SOURCES = scribo_filter_object_groups_v_thickness.cc scribo_filter_object_links_bbox_h_ratio_SOURCES = scribo_filter_object_links_bbox_h_ratio.cc @@ -147,10 +152,13 @@ scribo_filter_object_links_non_aligned_SOURCES = scribo_filter_object_links_non_ scribo_filter_object_links_non_aligned_simple_SOURCES = scribo_filter_object_links_non_aligned_simple.cc scribo_filter_object_links_non_h_aligned_SOURCES = scribo_filter_object_links_non_h_aligned.cc scribo_filter_object_links_non_v_aligned_SOURCES = scribo_filter_object_links_non_v_aligned.cc +scribo_filter_objects_h_thin_SOURCES = scribo_filter_objects_h_thin.cc scribo_filter_objects_large_SOURCES = scribo_filter_objects_large.cc +scribo_filter_objects_size_ratio_SOURCES = scribo_filter_objects_size_ratio.cc scribo_filter_objects_small_SOURCES = scribo_filter_objects_small.cc scribo_filter_objects_thick_SOURCES = scribo_filter_objects_thick.cc scribo_filter_objects_thin_SOURCES = scribo_filter_objects_thin.cc +scribo_filter_objects_v_thin_SOURCES = scribo_filter_objects_v_thin.cc scribo_fun_v2b_objects_small_filter_SOURCES = scribo_fun_v2b_objects_small_filter.cc scribo_make_all_SOURCES = scribo_make_all.cc scribo_make_debug_filename_SOURCES = scribo_make_debug_filename.cc -- 1.5.6.5

1 0

4556: Fix typo.
by Thierry Geraud 28 Sep '09

28 Sep '09

https://svn.lrde.epita.fr/svn/oln/trunk/scribo Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Fix typo. * text/recognition.hh (recognition): Fix typo in commentary. recognition.hh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) Index: text/recognition.hh --- text/recognition.hh (revision 4555) +++ text/recognition.hh (working copy) @@ -142,7 +142,7 @@ /// Improve text quality. - /// text_ima_cleand domain is larger than text_ima's. + /// text_ima_cleaned domain is larger than text_ima's. I text_ima_cleaned = text::clean(text_ima, dmap_win); // Setting objects to 'True'

1 0

milena r4555: Add test for dual input and fix p_transformed test
by Edwin Carlinet 25 Sep '09

25 Sep '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-09-25 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add test for dual input and fix p_transformed test. * core/site_set/p_transformed.cc: Add inverse and typedefs. * morpho/tree/Makefile.am, * morpho/tree/dual_input_tree.cc, Add dual input tree tests. * morpho/tree/filter/filter.cc: Minor changes. --- core/site_set/p_transformed.cc | 7 + morpho/tree/Makefile.am | 2 morpho/tree/dual_input_tree.cc | 173 +++++++++++++++++++++++++++++++++++++++++ morpho/tree/filter/filter.cc | 6 - 4 files changed, 184 insertions(+), 4 deletions(-) Index: trunk/milena/tests/core/site_set/p_transformed.cc =================================================================== --- trunk/milena/tests/core/site_set/p_transformed.cc (revision 4554) +++ trunk/milena/tests/core/site_set/p_transformed.cc (revision 4555) @@ -33,10 +33,17 @@ struct wrap : mln::Function_v2v< wrap > { typedef mln::point2d result; + typedef mln::point2d argument; + result operator()(const result& p) const { return result(p.row() + 5, p.col() + 1); } + + result inverse(const result& p) const + { + return result(p.row() - 5, p.col() - 1); + } }; Index: trunk/milena/tests/morpho/tree/filter/filter.cc =================================================================== --- trunk/milena/tests/morpho/tree/filter/filter.cc (revision 4554) +++ trunk/milena/tests/morpho/tree/filter/filter.cc (revision 4555) @@ -32,8 +32,7 @@ #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> -#include <mln/data/sort_psites.hh> -#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/component_tree.hh> #include <mln/morpho/tree/compute_attribute_image.hh> #include <mln/morpho/attribute/card.hh> @@ -59,8 +58,7 @@ typedef p_array< mln_site_(I) > S; typedef morpho::tree::data<I,S> tree_t; - S sorted_sites = data::sort_psites_decreasing(input); - tree_t tree(input, sorted_sites, c4()); + tree_t tree = morpho::tree::min_tree(input, c4()); // Test with increasing attribute -> area closing. { Index: trunk/milena/tests/morpho/tree/dual_input_tree.cc =================================================================== --- trunk/milena/tests/morpho/tree/dual_input_tree.cc (revision 0) +++ trunk/milena/tests/morpho/tree/dual_input_tree.cc (revision 4555) @@ -0,0 +1,173 @@ +// Copyright (C) 2008, 2009 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. + +#include <mln/core/image/image1d.hh> +#include <mln/core/alias/neighb1d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/make/image.hh> +#include <mln/morpho/tree/dual_input_tree.hh> + +template <typename V, unsigned dim, unsigned dim2> +void test(V (&f_)[dim], V (&m_)[dim], V (&points_)[dim2], V (&p_)[dim2]) +{ + using namespace mln; + typedef image1d<V> I; + typedef p_array< mln_psite(I) > S; + typedef morpho::tree::data<I,S> tree_t; + + + I f = make::image(f_); + I m = make::image(m_); + + + tree_t tree = morpho::tree::dual_input_max_tree(f, m, c2()); + + mln_dn_site_piter(tree_t) p(tree); + p.start(); + for (unsigned i = 0; i < dim2; ++i, p.next()) + { + mln_assertion(p.is_valid()); + mln_assertion(p == point1d(points_[i])); + mln_assertion(tree.parent(p) == point1d(p_[i])); + } + mln_assertion(! p.is_valid()); +} + + + +int main() +{ + + using namespace mln; + + typedef value::int_u8 V; + + //V f_[] = {10, 10, 20, 20, 30, 30, 40, 40, 30, 30, 20, 20, 30, 30, 20, 20, 10, 20, 20, 10}; + //V m_[] = {10, 10, 20, 20, 30, 30, 40, 40, 30, 30, 30, 30, 30, 30, 20, 20, 15, 15, 15, 15}; + + + //V f_[] = {15, 15, 10, 10, 05, 05, 8, 8, 5, 5, 10, 10, 15, 15}; + //V m_[] = {20, 20, 18, 18, 25, 25, 8, 8, 5, 5, 10, 10, 15, 15}; + + { + V f[] = {15, 15, 15}; + V m[] = {20, 20, 20}; + V s[] = {0, 1, 2}; + V p[] = {0, 0, 0}; + test(f, m, s, p); + } + + { + V f[] = {15, 17, 17, 19, 16}; + V m[] = {15, 17, 17, 19, 16}; + V s[] = {0, 4, 1, 2, 3}; + V p[] = {0, 0, 4, 1, 1}; + + + test(f, m, s, p); + } + + { + V f[] = {15, 17, 17, 15, 18, 19}; + V m[] = {15, 17, 17, 15, 18, 19}; + V s[] = {0, 3, 1, 2, 4, 5}; + V p[] = {0, 0, 0, 1, 0, 4}; + test(f, m, s, p); + } + + // Clustering: simple connection + { + V f[] = {15, 17, 17, 15, 18, 19}; + V m[] = {15, 18, 18, 18, 18, 19}; + V s[] = {0, 3, 1, 2, 4, 5}; + V p[] = {0, 0, 0, 1, 1, 4}; + test(f, m, s, p); + } + + // Clustering: merge two nodes + { + V f[] = {15, 18, 18, 15, 18, 19}; + V m[] = {15, 18, 18, 18, 18, 19}; + V s[] = {0, 3, 1, 2, 4, 5}; + V p[] = {0, 0, 0, 1, 1, 1}; + test(f, m, s, p); + } + + // Clustering: create new node + { + V f[] = {18, 15, 18}; + V m[] = {18, 17, 18}; + V s[] = {1, 4, 0, 2}; + V p[] = {1, 1, 4, 4}; + test(f, m, s, p); + } + + // Clustering: create new node + { + V f[] = {10, 10, 12, 12}; + V m[] = {11, 11, 13, 13}; + V s[] = {0, 1, 4, 2, 3}; + V p[] = {0, 0, 0, 4, 2}; + test(f, m, s, p); + } + + // Segmentation: simple (no node creation) + { + V f[] = {8, 10, 10, 12, 12}; + V m[] = {8, 8, 8, 12, 12}; + V s[] = {0, 1, 2, 3, 4}; + V p[] = {0, 0, 0, 0, 3}; + test(f, m, s, p); + } + + // Segmentation: simple (no node creation) + { + V f[] = {8, 10, 10, 8}; + V m[] = {8, 8, 8, 8}; + V s[] = {0, 3, 1, 2}; + V p[] = {0, 0, 0, 0}; + test(f, m, s, p); + } + + // Segmentation: create node + { + V f[] = {8, 10, 10, 8}; + V m[] = {8, 9, 9, 8}; + V s[] = {0, 3, 5, 1, 2}; + V p[] = {0, 0, 0, 5, 5}; + test(f, m, s, p); + } + + // Segmentation: create a root node + { + V f[] = {8, 10, 10, 8}; + V m[] = {8, 5, 9, 8}; + V s[] = {5, 0, 3, 1, 6, 2}; // Or {5, 0, 3, 6, 1, 2} for a strict sort + V p[] = {5, 5, 5, 5, 3, 6}; + test(f, m, s, p); + } + +} Index: trunk/milena/tests/morpho/tree/Makefile.am =================================================================== --- trunk/milena/tests/morpho/tree/Makefile.am (revision 4554) +++ trunk/milena/tests/morpho/tree/Makefile.am (revision 4555) @@ -22,11 +22,13 @@ check_PROGRAMS = \ compute_attribute_image \ compute_parent \ + dual_input_tree \ data \ max compute_attribute_image_SOURCES = compute_attribute_image.cc compute_parent_SOURCES = compute_parent.cc +dual_input_tree_SOURCES = dual_input_tree.cc data_SOURCES = data.cc max_SOURCES = max.cc

1 0

milena r4554: Add fast version of dual input max tree computation and fix
by Edwin Carlinet 25 Sep '09

25 Sep '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-09-25 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add fast version of dual input max tree computation and fix. * morpho/tree/all.hh: Update. * morpho/tree/compute_parent_dual_input.hh: Remove. * morpho/tree/data.hh: Fix constructors. * morpho/tree/dual_input_tree.hh: Add dispatches for generic / low quantized algorithms. * morpho/tree/impl/dual_hqueue.hh: New. * morpho/tree/impl/dual_union_find.hh: New. * morpho/tree/impl: New. --- all.hh | 1 data.hh | 105 ++++-------- dual_input_tree.hh | 75 +++++++- impl/dual_hqueue.hh | 408 ++++++++++++++++++++++++++++++++++++++++++++++++ impl/dual_union_find.hh | 361 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 874 insertions(+), 76 deletions(-) Index: trunk/milena/mln/morpho/tree/compute_parent_dual_input.hh (deleted) =================================================================== Index: trunk/milena/mln/morpho/tree/dual_input_tree.hh =================================================================== --- trunk/milena/mln/morpho/tree/dual_input_tree.hh (revision 4553) +++ trunk/milena/mln/morpho/tree/dual_input_tree.hh (revision 4554) @@ -25,14 +25,16 @@ /// \file /// -/// Compute a canonized (parenthood) component tree from a dual input. - +/// Compute a canonized component tree from a dual input. #ifndef MLN_MORPHO_TREE_DUAL_INPUT_TREE_HH # define MLN_MORPHO_TREE_DUAL_INPUT_TREE_HH # include <mln/data/sort_psites.hh> + # include <mln/morpho/tree/data.hh> +# include <mln/morpho/tree/impl/dual_union_find.hh> +# include <mln/morpho/tree/impl/dual_hqueue.hh> namespace mln { @@ -43,44 +45,95 @@ namespace tree { - template <typename I, typename M, typename N> + /// Compute the dual input max tree using mask-based connectivity. + /// + /// \param[in] f The original image. + /// \param[in] m The connectivity mask. + /// \param[in] nbh The neighborhood of the mask. + /// + /// \return The computed tree. + /// + template <typename I, typename N> inline - morpho::tree::data< I, p_array<mln_psite(I)> > + data< I, p_array<mln_psite(I)> > dual_input_max_tree(const Image& f, - const Image<M>& m, + const Image& m, const Neighborhood<N>& nbh); # ifndef MLN_INCLUDE_ONLY - template <typename I, typename M, typename N> + namespace internal + { + + template <typename I, typename N> + inline + data< I, p_array<mln_psite(I)> > + dual_input_max_tree_dispatch(trait::image::quant::any, + const I& f, + const I& m, + const N& nbh) + { + typedef p_array<mln_psite(I)> S; + typedef data<I,S> tree_t; + + S s_f = mln::data::sort_psites_increasing(f); + S s_m = mln::data::sort_psites_increasing(m); + + tree_t tree = impl::generic::dual_union_find(f, m, s_f, s_m, nbh); + return tree; + } + + template <typename I, typename N> + inline + data< I, p_array<mln_psite(I)> > + dual_input_max_tree_dispatch(trait::image::quant::low, + const I& f, + const I& m, + const N& nbh) + { + typedef p_array<mln_psite(I)> S; + typedef data<I,S> tree_t; + + tree_t tree = impl::dual_hqueue(f, m, nbh); + return tree; + } + + } // end of namespace mln::morpho::tree::internal + + + // Facades. + template <typename I, typename N> inline morpho::tree::data< I, p_array<mln_psite(I)> > dual_input_max_tree(const Image& f_, - const Image<M>& m_, + const Image& m_, const Neighborhood<N>& nbh_) { trace::entering("morpho::tree::dual_input_max_tree"); const I& f = exact(f_); - const M& m = exact(m_); + const I& m = exact(m_); const N& nbh = exact(nbh_); mln_precondition(f.is_valid()); mln_precondition(m.is_valid()); mln_precondition(nbh.is_valid()); + mln_precondition(f.domain() == m.domain()); typedef p_array<mln_psite(I)> S; typedef data<I,S> tree_t; - S s_f = mln::data::sort_psites_increasing(f); - S s_m = mln::data::sort_psites_increasing(m); - tree_t tree(f, m, s_f, s_m, nbh); + tree_t tree = internal::dual_input_max_tree_dispatch(mln_trait_image_quant(I)(), f, m, nbh); trace::exiting("morpho::tree::dual_input_max_tree"); return tree; } + + + + # endif // ! MLN_INCLUDE_ONLY } // end of namespace mln::morpho::tree Index: trunk/milena/mln/morpho/tree/impl/dual_hqueue.hh =================================================================== --- trunk/milena/mln/morpho/tree/impl/dual_hqueue.hh (revision 0) +++ trunk/milena/mln/morpho/tree/impl/dual_hqueue.hh (revision 4554) @@ -0,0 +1,408 @@ +// Copyright (C) 2008, 2009 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. + +#ifndef MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH +# define MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH + +/// +/// \brief The dual input tree algorithm specialized for low quantized image. +/// +/// This implementation is based on P. Salembier algorithm using +/// hierachical queues. This implies a low-quantized input image so +/// that the number of queues is limited. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. +/// +/// TODO: During the canonization pass, we build the tree site set +/// from the sorted site set of f, so that we compute twice f +/// histogram (can be avoided). + +# include <mln/data/sort_psites.hh> +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/hqueues.hh> +# include <mln/util/ord.hh> + +# include <mln/value/value_array.hh> +# include <mln/value/set.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + /// Compute a tree using hqueues. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename N> + inline + data<I, p_array<mln_psite(I)> > + dual_hqueue(const Image& f, + const Image& m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I, typename N, class E> + struct shared_flood_args + { + typedef mln_psite(I) P; + typedef mln_value(I) V; + typedef p_array S; + + const I& f; + const I& m; + const N& nbh; + mln_ch_value(I, P)& parent; + + // Aux data + util::hqueues<P, V>& hqueues; + const E& extend; // site -> site functor. + value::value_array<V, bool> is_node_at_level; + value::value_array<V, P> node_at_level; + mln_ch_value(I, bool) deja_vu; + const value::set<V>& vset; + + shared_flood_args(const I& f_, + const I& m_, + const N& neigb_, + mln_ch_value(I, P)& parent_, + util::hqueues<mln_psite(I), V>& hqueues_, + const E& extend_) + : f (f_), + m (m_), + nbh (neigb_), + parent (parent_), + hqueues (hqueues_), + extend (extend_), + is_node_at_level (false), + vset (hqueues.vset()) + { + initialize(deja_vu, f); + mln::data::fill(deja_vu, false); + } + }; + + template <typename I> + inline + histo::array<mln_value(I)> + compute_histo(const I& f, const I& m, mln_value(I)& hmin, mln_psite(I)& pmin) + { + histo::array<mln_value(I)> hm = histo::compute(m); + const histo::array<mln_value(I)> hf = histo::compute(f); + + { // Retrieve hmin. + unsigned i = 0; + while (hm[i] == 0) + ++i; + hmin = hm.vset()[i]; + } + + // Merge histograms. + for (unsigned i = 0; i < hm.nvalues(); ++i) + hm[i] += hf[i]; + + // Retrieve pmin. + mln_piter(I) p(m.domain()); + for (p.start(); m(p) != hmin; p.next()) + ; + mln_assertion(p.is_valid()); + pmin = p; + + return hm; + } + + // Site -> site functor: give for all p in Domain(f), its + // equivalence in the extended domain. + // TODO: make it generic. It works only on boxed domain. + template <typename I> + struct extend + { + extend(const mln_psite(I)::delta& dp) + : dp_ (dp) + { + } + + mln_psite(I) operator() (const mln_psite(I)& p) const + { + return p + dp_; + } + + private: + const mln_psite(I)::delta dp_; + }; + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + template <typename I, typename N, typename E> + unsigned + flood(internal::shared_flood_args<I, N, E>& args, const unsigned h_idx) + { + mln_assertion(args.is_node_at_level[h_idx]); + + while (!args.hqueues[h_idx].empty()) + { + mln_psite(I) p = args.hqueues[h_idx].pop_front(); + unsigned p_idx = args.vset.index_of(args.f(p)); + + if (p_idx != h_idx) + { // Intensity mismatch: irregular case. + mln_psite(I) pext = args.extend(p); + args.parent(pext) = args.node_at_level[h_idx]; + + if (p_idx > h_idx) // Singleton with parent at h. + args.parent(p) = args.node_at_level[h_idx]; + else + { + if (!args.is_node_at_level[p_idx]) + { + args.is_node_at_level[p_idx] = true; + args.node_at_level[p_idx] = p; + } + } + } + + if (p_idx <= h_idx) + { + if (!args.f.domain().has(args.node_at_level[p_idx]) || + util::ord_strict(p, args.node_at_level[p_idx])) + { // Regular case but a representative provided by the extension. + args.parent(args.node_at_level[p_idx]) = p; + args.node_at_level[p_idx] = p; + //args.parent(p) = p; + } + args.parent(p) = args.node_at_level[p_idx]; + } + + + // Process the neighbors + mln_niter(N) n(args.nbh, p); + for_all(n) + if (args.f.domain().has(n) && !args.deja_vu(n)) + { + unsigned mn = args.vset.index_of(args.m(n)); + unsigned fn = args.vset.index_of(args.f(n)); + args.hqueues[mn].push(n); + args.deja_vu(n) = true; + + mln_psite(I) ext = args.extend(n); + // Create a node at c. + { + mln_psite(I) node = (fn == mn) ? n : ext; + if (!args.is_node_at_level[mn]) + { + args.is_node_at_level[mn] = true; + args.node_at_level[mn] = node; + } + } + + while (mn > h_idx) + mn = flood(args, mn); + } + } + + // Retrieve dad. + args.is_node_at_level[h_idx] = false; + unsigned c = h_idx; + while (c > 0 && !args.is_node_at_level[c]) + --c; + + mln_psite(I) x = args.node_at_level[h_idx]; + if (c > 0) + args.parent(x) = args.node_at_level[c]; + else + args.parent(x) = x; + + return c; + } + + template <typename I, typename N> + inline + data< I, p_array<mln_psite(I)> > + dual_hqueue(const Image& f_, + const Image& m_, + const Neighborhood<N>& neibh_) + { + trace::entering("mln::morpho::tree::impl::dual_hqueue"); + + const I& f = exact(f_); + const I& m = exact(m_); + const N& nbh = exact(neibh_); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + util::timer tm; + tm.start(); + + // Histo. + mln_psite(I) pmin; + mln_value(I) hmin; + const histo::array<mln_value(I)> histo = internal::compute_histo(f, m, hmin, pmin); + util::hqueues<P, mln_value(I)> hqueues(histo); + + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_ext = f.domain(); + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + // Process. + internal::extend extend(dp); + internal::shared_flood_args< I, N, internal::extend > + args(f, m, nbh, parent, hqueues, extend); + + unsigned r = args.vset.index_of(hmin); + args.deja_vu(pmin) = true; + args.hqueues[r].push(pmin); + args.node_at_level[r] = (f(pmin) == hmin) ? pmin : extend(pmin); + args.is_node_at_level[r] = true; + flood(args, r); + + // Attach the nodes under hmin. + unsigned i = r; + do + { + if (args.is_node_at_level[i]) + { + parent(args.node_at_level[r]) = args.node_at_level[i]; + r = i; + } + } + while (i-- > 0); + parent(args.node_at_level[r]) = args.node_at_level[r]; //root + + // Canonization and make tree site set. + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + + p_array<mln_psite(I)> s_f = mln::data::sort_psites_increasing(f); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P x = p; + P q = parent(p); + + // Case: l: m <---- m <---- f + // Or + // Case l1: m <----- f impossible. + // | + // l2: m + mln_assertion(!(d_ext.has(q) && fext(p) == fext(q) && d_ext.has(parent(q)) && q != parent(q))); + + while (d_ext.has(q) && !deja_vu(q) && (fext(q) != fext(parent(q)) || q == parent(q))) + { + s.append(q); + deja_vu(q) = true; + x = q; + q = parent(q); + } + + if (d_ext.has(q) && fext(q) == fext(parent(q)) && q != parent(q)) + { + q = (parent(x) = parent(q)); + mln_assertion(f.domain().has(q)); + } + + if (fext(q) == fext(parent(q))) + parent(x) = parent(q); + + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + + } + + std::cout << "Construction de l'arbre en " << tm << " s." << std::endl; + + data<I, S> tree(fext, parent, s); + + trace::exiting("mln::morpho::tree::impl::dual_hqueue"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_COMPUTE_PARENT_DUAL_HQUEUE_HH + + + Index: trunk/milena/mln/morpho/tree/impl/dual_union_find.hh =================================================================== --- trunk/milena/mln/morpho/tree/impl/dual_union_find.hh (revision 0) +++ trunk/milena/mln/morpho/tree/impl/dual_union_find.hh (revision 4554) @@ -0,0 +1,361 @@ +// Copyright (C) 2008, 2009 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. + +#ifndef MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH + +/// +/// \brief The generic dual input tree algorithm for high quantized image. +/// +/// This implementation is based on tarjan's union method, so that +/// image quantization does not impact on the computation time. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. + +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + namespace generic + { + + /// Compute a tree using union-find method. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param s_f The sorted site set of \p f + /// \param s_m The sorted site set of \p m. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image& f, + const Image& m, + const Site_Set<S>& s_f, + const Site_Set<S>& s_m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + // For benchmark purpose. More than 50% of the time is spent + // in find_root function. + static util::timer t_prop; + + + template <typename I> + inline + mln_psite(I) find_root(I& zpar, + const mln_psite(I)& p) + { + if (zpar(p) == p) + return p; + + t_prop.resume(); + mln_psite(I) x = zpar(p); + while (zpar(x) != x) + x = zpar(x); + + mln_psite(I) tmp; + for (mln_psite(I) y = p; y != x; y = tmp) + { + tmp = zpar(y); + zpar(y) = x; + } + t_prop.stop(); + + return x; + } + + template <typename I> + inline + void + update_m_parent(const I& f, + mln_ch_value(I, mln_psite(I))& parent, + mln_ch_value(I, bool)& deja_vu, + p_array< mln_psite(I) >& sset, + const mln_domain(I)& d_ext, + const mln_psite(I)& p) + { + typedef mln_psite(I) P; + + P q = parent(p); + P x = parent(q); + + mln_assertion(d_ext.has(q)); + + while (d_ext.has(x) && f(q) == f(x) && q != x) + { + q = x; + x = parent(q); + } + + if (!d_ext.has(x)) + { + if (f(x) == f(parent(x))) + x = (parent(q) = parent(x)); + if (f(q) != f(x)) + { + x = q; + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + } + else + { + if (x != q) + { + update_m_parent(f, parent, deja_vu, sset, d_ext, q); + x = q; + } + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + for (P i = p, tmp = parent(i); i != q; i = tmp, tmp = parent(i)) + parent(i) = x; + } + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image& f_, + const Image& m_, + const Site_Set<S>& s_f_, + const Site_Set<S>& s_m_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::dual_union_find"); + + util::timer tm; + tm.start(); + internal::t_prop.reset(); + + typedef mln_psite(I) P; + typedef unsigned L; + + const I& f = exact(f_); + const I& m = exact(m_); + const S& s_f = exact(s_f_); + const S& s_m = exact(s_m_); + const N& nbh = exact(nbh_); + + // Aux data. + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_f = f.domain(); + mln_domain(I) d_ext = f.domain(); // translate dp + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + //Process + { + // Aux data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) zpar; + + initialize(deja_vu, fext); + initialize(zpar, fext); + mln::data::fill(deja_vu, false); + + mln_bkd_piter(S) p_f(s_f); // Backward. + mln_bkd_piter(S) p_m(s_m); // Backward. + p_f.start(); + p_m.start(); + + // Main loop. + while (p_m.is_valid() || p_f.is_valid()) + { + mln_bkd_piter(S)& it = (!p_f.is_valid() || (p_m.is_valid() && f(p_f) <= m(p_m))) ? p_m : p_f; + + P p = it; + P ext = p + dp; + + // std::cout << "-------------------" << std::endl; + // std::cout << "Take " << p << " of value " << (&it == &p_m ? m(p) : f(p)) + // << " from " << (&it == &p_m ? "mask" : "f") << std::endl; + // debug::println("Parent: ", parent); + // debug::println("Zpar: ", zpar); + + mln_assertion(!(deja_vu(p) && deja_vu(ext))); + if (deja_vu(ext)) // Seen by mask before f. + { + mln_assertion(m(p) >= f(p)); + // Make set. + parent(p) = p; + zpar(p) = p; + + P r = internal::find_root(zpar, ext); + zpar(r) = p; + parent(r) = p; + + deja_vu(p) = true; + } + else if (deja_vu(p)) // Seen by f before mask. + { + mln_assertion(f(p) > m(p)); + parent(p) = ext; + zpar(p) = ext; + parent(ext) = ext; + zpar(ext) = ext; + + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + //std::cout << "Root: " << r << std::endl; + if (r != ext) + { + parent(r) = ext; + zpar(r) = ext; + } + } + deja_vu(ext) = true; + } + else if (f(p) <= m(p)) // First time p encountered. + { + zpar(ext) = ext; + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + if (r != ext) + { + zpar(r) = ext; + parent(r) = ext; + } + } + deja_vu(ext) = true; + } + else + { + deja_vu(p) = true; + } + it.next(); + } + } + std::cout << ">> MAJ zpar: " << internal::t_prop << " s" << std::endl; + std::cout << "Parent construction: " << tm << " s" << std::endl; + tm.restart(); + + // Canonization + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P q = parent(p); + if (!f.domain().has(q)) + internal::update_m_parent(fext, parent, deja_vu, s, d_ext, p); + else if (fext(parent(q)) == f(q)) + parent(p) = parent(q); + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + } + std::cout << "Canonization: " << tm << " s" << std::endl; + + //mln_postcondition(internal::compute_parent_postconditions(fext, s, parent)); + + tree::data<I, p_array<mln_psite(I)> > tree(fext, parent, s); + trace::exiting("morpho::tree::impl::generic::dual_union_find"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH Index: trunk/milena/mln/morpho/tree/all.hh =================================================================== --- trunk/milena/mln/morpho/tree/all.hh (revision 4553) +++ trunk/milena/mln/morpho/tree/all.hh (revision 4554) @@ -48,6 +48,7 @@ # include <mln/morpho/tree/compute_attribute_image.hh> # include <mln/morpho/tree/compute_parent.hh> +# include <mln/morpho/tree/dual_input_tree.hh> # include <mln/morpho/tree/data.hh> # include <mln/morpho/tree/max.hh> # include <mln/morpho/tree/utils.hh> Index: trunk/milena/mln/morpho/tree/data.hh =================================================================== --- trunk/milena/mln/morpho/tree/data.hh (revision 4553) +++ trunk/milena/mln/morpho/tree/data.hh (revision 4554) @@ -32,7 +32,6 @@ /// of S container iterator) to go faster. # include <mln/morpho/tree/compute_parent.hh> -# include <mln/morpho/tree/compute_parent_dual_input.hh> # include <mln/core/site_set/p_array.hh> # include <mln/core/internal/site_set_iterator_base.hh> # include <mln/core/internal/piter_identity.hh> @@ -138,18 +137,18 @@ typedef mln::morpho::tree::depth1st_piter<self_> depth1st_piter; - /// Constructor. + /// Standard constructor. template <typename N> - data(const Image& f, const Site_Set<S>& s, const Neighborhood<N>& nbh); - - /// Constructor. - template <typename N, typename M> data(const Image& f, - const Image<M>& m, - const Site_Set<S>& s_f, - const Site_Set<S>& s_m, + const Site_Set<S>& s, const Neighborhood<N>& nbh); + /// Special constructor where the parent computation has + /// delegated to an external function. (To handle special case + /// of connectivity for example). + data(const Image& f, + const parent_t& parent, + const Site_Set<S>& s); /// \{ Base function-related materials @@ -205,13 +204,18 @@ unsigned nroots() const; protected: - const function& f_; - const sites_t s_; + void compute_children_(); + + protected: mln_ch_value(I, mln_psite(I)) parent_; // Parent image. mln_ch_value(I, nodes_t) children_; // Children image. - nodes_t nodes_; - leaves_t leaves_; - unsigned nroots_; + + function f_; // f image containing values of the tree nodes. + sites_t s_; // Sorted site set of the tree sites. (domain(f_) includes s_). + + nodes_t nodes_; // Sorted node set. + leaves_t leaves_; // Sorted leaf set. + unsigned nroots_; // For non-contigous domain image purpose. }; @@ -403,43 +407,15 @@ { template <typename I, typename S> - template <typename N, typename M> inline data<I, S>::data(const Image& f, - const Image<M>& m, - const Site_Set<S>& s_f, - const Site_Set<S>& s_m, - const Neighborhood<N>& nbh) - : f_(exact(f)), - s_(exact(s_f)) - { - const N& nbh_ = exact(nbh); - - // Compute parent image. - parent_ = morpho::tree::compute_parent_dual_input(f_, m, nbh_, s_, s_m); - initialize(children_, f); - - // Store tree nodes. - nroots_ = 0; - mln_bkd_piter(S) p(s_); - for_all(p) - { - if (f_(parent_(p)) != f_(p)) - { - nodes_.insert(p); - children_(parent_(p)).insert(p); - if (is_a_leaf(p)) - leaves_.insert(p); - } - else if (parent_(p) == p) //it's a root. + const mln_ch_value(I, mln_psite(I))& parent, + const Site_Set<S>& s) + : parent_ (parent), + f_ (exact(f)), + s_ (exact(s)) { - nodes_.insert(p); - if (is_a_leaf(p)) // One pixel image... - leaves_.insert(p); - ++nroots_; - } - } - mln_assertion(leaves_.nsites() > 0); + compute_children_(); } @@ -447,15 +423,25 @@ template <typename I, typename S> template <typename N> inline - data<I,S>::data(const Image& f, const Site_Set<S>& s, const Neighborhood<N>& nbh) + data<I,S>::data(const Image& f, + const Site_Set<S>& s, + const Neighborhood<N>& nbh) : f_(exact(f)), s_(exact(s)) { - const N& nbh_ = exact(nbh); - // Compute parent image. + const N& nbh_ = exact(nbh); parent_ = morpho::tree::compute_parent(f_, nbh_, s_); - initialize(children_, f); + + compute_children_(); + } + + template <typename I, typename S> + inline + void + data<I, S>::compute_children_() + { + initialize(children_, f_); // Store tree nodes. nroots_ = 0; @@ -480,24 +466,13 @@ mln_assertion(leaves_.nsites() > 0); } + template <typename I, typename S> inline mln_rvalue_(mln_ch_value(I, mln_psite(I))) data<I,S>::parent(const mln_psite(I)& p) const { - // HERE - -// mln_precondition(is_valid()); -// mln_rvalue(parent_t) tmp; -// if (! parent_.domain().has(p)) -// { -// std::cout << "KO next" << std::endl; -// std::cout << p << std::endl; -// std::cout << parent_.domain() << std::endl; -// } -// else -// std::cout << "ok next" << std::endl; -// mln_precondition(parent_.domain().has(p)); + mln_precondition(parent_.domain().has(p)); return parent_(p); }

1 0

milena r4553: Fix non generic stuff in translation function and fix transform morpher
by Edwin Carlinet 25 Sep '09

25 Sep '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-09-25 Edwin Carlinet <carlinet(a)lrde.epita.fr> Fix non generic stuff in translation function and fix transform morpher. * core/image/imorph/tr_image.hh, * core/site_set/p_transformed.hh, * core/site_set/p_transformed_piter.hh: Make them less strict with function return type. Allow functions having values that can be converted in the requested site. (ex: vector<1, u> -> point1d). * fun/p2p/translation.hh: Add argument type definition. * fun/x2x/translation.hh: Add inverse function. * geom/translate.hh: Fix non generic stuff and bug. --- core/image/imorph/tr_image.hh | 4 ++-- core/site_set/p_transformed.hh | 8 +++++--- core/site_set/p_transformed_piter.hh | 5 +++-- fun/p2p/translation.hh | 1 + fun/x2x/translation.hh | 10 ++++++++++ geom/translate.hh | 26 +++++++++++++------------- 6 files changed, 34 insertions(+), 20 deletions(-) Index: trunk/milena/mln/core/site_set/p_transformed.hh =================================================================== --- trunk/milena/mln/core/site_set/p_transformed.hh (revision 4552) +++ trunk/milena/mln/core/site_set/p_transformed.hh (revision 4553) @@ -33,7 +33,7 @@ # include <mln/core/internal/site_set_base.hh> # include <mln/core/concept/function.hh> - +# include <mln/convert/from_to.hh> namespace mln { @@ -81,7 +81,7 @@ template <typename S, typename F> class p_transformed : public internal::site_set_base_< mln_psite(S), p_transformed<S,F> >, - private metal::equal< mln_result(F), mln_psite(S) >::check_t + private mlc_converts_to(mln_result(F), mln_psite(S))::check_t { typedef p_transformed<S,F> self_; typedef internal::site_set_base_<mln_result(F), self_> super_; @@ -171,7 +171,9 @@ bool p_transformed<S,F>::has(const psite& p) const { - return s_.has(f_(p)); + mln_argument(F) arg; + convert::from_to(p, arg); + return s_.has(f_.inverse(arg)); } template <typename S, typename F> Index: trunk/milena/mln/core/site_set/p_transformed_piter.hh =================================================================== --- trunk/milena/mln/core/site_set/p_transformed_piter.hh (revision 4552) +++ trunk/milena/mln/core/site_set/p_transformed_piter.hh (revision 4553) @@ -32,6 +32,7 @@ # include <mln/core/internal/site_set_iterator_base.hh> # include <mln/core/site_set/p_transformed.hh> +# include <mln/convert/to.hh> namespace mln @@ -123,7 +124,7 @@ { pi_.start(); if (pi_.is_valid()) - p_ = s_->function()(pi_); + p_ = s_->function()(convert::to<mln_argument(F)>(pi_)); } template <typename Pi, typename S, typename F> @@ -133,7 +134,7 @@ { pi_.next(); if (pi_.is_valid()) - p_ = s_->function()(pi_); + p_ = s_->function()(convert::to<mln_argument(F)>(pi_)); } template <typename Pi, typename S, typename F> Index: trunk/milena/mln/core/image/imorph/tr_image.hh =================================================================== --- trunk/milena/mln/core/image/imorph/tr_image.hh (revision 4552) +++ trunk/milena/mln/core/image/imorph/tr_image.hh (revision 4553) @@ -81,12 +81,12 @@ // template <typename S, typename I, typename T> struct tr_image : - public mln::internal::image_identity< I, mln_domain(I), tr_image<S,I,T> > + public mln::internal::image_identity< I, S, tr_image<S,I,T> > { /// Super type. typedef - mln::internal::image_identity< I, mln_domain(I), tr_image<S,I,T> > super_; + mln::internal::image_identity< I, S, tr_image<S,I,T> > super_; /// Point_Site associated type. typedef mln_psite(I) psite; Index: trunk/milena/mln/geom/translate.hh =================================================================== --- trunk/milena/mln/geom/translate.hh (revision 4552) +++ trunk/milena/mln/geom/translate.hh (revision 4553) @@ -35,10 +35,10 @@ # include <mln/core/concept/box.hh> # include <mln/core/routine/extend.hh> - +# include <mln/core/site_set/p_transformed.hh> # include <mln/core/image/imorph/tr_image.hh> -# include <mln/data/paste.hh> +# include <mln/data/fill.hh> # include <mln/fun/x2x/translation.hh> @@ -105,22 +105,22 @@ const I& input = exact(input_); const S& output_domain = exact(output_domain_); const mln_exact(Ext)& extension = exact(extension_); - mlc_converts_to(mln_exact(Ext), mln_value(I))::check(); + //mlc_converts_to(mln_exact(Ext), mln_value(I))::check(); mln_precondition(input.is_valid()); mln_precondition(output_domain.is_valid()); - point2d c = geom::bbox(input).center(); - typedef fun::x2x::translation<2,double> trans_t; - trans_t - t(ref); - - tr_image<S,I,trans_t> tr_ima(output_domain, input, t); - - mln_concrete(I) output; - initialize(output, tr_ima); + //mln_psite(I) c = geom::bbox(input).center(); + typedef fun::x2x::translation<mln_site_(I)::dim, V> trans_t; + typedef p_transformed<mln_domain(I), trans_t> trans_domain_t; + typedef tr_image<trans_domain_t, I, trans_t> tr_ima_t; + + trans_t t(ref); + trans_domain_t d(input.domain(), t); + tr_ima_t tr_ima(d, input, t); - data::paste(extend(tr_ima, extension), output); + mln_concrete(I) output(output_domain); + data::fill(output, extend(tr_ima, extension) | output_domain); trace::exiting("geom::translate"); return output; Index: trunk/milena/mln/fun/p2p/translation.hh =================================================================== --- trunk/milena/mln/fun/p2p/translation.hh (revision 4552) +++ trunk/milena/mln/fun/p2p/translation.hh (revision 4553) @@ -47,6 +47,7 @@ struct translation_t : public Function_v2v< translation_t > { typedef P result; + typedef P argument; translation_t(const mln_delta(P)& dp); Index: trunk/milena/mln/fun/x2x/translation.hh =================================================================== --- trunk/milena/mln/fun/x2x/translation.hh (revision 4552) +++ trunk/milena/mln/fun/x2x/translation.hh (revision 4553) @@ -66,6 +66,8 @@ /// Perform the translation of the given vector algebra::vec<n,C> operator()(const algebra::vec<n,C>& v) const; + algebra::vec<n,C> inverse(const algebra::vec<n,C>& v) const; + /// Set a net translation vector. void set_t(const algebra::vec<n,C>& t); @@ -106,6 +108,14 @@ template <unsigned n, typename C> inline + algebra::vec<n,C> + translation<n,C>::inverse(const algebra::vec<n,C>& v) const + { + return v - t_; + } + + template <unsigned n, typename C> + inline translation<n,C> translation<n,C>::inv() const {

1 0

milena r4552: Add hierarchical queues for Salembier's algorithm
by Edwin Carlinet 25 Sep '09

25 Sep '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2009-09-25 Edwin Carlinet <carlinet(a)lrde.epita.fr> Add hierarchical queues for Salembier's algorithm. * core/site_set/p_queue_fast.hh: Add empty method. * util/all.hh: Update. * util/hqueues.hh: New. * value/all.hh: Update. * value/value_array.hh: New. Create an array indexed by a given type. (Similar to histo::array but the values are not limited to unsigned type). --- core/site_set/p_queue_fast.hh | 11 ++ util/all.hh | 1 util/hqueues.hh | 159 ++++++++++++++++++++++++++++++++++++ value/all.hh | 2 value/value_array.hh | 184 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 356 insertions(+), 1 deletion(-) Index: trunk/milena/mln/core/site_set/p_queue_fast.hh =================================================================== --- trunk/milena/mln/core/site_set/p_queue_fast.hh (revision 4551) +++ trunk/milena/mln/core/site_set/p_queue_fast.hh (revision 4552) @@ -111,6 +111,8 @@ /// Give the number of sites. unsigned nsites() const; + /// Test if the queue is empty. + bool empty() const; /// Push a site \p p in the queue. void push(const P& p); @@ -244,6 +246,15 @@ template <typename P> inline + bool + p_queue_fast::empty() const + { + mln_invariant(end_ >= begin_); + return end_ == begin_; + } + + template <typename P> + inline void p_queue_fast::push(const P& p) { Index: trunk/milena/mln/value/all.hh =================================================================== --- trunk/milena/mln/value/all.hh (revision 4551) +++ trunk/milena/mln/value/all.hh (revision 4552) @@ -53,7 +53,7 @@ # include <mln/value/interval.hh> # include <mln/value/label.hh> # include <mln/value/proxy.hh> - +# include <mln/value/value_array.hh> // FIXME: that includes concept/image.hh! Index: trunk/milena/mln/value/value_array.hh =================================================================== --- trunk/milena/mln/value/value_array.hh (revision 0) +++ trunk/milena/mln/value/value_array.hh (revision 4552) @@ -0,0 +1,184 @@ +// Copyright (C) 2009 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. + +#ifndef MLN_VALUE_VALUE_ARRAY_HH +# define MLN_VALUE_VALUE_ARRAY_HH + +/// \file +/// +/// Define a generic array indexed by an iterable type. + +# include <mln/value/set.hh> + + +namespace mln +{ + + namespace value + { + + + /// Generic array class over indexed by a value set with type \c T. + template <typename T, typename V> + struct value_array + { + enum { + nvalues = mln_card(T) + }; + + /// Constructors. + /// { + value_array(); + value_array(const V& v); + value_array(const value_array<T, V>& other); + value_array& operator=(const value_array<T, V>& other); + /// } + + /// Access elements through a value of \p T. + /// { + const V& operator()(const T& v) const; + V& operator()(const T& v); + /// } + + /// Access elements through array indexes. + /// { + const V& operator[](unsigned i) const; + V& operator[](unsigned i); + /// } + + /// Reference to the set of \p T. + const mln::value::set<T>& vset() const; + + protected: + + const mln::value::set<T>& s_; + V v_[nvalues]; + }; + + + template <typename T, typename V> + std::ostream& operator<<(std::ostream& ostr, const value_array<T, V>& a); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T, typename V> + inline + value_array<T,V>::value_array() + : s_ (mln::value::set<T>::the()) + { + typedef value::internal::iterable_set< T, set<T> > U; + mlc_is(set<T>, U)::check(); + } + + template <typename T, typename V> + inline + value_array<T,V>::value_array(const V& v) + : s_(mln::value::set<T>::the()) + { + typedef value::internal::iterable_set< T, set<T> > U; + mlc_is(set<T>, U)::check(); + + memset(v_, v, nvalues * sizeof(V)); + } + + template <typename T, typename V> + inline + value_array<T,V>::value_array(const value_array<T, V>& other) + : s_(other.s_) + { + memcpy(v_, other.v_, nvalues * sizeof(V)); + } + + template <typename T, typename V> + inline + value_array<T,V>& + value_array<T,V>::operator=(const value_array<T, V>& other) + { + if (&other != this) + memcpy(v_, other.v_, nvalues * sizeof(V)); + return *this; + } + + template <typename T, typename V> + inline + const V& + value_array<T,V>::operator()(const T& v) const + { + return v_[s_.index_of(v)]; + } + + template <typename T, typename V> + inline + V& + value_array<T,V>::operator()(const T& v) + { + return v_[s_.index_of(v)]; + } + + template <typename T, typename V> + inline + const mln::value::set<T>& + value_array<T,V>::vset() const + { + return s_; + } + + template <typename T, typename V> + inline + const V& + value_array<T,V>::operator[](unsigned i) const + { + mln_precondition(i < nvalues); + return v_[i]; + } + + template <typename T, typename V> + inline + V& + value_array<T,V>::operator[](unsigned i) + { + mln_precondition(i < nvalues); + return v_[i]; + } + + template <typename T, typename V> + inline + std::ostream& operator<<(std::ostream& ostr, const value_array<T,V>& a) + { + mln_viter(mln::value::set<T>) v(a.vset()); + for_all(v) + ostr << v << ':' << h(v) << ' '; + return ostr; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::value + +} // end of namespace mln + + +#endif // ! MLN_VALUE_VALUE_ARRAY_HH Index: trunk/milena/mln/util/all.hh =================================================================== --- trunk/milena/mln/util/all.hh (revision 4551) +++ trunk/milena/mln/util/all.hh (revision 4552) @@ -51,6 +51,7 @@ # include <mln/util/dindex.hh> # include <mln/util/eat.hh> # include <mln/util/edge.hh> +# include <mln/util/hqueues.hh> # include <mln/util/graph.hh> # include <mln/util/greater_point.hh> # include <mln/util/greater_psite.hh> Index: trunk/milena/mln/util/hqueues.hh =================================================================== --- trunk/milena/mln/util/hqueues.hh (revision 0) +++ trunk/milena/mln/util/hqueues.hh (revision 4552) @@ -0,0 +1,159 @@ +// Copyright (C) 2008, 2009 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. + +#ifndef MLN_UTIL_HQUEUES_HH +# define MLN_UTIL_HQUEUES_HH + +/// +/// \brief Generic class for hierarchical queues. +/// +/// Hierarchical queues are often used with connected operators +/// (P. Salemebier's max tree algorithm relies on these queues). To be +/// efficient, the hiererachy is a static array and each are +/// preallocated using an histogram. +/// +/// FIXME: consider hqueues as a site set ? + + +# include <mln/core/site_set/p_queue_fast.hh> +# include <mln/histo/array.hh> +# include <mln/value/set.hh> + + +namespace mln +{ + + namespace util + { + + template <typename P, typename T> + struct hqueues + { + enum { + nvalues = mln_card(T) + }; + + hqueues(const histo::array<T>& h); + + const p_queue_fast& operator[](unsigned i) const; + p_queue_fast& operator[](unsigned i); + + const p_queue_fast& operator()(const T& v) const; + p_queue_fast& operator()(const T& v); + + const mln::value::set<T>& vset() const; + + protected: + void pre_allocate_(unsigned i); + + const histo::array<T>& h_; + const mln::value::set<T>& s_; + std::vector<bool> allocated_; + std::vector< p_queue_fast >queues_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P, typename T> + inline + hqueues<P,T>::hqueues(const histo::array<T>& h) + : h_ (h), + s_ (mln::value::set<T>::the()), + allocated_ (nvalues, false), + queues_ (nvalues) + { + } + + template <typename P, typename T> + inline + void + hqueues<P,T>::pre_allocate_(unsigned i) + { + mln_precondition(i < nvalues); + if (!allocated_[i]) + { + queues_[i].reserve(h_[i]); + allocated_[i] = true; + } + } + + + template <typename P, typename T> + inline + const p_queue_fast& + hqueues<P,T>::operator[](unsigned i) const + { + mln_precondition(i < nvalues); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + p_queue_fast& + hqueues<P,T>::operator[](unsigned i) + { + mln_precondition(i < nvalues); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + const p_queue_fast& + hqueues<P,T>::operator()(const T& v) const + { + unsigned i = s_.index_of(v); + pre_allocate_(i); + return queues_[i]; + } + + template <typename P, typename T> + inline + p_queue_fast& + hqueues<P,T>::operator()(const T& v) + { + unsigned i = s_.index_of(v); + pre_allocate_(i); + return queues_[i]; + } + + + template <typename P, typename T> + inline + const mln::value::set<T>& + hqueues<P,T>::vset() const + { + return s_; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util + +} // end of namespace mln + +#endif // !MLN_UTIL_HQUEUES_HH

1 0