EstervQrCode 1.1.1
Library for qr code manipulation
index_testing.h
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  *
7  * THE BSD LICENSE
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *************************************************************************/
30 
31 #ifndef OPENCV_FLANN_INDEX_TESTING_H_
32 #define OPENCV_FLANN_INDEX_TESTING_H_
33 
35 
36 #include <cstring>
37 #include <cmath>
38 
39 #include "matrix.h"
40 #include "nn_index.h"
41 #include "result_set.h"
42 #include "logger.h"
43 #include "timer.h"
44 
45 
46 namespace cvflann
47 {
48 
49 inline int countCorrectMatches(int* neighbors, int* groundTruth, int n)
50 {
51  int count = 0;
52  for (int i=0; i<n; ++i) {
53  for (int k=0; k<n; ++k) {
54  if (neighbors[i]==groundTruth[k]) {
55  count++;
56  break;
57  }
58  }
59  }
60  return count;
61 }
62 
63 
64 template <typename Distance>
65 typename Distance::ResultType computeDistanceRaport(const Matrix<typename Distance::ElementType>& inputData, typename Distance::ElementType* target,
66  int* neighbors, int* groundTruth, int veclen, int n, const Distance& distance)
67 {
68  typedef typename Distance::ResultType DistanceType;
69 
70  DistanceType ret = 0;
71  for (int i=0; i<n; ++i) {
72  DistanceType den = distance(inputData[groundTruth[i]], target, veclen);
73  DistanceType num = distance(inputData[neighbors[i]], target, veclen);
74 
75  if ((den==0)&&(num==0)) {
76  ret += 1;
77  }
78  else {
79  ret += num/den;
80  }
81  }
82 
83  return ret;
84 }
85 
86 template <typename Distance>
87 float search_with_ground_truth(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
88  const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, int nn, int checks,
89  float& time, typename Distance::ResultType& dist, const Distance& distance, int skipMatches)
90 {
91  typedef typename Distance::ResultType DistanceType;
92 
93  if (matches.cols<size_t(nn)) {
94  Logger::info("matches.cols=%d, nn=%d\n",matches.cols,nn);
95 
96  FLANN_THROW(cv::Error::StsError, "Ground truth is not computed for as many neighbors as requested");
97  }
98 
99  KNNResultSet<DistanceType> resultSet(nn+skipMatches);
100  SearchParams searchParams(checks);
101 
102  std::vector<int> indices(nn+skipMatches);
103  std::vector<DistanceType> dists(nn+skipMatches);
104  int* neighbors = &indices[skipMatches];
105 
106  int correct = 0;
107  DistanceType distR = 0;
108  StartStopTimer t;
109  int repeats = 0;
110  while (t.value<0.2) {
111  repeats++;
112  t.start();
113  correct = 0;
114  distR = 0;
115  for (size_t i = 0; i < testData.rows; i++) {
116  resultSet.init(&indices[0], &dists[0]);
117  index.findNeighbors(resultSet, testData[i], searchParams);
118 
119  correct += countCorrectMatches(neighbors,matches[i], nn);
120  distR += computeDistanceRaport<Distance>(inputData, testData[i], neighbors, matches[i], (int)testData.cols, nn, distance);
121  }
122  t.stop();
123  }
124  time = float(t.value/repeats);
125 
126  float precicion = (float)correct/(nn*testData.rows);
127 
128  dist = distR/(testData.rows*nn);
129 
130  Logger::info("%8d %10.4g %10.5g %10.5g %10.5g\n",
131  checks, precicion, time, 1000.0 * time / testData.rows, dist);
132 
133  return precicion;
134 }
135 
136 
137 template <typename Distance>
138 float test_index_checks(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
139  const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
140  int checks, float& precision, const Distance& distance, int nn = 1, int skipMatches = 0)
141 {
142  typedef typename Distance::ResultType DistanceType;
143 
144  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
145  Logger::info("---------------------------------------------------------\n");
146 
147  float time = 0;
148  DistanceType dist = 0;
149  precision = search_with_ground_truth(index, inputData, testData, matches, nn, checks, time, dist, distance, skipMatches);
150 
151  return time;
152 }
153 
154 template <typename Distance>
155 float test_index_precision(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
156  const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
157  float precision, int& checks, const Distance& distance, int nn = 1, int skipMatches = 0)
158 {
159  typedef typename Distance::ResultType DistanceType;
160  const float SEARCH_EPS = 0.001f;
161 
162  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
163  Logger::info("---------------------------------------------------------\n");
164 
165  int c2 = 1;
166  float p2;
167  int c1 = 1;
168  //float p1;
169  float time;
170  DistanceType dist;
171 
172  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
173 
174  if (p2>precision) {
175  Logger::info("Got as close as I can\n");
176  checks = c2;
177  return time;
178  }
179 
180  while (p2<precision) {
181  c1 = c2;
182  //p1 = p2;
183  c2 *=2;
184  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
185  }
186 
187  int cx;
188  float realPrecision;
189  if (fabs(p2-precision)>SEARCH_EPS) {
190  Logger::info("Start linear estimation\n");
191  // after we got to values in the vecinity of the desired precision
192  // use linear approximation get a better estimation
193 
194  cx = (c1+c2)/2;
195  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
196  while (fabs(realPrecision-precision)>SEARCH_EPS) {
197 
198  if (realPrecision<precision) {
199  c1 = cx;
200  }
201  else {
202  c2 = cx;
203  }
204  cx = (c1+c2)/2;
205  if (cx==c1) {
206  Logger::info("Got as close as I can\n");
207  break;
208  }
209  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
210  }
211 
212  c2 = cx;
213  p2 = realPrecision;
214 
215  }
216  else {
217  Logger::info("No need for linear estimation\n");
218  cx = c2;
219  realPrecision = p2;
220  }
221 
222  checks = cx;
223  return time;
224 }
225 
226 
227 template <typename Distance>
228 void test_index_precisions(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData,
229  const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
230  float* precisions, int precisions_length, const Distance& distance, int nn = 1, int skipMatches = 0, float maxTime = 0)
231 {
232  typedef typename Distance::ResultType DistanceType;
233 
234  const float SEARCH_EPS = 0.001;
235 
236  // make sure precisions array is sorted
237  std::sort(precisions, precisions+precisions_length);
238 
239  int pindex = 0;
240  float precision = precisions[pindex];
241 
242  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
243  Logger::info("---------------------------------------------------------\n");
244 
245  int c2 = 1;
246  float p2;
247 
248  int c1 = 1;
249 
250  float time;
251  DistanceType dist;
252 
253  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
254 
255  // if precision for 1 run down the tree is already
256  // better then some of the requested precisions, then
257  // skip those
258  while (precisions[pindex]<p2 && pindex<precisions_length) {
259  pindex++;
260  }
261 
262  if (pindex==precisions_length) {
263  Logger::info("Got as close as I can\n");
264  return;
265  }
266 
267  for (int i=pindex; i<precisions_length; ++i) {
268 
269  precision = precisions[i];
270  while (p2<precision) {
271  c1 = c2;
272  c2 *=2;
273  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
274  if ((maxTime> 0)&&(time > maxTime)&&(p2<precision)) return;
275  }
276 
277  int cx;
278  float realPrecision;
279  if (fabs(p2-precision)>SEARCH_EPS) {
280  Logger::info("Start linear estimation\n");
281  // after we got to values in the vecinity of the desired precision
282  // use linear approximation get a better estimation
283 
284  cx = (c1+c2)/2;
285  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
286  while (fabs(realPrecision-precision)>SEARCH_EPS) {
287 
288  if (realPrecision<precision) {
289  c1 = cx;
290  }
291  else {
292  c2 = cx;
293  }
294  cx = (c1+c2)/2;
295  if (cx==c1) {
296  Logger::info("Got as close as I can\n");
297  break;
298  }
299  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
300  }
301 
302  c2 = cx;
303  p2 = realPrecision;
304 
305  }
306  else {
307  Logger::info("No need for linear estimation\n");
308  cx = c2;
309  realPrecision = p2;
310  }
311 
312  }
313 }
314 
315 }
316 
318 
319 #endif //OPENCV_FLANN_INDEX_TESTING_H_
std::distance
T distance(T... args)
std::fabs
T fabs(T... args)
index
int index
Definition: core_c.h:634
count
int count
Definition: core_c.h:1413
cv::k
CV_EXPORTS OutputArray int double double InputArray OutputArray int int bool double k
Definition: imgproc.hpp:2133
cv::Error::StsError
@ StsError
unknown /unspecified error
Definition: base.hpp:71
cvflann
Definition: flann.hpp:60
std::sort
T sort(T... args)
std::time
T time(T... args)