Can you detect circles only using the hough line transform?

Question

I'm not talking about the Hough Circle Transform (where you replace the representing eqns, hence the parameters with a 3D set) but a Hough Line Transform.

My solution to this:

A hough line transform maps lines to a single point in (p,theta) space. This point contains the number of points lying on the line in $(x,y)$ (cartesian) space. Conversely, a point $\mathbf{A}=(x,y) \in \mathbb{R}^2$ maps to a curve in polar $(r,\theta)$ space. This is because a point belongs to an infinite number of lines. Now, imagine a circle:

where the tangent $\mathbf{AB}$ is perpendicular to the line connecting the center and the point of contact ($\mathbf{NA}$). Let's call this line the radial line. Since the circle is a symmetrical object, this applies to every point on it.

This means essentially, that a circle is constructed of such infinite tangent lines which are perpendicular to the radial line. The tangents map to the bin in polar space: $\mathbf{A} \rightarrow (r, \theta)$. So essentially, the circle in $(x,y)$ space becomes a line in $(p,\theta)$ space. Am I correct in saying this?

Then could we apply a Hough transform on the Hough matrix itself to detect circles in the original $(X,Y)$ space?

(I know academics can be ruthless but newbee here so please be kind when tearing me a new one.)

Answer 1

No this won't work. Simply because we do not know the center of the circle in advance (no oracle telling us) and therefore we cannot find a voting space parameterization where $r$ is fixed and only $\theta$ changes. For each point both quantities will change and this will still generate a curve in the Hough space. Having said that, I think below there is something interesting which uses tangent lines to detect circles:

Although what we will be doing is not exactly a Hough line transform, your way of thinking is on the right track. There is a strong connection there but because the tangent is not well represented in the Hough-circle transform, it probably won't work. Yet, what you have described brought me to the following idea:

It is possible to create an accumulator in the cartesian space ($X$-$Y$), where each pixel casts multiple votes as a partial line segment, along its gradient direction (or opposite gradient direction). The center of the circle will lie at the intersection of those segments. The width of the line segment can be related to the radius of the circle we like to detect. I think this approach is tightly coupled to operating in the $\textit{dual space}$ instead of the original and has demonstrated advantages, especially for conic fitting (well, a circle is basically a conic). A dual space is nothing but the space composed of the tangents. Each tangent is a point, just like in Hough.

Out of interest and because I think this is not a bad idea, I implemented this operation in MATLAB. Of course, instead of explicit edge-detection, I would simply use a gradient magnitude thresholding and use the image gradient as a cue of the direction of $\mathbf{NA}$ vector.

Here is the original test image:

And here is the accumulator space I get when I search for circles with $r=30$ pixels:

With peaks detected by the houghpeaks function:

The same peaks visualized back on the image:

It is possible to see that thanks to the voting along the line, the approach is pretty robust to the noise in the radius, i.e. we do not need to specify the radius explicitly.

For interested reader, I also provide the MATLAB code I used to generate those images:

function [ x,y,V ] = hough_circle_dual( I, maxRadius, threshold, numMaxCircles )

[M, N] = size(I);
[Gx, Gy] = imgradientxy(I);
[Gmag, Gdir] = imgradient(Gx, Gy);

V = zeros(M, N);

for i=1:M
    for j=1:N
        if (Gmag(i,j)>threshold)
            g = [Gx(i, j) Gy(i, j)]./Gmag(i,j);
            p2 = maxRadius.*g + [j, i];
            [x, y] = bresenham(j,i,p2(1), p2(2));
            ind = (x>0 & y>0 & x<=N & y<=M);
            x = x(ind); y = y(ind);
            ind = sub2ind([M,N], y, x);
            V(ind) = V(ind)+1;
        end
    end
end
peaks = houghpeaks(V, numMaxCircles);
x = peaks(:,1);
y = peaks(:,2);
end

% generates a bresenham line (compactly written)
function [x, y]=bresenham(x1,y1,x2,y2)
x1=round(x1); x2=round(x2);
y1=round(y1); y2=round(y2);
dx=abs(x2-x1); dy=abs(y2-y1);
steep=abs(dy)>abs(dx);
if steep t=dx;dx=dy;dy=t; end

if dy==0, q=zeros(dx+1,1);
else, q=[0;diff(mod([floor(dx/2):-dy:-dy*dx+floor(dx/2)]',dx))>=0];
end

if steep
    if y1<=y2 y=[y1:y2]'; else y=[y1:-1:y2]'; end
    if x1<=x2 x=x1+cumsum(q);else x=x1-cumsum(q); end
else
    if x1<=x2 x=[x1:x2]'; else x=[x1:-1:x2]'; end
    if y1<=y2 y=y1+cumsum(q);else y=y1-cumsum(q); end
end
end

Here is how I would call this function in MATLAB 2016:

I=imread('coins.png');
[x, y, V] = hough_circle_dual(I, 30, 10, 10);
figure,imshow(V,[]);
hold on, plot(y,x,'r+');

The Bresenham line generation used here is taken from the FileExchange post.