result_set.h

00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *************************************************************************/
00030 
00031 #ifndef OPENCV_FLANN_RESULTSET_H
00032 #define OPENCV_FLANN_RESULTSET_H
00033 
00034 #include <algorithm>
00035 #include <cstring>
00036 #include <iostream>
00037 #include <limits>
00038 #include <set>
00039 #include <vector>
00040 
00041 namespace cvflann
00042 {
00043 
00044 /* This record represents a branch point when finding neighbors in
00045     the tree.  It contains a record of the minimum distance to the query
00046     point, as well as the node at which the search resumes.
00047  */
00048 
00049 template <typename T, typename DistanceType>
00050 struct BranchStruct
00051 {
00052     T node;           /* Tree node at which search resumes */
00053     DistanceType mindist;     /* Minimum distance to query for all nodes below. */
00054 
00055     BranchStruct() {}
00056     BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {}
00057 
00058     bool operator<(const BranchStruct<T, DistanceType>& rhs) const
00059     {
00060         return mindist<rhs.mindist;
00061     }
00062 };
00063 
00064 
00065 template <typename DistanceType>
00066 class ResultSet
00067 {
00068 public:
00069     virtual ~ResultSet() {}
00070 
00071     virtual bool full() const = 0;
00072 
00073     virtual void addPoint(DistanceType dist, int index) = 0;
00074 
00075     virtual DistanceType worstDist() const = 0;
00076 
00077 };
00078 
00079 /**
00080  * KNNSimpleResultSet does not ensure that the element it holds are unique.
00081  * Is used in those cases where the nearest neighbour algorithm used does not
00082  * attempt to insert the same element multiple times.
00083  */
00084 template <typename DistanceType>
00085 class KNNSimpleResultSet : public ResultSet<DistanceType>
00086 {
00087     int* indices;
00088     DistanceType* dists;
00089     int capacity;
00090     int count;
00091     DistanceType worst_distance_;
00092 
00093 public:
00094     KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0)
00095     {
00096     }
00097 
00098     void init(int* indices_, DistanceType* dists_)
00099     {
00100         indices = indices_;
00101         dists = dists_;
00102         count = 0;
00103         worst_distance_ = (std::numeric_limits<DistanceType>::max)();
00104         dists[capacity-1] = worst_distance_;
00105     }
00106 
00107     size_t size() const
00108     {
00109         return count;
00110     }
00111 
00112     bool full() const
00113     {
00114         return count == capacity;
00115     }
00116 
00117 
00118     void addPoint(DistanceType dist, int index)
00119     {
00120         if (dist >= worst_distance_) return;
00121         int i;
00122         for (i=count; i>0; --i) {
00123 #ifdef FLANN_FIRST_MATCH
00124             if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) )
00125 #else
00126             if (dists[i-1]>dist)
00127 #endif
00128             {
00129                 if (i<capacity) {
00130                     dists[i] = dists[i-1];
00131                     indices[i] = indices[i-1];
00132                 }
00133             }
00134             else break;
00135         }
00136         if (count < capacity) ++count;
00137         dists[i] = dist;
00138         indices[i] = index;
00139         worst_distance_ = dists[capacity-1];
00140     }
00141 
00142     DistanceType worstDist() const
00143     {
00144         return worst_distance_;
00145     }
00146 };
00147 
00148 /**
00149  * K-Nearest neighbour result set. Ensures that the elements inserted are unique
00150  */
00151 template <typename DistanceType>
00152 class KNNResultSet : public ResultSet<DistanceType>
00153 {
00154     int* indices;
00155     DistanceType* dists;
00156     int capacity;
00157     int count;
00158     DistanceType worst_distance_;
00159 
00160 public:
00161     KNNResultSet(int capacity_) : capacity(capacity_), count(0)
00162     {
00163     }
00164 
00165     void init(int* indices_, DistanceType* dists_)
00166     {
00167         indices = indices_;
00168         dists = dists_;
00169         count = 0;
00170         worst_distance_ = (std::numeric_limits<DistanceType>::max)();
00171         dists[capacity-1] = worst_distance_;
00172     }
00173 
00174     size_t size() const
00175     {
00176         return count;
00177     }
00178 
00179     bool full() const
00180     {
00181         return count == capacity;
00182     }
00183 
00184 
00185     void addPoint(DistanceType dist, int index)
00186     {
00187         if (dist >= worst_distance_) return;
00188         int i;
00189         for (i = count; i > 0; --i) {
00190 #ifdef FLANN_FIRST_MATCH
00191             if ( (dists[i-1]<=dist) && ((dist!=dists[i-1])||(indices[i-1]<=index)) )
00192 #else
00193             if (dists[i-1]<=dist)
00194 #endif
00195             {
00196                 // Check for duplicate indices
00197                 int j = i - 1;
00198                 while ((j >= 0) && (dists[j] == dist)) {
00199                     if (indices[j] == index) {
00200                         return;
00201                     }
00202                     --j;
00203                 }
00204                 break;
00205             }
00206         }
00207 
00208         if (count < capacity) ++count;
00209         for (int j = count-1; j > i; --j) {
00210             dists[j] = dists[j-1];
00211             indices[j] = indices[j-1];
00212         }
00213         dists[i] = dist;
00214         indices[i] = index;
00215         worst_distance_ = dists[capacity-1];
00216     }
00217 
00218     DistanceType worstDist() const
00219     {
00220         return worst_distance_;
00221     }
00222 };
00223 
00224 
00225 /**
00226  * A result-set class used when performing a radius based search.
00227  */
00228 template <typename DistanceType>
00229 class RadiusResultSet : public ResultSet<DistanceType>
00230 {
00231     DistanceType radius;
00232     int* indices;
00233     DistanceType* dists;
00234     size_t capacity;
00235     size_t count;
00236 
00237 public:
00238     RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) :
00239         radius(radius_), indices(indices_), dists(dists_), capacity(capacity_)
00240     {
00241         init();
00242     }
00243 
00244     ~RadiusResultSet()
00245     {
00246     }
00247 
00248     void init()
00249     {
00250         count = 0;
00251     }
00252 
00253     size_t size() const
00254     {
00255         return count;
00256     }
00257 
00258     bool full() const
00259     {
00260         return true;
00261     }
00262 
00263     void addPoint(DistanceType dist, int index)
00264     {
00265         if (dist<radius) {
00266             if ((capacity>0)&&(count < capacity)) {
00267                 dists[count] = dist;
00268                 indices[count] = index;
00269             }
00270             count++;
00271         }
00272     }
00273 
00274     DistanceType worstDist() const
00275     {
00276         return radius;
00277     }
00278 
00279 };
00280 
00281 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
00282 
00283 /** Class that holds the k NN neighbors
00284  * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
00285  */
00286 template<typename DistanceType>
00287 class UniqueResultSet : public ResultSet<DistanceType>
00288 {
00289 public:
00290     struct DistIndex
00291     {
00292         DistIndex(DistanceType dist, unsigned int index) :
00293             dist_(dist), index_(index)
00294         {
00295         }
00296         bool operator<(const DistIndex dist_index) const
00297         {
00298             return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_);
00299         }
00300         DistanceType dist_;
00301         unsigned int index_;
00302     };
00303 
00304     /** Default cosntructor */
00305     UniqueResultSet() :
00306         worst_distance_(std::numeric_limits<DistanceType>::max())
00307     {
00308     }
00309 
00310     /** Check the status of the set
00311      * @return true if we have k NN
00312      */
00313     inline bool full() const
00314     {
00315         return is_full_;
00316     }
00317 
00318     /** Remove all elements in the set
00319      */
00320     virtual void clear() = 0;
00321 
00322     /** Copy the set to two C arrays
00323      * @param indices pointer to a C array of indices
00324      * @param dist pointer to a C array of distances
00325      * @param n_neighbors the number of neighbors to copy
00326      */
00327     virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const
00328     {
00329         if (n_neighbors < 0) {
00330             for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
00331                      dist_indices_.end(); dist_index != dist_index_end; ++dist_index, ++indices, ++dist) {
00332                 *indices = dist_index->index_;
00333                 *dist = dist_index->dist_;
00334             }
00335         }
00336         else {
00337             int i = 0;
00338             for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
00339                      dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) {
00340                 *indices = dist_index->index_;
00341                 *dist = dist_index->dist_;
00342             }
00343         }
00344     }
00345 
00346     /** Copy the set to two C arrays but sort it according to the distance first
00347      * @param indices pointer to a C array of indices
00348      * @param dist pointer to a C array of distances
00349      * @param n_neighbors the number of neighbors to copy
00350      */
00351     virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
00352     {
00353         copy(indices, dist, n_neighbors);
00354     }
00355 
00356     /** The number of neighbors in the set
00357      * @return
00358      */
00359     size_t size() const
00360     {
00361         return dist_indices_.size();
00362     }
00363 
00364     /** The distance of the furthest neighbor
00365      * If we don't have enough neighbors, it returns the max possible value
00366      * @return
00367      */
00368     inline DistanceType worstDist() const
00369     {
00370         return worst_distance_;
00371     }
00372 protected:
00373     /** Flag to say if the set is full */
00374     bool is_full_;
00375 
00376     /** The worst distance found so far */
00377     DistanceType worst_distance_;
00378 
00379     /** The best candidates so far */
00380     std::set<DistIndex> dist_indices_;
00381 };
00382 
00383 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
00384 
00385 /** Class that holds the k NN neighbors
00386  * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
00387  */
00388 template<typename DistanceType>
00389 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
00390 {
00391 public:
00392     /** Constructor
00393      * @param capacity the number of neighbors to store at max
00394      */
00395     KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
00396     {
00397         this->is_full_ = false;
00398         this->clear();
00399     }
00400 
00401     /** Add a possible candidate to the best neighbors
00402      * @param dist distance for that neighbor
00403      * @param index index of that neighbor
00404      */
00405     inline void addPoint(DistanceType dist, int index)
00406     {
00407         // Don't do anything if we are worse than the worst
00408         if (dist >= worst_distance_) return;
00409         dist_indices_.insert(DistIndex(dist, index));
00410 
00411         if (is_full_) {
00412             if (dist_indices_.size() > capacity_) {
00413                 dist_indices_.erase(*dist_indices_.rbegin());
00414                 worst_distance_ = dist_indices_.rbegin()->dist_;
00415             }
00416         }
00417         else if (dist_indices_.size() == capacity_) {
00418             is_full_ = true;
00419             worst_distance_ = dist_indices_.rbegin()->dist_;
00420         }
00421     }
00422 
00423     /** Remove all elements in the set
00424      */
00425     void clear()
00426     {
00427         dist_indices_.clear();
00428         worst_distance_ = std::numeric_limits<DistanceType>::max();
00429         is_full_ = false;
00430     }
00431 
00432 protected:
00433     typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
00434     using UniqueResultSet<DistanceType>::is_full_;
00435     using UniqueResultSet<DistanceType>::worst_distance_;
00436     using UniqueResultSet<DistanceType>::dist_indices_;
00437 
00438     /** The number of neighbors to keep */
00439     unsigned int capacity_;
00440 };
00441 
00442 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
00443 
00444 /** Class that holds the radius nearest neighbors
00445  * It is more accurate than RadiusResult as it is not limited in the number of neighbors
00446  */
00447 template<typename DistanceType>
00448 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
00449 {
00450 public:
00451     /** Constructor
00452      * @param radius the maximum distance of a neighbor
00453      */
00454     RadiusUniqueResultSet(DistanceType radius) :
00455         radius_(radius)
00456     {
00457         is_full_ = true;
00458     }
00459 
00460     /** Add a possible candidate to the best neighbors
00461      * @param dist distance for that neighbor
00462      * @param index index of that neighbor
00463      */
00464     void addPoint(DistanceType dist, int index)
00465     {
00466         if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
00467     }
00468 
00469     /** Remove all elements in the set
00470      */
00471     inline void clear()
00472     {
00473         dist_indices_.clear();
00474     }
00475 
00476 
00477     /** Check the status of the set
00478      * @return alwys false
00479      */
00480     inline bool full() const
00481     {
00482         return true;
00483     }
00484 
00485     /** The distance of the furthest neighbor
00486      * If we don't have enough neighbors, it returns the max possible value
00487      * @return
00488      */
00489     inline DistanceType worstDist() const
00490     {
00491         return radius_;
00492     }
00493 private:
00494     typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
00495     using UniqueResultSet<DistanceType>::dist_indices_;
00496     using UniqueResultSet<DistanceType>::is_full_;
00497 
00498     /** The furthest distance a neighbor can be */
00499     DistanceType radius_;
00500 };
00501 
00502 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
00503 
00504 /** Class that holds the k NN neighbors within a radius distance
00505  */
00506 template<typename DistanceType>
00507 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
00508 {
00509 public:
00510     /** Constructor
00511      * @param capacity the number of neighbors to store at max
00512      * @param radius the maximum distance of a neighbor
00513      */
00514     KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
00515     {
00516         this->capacity_ = capacity;
00517         this->radius_ = radius;
00518         this->dist_indices_.reserve(capacity_);
00519         this->clear();
00520     }
00521 
00522     /** Remove all elements in the set
00523      */
00524     void clear()
00525     {
00526         dist_indices_.clear();
00527         worst_distance_ = radius_;
00528         is_full_ = false;
00529     }
00530 private:
00531     using KNNUniqueResultSet<DistanceType>::dist_indices_;
00532     using KNNUniqueResultSet<DistanceType>::is_full_;
00533     using KNNUniqueResultSet<DistanceType>::worst_distance_;
00534 
00535     /** The maximum number of neighbors to consider */
00536     unsigned int capacity_;
00537 
00538     /** The maximum distance of a neighbor */
00539     DistanceType radius_;
00540 };
00541 }
00542 
00543 #endif //OPENCV_FLANN_RESULTSET_H
00544