line detection

Line Detection via Hough Transform

I’ve had a hard time finding an explanation for how exactly hough transform works. No one seemed to key-in on a detail that was most integral to my understanding. So I will explain hough transform briefly while emphasizing the detail that helped me understand the Hough Transform.

The Hough Transform

First, begin with an image that you want to find lines in. I chose an image of a building for this example.

Building for Hough Transform Line Detection Example

Then run your favorite edge detection algorithm on it. I chose canny edge detection.

Edge map of building for Hough Transform Line Detection Example

Note: The lines are aliased here… and yes, as you might suspect, it does sometimes cause problems. But there is a simple way to handle it. Just increase the bin size for the accumulator matrix.

Note2: If you (..yes, you!) would like to know more about how aliased lines cause problems, just say so in the comments and I’ll do my best to shed light on the issue 😉

 How to Generate a Hough Transform Accumulator Matrix

This is the important part. The edge map (above) is what is used to generate the Hough accumulator matrix.

Okay. Here’s the trick… Each white pixel in the edge map will create a one pixel sine wave in the Hough accumulator matrix.

That means.. 1 pixel in edge map = 1 sine wave in accumulator matrix.

 

Use the [x,y] coordinates of white pixels in the edge map as parameters for computing [ρ, θ] needed for the sine wave  that will go into the accumulator matrix.

The general equation is: ρ = x*cos(θ) + y*sin(θ)

So for each white pixel, loop from θ = –90 to  θ = 90, calculating ρ at each iteration.

For each [ρ, θ] pair, the accumulator matrix gets increased by 1.

That is: AccumulatorMatrix[θ, ρ] = AccumulatorMatrix[θ, ρ] + 1;

The Hough Transform Accumulator Matrix

So now we’ve done it. We’ve accumulated sine waves for each white pixel in the edge map. Now all we need to do is extract the useful information out of it!

Hough Transform Accumulator Matrix (JET colormap)

This is essentially a grayscale image depicted with a JET colormap, so don’t worry if yours doesn’t look quite like this. You’ll know you did something wrong if you don’t see any sinusoidal lines. (You may need to scale your image linearly to bring out the detail.)

How to get Lines from the Accumulator Matrix

The first thing you do is threshold the accumulator matrix to find the hot spots in the image. The [x,y] coordinates of each hot spot define a point in a polar coordinate system. A point in the polar coordinate system is defined by ρ (rho, length) and θ (theta, angle). In this example, I believe I used a bin size of 1 when I filled the accumulator matrix. This means the polar variables ρ = y, and θ = x. If you’re using a bin size other than one, just scale the values, ρ = y*binSize, θ = x*binSize.

Once you have a polar point, imagine a vector from the origin to that polar point, the line that is detected in the image is perpendicular to that vector, and crosses through that point.

The value of the hotspot in the accumulator matrix is the number of pixels from the edge map that lie on that line.

The Result

Hough Transform Line Detection

I plotted 14 (of the many) lines that were detected based on the above hough transform. I could have extracted more lines from the image by changing the value I thresholded the accumulator matrix with. If I would’ve chosen a lower threshold value, more lines would have been detected.

 

Questions, Comments, Concerns?

Tags: , , , , , , , , ,

Thursday, April 19th, 2012 Computer Vision 4 Comments
Psst.. There is no more.