Corner detection or interest point detection is an approach used within computer vision systems to extract features and infer the contents of an image. Corner detection is frequently used in motion detection, tracking, image mosaicing, panorama stitching, 3D modelling and object recognition.

Formalization

A corner is defined as the intersection of two edges. An interest point is a point in an image which has a well-defined position and can be robustly detected. This means that an interest point can be a corner but it can also be, for example, an isolated point of local intensity maximum or minimum, line endings, or a point on a curve where the curvature is locally maximal. In practice, most so-called corner detection methods detect interest points in general rather than corners in particular. As a consequence, if only corners are to be detected it is necessary to do a local analysis of detected interest points to determine which of these are real corners.

Corner detectors are not usually very robust and often require expert supervision or large redundancies introduced to prevent the effect of individual errors from dominating the recognition task. The quality of a corner detector is often judged based on its ability to detect the same corner in multiple images, which are similar but not identical, for example having different lighting, translation, rotation and other transforms. A simple approach to corner detection in images is using correlation, but this gets very computationally expensive and suboptimal. An alternative approach used frequently is based on a method proposed by Harris and Stephens (below), which in turn is an improvement of a method by Moravec.

The Harris & Stephens corner detection algorithm

Without loss of generality, we will assume a grayscale 2-dimensional image is used. Let this image be given by $I(x,y)$

$\backslash nabla\; I(x,y)$ is the local gradient of the image and $\backslash nabla\; I(x,y)\; \backslash cdot\; n$ is the gradient along direction $n$. At a corner as we rotate $n$ through all possible values, we should find two directions where the gradient goes through a maximum.

$C\_n\; =\; \backslash frac\{\backslash begin\{vmatrix\}\; \backslash nabla\; I(x,y)\; \backslash cdot\; n\; \backslash end\{vmatrix\}\}\{\backslash begin\{Vmatrix\}\; n\; \backslash end\{Vmatrix\}\}$

$C\_n^2\; =\; \backslash frac\{n^T\; \backslash nabla\; I\; \backslash nabla\; I^T\; n\}\{n^T\; n\}$

where,

Just like in edge detection, we require that noise be eliminated from the images. This can be achieved by convolution with a Gaussian kernel or any appropriate alternative method. Let this smoothing operator be denoted by angle brackets and using the typical notation for partial derivatives, we get,

Note that $A$ is subtly different from the Hessian. Using this expression for A,

$C\_n^2\; =\; \backslash frac\{n^T\; A\; n\}\{n^T\; n\}$

which is the Rayleigh quotient and therefore is subject to the following bounds,

$\backslash lambda\_1\; \backslash le\; \backslash frac\{n^T\; A\; n\}\{n^T\; n\}\; \backslash le\; \backslash lambda\_2$

where $\backslash lambda\_1$ and $\backslash lambda\_2$ are the smallest and largest eigenvalues of the matrix A. This means as $n$ is varied through all possible values, $C\_n^2$ is restricted within these eigenvalue bounds. Based on the magnitudes of the eigenvalues, the following inferences can be made based on this argument:

1. If $\backslash lambda\_1\; \backslash approx\; 0$ and $\backslash lambda\_2\; \backslash approx\; 0$ then there are no features of interest at this pixel $(x,y)$.
2. If $\backslash lambda\_1\; \backslash approx\; 0$ and $\backslash lambda\_2$ is some large positive values, then an edge is found.
3. If $\backslash lambda\_1$ and $\backslash lambda\_2$ are both large, distinct positive values, then a corner is found.

Algorithms that implement this routine in practice usually look for a threshold in the following function $M\_c$, where $\backslash kappa$ is a tunable parameter which determines how 'edge-phobic' the algorithm is.

$M\_c\; =\; \backslash lambda\_1\; \backslash lambda\_2\; -\; \backslash kappa\; (\backslash lambda\_1\; +\; \backslash lambda\_2)^2$

$M\_c\; =\; \backslash operatorname\{det\}(A)\; -\; \backslash kappa\; \backslash ,\; \backslash operatorname\{trace\}^2(A)$

Therefore, the algorithm does not have to actually compute the eigenvalue decomposition of the matrix $A$ and instead it is sufficient to evaluate the determinant and trace of $A$ to find corners, or rather interest points in general.

The the value of $\backslash kappa$ has to be determined empirically, and in the literature values in the range 0.04 - 0.15 have been reported as feasible.

References

Computer vision | Image processing

角检测