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);

Hough Transform of coins.png with radius = 28

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.

Fairly decent Hough transform of the picture from Google

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

Original image:

enter image description here

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')

Could you post how you computed the hough transform? Your accumulation array appears to be 2D. Shouldn't it be 3D if you are detecting circles? You need x, y, and r to define a circle's size and location in a 2D image. That aside, you could try searching for local maxima in your array. The parameter points that represent circles should have much larger intensities than any other point. — eigenchris
@eigenchris: With a 3rd dimension, I guess I could check if each circle I create (along the edges of the image) has a local maxima. In the case where multiple intersection points exist ( because of unknown radius), how do I get the center of the circle? I could average some data out, but I am not sure which all values to take to average out. Does that make sense? — Mathews_M_J
The implementation would be nice. I suspect you've assumed a fixed radius and used a 2D parameter space, which won't work for the images you've shown us since the coins are of different sizes. — eigenchris
I do understand that a fixed radius might not be suitable, but is it somehow possible to get the center without it? I mean I can clearly see where the center of the circle should be from Hough Transform. I just don't understand how to make MATLAB know where it is. Is a three dimensional accumulator (one where I vary the radius as well) the only way? — Mathews_M_J

eigenchris eigenchris · Accepted Answer · 2015-02-14T07:43:48

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:

find the global maximum of your accumulator array using [~,max_idx] = max(accum(:)); [i,j] = ind2sub(size(accum), max_idx];
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)
add the center of mass pixel index to a list of circle centers
set all pixels in the small neighbourhood to zero (to prevent double-detection of the same pixel center)
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.

Hough Transform - Finding the center of the hough transform circles

2 Answers