Lib4U

‎"Behind every stack of books there is a flood of knowledge."

Locating Straight Lines in Noisy Images with the Hough Transform

htrand3d

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.

 

The Hough Algorithm

 

The Hough algorithm is used to locate the unique $(r,\theta )$-coordinate of a straight line. Each step of the Hough algorithm is outlined below.

 

1.
Quantize parameter space appropriately according to the image size in (x,y)-space.
For Example, consider a straight line $\ell$ in a 100 by 100 pixel image. This line $\ell$ can be represented by the equation,
 

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

 

The values of r that $\ell$ can take lie in the range $0\le r \le d$, where $d=\sqrt{100^{2}+100^{2}}$ is the length of the diagonal across the image. Thus the r values in parameter space are restricted by the image size in (x,y)-space. The values of $\theta $ that $\ell$ can take lie in the range $0 \le \theta \le 360^{o}$

2.
Construct an accumulator array $A(r,\theta)$ (i.e. an array with dimensions $r \times \theta$) with all elements initially set to zero. 

3.
Examine the input image for feature points. This may involve a gradient exceeding some threshold. This step however is optional. If it is not known what defines a feature point, then it is reasonable to include every point in the Hough transform. If it is the randomized Hough transform that is being implemented, then a number of random points in the image will be chosen for examination. 

4.
For each (xi,yi) point examined, evaluate the corresponding ri and $\theta_{i}$ values that the point may take. For each ri and $\theta_{i}$ value obtained, add one to the $A( r_{i} ,\theta_{i})$ position in the accumulator array,
 

\begin{displaymath}A( r_{i} ,\theta_{i})=A( r_{i} ,\theta_{i})+1.
\end{displaymath}

 

This constitutes a “vote” for this $(r_{i},\theta_{i})$ value. 

5.
Examine the accumulator array for global and local maxima (i.e. $(r,\theta )$ values that obtained significantly more votes). These maxima correspond to collinear points.
The longest line $\ell$ in the input image will have the maximum value in the accumulator array, and this maximum value provides a measure of how many points lie on the line. The position in the array$A(r_{m},\theta_{m})$ where this maximum value occurs corresponds to the r and $\theta $ values that represent $\ell$. Hence, $\ell$ can be reconstructed by the equation,
 

\begin{displaymath}r_{m}=x cos\theta_{m}+y sin\theta_{m} .
\end{displaymath}

A Single line in an Image

A program was written in Matlab to construct a line in a 100 by 100 pixel input image which did not contain noise. This line had a gradient m=0.75 and a y-intercept value of b=20.0. The program was then extended to implement the Hough algorithm on feature points only. Feature points were defined as points with a grey level of 200 or more. It was specified in the program that points on the line were to have a grey level of 255.
For each value of $\theta $ that this point could take, the corresponding r values were calculated. If a r value was found to be less than zero, then this r value was set to one. For each $(r,\theta )$ calculated, the corresponding positions in the accumulator array were incremented by a value of one.
After each feature point was examined, the maximum value in the accumulator array was located. The position $(r_{m},\theta_{m})$ in the array where this maximum occurred was noted. A line could then be reconstructed in a new image with the equation,

 

\begin{displaymath}r_{m}=x cos\theta_{m}+y sin\theta_{m} .
\end{displaymath}

 

The input image, accumulator array and the reconstructed line can be viewed in the figure below. The Matlab code can be viewed in Appendix B.

 

Figure 7: (a) Input image. (b) Image of the accumulator array. (c) Image of the reconstructed line.
\begin{figure}\par\centerline{\psfig{figure=htline.eps,clip=,height=15cm,angle=0}}
\par
\end{figure}

 

 

Two lines in a noisy image

The program used in the previous section to find a straight line in an image was extended to find a line in a noisy image. The noisy image was constructed with two lines, one of gradient m=2.0 and y-interceptb=10.0, and the other line of gradient m=-0.7 and y-intercept b=85.0. Rather than finding feature points, the program implemented the Hough transform on all points in the image. For each $(r,\theta )$ coordinate calculated, the accumulator array was incremented by the grey level value at the corresponding (x,y) pixel in the input image.
It should be noted that the Hough transform will only find the longest line in the image. To detect the second line in the image, the program would have to locate the second local maxima in the accumulator array. The input image, accumulator array, and reconstructed line can be viewed below. The Matlab code can be viewed in Appendic C.

 

Figure 8: (a) Input image. (b) Accumulator array. (c) Longest line in the input image reconstructed.
\begin{figure}\par\centerline{\psfig{figure=htrand_b.eps,clip=,height=15cm,angle=0}}
\par
\end{figure}

Below a surface plot of the accumulator array is shown. The highest and second highest peak in the surface plot correspond to the $(r,\theta )$-coordinates of the longest and second longest line respectively in the input image. It should be noted that all values in the accumulator array $A(r,\theta)$ for $180 \le \theta \le 270^{\circ}$ are zero. The dimensions of the input image restrict the parameters that a line in the image could have. 

Figure 9: Surface Plot of the Accumulator Array.

Source:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Virtual Fashion Technology

Virtual Fashion Education

toitocuaanhem

"chúng tôi chỉ là tôi tớ của anh em, vì Đức Kitô" (2Cr 4,5b)

VentureBeat

News About Tech, Money and Innovation

digitalerr0r

Modern art using the GPU

Theme Showcase

Find the perfect theme for your blog.

lsuvietnam

Learn to Learn

Gocomay's Blog

Con tằm đến thác vẫn còn vương tơ

Toán cho Vật lý

Khoa Vật lý, Đại học Sư phạm Tp.HCM - ĐT :(08)-38352020 - 109

Maths 4 Physics & more...

Blog Toán Cao Cấp (M4Ps)

Bucket List Publications

Indulge- Travel, Adventure, & New Experiences

Lib4U

‎"Behind every stack of books there is a flood of knowledge."

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.

%d bloggers like this: