Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

include/opencv2/flann/result_set.h@0:0e0631af0305, 2021-01-29 (annotated)

Committer:
RyoheiHagimoto
Date:
Fri Jan 29 04:53:38 2021 +0000
Revision:
0:0e0631af0305
copied from https://github.com/d-kato/opencv-lib.

Who changed what in which revision?

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