index_testing.h

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_FLANN_INDEX_TESTING_H_
00032 #define OPENCV_FLANN_INDEX_TESTING_H_
00033 
00034 #include <cstring>
00035 #include <cassert>
00036 #include <cmath>
00037 
00038 #include "matrix.h"
00039 #include "nn_index.h"
00040 #include "result_set.h"
00041 #include "logger.h"
00042 #include "timer.h"
00043 
00044 
00045 namespace cvflann
00046 {
00047 
00048 inline int countCorrectMatches(int* neighbors, int* groundTruth, int n)
00049 {
00050     int count = 0;
00051     for (int i=0; i<n; ++i) {
00052         for (int k=0; k<n; ++k) {
00053             if (neighbors[i]==groundTruth[k]) {
00054                 count++;
00055                 break;
00056             }
00057         }
00058     }
00059     return count;
00060 }
00061 
00062 
00063 template <typename Distance>
00064 typename Distance::ResultType computeDistanceRaport(const Matrix<typename Distance::ElementType>& inputData, typename Distance::ElementType* target,
00065                                                     int* neighbors, int* groundTruth, int veclen, int n, const Distance& distance)
00066 {
00067     typedef typename Distance::ResultType DistanceType;
00068 
00069     DistanceType ret = 0;
00070     for (int i=0; i<n; ++i) {
00071         DistanceType den = distance(inputData[groundTruth[i]], target, veclen);
00072         DistanceType num = distance(inputData[neighbors[i]], target, veclen);
00073 
00074         if ((den==0)&&(num==0)) {
00075             ret += 1;
00076         }
00077         else {
00078             ret += num/den;
00079         }
00080     }
00081 
00082     return ret;
00083 }
00084 
00085 template <typename Distance>
00086 float search_with_ground_truth(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
00087                                const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, int nn, int checks,
00088                                float& time, typename Distance::ResultType& dist, const Distance& distance, int skipMatches)
00089 {
00090     typedef typename Distance::ResultType DistanceType;
00091 
00092     if (matches.cols<size_t(nn)) {
00093         Logger::info("matches.cols=%d, nn=%d\n",matches.cols,nn);
00094 
00095         throw FLANNException("Ground truth is not computed for as many neighbors as requested");
00096     }
00097 
00098     KNNResultSet<DistanceType> resultSet(nn+skipMatches);
00099     SearchParams searchParams(checks);
00100 
00101     std::vector<int> indices(nn+skipMatches);
00102     std::vector<DistanceType> dists(nn+skipMatches);
00103     int* neighbors = &indices[skipMatches];
00104 
00105     int correct = 0;
00106     DistanceType distR = 0;
00107     StartStopTimer t;
00108     int repeats = 0;
00109     while (t.value<0.2) {
00110         repeats++;
00111         t.start();
00112         correct = 0;
00113         distR = 0;
00114         for (size_t i = 0; i < testData.rows; i++) {
00115             resultSet.init(&indices[0], &dists[0]);
00116             index.findNeighbors(resultSet, testData[i], searchParams);
00117 
00118             correct += countCorrectMatches(neighbors,matches[i], nn);
00119             distR += computeDistanceRaport<Distance>(inputData, testData[i], neighbors, matches[i], (int)testData.cols, nn, distance);
00120         }
00121         t.stop();
00122     }
00123     time = float(t.value/repeats);
00124 
00125     float precicion = (float)correct/(nn*testData.rows);
00126 
00127     dist = distR/(testData.rows*nn);
00128 
00129     Logger::info("%8d %10.4g %10.5g %10.5g %10.5g\n",
00130                  checks, precicion, time, 1000.0 * time / testData.rows, dist);
00131 
00132     return precicion;
00133 }
00134 
00135 
00136 template <typename Distance>
00137 float test_index_checks(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
00138                         const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
00139                         int checks, float& precision, const Distance& distance, int nn = 1, int skipMatches = 0)
00140 {
00141     typedef typename Distance::ResultType DistanceType;
00142 
00143     Logger::info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist\n");
00144     Logger::info("---------------------------------------------------------\n");
00145 
00146     float time = 0;
00147     DistanceType dist = 0;
00148     precision = search_with_ground_truth(index, inputData, testData, matches, nn, checks, time, dist, distance, skipMatches);
00149 
00150     return time;
00151 }
00152 
00153 template <typename Distance>
00154 float test_index_precision(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
00155                            const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
00156                            float precision, int& checks, const Distance& distance, int nn = 1, int skipMatches = 0)
00157 {
00158     typedef typename Distance::ResultType DistanceType;
00159     const float SEARCH_EPS = 0.001f;
00160 
00161     Logger::info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist\n");
00162     Logger::info("---------------------------------------------------------\n");
00163 
00164     int c2 = 1;
00165     float p2;
00166     int c1 = 1;
00167     //float p1;
00168     float time;
00169     DistanceType dist;
00170 
00171     p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
00172 
00173     if (p2>precision) {
00174         Logger::info("Got as close as I can\n");
00175         checks = c2;
00176         return time;
00177     }
00178 
00179     while (p2<precision) {
00180         c1 = c2;
00181         //p1 = p2;
00182         c2 *=2;
00183         p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
00184     }
00185 
00186     int cx;
00187     float realPrecision;
00188     if (fabs(p2-precision)>SEARCH_EPS) {
00189         Logger::info("Start linear estimation\n");
00190         // after we got to values in the vecinity of the desired precision
00191         // use linear approximation get a better estimation
00192 
00193         cx = (c1+c2)/2;
00194         realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
00195         while (fabs(realPrecision-precision)>SEARCH_EPS) {
00196 
00197             if (realPrecision<precision) {
00198                 c1 = cx;
00199             }
00200             else {
00201                 c2 = cx;
00202             }
00203             cx = (c1+c2)/2;
00204             if (cx==c1) {
00205                 Logger::info("Got as close as I can\n");
00206                 break;
00207             }
00208             realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
00209         }
00210 
00211         c2 = cx;
00212         p2 = realPrecision;
00213 
00214     }
00215     else {
00216         Logger::info("No need for linear estimation\n");
00217         cx = c2;
00218         realPrecision = p2;
00219     }
00220 
00221     checks = cx;
00222     return time;
00223 }
00224 
00225 
00226 template <typename Distance>
00227 void test_index_precisions(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
00228                            const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
00229                            float* precisions, int precisions_length, const Distance& distance, int nn = 1, int skipMatches = 0, float maxTime = 0)
00230 {
00231     typedef typename Distance::ResultType DistanceType;
00232 
00233     const float SEARCH_EPS = 0.001;
00234 
00235     // make sure precisions array is sorted
00236     std::sort(precisions, precisions+precisions_length);
00237 
00238     int pindex = 0;
00239     float precision = precisions[pindex];
00240 
00241     Logger::info("  Nodes  Precision(%)   Time(s)   Time/vec(ms)  Mean dist\n");
00242     Logger::info("---------------------------------------------------------\n");
00243 
00244     int c2 = 1;
00245     float p2;
00246 
00247     int c1 = 1;
00248     float p1;
00249 
00250     float time;
00251     DistanceType dist;
00252 
00253     p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
00254 
00255     // if precision for 1 run down the tree is already
00256     // better then some of the requested precisions, then
00257     // skip those
00258     while (precisions[pindex]<p2 && pindex<precisions_length) {
00259         pindex++;
00260     }
00261 
00262     if (pindex==precisions_length) {
00263         Logger::info("Got as close as I can\n");
00264         return;
00265     }
00266 
00267     for (int i=pindex; i<precisions_length; ++i) {
00268 
00269         precision = precisions[i];
00270         while (p2<precision) {
00271             c1 = c2;
00272             p1 = p2;
00273             c2 *=2;
00274             p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
00275             if ((maxTime> 0)&&(time > maxTime)&&(p2<precision)) return;
00276         }
00277 
00278         int cx;
00279         float realPrecision;
00280         if (fabs(p2-precision)>SEARCH_EPS) {
00281             Logger::info("Start linear estimation\n");
00282             // after we got to values in the vecinity of the desired precision
00283             // use linear approximation get a better estimation
00284 
00285             cx = (c1+c2)/2;
00286             realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
00287             while (fabs(realPrecision-precision)>SEARCH_EPS) {
00288 
00289                 if (realPrecision<precision) {
00290                     c1 = cx;
00291                 }
00292                 else {
00293                     c2 = cx;
00294                 }
00295                 cx = (c1+c2)/2;
00296                 if (cx==c1) {
00297                     Logger::info("Got as close as I can\n");
00298                     break;
00299                 }
00300                 realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
00301             }
00302 
00303             c2 = cx;
00304             p2 = realPrecision;
00305 
00306         }
00307         else {
00308             Logger::info("No need for linear estimation\n");
00309             cx = c2;
00310             realPrecision = p2;
00311         }
00312 
00313     }
00314 }
00315 
00316 }
00317 
00318 #endif //OPENCV_FLANN_INDEX_TESTING_H_