Hough Transform - Finding the center of the hough transform circles

Question

I have been reading up quite a bit on Hough circles and how it can be used to detect the center and radius of a circular object. Although I understood how the transform works I am still not able to to understand how to get the center of a circle. The code snippet below is customized purely for coins.png in MATLAB. I tried it with a slightly more complex picture and it fails miserably. I am fixing the radius and then getting the accumulator matrix.

Code:

temp = accum;
temp(find(temp<40))=0; %Thresholding
imshow(temp,[0 max(temp(:))])
temp = imdilate(temp, ones(6,6)); %Dilating
imshow(temp,[0 max(max(temp))]);
temp = imerode(temp,ones(3,3)); %Eroding
imshow(temp,[0 max(max(temp))]);
s = regionprops(im2bw(temp),'centroid'); %Computing centroid
centroids = cat(1, s.Centroid);

I wanted to test the code out on a different picture and found this one on google. The Hough Transform produced a favorable result, but it's more overlapping than the previous case and my method fails.

Can someone suggest what the best method is to compute the centroid of the hough circle?

---

Original image:

Full Code:

%%Read and find edges using a filter
i = imread('coins4.jpg');
i = rgb2gray(i);
i = imresize(i,0.125);
i_f = edge(i, 'canny',[0.01 0.45]);
imshow(i_f)

%%

[x y] = find(i_f>0); % Finds where the edges are and stores the x and y coordinates
edge_index = size(x);
radius = 30; %Fixed radius value
theta = 0:0.01:2*pi;
accum = zeros(size(i,1), size(i,2)); %Create an accumulator matrix.

r_co = radius*cos(theta);
r_si = radius*sin(theta);

x1 = repmat(x, 1, length(r_co));
y1 = repmat(y, 1, length(r_si));
x_r_co = repmat(r_co, length(x),1);
y_r_si = repmat(r_si, length(y),1);

%% Filling the accumulator
a = x1 - x_r_co;
b = y1 - y_r_si;

for cnt = 1:numel(a)
    a_cnt = round(a(cnt));
    b_cnt = round(b(cnt));
    if(a_cnt>0 && b_cnt>0 && a_cnt<=size(accum,1) && b_cnt<=size(accum,2))
        accum(a_cnt,b_cnt) = accum(a_cnt,b_cnt) + 1;
    end
end

imshow(accum,[0 max(max(accum))]);

 %% Thresholding and get the center of the circle.
close all;
temp = accum;
temp(find(temp<40))=0;
imshow(temp,[0 max(temp(:))])
temp = imdilate(temp, ones(6,6));
imshow(temp,[0 max(max(temp))]);
temp = imerode(temp,ones(3,3));
imshow(temp,[0 max(max(temp))]);
s = regionprops(im2bw(temp),'centroid');
centroids = cat(1, s.Centroid);
imshow(i);
hold on;
plot(centroids(:,1), centroids(:,2),'*b')

Answer 1

If you want to stick with the 2D image you have now, this is a simple algorithm that might work for your first image since all the coins are about the same size and it isn't too cluttered:

1. find the global maximum of your accumulator array using [~,max_idx] = max(accum(:)); [i,j] = ind2sub(size(accum), max_idx];
2. Take a small neighbourhood around this pixel (maybe a square with a 10 pixel radius) and calculate its center of mass and get its index (this basically finds the middle of the bright rings you see)
3. add the center of mass pixel index to a list of circle centers
4. set all pixels in the small neighbourhood to zero (to prevent double-detection of the same pixel center)
5. repeat from step 1. until you reach approximately 70% or so of the original global max

---

If that doesn't work, I'd suggest taking the 3D accumulator approach, which is much better for coins of variable size.

The reason you are getting "donut" shapes for some of the coins rather than circles with intense bright points at the centers is because the radius you are assuming is a little off. If you were to explore the 3rd dimension of the accumulator (the radius dimension), you would find that these "donuts" taper to a point, which you could then detect as a local maximum.

This does require a lot more time and memory but it would lead to the most accurate result and isn't a big adjustment code-wise. You can detect the maxima using a method similar to the one I mentioned above, but in 3D and without the center-of-mass trick in step 2.

Answer 2

So, there is a function in matlab that does exactly what you want, called imfindcircles. You give an image and a range of possible radii, it outputs the computed radii and the centers of the circles. Some other parameters allow to tweak the computation (and in my experience, using them is necessary for good results).

Now, if you want to find the centers and radii yourself (not using matlab) then you want to use a maximum finder on the accumulation matrix. The concept of the Hough transform is that the maxima you find on the accumulation matrix each correspond to a circle (parametrized usually in (radius, x_center, y_center). The tough part here is that you have a gigantic searchspace and many many many many maxima that are not "real" circles but artefacts. I do not know how to reliably differentiate these fake circles of the real ones -- and I expect it's a rather complicated check to do.

Hope this helps!