git.maemo.org Git - opencv/blob - 3rdparty/flann/algorithms/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 DIST_H
  32 #define DIST_H
  33
  34 #include <cmath>
  35 using namespace std;
  36
  37 #include "constants.h"
  38
  39 namespace flann
  40 {
  41
  42 /**
  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.
  46  */
  47 #define flann_dist custom_dist
  48 //#define flann_dist euclidean_dist
  49
  50
  51 /**
  52  *  Compute the squared Euclidean distance between two vectors.
  53  *
  54  *      This is highly optimised, with loop unrolling, as it is one
  55  *      of the most expensive inner loops.
  56  *
  57  *      The computation of squared root at the end is omitted for
  58  *      efficiency.
  59  */
  60 template <typename Iterator1, typename Iterator2>
  61 double euclidean_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
  62 {
  63         double distsq = acc;
  64         double diff0, diff1, diff2, diff3;
  65         Iterator1 lastgroup = last1 - 3;
  66
  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;
  74                 first1 += 4;
  75                 first2 += 4;
  76         }
  77         /* Process last 0-3 pixels.  Not needed for standard vector lengths. */
  78         while (first1 < last1) {
  79                 diff0 = *first1++ - *first2++;
  80                 distsq += diff0 * diff0;
  81         }
  82         return distsq;
  83 }
  84
  85 /**
  86  *  Compute the Manhattan (L_1) distance between two vectors.
  87  *
  88  *      This is highly optimised, with loop unrolling, as it is one
  89  *      of the most expensive inner loops.
  90  */
  91 template <typename Iterator1, typename Iterator2>
  92 double manhattan_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
  93 {
  94         double distsq = acc;
  95         double diff0, diff1, diff2, diff3;
  96         Iterator1 lastgroup = last1 - 3;
  97
  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;
 105                 first1 += 4;
 106                 first2 += 4;
 107         }
 108         /* Process last 0-3 pixels.  Not needed for standard vector lengths. */
 109         while (first1 < last1) {
 110                 diff0 = fabs(*first1++ - *first2++);
 111                 distsq += diff0;
 112         }
 113         return distsq;
 114 }
 115
 116
 117 extern int flann_minkowski_order;
 118 /**
 119  *  Compute the Minkowski (L_p) distance between two vectors.
 120  *
 121  *      This is highly optimised, with loop unrolling, as it is one
 122  *      of the most expensive inner loops.
 123  *
 124  *      The computation of squared root at the end is omitted for
 125  *      efficiency.
 126  */
 127 template <typename Iterator1, typename Iterator2>
 128 double minkowski_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
 129 {
 130         double distsq = acc;
 131         double diff0, diff1, diff2, diff3;
 132         Iterator1 lastgroup = last1 - 3;
 133
 134         int p = flann_minkowski_order;
 135
 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);
 143                 first1 += 4;
 144                 first2 += 4;
 145         }
 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);
 150         }
 151         return distsq;
 152 }
 153
 154
 155
 156
 157 extern flann_distance_t flann_distance_type;
 158 /**
 159  * Custom distance function. The distance computed is dependent on the value
 160  * of the 'flann_distance_type' global variable.
 161  *
 162  * If the last argument 'acc' is passed, the result is accumulated to the value
 163  * of this argument.
 164  */
 165 template <typename Iterator1, typename Iterator2>
 166 float custom_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
 167 {
 168         switch (flann_distance_type) {
 169         case EUCLIDEAN:
 170                 return (float)euclidean_dist(first1, last1, first2, acc);
 171         case MANHATTAN:
 172                 return (float)manhattan_dist(first1, last1, first2, acc);
 173         case MINKOWSKI:
 174                 return (float)minkowski_dist(first1, last1, first2, acc);
 175         default:
 176                 return (float)euclidean_dist(first1, last1, first2, acc);
 177         }
 178 }
 179
 180 /*
 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
 185  * zero-filled array.
 186  */
 187 template <typename T>
 188 struct ZeroIterator {
 189
 190         T operator*() {
 191                 return 0;
 192         }
 193
 194         T operator[](int /*index*/) {
 195                 return 0;
 196         }
 197
 198         ZeroIterator<T>& operator ++(int) {
 199                 return *this;
 200         }
 201
 202         ZeroIterator<T>& operator+=(int) {
 203                 return *this;
 204         }
 205
 206 };
 207 extern ZeroIterator<float> zero;
 208
 209 }
 210
 211 #endif //DIST_H