October 2009 - Olena-patches

4631: Add spaces to conform to the LRDE coding norm.
by Yann Jacquelet 15 Oct '09

15 Oct '09

* green/mln/io/plot/save_image_sh.hh: Add spaces in #include. --- trunk/milena/sandbox/ChangeLog | 6 +++ .../sandbox/green/mln/io/plot/save_image_sh.hh | 46 ++++++++++---------- 2 files changed, 29 insertions(+), 23 deletions(-) diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index 1985f2f..2ab7bd8 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,3 +1,9 @@ +2009-10-14 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + + Add spaces to conform to the LRDE coding norm. + + * green/mln/io/plot/save_image_sh.hh: Add spaces in #include. + 2009-10-13 Yann Jacquelet <jacquelet(a)lrde.epita.fr> Fix bugs in kmean2d.hh and continue kmean demo in the red/green space. diff --git a/trunk/milena/sandbox/green/mln/io/plot/save_image_sh.hh b/trunk/milena/sandbox/green/mln/io/plot/save_image_sh.hh index 8d09971..849365a 100644 --- a/trunk/milena/sandbox/green/mln/io/plot/save_image_sh.hh +++ b/trunk/milena/sandbox/green/mln/io/plot/save_image_sh.hh @@ -26,7 +26,7 @@ // executable file might be covered by the GNU General Public License. #ifndef MLN_IO_PLOT_SAVE_IMAGE_SH_HH -#define MLN_IO_PLOT_SAVE_IMAGE_SH_HH +# define MLN_IO_PLOT_SAVE_IMAGE_SH_HH /// \file /// @@ -41,34 +41,34 @@ /// that's all. /// -#include <fstream> -#include <string> +# include <fstream> +# include <string> -#include <mln/trace/entering.hh> -#include <mln/trace/exiting.hh> +# include <mln/trace/entering.hh> +# include <mln/trace/exiting.hh> -#include <mln/core/macros.hh> -#include <mln/core/contract.hh> -#include <mln/core/image/image1d.hh> -#include <mln/core/image/image2d.hh> -#include <mln/core/image/image3d.hh> +# include <mln/core/macros.hh> +# include <mln/core/contract.hh> +# include <mln/core/image/image1d.hh> +# include <mln/core/image/image2d.hh> +# include <mln/core/image/image3d.hh> -#include <mln/geom/min_ind.hh> -#include <mln/geom/max_ind.hh> -#include <mln/geom/min_row.hh> -#include <mln/geom/max_row.hh> -#include <mln/geom/min_col.hh> -#include <mln/geom/max_col.hh> +# include <mln/geom/min_ind.hh> +# include <mln/geom/max_ind.hh> +# include <mln/geom/min_row.hh> +# include <mln/geom/max_row.hh> +# include <mln/geom/min_col.hh> +# include <mln/geom/max_col.hh> -#include <mln/trait/value_.hh> +# include <mln/trait/value_.hh> -#include <mln/value/int_u.hh> -#include <mln/value/int_s.hh> -#include <mln/value/rgb.hh> -#include <mln/value/hsl.hh> -#include <mln/value/hsi.hh> +# include <mln/value/int_u.hh> +# include <mln/value/int_s.hh> +# include <mln/value/rgb.hh> +# include <mln/value/hsl.hh> +# include <mln/value/hsi.hh> -#include <mln/util/array.hh> +# include <mln/util/array.hh> namespace mln -- 1.5.6.5

1 0

4625: Add kmean2d demo for theo, work in progress.
by Yann Jacquelet 08 Oct '09

08 Oct '09

