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_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
00168
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
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
00229
00230
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
00256
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 }
00290
00291 #endif //_OPENCV_TESTING_H_