Image Component Library (ICL)
KMeans.h
Go to the documentation of this file.
1 /********************************************************************
2 ** Image Component Library (ICL) **
3 ** **
4 ** Copyright (C) 2006-2013 CITEC, University of Bielefeld **
5 ** Neuroinformatics Group **
6 ** Website: www.iclcv.org and **
7 ** http://opensource.cit-ec.de/projects/icl **
8 ** **
9 ** File : ICLMath/src/ICLMath/KMeans.h **
10 ** Module : ICLMath **
11 ** Authors: Christof Elbrechter **
12 ** **
13 ** **
14 ** GNU LESSER GENERAL PUBLIC LICENSE **
15 ** This file may be used under the terms of the GNU Lesser General **
16 ** Public License version 3.0 as published by the **
17 ** **
18 ** Free Software Foundation and appearing in the file LICENSE.LGPL **
19 ** included in the packaging of this file. Please review the **
20 ** following information to ensure the license requirements will **
21 ** be met: http://www.gnu.org/licenses/lgpl-3.0.txt **
22 ** **
23 ** The development of this software was supported by the **
24 ** Excellence Cluster EXC 277 Cognitive Interaction Technology. **
25 ** The Excellence Cluster EXC 277 is a grant of the Deutsche **
26 ** Forschungsgemeinschaft (DFG) in the context of the German **
27 ** Excellence Initiative. **
28 ** **
29 ********************************************************************/
30 
31 #pragma once
32 
33 #include <ICLUtils/CompatMacros.h>
34 #include <ICLUtils/Random.h>
35 #include <ICLUtils/Point32f.h>
36 #include <algorithm>
37 
38 namespace icl{
39  namespace math{
40 
41 
43 
57  template<class Vector, class Scalar>
58  class KMeans{
59 
61  std::vector<Vector> m_centers;
62 
64  std::vector<Vector> m_means;
65 
67  std::vector<int> m_nums;
68 
70  std::vector<Scalar> m_errors;
71 
73  static Scalar diff_power_two(const Scalar &a, const Scalar &b){
74  Scalar d = a-b;
75  return d*d;
76  }
77 
79  static inline Scalar dist(const Vector &a, const Vector &b){
80  return ::sqrt( std::inner_product(a.begin(),a.end(),b.begin(),Scalar(0), std::plus<Scalar>(), diff_power_two) );
81  }
82 
84  static inline void setVectorNull(Vector &v){
85  std::fill(v.begin(),v.end(),Scalar(0));
86  }
87 
88  public:
89 
92  const std::vector<Vector> &centers;
93  const std::vector<int> &nums;
94  const std::vector<Scalar> &errors;
95  };
96 
98  inline KMeans(int numCenters=0){
99  init(numCenters);
100  }
101 
103  inline void init(int numCenters){
104  m_centers.resize(numCenters);
105  m_means.resize(numCenters);
106  m_nums.resize(numCenters);
107  m_errors.resize(numCenters);
108  }
109 
111  inline int findNN(const Vector &v, Scalar &minDist){
112  int minIdx = 0;
113  minDist = dist(v,m_centers[0]);
114  for(size_t i=1;i<m_centers.size();++i){
115  Scalar currDist = dist(v,m_centers[i]);
116  if(currDist < minDist){
117  minDist = currDist;
118  minIdx = i;
119  }
120  }
121  return minIdx;
122  }
123 
125 
127  template<class RandomAcessIterator>
128  Result apply(RandomAcessIterator begin, RandomAcessIterator end, int numSteps = 1000, bool reinitCenters=true){
129  Scalar minDist = 0;
130 
131  if(reinitCenters){
132  URandI r((int)(end-begin)-1);
133  for(size_t i=0;i<m_centers.size();++i){
134  int ri = r;
135  m_centers[i] = *(begin+ri);
136  }
137  }
138 
139  for(int step=0;step<numSteps;++step){
140  // empty accumulators
141  for(size_t i=0;i<m_means.size();++i){
143  m_nums[i] = Scalar(0);
144  m_errors[i] = Scalar(0);
145  }
146 
147  // estimate means
148  for(RandomAcessIterator it=begin;it != end; ++it){
149  const int nn = findNN(*it,minDist);
150  m_means[nn] += *it;
151  m_nums[nn] ++;
152  m_errors[nn] += minDist;
153  }
154 
155  for(size_t i=0;i<m_means.size();++i){
156  if(m_nums[i]){
157  m_centers[i] = m_means[i] * (Scalar(1.0)/m_nums[i]);
158  m_errors[i] /= m_nums[i];
159  }// empty voronoi tessels are not moved
160  }
161  }
162 
163  Result r= { m_centers, m_nums, m_errors };
164  return r;
165  }
166  };
167 
169  template<>
171  return a.distanceTo(b);
172  }
173 
174  template<>
175  void KMeans<utils::Point32f, float>::setVectorNull(utils::Point32f &p){
177  }
181  }
182 }
ICLQt_API ImgQ sqrt(const ImgQ &image)
calls sqrt( each pixel)
undocument this line if you encounter any issues!
Definition: Any.h:37
#define ICLMath_API
Definition: CompatMacros.h:173
lightweight Random generator class for uniform random distributions in positive integer domain
Definition: Random.h:172
std::vector< Vector > m_centers
internal list of centroids
Definition: KMeans.h:61
KMeans(int numCenters=0)
constructor with optionally given number of centers
Definition: KMeans.h:98
static void setVectorNull(Vector &v)
sets a vector to null
Definition: KMeans.h:84
static Scalar diff_power_two(const Scalar &a, const Scalar &b)
internal utility function
Definition: KMeans.h:73
std::vector< Vector > m_means
internal buffer
Definition: KMeans.h:64
const std::vector< Scalar > & errors
average quantisation errors
Definition: KMeans.h:94
void init(int numCenters)
deferred intitialization with number of centers
Definition: KMeans.h:103
ICLQt_API void fill(float r, float g=-1, float b=-1, float alpha=255)
sets the current fill color to given r,g,b,alpha value
restult type
Definition: KMeans.h:91
int findNN(const Vector &v, Scalar &minDist)
finds the nearest centroid for a given data pointer
Definition: KMeans.h:111
static const Point32f null
null Point is x=0, y=0
Definition: Point32f.h:51
static Scalar dist(const Vector &a, const Vector &b)
utility function computing the vector distance
Definition: KMeans.h:79
Generic Implementation of the K-Means algorithm.
Definition: KMeans.h:58
const std::vector< Vector > & centers
final list of centroids
Definition: KMeans.h:92
Single precission 3D Vectors Point class of the ICL.
Definition: Point32f.h:41
float distanceTo(const Point32f &p) const
returns the euclidian distance to another point
std::vector< Scalar > m_errors
averate quantisation error for each centroid
Definition: KMeans.h:70
std::vector< int > m_nums
numbers of points associated to each centroid
Definition: KMeans.h:67
Result apply(RandomAcessIterator begin, RandomAcessIterator end, int numSteps=1000, bool reinitCenters=true)
runs the KMeans algorithms on the given data
Definition: KMeans.h:128
const std::vector< int > & nums
final number of points for each centroid
Definition: KMeans.h:93