Förstner-Harris

The Förstner-Harris algorithm (FG87,HS88) was explicitly designed to achieve high geometric stability. It defines as keypoints those points that have a local maximum when compared, in the least-squares sense, with their translated version. This algorithm has been so successful because it allows variations in image intensity in the neighborhood of a point to be detected using the autocorrelation matrix of the image's first derivatives.

Let the gradient images (which can be generated by a differential operator such as Sobel, Prewitt, or Roberts) $I_x(x,y)$ and $I_y(x,y)$ be, respectively, the horizontal and vertical gradients of the image being analyzed.

From these two images, it is possible to compute a function $\mathbf{C}(x,y)$^6.1 of the gradient images in a neighborhood of $(x,y)$, defined as

$$\mathbf{C}(x,y)=\begin{bmatrix} \sum_{\boldsymbol\delta \i... ...^2_y(\boldsymbol\delta) w(\boldsymbol\delta) \\ \end{bmatrix}$$ (6.3)

where $\boldsymbol\delta \in \Omega$ is the neighborhood of $(x,y)$ and $w(\boldsymbol\delta)$ is an optional kernel, usually either a Gaussian centered at $(x,y)$, to assign different weights to points in the neighborhood, or a constant window over $\Omega$. Originally, $w(\boldsymbol\delta)$ were very small filters, but as computing power increased, progressively larger Gaussian kernels came into use.

In practice, Harris uses two convolution filters: a derivative filter to compute the derivative images and an integration filter to compute the matrix elements. The size of these filters and the use of a Gaussian filter to weight the points are discussed in the following section on the scale at which features are detected.

The matrix $\mathbf{C}$ is the second-moment matrix. Keypoints can be detected by analyzing the eigenvalues $\lambda_0$ and $\lambda_1$ of the matrix $\mathbf{C}$ (see Section 2.9.1 for a more detailed discussion). The eigenvalues of the autocorrelation matrix $\mathbf{C}$ characterize the type of image contained in the window around the given point.

The matrix $\mathbf{C}$ therefore represents the local distribution of image gradients around the point under consideration. Its eigenvalues measure the intensity variation along two orthogonal directions and form the theoretical basis of the Harris and Shi-Tomasi operators and of the Kanade-Lucas-Tomasi tracker.

If two eigenvalues are very large, the point is a corner; if only one eigenvalue is large, it is an edge; otherwise, it is a reasonably flat region, or, in functional form,

$$C = \min( \lambda_0, \lambda_1 )$$ (6.4)

whose local maxima represent the corners detected by the Shi-Tomasi algorithm (ST94).

For a matrix $2 \times 2$, the eigenvalues are obtained as the solutions of the quadratic characteristic polynomial

$$p(x) = x^2 - \trace (\mathbf{C}) x + \det(\mathbf{C})$$ (6.5)

To avoid explicitly computing the eigenvalues of $\mathbf{C}$, Harris introduced an operator $H(x,y)$ defined as

$$H(x,y) = \det(\mathbf{C}) - \alpha \trace (\mathbf{C})^{2}$$ (6.6)

where $\alpha$ is a parameter between $0$ and $0.25$ and is usually set to $0.04$.

Figure 6.1: Response in the eigenvalue plane provided by the Harris equation for different threshold values, with $\alpha =0.04$. The region of interest is very similar to that provided by the Shi-Tomasi method, but without the need to explicitly compute the eigenvalues.

For Harris, the point $(x,y)$ is a keypoint (corner) if $H(x,y) > H_{thr}$, where $H_{thr}$ is a threshold to be defined. The parameter $\alpha$ controls the sensitivity of the feature detector. Qualitatively, increasing $\alpha$ removes edges, whereas increasing $H_{thr}$ removes flat regions (Figure 6.1).

Footnotes

...#tex2html_wrap_inline16566#^6.1

In the literature, this matrix is variously known as the autocorrelation matrix (especially in the original Harris context), the second-moment matrix (because of its relation to gradient statistics), or the structure tensor, a term now widely used in more formal treatments.