OpenCV 4.5.3(日本語機械翻訳)
dist.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_DIST_H_
32 #define OPENCV_FLANN_DIST_H_
33
35
36 #include <cmath>
37 #include <cstdlib>
38 #include <string.h>
39 #ifdef _MSC_VER
40 typedef unsigned __int32 uint32_t;
41 typedef unsigned __int64 uint64_t;
42 #else
43 #include <stdint.h>
44 #endif
45
46 #include "defines.h"
47
48 #if defined _WIN32 && (defined(_M_ARM) || defined(_M_ARM64))
49 # include <Intrin.h>
50 #endif
51
52 #if defined(__ARM_NEON__) && !defined(__CUDACC__)
53 # include "arm_neon.h"
54 #endif
55
56 namespace cvflann
57{
58
59 template<typename T>
60 inline T abs(T x) { return (x<0) ? -x : x; }
61
62 template<>
63 inline int abs<int>(int x) { return ::abs(x); }
64
65 template<>
66 inline float abs<float>(float x) { return fabsf(x); }
67
68 template<>
69 inline double abs<double>(double x) { return fabs(x); }
70
71
72 template<typename TargetType>
73 inline TargetType round(float x) { return static_cast<TargetType>(x); }
74
75 template<>
76 inline unsigned int round<unsigned int>(float x) { return static_cast< unsigned int >(x + 0.5f); }
77
78 template<>
79 inline unsigned short round<unsigned short>(float x) { return static_cast< unsigned short >(x + 0.5f); }
80
81 template<>
82 inline unsigned char round<unsigned char>(float x) { return static_cast< unsigned char >(x + 0.5f); }
83
84 template<>
85 inline long long round<long long>(float x) { return static_cast< long long >(x + 0.5f); }
86
87 template<>
88 inline long round<long>(float x) { return static_cast< long >(x + 0.5f); }
89
90 template<>
91 inline int round<int>(float x) { return static_cast< int >(x + 0.5f) - (x<0); }
92
93 template<>
94 inline short round<short>(float x) { return static_cast< short >(x + 0.5f) - (x<0); }
95
96 template<>
97 inline char round<char>(float x) { return static_cast< char >(x + 0.5f) - (x<0); }
98
99
100 template<typename TargetType>
101 inline TargetType round(double x) { return static_cast<TargetType>(x); }
102
103 template<>
104 inline unsigned int round<unsigned int>(double x) { return static_cast< unsigned int >(x + 0.5); }
105
106 template<>
107 inline unsigned short round<unsigned short>(double x) { return static_cast< unsigned short >(x + 0.5); }
108
109 template<>
110 inline unsigned char round<unsigned char>(double x) { return static_cast< unsigned char >(x + 0.5); }
111
112 template<>
113 inline long long round<long long>(double x) { return static_cast< long long >(x + 0.5); }
114
115 template<>
116 inline long round<long>(double x) { return static_cast< long >(x + 0.5); }
117
118 template<>
119 inline int round<int>(double x) { return static_cast< int >(x + 0.5) - (x<0); }
120
121 template<>
122 inline short round<short>(double x) { return static_cast< short >(x + 0.5) - (x<0); }
123
124 template<>
125 inline char round<char>(double x) { return static_cast< char >(x + 0.5) - (x<0); }
126
127
128 template<typename T>
129 struct Accumulator { typedef T Type; };
130 template<>
131 struct Accumulator<unsigned char> { typedef float Type; };
132 template<>
133 struct Accumulator<unsigned short> { typedef float Type; };
134 template<>
135 struct Accumulator<unsigned int> { typedef float Type; };
136 template<>
137 struct Accumulator<char> { typedef float Type; };
138 template<>
139 struct Accumulator<short> { typedef float Type; };
140 template<>
141 struct Accumulator<int> { typedef float Type; };
142
143 #undef True
144 #undef False
145
146 class True
147{
148 public:
149 static const bool val = true;
150};
151
152 class False
153{
154 public:
155 static const bool val = false;
156};
157
158
159 /*
160 * This is a "zero iterator". It basically behaves like a zero filled
161 * array to all algorithms that use arrays as iterators (STL style).
162 * It's useful when there's a need to compute the distance between feature
163 * and origin it and allows for better compiler optimisation than using a
164 * zero-filled array.
165 */
166 template <typename T>
167 struct ZeroIterator
168{
169
170 T operator*()
171 {
172 return 0;
173 }
174
175 T operator[](int)
176 {
177 return 0;
178 }
179
180 const ZeroIterator<T>& operator ++()
181 {
182 return *this;
183 }
184
185 ZeroIterator<T> operator ++(int)
186 {
187 return *this;
188 }
189
190 ZeroIterator<T>& operator+=(int)
191 {
192 return *this;
193 }
194
195};
196
197
198
205 template<class T>
206 struct L2_Simple
207{
208 typedef True is_kdtree_distance;
209 typedef True is_vector_space_distance;
210
211 typedef T ElementType;
212 typedef typename Accumulator<T>::Type ResultType;
213 typedef ResultType CentersType;
214
215 template <typename Iterator1, typename Iterator2>
216 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const
217 {
218 ResultType result = ResultType();
219 ResultType diff;
220 for(size_t i = 0; i < size; ++i ) {
221 diff = (ResultType)(*a++ - *b++);
222 result += diff*diff;
223 }
224 return result;
225 }
226
227 template <typename U, typename V>
228 inline ResultType accum_dist(const U& a, const V& b, int) const
229 {
230 return (a-b)*(a-b);
231 }
232};
233
234
235
239 template<class T>
240 struct L2
241{
242 typedef True is_kdtree_distance;
243 typedef True is_vector_space_distance;
244
245 typedef T ElementType;
246 typedef typename Accumulator<T>::Type ResultType;
247 typedef ResultType CentersType;
248
258 template <typename Iterator1, typename Iterator2>
259 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
260 {
261 ResultType result = ResultType();
262 ResultType diff0, diff1, diff2, diff3;
263 Iterator1 last = a + size;
264 Iterator1 lastgroup = last - 3;
265
266 /* Process 4 items with each loop for efficiency. */
267 while (a < lastgroup) {
268 diff0 = (ResultType)(a[0] - b[0]);
269 diff1 = (ResultType)(a[1] - b[1]);
270 diff2 = (ResultType)(a[2] - b[2]);
271 diff3 = (ResultType)(a[3] - b[3]);
272 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
273 a += 4;
274 b += 4;
275
276 if ((worst_dist>0)&&(result>worst_dist)) {
277 return result;
278 }
279 }
280 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
281 while (a < last) {
282 diff0 = (ResultType)(*a++ - *b++);
283 result += diff0 * diff0;
284 }
285 return result;
286 }
287
294 template <typename U, typename V>
295 inline ResultType accum_dist(const U& a, const V& b, int) const
296 {
297 return (a-b)*(a-b);
298 }
299};
300
301
302 /*
303 * Manhattan distance functor, optimized version
304 */
305 template<class T>
306 struct L1
307{
308 typedef True is_kdtree_distance;
309 typedef True is_vector_space_distance;
310
311 typedef T ElementType;
312 typedef typename Accumulator<T>::Type ResultType;
313 typedef ResultType CentersType;
314
321 template <typename Iterator1, typename Iterator2>
322 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
323 {
324 ResultType result = ResultType();
325 ResultType diff0, diff1, diff2, diff3;
326 Iterator1 last = a + size;
327 Iterator1 lastgroup = last - 3;
328
329 /* Process 4 items with each loop for efficiency. */
330 while (a < lastgroup) {
331 diff0 = (ResultType)abs(a[0] - b[0]);
332 diff1 = (ResultType)abs(a[1] - b[1]);
333 diff2 = (ResultType)abs(a[2] - b[2]);
334 diff3 = (ResultType)abs(a[3] - b[3]);
335 result += diff0 + diff1 + diff2 + diff3;
336 a += 4;
337 b += 4;
338
339 if ((worst_dist>0)&&(result>worst_dist)) {
340 return result;
341 }
342 }
343 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
344 while (a < last) {
345 diff0 = (ResultType)abs(*a++ - *b++);
346 result += diff0;
347 }
348 return result;
349 }
350
354 template <typename U, typename V>
355 inline ResultType accum_dist(const U& a, const V& b, int) const
356 {
357 return abs(a-b);
358 }
359};
360
361
362
363 template<class T>
364 struct MinkowskiDistance
365{
366 typedef True is_kdtree_distance;
367 typedef True is_vector_space_distance;
368
369 typedef T ElementType;
370 typedef typename Accumulator<T>::Type ResultType;
371 typedef ResultType CentersType;
372
373 int order;
374
375 MinkowskiDistance(int order_) : order(order_) {}
376
386 template <typename Iterator1, typename Iterator2>
387 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
388 {
389 ResultType result = ResultType();
390 ResultType diff0, diff1, diff2, diff3;
391 Iterator1 last = a + size;
392 Iterator1 lastgroup = last - 3;
393
394 /* Process 4 items with each loop for efficiency. */
395 while (a < lastgroup) {
396 diff0 = (ResultType)abs(a[0] - b[0]);
397 diff1 = (ResultType)abs(a[1] - b[1]);
398 diff2 = (ResultType)abs(a[2] - b[2]);
399 diff3 = (ResultType)abs(a[3] - b[3]);
400 result += pow(diff0,order) + pow(diff1,order) + pow(diff2,order) + pow(diff3,order);
401 a += 4;
402 b += 4;
403
404 if ((worst_dist>0)&&(result>worst_dist)) {
405 return result;
406 }
407 }
408 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
409 while (a < last) {
410 diff0 = (ResultType)abs(*a++ - *b++);
411 result += pow(diff0,order);
412 }
413 return result;
414 }
415
419 template <typename U, typename V>
420 inline ResultType accum_dist(const U& a, const V& b, int) const
421 {
422 return pow(static_cast<ResultType>(abs(a-b)),order);
423 }
424};
425
426
427
428 template<class T>
429 struct MaxDistance
430{
431 typedef False is_kdtree_distance;
432 typedef True is_vector_space_distance;
433
434 typedef T ElementType;
435 typedef typename Accumulator<T>::Type ResultType;
436 typedef ResultType CentersType;
437
443 template <typename Iterator1, typename Iterator2>
444 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
445 {
446 ResultType result = ResultType();
447 ResultType diff0, diff1, diff2, diff3;
448 Iterator1 last = a + size;
449 Iterator1 lastgroup = last - 3;
450
451 /* Process 4 items with each loop for efficiency. */
452 while (a < lastgroup) {
453 diff0 = abs(a[0] - b[0]);
454 diff1 = abs(a[1] - b[1]);
455 diff2 = abs(a[2] - b[2]);
456 diff3 = abs(a[3] - b[3]);
457 if (diff0>result) {result = diff0; }
458 if (diff1>result) {result = diff1; }
459 if (diff2>result) {result = diff2; }
460 if (diff3>result) {result = diff3; }
461 a += 4;
462 b += 4;
463
464 if ((worst_dist>0)&&(result>worst_dist)) {
465 return result;
466 }
467 }
468 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
469 while (a < last) {
470 diff0 = abs(*a++ - *b++);
471 result = (diff0>result) ? diff0 : result;
472 }
473 return result;
474 }
475
476 /* This distance functor is not dimension-wise additive, which
477 * makes it an invalid kd-tree distance, not implementing the accum_dist method */
478
479};
480
482
487 struct HammingLUT
488{
489 typedef False is_kdtree_distance;
490 typedef False is_vector_space_distance;
491
492 typedef unsigned char ElementType;
493 typedef int ResultType;
494 typedef ElementType CentersType;
495
498 template<typename Iterator2>
499 ResultType operator()(const unsigned char* a, const Iterator2 b, size_t size) const
500 {
501 static const uchar popCountTable[] =
502 {
503 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
504 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
505 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
506 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
507 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
508 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
509 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
510 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
511 };
512 ResultType result = 0;
513 const unsigned char* b2 = reinterpret_cast< const unsigned char*> (b);
514 for (size_t i = 0; i < size; i++) {
515 result += popCountTable[a[i] ^ b2[i]];
516 }
517 return result;
518 }
519
520
521 ResultType operator()(const unsigned char* a, const ZeroIterator<unsigned char> b, size_t size) const
522 {
523 (void)b;
524 static const uchar popCountTable[] =
525 {
526 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
527 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
528 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
529 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
530 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
531 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
532 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
533 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
534 };
535 ResultType result = 0;
536 for (size_t i = 0; i < size; i++) {
537 result += popCountTable[a[i]];
538 }
539 return result;
540 }
541};
542
547 template<class T>
548 struct Hamming
549{
550 typedef False is_kdtree_distance;
551 typedef False is_vector_space_distance;
552
553
554 typedef T ElementType;
555 typedef int ResultType;
556 typedef ElementType CentersType;
557
558 template<typename Iterator1, typename Iterator2>
559 ResultType operator()(const Iterator1 a, const Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const
560 {
561 ResultType result = 0;
562 #if defined(__ARM_NEON__) && !defined(__CUDACC__)
563 {
564 const unsigned char* a2 = reinterpret_cast< const unsigned char*> (a);
565 const unsigned char* b2 = reinterpret_cast< const unsigned char*> (b);
566 uint32x4_t bits = vmovq_n_u32(0);
567 for (size_t i = 0; i < size; i += 16) {
568 uint8x16_t A_vec = vld1q_u8 (a2 + i);
569 uint8x16_t B_vec = vld1q_u8 (b2 + i);
570 uint8x16_t AxorB = veorq_u8 (A_vec, B_vec);
571 uint8x16_t bitsSet = vcntq_u8 (AxorB);
572 uint16x8_t bitSet8 = vpaddlq_u8 (bitsSet);
573 uint32x4_t bitSet4 = vpaddlq_u16 (bitSet8);
574 bits = vaddq_u32(bits, bitSet4);
575 }
576 uint64x2_t bitSet2 = vpaddlq_u32 (bits);
577 result = vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),0);
578 result += vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),2);
579 }
580 #elif defined(__GNUC__)
581 {
582 //for portability just use unsigned long -- and use the __builtin_popcountll (see docs for __builtin_popcountll)
583 typedef unsigned long long pop_t;
584 const size_t modulo = size % sizeof(pop_t);
585 const pop_t* a2 = reinterpret_cast< const pop_t*> (a);
586 const pop_t* b2 = reinterpret_cast< const pop_t*> (b);
587 const pop_t* a2_end = a2 + (size / sizeof(pop_t));
588
589 for (; a2 != a2_end; ++a2, ++b2) result += __builtin_popcountll((*a2) ^ (*b2));
590
591 if (modulo) {
592 //in the case where size is not dividable by sizeof(size_t)
593 //need to mask off the bits at the end
594 pop_t a_final = 0, b_final = 0;
595 memcpy(&a_final, a2, modulo);
596 memcpy(&b_final, b2, modulo);
597 result += __builtin_popcountll(a_final ^ b_final);
598 }
599 }
600 #else // NO NEON and NOT GNUC
601 HammingLUT lut;
602 result = lut(reinterpret_cast< const unsigned char*> (a),
603 reinterpret_cast< const unsigned char*> (b), size);
604 #endif
605 return result;
606 }
607
608
609 template<typename Iterator1>
610 ResultType operator()(const Iterator1 a, ZeroIterator<unsigned char> b, size_t size, ResultType /*worst_dist*/ = -1) const
611 {
612 (void)b;
613 ResultType result = 0;
614 #if defined(__ARM_NEON__) && !defined(__CUDACC__)
615 {
616 const unsigned char* a2 = reinterpret_cast< const unsigned char*> (a);
617 uint32x4_t bits = vmovq_n_u32(0);
618 for (size_t i = 0; i < size; i += 16) {
619 uint8x16_t A_vec = vld1q_u8 (a2 + i);
620 uint8x16_t bitsSet = vcntq_u8 (A_vec);
621 uint16x8_t bitSet8 = vpaddlq_u8 (bitsSet);
622 uint32x4_t bitSet4 = vpaddlq_u16 (bitSet8);
623 bits = vaddq_u32(bits, bitSet4);
624 }
625 uint64x2_t bitSet2 = vpaddlq_u32 (bits);
626 result = vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),0);
627 result += vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),2);
628 }
629 #elif defined(__GNUC__)
630 {
631 //for portability just use unsigned long -- and use the __builtin_popcountll (see docs for __builtin_popcountll)
632 typedef unsigned long long pop_t;
633 const size_t modulo = size % sizeof(pop_t);
634 const pop_t* a2 = reinterpret_cast< const pop_t*> (a);
635 const pop_t* a2_end = a2 + (size / sizeof(pop_t));
636
637 for (; a2 != a2_end; ++a2) result += __builtin_popcountll(*a2);
638
639 if (modulo) {
640 //in the case where size is not dividable by sizeof(size_t)
641 //need to mask off the bits at the end
642 pop_t a_final = 0;
643 memcpy(&a_final, a2, modulo);
644 result += __builtin_popcountll(a_final);
645 }
646 }
647 #else // NO NEON and NOT GNUC
648 HammingLUT lut;
649 result = lut(reinterpret_cast< const unsigned char*> (a), b, size);
650 #endif
651 return result;
652 }
653};
654
655 template<typename T>
656 struct Hamming2
657{
658 typedef False is_kdtree_distance;
659 typedef False is_vector_space_distance;
660
661 typedef T ElementType;
662 typedef int ResultType;
663 typedef ElementType CentersType;
664
667 unsigned int popcnt32(uint32_t n) const
668 {
669 n -= ((n >> 1) & 0x55555555);
670 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
671 return (((n + (n >> 4))& 0xF0F0F0F)* 0x1010101) >> 24;
672 }
673
674 #ifdef FLANN_PLATFORM_64_BIT
675 unsigned int popcnt64(uint64_t n) const
676 {
677 n -= ((n >> 1) & 0x5555555555555555);
678 n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
679 return (((n + (n >> 4))& 0x0f0f0f0f0f0f0f0f)* 0x0101010101010101) >> 56;
680 }
681 #endif
682
683 template <typename Iterator1, typename Iterator2>
684 ResultType operator()(const Iterator1 a, const Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const
685 {
686 CV_DbgAssert(!(size % long_word_size_) && "vectors size must be multiple of long words size (i.e. 8)");
687
688 #ifdef FLANN_PLATFORM_64_BIT
689 const uint64_t* pa = reinterpret_cast< const uint64_t*>(a);
690 const uint64_t* pb = reinterpret_cast< const uint64_t*>(b);
691 ResultType result = 0;
692 size /= long_word_size_;
693 for(size_t i = 0; i < size; ++i ) {
694 result += popcnt64(*pa ^ *pb);
695 ++pa;
696 ++pb;
697 }
698 #else
699 const uint32_t* pa = reinterpret_cast< const uint32_t*>(a);
700 const uint32_t* pb = reinterpret_cast< const uint32_t*>(b);
701 ResultType result = 0;
702 size /= long_word_size_;
703 for(size_t i = 0; i < size; ++i ) {
704 result += popcnt32(*pa ^ *pb);
705 ++pa;
706 ++pb;
707 }
708 #endif
709 return result;
710 }
711
712
713 template <typename Iterator1>
714 ResultType operator()(const Iterator1 a, ZeroIterator<unsigned char> b, size_t size, ResultType /*worst_dist*/ = -1) const
715 {
716 CV_DbgAssert(!(size % long_word_size_) && "vectors size must be multiple of long words size (i.e. 8)");
717
718 (void)b;
719 #ifdef FLANN_PLATFORM_64_BIT
720 const uint64_t* pa = reinterpret_cast< const uint64_t*>(a);
721 ResultType result = 0;
722 size /= long_word_size_;
723 for(size_t i = 0; i < size; ++i ) {
724 result += popcnt64(*pa);
725 ++pa;
726 }
727 #else
728 const uint32_t* pa = reinterpret_cast< const uint32_t*>(a);
729 ResultType result = 0;
730 size /= long_word_size_;
731 for(size_t i = 0; i < size; ++i ) {
732 result += popcnt32(*pa);
733 ++pa;
734 }
735 #endif
736 return result;
737 }
738
739 private:
740 #ifdef FLANN_PLATFORM_64_BIT
741 static const size_t long_word_size_ = sizeof(uint64_t)/sizeof(unsigned char);
742 #else
743 static const size_t long_word_size_ = sizeof(uint32_t)/sizeof(unsigned char);
744 #endif
745};
746
747
748
750
751 struct DNAmmingLUT
752{
753 typedef False is_kdtree_distance;
754 typedef False is_vector_space_distance;
755
756 typedef unsigned char ElementType;
757 typedef int ResultType;
758 typedef ElementType CentersType;
759
762 template<typename Iterator2>
763 ResultType operator()(const unsigned char* a, const Iterator2 b, size_t size) const
764 {
765 static const uchar popCountTable[] =
766 {
767 0, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3,
768 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3,
769 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
770 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
771 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
772 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
773 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
774 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4
775 };
776 ResultType result = 0;
777 const unsigned char* b2 = reinterpret_cast< const unsigned char*> (b);
778 for (size_t i = 0; i < size; i++) {
779 result += popCountTable[a[i] ^ b2[i]];
780 }
781 return result;
782 }
783
784
785 ResultType operator()(const unsigned char* a, const ZeroIterator<unsigned char> b, size_t size) const
786 {
787 (void)b;
788 static const uchar popCountTable[] =
789 {
790 0, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3,
791 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3,
792 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
793 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
794 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
795 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
796 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4,
797 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4
798 };
799 ResultType result = 0;
800 for (size_t i = 0; i < size; i++) {
801 result += popCountTable[a[i]];
802 }
803 return result;
804 }
805};
806
807
808 template<typename T>
809 struct DNAmming2
810{
811 typedef False is_kdtree_distance;
812 typedef False is_vector_space_distance;
813
814 typedef T ElementType;
815 typedef int ResultType;
816 typedef ElementType CentersType;
817
820 unsigned int popcnt32(uint32_t n) const
821 {
822 n = ((n >> 1) | n) & 0x55555555;
823 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
824 return (((n + (n >> 4))& 0x0F0F0F0F)* 0x01010101) >> 24;
825 }
826
827 #ifdef FLANN_PLATFORM_64_BIT
828 unsigned int popcnt64(uint64_t n) const
829 {
830 n = ((n >> 1) | n) & 0x5555555555555555;
831 n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
832 return (((n + (n >> 4))& 0x0f0f0f0f0f0f0f0f)* 0x0101010101010101) >> 56;
833 }
834 #endif
835
836 template <typename Iterator1, typename Iterator2>
837 ResultType operator()(const Iterator1 a, const Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const
838 {
839 CV_DbgAssert(!(size % long_word_size_) && "vectors size must be multiple of long words size (i.e. 8)");
840
841 #ifdef FLANN_PLATFORM_64_BIT
842 const uint64_t* pa = reinterpret_cast< const uint64_t*>(a);
843 const uint64_t* pb = reinterpret_cast< const uint64_t*>(b);
844 ResultType result = 0;
845 size /= long_word_size_;
846 for(size_t i = 0; i < size; ++i ) {
847 result += popcnt64(*pa ^ *pb);
848 ++pa;
849 ++pb;
850 }
851 #else
852 const uint32_t* pa = reinterpret_cast< const uint32_t*>(a);
853 const uint32_t* pb = reinterpret_cast< const uint32_t*>(b);
854 ResultType result = 0;
855 size /= long_word_size_;
856 for(size_t i = 0; i < size; ++i ) {
857 result += popcnt32(*pa ^ *pb);
858 ++pa;
859 ++pb;
860 }
861 #endif
862 return result;
863 }
864
865
866 template <typename Iterator1>
867 ResultType operator()(const Iterator1 a, ZeroIterator<unsigned char> b, size_t size, ResultType /*worst_dist*/ = -1) const
868 {
869 CV_DbgAssert(!(size % long_word_size_) && "vectors size must be multiple of long words size (i.e. 8)");
870
871 (void)b;
872 #ifdef FLANN_PLATFORM_64_BIT
873 const uint64_t* pa = reinterpret_cast< const uint64_t*>(a);
874 ResultType result = 0;
875 size /= long_word_size_;
876 for(size_t i = 0; i < size; ++i ) {
877 result += popcnt64(*pa);
878 ++pa;
879 }
880 #else
881 const uint32_t* pa = reinterpret_cast< const uint32_t*>(a);
882 ResultType result = 0;
883 size /= long_word_size_;
884 for(size_t i = 0; i < size; ++i ) {
885 result += popcnt32(*pa);
886 ++pa;
887 }
888 #endif
889 return result;
890 }
891
892 private:
893 #ifdef FLANN_PLATFORM_64_BIT
894 static const size_t long_word_size_= sizeof(uint64_t)/sizeof(unsigned char);
895 #else
896 static const size_t long_word_size_= sizeof(uint32_t)/sizeof(unsigned char);
897 #endif
898};
899
900
901
902 template<class T>
903 struct HistIntersectionDistance
904{
905 typedef True is_kdtree_distance;
906 typedef True is_vector_space_distance;
907
908 typedef T ElementType;
909 typedef typename Accumulator<T>::Type ResultType;
910 typedef ResultType CentersType;
911
915 template <typename Iterator1, typename Iterator2>
916 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
917 {
918 ResultType result = ResultType();
919 ResultType min0, min1, min2, min3;
920 Iterator1 last = a + size;
921 Iterator1 lastgroup = last - 3;
922
923 /* Process 4 items with each loop for efficiency. */
924 while (a < lastgroup) {
925 min0 = (ResultType)(a[0] < b[0] ? a[0] : b[0]);
926 min1 = (ResultType)(a[1] < b[1] ? a[1] : b[1]);
927 min2 = (ResultType)(a[2] < b[2] ? a[2] : b[2]);
928 min3 = (ResultType)(a[3] < b[3] ? a[3] : b[3]);
929 result += min0 + min1 + min2 + min3;
930 a += 4;
931 b += 4;
932 if ((worst_dist>0)&&(result>worst_dist)) {
933 return result;
934 }
935 }
936 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
937 while (a < last) {
938 min0 = (ResultType)(*a < *b ? *a : *b);
939 result += min0;
940 ++a;
941 ++b;
942 }
943 return result;
944 }
945
949 template <typename U, typename V>
950 inline ResultType accum_dist(const U& a, const V& b, int) const
951 {
952 return a<b ? a : b;
953 }
954};
955
956
957
958 template<class T>
959 struct HellingerDistance
960{
961 typedef True is_kdtree_distance;
962 typedef True is_vector_space_distance;
963
964 typedef T ElementType;
965 typedef typename Accumulator<T>::Type ResultType;
966 typedef ResultType CentersType;
967
971 template <typename Iterator1, typename Iterator2>
972 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const
973 {
974 ResultType result = ResultType();
975 ResultType diff0, diff1, diff2, diff3;
976 Iterator1 last = a + size;
977 Iterator1 lastgroup = last - 3;
978
979 /* Process 4 items with each loop for efficiency. */
980 while (a < lastgroup) {
981 diff0 = sqrt(static_cast<ResultType>(a[0])) - sqrt(static_cast<ResultType>(b[0]));
982 diff1 = sqrt(static_cast<ResultType>(a[1])) - sqrt(static_cast<ResultType>(b[1]));
983 diff2 = sqrt(static_cast<ResultType>(a[2])) - sqrt(static_cast<ResultType>(b[2]));
984 diff3 = sqrt(static_cast<ResultType>(a[3])) - sqrt(static_cast<ResultType>(b[3]));
985 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
986 a += 4;
987 b += 4;
988 }
989 while (a < last) {
990 diff0 = sqrt(static_cast<ResultType>(*a++)) - sqrt(static_cast<ResultType>(*b++));
991 result += diff0 * diff0;
992 }
993 return result;
994 }
995
999 template <typename U, typename V>
1000 inline ResultType accum_dist(const U& a, const V& b, int) const
1001 {
1002 ResultType diff = sqrt(static_cast<ResultType>(a)) - sqrt(static_cast<ResultType>(b));
1003 return diff * diff;
1004 }
1005};
1006
1007
1008 template<class T>
1009 struct ChiSquareDistance
1010{
1011 typedef True is_kdtree_distance;
1012 typedef True is_vector_space_distance;
1013
1014 typedef T ElementType;
1015 typedef typename Accumulator<T>::Type ResultType;
1016 typedef ResultType CentersType;
1017
1021 template <typename Iterator1, typename Iterator2>
1022 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
1023 {
1024 ResultType result = ResultType();
1025 ResultType sum, diff;
1026 Iterator1 last = a + size;
1027
1028 while (a < last) {
1029 sum = (ResultType)(*a + *b);
1030 if (sum>0) {
1031 diff = (ResultType)(*a - *b);
1032 result += diff*diff/sum;
1033 }
1034 ++a;
1035 ++b;
1036
1037 if ((worst_dist>0)&&(result>worst_dist)) {
1038 return result;
1039 }
1040 }
1041 return result;
1042 }
1043
1047 template <typename U, typename V>
1048 inline ResultType accum_dist(const U& a, const V& b, int) const
1049 {
1050 ResultType result = ResultType();
1051 ResultType sum, diff;
1052
1053 sum = (ResultType)(a+b);
1054 if (sum>0) {
1055 diff = (ResultType)(a-b);
1056 result = diff*diff/sum;
1057 }
1058 return result;
1059 }
1060};
1061
1062
1063 template<class T>
1064 struct KL_Divergence
1065{
1066 typedef True is_kdtree_distance;
1067 typedef True is_vector_space_distance;
1068
1069 typedef T ElementType;
1070 typedef typename Accumulator<T>::Type ResultType;
1071 typedef ResultType CentersType;
1072
1076 template <typename Iterator1, typename Iterator2>
1077 ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const
1078 {
1079 ResultType result = ResultType();
1080 Iterator1 last = a + size;
1081
1082 while (a < last) {
1083 if ( *a != 0 && *b != 0 ) {
1084 ResultType ratio = (ResultType)(*a / *b);
1085 if (ratio>0) {
1086 result += *a * log(ratio);
1087 }
1088 }
1089 ++a;
1090 ++b;
1091
1092 if ((worst_dist>0)&&(result>worst_dist)) {
1093 return result;
1094 }
1095 }
1096 return result;
1097 }
1098
1102 template <typename U, typename V>
1103 inline ResultType accum_dist(const U& a, const V& b, int) const
1104 {
1105 ResultType result = ResultType();
1106 if( a != 0 && b != 0 ) {
1107 ResultType ratio = (ResultType)(a / b);
1108 if (ratio>0) {
1109 result = a * log(ratio);
1110 }
1111 }
1112 return result;
1113 }
1114};
1115
1116
1117 /*
1118 * Depending on processed distances, some of them are already squared (e.g. L2)
1119 * and some are not (e.g.Hamming). In KMeans++ for instance we want to be sure
1120 * we are working on ^2 distances, thus following templates to ensure that.
1121 */
1122 template <typename Distance, typename ElementType>
1123 struct squareDistance
1124{
1125 typedef typename Distance::ResultType ResultType;
1126 ResultType operator()( ResultType dist ) { return dist*dist; }
1127};
1128
1129
1130 template <typename ElementType>
1131 struct squareDistance<L2_Simple<ElementType>, ElementType>
1132{
1133 typedef typename L2_Simple<ElementType>::ResultType ResultType;
1134 ResultType operator()( ResultType dist ) { return dist; }
1135};
1136
1137 template <typename ElementType>
1138 struct squareDistance<L2<ElementType>, ElementType>
1139{
1140 typedef typename L2<ElementType>::ResultType ResultType;
1141 ResultType operator()( ResultType dist ) { return dist; }
1142};
1143
1144
1145 template <typename ElementType>
1146 struct squareDistance<MinkowskiDistance<ElementType>, ElementType>
1147{
1148 typedef typename MinkowskiDistance<ElementType>::ResultType ResultType;
1149 ResultType operator()( ResultType dist ) { return dist; }
1150};
1151
1152 template <typename ElementType>
1153 struct squareDistance<HellingerDistance<ElementType>, ElementType>
1154{
1155 typedef typename HellingerDistance<ElementType>::ResultType ResultType;
1156 ResultType operator()( ResultType dist ) { return dist; }
1157};
1158
1159 template <typename ElementType>
1160 struct squareDistance<ChiSquareDistance<ElementType>, ElementType>
1161{
1162 typedef typename ChiSquareDistance<ElementType>::ResultType ResultType;
1163 ResultType operator()( ResultType dist ) { return dist; }
1164};
1165
1166
1167 template <typename Distance>
1168 typename Distance::ResultType ensureSquareDistance( typename Distance::ResultType dist )
1169{
1170 typedef typename Distance::ElementType ElementType;
1171
1172 squareDistance<Distance, ElementType> dummy;
1173 return dummy( dist );
1174}
1175
1176
1177 /*
1178 * ...a template to tell the user if the distance he is working with is actually squared
1179 */
1180
1181 template <typename Distance, typename ElementType>
1182 struct isSquareDist
1183{
1184 bool operator()() { return false; }
1185};
1186
1187
1188 template <typename ElementType>
1189 struct isSquareDist<L2_Simple<ElementType>, ElementType>
1190{
1191 bool operator()() { return true; }
1192};
1193
1194 template <typename ElementType>
1195 struct isSquareDist<L2<ElementType>, ElementType>
1196{
1197 bool operator()() { return true; }
1198};
1199
1200
1201 template <typename ElementType>
1202 struct isSquareDist<MinkowskiDistance<ElementType>, ElementType>
1203{
1204 bool operator()() { return true; }
1205};
1206
1207 template <typename ElementType>
1208 struct isSquareDist<HellingerDistance<ElementType>, ElementType>
1209{
1210 bool operator()() { return true; }
1211};
1212
1213 template <typename ElementType>
1214 struct isSquareDist<ChiSquareDistance<ElementType>, ElementType>
1215{
1216 bool operator()() { return true; }
1217};
1218
1219
1220 template <typename Distance>
1221 bool isSquareDistance()
1222{
1223 typedef typename Distance::ElementType ElementType;
1224
1225 isSquareDist<Distance, ElementType> dummy;
1226 return dummy();
1227}
1228
1229 /*
1230 * ...and a template to ensure the user that he will process the normal distance,
1231 * and not squared distance, without losing processing time calling sqrt(ensureSquareDistance)
1232 * that will result in doing actually sqrt(dist*dist) for L1 distance for instance.
1233 */
1234 template <typename Distance, typename ElementType>
1235 struct simpleDistance
1236{
1237 typedef typename Distance::ResultType ResultType;
1238 ResultType operator()( ResultType dist ) { return dist; }
1239};
1240
1241
1242 template <typename ElementType>
1243 struct simpleDistance<L2_Simple<ElementType>, ElementType>
1244{
1245 typedef typename L2_Simple<ElementType>::ResultType ResultType;
1246 ResultType operator()( ResultType dist ) { return sqrt(dist); }
1247};
1248
1249 template <typename ElementType>
1250 struct simpleDistance<L2<ElementType>, ElementType>
1251{
1252 typedef typename L2<ElementType>::ResultType ResultType;
1253 ResultType operator()( ResultType dist ) { return sqrt(dist); }
1254};
1255
1256
1257 template <typename ElementType>
1258 struct simpleDistance<MinkowskiDistance<ElementType>, ElementType>
1259{
1260 typedef typename MinkowskiDistance<ElementType>::ResultType ResultType;
1261 ResultType operator()( ResultType dist ) { return sqrt(dist); }
1262};
1263
1264 template <typename ElementType>
1265 struct simpleDistance<HellingerDistance<ElementType>, ElementType>
1266{
1267 typedef typename HellingerDistance<ElementType>::ResultType ResultType;
1268 ResultType operator()( ResultType dist ) { return sqrt(dist); }
1269};
1270
1271 template <typename ElementType>
1272 struct simpleDistance<ChiSquareDistance<ElementType>, ElementType>
1273{
1274 typedef typename ChiSquareDistance<ElementType>::ResultType ResultType;
1275 ResultType operator()( ResultType dist ) { return sqrt(dist); }
1276};
1277
1278
1279 template <typename Distance>
1280 typename Distance::ResultType ensureSimpleDistance( typename Distance::ResultType dist )
1281{
1282 typedef typename Distance::ElementType ElementType;
1283
1284 simpleDistance<Distance, ElementType> dummy;
1285 return dummy( dist );
1286}
1287
1288}
1289
1291
1292 #endif //OPENCV_FLANN_DIST_H_
cv::sqrt
CV_EXPORTS_W void sqrt(InputArray src, OutputArray dst)
Calculates a square root of array elements.
cv::pow
CV_EXPORTS_W void pow(InputArray src, double power, OutputArray dst)
Raises every array element to a power.
cv::log
CV_EXPORTS_W void log(InputArray src, OutputArray dst)
Calculates the natural logarithm of every array element.
cv::operator*
CV_INLINE v_reg< _Tp, n > operator*(const v_reg< _Tp, n > &a, const v_reg< _Tp, n > &b)
Multiply values
cv::abs
softfloat abs(softfloat a)
Absolute value
Definition: softfloat.hpp:444
CV_DbgAssert
#define CV_DbgAssert(expr)
Definition: base.hpp:375
構築: doxygen 1.9.2