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_