Cinder

  • Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

include/opencv2/flann/result_set.h

Go to the documentation of this file.
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_RESULTSET_H_
00032 #define _OPENCV_RESULTSET_H_
00033 
00034 
00035 #include <algorithm>
00036 #include <limits>
00037 #include <vector>
00038 #include "opencv2/flann/dist.h"
00039 
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>
00050 struct BranchStruct {
00051     T node;           /* Tree node at which search resumes */
00052     float mindistsq;     /* Minimum distance to query for all nodes below. */
00053 
00054     bool operator<(const BranchStruct<T>& rhs)
00055     {
00056         return mindistsq<rhs.mindistsq;
00057     }
00058 
00059     static BranchStruct<T> make_branch(const T& aNode, float dist)
00060     {
00061         BranchStruct<T> branch;
00062         branch.node = aNode;
00063         branch.mindistsq = dist;
00064         return branch;
00065     }
00066 };
00067 
00068 
00069 
00070 
00071 
00072 template <typename ELEM_TYPE>
00073 class ResultSet
00074 {
00075 protected:
00076 
00077 public:
00078 
00079     virtual ~ResultSet() {};
00080 
00081     virtual void init(const ELEM_TYPE* target_, int veclen_) = 0;
00082 
00083     virtual int* getNeighbors() = 0;
00084 
00085     virtual float* getDistances() = 0;
00086 
00087     virtual size_t size() const = 0;
00088 
00089     virtual bool full() const = 0;
00090 
00091     virtual bool addPoint(const ELEM_TYPE* point, int index) = 0;
00092 
00093     virtual float worstDist() const = 0;
00094 
00095 };
00096 
00097 
00098 template <typename ELEM_TYPE>
00099 class KNNResultSet : public ResultSet<ELEM_TYPE>
00100 {
00101     const ELEM_TYPE* target;
00102     const ELEM_TYPE* target_end;
00103     int veclen;
00104 
00105     int* indices;
00106     float* dists;
00107     int capacity;
00108 
00109     int count;
00110 
00111 public:
00112     KNNResultSet(int capacity_, ELEM_TYPE* target_ = NULL, int veclen_ = 0 ) :
00113             target(target_), veclen(veclen_), capacity(capacity_), count(0)
00114     {
00115         target_end = target + veclen;
00116 
00117         indices = new int[capacity_];
00118         dists = new float[capacity_];
00119     }
00120 
00121     ~KNNResultSet()
00122     {
00123         delete[] indices;
00124         delete[] dists;
00125     }
00126 
00127     void init(const ELEM_TYPE* target_, int veclen_)
00128     {
00129         target = target_;
00130         veclen = veclen_;
00131         target_end = target + veclen;
00132         count = 0;
00133     }
00134 
00135 
00136     int* getNeighbors()
00137     {
00138         return indices;
00139     }
00140 
00141     float* getDistances()
00142     {
00143         return dists;
00144     }
00145 
00146     size_t size() const
00147     {
00148         return count;
00149     }
00150 
00151     bool full() const
00152     {
00153         return count == capacity;
00154     }
00155 
00156 
00157     bool addPoint(const ELEM_TYPE* point, int index)
00158     {
00159         for (int i=0;i<count;++i) {
00160             if (indices[i]==index) return false;
00161         }
00162         float dist = (float)flann_dist(target, target_end, point);
00163 
00164         if (count<capacity) {
00165             indices[count] = index;
00166             dists[count] = dist;
00167             ++count;
00168         }
00169         else if (dist < dists[count-1] || (dist == dists[count-1] && index < indices[count-1])) {
00170 //         else if (dist < dists[count-1]) {
00171             indices[count-1] = index;
00172             dists[count-1] = dist;
00173         }
00174         else {
00175             return false;
00176         }
00177 
00178         int i = count-1;
00179         // bubble up
00180         while (i>=1 && (dists[i]<dists[i-1] || (dists[i]==dists[i-1] && indices[i]<indices[i-1]) ) ) {
00181 //         while (i>=1 && (dists[i]<dists[i-1]) ) {
00182             std::swap(indices[i],indices[i-1]);
00183             std::swap(dists[i],dists[i-1]);
00184             i--;
00185         }
00186 
00187         return true;
00188     }
00189 
00190     float worstDist() const
00191     {
00192         return (count<capacity) ? (std::numeric_limits<float>::max)() : dists[count-1];
00193     }
00194 };
00195 
00196 
00200 template <typename ELEM_TYPE>
00201 class RadiusResultSet : public ResultSet<ELEM_TYPE>
00202 {
00203     const ELEM_TYPE* target;
00204     const ELEM_TYPE* target_end;
00205     int veclen;
00206 
00207     struct Item {
00208         int index;
00209         float dist;
00210 
00211         bool operator<(Item rhs) {
00212             return dist<rhs.dist;
00213         }
00214     };
00215 
00216     std::vector<Item> items;
00217     float radius;
00218 
00219     bool sorted;
00220     int* indices;
00221     float* dists;
00222     size_t count;
00223 
00224 private:
00225     void resize_vecs()
00226     {
00227         if (items.size()>count) {
00228             if (indices!=NULL) delete[] indices;
00229             if (dists!=NULL) delete[] dists;
00230             count = items.size();
00231             indices = new int[count];
00232             dists = new float[count];
00233         }
00234     }
00235 
00236 public:
00237     RadiusResultSet(float radius_) :
00238         radius(radius_), indices(NULL), dists(NULL)
00239     {
00240         sorted = false;
00241         items.reserve(16);
00242         count = 0;
00243     }
00244 
00245     ~RadiusResultSet()
00246     {
00247         if (indices!=NULL) delete[] indices;
00248         if (dists!=NULL) delete[] dists;
00249     }
00250 
00251     void init(const ELEM_TYPE* target_, int veclen_)
00252     {
00253         target = target_;
00254         veclen = veclen_;
00255         target_end = target + veclen;
00256         items.clear();
00257         sorted = false;
00258     }
00259 
00260     int* getNeighbors()
00261     {
00262         if (!sorted) {
00263             sorted = true;
00264             sort_heap(items.begin(), items.end());
00265         }
00266         resize_vecs();
00267         for (size_t i=0;i<items.size();++i) {
00268             indices[i] = items[i].index;
00269         }
00270         return indices;
00271     }
00272 
00273     float* getDistances()
00274     {
00275         if (!sorted) {
00276             sorted = true;
00277             sort_heap(items.begin(), items.end());
00278         }
00279         resize_vecs();
00280         for (size_t i=0;i<items.size();++i) {
00281             dists[i] = items[i].dist;
00282         }
00283         return dists;
00284     }
00285 
00286     size_t size() const
00287     {
00288         return items.size();
00289     }
00290 
00291     bool full() const
00292     {
00293         return true;
00294     }
00295 
00296     bool addPoint(const ELEM_TYPE* point, int index)
00297     {
00298         Item it;
00299         it.index = index;
00300         it.dist = (float)flann_dist(target, target_end, point);
00301         if (it.dist<=radius) {
00302             items.push_back(it);
00303             push_heap(items.begin(), items.end());
00304             return true;
00305         }
00306         return false;
00307     }
00308 
00309     float worstDist() const
00310     {
00311         return radius;
00312     }
00313 
00314 };
00315 
00316 } // namespace cvflann
00317 
00318 #endif //_OPENCV_RESULTSET_H_