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 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 (
*x*_{i},*y*_{i}) point examined, evaluate the corresponding*r*_{i}and values that the point may take. For each*r*_{i}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-intercept*b*=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.**Figure 8:**(a) Input image. (b) Accumulator array. (c) Longest line in the input image reconstructed.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:

Advertisements

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)

Cùng Viết Hiến Pháp

hienphap.net

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: