31 #ifndef OPENCV_FLANN_DIST_H_
32 #define OPENCV_FLANN_DIST_H_
46 #if (defined WIN32 || defined _WIN32) && defined(_M_ARM)
51 # include "arm_neon.h"
58 inline T abs(
T x) {
return (x<0) ? -x :
x; }
111 template <
typename Iterator1,
typename Iterator2>
116 for(
size_t i = 0; i <
size; ++i ) {
123 template <
typename U,
typename V>
153 template <
typename Iterator1,
typename Iterator2>
158 Iterator1 last = a +
size;
159 Iterator1 lastgroup = last - 3;
162 while (a < lastgroup) {
167 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
171 if ((worst_dist>0)&&(result>worst_dist)) {
178 result += diff0 * diff0;
189 template <
typename U,
typename V>
215 template <
typename Iterator1,
typename Iterator2>
220 Iterator1 last = a +
size;
221 Iterator1 lastgroup = last - 3;
224 while (a < lastgroup) {
229 result += diff0 + diff1 + diff2 + diff3;
233 if ((worst_dist>0)&&(result>worst_dist)) {
248 template <
typename U,
typename V>
279 template <
typename Iterator1,
typename Iterator2>
284 Iterator1 last = a +
size;
285 Iterator1 lastgroup = last - 3;
288 while (a < lastgroup) {
297 if ((worst_dist>0)&&(result>worst_dist)) {
312 template <
typename U,
typename V>
315 return pow(static_cast<ResultType>(
abs(a-b)),
order);
335 template <
typename Iterator1,
typename Iterator2>
340 Iterator1 last = a +
size;
341 Iterator1 lastgroup = last - 3;
344 while (a < lastgroup) {
345 diff0 =
abs(a[0] - b[0]);
346 diff1 =
abs(a[1] - b[1]);
347 diff2 =
abs(a[2] - b[2]);
348 diff3 =
abs(a[3] - b[3]);
349 if (diff0>result) {result = diff0; }
350 if (diff1>result) {result = diff1; }
351 if (diff2>result) {result = diff2; }
352 if (diff3>result) {result = diff3; }
356 if ((worst_dist>0)&&(result>worst_dist)) {
362 diff0 =
abs(*a++ - *b++);
363 result = (diff0>
result) ? diff0 : result;
391 static const uchar popCountTable[] =
393 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,
394 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,
395 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,
396 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,
397 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,
398 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,
399 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,
400 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
403 for (
int i = 0; i <
size; i++) {
404 result += popCountTable[a[i] ^ b[i]];
426 static const uchar popCountTable[] =
428 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,
429 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,
430 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,
431 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,
432 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,
433 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,
434 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,
435 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
438 for (
size_t i = 0; i <
size; i++) {
439 result += popCountTable[a[i] ^ b[i]];
459 template<
typename Iterator1,
typename Iterator2>
465 uint32x4_t
bits = vmovq_n_u32(0);
466 for (
size_t i = 0; i <
size; i += 16) {
467 uint8x16_t A_vec = vld1q_u8 (a + i);
468 uint8x16_t B_vec = vld1q_u8 (b + i);
469 uint8x16_t AxorB = veorq_u8 (A_vec, B_vec);
470 uint8x16_t bitsSet = vcntq_u8 (AxorB);
471 uint16x8_t bitSet8 = vpaddlq_u8 (bitsSet);
472 uint32x4_t bitSet4 = vpaddlq_u16 (bitSet8);
473 bits = vaddq_u32(bits, bitSet4);
475 uint64x2_t bitSet2 = vpaddlq_u32 (bits);
476 result = vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),0);
477 result += vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),2);
482 typedef unsigned long long pop_t;
483 const size_t modulo = size %
sizeof(pop_t);
484 const pop_t* a2 =
reinterpret_cast<const pop_t*
> (
a);
485 const pop_t* b2 =
reinterpret_cast<const pop_t*
> (
b);
486 const pop_t* a2_end = a2 + (size /
sizeof(pop_t));
488 for (; a2 != a2_end; ++a2, ++b2) result += __builtin_popcountll((*a2) ^ (*b2));
493 pop_t a_final = 0, b_final = 0;
494 memcpy(&a_final, a2, modulo);
495 memcpy(&b_final, b2, modulo);
496 result += __builtin_popcountll(a_final ^ b_final);
499 #else // NO NEON and NOT GNUC
500 typedef unsigned long long pop_t;
502 result =
lut(reinterpret_cast<const unsigned char*> (a),
503 reinterpret_cast<const unsigned char*> (b), size *
sizeof(pop_t));
522 n -= ((n >> 1) & 0x55555555);
523 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
524 return (((n + (n >> 4))& 0xF0F0F0F)* 0x1010101) >> 24;
527 #ifdef FLANN_PLATFORM_64_BIT
530 n -= ((n >> 1) & 0x5555555555555555);
531 n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
532 return (((n + (n >> 4))& 0x0f0f0f0f0f0f0f0f)* 0x0101010101010101) >> 56;
536 template <
typename Iterator1,
typename Iterator2>
539 #ifdef FLANN_PLATFORM_64_BIT
543 size /= (
sizeof(
uint64_t)/
sizeof(
unsigned char));
544 for(
size_t i = 0; i <
size; ++i ) {
553 size /= (
sizeof(
uint32_t)/
sizeof(
unsigned char));
554 for(
size_t i = 0; i <
size; ++i ) {
580 template <
typename Iterator1,
typename Iterator2>
585 Iterator1 last = a +
size;
586 Iterator1 lastgroup = last - 3;
589 while (a < lastgroup) {
590 min0 = (
ResultType)(a[0] < b[0] ? a[0] : b[0]);
591 min1 = (
ResultType)(a[1] < b[1] ? a[1] : b[1]);
592 min2 = (
ResultType)(a[2] < b[2] ? a[2] : b[2]);
593 min3 = (
ResultType)(a[3] < b[3] ? a[3] : b[3]);
594 result += min0 + min1 + min2 + min3;
597 if ((worst_dist>0)&&(result>worst_dist)) {
614 template <
typename U,
typename V>
635 template <
typename Iterator1,
typename Iterator2>
640 Iterator1 last = a +
size;
641 Iterator1 lastgroup = last - 3;
644 while (a < lastgroup) {
645 diff0 =
sqrt(static_cast<ResultType>(a[0])) -
sqrt(static_cast<ResultType>(b[0]));
646 diff1 =
sqrt(static_cast<ResultType>(a[1])) -
sqrt(static_cast<ResultType>(b[1]));
647 diff2 =
sqrt(static_cast<ResultType>(a[2])) -
sqrt(static_cast<ResultType>(b[2]));
648 diff3 =
sqrt(static_cast<ResultType>(a[3])) -
sqrt(static_cast<ResultType>(b[3]));
649 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
654 diff0 =
sqrt(static_cast<ResultType>(*a++)) -
sqrt(static_cast<ResultType>(*b++));
655 result += diff0 * diff0;
663 template <
typename U,
typename V>
666 return sqrt(static_cast<ResultType>(a)) -
sqrt(static_cast<ResultType>(b));
683 template <
typename Iterator1,
typename Iterator2>
688 Iterator1 last = a +
size;
694 result += diff*diff/
sum;
699 if ((worst_dist>0)&&(result>worst_dist)) {
709 template <
typename U,
typename V>
718 result = diff*diff/
sum;
737 template <
typename Iterator1,
typename Iterator2>
741 Iterator1 last = a +
size;
747 result += *a *
log(ratio);
753 if ((worst_dist>0)&&(result>worst_dist)) {
763 template <
typename U,
typename V>
769 result = a *
log(ratio);
784 template <
typename T>
817 #endif //OPENCV_FLANN_DIST_H_
unsigned __int32 uint32_t
Definition: dist.h:38
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:336
short float uchar uchar uchar uchar uchar ushort int uchar ushort int float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float int int int float int int int float int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP char CV_CUDEV_IMPLEMENT_VEC_BINARY_OP ushort CV_CUDEV_IMPLEMENT_VEC_BINARY_OP short CV_CUDEV_IMPLEMENT_VEC_BINARY_OP int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP uint CV_CUDEV_IMPLEMENT_VEC_BINARY_OP float CV_CUDEV_IMPLEMENT_VEC_BINARY_OP double char
Definition: vec_math.hpp:426
Accumulator< T >::Type ResultType
Definition: dist.h:575
CV_EXPORTS_W void sqrt(InputArray src, OutputArray dst)
computes square root of each matrix element (dst = src**0.5)
T ElementType
Definition: dist.h:141
unsigned int popcnt32(uint32_t n) const
Definition: dist.h:520
float Type
Definition: dist.h:78
False is_vector_space_distance
Definition: dist.h:417
CvArr const CvArr * lut
Definition: core_c.h:1439
True is_kdtree_distance
Definition: dist.h:138
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:124
True is_vector_space_distance
Definition: dist.h:627
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType=-1) const
Definition: dist.h:537
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:615
int ResultType
Definition: dist.h:385
const CvArr * U
Definition: core_c.h:733
CvPoint2D32f float float b
Definition: legacy.hpp:578
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:710
True is_kdtree_distance
Definition: dist.h:105
ResultType operator()(const unsigned char *a, const unsigned char *b, int size) const
Definition: dist.h:389
Accumulator< T >::Type ResultType
Definition: dist.h:678
CvSize size
Definition: calib3d.hpp:212
float Type
Definition: dist.h:72
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType=-1) const
Definition: dist.h:460
float Type
Definition: dist.h:76
ZeroIterator< T > & operator+=(int)
Definition: dist.h:808
T ElementType
Definition: dist.h:629
True is_kdtree_distance
Definition: dist.h:260
int ResultType
Definition: dist.h:457
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:249
True is_kdtree_distance
Definition: dist.h:626
Accumulator< T >::Type ResultType
Definition: dist.h:109
T operator[](int)
Definition: dist.h:793
const CvMat const CvMat const CvMat CvMat CvMat CvMat CvMat CvSize CvMat CvMat * T
Definition: calib3d.hpp:270
T ElementType
Definition: dist.h:263
False is_vector_space_distance
Definition: dist.h:382
float Type
Definition: dist.h:80
double abs< double >(double x)
Definition: dist.h:67
OutputArray sum
Definition: imgproc.hpp:620
False is_kdtree_distance
Definition: dist.h:416
int ResultType
Definition: dist.h:420
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:738
Accumulator< T >::Type ResultType
Definition: dist.h:732
unsigned __int64 uint64_t
Definition: dist.h:39
False is_vector_space_distance
Definition: dist.h:453
Accumulator< T >::Type ResultType
Definition: dist.h:328
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType=-1) const
Definition: dist.h:636
False is_kdtree_distance
Definition: dist.h:512
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:764
False is_kdtree_distance
Definition: dist.h:381
T ElementType
Definition: dist.h:515
unsigned char ElementType
Definition: dist.h:384
unsigned char ElementType
Definition: dist.h:419
float Type
Definition: dist.h:74
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType=-1) const
Definition: dist.h:112
int order
Definition: dist.h:266
GLenum GLint x
Definition: core_c.h:632
True is_vector_space_distance
Definition: dist.h:729
T ElementType
Definition: dist.h:108
Accumulator< T >::Type ResultType
Definition: dist.h:142
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:216
T ElementType
Definition: dist.h:206
T ElementType
Definition: dist.h:731
ResultType operator()(const unsigned char *a, const unsigned char *b, size_t size) const
Definition: dist.h:424
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:190
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:664
GLboolean GLboolean GLboolean b
Definition: legacy.hpp:633
True is_kdtree_distance
Definition: dist.h:571
True is_vector_space_distance
Definition: dist.h:204
const CvArr const CvArr * V
Definition: core_c.h:733
ResultType accum_dist(const U &a, const V &b, int) const
Definition: dist.h:313
float Type
Definition: dist.h:82
True is_vector_space_distance
Definition: dist.h:325
True is_vector_space_distance
Definition: dist.h:261
T ElementType
Definition: dist.h:677
True is_vector_space_distance
Definition: dist.h:572
const ZeroIterator< T > & operator++()
Definition: dist.h:798
CV_EXPORTS_W void log(InputArray src, OutputArray dst)
computes natural logarithm of absolute value of each matrix element: dst = log(abs(src)) ...
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:280
True is_vector_space_distance
Definition: dist.h:675
Accumulator< T >::Type ResultType
Definition: dist.h:264
GLboolean GLboolean GLboolean GLboolean a
Definition: legacy.hpp:633
True is_kdtree_distance
Definition: dist.h:728
T ElementType
Definition: dist.h:327
int abs< int >(int x)
Definition: dist.h:61
Accumulator< T >::Type ResultType
Definition: dist.h:207
unsigned int popcnt64(uint64_t n) const
Definition: dist.h:528
unsigned char uchar
Definition: types_c.h:170
T Type
Definition: dist.h:70
False is_kdtree_distance
Definition: dist.h:452
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:684
True is_kdtree_distance
Definition: dist.h:674
float abs< float >(float x)
Definition: dist.h:64
T ElementType
Definition: dist.h:574
::max::max int
Definition: functional.hpp:324
T abs(T x)
Definition: dist.h:58
CvPoint2D32f float a
Definition: legacy.hpp:578
int x
Definition: highgui_c.h:186
T operator*()
Definition: dist.h:788
short
Definition: vec_math.hpp:153
int ResultType
Definition: dist.h:516
True is_vector_space_distance
Definition: dist.h:139
MinkowskiDistance(int order_)
Definition: dist.h:268
True is_kdtree_distance
Definition: dist.h:203
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:581
True is_vector_space_distance
Definition: dist.h:106
Accumulator< T >::Type ResultType
Definition: dist.h:630
False is_kdtree_distance
Definition: dist.h:324
CV_EXPORTS_W void pow(InputArray src, double power, OutputArray dst)
raises the input matrix elements to the specified power (b = a**power)
T ElementType
Definition: dist.h:456
GLsizeiptr size
Definition: core_c.h:939
ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist=-1) const
Definition: dist.h:154
False is_vector_space_distance
Definition: dist.h:513