Namespaces
Variants
Actions

Difference between revisions of "Corner detection"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 6 formulas out of 6 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 6 formulas, 6 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
A processing stage in computer vision algorithms, aimed at detecting and classifying the nature of junctions in the image domain. A main reason why corner detection is important is that junctions provide important cues to local three-dimensional scene structure [[#References|[a1]]].
 
A processing stage in computer vision algorithms, aimed at detecting and classifying the nature of junctions in the image domain. A main reason why corner detection is important is that junctions provide important cues to local three-dimensional scene structure [[#References|[a1]]].
  
 
The presumably most straightforward method for detecting corners is by intersecting nearby edges. While this approach may give reasonable results under simple conditions, it relies on [[Edge detection|edge detection]] as a pre-processing stage and suffers from inherent limitations. For example, not all corners arise from intersections of straight edges. In addition, edge detectors have problems at junctions.
 
The presumably most straightforward method for detecting corners is by intersecting nearby edges. While this approach may give reasonable results under simple conditions, it relies on [[Edge detection|edge detection]] as a pre-processing stage and suffers from inherent limitations. For example, not all corners arise from intersections of straight edges. In addition, edge detectors have problems at junctions.
  
One way of detecting junctions directly from image intensities consists of finding points at which the gradient magnitude <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202501.png" /> and the curvature of level curves <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202502.png" /> assume high values simultaneously [[#References|[a2]]], [[#References|[a3]]]. A special choice is to consider the product of the level curve curvature and the gradient magnitude raised to the power three. This is the smallest value of the exponent that leads to a polynomial expression for the [[Differential invariant|differential invariant]]
+
One way of detecting junctions directly from image intensities consists of finding points at which the gradient magnitude $| \nabla L |$ and the curvature of level curves $\kappa$ assume high values simultaneously [[#References|[a2]]], [[#References|[a3]]]. A special choice is to consider the product of the level curve curvature and the gradient magnitude raised to the power three. This is the smallest value of the exponent that leads to a polynomial expression for the [[Differential invariant|differential invariant]]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202503.png" /></td> </tr></table>
+
\begin{equation*} \tilde { \kappa } = \kappa | \nabla L | = L _ { y } ^ { 2 } L _ { x x } - 2 L _ { x } L _ { y } L _ { x y } + L _ { x } ^ { 2 } L _ { y y }. \end{equation*}
  
 
Moreover, spatial extrema of this operator are preserved under affine transformations in the image domain, which implies that corners with different opening angles are treated in a qualitatively similar way. Specifically, spatial maxima of the square of this operator are regarded as candidate corners [[#References|[a4]]], [[#References|[a5]]].
 
Moreover, spatial extrema of this operator are preserved under affine transformations in the image domain, which implies that corners with different opening angles are treated in a qualitatively similar way. Specifically, spatial maxima of the square of this operator are regarded as candidate corners [[#References|[a4]]], [[#References|[a5]]].
Line 13: Line 21:
 
Another class of corner detectors [[#References|[a6]]], [[#References|[a7]]] is based on second-moment matrices [[#References|[a5]]]:
 
Another class of corner detectors [[#References|[a6]]], [[#References|[a7]]] is based on second-moment matrices [[#References|[a5]]]:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202504.png" /></td> </tr></table>
+
\begin{equation*} \mu ( x ) = \left( \begin{array} { l l } { \mu _ { 11 } } &amp; { \mu _ { 12 } } \\ { \mu _ { 21 } } &amp; { \mu _ { 22 } } \end{array} \right) = \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202505.png" /></td> </tr></table>
+
\begin{equation*} = \int _ { \xi \in {\bf R} ^ { 2 } } \left( \begin{array} { c c } { L _ { x } ^ { 2 } } &amp; { L _ { x } L _ { y } } \\ { L _ { x } L _ { y } } &amp; { L _ { y } ^ { 2 } } \end{array} \right) g ( x - \xi ; s ) d x, \end{equation*}
  
 
and corner features are defined from local maxima in a strength measure such as
 
and corner features are defined from local maxima in a strength measure such as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120250/c1202506.png" /></td> </tr></table>
+
\begin{equation*} C = \frac { \operatorname { det } \mu } { \operatorname { trace } ^ { 2 } \mu } \text { or } C ^ { \prime } = \frac { \operatorname { det } \mu } { \operatorname { trace } \mu }. \end{equation*}
  
 
Also, this feature detector responds to local curvature properties of the intensity landscape [[#References|[a8]]].
 
Also, this feature detector responds to local curvature properties of the intensity landscape [[#References|[a8]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Malik,  "Interpreting line drawings of curved objects"  ''Internat. J. Computer Vision'' , '''1'''  (1987)  pp. 73–104</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Kitchen,  A. Rosenfeld,  "Gray-level corner detection"  ''Pattern Recognition Lett.'' , '''1''' :  2  (1982)  pp. 95–102</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.J. Koenderink,  W. Richards,  "Two-dimensional curvature operators"  ''J. Optical Soc. Amer.'' , '''5''' :  7  (1988)  pp. 1136–1141</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Blom,  "Topological and geometrical aspects of image structure"  ''PhD ThesisUtrecht Univ., Netherlands''  (1992)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T. Lindeberg,  "Scale-space theory in computer vision" , Kluwer Acad. Publ.  (1994)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  W. Förstner,  E. Gülch,  "A fast operator for detection and precise location of distinct points, corners and centres of circular features" , ''Proc. ISPRS Intercommission Workshop''  (1987)  pp. 149–155</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  C.G. Harris,  M. Stephens,  "A combined corner and edge detector." , ''Proc. 4th Alvey Vision Vision Conf.''  (1988)  pp. 147–151</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.A. Noble,  "Finding corners"  ''Image and Vision Computing'' , '''6''' :  2  (1988)  pp. 121–128</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  J. Malik,  "Interpreting line drawings of curved objects"  ''Internat. J. Computer Vision'' , '''1'''  (1987)  pp. 73–104</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  L. Kitchen,  A. Rosenfeld,  "Gray-level corner detection"  ''Pattern Recognition Lett.'' , '''1''' :  2  (1982)  pp. 95–102</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  J.J. Koenderink,  W. Richards,  "Two-dimensional curvature operators"  ''J. Optical Soc. Amer.'' , '''5''' :  7  (1988)  pp. 1136–1141</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  J. Blom,  "Topological and geometrical aspects of image structure"  ''PhD ThesisUtrecht Univ., Netherlands''  (1992)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  T. Lindeberg,  "Scale-space theory in computer vision" , Kluwer Acad. Publ.  (1994)</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  W. Förstner,  E. Gülch,  "A fast operator for detection and precise location of distinct points, corners and centres of circular features" , ''Proc. ISPRS Intercommission Workshop''  (1987)  pp. 149–155</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  C.G. Harris,  M. Stephens,  "A combined corner and edge detector." , ''Proc. 4th Alvey Vision Vision Conf.''  (1988)  pp. 147–151</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  J.A. Noble,  "Finding corners"  ''Image and Vision Computing'' , '''6''' :  2  (1988)  pp. 121–128</td></tr></table>

Latest revision as of 16:45, 1 July 2020

A processing stage in computer vision algorithms, aimed at detecting and classifying the nature of junctions in the image domain. A main reason why corner detection is important is that junctions provide important cues to local three-dimensional scene structure [a1].

The presumably most straightforward method for detecting corners is by intersecting nearby edges. While this approach may give reasonable results under simple conditions, it relies on edge detection as a pre-processing stage and suffers from inherent limitations. For example, not all corners arise from intersections of straight edges. In addition, edge detectors have problems at junctions.

One way of detecting junctions directly from image intensities consists of finding points at which the gradient magnitude $| \nabla L |$ and the curvature of level curves $\kappa$ assume high values simultaneously [a2], [a3]. A special choice is to consider the product of the level curve curvature and the gradient magnitude raised to the power three. This is the smallest value of the exponent that leads to a polynomial expression for the differential invariant

\begin{equation*} \tilde { \kappa } = \kappa | \nabla L | = L _ { y } ^ { 2 } L _ { x x } - 2 L _ { x } L _ { y } L _ { x y } + L _ { x } ^ { 2 } L _ { y y }. \end{equation*}

Moreover, spatial extrema of this operator are preserved under affine transformations in the image domain, which implies that corners with different opening angles are treated in a qualitatively similar way. Specifically, spatial maxima of the square of this operator are regarded as candidate corners [a4], [a5].

When implementing this corner detector in practice, the computation of the discrete derivative approximations are preceded by a Gaussian smoothing step (see Scale-space theory; Edge detection).

Another class of corner detectors [a6], [a7] is based on second-moment matrices [a5]:

\begin{equation*} \mu ( x ) = \left( \begin{array} { l l } { \mu _ { 11 } } & { \mu _ { 12 } } \\ { \mu _ { 21 } } & { \mu _ { 22 } } \end{array} \right) = \end{equation*}

\begin{equation*} = \int _ { \xi \in {\bf R} ^ { 2 } } \left( \begin{array} { c c } { L _ { x } ^ { 2 } } & { L _ { x } L _ { y } } \\ { L _ { x } L _ { y } } & { L _ { y } ^ { 2 } } \end{array} \right) g ( x - \xi ; s ) d x, \end{equation*}

and corner features are defined from local maxima in a strength measure such as

\begin{equation*} C = \frac { \operatorname { det } \mu } { \operatorname { trace } ^ { 2 } \mu } \text { or } C ^ { \prime } = \frac { \operatorname { det } \mu } { \operatorname { trace } \mu }. \end{equation*}

Also, this feature detector responds to local curvature properties of the intensity landscape [a8].

References

[a1] J. Malik, "Interpreting line drawings of curved objects" Internat. J. Computer Vision , 1 (1987) pp. 73–104
[a2] L. Kitchen, A. Rosenfeld, "Gray-level corner detection" Pattern Recognition Lett. , 1 : 2 (1982) pp. 95–102
[a3] J.J. Koenderink, W. Richards, "Two-dimensional curvature operators" J. Optical Soc. Amer. , 5 : 7 (1988) pp. 1136–1141
[a4] J. Blom, "Topological and geometrical aspects of image structure" PhD ThesisUtrecht Univ., Netherlands (1992)
[a5] T. Lindeberg, "Scale-space theory in computer vision" , Kluwer Acad. Publ. (1994)
[a6] W. Förstner, E. Gülch, "A fast operator for detection and precise location of distinct points, corners and centres of circular features" , Proc. ISPRS Intercommission Workshop (1987) pp. 149–155
[a7] C.G. Harris, M. Stephens, "A combined corner and edge detector." , Proc. 4th Alvey Vision Vision Conf. (1988) pp. 147–151
[a8] J.A. Noble, "Finding corners" Image and Vision Computing , 6 : 2 (1988) pp. 121–128
How to Cite This Entry:
Corner detection. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Corner_detection&oldid=12237
This article was adapted from an original article by Tony Lindeberg (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article