Förstner-Harris

The Förstner-Harris algorithm (HS88,FG87) was specifically designed to provide high geometric stability for keypoints. The underlying idea is to find points for which a small translation of the neighborhood produces a significant change in the least-squares error between the original window and its translated version. The algorithm has been so successful because it characterizes changes in image intensity around a point using the structure tensor (autocorrelation matrix), constructed from the first derivatives of the image.

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

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 a neighborhood of $(x,y)$ and $w(\boldsymbol\delta)$ is an optional kernel, usually either a Gaussian centered at $(x,y)$, which allows points in the neighborhood to be weighted differently, or a constant window over $\Omega$. Originally, $w(\boldsymbol\delta)$ were very small filters, but as computing power has increased, progressively larger Gaussian kernels have been used.

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 content within the window around a given point.

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

If both eigenvalues are large, the point is a corner; if only one eigenvalue is large, it is an edge; otherwise, it lies in a reasonably flat region. In functional form, this can be expressed as

$$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 introduces 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$, usually set to $0.04$.

Figure 6.1: Response in the eigenvalue plane given by the Harris equation for different threshold values, with $\alpha =0.04$. The resulting region is very similar to that obtained with the Shi-Tomasi method, without requiring explicit computation of the eigenvalues.

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

Footnotes

...#tex2html_wrap_inline16570#^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 connection to gradient statistics), or the structure tensor, a term now widely used in more formal treatments.