* scribo/core/component_info.hh, * scribo/core/component_set.hh, * scribo/core/internal/doc_serializer.hh, * scribo/io/img/internal/debug_img_visitor.hh, * scribo/io/img/internal/draw_edges.hh, * scribo/io/img/internal/full_img_visitor.hh, * scribo/io/img/internal/non_text_img_visitor.hh, * scribo/io/xml/internal/extended_page_xml_visitor.hh, * scribo/io/xml/internal/full_xml_visitor.hh, * scribo/io/xml/internal/page_xml_visitor.hh, * scribo/util/component_outline.hh: Add a template parameter to component_info structure and update its use. --- scribo/ChangeLog | 17 + scribo/scribo/core/component_info.hh | 128 ++++--- scribo/scribo/core/component_set.hh | 179 ++++------ scribo/scribo/core/internal/doc_serializer.hh | 6 +- scribo/scribo/io/img/internal/debug_img_visitor.hh | 7 +- scribo/scribo/io/img/internal/draw_edges.hh | 7 +- scribo/scribo/io/img/internal/full_img_visitor.hh | 7 +- .../scribo/io/img/internal/non_text_img_visitor.hh | 7 +- .../io/xml/internal/extended_page_xml_visitor.hh | 7 +- scribo/scribo/io/xml/internal/full_xml_visitor.hh | 7 +- scribo/scribo/io/xml/internal/page_xml_visitor.hh | 25 +- scribo/scribo/util/component_outline.hh | 379 ++++++++++++++++++++ 12 files changed, 592 insertions(+), 184 deletions(-) create mode 100644 scribo/scribo/util/component_outline.hh diff --git a/scribo/ChangeLog b/scribo/ChangeLog index d3d7f90..8e3c903 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,22 @@ 2011-05-16 Guillaume Lazzara <lazzara@fidji.lrde.epita.fr> + Add holder information to component_info. + + * scribo/core/component_info.hh, + * scribo/core/component_set.hh, + * scribo/core/internal/doc_serializer.hh, + * scribo/io/img/internal/debug_img_visitor.hh, + * scribo/io/img/internal/draw_edges.hh, + * scribo/io/img/internal/full_img_visitor.hh, + * scribo/io/img/internal/non_text_img_visitor.hh, + * scribo/io/xml/internal/extended_page_xml_visitor.hh, + * scribo/io/xml/internal/full_xml_visitor.hh, + * scribo/io/xml/internal/page_xml_visitor.hh, + * scribo/util/component_outline.hh: Add a template parameter to + component_info structure and update its use. + +2011-05-16 Guillaume Lazzara <lazzara@fidji.lrde.epita.fr> + New specific toolchain for historical documents. * scribo/toolchain/content_in_hdoc.hh, diff --git a/scribo/scribo/core/component_info.hh b/scribo/scribo/core/component_info.hh index 1f94076..2fa2ad1 100644 --- a/scribo/scribo/core/component_info.hh +++ b/scribo/scribo/core/component_info.hh @@ -44,15 +44,21 @@ namespace scribo { + // Forward declarations. + template <typename L> class component_set; + typedef mln::util::object_id<scribo::ComponentId, unsigned> component_id_t; - class component_info : public Serializable<component_info> + + template <typename L> + class component_info : public Serializable<component_info<L> > { typedef mln::util::object_id<scribo::ComponentId, unsigned> component_id_t; public: component_info(); - component_info(const component_id_t& id, + component_info(const component_set<L>& holder, + const component_id_t& id, const mln::box2d& bbox, const mln::point2d& mass_center, unsigned card, @@ -80,6 +86,8 @@ namespace scribo bool is_valid() const; + const component_set<L>& holder() const; + protected: component_id_t id_; mln::box2d bbox_; @@ -90,36 +98,41 @@ namespace scribo component::Tag tag_; component::Type type_; + + component_set<L> holder_; }; + template <typename L> std::ostream& - operator<<(std::ostream& ostr, const component_info& info); + operator<<(std::ostream& ostr, const component_info<L>& info); + template <typename L> bool - operator==(const component_info& lhs, const component_info& rhs); + operator==(const component_info<L>& lhs, const component_info<L>& rhs); # ifndef MLN_INCLUDE_ONLY - inline - component_info::component_info() + template <typename L> + component_info<L>::component_info() : id_(0), tag_(component::Ignored), type_(component::Undefined) { } - inline - component_info::component_info(const component_id_t& id, - const mln::box2d& bbox, - const mln::point2d& mass_center, - unsigned card, - component::Type type) + template <typename L> + component_info<L>::component_info(const component_set<L>& holder, + const component_id_t& id, + const mln::box2d& bbox, + const mln::point2d& mass_center, + unsigned card, + component::Type type) : id_(id), bbox_(bbox), mass_center_(mass_center), card_(card), - type_(type) + type_(type), holder_(holder) { if (!bbox.is_valid()) tag_ = component::Ignored; @@ -128,114 +141,129 @@ namespace scribo } - inline - component_info::component_id_t - component_info::id() const + template <typename L> + typename component_info<L>::component_id_t + component_info<L>::id() const { return id_; } - inline + template <typename L> const mln::box2d& - component_info::bbox() const + component_info<L>::bbox() const { return bbox_; } - inline + template <typename L> const mln::point2d& - component_info::mass_center() const + component_info<L>::mass_center() const { return mass_center_; } - inline + template <typename L> unsigned - component_info::card() const + component_info<L>::card() const { return card_; } - inline + template <typename L> bool - component_info::has_features() const + component_info<L>::has_features() const { return features_.valid; } - inline + template <typename L> void - component_info::update_features(const component_features_data& features) + component_info<L>::update_features(const component_features_data& features) { features_ = features; } - inline + template <typename L> const component_features_data& - component_info::features() const + component_info<L>::features() const { return features_; } - inline + template <typename L> component::Tag - component_info::tag() const + component_info<L>::tag() const { return tag_; } - inline + template <typename L> void - component_info::update_tag(component::Tag tag) + component_info<L>::update_tag(component::Tag tag) { tag_ = tag; } - inline + template <typename L> component::Type - component_info::type() const + component_info<L>::type() const { return type_; } - inline + template <typename L> void - component_info::update_type(component::Type type) + component_info<L>::update_type(component::Type type) { type_ = type; } - inline + template <typename L> bool - component_info::is_valid() const + component_info<L>::is_valid() const { return tag_ != component::Ignored && bbox_.is_valid(); } - inline + template <typename L> + const component_set<L>& + component_info<L>::holder() const + { + return holder_; + } + + + template <typename L> std::ostream& - operator<<(std::ostream& ostr, const component_info& info) + operator<<(std::ostream& ostr, const component_info<L>& info) { - return ostr << "component_info(" - << "id=" << info.id() - << ", bbox=" << info.bbox() - << ", mass_center=" << info.mass_center() - << ", card=" << info.card() - << ", tag=" << info.tag() - << ", features=" << info.features() - << ")" << std::endl; + ostr << "component_info(" + << "id=" << info.id() + << ", bbox=" << info.bbox() + << ", mass_center=" << info.mass_center() + << ", card=" << info.card() + << ", tag=" << info.tag(); + + if (info.features().valid) + ostr << ", features=" << info.features(); + else + ostr << ", features=none"; + + ostr << ")" << std::endl; + + return ostr; } - inline + template <typename L> bool - operator==(const component_info& lhs, const component_info& rhs) + operator==(const component_info<L>& lhs, const component_info<L>& rhs) { return diff --git a/scribo/scribo/core/component_set.hh b/scribo/scribo/core/component_set.hh index 3587302..4f4cd61 100644 --- a/scribo/scribo/core/component_set.hh +++ b/scribo/scribo/core/component_set.hh @@ -98,7 +98,7 @@ namespace scribo component::Type type = component::Undefined); component_set_data(const L& ima, const mln_value(L)& ncomps, - const mln::util::array<scribo::component_info>& infos); + const mln::util::array<scribo::component_info<L> >& infos); void fill_infos(const mln::util::array<pair_accu_t>& attribs, component::Type type = component::Undefined); @@ -111,7 +111,7 @@ namespace scribo L ima_; mln_value(L) ncomps_; - mln::util::array<scribo::component_info> infos_; + mln::util::array<scribo::component_info<L> > infos_; mln_ch_value(L, bool) separators_; }; @@ -162,16 +162,16 @@ namespace scribo mln_value(L) nelements() const; /// Return component information for a given component id \p id. - const component_info& info(const mln_value(L)& id) const; + const component_info<L>& info(const mln_value(L)& id) const; /// Return component information for a given component id \p id. - component_info& info(const mln_value(L)& id); + component_info<L>& info(const mln_value(L)& id); /// Return component information for a given component id \p id. - component_info& operator()(const component_id_t& id); + component_info<L>& operator()(const component_id_t& id); /// Return component information for a given component id \p id. - const component_info& operator()(const component_id_t& id) const; + const component_info<L>& operator()(const component_id_t& id) const; /// Update tag of components set to 'false' in \p f with \p tag. @@ -211,7 +211,7 @@ namespace scribo /// @{ /// Return all the component infos. - const mln::util::array<scribo::component_info>& infos_() const; + const mln::util::array<scribo::component_info<L> >& infos_() const; /// Unique set Id. id_t id_() const; @@ -278,99 +278,6 @@ namespace scribo const mln_value(L)& ncomps) : ima_(ima), ncomps_(ncomps) { - initialize(separators_, ima); // FIXME: to be removed - mln::data::fill(separators_, false); - - typedef mln::accu::shape::bbox<mln_site(L)> bbox_accu_t; - typedef mln::accu::center<mln_site(L)> center_accu_t; - typedef mln::accu::pair<bbox_accu_t, center_accu_t> pair_accu_t; - - - mln::util::array<pair_accu_t> attribs; - mln::labeling::compute(attribs, ima_, ncomps_); - - fill_infos(attribs); - } - - - template <typename L> - inline - component_set_data<L>::component_set_data(const L& ima, - const mln_value(L)& ncomps, - const mln::util::array<pair_accu_t>& attribs, - component::Type type) - : ima_(ima), ncomps_(ncomps) - { - initialize(separators_, ima); // FIXME: to be removed - mln::data::fill(separators_, false); - - fill_infos(attribs, type); - } - - template <typename L> - inline - component_set_data<L>::component_set_data(const L& ima, - const mln_value(L)& ncomps, - const mln::util::array<pair_data_t>& attribs, - component::Type type) - : ima_(ima), ncomps_(ncomps) - { - initialize(separators_, ima); // FIXME: to be removed - mln::data::fill(separators_, false); - - fill_infos(attribs, type); - } - - template <typename L> - inline - component_set_data<L>::component_set_data(const L& ima, - const mln_value(L)& ncomps, - const mln::util::array<scribo::component_info>& infos) - : ima_(ima), ncomps_(ncomps), infos_(infos) - { - initialize(separators_, ima); // FIXME: to be removed - mln::data::fill(separators_, false); - } - - - template <typename L> - inline - void - component_set_data<L>::fill_infos(const mln::util::array<pair_accu_t>& attribs, - component::Type type) - { - typedef mln_site(L) P; - - infos_.reserve(mln::value::next(ncomps_)); - - infos_.append(component_info()); // Component 0, i.e. the background. - for_all_comp_data(i, attribs) - { - component_info info(i, attribs[i].first(), - attribs[i].second(), attribs[i].second_accu().nsites(), - type); - infos_.append(info); - } - } - - template <typename L> - inline - void - component_set_data<L>::fill_infos(const mln::util::array<pair_data_t>& attribs, - component::Type type) - { - typedef mln_site(L) P; - - infos_.reserve(mln::value::next(ncomps_)); - - infos_.append(component_info()); // Component 0, i.e. the background. - for_all_comp_data(i, attribs) - { - component_info info(i, attribs[i].first, - attribs[i].second.first, attribs[i].second.second, - type); - infos_.append(info); - } } @@ -383,7 +290,7 @@ namespace scribo ncomps_ = ncomps; infos_.reserve(ncomps_); - infos_.append(component_info()); // Component 0, i.e. the background. + infos_.append(component_info<L>()); // Component 0, i.e. the background. } @@ -410,6 +317,30 @@ namespace scribo component_set<L>::component_set(const L& ima, const mln_value(L)& ncomps) { data_ = new internal::component_set_data<L>(ima, ncomps); + + initialize(data_->separators_, ima); // FIXME: to be removed + mln::data::fill(data_->separators_, false); + + typedef mln::accu::shape::bbox<mln_site(L)> bbox_accu_t; + typedef mln::accu::center<mln_site(L)> center_accu_t; + typedef mln::accu::pair<bbox_accu_t, center_accu_t> pair_accu_t; + + + mln::util::array<pair_accu_t> attribs; + mln::labeling::compute(attribs, ima, ncomps); + + + typedef mln_site(L) P; + + data_->infos_.reserve(mln::value::next(ncomps)); + + data_->infos_.append(component_info<L>()); // Component 0, i.e. the background. + for_all_comp_data(i, attribs) + { + component_info<L> info(*this, i, attribs[i].first(), + attribs[i].second(), attribs[i].second_accu().nsites()); + data_->infos_.append(info); + } } @@ -419,7 +350,23 @@ namespace scribo const mln::util::array<pair_accu_t>& attribs, component::Type type) { - data_ = new internal::component_set_data<L>(ima, ncomps, attribs, type); + data_ = new internal::component_set_data<L>(ima, ncomps); + + initialize(data_->separators_, ima); // FIXME: to be removed + mln::data::fill(data_->separators_, false); + + typedef mln_site(L) P; + + data_->infos_.reserve(mln::value::next(ncomps)); + + data_->infos_.append(component_info<L>()); // Component 0, i.e. the background. + for_all_comp_data(i, attribs) + { + component_info<L> info(*this, i, attribs[i].first(), + attribs[i].second(), attribs[i].second_accu().nsites(), + type); + data_->infos_.append(info); + } } @@ -430,7 +377,23 @@ namespace scribo const mln::util::array<pair_data_t>& attribs, component::Type type) { - data_ = new internal::component_set_data<L>(ima, ncomps, attribs, type); + data_ = new internal::component_set_data<L>(ima, ncomps); + + initialize(data_->separators_, ima); // FIXME: to be removed + mln::data::fill(data_->separators_, false); + + typedef mln_site(L) P; + + data_->infos_.reserve(mln::value::next(ncomps)); + + data_->infos_.append(component_info<L>()); // Component 0, i.e. the background. + for_all_comp_data(i, attribs) + { + component_info<L> info(*this, i, attribs[i].first, + attribs[i].second.first, attribs[i].second.second, + type); + data_->infos_.append(info); + } } @@ -445,7 +408,7 @@ namespace scribo template <typename L> inline - const component_info& + const component_info<L>& component_set<L>::info(const mln_value(L)& id) const { return data_->infos_[id]; @@ -453,7 +416,7 @@ namespace scribo template <typename L> inline - component_info& + component_info<L>& component_set<L>::info(const mln_value(L)& id) { return data_->infos_[id]; @@ -461,7 +424,7 @@ namespace scribo template <typename L> inline - const component_info& + const component_info<L>& component_set<L>::operator()(const component_id_t& id) const { return data_->infos_[id]; @@ -469,7 +432,7 @@ namespace scribo template <typename L> inline - component_info& + component_info<L>& component_set<L>::operator()(const component_id_t& id) { return data_->infos_[id]; @@ -611,7 +574,7 @@ namespace scribo template <typename L> inline - const mln::util::array<scribo::component_info>& + const mln::util::array<scribo::component_info<L> >& component_set<L>::infos_() const { return data_->infos_; diff --git a/scribo/scribo/core/internal/doc_serializer.hh b/scribo/scribo/core/internal/doc_serializer.hh index 2655100..606716b 100644 --- a/scribo/scribo/core/internal/doc_serializer.hh +++ b/scribo/scribo/core/internal/doc_serializer.hh @@ -65,7 +65,8 @@ namespace scribo template <typename L> void visit(const component_set<L>& comp_set) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -113,8 +114,9 @@ namespace scribo } template <typename E> + template <typename L> void - doc_serializer<E>::visit(const component_info& info) const + doc_serializer<E>::visit(const component_info<L>& info) const { } diff --git a/scribo/scribo/io/img/internal/debug_img_visitor.hh b/scribo/scribo/io/img/internal/debug_img_visitor.hh index 62097f5..5ad1dd3 100644 --- a/scribo/scribo/io/img/internal/debug_img_visitor.hh +++ b/scribo/scribo/io/img/internal/debug_img_visitor.hh @@ -69,7 +69,8 @@ namespace scribo template <typename L> void visit(const document<L>& doc) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -173,9 +174,9 @@ namespace scribo /// Component_info // - inline + template <typename L> void - debug_img_visitor::visit(const component_info& info) const + debug_img_visitor::visit(const component_info<L>& info) const { switch (info.type()) { diff --git a/scribo/scribo/io/img/internal/draw_edges.hh b/scribo/scribo/io/img/internal/draw_edges.hh index 664a352..8903a7e 100644 --- a/scribo/scribo/io/img/internal/draw_edges.hh +++ b/scribo/scribo/io/img/internal/draw_edges.hh @@ -60,8 +60,9 @@ namespace scribo /*! \brief Draw component edges. */ + template <typename L> void - draw_edges(const component_info& info, + draw_edges(const component_info<L>& info, image2d<value::rgb8>& output, const value::rgb8& value, const image2d<scribo::def::lbl_type>& edges); @@ -69,9 +70,9 @@ namespace scribo # ifndef MLN_INCLUDE_ONLY - inline + template <typename L> void - draw_edges(const component_info& info, + draw_edges(const component_info<L>& info, image2d<value::rgb8>& output, const value::rgb8& value, const image2d<scribo::def::lbl_type>& edges) { diff --git a/scribo/scribo/io/img/internal/full_img_visitor.hh b/scribo/scribo/io/img/internal/full_img_visitor.hh index 170b6a1..662d8d1 100644 --- a/scribo/scribo/io/img/internal/full_img_visitor.hh +++ b/scribo/scribo/io/img/internal/full_img_visitor.hh @@ -66,7 +66,8 @@ namespace scribo template <typename L> void visit(const document<L>& doc) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -129,9 +130,9 @@ namespace scribo /// Component_info // - inline + template <typename L> void - full_img_visitor::visit(const component_info& info) const + full_img_visitor::visit(const component_info<L>& info) const { switch (info.type()) { diff --git a/scribo/scribo/io/img/internal/non_text_img_visitor.hh b/scribo/scribo/io/img/internal/non_text_img_visitor.hh index cc1acb9..475a0a1 100644 --- a/scribo/scribo/io/img/internal/non_text_img_visitor.hh +++ b/scribo/scribo/io/img/internal/non_text_img_visitor.hh @@ -67,7 +67,8 @@ namespace scribo template <typename L> void visit(const component_set<L>& comp_set) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; private: // Attributes mln::image2d<value::rgb8>& output; @@ -126,9 +127,9 @@ namespace scribo /// Component_info // - inline + template <typename L> void - non_text_img_visitor::visit(const component_info& info) const + non_text_img_visitor::visit(const component_info<L>& info) const { switch (info.type()) { diff --git a/scribo/scribo/io/xml/internal/extended_page_xml_visitor.hh b/scribo/scribo/io/xml/internal/extended_page_xml_visitor.hh index 0cdebb5..2611d4a 100644 --- a/scribo/scribo/io/xml/internal/extended_page_xml_visitor.hh +++ b/scribo/scribo/io/xml/internal/extended_page_xml_visitor.hh @@ -80,7 +80,8 @@ namespace scribo template <typename L> void visit(const component_set<L>& comp_set) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -159,9 +160,9 @@ namespace scribo /// Component_info // - inline + template <typename L> void - extended_page_xml_visitor::visit(const component_info& info) const + extended_page_xml_visitor::visit(const component_info<L>& info) const { switch (info.type()) { diff --git a/scribo/scribo/io/xml/internal/full_xml_visitor.hh b/scribo/scribo/io/xml/internal/full_xml_visitor.hh index a8dfffe..614c473 100644 --- a/scribo/scribo/io/xml/internal/full_xml_visitor.hh +++ b/scribo/scribo/io/xml/internal/full_xml_visitor.hh @@ -85,7 +85,8 @@ namespace scribo template <typename L> void visit(const component_set<L>& comp_set) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -350,9 +351,9 @@ namespace scribo /// Component_info // - inline + template <typename L> void - full_xml_visitor::visit(const component_info& info) const + full_xml_visitor::visit(const component_info<L>& info) const { switch (info.type()) { diff --git a/scribo/scribo/io/xml/internal/page_xml_visitor.hh b/scribo/scribo/io/xml/internal/page_xml_visitor.hh index 0f3cce1..b807dbb 100644 --- a/scribo/scribo/io/xml/internal/page_xml_visitor.hh +++ b/scribo/scribo/io/xml/internal/page_xml_visitor.hh @@ -35,6 +35,8 @@ # include <scribo/core/internal/doc_serializer.hh> # include <scribo/convert/to_base64.hh> +# include <scribo/util/component_outline.hh> + # include <scribo/io/xml/internal/print_box_coords.hh> # include <scribo/io/xml/internal/print_page_preambule.hh> # include <scribo/io/xml/internal/compute_text_colour.hh> @@ -76,7 +78,8 @@ namespace scribo template <typename L> void visit(const component_set<L>& comp_set) const; - void visit(const component_info& info) const; + template <typename L> + void visit(const component_info<L>& info) const; template <typename L> void visit(const paragraph_set<L>& parset) const; @@ -120,7 +123,9 @@ namespace scribo // Page elements (Pictures, ...) if (doc.has_elements()) + { doc.elements().accept(*this); + } // line seraparators if (doc.has_vline_seps()) @@ -147,10 +152,18 @@ namespace scribo /// Component_info // - inline + template <typename L> void - page_xml_visitor::visit(const component_info& info) const + page_xml_visitor::visit(const component_info<L>& info) const { + // Getting component outline + scribo::def::lbl_type id = (scribo::def::lbl_type)info.id().to_equiv(); + const L& lbl = info.holder().labeled_image(); + p_array<point2d> + par = util::component_outline(((lbl | info.bbox()) + | (pw::value(lbl) == pw::cst(id))), + 1); + switch (info.type()) { case component::VerticalLineSeparator: @@ -159,7 +172,7 @@ namespace scribo << "\" orientation=\"0.000000\" " << " colour=\"black\">" << std::endl; - internal::print_box_coords(output, info.bbox(), " "); + internal::print_image_coords(output, par, " "); output << " </SeparatorRegion>" << std::endl; break; @@ -171,7 +184,7 @@ namespace scribo << "\" orientation=\"0.000000\" " << " colour=\"black\">" << std::endl; - internal::print_box_coords(output, info.bbox(), " "); + internal::print_image_coords(output, par, " "); output << " </SeparatorRegion>" << std::endl; break; @@ -187,7 +200,7 @@ namespace scribo << " embText=\"false\" " << " bgColour=\"white\">" << std::endl; - internal::print_box_coords(output, info.bbox(), " "); + internal::print_image_coords(output, par, " "); output << " </ImageRegion>" << std::endl; break; diff --git a/scribo/scribo/util/component_outline.hh b/scribo/scribo/util/component_outline.hh new file mode 100644 index 0000000..85ab4a7 --- /dev/null +++ b/scribo/scribo/util/component_outline.hh @@ -0,0 +1,379 @@ +// Copyright (C) 2011 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_UTIL_COMPONENT_OUTLINE_HH +# define SCRIBO_UTIL_COMPONENT_OUTLINE_HH + +/*! + * \file + * + * \brief Define a function which finds a polygonal approximation + * of a component's contour using the Douglas-Peucker algorithm. + * + */ + +# include <mln/core/concept/image.hh> +# include <mln/core/site_set/p_array.hh> +# include <mln/geom/all.hh> + +# include <utility> +# include <cmath> + +#include <mln/accu/shape/bbox.hh> + +namespace scribo +{ + + namespace util + { + + /*! Finds the 'douglas-peucker' polygonal approximation. + * + * Assumes there's only one centered component. + * More information about the algorithm can be found here : + * http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm + * + * Returns an ordered vector of points defining the polygonal contour. + * + * \param[in] ima_ The component whose contour is sought. + * \param[in] precision The max distance between the approximation + * and the curve. + */ + template <typename I> + mln::p_array<mln::point2d> + component_outline(const mln::Image<I>& ima, float precision); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + typedef enum + { + DIR_RIGHT = 0, + DIR_RIGHT_UP = 1, + DIR_UP = 2, + DIR_LEFT_UP = 3, + DIR_LEFT = 4, + DIR_LEFT_DOWN = 5, + DIR_DOWN = 6, + DIR_RIGHT_DOWN = 7, + DIR_NONE = 8 + } e_dir; + + /// Give the point2d which is in the given dir relatively to p. + static inline + mln::point2d + iterate_in_dir(const mln::point2d& p, + e_dir dir) + { + int dx = 0; + int dy = 0; + + switch (dir) + { + case DIR_RIGHT: + dx = 1; + break; + case DIR_RIGHT_UP: + dx = 1; + dy = -1; + break; + case DIR_UP: + dy = -1; + break; + case DIR_LEFT_UP: + dx = dy = -1; + break; + case DIR_LEFT: + dx = -1; + break; + case DIR_LEFT_DOWN: + dx = -1; + dy = 1; + break; + case DIR_DOWN: + dy = 1; + break; + case DIR_RIGHT_DOWN: + dx = dy = 1; + break; + default: + break; + } + + return mln::point2d(p[0] + dx, p[1] + dy); + } + + /// Decrement the given direction. + static inline + void + dec_dir(e_dir* d) + { + *d = (e_dir) (((unsigned)*d + 7) & 7); + } + + /// Increment the given direction (clockwise). + static inline + void + inc_dir(e_dir* d) + { + *d = (e_dir) (((unsigned)*d + 9) & 7); + } + + /// Inverse the given direction. + static inline + void + inverse_dir(e_dir* d) + { + *d = (e_dir) (((unsigned)*d + 4) & 7); + } + + /// Initialize the direction in which to find next points in the contour + template <typename I> + static inline + e_dir + find_first_dir(const I& ima, + const mln::point2d& p) + { + e_dir dir = DIR_NONE; + + mln::point2d n; + do + { + dec_dir(&dir); + n = iterate_in_dir(p, dir); + } + while (ima(n) != mln::literal::zero); + + while (ima(n) == mln::literal::zero) + { + inc_dir(&dir); + n = iterate_in_dir(p, dir); + } + + return (dir); + } + + /// Give the next point in the contour + template <typename I> + static + mln::point2d + next_pt_in_contour(const I& ima, + const mln::point2d& ori, + e_dir* last_dir) + { + e_dir dir = (*last_dir); + dec_dir(&dir); + mln::point2d cur; + + do + { + cur = iterate_in_dir(ori, dir); + dec_dir(&dir); + } + while (ima(cur) == mln::literal::zero); + + *last_dir = dir; + inverse_dir(last_dir); + return cur; + } + + /// Give The farthest point from line (begin, end) or NULL + /// if that distance is inferior to the given precision. (bottleneck) + template <typename I> + static inline + mln::point2d + find_farthest(const I& ima, + const mln::point2d& begin, + const mln::point2d& end, + float precision) + { + float d = 0.; + float dmax = 0.; + e_dir dir = find_first_dir(ima, begin); + + float a = end[1] - begin[1]; + float b = begin[0] - end[0]; + float c = begin[1] * end[0] - begin[0] * end[1]; + float norm = sqrt ((a * a) + (b * b)); + + mln::point2d max; + mln::point2d cur; + mln::point2d old; + + cur = begin; + max = cur; + + while (cur != end) + { + old = cur; + cur = next_pt_in_contour(ima, cur, &dir); + + d = a * cur[0] + cur[1] * b + c; + + if (d < 0) + d = -d; + + if (d > dmax) + { + dmax = d; + max = cur; + } + + } + + if (dmax > precision * norm) + return max; + else + return begin; + } + + /// Split the line (begin, end) at the farthest point on the curve + /// and apply itself recursively. + template <typename I> + void + split_rec(const I& ima, + const mln::point2d& begin, + const mln::point2d& end, + mln::p_array<mln::point2d>& l, + float precision) + { + mln::point2d node = find_farthest(ima, begin, end, precision); + + if (node != begin) + { + split_rec(ima, begin, node, l, precision); + + l.append(node); + + split_rec(ima, node, end, l, precision); + } + } + + /// Init the spliting procedure on both side of the line. + template <typename I> + void + split(const I& ima, + const mln::point2d& begin, + const mln::point2d& end, + mln::p_array<mln::point2d>& l, + float precision) + { + mln::point2d node; + + node = find_farthest(ima, begin, end, precision); + + l.append(begin); + + if (node != begin) + { + split_rec(ima, begin, node, l, precision); + + l.append(node); + + split_rec(ima, node, end, l, precision); + } + + l.append(end); + + node = find_farthest(ima, end, begin, precision); + + if (node != end) + { + split_rec(ima, end, node, l, precision); + + l.append(node); + + split_rec(ima, node, begin, l, precision); + } + } + + /// Find (simply) 2 points on the contour of the component + template <typename I> + static inline + std::pair<mln::point2d, mln::point2d> + get_initials(const I& ima) + { + mln::point2d begin(mln::geom::min_row(ima), + mln::geom::min_col(ima)); + mln::point2d end(mln::geom::max_row(ima), + mln::geom::max_col(ima)); + + while (ima(begin) == mln::literal::zero) + begin[0]++; + + while (ima(end) == mln::literal::zero) + end[0]--; + + return std::pair<mln::point2d, mln::point2d> (begin, end); + } + } // end of namespace internal + + + + + template <typename I> + mln::p_array<mln::point2d> + component_outline(const mln::Image<I>& ima_, + float precision) + { + mln::trace::entering("scribo::component_outline"); + + const I& ima = exact(ima_); + + mln_precondition(ima.is_valid()); + + mln::accu::shape::bbox<point2d> ab; + mln_piter(I) p(ima.domain()); + for_all(p) + ab.take(p); + + std::cout << ab.to_result() << std::endl; + + mln::p_array<mln::point2d> contour; + std::pair<mln::point2d, mln::point2d> initials = + internal::get_initials(ima); + + std::cout << " - " << initials.first << " - " << initials.second << std::endl; + + internal::split(ima, + initials.first, + initials.second, + contour, + precision); + + mln::trace::exiting("scribo::component_outline"); + + return contour; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace util + +} // end of namespace scribo + +#endif // ! SCRIBO_UTIL_COMPONENT_OUTLINE_HH -- 1.5.6.5