result_set.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  *
7  * THE BSD LICENSE
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *************************************************************************/
30 
31 #ifndef OPENCV_FLANN_RESULTSET_H
32 #define OPENCV_FLANN_RESULTSET_H
33 
34 #include <algorithm>
35 #include <cstring>
36 #include <iostream>
37 #include <limits>
38 #include <set>
39 #include <vector>
40 
41 namespace cvflann
42 {
43 
44 /* This record represents a branch point when finding neighbors in
45  the tree. It contains a record of the minimum distance to the query
46  point, as well as the node at which the search resumes.
47  */
48 
49 template <typename T, typename DistanceType>
51 {
52  T node; /* Tree node at which search resumes */
53  DistanceType mindist; /* Minimum distance to query for all nodes below. */
54 
56  BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {}
57 
58  bool operator<(const BranchStruct<T, DistanceType>& rhs) const
59  {
60  return mindist<rhs.mindist;
61  }
62 };
63 
64 
65 template <typename DistanceType>
66 class ResultSet
67 {
68 public:
69  virtual ~ResultSet() {}
70 
71  virtual bool full() const = 0;
72 
73  virtual void addPoint(DistanceType dist, int index) = 0;
74 
75  virtual DistanceType worstDist() const = 0;
76 
77 };
78 
84 template <typename DistanceType>
85 class KNNSimpleResultSet : public ResultSet<DistanceType>
86 {
87  int* indices;
88  DistanceType* dists;
89  int capacity;
90  int count;
91  DistanceType worst_distance_;
92 
93 public:
94  KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0)
95  {
96  }
97 
98  void init(int* indices_, DistanceType* dists_)
99  {
100  indices = indices_;
101  dists = dists_;
102  count = 0;
103  worst_distance_ = (std::numeric_limits<DistanceType>::max)();
104  dists[capacity-1] = worst_distance_;
105  }
106 
107  size_t size() const
108  {
109  return count;
110  }
111 
112  bool full() const
113  {
114  return count == capacity;
115  }
116 
117 
118  void addPoint(DistanceType dist, int index)
119  {
120  if (dist >= worst_distance_) return;
121  int i;
122  for (i=count; i>0; --i) {
123 #ifdef FLANN_FIRST_MATCH
124  if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) )
125 #else
126  if (dists[i-1]>dist)
127 #endif
128  {
129  if (i<capacity) {
130  dists[i] = dists[i-1];
131  indices[i] = indices[i-1];
132  }
133  }
134  else break;
135  }
136  if (count < capacity) ++count;
137  dists[i] = dist;
138  indices[i] = index;
139  worst_distance_ = dists[capacity-1];
140  }
141 
142  DistanceType worstDist() const
143  {
144  return worst_distance_;
145  }
146 };
147 
151 template <typename DistanceType>
152 class KNNResultSet : public ResultSet<DistanceType>
153 {
154  int* indices;
155  DistanceType* dists;
156  int capacity;
157  int count;
158  DistanceType worst_distance_;
159 
160 public:
161  KNNResultSet(int capacity_) : capacity(capacity_), count(0)
162  {
163  }
164 
165  void init(int* indices_, DistanceType* dists_)
166  {
167  indices = indices_;
168  dists = dists_;
169  count = 0;
170  worst_distance_ = (std::numeric_limits<DistanceType>::max)();
171  dists[capacity-1] = worst_distance_;
172  }
173 
174  size_t size() const
175  {
176  return count;
177  }
178 
179  bool full() const
180  {
181  return count == capacity;
182  }
183 
184 
185  void addPoint(DistanceType dist, int index)
186  {
187  if (dist >= worst_distance_) return;
188  int i;
189  for (i = count; i > 0; --i) {
190 #ifdef FLANN_FIRST_MATCH
191  if ( (dists[i-1]<=dist) && ((dist!=dists[i-1])||(indices[i-1]<=index)) )
192 #else
193  if (dists[i-1]<=dist)
194 #endif
195  {
196  // Check for duplicate indices
197  int j = i - 1;
198  while ((j >= 0) && (dists[j] == dist)) {
199  if (indices[j] == index) {
200  return;
201  }
202  --j;
203  }
204  break;
205  }
206  }
207 
208  if (count < capacity) ++count;
209  for (int j = count-1; j > i; --j) {
210  dists[j] = dists[j-1];
211  indices[j] = indices[j-1];
212  }
213  dists[i] = dist;
214  indices[i] = index;
215  worst_distance_ = dists[capacity-1];
216  }
217 
218  DistanceType worstDist() const
219  {
220  return worst_distance_;
221  }
222 };
223 
224 
228 template <typename DistanceType>
229 class RadiusResultSet : public ResultSet<DistanceType>
230 {
231  DistanceType radius;
232  int* indices;
233  DistanceType* dists;
234  size_t capacity;
235  size_t count;
236 
237 public:
238  RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) :
239  radius(radius_), indices(indices_), dists(dists_), capacity(capacity_)
240  {
241  init();
242  }
243 
245  {
246  }
247 
248  void init()
249  {
250  count = 0;
251  }
252 
253  size_t size() const
254  {
255  return count;
256  }
257 
258  bool full() const
259  {
260  return true;
261  }
262 
263  void addPoint(DistanceType dist, int index)
264  {
265  if (dist<radius) {
266  if ((capacity>0)&&(count < capacity)) {
267  dists[count] = dist;
268  indices[count] = index;
269  }
270  count++;
271  }
272  }
273 
274  DistanceType worstDist() const
275  {
276  return radius;
277  }
278 
279 };
280 
282 
286 template<typename DistanceType>
287 class UniqueResultSet : public ResultSet<DistanceType>
288 {
289 public:
290  struct DistIndex
291  {
292  DistIndex(DistanceType dist, unsigned int index) :
293  dist_(dist), index_(index)
294  {
295  }
296  bool operator<(const DistIndex dist_index) const
297  {
298  return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_);
299  }
300  DistanceType dist_;
301  unsigned int index_;
302  };
303 
306  worst_distance_(std::numeric_limits<DistanceType>::max())
307  {
308  }
309 
313  inline bool full() const
314  {
315  return is_full_;
316  }
317 
320  virtual void clear() = 0;
321 
327  virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const
328  {
329  if (n_neighbors < 0) {
330  for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
331  dist_indices_.end(); dist_index != dist_index_end; ++dist_index, ++indices, ++dist) {
332  *indices = dist_index->index_;
333  *dist = dist_index->dist_;
334  }
335  }
336  else {
337  int i = 0;
338  for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
339  dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) {
340  *indices = dist_index->index_;
341  *dist = dist_index->dist_;
342  }
343  }
344  }
345 
351  virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
352  {
353  copy(indices, dist, n_neighbors);
354  }
355 
359  size_t size() const
360  {
361  return dist_indices_.size();
362  }
363 
368  inline DistanceType worstDist() const
369  {
370  return worst_distance_;
371  }
372 protected:
374  bool is_full_;
375 
377  DistanceType worst_distance_;
378 
380  std::set<DistIndex> dist_indices_;
381 };
382 
384 
388 template<typename DistanceType>
389 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
390 {
391 public:
395  KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
396  {
397  this->is_full_ = false;
398  this->clear();
399  }
400 
405  inline void addPoint(DistanceType dist, int index)
406  {
407  // Don't do anything if we are worse than the worst
408  if (dist >= worst_distance_) return;
409  dist_indices_.insert(DistIndex(dist, index));
410 
411  if (is_full_) {
412  if (dist_indices_.size() > capacity_) {
413  dist_indices_.erase(*dist_indices_.rbegin());
414  worst_distance_ = dist_indices_.rbegin()->dist_;
415  }
416  }
417  else if (dist_indices_.size() == capacity_) {
418  is_full_ = true;
419  worst_distance_ = dist_indices_.rbegin()->dist_;
420  }
421  }
422 
425  void clear()
426  {
427  dist_indices_.clear();
428  worst_distance_ = std::numeric_limits<DistanceType>::max();
429  is_full_ = false;
430  }
431 
432 protected:
437 
439  unsigned int capacity_;
440 };
441 
443 
447 template<typename DistanceType>
448 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
449 {
450 public:
455  radius_(radius)
456  {
457  is_full_ = true;
458  }
459 
464  void addPoint(DistanceType dist, int index)
465  {
466  if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
467  }
468 
471  inline void clear()
472  {
473  dist_indices_.clear();
474  }
475 
476 
480  inline bool full() const
481  {
482  return true;
483  }
484 
489  inline DistanceType worstDist() const
490  {
491  return radius_;
492  }
493 private:
494  typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
497 
499  DistanceType radius_;
500 };
501 
503 
506 template<typename DistanceType>
507 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
508 {
509 public:
513  KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
514  {
515  this->capacity_ = capacity;
516  this->radius_ = radius;
517  this->dist_indices_.reserve(capacity_);
518  this->clear();
519  }
520 
523  void clear()
524  {
525  dist_indices_.clear();
526  worst_distance_ = radius_;
527  is_full_ = false;
528  }
529 private:
533 
535  unsigned int capacity_;
536 
538  DistanceType radius_;
539 };
540 }
541 
542 #endif //OPENCV_FLANN_RESULTSET_H
KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
Definition: result_set.h:513
int int * max
DistIndex(DistanceType dist, unsigned int index)
Definition: result_set.h:292
virtual bool full() const =0
virtual void addPoint(DistanceType dist, int index)=0
Definition: result_set.h:287
BranchStruct()
Definition: result_set.h:55
bool full() const
Definition: result_set.h:112
void init()
Definition: result_set.h:248
GLuint index
Definition: core_c.h:986
size_t size() const
Definition: result_set.h:107
bool full() const
Definition: result_set.h:258
const CvMat const CvMat const CvMat CvMat CvMat CvMat CvMat CvSize CvMat CvMat * T
Definition: calib3d.hpp:270
DistanceType worst_distance_
Definition: result_set.h:377
void init(int *indices_, DistanceType *dists_)
Definition: result_set.h:98
void addPoint(DistanceType dist, int index)
Definition: result_set.h:405
T node
Definition: result_set.h:52
KNNResultSet(int capacity_)
Definition: result_set.h:161
void addPoint(DistanceType dist, int index)
Definition: result_set.h:263
void init(int *indices_, DistanceType *dists_)
Definition: result_set.h:165
RadiusUniqueResultSet(DistanceType radius)
Definition: result_set.h:454
size_t size() const
Definition: result_set.h:253
void clear()
Definition: result_set.h:471
virtual void sortAndCopy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:351
Definition: result_set.h:229
void clear()
Definition: result_set.h:523
DistanceType dist_
Definition: result_set.h:300
GLuint GLuint GLsizei GLenum const GLvoid * indices
Definition: legacy.hpp:3084
DistanceType worstDist() const
Definition: result_set.h:274
int index
Definition: core_c.h:309
size_t size() const
Definition: result_set.h:359
virtual DistanceType worstDist() const =0
Definition: result_set.h:152
Definition: result_set.h:507
KNNUniqueResultSet(unsigned int capacity)
Definition: result_set.h:395
bool full() const
Definition: result_set.h:480
size_t size() const
Definition: result_set.h:174
GLuint GLuint GLsizei count
Definition: core_c.h:973
Definition: result_set.h:290
RadiusResultSet(DistanceType radius_, int *indices_, DistanceType *dists_, int capacity_)
Definition: result_set.h:238
void clear()
Definition: result_set.h:425
bool full() const
Definition: result_set.h:179
virtual ~ResultSet()
Definition: result_set.h:69
Definition: result_set.h:389
void addPoint(DistanceType dist, int index)
Definition: result_set.h:185
UniqueResultSet()
Definition: result_set.h:305
virtual void copy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:327
const CvMat CvMat * indices
Definition: legacy.hpp:3052
Definition: result_set.h:66
std::set< DistIndex > dist_indices_
Definition: result_set.h:380
UniqueResultSet< DistanceType >::DistIndex DistIndex
Definition: result_set.h:433
Definition: result_set.h:448
Definition: result_set.h:85
bool full() const
Definition: result_set.h:313
DistanceType mindist
Definition: result_set.h:53
DistanceType worstDist() const
Definition: result_set.h:368
bool operator<(const DistIndex dist_index) const
Definition: result_set.h:296
void addPoint(DistanceType dist, int index)
Definition: result_set.h:464
void addPoint(DistanceType dist, int index)
Definition: result_set.h:118
KNNSimpleResultSet(int capacity_)
Definition: result_set.h:94
DistanceType worstDist() const
Definition: result_set.h:218
DistanceType worstDist() const
Definition: result_set.h:142
CvPoint int radius
Definition: core_c.h:1290
CvPoint3D64f double * dist
Definition: legacy.hpp:556
~RadiusResultSet()
Definition: result_set.h:244
Definition: result_set.h:50
virtual void clear()=0
unsigned int capacity_
Definition: result_set.h:439
BranchStruct(const T &aNode, DistanceType dist)
Definition: result_set.h:56
bool is_full_
Definition: result_set.h:374
DistanceType worstDist() const
Definition: result_set.h:489
unsigned int index_
Definition: result_set.h:301