Circular Hough Transform in MATLab

[Paul_Johno]

Hi all,

I'm using the circular hough transform (CHT) in MATLab to identify some circles within images. While I can get the CHT to work, I don't fully understand it, and I was hoping someone could explain it to me in laymans terms. I've had a hunt through Google and I still haven't gained a reasonable understanding.

This would be a massive help, thanks.
Paul

[gorcee]

Hi all,

I'm using the circular hough transform (CHT) in MATLab to identify some circles within images. While I can get the CHT to work, I don't fully understand it, and I was hoping someone could explain it to me in laymans terms. I've had a hunt through Google and I still haven't gained a reasonable understanding.

This would be a massive help, thanks.
Paul

Are you familiar with the traditional Hough Transform? I'll explain that, and then you should be able to extend it to the circular transform.

The traditional HT is used for detecting lines. The way it does this is simple. Assume you have run an image through an edge detection algorithm, and you have a black/white image that contains all the edges. These edges make up a set of points/pixels.

The HT iterates through each point. At each point, it generates a set of lines passing through the pixel at different angles (0 to 180 degrees, with some pre-defined granularity). So at the point (x0,y0), the HT draws a line through (x0,y0) at (for 5 degree granularity) 0 degrees, 5 degrees, 10 degrees, etc. The angle is our value of \theta. Store that for a moment.

Now, we have this line that we just drew at angle \theta through (x0,y0). Draw a line perpendicular to this one that goes through the origin (it might not be in the image itself!). The distance between the origin and where this new line intersects is our value of r.

Make a table. We now have a value of \theta that we selected, and a value of r that we computed. Imagine that your table has \theta as rows, and r as columns. When you encounter a (\theta, r) pair, add a vote to that part of the table (ie, increment it by 1).

What happens is that any time you land on a pixel that makes a line with another pixel, that same (\theta, r) gets voted up. So the cells in the table with the highest votes represent the longest lines.

Think about the line y=ax+b. This line covers an infinite number of points in Cartesian (x,y) space. But in parameter space, it is uniquely defined by a single point: (a,b). Another way of saying this is that if I made a function:

Code: Select all

function y=drawLine(a,b)
y = a*x+b;


I could cover an infinite number of points just by specifying one single point in parameter space.

I'll try to draw you an image to make some sense of things.

[gorcee]

Ok so, let's say we have this image:



Now, let's start our Hough Transform. We take a point (x0,y0), and we draw a line through it with angle \theta_i. We then find a line perpendicular to this one that also passes through the origin. The distance between the origin and where the new line intersects is r. We'll also test a bunch of other thetas, but this works for now.



Moving on to the next point (x1,y1), we find that when we try the same theta_i, we get another r (I didn't label it differently in my picture, but you follow).



Now. If we let \theta_k follow along the line we're studying, what do we find?

It should be pretty obvious that since all the pixels along that line are collinear, at \theta_k, for each pixel, we'll compute the same value of r. So we'll get 12 votes for that (\theta_k, r_k) combination.


The CHT is essentially the same thing, but we're looking for circles, not lines.

[Paul_Johno]

Thanks for taking the time to reply gorcee, that's a big help.
I'll let you know how I get on, and will no doubt have more questions!

Thanks so much,
Paul

[Paul_Johno]

Hi gorcee, I'm not very mathematically minded, so please bare with me.

So for point (x0, y0) the HT will iterate all angles between 0 degrees and 180 degrees? In your example your the line you draw on (x0, y0) is around 10 degrees from horizontal... how did you determine this?

What does "r" stand for in your example? And for each of these angles we then compute r by drawing a perpendicular line from theta (and our pixel of interest), to the top left of the screen, the origin? If r must always go to the origin (top left corner), does this mean it dictates the angle theta?

Many thanks,
Paul

[gorcee]

Hi gorcee, I'm not very mathematically minded, so please bare with me.

So for point (x0, y0) the HT will iterate all angles between 0 degrees and 180 degrees? In your example your the line you draw on (x0, y0) is around 10 degrees from horizontal... how did you determine this?

What does "r" stand for in your example? And for each of these angles we then compute r by drawing a perpendicular line from theta (and our pixel of interest), to the top left of the screen, the origin? If r must always go to the origin (top left corner), does this mean it dictates the angle theta?

Many thanks,
Paul

We determine the angles by simply choosing them. For one application, I used angles starting at 0 and incrementing every 5 degrees. Other applications might require you to do every 2 degrees, or 1 degree, or whatever.

I drew the line in my earlier example at that angle because it was easy, and because I could draw a line perpendicular to it that goes through the origin pretty easily.

r is determined like this:

1.) Draw a line with angle \theta through (x0,y0). Call this Line A.
2.) Draw a line segment from the origin perpendicular to Line A.
3.) r is the length of this line segment.

[ike.marsa]

i want to implement Hough Transform under the equation y=mx+c
if m<1 so the equation becomes c=-xm+y
if m>1 so the equation becomes c=-ym+x

help me with code please....
it's for my undergraduate thesis....