1 /***********************************************************************
2 * Software License Agreement (BSD License)
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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 *************************************************************************/
31 #ifndef OPENCV_FLANN_RESULTSET_H
32 #define OPENCV_FLANN_RESULTSET_H
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.
49 template <typename T, typename DistanceType>
52 T node; /* Tree node at which search resumes */
53 DistanceType mindist; /* Minimum distance to query for all nodes below. */
56 BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {}
58 bool operator<(const BranchStruct<T, DistanceType>& rhs) const
60 return mindist<rhs.mindist;
65 template <typename DistanceType>
69 virtual ~ResultSet() {}
71 virtual bool full() const = 0;
73 virtual void addPoint(DistanceType dist, int index) = 0;
75 virtual DistanceType worstDist() const = 0;
80 * KNNSimpleResultSet does not ensure that the element it holds are unique.
81 * Is used in those cases where the nearest neighbour algorithm used does not
82 * attempt to insert the same element multiple times.
84 template <typename DistanceType>
85 class KNNSimpleResultSet : public ResultSet<DistanceType>
91 DistanceType worst_distance_;
94 KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0)
98 void init(int* indices_, DistanceType* dists_)
103 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
104 dists[capacity-1] = worst_distance_;
114 return count == capacity;
118 void addPoint(DistanceType dist, int index)
120 if (dist >= worst_distance_) return;
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)) )
130 dists[i] = dists[i-1];
131 indices[i] = indices[i-1];
136 if (count < capacity) ++count;
139 worst_distance_ = dists[capacity-1];
142 DistanceType worstDist() const
144 return worst_distance_;
149 * K-Nearest neighbour result set. Ensures that the elements inserted are unique
151 template <typename DistanceType>
152 class KNNResultSet : public ResultSet<DistanceType>
158 DistanceType worst_distance_;
161 KNNResultSet(int capacity_) : capacity(capacity_), count(0)
165 void init(int* indices_, DistanceType* dists_)
170 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
171 dists[capacity-1] = worst_distance_;
181 return count == capacity;
185 void addPoint(DistanceType dist, int index)
187 if (dist >= worst_distance_) return;
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)) )
193 if (dists[i-1]<=dist)
196 // Check for duplicate indices
198 while ((j >= 0) && (dists[j] == dist)) {
199 if (indices[j] == index) {
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];
215 worst_distance_ = dists[capacity-1];
218 DistanceType worstDist() const
220 return worst_distance_;
226 * A result-set class used when performing a radius based search.
228 template <typename DistanceType>
229 class RadiusResultSet : public ResultSet<DistanceType>
238 RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) :
239 radius(radius_), indices(indices_), dists(dists_), capacity(capacity_)
263 void addPoint(DistanceType dist, int index)
266 if ((capacity>0)&&(count < capacity)) {
268 indices[count] = index;
274 DistanceType worstDist() const
281 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
283 /** Class that holds the k NN neighbors
284 * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
286 template<typename DistanceType>
287 class UniqueResultSet : public ResultSet<DistanceType>
292 DistIndex(DistanceType dist, unsigned int index) :
293 dist_(dist), index_(index)
296 bool operator<(const DistIndex dist_index) const
298 return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_);
304 /** Default cosntructor */
306 worst_distance_(std::numeric_limits<DistanceType>::max())
310 /** Check the status of the set
311 * @return true if we have k NN
313 inline bool full() const
318 /** Remove all elements in the set
320 virtual void clear() = 0;
322 /** Copy the set to two C arrays
323 * @param indices pointer to a C array of indices
324 * @param dist pointer to a C array of distances
325 * @param n_neighbors the number of neighbors to copy
327 virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const
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_;
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_;
346 /** Copy the set to two C arrays but sort it according to the distance first
347 * @param indices pointer to a C array of indices
348 * @param dist pointer to a C array of distances
349 * @param n_neighbors the number of neighbors to copy
351 virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
353 copy(indices, dist, n_neighbors);
356 /** The number of neighbors in the set
361 return dist_indices_.size();
364 /** The distance of the furthest neighbor
365 * If we don't have enough neighbors, it returns the max possible value
368 inline DistanceType worstDist() const
370 return worst_distance_;
373 /** Flag to say if the set is full */
376 /** The worst distance found so far */
377 DistanceType worst_distance_;
379 /** The best candidates so far */
380 std::set<DistIndex> dist_indices_;
383 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
385 /** Class that holds the k NN neighbors
386 * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
388 template<typename DistanceType>
389 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
393 * @param capacity the number of neighbors to store at max
395 KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
397 this->is_full_ = false;
401 /** Add a possible candidate to the best neighbors
402 * @param dist distance for that neighbor
403 * @param index index of that neighbor
405 inline void addPoint(DistanceType dist, int index)
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));
412 if (dist_indices_.size() > capacity_) {
413 dist_indices_.erase(*dist_indices_.rbegin());
414 worst_distance_ = dist_indices_.rbegin()->dist_;
417 else if (dist_indices_.size() == capacity_) {
419 worst_distance_ = dist_indices_.rbegin()->dist_;
423 /** Remove all elements in the set
427 dist_indices_.clear();
428 worst_distance_ = std::numeric_limits<DistanceType>::max();
433 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
434 using UniqueResultSet<DistanceType>::is_full_;
435 using UniqueResultSet<DistanceType>::worst_distance_;
436 using UniqueResultSet<DistanceType>::dist_indices_;
438 /** The number of neighbors to keep */
439 unsigned int capacity_;
442 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
444 /** Class that holds the radius nearest neighbors
445 * It is more accurate than RadiusResult as it is not limited in the number of neighbors
447 template<typename DistanceType>
448 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
452 * @param capacity the number of neighbors to store at max
454 RadiusUniqueResultSet(DistanceType radius) :
460 /** Add a possible candidate to the best neighbors
461 * @param dist distance for that neighbor
462 * @param index index of that neighbor
464 void addPoint(DistanceType dist, int index)
466 if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
469 /** Remove all elements in the set
473 dist_indices_.clear();
477 /** Check the status of the set
478 * @return alwys false
480 inline bool full() const
485 /** The distance of the furthest neighbor
486 * If we don't have enough neighbors, it returns the max possible value
489 inline DistanceType worstDist() const
494 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
495 using UniqueResultSet<DistanceType>::dist_indices_;
496 using UniqueResultSet<DistanceType>::is_full_;
498 /** The furthest distance a neighbor can be */
499 DistanceType radius_;
502 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
504 /** Class that holds the k NN neighbors within a radius distance
506 template<typename DistanceType>
507 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
511 * @param capacity the number of neighbors to store at max
513 KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
515 this->capacity_ = capacity;
516 this->radius_ = radius;
517 this->dist_indices_.reserve(capacity_);
521 /** Remove all elements in the set
525 dist_indices_.clear();
526 worst_distance_ = radius_;
530 using KNNUniqueResultSet<DistanceType>::dist_indices_;
531 using KNNUniqueResultSet<DistanceType>::is_full_;
532 using KNNUniqueResultSet<DistanceType>::worst_distance_;
534 /** The maximum number of neighbors to consider */
535 unsigned int capacity_;
537 /** The maximum distance of a neighbor */
538 DistanceType radius_;
542 #endif //OPENCV_FLANN_RESULTSET_H