Interest operator

Image with distinctive points (red crosses). The Harris Corner Detector was used

In the field of image processing, interest operators are algorithms that extract prominent points in images and at the same time supply one or more parameters. Distinctive places are those points that are as unique as possible in a limited environment. The interior of linear edges does not belong to the distinctive points, see edge detection . Further requirements for interest operators are the invariance to image changes such as geometric and radiometric distortions (e.g. rotations, scaling), the insensitivity to noise and interpretability (suitable for further image analysis).

The result of the search for prominent points is used, for example, to calculate the epipolar geometry between two cameras or for image-based tracking .

Well-known interest operators are the Moravec operator, the Plessy point detector (mostly Harris Corner Detector ), the FAST operator ( features from accelerated segment test ) and the Förstner operator.

Moravec operator

The Moravec operator was introduced by Hans Moravec in 1977. It calculates the mean quadratic gradient sums in the four main directions of the window of size . ${\displaystyle k\times l}$

${\displaystyle V_{1}={\frac {1}{p(q-1)}}\sum _{i=-k}^{k}\sum _{j=-l}^{l-1}{\bigl (}g(i,j)-g(i,j+1){\bigr )}^{2}}$

${\displaystyle V_{2}={\frac {1}{(p-1)q}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l}{\bigl (}g(i,j)-g(i+1,j){\bigr )}^{2}}$

${\displaystyle V_{3}={\frac {1}{(p-1)(q-1)}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l-1}{\bigl (}g(i,j)-g(i+1,j+1){\bigr )}^{2}}$

${\displaystyle V_{4}={\frac {1}{(p-1)(q-1)}}\sum _{i=-k}^{k-1}\sum _{j=-l}^{l-1}{\bigl (}g(i,j+1)-g(i+1,j){\bigr )}^{2}}$

${\displaystyle V=\min(V_{1},V_{2},V_{3},V_{4})}$

with and . ${\displaystyle p=2k+1}$ ${\displaystyle q=2l+1}$

If the value is above a certain threshold, there is a prominent point. The Moravec operator is very easy to implement and requires little computing time. However, it is not rotationally invariant and its accuracy is only 1 pixel.

Harris Corner Detector

The Harris Corner Detector (seldom called Plessy Point Detector) was introduced in 1988 by Harris and Stephens. They described an improvement of the Moravec operator by solving the discrete displacements and directions with the help of the autocorrelation function and thus also increasing the accuracy of the localization.

The autocorrelation matrix is calculated by summing the derivative of the image function in the area around a point: ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle \Omega }$

${\displaystyle A={\begin{bmatrix}\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)^{2}&\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)\cdot f_{y}(i,j)\\\sum \limits _{(i,j)\in \Omega }f_{x}(i,j)\cdot f_{y}(i,j)&\sum \limits _{(i,j)\in \Omega }f_{y}(i,j)^{2}\\\end{bmatrix}}.}$

${\displaystyle f_{x}}$and are the partial derivatives of the image function . ${\displaystyle f_{y}}$ ${\displaystyle f}$

${\displaystyle A}$describes the neighborhood structure around the place . Their rank differs depending on the property of the environment: ${\displaystyle (x,y)}$

Rank 2: There is a prominent point.

Rank 1: There is a straight edge.

Rank 0: There is a homogeneous, unstructured surface.

The eigenvalues of give a description of the neighborhood structure that is rotationally invariant. The eigenvalues ​​are proportional to the gray value changes in the image along the main directions (corresponds to the direction of the eigenvectors ). Because of these properties, the eigenvalues ​​are ideally suited to assess the neighborhood structure. An analysis of the parameter space basically reveals three cases that can be distinguished: ${\displaystyle \lambda _{1},\lambda _{2}}$ ${\displaystyle A}$

• a) If both eigenvalues ​​are small, then the gray value changes along the main directions are also small, ie the gray values ​​are constant in the area. This means that the local autocorrelation function is flat.
• b) If one eigenvalue is large and the other small, then there is a local autocorrelation function that shows a clear edge. The large eigenvalue indicates a large change in gray value perpendicular to the edge, whereas the small eigenvalue along the edge indicates no or only slight change in the gray values.
• c) If both eigenvalues ​​are large, i.e. the gray value changes in both directions are also large, the local autocorrelation function looks like a sharp mountain peak. It is therefore a corner point.

In order to be able to carry out a classification to differentiate the cases a) to c), a function based on the eigenvalues ​​is required, which shows the point strength. In order to avoid the eigenvalue decomposition of the matrix , the following relationships can be used: ${\displaystyle A}$

${\displaystyle \det(A)=\lambda _{1}\cdot \lambda _{2}}$

${\displaystyle \operatorname {spur} (A)=\lambda _{1}+\lambda _{2}}$

This means that the point strength can now be calculated directly using the formula ${\displaystyle V}$ ${\displaystyle A}$

${\displaystyle V=\det(A)-k\operatorname {spur} (A)^{2}}$

be calculated. In order to separate the edges from prominent points, is selected. In this way, positive values ​​are obtained for points and negative values ​​for edges. A local non-maxima suppression finally supplies the position of the interest point. ${\displaystyle k=0{,}04}$

Forstner operator

The Förstner operator regards the task as a comparison of two image sections of the same size that are shifted against each other and are noisy. This is formulated using a least-squares adjustment in the Gauss-Markoff model. The formal solution is obtained by setting up a system of normal equations and inverting the system of equations. The trick here is that you are not interested in the solution of the normal equation system, but only want to estimate the precision with which you can assign the two image sections. To do this, one calculates the covariance matrix . Furthermore, when considering the corresponding normal equations, it turns out that the normal equation matrix is identical to the autocorrelation matrix . ${\displaystyle C={\widehat {\sigma }}_{\Delta g}^{2}\cdot N^{-1}}$ ${\displaystyle N}$ ${\displaystyle A}$

