It's only a first version, far from being optimized. Besides, it doesn't
include (yet) the latest ideas/variations on the algorithm discussed this
week.
2006-08-25 Roland Levillain <roland(a)lrde.epita.fr>
Max-tree computation based on Fiorio's and Gustedt's labelling
algorithm.
* oln/lrde/ufmt/fiorio-1.hh, oln/lrde/ufmt/fiorio-2.hh: New.
* oln/lrde/ufmt/bin/fiorio.cc: New.
* oln/lrde/ufmt/README: Update.
Make the the olena/oln/lrde/ufmt hierarchy a full-fledged part of
the autoconfiscated package.
* oln/lrde/Makefile.am, oln/lrde/ufmt/Makefile.am,
* oln/lrde/ufmt/bin/Makefile.am: New.
* TODO: New.
--- 10.249/olena/oln/lrde/ufmt/README Mon, 21 Aug 2006 17:17:14 +0200 theo
(oln/x/22_README 1.2 644)
+++ 10.250/olena/oln/lrde/ufmt/README Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/22_README 1.3 644)
@@ -121,3 +121,17 @@
flooding
p as point2d
father as map<pair,pair>
+
+
+
+* fiorio
+Max-tree computation based on Fiorio's and Gustedt's labelling
+algorithm.
+
+** fiorio-1.hh
+My (Roland) first implementation of the max-tree computation using
+Fiorio's and Gustedt's algorithm.
+
+** fiorio-2.hh
+My second implementation of the max-tree computation using Fiorio's and
+Gustedt's algorithm, using routines of Tho's (anc, insert, etc.)
--- 10.249/olena/TODO Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/TODO Fri, 25 Aug 2006 17:56:35 +0200 levill_r (oln/x/24_TODO 1.1 644)
@@ -0,0 +1,3 @@
+TODO -*- outline -*-
+
+* Clean up oln/lrde.
--- 10.249/olena/oln/lrde/Makefile.am Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/oln/lrde/Makefile.am Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/25_Makefile.a 1.1 644)
@@ -0,0 +1,9 @@
+## Process this file with Automake to produce Makefile.in -*- Makefile -*-
+
+## -- FIXME: Improve integration. ----------------------------------------
+##
+## The contents of `olena/lrde' should be moved to subdirectory of
+## `olena/oln', and the contents of `olena/lrde/ufmt/bin to `olena/tests'
+## or to `tools'.
+SUBDIRS = ufmt
+## ---------------------------------------- FIXME: Improve integration. --
--- 10.249/olena/oln/lrde/ufmt/Makefile.am Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/oln/lrde/ufmt/Makefile.am Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/26_Makefile.a 1.1 644)
@@ -0,0 +1,28 @@
+## Process this file with Automake to produce Makefile.in -*- Makefile -*-
+
+## -- FIXME: Improve integration. ----------------------------------------
+##
+## The contents of `olena/lrde' should be moved to subdirectory of
+## `olena/oln', and the contents of `olena/lrde/ufmt/bin to `olena/tests'
+## or to `tools'.
+
+SUBDIRS = bin
+
+noinst_HEADERS = \
+ ad_maxtree.hh \
+ ap_maxtree.hh \
+ basic_maxtree.hh \
+ basic_salembier.hh \
+ fiorio-1.hh \
+ fiorio-2.hh \
+ hdc_maxtree.hh \
+ hpc_maxtree.hh \
+ log.hh \
+ r1ic_maxtree.hh \
+ rpc_maxtree.hh \
+ utils.hh
+
+EXTRA_DIST = README \
+ img/lena64nb.pgm img/lena64.pbm img/lena64.pgm img/lena6.pgm
+
+## ---------------------------------------- FIXME: Improve integration. --
--- 10.249/olena/oln/lrde/ufmt/fiorio-1.hh Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/oln/lrde/ufmt/fiorio-1.hh Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/27_fiorio-1.h 1.1 644)
@@ -0,0 +1,322 @@
+// Copyright (C) 2006 EPITA Research and Development Laboratory
+//
+// This file is part of the Olena Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License version 2 as published by the
+// Free Software Foundation.
+//
+// This library 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 this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+// Boston, MA 02111-1307, USA.
+//
+// As a special exception, you may use this file as part of a free
+// software library 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.
+
+
+/** \brief An adadpatation of Fiorio's and Gustedt's algorithm
+ (fiorio.96.tcs).
+
+ Ref.: Christophe Fiorio and Jens Gustedt. Two linear time
+ Union-Find strategies for image processing. Theoretical Computer
+ Science, 1996.
+
+ \note This is the original version of my implementation, that
+ started to work on August 25th, 2006. */
+
+
+#ifndef OLENA_LRDE_UFMT_FIORIO_HH
+# define OLENA_LRDE_UFMT_FIORIO_HH
+
+# include <algorithm>
+
+# include <oln/core/image2d.hh>
+# include <oln/level/fill.hh>
+
+namespace oln
+{
+ namespace lrde
+ {
+ namespace ufmt
+ {
+
+ // FIXME: Not generic (works only on 2-D images).
+ template <typename I>
+ class fiorio
+ {
+ typedef oln_point_type(I) point;
+ typedef oln_value_type(I) value;
+ typedef oln_iter_type(I) piter;
+ // typedef oln_neighborhood_type(I) Nbh;
+ // typedef oln_iter_type(Nbh) niter;
+ typedef typename mute<I, point>::ret parent_type;
+
+ // FIXME: Should be elsewhere!
+ typedef oln::image2d<unsigned> area_type;
+
+ public:
+ fiorio(const abstract::image<I>& ima) :
+ ima_(ima.exact().clone()), parent_(ima.size())
+ , n_level_roots_cpt_(ima.npoints())
+// , area_(ima_.size())
+ {
+ // Init the image of parents.
+ piter p (parent_);
+ for_all (p)
+ parent_[p] = p;
+
+ // FIXME: Should be elsewhere!
+ // Init the image of data.
+// oln::level::fill (area_, 1);
+ }
+
+ /// Entry point of the algorithm.
+ void go()
+ {
+ scan_line();
+ }
+
+
+ /// Images accessors.
+ /// \{
+ public:
+ const I& ima() const
+ {
+ return ima_;
+ }
+
+ const parent_type& parent() const
+ {
+ return parent_;
+ }
+ /// \}
+
+
+ /// Level roots.
+ /// \{
+ /// Get the number of level roots (method 1, using a counter
+ /// updated by the algorithm).
+ unsigned n_level_roots1() const
+ {
+ return n_level_roots_cpt_;
+ }
+
+ /// Get the number of level roots (method 2, computing from the
+ /// PARENT image.
+ unsigned n_level_roots2() const
+ {
+ unsigned n_level_roots = 0;
+ oln_iter_type(parent_type) p(parent_);
+ for_all (p)
+ if (is_level_root(p))
+ ++n_level_roots;
+ return n_level_roots;
+ }
+
+ /// The type of an image of level roots
+ typedef typename mute<parent_type, bool>::ret level_roots_image_type;
+
+ /// \brief Compute the image of level roots.
+ ///
+ /// A value of \a true means that the point is a level root in ima.
+ level_roots_image_type level_roots() const
+ {
+ // Image of level roots.
+ level_roots_image_type level_roots (ima_.size());
+ oln_iter_type(parent_type) p(ima_);
+ for_all (p)
+ level_roots[p] = is_level_root(p);
+ return level_roots;
+ }
+ /// \}
+
+
+ protected:
+ // Improve to handle other neighborhoods than 4-c.
+ void scan_line()
+ {
+ // Special treatment of the first line (no merge).
+ build_tree_of_line(0);
+ for (coord i = 1; i < ima_.nrows(); ++i)
+ {
+ build_tree_of_line(i);
+ // Merge the tree of the current line with the rest of the image.
+ merge_line(i);
+ }
+ }
+
+ void build_tree_of_line(coord row)
+ {
+ // Start at the second pixel (the first pixel has no left
+ // neighbor.
+ for (coord j = 1; j < ima_.ncols(); ++j)
+ {
+ point left = find_level_root(point(row, j - 1));
+ point this_one = point(row, j);
+ merge(left, this_one);
+ }
+ }
+
+ void merge_line(coord row)
+ {
+ precondition(row > 0);
+
+ // Special treatment of the pixel on the first column.
+ {
+ point p (row, 0);
+ point upper (row - 1, 0);
+ // Merge with upper pixel.
+ merge(p, upper);
+ }
+ for (coord col = 1; col < ima_.ncols(); ++col)
+ {
+ point p (row, col );
+ point upper (row - 1, col );
+ point left (row, col - 1);
+ // FIXME: Disabled, since /a priori/ useless.
+ // (Remove it?)
+#if 0
+ // Merge with left pixel.
+ merge(p, left);
+#endif
+ // Merge with upper pixel.
+ merge(p, upper);
+ }
+ }
+
+ // FIXME: Turn this recursive method into a loop!
+ // FIXME: Get rid of the swap, using an introductory method.
+ /// \note Th�o calls this method ``update'.
+ void merge(const point& p, const point& q)
+ {
+ point r = find_level_root(p);
+ point s = find_level_root(q);
+
+ // Stop the recursion when R and S are equal.
+ if (r == s)
+ return;
+
+ // Update the number of level roots.
+ if (ima_[r] == ima_[s])
+ --n_level_roots_cpt_;
+
+ // The rest of the routine assumes that R has a value
+ // greater or equal to S; swap them if needed.
+ if (ima_[r] < ima_[s])
+ std::swap(r, s);
+
+ point t = parent_[r];
+
+ // Join R and S only if S is higher than the parent of R.
+ if (r == t or ima_[s] > ima_[t])
+ parent_[r] = s;
+ // FIXME: Study whether the order (S, T) is important. That
+ // might be the case when S and T have the same value.
+ merge(t, s);
+ }
+
+ /// \note Th�o calls this function ``is_root'.
+ bool is_top(const point& p) const
+ {
+ return parent_[p] == p;
+ }
+
+ bool is_level_root(const point& p) const
+ {
+ return
+ is_top(p) ||
+ (ima_[parent_[p]] != ima_[p]);
+ }
+
+ /// \brief Find the level root of the component that P belongs to.
+ ///
+ /// Based on find_compress.
+ /// \note (This is my version.)
+ point find_level_root(const point& p)
+ {
+ // Path compression.
+ if (not is_top(p))
+ parent_[p] = find_level_root(parent_[p]);
+ // Is P a level root at the end the routine?
+ if (is_level_root(p))
+ return p;
+ else
+ return parent_[p];
+ }
+
+ protected:
+ /// \note Th�o calls this image ``f''.
+ I ima_;
+ /// \note Th�o calls this image ``par''.
+ parent_type parent_;
+ // Counter of level roots (method 1).
+ unsigned n_level_roots_cpt_;
+
+
+
+// ----------------------------------------------------------------
+
+// FIXME: Should be elsewhere!
+
+// public:
+// void area_opening (unsigned size)
+// {
+// oln_iter_type_(area_type) p(area_);
+
+// // First pass: sum areas.
+// for_all(p)
+// {
+// point p_parent = parent_[p];
+// while (p != p_parent)
+// {
+// area_[p_parent] += 1;
+// }
+// }
+
+// // Second pass: cut branches in the max-tree.
+// for_all(p)
+// merge(p, size);
+// }
+
+// protected:
+// // Attach P to Q.
+// // FIXME: The criterion should be passed as a function object.
+// point merge (const point& p, unsigned size)
+// {
+// if (not is_top(p) && area_[p] < size)
+// {
+// // Find the component satisfying the criterion.
+// point new_level_root = merge(parent_[p], size);
+// // Attach P to its new component representant (level root).
+// parent_[p] = new_level_root;
+// // Take the color of the new component.
+// ima_[p] = ima_[new_level_root];
+// return new_level_root;
+// }
+// else
+// return p;
+// }
+
+// protected:
+// area_type area_;
+ };
+
+ } // end of namespace oln::lrde::ufmt
+
+ } // end of namespace oln::lrde
+
+} // end of namespace oln
+
+#endif // ! OLENA_LRDE_UFMT_FIORIO_HH
--- 10.249/olena/oln/lrde/ufmt/fiorio-2.hh Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/oln/lrde/ufmt/fiorio-2.hh Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/28_fiorio-2.h 1.1 644)
@@ -0,0 +1,351 @@
+// Copyright (C) 2006 EPITA Research and Development Laboratory
+//
+// This file is part of the Olena Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License version 2 as published by the
+// Free Software Foundation.
+//
+// This library 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 this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+// Boston, MA 02111-1307, USA.
+//
+// As a special exception, you may use this file as part of a free
+// software library 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.
+
+
+/** \brief An adadpatation of Fiorio's and Gustedt's algorithm
+ (fiorio.96.tcs).
+
+ Ref.: Christophe Fiorio and Jens Gustedt. Two linear time
+ Union-Find strategies for image processing. Theoretical Computer
+ Science, 1996.
+
+ \note This is the second version of my implementation, augmented
+ with Th�o's (better) routines and ideas. */
+
+
+#ifndef OLENA_LRDE_UFMT_FIORIO_HH
+# define OLENA_LRDE_UFMT_FIORIO_HH
+
+# include <algorithm>
+
+# include <oln/core/image2d.hh>
+# include <oln/level/fill.hh>
+
+namespace oln
+{
+ namespace lrde
+ {
+ namespace ufmt
+ {
+
+ // FIXME: Not generic (works only on 2-D images).
+ template <typename I>
+ class fiorio
+ {
+ typedef oln_point_type(I) point;
+ typedef oln_value_type(I) value;
+ typedef oln_iter_type(I) piter;
+ // typedef oln_neighborhood_type(I) Nbh;
+ // typedef oln_iter_type(Nbh) niter;
+ typedef typename mute<I, point>::ret parent_type;
+
+ // FIXME: Should be elsewhere!
+ typedef oln::image2d<unsigned> area_type;
+
+ public:
+ fiorio(const abstract::image<I>& ima) :
+ ima_(ima.exact().clone()), parent_(ima.size())
+ , n_level_roots_cpt_(ima.npoints())
+// , area_(ima_.size())
+ {
+ // Init the image of parents.
+ piter p (parent_);
+ for_all (p)
+ parent_[p] = p;
+
+ // FIXME: Should be elsewhere!
+ // Init the image of data.
+// oln::level::fill (area_, 1);
+ }
+
+ /// Entry point of the algorithm.
+ void go()
+ {
+ scan_line();
+ }
+
+
+ /// Images accessors.
+ /// \{
+ public:
+ const I& ima() const
+ {
+ return ima_;
+ }
+
+ const parent_type& parent() const
+ {
+ return parent_;
+ }
+ /// \}
+
+
+ /// Level roots.
+ /// \{
+ /// Get the number of level roots (method 1, using a counter
+ /// updated by the algorithm).
+ unsigned n_level_roots1() const
+ {
+ return n_level_roots_cpt_;
+ }
+
+ /// Get the number of level roots (method 2, computing from the
+ /// PARENT image.
+ unsigned n_level_roots2() const
+ {
+ unsigned n_level_roots = 0;
+ oln_iter_type(parent_type) p(parent_);
+ for_all (p)
+ if (is_level_root(p))
+ ++n_level_roots;
+ return n_level_roots;
+ }
+
+ /// The type of an image of level roots
+ typedef typename mute<parent_type, bool>::ret level_roots_image_type;
+
+ /// \brief Compute the image of level roots.
+ ///
+ /// A value of \a true means that the point is a level root in ima.
+ level_roots_image_type level_roots() const
+ {
+ // Image of level roots.
+ level_roots_image_type level_roots (ima_.size());
+ oln_iter_type(parent_type) p(ima_);
+ for_all (p)
+ level_roots[p] = is_level_root(p);
+ return level_roots;
+ }
+ /// \}
+
+
+ protected:
+ // Improve to handle other neighborhoods than 4-c.
+ void scan_line()
+ {
+ // Special treatment of the first line (no merge).
+ build_tree_of_line(0);
+ for (coord i = 1; i < ima_.nrows(); ++i)
+ {
+ build_tree_of_line(i);
+ // Merge the tree of the current line with the rest of the image.
+ merge_line(i);
+ }
+ }
+
+ void build_tree_of_line(coord row)
+ {
+ // Start at the second pixel (the first pixel has no left
+ // neighbor.
+ for (coord j = 1; j < ima_.ncols(); ++j)
+ {
+ point left = find_level_root(point(row, j - 1));
+ point this_one = point(row, j);
+ insert(this_one, left);
+ }
+ }
+
+ void merge_line(coord row)
+ {
+ precondition(row > 0);
+
+ for (coord col = 0; col < ima_.ncols(); ++col)
+ {
+ point p (row, col );
+ point upper (row - 1, col );
+
+ // Note: merging with the left pixel is useless.
+
+ // Merge with upper pixel.
+ merge(p, upper);
+ }
+ }
+
+ /// Insert \a p in a tree of which \a n is a neighbor of \a p.
+ void insert(const point& p, const point& n)
+ {
+ point r = find_ancestor(n, ima_[p]);
+ if (ima_[r] <= ima_[p])
+ {
+ parent_[p] = r;
+ if (ima_[r] == ima_[p])
+ // Update the number of level roots.
+ --n_level_roots_cpt_;
+ }
+ else
+ {
+ if (not is_top(r))
+ parent_[p] = parent_[r];
+ parent_[r] = p;
+ }
+ }
+
+ /// Front-end to \a merge_.
+ void merge(const point& p, const point& q)
+ {
+ // The \a merge_ routine assumes that P has a value greater
+ // or equal to Q; swap them if needed.
+ if (ima_[p] >= ima_[q])
+ merge_(p, q);
+ else
+ merge_(q, p);
+ }
+
+ // FIXME: Turn this recursive method into a loop!
+ // FIXME: Get rid of the swap, using an introductory method.
+ /// \note Th�o calls this method ``update'.
+ void merge_(const point& p, const point& q)
+ {
+ precondition (p != q);
+ precondition (ima_[p] >= ima_[q]);
+
+ point r = find_ancestor(p, ima_[q]);
+ point s = find_level_root(q);
+
+ // Stop the recursion when R and S are equal (i.e., they are
+ // already merged).
+ if (r == s)
+ return;
+
+ // FIXME: Have a look at Th�o's ``update'' routine to see
+ // if we can improve this method.
+ // \{
+ point t = parent_[s];
+
+ if (ima_[s] == ima_[r])
+ {
+ parent_[s] = r;
+ // Update the number of level roots.
+ --n_level_roots_cpt_;
+ }
+ else
+ {
+ if (not is_top(r))
+ parent_[s] = parent_[r];
+ parent_[r] = s;
+ }
+ merge_(r, t);
+ }
+
+ /// \note Th�o calls this function ``is_root'.
+ bool is_top(const point& p) const
+ {
+ return parent_[p] == p;
+ }
+
+ bool is_level_root(const point& p) const
+ {
+ return
+ is_top(p) ||
+ (ima_[parent_[p]] != ima_[p]);
+ }
+
+ /// \brief Find the level root of the component that P belongs to.
+ /// \note From Th�o.
+ point find_level_root(const point& p)
+ {
+ // Is P a level root at the end the routine?
+ if (is_level_root(p))
+ return p;
+ else
+ // Path compression.
+ return parent_[p] = find_level_root(parent_[p]);
+ }
+
+ /// \note From Th�o.
+ /// \note Th�o calls this method ``anc''.
+ point find_ancestor(point p, const value& level)
+ {
+ while (not is_top(p) and ima_[parent_[p]] >= level)
+ p = find_level_root(parent_[p]);
+ return p;
+ }
+
+ protected:
+ /// \note Th�o calls this image ``f''.
+ I ima_;
+ /// \note Th�o calls this image ``par''.
+ parent_type parent_;
+ // Counter of level roots (method 1).
+ unsigned n_level_roots_cpt_;
+
+
+
+// ----------------------------------------------------------------
+
+// FIXME: Should be elsewhere!
+
+// public:
+// void area_opening (unsigned size)
+// {
+// oln_iter_type_(area_type) p(area_);
+
+// // First pass: sum areas.
+// for_all(p)
+// {
+// point p_parent = parent_[p];
+// while (p != p_parent)
+// {
+// area_[p_parent] += 1;
+// }
+// }
+
+// // Second pass: cut branches in the max-tree.
+// for_all(p)
+// merge(p, size);
+// }
+
+// protected:
+// // Attach P to Q.
+// // FIXME: The criterion should be passed as a function object.
+// point merge (const point& p, unsigned size)
+// {
+// if (not is_top(p) && area_[p] < size)
+// {
+// // Find the component satisfying the criterion.
+// point new_level_root = merge(parent_[p], size);
+// // Attach P to its new component representant (level root).
+// parent_[p] = new_level_root;
+// // Take the color of the new component.
+// ima_[p] = ima_[new_level_root];
+// return new_level_root;
+// }
+// else
+// return p;
+// }
+
+// protected:
+// area_type area_;
+ };
+
+ } // end of namespace oln::lrde::ufmt
+
+ } // end of namespace oln::lrde
+
+} // end of namespace oln
+
+#endif // ! OLENA_LRDE_UFMT_FIORIO_HH
--- 10.249/olena/oln/lrde/ufmt/bin/Makefile.am Fri, 25 Aug 2006 18:01:35 +0200 levill_r
()
+++ 10.250/olena/oln/lrde/ufmt/bin/Makefile.am Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/29_Makefile.a 1.1 644)
@@ -0,0 +1,18 @@
+AM_CXXFLAGS = -O3 -ggdb -Wall -Werror -ansi -pedantic
+AM_LDFLAGS = $(ZLIB_LDFLAGS)
+
+check_PROGRAMS = basic_maxtree basic_salembier fiorio-1 fiorio-2 \
+ hdc_maxtree hpc_maxtree r1ic_maxtree rpc_maxtree
+
+basic_maxtree_SOURCES = basic_maxtree.cc
+basic_salembier_SOURCES = basic_salembier.cc
+hdc_maxtree_SOURCES = hdc_maxtree.cc
+hpc_maxtree_SOURCES = hpc_maxtree.cc
+r1ic_maxtree_SOURCES = r1ic_maxtree.cc
+rpc_maxtree_SOURCES = rpc_maxtree.cc
+
+fiorio_1_SOURCES = fiorio.cc
+fiorio_2_SOURCES = fiorio.cc
+fiorio_2_CPPFLAGS = -DFIORIO_VERSION=2
+
+# FIXME: Write (runtime) tests!
--- 10.249/olena/oln/lrde/ufmt/bin/fiorio.cc Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/olena/oln/lrde/ufmt/bin/fiorio.cc Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/x/30_fiorio.cc 1.1 644)
@@ -0,0 +1,84 @@
+#include <cstdlib>
+
+#include <ntg/int.hh>
+#include <ntg/color/rgb.hh>
+
+#include <oln/basics2d.hh>
+#include <oln/level/fill.hh>
+
+// Max-tree computation base on Fiorio's and Gustedt's algorithm.
+#if defined(FIORIO_VERSION) && FIORIO_VERSION == 2
+# include <oln/lrde/ufmt/fiorio-2.hh>
+#else
+# include <oln/lrde/ufmt/fiorio-1.hh>
+#endif
+
+
+void usage(char* argv[])
+{
+ std::cerr << "usage: " << argv[0] << " input.pgm
"//"level-roots.pbm"
+ << std::endl
+ << "Max-tree computation with Fiorio's and Gustedt's
algorithm."
+ << std::endl;
+ // FIXME: get precise description...
+ exit(1);
+}
+
+
+int main(int argc, char* argv[])
+{
+// if (argc != 3)
+// usage(argv);
+ if (argc != 2)
+ usage(argv);
+
+ typedef oln::image2d<ntg::int_u8> image_type;
+
+ image_type input = oln::io::load(argv[1]);
+
+ typedef oln::lrde::ufmt::fiorio<image_type> algorithm_type;
+
+ algorithm_type run(input);
+ std::cout << "npoint = " <<
run.ima().npoints()
+ << std::endl;
+ run.go();
+ std::cout << "n level roots (first version) = " <<
run.n_level_roots1()
+ << std::endl
+ << "n level roots (second version) = " <<
run.n_level_roots2()
+ << std::endl;
+
+// // Save the image of level roots.
+// oln::save(run.level_roots(), argv[2]);
+
+#if 0
+ // Create an image of components.
+ image_type output (input.size());
+ oln::level::fill (output, 0);
+ unsigned color = 1;
+ oln_iter_type_(image_type) p(algo.parent());
+ for_all(p)
+ {
+ oln::point2d root = algo.parent()[p];
+ // Assign a color to the root point of the component if not yet
+ // done.
+ if (output[root] == 0)
+ output[root] = color;
+ // If P is not a root, assign it the color of its root.
+ if (p != root)
+ output[p] = output[root];
+
+ // Increment the color, handling overflows (sigh). This is
+ // quick and dirty, but allows us to view the output image
+ // easily.
+ color =
+ color >= 255 ?
+ 1 :
+ color + 1;
+ }
+#endif
+
+#if 0
+ algo.area_opening (5);
+ oln::io::save (algo.ima(), argv[2]);
+#endif
+}
--- 10.249/configure.ac Tue, 11 Jul 2006 15:25:21 +0200 levill_r (oln/3_configure.
1.47.1.1.1.1.1.4.1.15.1.16.1.9 600)
+++ 10.250/configure.ac Fri, 25 Aug 2006 17:56:35 +0200 levill_r (oln/3_configure.
1.47.1.1.1.1.1.4.1.15.1.16.1.10 600)
@@ -5,7 +5,7 @@
AC_INIT([Olena], OLN_VERSION, OLN_CONTACT, [olena])
AC_CONFIG_AUX_DIR([config])
AC_CONFIG_SRCDIR([config/oln.m4])
-AM_INIT_AUTOMAKE([1.7 no-define foreign dist-bzip2])
+AM_INIT_AUTOMAKE([1.9.5 no-define foreign dist-bzip2])
AC_CONFIG_HEADERS([config.h:config.hin])
# FIXME: maybe not the best way to do this
@@ -463,6 +463,16 @@
AC_SUBST([DOC_CPPFLAGS])
AC_SUBST([TOOLS_LDFLAGS])
+## -- FIXME: Improve integration. ----------------------------------------
+##
+## The contents of `olena/lrde' should be moved to subdirectory of
+## `olena/oln', and the contents of `olena/lrde/ufmt/bin to `olena/tests'
+## or to `tools'.
+AC_CONFIG_FILES([olena/oln/lrde/Makefile
+ olena/oln/lrde/ufmt/Makefile
+ olena/oln/lrde/ufmt/bin/Makefile])
+## ---------------------------------------- FIXME: Improve integration. --
+
AC_OUTPUT
if test "x$oln_cxxflags_clean" = xno; then
--- 10.249/olena/oln/Makefile.am Tue, 13 Apr 2004 13:53:26 +0200 palma_g
(oln/q/47_Makefile.a 1.3.1.1.1.6.1.7.1.7.1.1 600)
+++ 10.250/olena/oln/Makefile.am Fri, 25 Aug 2006 17:56:35 +0200 levill_r
(oln/q/47_Makefile.a 1.3.1.1.1.6.1.7.1.7.1.2 600)
@@ -10,3 +10,11 @@
olndir = $(includedir)/oln
nobase_oln_HEADERS = $(OLN_DEP)
+
+## -- FIXME: Improve integration. ----------------------------------------
+##
+## The contents of `olena/lrde' should be moved to subdirectory of
+## `olena/oln', and the contents of `olena/lrde/ufmt/bin to `olena/tests'
+## or to `tools'.
+SUBDIRS = . lrde/ufmt
+## ---------------------------------------- FIXME: Improve integration. --
--- 10.249/TODO Fri, 25 Aug 2006 18:01:35 +0200 levill_r ()
+++ 10.250/TODO Fri, 25 Aug 2006 17:56:35 +0200 levill_r (oln/x/23_TODO 1.1 644)
@@ -0,0 +1,3 @@
+TODO -*- outline -*-
+
+* Update the address of the FSF in Copyright notices (write a script)
--- 10.249/oln.prj
+++ 10.250/oln.prj
@@ -1,39 +1,27 @@
;; -*- Prcs -*-
(Created-By-Prcs-Version 1 3 3)
(Project-Description "Olena")
-(Project-Version oln 10 249)
-(Parent-Version oln 10 246)
-(Version-Log "2006-08-21 Thierry GERAUD <theo(a)tegucigalpa.lrde.epita.fr>
-
- Rename to conform to conventions given in the README file.
-
- * olena/oln/lrde/ufmt/README: Update.
- * olena/oln/lrde/ufmt/sp_maxtree.hh: Rename as...
- * olena/oln/lrde/ufmt/hpc_maxtree.hh: ...this.
- * olena/oln/lrde/ufmt/ai_maxtree.hh: Rename as...
- * olena/oln/lrde/ufmt/ad_maxtree.hh: ...this.
- * olena/oln/lrde/ufmt/si_maxtree.hh: Rename as...
- * olena/oln/lrde/ufmt/hdc_maxtree.hh: ...this.
- * olena/oln/lrde/ufmt/rup_maxtree.hh: Rename as...
- * olena/oln/lrde/ufmt/rpc_maxtree.hh: ...this.
- * olena/oln/lrde/ufmt/r1_maxtree.hh: Rename as...
- * olena/oln/lrde/ufmt/r1ic_maxtree.hh: ...this.
- * olena/oln/lrde/ufmt/bin/: Update.
-
- New versions with full compressed aux data.
-
- * olena/oln/lrde/ufmt/hdx_maxtree.hh: New.
- * olena/oln/lrde/ufmt/hpx_maxtree.hh: New.
- * olena/oln/lrde/ufmt/bin/hdx_maxtree.cc: New.
- * olena/oln/lrde/ufmt/bin/hpx_maxtree.cc: New.
-
- Bonus.
-
- * olena/oln/lrde/ufmt/bin/basic_salembier.cc: Add c2 case.
- ")
+(Project-Version oln 10 250)
+(Parent-Version oln 10 248)
+(Version-Log "2006-08-25 Roland Levillain <roland(a)lrde.epita.fr>
+
+ Max-tree computation based on Fiorio's and Gustedt's labelling
+ algorithm.
+
+ * oln/lrde/ufmt/fiorio-1.hh, oln/lrde/ufmt/fiorio-2.hh: New.
+ * oln/lrde/ufmt/bin/fiorio.cc: New.
+ * oln/lrde/ufmt/README: Update.
+
+ Make the the olena/oln/lrde/ufmt hierarchy a full-fledged part of
+ the autoconfiscated package.
+
+ * oln/lrde/Makefile.am, oln/lrde/ufmt/Makefile.am,
+ * oln/lrde/ufmt/bin/Makefile.am: New.
+ * TODO: New.
+")
(New-Version-Log "")
-(Checkin-Time "Mon, 21 Aug 2006 17:17:14 +0200")
-(Checkin-Login theo)
+(Checkin-Time "Fri, 25 Aug 2006 17:56:35 +0200")
+(Checkin-Login levill_r)
;; diff-ignore tests/data/.*pbm$
;; diff-ignore .*\.pbm$
;; diff-ignore .*\.pgm$
@@ -62,6 +50,7 @@
"stamp-h\\([0-9]\\)\\?$"
"CVS/"
".cvsignore$"
+ "^_build"
"obsolete/"
"/obsolete/"
"autom4te.cache"
@@ -93,11 +82,15 @@
"^\\(.*/\\)\\?aclocal.m4$"
"/configure$"
"^configure$"
+ "^config\\.site$"
"utilities/morpho/morpho-rules.make$"
"doc/ref/filelists.make$"
"config.h\\(in\\)\\?$"
"doc/ref/ref-level.tex"
"doc/ref/ref-morpho.tex"
+ "^doc/ref/exdoc\\.mk$"
+ "^doc/ref/doxygen\\.config$"
+ "^doc/ref/out/exdoc\\.config$"
"utilities/.*\\.1$"
"^attic/"
"oln-"
@@ -119,6 +112,7 @@
"olena/img/lena16b.ppgm"
"olena/img/lena16b.pgm"
"^tools/swilena/src/.*\\.i"
+ "^tools/swilena/doc/swilena\\.info$"
"olena/img/lena1d.ppbm"
"olena/img/lena1d128.pgm"
"olena/img/lena1d.pppm"
@@ -132,21 +126,18 @@
"olena/img/lena1d16b.ppbm"
"\\.xvpics/"
"old/"
- "^config/config\\.sub$"
- "^doc/ref/exdoc\\.mk$"
- "^doc/ref/out/exdoc\\.config$"
- "^config/config\\.guess$"
- "^doc/ref/doxygen\\.config$"
+ "^libtool$"
"^config/ltmain\\.sh$"
- "^libtool$"))
+ "^config/config\\.guess$"
+ "^config/config\\.sub$"))
(Project-Keywords)
(Files
- (ChangeLog (oln/o/33_ChangeLog 1.37.1.16.1.17.1.19.1.28 600))
+ (ChangeLog (oln/o/33_ChangeLog 1.37.1.16.1.17.1.19.1.29 600))
(doc/ChangeLog (oln/o/31_ChangeLog 1.38.1.7.1.5.1.14.1.17 600))
(integre/ChangeLog (oln/q/35_ChangeLog 1.12.1.2.1.51 600))
(metalic/ChangeLog (oln/q/30_ChangeLog 1.3.1.44 600))
- (olena/ChangeLog (oln/o/30_ChangeLog 1.27.1.36.1.3.1.11.1.5.1.64.1.47.1.93.1.27.2.12
600))
+ (olena/ChangeLog (oln/o/30_ChangeLog 1.27.1.36.1.3.1.11.1.5.1.64.1.47.1.93.1.27.2.13
600))
(tools/ChangeLog (oln/o/32_ChangeLog 1.10.1.17 600))
(tools/swilena/ChangeLog (oln/n/37_ChangeLog 1.7.1.48 600))
@@ -158,7 +149,7 @@
(cleanup.sh (oln/o/29_cleanup.sh 1.6 700))
- (configure.ac (oln/3_configure. 1.47.1.1.1.1.1.4.1.15.1.16.1.9 600))
+ (configure.ac (oln/3_configure. 1.47.1.1.1.1.1.4.1.15.1.16.1.10 600))
(doc/demo/image.cc (oln/d/46_image.cc 1.8 600))
(doc/demo/Makefile.am (oln/d/44_Makefile.a 1.16.1.2 600))
@@ -823,7 +814,7 @@
(integre/tests/check/defs.in (oln/q/42_defs.in 1.1 600))
(metalic/mlc/array/objs.hh (oln/q/45_objs.hh 1.3 600))
(metalic/mlc/config/system.hh (oln/q/46_system.hh 1.2 600))
- (olena/oln/Makefile.am (oln/q/47_Makefile.a 1.3.1.1.1.6.1.7.1.7.1.1 600))
+ (olena/oln/Makefile.am (oln/q/47_Makefile.a 1.3.1.1.1.6.1.7.1.7.1.2 600))
(integre/ntg/config/system.hh (oln/q/48_system.hh 1.2 600))
(metalic/tests/main/tests/is_a1 (oln/r/17_is_a1 1.4 600))
(metalic/tests/main/tests/ensure3 (oln/r/18_ensure3 1.4 600))
@@ -1582,7 +1573,7 @@
- (olena/oln/lrde/ufmt/README (oln/x/22_README 1.2 644))
+ (olena/oln/lrde/ufmt/README (oln/x/22_README 1.3 644))
;; Files deleted by depopulate at Fri, 04 Aug 2006 18:41:16 +0200,
;; from version 10.245(w), by theo:
@@ -1593,18 +1584,38 @@
; (olena/oln/lrde/ufmt/bin/exe/rup_maxtree () :no-keywords)
; (olena/oln/lrde/ufmt/bin/exe/basic_salembier () :no-keywords)
; (olena/oln/lrde/ufmt/bin/exe/basic_maxtree () :no-keywords)
+
+;; Files deleted by depopulate at Thu, 17 Aug 2006 10:46:05 +0200,
+;; from version 10.246(w), by levill_r:
+
+ ; (libtool ())
+ ; (config/ltmain.sh ())
+ ; (config/config.sub ())
+ ; (config/config.guess ())
+ ; (doc/ref/exdoc.mk ())
+ ; (doc/ref/doxygen.config ())
+ ; (doc/ref/out/exdoc.config ())
+
+;; Files added by populate at Fri, 25 Aug 2006 17:30:22 +0200,
+;; to version 10.248(w), by levill_r:
+
+ (TODO (oln/x/23_TODO 1.1 644))
+ (olena/TODO (oln/x/24_TODO 1.1 644))
+ (olena/oln/lrde/Makefile.am (oln/x/25_Makefile.a 1.1 644))
+ (olena/oln/lrde/ufmt/Makefile.am (oln/x/26_Makefile.a 1.1 644))
+ (olena/oln/lrde/ufmt/fiorio-1.hh (oln/x/27_fiorio-1.h 1.1 644))
+ (olena/oln/lrde/ufmt/fiorio-2.hh (oln/x/28_fiorio-2.h 1.1 644))
+ (olena/oln/lrde/ufmt/bin/Makefile.am (oln/x/29_Makefile.a 1.1 644))
+ (olena/oln/lrde/ufmt/bin/fiorio.cc (oln/x/30_fiorio.cc 1.1 644))
)
(Merge-Parents
- (10.248 incomplete)
- (10.248 incomplete)
- (10.248 complete
- (ChangeLog ChangeLog ChangeLog r) (doc/ChangeLog doc/ChangeLog doc/ChangeLog r)
- (integre/ChangeLog integre/ChangeLog integre/ChangeLog r) (metalic/ChangeLog
metalic/ChangeLog metalic/ChangeLog r)
- (olena/ChangeLog olena/ChangeLog olena/ChangeLog r) (tools/swilena/ChangeLog
tools/swilena/ChangeLog tools/swilena/ChangeLog r)
- (libtool libtool () d) (config/ltmain.sh config/ltmain.sh () d)
- (config/config.sub config/config.sub () d) (config/config.guess config/config.guess
() d)
- (doc/ref/exdoc.mk doc/ref/exdoc.mk () d) (doc/ref/doxygen.config
doc/ref/doxygen.config () d)
- (doc/ref/out/exdoc.config doc/ref/out/exdoc.config () d)
- )
+ (10.249 complete
+ (ChangeLog ChangeLog ChangeLog r) (olena/oln/lrde/ufmt/bin/basic_salembier.cc
olena/oln/lrde/ufmt/bin/basic_salembier.cc olena/oln/lrde/ufmt/bin/basic_salembier.cc r)
+ (olena/oln/lrde/ufmt/log.hh olena/oln/lrde/ufmt/log.hh olena/oln/lrde/ufmt/log.hh r)
(olena/oln/lrde/ufmt/ad_maxtree.hh olena/oln/lrde/ufmt/ai_maxtree.hh
olena/oln/lrde/ufmt/ad_maxtree.hh r)
+ (olena/oln/lrde/ufmt/hdc_maxtree.hh olena/oln/lrde/ufmt/si_maxtree.hh
olena/oln/lrde/ufmt/hdc_maxtree.hh r) (olena/oln/lrde/ufmt/rpc_maxtree.hh
olena/oln/lrde/ufmt/rup_maxtree.hh olena/oln/lrde/ufmt/rpc_maxtree.hh r)
+ (olena/oln/lrde/ufmt/hpc_maxtree.hh olena/oln/lrde/ufmt/sp_maxtree.hh
olena/oln/lrde/ufmt/hpc_maxtree.hh r) (olena/oln/lrde/ufmt/ap_maxtree.hh
olena/oln/lrde/ufmt/ap_maxtree.hh olena/oln/lrde/ufmt/ap_maxtree.hh r)
+ (olena/oln/lrde/ufmt/r1ic_maxtree.hh olena/oln/lrde/ufmt/r1_maxtree.hh
olena/oln/lrde/ufmt/r1ic_maxtree.hh r) (olena/oln/lrde/ufmt/bin/rpc_maxtree.cc
olena/oln/lrde/ufmt/bin/rup_maxtree.cc olena/oln/lrde/ufmt/bin/rpc_maxtree.cc r)
+ (olena/oln/lrde/ufmt/bin/hdc_maxtree.cc olena/oln/lrde/ufmt/bin/si_maxtree.cc
olena/oln/lrde/ufmt/bin/hdc_maxtree.cc r) (olena/oln/lrde/ufmt/bin/hpc_maxtree.cc
olena/oln/lrde/ufmt/bin/sp_maxtree.cc olena/oln/lrde/ufmt/bin/hpc_maxtree.cc r)
+ (olena/oln/lrde/ufmt/bin/r1ic_maxtree.cc olena/oln/lrde/ufmt/bin/r1_maxtree.cc
olena/oln/lrde/ufmt/bin/r1ic_maxtree.cc r) (olena/oln/lrde/ufmt/README
olena/oln/lrde/ufmt/README olena/oln/lrde/ufmt/README m))
)
(New-Merge-Parents)