# Lib4U

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

# 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.

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

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

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

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

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

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 -coordinate. This unique -coordinate is the point that all three sinusoidal curves share in parameter space.

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  value.
The Hough transform essentially locates the common  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 -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  in a 100 by 100 pixel image. This line  can be represented by the equation,

The values of r that  can take lie in the range , where  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  that  can take lie in the range

2.
Construct an accumulator array  (i.e. an array with dimensions ) 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  values that the point may take. For each ri and  value obtained, add one to the  position in the accumulator array,

This constitutes a “vote” for this  value.

5.
Examine the accumulator array for global and local maxima (i.e.  values that obtained significantly more votes). These maxima correspond to collinear points.
The longest line  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 where this maximum value occurs corresponds to the r and  values that represent . Hence,  can be reconstructed by the equation,

# 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  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  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  in the array where this maximum occurred was noted. A line could then be reconstructed in a new image with the equation,

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.

# 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  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.

Below a surface plot of the accumulator array is shown. The highest and second highest peak in the surface plot correspond to the -coordinates of the longest and second longest line respectively in the input image. It should be noted that all values in the accumulator array  for  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:

### Information

This entry was posted on February 17, 2013 by in Automatic & Robotic, Computer Science, Digital Signal Process, Electronic & Computer Engineering, Science & Technology.

### Pages

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.