The covariance matrix thus indicates how precisely the position of the interest point can be determined. This can be visualized by means of an error ellipse . The semi-axes of the error ellipse correspond to the eigenvectors and eigenvalues ​​of the covariance matrix. Large gradients in (corresponds to a large change in the gray values ​​in the image) accordingly lead to small variances or covariances in and thus to more precise determinability. A good point of interest is when the error ellipse is as small as possible and as round as possible. In contrast to this, the error ellipse has a very small and a very large semi-axis ( small, large) along a pronounced gray value edge, so the point would be well determined perpendicular to the edge, but poorly determined along the edge. ${\displaystyle C}$ ${\displaystyle {\tilde {\lambda }}_{1},{\tilde {\lambda }}_{2}}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle {\tilde {\lambda }}_{1}}$ ${\displaystyle {\tilde {\lambda }}_{2}}$

The eigenvalues ​​of the coefficient matrix are also identical to the reciprocal eigenvalues ​​of . This can be used advantageously to avoid the inversion of or . The length of the semiaxes of the error ellipse are then inversely proportional to the eigenvalues of . ${\displaystyle Q=N^{-1}}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle A}$ ${\displaystyle \lambda _{1},\lambda _{2}}$ ${\displaystyle N}$

To assess the point of interest, Förstner has defined two dimensions: weight and roundness . ${\displaystyle w}$ ${\displaystyle q}$

The weight is calculated as follows:

${\displaystyle w={\frac {1}{\operatorname {spur} (A^{-1})}}={\frac {\det(A)}{\operatorname {spur} (A)}}={\frac {\lambda _{1}\lambda _{2}}{\lambda _{1}+\lambda _{2}}}}$.

It is inversely proportional to the size of the error ellipse, that is, a small error ellipse gives a large weight. And the roundness is:

${\displaystyle q=1-\left({\frac {\lambda _{1}-\lambda _{2}}{\lambda _{1}+\lambda _{2}}}\right)^{2}={\frac {4\det(A)}{\operatorname {spur} (A)^{2}}}={\frac {4\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})^{2}}}.}$

The range of values ​​for is between 0 and 1 ( is exactly circular). Given by the formulas can be and one hand without inversion of or on the other hand without eigenvalue decomposition of charge. ${\displaystyle q}$ ${\displaystyle q=1,0}$ ${\displaystyle w}$ ${\displaystyle q}$ ${\displaystyle A}$ ${\displaystyle A}$

The suitability of an interest point can be assessed using these two parameters:

1. Distinctive points have small, circular ellipses (corresponds to great weight and roundness close to 1).
2. Straight edges can be detected by elongated fault ellipses (corresponds to a small roundness).
3. Large ellipses (corresponds to a small weight) indicate an unstructured, uniform surface.

A convolution kernel with a window size of 5 × 5 or 7 × 7 pixels is recommended for practical implementation. As a rule of thumb for an interest point, you can specify the roundness . The Forstner operator is not very sensitive to changes in . The specification is more difficult because it depends on the image contrast. One method is to select percent of the points with the largest values, e.g. B. of all points (which meet the condition ) the 10% with the greatest . Alternatively, a threshold value can be calculated from the mean value of all over the entire image. The value of is also the "strength" of the interest point. ${\displaystyle q>0{,}8}$ ${\displaystyle q}$ ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle q}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$

In addition, it is necessary to carry out a local non-maximum suppression.

Also of Förstner Although the image information is present only in the pixel grid, an interpolated version of the operator can be evaluated for a continuum of positions and thereby a (corner or Zentrums-) point to be localized with subpixel accuracy: the calculation of the subpixel Interestpunktes described.

software

• Corner detection in Scikit-image (Python)
• Feature detection in OpenCV (C ++, Python)

Individual evidence

1. ^ OpenCV: FAST Algorithm for Corner Detection. Retrieved December 12, 2018 . 
2. ^ HP Moravec: Towards Automatic Visual Obstacle Avoidance . In: Proceedings of the 5th International Joint Conference on Artificial Intelligence . 1977, p. 584 .
3. ^ ^{A b} C. Harris and M. Stephens: A combined corner and edge detector . In: Proceedings of the 4th Alvey Vision Conference . 1988, p. 147–151 ( semanticscholar.org [PDF]).
4. ↑ OpenCV tutorial
5. ↑ Volker Rodehorst, Andreas Koschan: Comparison and Evaluation of Feature Point Detectors. 2006, accessed on July 6, 2020 . 
6. ↑ Wolfgang Förstner and E. Gülch: A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centers of Circular Features . In: Proceedings of the ISPRS Intercommission Workshop on Fast Processing of Photogrammetric Data . 1987, p. 281-305 .
7. ↑ ^{a b} Wolfgang Förstner: Statistical procedures for automatic image analysis and their evaluation in object recognition and measurement (habilitation) . In: German Geodetic Commission at the Bavarian Academy of Sciences (Hrsg.): DGK . Series C - Dissertations, Issue No. 370 . Munich 1991 ( uni-bonn.de [PDF]).
8. ↑ ^{a b} Wolfgang Förstner: A Feature Based Correspondence Algorithm For Image Matching. In: International Archive of Photogrammetry. 1986, accessed July 4, 2020 .