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_