Thursday, December 13, 2012

Implementing Hough Transform (Line Detection)

Hough transformation is an interesting image processing algorithm used to detect simple geometric shapes like straight lines in images. It serves as a beautiful example of thinking mathematically in different coordinate space. There are numerous articles on the internet describing the working. To begin with one can refer to the wikipedia page here. If you haven't already, would help to go through them before continuing in this post.

Hough transform is based on the fact that a line in the x-y cartesian coordinate system can be mapped onto a point in the rho-theta space.

Now when we see a point on an image, and we are not sure whether or not it belongs to a line like structure in the image, we just go ahead and plot a point for all possible lines that can pass through that point. That would result in a sinusoidal curve in the rho-theta space. 


If the point actually does belong to a line, the actual rho-theta coordinate in the rho-theta plane will be reinforced by all points that belong to the line.

If we plot an intensity curve of the reinforcement strength (number of curves that cross a point in the rho-theta space), we can see peaks at the values that correspond to possible lines. These points can be isolated and picked up by applying a threshold value.

Though OpenCV already has an implementation of the hough transform, it was interesting to build an implementation of my own to see how it works. The source code of my implementation can be obtained here.

Taking a simple example of an image with two lines, here’s what we observe:
Image with lines that we want to detect

Edge detected image

Hough space intensity plot with two bright points.

The lines detected:

  1. rho -1, theta -1.021018 (-58.500004 degrees) 
  2. rho 148, theta 1.028872 (58.949993 degrees) 

Line 1 corresponds to the line that appears to be starting from the bottom left corner and Line 2 corresponds to the one that appears to be starting from the top left corner.

It is interesting to try out different images with different threshold values to see how it affects the detection. You can also change the rho and theta granularity level (in the code) to see their effects on the detection accuracy.



Credits for images 2 & 3:
http://www.ebsd-image.org/documentation/reference/ops/hough/op/houghtransform.html

5 comments:

Anonymous said...

Good day,

Firstly thanks for your post, it has been useful in familiarising myself with the Hough Transform. I was wondering how one would go about changing your code to work with 2D data points and not images.

The reason for this is; is that I am not familiar with OpenCV and would like to use the Hough Transform on straight forward 2D data (based on x and y points); to detect how many lines can be fitted to the 2D data points.

Thanks in advance for your assitance.

Tanmay said...

Hi, thanks for your interest.

Changing it for 2D points should be pretty straight forward. Modify the section that goes through the opencv image pixels to go through your 2D array. You can find the maximas as usual, but you may have to get the thresholds to a very low value since there may not be too many points.

Cheers!

Kevin Hanks said...

Great job dude.
But how can u draw lines after u get the rho and theta values. Can u please give a brief example?

Tanmay said...

Hi Kevin.

I think you mean to have a way of converting from rho theta to the "y = mx + c" form. It is simply:

y = rho/sin(theta) - x * cos(theta) / sin(theta)

Lavender said...

I tried to run your program and these are the mistakes I encountered.
1>d:\eg3243\projects\hough transform\hough transform\hough transform.cpp(20): error C2668: 'sqrt' : ambiguous call to overloaded function
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\math.h(589): could be 'long double sqrt(long double)'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\math.h(541): or 'float sqrt(float)'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\math.h(127): or 'double sqrt(double)'
1> while trying to match the argument list '(int)'
1>d:\eg3243\projects\hough transform\hough transform\hough transform.cpp(85): warning C4244: 'initializing' : conversion from 'float' to 'int', possible loss of data
1>d:\eg3243\projects\hough transform\hough transform\hough transform.cpp(90): warning C4244: 'initializing' : conversion from 'float' to 'int', possible loss of data
1>d:\eg3243\projects\hough transform\hough transform\hough transform.cpp(97): warning C4244: 'initializing' : conversion from 'double' to 'float', possible loss of data
1>d:\eg3243\projects\hough transform\hough transform\hough transform.cpp(98): warning C4244: 'initializing' : conversion from 'double' to 'float', possible loss of data
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
Can you show me what caused these errors?
Thank you so much
My email address is lavenderziyi@hotmail.com