* green/k_mean/Makefile.am : Remove old makefile. * green/k_mean/k_mean.hh : Remove old library code. * green/k_mean/k_mean.cc : Remove old unitary tests. * green/k_mean : Remove old directory. --- trunk/milena/sandbox/ChangeLog | 9 + trunk/milena/sandbox/green/k_mean/Makefile.am | 50 -- trunk/milena/sandbox/green/k_mean/k_mean.cc | 450 ----------------- trunk/milena/sandbox/green/k_mean/k_mean.hh | 672 ------------------------- 4 files changed, 9 insertions(+), 1172 deletions(-) delete mode 100644 trunk/milena/sandbox/green/k_mean/Makefile.am delete mode 100644 trunk/milena/sandbox/green/k_mean/k_mean.cc delete mode 100644 trunk/milena/sandbox/green/k_mean/k_mean.hh diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog index 4555e7f..2a8148f 100644 --- a/trunk/milena/sandbox/ChangeLog +++ b/trunk/milena/sandbox/ChangeLog @@ -1,5 +1,14 @@ 2009-09-07 Yann Jacquelet &lt;jacquelet(a)lrde.epita.fr&gt; + Delete old k_mean source location. + + * green/k_mean/Makefile.am : Remove old makefile. + * green/k_mean/k_mean.hh : Remove old library code. + * green/k_mean/k_mean.cc : Remove old unitary tests. + * green/k_mean : Remove old directory. + +2009-09-07 Yann Jacquelet &lt;jacquelet(a)lrde.epita.fr&gt; + Delete old histo1d source location. * green/histo1d/Makefile.am : Remove old makefile. diff --git a/trunk/milena/sandbox/green/k_mean/Makefile.am b/trunk/milena/sandbox/green/k_mean/Makefile.am deleted file mode 100644 index 1834984..0000000 --- a/trunk/milena/sandbox/green/k_mean/Makefile.am +++ /dev/null @@ -1,50 +0,0 @@ -# -# Generic Makefile -# - -BIN_PATTERN= trunk/build/milena -SRC_PATTERN= trunk/milena - -INCLUDES= -I/home/green/svn/oln/trunk/milena -CXXFLAGS= -ggdb -O0 -Wall -W -pedantic -ansi -pipe $(INCLUDES) -ECHO= echo -RM= rm -MKDIR= mkdir -CP= cp - -ifeq ($(findstring $(BIN_PATTERN),$(PWD)), $(BIN_PATTERN)) -BIN_DIR= -SRC_DIR= $(subst $(BIN_PATTERN),$(SRC_PATTERN), $(PWD))/ -else -BIN_DIR= $(subst $(SRC_PATTERN),$(BIN_PATTERN), $(PWD))/ -SRC_DIR= -endif - -TARGET= $(BIN_DIR)$(notdir $(PWD)) -BIN_MAKE= $(BIN_DIR)Makefile -SRC_MAKE= $(SRC_DIR)Makefile.am - - -SRC_FILES= $(wildcard $(SRC_DIR)*.cc) -OLD_FILES= $(addsuffix ~, $(SRC_FILES)) -OBJ_FILES= $(addprefix $(BIN_DIR), $(notdir $(SRC_FILES:%.cc=%.o))) - - -all: $(BIN_DIR) $(TARGET) - @$(ECHO) "Compilation terminée" - -$(BIN_DIR): - $(MKDIR) $(BIN_DIR) - $(CP) $(SRC_MAKE) $(BIN_MAKE) - -$(TARGET):$(OBJ_FILES) - $(LINK.cc) $^ $(LOADLIBES) $(LDLIBS) -o $@ - -$(BIN_DIR)%.o:$(SRC_DIR)%.cc - $(COMPILE.cc) $(OUTPUT_OPTION) $< - -clean: - -@$(RM) $(TARGET) - -@$(RM) $(OBJ_FILES) - -@$(RM) $(OLD_FILES) - diff --git a/trunk/milena/sandbox/green/k_mean/k_mean.cc b/trunk/milena/sandbox/green/k_mean/k_mean.cc deleted file mode 100644 index 985e0e0..0000000 --- a/trunk/milena/sandbox/green/k_mean/k_mean.cc +++ /dev/null @@ -1,450 +0,0 @@ -// UNARY TESTS ON K_MEAN - -#include "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; -} diff --git a/trunk/milena/sandbox/green/k_mean/k_mean.hh b/trunk/milena/sandbox/green/k_mean/k_mean.hh deleted file mode 100644 index db3f34c..0000000 --- a/trunk/milena/sandbox/green/k_mean/k_mean.hh +++ /dev/null @@ -1,672 +0,0 @@ -// 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 -- 1.5.6.5