modules/features2d/src/detectors.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 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,
  23 //     this list of conditions and the following disclaimer in the documentation
  24 //     and/or other materials provided with the distribution.
  25 //
  26 //   * The name of Intel Corporation may not be used to endorse or promote products
  27 //     derived from this software without specific prior written permission.
  28 //
  29 // This software is provided by the copyright holders and contributors "as is" and
  30 // any express or implied warranties, including, but not limited to, the implied
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,
  33 // indirect, incidental, special, exemplary, or consequential damages
  34 // (including, but not limited to, procurement of substitute goods or services;
  35 // loss of use, data, or profits; or business interruption) however caused
  36 // and on any theory of liability, whether in contract, strict liability,
  37 // or tort (including negligence or otherwise) arising in any way out of
  38 // the use of this software, even if advised of the possibility of such damage.
  39 //
  40 //M*/
  41
  42 #include "precomp.hpp"
  43
  44 using namespace std;
  45
  46 namespace cv
  47 {
  48
  49 /*
  50  *  FeatureDetector
  51  */
  52
  53 FeatureDetector::~FeatureDetector()
  54 {}
  55
  56 void FeatureDetector::detect( const Mat& image, vector<KeyPoint>& keypoints, const Mat& mask ) const
  57 {
  58     keypoints.clear();
  59
  60     if( image.empty() )
  61         return;
  62
  63     CV_Assert( mask.empty() || (mask.type() == CV_8UC1 && mask.size() == image.size()) );
  64
  65     detectImpl( image, keypoints, mask );
  66 }
  67
  68 void FeatureDetector::detect(const vector<Mat>& imageCollection, vector<vector<KeyPoint> >& pointCollection, const vector<Mat>& masks ) const
  69 {
  70     pointCollection.resize( imageCollection.size() );
  71     for( size_t i = 0; i < imageCollection.size(); i++ )
  72         detect( imageCollection[i], pointCollection[i], masks.empty() ? Mat() : masks[i] );
  73 }
  74
  75 /*void FeatureDetector::read( const FileNode& )
  76 {}
  77
  78 void FeatureDetector::write( FileStorage& ) const
  79 {}*/
  80
  81 bool FeatureDetector::empty() const
  82 {
  83     return false;
  84 }
  85
  86 void FeatureDetector::removeInvalidPoints( const Mat& mask, vector<KeyPoint>& keypoints )
  87 {
  88     KeyPointsFilter::runByPixelsMask( keypoints, mask );
  89 }
  90
  91 Ptr<FeatureDetector> FeatureDetector::create( const string& detectorType )
  92 {
  93     if( detectorType.find("Grid") == 0 )
  94     {
  95         return new GridAdaptedFeatureDetector(FeatureDetector::create(
  96                                 detectorType.substr(strlen("Grid"))));
  97     }
  98
  99     if( detectorType.find("Pyramid") == 0 )
 100     {
 101         return new PyramidAdaptedFeatureDetector(FeatureDetector::create(
 102                                 detectorType.substr(strlen("Pyramid"))));
 103     }
 104
 105     if( detectorType.find("Dynamic") == 0 )
 106     {
 107         return new DynamicAdaptedFeatureDetector(AdjusterAdapter::create(
 108                                 detectorType.substr(strlen("Dynamic"))));
 109     }
 110
 111     if( detectorType.compare( "HARRIS" ) == 0 )
 112     {
 113         Ptr<FeatureDetector> fd = FeatureDetector::create("GFTT");
 114         fd->set("useHarrisDetector", true);
 115         return fd;
 116     }
 117
 118     return Algorithm::create<FeatureDetector>("Feature2D." + detectorType);
 119 }
 120
 121
 122 GFTTDetector::GFTTDetector( int _nfeatures, double _qualityLevel,
 123                             double _minDistance, int _blockSize,
 124                             bool _useHarrisDetector, double _k )
 125     : nfeatures(_nfeatures), qualityLevel(_qualityLevel), minDistance(_minDistance),
 126     blockSize(_blockSize), useHarrisDetector(_useHarrisDetector), k(_k)
 127 {
 128 }
 129
 130 void GFTTDetector::detectImpl( const Mat& image, vector<KeyPoint>& keypoints, const Mat& mask) const
 131 {
 132     Mat grayImage = image;
 133     if( image.type() != CV_8U ) cvtColor( image, grayImage, CV_BGR2GRAY );
 134
 135     vector<Point2f> corners;
 136     goodFeaturesToTrack( grayImage, corners, nfeatures, qualityLevel, minDistance, mask,
 137                          blockSize, useHarrisDetector, k );
 138     keypoints.resize(corners.size());
 139     vector<Point2f>::const_iterator corner_it = corners.begin();
 140     vector<KeyPoint>::iterator keypoint_it = keypoints.begin();
 141     for( ; corner_it != corners.end(); ++corner_it, ++keypoint_it )
 142     {
 143         *keypoint_it = KeyPoint( *corner_it, (float)blockSize );
 144     }
 145 }
 146
 147 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 148
 149 /*
 150  *  DenseFeatureDetector
 151  */
 152 DenseFeatureDetector::DenseFeatureDetector( float _initFeatureScale, int _featureScaleLevels,
 153                                       float _featureScaleMul, int _initXyStep,
 154                                       int _initImgBound, bool _varyXyStepWithScale,
 155                                       bool _varyImgBoundWithScale ) :
 156     initFeatureScale(_initFeatureScale), featureScaleLevels(_featureScaleLevels),
 157     featureScaleMul(_featureScaleMul), initXyStep(_initXyStep), initImgBound(_initImgBound),
 158     varyXyStepWithScale(_varyXyStepWithScale), varyImgBoundWithScale(_varyImgBoundWithScale)
 159 {}
 160
 161
 162 void DenseFeatureDetector::detectImpl( const Mat& image, vector<KeyPoint>& keypoints, const Mat& mask ) const
 163 {
 164     float curScale = static_cast<float>(initFeatureScale);
 165     int curStep = initXyStep;
 166     int curBound = initImgBound;
 167     for( int curLevel = 0; curLevel < featureScaleLevels; curLevel++ )
 168     {
 169         for( int x = curBound; x < image.cols - curBound; x += curStep )
 170         {
 171             for( int y = curBound; y < image.rows - curBound; y += curStep )
 172             {
 173                 keypoints.push_back( KeyPoint(static_cast<float>(x), static_cast<float>(y), curScale) );
 174             }
 175         }
 176
 177         curScale = static_cast<float>(curScale * featureScaleMul);
 178         if( varyXyStepWithScale ) curStep = static_cast<int>( curStep * featureScaleMul + 0.5f );
 179         if( varyImgBoundWithScale ) curBound = static_cast<int>( curBound * featureScaleMul + 0.5f );
 180     }
 181
 182     KeyPointsFilter::runByPixelsMask( keypoints, mask );
 183 }
 184
 185 /*
 186  *  GridAdaptedFeatureDetector
 187  */
 188 GridAdaptedFeatureDetector::GridAdaptedFeatureDetector( const Ptr<FeatureDetector>& _detector,
 189                                                         int _maxTotalKeypoints, int _gridRows, int _gridCols )
 190     : detector(_detector), maxTotalKeypoints(_maxTotalKeypoints), gridRows(_gridRows), gridCols(_gridCols)
 191 {}
 192
 193 bool GridAdaptedFeatureDetector::empty() const
 194 {
 195     return detector.empty() || (FeatureDetector*)detector->empty();
 196 }
 197
 198 struct ResponseComparator
 199 {
 200     bool operator() (const KeyPoint& a, const KeyPoint& b)
 201     {
 202         return std::abs(a.response) > std::abs(b.response);
 203     }
 204 };
 205
 206 static void keepStrongest( int N, vector<KeyPoint>& keypoints )
 207 {
 208     if( (int)keypoints.size() > N )
 209     {
 210         vector<KeyPoint>::iterator nth = keypoints.begin() + N;
 211         std::nth_element( keypoints.begin(), nth, keypoints.end(), ResponseComparator() );
 212         keypoints.erase( nth, keypoints.end() );
 213     }
 214 }
 215
 216 namespace {
 217 class GridAdaptedFeatureDetectorInvoker : public ParallelLoopBody
 218 {
 219 private:
 220     int gridRows_, gridCols_;
 221     int maxPerCell_;
 222     vector<KeyPoint>& keypoints_;
 223     const Mat& image_;
 224     const Mat& mask_;
 225     const Ptr<FeatureDetector>& detector_;
 226     Mutex* kptLock_;
 227
 228     GridAdaptedFeatureDetectorInvoker& operator=(const GridAdaptedFeatureDetectorInvoker&); // to quiet MSVC
 229
 230 public:
 231
 232     GridAdaptedFeatureDetectorInvoker(const Ptr<FeatureDetector>& detector, const Mat& image, const Mat& mask,
 233                                       vector<KeyPoint>& keypoints, int maxPerCell, int gridRows, int gridCols,
 234                                       cv::Mutex* kptLock)
 235         : gridRows_(gridRows), gridCols_(gridCols), maxPerCell_(maxPerCell),
 236           keypoints_(keypoints), image_(image), mask_(mask), detector_(detector),
 237           kptLock_(kptLock)
 238     {
 239     }
 240
 241     void operator() (const Range& range) const
 242     {
 243         for (int i = range.start; i < range.end; ++i)
 244         {
 245             int celly = i / gridCols_;
 246             int cellx = i - celly * gridCols_;
 247
 248             Range row_range((celly*image_.rows)/gridRows_, ((celly+1)*image_.rows)/gridRows_);
 249             Range col_range((cellx*image_.cols)/gridCols_, ((cellx+1)*image_.cols)/gridCols_);
 250
 251             Mat sub_image = image_(row_range, col_range);
 252             Mat sub_mask;
 253             if (!mask_.empty()) sub_mask = mask_(row_range, col_range);
 254
 255             vector<KeyPoint> sub_keypoints;
 256             sub_keypoints.reserve(maxPerCell_);
 257
 258             detector_->detect( sub_image, sub_keypoints, sub_mask );
 259             keepStrongest( maxPerCell_, sub_keypoints );
 260
 261             std::vector<cv::KeyPoint>::iterator it = sub_keypoints.begin(),
 262                                                 end = sub_keypoints.end();
 263             for( ; it != end; ++it )
 264             {
 265                 it->pt.x += col_range.start;
 266                 it->pt.y += row_range.start;
 267             }
 268
 269             cv::AutoLock join_keypoints(*kptLock_);
 270             keypoints_.insert( keypoints_.end(), sub_keypoints.begin(), sub_keypoints.end() );
 271         }
 272     }
 273 };
 274 } // namepace
 275
 276 void GridAdaptedFeatureDetector::detectImpl( const Mat& image, vector<KeyPoint>& keypoints, const Mat& mask ) const
 277 {
 278     if (image.empty() || maxTotalKeypoints < gridRows * gridCols)
 279     {
 280         keypoints.clear();
 281         return;
 282     }
 283     keypoints.reserve(maxTotalKeypoints);
 284     int maxPerCell = maxTotalKeypoints / (gridRows * gridCols);
 285
 286     cv::Mutex kptLock;
 287     cv::parallel_for_(cv::Range(0, gridRows * gridCols),
 288         GridAdaptedFeatureDetectorInvoker(detector, image, mask, keypoints, maxPerCell, gridRows, gridCols, &kptLock));
 289 }
 290
 291 /*
 292  *  PyramidAdaptedFeatureDetector
 293  */
 294 PyramidAdaptedFeatureDetector::PyramidAdaptedFeatureDetector( const Ptr<FeatureDetector>& _detector, int _maxLevel )
 295     : detector(_detector), maxLevel(_maxLevel)
 296 {}
 297
 298 bool PyramidAdaptedFeatureDetector::empty() const
 299 {
 300     return detector.empty() || (FeatureDetector*)detector->empty();
 301 }
 302
 303 void PyramidAdaptedFeatureDetector::detectImpl( const Mat& image, vector<KeyPoint>& keypoints, const Mat& mask ) const
 304 {
 305     Mat src = image;
 306     Mat src_mask = mask;
 307
 308     Mat dilated_mask;
 309     if( !mask.empty() )
 310     {
 311         dilate( mask, dilated_mask, Mat() );
 312         Mat mask255( mask.size(), CV_8UC1, Scalar(0) );
 313         mask255.setTo( Scalar(255), dilated_mask != 0 );
 314         dilated_mask = mask255;
 315     }
 316
 317     for( int l = 0, multiplier = 1; l <= maxLevel; ++l, multiplier *= 2 )
 318     {
 319         // Detect on current level of the pyramid
 320         vector<KeyPoint> new_pts;
 321         detector->detect( src, new_pts, src_mask );
 322         vector<KeyPoint>::iterator it = new_pts.begin(),
 323                                    end = new_pts.end();
 324         for( ; it != end; ++it)
 325         {
 326             it->pt.x *= multiplier;
 327             it->pt.y *= multiplier;
 328             it->size *= multiplier;
 329             it->octave = l;
 330         }
 331         keypoints.insert( keypoints.end(), new_pts.begin(), new_pts.end() );
 332
 333         // Downsample
 334         if( l < maxLevel )
 335         {
 336             Mat dst;
 337             pyrDown( src, dst );
 338             src = dst;
 339
 340             if( !mask.empty() )
 341                 resize( dilated_mask, src_mask, src.size(), 0, 0, CV_INTER_AREA );
 342         }
 343     }
 344
 345     if( !mask.empty() )
 346         KeyPointsFilter::runByPixelsMask( keypoints, mask );
 347 }
 348
 349
 350 }