Harris Affine Region Detector - Computation and Implementation

Computation and Implementation

The computational complexity of the Harris-Affine detector is broken into two parts: initial point detection and affine region normalization. The initial point detection algorithm, Harris-Laplace, has complexity where is the number of pixels in the image. The affine region normalization algorithm automatically detects the scale and estimates the shape adaptation matrix, . This process has complexity, where is the number of initial points, is the size of the search space for the automatic scale selection and is the number of iterations required to compute the matrix.

Some methods exist to reduce the complexity of the algorithm at the expense of accuracy. One method is to eliminate the search in the differentiation scale step. Rather than choose a factor from a set of factors, the sped-up algorithm chooses the scale to be constant across iterations and points: . Although this reduction in search space might decrease the complexity, this change can severely effect the convergence of the matrix.