Circle Hough Transform. Improvement by knowing edge direction

I'm studying Hough Transform. I have fully understood the HT for detecting lines and successfully implemented it. I have more problems with the circle detection HT. Given a circle, if the radius is known i have to work in a 2d parameter space (each point in the image space becomes a circle in the parameter space; the intersection of all the circles gives me the center of the image circle). If the radius is not known the parameter space becomes 3d. What i don't understand is why if i know the direction of the edges, even if my radius is unknown the parameter space lowers to 2d.

• What is the direction of edges? Do you mean that after reading several points you realize it is concave and based on that instead of creating circle of the results you get only one point (the center)? Or you can traverse them in clockwise direction? I understand the HT circle is fancy algorithm, but for known radius it may be used in short term form or other technique would be faster. – Evil Sep 15 '16 at 16:03
• "direction of the edges" - what edges? You didn't mention anything about edges before that point. The Hough transform usually takes as input a set of points (no edges) and outputs a circle, so I'm not sure what you're talking about. – D.W. Sep 16 '16 at 1:34
• @D.W. The set of points passed to the transform are called edge points if they were determined by some edge detection or thresholding process. Hence the name. Nicola is using a shorthand. – GEL Sep 16 '16 at 3:06
• @GEL Thank you for explanation, I never heard it before. – Evil Sep 16 '16 at 17:18

Consider circles of the form

$$(x - a)^2 + (y - b)^2 = r^2$$

The Circular Hough Transform with unknown radius and unknown gradient information has a parameter space $(a, b, r) \in H$. Given a single edge point we'd end up drawing a right cone increasing along the positive $r$ axis with its tip centered at $(x, y, 0)$.

Now to your question. When you know the gradient $\nabla I(x,y)$ of an edge point, $(x,y)$ from your image $I$, you have a vector originating from the center of the circle pointing outward. Since you have your edge point $(x,y)$ the center $(a, b)$ must lie somewhere along the lines $(x,y) \pm r \nabla I(x,y)$. There is only one variable in that statement, $r$.

Now the Circular Hough Transform becomes: for each edge point $(x,y)$, and for each plausible radius $r$, calculate $(a, b) = (x, y) \pm r \nabla I(x,y)$ and increment the accumulator array index $(a, b, r)$ by $1$. Then you go a do your usual vote counting to find the most likely parameters $(a, b, r)$.

For further details refer to D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes" Pattern Recognition. Vol.13. 1981. Extends this concept to ellipses, general analytic curves, and the general transform.

• Great answer.. however I don't understand why you used $\pm$ in $(x,y) \pm r \nabla I(x,y)$.. I mean, don't we know the gradient orientation? Maybe it's because we don't know if the intensity of the circle is higher or lower with respect to background? thanks a lot! – Surfer on the fall May 6 '18 at 6:43