1 /*M/////////////////////////////////////////////////////////////////////////////////////// 2 // 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4 // 5 // By downloading, copying, installing or using the software you agree to this license. 6 // If you do not agree to this license, do not download, install, 7 // copy or use the software. 8 // 9 // 10 // License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. 14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved. 15 // Copyright (C) 2014, Itseez Inc, all rights reserved. 16 // Third party copyrights are property of their respective owners. 17 // 18 // Redistribution and use in source and binary forms, with or without modification, 19 // are permitted provided that the following conditions are met: 20 // 21 // * Redistribution's of source code must retain the above copyright notice, 22 // this list of conditions and the following disclaimer. 23 // 24 // * Redistribution's in binary form must reproduce the above copyright notice, 25 // this list of conditions and the following disclaimer in the documentation 26 // and/or other materials provided with the distribution. 27 // 28 // * The name of the copyright holders may not be used to endorse or promote products 29 // derived from this software without specific prior written permission. 30 // 31 // This software is provided by the copyright holders and contributors "as is" and 32 // any express or implied warranties, including, but not limited to, the implied 33 // warranties of merchantability and fitness for a particular purpose are disclaimed. 34 // In no event shall the Intel Corporation or contributors be liable for any direct, 35 // indirect, incidental, special, exemplary, or consequential damages 36 // (including, but not limited to, procurement of substitute goods or services; 37 // loss of use, data, or profits; or business interruption) however caused 38 // and on any theory of liability, whether in contract, strict liability, 39 // or tort (including negligence or otherwise) arising in any way out of 40 // the use of this software, even if advised of the possibility of such damage. 41 // 42 //M*/ 43 44 #include "test_precomp.hpp" 45 46 #include <algorithm> 47 #include <vector> 48 #include <iostream> 49 50 using namespace std; 51 using namespace cv; 52 using namespace cv::flann; 53 54 //-------------------------------------------------------------------------------- 55 class NearestNeighborTest : public cvtest::BaseTest 56 { 57 public: 58 NearestNeighborTest() {} 59 protected: 60 static const int minValue = 0; 61 static const int maxValue = 1; 62 static const int dims = 30; 63 static const int featuresCount = 2000; 64 static const int K = 1; // * should also test 2nd nn etc.? 65 66 67 virtual void run( int start_from ); 68 virtual void createModel( const Mat& data ) = 0; 69 virtual int findNeighbors( Mat& points, Mat& neighbors ) = 0; 70 virtual int checkGetPoins( const Mat& data ); 71 virtual int checkFindBoxed(); 72 virtual int checkFind( const Mat& data ); 73 virtual void releaseModel() = 0; 74 }; 75 76 int NearestNeighborTest::checkGetPoins( const Mat& ) 77 { 78 return cvtest::TS::OK; 79 } 80 81 int NearestNeighborTest::checkFindBoxed() 82 { 83 return cvtest::TS::OK; 84 } 85 86 int NearestNeighborTest::checkFind( const Mat& data ) 87 { 88 int code = cvtest::TS::OK; 89 int pointsCount = 1000; 90 float noise = 0.2f; 91 92 RNG rng; 93 Mat points( pointsCount, dims, CV_32FC1 ); 94 Mat results( pointsCount, K, CV_32SC1 ); 95 96 std::vector<int> fmap( pointsCount ); 97 for( int pi = 0; pi < pointsCount; pi++ ) 98 { 99 int fi = rng.next() % featuresCount; 100 fmap[pi] = fi; 101 for( int d = 0; d < dims; d++ ) 102 points.at<float>(pi, d) = data.at<float>(fi, d) + rng.uniform(0.0f, 1.0f) * noise; 103 } 104 105 code = findNeighbors( points, results ); 106 107 if( code == cvtest::TS::OK ) 108 { 109 int correctMatches = 0; 110 for( int pi = 0; pi < pointsCount; pi++ ) 111 { 112 if( fmap[pi] == results.at<int>(pi, 0) ) 113 correctMatches++; 114 } 115 116 double correctPerc = correctMatches / (double)pointsCount; 117 if (correctPerc < .75) 118 { 119 ts->printf( cvtest::TS::LOG, "correct_perc = %d\n", correctPerc ); 120 code = cvtest::TS::FAIL_BAD_ACCURACY; 121 } 122 } 123 124 return code; 125 } 126 127 void NearestNeighborTest::run( int /*start_from*/ ) { 128 int code = cvtest::TS::OK, tempCode; 129 Mat desc( featuresCount, dims, CV_32FC1 ); 130 randu( desc, Scalar(minValue), Scalar(maxValue) ); 131 132 createModel( desc ); 133 134 tempCode = checkGetPoins( desc ); 135 if( tempCode != cvtest::TS::OK ) 136 { 137 ts->printf( cvtest::TS::LOG, "bad accuracy of GetPoints \n" ); 138 code = tempCode; 139 } 140 141 tempCode = checkFindBoxed(); 142 if( tempCode != cvtest::TS::OK ) 143 { 144 ts->printf( cvtest::TS::LOG, "bad accuracy of FindBoxed \n" ); 145 code = tempCode; 146 } 147 148 tempCode = checkFind( desc ); 149 if( tempCode != cvtest::TS::OK ) 150 { 151 ts->printf( cvtest::TS::LOG, "bad accuracy of Find \n" ); 152 code = tempCode; 153 } 154 155 releaseModel(); 156 157 ts->set_failed_test_info( code ); 158 } 159 160 //-------------------------------------------------------------------------------- 161 class CV_FlannTest : public NearestNeighborTest 162 { 163 public: 164 CV_FlannTest() {} 165 protected: 166 void createIndex( const Mat& data, const IndexParams& params ); 167 int knnSearch( Mat& points, Mat& neighbors ); 168 int radiusSearch( Mat& points, Mat& neighbors ); 169 virtual void releaseModel(); 170 Index* index; 171 }; 172 173 void CV_FlannTest::createIndex( const Mat& data, const IndexParams& params ) 174 { 175 index = new Index( data, params ); 176 } 177 178 int CV_FlannTest::knnSearch( Mat& points, Mat& neighbors ) 179 { 180 Mat dist( points.rows, neighbors.cols, CV_32FC1); 181 int knn = 1, j; 182 183 // 1st way 184 index->knnSearch( points, neighbors, dist, knn, SearchParams() ); 185 186 // 2nd way 187 Mat neighbors1( neighbors.size(), CV_32SC1 ); 188 for( int i = 0; i < points.rows; i++ ) 189 { 190 float* fltPtr = points.ptr<float>(i); 191 vector<float> query( fltPtr, fltPtr + points.cols ); 192 vector<int> indices( neighbors1.cols, 0 ); 193 vector<float> dists( dist.cols, 0 ); 194 index->knnSearch( query, indices, dists, knn, SearchParams() ); 195 vector<int>::const_iterator it = indices.begin(); 196 for( j = 0; it != indices.end(); ++it, j++ ) 197 neighbors1.at<int>(i,j) = *it; 198 } 199 200 // compare results 201 if( cvtest::norm( neighbors, neighbors1, NORM_L1 ) != 0 ) 202 return cvtest::TS::FAIL_BAD_ACCURACY; 203 204 return cvtest::TS::OK; 205 } 206 207 int CV_FlannTest::radiusSearch( Mat& points, Mat& neighbors ) 208 { 209 Mat dist( 1, neighbors.cols, CV_32FC1); 210 Mat neighbors1( neighbors.size(), CV_32SC1 ); 211 float radius = 10.0f; 212 int j; 213 214 // radiusSearch can only search one feature at a time for range search 215 for( int i = 0; i < points.rows; i++ ) 216 { 217 // 1st way 218 Mat p( 1, points.cols, CV_32FC1, points.ptr<float>(i) ), 219 n( 1, neighbors.cols, CV_32SC1, neighbors.ptr<int>(i) ); 220 index->radiusSearch( p, n, dist, radius, neighbors.cols, SearchParams() ); 221 222 // 2nd way 223 float* fltPtr = points.ptr<float>(i); 224 vector<float> query( fltPtr, fltPtr + points.cols ); 225 vector<int> indices( neighbors1.cols, 0 ); 226 vector<float> dists( dist.cols, 0 ); 227 index->radiusSearch( query, indices, dists, radius, neighbors.cols, SearchParams() ); 228 vector<int>::const_iterator it = indices.begin(); 229 for( j = 0; it != indices.end(); ++it, j++ ) 230 neighbors1.at<int>(i,j) = *it; 231 } 232 // compare results 233 if( cvtest::norm( neighbors, neighbors1, NORM_L1 ) != 0 ) 234 return cvtest::TS::FAIL_BAD_ACCURACY; 235 236 return cvtest::TS::OK; 237 } 238 239 void CV_FlannTest::releaseModel() 240 { 241 delete index; 242 } 243 244 //--------------------------------------- 245 class CV_FlannLinearIndexTest : public CV_FlannTest 246 { 247 public: 248 CV_FlannLinearIndexTest() {} 249 protected: 250 virtual void createModel( const Mat& data ) { createIndex( data, LinearIndexParams() ); } 251 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return knnSearch( points, neighbors ); } 252 }; 253 254 //--------------------------------------- 255 class CV_FlannKMeansIndexTest : public CV_FlannTest 256 { 257 public: 258 CV_FlannKMeansIndexTest() {} 259 protected: 260 virtual void createModel( const Mat& data ) { createIndex( data, KMeansIndexParams() ); } 261 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return radiusSearch( points, neighbors ); } 262 }; 263 264 //--------------------------------------- 265 class CV_FlannKDTreeIndexTest : public CV_FlannTest 266 { 267 public: 268 CV_FlannKDTreeIndexTest() {} 269 protected: 270 virtual void createModel( const Mat& data ) { createIndex( data, KDTreeIndexParams() ); } 271 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return radiusSearch( points, neighbors ); } 272 }; 273 274 //---------------------------------------- 275 class CV_FlannCompositeIndexTest : public CV_FlannTest 276 { 277 public: 278 CV_FlannCompositeIndexTest() {} 279 protected: 280 virtual void createModel( const Mat& data ) { createIndex( data, CompositeIndexParams() ); } 281 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return knnSearch( points, neighbors ); } 282 }; 283 284 //---------------------------------------- 285 class CV_FlannAutotunedIndexTest : public CV_FlannTest 286 { 287 public: 288 CV_FlannAutotunedIndexTest() {} 289 protected: 290 virtual void createModel( const Mat& data ) { createIndex( data, AutotunedIndexParams() ); } 291 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return knnSearch( points, neighbors ); } 292 }; 293 //---------------------------------------- 294 class CV_FlannSavedIndexTest : public CV_FlannTest 295 { 296 public: 297 CV_FlannSavedIndexTest() {} 298 protected: 299 virtual void createModel( const Mat& data ); 300 virtual int findNeighbors( Mat& points, Mat& neighbors ) { return knnSearch( points, neighbors ); } 301 }; 302 303 void CV_FlannSavedIndexTest::createModel(const cv::Mat &data) 304 { 305 switch ( cvtest::randInt(ts->get_rng()) % 2 ) 306 { 307 //case 0: createIndex( data, LinearIndexParams() ); break; // nothing to save for linear search 308 case 0: createIndex( data, KMeansIndexParams() ); break; 309 case 1: createIndex( data, KDTreeIndexParams() ); break; 310 //case 2: createIndex( data, CompositeIndexParams() ); break; // nothing to save for linear search 311 //case 2: createIndex( data, AutotunedIndexParams() ); break; // possible linear index ! 312 default: assert(0); 313 } 314 string filename = tempfile(); 315 index->save( filename ); 316 317 createIndex( data, SavedIndexParams(filename.c_str())); 318 remove( filename.c_str() ); 319 } 320 321 TEST(Features2d_FLANN_Linear, regression) { CV_FlannLinearIndexTest test; test.safe_run(); } 322 TEST(Features2d_FLANN_KMeans, regression) { CV_FlannKMeansIndexTest test; test.safe_run(); } 323 TEST(Features2d_FLANN_KDTree, regression) { CV_FlannKDTreeIndexTest test; test.safe_run(); } 324 TEST(Features2d_FLANN_Composite, regression) { CV_FlannCompositeIndexTest test; test.safe_run(); } 325 TEST(Features2d_FLANN_Auto, regression) { CV_FlannAutotunedIndexTest test; test.safe_run(); } 326 TEST(Features2d_FLANN_Saved, regression) { CV_FlannSavedIndexTest test; test.safe_run(); } 327