00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #ifndef _OPENCV_DIST_H_
00032 #define _OPENCV_DIST_H_
00033
00034 #include <cmath>
00035
00036 #include "opencv2/flann/general.h"
00037
00038 namespace cvflann
00039 {
00040
00046 #define flann_dist custom_dist
00047
00048
00049
00059 template <typename Iterator1, typename Iterator2>
00060 double euclidean_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00061 {
00062 double distsq = acc;
00063 double diff0, diff1, diff2, diff3;
00064 Iterator1 lastgroup = last1 - 3;
00065
00066
00067 while (first1 < lastgroup) {
00068 diff0 = first1[0] - first2[0];
00069 diff1 = first1[1] - first2[1];
00070 diff2 = first1[2] - first2[2];
00071 diff3 = first1[3] - first2[3];
00072 distsq += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
00073 first1 += 4;
00074 first2 += 4;
00075 }
00076
00077 while (first1 < last1) {
00078 diff0 = *first1++ - *first2++;
00079 distsq += diff0 * diff0;
00080 }
00081 return distsq;
00082 }
00083
00084 CV_EXPORTS double euclidean_dist(const unsigned char* first1, const unsigned char* last1, unsigned char* first2, double acc);
00085
00086
00093 template <typename Iterator1, typename Iterator2>
00094 double manhattan_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00095 {
00096 double distsq = acc;
00097 double diff0, diff1, diff2, diff3;
00098 Iterator1 lastgroup = last1 - 3;
00099
00100
00101 while (first1 < lastgroup) {
00102 diff0 = fabs(first1[0] - first2[0]);
00103 diff1 = fabs(first1[1] - first2[1]);
00104 diff2 = fabs(first1[2] - first2[2]);
00105 diff3 = fabs(first1[3] - first2[3]);
00106 distsq += diff0 + diff1 + diff2 + diff3;
00107 first1 += 4;
00108 first2 += 4;
00109 }
00110
00111 while (first1 < last1) {
00112 diff0 = fabs(*first1++ - *first2++);
00113 distsq += diff0;
00114 }
00115 return distsq;
00116 }
00117
00118
00119 CV_EXPORTS int flann_minkowski_order();
00129 template <typename Iterator1, typename Iterator2>
00130 double minkowski_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00131 {
00132 double distsq = acc;
00133 double diff0, diff1, diff2, diff3;
00134 Iterator1 lastgroup = last1 - 3;
00135
00136 int p = flann_minkowski_order();
00137
00138
00139 while (first1 < lastgroup) {
00140 diff0 = fabs(first1[0] - first2[0]);
00141 diff1 = fabs(first1[1] - first2[1]);
00142 diff2 = fabs(first1[2] - first2[2]);
00143 diff3 = fabs(first1[3] - first2[3]);
00144 distsq += pow(diff0,p) + pow(diff1,p) + pow(diff2,p) + pow(diff3,p);
00145 first1 += 4;
00146 first2 += 4;
00147 }
00148
00149 while (first1 < last1) {
00150 diff0 = fabs(*first1++ - *first2++);
00151 distsq += pow(diff0,p);
00152 }
00153 return distsq;
00154 }
00155
00156
00157
00158 template <typename Iterator1, typename Iterator2>
00159 double max_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00160 {
00161 double dist = acc;
00162 Iterator1 lastgroup = last1 - 3;
00163 double diff0, diff1, diff2, diff3;
00164
00165
00166 while (first1 < lastgroup) {
00167 diff0 = fabs(first1[0] - first2[0]);
00168 diff1 = fabs(first1[1] - first2[1]);
00169 diff2 = fabs(first1[2] - first2[2]);
00170 diff3 = fabs(first1[3] - first2[3]);
00171 if (diff0 > dist) dist = diff0;
00172 if (diff1 > dist) dist = diff1;
00173 if (diff2 > dist) dist = diff2;
00174 if (diff3 > dist) dist = diff3;
00175 first1 += 4;
00176 first2 += 4;
00177 }
00178
00179 while (first1 < last1) {
00180 diff0 = fabs(*first1++ - *first2++);
00181 dist = (diff0 > dist) ? diff0 : dist;
00182 }
00183 return dist;
00184 }
00185
00186
00187 template <typename Iterator1, typename Iterator2>
00188 double hist_intersection_kernel(Iterator1 first1, Iterator1 last1, Iterator2 first2)
00189 {
00190 double kernel = 0;
00191 Iterator1 lastgroup = last1 - 3;
00192 double min0, min1, min2, min3;
00193
00194
00195 while (first1 < lastgroup) {
00196 min0 = first1[0] < first2[0] ? first1[0] : first2[0];
00197 min1 = first1[1] < first2[1] ? first1[1] : first2[1];
00198 min2 = first1[2] < first2[2] ? first1[2] : first2[2];
00199 min3 = first1[3] < first2[3] ? first1[3] : first2[3];
00200 kernel += min0 + min1 + min2 + min3;
00201 first1 += 4;
00202 first2 += 4;
00203 }
00204
00205 while (first1 < last1) {
00206 min0 = first1[0] < first2[0] ? first1[0] : first2[0];
00207 kernel += min0;
00208 first1++;
00209 first2++;
00210 }
00211 return kernel;
00212 }
00213
00214 template <typename Iterator1, typename Iterator2>
00215 double hist_intersection_dist_sq(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00216 {
00217 double dist_sq = acc - 2 * hist_intersection_kernel(first1, last1, first2);
00218 while (first1 < last1) {
00219 dist_sq += *first1 + *first2;
00220 first1++;
00221 first2++;
00222 }
00223 return dist_sq;
00224 }
00225
00226
00227
00228 template <typename Iterator1, typename Iterator2>
00229 double hellinger_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00230 {
00231 double distsq = acc;
00232 double diff0, diff1, diff2, diff3;
00233 Iterator1 lastgroup = last1 - 3;
00234
00235
00236 while (first1 < lastgroup) {
00237 diff0 = sqrt(first1[0]) - sqrt(first2[0]);
00238 diff1 = sqrt(first1[1]) - sqrt(first2[1]);
00239 diff2 = sqrt(first1[2]) - sqrt(first2[2]);
00240 diff3 = sqrt(first1[3]) - sqrt(first2[3]);
00241 distsq += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
00242 first1 += 4;
00243 first2 += 4;
00244 }
00245
00246 while (first1 < last1) {
00247 diff0 = sqrt(*first1++) - sqrt(*first2++);
00248 distsq += diff0 * diff0;
00249 }
00250 return distsq;
00251 }
00252
00253
00254
00255 template <typename Iterator1, typename Iterator2>
00256 double chi_square_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00257 {
00258 double dist = acc;
00259
00260 while (first1 < last1) {
00261 double sum = *first1 + *first2;
00262 if (sum > 0) {
00263 double diff = *first1 - *first2;
00264 dist += diff * diff / sum;
00265 }
00266 first1++;
00267 first2++;
00268 }
00269 return dist;
00270 }
00271
00272
00273
00274 template <typename Iterator1, typename Iterator2>
00275 double kl_divergence(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00276 {
00277 double div = acc;
00278
00279 while (first1 < last1) {
00280 if (*first2 != 0) {
00281 double ratio = *first1 / *first2;
00282 if (ratio > 0) {
00283 div += *first1 * log(ratio);
00284 }
00285 }
00286 first1++;
00287 first2++;
00288 }
00289 return div;
00290 }
00291
00292
00293
00294
00295 CV_EXPORTS flann_distance_t flann_distance_type();
00303 template <typename Iterator1, typename Iterator2>
00304 double custom_dist(Iterator1 first1, Iterator1 last1, Iterator2 first2, double acc = 0)
00305 {
00306 switch (flann_distance_type()) {
00307 case FLANN_DIST_EUCLIDEAN:
00308 return euclidean_dist(first1, last1, first2, acc);
00309 case FLANN_DIST_MANHATTAN:
00310 return manhattan_dist(first1, last1, first2, acc);
00311 case FLANN_DIST_MINKOWSKI:
00312 return minkowski_dist(first1, last1, first2, acc);
00313 case FLANN_DIST_MAX:
00314 return max_dist(first1, last1, first2, acc);
00315 case FLANN_DIST_HIST_INTERSECT:
00316 return hist_intersection_dist_sq(first1, last1, first2, acc);
00317 case FLANN_DIST_HELLINGER:
00318 return hellinger_dist(first1, last1, first2, acc);
00319 case FLANN_DIST_CS:
00320 return chi_square_dist(first1, last1, first2, acc);
00321 case FLANN_DIST_KL:
00322 return kl_divergence(first1, last1, first2, acc);
00323 default:
00324 return euclidean_dist(first1, last1, first2, acc);
00325 }
00326 }
00327
00328
00329
00330
00331
00332
00333
00334
00335 template <typename T>
00336 struct ZeroIterator {
00337
00338 T operator*() {
00339 return 0;
00340 }
00341
00342 T operator[](int) {
00343 return 0;
00344 }
00345
00346 ZeroIterator<T>& operator ++(int) {
00347 return *this;
00348 }
00349
00350 ZeroIterator<T>& operator+=(int) {
00351 return *this;
00352 }
00353
00354 };
00355
00356 CV_EXPORTS ZeroIterator<float>& zero();
00357
00358 }
00359
00360 #endif //_OPENCV_DIST_H_