1 /***********************************************************************
2 * Software License Agreement (BSD License)
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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 *************************************************************************/
37 #include "constants.h"
43 * Distance function by default set to the custom distance
44 * function. This can be set to a specific distance function
45 * for further efficiency.
47 #define flann_dist custom_dist
48 //#define flann_dist euclidean_dist
52 * Compute the squared Euclidean distance between two vectors.
54 * This is highly optimised, with loop unrolling, as it is one
55 * of the most expensive inner loops.
57 * The computation of squared root at the end is omitted for
60 template <typename Iterator1, typename Iterator2>
61 double euclidean_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
64 double diff0, diff1, diff2, diff3;
65 Iterator1 lastgroup = last1 - 3;
67 /* Process 4 items with each loop for efficiency. */
68 while (first1 < lastgroup) {
69 diff0 = first1[0] - first2[0];
70 diff1 = first1[1] - first2[1];
71 diff2 = first1[2] - first2[2];
72 diff3 = first1[3] - first2[3];
73 distsq += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
77 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
78 while (first1 < last1) {
79 diff0 = *first1++ - *first2++;
80 distsq += diff0 * diff0;
86 * Compute the Manhattan (L_1) distance between two vectors.
88 * This is highly optimised, with loop unrolling, as it is one
89 * of the most expensive inner loops.
91 template <typename Iterator1, typename Iterator2>
92 double manhattan_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
95 double diff0, diff1, diff2, diff3;
96 Iterator1 lastgroup = last1 - 3;
98 /* Process 4 items with each loop for efficiency. */
99 while (first1 < lastgroup) {
100 diff0 = fabs(first1[0] - first2[0]);
101 diff1 = fabs(first1[1] - first2[1]);
102 diff2 = fabs(first1[2] - first2[2]);
103 diff3 = fabs(first1[3] - first2[3]);
104 distsq += diff0 + diff1 + diff2 + diff3;
108 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
109 while (first1 < last1) {
110 diff0 = fabs(*first1++ - *first2++);
117 extern int flann_minkowski_order;
119 * Compute the Minkowski (L_p) distance between two vectors.
121 * This is highly optimised, with loop unrolling, as it is one
122 * of the most expensive inner loops.
124 * The computation of squared root at the end is omitted for
127 template <typename Iterator1, typename Iterator2>
128 double minkowski_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
131 double diff0, diff1, diff2, diff3;
132 Iterator1 lastgroup = last1 - 3;
134 int p = flann_minkowski_order;
136 /* Process 4 items with each loop for efficiency. */
137 while (first1 < lastgroup) {
138 diff0 = fabs(first1[0] - first2[0]);
139 diff1 = fabs(first1[1] - first2[1]);
140 diff2 = fabs(first1[2] - first2[2]);
141 diff3 = fabs(first1[3] - first2[3]);
142 distsq += pow(diff0,p) + pow(diff1,p) + pow(diff2,p) + pow(diff3,p);
146 /* Process last 0-3 pixels. Not needed for standard vector lengths. */
147 while (first1 < last1) {
148 diff0 = fabs(*first1++ - *first2++);
149 distsq += pow(diff0,p);
157 extern flann_distance_t flann_distance_type;
159 * Custom distance function. The distance computed is dependent on the value
160 * of the 'flann_distance_type' global variable.
162 * If the last argument 'acc' is passed, the result is accumulated to the value
165 template <typename Iterator1, typename Iterator2>
166 float custom_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
168 switch (flann_distance_type) {
170 return (float)euclidean_dist(first1, last1, first2, acc);
172 return (float)manhattan_dist(first1, last1, first2, acc);
174 return (float)minkowski_dist(first1, last1, first2, acc);
176 return (float)euclidean_dist(first1, last1, first2, acc);
181 * This is a "zero iterator". It basically behaves like a zero filled
182 * array to all algorithms that use arrays as iterators (STL style).
183 * It's useful when there's a need to compute the distance between feature
184 * and origin it and allows for better compiler optimisation than using a
187 template <typename T>
188 struct ZeroIterator {
194 T operator[](int /*index*/) {
198 ZeroIterator<T>& operator ++(int) {
202 ZeroIterator<T>& operator+=(int) {
207 extern ZeroIterator<float> zero;