Monday, January 24, 2011

Star Feature Detector

Star Feature Detector is derived from CenSurE (Center Surrounded Extrema) detector. While CenSurE uses polygons such as Square, Hexagon and Octagons as a more computable alternative to circle. As far as I could tell, Star mimics the circle with 2 overlapping squares: 1 upright and 1 45-degree rotated. These polygons are bi-level. The can be seen as polygons with thick borders. The borders and the enclosed area have weights of opposing signs.

* It works in gray scale only *

  • Build Integral Image - Square and/or Slanted-variants (trapezoids). The slanted ones are used to compute polygon shaped filters.
  • Approximate LoG (Laplacian of Gaussian) with choice of the bi-level polygons. The outer strip and inner strip has opposing weights. It is supposed to produce zero DC value. Meaning the ratio of the weights should somehow be related to the area under the 2 levels.
  • Let m, n be parameters that defines of the inner region and outer boundary (thickness, sort-of).
  • A set of filters will be defined, based on the pairs of (m, n) values. (By experiment?)
  • Repeat the convolution on the same input image with each of the scaled filter. There will be no-subsampling, therefore no need to localize points from higher-scales.
  • Non Maxima Suppression
    • Feature corners are filter-response maximas in a 3x3x3 neighbors.
    • Eliminate weak feature points - with values below a filter response threshold.
  • Edge Suppression
    • Remove unstable points on edges by examining each feature corner with Harris measure under a 9x9 window. Eliminate points having the high ratio of the two highest Principle Curvatures, above a predefined threshold.
  • The CenSurE paper suggests to use improved Upright SURF: MU-SURF. That reduces the 'boundary effect' by making oversized masks when calculating Haars wavelet responses.
  • It also weighted the wavelet responses twice with Gaussian.
  • Shares the characteristics of SURF descriptors in terms of quick matching with +/- signs.
Sample (detector_simple) 

Parameters (by observation)
  • maxSize - choose the number of filters to be applied, the parameter value set the maximum size (last filter). Refer to icvStarDetectorComputeResponses():sizes0[] array.
  • responseThreshold - eliminate weak corners.
  • lineThresholds: maximum ratio between some factors that made up the Harris messure
    • lineThresholdProjected (first test) - Harris of responses
    • lineThresholdBinarized (second test) - Harris of sizes (refer to size1[]). Seems like size1 is simply a copy of size0 up to the max scale currently used.
    • Has to satisfy both tests to avoid elimination.
  • suppressNonMaxSize - window size (n-by-n) to apply the non-maximal suppression.
  • Detect fewer points on human faces with default parameters comparing to SURF/SIFT. Fewer on the hair. (line-suppression?)
  • maxSize @ default value (45) detects the most points on Kobe's Picture. Not apply to all images. But the values towards both ends detects much fewer points.
  • responseThreshold - when threshold set to relatively high, only circular objects or good corners like 30-45 degrees (such as necklace pendants, polo-shirt collars) remains.
  • suppressNonMaxSize - increasing the window size remove feature points that are close to each other.
  • increase/decrease the lineThreshold pairs with the same ratio, seeing fewer/more points along the hairlines.
  • 572 points detected in 1 second (Obama portrait in original size)
  • CenSurE: Center Surround Extremas for Realtime Feature Detection and Matching.  Agrawal, Konolige and Blas.
  • Computer Vision and Graphics: Second International Conference, Iccvg ..., Part 2 edited by Leonard Bolc, Ryszard Tadeusiewicz, Leszek J. Chmielewski, Konrad Wojciechowski


  1. Have you a code where the star detector is used to compare two images?

  2. I uploaded the 'detector_simple.cpp' sample code to google-code. It might not compile on your OpenCV package because some custom API changes I made. But I am sure you could use this for reference. Quite simple, actually.

  3. there is any source code to view the result ?

  4. What feature detector most robust SURF, SIFT or STAR?