[Olena-patches] olena-0.10 10.269: Add a more generic version of Salembier's algorithm

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. * 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. * oln/lrde/efigi/pgm2pfm_wo_noise.cc: New * oln/lrde/efigi/Makefile.am: New. --- 10.268/olena/oln/lrde/ufmt/basic_salembier.hh Thu, 03 Aug 2006 16:06:43 +0200 theo (oln/w/51_basic_sale 1.1 644) +++ 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) @@ -36,7 +36,6 @@ # include <oln/lrde/ufmt/utils.hh> - namespace oln { @@ -46,6 +45,13 @@ namespace ufmt { + /*-----------------------------------------------------------. + | Original version of Salembier's algorithm (working only on | + | image of unsigned integers). | + `-----------------------------------------------------------*/ + + /// Version of hqueue for unsigned values, using an array of + /// queues, indexed by the gray level. template <class P> struct hqueue_t { @@ -91,10 +97,29 @@ return s; } + void print (std::ostream& os) + { + os << "hqueue = {"; + for (unsigned h = 0; h < nvalues; ++h) + if (not empty(h)) + { + os << " " << h << " -> { "; + std::queue<P> queue_copy = q[h]; + while (not queue_copy.empty()) + { + os << queue_copy.front () << " "; + queue_copy.pop(); + } + os << "}"; + } + os << " }" << std::endl; + } + std::queue<P>* q; }; + /// Salembier's algorithm -- Version for images of unsigned integers. template <class I> struct basic_salembier { @@ -175,6 +200,7 @@ while (not hqueue.empty(h)) { point p = hqueue.first(h); + status[p] = number_nodes[h]; oln_neighb_type(Nbh) q(nbh, p); @@ -204,7 +230,7 @@ if (m >= 0) { int j = number_nodes[m]; - father[pair_t(i, h)] = pair_t(j, m ); + father[pair_t(i, h)] = pair_t(j, m); } else { @@ -223,7 +249,6 @@ }; // end of struct basic_salembier - } // end of namespace oln::lrde::ufmt } // end of namespace oln::lrde --- 10.268/olena/oln/lrde/ufmt/bin/basic_salembier.cc Mon, 21 Aug 2006 17:17:14 +0200 theo (oln/x/1_basic_sale 1.2 644) +++ 10.269/olena/oln/lrde/ufmt/bin/basic_salembier.cc Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/x/1_basic_sale 1.3 644) @@ -3,6 +3,7 @@ #include <ntg/int.hh> #include <oln/basics2d.hh> +#include <oln/utils/timer.hh> #include <oln/lrde/ufmt/basic_salembier.hh> @@ -10,7 +11,8 @@ void usage(char* argv[]) { std::cerr << "usage: " << argv[0] << " input.pgm c" << std::endl; - std::cerr << "basic max-tree computation with salembier's flooding" << std::endl; + std::cerr << "basic max-tree computation with salembier's flooding" + << std::endl; // FIXME: get precise description... exit(1); } @@ -25,6 +27,7 @@ typedef image2d<ntg::int_u8> image_t; image_t input = load(argv[1]); + assert (input.has_impl()); int c = atoi(argv[2]); if (not (c == 2 or c == 4 or c == 8)) @@ -39,6 +42,10 @@ nbh = c == 4 ? neighb_c4() : neighb_c8(); algorithm_t run(input, nbh); + utils::timer t; + t.start(); run.go(); - std::cout << "n level roots = " << run.n_level_roots() << std::endl; + t.stop(); + std::cout << "n level roots = " << run.n_level_roots() << std::endl + << "elapsed time = " << t.last_time() << std::endl; } --- 10.268/olena/oln/lrde/Makefile.am Fri, 25 Aug 2006 17:56:35 +0200 levill_r (oln/x/25_Makefile.a 1.1 644) +++ 10.269/olena/oln/lrde/Makefile.am Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/x/25_Makefile.a 1.2 644) @@ -5,5 +5,5 @@ ## 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 +SUBDIRS = efigi ufmt ## ---------------------------------------- FIXME: Improve integration. -- --- 10.268/olena/oln/lrde/ufmt/Makefile.am Fri, 20 Oct 2006 19:13:44 +0200 levill_r (oln/x/26_Makefile.a 1.4 644) +++ 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) @@ -14,7 +14,10 @@ attributes.hh \ basic_maxtree.hh \ basic_najman.hh \ + \ basic_salembier.hh \ + generic_salembier.hh \ + \ fiorio-1.hh \ fiorio-2.hh \ fiorio-3.hh \ --- 10.268/olena/oln/lrde/ufmt/bin/Makefile.am Tue, 29 Aug 2006 14:48:46 +0200 levill_r (oln/x/29_Makefile.a 1.3 644) +++ 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) @@ -3,17 +3,24 @@ check_PROGRAMS = \ basic_maxtree basic_najman basic_salembier \ + generic_salembier_int_u8 generic_salembier_float \ fiorio-1 fiorio-2 fiorio-3 \ hdc_maxtree hpc_maxtree r1ic_maxtree rpc_maxtree basic_maxtree_SOURCES = basic_maxtree.cc basic_najman_SOURCES = basic_najman.cc basic_salembier_SOURCES = basic_salembier.cc + +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) + fiorio_1_SOURCES = fiorio.cc fiorio_2_SOURCES = fiorio.cc fiorio_2_CPPFLAGS = -DFIORIO_VERSION=2 fiorio_3_SOURCES = fiorio.cc fiorio_3_CPPFLAGS = -DFIORIO_VERSION=3 + hdc_maxtree_SOURCES = hdc_maxtree.cc hpc_maxtree_SOURCES = hpc_maxtree.cc r1ic_maxtree_SOURCES = r1ic_maxtree.cc Only in 10.269: olena/oln/lrde/efigi/pgm2pfm_wo_noise.cc Only in 10.269: olena/oln/lrde/efigi/Makefile.am Only in 10.269: olena/oln/lrde/ufmt/naive_generic_salembier.hh Only in 10.269: olena/oln/lrde/ufmt/generic_salembier.hh Only in 10.269: olena/oln/lrde/ufmt/bin/generic_salembier_int_u8.cc Only in 10.269: olena/oln/lrde/ufmt/bin/generic_salembier_float.cc --- 10.268/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) +++ 10.269/configure.ac Wed, 20 Dec 2006 14:46:12 +0100 levill_r (oln/3_configure. 1.47.1.1.1.1.1.4.1.15.1.16.1.11 600) @@ -469,6 +469,7 @@ ## `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/efigi/Makefile olena/oln/lrde/ufmt/Makefile olena/oln/lrde/ufmt/bin/Makefile]) ## ---------------------------------------- FIXME: Improve integration. -- --- 10.268/oln.prj +++ 10.269/oln.prj @@ -1,25 +1,31 @@ ;; -*- Prcs -*- (Created-By-Prcs-Version 1 3 3) (Project-Description "Olena") -(Project-Version oln 10 268) -(Parent-Version oln 10 255) -(Version-Log "2006-12-15 Thierry GERAUD &lt;theo(a)tegucigalpa.lrde.epita.fr&gt; - - Add some EFIGI utilities. - - * olena/oln/lrde/efigi/pfm2pgm.cc, - * olena/oln/lrde/efigi/misc.hh, - * olena/oln/lrde/efigi/io.hh, - * olena/oln/lrde/efigi/req.hh, - * olena/oln/lrde/efigi/wst.cc, - * olena/oln/lrde/efigi/gaussian.cc, - * olena/oln/lrde/efigi/pgm2pfm.cc, - * olena/oln/lrde/efigi/wst.hh: - New. +(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. + * 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. + + * oln/lrde/efigi/pgm2pfm_wo_noise.cc: New + * oln/lrde/efigi/Makefile.am: New. ") (New-Version-Log "") -(Checkin-Time "Fri, 15 Dec 2006 10:22:33 +0100") -(Checkin-Login theo) +(Checkin-Time "Wed, 20 Dec 2006 14:46:12 +0100") +(Checkin-Login levill_r) ;; diff-ignore tests/data/.*pbm$ ;; diff-ignore .*\.pbm$ ;; diff-ignore .*\.pgm$ @@ -131,11 +137,11 @@ (Project-Keywords) (Files - (ChangeLog (oln/o/33_ChangeLog 1.37.1.16.1.17.1.19.1.29 600)) + (ChangeLog (oln/o/33_ChangeLog 1.37.1.16.1.17.1.19.1.30 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.18.1.7 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)) (tools/ChangeLog (oln/o/32_ChangeLog 1.10.1.17 600)) (tools/swilena/ChangeLog (oln/n/37_ChangeLog 1.7.1.52 600)) @@ -147,7 +153,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.10 600)) + (configure.ac (oln/3_configure. 1.47.1.1.1.1.1.4.1.15.1.16.1.11 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)) @@ -1537,9 +1543,9 @@ - (olena/oln/lrde/ufmt/basic_salembier.hh (oln/w/51_basic_sale 1.1 644)) + (olena/oln/lrde/ufmt/basic_salembier.hh (oln/w/51_basic_sale 1.2 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.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)) (olena/oln/lrde/ufmt/bin/gpp (oln/x/3_gpp 1.1.1.1 755)) @@ -1586,11 +1592,11 @@ (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.4 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/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.3 644)) + (olena/oln/lrde/ufmt/bin/Makefile.am (oln/x/29_Makefile.a 1.4 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: @@ -1648,21 +1654,18 @@ (olena/oln/lrde/ufmt/fiorio-3.hh (oln/x/44_fiorio-3.h 1.1 644)) (olena/oln/lrde/ufmt/img/lena64nb.pgm (oln/x/47_lena64nb.p 1.1 644) :no-keywords) - (olena/oln/lrde/ufmt/img/lena64.pbm (oln/x/48_lena64.pbm 1.1 644) :no-keywords)) + (olena/oln/lrde/ufmt/img/lena64.pbm (oln/x/48_lena64.pbm 1.1 644) :no-keywords) +;; Files added by populate at Wed, 20 Dec 2006 11:47:55 +0100, +;; to version 10.268(w), by levill_r: + + (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/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)) +) (Merge-Parents - (10.267 complete - (olena/ChangeLog olena/ChangeLog olena/ChangeLog m) (tools/swilena/ChangeLog tools/swilena/ChangeLog tools/swilena/ChangeLog r) - (olena/oln/Makefile.am olena/oln/Makefile.am olena/oln/Makefile.am r) (tools/swilena/ruby/Makefile.am tools/swilena/ruby/Makefile.am tools/swilena/ruby/Makefile.am r) - (tools/swilena/python/Makefile.am tools/swilena/python/Makefile.am tools/swilena/python/Makefile.am r) (olena/oln/makefile.src olena/oln/makefile.src olena/oln/makefile.src r) - (tools/swilena/ruby/ltrequire.rb tools/swilena/ruby/ltrequire.rb tools/swilena/ruby/ltrequire.rb r) (olena/oln/lrde/ufmt/bin/gppo olena/oln/lrde/ufmt/bin/gppo olena/oln/lrde/ufmt/bin/gppo r) - (olena/oln/lrde/ufmt/bin/gpp olena/oln/lrde/ufmt/bin/gpp olena/oln/lrde/ufmt/bin/gpp r) (olena/oln/lrde/ufmt/bin/inc olena/oln/lrde/ufmt/bin/inc () d) - (olena/oln/lrde/ufmt/utils.hh olena/oln/lrde/ufmt/utils.hh olena/oln/lrde/ufmt/utils.hh r) (olena/oln/lrde/ufmt/README olena/oln/lrde/ufmt/README olena/oln/lrde/ufmt/README r) - (olena/oln/lrde/ufmt/Makefile.am olena/oln/lrde/ufmt/Makefile.am olena/oln/lrde/ufmt/Makefile.am r) (olena/oln/lrde/ufmt/fiorio-1.hh olena/oln/lrde/ufmt/fiorio-1.hh olena/oln/lrde/ufmt/fiorio-1.hh r) - (olena/oln/lrde/ufmt/fiorio-2.hh olena/oln/lrde/ufmt/fiorio-2.hh olena/oln/lrde/ufmt/fiorio-2.hh r) (olena/oln/lrde/ufmt/bin/Makefile.am olena/oln/lrde/ufmt/bin/Makefile.am olena/oln/lrde/ufmt/bin/Makefile.am r) - (olena/oln/lrde/ufmt/bin/fiorio.cc olena/oln/lrde/ufmt/bin/fiorio.cc olena/oln/lrde/ufmt/bin/fiorio.cc r) (olena/oln/lrde/ufmt/attributes.hh olena/oln/lrde/ufmt/attributes.hh olena/oln/lrde/ufmt/attributes.hh r) - (olena/oln/lrde/ufmt/attributes_bis.hh olena/oln/lrde/ufmt/attributes_bis.hh olena/oln/lrde/ufmt/attributes_bis.hh r) (olena/oln/lrde/ufmt/basic_najman.hh olena/oln/lrde/ufmt/basic_najman.hh olena/oln/lrde/ufmt/basic_najman.hh r) - (() () olena/oln/lrde/ufmt/fiorio-3.hh a) (() () olena/oln/lrde/ufmt/img/lena64nb.pgm a) - (() () olena/oln/lrde/ufmt/img/lena64.pbm a) - ) + (10.268 complete) ) (New-Merge-Parents)