Joe Verbout / Mbed 2 deprecated main

opencv on mbed

Dependencies:   mbed

opencv2/flann/result_set.h@0:ea44dc9ed014, 2016-03-31 (annotated)

Committer:
joeverbout
Date:
Thu Mar 31 21:16:38 2016 +0000
Revision:
0:ea44dc9ed014
OpenCV on mbed attempt

Who changed what in which revision?

UserRevisionLine numberNew contents of line
joeverbout 0:ea44dc9ed014 1 /***********************************************************************
joeverbout 0:ea44dc9ed014 2 * Software License Agreement (BSD License)
joeverbout 0:ea44dc9ed014 3 *
joeverbout 0:ea44dc9ed014 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 6 *
joeverbout 0:ea44dc9ed014 7 * THE BSD LICENSE
joeverbout 0:ea44dc9ed014 8 *
joeverbout 0:ea44dc9ed014 9 * Redistribution and use in source and binary forms, with or without
joeverbout 0:ea44dc9ed014 10 * modification, are permitted provided that the following conditions
joeverbout 0:ea44dc9ed014 11 * are met:
joeverbout 0:ea44dc9ed014 12 *
joeverbout 0:ea44dc9ed014 13 * 1. Redistributions of source code must retain the above copyright
joeverbout 0:ea44dc9ed014 14 * notice, this list of conditions and the following disclaimer.
joeverbout 0:ea44dc9ed014 15 * 2. Redistributions in binary form must reproduce the above copyright
joeverbout 0:ea44dc9ed014 16 * notice, this list of conditions and the following disclaimer in the
joeverbout 0:ea44dc9ed014 17 * documentation and/or other materials provided with the distribution.
joeverbout 0:ea44dc9ed014 18 *
joeverbout 0:ea44dc9ed014 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
joeverbout 0:ea44dc9ed014 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
joeverbout 0:ea44dc9ed014 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
joeverbout 0:ea44dc9ed014 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
joeverbout 0:ea44dc9ed014 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
joeverbout 0:ea44dc9ed014 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
joeverbout 0:ea44dc9ed014 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
joeverbout 0:ea44dc9ed014 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
joeverbout 0:ea44dc9ed014 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
joeverbout 0:ea44dc9ed014 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
joeverbout 0:ea44dc9ed014 29 *************************************************************************/
joeverbout 0:ea44dc9ed014 30
joeverbout 0:ea44dc9ed014 31 #ifndef OPENCV_FLANN_RESULTSET_H
joeverbout 0:ea44dc9ed014 32 #define OPENCV_FLANN_RESULTSET_H
joeverbout 0:ea44dc9ed014 33
joeverbout 0:ea44dc9ed014 34 #include <algorithm>
joeverbout 0:ea44dc9ed014 35 #include <cstring>
joeverbout 0:ea44dc9ed014 36 #include <iostream>
joeverbout 0:ea44dc9ed014 37 #include <limits>
joeverbout 0:ea44dc9ed014 38 #include <set>
joeverbout 0:ea44dc9ed014 39 #include <vector>
joeverbout 0:ea44dc9ed014 40
joeverbout 0:ea44dc9ed014 41 namespace cvflann
joeverbout 0:ea44dc9ed014 42 {
joeverbout 0:ea44dc9ed014 43
joeverbout 0:ea44dc9ed014 44 /* This record represents a branch point when finding neighbors in
joeverbout 0:ea44dc9ed014 45 the tree. It contains a record of the minimum distance to the query
joeverbout 0:ea44dc9ed014 46 point, as well as the node at which the search resumes.
joeverbout 0:ea44dc9ed014 47 */
joeverbout 0:ea44dc9ed014 48
joeverbout 0:ea44dc9ed014 49 template <typename T, typename DistanceType>
joeverbout 0:ea44dc9ed014 50 struct BranchStruct
joeverbout 0:ea44dc9ed014 51 {
joeverbout 0:ea44dc9ed014 52 T node; /* Tree node at which search resumes */
joeverbout 0:ea44dc9ed014 53 DistanceType mindist; /* Minimum distance to query for all nodes below. */
joeverbout 0:ea44dc9ed014 54
joeverbout 0:ea44dc9ed014 55 BranchStruct() {}
joeverbout 0:ea44dc9ed014 56 BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {}
joeverbout 0:ea44dc9ed014 57
joeverbout 0:ea44dc9ed014 58 bool operator<(const BranchStruct<T, DistanceType>& rhs) const
joeverbout 0:ea44dc9ed014 59 {
joeverbout 0:ea44dc9ed014 60 return mindist<rhs.mindist;
joeverbout 0:ea44dc9ed014 61 }
joeverbout 0:ea44dc9ed014 62 };
joeverbout 0:ea44dc9ed014 63
joeverbout 0:ea44dc9ed014 64
joeverbout 0:ea44dc9ed014 65 template <typename DistanceType>
joeverbout 0:ea44dc9ed014 66 class ResultSet
joeverbout 0:ea44dc9ed014 67 {
joeverbout 0:ea44dc9ed014 68 public:
joeverbout 0:ea44dc9ed014 69 virtual ~ResultSet() {}
joeverbout 0:ea44dc9ed014 70
joeverbout 0:ea44dc9ed014 71 virtual bool full() const = 0;
joeverbout 0:ea44dc9ed014 72
joeverbout 0:ea44dc9ed014 73 virtual void addPoint(DistanceType dist, int index) = 0;
joeverbout 0:ea44dc9ed014 74
joeverbout 0:ea44dc9ed014 75 virtual DistanceType worstDist() const = 0;
joeverbout 0:ea44dc9ed014 76
joeverbout 0:ea44dc9ed014 77 };
joeverbout 0:ea44dc9ed014 78
joeverbout 0:ea44dc9ed014 79 /**
joeverbout 0:ea44dc9ed014 80 * KNNSimpleResultSet does not ensure that the element it holds are unique.
joeverbout 0:ea44dc9ed014 81 * Is used in those cases where the nearest neighbour algorithm used does not
joeverbout 0:ea44dc9ed014 82 * attempt to insert the same element multiple times.
joeverbout 0:ea44dc9ed014 83 */
joeverbout 0:ea44dc9ed014 84 template <typename DistanceType>
joeverbout 0:ea44dc9ed014 85 class KNNSimpleResultSet : public ResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 86 {
joeverbout 0:ea44dc9ed014 87 int* indices;
joeverbout 0:ea44dc9ed014 88 DistanceType* dists;
joeverbout 0:ea44dc9ed014 89 int capacity;
joeverbout 0:ea44dc9ed014 90 int count;
joeverbout 0:ea44dc9ed014 91 DistanceType worst_distance_;
joeverbout 0:ea44dc9ed014 92
joeverbout 0:ea44dc9ed014 93 public:
joeverbout 0:ea44dc9ed014 94 KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0)
joeverbout 0:ea44dc9ed014 95 {
joeverbout 0:ea44dc9ed014 96 }
joeverbout 0:ea44dc9ed014 97
joeverbout 0:ea44dc9ed014 98 void init(int* indices_, DistanceType* dists_)
joeverbout 0:ea44dc9ed014 99 {
joeverbout 0:ea44dc9ed014 100 indices = indices_;
joeverbout 0:ea44dc9ed014 101 dists = dists_;
joeverbout 0:ea44dc9ed014 102 count = 0;
joeverbout 0:ea44dc9ed014 103 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
joeverbout 0:ea44dc9ed014 104 dists[capacity-1] = worst_distance_;
joeverbout 0:ea44dc9ed014 105 }
joeverbout 0:ea44dc9ed014 106
joeverbout 0:ea44dc9ed014 107 size_t size() const
joeverbout 0:ea44dc9ed014 108 {
joeverbout 0:ea44dc9ed014 109 return count;
joeverbout 0:ea44dc9ed014 110 }
joeverbout 0:ea44dc9ed014 111
joeverbout 0:ea44dc9ed014 112 bool full() const
joeverbout 0:ea44dc9ed014 113 {
joeverbout 0:ea44dc9ed014 114 return count == capacity;
joeverbout 0:ea44dc9ed014 115 }
joeverbout 0:ea44dc9ed014 116
joeverbout 0:ea44dc9ed014 117
joeverbout 0:ea44dc9ed014 118 void addPoint(DistanceType dist, int index)
joeverbout 0:ea44dc9ed014 119 {
joeverbout 0:ea44dc9ed014 120 if (dist >= worst_distance_) return;
joeverbout 0:ea44dc9ed014 121 int i;
joeverbout 0:ea44dc9ed014 122 for (i=count; i>0; --i) {
joeverbout 0:ea44dc9ed014 123 #ifdef FLANN_FIRST_MATCH
joeverbout 0:ea44dc9ed014 124 if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) )
joeverbout 0:ea44dc9ed014 125 #else
joeverbout 0:ea44dc9ed014 126 if (dists[i-1]>dist)
joeverbout 0:ea44dc9ed014 127 #endif
joeverbout 0:ea44dc9ed014 128 {
joeverbout 0:ea44dc9ed014 129 if (i<capacity) {
joeverbout 0:ea44dc9ed014 130 dists[i] = dists[i-1];
joeverbout 0:ea44dc9ed014 131 indices[i] = indices[i-1];
joeverbout 0:ea44dc9ed014 132 }
joeverbout 0:ea44dc9ed014 133 }
joeverbout 0:ea44dc9ed014 134 else break;
joeverbout 0:ea44dc9ed014 135 }
joeverbout 0:ea44dc9ed014 136 if (count < capacity) ++count;
joeverbout 0:ea44dc9ed014 137 dists[i] = dist;
joeverbout 0:ea44dc9ed014 138 indices[i] = index;
joeverbout 0:ea44dc9ed014 139 worst_distance_ = dists[capacity-1];
joeverbout 0:ea44dc9ed014 140 }
joeverbout 0:ea44dc9ed014 141
joeverbout 0:ea44dc9ed014 142 DistanceType worstDist() const
joeverbout 0:ea44dc9ed014 143 {
joeverbout 0:ea44dc9ed014 144 return worst_distance_;
joeverbout 0:ea44dc9ed014 145 }
joeverbout 0:ea44dc9ed014 146 };
joeverbout 0:ea44dc9ed014 147
joeverbout 0:ea44dc9ed014 148 /**
joeverbout 0:ea44dc9ed014 149 * K-Nearest neighbour result set. Ensures that the elements inserted are unique
joeverbout 0:ea44dc9ed014 150 */
joeverbout 0:ea44dc9ed014 151 template <typename DistanceType>
joeverbout 0:ea44dc9ed014 152 class KNNResultSet : public ResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 153 {
joeverbout 0:ea44dc9ed014 154 int* indices;
joeverbout 0:ea44dc9ed014 155 DistanceType* dists;
joeverbout 0:ea44dc9ed014 156 int capacity;
joeverbout 0:ea44dc9ed014 157 int count;
joeverbout 0:ea44dc9ed014 158 DistanceType worst_distance_;
joeverbout 0:ea44dc9ed014 159
joeverbout 0:ea44dc9ed014 160 public:
joeverbout 0:ea44dc9ed014 161 KNNResultSet(int capacity_) : capacity(capacity_), count(0)
joeverbout 0:ea44dc9ed014 162 {
joeverbout 0:ea44dc9ed014 163 }
joeverbout 0:ea44dc9ed014 164
joeverbout 0:ea44dc9ed014 165 void init(int* indices_, DistanceType* dists_)
joeverbout 0:ea44dc9ed014 166 {
joeverbout 0:ea44dc9ed014 167 indices = indices_;
joeverbout 0:ea44dc9ed014 168 dists = dists_;
joeverbout 0:ea44dc9ed014 169 count = 0;
joeverbout 0:ea44dc9ed014 170 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
joeverbout 0:ea44dc9ed014 171 dists[capacity-1] = worst_distance_;
joeverbout 0:ea44dc9ed014 172 }
joeverbout 0:ea44dc9ed014 173
joeverbout 0:ea44dc9ed014 174 size_t size() const
joeverbout 0:ea44dc9ed014 175 {
joeverbout 0:ea44dc9ed014 176 return count;
joeverbout 0:ea44dc9ed014 177 }
joeverbout 0:ea44dc9ed014 178
joeverbout 0:ea44dc9ed014 179 bool full() const
joeverbout 0:ea44dc9ed014 180 {
joeverbout 0:ea44dc9ed014 181 return count == capacity;
joeverbout 0:ea44dc9ed014 182 }
joeverbout 0:ea44dc9ed014 183
joeverbout 0:ea44dc9ed014 184
joeverbout 0:ea44dc9ed014 185 void addPoint(DistanceType dist, int index)
joeverbout 0:ea44dc9ed014 186 {
joeverbout 0:ea44dc9ed014 187 if (dist >= worst_distance_) return;
joeverbout 0:ea44dc9ed014 188 int i;
joeverbout 0:ea44dc9ed014 189 for (i = count; i > 0; --i) {
joeverbout 0:ea44dc9ed014 190 #ifdef FLANN_FIRST_MATCH
joeverbout 0:ea44dc9ed014 191 if ( (dists[i-1]<=dist) && ((dist!=dists[i-1])||(indices[i-1]<=index)) )
joeverbout 0:ea44dc9ed014 192 #else
joeverbout 0:ea44dc9ed014 193 if (dists[i-1]<=dist)
joeverbout 0:ea44dc9ed014 194 #endif
joeverbout 0:ea44dc9ed014 195 {
joeverbout 0:ea44dc9ed014 196 // Check for duplicate indices
joeverbout 0:ea44dc9ed014 197 int j = i - 1;
joeverbout 0:ea44dc9ed014 198 while ((j >= 0) && (dists[j] == dist)) {
joeverbout 0:ea44dc9ed014 199 if (indices[j] == index) {
joeverbout 0:ea44dc9ed014 200 return;
joeverbout 0:ea44dc9ed014 201 }
joeverbout 0:ea44dc9ed014 202 --j;
joeverbout 0:ea44dc9ed014 203 }
joeverbout 0:ea44dc9ed014 204 break;
joeverbout 0:ea44dc9ed014 205 }
joeverbout 0:ea44dc9ed014 206 }
joeverbout 0:ea44dc9ed014 207
joeverbout 0:ea44dc9ed014 208 if (count < capacity) ++count;
joeverbout 0:ea44dc9ed014 209 for (int j = count-1; j > i; --j) {
joeverbout 0:ea44dc9ed014 210 dists[j] = dists[j-1];
joeverbout 0:ea44dc9ed014 211 indices[j] = indices[j-1];
joeverbout 0:ea44dc9ed014 212 }
joeverbout 0:ea44dc9ed014 213 dists[i] = dist;
joeverbout 0:ea44dc9ed014 214 indices[i] = index;
joeverbout 0:ea44dc9ed014 215 worst_distance_ = dists[capacity-1];
joeverbout 0:ea44dc9ed014 216 }
joeverbout 0:ea44dc9ed014 217
joeverbout 0:ea44dc9ed014 218 DistanceType worstDist() const
joeverbout 0:ea44dc9ed014 219 {
joeverbout 0:ea44dc9ed014 220 return worst_distance_;
joeverbout 0:ea44dc9ed014 221 }
joeverbout 0:ea44dc9ed014 222 };
joeverbout 0:ea44dc9ed014 223
joeverbout 0:ea44dc9ed014 224
joeverbout 0:ea44dc9ed014 225 /**
joeverbout 0:ea44dc9ed014 226 * A result-set class used when performing a radius based search.
joeverbout 0:ea44dc9ed014 227 */
joeverbout 0:ea44dc9ed014 228 template <typename DistanceType>
joeverbout 0:ea44dc9ed014 229 class RadiusResultSet : public ResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 230 {
joeverbout 0:ea44dc9ed014 231 DistanceType radius;
joeverbout 0:ea44dc9ed014 232 int* indices;
joeverbout 0:ea44dc9ed014 233 DistanceType* dists;
joeverbout 0:ea44dc9ed014 234 size_t capacity;
joeverbout 0:ea44dc9ed014 235 size_t count;
joeverbout 0:ea44dc9ed014 236
joeverbout 0:ea44dc9ed014 237 public:
joeverbout 0:ea44dc9ed014 238 RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) :
joeverbout 0:ea44dc9ed014 239 radius(radius_), indices(indices_), dists(dists_), capacity(capacity_)
joeverbout 0:ea44dc9ed014 240 {
joeverbout 0:ea44dc9ed014 241 init();
joeverbout 0:ea44dc9ed014 242 }
joeverbout 0:ea44dc9ed014 243
joeverbout 0:ea44dc9ed014 244 ~RadiusResultSet()
joeverbout 0:ea44dc9ed014 245 {
joeverbout 0:ea44dc9ed014 246 }
joeverbout 0:ea44dc9ed014 247
joeverbout 0:ea44dc9ed014 248 void init()
joeverbout 0:ea44dc9ed014 249 {
joeverbout 0:ea44dc9ed014 250 count = 0;
joeverbout 0:ea44dc9ed014 251 }
joeverbout 0:ea44dc9ed014 252
joeverbout 0:ea44dc9ed014 253 size_t size() const
joeverbout 0:ea44dc9ed014 254 {
joeverbout 0:ea44dc9ed014 255 return count;
joeverbout 0:ea44dc9ed014 256 }
joeverbout 0:ea44dc9ed014 257
joeverbout 0:ea44dc9ed014 258 bool full() const
joeverbout 0:ea44dc9ed014 259 {
joeverbout 0:ea44dc9ed014 260 return true;
joeverbout 0:ea44dc9ed014 261 }
joeverbout 0:ea44dc9ed014 262
joeverbout 0:ea44dc9ed014 263 void addPoint(DistanceType dist, int index)
joeverbout 0:ea44dc9ed014 264 {
joeverbout 0:ea44dc9ed014 265 if (dist<radius) {
joeverbout 0:ea44dc9ed014 266 if ((capacity>0)&&(count < capacity)) {
joeverbout 0:ea44dc9ed014 267 dists[count] = dist;
joeverbout 0:ea44dc9ed014 268 indices[count] = index;
joeverbout 0:ea44dc9ed014 269 }
joeverbout 0:ea44dc9ed014 270 count++;
joeverbout 0:ea44dc9ed014 271 }
joeverbout 0:ea44dc9ed014 272 }
joeverbout 0:ea44dc9ed014 273
joeverbout 0:ea44dc9ed014 274 DistanceType worstDist() const
joeverbout 0:ea44dc9ed014 275 {
joeverbout 0:ea44dc9ed014 276 return radius;
joeverbout 0:ea44dc9ed014 277 }
joeverbout 0:ea44dc9ed014 278
joeverbout 0:ea44dc9ed014 279 };
joeverbout 0:ea44dc9ed014 280
joeverbout 0:ea44dc9ed014 281 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
joeverbout 0:ea44dc9ed014 282
joeverbout 0:ea44dc9ed014 283 /** Class that holds the k NN neighbors
joeverbout 0:ea44dc9ed014 284 * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
joeverbout 0:ea44dc9ed014 285 */
joeverbout 0:ea44dc9ed014 286 template<typename DistanceType>
joeverbout 0:ea44dc9ed014 287 class UniqueResultSet : public ResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 288 {
joeverbout 0:ea44dc9ed014 289 public:
joeverbout 0:ea44dc9ed014 290 struct DistIndex
joeverbout 0:ea44dc9ed014 291 {
joeverbout 0:ea44dc9ed014 292 DistIndex(DistanceType dist, unsigned int index) :
joeverbout 0:ea44dc9ed014 293 dist_(dist), index_(index)
joeverbout 0:ea44dc9ed014 294 {
joeverbout 0:ea44dc9ed014 295 }
joeverbout 0:ea44dc9ed014 296 bool operator<(const DistIndex dist_index) const
joeverbout 0:ea44dc9ed014 297 {
joeverbout 0:ea44dc9ed014 298 return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_);
joeverbout 0:ea44dc9ed014 299 }
joeverbout 0:ea44dc9ed014 300 DistanceType dist_;
joeverbout 0:ea44dc9ed014 301 unsigned int index_;
joeverbout 0:ea44dc9ed014 302 };
joeverbout 0:ea44dc9ed014 303
joeverbout 0:ea44dc9ed014 304 /** Default cosntructor */
joeverbout 0:ea44dc9ed014 305 UniqueResultSet() :
joeverbout 0:ea44dc9ed014 306 worst_distance_(std::numeric_limits<DistanceType>::max())
joeverbout 0:ea44dc9ed014 307 {
joeverbout 0:ea44dc9ed014 308 }
joeverbout 0:ea44dc9ed014 309
joeverbout 0:ea44dc9ed014 310 /** Check the status of the set
joeverbout 0:ea44dc9ed014 311 * @return true if we have k NN
joeverbout 0:ea44dc9ed014 312 */
joeverbout 0:ea44dc9ed014 313 inline bool full() const
joeverbout 0:ea44dc9ed014 314 {
joeverbout 0:ea44dc9ed014 315 return is_full_;
joeverbout 0:ea44dc9ed014 316 }
joeverbout 0:ea44dc9ed014 317
joeverbout 0:ea44dc9ed014 318 /** Remove all elements in the set
joeverbout 0:ea44dc9ed014 319 */
joeverbout 0:ea44dc9ed014 320 virtual void clear() = 0;
joeverbout 0:ea44dc9ed014 321
joeverbout 0:ea44dc9ed014 322 /** Copy the set to two C arrays
joeverbout 0:ea44dc9ed014 323 * @param indices pointer to a C array of indices
joeverbout 0:ea44dc9ed014 324 * @param dist pointer to a C array of distances
joeverbout 0:ea44dc9ed014 325 * @param n_neighbors the number of neighbors to copy
joeverbout 0:ea44dc9ed014 326 */
joeverbout 0:ea44dc9ed014 327 virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const
joeverbout 0:ea44dc9ed014 328 {
joeverbout 0:ea44dc9ed014 329 if (n_neighbors < 0) {
joeverbout 0:ea44dc9ed014 330 for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
joeverbout 0:ea44dc9ed014 331 dist_indices_.end(); dist_index != dist_index_end; ++dist_index, ++indices, ++dist) {
joeverbout 0:ea44dc9ed014 332 *indices = dist_index->index_;
joeverbout 0:ea44dc9ed014 333 *dist = dist_index->dist_;
joeverbout 0:ea44dc9ed014 334 }
joeverbout 0:ea44dc9ed014 335 }
joeverbout 0:ea44dc9ed014 336 else {
joeverbout 0:ea44dc9ed014 337 int i = 0;
joeverbout 0:ea44dc9ed014 338 for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
joeverbout 0:ea44dc9ed014 339 dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) {
joeverbout 0:ea44dc9ed014 340 *indices = dist_index->index_;
joeverbout 0:ea44dc9ed014 341 *dist = dist_index->dist_;
joeverbout 0:ea44dc9ed014 342 }
joeverbout 0:ea44dc9ed014 343 }
joeverbout 0:ea44dc9ed014 344 }
joeverbout 0:ea44dc9ed014 345
joeverbout 0:ea44dc9ed014 346 /** Copy the set to two C arrays but sort it according to the distance first
joeverbout 0:ea44dc9ed014 347 * @param indices pointer to a C array of indices
joeverbout 0:ea44dc9ed014 348 * @param dist pointer to a C array of distances
joeverbout 0:ea44dc9ed014 349 * @param n_neighbors the number of neighbors to copy
joeverbout 0:ea44dc9ed014 350 */
joeverbout 0:ea44dc9ed014 351 virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
joeverbout 0:ea44dc9ed014 352 {
joeverbout 0:ea44dc9ed014 353 copy(indices, dist, n_neighbors);
joeverbout 0:ea44dc9ed014 354 }
joeverbout 0:ea44dc9ed014 355
joeverbout 0:ea44dc9ed014 356 /** The number of neighbors in the set
joeverbout 0:ea44dc9ed014 357 * @return
joeverbout 0:ea44dc9ed014 358 */
joeverbout 0:ea44dc9ed014 359 size_t size() const
joeverbout 0:ea44dc9ed014 360 {
joeverbout 0:ea44dc9ed014 361 return dist_indices_.size();
joeverbout 0:ea44dc9ed014 362 }
joeverbout 0:ea44dc9ed014 363
joeverbout 0:ea44dc9ed014 364 /** The distance of the furthest neighbor
joeverbout 0:ea44dc9ed014 365 * If we don't have enough neighbors, it returns the max possible value
joeverbout 0:ea44dc9ed014 366 * @return
joeverbout 0:ea44dc9ed014 367 */
joeverbout 0:ea44dc9ed014 368 inline DistanceType worstDist() const
joeverbout 0:ea44dc9ed014 369 {
joeverbout 0:ea44dc9ed014 370 return worst_distance_;
joeverbout 0:ea44dc9ed014 371 }
joeverbout 0:ea44dc9ed014 372 protected:
joeverbout 0:ea44dc9ed014 373 /** Flag to say if the set is full */
joeverbout 0:ea44dc9ed014 374 bool is_full_;
joeverbout 0:ea44dc9ed014 375
joeverbout 0:ea44dc9ed014 376 /** The worst distance found so far */
joeverbout 0:ea44dc9ed014 377 DistanceType worst_distance_;
joeverbout 0:ea44dc9ed014 378
joeverbout 0:ea44dc9ed014 379 /** The best candidates so far */
joeverbout 0:ea44dc9ed014 380 std::set<DistIndex> dist_indices_;
joeverbout 0:ea44dc9ed014 381 };
joeverbout 0:ea44dc9ed014 382
joeverbout 0:ea44dc9ed014 383 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
joeverbout 0:ea44dc9ed014 384
joeverbout 0:ea44dc9ed014 385 /** Class that holds the k NN neighbors
joeverbout 0:ea44dc9ed014 386 * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays
joeverbout 0:ea44dc9ed014 387 */
joeverbout 0:ea44dc9ed014 388 template<typename DistanceType>
joeverbout 0:ea44dc9ed014 389 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 390 {
joeverbout 0:ea44dc9ed014 391 public:
joeverbout 0:ea44dc9ed014 392 /** Constructor
joeverbout 0:ea44dc9ed014 393 * @param capacity the number of neighbors to store at max
joeverbout 0:ea44dc9ed014 394 */
joeverbout 0:ea44dc9ed014 395 KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
joeverbout 0:ea44dc9ed014 396 {
joeverbout 0:ea44dc9ed014 397 this->is_full_ = false;
joeverbout 0:ea44dc9ed014 398 this->clear();
joeverbout 0:ea44dc9ed014 399 }
joeverbout 0:ea44dc9ed014 400
joeverbout 0:ea44dc9ed014 401 /** Add a possible candidate to the best neighbors
joeverbout 0:ea44dc9ed014 402 * @param dist distance for that neighbor
joeverbout 0:ea44dc9ed014 403 * @param index index of that neighbor
joeverbout 0:ea44dc9ed014 404 */
joeverbout 0:ea44dc9ed014 405 inline void addPoint(DistanceType dist, int index)
joeverbout 0:ea44dc9ed014 406 {
joeverbout 0:ea44dc9ed014 407 // Don't do anything if we are worse than the worst
joeverbout 0:ea44dc9ed014 408 if (dist >= worst_distance_) return;
joeverbout 0:ea44dc9ed014 409 dist_indices_.insert(DistIndex(dist, index));
joeverbout 0:ea44dc9ed014 410
joeverbout 0:ea44dc9ed014 411 if (is_full_) {
joeverbout 0:ea44dc9ed014 412 if (dist_indices_.size() > capacity_) {
joeverbout 0:ea44dc9ed014 413 dist_indices_.erase(*dist_indices_.rbegin());
joeverbout 0:ea44dc9ed014 414 worst_distance_ = dist_indices_.rbegin()->dist_;
joeverbout 0:ea44dc9ed014 415 }
joeverbout 0:ea44dc9ed014 416 }
joeverbout 0:ea44dc9ed014 417 else if (dist_indices_.size() == capacity_) {
joeverbout 0:ea44dc9ed014 418 is_full_ = true;
joeverbout 0:ea44dc9ed014 419 worst_distance_ = dist_indices_.rbegin()->dist_;
joeverbout 0:ea44dc9ed014 420 }
joeverbout 0:ea44dc9ed014 421 }
joeverbout 0:ea44dc9ed014 422
joeverbout 0:ea44dc9ed014 423 /** Remove all elements in the set
joeverbout 0:ea44dc9ed014 424 */
joeverbout 0:ea44dc9ed014 425 void clear()
joeverbout 0:ea44dc9ed014 426 {
joeverbout 0:ea44dc9ed014 427 dist_indices_.clear();
joeverbout 0:ea44dc9ed014 428 worst_distance_ = std::numeric_limits<DistanceType>::max();
joeverbout 0:ea44dc9ed014 429 is_full_ = false;
joeverbout 0:ea44dc9ed014 430 }
joeverbout 0:ea44dc9ed014 431
joeverbout 0:ea44dc9ed014 432 protected:
joeverbout 0:ea44dc9ed014 433 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
joeverbout 0:ea44dc9ed014 434 using UniqueResultSet<DistanceType>::is_full_;
joeverbout 0:ea44dc9ed014 435 using UniqueResultSet<DistanceType>::worst_distance_;
joeverbout 0:ea44dc9ed014 436 using UniqueResultSet<DistanceType>::dist_indices_;
joeverbout 0:ea44dc9ed014 437
joeverbout 0:ea44dc9ed014 438 /** The number of neighbors to keep */
joeverbout 0:ea44dc9ed014 439 unsigned int capacity_;
joeverbout 0:ea44dc9ed014 440 };
joeverbout 0:ea44dc9ed014 441
joeverbout 0:ea44dc9ed014 442 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
joeverbout 0:ea44dc9ed014 443
joeverbout 0:ea44dc9ed014 444 /** Class that holds the radius nearest neighbors
joeverbout 0:ea44dc9ed014 445 * It is more accurate than RadiusResult as it is not limited in the number of neighbors
joeverbout 0:ea44dc9ed014 446 */
joeverbout 0:ea44dc9ed014 447 template<typename DistanceType>
joeverbout 0:ea44dc9ed014 448 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 449 {
joeverbout 0:ea44dc9ed014 450 public:
joeverbout 0:ea44dc9ed014 451 /** Constructor
joeverbout 0:ea44dc9ed014 452 * @param radius the maximum distance of a neighbor
joeverbout 0:ea44dc9ed014 453 */
joeverbout 0:ea44dc9ed014 454 RadiusUniqueResultSet(DistanceType radius) :
joeverbout 0:ea44dc9ed014 455 radius_(radius)
joeverbout 0:ea44dc9ed014 456 {
joeverbout 0:ea44dc9ed014 457 is_full_ = true;
joeverbout 0:ea44dc9ed014 458 }
joeverbout 0:ea44dc9ed014 459
joeverbout 0:ea44dc9ed014 460 /** Add a possible candidate to the best neighbors
joeverbout 0:ea44dc9ed014 461 * @param dist distance for that neighbor
joeverbout 0:ea44dc9ed014 462 * @param index index of that neighbor
joeverbout 0:ea44dc9ed014 463 */
joeverbout 0:ea44dc9ed014 464 void addPoint(DistanceType dist, int index)
joeverbout 0:ea44dc9ed014 465 {
joeverbout 0:ea44dc9ed014 466 if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
joeverbout 0:ea44dc9ed014 467 }
joeverbout 0:ea44dc9ed014 468
joeverbout 0:ea44dc9ed014 469 /** Remove all elements in the set
joeverbout 0:ea44dc9ed014 470 */
joeverbout 0:ea44dc9ed014 471 inline void clear()
joeverbout 0:ea44dc9ed014 472 {
joeverbout 0:ea44dc9ed014 473 dist_indices_.clear();
joeverbout 0:ea44dc9ed014 474 }
joeverbout 0:ea44dc9ed014 475
joeverbout 0:ea44dc9ed014 476
joeverbout 0:ea44dc9ed014 477 /** Check the status of the set
joeverbout 0:ea44dc9ed014 478 * @return alwys false
joeverbout 0:ea44dc9ed014 479 */
joeverbout 0:ea44dc9ed014 480 inline bool full() const
joeverbout 0:ea44dc9ed014 481 {
joeverbout 0:ea44dc9ed014 482 return true;
joeverbout 0:ea44dc9ed014 483 }
joeverbout 0:ea44dc9ed014 484
joeverbout 0:ea44dc9ed014 485 /** The distance of the furthest neighbor
joeverbout 0:ea44dc9ed014 486 * If we don't have enough neighbors, it returns the max possible value
joeverbout 0:ea44dc9ed014 487 * @return
joeverbout 0:ea44dc9ed014 488 */
joeverbout 0:ea44dc9ed014 489 inline DistanceType worstDist() const
joeverbout 0:ea44dc9ed014 490 {
joeverbout 0:ea44dc9ed014 491 return radius_;
joeverbout 0:ea44dc9ed014 492 }
joeverbout 0:ea44dc9ed014 493 private:
joeverbout 0:ea44dc9ed014 494 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
joeverbout 0:ea44dc9ed014 495 using UniqueResultSet<DistanceType>::dist_indices_;
joeverbout 0:ea44dc9ed014 496 using UniqueResultSet<DistanceType>::is_full_;
joeverbout 0:ea44dc9ed014 497
joeverbout 0:ea44dc9ed014 498 /** The furthest distance a neighbor can be */
joeverbout 0:ea44dc9ed014 499 DistanceType radius_;
joeverbout 0:ea44dc9ed014 500 };
joeverbout 0:ea44dc9ed014 501
joeverbout 0:ea44dc9ed014 502 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
joeverbout 0:ea44dc9ed014 503
joeverbout 0:ea44dc9ed014 504 /** Class that holds the k NN neighbors within a radius distance
joeverbout 0:ea44dc9ed014 505 */
joeverbout 0:ea44dc9ed014 506 template<typename DistanceType>
joeverbout 0:ea44dc9ed014 507 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
joeverbout 0:ea44dc9ed014 508 {
joeverbout 0:ea44dc9ed014 509 public:
joeverbout 0:ea44dc9ed014 510 /** Constructor
joeverbout 0:ea44dc9ed014 511 * @param capacity the number of neighbors to store at max
joeverbout 0:ea44dc9ed014 512 * @param radius the maximum distance of a neighbor
joeverbout 0:ea44dc9ed014 513 */
joeverbout 0:ea44dc9ed014 514 KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
joeverbout 0:ea44dc9ed014 515 {
joeverbout 0:ea44dc9ed014 516 this->capacity_ = capacity;
joeverbout 0:ea44dc9ed014 517 this->radius_ = radius;
joeverbout 0:ea44dc9ed014 518 this->dist_indices_.reserve(capacity_);
joeverbout 0:ea44dc9ed014 519 this->clear();
joeverbout 0:ea44dc9ed014 520 }
joeverbout 0:ea44dc9ed014 521
joeverbout 0:ea44dc9ed014 522 /** Remove all elements in the set
joeverbout 0:ea44dc9ed014 523 */
joeverbout 0:ea44dc9ed014 524 void clear()
joeverbout 0:ea44dc9ed014 525 {
joeverbout 0:ea44dc9ed014 526 dist_indices_.clear();
joeverbout 0:ea44dc9ed014 527 worst_distance_ = radius_;
joeverbout 0:ea44dc9ed014 528 is_full_ = false;
joeverbout 0:ea44dc9ed014 529 }
joeverbout 0:ea44dc9ed014 530 private:
joeverbout 0:ea44dc9ed014 531 using KNNUniqueResultSet<DistanceType>::dist_indices_;
joeverbout 0:ea44dc9ed014 532 using KNNUniqueResultSet<DistanceType>::is_full_;
joeverbout 0:ea44dc9ed014 533 using KNNUniqueResultSet<DistanceType>::worst_distance_;
joeverbout 0:ea44dc9ed014 534
joeverbout 0:ea44dc9ed014 535 /** The maximum number of neighbors to consider */
joeverbout 0:ea44dc9ed014 536 unsigned int capacity_;
joeverbout 0:ea44dc9ed014 537
joeverbout 0:ea44dc9ed014 538 /** The maximum distance of a neighbor */
joeverbout 0:ea44dc9ed014 539 DistanceType radius_;
joeverbout 0:ea44dc9ed014 540 };
joeverbout 0:ea44dc9ed014 541 }
joeverbout 0:ea44dc9ed014 542
joeverbout 0:ea44dc9ed014 543 #endif //OPENCV_FLANN_RESULTSET_H
joeverbout 0:ea44dc9ed014 544