OpenCV 4.5.3(日本語機械翻訳)
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 float p1;
250
251 float time;
252 DistanceType dist;
253
254 p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
255
256 // if precision for 1 run down the tree is already
257 // better then some of the requested precisions, then
258 // skip those
259 while (precisions[pindex]<p2 && pindex<precisions_length) {
260 pindex++;
261 }
262
263 if (pindex==precisions_length) {
264 Logger::info("Got as close as I can\n");
265 return;
266 }
267
268 for (int i=pindex; i<precisions_length; ++i) {
269
270 precision = precisions[i];
271 while (p2<precision) {
272 c1 = c2;
273 p1 = p2;
274 c2 *=2;
275 p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches);
276 if ((maxTime> 0)&&(time > maxTime)&&(p2<precision)) return;
277 }
278
279 int cx;
280 float realPrecision;
281 if (fabs(p2-precision)>SEARCH_EPS) {
282 Logger::info("Start linear estimation\n");
283 // after we got to values in the vecinity of the desired precision
284 // use linear approximation get a better estimation
285
286 cx = (c1+c2)/2;
287 realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
288 while (fabs(realPrecision-precision)>SEARCH_EPS) {
289
290 if (realPrecision<precision) {
291 c1 = cx;
292 }
293 else {
294 c2 = cx;
295 }
296 cx = (c1+c2)/2;
297 if (cx==c1) {
298 Logger::info("Got as close as I can\n");
299 break;
300 }
301 realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches);
302 }
303
304 c2 = cx;
305 p2 = realPrecision;
306
307 }
308 else {
309 Logger::info("No need for linear estimation\n");
310 cx = c2;
311 realPrecision = p2;
312 }
313
314 }
315}
316
317}
318
320
321 #endif //OPENCV_FLANN_INDEX_TESTING_H_
cv::sort
CV_EXPORTS_W void sort(InputArray src, OutputArray dst, int flags)
Sorts each row or each column of a matrix.
構築: doxygen 1.9.2