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