Cinder

  • Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

include/opencv2/flann/index_testing.h

Go to the documentation of this file.
00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *************************************************************************/
00030 
00031 #ifndef _OPENCV_TESTING_H_
00032 #define _OPENCV_TESTING_H_
00033 
00034 #include <cstring>
00035 #include <cassert>
00036 
00037 #include "opencv2/flann/matrix.h"
00038 #include "opencv2/flann/nn_index.h"
00039 #include "opencv2/flann/result_set.h"
00040 #include "opencv2/flann/logger.h"
00041 #include "opencv2/flann/timer.h"
00042 
00043 
00044 
00045 namespace cvflann
00046 {
00047 
00048 CV_EXPORTS int countCorrectMatches(int* neighbors, int* groundTruth, int n);
00049 
00050 
00051 template <typename ELEM_TYPE>
00052 float computeDistanceRaport(const Matrix<ELEM_TYPE>& inputData, ELEM_TYPE* target, int* neighbors, int* groundTruth, int veclen, int n)
00053 {
00054     ELEM_TYPE* target_end = target + veclen;
00055     float ret = 0;
00056     for (int i=0;i<n;++i) {
00057         float den = (float)flann_dist(target,target_end, inputData[groundTruth[i]]);
00058         float num = (float)flann_dist(target,target_end, inputData[neighbors[i]]);
00059 
00060         if (den==0 && num==0) {
00061             ret += 1;
00062         }
00063         else {
00064             ret += num/den;
00065         }
00066     }
00067 
00068     return ret;
00069 }
00070 
00071 template <typename ELEM_TYPE>
00072 float search_with_ground_truth(NNIndex<ELEM_TYPE>& index, const Matrix<ELEM_TYPE>& inputData, const Matrix<ELEM_TYPE>& testData, const Matrix<int>& matches, int nn, int checks, float& time, float& dist, int skipMatches)
00073 {
00074     if (matches.cols<size_t(nn)) {
00075         logger().info("matches.cols=%d, nn=%d\n",matches.cols,nn);
00076 
00077         throw FLANNException("Ground truth is not computed for as many neighbors as requested");
00078     }
00079 
00080     KNNResultSet<ELEM_TYPE> resultSet(nn+skipMatches);
00081     SearchParams searchParams(checks);
00082 
00083     int correct = 0;
00084     float distR = 0;
00085     StartStopTimer t;
00086     int repeats = 0;
00087     while (t.value<0.2) {
00088         repeats++;
00089         t.start();
00090         correct = 0;
00091         distR = 0;
00092         for (size_t i = 0; i < testData.rows; i++) {
00093             ELEM_TYPE* target = testData[i];
00094             resultSet.init(target, (int)testData.cols);
00095             index.findNeighbors(resultSet,target, searchParams);
00096             int* neighbors = resultSet.getNeighbors();
00097             neighbors = neighbors+skipMatches;
00098 
00099             correct += countCorrectMatches(neighbors,matches[i], nn);
00100             distR += computeDistanceRaport(inputData, target,neighbors,matches[i], (int)testData.cols, nn);
00101         }
00102         t.stop();
00103     }
00104     time = (float)(t.value/repeats);
00105 
00106 
00107     float precicion = (float)correct/(nn*testData.rows);
00108 
00109     dist = distR/(testData.rows*nn);
00110 
00111     logger().info("%8d %10.4g %10.5g %10.5g %10.5g\n",
00112             checks, precicion, time, 1000.0 * time / testData.rows, dist);
00113 
00114     return precicion;
00115 }
00116 
00117 
00118 template <typename ELEM_TYPE>
00119 float test_index_checks(NNIndex<ELEM_TYPE>& index, const Matrix<ELEM_TYPE>& inputData, const Matrix<ELEM_TYPE>& testData, const Matrix<int>& matches,
00120             int checks, float& precision, int nn = 1, int skipMatches = 0)
00121 {
00122     logger().info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist\n");
00123     logger().info("---------------------------------------------------------\n");
00124 
00125     float time = 0;
00126     float dist = 0;
00127     precision = search_with_ground_truth(index, inputData, testData, matches, nn, checks, time, dist, skipMatches);
00128 
00129     return time;
00130 }
00131 
00132 template <typename ELEM_TYPE>
00133 float test_index_precision(NNIndex<ELEM_TYPE>& index, const Matrix<ELEM_TYPE>& inputData, const Matrix<ELEM_TYPE>& testData, const Matrix<int>& matches,
00134              float precision, int& checks, int nn = 1, int skipMatches = 0)
00135 {
00136     const float SEARCH_EPS = 0.001f;
00137 
00138     logger().info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist\n");
00139     logger().info("---------------------------------------------------------\n");
00140 
00141     int c2 = 1;
00142     float p2;
00143     int c1 = 1;
00144     float p1;
00145     float time;
00146     float dist;
00147 
00148     p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, skipMatches);
00149 
00150     if (p2>precision) {
00151         logger().info("Got as close as I can\n");
00152         checks = c2;
00153         return time;
00154     }
00155 
00156     while (p2<precision) {
00157         c1 = c2;
00158         p1 = p2;
00159         c2 *=2;
00160         p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, skipMatches);
00161     }
00162 
00163     int cx;
00164     float realPrecision;
00165     if (fabs(p2-precision)>SEARCH_EPS) {
00166         logger().info("Start linear estimation\n");
00167         // after we got to values in the vecinity of the desired precision
00168         // use linear approximation get a better estimation
00169 
00170         cx = (c1+c2)/2;
00171         realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, skipMatches);
00172         while (fabs(realPrecision-precision)>SEARCH_EPS) {
00173 
00174             if (realPrecision<precision) {
00175                 c1 = cx;
00176             }
00177             else {
00178                 c2 = cx;
00179             }
00180             cx = (c1+c2)/2;
00181             if (cx==c1) {
00182                 logger().info("Got as close as I can\n");
00183                 break;
00184             }
00185             realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, skipMatches);
00186         }
00187 
00188         c2 = cx;
00189         p2 = realPrecision;
00190 
00191     } else {
00192         logger().info("No need for linear estimation\n");
00193         cx = c2;
00194         realPrecision = p2;
00195     }
00196 
00197     checks = cx;
00198     return time;
00199 }
00200 
00201 
00202 template <typename ELEM_TYPE>
00203 float test_index_precisions(NNIndex<ELEM_TYPE>& index, const Matrix<ELEM_TYPE>& inputData, const Matrix<ELEM_TYPE>& testData, const Matrix<int>& matches,
00204                     float* precisions, int precisions_length, int nn = 1, int skipMatches = 0, float maxTime = 0)
00205 {
00206     const float SEARCH_EPS = 0.001;
00207 
00208     // make sure precisions array is sorted
00209     std::sort(precisions, precisions+precisions_length);
00210 
00211     int pindex = 0;
00212     float precision = precisions[pindex];
00213 
00214     logger().info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist");
00215     logger().info("---------------------------------------------------------");
00216 
00217     int c2 = 1;
00218     float p2;
00219 
00220     int c1 = 1;
00221     float p1;
00222 
00223     float time;
00224     float dist;
00225 
00226     p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, skipMatches);
00227 
00228     // if precision for 1 run down the tree is already
00229     // better then some of the requested precisions, then
00230     // skip those
00231     while (precisions[pindex]<p2 && pindex<precisions_length) {
00232         pindex++;
00233     }
00234 
00235     if (pindex==precisions_length) {
00236         logger().info("Got as close as I can\n");
00237         return time;
00238     }
00239 
00240     for (int i=pindex;i<precisions_length;++i) {
00241 
00242         precision = precisions[i];
00243         while (p2<precision) {
00244             c1 = c2;
00245             p1 = p2;
00246             c2 *=2;
00247             p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, skipMatches);
00248             if (maxTime> 0 && time > maxTime && p2<precision) return time;
00249         }
00250 
00251         int cx;
00252         float realPrecision;
00253         if (fabs(p2-precision)>SEARCH_EPS) {
00254             logger().info("Start linear estimation\n");
00255             // after we got to values in the vecinity of the desired precision
00256             // use linear approximation get a better estimation
00257 
00258             cx = (c1+c2)/2;
00259             realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, skipMatches);
00260             while (fabs(realPrecision-precision)>SEARCH_EPS) {
00261 
00262                 if (realPrecision<precision) {
00263                     c1 = cx;
00264                 }
00265                 else {
00266                     c2 = cx;
00267                 }
00268                 cx = (c1+c2)/2;
00269                 if (cx==c1) {
00270                     logger().info("Got as close as I can\n");
00271                     break;
00272                 }
00273                 realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, skipMatches);
00274             }
00275 
00276             c2 = cx;
00277             p2 = realPrecision;
00278 
00279         } else {
00280             logger().info("No need for linear estimation\n");
00281             cx = c2;
00282             realPrecision = p2;
00283         }
00284 
00285     }
00286     return time;
00287 }
00288 
00289 } // namespace cvflann
00290 
00291 #endif //_OPENCV_TESTING_H_