* green/demo/clustering/kmean2d/Makefile.am: New makefile. * green/demo/clustering/kmean2d/kmean2d.cc: New demo code. * green/mln/clustering/kmean2d.hh: New library file. --- trunk/milena/sandbox/ChangeLog | 8 + .../green/demo/clustering/kmean2d/Makefile.am | 148 +++ .../green/demo/clustering/kmean2d/kmean2d.cc | 237 ++++ .../milena/sandbox/green/mln/clustering/kmean2d.hh | 1340 ++++++++++++++++++++ 4 files changed, 1733 insertions(+), 0 deletions(-) create mode 100644 trunk/milena/sandbox/green/demo/clustering/kmean2d/Makefile.am create mode 100644 trunk/milena/sandbox/green/demo/clustering/kmean2d/kmean2d.cc create mode 100644 trunk/milena/sandbox/green/mln/clustering/kmean2d.hh diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index f3f91d6..d7bce42 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,5 +1,13 @@ 2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Add kmean2d demo for theo, work in progress. + + * green/demo/clustering/kmean2d/Makefile.am: New makefile. + * green/demo/clustering/kmean2d/kmean2d.cc: New demo code. + * green/mln/clustering/kmean2d.hh: New library file. + +2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Fix LRDE norm fault in rgb8_to_rgn.hh * green/mln/fun/v2v/rg8_to_rgn.hh: Correct space location. diff --git a/trunk/milena/sandbox/green/demo/clustering/kmean2d/Makefile.am b/trunk/milena/sandbox/green/demo/clustering/kmean2d/Makefile.am new file mode 100644 index 0000000..91230b6 --- /dev/null +++ b/trunk/milena/sandbox/green/demo/clustering/kmean2d/Makefile.am @@ -0,0 +1,148 @@ +# +# Generic Makefile +# + +######### +# TOOLS # +######### + +INCLUDES= -I$(HOME)/svn/oln/trunk/milena/sandbox/green +CXXFLAGS= -ggdb -O0 -Wall -W -pedantic -ansi -pipe $(INCLUDES) +ECHO= echo +RM= rm +MKDIR= mkdir -p +CP= cp + +SOURCE_PATTERN= green/demo +BUILD__PATTERN= green/build/demo + + +ifeq ($(findstring $(BUILD__PATTERN),$(PWD)), $(BUILD__PATTERN)) +# Case where make is done from build directory. +SOURCE_DIR= $(subst $(BUILD__PATTERN),$(SOURCE_PATTERN),$(PWD)) +BUILD__DIR= $(PWD)/ +else +# Case where make is done from source directory. +SOURCE_DIR= $(PWD)/ +BUILD__DIR= $(subst $(SOURCE_PATTERN),$(BUILD__PATTERN),$(PWD)) +endif + +SRC= $(notdir $(wildcard $(SOURCE_DIR)/*.cc)) +OLD= $(notdir $(wildcard $(SOURCE_DIR)/*~)) +OBJ= $(patsubst %.cc,%.o,$(SRC)) +SOURCE_MAKEFILE=Makefile.am +BUILD__MAKEFILE=Makefile +TARGET_FILE= $(notdir $(PWD)) +SOURCE_FILES= $(notdir $(wildcard $(SOURCE_DIR)/*.*)) +BUILD__FILES= $(filter-out $(SRC) $(SOURCE_MAKEFILE), $(SOURCE_FILES)) + +BUILD__F_PATH= $(addprefix $(BUILD__DIR)/,$(BUILD__FILES)) +SOURCE_F_PATH= $(addprefix $(SOURCE_DIR)/,$(SOURCE_FILES)) + +BUILD__M_PATH= $(addprefix $(BUILD__DIR)/,$(BUILD__MAKEFILE)) +SOURCE_M_PATH= $(addprefix $(SOURCE_DIR)/,$(SOURCE_MAKEFILE)) + +TARGET_F_PATH= $(addprefix $(BUILD__DIR)/,$(TARGET_FILE)) +OBJ_F_PATH= $(addprefix $(BUILD__DIR)/,$(OBJ)) +SRC_F_PATH= $(addprefix $(SOURCE_DIR)/,$(SRC)) +OLD_F_PATH= $(addprefix $(SOURCE_DIR)/,$(OLD)) + +############# +# BOOTSTRAP # +############# + + +bootstrap: $(BUILD__DIR) $(BUILD__F_PATH) $(BUILD__M_PATH) + +# Create, if nessary, the destination directory +$(BUILD__DIR): + $(MKDIR) $(BUILD__DIR) + +# Copy, if nessary, all the files, except the Makefile.am +$(BUILD__F_PATH): $(SOURCE_F_PATH) + $(CP) $(addprefix $(SOURCE_DIR),$(@F)) $@ + +# Copy if nessary, the Makefile.am into Makefile +$(BUILD__M_PATH): $(SOURCE_M_PATH) + $(CP) $(SOURCE_M_PATH) $(BUILD__M_PATH) + + +####### +# ALL # +####### + +# We assume that the call is done from the build directory. +# With the directive vpath, hidden files are found in the source directory. + +all: $(TARGET_F_PATH) + + +$(TARGET_F_PATH): $(OBJ_F_PATH) + $(LINK.cc) $< $(LOADLIBES) $(LDLIBS) -o $@ + +$(OBJ_F_PATH):$(SRC_F_PATH) + $(COMPILE.cc) $(OUTPUT_OPTION) $< + + +######### +# CLEAN # +######### + +# Force every time the deletion +clean: clean_target clean_obj clean_dst clean_old #clean_make + + +clean_target: + -@$(RM) $(TARGET_F_PATH) &> /dev/null + +clean_obj: + -@$(RM) $(OBJ_F_PATH) &> /dev/null + +clean_dst: + -@$(RM) $(BUILD_F_PATH) &> /dev/null + +clean_make: + -@$(RM) $(BUILD_M_PATH) &> /dev/null + +clean_old: + -@$(RM) $(OLD_F_PATH) &> /dev/null + + +######### +# PRINT # +######### + +print: print_tools print_bootstrap + +print_tools: + @$(ECHO) "HOME = $(HOME)" + @$(ECHO) "INCLUDES = $(INCLUDES)" + @$(ECHO) "CXXFLAGS = $(CXXFLAGS)" + @$(ECHO) "ECHO = $(ECHO)" + @$(ECHO) "RM = $(RM)" + @$(ECHO) "MKDIR = $(MKDIR)" + @$(ECHO) "CP = $(CP)" + @$(ECHO) + +print_bootstrap: + @$(ECHO) "PWD = $(PWD)" + @$(ECHO) "SOURCE_PATTERN = $(SOURCE_PATTERN)" + @$(ECHO) "BUILD__PATTERN = $(BUILD__PATTERN)" + @$(ECHO) "SOURCE_DIR = $(SOURCE_DIR)" + @$(ECHO) "BUILD__DIR = $(BUILD__DIR)" + @$(ECHO) "SOURCE_MAKEFILE = $(SOURCE_MAKEFILE)" + @$(ECHO) "BUILD__MAKEFILE = $(BUILD__MAKEFILE)" + @$(ECHO) "TARGET_FILE = $(TARGET_FILE)" + @$(ECHO) "SOURCE_FILES = $(SOURCE_FILES)" + @$(ECHO) "SOURCE_F_PATH = $(SOURCE_F_PATH)" + @$(ECHO) "BUILD__FILES = $(BUILD__FILES)" + @$(ECHO) "BUILD__F_PATH = $(BUILD__F_PATH)" + @$(ECHO) "BUILD__M_PATH = $(BUILD__M_PATH)" + @$(ECHO) "SOURCE_M_PATH = $(SOURCE_M_PATH)" + @$(ECHO) "SRC = $(SRC)" + @$(ECHO) "OBJ = $(OBJ)" + @$(ECHO) "OLD = $(OLD)" + @$(ECHO) "SRC_F_PATH = $(SRC_F_PATH)" + @$(ECHO) "OBJ_F_PATH = $(OBJ_F_PATH)" + @$(ECHO) "OLD_F_PATH = $(OLD_F_PATH)" + @$(ECHO) diff --git a/trunk/milena/sandbox/green/demo/clustering/kmean2d/kmean2d.cc b/trunk/milena/sandbox/green/demo/clustering/kmean2d/kmean2d.cc new file mode 100644 index 0000000..ebb5981 --- /dev/null +++ b/trunk/milena/sandbox/green/demo/clustering/kmean2d/kmean2d.cc @@ -0,0 +1,237 @@ +// DEMO ON KMEAN2D + +#include <mln/clustering/kmean2d.hh> + +#include <iostream> +#include <sstream> + +#include <mln/img_path.hh> +#include <mln/pw/value.hh> + +#include <mln/value/int_u8.hh> +#include <mln/value/label_8.hh> +#include <mln/value/rgb8.hh> +#include <mln/value/value_array.hh> + +#include <mln/core/macros.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/image/dmorph/image_if.hh> + +#include <mln/data/transform.hh> +#include <mln/fun/v2v/rgb8_to_rgbn.hh> +#include <mln/fun/v2v/component.hh> + +#include <mln/io/ppm/load.hh> +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> +#include <mln/io/plot/save_image_sh.hh> + +#include <mln/value/rg.hh> +#include <mln/fun/v2v/rgb_to_rg.hh> +#include <mln/fun/v2v/rg_to_rgb.hh> + +#include <mln/accu/stat/histo2d.hh> +#include <mln/data/compute.hh> + + + +void do_demo(const std::string& image, + const unsigned k_center, + const unsigned n_times, + const unsigned watch_dog) +{ + typedef mln::clustering::kmean2d<double,8> t_kmean; + typedef mln::value::rg<8> t_rg8; + typedef mln::value::rgb8 t_rgb8; + typedef mln::value::int_u8 t_int_u8; + typedef mln::algebra::vec<2,t_int_u8> t_vec_rg8; + typedef mln::image2d<t_rgb8> t_image2d_rgb8; + typedef mln::image2d<t_int_u8> t_image2d_int_u8; + typedef mln::fun::v2v::component<t_rgb8, 0> t_comp_red; + typedef mln::fun::v2v::component<t_rgb8, 1> t_comp_green; + typedef mln::fun::v2v::component<t_rgb8, 2> t_comp_blue; + typedef mln::fun::v2v::rgb_to_rg<8> t_rgb_to_rg; + typedef mln::fun::v2v::rg_to_rgb<8> t_rg_to_rgb; + typedef mln::image2d<t_vec_rg8> t_image2d_vec_rg8; + typedef mln::image2d<t_rg8> t_image2d_rg8; + typedef mln::image2d<unsigned> t_histo2d; + + t_image2d_rgb8 house_rgb8; + t_image2d_int_u8 house_red; + t_image2d_int_u8 house_blue; + t_image2d_int_u8 house_green; + //t_image2d_vec_rg8 house_rg8; + t_image2d_rgb8 house_cast; + t_image2d_rg8 house_rg8; + t_histo2d house_histo; + + + mln::io::ppm::load(house_rgb8, image.c_str()); + house_red = mln::data::transform(house_rgb8, t_comp_red()); + house_green = mln::data::transform(house_rgb8, t_comp_green()); + house_blue = mln::data::transform(house_rgb8, t_comp_blue()); + + house_rg8 = mln::data::transform(house_rgb8, t_rgb_to_rg()); + house_histo = mln::data::compute(mln::accu::meta::stat::histo2d(), house_rg8); + + house_cast = mln::data::transform(house_rg8, t_rg_to_rgb()); + + t_kmean kmean(house_rg8, k_center, watch_dog, n_times); + + mln::io::pgm::save(house_red, "red.pgm"); + mln::io::pgm::save(house_green, "green.pgm"); + mln::io::pgm::save(house_blue, "blue.pgm"); + mln::io::ppm::save(house_cast, "red_green.ppm"); + mln::io::pgm::save(house_histo, "histo.pgm"); + mln::io::plot::save_image_sh(house_histo, "histo.sh"); + +/* + mln::io::plot::save_image_sh(mean_img, "mean.sh"); + mln::io::plot::save_image_sh(mean_cnv, "mean_cnv.sh"); + mln::io::plot::save_image_sh(variance_cnv, "variance_cnv.sh"); +*/ +} +/* +void do_demo(const std::string& image, + const unsigned k_center, + const unsigned n_times, + const unsigned watch_dog) +{ + typedef mln::clustering::kmean3d<double,5> t_kmean; + typedef mln::value::label_8 t_label_8; + typedef mln::value::rgb8 t_rgb8; + typedef mln::value::rgb<5> t_rgb5; + typedef mln::image2d<t_rgb8> t_image2d_rgb8; + typedef mln::image2d<t_rgb5> t_image2d_rgb5; + + t_image2d_rgb8 house_rgb8; + t_image2d_rgb5 house_rgb5; + + mln::io::ppm::load(house_rgb8, image.c_str()); + house_rgb5=mln::data::transform(house_rgb8,mln::fun::v2v::rgb8_to_rgbn<5>()); + + t_kmean kmean(house_rgb5, k_center, watch_dog, n_times); + + mln::trace::quiet = false; + + //kmean.launch_one_time(); + kmean.launch_n_times(); + + // Not safe because we don't test kmean.is_valid() + + t_kmean::t_color_dbg color_img = kmean.get_color_dbg(); + t_kmean::t_mean_dbg mean_img = kmean.get_mean_dbg(); + t_kmean::t_label_dbg label_img = kmean.get_label_dbg(); + t_kmean::t_variance_cnv variance_cnv = kmean.get_variance_cnv(); + t_kmean::t_mean_cnv mean_cnv = kmean.get_mean_cnv(); + + mln::io::ppm::save(mean_img, "mean.ppm"); + mln::io::ppm::save(color_img, "color.ppm"); + mln::io::pgm::save(label_img, "label.pgm"); + + mln::io::plot::save_image_sh(mean_img, "mean.sh"); + mln::io::plot::save_image_sh(mean_cnv, "mean_cnv.sh"); + mln::io::plot::save_image_sh(variance_cnv, "variance_cnv.sh"); +} +*/ +void demo(const std::string& image = OLENA_IMG_PATH"/house.ppm", + const unsigned k_center = 3, + const unsigned n_times = 10, + const unsigned watch_dog = 10) +{ + std::cout << "----------------------------------------" << std::endl; + std::cout << "Launching the demo with these parameters" << std::endl; + std::cout << "image : " << image << std::endl; + std::cout << "k_center : " << k_center << std::endl; + std::cout << "n_times : " << n_times << std::endl; + std::cout << "watch_dog : " << watch_dog << std::endl; + std::cout << "----------------------------------------" << std::endl; + + do_demo(image, k_center, n_times, watch_dog); +} + +void usage(const int argc, const char *args[]) +{ + std::cout << "----------------------------------------" << std::endl; + std::cout << "argc : " << argc << std::endl; + + for (int i = 0; i < argc; ++i) + std::cout << "args[" << i << "] : " << args[i] << std::endl; + + std::cout << "----------------------------------------" << std::endl; + std::cout << "usage: kmean1d [image [k_center [n_times [watch_dog]]]]" + << std::endl; + std::cout << "pbm image (points to work with)" << std::endl; + std::cout << "unsigned k_center (number of centers)" << std::endl; + std::cout << "unsigned n_times (number of launching)" << std::endl; + std::cout << "unsigned watch_dog (convergence loop)" << std::endl; + std::cout << "----------------------------------------" << std::endl; +} + +bool char_to_unsigned(const bool status, const char *arg, unsigned& val) +{ + bool result = false; + + if (status) + { + std::istringstream arg_stream(arg); + + arg_stream >> val; + + result = !arg_stream.fail(); + } + + return result; +} + +bool char_to_string(const bool status, const char *arg, std::string& val) +{ + bool result = false; + + if (status) + { + std::istringstream arg_stream(arg); + + arg_stream >> val; + + return !arg_stream.fail(); + } + + return result; +} + +int main(const int argc, const char *args[]) +{ + std::string image("top"); + unsigned k_center; + unsigned watch_dog; + unsigned n_times; + bool status = true; + + switch (argc) + { + case 5: status = char_to_unsigned(status, args[4], watch_dog); + case 4: status = char_to_unsigned(status, args[3], n_times); + case 3: status = char_to_unsigned(status, args[2], k_center); + case 2: status = char_to_string(status, args[1], image); break; + case 1: status = true; break; + default: status = false; + } + + if (status) + { + switch (argc) + { + case 1: demo(); break; + case 2: demo(image); break; + case 3: demo(image, k_center); break; + case 4: demo(image, k_center, n_times); break; + case 5: demo(image, k_center, n_times, watch_dog); break; + } + } + else + usage(argc, args); + + return 0; +} diff --git a/trunk/milena/sandbox/green/mln/clustering/kmean2d.hh b/trunk/milena/sandbox/green/mln/clustering/kmean2d.hh new file mode 100644 index 0000000..4ff2e6d --- /dev/null +++ b/trunk/milena/sandbox/green/mln/clustering/kmean2d.hh @@ -0,0 +1,1340 @@ +// Copyright (C) 2008,2009 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 MLN_CLUSTERING_KMEAN2D_HH +#define MLN_CLUSTERING_KMEAN2D_HH + +/// \file +/// +/// \brief Implements the optimized kmean algorithm. +/// +/// This algorithm is optimized in the way it proceeds directly with +/// the greylevel attribute inspite of the pixel attribute. The +/// algorithm is independant from the image dimension. But, we have to +/// compute one time the histogram. In fact, we move a recurrent cost +/// to a fix cost in the complexity. This version is very adapted to +/// images with small quantification. + +#include <limits.h> +#include <iostream> +#include <mln/trace/entering.hh> +#include <mln/trace/exiting.hh> + +#include <mln/core/contract.hh> +#include <mln/trait/value_.hh> +#include <mln/accu/stat/histo2d.hh> + +#include <mln/math/min.hh> +#include <mln/math/sqr.hh> +#include <mln/norm/l2.hh> + +#include <mln/core/image/image2d.hh> +#include <mln/core/concept/image.hh> +#include <mln/value/int_u.hh> +#include <mln/value/rgb8.hh> +#include <mln/value/rg.hh> +#include <mln/core/macros.hh> + +#include <mln/data/compute.hh> +#include <mln/debug/println.hh> +#include <mln/data/fill.hh> +#include <mln/literal/zero.hh> +#include <mln/literal/one.hh> +#include <mln/labeling/colorize.hh> +#include <mln/labeling/mean_values.hh> + +#include <mln/io/ppm/save.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/util/array.hh> +#include <mln/algebra/vec.hh> + +namespace mln +{ + + namespace clustering + { + + // Forward declaration. + template <typename T, unsigned n> + struct kmean2d; + + } // end of namespace mln::clustering + + namespace clustering + { + /// \brief Implements the kmean algorithm in a specific way. + /// + /// This version of the kmean algorithm uses a greyscale image as input, + /// temporary images for computations and produces images as result. Images + /// play the role of matrix or vector in standard statistic algoritm. + /// + /// T is the type used for computations (float or double). + /// n is the quantification for the image grayscale. + template <typename T, unsigned n> + struct kmean2d + { + /// Type definitions. + /// \brief A few type definitions to limit the refactoring impact. + ///{ + + typedef value::rgb<8> t_rgb; + typedef value::label<8> t_label; + typedef value::rg<n> t_value; + typedef mln_trait_value_comp(t_value,0) t_value_comp0; + typedef mln_trait_value_comp(t_value,1) t_value_comp1; + typedef T t_result1d; + typedef algebra::vec<2,T> t_result2d; + + /// FIXME t_point n'est pas forcément une image 2d, bien au contraire. + typedef image2d<t_value> t_point_img; + typedef image2d<unsigned> t_histo_img; + typedef util::array<t_result1d> t_number_img; + typedef util::array<t_result2d> t_mean_img; + typedef util::array<t_result1d> t_variance_img; + + typedef image2d<t_label> t_group_img; + typedef image2d<t_result1d> t_distance_val; + typedef util::array<t_distance_val> t_distance_img; + + typedef image2d<t_label> t_label_dbg; + typedef image2d<t_rgb> t_color_dbg; + typedef image2d<t_value> t_mean_dbg; + + typedef image1d<t_result2d> t_mean_val; + typedef util::array<t_mean_val> t_mean_set; + typedef util::array<t_mean_set> t_mean_cnv; + typedef image1d<t_result1d> t_variance_val; + typedef util::array<t_variance_val> t_variance_cnv; + + ///} + + //------------------------------------------------------------------------ + // Constructor + //------------------------------------------------------------------------ + + /// \brief Constructor + /// \param[in] point : the image as the population of pixels. + /// \param[in] k_center : the number of centers. + /// \param[in] watch_dog : the limit to observe the convergence (10). + /// \param[in] n_times : the number of times that we executed kmean(10). + + kmean2d(const t_point_img& point, + const unsigned k_center, + const unsigned watch_dog = 10, + const unsigned n_times = 10); + + //------------------------------------------------------------------------ + // Accessors + //------------------------------------------------------------------------ + + /// Mutator and accessors. + /// \{ + /// \brief Mutator and accessors are required for debugging and testing. + /// + /// Testing needs to hack the kmean loop process in order to verify each + /// step of the algorithm. + + void set_point(t_point_img& point); + void set_histo(t_histo_img& histo); + void set_number(t_number_img& number); + void set_mean(t_mean_img& mean); + void set_variance(t_variance_img& variance); + void set_group(t_group_img& group); + void set_distance(t_distance_img& distance); + + // Hacking outputs + t_point_img& get_point(); + t_histo_img& get_histo(); + t_number_img& get_number(); + t_mean_img& get_mean(); + t_variance_img& get_variance(); + t_group_img& get_group(); + t_distance_img& get_distance(); + + // Testing outputs + t_color_dbg& get_color_dbg(); + t_mean_dbg& get_mean_dbg(); + t_label_dbg& get_label_dbg(); + + t_mean_cnv& get_mean_cnv(); + t_variance_cnv& get_variance_cnv(); + + // Normal outputs + t_mean_img& to_result(); + + /// \} + + //------------------------------------------------------------------------ + // Printing temporary results + //------------------------------------------------------------------------ + + void print_mean(); + void print_number(); + void print_variance(); + void print_distance(); + void print_group(); + void print_point(); + void print_histo(); + + //------------------------------------------------------------------------ + // Initializations of centers + //------------------------------------------------------------------------ + + /// Initialization of centers. + /// \{ + /// \brief Two ways: Regular greylevel tick or random greylevel value or. + /// + /// There is two way to proceed the initialization. First of all, we + /// divide the greyscale in regular tick and we assigne them to the mean + /// of the centers. Finaly, we can ask random initialization along the + /// greyscale axis. The second process is needed to launch_n_times the + /// kmean and converge to the best descent. + + void init_mean(); + void init_mean_regular(); + void init_mean_random(); + + /// \} + + + //------------------------------------------------------------------------ + // Computations of distance, group, center, within variance + //------------------------------------------------------------------------ + + /// Computations of distance, group, center, within variance. + /// \{ + /// \brief Update the statistical information needed by the kmean process. + /// + /// The kmean process is a loop where distance from centers to pixels are + /// first compute. Then we assign the pixels to their nearest center. + /// The new location of each center can then update. Finaly, hommogeneity + /// in group is observed by the within variance. + + void update_distance(); + void update_group(); + void update_mean(); + void update_variance(); + + /// \} + + //------------------------------------------------------------------------ + // Main loop + //------------------------------------------------------------------------ + + /// kmean main loop + /// \{ + /// \brief User interface to launch the kmean process. + /// + /// There are two ways to launch the kmean process. The first one allow to + /// run it one time until convergence. As the process is a descent, it + /// depends on the initial center locations. The second call allow us to + /// rerun the process many times and to keep the best result (the one + /// with the smallest within variance). + + void launch_one_time(); + void launch_n_times(); + + /// \} + + //------------------------------------------------------------------------ + // Checking the validiy of the results + //------------------------------------------------------------------------ + + /// Checking the validity of the results. + /// \{ + /// \brief These methods help us to determine the validity of the results. + /// + /// After each launching the kmean process one time, we need to know if + /// the descent was successfull or not. The method is_valid_descent do it + /// for us. The method looks for a bad center (a class with no greylevel + /// associate to it) and a failure in the convergence. + + bool is_descent_valid(); + + /// \} + + //------------------------------------------------------------------------ + // Debugging tools + //------------------------------------------------------------------------ + + /// Debugging tools + /// \{ + /// \brief These methods help to interpret results. + /// + /// The methods build_label_dbg and build_all_dbg work in the input data + /// space. The first one build the 2d image of labels. The second call the + /// first one and then builds the colorize label' image and the mean + /// greylevel image. The update_cnv and finalize_cnv methods are used to + /// trace the convergence. They fill two images with the mean info and + /// the within variance info along the convergence and the tries. + + void build_label_dbg(); + void build_mean_dbg(); + void build_all_dbg(); + void update_cnv(); + void finalize_cnv(); + + /// \} + + + private: + /// Parameters. + /// \{ + /// \brief These parameters control the convergence of the process. + /// + /// The first parameter, k_center, defines the number of center for kmean. + /// In fact, watch_dog limit the number of iteration that a simple kmean + /// loop can do. If the process reaches the watch_dog limit, it means + /// that the process will not converge at all. The second parameter + /// n_times is the number of times we launch again and again the simple + /// kmean loop. As the kmean process is a descent, restarting the process + /// from different location will confort us in that we found a global + /// minima, not just a local one. + + unsigned _k_center; + unsigned _watch_dog; + unsigned _n_times; + + /// \} + + /// Convergence information. + /// \{ + /// \brief This information is used to follow the convergence. + /// + /// The within_variance is the homogeniety indicator for the + /// kmean process. The ideal situation is to find the center + /// with the minimum variance around them. The within variance + /// is just the sum of all variance around the centers. The + /// current_step variable allows us to remember the current + /// iteration in the kmean loop. This information is needed by + /// is_descent_valid routine which decide if convergence occurs + /// or not. The current_step info explicit where we are in the + /// kmean iteration. The last information, current_launching, + /// traces the progress while iterates kmean loop again and + /// again. The flag is_number_valid is set when a empty class + /// appears. This flag inhibit the process and force to restart + /// a try. + + t_result1d _within_variance; + unsigned _current_step; + unsigned _current_launching; + bool _is_number_valid; + + static const unsigned _N_TRIES = 3; + + /// \} + + /// Result of the kmean process. + /// \{ + /// \brief The center location are the major results of the kmean process. + /// + /// The kmean process result is composed by three information. The best + /// launching iteration, the best within variance obtained and the + /// location of the centers associated. + + unsigned _launching_min; + t_result1d _variance_min; + t_mean_img _mean_min; + + /// Inputs. + /// \{ + /// \brief The inputs are the distribution of the values and the values. + /// + /// The point image is a saving data for the real inputs. In fact, we use + /// the histogram information in the optimized kmean process. + + t_point_img _point; + t_histo_img _histo; + + ///\} + + /// Centers description. + /// \{ + /// \brief Centers are described by the first moment of their group. + /// + /// Centers are describe by their group attributes like the number of + /// pixels wich are relying on, the mass center of the group and the + /// homogeneity of the group. The variance is used as indicator for the + /// convergence. The number of pixels is used as integrity indicator. + /// A center with no point is a non sense. Theses informations are updated + /// after each kmean iteration. + + t_number_img _number; // k x 1 + t_mean_img _mean; // k x 1 + t_variance_img _variance; // k x 1 within group + + /// \} + + /// Greylevels description. + /// \{ + /// \brief The information are concerned with the greylevel input image. + /// + /// The group image allow us to decide which greylevel (and of course + /// which pixel) is assigned to a center. The distance image give us a + /// clue on how a greylevel could contribute to a center. The summation + /// over the greylevels of a center give us the within variance. + + t_group_img _group; // g x 1 because dim(t_value) = 1 + t_distance_img _distance; // label x graylevel + + /// \} + + /// Debugging, calibrating and testing results. + /// \{ + /// \brief Some exports information to control the results. + /// + /// We come back in the input space. Label is the image which associates + /// each pixel to its center. Color is the image which gives a random rgb + /// color to each label. We can then visualize the regions of the same + /// label (assigned to the same center) in the image. The mean image + /// associate the mean of each pixel center to each pixel. We obtain thus + /// a rebuilded image. + + t_label_dbg _label_dbg; + t_color_dbg _color_dbg; + t_mean_dbg _mean_dbg; + + /// \} + + /// Debugging, calibrating and testing convergence. + /// \{ + /// \brief Trace the variance and the center evolution. + /// + /// The mean_cnv image is a trace of the evolution of the mean' signal. + /// We can observe the variation of the mean of each center along the + /// kmean loop or along the different launch. The variance_cnv is a trace + /// of the within variance along the kmean loop or along the different + /// launch. + + t_mean_cnv _mean_cnv; + t_variance_cnv _variance_cnv; + + /// \} + }; + +#ifndef MLN_INCLUDE_ONLY + + //-------------------------------------------------------------------------- + // Constructor + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + kmean2d<T,n>::kmean2d(const t_point_img& point, + const unsigned k_center, + const unsigned watch_dog, + const unsigned n_times) + { + trace::entering("mln::clustering::kmean2d::kmean2d"); + mln_precondition(point.is_valid()); + + _k_center = k_center; + _watch_dog = watch_dog; + _n_times = n_times; + _point = point; + _histo = data::compute(accu::meta::stat::histo2d(),_point); + + // Results aren't valid since they aren't available + _is_number_valid = false; + _current_step = 0; + _current_launching = 0; + + for (unsigned i = 0; i < _k_center; ++i) + { + _number.append(literal::zero); + _mean.append(literal::zero); + _variance.append(literal::zero); + } + + _group.init_(box2d(point2d(mln_min(t_value_comp0), + mln_min(t_value_comp1)), + point2d(mln_max(t_value_comp0), + mln_max(t_value_comp1)))); + + for (unsigned i = 0; i < _k_center; ++i) + { + t_distance_val img(box2d(point2d(mln_min(t_value_comp0), + mln_min(t_value_comp1)), + point2d(mln_max(t_value_comp0), + mln_max(t_value_comp1)))); + + _distance.append(img); + } + + // Debugging, calibrating and testing + initialize(_label_dbg, _point); + initialize(_color_dbg, _point); + initialize(_mean_dbg, _point); + + // Observing the convergence + + for (unsigned i = 0; i < _n_times; ++i) + { + t_variance_val img(box1d(point1d(0), point1d(_watch_dog-1))); + + data::fill(img, literal::zero); + + _variance_cnv.append(img); + } + + for (unsigned i = 0; i < _k_center; ++i) + { + t_mean_set mean_set; + + for (unsigned j = 0; j < _n_times; ++j) + { + t_mean_val img(box1d(point1d(0), point1d(_watch_dog-1))); + + data::fill(img, literal::zero); + + mean_set.append(img); + } + + _mean_cnv.append(mean_set); + } + + trace::exiting("mln::clustering::kmean2d::kmean2d"); + } + + //-------------------------------------------------------------------------- + // Mutators and accessors + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_point(t_point_img& point) + { + trace::entering("mln::clustering::kmean2d::set_point"); + + _point = point; + + trace::exiting("mln::clustering::kmean2d::set_point"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_histo(t_histo_img& histo) + { + trace::entering("mln::clustering::kmean2d::set_histo"); + + _histo = histo; + + trace::exiting("mln::clustering::kmean2d::set_histo"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_number(t_number_img& number) + { + trace::entering("mln::clustering::kmean2d::set_number"); + + _number = number; + + trace::exiting("mln::clustering::kmean2d::set_number"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_mean(t_mean_img& mean) + { + trace::entering("mln::clustering::kmean2d::set_mean"); + + _mean = mean; + + trace::exiting("mln::clustering::kmean2d::set_mean"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_variance(t_variance_img& variance) + { + trace::entering("mln::clustering::kmean2d::set_variance"); + + _variance = variance; + + trace::exiting("mln::clustering::kmean2d::set_variance"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_group(t_group_img& group) + { + trace::entering("mln::clustering::kmean2d::set_group"); + + _group = group; + + trace::exiting("mln::clustering::kmean2d::set_group"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::set_distance(t_distance_img& distance) + { + trace::entering("mln::clustering::kmean2d::set_distance"); + + _distance = distance; + + trace::exiting("mln::clustering::kmean2d::set_distance"); + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_point_img& kmean2d<T,n>::get_point() + { + trace::entering("mln::clustering::kmean2d::get_point"); + + trace::exiting("mln::clustering::kmean2d::get_point"); + return _point; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_histo_img& kmean2d<T,n>::get_histo() + { + trace::entering("mln::clustering::kmean2d::get_histo"); + + trace::exiting("mln::clustering::kmean2d::get_histo"); + return _histo; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_number_img& kmean2d<T,n>::get_number() + { + trace::entering("mln::clustering::kmean2d::get_number"); + + trace::exiting("mln::clustering::kmean2d::get_number"); + return _number; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_mean_img& kmean2d<T,n>::get_mean() + { + trace::entering("mln::clustering::kmean2d::get_mean"); + + trace::exiting("mln::clustering::kmean2d::get_mean"); + return _mean; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_variance_img& kmean2d<T,n>::get_variance() + { + trace::entering("mln::clustering::kmean2d::get_variance"); + + trace::exiting("mln::clustering::kmean2d::get_variance"); + return _variance; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_group_img& kmean2d<T,n>::get_group() + { + trace::entering("mln::clustering::kmean2d::get_group"); + + trace::exiting("mln::clustering::kmean2d::get_group"); + return _group; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_distance_img& kmean2d<T,n>::get_distance() + { + trace::entering("mln::clustering::kmean2d::get_distance"); + + trace::exiting("mln::clustering::kmean2d::get_distance"); + return _distance; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_color_dbg& kmean2d<T,n>::get_color_dbg() + { + trace::entering("mln::clustering::kmean2d::get_color_dbg"); + + trace::exiting("mln::clustering::kmean2d::get_color_dbg"); + return _color_dbg; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_mean_dbg& kmean2d<T,n>::get_mean_dbg() + { + trace::entering("mln::clustering::kmean2d::get_mean_dbg"); + + trace::exiting("mln::clustering::kmean2d::get_mean_dbg"); + return _mean_dbg; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_label_dbg& kmean2d<T,n>::get_label_dbg() + { + trace::entering("mln::clustering::kmean2d::get_label_dbg"); + + trace::exiting("mln::clustering::kmean2d::get_label_dbg"); + return _label_dbg; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_mean_cnv& kmean2d<T,n>::get_mean_cnv() + { + trace::entering("mln::clustering::kmean2d::get_mean_cnv"); + + trace::exiting("mln::clustering::kmean2d::get_mean_cnv"); + return _mean_cnv; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_variance_cnv& kmean2d<T,n>::get_variance_cnv() + { + trace::entering("mln::clustering::kmean2d::get_variance_cnv"); + + trace::exiting("mln::clustering::kmean2d::get_variance_cnv"); + return _variance_cnv; + } + + template <typename T, unsigned n> + inline + typename kmean2d<T,n>::t_mean_img& kmean2d<T,n>::to_result() + { + trace::entering("mln::clustering::kmean2d::to_result"); + + trace::exiting("mln::clustering::kmean2d::to_result"); + return _mean_min; + } + + //-------------------------------------------------------------------------- + // Printing temporary results + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_mean() + { + trace::entering("mln::clustering::kmean2d::print_mean"); + + mln_eiter(t_mean_img) l(_mean); + + for_all(l) + { + std::cout << "mean(" << l.index_(); + std::cout << ") = [r=" << _mean[l.index_()][0]; + std::cout << ", g=" << _mean[l.index_()][1]; + std::cout << ", b=" << _mean[l.index_()][2]; + std::cout << "]" << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::print_mean"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_number() + { + trace::entering("mln::clustering::kmean2d::print_number"); + + mln_eiter(t_number_img) l(_number); + + for_all(l) + { + std::cout << "number(" << l.index_(); + std::cout << ") = " << _number[l.index_()]; + std::cout << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::print_number"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_variance() + { + trace::entering("mln::clustering::kmean2d::print_variance"); + + mln_eiter(t_variance_img) l(_number); + + for_all(l) + { + std::cout << "variance(" << l.index_(); + std::cout << ") = " << _variance[l.index_()]; + std::cout << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::print_variance"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_histo() + { + trace::entering("mln::clustering::kmean2d::print_histo"); + + mln_piter(t_histo_img) rgb(_histo.domain()); + + for_all(rgb) + { + if (0 < _histo(rgb)) + { + std::cout << "histo(r=" << rgb.row(); + std::cout << ", g=" << rgb.col(); + std::cout << ")= " << _histo(rgb); + std::cout << std::endl; + } + } + + trace::exiting("mln::clustering::kmean2d::print_histo"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_group() + { + trace::entering("mln::clustering::kmean2d::print_group"); + + mln_piter(t_group_img) rgb(_group.domain()); + + for_all(rgb) + { + if (0 < _histo(rgb)) + { + std::cout << "group(r=" << rgb.row(); + std::cout << ", g=" << rgb.col(); + std::cout << ")= " << _group(rgb); + std::cout << std::endl; + } + } + + trace::exiting("mln::clustering::kmean2d::print_group"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_distance() + { + trace::entering("mln::clustering::kmean2d::print_distance"); + + mln_eiter(t_distance_img) l(_distance); + + for_all(l) + { + mln_piter(t_distance_val) rgb(_distance[l.index_()].domain()); + + for_all(rgb) + { + if (0 < _histo(rgb)) + { + std::cout << "distance(l=" << l.index_(); + std::cout << ",r=" << rgb.row(); + std::cout << ", g=" << rgb.col(); + std::cout << ")= " << _distance[l.index_()](rgb); + std::cout << std::endl; + } + } + } + + trace::exiting("mln::clustering::kmean2d::print_distance"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::print_point() + { + trace::entering("mln::clustering::kmean2d::print_point"); + + mln_piter(t_point_img) p(_point.domain()); + + for_all(p) + { + std::cout << "point(r=" << p.row(); + std::cout << ", c=" << p.col(); + std::cout << ")= " << _point(p); + std::cout << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::print_point"); + } + + + + //-------------------------------------------------------------------------- + // Initialization of centers + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::init_mean_random() + { + trace::entering("mln::clustering::kmean2d::init_mean_random"); + + t_value_comp0 min_comp0 = mln_min(t_value_comp0); + t_value_comp0 max_comp0 = mln_max(t_value_comp0); + t_value_comp1 min_comp1 = mln_min(t_value_comp1); + t_value_comp1 max_comp1 = mln_max(t_value_comp1); + + mln_eiter(t_mean_img) l(_mean); + + for_all(l) + { + _mean[l.index_()][0] = (rand() % (max_comp0-min_comp0)) + min_comp0; + _mean[l.index_()][1] = (rand() % (max_comp1-min_comp1)) + min_comp1; + } + + trace::exiting("mln::clustering::kmean2d::init_mean_random"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::init_mean() + { + trace::entering("mln::clustering::kmean2d::init_mean"); + + init_mean_random(); + + trace::exiting("mln::clustering::kmean2d::init_mean"); + } + + //-------------------------------------------------------------------------- + // Computations of distance, group, center, within variance + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::update_distance() + { + trace::entering("mln::clustering::kmean2d::update_distance"); + + for (unsigned i = 0; i < _k_center; ++i) + { + mln_piter(t_distance_val) d(_distance[i].domain()); + + for_all(d) + { + // the square distance + t_result1d diff2_row = math::sqr(d.row() - _mean[i][0]); + t_result1d diff2_col = math::sqr(d.col() - _mean[i][1]); + t_result1d diff2_sli = math::sqr(d.sli() - _mean[i][2]); + _distance[i](d) = _histo(d)*(diff2_row + diff2_col + diff2_sli); + /* + std::cout << "row : " << d.row() << std::endl; + std::cout << "col : " << d.col() << std::endl; + std::cout << "histo : " << _histo(point1d(d.row())) << std::endl; + std::cout << "center : " << _mean(point1d(d.col())) << std::endl; + std::cout << "distance : " << _distance(d) << std::endl; + std::cout << "--------------------------------------" << std::endl; + */ + } + } + + trace::exiting("mln::clustering::kmean2d::update_distance"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::update_group() + { + trace::entering("mln::clustering::kmean2d::update_group"); + + mln_piter(t_group_img) rgb(_group.domain()); + + for_all(rgb) + { + mln_eiter(t_distance_img) l(_distance); + t_result1d min = mln_max(t_result1d); + t_label label = mln_max(t_label); + + //std::cout << "g = " << g << std::endl; + + for_all(l) + { + if (min > _distance[l.index_()](rgb)) + { + min = _distance[l.index_()](rgb); + label = l.index_(); + } + + //std::cout << "d" << l << " = " << + // _distance(point2d(g.ind(), l.ind())) << std::endl; + } + + //std::cout << "g = " << g << std::endl; + + _group(rgb) = label; + //std::cout << "group = " << _group(g) << std::endl; + //std::cout << "-----------" << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::update_group"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::update_mean() + { + trace::entering("mln::clustering::kmean2d::update_mean"); + + /// FIXME VERIFIER QUE L'ON PEUT OBTENIR UNE IMAGE EN NDG SIGNE + + // avec g le niveau de gris (signed or not signed) + // w[g] la classe de g sous forme d'image + // h[g] l'histogramme de l'image sous forme d'image + // + // Vg in [0..255] + // si w[g] = l + // c[l] += h(g) * g + // n[l] += h(g) + // + // c[l] /= n + + + mln_eiter(t_number_img) en(_number); + mln_eiter(t_mean_img) em(_mean); + + for_all_2(en,em) + { + _number[en.index_()] = literal::zero; + _mean[em.index_()] = literal::zero; + } + + mln_piter(t_group_img) rgb(_group.domain()); + + for_all(rgb) + { + // peut être faut-il le decomposer par composantes + _mean[_group(rgb)][0] += rgb.row() * _histo(rgb); + _mean[_group(rgb)][1] += rgb.col() * _histo(rgb); + _number(_group(rgb)) += _histo(rgb); + } + + mln_eiter(t_mean_img) l(_mean); + + /* + for_all(l) + { + std::cout << "c(" << l << ") = " << _mean(l) << std::endl; + std::cout << "n(" << l << ") = " << _number(l) << std::endl; + } + */ + for_all(l) + { + // State the stopping propagation Nan flag + _is_number_valid = (0 != _number[l.index_()]); + + // Emergency exit + if (!_is_number_valid) + break; + + // Compute the mean + _mean[l.index_()] /= _number[l.index_()]; + + // Debugging + //std::cout << "c" << l << " = " << _mean(l) << std::endl; + } + + trace::exiting("mln::clustering::kmean2d::update_mean"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::update_variance() + { + trace::entering("mln::clustering::kmean2d::update_variance"); + + _within_variance = literal::zero; + mln_eiter(t_variance_img) l(_variance); + + for_all(l) + { + _variance[l.index_()] = literal::zero; + + mln_piter(t_group_img) rgb(_group.domain()); + + for_all(rgb) + { + if (l.index_() == _group(rgb)) + _variance[l.index_()] += _distance[l.index_()](rgb); + } + + _within_variance += _variance[l.index_()]; + //std::cout << "v(" << l << ") = " << _variance(l) << std::endl; + } + + //std::cout << "result" << result << std::endl; + + trace::exiting("mln::clustering::kmean2d::update_variance"); + } + + //-------------------------------------------------------------------------- + // Debugging tools + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::build_label_dbg() + { + trace::entering("mln::clustering::kmean2d::build_label_dbg"); + + mln_piter(t_point_img) pi(_point.domain()); + mln_piter(t_label_dbg) po(_label_dbg.domain()); + + for_all_2(pi, po) + { + t_value val = _point(pi); + t_label grp = _group(point2d(val.red(), val.green())); + + // As label zero has got a particular semantic, the first label is one + _label_dbg(po) = ++grp; + } + + trace::exiting("mln::clustering::kmean2d::build_label_dbg"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::build_mean_dbg() + { + trace::entering("mln::clustering::kmean2d::build_mean_dbg"); + + mln_piter(t_mean_dbg) p(_mean_dbg.domain()); + + for_all(p) + { + _mean_dbg(p).red() = static_cast<unsigned>(_mean[_label_dbg(p)][0]); + _mean_dbg(p).green() = static_cast<unsigned>(_mean[_label_dbg(p)][1]); + _mean_dbg(p).blue() = static_cast<unsigned>(_mean[_label_dbg(p)][2]); + } + + trace::exiting("mln::clustering::kmean2d::build_mean_dbg"); + } + + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::build_all_dbg() + { + trace::entering("mln::clustering::kmean2d::build_all_dbg"); + build_label_dbg(); + //build_mean_dbg(); + _mean_dbg = labeling::mean_values(_point, _label_dbg, _k_center); + _color_dbg = labeling::colorize(value::rgb8(), _label_dbg); + + trace::exiting("mln::clustering::kmean2d::build_all_dbg"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::update_cnv() + { + trace::entering("mln::clustering::kmean2d::update_cnv"); + + _variance_cnv[_current_launching](point1d(_current_step)) + = _within_variance; + + mln_eiter(t_mean_img) l(_mean); + + for_all(l) + { + _mean_cnv[l.index_()][_current_launching](point1d(_current_step)) + = _mean[l.index_()]; + } + + trace::exiting("mln::clustering::kmean2d::update_cnv"); + } + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::finalize_cnv() + { + trace::entering("mln::clustering::kmean2d::finalize_cnv"); + + // saturate the curv with the within variance + for (unsigned i = _current_step; i < _watch_dog; ++i) + _variance_cnv[_current_launching](point1d(i)) = _within_variance; + + for (unsigned i = _current_step; i < _watch_dog; ++i) + { + mln_eiter(t_mean_img) l(_mean); + + for_all(l) + { + _mean_cnv[l.index_()][_current_launching](point1d(i)) + = _mean[l.index_()]; + } + } + + trace::exiting("mln::clustering::kmean2d::finalize_cnv"); + } + + + //-------------------------------------------------------------------------- + // Checking the validity of the results + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + bool kmean2d<T,n>::is_descent_valid() + { + trace::entering("mln::clustering::kmean2d::is_descent_valid"); + + bool result = _is_number_valid && (_current_step < _watch_dog); + + trace::exiting("mln::clustering::kmean2d::is_descent_valid"); + return result; + } + + + //-------------------------------------------------------------------------- + // Main loop + //-------------------------------------------------------------------------- + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::launch_one_time() + { + trace::entering("mln::clustering::kmean2d::launch_one_time"); + + //std::cout << "----------------------------------------" << std::endl; + + // Initialization to start the descent + t_result1d old_variance = mln_max(t_result1d); + _within_variance = mln_max(t_result1d); + _current_step = 0; + + // Build the first group and evaluate its caharacteristics + init_mean(); + update_distance(); + + //print_point(); + //print_histo(); + //print_mean(); + //print_distance(); + + //std::cout << "first_variance : " << old_variance << std::endl; + + // Execute the descent + do + { + old_variance = _within_variance; + + update_group(); + + //print_group(); + + update_mean(); // update _is_number_valid + + //print_mean(); + + // Stopping Nan propagation + if (!_is_number_valid) + break; + + update_distance(); + + //print_distance(); + + update_variance(); // update _within_variance + + //print_variance(); + + // Debugging code + update_cnv(); + + std::cout << "_current_step : " << _current_step << std::endl; + std::cout << "_within_variance : " << _within_variance << std::endl; + + ++_current_step; + } + while (_current_step < _watch_dog && _within_variance < old_variance); + + //std::cout << "----------------------------------------" << std::endl; + + finalize_cnv(); + //build_all_dbg(); + + trace::exiting("mln::clustering::kmean2d::launch_one_time"); + } + + + template <typename T, unsigned n> + inline + void kmean2d<T,n>::launch_n_times() + { + trace::entering("mln::clustering::kmean2d::launch_n_times"); + + //std::cout << "watch_dog : " << _watch_dog << std::endl; + //std::cout << "n_times : " << _n_times << std::endl; + + // number of times we reexecute launch_one_time without any success + unsigned tries = 0; + + _variance_min = mln_max(t_result1d); + _current_launching = 0; + + // Execute the descent n times + while (_current_launching < _n_times) + { + launch_one_time(); + + if (is_descent_valid() || _N_TRIES < tries) + { + if (_within_variance < _variance_min) + { + _variance_min = _within_variance; + _mean_min = _mean; + _launching_min = _current_launching; + } + + // Reinitialize the number of echecs possible + tries = 0; + + //std::cout << "_current_launching : " << _current_launching + // << std::endl; + + //std::cout << "within_variance[" << _current_launching << "] = " + // << _within_variance << std::endl; + + ++_current_launching; + } + else + ++tries; + } + + //Debugging code + build_all_dbg(); + + trace::exiting("mln::clustering::kmean2d::launch_n_times"); + } + +#endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::clustering + +} // end of namespace mln + +#endif // ! MLN_CLUSTERING_KMEAN2D_HH -- 1.5.6.5

