* scribo/src/afp/components.hh, * scribo/src/afp/link.hh, * scribo/src/afp/regroup.hh: New. --- scribo/ChangeLog | 8 ++ scribo/src/afp/components.hh | 255 ++++++++++++++++++++++++++++++++++++++++++ scribo/src/afp/link.hh | 138 +++++++++++++++++++++++ scribo/src/afp/regroup.hh | 84 ++++++++++++++ 4 files changed, 485 insertions(+), 0 deletions(-) create mode 100644 scribo/src/afp/components.hh create mode 100644 scribo/src/afp/link.hh create mode 100644 scribo/src/afp/regroup.hh diff --git a/scribo/ChangeLog b/scribo/ChangeLog index f7a0e58..d35119e 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,13 @@ 2010-02-19 Guillaume Lazzara <z@lrde.epita.fr> + Add dedicated routines for AFP's use case. + + * scribo/src/afp/components.hh, + * scribo/src/afp/link.hh, + * scribo/src/afp/regroup.hh: New. + +2010-02-19 Guillaume Lazzara <z@lrde.epita.fr> + Add new tools in Scribo. * src/preprocessing/Makefile.am, diff --git a/scribo/src/afp/components.hh b/scribo/src/afp/components.hh new file mode 100644 index 0000000..7db8572 --- /dev/null +++ b/scribo/src/afp/components.hh @@ -0,0 +1,255 @@ +#include <mln/io/pbm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/extension/adjust.hh> +#include <mln/extension/fill.hh> +#include <mln/data/fill.hh> +#include <mln/accu/shape/bbox.hh> + +#include <mln/core/alias/neighb2d.hh> +#include <mln/core/image/dmorph/image_if.hh> +#include <mln/pw/value.hh> +#include <mln/debug/println.hh> + +#include <mln/util/timer.hh> +#include <mln/labeling/foreground.hh> +#include <mln/labeling/wrap.hh> +#include <mln/extension/fill.hh> +#include <mln/data/compare.hh> + + +namespace mln +{ + + template <typename I> + unsigned my_find_root(image2d<I>& data, unsigned x) + { + if (data.element(x).parent == x) + return x; + else + return data.element(x).parent = my_find_root(data, + data.element(x).parent); + } + + + + struct info + { + unsigned parent; + unsigned card; + float row_sum, col_sum; + point2d p_min, p_max; + + int width() const + { + return p_max.col() - p_min.col(); + } + + int height() const + { + return p_max.row() - p_min.row(); + } + + void init(unsigned p, int row, int col) + { + parent = p; + card = 1; + row_sum = row; + col_sum = col; + p_min.row() = row; + p_max.row() = row; + p_min.col() = col; + p_max.col() = col; + } + + void update(info& r) + { + r.parent = this->parent; + card += r.card; + row_sum += r.row_sum; + col_sum += r.col_sum; + + // bkd browsing => p is always higher (lower row) than r + mln_invariant(p_min.row() <= r.p_min.row()); + + if (r.p_min.col() < p_min.col()) + p_min.col() = r.p_min.col(); + if (r.p_max.row() > p_max.row()) + p_max.row() = r.p_max.row(); + if (r.p_max.col() > p_max.col()) + p_max.col() = r.p_max.col(); + } + }; + + + + template <typename V> + image2d<V> + extract_components(const image2d<bool>& input, + V& nlabels, + util::array<box2d>& bboxes, + util::array<point2d>& mass_centers) + { + typedef image2d<bool> I; + + neighb2d nbh = c8(); + const int + nrows = input.nrows(), + ncols = input.ncols(); + + bboxes.resize(1); + mass_centers.resize(1); + + image2d<info> data; + image2d<V> label; + V current_label = 0; + int N, dp_border; + +// util::timer time; +// time.start(); + + // init + { + extension::adjust(input, nbh); + N = input.nelements(); + dp_border = 2 * input.border(); + extension::fill(input, false); + initialize(data, input); + } + +// float t = time; +// std::cout << "init = " << t << std::endl; +// time.restart(); + + // 1st pass + { + util::array<int> dp = positive_offsets_wrt(input, nbh); + const unsigned n_nbhs = dp.nelements(); + + // Backward. + unsigned p = input.index_of_point(point2d(nrows - 1, ncols - 1)); + for (int row = nrows - 1; row >= 0; --row, p -= dp_border) + for (int col = ncols - 1; col >= 0; --col, --p) + { + if (! input.element(p)) + continue; + + data.element(p).init(p, row, col); // init + + for (unsigned i = 0; i < n_nbhs; ++i) + { + unsigned n = p + dp[i]; + if (! input.element(n)) + continue; + unsigned r = my_find_root(data, n); + if (r != p) + { + data.element(p).update( data.element(r) ); // update + } + } + } + } + +// t = time; +// std::cout << "1st pass = " << t << std::endl; +// time.restart(); + + // 2nd pass + { + initialize(label, input); + data::fill(label, 0); + + // Forward. + unsigned p = input.index_of_point(point2d(0, 0)); + for (int row = 0; row < nrows; ++row, p += dp_border) + for (int col = 0; col < ncols; ++col, ++p) + { + if (! input.element(p)) + continue; + const info& dta = data.element(p); + if (dta.parent == p) + { + if (dta.card > 5 + && (dta.width() >= 1 + && dta.height() >= 1)) + { + label.element(p) = ++current_label; + + bboxes.append(box2d(dta.p_min, dta.p_max)); + mass_centers.append(point2d(dta.row_sum / dta.card, + dta.col_sum / dta.card)); + } + } + else + label.element(p) = label.element(dta.parent); + } + } +// t = time; +// std::cout << "2nd pass = " << t << std::endl; + + nlabels = current_label; + return label; + } + + +} // mln + + + +// void usage(char* argv[]) +// { +// std::cerr << argv[0] << " input.pbm output.pgm" << std::endl; +// std::abort(); +// } + + +// int main(int argc, char* argv[]) +// { +// if (argc != 3) +// usage(argv); + +// using namespace mln; + +// image2d<bool> input; +// io::pbm::load(input, argv[1]); + + +// image2d<unsigned> ref; + +// // { +// // util::timer t; +// // t.start(); + +// // unsigned nlabels; +// // ref = labeling::foreground(input, c4(), nlabels); + +// // float ts = t.stop(); +// // std::cout << "tufa: " << ts << " " << nlabels << std::endl; +// // } + +// { +// util::timer t; +// t.start(); + + +// util::array<box2d> bboxes(1, box2d(1,1)); +// util::array<point2d> mass_centers(1, point2d(0,0)); + +// // util::array<std::pair<box2d, point2d> > data_out(1); +// unsigned nlabels; +// image2d<unsigned> comps = extract_components(input, nlabels, bboxes, mass_centers); + +// float ts = t.stop(); +// std::cout << ts << " " << nlabels << std::endl; + +// // std::cout << bboxes << std::endl; +// // std::cout << mass_centers << std::endl; + +// // if (comps != ref) +// // std::cout << "diff" << std::endl; + +// io::pgm::save(labeling::wrap(value::int_u8(), comps), +// argv[2]); +// } + +// } diff --git a/scribo/src/afp/link.hh b/scribo/src/afp/link.hh new file mode 100644 index 0000000..b899957 --- /dev/null +++ b/scribo/src/afp/link.hh @@ -0,0 +1,138 @@ +#include <mln/geom/ncols.hh> +#include <mln/geom/nrows.hh> +#include <mln/util/couple.hh> +#include <scribo/core/object_image.hh> +#include <scribo/core/macros.hh> +#include <scribo/primitive/internal/init_link_array.hh> + +namespace scribo +{ + + namespace primitive + { + + namespace link + { + + + template <typename L> + util::couple<object_links<L>, object_links<L> > + left_right(const object_image(L)& objects) + { + object_links<L> + right(objects, static_cast<unsigned>(objects.nlabels()) + 1); + primitive::internal::init_link_array(right); + + object_links<L> + left(objects, static_cast<unsigned>(objects.nlabels()) + 1); + primitive::internal::init_link_array(left); + + for_all_components(i, objects.bboxes()) + { + float + w = (objects.bbox(i).pmax().col() + - objects.bbox(i).pmin().col()), + h = (objects.bbox(i).pmax().row() + - objects.bbox(i).pmin().row()); + unsigned dmax = (w / 2.0f) + (3 * math::max(w, h)); + + + const mln_site(L) c = objects.mass_center(i); + + int + midcol = (objects.bbox(i).pmax().col() + - objects.bbox(i).pmin().col()) / 2; + int + nrightima = geom::ncols(objects) - c.col(), + nleftima = c.col(), + nright = std::min(static_cast<unsigned>(nrightima), midcol + dmax), + nleft = std::min(static_cast<unsigned>(nleftima), midcol + dmax); + + // Right + { + const mln_value(L) + *p = &objects(c), + *pstop = p + nright + 1; + + for (; p != pstop; ++p) + { + if (*p != literal::zero // Not the background + && *p != i // Not the current component + && right[*p] != i) // No loops + { + right[i] = *p; + break; + } + } + } + + + // Left + { + const mln_value(L) + *p = &objects(c), + *pstop = p - nleft - 1; + + for (; p != pstop; --p) + { + if (*p != literal::zero // Not the background + && *p != i // Not the current component + && left[*p] != i) // No loops + { + left[i] = *p; + break; + } + } + } + } + + return mln::make::couple(left, right); + } + + + template <typename L> + object_links<L> + left(const object_image(L)& objects, unsigned dmax) + { + object_links<L> + left(objects, static_cast<unsigned>(objects.nlabels()) + 1); + primitive::internal::init_link_array(left); + + for_all_components(i, objects.bboxes()) + { + const mln_site(L) c = objects.mass_center(i); + + int + midcol = (objects.bbox(i).pmax().col() + - objects.bbox(i).pmin().col()) / 2; + int + nleftima = c.col(), + nleft = std::min(static_cast<unsigned>(nleftima), midcol + dmax); + + // Left + { + const mln_value(L) + *p = &objects(c), + *pstop = p - nleft - 1; + + for (; p != pstop; --p) + { + if (*p != literal::zero // Not the background + && *p != i // Not the current component + && left[*p] != i) // No loops + { + left[i] = *p; + break; + } + } + } + } + + return left; + } + + } // end of namespace scribo::primitive::link + + } // end of namespace scribo::primitive + +} // end of namespace scribo diff --git a/scribo/src/afp/regroup.hh b/scribo/src/afp/regroup.hh new file mode 100644 index 0000000..c24880b --- /dev/null +++ b/scribo/src/afp/regroup.hh @@ -0,0 +1,84 @@ +#include <mln/geom/ncols.hh> +#include <mln/geom/nrows.hh> +#include <mln/util/couple.hh> +#include <scribo/core/object_image.hh> +#include <scribo/core/macros.hh> +#include <scribo/primitive/internal/init_link_array.hh> + +namespace scribo +{ + + namespace primitive + { + + namespace group + { + + template <typename L> + object_groups<L> + regroup_left(const object_image(L)& objects, + const object_groups<L>& groups, + unsigned dmax) + { + trace::entering("scribo::primitive::group::regroup_left"); + + mln_precondition(groups.is_valid()); + + object_groups<L> + new_groups(objects, static_cast<unsigned>(objects.nlabels()) + 1, 0); + + unsigned ngroups = 0; + for_all_components(i, objects.bboxes()) + { + if (groups[i] == 0) + continue; + + // We MUST set a group id here since the most left group + // component won't have any id otherwise. + if (new_groups[i] == 0) + new_groups[i] = ++ngroups; + + const mln_site(L) c = objects.mass_center(i); + + int + midcol = (objects.bbox(i).pmax().col() + - objects.bbox(i).pmin().col()) / 2; + int + nleftima = geom::ncols(objects), + nleft = std::min(static_cast<unsigned>(nleftima), midcol + dmax); + + // Left + { + const mln_value(L) + *p = &objects(c), + *pstop = p - nleft - 1; + + for (; p != pstop; --p) + { + if (*p != literal::zero // Not the background + && *p != i // Not the current component +// && new_groups[*p] != ngroups + && groups[*p] != 0) + { + if (new_groups[*p] == 0) + new_groups[*p] = ngroups; + else + { + new_groups[i] = new_groups[*p]; + --ngroups; + } + + break; + } + } + } + } + + return new_groups; + } + + } // end of namespace scribo::primitive::group + + } // end of namespace scribo::primitive + +} // end of namespace scribo -- 1.5.6.5