* scribo/layout/internal/voronoi/bbox2d.hh, * scribo/layout/internal/voronoi/distance.hh, * scribo/layout/internal/voronoi/distribution.hh, * scribo/layout/internal/voronoi/filter.hh, * scribo/layout/internal/voronoi/flooding.hh, * scribo/layout/internal/voronoi/labeling.hh, * scribo/layout/internal/voronoi/outline.hh, * scribo/layout/internal/voronoi/sort.hh, * scribo/layout/voronoi.hh, * tests/layout/voronoi.cc: New. * tests/layout/Makefile.am: Add new target. --- scribo/ChangeLog | 17 + scribo/scribo/layout/internal/voronoi/bbox2d.hh | 201 ++++++++++ scribo/scribo/layout/internal/voronoi/distance.hh | 156 ++++++++ .../scribo/layout/internal/voronoi/distribution.hh | 195 ++++++++++ scribo/scribo/layout/internal/voronoi/filter.hh | 115 ++++++ scribo/scribo/layout/internal/voronoi/flooding.hh | 283 ++++++++++++++ scribo/scribo/layout/internal/voronoi/labeling.hh | 163 ++++++++ scribo/scribo/layout/internal/voronoi/outline.hh | 386 ++++++++++++++++++++ .../internal/{hist_info.hh => voronoi/sort.hh} | 61 +++- scribo/scribo/layout/voronoi.hh | 197 ++++++++++ scribo/tests/layout/Makefile.am | 6 +- scribo/tests/layout/voronoi.cc | 151 ++++++++ 12 files changed, 1913 insertions(+), 18 deletions(-) create mode 100644 scribo/scribo/layout/internal/voronoi/bbox2d.hh create mode 100644 scribo/scribo/layout/internal/voronoi/distance.hh create mode 100644 scribo/scribo/layout/internal/voronoi/distribution.hh create mode 100644 scribo/scribo/layout/internal/voronoi/filter.hh create mode 100644 scribo/scribo/layout/internal/voronoi/flooding.hh create mode 100644 scribo/scribo/layout/internal/voronoi/labeling.hh create mode 100644 scribo/scribo/layout/internal/voronoi/outline.hh copy scribo/scribo/layout/internal/{hist_info.hh => voronoi/sort.hh} (57%) create mode 100644 scribo/scribo/layout/voronoi.hh create mode 100644 scribo/tests/layout/voronoi.cc diff --git a/scribo/ChangeLog b/scribo/ChangeLog index 90de65c..03d1928 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,3 +1,20 @@ +2013-05-14 Guillaume Lazzara <z@lrde.epita.fr> + + Add Voronoi layout analysis algorithm. + + * scribo/layout/internal/voronoi/bbox2d.hh, + * scribo/layout/internal/voronoi/distance.hh, + * scribo/layout/internal/voronoi/distribution.hh, + * scribo/layout/internal/voronoi/filter.hh, + * scribo/layout/internal/voronoi/flooding.hh, + * scribo/layout/internal/voronoi/labeling.hh, + * scribo/layout/internal/voronoi/outline.hh, + * scribo/layout/internal/voronoi/sort.hh, + * scribo/layout/voronoi.hh, + * tests/layout/voronoi.cc: New. + + * tests/layout/Makefile.am: Add new target. + 2013-04-26 Guillaume Lazzara <z@lrde.epita.fr> * scribo/binarization/sauvola_ms_split.hh: Make use of all arguments. diff --git a/scribo/scribo/layout/internal/voronoi/bbox2d.hh b/scribo/scribo/layout/internal/voronoi/bbox2d.hh new file mode 100644 index 0000000..5062713 --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/bbox2d.hh @@ -0,0 +1,201 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief 2D Bounding box class used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_BBOX2D_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_BBOX2D_HH + +# include <mln/core/alias/point2d.hh> + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + + using namespace mln; + + class bbox2d + { + public: + bbox2d(); + + bbox2d(const unsigned n, + const point2d& pmin, + const point2d& pmax); + + void extend(const point2d& p); + void extend(const bbox2d& b); + + point2d& pmin(); + const point2d& pmin() const; + + point2d& pmax(); + const point2d& pmax() const; + + point2d pcenter() const; + + unsigned bbox_number() const; + + void set_bbox_number(const unsigned id); + + private: + unsigned n_; + point2d pmin_; + point2d pmax_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + //--------------------------- + // Bounding box 2D + //--------------------------- + + inline + bbox2d::bbox2d() + : n_(0), pmin_(point2d(0, 0)), pmax_(point2d(0, 0)) + { + } + + inline + bbox2d::bbox2d(const unsigned n, + const point2d& pmin, + const point2d& pmax) + : n_(n), pmin_(pmin), pmax_(pmax) + { + } + + inline + void + bbox2d::extend(const point2d& p) + { + const int col = p.col(); + const int row = p.row(); + + if (col < pmin_.col()) + pmin_.col() = col; + + if (col > pmax_.col()) + pmax_.col() = col; + + if (row < pmin_.row()) + pmin_.row() = row; + + if (row > pmax_.row()) + pmax_.row() = row; + } + + inline + void + bbox2d::extend(const bbox2d& b) + { + if (b.pmin().col() < pmin_.col()) + pmin_.col() = b.pmin().col(); + + if (b.pmin().row() < pmin_.row()) + pmin_.row() = b.pmin().row(); + + if (b.pmax().col() > pmax_.col()) + pmax_.col() = b.pmax().col(); + + if (b.pmax().row() > pmax_.row()) + pmax_.row() = b.pmax().row(); + } + + inline + point2d& + bbox2d::pmin() + { + return pmin_; + } + + inline + const point2d& + bbox2d::pmin() const + { + return pmin_; + } + + inline + point2d& + bbox2d::pmax() + { + return pmax_; + } + + inline + const point2d& + bbox2d::pmax() const + { + return pmax_; + } + + inline + point2d + bbox2d::pcenter() const + { + point2d p(pmin_.row() + (pmax_.row() - pmin_.row()) / 2, + pmin_.col() + (pmax_.col() - pmin_.col()) / 2); + + return p; + } + + inline + unsigned + bbox2d::bbox_number() const + { + return n_; + } + + inline + void + bbox2d::set_bbox_number(const unsigned id) + { + n_ = id; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_BBOX2D_HH + diff --git a/scribo/scribo/layout/internal/voronoi/distance.hh b/scribo/scribo/layout/internal/voronoi/distance.hh new file mode 100644 index 0000000..bf46b82 --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/distance.hh @@ -0,0 +1,156 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTANCE_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTANCE_HH + + +# include <climits> +# include <map> +# include <vector> +# include <mln/core/alias/point2d.hh> +# include <mln/util/ord_pair.hh> +# include <mln/util/graph.hh> +# include <scribo/layout/internal/voronoi/flooding.hh> + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + + using namespace mln; + using namespace internal::voronoi; + + + int euclidean_distance(const point2d& p1, + const point2d& p2); + + int components_min_distance(const outline_bbox& o_b1, + const outline_bbox& o_b2); + + void compute_adjacency_distances(const std::vector<outline_bbox>& bbox_list, + util::graph& rag, + std::map<util::ord_pair<unsigned>, + int>& distances, + int& max_distance); + +# ifndef MLN_INCLUDE_ONLY + + inline + int euclidean_distance(const point2d& p1, + const point2d& p2) + { + const int delta_x = p1.col() - p2.col(); + const int delta_y = p1.row() - p2.row(); + + return (delta_x * delta_x + delta_y * delta_y); + } + + inline + int components_min_distance(const outline_bbox& o_b1, + const outline_bbox& o_b2) + { + const std::vector<point2d>& points_b1 = o_b1.outline_points; + const std::vector<point2d>& points_b2 = o_b2.outline_points; + const unsigned nelements_b1 = points_b1.size(); + const unsigned nelements_b2 = points_b2.size(); + int min_distance = INT_MAX; + + for (unsigned i = 0; i < nelements_b1; ++i) + { + const point2d& p1 = points_b1[i]; + + for (unsigned j = 0; j < nelements_b2; ++j) + { + const point2d& p2 = points_b2[j]; + const int distance = euclidean_distance(p1, p2); + + if (distance < min_distance) + min_distance = distance; + } + } + + return min_distance; + } + + inline + void compute_adjacency_distances(const std::vector<outline_bbox>& bbox_list, + util::graph& rag, + std::map<util::ord_pair<unsigned>, + int>& distances, + int& max_distance) + { + std::map<unsigned, std::vector<unsigned> > neighbors_seen; + mln_edge_iter_(util::graph) e(rag); + + for_all(e) + { + const unsigned v1 = e.v1(); + const unsigned v2 = e.v2(); + + const std::vector<unsigned>& n = neighbors_seen[v1]; + + if (std::find(n.begin(), n.end(), v2) != n.end()) + continue; + + neighbors_seen[v1].push_back(v2); + neighbors_seen[v2].push_back(v1); + + int min_distance = components_min_distance(bbox_list[v1 - 1], + bbox_list[v2 - 1]); + + min_distance = round(sqrt(min_distance)); + + if (min_distance > max_distance) + max_distance = min_distance; + + distances[util::ord_pair<unsigned>(v1, v2)] = min_distance; + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTANCE_HH + diff --git a/scribo/scribo/layout/internal/voronoi/distribution.hh b/scribo/scribo/layout/internal/voronoi/distribution.hh new file mode 100644 index 0000000..726ae01 --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/distribution.hh @@ -0,0 +1,195 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTRIBUTION_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTRIBUTION_HH + +# include <climits> +# include <cstdlib> +# include <vector> +# include <map> +# include <mln/util/ord_pair.hh> + + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + using namespace mln; + + void compute_peaks(const std::vector<int>& distribution, + const float t, + int& td1, + int& td2); + + void compute_distribution(const int max_distance, + const std::map<util::ord_pair<unsigned>, + int>& distances, + const float t, + int& td1, + int& td2); + +# ifndef MLN_INCLUDE_ONLY + + inline + void compute_peaks(const std::vector<int>& distribution, + const float t, + int& td1, + int& td2) + { + const int nelements = distribution.size(); + int peak_index1 = 0; + int peak_index2 = 0; + int peak_value1 = 0; + int peak_value2 = 0; + + for (int i = 0; i < nelements; ++i) + { + const int index_min = i - 1; + const int index_max = i + 1; + + if (index_min < 0 || index_max >= nelements) + continue; + + if (distribution[index_min] < distribution[i] && + distribution[index_max] < distribution[i]) + { + if (distribution[i] > peak_value1) + { + peak_index2 = peak_index1; + peak_value2 = peak_value1; + peak_index1 = i; + peak_value1 = distribution[i]; + } + else if (distribution[i] > peak_value2) + { + peak_index2 = i; + peak_value2 = distribution[i]; + } + } + } + + int td2_value = 0; + + if (peak_index1 < peak_index2) + { + td1 = peak_index1; + td2 = peak_index2; + td2_value = peak_value2 * t; + } + else + { + td1 = peak_index2; + td2 = peak_index1; + td2_value = peak_value1 * t; + } + + int min_delta = INT_MAX; + + for (int i = td2 + 1; i < nelements; ++i) + { + const int delta = abs(distribution[i] - td2_value); + + if (delta == 0) + { + td2 = i; + break; + } + + if (delta < min_delta) + { + td2 = i; + min_delta = delta; + } + } + } + + inline + void compute_distribution(const int max_distance, + const std::map<util::ord_pair<unsigned>, + int>& distances, + const float t, + int& td1, + int& td2) + { + const int nelements = max_distance + 1; + const int window = 2; + std::vector<int> distribution(nelements, 0); + std::vector<int> smoothed_distribution(nelements, 0); + std::map<util::ord_pair<unsigned>, int>::const_iterator it_begin = + distances.begin(); + std::map<util::ord_pair<unsigned>, int>::const_iterator it_end = + distances.end(); + + for (; it_begin != it_end; ++it_begin) + ++distribution[(*it_begin).second]; + + const int factor = 2 * window + 1; + + // Smoothed distribution + for (int i = 0; i < nelements; ++i) + { + int count = 0; + + for (int j = i - window; j <= i + window; ++j) + { + if (j < 0 || j >= nelements) + continue; + + count += distribution[j]; + } + + smoothed_distribution[i] = count / factor; + } + + // Compute peaks in distribution + compute_peaks(smoothed_distribution, t, td1, td2); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_DISTRIBUTION_HH + + diff --git a/scribo/scribo/layout/internal/voronoi/filter.hh b/scribo/scribo/layout/internal/voronoi/filter.hh new file mode 100644 index 0000000..be3673a --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/filter.hh @@ -0,0 +1,115 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_FILTER_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_FILTER_HH + +# include <climits> +# include <vector> +# include <map> +# include <mln/util/ord_pair.hh> +# include <mln/util/graph.hh> +# include <scribo/layout/internal/voronoi/flooding.hh> + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + using namespace mln; + using namespace internal::voronoi; + + void invalidate_edges(const std::map<util::ord_pair<unsigned>, int>& distances, + const std::vector<outline_bbox>& bbox_list, + const util::graph& rag, + util::graph& g, + const float td1, + const float td2, + const float ta); + +# ifndef MLN_INCLUDE_ONLY + + inline + void invalidate_edges(const std::map<util::ord_pair<unsigned>, int>& distances, + const std::vector<outline_bbox>& bbox_list, + const util::graph& rag, + util::graph& g, + const float td1, + const float td2, + const float ta) + { + mln_edge_iter_(util::graph) e(rag); + + for_all(e) + { + const unsigned v1 = e.v1(); + const unsigned v2 = e.v2(); + + const outline_bbox& b1 = bbox_list[v1 - 1]; + const outline_bbox& b2 = bbox_list[v2 - 1]; + + std::map<util::ord_pair<unsigned>, int>::const_iterator it_map = + distances.find(util::ord_pair<unsigned>(v1, v2)); + + if (it_map != distances.end()) + { + const float d = (*it_map).second; + const float area1 = b1.area; + const float area2 = b2.area; + const float area_ratio = std::max(area1, area2) / + std::min(area1, area2); + const bool cond1 = (d / td1) < 1; + const bool cond2 = (d / td2 + area_ratio / ta) < 1; + + if (cond1 || cond2) + g.add_edge(e.v1(), e.v2()); + } + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_FILTER_HH + + diff --git a/scribo/scribo/layout/internal/voronoi/flooding.hh b/scribo/scribo/layout/internal/voronoi/flooding.hh new file mode 100644 index 0000000..20c463b --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/flooding.hh @@ -0,0 +1,283 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_FLOODING_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_FLOODING_HH + +# include <climits> +# include <vector> +# include <map> +# include <mln/core/image/image2d.hh> +# include <mln/util/ord_pair.hh> +# include <mln/util/graph.hh> +# include <scribo/layout/internal/voronoi/bbox2d.hh> + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + using namespace mln; + + + struct outline_bbox + { + outline_bbox(); + + bbox2d bbox; + unsigned area; + std::vector<point2d> outline_points; + }; + + void propagate(const point2d& p, + std::vector<point2d>& next_position_list, + const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned nlabels, + outline_bbox& o_b); + + void flood(const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned nlabels, + const point2d& start_pt, + outline_bbox& o_b); + + +# ifndef MLN_INCLUDE_ONLY + + //--------------------------- + // Outline bbox + //--------------------------- + + outline_bbox::outline_bbox() + : area(0) + { + } + + //--------------------------- + // Propagate + //--------------------------- + + inline + void propagate(const point2d& p, + std::vector<point2d>& next_position_list, + const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned nlabels, + outline_bbox& o_b) + { + int x = p.col(); + int y = p.row(); + int nx; + int ny; + int ncols = input.ncols(); + int nrows = input.nrows(); + + { + nx = x + 1; + + if (nx < ncols) + { + unsigned& pixel = labeled_image.at_(y, nx); + if (input.at_(y, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(y, nx)); + ++o_b.area; + } + } + } + + { + nx = x + 1; + ny = y + 1; + + if (nx < ncols && ny < nrows) + { + unsigned& pixel = labeled_image.at_(ny, nx); + if (input.at_(ny, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, nx)); + ++o_b.area; + } + } + } + + { + ny = y + 1; + + if (ny < nrows) + { + unsigned& pixel = labeled_image.at_(ny, x); + if (input.at_(ny, x) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, x)); + ++o_b.area; + } + } + } + + { + nx = x - 1; + ny = y + 1; + + if (nx >= 0 && ny < nrows) + { + unsigned& pixel = labeled_image.at_(ny, nx); + if (input.at_(ny, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, nx)); + ++o_b.area; + } + } + } + + { + nx = x - 1; + + if (nx >= 0) + { + unsigned& pixel = labeled_image.at_(y, nx); + if (input.at_(y, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(y, nx)); + ++o_b.area; + } + } + } + + { + nx = x - 1; + ny = y - 1; + + if (nx >= 0 && ny >= 0) + { + unsigned& pixel = labeled_image.at_(ny, nx); + if (input.at_(ny, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, nx)); + ++o_b.area; + } + } + } + + { + ny = y - 1; + + if (ny >= 0) + { + unsigned& pixel = labeled_image.at_(ny, x); + if (input.at_(ny, x) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, x)); + ++o_b.area; + } + } + } + + { + nx = x + 1; + ny = y - 1; + + if (nx < ncols && ny >= 0) + { + unsigned& pixel = labeled_image.at_(ny, nx); + if (input.at_(ny, nx) && !pixel) + { + pixel = nlabels; + next_position_list.push_back(point2d(ny, nx)); + ++o_b.area; + } + } + } + } + + //--------------------------- + // Flood + //--------------------------- + + inline + void flood(const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned nlabels, + const point2d& start_pt, + outline_bbox& o_b) + { + std::vector<point2d> position_list; + std::vector<point2d> next_position_list; + + next_position_list.reserve(8); + ++o_b.area; + + position_list.push_back(start_pt); + + while (! position_list.empty()) + { + next_position_list.clear(); + const unsigned nelements = position_list.size(); + + for (unsigned i = 0; i < nelements; ++i) + { + const point2d& p = position_list[i]; + + // Propagate the labeling + propagate(p, next_position_list, input, labeled_image, nlabels, o_b); + } + + position_list.clear(); + position_list = next_position_list; + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_FLOODING_HH + + diff --git a/scribo/scribo/layout/internal/voronoi/labeling.hh b/scribo/scribo/layout/internal/voronoi/labeling.hh new file mode 100644 index 0000000..c724c8b --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/labeling.hh @@ -0,0 +1,163 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_LABELING_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_LABELING_HH + + +#include <mln/core/image/image2d.hh> +#include <scribo/layout/internal/voronoi/bbox2d.hh> +#include <scribo/layout/internal/voronoi/outline.hh> + + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + using namespace mln; + + + void erase_component(image2d<bool>& input, + image2d<unsigned>& labeled_img, + const bbox2d& bbox, + const unsigned value); + + void component_labeling(image2d<bool>& input, + unsigned& nlabels, + std::vector<outline_bbox>& bbox_list, + image2d<unsigned>& labeled_image, + const unsigned sampling_interval, + const unsigned minimum_outline_length, + const unsigned maximum_width, + const unsigned maximum_height); + +# ifndef MLN_INCLUDE_ONLY + + //--------------------------- + // Erase component + //--------------------------- + + inline + void erase_component(image2d<bool>& input, + image2d<unsigned>& labeled_img, + const bbox2d& bbox, + const unsigned value) + { + box2d b(bbox.pmin(), bbox.pmax()); + mln_piter_(box2d) p(b); + + for_all(p) + { + if (labeled_img(p) == value) + { + input(p) = false; + labeled_img(p) = 0; + } + } + } + + //--------------------------- + // Component labeling + //--------------------------- + + inline + void component_labeling(image2d<bool>& input, + unsigned& nlabels, + std::vector<outline_bbox>& bbox_list, + image2d<unsigned>& labeled_image, + const unsigned sampling_interval, + const unsigned minimum_outline_length, + const unsigned maximum_width, + const unsigned maximum_height) + { + const int nrows = input.nrows(); + const int ncols = input.ncols(); + + for (int i = 0; i < nrows; ++i) + { + for (int j = 0; j < ncols; ++j) + { + if (input.at_(i, j)) + { + if (!labeled_image.at_(i, j)) + { + ++nlabels; + labeled_image.at_(i, j) = nlabels; + + point2d p(i, j); + outline_bbox o_b; + o_b.bbox = bbox2d(nlabels, p, p); + + const unsigned outline_length = + follow_outline(o_b, p, input, labeled_image, + sampling_interval, nlabels); + + const bbox2d& b = o_b.bbox; + const unsigned width = b.pmax().col() - b.pmin().col(); + const unsigned height = b.pmax().row() - b.pmin().row(); + + if (outline_length > minimum_outline_length && + width < maximum_width && + height < maximum_height) + bbox_list.push_back(o_b); + else + { + erase_component(input, labeled_image, o_b.bbox, nlabels); + --nlabels; + } + } + else + for (; input.at_(i, j); ++j); + } + } + } + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_LABELING_HH + + + diff --git a/scribo/scribo/layout/internal/voronoi/outline.hh b/scribo/scribo/layout/internal/voronoi/outline.hh new file mode 100644 index 0000000..e6e9ed8 --- /dev/null +++ b/scribo/scribo/layout/internal/voronoi/outline.hh @@ -0,0 +1,386 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Routines used in Voronoi algorithm. + + +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_OUTLINE_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_OUTLINE_HH + +#include <scribo/layout/internal/voronoi/flooding.hh> + + +namespace scribo +{ + + namespace layout + { + + namespace internal + { + + namespace voronoi + { + using namespace mln; + + + void left_up(int& direction, + const image2d<bool>& input, + const point2d& cur_pt); + + void left_up_after(int& direction, + const unsigned i); + + void right_up(int& direction, + const image2d<bool>& input, + const point2d& cur_pt); + + void right_up_after(int& direction, + const unsigned i); + + void right_down(int& direction, + const image2d<bool>& input, + const point2d& cur_pt); + + void right_down_after(int& direction, + const unsigned i); + + void left_down(int& direction, + const image2d<bool>& input, + const point2d& cur_pt); + + void left_down_after(int& direction, + const unsigned i); + + void find_next_point(const image2d<bool>& input, + point2d& cur_pt, + int& direction); + + unsigned follow_outline(outline_bbox& o_b, + const point2d& start_pt, + const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned sampling_interval, + const unsigned nlabels); + +# ifndef MLN_INCLUDE_ONLY + + //------------------------- + // Offset + //------------------------- + + static const int offset[4][8][2] = + { + { { -1, 0 }, { 0, -1 }, { -1, -1 }, { 1, 0 }, { 1, -1 }, { 0, 1 }, { + 1, 1 }, { -1, 1 } }, + { { 0, -1 }, { 1, 0 }, { 1, -1 }, { 0, 1 }, { 1, 1 }, { -1, 0 }, { + -1, 1 }, { -1, -1 } }, + { { 1, 0 }, { 0, 1 }, { 1, 1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { + -1, -1 }, { 1, -1 } }, + { { 0, 1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { -1, -1 }, { 1, 0 }, { + 1, -1 }, { 1, 1 } } + }; + + //------------------------- + // Left up + //------------------------- + + inline + void left_up(int& direction, + const image2d<bool>& input, + const point2d& cur_pt) + { + const point2d p2(cur_pt.row() + offset[direction][5][1], + cur_pt.col() + offset[direction][5][0]); + const point2d p3(cur_pt.row() + offset[direction][7][1], + cur_pt.col() + offset[direction][7][0]); + + if (!input(p2) && input(p3)) + { + direction = 3; + return; + } + } + + //------------------------- + // After left up + //------------------------- + + inline + void left_up_after(int& direction, + const unsigned i) + { + if (i == 3 || i == 4) + direction = 1; + else if (i == 5 || i == 6) + direction = 2; + else if (i == 7) + direction = 3; + } + + //------------------------- + // Right up + //------------------------- + + inline + void right_up(int& direction, + const image2d<bool>& input, + const point2d& cur_pt) + { + const point2d p1(cur_pt.row() + offset[direction][0][1], + cur_pt.col() + offset[direction][0][0]); + const point2d p2(cur_pt.row() + offset[direction][5][1], + cur_pt.col() + offset[direction][5][0]); + const point2d p3(cur_pt.row() + offset[direction][7][1], + cur_pt.col() + offset[direction][7][0]); + + if (!input(p2) && (input(p1) || input(p3))) + { + direction = 0; + return; + } + } + + //------------------------- + // After right up + //------------------------- + + inline + void right_up_after(int& direction, + const unsigned i) + { + if (i == 3 || i == 4) + direction = 2; + else if (i == 5 || i == 6) + direction = 3; + else if (i == 7) + direction = 0; + } + + //------------------------- + // Right down + //------------------------- + + inline + void right_down(int& direction, + const image2d<bool>& input, + const point2d& cur_pt) + { + const point2d p2(cur_pt.row() + offset[direction][5][1], + cur_pt.col() + offset[direction][5][0]); + const point2d p3(cur_pt.row() + offset[direction][7][1], + cur_pt.col() + offset[direction][7][0]); + + if (!input(p2) && input(p3)) + { + direction = 1; + return; + } + } + + //------------------------- + // After right down + //------------------------- + + inline + void right_down_after(int& direction, + const unsigned i) + { + if (i == 3 || i == 4) + direction = 3; + else if (i == 5 || i == 6) + direction = 0; + else if (i == 7) + direction = 1; + } + + //------------------------- + // Left down + //------------------------- + + inline + void left_down(int& direction, + const image2d<bool>& input, + const point2d& cur_pt) + { + const point2d p1(cur_pt.row() + offset[direction][0][1], + cur_pt.col() + offset[direction][0][0]); + const point2d p2(cur_pt.row() + offset[direction][5][1], + cur_pt.col() + offset[direction][5][0]); + const point2d p3(cur_pt.row() + offset[direction][7][1], + cur_pt.col() + offset[direction][7][0]); + + if (!input(p2) && (input(p1) || input(p3))) + { + direction = 2; + return; + } + } + + //------------------------- + // After left down + //------------------------- + + inline + void left_down_after(int& direction, + const unsigned i) + { + if (i == 3 || i == 4) + direction = 0; + else if (i == 5 || i == 6) + direction = 1; + else if (i == 7) + direction = 2; + } + + //------------------------- + // Find next point + //------------------------- + + inline + void find_next_point(const image2d<bool>& input, + point2d& cur_pt, + int& direction) + { + unsigned i = 0; + point2d tmp; + + switch (direction) + { + case 0: left_up(direction, input, cur_pt); break; + case 1: right_up(direction , input, cur_pt); break; + case 2: right_down(direction, input, cur_pt); break; + case 3: left_down(direction, input, cur_pt); break; + } + + for (; i < 8; ++i) + { + tmp = point2d(cur_pt.row() + offset[direction][i][1], + cur_pt.col() + offset[direction][i][0]); + + if (input(tmp)) + break; + } + + // Should not happen + if (i == 8) + return; + + switch (direction) + { + case 0: left_up_after(direction, i); break; + case 1: right_up_after(direction , i); break; + case 2: right_down_after(direction, i); break; + case 3: left_down_after(direction, i); break; + } + + cur_pt = tmp; + } + + //------------------------- + // Follow outline + //------------------------- + + inline + unsigned follow_outline(outline_bbox& o_b, + const point2d& start_pt, + const image2d<bool>& input, + image2d<unsigned>& labeled_image, + const unsigned sampling_interval, + const unsigned nlabels) + { + int direction = 0; + point2d cur_pt = start_pt; + std::vector<point2d>& points = o_b.outline_points; + unsigned sample_count = 0; + unsigned outline_count = 0; + + // Flood the connected component + flood(input, labeled_image, nlabels, start_pt, o_b); + + find_next_point(input, cur_pt, direction); + points.push_back(cur_pt); + labeled_image(cur_pt) = nlabels; + ++sample_count; + ++outline_count; + + while (cur_pt != start_pt) + { + find_next_point(input, cur_pt, direction); + ++outline_count; + o_b.bbox.extend(cur_pt); + + if (sample_count == 0) + points.push_back(cur_pt); + + ++sample_count; + + if (sample_count == sampling_interval) + sample_count = 0; + } + + find_next_point(input, cur_pt, direction); + + if (std::find(points.begin(), points.end(), cur_pt) == points.end()) + { + points.push_back(cur_pt); + + while (cur_pt != start_pt) + { + find_next_point(input, cur_pt, direction); + ++outline_count; + o_b.bbox.extend(cur_pt); + + if (sample_count == 0) + points.push_back(cur_pt); + + ++sample_count; + + if (sample_count == sampling_interval) + sample_count = 0; + } + } + + return outline_count; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout::internal::voronoi + + } // end of namespace scribo::layout::internal + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_OUTLINE_HH + + + + diff --git a/scribo/scribo/layout/internal/hist_info.hh b/scribo/scribo/layout/internal/voronoi/sort.hh similarity index 57% copy from scribo/scribo/layout/internal/hist_info.hh copy to scribo/scribo/layout/internal/voronoi/sort.hh index 13de128..6efa046 100644 --- a/scribo/scribo/layout/internal/hist_info.hh +++ b/scribo/scribo/layout/internal/voronoi/sort.hh @@ -25,11 +25,16 @@ /// \file /// -/// \brief Histogram information used in XY-Cut algorithm. +/// \brief Routines used in Voronoi algorithm. -#ifndef SCRIBO_LAYOUT_INTERNAL_HIST_INFO_HH -# define SCRIBO_LAYOUT_INTERNAL_HIST_INFO_HH +#ifndef SCRIBO_LAYOUT_INTERNAL_VORONOI_SORT_HH +# define SCRIBO_LAYOUT_INTERNAL_VORONOI_SORT_HH + +# include <mln/core/image/image2d.hh> +# include <mln/value/int_u16.hh> +# include <scribo/layout/internal/voronoi/flooding.hh> + namespace scribo { @@ -40,29 +45,55 @@ namespace scribo namespace internal { - /// \internal \brief Histogram information used in XY-Cut algorithm. - struct hist_info + namespace voronoi { - hist_info(); + using namespace mln; - unsigned horizontal; - unsigned vertical; - }; + void reorder_bbox_list(std::vector<outline_bbox>& bbox_list, + const image2d<value::int_u16>& ws); # ifndef MLN_INCLUDE_ONLY - hist_info::hist_info() - : horizontal(0), - vertical(0) - { - } + inline + void reorder_bbox_list(std::vector<outline_bbox>& bbox_list, + const image2d<value::int_u16>& ws) + { + const unsigned nelements = bbox_list.size(); + std::vector<outline_bbox> list(bbox_list.size()); + + for (unsigned i = 0; i < nelements; ++i) + { + // outline_bbox tmp = bbox_list[i]; + point2d center = bbox_list[i].bbox.pcenter(); + int index = ws(center) - 1; + + if (index < 0) + continue; + + list[i] = bbox_list[index]; + + // bbox_list[i] = bbox_list[index]; + // bbox_list[index] = tmp; + } + + bbox_list.clear(); + bbox_list = list; + } + # endif // ! MLN_INCLUDE_ONLY + } // end of namespace scribo::layout::internal::voronoi + } // end of namespace scribo::layout::internal } // end of namespace scribo::layout } // end of namespace scribo -#endif // ! SCRIBO_LAYOUT_INTERNAL_HIST_INFO_HH +#endif // ! SCRIBO_LAYOUT_INTERNAL_VORONOI_SORT_HH + + + + + diff --git a/scribo/scribo/layout/voronoi.hh b/scribo/scribo/layout/voronoi.hh new file mode 100644 index 0000000..96269ac --- /dev/null +++ b/scribo/scribo/layout/voronoi.hh @@ -0,0 +1,197 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file +/// +/// \brief Voronoi layout analysis algorithm. + +#ifndef SCRIBO_LAYOUT_VORONOI_HH +# define SCRIBO_LAYOUT_VORONOI_HH + +# include <mln/value/rgb8.hh> +# include <mln/core/alias/neighb2d.hh> +# include <mln/transform/distance_front.hh> +# include <mln/value/int_u8.hh> +# include <mln/value/int_u16.hh> +# include <mln/data/convert.hh> +# include <mln/make/w_window2d_int.hh> +# include <mln/morpho/watershed/flooding.hh> +# include <mln/util/graph.hh> +# include <mln/make/region_adjacency_graph.hh> +# include <mln/make/p_vertices_with_mass_centers.hh> +# include <mln/util/ord_pair.hh> +# include <mln/debug/draw_graph.hh> +# include <mln/literal/colors.hh> +# include <mln/pw/all.hh> +# include <mln/core/image/dmorph/image_if.hh> + +# include <scribo/layout/internal/voronoi/labeling.hh> +# include <scribo/layout/internal/voronoi/sort.hh> +# include <scribo/layout/internal/voronoi/distance.hh> +# include <scribo/layout/internal/voronoi/distribution.hh> +# include <scribo/layout/internal/voronoi/filter.hh> + +#include <mln/io/ppm/save.hh> + +namespace scribo +{ + + namespace layout + { + using namespace mln; + + /*! \brief Voronoi layout analysis algorithm. + + \param[in] ima A Binary image. + + \return A graph of connected components grouped by logical + blocks. + + \ingroup grpalgolayout + */ + template <typename I> + util::graph + voronoi(const Image<I>& ima); + + +# ifndef MLN_INCLUDE_ONLY + + + + template <typename I> + util::graph + voronoi(const Image<I>& ima_) + { + mln_trace("scribo::layout::voronoi"); + + typedef mln_value(I) V; + typedef mln_box(I) B; + mlc_is(V,bool)::check(); + + const I& ima = exact(ima_); + mln_precondition(ima.is_valid()); + + using namespace internal::voronoi; + + const box2d& domain = ima.domain(); + mln_concrete(I) input = duplicate(ima); + + //------------------------- + // Labeling + //------------------------- + + unsigned nlabels = 0; + std::vector<outline_bbox> bbox_list; + image2d<unsigned> labeled_image(domain); + component_labeling(input, nlabels, bbox_list, labeled_image, 5, 13, + 500, 500); + + bbox_list.clear(); + data::fill(labeled_image, 0); + nlabels = 0; + + component_labeling(input, nlabels, bbox_list, labeled_image, 5, 0, + 500, 500); + + + //------------------------- + // Compute Voronoi diagram + //------------------------- + + image2d<value::int_u16> ws; + value::int_u16 nbasins; + image2d<value::int_u8> dist_map; + + int vals[] = { 0, 11, 0, 11, 0, + 11, 7, 5, 7, 11, + 0, 5, 0, 5, 0, + 11, 7, 5, 7, 11, + 0, 11, 0, 11, 0 }; + + dist_map = transform::distance_front(input, c8(), + make::w_window2d_int(vals), + mln_max(value::int_u8)); + + + // Watershed transform + ws = morpho::watershed::flooding(dist_map, c8(), nbasins); + + // Reorder bounding box list + reorder_bbox_list(bbox_list, ws); + + //------------------------- + // Compute Region Adjacency Graph + //------------------------- + + util::graph rag = make::region_adjacency_graph(ws, c8(), nbasins); + std::map<util::ord_pair<unsigned>, int> distances; + int max_distance = 0; + + // Compute minimal distance between sample points of adjacent + // components outline + compute_adjacency_distances(bbox_list, rag, distances, max_distance); + + //------------------------- + // Compute thresholds + //------------------------- + + int td1 = 0; + int td2 = 0; + int ta = 40; + float t = 0.34; + + compute_distribution(max_distance, distances, t, td1, td2); + + //------------------------- + // Invalidate edges + //------------------------- + + util::graph g(rag.v_nmax()); + invalidate_edges(distances, bbox_list, rag, g, td1, td2, ta); + + // //------------------------- + // // Saving + // //------------------------- + + // image2d<value::rgb8> output = data::convert(value::rgb8(), input); + // data::fill((output |(pw::value(ws) == 0)).rw(), literal::orange); + + // p_vertices< util::graph, fun::i2v::array<point2d> > p_v = + // make::p_vertices_with_mass_centers(ws, g); + + // debug::draw_graph(output, p_v, literal::blue, literal::green); + // io::ppm::save(output, "output.ppm"); + + return g; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace scribo::layout + +} // end of namespace scribo + +#endif // ! SCRIBO_LAYOUT_VORONOI_HH diff --git a/scribo/tests/layout/Makefile.am b/scribo/tests/layout/Makefile.am index 09990b1..e1ad394 100644 --- a/scribo/tests/layout/Makefile.am +++ b/scribo/tests/layout/Makefile.am @@ -1,5 +1,4 @@ -# Copyright (C) 2013 EPITA Research and Development -# Laboratory (LRDE). +# Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE). # # This file is part of Olena. # @@ -17,6 +16,7 @@ include $(top_srcdir)/scribo/tests/tests.mk -check_PROGRAMS = xy_cut +check_PROGRAMS = voronoi \ + xy_cut TESTS = $(check_PROGRAMS) diff --git a/scribo/tests/layout/voronoi.cc b/scribo/tests/layout/voronoi.cc new file mode 100644 index 0000000..13bd965 --- /dev/null +++ b/scribo/tests/layout/voronoi.cc @@ -0,0 +1,151 @@ +// Copyright (C) 2013 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to produce +// an executable, this file does not by itself cause the resulting +// executable to be covered by the GNU General Public License. This +// exception does not however invalidate any other reasons why the +// executable file might be covered by the GNU General Public License. + +/// \file + +#include <iostream> +#include <mln/io/pbm/load.hh> +#include <mln/make/box2d.hh> +#include <scribo/layout/voronoi.hh> + +#include "tests/data.hh" + +using namespace mln; + +struct pt +{ + mln::util::vertex_id_t v1; + mln::util::vertex_id_t v2; +}; + +static const pt ref[][8] = { + { {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} , {0,0} }, + { { 1,2 }, { 1,8 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 1,2 }, { 2,3 }, { 2,8 }, { 2,14 }, { 2,21 }, { 2,28 }, {0,0}, {0,0} }, + { { 2,3 }, { 3,14 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 4,6 }, { 4,13 }, { 4,18 }, { 4,26 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 5,15 }, { 5,16 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 4,6 }, { 6,18 }, { 6,20 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 7,17 }, { 7,32 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 1,8 }, { 2,8 }, { 8,13 }, { 8,21 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 9,10 }, { 9,19 }, { 9,22 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 9,10 }, { 10,11 }, { 10,22 }, { 10,23 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 10,11 }, { 11,12 }, { 11,23 }, { 11,24 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 11,12 }, { 12,24 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 4,13 }, { 8,13 }, { 13,26 }, { 13,27 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 2,14 }, { 3,14 }, { 14,15 }, { 14,28 }, { 14,29 }, {0,0}, {0,0}, {0,0} }, + { { 5,15 }, { 14,15 }, { 15,16 }, { 15,29 }, { 15,30 }, {0,0}, {0,0}, {0,0} }, + { { 5,16 }, { 15,16 }, { 16,17 }, { 16,30 }, { 16,31 }, {0,0}, {0,0}, {0,0} }, + { { 7,17 }, { 16,17 }, { 17,31 }, { 17,32 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 4,18 }, { 6,18 }, { 18,20 }, { 18,25 }, { 18,26 }, {0,0}, {0,0}, {0,0} }, + { { 9,19 }, { 19,22 }, { 19,33 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 6,20 }, { 18,20 }, { 20,25 }, { 20,35 }, { 20,36 }, { 20,41 }, {0,0}, {0,0} }, + { { 2,21 }, { 8,21 }, { 21,27 }, { 21,28 }, { 21,43 }, { 21,44 }, {0,0}, {0,0} }, + { { 9,22 }, { 10,22 }, { 19,22 }, { 22,23 }, { 22,33 }, { 22,39 }, {0,0}, {0,0} }, + { { 10,23 }, { 11,23 }, { 22,23 }, { 23,24 }, { 23,39 }, { 23,40 }, {0,0}, {0,0} }, + { { 11,24 }, { 12,24 }, { 23,24 }, { 24,34 }, { 24,35 }, { 24,40 }, {0,0}, {0,0} }, + { { 18,25 }, { 20,25 }, { 25,26 }, { 25,36 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 4,26 }, { 13,26 }, { 18,26 }, { 25,26 }, { 26,27 }, { 26,36 }, { 26,37 }, {0,0} }, + { { 13,27 }, { 21,27 }, { 26,27 }, { 27,37 }, { 27,42 }, {0,0}, {0,0}, {0,0} }, + { { 2,28 }, { 14,28 }, { 21,28 }, { 28,29 }, { 28,44 }, {0,0}, {0,0}, {0,0} }, + { { 14,29 }, { 15,29 }, { 28,29 }, { 29,30 }, { 29,46 }, { 29,47 }, {0,0}, {0,0} }, + { { 15,30 }, { 16,30 }, { 29,30 }, { 30,31 }, { 30,38 }, { 30,47 }, {0,0}, {0,0} }, + { { 16,31 }, { 17,31 }, { 30,31 }, { 31,32 }, { 31,38 }, {0,0}, {0,0}, {0,0} }, + { { 7,32 }, { 17,32 }, { 31,32 }, { 32,38 }, { 32,45 }, { 32,48 }, {0,0}, {0,0} }, + { { 19,33 }, { 22,33 }, { 33,39 }, { 33,57 }, { 33,58 }, {0,0}, {0,0}, {0,0} }, + { { 24,34 }, { 34,35 }, { 34,40 }, { 34,49 }, { 34,56 }, {0,0}, {0,0}, {0,0} }, + { { 20,35 }, { 24,35 }, { 34,35 }, { 35,41 }, { 35,56 }, {0,0}, {0,0}, {0,0} }, + { { 20,36 }, { 25,36 }, { 26,36 }, { 36,37 }, { 36,41 }, { 36,51 }, {0,0}, {0,0} }, + { { 26,37 }, { 27,37 }, { 36,37 }, { 37,42 }, { 37,50 }, { 37,52 }, {0,0}, {0,0} }, + { { 30,38 }, { 31,38 }, { 32,38 }, { 38,47 }, { 38,48 }, { 38,55 }, {0,0}, {0,0} }, + { { 22,39 }, { 23,39 }, { 33,39 }, { 39,40 }, { 39,58 }, {0,0}, {0,0}, {0,0} }, + { { 23,40 }, { 24,40 }, { 34,40 }, { 39,40 }, { 40,49 }, { 40,58 }, {0,0}, {0,0} }, + { { 20,41 }, { 35,41 }, { 36,41 }, { 41,51 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 27,42 }, { 37,42 }, { 42,43 }, { 42,50 }, { 42,53 }, {0,0}, {0,0}, {0,0} }, + { { 21,43 }, { 42,43 }, { 43,44 }, { 43,53 }, { 43,59 }, {0,0}, {0,0}, {0,0} }, + { { 21,44 }, { 28,44 }, { 43,44 }, { 44,46 }, { 44,54 }, {0,0}, {0,0}, {0,0} }, + { { 32,45 }, { 45,48 }, { 45,63 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 29,46 }, { 44,46 }, { 46,47 }, { 46,54 }, { 46,60 }, { 46,61 }, {0,0}, {0,0} }, + { { 29,47 }, { 30,47 }, { 38,47 }, { 46,47 }, { 47,61 }, {0,0}, {0,0}, {0,0} }, + { { 32,48 }, { 38,48 }, { 45,48 }, { 48,55 }, { 48,63 }, {0,0}, {0,0}, {0,0} }, + { { 34,49 }, { 40,49 }, { 49,56 }, { 49,58 }, { 49,75 }, {0,0}, {0,0}, {0,0} }, + { { 37,50 }, { 42,50 }, { 50,52 }, { 50,53 }, { 50,66 }, {0,0}, {0,0}, {0,0} }, + { { 36,51 }, { 41,51 }, { 51,52 }, { 51,69 }, { 51,72 }, {0,0}, {0,0}, {0,0} }, + { { 37,52 }, { 50,52 }, { 51,52 }, { 52,66 }, { 52,72 }, {0,0}, {0,0}, {0,0} }, + { { 42,53 }, { 43,53 }, { 50,53 }, { 53,59 }, { 53,77 }, {0,0}, {0,0}, {0,0} }, + { { 44,54 }, { 46,54 }, { 54,59 }, { 54,60 }, { 54,65 }, { 54,67 }, {0,0}, {0,0} }, + { { 38,55 }, { 48,55 }, { 55,61 }, { 55,62 }, { 55,63 }, {0,0}, {0,0}, {0,0} }, + { { 34,56 }, { 35,56 }, { 49,56 }, { 56,69 }, { 56,75 }, { 56,76 }, {0,0}, {0,0} }, + { { 33,57 }, { 57,58 }, { 57,73 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 33,58 }, { 39,58 }, { 40,58 }, { 49,58 }, { 57,58 }, { 58,73 }, { 58,74 }, { 58,75 } }, + { { 43,59 }, { 53,59 }, { 54,59 }, { 59,65 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 46,60 }, { 54,60 }, { 60,61 }, { 60,67 }, { 60,70 }, {0,0}, {0,0}, {0,0} }, + { { 46,61 }, { 47,61 }, { 55,61 }, { 60,61 }, { 61,62 }, { 61,70 }, { 61,71 }, {0,0} }, + { { 55,62 }, { 61,62 }, { 62,63 }, { 62,71 }, { 62,79 }, { 62,80 }, {0,0}, {0,0} }, + { { 45,63 }, { 48,63 }, { 55,63 }, { 62,63 }, { 63,64 }, { 63,68 }, { 63,80 }, {0,0} }, + { { 63,64 }, { 64,68 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 54,65 }, { 59,65 }, { 65,67 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 50,66 }, { 52,66 }, { 66,72 }, { 66,77 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 54,67 }, { 60,67 }, { 65,67 }, { 67,70 }, { 67,78 }, {0,0}, {0,0}, {0,0} }, + { { 63,68 }, { 64,68 }, { 68,80 }, { 68,81 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 51,69 }, { 56,69 }, { 69,76 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 60,70 }, { 61,70 }, { 67,70 }, { 70,71 }, { 70,78 }, {0,0}, {0,0}, {0,0} }, + { { 61,71 }, { 62,71 }, { 70,71 }, { 71,79 }, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 51,72 }, { 52,72 }, { 66,72 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 57,73 }, { 58,73 }, { 73,74 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 58,74 }, { 73,74 }, { 74,75 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 49,75 }, { 56,75 }, { 58,75 }, { 74,75 }, { 75,76 }, {0,0}, {0,0}, {0,0} }, + { { 56,76 }, { 69,76 }, { 75,76 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 53,77 }, { 66,77 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 67,78 }, { 70,78 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 62,79 }, { 71,79 }, { 79,80 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, + { { 62,80 }, { 63,80 }, { 68,80 }, { 79,80 }, { 80,81 }, {0,0}, {0,0}, {0,0} }, + { { 68,81 }, { 80,81 }, {0,0}, {0,0}, {0,0}, {0,0}, {0,0}, {0,0} }, +}; + + +int main() +{ + + image2d<bool> input; + io::pbm::load(input, SCRIBO_IMG_DIR "/alignment_3.pbm"); + util::graph g = scribo::layout::voronoi(input); + + mln_assertion(g.v_nmax() == 82); + + mln_vertex_iter_(util::graph) v(g); + mln_vertex_nbh_edge_iter_(util::graph) n(v); + for_all(v) + { + int edge_id = 0; + for_all(n) + { + mln_assertion(ref[v][edge_id].v1 != 0 && ref[v][edge_id].v2 != 0); + mln_assertion(ref[v][edge_id].v1 == n.v1()); + mln_assertion(ref[v][edge_id].v2 == n.v2()); + ++edge_id; + } + } +} -- 1.7.2.5