1 0

4624: Fix LRDE norm fault in rgb8_to_rgn.hh
by Yann Jacquelet 08 Oct '09

08 Oct '09

* green/mln/fun/v2v/rg8_to_rgn.hh: Correct space location. --- trunk/milena/sandbox/ChangeLog | 7 +++++++ .../sandbox/green/mln/fun/v2v/rgb8_to_rgbn.hh | 20 ++++++++++---------- 2 files changed, 17 insertions(+), 10 deletions(-) diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index 8c48c64..f3f91d6 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,5 +1,12 @@ 2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Fix LRDE norm fault in rgb8_to_rgn.hh + + * green/mln/fun/v2v/rg8_to_rgn.hh: Correct space location. + + +2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Add a new (red,green) value type. * green/mln/value/rg.hh: New library file. diff --git a/trunk/milena/sandbox/green/mln/fun/v2v/rgb8_to_rgbn.hh b/trunk/milena/sandbox/green/mln/fun/v2v/rgb8_to_rgbn.hh index b40ca5b..2918b1a 100644 --- a/trunk/milena/sandbox/green/mln/fun/v2v/rgb8_to_rgbn.hh +++ b/trunk/milena/sandbox/green/mln/fun/v2v/rgb8_to_rgbn.hh @@ -25,12 +25,12 @@ // exception does not however invalidate any other reasons why the // executable file might be covered by the GNU General Public License. -#ifndef MLN_FUN_V2V_RGB8_TO_RGBN_HH -#define MLN_FUN_V2V_RGB8_TO_RGBN_HH +#ifndef MLN_FUN_V2V_RGB8_TO_RGBN_HH +# define MLN_FUN_V2V_RGB8_TO_RGBN_HH -#include <mln/value/rgb8.hh> -#include <mln/value/rgb.hh> -#include <mln/core/contract.hh> +# include <mln/value/rgb8.hh> +# include <mln/value/rgb.hh> +# include <mln/core/contract.hh> /// \file /// @@ -41,7 +41,7 @@ namespace mln namespace fun { - + namespace v2v { @@ -54,13 +54,13 @@ namespace mln { typedef value::rgb8 argument; typedef value::rgb<n> result; - + result operator()(const argument& c) const { mln_precondition(8 > n); unsigned size = pow(2,(8-n)); - /* + /* std::cout << "c : " << c << std::endl; std::cout << "red : " << c.red() << std::endl; std::cout << "size : " << size << std::endl; @@ -68,13 +68,13 @@ namespace mln std::cout << "max : " << (mln_max(mln::value::int_u<n>)) << std::endl; */ result res(c.red() / size, c.green() / size, c.blue() / size); - + return res; } }; } - + } } -- 1.5.6.5

1 0

4623: Add a new (red,green) value type.
by Yann Jacquelet 08 Oct '09

08 Oct '09

* green/mln/value/rg.hh: New library file. * green/mln/fun/v2v/rgb_to_rg.hh: New library file. * green/mln/fun/v2v/rg_to_rgb.hh: New library file. --- trunk/milena/sandbox/ChangeLog | 8 ++ .../milena/sandbox/green/mln/fun/v2v/rg_to_rgb.hh | 70 ++++++++++++ .../milena/sandbox/green/mln/fun/v2v/rgb_to_rg.hh | 70 ++++++++++++ trunk/milena/sandbox/green/mln/value/rg.hh | 116 ++++++++++++++++++++ 4 files changed, 264 insertions(+), 0 deletions(-) create mode 100644 trunk/milena/sandbox/green/mln/fun/v2v/rg_to_rgb.hh create mode 100644 trunk/milena/sandbox/green/mln/fun/v2v/rgb_to_rg.hh create mode 100644 trunk/milena/sandbox/green/mln/value/rg.hh diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index 9c03dec..8c48c64 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,5 +1,13 @@ 2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Add a new (red,green) value type. + + * green/mln/value/rg.hh: New library file. + * green/mln/fun/v2v/rgb_to_rg.hh: New library file. + * green/mln/fun/v2v/rg_to_rgb.hh: New library file. + +2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Add histogram accumulator which produce a 2d image result. * green/mln/accu/stat/histo2d.hh: New library file. diff --git a/trunk/milena/sandbox/green/mln/fun/v2v/rg_to_rgb.hh b/trunk/milena/sandbox/green/mln/fun/v2v/rg_to_rgb.hh new file mode 100644 index 0000000..ca7ba51 --- /dev/null +++ b/trunk/milena/sandbox/green/mln/fun/v2v/rg_to_rgb.hh @@ -0,0 +1,70 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009 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 MLN_FUN_V2V_RG_TO_RGB_HH +# define MLN_FUN_V2V_RG_TO_RGB_HH + +# include <mln/value/rgb.hh> +# include <mln/value/rg.hh> +# include <mln/core/contract.hh> + +/// \file +/// +/// \brief Convert rg value to rgb + +namespace mln +{ + + namespace fun + { + + namespace v2v + { + + /// \brief Convert rg value to rgb. + /// + /// \ingroup modfunv2v + + template <unsigned n> + struct rg_to_rgb : Function_v2v< rg_to_rgb<n> > + { + typedef value::rg<n> argument; + typedef value::rgb<n> result; + + result operator()(const argument& v) const + { + return value::rgb<n>(v.red(), v.green(), 127); + } + }; + + } // end of namespace mln::fun::v2v + + } // end of namespace mln::fun + +} // end of namespace mln + +#endif // ! MLN_FUN_V2V_RG_TO_RGB_HH diff --git a/trunk/milena/sandbox/green/mln/fun/v2v/rgb_to_rg.hh b/trunk/milena/sandbox/green/mln/fun/v2v/rgb_to_rg.hh new file mode 100644 index 0000000..f5163ad --- /dev/null +++ b/trunk/milena/sandbox/green/mln/fun/v2v/rgb_to_rg.hh @@ -0,0 +1,70 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009 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 MLN_FUN_V2V_RGB_TO_RG_HH +# define MLN_FUN_V2V_RGB_TO_RG_HH + +# include <mln/value/rgb.hh> +# include <mln/value/rg.hh> +# include <mln/core/contract.hh> + +/// \file +/// +/// \brief Convert rgb value to rg + +namespace mln +{ + + namespace fun + { + + namespace v2v + { + + /// \brief Convert rgb value to rg. + /// + /// \ingroup modfunv2v + + template <unsigned n> + struct rgb_to_rg : Function_v2v< rgb_to_rg<n> > + { + typedef value::rgb<n> argument; + typedef value::rg<n> result; + + result operator()(const argument& v) const + { + return value::rg<n>(v); + } + }; + + } // end of namespace mln::fun::v2v + + } // end of namespace mln::fun + +} // end of namespace mln + +#endif // ! MLN_FUN_V2V_RGB_TO_RG_HH diff --git a/trunk/milena/sandbox/green/mln/value/rg.hh b/trunk/milena/sandbox/green/mln/value/rg.hh new file mode 100644 index 0000000..f7205fc --- /dev/null +++ b/trunk/milena/sandbox/green/mln/value/rg.hh @@ -0,0 +1,116 @@ +// Copyright (C) 2007, 2008, 2009 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 MLN_VALUE_RG_HH +# define MLN_VALUE_RG_HH + + +#include <mln/value/concept/vectorial.hh> +# include <mln/value/int_u.hh> + +#include <mln/trait/value_.hh> +# include <mln/algebra/vec.hh> + +namespace mln +{ + + namespace value + { + + // Forward declaration. + template <unsigned n> struct rg; + + } // end of namespace mln::value + + namespace trait + { + + template <unsigned n> + struct value_< mln::value::rg<n> > + { + enum { + dim = 2, + nbits = dim * n, + card = mln_value_card_from_(nbits) + }; + + typedef trait::value::nature::vectorial nature; + typedef trait::value::kind::color kind; + typedef trait::value::quant::high quant; + + typedef void comp; + typedef mln::value::int_u<n> comp_0; + typedef mln::value::int_u<n> comp_1; + + static comp_0 get_comp_0(const mln::value::rg<n>& v){return v.red(); } + static comp_1 get_comp_1(const mln::value::rg<n>& v){return v.green();} + + typedef algebra::vec<dim, float> sum; + + static const char* name() + { + static std::string s = std::string("rg").append(1, 8 + '0'); + return s.c_str(); + } + }; + + } // end of namespace mln::trait + + namespace value + { + template <unsigned n> + struct rg :public mln::value::Vectorial< rg<n> >, + public internal::value_like_< + algebra::vec< 2, int_u<n> >, // Equivalent. + algebra::vec< 2, int_u<n> >, // Encoding. + algebra::vec< 2, int >, // Interoperation. + rg<n> > // Exact. + { + typedef int_u<n> t_red; + typedef int_u<n> t_green; + + int_u<n> red() const {return this->v_[0];} + int_u<n>& red() {return this->v_[0];} + int_u<n> green() const {return this->v_[1];} + int_u<n>& green() {return this->v_[1];} + + rg(){} + rg(const rgb8& val){this->v_[0] = val.red(); this->v_[1] = val.green();} + + rg operator=(const rg& rhs) + { + if (&rhs != this) + this->v_ = rhs.v_; + + return *this; + } + }; + + } // end of namespace mln::value + +} // end of namespace mln + +#endif // ! MLN_VALUE_RG_HH -- 1.5.6.5

1 0

4622: Add histogram accumulator which produce a 2d image result.
by Yann Jacquelet 08 Oct '09

08 Oct '09

* green/mln/accu/stat/histo2d.hh: New library file. --- trunk/milena/sandbox/ChangeLog | 7 + .../milena/sandbox/green/mln/accu/stat/histo2d.hh | 346 ++++++++++++++++++++ 2 files changed, 353 insertions(+), 0 deletions(-) create mode 100644 trunk/milena/sandbox/green/mln/accu/stat/histo2d.hh diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index 1d68213..9c03dec 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,5 +1,12 @@ 2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Add histogram accumulator which produce a 2d image result. + + * green/mln/accu/stat/histo2d.hh: New library file. + + +2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + Correct bad behaviour in kmean3d (see usage of zero label). * green/mln/clustering/kmean3d.hh diff --git a/trunk/milena/sandbox/green/mln/accu/stat/histo2d.hh b/trunk/milena/sandbox/green/mln/accu/stat/histo2d.hh new file mode 100644 index 0000000..fbe9a42 --- /dev/null +++ b/trunk/milena/sandbox/green/mln/accu/stat/histo2d.hh @@ -0,0 +1,346 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009 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 MLN_ACCU_STAT_HISTO2D_HH +# define MLN_ACCU_STAT_HISTO2D_HH + +/// \file +/// +/// \brief Define a histogram as an accumulator which returns an image1d . +/// +/// This source implements the discrete histogram version. The number of beans +/// is infer from the number of greylevels. A typical rgb8 image has got +/// 256x3 bins. Working with a 8 bit quantification in rgb is very costly. +/// The following sample is a typical use of the histogram. +/// +/// #include <mln/value/rgb.hh> +/// #include <mln/core/image/image1d.hh> +/// #include <mln/core/image/image3d.hh> +/// #include <mln/io/ppm/load.hh> +/// #include <mln/accu/stat/histo3d_rgb.hh> +/// #include <mln/data/compute.hh> +/// +/// #define OLENA_LENA ""/usr/local/share/olena/images/lena.ppm" +/// +/// void test() +/// { +/// typedef mln::value::rgb<7> rgb7; +/// mln::image2d<rgb7> img_ref; +/// mln::image3d<unsigned> img_res; +/// +/// mln::io::ppm::load(img_ref, OLENA_LENA); +/// img_res=mln::data::compute(mln::accu::meta::stat::histo3d_rgb(),img_ref); +/// } + + +# include <iostream> + +# include <mln/accu/internal/base.hh> + +# include <mln/core/macros.hh> +# include <mln/core/image/image2d.hh> +# include <mln/core/alias/point2d.hh> +# include <mln/core/alias/box2d.hh> + +# include <mln/trait/value/comp.hh> + +# include <mln/arith/plus.hh> + +# include <mln/trace/entering.hh> +# include <mln/trace/exiting.hh> + +# include <mln/value/ops.hh> + +namespace mln +{ + + namespace accu + { + + namespace stat + { + + // Forward declaration + template <typename V> + struct histo2d; + + } // end of namespace mln::accu::stat + + namespace meta + { + + namespace stat + { + + struct histo2d : public Meta_Accumulator<histo2d> + { + template <typename V> + struct with + { + typedef accu::stat::histo2d<V> ret; + }; + }; + + } // end of namespace mln::accu::meta::stat + + } // end of namespace mln::accu::meta + + } // end of namespace mln::accu + + + namespace trait + { + + template <typename V> + struct accumulator_< mln::accu::stat::histo2d<V> > + { + typedef accumulator::has_untake::no has_untake; + typedef accumulator::has_set_value::no has_set_value; + typedef accumulator::has_stop::no has_stop; + typedef accumulator::when_pix::use_v when_pix; + }; + + template <typename V> + struct set_precise_binary_<op::eq, + accu::stat::histo2d<V>, + accu::stat::histo2d<V> > + { + typedef bool ret; + }; + + } // end of namespace mln::trait + + namespace accu + { + + namespace stat + { + + /// \brief Define an histogram which returns an image3d . + /// + /// Param V defines the space in which we count the values. + /// For instance, this histogram works image2d<rgb<2>> or + /// image2d<rgb<7>>. The histogram count the occurrence of each value. + /// The number of bins depends of the grayscale values, for 8 bits there + /// is 256x3 bins. Note that over + /// quantification works too. + /// + /// \ingroup modaccuvalues + + template <typename V> + struct histo2d : + public mln::accu::internal::base<image2d<unsigned>, histo2d<V> > + { + typedef V argument; + typedef image2d<unsigned> result; + typedef result q_result; + + /// Constructors + /// \{ + /// \brief Initialize the size of the resulting image1d. + /// + /// Initialize the size the resulting image from the theorical dynamic + /// of the greylevel values (Use V to manage it). + histo2d(); + /// \} + + + /// Manipulators. + /// \{ + /// \brief Initialize the histogram with zero value. + /// + /// This method must be called just before starting the use of the + /// histogram. If it's not, resulting values won't converge to the + /// density. + void init(); + + + /// \brief Update the histogram with the RGB pixel t. + /// \param[in] t a greylevel pixel of type V. + /// + /// The end user shouldn't call this method. In place of it, he can + /// go through the data compute interface. + void take(const argument& t); + + + /// \brief Update the histogram with an other histogram. + /// \param[in] other the other histogram. + void take(const histo2d<V>& other); + /// \} + + /// Accessors. + /// \{ + /// \brief Return the histogram as an image1d. + /// + /// This is the machinery to communicate with data compute interface. + /// The end user should'nt use it. + result to_result() const; + operator result () const; + /// \} + + /// \brief Check whethever this accumulator is able to return a result. + /// + /// Depends if the resulting image1d is valid. We can assume it is quite + /// always the case. + bool is_valid() const; + + protected: + result count_; + }; + + /// \brief Check wethever an histogram is equal to an other one. + /// \param[in] histo1 the first histogram to compare with. + /// \param[in] histo2 the second histogram. + /// + /// The operator compare all the bins from the two histogram. + + template <typename V> + bool operator==(const histo2d<V>& histo1, + const histo2d<V>& histo2); + +#ifndef MLN_INCLUDE_ONLY + + template <typename V> + inline + histo2d<V>::histo2d() + { + trace::entering("mln::accu::stat::histo2d::histo2d"); + typedef mln_trait_value_comp(V,0) comp0; + typedef mln_trait_value_comp(V,1) comp1; + + // comp keep a trace of the dimension of the theorical image. + // mln_min(comp) --> 0 + // mln_max(comp) --> 2^(n-1) [127 for n=7][255 for n=8] ... + + count_.init_(box2d(point2d(mln_min(comp0), + mln_min(comp1)), + point2d(mln_max(comp0), + mln_max(comp1)))); + + trace::exiting("mln::accu::stat::histo2d::histo2d"); + } + + template <typename V> + inline + void histo2d<V>::init() + { + trace::entering("mln::accu::stat::histo2d::init"); + + data::fill(count_, 0); + trace::exiting("mln::accu::stat::histo2d::init"); + } + + template <typename V> + inline + void histo2d<V>::take(const argument& t) + { + trace::entering("mln::accu::stat::histo2d::take"); + + // Just convert a greyscale value (int_u8 like) to a position for an + // iterator on the resulting image. + // Take care to the constructor : Point(slice, row, column) + ++count_(point2d(t.red(), t.green())); + + trace::exiting("mln::accu::stat::histo2d::take"); + } + + + template <typename V> + inline + void histo2d<V>::take(const histo2d<V>& other) + { + trace::entering("mln::accu::stat::histo2d::take"); + + count_ += other.count_; + + trace::exiting("mln::accu::stat::histo2d::take"); + } + + template <typename V> + inline + typename histo2d<V>::result histo2d<V>::to_result() const + { + trace::entering("mln::accu::stat::histo2d::to_result"); + + trace::exiting("mln::accu::stat::histo2d::to_result"); + return count_; + } + + template <typename V> + inline + histo2d<V>::operator result() const + { + trace::entering("mln::accu::stat::histo2d::operator result"); + + trace::exiting("mln::accu::stat::histo2d::operator result"); + return count_; + } + + template <typename V> + inline + bool histo2d<V>::is_valid() const + { + trace::entering("mln::accu::stat::histo2d::is_valid"); + bool result = count_.is_valid(); + + trace::exiting("mln::accu::stat::histo2d::is_valid"); + return result; + } + + template <typename V> + bool operator==(const histo2d<V>& histo1, + const histo2d<V>& histo2) + { + trace::entering("mln::accu::stat::operator=="); + + bool result = true; + const image2d<unsigned>& res1 = histo1.to_result(); + const image2d<unsigned>& res2 = histo2.to_result(); + + mln_precondition(res1.is_valid()); + mln_precondition(res2.is_valid()); + + mln_piter(image2d<unsigned>) p1(res1.domain()); + mln_piter(image2d<unsigned>) p2(res2.domain()); + + for_all_2(p1, p2) + result &= (res1(p1) == res2(p2)); + + trace::exiting("mln::accu::stat::operator=="); + return result; + } + +#endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::accu::stat + + } // end of namespace mln::accu + +} // end of namespace mln + +#endif // ! MLN_ACCU_STAT_HISTO2D_HH -- 1.5.6.5

1 0

4621: Correct bad behaviour in kmean3d (see usage of zero label).
by Yann Jacquelet 08 Oct '09

08 Oct '09

* green/mln/clustering/kmean3d.hh (build_all_dbg, build_mean_dbg): Fix bad behaviour. --- trunk/milena/sandbox/ChangeLog | 9 +++++++++ .../milena/sandbox/green/mln/clustering/kmean3d.hh | 8 +++++--- 2 files changed, 14 insertions(+), 3 deletions(-) diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index ee9ccee..1d68213 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,3 +1,11 @@ +2009-10-08 Yann Jacquelet <jacquelet(a)lrde.epita.fr> + + Correct bad behaviour in kmean3d (see usage of zero label). + + * green/mln/clustering/kmean3d.hh + (build_all_dbg, build_mean_dbg): Fix bad behaviour. + + 2009-10-07 Edwin Carlinet <carlinet(a)lrde.epita.fr> Alternate representation of tree (some tries...). @@ -54,6 +62,7 @@ * edwin/mln/util/ctree/node.hh: Materials for the new tree representation. + 2009-10-07 Yann Jacquelet <jacquelet(a)lrde.epita.fr> Update the demo for debugging purpose. diff --git a/trunk/milena/sandbox/green/mln/clustering/kmean3d.hh b/trunk/milena/sandbox/green/mln/clustering/kmean3d.hh index 81b4f37..6aebefc 100644 --- a/trunk/milena/sandbox/green/mln/clustering/kmean3d.hh +++ b/trunk/milena/sandbox/green/mln/clustering/kmean3d.hh @@ -60,6 +60,7 @@ #include <mln/debug/println.hh> #include <mln/data/fill.hh> #include <mln/literal/zero.hh> +#include <mln/literal/one.hh> #include <mln/labeling/colorize.hh> #include <mln/labeling/mean_values.hh> @@ -1117,7 +1118,8 @@ namespace mln t_value val = _point(pi); t_label grp = _group(point3d(val.blue(), val.red(), val.green())); - _label_dbg(po) = grp; + // As label zero has got a particular semantic, the first label is one + _label_dbg(po) = ++grp; } trace::exiting("mln::clustering::kmean3d::build_label_dbg"); @@ -1148,8 +1150,8 @@ namespace mln { trace::entering("mln::clustering::kmean3d::build_all_dbg"); build_label_dbg(); - build_mean_dbg(); - //_mean_dbg = labeling::mean_values(_point, _label_dbg, _k_center); + //build_mean_dbg(); + _mean_dbg = labeling::mean_values(_point, _label_dbg, _k_center); _color_dbg = labeling::colorize(value::rgb8(), _label_dbg); trace::exiting("mln::clustering::kmean3d::build_all_dbg"); -- 1.5.6.5

1 0

r4620: Alternate representation of tree (some tries...)
by Edwin Carlinet 07 Oct '09

