modules/flann/include/opencv2/flann/result_set.h

   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>
  50 struct BranchStruct
  51 {
  52     T node;           /* Tree node at which search resumes */
  53     DistanceType mindist;     /* Minimum distance to query for all nodes below. */
  54
  55     BranchStruct() {}
  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
  79 /**
  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.
  83  */
  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
 148 /**
 149  * K-Nearest neighbour result set. Ensures that the elements inserted are unique
 150  */
 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
 225 /**
 226  * A result-set class used when performing a radius based search.
 227  */
 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
 244     ~RadiusResultSet()
 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
 281 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 282
 283 /** Class that holds the k NN neighbors
 284  * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
 285  */
 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
 304     /** Default cosntructor */
 305     UniqueResultSet() :
 306         worst_distance_(std::numeric_limits<DistanceType>::max())
 307     {
 308     }
 309
 310     /** Check the status of the set
 311      * @return true if we have k NN
 312      */
 313     inline bool full() const
 314     {
 315         return is_full_;
 316     }
 317
 318     /** Remove all elements in the set
 319      */
 320     virtual void clear() = 0;
 321
 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
 326      */
 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
 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
 350      */
 351     virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
 352     {
 353         copy(indices, dist, n_neighbors);
 354     }
 355
 356     /** The number of neighbors in the set
 357      * @return
 358      */
 359     size_t size() const
 360     {
 361         return dist_indices_.size();
 362     }
 363
 364     /** The distance of the furthest neighbor
 365      * If we don't have enough neighbors, it returns the max possible value
 366      * @return
 367      */
 368     inline DistanceType worstDist() const
 369     {
 370         return worst_distance_;
 371     }
 372 protected:
 373     /** Flag to say if the set is full */
 374     bool is_full_;
 375
 376     /** The worst distance found so far */
 377     DistanceType worst_distance_;
 378
 379     /** The best candidates so far */
 380     std::set<DistIndex> dist_indices_;
 381 };
 382
 383 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 384
 385 /** Class that holds the k NN neighbors
 386  * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
 387  */
 388 template<typename DistanceType>
 389 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
 390 {
 391 public:
 392     /** Constructor
 393      * @param capacity the number of neighbors to store at max
 394      */
 395     KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
 396     {
 397         this->is_full_ = false;
 398         this->clear();
 399     }
 400
 401     /** Add a possible candidate to the best neighbors
 402      * @param dist distance for that neighbor
 403      * @param index index of that neighbor
 404      */
 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
 423     /** Remove all elements in the set
 424      */
 425     void clear()
 426     {
 427         dist_indices_.clear();
 428         worst_distance_ = std::numeric_limits<DistanceType>::max();
 429         is_full_ = false;
 430     }
 431
 432 protected:
 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_;
 437
 438     /** The number of neighbors to keep */
 439     unsigned int capacity_;
 440 };
 441
 442 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 443
 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
 446  */
 447 template<typename DistanceType>
 448 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
 449 {
 450 public:
 451     /** Constructor
 452      * @param capacity the number of neighbors to store at max
 453      */
 454     RadiusUniqueResultSet(DistanceType radius) :
 455         radius_(radius)
 456     {
 457         is_full_ = true;
 458     }
 459
 460     /** Add a possible candidate to the best neighbors
 461      * @param dist distance for that neighbor
 462      * @param index index of that neighbor
 463      */
 464     void addPoint(DistanceType dist, int index)
 465     {
 466         if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
 467     }
 468
 469     /** Remove all elements in the set
 470      */
 471     inline void clear()
 472     {
 473         dist_indices_.clear();
 474     }
 475
 476
 477     /** Check the status of the set
 478      * @return alwys false
 479      */
 480     inline bool full() const
 481     {
 482         return true;
 483     }
 484
 485     /** The distance of the furthest neighbor
 486      * If we don't have enough neighbors, it returns the max possible value
 487      * @return
 488      */
 489     inline DistanceType worstDist() const
 490     {
 491         return radius_;
 492     }
 493 private:
 494     typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
 495     using UniqueResultSet<DistanceType>::dist_indices_;
 496     using UniqueResultSet<DistanceType>::is_full_;
 497
 498     /** The furthest distance a neighbor can be */
 499     DistanceType radius_;
 500 };
 501
 502 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 503
 504 /** Class that holds the k NN neighbors within a radius distance
 505  */
 506 template<typename DistanceType>
 507 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
 508 {
 509 public:
 510     /** Constructor
 511      * @param capacity the number of neighbors to store at max
 512      */
 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
 521     /** Remove all elements in the set
 522      */
 523     void clear()
 524     {
 525         dist_indices_.clear();
 526         worst_distance_ = radius_;
 527         is_full_ = false;
 528     }
 529 private:
 530     using KNNUniqueResultSet<DistanceType>::dist_indices_;
 531     using KNNUniqueResultSet<DistanceType>::is_full_;
 532     using KNNUniqueResultSet<DistanceType>::worst_distance_;
 533
 534     /** The maximum number of neighbors to consider */
 535     unsigned int capacity_;
 536
 537     /** The maximum distance of a neighbor */
 538     DistanceType radius_;
 539 };
 540 }
 541
 542 #endif //OPENCV_FLANN_RESULTSET_H