1 /****************************************************************************** 2 * $Id: gdal_simplesurf.h 595fc490ff5c1572fd1e75b4d5840ef30a170e74 2020-06-19 18:24:16 +0200 Even Rouault $ 3 * Project: GDAL 4 * Purpose: Correlator 5 * Author: Andrew Migal, migal.drew@gmail.com 6 * 7 ****************************************************************************** 8 * Copyright (c) 2012, Andrew Migal 9 * 10 * Permission is hereby granted, free of charge, to any person obtaining a 11 * copy of this software and associated documentation files (the "Software"), 12 * to deal in the Software without restriction, including without limitation 13 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 14 * and/or sell copies of the Software, and to permit persons to whom the 15 * Software is furnished to do so, subject to the following conditions: 16 * 17 * The above copyright notice and this permission notice shall be included 18 * in all copies or substantial portions of the Software. 19 * 20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 21 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 23 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 25 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 26 * DEALINGS IN THE SOFTWARE. 27 ****************************************************************************/ 28 29 /** 30 * @file 31 * @author Andrew Migal migal.drew@gmail.com 32 * @brief Class for searching corresponding points on images. 33 */ 34 35 #ifndef GDALSIMPLESURF_H_ 36 #define GDALSIMPLESURF_H_ 37 38 #include "gdal_priv.h" 39 #include "cpl_conv.h" 40 #include <list> 41 42 /** 43 * @brief Class of "feature point" in raster. Used by SURF-based algorithm. 44 * 45 * @details This point presents coordinates of distinctive pixel in image. 46 * In computer vision, feature points - the most "strong" and "unique" 47 * pixels (or areas) in picture, which can be distinguished from others. 48 * For more details, see FAST corner detector, SIFT, SURF and similar algorithms. 49 */ 50 class GDALFeaturePoint 51 { 52 public: 53 /** 54 * Standard constructor. Initializes all parameters with negative numbers 55 * and allocates memory for descriptor. 56 */ 57 GDALFeaturePoint(); 58 59 /** 60 * Copy constructor 61 * @param fp Copied instance of GDALFeaturePoint class 62 */ 63 GDALFeaturePoint(const GDALFeaturePoint& fp); 64 65 /** 66 * Create instance of GDALFeaturePoint class 67 * 68 * @param nX X-coordinate (pixel) 69 * @param nY Y-coordinate (line) 70 * @param nScale Scale which contains this point (2, 4, 8, 16 and so on) 71 * @param nRadius Half of the side of descriptor area 72 * @param nSign Sign of Hessian determinant for this point 73 * 74 * @note This constructor normally is invoked by SURF-based algorithm, 75 * which provides all necessary parameters. 76 */ 77 GDALFeaturePoint(int nX, int nY, int nScale, int nRadius, int nSign); 78 virtual ~GDALFeaturePoint(); 79 80 /** Assignment operator */ 81 GDALFeaturePoint& operator=(const GDALFeaturePoint& point); 82 83 /** 84 * Provide access to point's descriptor. 85 * 86 * @param nIndex Position of descriptor's value. 87 * nIndex should be within range from 0 to DESC_SIZE (in current version - 64) 88 * 89 * @return Reference to value of descriptor in 'nIndex' position. 90 * If index is out of range then behavior is undefined. 91 */ 92 double& operator[](int nIndex); 93 94 /** Descriptor length */ 95 static const int DESC_SIZE = 64; 96 97 /** 98 * Fetch X-coordinate (pixel) of point 99 * 100 * @return X-coordinate in pixels 101 */ 102 int GetX() const; 103 104 /** 105 * Set X coordinate of point 106 * 107 * @param nX X coordinate in pixels 108 */ 109 void SetX(int nX); 110 111 /** 112 * Fetch Y-coordinate (line) of point. 113 * 114 * @return Y-coordinate in pixels. 115 */ 116 int GetY() const; 117 118 /** 119 * Set Y coordinate of point. 120 * 121 * @param nY Y coordinate in pixels. 122 */ 123 void SetY(int nY); 124 125 /** 126 * Fetch scale of point. 127 * 128 * @return Scale for this point. 129 */ 130 int GetScale() const ; 131 132 /** 133 * Set scale of point. 134 * 135 * @param nScale Scale for this point. 136 */ 137 void SetScale(int nScale); 138 139 /** 140 * Fetch radius of point. 141 * 142 * @return Radius for this point. 143 */ 144 int GetRadius() const; 145 146 /** 147 * Set radius of point. 148 * 149 * @param nRadius Radius for this point. 150 */ 151 void SetRadius(int nRadius); 152 153 /** 154 * Fetch sign of Hessian determinant of point. 155 * 156 * @return Sign for this point. 157 */ 158 int GetSign() const; 159 160 /** 161 * Set sign of point. 162 * 163 * @param nSign Sign of Hessian determinant for this point. 164 */ 165 void SetSign(int nSign); 166 167 private: 168 // Coordinates of point in image 169 int nX; 170 int nY; 171 // -------------------- 172 int nScale; 173 int nRadius; 174 int nSign; 175 // Descriptor array 176 double *padfDescriptor; 177 }; 178 179 /** 180 * @author Andrew Migal migal.drew@gmail.com 181 * @brief Integral image class (summed area table). 182 * @details Integral image is a table for fast computing the sum of 183 * values in rectangular subarea. In more detail, for 2-dimensional array 184 * of numbers this class provides capability to get sum of values in 185 * rectangular arbitrary area with any size in constant time. 186 * Integral image is constructed from grayscale picture. 187 */ 188 class GDALIntegralImage 189 { 190 CPL_DISALLOW_COPY_ASSIGN(GDALIntegralImage) 191 192 public: 193 GDALIntegralImage(); 194 virtual ~GDALIntegralImage(); 195 196 /** 197 * Compute integral image for specified array. Result is stored internally. 198 * 199 * @param padfImg Pointer to 2-dimensional array of values 200 * @param nHeight Number of rows in array 201 * @param nWidth Number of columns in array 202 */ 203 void Initialize(const double **padfImg, int nHeight, int nWidth); 204 205 /** 206 * Fetch value of specified position in integral image. 207 * 208 * @param nRow Row of this position 209 * @param nCol Column of this position 210 * 211 * @return Value in specified position or zero if parameters are out of range. 212 */ 213 double GetValue(int nRow, int nCol); 214 215 /** 216 * Get sum of values in specified rectangular grid. Rectangle is constructed 217 * from left top point. 218 * 219 * @param nRow Row of left top point of rectangle 220 * @param nCol Column of left top point of rectangle 221 * @param nWidth Width of rectangular area (number of columns) 222 * @param nHeight Height of rectangular area (number of rows) 223 * 224 * @return Sum of values in specified grid. 225 */ 226 double GetRectangleSum(int nRow, int nCol, int nWidth, int nHeight); 227 228 /** 229 * Get value of horizontal Haar wavelet in specified square grid. 230 * 231 * @param nRow Row of left top point of square 232 * @param nCol Column of left top point of square 233 * @param nSize Side of the square 234 * 235 * @return Value of horizontal Haar wavelet in specified square grid. 236 */ 237 double HaarWavelet_X(int nRow, int nCol, int nSize); 238 239 /** 240 * Get value of vertical Haar wavelet in specified square grid. 241 * 242 * @param nRow Row of left top point of square 243 * @param nCol Column of left top point of square 244 * @param nSize Side of the square 245 * 246 * @return Value of vertical Haar wavelet in specified square grid. 247 */ 248 double HaarWavelet_Y(int nRow, int nCol, int nSize); 249 250 /** 251 * Fetch height of integral image. 252 * 253 * @return Height of integral image (number of rows). 254 */ 255 int GetHeight(); 256 257 /** 258 * Fetch width of integral image. 259 * 260 * @return Width of integral image (number of columns). 261 */ 262 int GetWidth(); 263 264 private: 265 double **pMatrix = nullptr; 266 int nWidth = 0; 267 int nHeight = 0; 268 }; 269 270 /** 271 * @author Andrew Migal migal.drew@gmail.com 272 * @brief Class for computation and storage of Hessian values in SURF-based algorithm. 273 * 274 * @details SURF-based algorithm normally uses this class for searching 275 * feature points on raster images. Class also contains traces of Hessian matrices 276 * to provide fast computations. 277 */ 278 class GDALOctaveLayer 279 { 280 CPL_DISALLOW_COPY_ASSIGN(GDALOctaveLayer) 281 282 public: 283 GDALOctaveLayer(); 284 285 /** 286 * Create instance with provided parameters. 287 * 288 * @param nOctave Number of octave which contains this layer 289 * @param nInterval Number of position in octave 290 * 291 * @note Normally constructor is invoked only by SURF-based algorithm. 292 */ 293 GDALOctaveLayer(int nOctave, int nInterval); 294 virtual ~GDALOctaveLayer(); 295 296 /** 297 * Perform calculation of Hessian determinants and their signs 298 * for specified integral image. Result is stored internally. 299 * 300 * @param poImg Integral image object, which provides all necessary 301 * data for computation 302 * 303 * @note Normally method is invoked only by SURF-based algorithm. 304 */ 305 void ComputeLayer(GDALIntegralImage *poImg); 306 307 /** 308 * Octave which contains this layer (1,2,3...) 309 */ 310 int octaveNum; 311 /** 312 * Length of the side of filter 313 */ 314 int filterSize; 315 /** 316 * Length of the border 317 */ 318 int radius; 319 /** 320 * Scale for this layer 321 */ 322 int scale; 323 /** 324 * Image width in pixels 325 */ 326 int width; 327 /** 328 * Image height in pixels 329 */ 330 int height; 331 /** 332 * Hessian values for image pixels 333 */ 334 double **detHessians; 335 /** 336 * Hessian signs for speeded matching 337 */ 338 int **signs; 339 }; 340 341 /** 342 * @author Andrew Migal migal.drew@gmail.com 343 * @brief Class for handling octave layers in SURF-based algorithm. 344 * @details Class contains OctaveLayers and provides capability to construct octave space and distinguish 345 * feature points. Normally this class is used only by SURF-based algorithm. 346 */ 347 class GDALOctaveMap 348 { 349 CPL_DISALLOW_COPY_ASSIGN( GDALOctaveMap ) 350 351 public: 352 /** 353 * Create octave space. Octave numbers are start with one. (1, 2, 3, 4, ... ) 354 * 355 * @param nOctaveStart Number of bottom octave 356 * @param nOctaveEnd Number of top octave. Should be equal or greater than OctaveStart 357 */ 358 GDALOctaveMap(int nOctaveStart, int nOctaveEnd); 359 virtual ~GDALOctaveMap(); 360 361 /** 362 * Calculate Hessian values for octave space 363 * (for all stored octave layers) using specified integral image 364 * @param poImg Integral image instance which provides necessary data 365 * @see GDALOctaveLayer 366 */ 367 void ComputeMap(GDALIntegralImage *poImg); 368 369 /** 370 * Method makes decision that specified point 371 * in middle octave layer is maximum among all points 372 * from 3x3x3 neighbourhood (surrounding points in 373 * bottom, middle and top layers). Provided layers should be from the same octave's interval. 374 * Detects feature points. 375 * 376 * @param row Row of point, which is candidate to be feature point 377 * @param col Column of point, which is candidate to be feature point 378 * @param bot Bottom octave layer 379 * @param mid Middle octave layer 380 * @param top Top octave layer 381 * @param threshold Threshold for feature point recognition. Detected feature point 382 * will have Hessian value greater than this provided threshold. 383 * 384 * @return TRUE if candidate was evaluated as feature point or FALSE otherwise. 385 */ 386 static bool PointIsExtremum(int row, int col, GDALOctaveLayer *bot, 387 GDALOctaveLayer *mid, GDALOctaveLayer *top, double threshold); 388 389 /** 390 * 2-dimensional array of octave layers 391 */ 392 GDALOctaveLayer ***pMap; 393 394 /** 395 * Value for constructing internal octave space 396 */ 397 static const int INTERVALS = 4; 398 399 /** 400 * Number of bottom octave 401 */ 402 int octaveStart; 403 404 /** 405 * Number of top octave. Should be equal or greater than OctaveStart 406 */ 407 int octaveEnd; 408 }; 409 410 /** 411 * @author Andrew Migal migal.drew@gmail.com 412 * @brief Class for searching corresponding points on images. 413 * @details Provides capability for detection feature points 414 * and finding equal points on different images. 415 * Class implements simplified version of SURF algorithm (Speeded Up Robust Features). 416 * As original, this realization is scale invariant, but sensitive to rotation. 417 * Images should have similar rotation angles (maximum difference is up to 10-15 degrees), 418 * otherwise algorithm produces incorrect and very unstable results. 419 */ 420 421 class GDALSimpleSURF 422 { 423 private: 424 /** 425 * Class stores indexes of pair of point 426 * and distance between them. 427 */ 428 class MatchedPointPairInfo 429 { 430 public: MatchedPointPairInfo(int nInd_1,int nInd_2,double dfDist)431 MatchedPointPairInfo(int nInd_1, int nInd_2, double dfDist): 432 ind_1(nInd_1), ind_2(nInd_2), euclideanDist(dfDist) {} 433 434 int ind_1; 435 int ind_2; 436 double euclideanDist; 437 }; 438 439 CPL_DISALLOW_COPY_ASSIGN( GDALSimpleSURF ) 440 441 public: 442 /** 443 * Prepare class according to specified parameters. Octave numbers affects 444 * to amount of detected points and their robustness. 445 * Range between bottom and top octaves also affects to required time of detection points 446 * (if range is large, algorithm should perform more operations). 447 * @param nOctaveStart Number of bottom octave. Octave numbers starts with one 448 * @param nOctaveEnd Number of top octave. Should be equal or greater than OctaveStart 449 * 450 * @note 451 * Every octave finds points with specific size. For small images 452 * use small octave numbers, for high resolution - large. 453 * For 1024x1024 images it's normal to use any octave numbers from range 1-6. 454 * (for example, octave start - 1, octave end - 3, or octave start - 2, octave end - 2.) 455 * For larger images, try 1-10 range or even higher. 456 * Pay attention that number of detected point decreases quickly per octave 457 * for particular image. Algorithm finds more points in case of small octave numbers. 458 * If method detects nothing, reduce bottom bound of octave range. 459 * 460 * NOTICE that every octave requires time to compute. Use a little range 461 * or only one octave if execution time is significant. 462 */ 463 GDALSimpleSURF(int nOctaveStart, int nOctaveEnd); 464 virtual ~GDALSimpleSURF(); 465 466 /** 467 * Convert image with RGB channels to grayscale using "luminosity" method. 468 * Result is used in SURF-based algorithm, but may be used anywhere where 469 * grayscale images with nice contrast are required. 470 * 471 * @param red Image's red channel 472 * @param green Image's green channel 473 * @param blue Image's blue channel 474 * @param nXSize Width of initial image 475 * @param nYSize Height of initial image 476 * @param padfImg Array for resulting grayscale image 477 * @param nHeight Height of resulting image 478 * @param nWidth Width of resulting image 479 * 480 * @return CE_None or CE_Failure if error occurs. 481 */ 482 static CPLErr ConvertRGBToLuminosity( 483 GDALRasterBand *red, 484 GDALRasterBand *green, 485 GDALRasterBand *blue, 486 int nXSize, int nYSize, 487 double **padfImg, int nHeight, int nWidth); 488 489 /** 490 * Find feature points using specified integral image. 491 * 492 * @param poImg Integral image to be used 493 * @param dfThreshold Threshold for feature point recognition. Detected feature point 494 * will have Hessian value greater than this provided threshold. 495 * 496 * @note Typical threshold's value is 0,001. But this value 497 * can be various in each case and depends on image's nature. 498 * For example, value can be 0.002 or 0.005. 499 * Fill free to experiment with it. 500 * If threshold is high, than number of detected feature points is small, 501 * and vice versa. 502 */ 503 std::vector<GDALFeaturePoint>* 504 ExtractFeaturePoints(GDALIntegralImage *poImg, double dfThreshold); 505 506 /** 507 * Find corresponding points (equal points in two collections). 508 * 509 * @param poMatchPairs Resulting collection for matched points 510 * @param poFirstCollect Points on the first image 511 * @param poSecondCollect Points on the second image 512 * @param dfThreshold Value from 0 to 1. Threshold affects to number of 513 * matched points. If threshold is higher, amount of corresponding 514 * points is larger, and vice versa 515 * 516 * @note Typical threshold's value is 0,1. BUT it's a very approximate guide. 517 * It can be 0,001 or even 1. This threshold provides direct adjustment 518 * of point matching. 519 * NOTICE that if threshold is lower, matches are more robust and correct, but 520 * number of matched points is smaller. Therefore if algorithm performs many 521 * false detections and produces bad results, reduce threshold. Otherwise, if 522 * algorithm finds nothing, increase threshold. 523 * 524 * @return CE_None or CE_Failure if error occurs. 525 */ 526 static CPLErr MatchFeaturePoints( 527 std::vector<GDALFeaturePoint*> *poMatchPairs, 528 std::vector<GDALFeaturePoint> *poFirstCollect, 529 std::vector<GDALFeaturePoint> *poSecondCollect, 530 double dfThreshold); 531 532 private: 533 /** 534 * Compute euclidean distance between descriptors of two feature points. 535 * It's used in comparison and matching of points. 536 * 537 * @param firstPoint First feature point to be compared 538 * @param secondPoint Second feature point to be compared 539 * 540 * @return Euclidean distance between descriptors. 541 */ 542 static double GetEuclideanDistance( 543 GDALFeaturePoint &firstPoint, GDALFeaturePoint &secondPoint); 544 545 /** 546 * Set provided distance values to range from 0 to 1. 547 * 548 * @param poList List of distances to be normalized 549 */ 550 static void NormalizeDistances(std::list<MatchedPointPairInfo> *poList); 551 552 /** 553 * Compute descriptor for specified feature point. 554 * 555 * @param poPoint Feature point instance 556 * @param poImg image where feature point was found 557 */ 558 static void SetDescriptor(GDALFeaturePoint *poPoint, GDALIntegralImage *poImg); 559 560 private: 561 int octaveStart; 562 int octaveEnd; 563 GDALOctaveMap *poOctMap; 564 }; 565 566 #endif /* GDALSIMPLESURF_H_ */ 567