Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
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
00045
00046
00047
00048
00049 template <typename T>
00050 struct BranchStruct {
00051 T node;
00052 float mindistsq;
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
00171 indices[count-1] = index;
00172 dists[count-1] = dist;
00173 }
00174 else {
00175 return false;
00176 }
00177
00178 int i = count-1;
00179
00180 while (i>=1 && (dists[i]<dists[i-1] || (dists[i]==dists[i-1] && indices[i]<indices[i-1]) ) ) {
00181
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 }
00317
00318 #endif //_OPENCV_RESULTSET_H_