index_testing.h
Go to the documentation of this file.
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 RTABMAP_FLANN_INDEX_TESTING_H_
32 #define RTABMAP_FLANN_INDEX_TESTING_H_
33 
34 #include <cstring>
35 #include <cassert>
36 #include <cmath>
37 
38 #include "rtflann/util/matrix.h"
41 #include "rtflann/util/logger.h"
42 #include "rtflann/util/timer.h"
43 
44 
45 namespace rtflann
46 {
47 
48 inline int countCorrectMatches(size_t* neighbors, size_t* groundTruth, int n)
49 {
50  int count = 0;
51  for (int i=0; i<n; ++i) {
52  for (int k=0; k<n; ++k) {
53  if (neighbors[i]==groundTruth[k]) {
54  count++;
55  break;
56  }
57  }
58  }
59  return count;
60 }
61 
62 
63 template <typename Distance>
64 typename Distance::ResultType computeDistanceRaport(const Matrix<typename Distance::ElementType>& inputData, typename Distance::ElementType* target,
65  size_t* neighbors, size_t* groundTruth, int veclen, int n, const Distance& distance)
66 {
67  typedef typename Distance::ResultType DistanceType;
68 
69  DistanceType ret = 0;
70  for (int i=0; i<n; ++i) {
71  DistanceType den = distance(inputData[groundTruth[i]], target, veclen);
72  DistanceType num = distance(inputData[neighbors[i]], target, veclen);
73 
74  if ((den==0)&&(num==0)) {
75  ret += 1;
76  }
77  else {
78  ret += num/den;
79  }
80  }
81 
82  return ret;
83 }
84 
85 template <typename Index, typename Distance>
87  const Matrix<typename Distance::ElementType>& testData, const Matrix<size_t>& matches, int nn, int checks,
88  float& time, typename Distance::ResultType& dist, const Distance& distance, int skipMatches)
89 {
90  typedef typename Distance::ElementType ElementType;
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  throw FLANNException("Ground truth is not computed for as many neighbors as requested");
96  }
97 
98  SearchParams searchParams(checks);
99 
100  size_t* indices = new size_t[nn+skipMatches];
101  DistanceType* dists = new DistanceType[nn+skipMatches];
102 
103  Matrix<size_t> indices_mat(indices, 1, nn+skipMatches);
104  Matrix<DistanceType> dists_mat(dists, 1, nn+skipMatches);
105 
106  size_t* neighbors = indices + skipMatches;
107 
108  int correct = 0;
109  DistanceType distR = 0;
110  StartStopTimer t;
111  int repeats = 0;
112  while (t.value<0.2) {
113  repeats++;
114  t.start();
115  correct = 0;
116  distR = 0;
117  for (size_t i = 0; i < testData.rows; i++) {
118  index.knnSearch(Matrix<ElementType>(testData[i], 1, testData.cols), indices_mat, dists_mat, nn+skipMatches, searchParams);
119 
120  correct += countCorrectMatches(neighbors,matches[i], nn);
121  distR += computeDistanceRaport<Distance>(inputData, testData[i], neighbors, matches[i], testData.cols, nn, distance);
122  }
123  t.stop();
124  }
125  time = float(t.value/repeats);
126 
127  delete[] indices;
128  delete[] dists;
129 
130  float precicion = (float)correct/(nn*testData.rows);
131 
132  dist = distR/(testData.rows*nn);
133 
134  Logger::info("%8d %10.4g %10.5g %10.5g %10.5g\n",
135  checks, precicion, time, 1000.0 * time / testData.rows, dist);
136 
137  return precicion;
138 }
139 
140 
141 template <typename Index, typename Distance>
143  const Matrix<typename Distance::ElementType>& testData, const Matrix<size_t>& matches,
144  int checks, float& precision, const Distance& distance, int nn = 1, int skipMatches = 0)
145 {
146  typedef typename Distance::ResultType DistanceType;
147 
148  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
149  Logger::info("---------------------------------------------------------\n");
150 
151  float time = 0;
152  DistanceType dist = 0;
153  precision = search_with_ground_truth(index, inputData, testData, matches, nn, checks, time, dist, distance, skipMatches);
154 
155  return time;
156 }
157 
158 template <typename Index, typename Distance>
160  const Matrix<typename Distance::ElementType>& testData, const Matrix<size_t>& matches,
161  float precision, int& checks, const Distance& distance, int nn = 1, int skipMatches = 0)
162 {
163  typedef typename Distance::ResultType DistanceType;
164  const float SEARCH_EPS = 0.001f;
165 
166  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
167  Logger::info("---------------------------------------------------------\n");
168 
169  int c2 = 1;
170  float p2;
171  int c1 = 1;
172 // float p1;
173  float time;
174  DistanceType dist;
175 
176  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
177 
178  if (p2>precision) {
179  Logger::info("Got as close as I can\n");
180  checks = c2;
181  return time;
182  }
183 
184  while (p2<precision) {
185  c1 = c2;
186 // p1 = p2;
187  c2 *=2;
188  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
189  }
190 
191  int cx;
192  float realPrecision;
193  if (fabs(p2-precision)>SEARCH_EPS) {
194  Logger::info("Start linear estimation\n");
195  // after we got to values in the vecinity of the desired precision
196  // use linear approximation get a better estimation
197 
198  cx = (c1+c2)/2;
199  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
200  while (fabs(realPrecision-precision)>SEARCH_EPS) {
201 
202  if (realPrecision<precision) {
203  c1 = cx;
204  }
205  else {
206  c2 = cx;
207  }
208  cx = (c1+c2)/2;
209  if (cx==c1) {
210  Logger::info("Got as close as I can\n");
211  break;
212  }
213  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
214  }
215 
216  c2 = cx;
217  p2 = realPrecision;
218 
219  }
220  else {
221  Logger::info("No need for linear estimation\n");
222  cx = c2;
223  realPrecision = p2;
224  }
225 
226  checks = cx;
227  return time;
228 }
229 
230 
231 template <typename Index, typename Distance>
233  const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches,
234  float* precisions, int precisions_length, const Distance& distance, int nn = 1, int skipMatches = 0, float maxTime = 0)
235 {
236  typedef typename Distance::ResultType DistanceType;
237 
238  const float SEARCH_EPS = 0.001;
239 
240  // make sure precisions array is sorted
241  std::sort(precisions, precisions+precisions_length);
242 
243  int pindex = 0;
244  float precision = precisions[pindex];
245 
246  Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n");
247  Logger::info("---------------------------------------------------------\n");
248 
249  int c2 = 1;
250  float p2;
251 
252  int c1 = 1;
253  float p1;
254 
255  float time;
256  DistanceType dist;
257 
258  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
259 
260  // if precision for 1 run down the tree is already
261  // better then some of the requested precisions, then
262  // skip those
263  while (precisions[pindex]<p2 && pindex<precisions_length) {
264  pindex++;
265  }
266 
267  if (pindex==precisions_length) {
268  Logger::info("Got as close as I can\n");
269  return;
270  }
271 
272  for (int i=pindex; i<precisions_length; ++i) {
273 
274  precision = precisions[i];
275  while (p2<precision) {
276  c1 = c2;
277  p1 = p2;
278  c2 *=2;
279  p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
280  if ((maxTime> 0)&&(time > maxTime)&&(p2<precision)) return;
281  }
282 
283  int cx;
284  float realPrecision;
285  if (fabs(p2-precision)>SEARCH_EPS) {
286  Logger::info("Start linear estimation\n");
287  // after we got to values in the vecinity of the desired precision
288  // use linear approximation get a better estimation
289 
290  cx = (c1+c2)/2;
291  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
292  while (fabs(realPrecision-precision)>SEARCH_EPS) {
293 
294  if (realPrecision<precision) {
295  c1 = cx;
296  }
297  else {
298  c2 = cx;
299  }
300  cx = (c1+c2)/2;
301  if (cx==c1) {
302  Logger::info("Got as close as I can\n");
303  break;
304  }
305  realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
306  }
307 
308  c2 = cx;
309  p2 = realPrecision;
310 
311  }
312  else {
313  Logger::info("No need for linear estimation\n");
314  cx = c2;
315  realPrecision = p2;
316  }
317 
318  }
319 }
320 
321 }
322 
323 #endif //FLANN_INDEX_TESTING_H_
float test_index_checks(Index &index, const Matrix< typename Distance::ElementType > &inputData, const Matrix< typename Distance::ElementType > &testData, const Matrix< size_t > &matches, int checks, float &precision, const Distance &distance, int nn=1, int skipMatches=0)
GLM_FUNC_DECL genType::value_type distance(genType const &p0, genType const &p1)
size_t rows
Definition: matrix.h:72
int countCorrectMatches(size_t *neighbors, size_t *groundTruth, int n)
Definition: index_testing.h:48
int knnSearch(const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
Perform k-nearest neighbor search.
Definition: flann.hpp:246
size_t cols
Definition: matrix.h:73
float test_index_precision(Index &index, const Matrix< typename Distance::ElementType > &inputData, const Matrix< typename Distance::ElementType > &testData, const Matrix< size_t > &matches, float precision, int &checks, const Distance &distance, int nn=1, int skipMatches=0)
float search_with_ground_truth(Index &index, const Matrix< typename Distance::ElementType > &inputData, const Matrix< typename Distance::ElementType > &testData, const Matrix< size_t > &matches, int nn, int checks, float &time, typename Distance::ResultType &dist, const Distance &distance, int skipMatches)
Definition: index_testing.h:86
precision
Definition: precision.hpp:33
Distance::ResultType computeDistanceRaport(const Matrix< typename Distance::ElementType > &inputData, typename Distance::ElementType *target, size_t *neighbors, size_t *groundTruth, int veclen, int n, const Distance &distance)
Definition: index_testing.h:64
const int c1
Definition: SuperPoint.cc:15
const int c2
Definition: SuperPoint.cc:16
void test_index_precisions(Index &index, const Matrix< typename Distance::ElementType > &inputData, const Matrix< typename Distance::ElementType > &testData, const Matrix< int > &matches, float *precisions, int precisions_length, const Distance &distance, int nn=1, int skipMatches=0, float maxTime=0)


rtabmap
Author(s): Mathieu Labbe
autogenerated on Mon Dec 14 2020 03:34:59