modules/imgproc/src/featureselect.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 #include "opencl_kernels.hpp"
  44
  45 #include <cstdio>
  46 #include <vector>
  47 #include <iostream>
  48 #include <functional>
  49
  50 namespace cv
  51 {
  52
  53 struct greaterThanPtr :
  54         public std::binary_function<const float *, const float *, bool>
  55 {
  56     bool operator () (const float * a, const float * b) const
  57     { return *a > *b; }
  58 };
  59
  60 struct Corner
  61 {
  62     float val;
  63     short y;
  64     short x;
  65
  66     bool operator < (const Corner & c) const
  67     {  return val > c.val; }
  68 };
  69
  70 #ifdef HAVE_OPENCL
  71
  72 static bool ocl_goodFeaturesToTrack( InputArray _image, OutputArray _corners,
  73                                      int maxCorners, double qualityLevel, double minDistance,
  74                                      InputArray _mask, int blockSize,
  75                                      bool useHarrisDetector, double harrisK )
  76 {
  77     UMat eig, tmp;
  78     if( useHarrisDetector )
  79         cornerHarris( _image, eig, blockSize, 3, harrisK );
  80     else
  81         cornerMinEigenVal( _image, eig, blockSize, 3 );
  82
  83     double maxVal = 0;
  84     minMaxLoc( eig, NULL, &maxVal, NULL, NULL, _mask );
  85     threshold( eig, eig, maxVal*qualityLevel, 0, THRESH_TOZERO );
  86     dilate( eig, tmp, Mat());
  87
  88     Size imgsize = _image.size();
  89     std::vector<Corner> tmpCorners;
  90     size_t total, i, j, ncorners = 0, possibleCornersCount =
  91             std::max(1024, static_cast<int>(imgsize.area() * 0.1));
  92     bool haveMask = !_mask.empty();
  93
  94     // collect list of pointers to features - put them into temporary image
  95     {
  96         ocl::Kernel k("findCorners", ocl::imgproc::gftt_oclsrc,
  97                       format(haveMask ? "-D HAVE_MASK" : ""));
  98         if (k.empty())
  99             return false;
 100
 101         UMat counter(1, 1, CV_32SC1, Scalar::all(0)),
 102                 corners(1, (int)(possibleCornersCount * sizeof(Corner)), CV_8UC1);
 103         ocl::KernelArg eigarg = ocl::KernelArg::ReadOnlyNoSize(eig),
 104                 tmparg = ocl::KernelArg::ReadOnlyNoSize(tmp),
 105                 cornersarg = ocl::KernelArg::PtrWriteOnly(corners),
 106                 counterarg = ocl::KernelArg::PtrReadWrite(counter);
 107
 108         if (!haveMask)
 109             k.args(eigarg, tmparg, cornersarg, counterarg,
 110                    imgsize.height - 2, imgsize.width - 2);
 111         else
 112         {
 113             UMat mask = _mask.getUMat();
 114             k.args(eigarg, ocl::KernelArg::ReadOnlyNoSize(mask), tmparg,
 115                    cornersarg, counterarg, imgsize.height - 2, imgsize.width - 2);
 116         }
 117
 118         size_t globalsize[2] = { imgsize.width - 2, imgsize.height - 2 };
 119         if (!k.run(2, globalsize, NULL, false))
 120             return false;
 121
 122         total = counter.getMat(ACCESS_READ).at<int>(0, 0);
 123         int totalb = (int)(sizeof(Corner) * total);
 124
 125         tmpCorners.resize(total);
 126         Mat mcorners(1, totalb, CV_8UC1, &tmpCorners[0]);
 127         corners.colRange(0, totalb).copyTo(mcorners);
 128     }
 129
 130     std::sort( tmpCorners.begin(), tmpCorners.end() );
 131     std::vector<Point2f> corners;
 132     corners.reserve(total);
 133
 134     if (minDistance >= 1)
 135     {
 136          // Partition the image into larger grids
 137         int w = imgsize.width, h = imgsize.height;
 138
 139         const int cell_size = cvRound(minDistance);
 140         const int grid_width = (w + cell_size - 1) / cell_size;
 141         const int grid_height = (h + cell_size - 1) / cell_size;
 142
 143         std::vector<std::vector<Point2f> > grid(grid_width*grid_height);
 144         minDistance *= minDistance;
 145
 146         for( i = 0; i < total; i++ )
 147         {
 148             const Corner & c = tmpCorners[i];
 149             bool good = true;
 150
 151             int x_cell = c.x / cell_size;
 152             int y_cell = c.y / cell_size;
 153
 154             int x1 = x_cell - 1;
 155             int y1 = y_cell - 1;
 156             int x2 = x_cell + 1;
 157             int y2 = y_cell + 1;
 158
 159             // boundary check
 160             x1 = std::max(0, x1);
 161             y1 = std::max(0, y1);
 162             x2 = std::min(grid_width-1, x2);
 163             y2 = std::min(grid_height-1, y2);
 164
 165             for( int yy = y1; yy <= y2; yy++ )
 166                 for( int xx = x1; xx <= x2; xx++ )
 167                 {
 168                     std::vector<Point2f> &m = grid[yy*grid_width + xx];
 169
 170                     if( m.size() )
 171                     {
 172                         for(j = 0; j < m.size(); j++)
 173                         {
 174                             float dx = c.x - m[j].x;
 175                             float dy = c.y - m[j].y;
 176
 177                             if( dx*dx + dy*dy < minDistance )
 178                             {
 179                                 good = false;
 180                                 goto break_out;
 181                             }
 182                         }
 183                     }
 184                 }
 185
 186             break_out:
 187
 188             if (good)
 189             {
 190                 grid[y_cell*grid_width + x_cell].push_back(Point2f((float)c.x, (float)c.y));
 191
 192                 corners.push_back(Point2f((float)c.x, (float)c.y));
 193                 ++ncorners;
 194
 195                 if( maxCorners > 0 && (int)ncorners == maxCorners )
 196                     break;
 197             }
 198         }
 199     }
 200     else
 201     {
 202         for( i = 0; i < total; i++ )
 203         {
 204             const Corner & c = tmpCorners[i];
 205
 206             corners.push_back(Point2f((float)c.x, (float)c.y));
 207             ++ncorners;
 208             if( maxCorners > 0 && (int)ncorners == maxCorners )
 209                 break;
 210         }
 211     }
 212
 213     Mat(corners).convertTo(_corners, _corners.fixedType() ? _corners.type() : CV_32F);
 214     return true;
 215 }
 216
 217 #endif
 218
 219 }
 220
 221 void cv::goodFeaturesToTrack( InputArray _image, OutputArray _corners,
 222                               int maxCorners, double qualityLevel, double minDistance,
 223                               InputArray _mask, int blockSize,
 224                               bool useHarrisDetector, double harrisK )
 225 {
 226     CV_Assert( qualityLevel > 0 && minDistance >= 0 && maxCorners >= 0 );
 227     CV_Assert( _mask.empty() || (_mask.type() == CV_8UC1 && _mask.sameSize(_image)) );
 228
 229     CV_OCL_RUN(_image.dims() <= 2 && _image.isUMat(),
 230                ocl_goodFeaturesToTrack(_image, _corners, maxCorners, qualityLevel, minDistance,
 231                                     _mask, blockSize, useHarrisDetector, harrisK))
 232
 233     Mat image = _image.getMat(), eig, tmp;
 234     if( useHarrisDetector )
 235         cornerHarris( image, eig, blockSize, 3, harrisK );
 236     else
 237         cornerMinEigenVal( image, eig, blockSize, 3 );
 238
 239     double maxVal = 0;
 240     minMaxLoc( eig, 0, &maxVal, 0, 0, _mask );
 241     threshold( eig, eig, maxVal*qualityLevel, 0, THRESH_TOZERO );
 242     dilate( eig, tmp, Mat());
 243
 244     Size imgsize = image.size();
 245     std::vector<const float*> tmpCorners;
 246
 247     // collect list of pointers to features - put them into temporary image
 248     Mat mask = _mask.getMat();
 249     for( int y = 1; y < imgsize.height - 1; y++ )
 250     {
 251         const float* eig_data = (const float*)eig.ptr(y);
 252         const float* tmp_data = (const float*)tmp.ptr(y);
 253         const uchar* mask_data = mask.data ? mask.ptr(y) : 0;
 254
 255         for( int x = 1; x < imgsize.width - 1; x++ )
 256         {
 257             float val = eig_data[x];
 258             if( val != 0 && val == tmp_data[x] && (!mask_data || mask_data[x]) )
 259                 tmpCorners.push_back(eig_data + x);
 260         }
 261     }
 262
 263     std::sort( tmpCorners.begin(), tmpCorners.end(), greaterThanPtr() );
 264     std::vector<Point2f> corners;
 265     size_t i, j, total = tmpCorners.size(), ncorners = 0;
 266
 267     if (minDistance >= 1)
 268     {
 269          // Partition the image into larger grids
 270         int w = image.cols;
 271         int h = image.rows;
 272
 273         const int cell_size = cvRound(minDistance);
 274         const int grid_width = (w + cell_size - 1) / cell_size;
 275         const int grid_height = (h + cell_size - 1) / cell_size;
 276
 277         std::vector<std::vector<Point2f> > grid(grid_width*grid_height);
 278
 279         minDistance *= minDistance;
 280
 281         for( i = 0; i < total; i++ )
 282         {
 283             int ofs = (int)((const uchar*)tmpCorners[i] - eig.data);
 284             int y = (int)(ofs / eig.step);
 285             int x = (int)((ofs - y*eig.step)/sizeof(float));
 286
 287             bool good = true;
 288
 289             int x_cell = x / cell_size;
 290             int y_cell = y / cell_size;
 291
 292             int x1 = x_cell - 1;
 293             int y1 = y_cell - 1;
 294             int x2 = x_cell + 1;
 295             int y2 = y_cell + 1;
 296
 297             // boundary check
 298             x1 = std::max(0, x1);
 299             y1 = std::max(0, y1);
 300             x2 = std::min(grid_width-1, x2);
 301             y2 = std::min(grid_height-1, y2);
 302
 303             for( int yy = y1; yy <= y2; yy++ )
 304                 for( int xx = x1; xx <= x2; xx++ )
 305                 {
 306                     std::vector <Point2f> &m = grid[yy*grid_width + xx];
 307
 308                     if( m.size() )
 309                     {
 310                         for(j = 0; j < m.size(); j++)
 311                         {
 312                             float dx = x - m[j].x;
 313                             float dy = y - m[j].y;
 314
 315                             if( dx*dx + dy*dy < minDistance )
 316                             {
 317                                 good = false;
 318                                 goto break_out;
 319                             }
 320                         }
 321                     }
 322                 }
 323
 324             break_out:
 325
 326             if (good)
 327             {
 328                 grid[y_cell*grid_width + x_cell].push_back(Point2f((float)x, (float)y));
 329
 330                 corners.push_back(Point2f((float)x, (float)y));
 331                 ++ncorners;
 332
 333                 if( maxCorners > 0 && (int)ncorners == maxCorners )
 334                     break;
 335             }
 336         }
 337     }
 338     else
 339     {
 340         for( i = 0; i < total; i++ )
 341         {
 342             int ofs = (int)((const uchar*)tmpCorners[i] - eig.data);
 343             int y = (int)(ofs / eig.step);
 344             int x = (int)((ofs - y*eig.step)/sizeof(float));
 345
 346             corners.push_back(Point2f((float)x, (float)y));
 347             ++ncorners;
 348             if( maxCorners > 0 && (int)ncorners == maxCorners )
 349                 break;
 350         }
 351     }
 352
 353     Mat(corners).convertTo(_corners, _corners.fixedType() ? _corners.type() : CV_32F);
 354 }
 355
 356 CV_IMPL void
 357 cvGoodFeaturesToTrack( const void* _image, void*, void*,
 358                        CvPoint2D32f* _corners, int *_corner_count,
 359                        double quality_level, double min_distance,
 360                        const void* _maskImage, int block_size,
 361                        int use_harris, double harris_k )
 362 {
 363     cv::Mat image = cv::cvarrToMat(_image), mask;
 364     std::vector<cv::Point2f> corners;
 365
 366     if( _maskImage )
 367         mask = cv::cvarrToMat(_maskImage);
 368
 369     CV_Assert( _corners && _corner_count );
 370     cv::goodFeaturesToTrack( image, corners, *_corner_count, quality_level,
 371         min_distance, mask, block_size, use_harris != 0, harris_k );
 372
 373     size_t i, ncorners = corners.size();
 374     for( i = 0; i < ncorners; i++ )
 375         _corners[i] = corners[i];
 376     *_corner_count = (int)ncorners;
 377 }
 378
 379 /* End of file. */