next up previous
Next: The Hough Algorithm Up: No Title Previous: Introduction

Theory

Consider a straight line y which is a function of the spatial coordinate x. This line can be represented by the equation y = mx + b where m is the gradient and b is the y-intercept of the line.
A point on the line will have a fixed (x',y') coordinate , however may have a whole range of m and b values defining it.


 
Figure 1: A single point (x',y') may have a range of m and b values defining it.
\begin{figure}\par\centerline{\psfig{figure=scase1.eps,clip=,height=6cm,angle=0}} \par \par\end{figure}

Thus one point in (x,y)-space has an associated straight line in (m,b)-parameter space.


 
Figure 2: The point (x',y') is represented by a straight line in parameter space
\begin{figure}\par\centerline{\psfig{figure=scase2.eps,clip=,height=6cm,angle=0}} \par \par\end{figure}

Due to the difficulties involved with lines of infinite slope, it is more suitable to represent the line as a function of r and $\theta $, where,

\begin{displaymath}r=x cos\theta+y sin\theta \end{displaymath}

and r is the length of the line $\ell$ extending from the origin perpendicular to the line y = mx + b and $\theta $ is the angle $\ell$ makes with the x-axis.

 
Figure: The line y can be represented by the parameters r and $\theta $.
\begin{figure}\par\centerline{\psfig{figure=scase3.eps,clip=,height=7cm,angle=0}} \par \par\end{figure}

A single point on this line thus has a whole range of possible r and $\theta $values associated with it. This single point is mapped to a sinusoidal curve in $(r,\theta )$ parameter space.
To illustrate this a single in (x,y)-space is shown below along with the corresponding image for this point in $(r,\theta )$-space.


 
Figure: One point in (x,y)-space maps to a curve in $(r,\theta )$-space
\begin{figure}\par\centerline{\psfig{figure=hpoints1.eps,clip=,height=7cm,angle=0}} \par \par\end{figure}

Now consider a second point in (x,y)-space. This too maps to a curve in $(r,\theta )$-space.


 
Figure: Two points map to two curves in $(r,\theta )$-space
\begin{figure}\par\centerline{\psfig{figure=hpoints2.eps,clip=,height=7cm,angle=0}} \par \par\end{figure}

If we then add a third collinear point we obtain three sinusoidal curves in parameter space. It should be noted however, that these three curves in parameter space share a common point of intersection. This is because each of the three points in (x,y)-space all lie on the same line which can be represented by a unique $(r,\theta )$-coordinate. This unique $(r,\theta )$-coordinate is the point that all three sinusoidal curves share in parameter space.


 
Figure: The corresponding curves in $(r,\theta )$-space of three collinear points share a common point of intersection.
\begin{figure}\par\centerline{\psfig{figure=hpoints3.eps,clip=,height=7cm,angle=0}} \par \end{figure}

Hence all points on a straight line will map to a corresponding curve in parameter space. The curves will be different for each individual (x,y) point, however the curves associated with collinear points will all intersect at a common $(r,\theta )$ value.
The Hough transform essentially locates the common $(r,\theta )$ intersection point. With the knowledge of these two coordinates, the corresponding line in (x,y)-space can be reconstructed.

next up previous
Next: The Hough Algorithm Up: No Title Previous: Introduction
vicky safouris
2000-06-02