* green/mln : New dev directory. * green/mln/clustering : New directory. * green/mln/clustering/k_mean.hh : New k_mean source location. * green/tests : New unitary test directory. * green/tests/clustering : New directory. * green/tests/clustering/k_mean : New k_mean test directory. * green/tests/clustering/k_mean/Makefile.am: New makefle. * green/tests/clustering/k_mean/k_mean.cc : New unit tests location. --- trunk/milena/sandbox/ChangeLog | 13 + .../milena/sandbox/green/mln/clustering/k_mean.hh | 672 ++++++++++++++++++++ .../green/tests/clustering/k_mean/Makefile.am | 148 +++++ .../green/tests/clustering/k_mean/k_mean.cc | 450 +++++++++++++ 4 files changed, 1283 insertions(+), 0 deletions(-) create mode 100644 trunk/milena/sandbox/green/mln/clustering/k_mean.hh create mode 100644 trunk/milena/sandbox/green/tests/clustering/k_mean/Makefile.am create mode 100644 trunk/milena/sandbox/green/tests/clustering/k_mean/k_mean.cc diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index ed708ca..b0d54dd 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,3 +1,16 @@ +2009-09-07 Yann Jacquelet &lt;jacquelet(a)lrde.epita.fr&gt; + + Do some refactoring for best future olena integration. + + * green/mln : New dev directory. + * green/mln/clustering : New directory. + * green/mln/clustering/k_mean.hh : New k_mean source location. + * green/tests : New unitary test directory. + * green/tests/clustering : New directory. + * green/tests/clustering/k_mean : New k_mean test directory. + * green/tests/clustering/k_mean/Makefile.am: New makefle. + * green/tests/clustering/k_mean/k_mean.cc : New unit tests location. + 2009-09-07 Fabien Freling &lt;fabien.freling(a)lrde.epita.fr&gt; Fix output dimensions. diff --git a/trunk/milena/sandbox/green/mln/clustering/k_mean.hh b/trunk/milena/sandbox/green/mln/clustering/k_mean.hh new file mode 100644 index 0000000..db3f34c --- /dev/null +++ b/trunk/milena/sandbox/green/mln/clustering/k_mean.hh @@ -0,0 +1,672 @@ +// 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_CLUSTERING_K_MEAN_HH +#define MLN_CLUSTERING_K_MEAN_HH + +/// \file +/// +/// \brief Implements the K MEAN algorithm. +/// DO +/// - ASSIGNEMENT STEP +/// - UPDATE STEP +/// LOOP UNTIL CONVERGENCE +/// +/// ASSIGNEMENT STEP +/// BEGIN +/// - COMPUTE THE DISTANCE MATRIX FROM POINTS TO CENTERS +/// - COMPUTE GROUP MATRIX WHERE EACH POINT IS ASSIGNED TO NEAREST CENTER +/// END +/// +/// UPDATE STEP +/// BEGIN +/// - COMPUTE THE MEAN OF THE GROUPS WHICH ARE THE NEW CENTERS +/// END + +#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/algebra/mat.hh> +#include <mln/algebra/vec.hh> + +#include <mln/math/min.hh> +#include <mln/norm/l2.hh> + +#include <mln/core/concept/image.hh> +#include <mln/core/macros.hh> + +namespace mln +{ + + namespace clustering + { + + // Forward declaration. + template <unsigned n, unsigned k, unsigned p, typename T> + struct k_mean; + + } // end of namespace mln::clustering + + namespace clustering + { + + // + // PARAM : DIM VECTOR, NUMBER OF CLASSES + // INPUT : MATRIX 1..N (SAMPLE) + // WORK + // + + // n is the size of the sample. + // k is the number of centers. + // p is the number of attributes for a point. + // T is the type for computations. + template <unsigned n, unsigned k, unsigned p, typename T> + struct k_mean + { + + //------------------------------------------------------------------------ + // Constructor and destructor + //------------------------------------------------------------------------ + + k_mean(); + ~k_mean(); + + + //------------------------------------------------------------------------ + // Accessors + //------------------------------------------------------------------------ + + algebra::mat<n, p, T>& get_point(); + algebra::mat<k, p, T>& get_center(); + algebra::mat<n, k, T>& get_distance(); + algebra::mat<n, k, T>& get_group(); + algebra::vec<k, T>& get_variance(); + + + //------------------------------------------------------------------------ + // Tools + //------------------------------------------------------------------------ + + + /// \brief Return the euclidian distance beetween vector x and vector y. + /// + /// Compute the f$\sqrt(\sum_{i=0}^P ((x_i - y_i)^2)$f + /// + /// \param[in] x a vector of dimension 1xP. + /// \param[in] y a second vector of dimension 1xP. + /// \return the distance between x and y. + + mln_sum_product(T,T) euclidian_distance(const algebra::vec<p,T>& x, + const algebra::vec<p,T>& y) const; + + /// \brief Return the ith column. + /// + /// \param[in] m a matrix of dimension {N or K}xP. + /// \return the ith column as a vector of dimension 1xP. + + + /// \brief Return the ith column. + /// + /// \param[in] m a matrix of dimension {N or K}xP. + /// \return the ith column as a vector of dimension 1xP. + template <unsigned q, unsigned r> + algebra::vec<q,T> col(const algebra::mat<r, q, T>& m, + const unsigned _col) const; + + template <unsigned q, unsigned r> + algebra::vec<q,T>* ptr_col(const algebra::mat<r, q, T>& m, + const unsigned _col) const; + + template <unsigned q, unsigned r> + algebra::vec<r,T> row(const algebra::mat<r, q, T>& m, + const unsigned _row) const; + + template <unsigned q, unsigned r> + void div_col(algebra::mat<r, q, T>& m, + const unsigned _col, + const T value); + + template <unsigned q, unsigned r> + mln_sum(T) sum_row(const algebra::mat<r, q, T>& m, + const unsigned _row) const; + + template <unsigned q, typename M> + M min_col(const algebra::vec<q, M>& x) const; + + + //------------------------------------------------------------------------ + // Initializations of points and centers + //------------------------------------------------------------------------ + + /// \brief Initialize the matrix _point with the pixels of an image. + /// + /// \param[in] input an image which contains the data points. + template <typename I> + void init_point(const Image<I>& _input); + void init_center(); + + + //------------------------------------------------------------------------ + // Computations of distance, group, center, within variance + //------------------------------------------------------------------------ + + void update_distance(); + void update_group(); + void update_center(); + T update_variance(); + + + //------------------------------------------------------------------------ + // Main loop + //------------------------------------------------------------------------ + + template <typename I> + void loop(const Image<I>& _input); + //void loop(); + + private: + static const unsigned watch_dog = 100; + + /// \brief _points contains the concatenation of every data points. + /// + /// One data point is a vector 1xP where P is the number of attributes. + /// _points is a matrix NxP where N is the number of data points. + algebra::mat<n, p, T>* _point; + + /// \brief _distance contains all the euclidian distances between points + /// and the centers. + /// + /// _distance is a matrix NxK where N is the number of data points and + /// K the number of centers. + algebra::mat<n, k, mln_sum_product(T,T)>* _distance; + + /// \brief _group contains the point assignement to one center. + /// + /// _group is a boolean matrix NxK where N is the number of data points + /// and K the number of centers. + algebra::mat<n, k, T>* _group; + + /// \brief _center contains the coordonnate of the K centers. + /// + /// _center is a matrix KxP where K is the number of centers and P is the + /// number of attributes. + algebra::mat<k, p, T>* _center; + + algebra::vec<k, T>* _variance; + }; + +#ifndef MLN_INCLUDE_ONLY + + //-------------------------------------------------------------------------- + // Constructor and destructor + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + k_mean<n,k,p,T>::k_mean() + { + trace::entering("mln::clustering::k_mean::k_mean"); + + _point = new algebra::mat<n, p, T>(); + _distance = new algebra::mat<n, k, mln_sum_product(T,T)>(); + _group = new algebra::mat<n, k, T>(); + _center = new algebra::mat<k, p, T>(); + _variance = new algebra::vec<k,T>(); + + mln_postcondition(_point != 0); + mln_postcondition(_distance != 0); + mln_postcondition(_group != 0); + mln_postcondition(_center != 0); + mln_postcondition(_variance != 0); + + trace::exiting("mln::clustering::k_mean::k_mean"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + k_mean<n,k,p,T>::~k_mean() + { + trace::entering("mln::clustering::k_mean::~k_mean"); + + delete _point; + delete _distance; + delete _group; + delete _center; + delete _variance; + + trace::exiting("mln::clustering::k_mean::~k_mean"); + } + + //-------------------------------------------------------------------------- + // Accessors + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + algebra::mat<n, p, T>& + k_mean<n,k,p,T>::get_point() + { + trace::entering("mln::clustering::k_mean::get_point"); + trace::exiting("mln::clustering::k_mean::get_point"); + + return *_point; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + algebra::mat<k, p, T>& + k_mean<n,k,p,T>::get_center() + { + trace::entering("mln::clustering::k_mean::get_center"); + trace::exiting("mln::clustering::k_mean::get_center"); + + return *_center; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + algebra::mat<n, k, T>& + k_mean<n,k,p,T>::get_distance() + { + trace::entering("mln::clustering::k_mean::get_distance"); + trace::exiting("mln::clustering::k_mean::get_distance"); + + return *_distance; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + algebra::mat<n, k, T>& + k_mean<n,k,p,T>::get_group() + { + trace::entering("mln::clustering::k_mean::get_group"); + trace::exiting("mln::clustering::k_mean::get_group"); + + return *_group; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + algebra::vec<k, T>& + k_mean<n,k,p,T>::get_variance() + { + trace::entering("mln::clustering::k_mean::get_variance"); + trace::exiting("mln::clustering::k_mean::get_variance"); + + return *_variance; + } + + //-------------------------------------------------------------------------- + // Tools + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, unsigned r> + inline + algebra::vec<r, T> k_mean<n,k,p,T>::row(const algebra::mat<r, q, T>& m, + const unsigned _row) const + { + trace::entering("mln::clustering::k_mean::row"); + mln_precondition(q > _row); + + algebra::vec<r, T> result; + + for (unsigned i = 0; i < r; ++i) + result[i] = m(i, _row); + + trace::exiting("mln::clustering::k_mean::row"); + return result; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, unsigned r> + inline + algebra::vec<q,T> k_mean<n,k,p,T>::col(const algebra::mat<r, q, T>& m, + const unsigned _col) const + { + trace::entering("mln::clustering::k_mean::col"); + mln_precondition(r > _col); + + algebra::vec<q, T> result; + + for (unsigned j = 0; j < q; ++j) + result[j] = m(_col, j); + + trace::exiting("mln::clustering::k_mean::col"); + return result; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, unsigned r> + inline + algebra::vec<q,T>* k_mean<n,k,p,T>::ptr_col(const algebra::mat<r, q, T>& m, + const unsigned _col) const + { + trace::entering("mln::clustering::k_mean::ptr_col"); + mln_precondition(r > _col); + + algebra::vec<q, T> *result = new algebra::vec<q, T>(); + + for (unsigned j = 0; j < q; ++j) + (*result)[j] = m(_col, j); + + trace::exiting("mln::clustering::k_mean::ptr_col"); + return result; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, unsigned r> + inline + mln_sum(T) k_mean<n,k,p,T>::sum_row(const algebra::mat<r, q, T>& m, + const unsigned _row) const + { + trace::entering("mln::clustering::k_mean::sum_row"); + mln_precondition(q > _row); + + mln_sum(T) result; + + for (unsigned j = 0; j < r; ++j) + result += m(j, _row); + + trace::exiting("mln::clustering::k_mean::sum_row"); + return result; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, unsigned r> + inline + void k_mean<n,k,p,T>::div_col(algebra::mat<r, q, T>& m, + const unsigned _col, + const T value) + { + trace::entering("mln::clustering::k_mean::div_col"); + mln_precondition(r > _col); + + for (unsigned j = 0; j < q; ++j) + m(_col, j) /= value; + + trace::exiting("mln::clustering::k_mean::div_col"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + template <unsigned q, typename M> + inline + M k_mean<n,k,p,T>::min_col(const algebra::vec<q, M>& x) const + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::min_col"); + + M result = x[0]; + + for (unsigned i = 1; i < q; ++i) + result = math::min(result, x[i]); + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::min_col"); + return result; + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + mln_sum_product(T,T) + k_mean<n,k,p,T>::euclidian_distance(const algebra::vec<p, T>& x, + const algebra::vec<p, T>& y) const + { + trace::entering("mln::clustering::k_mean::euclidian_distance"); + //vec<p, double> tmp = norm::l2(x - y); + const algebra::vec<p, double> tmp = (x - y); + mln_sum_product(T,T) result = tmp*tmp; + + trace::exiting("mln::clustering::k_mean::euclidian_distance"); + return result; + } + + + //-------------------------------------------------------------------------- + // Initializations of points and centers + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + template <typename I> + inline + void k_mean<n,k,p,T>::init_point(const Image<I>& _input) + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::init"); + + const I& input = exact(_input); + algebra::mat<n, p, T>& point = *_point; + + mln_precondition(input.is_valid()); + mln_precondition(n == input.nrows() * input.ncols()); + //mln_precondition(n == input.nrows()); + //mln_precondition(n == input.nrows() * input.ncols() * input.nslices()); + + mln_piter(I) pi(input.domain()); + unsigned i = -1; + + for_all(pi) + { + //std::cout << pi << std::endl; + + ++i; + for (unsigned j = 0; j < p; ++j) + { + + point(i,j) = input(pi).comp(j); + //point(i,j) = input(pi); + } + } + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::init"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + void k_mean<n,k,p,T>::init_center() + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::init_center"); + + algebra::mat<n, p, T>& point = *_point; + algebra::mat<k, p, T>& center = *_center; + + // A random point is choosen to be the initial value for a center. + for (unsigned i = 0; i < k; ++i) + { + unsigned random = rand() % n; + + for (unsigned j = 0; j < p; ++j) + { + center(i,j) = point(random, j); + } + + //std::cout << "center(" << i << ")" << col(center, i) << std::endl; + } + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::init_center"); + } + + + //-------------------------------------------------------------------------- + // Computations of distance, group, center, within variance + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + void k_mean<n,k,p,T>::update_distance() + { + trace::entering("mln::clustering::k_mean::update_distance"); + //mln::trace::quiet = true; + + // the result is stored in _distance matrix. + algebra::mat<n, p, T>& point = *_point; + algebra::mat<n, k, T>& distance = *_distance; + algebra::mat<k, p, T>& center = *_center; + + // for all points in the data cloud. + for (unsigned i = 0; i < n; ++i) + { + // for every center + for (unsigned j = 0; j < k; ++j) + { + distance(i,j) = euclidian_distance(col(point,i),col(center,j)); + } + } + //mln::trace::quiet = false; + trace::exiting("mln::clustering::k_mean::update_distance"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + void k_mean<n,k,p,T>::update_group() + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::update_group"); + + algebra::mat<n, k, mln_sum_product(T,T)>& distance = *_distance; + algebra::mat<n, k, T>& group = *_group; + + // for each point + for (unsigned i = 0; i < n; ++i) + { + // tell us the minimum distance from a specific point to a group + mln_sum_product(T,T) min_dist = min_col(col(distance, i)); + + // for each center + for (unsigned j = 0; j < k; ++j) + group(i,j) = (min_dist == distance(i,j))? 1.0 : 0.0; + } + + // mln_postcondition(sum(col(distance(i,j)) == 1) Vi + trace::exiting("mln::clustering::k_mean<n,k,p,T>::update_group"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + void k_mean<n,k,p,T>::update_center() + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::update_center"); + + algebra::mat<n, p, T>& point = *_point; + algebra::mat<k, p, T>& center = *_center; + algebra::mat<n, k, T>& group = *_group; + + // center = (group.t() * point); + + for (unsigned i = 0; i < k; ++i) + { + for (unsigned j = 0; j < p; ++j) + { + center(i,j) = literal::zero; + + for (unsigned l = 0; l < n; ++l) + center(i,j) += group(l,i) * point(l,j); + } + } + + for (unsigned i = 0; i < k; ++i) + div_col(center, i, sum_row(group, i)); + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::update_center"); + } + + template <unsigned n, unsigned k, unsigned p, typename T> + inline + T k_mean<n,k,p,T>::update_variance() + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::update_variance"); + + algebra::vec<k, T>& variance = *_variance; + algebra::mat<n, k, T>& distance = *_distance; + algebra::mat<n, k, T>& group = *_group; + T result = literal::zero; + + // for every group + for (unsigned i = 0; i < k; ++i) + { + variance[i] = row(group, i) * row(distance, i); + result += variance[i]; + } + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::update_variance"); + return result; + } + + + //-------------------------------------------------------------------------- + // Main loop + //-------------------------------------------------------------------------- + + template <unsigned n, unsigned k, unsigned p, typename T> + template <typename I> + inline + void k_mean<n,k,p,T>::loop(const Image<I>& _input) + //void k_mean<n,k,p,T>::loop() + { + trace::entering("mln::clustering::k_mean<n,k,p,T>::loop"); + + T within_variance = INT_MAX-1; + T old_variance = INT_MAX; + + init_point(_input); + init_center(); + + std::cout << "LOOP" << std::endl; + + for (unsigned i = 0; i < watch_dog && within_variance < old_variance; ++i) + { + update_distance(); + + std::cout << "DISTANCE DONE" << std::endl; + + update_group(); + + std::cout << "GROUP DONE" << std::endl; + + update_center(); + + std::cout << "UPDATE CENTER DONE" << std::endl; + + old_variance = within_variance; + within_variance = update_variance(); + + std::cout << i << " : " << within_variance << std::endl; + } + + trace::exiting("mln::clustering::k_mean<n,k,p,T>::loop"); + } + + + +#endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::clustering + +} // end of namespace mln::clustering + +#endif // ! MLN_CLUSTERING_K_MEAN_HH diff --git a/trunk/milena/sandbox/green/tests/clustering/k_mean/Makefile.am b/trunk/milena/sandbox/green/tests/clustering/k_mean/Makefile.am new file mode 100644 index 0000000..5f00678 --- /dev/null +++ b/trunk/milena/sandbox/green/tests/clustering/k_mean/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/tests +BUILD__PATTERN= green/build/tests + + +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: print 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/tests/clustering/k_mean/k_mean.cc b/trunk/milena/sandbox/green/tests/clustering/k_mean/k_mean.cc new file mode 100644 index 0000000..27751fd --- /dev/null +++ b/trunk/milena/sandbox/green/tests/clustering/k_mean/k_mean.cc @@ -0,0 +1,450 @@ +// UNARY TESTS ON K_MEAN + +#include <mln/clustering/k_mean.hh> + +#include <iostream> + +#include <mln/pw/value.hh> + +#include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> + +#include <mln/literal/colors.hh> + +#include <mln/algebra/vec.hh> +#include <mln/algebra/mat.hh> + +#include <mln/core/macros.hh> +#include <mln/core/contract.hh> +#include <mln/core/image/image2d.hh> +#include <mln/core/image/dmorph/image_if.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/data/transform.hh> + +#include <mln/trait/value/print.hh> +#include <mln/trait/image/print.hh> + +#define SIZE_IMAGE 512 +#define SIZE_SAMPLE1 (512*512) +#define SIZE_SAMPLE2 4 +#define NB_CENTER 2 +#define DIM_POINT 3 +#define TYPE_POINT double +#define MAT_POINT1 mln::algebra::mat<SIZE_SAMPLE1, DIM_POINT, TYPE_POINT> +#define MAT_POINT2 mln::algebra::mat<SIZE_SAMPLE2, DIM_POINT, TYPE_POINT> +#define MAT_CENTER mln::algebra::mat<NB_CENTER, DIM_POINT, TYPE_POINT> +#define MAT_DISTANCE1 mln::algebra::mat<SIZE_SAMPLE1, NB_CENTER, TYPE_POINT> +#define MAT_DISTANCE2 mln::algebra::mat<SIZE_SAMPLE2, NB_CENTER, TYPE_POINT> +#define MAT_GROUP1 mln::algebra::mat<SIZE_SAMPLE1, NB_CENTER, TYPE_POINT> +#define MAT_GROUP2 mln::algebra::mat<SIZE_SAMPLE2, NB_CENTER, TYPE_POINT> +#define VEC_VAR mln::algebra::vec<NB_CENTER, TYPE_POINT> + + +void test_instantiation() +{ + mln::clustering::k_mean<SIZE_SAMPLE2,NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + // test the compilation + + std::cout << "test instantiation : ok" << std::endl; +} + +struct rgb8_to_4colors : mln::Function_v2v<rgb8_to_4colors> +{ + typedef mln::value::rgb8 result; + + mln::value::rgb8 operator()(const mln::value::rgb8& color) const + { + mln::value::rgb8 result; + unsigned hash = (color.red() + color.green() + color.blue()) % 4; + + switch (hash) + { + case 0: result = mln::literal::lime; break; + case 1: result = mln::literal::brown; break; + case 2: result = mln::literal::teal; break; + case 3: result = mln::literal::purple; break; + } + + return result; + } +}; + + +void print_color(const mln::value::rgb8& color) +{ + std::cout << "{r=" << color.red() << ", "; + std::cout << "g=" << color.green() << ", "; + std::cout << "b=" << color.blue() << "}" << std::endl; +} + +void fill_image_with_4colors(mln::image2d<mln::value::rgb8>& img) +{ + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + + img = mln::data::transform(img, rgb8_to_4colors()); + + //print_color(lime); + //print_color(brown); + //print_color(teal); + //print_color(purple); +} + +bool is_equivalent(const mln::image2d<mln::value::rgb8>& img, + const MAT_POINT1& point) +{ + mln_piter_(mln::image2d<mln::value::rgb8>) pi(img.domain()); + bool result = true; + unsigned index = -1; + + for_all(pi) + { + bool test = true; + + ++index; + + test = test && (point(index,0) == img(pi).red()); + test = test && (point(index,1) == img(pi).green()); + test = test && (point(index,2) == img(pi).blue()); + + if (!test) + { + std::cout << pi; + std::cout << "{r=" << img(pi).red() << ", "; + std::cout << "g=" << img(pi).green() << ", "; + std::cout << "b=" << img(pi).blue() << "}"; + std::cout << index; + std::cout << "[r=" << point(index,0) << ", "; + std::cout << "g=" << point(index,1) << ", "; + std::cout << "b=" << point(index,2) << "]" << std::endl; + + mln_assertion(test); + } + + result &= test; + } + + return result; +} + +void test_init_point() +{ + typedef mln::value::rgb8 rgb8; + mln::image2d<rgb8> img_ref; + + mln::clustering::k_mean<SIZE_SAMPLE1,NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + mln::io::ppm::load(img_ref, "/usr/local/share/olena/images/lena.ppm"); + //mln::io::ppm::save(img_ref, "verif.ppm"); + + fill_image_with_4colors(img_ref); + kmean.init_point(img_ref); + + mln_assertion(true == is_equivalent(img_ref, kmean.get_point())); + + std::cout << "Test init point : ok" << std::endl; +} + +void set_point(MAT_POINT2& point, + const unsigned index, + const mln::value::rgb8& color) +{ + point(index,0) = color.red(); + point(index,1) = color.green(); + point(index,2) = color.blue(); +} + +void fake_init_point(MAT_POINT2& point, + const mln::value::rgb8& point1, + const mln::value::rgb8& point2, + const mln::value::rgb8& point3, + const mln::value::rgb8& point4) +{ + set_point(point, 0, point1); + set_point(point, 1, point2); + set_point(point, 2, point3); + set_point(point, 3, point4); +} + +bool is_equal(const mln::value::rgb8& ref, + const MAT_CENTER& center, + const unsigned i) +{ + bool result = true; + + result = result && (center(i, 0) - ref.red() < 1.0); + result = result && (center(i, 1) - ref.green() < 1.0); + result = result && (center(i, 2) - ref.blue() < 1.0); + + return result; +} + +void test_init_center() +{ + mln::clustering::k_mean<SIZE_SAMPLE2, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + + fake_init_point(kmean.get_point(), lime, brown, teal, purple); + kmean.init_center(); + + mln_assertion(is_equal(lime, kmean.get_center(), 0) || + is_equal(brown, kmean.get_center(), 0) || + is_equal(teal, kmean.get_center(), 0) || + is_equal(purple, kmean.get_center(), 0)); + + mln_assertion(is_equal(lime, kmean.get_center(), 1) || + is_equal(brown, kmean.get_center(), 1) || + is_equal(teal, kmean.get_center(), 1) || + is_equal(purple, kmean.get_center(), 1)); + + std::cout << "Test init center : ok" << std::endl; +} + +void set_center(MAT_CENTER& center, + const unsigned index, + const mln::value::rgb8& color) +{ + center(index,0) = color.red(); + center(index,1) = color.green(); + center(index,2) = color.blue(); +} + +void fake_init_center(MAT_CENTER& center, + const mln::value::rgb8 center1, + const mln::value::rgb8 center2) +{ + + set_center(center, 0, center1); + set_center(center, 1, center2); +} + + +double dist(mln::value::rgb8 color1, mln::value::rgb8 color2) +{ + double red = color1.red() - color2.red(); + double green = color1.green() - color2.green(); + double blue = color1.blue() - color2.blue(); + double result= red * red + green * green + blue * blue; + + return result; +} + +void test_update_distance() +{ + mln::clustering::k_mean<SIZE_SAMPLE2, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + const mln::value::rgb8 c1 = lime; + const mln::value::rgb8 c2 = purple; + const MAT_DISTANCE2& dist_v = kmean.get_distance(); + + fake_init_point(kmean.get_point(), lime, brown, teal, purple); + fake_init_center(kmean.get_center(), c1, c2); + kmean.update_distance(); + + mln_assertion(dist(lime, c1) == dist_v(0,0)); + mln_assertion(dist(lime, c2) == dist_v(0,1)); + mln_assertion(dist(brown, c1) == dist_v(1,0)); + mln_assertion(dist(brown, c2) == dist_v(1,1)); + mln_assertion(dist(teal, c1) == dist_v(2,0)); + mln_assertion(dist(teal, c2) == dist_v(2,1)); + mln_assertion(dist(purple, c1) == dist_v(3,0)); + mln_assertion(dist(purple, c2) == dist_v(3,1)); + + std::cout << "Test update distance : ok" << std::endl; +} + +void set_distance(MAT_DISTANCE2& distance, + const unsigned index, + const double d1, + const double d2) +{ + distance(index,0) = d1; + distance(index,1) = d2; +} + +void fake_update_distance(MAT_DISTANCE2& distance, + const mln::value::rgb8& point1, + const mln::value::rgb8& point2, + const mln::value::rgb8& point3, + const mln::value::rgb8& point4, + const mln::value::rgb8& center1, + const mln::value::rgb8& center2) +{ + set_distance(distance, 0, dist(point1, center1), dist(point1, center2)); + set_distance(distance, 1, dist(point2, center1), dist(point2, center2)); + set_distance(distance, 2, dist(point3, center1), dist(point3, center2)); + set_distance(distance, 3, dist(point4, center1), dist(point4, center2)); + + /* + for (int i = 0; i < SIZE_SAMPLE2; ++i) + for (int j = 0; j < NB_CENTER; ++j) + std::cout << "d(" << i << "," << j << ") = " << distance(i,j) <<std::endl; + */ +} + +void test_update_group() +{ + mln::clustering::k_mean<SIZE_SAMPLE2, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + const mln::value::rgb8 c1 = lime; + const mln::value::rgb8 c2 = purple; + const unsigned point1_min= 0; // lime near lime (c1) + const unsigned point2_min= 1; // brown near purple (c2) + const unsigned point3_min= 1; // teal near purple (c2) + const unsigned point4_min= 1; // purple near purple (c2) + const MAT_GROUP2& group = kmean.get_group(); + + fake_init_point(kmean.get_point(), lime, brown, teal, purple); + fake_init_center(kmean.get_center(), c1, c2); + fake_update_distance(kmean.get_distance(), lime, brown, teal, purple, c1, c2); + kmean.update_group(); + + mln_assertion(0.0 == group(0, 1 - point1_min)); + mln_assertion(1.0 == group(0, point1_min)); + mln_assertion(0.0 == group(1, 1 - point2_min)); + mln_assertion(1.0 == group(1, point2_min)); + mln_assertion(0.0 == group(2, 1 - point3_min)); + mln_assertion(1.0 == group(2, point3_min)); + mln_assertion(0.0 == group(3, 1 - point4_min)); + mln_assertion(1.0 == group(3, point4_min)); + + std::cout << "Test update group : ok" << std::endl; +} + +void set_group(MAT_GROUP2& group, + const unsigned index, + const unsigned min) +{ + group(index, min) = 1.0; + group(index, 1-min) = 0.0; +} + + +void fake_update_group(MAT_GROUP2& group, + const unsigned& point1_min, + const unsigned& point2_min, + const unsigned& point3_min, + const unsigned& point4_min) +{ + set_group(group, 0, point1_min); + set_group(group, 1, point2_min); + set_group(group, 2, point3_min); + set_group(group, 3, point4_min); +} + +void test_update_center() +{ + mln::clustering::k_mean<SIZE_SAMPLE2, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + const mln::value::rgb8 c1 = lime; + const mln::value::rgb8 c2 = purple; + const unsigned pt1_min = 0; // lime near lime (c1) + const unsigned pt2_min = 1; // brown near purple (c2) + const unsigned pt3_min = 1; // teal near purple (c2) + const unsigned pt4_min = 1; // purple near purple (c2) + const mln::value::rgb8 mean_c1 = lime; + const mln::value::rgb8 mean_c2 = (brown+teal+purple)/3; + + fake_init_point(kmean.get_point(), lime, brown, teal, purple); + fake_init_center(kmean.get_center(), c1, c2); + fake_update_distance(kmean.get_distance(), lime, brown, teal, purple, c1, c2); + fake_update_group(kmean.get_group(), pt1_min, pt2_min, pt3_min, pt4_min); + kmean.update_center(); + + mln_assertion(is_equal(mean_c1, kmean.get_center(), 0)); + mln_assertion(is_equal(mean_c2, kmean.get_center(), 1)); + + std::cout << "Test update center : ok" << std::endl; +} + +void test_update_variance() +{ + mln::clustering::k_mean<SIZE_SAMPLE2, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + const mln::value::rgb8 lime = mln::literal::lime; + const mln::value::rgb8 brown = mln::literal::brown; + const mln::value::rgb8 teal = mln::literal::teal; + const mln::value::rgb8 purple = mln::literal::purple; + const mln::value::rgb8 c1 = lime; + const mln::value::rgb8 c2 = purple; + const unsigned pt1_min = 0; // lime near lime (c1) + const unsigned pt2_min = 1; // brown near purple (c2) + const unsigned pt3_min = 1; // teal near purple (c2) + const unsigned pt4_min = 1; // purple near purple (c2) + const double v1 = 0; + const double v2 = dist(purple, brown) + dist(purple, teal); + const mln::value::rgb8 mean_c2 = (brown+teal+purple)/3; + const VEC_VAR& var = kmean.get_variance(); + + fake_init_point(kmean.get_point(), lime, brown, teal, purple); + fake_init_center(kmean.get_center(), c1, c2); + fake_update_distance(kmean.get_distance(), lime, brown, teal, purple, c1, c2); + fake_update_group(kmean.get_group(), pt1_min, pt2_min, pt3_min, pt4_min); + kmean.update_variance(); + + mln_assertion(v1 == var[0]); + mln_assertion(v2 == var[1]); + + std::cout << "Test update variance : ok" << std::endl; +} + +void test_loop() +{ + typedef mln::value::rgb8 rgb8; + mln::image2d<rgb8> img_ref; + + mln::clustering::k_mean<SIZE_SAMPLE1, NB_CENTER, DIM_POINT, TYPE_POINT> kmean; + + mln::io::ppm::load(img_ref, "/usr/local/share/olena/images/lena.ppm"); + //mln::io::ppm::save(img_ref, "verif.ppm"); + + fill_image_with_4colors(img_ref); + kmean.init_point(img_ref); + + kmean.loop(img_ref); + + + // std::cout << "Test update variance: ok" << std::endl; +} + + +int main() +{ + //test_instantiation(); + //test_init_point(); + //test_init_center(); + //test_update_distance(); + //test_update_group(); + //test_update_center(); + //test_update_variance(); + + // mln::trace::quiet = false; + + test_loop(); + + return 0; +} -- 1.5.6.5