07 Oct '09

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-10-07 Edwin Carlinet <carlinet(a)lrde.epita.fr> Alternate representation of tree (some tries...). * edwin/exec/benchmark/Makefile, * edwin/exec/benchmark/newv.cc, * edwin/exec/benchmark/oldv.cc, * edwin/exec/benchmark: Applications, and comparaisons between the old and new version. * edwin/mln/core, * edwin/mln/core/concept/dindex_site.hh, * edwin/mln/core/concept/index_site.hh, * edwin/mln/core/dindex_site.hh, * edwin/mln/core/internal/index_site_base.hh, * edwin/mln/core/internal, * edwin/mln/core/site_set/p_run_idx.hh, * edwin/mln/core/site_set/p_run_idx_piter.hh, * edwin/mln/core/site_set: Temporary type for index site (used by the node type), its site set and its iterators. * edwin/mln/core/concept/tree.hh, * edwin/mln/core/concept: Tree concept. * edwin/mln/core/image, * edwin/mln/core/image/attribute_image.hh: Attribute image type. * edwin/mln/debug, * edwin/mln/debug/ctree.hh: Debug tools with println overloads. * edwin/mln/morpho/tree/component_tree.hh: Shortcuts for building min and max tree. * edwin/mln/morpho/tree/compute_attribute_image.hh: Compute an attribute using the new tree representation. * edwin/mln/morpho/tree/impl, * edwin/mln/morpho/tree/impl/union_find.hh: (Simple) tree computation based on union-find method. * edwin/mln/morpho/tree/propagate_node.hh: Temporary methods for fast propagation. Will be useless as soon as the subdomain morpher will be specialized. * edwin/mln/util, * edwin/mln/util/ctree, * edwin/mln/util/ctree/ctree.hh, * edwin/mln/util/ctree/internal, * edwin/mln/util/ctree/internal/tree_base.hh, * edwin/mln/util/ctree/node.hh: Materials for the new tree representation. --- exec/benchmark/Makefile | 21 + exec/benchmark/newv.cc | 86 ++++ exec/benchmark/oldv.cc | 82 ++++ mln/core/concept/dindex_site.hh | 253 ++++++++++++ mln/core/concept/index_site.hh | 311 +++++++++++++++ mln/core/concept/tree.hh | 148 +++++++ mln/core/dindex_site.hh | 119 +++++ mln/core/image/attribute_image.hh | 435 +++++++++++++++++++++ mln/core/internal/index_site_base.hh | 254 ++++++++++++ mln/core/site_set/p_run_idx.hh | 458 ++++++++++++++++++++++ mln/core/site_set/p_run_idx_piter.hh | 222 ++++++++++ mln/debug/ctree.hh | 155 +++++++ mln/morpho/tree/component_tree.hh | 124 ++++++ mln/morpho/tree/compute_attribute_image.hh | 178 ++++++++ mln/morpho/tree/impl/dual_hqueue.hh | 408 ++++++++++++++++++++ mln/morpho/tree/impl/dual_union_find.hh | 361 +++++++++++++++++ mln/morpho/tree/impl/union_find.hh | 172 ++++++++ mln/morpho/tree/propagate_node.hh | 112 +++++ mln/util/ctree/ctree.hh | 589 +++++++++++++++++++++++++++++ mln/util/ctree/internal/tree_base.hh | 140 ++++++ mln/util/ctree/node.hh | 183 +++++++++ 21 files changed, 4811 insertions(+) Index: trunk/milena/sandbox/edwin/exec/benchmark/newv.cc =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/newv.cc (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/newv.cc (revision 4620) @@ -0,0 +1,86 @@ +#include <mln/core/image/image2d.hh> +#include <mln/core/image/attribute_image.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/util/ctree/ctree.hh> + +#include <mln/morpho/tree/component_tree.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/tree/filter/min.hh> +#include <mln/morpho/attribute/volume.hh> +#include <mln/morpho/attribute/card.hh> + + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/pw/all.hh> +#include <mln/core/var.hh> + +#include <mln/util/timer.hh> +#include <iostream> + +#include <mln/debug/ctree.hh> +#include <mln/debug/println.hh> + +void usage(char** argv) +{ + std::cout << "Usage: " << argv[0] << " image lambda [new.pgm]" + << std::endl; + abort(); +} + +static mln::util::timer tm; + +void bench(const char* msg) +{ + std::cout << msg << " in " << tm << " s" << std::endl; + tm.restart(); +} + +int main(int argc, char** argv) +{ + using namespace mln; + using value::int_u8; + + if (argc < 3) + usage(argv); + + const char* finput = argv[1]; + const unsigned lambda = atoi(argv[2]); + const char* foutput = (argc > 3) ? argv[3] : "new.pgm"; + + tm.start(); + + + typedef image2d<int_u8> I; + I input; + io::pgm::load(input, finput); + bench("Image Loadin"); + + // Tree Computation + typedef util::ctree::ctree tree_t; + tree_t tree = morpho::tree::max_tree(input, c4()); + bench("Tree construction"); + + // Compute Attribute + typedef attribute_image<tree_t, unsigned> A; + morpho::attribute::volume attribute; + A attr_img = morpho::tree::compute_attribute_image(tree, attribute); + bench("Attribute Computation (volume)"); + + // Filtering + attribute_image<tree_t, int_u8> out = tree.to_image(); + mln_VAR(predicate, pw::value(attr_img) > pw::cst(lambda)); + morpho::tree::filter::min(out, predicate); + bench("Filtering"); + + // Converting + I output; + convert::over_load::from_to_(out, output); // FIXME ! + bench("Restore"); + + io::pgm::save(output, foutput); + bench("Image Savin"); +} Index: trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc (revision 4620) @@ -0,0 +1,82 @@ +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/component_tree.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/tree/propagate_representative.hh> +#include <mln/morpho/tree/filter/min.hh> +#include <mln/morpho/attribute/volume.hh> +#include <mln/morpho/attribute/card.hh> + +#include <mln/pw/all.hh> +#include <mln/core/var.hh> + +#include <mln/debug/println.hh> +#include <mln/util/timer.hh> +#include <iostream> + +void usage(char** argv) +{ + std::cout << "Usage: " << argv[0] << " image lambda [old.pgm]" + << std::endl; + abort(); +} + +static mln::util::timer tm; + +void bench(const char* msg) +{ + std::cout << msg << " in " << tm << " s" << std::endl; + tm.restart(); +} + +int main(int argc, char** argv) +{ + using namespace mln; + using value::int_u8; + + if (argc < 3) + usage(argv); + + const char* finput = argv[1]; + const unsigned lambda = atoi(argv[2]); + const char* foutput = (argc > 3) ? argv[3] : "old.pgm"; + + tm.start(); + + + typedef image2d<int_u8> I; + I input; + io::pgm::load(input, finput); + bench("Image Loadin"); + + // Tree Computation + typedef morpho::tree::data<I, p_array<mln_psite_(I)> > tree_t; + tree_t tree = morpho::tree::max_tree(input, c4()); + bench("Tree construction"); + + // Compute Attribute + typedef mln_ch_value_(I, unsigned) A; + morpho::attribute::volume attribute; + A attr_img = morpho::tree::compute_attribute_image(attribute, tree); + bench("Attribute Computation (volume)"); + + // Filtering + I out = duplicate(input); + mln_VAR(predicate, pw::value(attr_img) > pw::cst(lambda)); + morpho::tree::filter::min(tree, out, predicate); + bench("Filtering"); + + // Restore + morpho::tree::propagate_representative(tree, out); + bench("Restore"); + + io::pgm::save(out, foutput); + bench("Image Savin"); +} Index: trunk/milena/sandbox/edwin/exec/benchmark/Makefile =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/Makefile (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/Makefile (revision 4620) @@ -0,0 +1,21 @@ +-include makefile.rules + +MLN_DIR = ~/olena/trunk/milena +CXXFLAGS += -W -Wall +CXXFLAGS += $(if $(DEBUG), -g -ggdb, -DNDEBUG $(if $(RELEASE), -O3, -O1)) +MY_CXXFLAGS := $(CXXFLAGS) -I $(MLN_DIR)/sandbox/edwin -I $(MLN_DIR) +CXXFLAGS += -I $(MLN_DIR) +CC = g++ +LDFLAGS = + +all: oldv newv + +newv.o: newv.cc + $(CXX) $(MY_CXXFLAGS) -c $< + +clean: + rm -f *.o + +newv: newv.o + +oldv: oldv.o Index: trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh (revision 4620) @@ -0,0 +1,124 @@ +// Copyright (C) 2008, 2009 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. + + +/// \file +/// +/// Compute a canonized (parenthood) component tree from an image. + + +#ifndef MLN_MORPHO_TREE_COMPONENT_TREE_HH +# define MLN_MORPHO_TREE_COMPONENT_TREE_HH + +# include <mln/tag/tree.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/morpho/tree/impl/union_find.hh> +# include <mln/morpho/tree/impl/hqueue.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + /// Compute a canonized min-tree. + /// + /// \param[in] f The input image. + /// \param[in] nbh The neighborhood. + /// + /// \return The corresponding min-tree structure. + /// + template <typename I, typename N> + inline + util::ctree::ctree + min_tree(const Image& f, const Neighborhood<N>& nbh); + + /// Compute a canonized max-tree. + /// + /// \param[in] f The input image. + /// \param[in] nbh The neighborhood. + /// + /// \return The corresponding max-tree structure. + /// + template <typename I, typename N> + inline + util::ctree::ctree + max_tree(const Image& f, const Neighborhood<N>& nbh); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename N> + inline + util::ctree::ctree + min_tree(const Image& f_, const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::min_tree"); + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + util::ctree::ctree tree = + morpho::tree::impl::generic::union_find(tag::tree::min, f, nbh); + + trace::exiting("morpho::tree::min_tree"); + return tree; + } + + template <typename I, typename N> + inline + util::ctree::ctree + max_tree(const Image& f_, const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::max_tree"); + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + util::ctree::ctree tree = + morpho::tree::impl::generic::union_find(tag::tree::max, f, nbh); + + trace::exiting("morpho::tree::max_tree"); + return tree; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_COMPONENT_TREE_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh (revision 4620) @@ -0,0 +1,178 @@ +// Copyright (C) 2008, 2009 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 COMPUTE_ATTRIBUTE_IMAGE_HH +# define COMPUTE_ATTRIBUTE_IMAGE_HH +/// +/// +/// \brief Compute an attribute on a morphological tree. +/// +/// \todo Specialize for fast image. +/// + + +# include <mln/core/image/attribute_image.hh> +# include <mln/core/concept/tree.hh> +# include <mln/core/concept/accumulator.hh> + +# include <mln/data/fill.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree, + const Accumulator<A>& accu); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_none, + const T&, A& accu, + const mln_psite(T)&) + { + accu.take(); + } + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_pix, + const T& tree, A& accu, + const mln_psite(T)& p) + { + accu.take(make::pix(p, tree.f(p))); + } + + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_v, + const T& tree, A& accu, + const mln_psite(T)& p) + { + accu.take(tree.f(p)); + } + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_p, + const T&, A& accu, + const mln_psite(T)& p) + { + accu.take(p); + } + + template <typename T, typename A> + void + take_as_init(const T& tree, A& a, const mln_psite(T)& p) + { + take_as_init(mln_trait_accumulator_when_pix(A)(), tree, a, p); + } + + } // end of namespace namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const T& tree, const A& accu, attribute_image<T, A>* accu_img = 0) + { + attribute_image<T, A> a(tree); + (void) accu_img; + + // Transmit dynamic data of accumulator (ex: rank filter). + data::fill(a, accu); + + // Initialize. Each node takes its content. + { + mln_fwd_piter(T::domain_t) p(tree.domain()); + for_all(p) + internal::take_as_init(tree, a.element(tree.node_at_(p)), p); + } + + // Transmit to parent. + for (unsigned i = tree.n_nodes() - 1; i > 0; --i) + { + unsigned q = tree.parent_at_(i); + if (q != i) // The current node is not a root. + a.element(q).take(a.element(i)); + } + + attribute_image<T, mln_result(A)> out(tree); + for (unsigned i = 0; i < tree.n_nodes(); i++) + out.element(i) = a.element(i).to_result(); + + return out; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + + + // Facades + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree_, const Accumulator<A>& acc) + { + trace::entering("mln::morpho::tree::compute_attribute_image"); + const T& tree = exact(tree_); + const A& accu = exact(acc); + + mln_precondition(tree.is_valid()); + + return impl::generic::compute_attribute_image(tree, accu); + trace::exiting("mln::morpho::tree::compute_attribute_image"); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !COMPUTE_ATTRIBUTE_IMAGE_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh (revision 4620) @@ -0,0 +1,408 @@ +// Copyright (C) 2008, 2009 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 MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH +# define MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH + +/// +/// \brief The dual input tree algorithm specialized for low quantized image. +/// +/// This implementation is based on P. Salembier algorithm using +/// hierachical queues. This implies a low-quantized input image so +/// that the number of queues is limited. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. +/// +/// TODO: During the canonization pass, we build the tree site set +/// from the sorted site set of f, so that we compute twice f +/// histogram (can be avoided). + +# include <mln/data/sort_psites.hh> +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/hqueues.hh> +# include <mln/util/ord.hh> + +# include <mln/value/value_array.hh> +# include <mln/value/set.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + /// Compute a tree using hqueues. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename N> + inline + data<I, p_array<mln_psite(I)> > + dual_hqueue(const Image& f, + const Image& m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I, typename N, class E> + struct shared_flood_args + { + typedef mln_psite(I) P; + typedef mln_value(I) V; + typedef p_array S; + + const I& f; + const I& m; + const N& nbh; + mln_ch_value(I, P)& parent; + + // Aux data + util::hqueues<P, V>& hqueues; + const E& extend; // site -> site functor. + value::value_array<V, bool> is_node_at_level; + value::value_array<V, P> node_at_level; + mln_ch_value(I, bool) deja_vu; + const value::set<V>& vset; + + shared_flood_args(const I& f_, + const I& m_, + const N& neigb_, + mln_ch_value(I, P)& parent_, + util::hqueues<mln_psite(I), V>& hqueues_, + const E& extend_) + : f (f_), + m (m_), + nbh (neigb_), + parent (parent_), + hqueues (hqueues_), + extend (extend_), + is_node_at_level (false), + vset (hqueues.vset()) + { + initialize(deja_vu, f); + mln::data::fill(deja_vu, false); + } + }; + + template <typename I> + inline + histo::array<mln_value(I)> + compute_histo(const I& f, const I& m, mln_value(I)& hmin, mln_psite(I)& pmin) + { + histo::array<mln_value(I)> hm = histo::compute(m); + const histo::array<mln_value(I)> hf = histo::compute(f); + + { // Retrieve hmin. + unsigned i = 0; + while (hm[i] == 0) + ++i; + hmin = hm.vset()[i]; + } + + // Merge histograms. + for (unsigned i = 0; i < hm.nvalues(); ++i) + hm[i] += hf[i]; + + // Retrieve pmin. + mln_piter(I) p(m.domain()); + for (p.start(); m(p) != hmin; p.next()) + ; + mln_assertion(p.is_valid()); + pmin = p; + + return hm; + } + + // Site -> site functor: give for all p in Domain(f), its + // equivalence in the extended domain. + // TODO: make it generic. It works only on boxed domain. + template <typename I> + struct extend + { + extend(const mln_psite(I)::delta& dp) + : dp_ (dp) + { + } + + mln_psite(I) operator() (const mln_psite(I)& p) const + { + return p + dp_; + } + + private: + const mln_psite(I)::delta dp_; + }; + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + template <typename I, typename N, typename E> + unsigned + flood(internal::shared_flood_args<I, N, E>& args, const unsigned h_idx) + { + mln_assertion(args.is_node_at_level[h_idx]); + + while (!args.hqueues[h_idx].empty()) + { + mln_psite(I) p = args.hqueues[h_idx].pop_front(); + unsigned p_idx = args.vset.index_of(args.f(p)); + + if (p_idx != h_idx) + { // Intensity mismatch: irregular case. + mln_psite(I) pext = args.extend(p); + args.parent(pext) = args.node_at_level[h_idx]; + + if (p_idx > h_idx) // Singleton with parent at h. + args.parent(p) = args.node_at_level[h_idx]; + else + { + if (!args.is_node_at_level[p_idx]) + { + args.is_node_at_level[p_idx] = true; + args.node_at_level[p_idx] = p; + } + } + } + + if (p_idx <= h_idx) + { + if (!args.f.domain().has(args.node_at_level[p_idx]) || + util::ord_strict(p, args.node_at_level[p_idx])) + { // Regular case but a representative provided by the extension. + args.parent(args.node_at_level[p_idx]) = p; + args.node_at_level[p_idx] = p; + //args.parent(p) = p; + } + args.parent(p) = args.node_at_level[p_idx]; + } + + + // Process the neighbors + mln_niter(N) n(args.nbh, p); + for_all(n) + if (args.f.domain().has(n) && !args.deja_vu(n)) + { + unsigned mn = args.vset.index_of(args.m(n)); + unsigned fn = args.vset.index_of(args.f(n)); + args.hqueues[mn].push(n); + args.deja_vu(n) = true; + + mln_psite(I) ext = args.extend(n); + // Create a node at c. + { + mln_psite(I) node = (fn == mn) ? n : ext; + if (!args.is_node_at_level[mn]) + { + args.is_node_at_level[mn] = true; + args.node_at_level[mn] = node; + } + } + + while (mn > h_idx) + mn = flood(args, mn); + } + } + + // Retrieve dad. + args.is_node_at_level[h_idx] = false; + unsigned c = h_idx; + while (c > 0 && !args.is_node_at_level[c]) + --c; + + mln_psite(I) x = args.node_at_level[h_idx]; + if (c > 0) + args.parent(x) = args.node_at_level[c]; + else + args.parent(x) = x; + + return c; + } + + template <typename I, typename N> + inline + data< I, p_array<mln_psite(I)> > + dual_hqueue(const Image& f_, + const Image& m_, + const Neighborhood<N>& neibh_) + { + trace::entering("mln::morpho::tree::impl::dual_hqueue"); + + const I& f = exact(f_); + const I& m = exact(m_); + const N& nbh = exact(neibh_); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + util::timer tm; + tm.start(); + + // Histo. + mln_psite(I) pmin; + mln_value(I) hmin; + const histo::array<mln_value(I)> histo = internal::compute_histo(f, m, hmin, pmin); + util::hqueues<P, mln_value(I)> hqueues(histo); + + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_ext = f.domain(); + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + // Process. + internal::extend extend(dp); + internal::shared_flood_args< I, N, internal::extend > + args(f, m, nbh, parent, hqueues, extend); + + unsigned r = args.vset.index_of(hmin); + args.deja_vu(pmin) = true; + args.hqueues[r].push(pmin); + args.node_at_level[r] = (f(pmin) == hmin) ? pmin : extend(pmin); + args.is_node_at_level[r] = true; + flood(args, r); + + // Attach the nodes under hmin. + unsigned i = r; + do + { + if (args.is_node_at_level[i]) + { + parent(args.node_at_level[r]) = args.node_at_level[i]; + r = i; + } + } + while (i-- > 0); + parent(args.node_at_level[r]) = args.node_at_level[r]; //root + + // Canonization and make tree site set. + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + + p_array<mln_psite(I)> s_f = mln::data::sort_psites_increasing(f); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P x = p; + P q = parent(p); + + // Case: l: m <---- m <---- f + // Or + // Case l1: m <----- f impossible. + // | + // l2: m + mln_assertion(!(d_ext.has(q) && fext(p) == fext(q) && d_ext.has(parent(q)) && q != parent(q))); + + while (d_ext.has(q) && !deja_vu(q) && (fext(q) != fext(parent(q)) || q == parent(q))) + { + s.append(q); + deja_vu(q) = true; + x = q; + q = parent(q); + } + + if (d_ext.has(q) && fext(q) == fext(parent(q)) && q != parent(q)) + { + q = (parent(x) = parent(q)); + mln_assertion(f.domain().has(q)); + } + + if (fext(q) == fext(parent(q))) + parent(x) = parent(q); + + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + + } + + std::cout << "Construction de l'arbre en " << tm << " s." << std::endl; + + data<I, S> tree(fext, parent, s); + + trace::exiting("mln::morpho::tree::impl::dual_hqueue"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_COMPUTE_PARENT_DUAL_HQUEUE_HH + + + Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh (revision 4620) @@ -0,0 +1,172 @@ +// Copyright (C) 2008, 2009 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 MLN_MORPHO_TREE_IMPL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMPL_UNION_FIND_HH + +# include <mln/data/sort_psites.hh> +# include <mln/util/ctree/ctree.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + template <typename T, typename I, typename N> + util::ctree::ctree + union_find(const tag::tree::tree_t<T>&, + const Image& f, + const Neighborhood<N>& nbh); + } + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::max_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_increasing(f); + return data; + } + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::min_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_decreasing(f); + return data; + } + + template <typename T> + inline + mln_psite(T) + zfind_root(T& zpar, const mln_psite(T)& x) + { + mlc_equal(mln_value(T), mln_psite(T))::check(); + if (zpar(x) == x) + return x; + else + return zpar(x) = zfind_root(zpar, zpar(x)); + } + + } + + + namespace impl + { + + namespace generic + { + + template <typename T, typename I, typename N> + util::ctree::ctree + union_find(const tag::tree::tree_t<T>&, + const Image& f_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::union_find"); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + S s = internal::sort_sites_set(T (), f); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) area; + mln_ch_value(I, P) zpar; + unsigned nb_nodes = s.nsites(); + + initialize(deja_vu, f); + initialize(parent, f); + initialize(area, f); + initialize(zpar, f); + + // Initialization. + data::fill(deja_vu, false); + data::fill(area, 0); + + // Body. + mln_bkd_piter(S) p(s); // Backward. + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make-Set. + parent(p) = p; + zpar(p) = p; + + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + // Do-Union. + P r = internal::zfind_root(zpar, n); + if (r != p) + { + parent(r) = p; + zpar(r) = p; + area(p) += area(r); + if (f(r) != f(p)) + ++area(p); + else + --nb_nodes; + } + } + deja_vu(p) = true; + } + + util::ctree::ctree tree(f, s, parent, area, nb_nodes); + + trace::exiting("morpho::tree::impl::generic::union_find"); + return tree; + } + + } + + } +# endif // ! MLN_INCLUDE_ONLY + } + + } + +} +#endif // !MLN_MORPHO_TREE_IMPL_UNION_FIND_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh (revision 4620) @@ -0,0 +1,361 @@ +// Copyright (C) 2008, 2009 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 MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH + +/// +/// \brief The generic dual input tree algorithm for high quantized image. +/// +/// This implementation is based on tarjan's union method, so that +/// image quantization does not impact on the computation time. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. + +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + namespace generic + { + + /// Compute a tree using union-find method. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param s_f The sorted site set of \p f + /// \param s_m The sorted site set of \p m. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image& f, + const Image& m, + const Site_Set<S>& s_f, + const Site_Set<S>& s_m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + // For benchmark purpose. More than 50% of the time is spent + // in find_root function. + static util::timer t_prop; + + + template <typename I> + inline + mln_psite(I) find_root(I& zpar, + const mln_psite(I)& p) + { + if (zpar(p) == p) + return p; + + t_prop.resume(); + mln_psite(I) x = zpar(p); + while (zpar(x) != x) + x = zpar(x); + + mln_psite(I) tmp; + for (mln_psite(I) y = p; y != x; y = tmp) + { + tmp = zpar(y); + zpar(y) = x; + } + t_prop.stop(); + + return x; + } + + template <typename I> + inline + void + update_m_parent(const I& f, + mln_ch_value(I, mln_psite(I))& parent, + mln_ch_value(I, bool)& deja_vu, + p_array< mln_psite(I) >& sset, + const mln_domain(I)& d_ext, + const mln_psite(I)& p) + { + typedef mln_psite(I) P; + + P q = parent(p); + P x = parent(q); + + mln_assertion(d_ext.has(q)); + + while (d_ext.has(x) && f(q) == f(x) && q != x) + { + q = x; + x = parent(q); + } + + if (!d_ext.has(x)) + { + if (f(x) == f(parent(x))) + x = (parent(q) = parent(x)); + if (f(q) != f(x)) + { + x = q; + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + } + else + { + if (x != q) + { + update_m_parent(f, parent, deja_vu, sset, d_ext, q); + x = q; + } + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + for (P i = p, tmp = parent(i); i != q; i = tmp, tmp = parent(i)) + parent(i) = x; + } + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image& f_, + const Image& m_, + const Site_Set<S>& s_f_, + const Site_Set<S>& s_m_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::dual_union_find"); + + util::timer tm; + tm.start(); + internal::t_prop.reset(); + + typedef mln_psite(I) P; + typedef unsigned L; + + const I& f = exact(f_); + const I& m = exact(m_); + const S& s_f = exact(s_f_); + const S& s_m = exact(s_m_); + const N& nbh = exact(nbh_); + + // Aux data. + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_f = f.domain(); + mln_domain(I) d_ext = f.domain(); // translate dp + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + //Process + { + // Aux data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) zpar; + + initialize(deja_vu, fext); + initialize(zpar, fext); + mln::data::fill(deja_vu, false); + + mln_bkd_piter(S) p_f(s_f); // Backward. + mln_bkd_piter(S) p_m(s_m); // Backward. + p_f.start(); + p_m.start(); + + // Main loop. + while (p_m.is_valid() || p_f.is_valid()) + { + mln_bkd_piter(S)& it = (!p_f.is_valid() || (p_m.is_valid() && f(p_f) <= m(p_m))) ? p_m : p_f; + + P p = it; + P ext = p + dp; + + // std::cout << "-------------------" << std::endl; + // std::cout << "Take " << p << " of value " << (&it == &p_m ? m(p) : f(p)) + // << " from " << (&it == &p_m ? "mask" : "f") << std::endl; + // debug::println("Parent: ", parent); + // debug::println("Zpar: ", zpar); + + mln_assertion(!(deja_vu(p) && deja_vu(ext))); + if (deja_vu(ext)) // Seen by mask before f. + { + mln_assertion(m(p) >= f(p)); + // Make set. + parent(p) = p; + zpar(p) = p; + + P r = internal::find_root(zpar, ext); + zpar(r) = p; + parent(r) = p; + + deja_vu(p) = true; + } + else if (deja_vu(p)) // Seen by f before mask. + { + mln_assertion(f(p) > m(p)); + parent(p) = ext; + zpar(p) = ext; + parent(ext) = ext; + zpar(ext) = ext; + + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + //std::cout << "Root: " << r << std::endl; + if (r != ext) + { + parent(r) = ext; + zpar(r) = ext; + } + } + deja_vu(ext) = true; + } + else if (f(p) <= m(p)) // First time p encountered. + { + zpar(ext) = ext; + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + if (r != ext) + { + zpar(r) = ext; + parent(r) = ext; + } + } + deja_vu(ext) = true; + } + else + { + deja_vu(p) = true; + } + it.next(); + } + } + std::cout << ">> MAJ zpar: " << internal::t_prop << " s" << std::endl; + std::cout << "Parent construction: " << tm << " s" << std::endl; + tm.restart(); + + // Canonization + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P q = parent(p); + if (!f.domain().has(q)) + internal::update_m_parent(fext, parent, deja_vu, s, d_ext, p); + else if (fext(parent(q)) == f(q)) + parent(p) = parent(q); + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + } + std::cout << "Canonization: " << tm << " s" << std::endl; + + //mln_postcondition(internal::compute_parent_postconditions(fext, s, parent)); + + tree::data<I, p_array<mln_psite(I)> > tree(fext, parent, s); + trace::exiting("morpho::tree::impl::generic::dual_union_find"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh (revision 4620) @@ -0,0 +1,112 @@ +// Copyright (C) 2009 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 MLN_MORPHO_TREE_PROPAGATE_NODE_HH +# define MLN_MORPHO_TREE_PROPAGATE_NODE_HH + +/// \file +/// +/// Functions to propagate node in the tree. +/// +/// \todo: The new implementation permits: + to propagate toward +/// subcomponents very fast (data::fill)\ + to propagate toward +/// supernodes as fast as the previous component\ + the attribute +/// image is still valid without the use of propagate_representative +/// that does not make sense any more. +/// +/// We are able in both cases to do something like: +/// + data::fill(attr_img | asc(n), v) +/// + data::fill(attr_img | desc(n), v) +/// +/// However the subimage morpher is not specialized for fast image and +/// does not take benefits in the fact that: +/// + desc(n) is a p_run (so can be memseté) +/// + attr_img can accessed by indexed (element() method for fast-image) + +# include <mln/core/image/attribute_image.hh> +# include <algorithm> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + template <typename T, typename V> + inline + unsigned + propagate_node_to_descendants(attribute_image<T, V>& a, + const typename T::node_t& n, + const V& value) + { + typedef typename T::nodes_t desc_t; + mln_precondition(a.is_valid()); + mln_precondition(a.has(n)); + + // (n € desc(n)) but we don't set its value. + unsigned i = a.tree().desc(n).nsites(); + + if (i > 0) + { + mln_assertion(a.tree().has_index(n.index() + i)); + V* v = a.buffer() + n.index(); + std::fill(v + 1, v + i, value); + } + return i - 1; + } + + template <typename T, typename V> + inline + unsigned + propagate_node_to_ancestors(attribute_image<T, V>& a, + typename T::node_t n, + const V& v) + { + mln_precondition(a.is_valid()); + mln_precondition(a.has(n)); + + if (a.tree().is_a_root(n)) + return 0; + + unsigned i = 0; + do { + n = a.tree().parent(n); + a(n) = v; + ++i; + } while (!a.tree().is_a_root(n)); + + return i; + } + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // ! MLN_MORPHO_TREE_PROPAGATE_NODE_HH Index: trunk/milena/sandbox/edwin/mln/debug/ctree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/debug/ctree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/debug/ctree.hh (revision 4620) @@ -0,0 +1,155 @@ +// Copyright (C) 2008, 2009 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 MLN_DEBUG_CTREE_HH +# define MLN_DEBUG_CTREE_HH + +# include <mln/util/ctree/ctree.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/core/site_set/p_array.hh> +# include <mln/math/max.hh> +# include <vector> +# include <iostream> + + +namespace mln +{ + + namespace debug + { + + /// \brief Print a morphological tree. + /// + /// \param[in] tree The tree to be print. + /// + template <typename T> + void + println(const Tree<T>& tree); + + /// \brief Print an attribute image. + /// + /// \param[in] a The attribute image. + /// + template <typename T, typename V> + void + println(const attribute_image<T, V>& a); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename V> + void + println(const T& tree, const std::vector<V>& values) + { + typedef std::vector< p_array<mln_psite(T)> > hset_t; + hset_t hset(tree.nodes().nsites()); + + // Make site set of each node. + { + mln_piter(T::domain_t) p(tree.domain()); + for_all(p) + hset[tree.node(p).index()].insert(p); + } + + // Retrieve the height + unsigned height = 0; + { + attribute_image<T, unsigned> h(tree); + data::fill(h, 0); + + mln_bkd_piter(T::nodes_t) n(tree.nodes()); + for_all(n) + if (!tree.is_a_root(n)) + h(tree.parent(n)) = math::max(h(tree.parent(n)), h(n) + 1); + else + height = math::max(height, h(n)); + } + { + std::cout << "Node"; + for (unsigned i = 0; i < height; i++) + std::cout << " "; + std::cout << "Value\tSites" << std::endl; + } + + mln_fwd_piter(T::nodes_t) n(tree.nodes()); + typename T::node_t old; + unsigned depth = 0; + for_all(n) + { + if (tree.is_a_root(n)) + depth = 0; + else + { + while (old != tree.parent(n)) + { + --depth; + old = tree.parent(old); + } + ++depth; + } + + for (unsigned i = 0; i < depth; i++) + std::cout << " "; + std::cout << n; + for (unsigned i = depth; i < height + 1; i++) + std::cout << " "; + + old = n; + std::cout << values[old.index()] << "\t" + << hset[old.index()] << std::endl; + } + + } + + } // end of namespace mln::debug::internal + + template <typename T> + void + println(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + + mln_precondition(tree.is_valid()); + internal::println(tree, tree.data_hook_()->values_); + } + + template <typename T, typename V> + void + println(const attribute_image<T, V>& a) + { + mln_precondition(a.is_valid()); + internal::println(a.tree(), a.hook_data_()->values_); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::debug + +} // end of namespace mln + +#endif // !MLN_DEBUG_CTREE_HH Index: trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh (revision 4620) @@ -0,0 +1,458 @@ +// Copyright (C) 2007, 2008, 2009 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 MLN_CORE_SITE_SET_P_RUN_IDX_HH +# define MLN_CORE_SITE_SET_P_RUN_IDX_HH + +/// \file +/// +/// Definition of a run of index sites. +/// +/// \todo Use a lazy approach (in subj) like in p_array psite. +/// +/// FIXME: Wanted to have: +/// p_run_idx_psite < internal::index_site_base +/// < internal::pseudo_site_base +/// but diamond inheritance doesn't work even with virtual keyword... + +# include <mln/core/internal/index_site_base.hh> +# include <mln/core/internal/site_set_base.hh> +# include <mln/core/internal/pseudo_site_base.hh> +# include <mln/util/index.hh> + + +namespace mln +{ + + // Forward declarations. + template <typename P> class p_run_idx; + template <typename P> class p_run_idx_psite; + template <typename P> class p_run_idx_fwd_piter_; + template <typename P> class p_run_idx_bkd_piter_; + + namespace trait + { + + template <typename P> + struct site_set_< p_run_idx > + { + typedef trait::site_set::nsites::known nsites; + typedef trait::site_set::bbox::unknown bbox; + typedef trait::site_set::contents::fixed contents; + typedef trait::site_set::arity::unique arity; + }; + + template <typename P> + struct set_precise_unary_< op::ord, p_run_idx > + { + typedef set_precise_unary_< op::ord, p_run_idx > ret; // Itself. + bool strict(const p_run_idx& lhs, const p_run_idx& rhs) const; + }; + + } // end of namespace trait + + + + /// \brief Site set class in run. + /// + /// \ingroup modsitesetbasic + template <typename P> + class p_run_idx : public internal::site_set_base_< P, p_run_idx > + { + public: + + /// Element associated type. + typedef P element; + + /// Psite associated type. + typedef p_run_idx_psite psite; + + /// Forward Site_Iterator associated type. + typedef p_run_idx_fwd_piter_ fwd_piter; + + /// Backward Site_Iterator associated type. + typedef p_run_idx_bkd_piter_ bkd_piter; + + /// Site_Iterator associated type. + typedef fwd_piter piter; + + + /// Constructor without argument. + p_run_idx(); + + /// Constructor. + p_run_idx(const P& start, const mln_delta(P)& len); + + /// Constructor. + p_run_idx(const P& start, const P& end); + + /// Init + void init(const P& start, const mln_delta(P)& len); + + /// Constructor. + void init(const P& start, const P& end); + + /// Test if \p p belongs to this site set. + bool has(const psite& p) const; + + /// Test if \p p belongs to this site set. + bool has(const P& p) const; + + /// Test if index \p i belongs to this site set. + bool has_index(unsigned i) const; + + /// Give the number of sites. + unsigned nsites() const; + + /// Return the \p i-th site. + P operator[](int i) const; + + /// Return the starting site. + const P& start() const; + + /// Return (compute) the ending site. + P end() const; + + /// Test if this run is valid, i.e., with length > 0. + bool is_valid() const; + + /// Return the size of this site set in memory. + std::size_t memory_size() const; + + protected: + + /// The first site of the run. + P start_; + + /// The length of the run. + mln_delta(P) len_; + }; + + + template <typename P> + std::ostream& operator<<(std::ostream& ostr, const p_run_idx& r); + + template <typename P> + class p_run_idx_psite : public internal::pseudo_site_base_< const P&, p_run_idx_psite > + { + typedef p_run_idx_psite self; + typedef internal::pseudo_site_base_<const P&, self> super; + + public: + + // This associated type is important to know that this particular + // pseudo site knows the site set it refers to. + typedef p_run_idx target; + + // As a Proxy: + const P& subj_(); + + p_run_idx_psite(); + p_run_idx_psite(const p_run_idx& run, int i); + + int index() const; + void change_index(int i); + void inc_index(); + void dec_index(); + + const p_run_idx* target_() const; + void change_target(const p_run_idx& new_target); + + bool is_valid() const; + + operator util::index() const; + + const p_run_idx& run() const; + + private: + + const p_run_idx* run_; + int i_; + mutable P p_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_run_idx::p_run_idx() + { + len_.change_value(0); + } + + template <typename P> + inline + p_run_idx::p_run_idx(const P& start, const mln_delta(P)& len) + { + mln_precondition(len.value() != 0); + init(start, len); + } + + + template <typename P> + inline + void + p_run_idx::init(const P& start, const mln_delta(P)& len) + { + mln_precondition(len.value() != 0); + start_ = start; + len_ = len; + } + + template <typename P> + inline + p_run_idx::p_run_idx(const P& start, const P& end) + { + mln_precondition(start <= end); + init(start, end - start + 1); + } + + template <typename P> + inline + void + p_run_idx::init(const P& start, const P& end) + { + mln_precondition(start <= end); + init(start, end - start + 1); + } + + template <typename P> + inline + bool + p_run_idx::is_valid() const + { + return len_.value() != 0; + } + + template <typename P> + inline + bool + p_run_idx::has(const psite& p) const + { + mln_precondition(p.target_() == this); // FIXME: Refine. + if (p.index() >= len_.value()) + return false; + // The type of rhs below is mln_site(p_run_idx). + mln_invariant(p.to_site() == (*this)[p.index()]); + return true; + } + + template <typename P> + inline + bool + p_run_idx::has(const P& p) const + { + mln_precondition(is_valid()); + return start_ <= p && p <= end(); + } + + template <typename P> + inline + bool + p_run_idx::has_index(unsigned i) const + { + return i < len_.value(); + } + + template <typename P> + inline + unsigned + p_run_idx::nsites() const + { + mln_precondition(is_valid()); + return len_.value(); + } + + template <typename P> + inline + P + p_run_idx::operator[](int i) const + { + mln_precondition(is_valid()); + mln_precondition(i >= 0); + mln_precondition(i < len_.value()); + P p = start_ + (mln_delta(P))i; + return p; + } + + template <typename P> + inline + const P& + p_run_idx::start() const + { + return start_; + } + + template <typename P> + inline + P + p_run_idx::end() const + { + P p = start_ + (len_ - 1); + return p; + } + + template <typename P> + inline + std::size_t + p_run_idx::memory_size() const + { + return sizeof(*this); + } + + template <typename P> + std::ostream& operator<<(std::ostream& ostr, const p_run_idx& r) + { + ostr << '(' << r.start() << ", " << r.nsites() << ')'; + return ostr; + } + + // p_run_idx_psite + + template <typename P> + inline + p_run_idx_psite::p_run_idx_psite() + : run_(0), + i_(0) + { + } + + template <typename P> + inline + p_run_idx_psite::p_run_idx_psite(const p_run_idx& run, int i) + : run_(&run), + i_(i), + p_(run.start()) + { + p_ += i_; + } + + template <typename P> + inline + bool + p_run_idx_psite::is_valid() const + { + return run_ != 0 && run_->has_index(i_); + } + + template <typename P> + inline + int + p_run_idx_psite::index() const + { + return i_; + } + + template <typename P> + inline + void + p_run_idx_psite::change_index(int i) + { + p_ += (mln_delta(P))(i - i_); + i_ = i; + } + + template <typename P> + inline + void + p_run_idx_psite::dec_index() + { + --i_; + p_.dec_index(); + } + + template <typename P> + inline + void + p_run_idx_psite::inc_index() + { + ++i_; + p_.inc_index(); + } + + template <typename P> + inline + const p_run_idx* + p_run_idx_psite::target_() const + { + return run_; + } + + template <typename P> + inline + void + p_run_idx_psite::change_target(const p_run_idx& new_target) + { + run_ = & new_target; + i_ = 0; + p_ = run_->start(); + } + + template <typename P> + inline + const P& + p_run_idx_psite::subj_() + { + return p_; + } + + template <typename P> + inline + p_run_idx_psite::operator util::index() const + { + return i_; + } + + template <typename P> + inline + const p_run_idx& + p_run_idx_psite::run() const + { + mln_precondition(run_ != 0); + return *run_; + } + namespace trait + { + + template <typename P> + inline + bool + set_precise_unary_< op::ord, p_run_idx >::strict(const p_run_idx& lhs, const p_run_idx& rhs) const + { + return util::ord_strict(lhs.start(), rhs.start()); + } + + } // end of namespace trait + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/site_set/p_run_idx_piter.hh> + + +#endif // ! MLN_CORE_SITE_SET_P_RUN_IDX_HH Index: trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh (revision 4620) @@ -0,0 +1,222 @@ +// Copyright (C) 2007, 2008, 2009 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 MLN_CORE_SITE_SET_P_RUN_IDX_PITER_HH +# define MLN_CORE_SITE_SET_P_RUN_IDX_PITER_HH + +/*! \file + * + * \brief Definition of point iterators on mln::p_run_idx. + */ + +# include <mln/core/site_set/p_run_idx.hh> +# include <mln/core/internal/site_set_iterator_base.hh> + + +namespace mln +{ + + /*! \brief Forward iterator on points of a p_run_idx. + * + */ + template <typename P> + class p_run_idx_fwd_piter_ + : + public internal::site_set_iterator_base< p_run_idx, + p_run_idx_fwd_piter_ > + { + typedef p_run_idx_fwd_piter_ self_; + typedef internal::site_set_iterator_base< p_run_idx, self_ > super_; + public: + + /// Constructor without arguments. + p_run_idx_fwd_piter_(); + + /// Coordinate associated type. + p_run_idx_fwd_piter_(const p_run_idx& r); + + /// Test if the iterator is valid. + bool is_valid_() const; + + /// Invalidate the iterator. + void invalidate_(); + + /// Start an iteration. + void start_(); + + /// Go to the next point. + void next_(); + + protected: + using super_::p_; + using super_::s_; + }; + + + + /*! \brief Backward iterator on points of a p_run_idx. + * + */ + template <typename P> + class p_run_idx_bkd_piter_ + : + public internal::site_set_iterator_base< p_run_idx, + p_run_idx_bkd_piter_ > + { + typedef p_run_idx_bkd_piter_ self_; + typedef internal::site_set_iterator_base< p_run_idx, self_ > super_; + public: + + /// Constructor without arguments. + p_run_idx_bkd_piter_(); + + /// Coordinate associated type. + p_run_idx_bkd_piter_(const p_run_idx& r); + + /// Test if the iterator is valid. + bool is_valid_() const; + + /// Invalidate the iterator. + void invalidate_(); + + /// Start an iteration. + void start_(); + + /// Go to the next point. + void next_(); + + protected: + using super_::p_; + using super_::s_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + // p_run_idx_fwd_piter_ + + template <typename P> + inline + p_run_idx_fwd_piter_::p_run_idx_fwd_piter_() + { + } + + template <typename P> + inline + p_run_idx_fwd_piter_::p_run_idx_fwd_piter_(const p_run_idx& r) + { + this->change_target(r); + } + + template <typename P> + inline + bool + p_run_idx_fwd_piter_::is_valid_() const + { + mln_invariant(p_.index() >= 0); + return p_.index() < int(s_->nsites()); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_::invalidate_() + { + p_.change_index(s_->nsites()); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_::start_() + { + p_.change_index(0); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_::next_() + { + p_.inc_index(); + } + + + // p_run_idx_bkd_piter_ + + template <typename P> + inline + p_run_idx_bkd_piter_::p_run_idx_bkd_piter_() + { + } + + template <typename P> + inline + p_run_idx_bkd_piter_::p_run_idx_bkd_piter_(const p_run_idx& r) + { + this->change_target(r); + } + + template <typename P> + inline + bool + p_run_idx_bkd_piter_::is_valid_() const + { + mln_invariant(p_.index() < int(s_->nsites())); + return p_.index() >= 0; + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_::invalidate_() + { + p_.change_index(-1); + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_::start_() + { + p_.change_index(s_->nsites() - 1); + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_::next_() + { + p_.dec_index(); + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_SITE_SET_P_RUN_IDX_PITER_HH Index: trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh (revision 4620) @@ -0,0 +1,435 @@ +// Copyright (C) 2008, 2009 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 MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH +# define MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH + +# include <mln/core/internal/image_primary.hh> +# include <mln/core/concept/tree.hh> +# include <mln/metal/converts_to.hh> + +namespace mln +{ + // Forward declaration. + template <typename T, typename V> class attribute_image; + + namespace internal + { + + /// Data structure for \c mln::attribute_image + template <typename T, typename V> + struct data< mln::attribute_image<T, V> > + { + data(); + data(const T& tree); + ~data(); + + std::vector<V> values_; + T tree_; // An attribute image can hold the tracked-data of the tree. + }; + + } // end of namespace mln::internal + + namespace trait + { + + template <typename T, typename V> + struct image_< attribute_image<T, V> > : default_image_< V, attribute_image<T, V> > + { + // misc + typedef trait::image::category::primary category; + typedef trait::image::speed::fastest speed; + typedef trait::image::size::regular size; + + // value + typedef trait::image::vw_io::none vw_io; + typedef trait::image::vw_set::none vw_set; + typedef trait::image::value_access::direct value_access; + typedef trait::image::value_alignment::irrelevant value_alignment; + typedef trait::image::value_browsing::site_wise_only value_browsing; + typedef trait::image::value_storage::one_block value_storage; + typedef trait::image::value_io::read_write value_io; + + // site / domain + typedef trait::image::pw_io::read_write pw_io; + typedef trait::image::localization::none localization; + typedef trait::image::dimension::none dimension; + + // extended domain + typedef trait::image::ext_domain::none ext_domain; + typedef trait::image::ext_value::irrelevant ext_value; + typedef trait::image::ext_io::irrelevant ext_io; + }; + + } // end of namespace mln::trait + + + namespace convert + { + + namespace over_load + { + + template <typename T, typename V, typename I> + void + from_to_(const mln::attribute_image<T, V>& from, Image& to_) + { + typedef mln::attribute_image<T, V> A; + I& to = exact(to_); + + mlc_converts_to(V, mln_value(I))::check(); + mlc_converts_to(typename T::domain_t, mln_domain(I))::check(); + + mln_precondition(from.is_valid()); + to.init_(from.tree().domain()); + + mln_fwd_piter(I) p(to.domain()); + for_all(p) + convert::from_to(from(from.tree().node(p)), to(p)); + } + + } // enf of namespace mln::convert::over_load + + } // end of namespace mln::convert + + + /// Basic attribute image class. + /// + /// The parameter \c V is the type of pixel values (usually the + /// result type of the attribute). This image class stores data in + /// memory. + /// + /// \ingroup modimageconcrete + // + template <typename T, typename V> + class attribute_image : public internal::image_primary< V, typename T::nodes_t, attribute_image<T, V> > + { + typedef internal::image_primary< V, typename T::nodes_t, attribute_image<T, V> > super_; + typedef attribute_image<T, V> self_; + + public: + + /// Value associated type. + typedef V value; + /// Return type of read-only access. + typedef const V& rvalue; + /// Return type of read-write access. + typedef V& lvalue; + + + /// Site (node) assocatied type. + typedef typename T::node_t node_t; + typedef node_t site; + typedef node_t psite; + + /// Site set (node set) associated type. + typedef typename T::nodes_t nodes_t; + + /// Skeleton. + typedef attribute_image< T, tag::value_<V> > skeleton; + + /// Constructors + /// \{ + /// Constructor without argument. + attribute_image(); + /// Allocate an attribute image respecting the size of the tree. + attribute_image(const Tree<T>& tree); + /// \} + + /// Initialize an empty image. + void init_(const Tree<T>& tree); + + /// Test if the node \p n is valid. + bool has(const node_t& n) const; + + /// Give the node site set. + const nodes_t& domain() const; + + /// Read-only access to the image value at node \p n. + rvalue operator()(const node_t& n) const; + + /// Read-write access to the image value at node \p n. + lvalue operator()(const node_t& n); + + // Specific methods: + // ---------------- + + /// Read access to the value at point \p p. + /// Note: can be ambigous if the node content is a node set. + rvalue operator()(const mln_psite(T)& p) const; + + /// Return the tree. + const T& tree() const; + + /// Change the target tree. + void change_tree(const Tree<T>& tree); + + // As a fastest image. + // ------------------ + + /// Give the number of elements. + unsigned nelements() const; + + /// Read-only access to the image value lacated at index \p i. + rvalue element(unsigned i) const; + + /// Read-write access to the image value lacated at index \p i. + lvalue element(unsigned i); + + /// Return the border. (Required by image fastest / return always 0). + unsigned border() const; + + /// Give the delta_index corresponding to the delta point. + int delta_index(const mln_delta(node_t)& dp) const; + + /// Give the point corresponding to the index \p i; + node_t point_at_index(unsigned i) const; + + /// Give a hook to the value buffer. + const value* buffer() const; + + /// Give a hook to the value buffer. + value* buffer(); + }; + + // Forward declaration. + template <typename T, typename V, typename V2> + void init_(tag::image_t, mln::attribute_image<T, V>& target, const mln::attribute_image<T, V2>& model); + + +# ifndef MLN_INCLUDE_ONLY + + // init_ + + template <typename T, typename V, typename V2> + inline + void + init_(tag::image_t, mln::attribute_image<T, V>& target, const mln::attribute_image<T, V2>& model) + { + target.init_(model.tree()); + } + + // internal::data + + namespace internal + { + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::data() + { + } + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::data(const T& tree) + : values_ (tree.n_nodes()), + tree_ (tree) + { + } + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::~data() + { + } + + } // end of namespace mln::internal + + + template <typename T, typename V> + inline + attribute_image<T, V>::attribute_image() + { + } + + + template <typename T, typename V> + inline + attribute_image<T, V>::attribute_image(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + mln_precondition(tree.is_valid()); + this->data_ = new internal::data< self_ >(tree); + } + + template <typename T, typename V> + inline + unsigned + attribute_image<T, V>::border() const + { + return 0; + } + + template <typename T, typename V> + inline + void + attribute_image<T, V>::init_(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + mln_precondition(tree.is_valid()); + this->data_->tree_ = tree; + this->data_->values_.resize(tree.n_nodes()); + } + + template <typename T, typename V> + inline + bool + attribute_image<T, V>::has(const node_t& n) const + { + mln_precondition(this->is_valid()); + return this->domain().has(n); + } + + template <typename T, typename V> + inline + const typename T::nodes_t& + attribute_image<T, V>::domain() const + { + mln_precondition(this->is_valid()); + return this->data_->tree_.nodes(); + } + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::operator()(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename T, typename V> + inline + V& + attribute_image<T, V>::operator()(const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + // Specific methods: + // ---------------- + + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::operator()(const mln_psite(T)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->tree_.has(p)); + return this->data_->values_[this->data_->tree_.node_at_(p)]; + } + + template <typename T, typename V> + inline + const T& + attribute_image<T, V>::tree() const + { + mln_precondition(this->is_valid()); + return this->data_->tree_; + } + + template <typename T, typename V> + inline + void + attribute_image<T, V>::change_tree(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + mln_precondition(tree.is_valid()); + this->data_->tree_ = tree; + } + + template <typename T, typename V> + inline + unsigned + attribute_image<T, V>::nelements() const + { + mln_precondition(this->is_valid()); + return this->domain().nsites(); + } + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::element(unsigned i) const + { + mln_precondition(this->is_valid()); + mln_precondition(i < this->nelements()); + return this->data_->values_[i]; + } + + template <typename T, typename V> + inline + V& + attribute_image<T, V>::element(unsigned i) + { + mln_precondition(this->is_valid()); + mln_precondition(i < this->nelements()); + return this->data_->values_[i]; + } + + template <typename T, typename V> + inline + int + attribute_image<T, V>::delta_index(const mln_delta(node_t)& dp) const + { + mln_precondition(this->is_valid()); + return dp.value(); + } + + template <typename T, typename V> + inline + typename T::node_t + attribute_image<T, V>::point_at_index(unsigned i) const + { + mln_precondition(this->is_valid()); + node_t tmp(this->data_->tree_, i); + return tmp; + } + + template <typename T, typename V> + inline + const V* + attribute_image<T, V>::buffer() const + { + return &(this->data_->values_[0]); + } + + template <typename T, typename V> + inline + V* attribute_image<T, V>::buffer() + { + return &(this->data_->values_[0]); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh (revision 4620) @@ -0,0 +1,311 @@ +// Copyright (C) 2008, 2009 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. + +/// +/// \brief Definition of the concept mln::index_site. +/// +/// FIXME: doc! +/// + + +#ifndef MLN_CORE_CONCEPT_INDEX_SITE_HH +# define MLN_CORE_CONCEPT_INDEX_SITE_HH + +# include <mln/core/concept/site.hh> +# include <mln/value/concept/integer.hh> +# include <mln/core/concept/dindex_site.hh> + + +namespace mln +{ + // Forward declaration. + template <typename E> struct Index_Site; + + namespace trait + { + + template < typename P, typename D > + struct set_binary_< op::plus, + mln::Index_Site, P, mln::Dindex_Site, D > + { + typedef P ret; + }; + + template < typename P, typename D > + struct set_binary_< op::minus, + mln::Index_Site, P, mln::Dindex_Site, D > + { + typedef P ret; + }; + + template < typename L, typename R > + struct set_binary_< op::minus, + mln::Index_Site, L, mln::Index_Site, R > + { + typedef mln_delta(L) ret; + }; + + template < typename L, typename R > + struct set_binary_< op::times, + mln::Index_Site, L, + mln::Object, mln::value::scalar_<R> > + { + typedef L ret; + }; + + template < typename L, typename R > + struct set_binary_< op::div, + mln::Index_Site, L, + mln::Object, mln::value::scalar_<R> > + { + typedef L ret; + }; + + template <typename P> + struct set_unary_< op::ord, mln::Index_Site, P > + { + typedef mln::internal::ord_less ret; + }; + + } + + // Index Site category flag type. + template <> + struct Index_Site<void> + { + typedef Site<void> super; + }; + + template <typename E> + struct Index_Site : public Site<E> + { + typedef Index_Site<void> category; + + /* + typedef delta; + typedef index_t; + + const index_t& index() const; + void change_index(const index_t&); + + void dec_index(); + void inc_index(); + + */ + + protected: + Index_Site(); + }; + + // Conversion. + + namespace convert + { + + namespace over_load + { + + template <typename P> + void + from_to_(const Index_Site& from, mln_delta(P)& to); + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + + /// Operators. + /// \{ + template <typename P> + std::ostream& + operator<<(std::ostream& ostr, const Index_Site& dp); + + template <typename L, typename R> + bool operator==(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename L, typename R> + bool operator<(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename P, typename D> + P operator+(const Index_Site& p, const Dindex_Site<D>& dp); + + template <typename P, typename D> + P operator-(const Index_Site& p, const Dindex_Site<D>& dp); + + template <typename P, typename S> + P operator*(const Index_Site& p, const value::scalar_<S>& s); + + template <typename P, typename S> + P operator/(const Index_Site& p, const value::scalar_<S>& s); + + template <typename L, typename R> + mln_delta(L) operator-(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename P, typename D> + P& operator+=(Index_Site& p, const Dindex_Site<D>& dp); + + template <typename P, typename D> + P& operator-=(Index_Site& p, const Dindex_Site<D>& dp); + + template <typename P, typename S> + P& operator*=(Index_Site& p, const value::scalar_<S>& s); + + template <typename P, typename S> + P& operator/=(Index_Site& p, const value::scalar_<S>& s); + + /// \} + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Index_Site<E>::Index_Site() + { + typedef mln_delta(E) delta; + typedef typename E::index_t index_t; + + void (E::*m1)() = & E::inc_index; + m1 = 0; + void (E::*m2)() = & E::dec_index; + m2 = 0; + const index_t& (E::*m3)() const = & E::index; + m3 = 0; + void (E::*m4)(const index_t&) = & E::change_index; + m4 = 0; + } + + namespace convert + { + + namespace over_load + { + + template <typename P> + void + from_to_(const Index_Site& from, mln_delta(P)& to) + { + to.value() = exact(from).index(); + } + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + template <typename P> + std::ostream& + operator<<(std::ostream& ostr, const Index_Site& p) + { + ostr << '(' << debug::format(exact(p).index()) << ')'; + return ostr; + } + + template <typename L, typename R> + bool operator==(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + return exact(lhs).index() == exact(rhs).index(); + } + + template <typename L, typename R> + bool operator<(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + return exact(lhs).index() < exact(rhs).index(); + } + + template <typename P, typename D> + P operator+(const Index_Site& p, const Dindex_Site<D>& dp) + { + P tmp = exact(p); + tmp.change_index(tmp.index() + exact(dp).value()); + return tmp; + } + + template <typename P, typename D> + P operator-(const Index_Site& p, const Dindex_Site<D>& dp) + { + P tmp = exact(p); + tmp.change_index(tmp.index() - exact(dp).value()); + return tmp; + } + + template <typename P, typename S> + P operator*(const Index_Site& p, const value::scalar_<S>& s) + { + S equiv = s.to_equiv(); + P tmp = exact(p); + tmp.change_index(tmp.index() * equiv); + return tmp; + } + + + template <typename P, typename S> + P operator/(const Index_Site& p, const value::scalar_<S>& s) + { + S equiv = s.to_equiv(); + P tmp = exact(p); + tmp.change_index(tmp.index() / equiv); + return tmp; + } + + + template <typename L, typename R> + mln_delta(L) operator-(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + mln_delta(L) delta(exact(lhs).index() - exact(rhs).index()); + mln_postcondition(rhs + delta == lhs); + return delta; + } + + template <typename P, typename D> + P& operator+=(Index_Site& p, const Dindex_Site<D>& dp) + { + exact(p).change_index(exact(p).index() + exact(dp).value()); + return exact(p); + } + + template <typename P, typename D> + P& operator-=(Index_Site& p, const Dindex_Site<D>& dp) + { + exact(p).change_index(exact(p).index() - exact(dp).value()); + return exact(p); + } + + template <typename P, typename S> + P& operator*=(Index_Site& p, const value::scalar_<S>& s) + { + exact(p).change_index(exact(p).index() * s); + return exact(p); + } + + template <typename P, typename S> + P& operator/=(Index_Site& p, const value::scalar_<S>& s) + { + exact(p).change_index(exact(p).index() / s); + return exact(p); + } +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_INDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh (revision 4620) @@ -0,0 +1,253 @@ +// Copyright (C) 2008, 2009 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. + +/// +/// \file +/// +/// Definition of the concept mln::Dindex_Site +/// + +#ifndef MLN_CORE_CONCEPT_DINDEX_SITE_HH +# define MLN_CORE_CONCEPT_DINDEX_SITE_HH + +namespace mln +{ + + // Forward declaration. + template <typename E> struct Dindex_Site; + + + namespace trait + { + + // FIXME: Add promotion. + + template < typename L, typename R > + struct set_binary_< op::plus, + mln::Dindex_Site, L, mln::Dindex_Site, R > + { + typedef L ret; + }; + + template < typename L, typename R > + struct set_binary_< op::minus, + mln::Dindex_Site, L, mln::Dindex_Site, R > + { + typedef L ret; + }; + + template < typename L, typename S> + struct set_binary_< op::plus, + mln::Dindex_Site, L, mln::value::Scalar, S > + { + typedef L ret; + }; + + template < typename L, typename S> + struct set_binary_< op::minus, + mln::Dindex_Site, L, mln::value::Scalar, S > + { + typedef L ret; + }; + + template < typename D, typename S > + struct set_binary_< op::times, + mln::Dindex_Site, D, + mln::value::Scalar, S > + { + typedef D ret; + }; + + template <typename D> + struct set_unary_< op::ord, mln::Dindex_Site, D > + { + typedef mln::internal::ord_less< D > ret; + }; + + } // end of namespace mln::trait + + + + /// Delta point site category flag type. + template <> + struct Dindex_Site<void> + { + typedef Object<void> super; + }; + + + /// FIXME: Doc! + template <typename E> + struct Dindex_Site : public Object<E> + { + typedef Dindex_Site<void> category; + + /* + typedef value_t; + typedef site; + typedef psite; + + const value_t& value(); + void change_value(const value_t&); + */ + + protected: + Dindex_Site(); + }; + + + + // Operators. + + template <typename D> + std::ostream& + operator<<(std::ostream& ostr, const Dindex_Site<D>& dp); + + template <typename L, typename R> + bool + operator==(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + + template <typename L, typename R> + L operator+(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + template <typename L, typename R> + L operator-(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + template <typename L, typename S> + L operator+(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs); + + template <typename L, typename S> + L operator-(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs); + + template <typename D, typename S> + D operator*(const Dindex_Site<D>& lhs, const value::Scalar<S>& rhs); + + + namespace convert + { + + namespace over_load + { + + template <typename D> + void + from_to_(const Dindex_Site<D>& from, mln_site(D)& to); + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Dindex_Site<E>::Dindex_Site() + { + typedef typename E::value_t value_t; + const value_t& (E::*m)() const = & E::value; + m = 0; + } + + + template <typename D> + inline + std::ostream& operator<<(std::ostream& ostr, const Dindex_Site<D>& dp) + { + ostr << '(' << debug::format(exact(dp).value()) << ')'; + return ostr; + } + + + template <typename L, typename R> + inline + bool operator==(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + return exact(lhs).value() == exact(rhs).value(); + } + + template <typename L, typename R> + inline + L operator+(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + L tmp(exact(lhs).value() + exact(rhs).value()); + return tmp; + } + + template <typename L, typename R> + inline + L operator-(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + L tmp(exact(lhs).value() - exact(rhs).value()); + return tmp; + } + + template <typename L, typename S> + inline + L operator+(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs) + { + L tmp(exact(lhs).value() + exact(rhs).to_equiv()); + return tmp; + } + + template <typename L, typename S> + inline + L operator-(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs) + { + L tmp(exact(lhs).value() - exact(rhs).to_equiv()); + return tmp; + } + + template <typename D, typename S> + D operator*(const Dindex_Site<D>& lhs, const value::Scalar<S>& rhs) + { + D tmp(exact(lhs).value() * exact(rhs).to_equiv()); + return tmp; + } + + namespace convert + { + + namespace over_load + { + + template <typename D> + inline + void + from_to_(const Dindex_Site<D>& dp, mln_site(D)& p) + { + p.change_index(exact(dp).value()); + } + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_DINDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/tree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/tree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/tree.hh (revision 4620) @@ -0,0 +1,148 @@ +// Copyright (C) 2008, 2009 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 MLN_CORE_CONCEPT_TREE_HH +# define MLN_CORE_CONCEPT_TREE_HH + +# include <mln/core/concept/object.hh> + +namespace mln +{ + + // Forward declaration. + template <typename E> struct Tree; + + // Tree category flag type. + template <> + struct Tree<void> + { + typedef Object<void> super; + }; + + template <typename E> + struct Tree : public Object<E> + { + typedef Tree<void> category; + + /* + // Original image related + typedef site; + typedef psite; + + typedef value; + typedef rvalue; + typedef lvalue; + + // Node/Site related material. + typedef domain_t; + const domain_t& domain() const; + + typedef nodes_t; + const nodes_t& nodes() const; + + bool has(const node_t&) const; + bool has(const psite&) const; + + // Value related material. + rvalue f() (const psite&) const; + lvalue f() (const psite&); + rvalue f[] (const node_t&) const; + lvalue f[] (const node_t&); + + // Node relationship. + node_t node(const psite&) const; + void set_node(const psite&, const node_t&); + node_t parent(const node_id_t&) const; + void set_parent(const node_t&, const node_t&); + + // Node test materials + bool is_a_leaf(const node_t&) const; + bool is_a_root(const node_t&) const; + */ + + protected: + Tree(); + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Tree<E>::Tree() + { + typedef mln_site(E) site; + typedef mln_psite(E) psite; + + typedef mln_value(E) value; + typedef mln_rvalue(E) rvalue; + typedef mln_lvalue(E) lvalue; + + typedef typename E::node_t node_t; + + // Site/Node related material. + typedef mln_domain(E) domain_t; + typedef typename E::nodes_t nodes_t; + + const domain_t& (E::*m1)() const = & E::domain; + m1 = 0; + const nodes_t& (E::*m2)() const = & E::nodes; + m2 = 0; + bool (E::*m3)(const node_t&) const = & E::has; + m3 = 0; + bool (E::*m4)(const psite&) const = & E::has; + m4 = 0; + + // Value related material. + rvalue (E::*m5)(const psite&) const = & E::f; + m5 = 0; + lvalue (E::*m6)(const psite&) = & E::f; + m6 = 0; + rvalue (E::*m7)(const node_t&) const = & E::f; + m7 = 0; + lvalue (E::*m8)(const node_t&) = & E::f; + m8 = 0; + + // Node relationship. + node_t (E::*m9)(const psite&) const = & E::node; + m9 = 0; + void (E::*m10)(const psite&, const node_t&) = & E::set_node; + m10 = 0; + node_t (E::*m11)(const node_t&) const = & E::parent; + m11 = 0; + void (E::*m12)(const node_t&, const node_t&) = & E::set_parent; + m12 = 0; + + // Node tests + bool (E::*m13)(const node_t&) const = & E::is_a_leaf; + m13 = 0; + bool (E::*m14)(const node_t&) const = & E::is_a_root; + m14 = 0; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_TREE_HH Index: trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh (revision 4620) @@ -0,0 +1,254 @@ +// Copyright (C) 2008, 2009 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 MLN_CORE_INTERNAL_INDEX_SITE_BASE_HH +# define MLN_CORE_INTERNAL_INDEX_SITE_BASE_HH + +# include <mln/core/concept/index_site.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/value/concept/integer.hh> + +namespace mln +{ + /// \{ Forward declarations. + namespace literal + { + struct zero_t; + struct one_t; + } + + template <typename E> struct dindex_site; + /// \} + + + namespace internal + { + + template <typename E> struct index_site_base; + + template <typename E = void> + struct index_site_base : public Index_Site<E> + { + typedef index_site_base<E> self; + + typedef index_site_base<E> site; + typedef index_site_base<E> psite; + + typedef dindex_site<E> delta; + typedef dindex_site<E> dpsite; + + typedef unsigned index_t; + + /// Constructors + /// \{ + index_site_base(); + explicit index_site_base(unsigned i); + index_site_base(const literal::zero_t&); + index_site_base(const literal::one_t&); + /// \} + + /// Index materials + /// \{ + /// Return the current index. + const index_t& index() const; + /// Change the current index. + void change_index(const index_t&); + /// Increment the current index. + void inc_index(); + /// Decrement the current index. + void dec_index(); + /// \} + + /// Operators + /// \{ + self& operator+= (const delta&); + self& operator-= (const delta&); + /// \} + + protected: + index_t i_; + }; + + + /// subject_impl specialization (Proxy) + /// \{ + + template <typename P, typename E> + struct subject_impl< const index_site_base, E > + { + //const typename index_site_base::index_t& index() const; + + private: + const E& exact_() const; + }; + + template <typename P, typename E> + struct subject_impl< index_site_base, E > : + subject_impl< const index_site_base, E > + { + //void change_index(const typename index_site_base::index_t& idx); + void inc_index(); + void dec_index(); + + private: + E& exact_(); + }; + + /// \} + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + index_site_base<E>::index_site_base() + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(unsigned i) + : i_ (i) + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(const literal::zero_t&) + : i_ (0) + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(const literal::one_t&) + : i_ (1) + { + } + + template <typename E> + inline + const typename index_site_base<E>::index_t& + index_site_base<E>::index() const + { + return i_; + } + + template <typename E> + inline + void + index_site_base<E>::dec_index() + { + --i_; + } + + template <typename E> + inline + void + index_site_base<E>::inc_index() + { + ++i_; + } + + + template <typename E> + inline + void + index_site_base<E>::change_index(const index_t& idx) + { + i_ = idx; + } + + template <typename E> + inline + index_site_base<E>& + index_site_base<E>::operator+=(const delta& dp) + { + i_ += dp.value(); + return *this; + } + + template <typename E> + inline + index_site_base<E>& + index_site_base<E>::operator-=(const delta& dp) + { + mln_precondition(dp.value() >= i_); + i_ -= dp.value(); + return *this; + } + + + template <typename P, typename E> + const E& + subject_impl< const index_site_base, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename P, typename E> + E& + subject_impl< index_site_base, E >::exact_() + { + return internal::force_exact<E>(*this); + } + + // template <typename P, typename E> + // const typename index_site_base::index_t& + // subject_impl< const index_site_base, E >::index() const + // { + // return exact_().get_subject().index(); + // } + + // template <typename P, typename E> + // void + // subject_impl< index_site_base, E >::change_index(const typename index_site_base::index_t& idx) + // { + // return exact_().get_subject().change_index(idx); + // } + + template <typename P, typename E> + void + subject_impl< index_site_base, E >::inc_index() + { + return exact_().get_subject().inc_index(); + } + + template <typename P, typename E> + void + subject_impl< index_site_base, E >::dec_index() + { + return exact_().get_subject().dec_index(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::internal + +} // end of namespace mln + +# include <mln/core/dindex_site.hh> + +#endif // !MLN_CORE_INDEX_SITE_BASE_HH Index: trunk/milena/sandbox/edwin/mln/core/dindex_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/dindex_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/dindex_site.hh (revision 4620) @@ -0,0 +1,119 @@ +// Copyright (C) 2008, 2009 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 MLN_CORE_DINDEX_SITE_HH +# define MLN_CORE_DINDEX_SITE_HH + +# include <mln/core/concept/index_site.hh> +# include <mln/core/concept/dindex_site.hh> + +namespace mln +{ + /// \{ Forward declarations. + namespace literal { + struct zero_t; + struct one_t; + } + /// \} + + + template <typename P> struct dindex_site; + + template <typename P> + struct dindex_site : public Dindex_Site< dindex_site > + { + typedef P site; + typedef P psite; + + typedef int value_t; + + /// Constructors + /// \{ + dindex_site(); + dindex_site(int i); + dindex_site(const literal::zero_t&); + dindex_site(const literal::one_t&); + /// \} + + /// Value access + /// \{ + const value_t& value() const; + void change_value(const value_t& v); + /// \} + + protected: + value_t v_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + dindex_site::dindex_site() + { + } + + template <typename P> + inline + dindex_site::dindex_site(int i) + : v_ (i) + { + } + + template <typename P> + inline + dindex_site::dindex_site(const literal::zero_t&) + : v_ (0) + { + } + + template <typename P> + inline + dindex_site::dindex_site(const literal::one_t&) + : v_ (1) + { + } + + template <typename P> + inline + const typename dindex_site::value_t& + dindex_site::value() const + { + return v_; + } + + template <typename P> + inline + void + dindex_site::change_value(const value_t& v) + { + v_ = v; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_DINDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh (revision 4620) @@ -0,0 +1,589 @@ +// Copyright (C) 2008, 2009 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. + +/// FIXME: because there're some stuffs not enough clear... +/// In the previous implementation of the morpho tree, the site set and +/// the domain set had the same type, so that +/// E(nodes) is included in E(sites). In fact, (I think) that's a +/// mistake that comes from the representation using parent image. For +/// real, the tree can be considered as a triplet (node_set, function, +/// relationship) (N, F, R) such that F: node -> (site_set, value) and +/// R: parent node -> node and N: the node set. +/// +/// Currently, the node type is not a site but it should +/// be. And so, the set of nodes: nodes_t < Site_Set. +/// We should implement (but I don't know how to make it well) the type +/// Attribute_image < Image that have two kind of sites +/// (node and site of the original image) with +/// overloaded operator(): node -> value +/// mln_psite(nodes_t) -> value +/// +/// + +/// The differences and what they imply. +/// Attribute_image a; Tree t +/// Node_Set nodes; Site_Set s; +/// +/// I'd like to be able to write: +/// a | (subset of t.nodes) as whell as a | (subset of t.domain()) + +// \todo definition of site, psite is ambigous, replace with content_t +// or other. +// \todo node operator ? + + + +#ifndef MLN_UTIL_CTREE_CTREE_HH +# define MLN_UTIL_CTREE_CTREE_HH + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/site_set.hh> +# include <mln/util/ctree/internal/tree_base.hh> +# include <algorithm> + +namespace mln +{ + + /// Forward declaration. + namespace util { namespace ctree { template <typename I> class ctree; } } + + namespace internal + { + /// Data structure for component tree. + template <> + template <typename I> + struct data< util::ctree::ctree > + { + typedef util::ctree::ctree T; + typedef typename T::node_t::index_t index_t; + + data(const I&); + ~data(); + + mln_ch_value(I, index_t) map_; + std::vector<index_t> parent_; + std::vector<unsigned> n_nodes_; + std::vector<mln_value(I)> values_; + + const mln_domain(I)& domain_; + typename T::nodes_t nodes_; + }; + + } // end of namespace mln::internal + + namespace util + { + + namespace ctree + { + + template <typename I> + struct ctree : public internal::tree_base< I, ctree > + { + /// The super class. + typedef internal::tree_base<I, ctree > super; + + /// Site related type definitions. + /// \{ + /// The type of site. + typedef mln_site(I) site; + /// The type of pseudo-site. + typedef mln_psite(I) psite; + /// The type of domain. + typedef mln_domain(I) domain_t; + /// \} + + /// Node related type definions. + /// \{ + /// The type of node. + typedef typename super::node_t node_t; + /// The type of node set. + typedef typename super::nodes_t nodes_t; + /// \} + + /// Node/Site value related type definitions. + /// \{ + /// The type of node value + typedef mln_value(I) value; + /// The type of node rvalue. + typedef mln_rvalue(I) rvalue; + /// The type of node lvalue. + typedef mln_lvalue(I) lvalue; + /// \} + + /// Constructors + /// \{ + ctree(); + + /// Constructor from union-find results. + /// \param[in] f The input image. + /// \param[in] parent The (not necessary canonized) parent image. + /// \param[in] area The number of nodes in each sub-tree. + /// \param[in] s The sorted site set. + /// \param[in] nb_nodes The total number of nodes. + template <typename S> + ctree(const Image& f, + const Site_Set<S>& s, + mln_ch_value(I, psite)& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes); + /// \} + + /// Misc. + /// \{ + const domain_t& domain() const; + const nodes_t& nodes() const; + bool has(const psite&) const; + bool has(const node_t&) const; + unsigned n_nodes() const; + /// \} + + /// Value access material. + /// \{ + rvalue f(const psite&) const; + lvalue f(const psite&); + rvalue f(const node_t&) const; + lvalue f(const node_t&); + /// \} + + /// Node relationship material. + /// \{ + node_t node(const psite&) const; + void set_node(const psite&, const node_t&); + node_t parent(const node_t&) const; + void set_parent(const node_t& n, const node_t& parent); + + /// Return the node set of the sub-tree of \p n. + nodes_t desc(const node_t& n) const; + /// Return the node set of ancestors of \p n. + nodes_t anc(const node_t& n) const; + /// \} + + /// Node tests material. + /// \{ + bool is_a_leaf(const node_t&) const; + bool is_a_root(const node_t&) const; + /// \} + + /// Fast access material. + /// \{ + bool has_index(unsigned i) const; + rvalue f_at_(unsigned i) const; + lvalue f_at_(unsigned i); + unsigned parent_at_(unsigned i) const; + unsigned& parent_at_(unsigned i); + unsigned node_at_(const psite& p) const; + unsigned& node_at_(const psite& p); + /// \} + + /// To attribute image + attribute_image<ctree, value> to_image() const; + + /// Site -> node function. + /// \{ + /// Return the map Site -> Node as a V2V function. + //pw::value< mln_ch_value(I, node_t) > mapper() const; + /// \} + + }; + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + inline + data< util::ctree::ctree >::data(const I& f) + : domain_ (f.domain()) + { + } + + template <typename I> + inline + data< util::ctree::ctree >::~data() + { + } + + } // end of namespace mln::internal + + namespace util + { + + namespace ctree + { + namespace internal + { + template <typename T> + struct create_node : Function_v2v< create_node<T> > + { + typedef typename T::index_t param; + typedef typename T::node_t result; + + create_node(const T& tree) + : tree_ (tree) + { + } + + result + operator()(const param& idx) const + { + result tmp(tree_, idx); + return tmp; + } + + private: + const T& tree_; + }; + } + + + template <typename I> + inline + ctree::ctree() + { + } + + template <typename I> + template <typename S> + inline + ctree::ctree(const Image& f_, + const Site_Set<S>& s_, + mln_ch_value(I, mln_psite(I))& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes) + { + const I& f = exact(f_); + const S& s = exact(s_); + + mln_precondition(f.is_valid()); + mln_precondition(s.is_valid()); + mln_precondition(parent.is_valid()); + mln_precondition(area.is_valid()); + mln_precondition(f.domain() == parent.domain()); + mln_precondition(f.domain() == area.domain()); + mln_precondition(f.domain().nsites() == s.nsites()); + + this->data_ = new mln::internal::data< ctree >(f); + + initialize(this->data_->map_, f); + this->data_->parent_.resize(nb_nodes); + this->data_->n_nodes_.resize(nb_nodes); + this->data_->values_.resize(nb_nodes); + this->data_->nodes_.init(node_t(*this, 0), nb_nodes); + + //debug::println("Parent: ", parent); + //debug::println("Area: ", area); + + unsigned root_offset = 0; + mln_fwd_piter(S) p(s); + for_all(p) + { + psite q = parent(p); + + if (f(parent(q)) == f(q)) // Canonization + q = (parent(p) = parent(q)); + + if (f(p) == f(q) && p != q) // Not a node. + { + this->data_->map_(p) = this->data_->map_(parent(p)); + } + else + { + unsigned& offset = (p == q) ? root_offset : area(q); + + // Insert Node. + mln_assertion(offset < nb_nodes); + this->data_->map_(p) = offset; + this->data_->parent_[offset] = this->data_->map_(q); + this->data_->values_[offset] = f(p); + this->data_->n_nodes_[offset] = area(p); + area(p) = offset + 1; + offset += this->data_->n_nodes_[offset] + 1; + } + } + } + + + template <typename I> + inline + const mln_domain(I)& + ctree::domain() const + { + return this->data_->domain_; + } + + template <typename I> + inline + const typename ctree::nodes_t& + ctree::nodes() const + { + return this->data_->nodes_; + } + + template <typename I> + inline + unsigned + ctree::n_nodes() const + { + mln_precondition(this->is_valid()); + return this->data_->nodes_.nsites(); + } + + template <typename I> + inline + bool + ctree::has(const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + return this->data_->domain_.has(p); + } + + template <typename I> + inline + bool + ctree::has(const node_t& n) const + { + mln_precondition(this->is_valid()); + return n.index() < this->data_->nodes_.nsites(); + } + + template <typename I> + inline + mln_rvalue(I) + ctree::f (const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + return this->data_->values_[this->data_->map_(p)]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree::f (const mln_psite(I)& p) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + return this->data_->values_[this->data_->map_(p)]; + } + + template <typename I> + inline + mln_rvalue(I) + ctree::f (const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree::f (const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename I> + inline + typename ctree::node_t + ctree::node(const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + node_t tmp(*this, this->data_->map_(p)); + mln_postcondition(this->has(tmp)); + return tmp; + } + + template <typename I> + inline + void + ctree::set_node(const mln_psite(I)& p, const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_precondition(this->has(n)); + this->data_->map_(p) = n.index(); + } + + + template <typename I> + inline + typename ctree::node_t + ctree::parent(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + node_t tmp(*this, this->data_->parent_[n.index()]); + mln_postcondition(tmp.index() < n.index()); + return tmp; + } + + template <typename I> + inline + void + ctree::set_parent(const node_t& n, const node_t& parent) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + mln_precondition(this->has(parent)); + this->data_->parent_[n.index()] = parent.index(); + } + + template <typename I> + inline + typename ctree::nodes_t + ctree::desc(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + nodes_t tmp(n, this->data_->n_nodes_[n.index()] + 1); + return tmp; + } + + template <typename I> + inline + bool + ctree::is_a_root(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return (this->data_->parent_[n.index()] == n.index()); + } + + template <typename I> + inline + bool + ctree::is_a_leaf(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return (this->data_->n_nodes_[n.index()] == 0); + } + + template <typename I> + inline + bool + ctree::has_index(unsigned i) const + { + mln_precondition(this->is_valid()); + return i <= this->n_nodes(); + } + + template <typename I> + inline + mln_rvalue(I) + ctree::f_at_(unsigned i) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->values_[i]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree::f_at_(unsigned i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->values_[i]; + } + + template <typename I> + inline + unsigned + ctree::parent_at_(unsigned i) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + mln_postcondition(this->has_index(this->data_->parent_[i])); + return this->data_->parent_[i]; + } + + template <typename I> + inline + unsigned& + ctree::parent_at_(unsigned i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + mln_postcondition(this->has_index(this->data_->parent_[i])); + return this->data_->parent_[i]; + } + + template <typename I> + inline + unsigned + ctree::node_at_(const psite& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_postcondition(this->has_index(this->data_->map_(p))); + return this->data_->map_(p); + } + + template <typename I> + inline + unsigned& + ctree::node_at_(const psite& p) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_postcondition(this->has_index(this->data_->map_(p))); + return this->data_->map_(p); + } + + template <typename I> + inline + attribute_image<ctree, mln_value(I)> + ctree::to_image() const + { + mln_precondition(this->is_valid()); + + attribute_image<ctree, value> to(*this); + std::copy(this->data_->values_.begin(), this->data_->values_.end(), to.buffer()); + return to; + } + + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_CTREE_HH Index: trunk/milena/sandbox/edwin/mln/util/ctree/node.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/node.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/node.hh (revision 4620) @@ -0,0 +1,183 @@ +// Copyright (C) 2008, 2009 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 MLN_UTIL_CTREE_NODE_HH +# define MLN_UTIL_CTREE_NODE_HH + +# include <mln/core/internal/index_site_base.hh> + +namespace mln +{ + + /// Node category flag type. + template <typename E> struct Node {}; + + template <> + struct Node<void> + { + typedef Index_Site<void> super; + }; + + namespace util + { + + namespace ctree + { + + template <typename T> + class node : public internal::index_site_base< node<T> > + { + public: + /// Object category. + typedef Node<void> category; + + typedef internal::index_site_base<node> super; + + typedef typename super::index_t index_t; + + /// Constructors + /// \{ + node(); + node(const Tree<T>& tree); + node(const Tree<T>& tree, const index_t& id); + /// \} + + /// Return whether the node is valid. + const T& tree() const; + void change_target(const Tree<T>& tree); + + private: + const T* tree_; + }; + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + + namespace internal + { + + /// subject_impl specialization (Proxy) + /// \{ + + template <typename T, typename E> + struct subject_impl< const util::ctree::node<T>, E > : + subject_impl< const internal::index_site_base< util::ctree::node<T> > , E > + { + const T& tree() const; + + private: + const E& exact_() const; + }; + + template <typename T, typename E> + struct subject_impl< util::ctree::node<T>, E > : + subject_impl< const util::ctree::node<T>, E >, + subject_impl< internal::index_site_base< util::ctree::node<T> > , E > + { + }; + + /// \} + + } // end of namespace mln::internal + +# ifndef MLN_INCLUDE_ONLY + + namespace util + { + + namespace ctree + { + + template <typename T> + inline + node<T>::node() + : tree_ (0) + { + } + + template <typename T> + inline + node<T>::node(const Tree<T>& tree) + : tree_ (&(exact(tree))) + { + } + + + template <typename T> + inline + node<T>::node(const Tree<T>& tree, const index_t& i) + : super(i), + tree_ (&(exact(tree))) + { + } + + template <typename T> + inline + const T& + node<T>::tree() const + { + return tree_; + } + + template <typename T> + inline + void + node<T>::change_target(const Tree<T>& tree) + { + tree_ = &(exact(tree)); + } + + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + + namespace internal + { + + template <typename T, typename E> + inline + const E& + subject_impl< const util::ctree::node<T>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename T, typename E> + inline + const T& + subject_impl< const util::ctree::node<T>, E >::tree() const + { + return exact_().get_subject().tree(); + } + + } // end of namespace mln::internal + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_NODE_HH Index: trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh (revision 4620) @@ -0,0 +1,140 @@ +// Copyright (C) 2008, 2009 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 MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH +# define MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH + +# include <mln/core/concept/object.hh> +# include <mln/core/concept/tree.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/core/internal/data.hh> + +# include <mln/core/site_set/p_run_idx.hh> + +# include <mln/util/ctree/node.hh> +# include <mln/util/tracked_ptr.hh> + +namespace mln +{ + + namespace util + { + + namespace ctree + { + + namespace internal + { + + template <typename I, typename E> + class tree_base : public Tree<E> + { + public: + /// Site related type definitions. + /// \{ + /// The type of site. + typedef mln_site(I) site; + /// The type of pseudo-site. + typedef mln_psite(I) psite; + /// The type of domain. + typedef mln_domain(I) domain_t; + /// \} + + /// Node related type definions. + /// \{ + /// The type of the node. + typedef ctree::node<E> node_t; + /// The type of node set. + typedef p_run_idx<node_t> nodes_t; + /// \} + + /// Node/Site value related type definitions. + /// \{ + /// The type of node value + typedef mln_value(I) value; + /// The type of node rvalue. + typedef mln_rvalue(I) rvalue; + /// The type of node lvalue. + typedef mln_lvalue(I) lvalue; + /// \} + + /// Check validity. + bool is_valid() const; + void invalidate(); + + /// Hook to data; for debugging purpose. + const util::tracked_ptr< mln::internal::data<E> >& data_hook_() const; + + public: // Tmp for construction. + util::tracked_ptr< mln::internal::data<E> > data_; + protected: + tree_base(); + }; + +# ifndef MLN_INCLUDE_ONLY + + template<typename I, typename E> + inline + tree_base<I,E>::tree_base() + : data_ (0) + { + } + + template <typename I, typename E> + inline + bool + tree_base<I,E>::is_valid() const + { + return data_ != 0; + } + + template <typename I, typename E> + inline + void + tree_base<I,E>::invalidate() + { + data_.clean_(); + } + + template<typename I, typename E> + inline + const util::tracked_ptr< mln::internal::data<E> >& + tree_base<I,E>::data_hook_() const + { + return data_; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util::ctree::internal + + } // end of namespace mln::util::ctree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH

1 0

[PATCH 4/4] Fix a precondition in apps/graph-morpho.
by Roland Levillain 06 Oct '09

06 Oct '09

* apps/graph-morpho/morpho.hh (combine): Check the exact images, not the abstract ones. --- milena/ChangeLog | 7 +++++++ milena/apps/graph-morpho/morpho.hh | 6 ++++-- 2 files changed, 11 insertions(+), 2 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index a308bc3..7178936 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,12 @@ 2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Fix a precondition in apps/graph-morpho. + + * apps/graph-morpho/morpho.hh (combine): Check the exact images, + not the abstract ones. + +2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Fix the instruction flow in multiple_qiter<W,F>::change_target. * mln/win/multiple.hh (mln::win::multiple_qiter<W,F>::change_target): diff --git a/milena/apps/graph-morpho/morpho.hh b/milena/apps/graph-morpho/morpho.hh index 5aaecae..2288995 100644 --- a/milena/apps/graph-morpho/morpho.hh +++ b/milena/apps/graph-morpho/morpho.hh @@ -177,13 +177,15 @@ namespace trait template <typename I> inline mln_concrete(I) -combine(const mln::Image& vertices, const mln::Image& edges) +combine(const mln::Image& vertices_, const mln::Image& edges_) { typedef trait::graph T; + const I& vertices = mln::exact(vertices_); + const I& edges = mln::exact(edges_); mln_precondition(vertices.domain() == edges.domain()); mln_concrete(I) output; - mln::initialize(output, exact(vertices)); + mln::initialize(output, vertices); mln::data::fill(output, false); mln::data::paste(vertices | T::is_vertex(), output); mln::data::paste(edges | T::is_edge(), output); -- 1.6.3.1

1 0

[PATCH 3/4] Fix the instruction flow in multiple_qiter<W, F>::change_target.
by Roland Levillain 06 Oct '09

06 Oct '09

* mln/win/multiple.hh (mln::win::multiple_qiter<W,F>::change_target): Set the size before delegating the call to the base class, so that postconditions can be honored. --- milena/ChangeLog | 8 ++++++++ milena/mln/win/multiple.hh | 2 +- 2 files changed, 9 insertions(+), 1 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 4caaa0a..a308bc3 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,13 @@ 2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Fix the instruction flow in multiple_qiter<W,F>::change_target. + + * mln/win/multiple.hh (mln::win::multiple_qiter<W,F>::change_target): + Set the size before delegating the call to the base class, so that + postconditions can be honored. + +2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Honor strict-aliasing rules in memset_. * mln/data/memset_.hh (mln::data::impl::memset): Here. diff --git a/milena/mln/win/multiple.hh b/milena/mln/win/multiple.hh index a12bf83..18b65c8 100644 --- a/milena/mln/win/multiple.hh +++ b/milena/mln/win/multiple.hh @@ -340,8 +340,8 @@ namespace mln void multiple_qiter<W,F>::change_target(const multiple<W,F>& w) { - this->super_::change_target(w); size_ = w.size(); + this->super_::change_target(w); } template <typename W, typename F> -- 1.6.3.1

1 0

[PATCH 2/4] Honor strict-aliasing rules in memset_.
by Roland Levillain 06 Oct '09

06 Oct '09

* mln/data/memset_.hh (mln::data::impl::memset): Here. --- milena/ChangeLog | 6 ++++++ milena/mln/data/memset_.hh | 16 ++++++++++++---- 2 files changed, 18 insertions(+), 4 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index fc516e7..4caaa0a 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,11 @@ 2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Honor strict-aliasing rules in memset_. + + * mln/data/memset_.hh (mln::data::impl::memset): Here. + +2009-10-06 Roland Levillain <roland(a)lrde.epita.fr> + Warn about a bug in memcpy_ with g++ 4.2 on Debian for IA-32. * mln/data/memcpy_.hh (mln::data::impl::memcpy_): Here. diff --git a/milena/mln/data/memset_.hh b/milena/mln/data/memset_.hh index 4559e05..42b1412 100644 --- a/milena/mln/data/memset_.hh +++ b/milena/mln/data/memset_.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2007, 2008, 2009 EPITA Research and Development +// Laboratory (LRDE) // // This file is part of Olena. // @@ -101,9 +102,16 @@ namespace mln if (sizeof(mln_value(I)) == 1) { - std::memset((void*)(& pix.val()), - *(const int*)(&v), // violent cast - n); + /* Because of strict-aliasing rules, we cannot use + + *(const int*)(&v) + + as second argument for std::memset. Hence the use of + std::memcpy. See the `-fstrict-aliasing' entry in GCC's + documentation for more information. */ + char c; + std::memcpy(&c, &v, 1); + std::memset((void*)(& pix.val()), c, n); } else { -- 1.6.3.1

1 0