OpenCV 4.5.3(日本語機械翻訳)
result_set.h
1 /***********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6 *
7 * THE BSD LICENSE
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *************************************************************************/
30
31 #ifndef OPENCV_FLANN_RESULTSET_H
32 #define OPENCV_FLANN_RESULTSET_H
33
35
36 #include <algorithm>
37 #include <cstring>
38 #include <iostream>
39 #include <limits>
40 #include <set>
41 #include <vector>
42
43 namespace cvflann
44{
45
46 /* This record represents a branch point when finding neighbors in
47 the tree. It contains a record of the minimum distance to the query
48 point, as well as the node at which the search resumes.
49 */
50
51 template <typename T, typename DistanceType>
52 struct BranchStruct
53{
54 T node; /* Tree node at which search resumes */
55 DistanceType mindist; /* Minimum distance to query for all nodes below. */
56
57 BranchStruct() {}
58 BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {}
59
60 bool operator<(const BranchStruct<T, DistanceType>& rhs) const
61 {
62 return mindist<rhs.mindist;
63 }
64};
65
66
67 template <typename DistanceType>
68 class ResultSet
69{
70 public:
71 virtual ~ResultSet() {}
72
73 virtual bool full() const = 0;
74
75 virtual void addPoint(DistanceType dist, int index) = 0;
76
77 virtual DistanceType worstDist() const = 0;
78
79};
80
86 template <typename DistanceType>
87 class KNNSimpleResultSet : public ResultSet<DistanceType>
88{
89 int* indices;
90 DistanceType* dists;
91 int capacity;
92 int count;
93 DistanceType worst_distance_;
94
95 public:
96 KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0)
97 {
98 }
99
100 void init(int* indices_, DistanceType* dists_)
101 {
102 indices = indices_;
103 dists = dists_;
104 count = 0;
105 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
106 dists[capacity-1] = worst_distance_;
107 }
108
109 size_t size() const
110 {
111 return count;
112 }
113
114 bool full() const CV_OVERRIDE
115 {
116 return count == capacity;
117 }
118
119
120 void addPoint(DistanceType dist, int index) CV_OVERRIDE
121 {
122 if (dist >= worst_distance_) return;
123 int i;
124 for (i=count; i>0; --i) {
125 #ifdef FLANN_FIRST_MATCH
126 if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) )
127 #else
128 if (dists[i-1]>dist)
129 #endif
130 {
131 if (i<capacity) {
132 dists[i] = dists[i-1];
133 indices[i] = indices[i-1];
134 }
135 }
136 else break;
137 }
138 if (count < capacity) ++count;
139 dists[i] = dist;
140 indices[i] = index;
141 worst_distance_ = dists[capacity-1];
142 }
143
144 DistanceType worstDist() const CV_OVERRIDE
145 {
146 return worst_distance_;
147 }
148};
149
153 template <typename DistanceType>
154 class KNNResultSet : public ResultSet<DistanceType>
155{
156 int* indices;
157 DistanceType* dists;
158 int capacity;
159 int count;
160 DistanceType worst_distance_;
161
162 public:
163 KNNResultSet(int capacity_)
164 : indices(NULL), dists(NULL), capacity(capacity_), count(0), worst_distance_(0)
165 {
166 }
167
168 void init(int* indices_, DistanceType* dists_)
169 {
170 indices = indices_;
171 dists = dists_;
172 count = 0;
173 worst_distance_ = (std::numeric_limits<DistanceType>::max)();
174 dists[capacity-1] = worst_distance_;
175 }
176
177 size_t size() const
178 {
179 return count;
180 }
181
182 bool full() const CV_OVERRIDE
183 {
184 return count == capacity;
185 }
186
187
188 void addPoint(DistanceType dist, int index) CV_OVERRIDE
189 {
190 CV_DbgAssert(indices);
191 CV_DbgAssert(dists);
192 if (dist >= worst_distance_) return;
193 int i;
194 for (i = count; i > 0; --i) {
195 #ifdef FLANN_FIRST_MATCH
196 if ( (dists[i-1]<=dist) && ((dist!=dists[i-1])||(indices[i-1]<=index)) )
197 #else
198 if (dists[i-1]<=dist)
199 #endif
200 {
201 // Check for duplicate indices
202 for (int j = i; dists[j] == dist && j--;) {
203 if (indices[j] == index) {
204 return;
205 }
206 }
207 break;
208 }
209 }
210
211 if (count < capacity) ++count;
212 for (int j = count-1; j > i; --j) {
213 dists[j] = dists[j-1];
214 indices[j] = indices[j-1];
215 }
216 dists[i] = dist;
217 indices[i] = index;
218 worst_distance_ = dists[capacity-1];
219 }
220
221 DistanceType worstDist() const CV_OVERRIDE
222 {
223 return worst_distance_;
224 }
225};
226
227
231 template <typename DistanceType>
232 class RadiusResultSet : public ResultSet<DistanceType>
233{
234 DistanceType radius;
235 int* indices;
236 DistanceType* dists;
237 size_t capacity;
238 size_t count;
239
240 public:
241 RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) :
242 radius(radius_), indices(indices_), dists(dists_), capacity(capacity_)
243 {
244 init();
245 }
246
247 ~RadiusResultSet()
248 {
249 }
250
251 void init()
252 {
253 count = 0;
254 }
255
256 size_t size() const
257 {
258 return count;
259 }
260
261 bool full() const
262 {
263 return true;
264 }
265
266 void addPoint(DistanceType dist, int index)
267 {
268 if (dist<radius) {
269 if ((capacity>0)&&(count < capacity)) {
270 dists[count] = dist;
271 indices[count] = index;
272 }
273 count++;
274 }
275 }
276
277 DistanceType worstDist() const
278 {
279 return radius;
280 }
281
282};
283
285
289 template<typename DistanceType>
290 class UniqueResultSet : public ResultSet<DistanceType>
291{
292 public:
293 struct DistIndex
294 {
295 DistIndex(DistanceType dist, unsigned int index) :
296 dist_(dist), index_(index)
297 {
298 }
299 bool operator<(const DistIndex dist_index) const
300 {
301 return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_);
302 }
303 DistanceType dist_;
304 unsigned int index_;
305 };
306
308 UniqueResultSet() :
309 is_full_(false), worst_distance_(std::numeric_limits<DistanceType>::max())
310 {
311 }
312
316 inline bool full() const CV_OVERRIDE
317 {
318 return is_full_;
319 }
320
323 virtual void clear() = 0;
324
330 virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const
331 {
332 if (n_neighbors < 0) {
333 for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
334 dist_indices_.end(); dist_index != dist_index_end; ++dist_index, ++indices, ++dist) {
335 *indices = dist_index->index_;
336 *dist = dist_index->dist_;
337 }
338 }
339 else {
340 int i = 0;
341 for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end =
342 dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) {
343 *indices = dist_index->index_;
344 *dist = dist_index->dist_;
345 }
346 }
347 }
348
354 virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const
355 {
356 copy(indices, dist, n_neighbors);
357 }
358
362 size_t size() const
363 {
364 return dist_indices_.size();
365 }
366
371 inline DistanceType worstDist() const CV_OVERRIDE
372 {
373 return worst_distance_;
374 }
375 protected:
377 bool is_full_;
378
380 DistanceType worst_distance_;
381
383 std::set<DistIndex> dist_indices_;
384};
385
387
391 template<typename DistanceType>
392 class KNNUniqueResultSet : public UniqueResultSet<DistanceType>
393{
394 public:
398 KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity)
399 {
400 this->is_full_ = false;
401 this->clear();
402 }
403
408 inline void addPoint(DistanceType dist, int index) CV_OVERRIDE
409 {
410 // Don't do anything if we are worse than the worst
411 if (dist >= worst_distance_) return;
412 dist_indices_.insert(DistIndex(dist, index));
413
414 if (is_full_) {
415 if (dist_indices_.size() > capacity_) {
416 dist_indices_.erase(*dist_indices_.rbegin());
417 worst_distance_ = dist_indices_.rbegin()->dist_;
418 }
419 }
420 else if (dist_indices_.size() == capacity_) {
421 is_full_ = true;
422 worst_distance_ = dist_indices_.rbegin()->dist_;
423 }
424 }
425
428 void clear() CV_OVERRIDE
429 {
430 dist_indices_.clear();
431 worst_distance_ = std::numeric_limits<DistanceType>::max();
432 is_full_ = false;
433 }
434
435 protected:
436 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
437 using UniqueResultSet<DistanceType>::is_full_;
438 using UniqueResultSet<DistanceType>::worst_distance_;
439 using UniqueResultSet<DistanceType>::dist_indices_;
440
442 unsigned int capacity_;
443};
444
446
450 template<typename DistanceType>
451 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType>
452{
453 public:
457 RadiusUniqueResultSet(DistanceType radius) :
458 radius_(radius)
459 {
460 is_full_ = true;
461 }
462
467 void addPoint(DistanceType dist, int index) CV_OVERRIDE
468 {
469 if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index));
470 }
471
474 inline void clear() CV_OVERRIDE
475 {
476 dist_indices_.clear();
477 }
478
479
483 inline bool full() const CV_OVERRIDE
484 {
485 return true;
486 }
487
492 inline DistanceType worstDist() const CV_OVERRIDE
493 {
494 return radius_;
495 }
496 private:
497 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex;
498 using UniqueResultSet<DistanceType>::dist_indices_;
499 using UniqueResultSet<DistanceType>::is_full_;
500
502 DistanceType radius_;
503};
504
506
509 template<typename DistanceType>
510 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType>
511{
512 public:
517 KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius)
518 {
519 this->capacity_ = capacity;
520 this->radius_ = radius;
521 this->dist_indices_.reserve(capacity_);
522 this->clear();
523 }
524
527 void clear()
528 {
529 dist_indices_.clear();
530 worst_distance_ = radius_;
531 is_full_ = false;
532 }
533 private:
534 using KNNUniqueResultSet<DistanceType>::dist_indices_;
535 using KNNUniqueResultSet<DistanceType>::is_full_;
536 using KNNUniqueResultSet<DistanceType>::worst_distance_;
537
539 unsigned int capacity_;
540
542 DistanceType radius_;
543};
544}
545
547
548 #endif //OPENCV_FLANN_RESULTSET_H
cv::max
CV_EXPORTS_W void max(InputArray src1, InputArray src2, OutputArray dst)
Calculates per-element maximum of two arrays or an array and a scalar.
CV_DbgAssert
#define CV_DbgAssert(expr)
Definition: base.hpp:375
構築: doxygen 1.9.2