center_chooser.h
Go to the documentation of this file.
1 /*
2  * center_chooser.h
3  *
4  * Created on: 2012-11-04
5  * Author: marius
6  */
7 
8 #ifndef RTABMAP_CENTER_CHOOSER_H_
9 #define RTABMAP_CENTER_CHOOSER_H_
10 
11 #include "rtflann/util/matrix.h"
12 
13 namespace rtflann
14 {
15 
16 template <typename Distance, typename ElementType>
18 {
19  typedef typename Distance::ResultType ResultType;
20  ResultType operator()( ResultType dist ) { return dist*dist; }
21 };
22 
23 
24 template <typename ElementType>
25 struct squareDistance<L2_Simple<ElementType>, ElementType>
26 {
28  ResultType operator()( ResultType dist ) { return dist; }
29 };
30 
31 template <typename ElementType>
32 struct squareDistance<L2_3D<ElementType>, ElementType>
33 {
35  ResultType operator()( ResultType dist ) { return dist; }
36 };
37 
38 template <typename ElementType>
39 struct squareDistance<L2<ElementType>, ElementType>
40 {
42  ResultType operator()( ResultType dist ) { return dist; }
43 };
44 
45 
46 template <typename ElementType>
47 struct squareDistance<HellingerDistance<ElementType>, ElementType>
48 {
50  ResultType operator()( ResultType dist ) { return dist; }
51 };
52 
53 
54 template <typename ElementType>
55 struct squareDistance<ChiSquareDistance<ElementType>, ElementType>
56 {
58  ResultType operator()( ResultType dist ) { return dist; }
59 };
60 
61 
62 template <typename Distance>
63 typename Distance::ResultType ensureSquareDistance( typename Distance::ResultType dist )
64 {
65  typedef typename Distance::ElementType ElementType;
66 
68  return dummy( dist );
69 }
70 
71 
72 
73 template <typename Distance>
75 {
76 public:
77  typedef typename Distance::ElementType ElementType;
78  typedef typename Distance::ResultType DistanceType;
79 
80  CenterChooser(const Distance& distance, const std::vector<ElementType*>& points) : distance_(distance), points_(points) {};
81 
82  virtual ~CenterChooser() {};
83 
84  void setDataSize(size_t cols) { cols_ = cols; }
85 
95  virtual void operator()(int k, int* indices, int indices_length, int* centers, int& centers_length) = 0;
96 
97 protected:
98  const Distance distance_;
99  const std::vector<ElementType*>& points_;
100  size_t cols_;
101 };
102 
103 
104 template <typename Distance>
105 class RandomCenterChooser : public CenterChooser<Distance>
106 {
107 public:
108  typedef typename Distance::ElementType ElementType;
109  typedef typename Distance::ResultType DistanceType;
113 
114  RandomCenterChooser(const Distance& distance, const std::vector<ElementType*>& points) :
115  CenterChooser<Distance>(distance, points) {}
116 
117  void operator()(int k, int* indices, int indices_length, int* centers, int& centers_length)
118  {
119  UniqueRandom r(indices_length);
120 
121  int index;
122  for (index=0; index<k; ++index) {
123  bool duplicate = true;
124  int rnd;
125  while (duplicate) {
126  duplicate = false;
127  rnd = r.next();
128  if (rnd<0) {
129  centers_length = index;
130  return;
131  }
132 
133  centers[index] = indices[rnd];
134 
135  for (int j=0; j<index; ++j) {
136  DistanceType sq = distance_(points_[centers[index]], points_[centers[j]], cols_);
137  if (sq<1e-16) {
138  duplicate = true;
139  }
140  }
141  }
142  }
143 
144  centers_length = index;
145  }
146 };
147 
148 
149 
153 template <typename Distance>
154 class GonzalesCenterChooser : public CenterChooser<Distance>
155 {
156 public:
157  typedef typename Distance::ElementType ElementType;
158  typedef typename Distance::ResultType DistanceType;
159 
163 
164  GonzalesCenterChooser(const Distance& distance, const std::vector<ElementType*>& points) :
165  CenterChooser<Distance>(distance, points) {}
166 
167  void operator()(int k, int* indices, int indices_length, int* centers, int& centers_length)
168  {
169  int n = indices_length;
170 
171  int rnd = rand_int(n);
172  assert(rnd >=0 && rnd < n);
173 
174  centers[0] = indices[rnd];
175 
176  int index;
177  for (index=1; index<k; ++index) {
178 
179  int best_index = -1;
180  DistanceType best_val = 0;
181  for (int j=0; j<n; ++j) {
182  DistanceType dist = distance_(points_[centers[0]],points_[indices[j]],cols_);
183  for (int i=1; i<index; ++i) {
184  DistanceType tmp_dist = distance_(points_[centers[i]],points_[indices[j]],cols_);
185  if (tmp_dist<dist) {
186  dist = tmp_dist;
187  }
188  }
189  if (dist>best_val) {
190  best_val = dist;
191  best_index = j;
192  }
193  }
194  if (best_index!=-1) {
195  centers[index] = indices[best_index];
196  }
197  else {
198  break;
199  }
200  }
201  centers_length = index;
202  }
203 };
204 
205 
210 template <typename Distance>
211 class KMeansppCenterChooser : public CenterChooser<Distance>
212 {
213 public:
214  typedef typename Distance::ElementType ElementType;
215  typedef typename Distance::ResultType DistanceType;
216 
220 
221  KMeansppCenterChooser(const Distance& distance, const std::vector<ElementType*>& points) :
222  CenterChooser<Distance>(distance, points) {}
223 
224  void operator()(int k, int* indices, int indices_length, int* centers, int& centers_length)
225  {
226  int n = indices_length;
227 
228  double currentPot = 0;
229  DistanceType* closestDistSq = new DistanceType[n];
230 
231  // Choose one random center and set the closestDistSq values
232  int index = rand_int(n);
233  assert(index >=0 && index < n);
234  centers[0] = indices[index];
235 
236  // Computing distance^2 will have the advantage of even higher probability further to pick new centers
237  // far from previous centers (and this complies to "k-means++: the advantages of careful seeding" article)
238  for (int i = 0; i < n; i++) {
239  closestDistSq[i] = distance_(points_[indices[i]], points_[indices[index]], cols_);
240  closestDistSq[i] = ensureSquareDistance<Distance>( closestDistSq[i] );
241  currentPot += closestDistSq[i];
242  }
243 
244 
245  const int numLocalTries = 1;
246 
247  // Choose each center
248  int centerCount;
249  for (centerCount = 1; centerCount < k; centerCount++) {
250 
251  // Repeat several trials
252  double bestNewPot = -1;
253  int bestNewIndex = 0;
254  for (int localTrial = 0; localTrial < numLocalTries; localTrial++) {
255 
256  // Choose our center - have to be slightly careful to return a valid answer even accounting
257  // for possible rounding errors
258  double randVal = rand_double(currentPot);
259  for (index = 0; index < n-1; index++) {
260  if (randVal <= closestDistSq[index]) break;
261  else randVal -= closestDistSq[index];
262  }
263 
264  // Compute the new potential
265  double newPot = 0;
266  for (int i = 0; i < n; i++) {
267  DistanceType dist = distance_(points_[indices[i]], points_[indices[index]], cols_);
268  newPot += std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] );
269  }
270 
271  // Store the best result
272  if ((bestNewPot < 0)||(newPot < bestNewPot)) {
273  bestNewPot = newPot;
274  bestNewIndex = index;
275  }
276  }
277 
278  // Add the appropriate center
279  centers[centerCount] = indices[bestNewIndex];
280  currentPot = bestNewPot;
281  for (int i = 0; i < n; i++) {
282  DistanceType dist = distance_(points_[indices[i]], points_[indices[bestNewIndex]], cols_);
283  closestDistSq[i] = std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] );
284  }
285  }
286 
287  centers_length = centerCount;
288 
289  delete[] closestDistSq;
290  }
291 };
292 
293 
294 
306 template <typename Distance>
307 class GroupWiseCenterChooser : public CenterChooser<Distance>
308 {
309 public:
310  typedef typename Distance::ElementType ElementType;
311  typedef typename Distance::ResultType DistanceType;
312 
316 
317  GroupWiseCenterChooser(const Distance& distance, const std::vector<ElementType*>& points) :
318  CenterChooser<Distance>(distance, points) {}
319 
320  void operator()(int k, int* indices, int indices_length, int* centers, int& centers_length)
321  {
322  const float kSpeedUpFactor = 1.3f;
323 
324  int n = indices_length;
325 
326  DistanceType* closestDistSq = new DistanceType[n];
327 
328  // Choose one random center and set the closestDistSq values
329  int index = rand_int(n);
330  assert(index >=0 && index < n);
331  centers[0] = indices[index];
332 
333  for (int i = 0; i < n; i++) {
334  closestDistSq[i] = distance_(points_[indices[i]], points_[indices[index]], cols_);
335  }
336 
337 
338  // Choose each center
339  int centerCount;
340  for (centerCount = 1; centerCount < k; centerCount++) {
341 
342  // Repeat several trials
343  double bestNewPot = -1;
344  int bestNewIndex = 0;
345  DistanceType furthest = 0;
346  for (index = 0; index < n; index++) {
347 
348  // We will test only the potential of the points further than current candidate
349  if( closestDistSq[index] > kSpeedUpFactor * (float)furthest ) {
350 
351  // Compute the new potential
352  double newPot = 0;
353  for (int i = 0; i < n; i++) {
354  newPot += std::min( distance_(points_[indices[i]], points_[indices[index]], cols_)
355  , closestDistSq[i] );
356  }
357 
358  // Store the best result
359  if ((bestNewPot < 0)||(newPot <= bestNewPot)) {
360  bestNewPot = newPot;
361  bestNewIndex = index;
362  furthest = closestDistSq[index];
363  }
364  }
365  }
366 
367  // Add the appropriate center
368  centers[centerCount] = indices[bestNewIndex];
369  for (int i = 0; i < n; i++) {
370  closestDistSq[i] = std::min( distance_(points_[indices[i]], points_[indices[bestNewIndex]], cols_)
371  , closestDistSq[i] );
372  }
373  }
374 
375  centers_length = centerCount;
376 
377  delete[] closestDistSq;
378  }
379 };
380 
381 
382 }
383 
384 
385 #endif /* RTABMAP_CENTER_CHOOSER_H_ */
Distance::ElementType ElementType
Accumulator< T >::Type ResultType
Definition: dist.h:642
GLM_FUNC_DECL genType min(genType const &x, genType const &y)
Distance::ResultType ResultType
GLM_FUNC_DECL genType e()
RandomCenterChooser(const Distance &distance, const std::vector< ElementType *> &points)
GLM_FUNC_DECL genType::value_type distance(genType const &p0, genType const &p1)
void operator()(int k, int *indices, int indices_length, int *centers, int &centers_length)
Accumulator< T >::Type ResultType
Definition: dist.h:690
Distance::ElementType ElementType
int rand_int(int high=RAND_MAX, int low=0)
Definition: random.h:73
Accumulator< T >::Type ResultType
Definition: dist.h:79
Distance::ResultType DistanceType
Distance::ResultType ensureSquareDistance(typename Distance::ResultType dist)
void operator()(int k, int *indices, int indices_length, int *centers, int &centers_length)
Distance::ResultType DistanceType
CenterChooser(const Distance &distance, const std::vector< ElementType *> &points)
GroupWiseCenterChooser(const Distance &distance, const std::vector< ElementType *> &points)
Distance::ElementType ElementType
const std::vector< ElementType * > & points_
Distance::ElementType ElementType
Distance::ResultType DistanceType
void setDataSize(size_t cols)
Distance::ResultType DistanceType
void operator()(int k, int *indices, int indices_length, int *centers, int &centers_length)
Distance::ResultType DistanceType
void operator()(int k, int *indices, int indices_length, int *centers, int &centers_length)
double rand_double(double high=1.0, double low=0)
Definition: random.h:62
Distance::ElementType ElementType
dist
Accumulator< T >::Type ResultType
Definition: dist.h:138
ResultType operator()(ResultType dist)
Accumulator< T >::Type ResultType
Definition: dist.h:106
const Distance distance_
KMeansppCenterChooser(const Distance &distance, const std::vector< ElementType *> &points)
GonzalesCenterChooser(const Distance &distance, const std::vector< ElementType *> &points)


rtabmap
Author(s): Mathieu Labbe
autogenerated on Mon Jan 23 2023 03:37:28