Namespaces
Variants
Actions

Difference between revisions of "Hough transformation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
h1103201.png
 +
$#A+1 = 39 n = 0
 +
$#C+1 = 39 : ~/encyclopedia/old_files/data/H110/H.1100320 Hough transformation
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
An approach to detect straight lines (or curves) in an image (a picture), by applying a coordinate transformation to the image such that all the points belonging to a line (or a curve) are mapped into a single point in the transformed space.
 
An approach to detect straight lines (or curves) in an image (a picture), by applying a coordinate transformation to the image such that all the points belonging to a line (or a curve) are mapped into a single point in the transformed space.
  
The method to detect lines may be explained as follows [[#References|[a2]]]. The set of all straight lines in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103201.png" />-image plane gives rise to a two-parameter family. When using the normal parametrization (cf. also [[Normal equation|Normal equation]]), the equation of a line is given by
+
The method to detect lines may be explained as follows [[#References|[a2]]]. The set of all straight lines in the $  ( x,y ) $-
 +
image plane gives rise to a two-parameter family. When using the normal parametrization (cf. also [[Normal equation|Normal equation]]), the equation of a line is given by
  
<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/h/h110/h110320/h1103202.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$ \tag{a1 }
 +
x  \cos  \theta + y  \sin  \theta = \rho,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103203.png" /> is the oriented angle of the [[Normal|normal]] onto the line, and where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103204.png" /> is the algebraic distance of the line from the origin. Restricting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103205.png" /> to the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103206.png" />, the normal parameters for a line are unique. Taking the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103207.png" />-space as the transformed space, every line in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103208.png" />-plane corresponds to a unique point in the transformed space (in the original Hough-transform method the slope-intercept representation of a line, namely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h1103209.png" />, was used, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032010.png" />-space was the transformed space; as both the slope and the intercept may become infinite, the technique is more involved, [[#References|[a3]]]).
+
where $  \theta $
 +
is the oriented angle of the [[Normal|normal]] onto the line, and where $  \rho $
 +
is the algebraic distance of the line from the origin. Restricting $  \theta $
 +
to the interval $  [ 0, \pi ] $,
 +
the normal parameters for a line are unique. Taking the $  ( \theta, \rho ) $-
 +
space as the transformed space, every line in the $  ( x,y ) $-
 +
plane corresponds to a unique point in the transformed space (in the original Hough-transform method the slope-intercept representation of a line, namely $  y = mx + b $,  
 +
was used, and the $  ( m,b ) $-
 +
space was the transformed space; as both the slope and the intercept may become infinite, the technique is more involved, [[#References|[a3]]]).
  
Taking now a fixed point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032011.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032012.png" />-plane, this point gives rise in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032013.png" />-space to a curve defined by
+
Taking now a fixed point $  ( x _ {i} ,y _ {i} ) $
 +
in the $  ( x,y ) $-
 +
plane, this point gives rise in the $  ( \theta, \rho ) $-
 +
space to a curve defined by
  
<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/h/h110/h110320/h11032014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
$$ \tag{a2 }
 +
\rho = x _ {i}  \cos  \theta + y _ {i}  \sin  \theta.
 +
$$
  
Clearly, when one has a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032015.png" /> of picture points that are collinear in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032016.png" />-plane, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032017.png" /> curves in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032018.png" />-space corresponding to these points according to (a2) have a common point of intersection, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032019.png" />. Writing (a1) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032021.png" />, one obtains the equation of a line in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032022.png" />-plane passing through the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032023.png" /> points.
+
Clearly, when one has a set $  \{ ( x _ {1} ,y _ {1} ) \dots ( x _ {n} ,y _ {n} ) \} $
 +
of picture points that are collinear in the $  ( x,y ) $-
 +
plane, the $  n $
 +
curves in the $  ( \theta, \rho ) $-
 +
space corresponding to these points according to (a2) have a common point of intersection, say $  ( \theta _ {s} , \rho _ {s} ) $.  
 +
Writing (a1) with $  \theta \equiv \theta _ {s} $
 +
and $  \rho \equiv \rho _ {s} $,  
 +
one obtains the equation of a line in the $  ( x,y ) $-
 +
plane passing through the $  n $
 +
points.
  
Having now a digital picture in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032024.png" />-plane, and mapping all these points to their corresponding curves in the parameter space, collinear subsets of picture points can be found by searching coincident points of intersection in the parameter space. In practice this is done by quantizing both parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032026.png" />, and treating the quantized region as a two-dimensional array of accumulators. For each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032027.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032028.png" />-picture plane, the curve corresponding to it by (a2) gives rise to incrementing the count in some cells of the array. After all picture points have been treated, the array is inspected to find cells having high counts. When in some cell <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032029.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032030.png" /> counts, then the line with normal parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032031.png" /> passes (approximately) through <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032032.png" /> picture points.
+
Having now a digital picture in the $  ( x,y ) $-
 +
plane, and mapping all these points to their corresponding curves in the parameter space, collinear subsets of picture points can be found by searching coincident points of intersection in the parameter space. In practice this is done by quantizing both parameters $  \theta $
 +
and $  \rho $,  
 +
and treating the quantized region as a two-dimensional array of accumulators. For each point $  ( x _ {i} ,y _ {i} ) $
 +
in the $  ( x,y ) $-
 +
picture plane, the curve corresponding to it by (a2) gives rise to incrementing the count in some cells of the array. After all picture points have been treated, the array is inspected to find cells having high counts. When in some cell $  ( \theta _ {a} , \rho _ {b} ) $
 +
there are $  m $
 +
counts, then the line with normal parameters $  ( \theta _ {a} , \rho _ {b} ) $
 +
passes (approximately) through $  m $
 +
picture points.
  
The Hough-transform method as explained above to detect straight lines in a picture can, in principle, be generalized to detect analytic curves involving more than two parameters. For instance, as the equation of a circle in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032033.png" />-plane is given by
+
The Hough-transform method as explained above to detect straight lines in a picture can, in principle, be generalized to detect analytic curves involving more than two parameters. For instance, as the equation of a circle in the $  ( x,y ) $-
 +
plane is given by
  
<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/h/h110/h110320/h11032034.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
$$ \tag{a3 }
 +
( x - a )  ^ {2} + ( y - b ) ^ {2} = r  ^ {2} ,
 +
$$
  
a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032035.png" /> on that circle determines a subset of the three-dimensional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032036.png" />-parameter space. When a number of picture points are arranged on a circle with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032037.png" />, the corresponding subsets in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032038.png" />-parameter space will intersect at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110320/h11032039.png" />, and this point may be detected by using a three-dimensional array. As methods to detect curves in a picture are usually applied to find out if edge points are situated on a particular curve, it is often possible to reduce the number of points to be checked, while also the use of directional information may reduce the computational burden [[#References|[a1]]].
+
a point $  ( x _ {i} ,y _ {i} ) $
 +
on that circle determines a subset of the three-dimensional $  ( a,b,r ) $-
 +
parameter space. When a number of picture points are arranged on a circle with parameters $  ( a _ {0} ,b _ {0} ,r _ {0} ) $,  
 +
the corresponding subsets in the $  ( a,b,r ) $-
 +
parameter space will intersect at the point $  ( a _ {0} ,b _ {0} ,r _ {0} ) $,  
 +
and this point may be detected by using a three-dimensional array. As methods to detect curves in a picture are usually applied to find out if edge points are situated on a particular curve, it is often possible to reduce the number of points to be checked, while also the use of directional information may reduce the computational burden [[#References|[a1]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.H. Ballard,  "Generalizing the Hough transform to detect arbitrary shapes"  ''Pattern Recognition'' , '''13'''  (1981)  pp. 111–122</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Bässmann,  PH.W. Besslich,  "Konturorientierte Verfahren in der digitalen Bildverarbeitung" , Springer  (1989)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Rosenfeld,  A.C Kak,  "Digital picture processing" , '''2''' , Acad. Press  (1982)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.H. Ballard,  "Generalizing the Hough transform to detect arbitrary shapes"  ''Pattern Recognition'' , '''13'''  (1981)  pp. 111–122</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Bässmann,  PH.W. Besslich,  "Konturorientierte Verfahren in der digitalen Bildverarbeitung" , Springer  (1989)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Rosenfeld,  A.C Kak,  "Digital picture processing" , '''2''' , Acad. Press  (1982)</TD></TR></table>

Latest revision as of 22:11, 5 June 2020


An approach to detect straight lines (or curves) in an image (a picture), by applying a coordinate transformation to the image such that all the points belonging to a line (or a curve) are mapped into a single point in the transformed space.

The method to detect lines may be explained as follows [a2]. The set of all straight lines in the $ ( x,y ) $- image plane gives rise to a two-parameter family. When using the normal parametrization (cf. also Normal equation), the equation of a line is given by

$$ \tag{a1 } x \cos \theta + y \sin \theta = \rho, $$

where $ \theta $ is the oriented angle of the normal onto the line, and where $ \rho $ is the algebraic distance of the line from the origin. Restricting $ \theta $ to the interval $ [ 0, \pi ] $, the normal parameters for a line are unique. Taking the $ ( \theta, \rho ) $- space as the transformed space, every line in the $ ( x,y ) $- plane corresponds to a unique point in the transformed space (in the original Hough-transform method the slope-intercept representation of a line, namely $ y = mx + b $, was used, and the $ ( m,b ) $- space was the transformed space; as both the slope and the intercept may become infinite, the technique is more involved, [a3]).

Taking now a fixed point $ ( x _ {i} ,y _ {i} ) $ in the $ ( x,y ) $- plane, this point gives rise in the $ ( \theta, \rho ) $- space to a curve defined by

$$ \tag{a2 } \rho = x _ {i} \cos \theta + y _ {i} \sin \theta. $$

Clearly, when one has a set $ \{ ( x _ {1} ,y _ {1} ) \dots ( x _ {n} ,y _ {n} ) \} $ of picture points that are collinear in the $ ( x,y ) $- plane, the $ n $ curves in the $ ( \theta, \rho ) $- space corresponding to these points according to (a2) have a common point of intersection, say $ ( \theta _ {s} , \rho _ {s} ) $. Writing (a1) with $ \theta \equiv \theta _ {s} $ and $ \rho \equiv \rho _ {s} $, one obtains the equation of a line in the $ ( x,y ) $- plane passing through the $ n $ points.

Having now a digital picture in the $ ( x,y ) $- plane, and mapping all these points to their corresponding curves in the parameter space, collinear subsets of picture points can be found by searching coincident points of intersection in the parameter space. In practice this is done by quantizing both parameters $ \theta $ and $ \rho $, and treating the quantized region as a two-dimensional array of accumulators. For each point $ ( x _ {i} ,y _ {i} ) $ in the $ ( x,y ) $- picture plane, the curve corresponding to it by (a2) gives rise to incrementing the count in some cells of the array. After all picture points have been treated, the array is inspected to find cells having high counts. When in some cell $ ( \theta _ {a} , \rho _ {b} ) $ there are $ m $ counts, then the line with normal parameters $ ( \theta _ {a} , \rho _ {b} ) $ passes (approximately) through $ m $ picture points.

The Hough-transform method as explained above to detect straight lines in a picture can, in principle, be generalized to detect analytic curves involving more than two parameters. For instance, as the equation of a circle in the $ ( x,y ) $- plane is given by

$$ \tag{a3 } ( x - a ) ^ {2} + ( y - b ) ^ {2} = r ^ {2} , $$

a point $ ( x _ {i} ,y _ {i} ) $ on that circle determines a subset of the three-dimensional $ ( a,b,r ) $- parameter space. When a number of picture points are arranged on a circle with parameters $ ( a _ {0} ,b _ {0} ,r _ {0} ) $, the corresponding subsets in the $ ( a,b,r ) $- parameter space will intersect at the point $ ( a _ {0} ,b _ {0} ,r _ {0} ) $, and this point may be detected by using a three-dimensional array. As methods to detect curves in a picture are usually applied to find out if edge points are situated on a particular curve, it is often possible to reduce the number of points to be checked, while also the use of directional information may reduce the computational burden [a1].

References

[a1] D.H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes" Pattern Recognition , 13 (1981) pp. 111–122
[a2] H. Bässmann, PH.W. Besslich, "Konturorientierte Verfahren in der digitalen Bildverarbeitung" , Springer (1989)
[a3] A. Rosenfeld, A.C Kak, "Digital picture processing" , 2 , Acad. Press (1982)
How to Cite This Entry:
Hough transformation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hough_transformation&oldid=47276
This article was adapted from an original article by G. Crombez (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article