[Olena-patches] olena-0.10 10.270: New versions of Salembier et al. algorithm

2007-01-03 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; New versions of Salembier et al. algorithm. * oln/lrde/ufmt/generic_salembier.hh (oln::lrde::ufmt::generic_salembier): Add a second template parameter, defaulting to std::greater< oln_value_type(I) >. Use this parameter for comparisons, to have the algorithm be more flexible. * oln/lrde/ufmt/bin/generic_salembier_float2.cc: New. Use the second template parameter of oln::lrde::ufmt::generic_salembier to create a more flexible version of generic_salembier_float where float comparisons are performed using a maxium relative error and a maximum absolute error. * oln/lrde/ufmt/generic_simplified_salembier.hh: New. A simplified version of oln::lrde::ufmt::generic_salembier, specially useful on float images. * oln/lrde/ufmt/bin/generic_simplified_salembier_float.cc: New. * oln/lrde/ufmt/naive_generic_salembier.hh: New. A previous attempt before generic_simplified_salembier. * oln/lrde/ufmt/basic_salembier.hh: More documentation. * oln/lrde/ufmt/bin/basic_najman.cc: Typo. * oln/lrde/ufmt/README: Document Salembier et al. algorithm variants. * oln/lrde/ufmt/bin/Makefile.am (check_PROGRAMS): Add generic_salembier_float2, generic_simplified_salembier_float and naive_generic_salembier_float. (generic_salembier_float2_SOURCES) (generic_salembier_float2_LDFLAGS) (generic_simplified_salembier_float_SOURCES) (generic_simplified_salembier_float_LDFLAGS) (naive_generic_salembier_float_SOURCES) (naive_generic_salembier_float_LDFLAGS): New. * oln/lrde/ufmt/Makefile.am (noinst_HEADERS): Add generic_simplified_salembier.hh and naive_generic_salembier.hh. --- 10.269/olena/oln/lrde/ufmt/basic_salembier.hh Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/w/51_basic_sale 1.2 644) +++ 10.270/olena/oln/lrde/ufmt/basic_salembier.hh Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/w/51_basic_sale 1.3 644) @@ -119,7 +119,47 @@ }; - /// Salembier's algorithm -- Version for images of unsigned integers. + /** \brief Salembier's algorithm -- Version for images of + unsigned integers. + + The (corrected) algorithm, as written in the original + article, is as follows: + + \verbatim + + flood (h) + + while not hqueue-empty (h) + p <- hqueue-first (h) + STATUS(p) <- number-nodes (h) + for every neighbor q of p + if STATUS(q) == "Not analyzed" + hqueue-add(ORI(q), q) + STATUS(q) <- "In the queue" + node-at-level(ORI(q)) <- true + if (ORI(q) > ORI(p)) + m = ORI(q) + repeat + m <- flood(m) + until m <= h + number-nodes(h) <- number-nodes(h) + 1 + + m <- h - 1 + while m >= 0 and node-at-level(m) == false + m <- m - 1 + i <- number-nodes(h) - 1 + if m >= 0 + j <- number-nodes(m) + father of C(i, h) <- node C(j, m) + else + C(i, h) has no father // C(i, h) is root node. + node-at-level(h) <- false + return m + + \endverbatim + + \ref salembier.98.itip. */ + template <class I> struct basic_salembier { --- 10.269/olena/oln/lrde/ufmt/README Tue, 29 Aug 2006 14:48:46 +0200 levill_r (oln/x/22_README 1.6 644) +++ 10.270/olena/oln/lrde/ufmt/README Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/x/22_README 1.7 644) @@ -123,11 +123,50 @@ spx impled -* basic_salembier +* algorithms deriving from Salembier et al. algorithm + +** basic_salembier + +flooding +p as point2d +father as std::map<pair_t, pair_t> +hqueue as an array of std::queue<point> +works only on image of unsigned integers (unsigned int or ntg::int_u8 + for instance) + +** generic_salembier + +flooding +p as point2d +father as std::map<pair, pair> +hqueue as std::map<value, std::queue<point> > +modifiable comparison function on values (defaulting to + std::greater< oln_value_type(I) >) +works only on any kind of image whose values are comparable + +** generic_simplified_salembier + +flooding +the algorithm consider that each site (pixel) has a unique ``value'' + within the image (the algorithm no longer works on levels, only on + points, which are totally ordered) +p as point2d +father as std::map<point, point, point_less<I, point> > +no hqueue, but a set of points instead +works on any kind of image whose values are comparable + +** naive_generic_salembier + +A previous version of generic_simplified_salembier, probablt no longer +useful. flooding +the algorithm doesn't really handle flat zones (i.e., contiguous +pixels having the same value). p as point2d -father as map<pair,pair> +father as std::map<pair, pair> +hqueue as std::map<V, P> +works on any kind of image whose values are comparable --- 10.269/olena/oln/lrde/ufmt/Makefile.am Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/x/26_Makefile.a 1.5 644) +++ 10.270/olena/oln/lrde/ufmt/Makefile.am Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/x/26_Makefile.a 1.6 644) @@ -17,6 +17,8 @@ \ basic_salembier.hh \ generic_salembier.hh \ + generic_simplified_salembier.hh \ + naive_generic_salembier.hh \ \ fiorio-1.hh \ fiorio-2.hh \ --- 10.269/olena/oln/lrde/ufmt/bin/Makefile.am Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/x/29_Makefile.a 1.4 644) +++ 10.270/olena/oln/lrde/ufmt/bin/Makefile.am Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/x/29_Makefile.a 1.5 644) @@ -1,10 +1,12 @@ AM_CXXFLAGS = -Wall -Werror -ansi -pedantic -ggdb -O3 -DNDEBUG AM_LDFLAGS = $(ZLIB_LDFLAGS) -check_PROGRAMS = \ - basic_maxtree basic_najman basic_salembier \ - generic_salembier_int_u8 generic_salembier_float \ - fiorio-1 fiorio-2 fiorio-3 \ +check_PROGRAMS = \ + basic_maxtree basic_najman basic_salembier \ + generic_salembier_int_u8 generic_salembier_float generic_salembier_float2 \ + generic_simplified_salembier_float \ + naive_generic_salembier_float \ + fiorio-1 fiorio-2 fiorio-3 \ hdc_maxtree hpc_maxtree r1ic_maxtree rpc_maxtree basic_maxtree_SOURCES = basic_maxtree.cc @@ -14,6 +16,12 @@ generic_salembier_int_u8_SOURCES = generic_salembier_int_u8.cc generic_salembier_float_SOURCES = generic_salembier_float.cc generic_salembier_float_LDFLAGS = -lcfitsio $(ZLIB_LDFLAGS) +generic_salembier_float2_SOURCES = generic_salembier_float2.cc +generic_salembier_float2_LDFLAGS = -lcfitsio $(ZLIB_LDFLAGS) +generic_simplified_salembier_float_SOURCES = generic_simplified_salembier_float.cc +generic_simplified_salembier_float_LDFLAGS = -lcfitsio $(ZLIB_LDFLAGS) +naive_generic_salembier_float_SOURCES = naive_generic_salembier_float.cc +naive_generic_salembier_float_LDFLAGS = -lcfitsio $(ZLIB_LDFLAGS) fiorio_1_SOURCES = fiorio.cc fiorio_2_SOURCES = fiorio.cc --- 10.269/olena/oln/lrde/ufmt/bin/basic_najman.cc Mon, 28 Aug 2006 18:17:59 +0200 berger_c (oln/x/43_basic_najm 1.1 644) +++ 10.270/olena/oln/lrde/ufmt/bin/basic_najman.cc Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/x/43_basic_najm 1.2 644) @@ -11,7 +11,8 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " input.pgm c" << std::endl; - std::cerr << "basic max-tree computation with union-find" << std::endl; + std::cerr << "basic max-tree computation with Najman et al. algorithm" + << std::endl; // FIXME: get precise description... exit(1); } --- 10.269/olena/oln/lrde/ufmt/naive_generic_salembier.hh Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/y/7_naive_gene 1.1 644) +++ 10.270/olena/oln/lrde/ufmt/naive_generic_salembier.hh Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/y/7_naive_gene 1.2 644) @@ -25,6 +25,12 @@ // reasons why the executable file might be covered by the GNU General // Public License. + +// FIXME: This version of Salembier et al. algorithm has been +// superseded by oln::lrde::ufmt::generic_simplified_salembier, and +// should not be useful anymore. + + #ifndef OLENA_LRDE_UFMT_NAIVE_GENERIC_SALEMBIER_HH # define OLENA_LRDE_UFMT_NAIVE_GENERIC_SALEMBIER_HH @@ -202,7 +208,7 @@ m = levels.find(f[q]); if (m == levels.end()) abort(); - while (*m > h) // err. 2 + while (m != levels.end() and *m > h) // err. 2 m = flood(*m); } } --- 10.269/olena/oln/lrde/ufmt/generic_salembier.hh Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/y/8_generic_sa 1.1 644) +++ 10.270/olena/oln/lrde/ufmt/generic_salembier.hh Wed, 03 Jan 2007 15:17:57 +0100 levill_r (oln/y/8_generic_sa 1.2 644) @@ -115,7 +115,8 @@ }; - template <class I> + template < class I, + class Greater = std::greater< oln_value_type(I) > > struct generic_salembier { typedef oln_point_type(I) point; @@ -140,12 +141,15 @@ generic_hqueue_t<value, point> hqueue; value h_min; - typedef std::set< value, std::greater<value> > levels_t; + typedef std::set< value, Greater > levels_t; typedef typename levels_t::const_iterator level_iterator; // Set of all values present in the input image, sorting in // descending order. levels_t levels; + // Level comparison function. + Greater level_greater; + typedef std::pair<unsigned, value> pair_t; std::map<pair_t, pair_t> father; @@ -181,7 +185,7 @@ // Init levels. levels.insert(f[p]); // Find the global Only in 10.270: olena/oln/lrde/ufmt/bin/generic_salembier_float2.cc Only in 10.270: olena/oln/lrde/ufmt/bin/generic_simplified_salembier_float.cc Only in 10.270: olena/oln/lrde/ufmt/bin/naive_generic_salembier_float.cc Only in 10.270: olena/oln/lrde/ufmt/generic_simplified_salembier.hh minimum. - if (f[p] < h_min) + if (level_greater(h_min, f[p])) // Was: f[p] < h_min { h_min = f[p]; p_min = p; @@ -215,7 +219,7 @@ m = levels.find(f[q]); if (m == levels.end()) abort(); - while (*m > h) // err. 2 + while (m != levels.end() and *m > h) // err. 2 m = flood(*m); } } --- 10.269/oln.prj +++ 10.270/oln.prj @@ -1,30 +1,47 @@ ;; -*- Prcs -*- (Created-By-Prcs-Version 1 3 3) (Project-Description "Olena") -(Project-Version oln 10 269) -(Parent-Version oln 10 268) -(Version-Log "2006-12-20 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; - - Add a more generic version of Salembier's algorithm. - - * oln/lrde/ufmt/basic_salembier.hh - (oln::lrde::ufmt::hqueue_t::print): New method. - * oln/lrde/ufmt/generic_salembier.hh: New. - * oln/lrde/ufmt/bin/basic_salembier.cc: Add a timer. - * oln/lrde/ufmt/bin/generic_salembier_int_u8.cc, - * oln/lrde/ufmt/bin/generic_salembier_float.cc: New. - * oln/lrde/Makefile.am (SUBDIRS): Add efigi. +(Project-Version oln 10 270) +(Parent-Version oln 10 269) +(Version-Log "2007-01-03 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + + New versions of Salembier et al. algorithm. + + * oln/lrde/ufmt/generic_salembier.hh + (oln::lrde::ufmt::generic_salembier): Add a second template + parameter, defaulting to std::greater< oln_value_type(I) >. Use + this parameter for comparisons, to have the algorithm be more + flexible. + * oln/lrde/ufmt/bin/generic_salembier_float2.cc: New. + Use the second template parameter of + oln::lrde::ufmt::generic_salembier to create a more flexible + version of generic_salembier_float where float comparisons are + performed using a maxium relative error and a maximum absolute + error. + * oln/lrde/ufmt/generic_simplified_salembier.hh: New. + A simplified version of oln::lrde::ufmt::generic_salembier, + specially useful on float images. + * oln/lrde/ufmt/bin/generic_simplified_salembier_float.cc: New. + * oln/lrde/ufmt/naive_generic_salembier.hh: New. + A previous attempt before generic_simplified_salembier. + * oln/lrde/ufmt/basic_salembier.hh: More documentation. + * oln/lrde/ufmt/bin/basic_najman.cc: Typo. + * oln/lrde/ufmt/README: Document Salembier et al. algorithm variants. * oln/lrde/ufmt/bin/Makefile.am (check_PROGRAMS): Add - generic_salembier_int_u8 and generic_salembier_float. - (generic_salembier_int_u8_SOURCES) - (generic_salembier_float_SOURCES) - (generic_salembier_float_LDFLAGS): New. + generic_salembier_float2, generic_simplified_salembier_float + and naive_generic_salembier_float. + (generic_salembier_float2_SOURCES) + (generic_salembier_float2_LDFLAGS) + (generic_simplified_salembier_float_SOURCES) + (generic_simplified_salembier_float_LDFLAGS) + (naive_generic_salembier_float_SOURCES) + (naive_generic_salembier_float_LDFLAGS): New. + * oln/lrde/ufmt/Makefile.am (noinst_HEADERS): Add + generic_simplified_salembier.hh and naive_generic_salembier.hh. - * oln/lrde/efigi/pgm2pfm_wo_noise.cc: New - * oln/lrde/efigi/Makefile.am: New. ") (New-Version-Log "") -(Checkin-Time "Wed, 20 Dec 2006 14:46:12 +0100") +(Checkin-Time "Wed, 03 Jan 2007 15:17:57 +0100") (Checkin-Login levill_r) ;; diff-ignore tests/data/.*pbm$ ;; diff-ignore .*\.pbm$ @@ -141,7 +158,7 @@ (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.18.1.8 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.18.1.9 600)) (tools/ChangeLog (oln/o/32_ChangeLog 1.10.1.17 600)) (tools/swilena/ChangeLog (oln/n/37_ChangeLog 1.7.1.52 600)) @@ -1543,7 +1560,7 @@ - (olena/oln/lrde/ufmt/basic_salembier.hh (oln/w/51_basic_sale 1.2 644)) + (olena/oln/lrde/ufmt/basic_salembier.hh (oln/w/51_basic_sale 1.3 644)) (olena/oln/lrde/ufmt/bin/basic_maxtree.cc (oln/x/0_basic_maxt 1.2 644)) (olena/oln/lrde/ufmt/bin/basic_salembier.cc (oln/x/1_basic_sale 1.3 644)) (olena/oln/lrde/ufmt/bin/gppo (oln/x/2_gppo 1.1.1.1 755)) @@ -1577,7 +1594,7 @@ - (olena/oln/lrde/ufmt/README (oln/x/22_README 1.6 644)) + (olena/oln/lrde/ufmt/README (oln/x/22_README 1.7 644)) ;; Files deleted by depopulate at Fri, 04 Aug 2006 18:41:16 +0200, ;; from version 10.245(w), by theo: @@ -1593,10 +1610,10 @@ (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.2 644)) - (olena/oln/lrde/ufmt/Makefile.am (oln/x/26_Makefile.a 1.5 644)) + (olena/oln/lrde/ufmt/Makefile.am (oln/x/26_Makefile.a 1.6 644)) (olena/oln/lrde/ufmt/fiorio-1.hh (oln/x/27_fiorio-1.h 1.3 644)) (olena/oln/lrde/ufmt/fiorio-2.hh (oln/x/28_fiorio-2.h 1.3 644)) - (olena/oln/lrde/ufmt/bin/Makefile.am (oln/x/29_Makefile.a 1.4 644)) + (olena/oln/lrde/ufmt/bin/Makefile.am (oln/x/29_Makefile.a 1.5 644)) (olena/oln/lrde/ufmt/bin/fiorio.cc (oln/x/30_fiorio.cc 1.3 644)) ;; Files added by populate at Mon, 28 Aug 2006 10:51:36 +0200, ;; to version 10.249(w), by theo: @@ -1637,7 +1654,7 @@ ;; Files added by populate at Mon, 28 Aug 2006 18:08:14 +0200, ;; to version 10.253(w), by berger_c: - (olena/oln/lrde/ufmt/bin/basic_najman.cc (oln/x/43_basic_najm 1.1 644)) + (olena/oln/lrde/ufmt/bin/basic_najman.cc (oln/x/43_basic_najm 1.2 644)) ;; Files added by populate at Fri, 15 Dec 2006 10:12:49 +0100, ;; to version 10.255(w), by theo: @@ -1660,12 +1677,18 @@ (olena/oln/lrde/efigi/pgm2pfm_wo_noise.cc (oln/y/5_pgm2pfm_wo 1.1 644)) (olena/oln/lrde/efigi/Makefile.am (oln/y/6_Makefile.a 1.1 644)) - (olena/oln/lrde/ufmt/naive_generic_salembier.hh (oln/y/7_naive_gene 1.1 644)) - (olena/oln/lrde/ufmt/generic_salembier.hh (oln/y/8_generic_sa 1.1 644)) + (olena/oln/lrde/ufmt/naive_generic_salembier.hh (oln/y/7_naive_gene 1.2 644)) + (olena/oln/lrde/ufmt/generic_salembier.hh (oln/y/8_generic_sa 1.2 644)) (olena/oln/lrde/ufmt/bin/generic_salembier_int_u8.cc (oln/y/9_generic_sa 1.1 644)) (olena/oln/lrde/ufmt/bin/generic_salembier_float.cc (oln/y/10_generic_sa 1.1 644)) + +;; Files added by populate at Wed, 03 Jan 2007 14:28:38 +0100, +;; to version 10.269(w), by levill_r: + + (olena/oln/lrde/ufmt/bin/generic_salembier_float2.cc (oln/y/11_generic_sa 1.1 644)) + (olena/oln/lrde/ufmt/bin/generic_simplified_salembier_float.cc (oln/y/12_generic_si 1.1 644)) + (olena/oln/lrde/ufmt/bin/naive_generic_salembier_float.cc (oln/y/13_naive_gene 1.1 644)) + (olena/oln/lrde/ufmt/generic_simplified_salembier.hh (oln/y/14_generic_si 1.1 644)) ) -(Merge-Parents - (10.268 complete) -) +(Merge-Parents) (New-Merge-Parents)