modules/legacy/test/test_nearestneighbors.cpp

   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 // Third party copyrights are property of their respective owners.
  16 //
  17 // Redistribution and use in source and binary forms, with or without modification,
  18 // are permitted provided that the following conditions are met:
  19 //
  20 //   * Redistribution's of source code must retain the above copyright notice,
  21 //     this list of conditions and the following disclaimer.
  22 //
  23 //   * Redistribution's in binary form must reproduce the above copyright notice,
  24 //     this list of conditions and the following disclaimer in the documentation
  25 //     and/or other materials provided with the distribution.
  26 //
  27 //   * The name of the copyright holders may not be used to endorse or promote products
  28 //     derived from this software without specific prior written permission.
  29 //
  30 // This software is provided by the copyright holders and contributors "as is" and
  31 // any express or implied warranties, including, but not limited to, the implied
  32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  33 // In no event shall the Intel Corporation or contributors be liable for any direct,
  34 // indirect, incidental, special, exemplary, or consequential damages
  35 // (including, but not limited to, procurement of substitute goods or services;
  36 // loss of use, data, or profits; or business interruption) however caused
  37 // and on any theory of liability, whether in contract, strict liability,
  38 // or tort (including negligence or otherwise) arising in any way out of
  39 // the use of this software, even if advised of the possibility of such damage.
  40 //
  41 //M*/
  42
  43 #include "test_precomp.hpp"
  44
  45 #include <algorithm>
  46 #include <vector>
  47 #include <iostream>
  48
  49 using namespace cv;
  50 using namespace cv::flann;
  51
  52 //--------------------------------------------------------------------------------
  53 class NearestNeighborTest : public cvtest::BaseTest
  54 {
  55 public:
  56     NearestNeighborTest() {}
  57 protected:
  58     static const int minValue = 0;
  59     static const int maxValue = 1;
  60     static const int dims = 30;
  61     static const int featuresCount = 2000;
  62     static const int K = 1; // * should also test 2nd nn etc.?
  63
  64
  65     virtual void run( int start_from );
  66     virtual void createModel( const Mat& data ) = 0;
  67     virtual int findNeighbors( Mat& points, Mat& neighbors ) = 0;
  68     virtual int checkGetPoins( const Mat& data );
  69     virtual int checkFindBoxed();
  70     virtual int checkFind( const Mat& data );
  71     virtual void releaseModel() = 0;
  72 };
  73
  74 int NearestNeighborTest::checkGetPoins( const Mat& )
  75 {
  76    return cvtest::TS::OK;
  77 }
  78
  79 int NearestNeighborTest::checkFindBoxed()
  80 {
  81     return cvtest::TS::OK;
  82 }
  83
  84 int NearestNeighborTest::checkFind( const Mat& data )
  85 {
  86     int code = cvtest::TS::OK;
  87     int pointsCount = 1000;
  88     float noise = 0.2f;
  89
  90     RNG rng;
  91     Mat points( pointsCount, dims, CV_32FC1 );
  92     Mat results( pointsCount, K, CV_32SC1 );
  93
  94     std::vector<int> fmap( pointsCount );
  95     for( int pi = 0; pi < pointsCount; pi++ )
  96     {
  97         int fi = rng.next() % featuresCount;
  98         fmap[pi] = fi;
  99         for( int d = 0; d < dims; d++ )
 100             points.at<float>(pi, d) = data.at<float>(fi, d) + rng.uniform(0.0f, 1.0f) * noise;
 101     }
 102
 103     code = findNeighbors( points, results );
 104
 105     if( code == cvtest::TS::OK )
 106     {
 107         int correctMatches = 0;
 108         for( int pi = 0; pi < pointsCount; pi++ )
 109         {
 110             if( fmap[pi] == results.at<int>(pi, 0) )
 111                 correctMatches++;
 112         }
 113
 114         double correctPerc = correctMatches / (double)pointsCount;
 115         if (correctPerc < .75)
 116         {
 117             ts->printf( cvtest::TS::LOG, "correct_perc = %d\n", correctPerc );
 118             code = cvtest::TS::FAIL_BAD_ACCURACY;
 119         }
 120     }
 121
 122     return code;
 123 }
 124
 125 void NearestNeighborTest::run( int /*start_from*/ ) {
 126     int code = cvtest::TS::OK, tempCode;
 127     Mat desc( featuresCount, dims, CV_32FC1 );
 128     randu( desc, Scalar(minValue), Scalar(maxValue) );
 129
 130     createModel( desc );
 131
 132     tempCode = checkGetPoins( desc );
 133     if( tempCode != cvtest::TS::OK )
 134     {
 135         ts->printf( cvtest::TS::LOG, "bad accuracy of GetPoints \n" );
 136         code = tempCode;
 137     }
 138
 139     tempCode = checkFindBoxed();
 140     if( tempCode != cvtest::TS::OK )
 141     {
 142         ts->printf( cvtest::TS::LOG, "bad accuracy of FindBoxed \n" );
 143         code = tempCode;
 144     }
 145
 146     tempCode = checkFind( desc );
 147     if( tempCode != cvtest::TS::OK )
 148     {
 149         ts->printf( cvtest::TS::LOG, "bad accuracy of Find \n" );
 150         code = tempCode;
 151     }
 152
 153     releaseModel();
 154
 155     ts->set_failed_test_info( code );
 156 }
 157
 158 //--------------------------------------------------------------------------------
 159 class CV_LSHTest : public NearestNeighborTest
 160 {
 161 public:
 162     CV_LSHTest() {}
 163 protected:
 164     virtual void createModel( const Mat& data );
 165     virtual int findNeighbors( Mat& points, Mat& neighbors );
 166     virtual void releaseModel();
 167     struct CvLSH* lsh;
 168     CvMat desc;
 169 };
 170
 171 void CV_LSHTest::createModel( const Mat& data )
 172 {
 173     desc = data;
 174     lsh = cvCreateMemoryLSH( data.cols, data.rows, 70, 20, CV_32FC1 );
 175     cvLSHAdd( lsh, &desc );
 176 }
 177
 178 int CV_LSHTest::findNeighbors( Mat& points, Mat& neighbors )
 179 {
 180     const int emax = 20;
 181     Mat dist( points.rows, neighbors.cols, CV_64FC1);
 182     CvMat _dist = dist, _points = points, _neighbors = neighbors;
 183     cvLSHQuery( lsh, &_points, &_neighbors, &_dist, neighbors.cols, emax );
 184     return cvtest::TS::OK;
 185 }
 186
 187 void CV_LSHTest::releaseModel()
 188 {
 189     cvReleaseLSH( &lsh );
 190 }
 191
 192 //--------------------------------------------------------------------------------
 193 class CV_FeatureTreeTest_C : public NearestNeighborTest
 194 {
 195 public:
 196     CV_FeatureTreeTest_C() {}
 197 protected:
 198     virtual int findNeighbors( Mat& points, Mat& neighbors );
 199     virtual void releaseModel();
 200     CvFeatureTree* tr;
 201     CvMat desc;
 202 };
 203
 204 int CV_FeatureTreeTest_C::findNeighbors( Mat& points, Mat& neighbors )
 205 {
 206     const int emax = 20;
 207     Mat dist( points.rows, neighbors.cols, CV_64FC1);
 208     CvMat _dist = dist, _points = points, _neighbors = neighbors;
 209     cvFindFeatures( tr, &_points, &_neighbors, &_dist, neighbors.cols, emax );
 210     return cvtest::TS::OK;
 211 }
 212
 213 void CV_FeatureTreeTest_C::releaseModel()
 214 {
 215     cvReleaseFeatureTree( tr );
 216 }
 217
 218 //--------------------------------------
 219 class CV_SpillTreeTest_C : public CV_FeatureTreeTest_C
 220 {
 221 public:
 222     CV_SpillTreeTest_C() {}
 223 protected:
 224     virtual void createModel( const Mat& data );
 225 };
 226
 227 void CV_SpillTreeTest_C::createModel( const Mat& data )
 228 {
 229     desc = data;
 230     tr = cvCreateSpillTree( &desc );
 231 }
 232
 233 //--------------------------------------
 234 class CV_KDTreeTest_C : public CV_FeatureTreeTest_C
 235 {
 236 public:
 237     CV_KDTreeTest_C() {}
 238 protected:
 239     virtual void createModel( const Mat& data );
 240     virtual int checkFindBoxed();
 241 };
 242
 243 void CV_KDTreeTest_C::createModel( const Mat& data )
 244 {
 245     desc = data;
 246     tr = cvCreateKDTree( &desc );
 247 }
 248
 249 int CV_KDTreeTest_C::checkFindBoxed()
 250 {
 251     Mat min(1, dims, CV_32FC1 ), max(1, dims, CV_32FC1 ), indices( 1, 1, CV_32SC1 );
 252     float l = minValue, r = maxValue;
 253     min.setTo(Scalar(l)), max.setTo(Scalar(r));
 254     CvMat _min = min, _max = max, _indices = indices;
 255     // TODO check indices
 256     if( cvFindFeaturesBoxed( tr, &_min, &_max, &_indices ) != featuresCount )
 257         return cvtest::TS::FAIL_BAD_ACCURACY;
 258     return cvtest::TS::OK;
 259 }
 260
 261
 262 TEST(Legacy_LSH, regression) { CV_LSHTest test; test.safe_run(); }
 263 TEST(Legacy_SpillTree, regression) { CV_SpillTreeTest_C test; test.safe_run(); }
 264 TEST(Legacy_KDTree_C, regression) { CV_KDTreeTest_C test; test.safe_run(); }