# How to segment multiple overlapping coins (ellipses)

I am doing a program that counts coins (and tells their value by their size) with OpenCV (C++).

Let's say we have an image of some coins.

If there is an overlap of two coins at the same time, it is relatively easy to segment the coins doing the distance transform, thresholding so that coins are sepparated, doing a skeleton of the background, and then drawing that skeleton into the original image.

But what if there is an overlap of 3 coins like in the image below: What is the best way to detect 3 coins in that case? Hough circles?

• This seems more of a computer vision question than computer graphics. – user29633 Nov 6 '18 at 4:19
• What would be the correct site for computer vision? I was looking at the list and thought it would be this one – Cacahuete Frito Nov 6 '18 at 8:29
• Computer graphics has its own stackexchange: computergraphics.stackexchange.com You are at the correct site. – Tolga Birdal Nov 8 '18 at 23:00

Segmentation is generally a process that is very susceptible to noise. I would better use a detector, especially for geometric shapes like coins. Remember, if you have a good detection, you also ease the segmentation problem dramatically. For the example of coins, a good model would be to use an ellipse: every circle/ellipse appears to be an ellipse under perspective projection, up to a negligible error.

Luckily, there are many good methods that can detect ellipses without segmentation. ELSD is one, Hough transform is another. In a previous post, I have explained how to use ELSD to spot spherical particles. Now I will take the Hough transform approach - this results in a minimal code that works and which I will share below. This might also be more intuitive to understand.

I will now explain a hypothesize-merge algorithm. Assume that we are given a grayscale image $$I$$, with gaussian smoothed edges $$E$$. The idea would be to apply a Hough ellipse detector on $$E$$ to get a large set of ellipse hypotheses $$\{\mathbf{\Psi}_{1..n}\}$$ and then cluster them to a reduced subset $$\{\mathbf{\Psi}_{1..k}\}$$ where $$k<. If $$k$$ is known (for instance this image with six coins has $$k=6$$) we can make use of this knowledge. Though, I will not assume this. Using the referred ellipse detector (see above) and an available mean shift clustering, I have devised the following MATLAB script (all of this can be implemented in OpenCV with reasonable little effort):

%% PARAMETERS
% blur the image to suppress some noise
gaussSigma = 1.0;

% parameters of the canny algorithm
edgeThMin = 0.03;
edgeThMax = 0.3; % usually set to 10*edgeThMin

% override some default parameters - tune them to the size of a coin
minEllipseMajorAxis = 45;
maxEllipseMajorAxis = 110;

% coins are circle like but in case of projectivity set to a lower value
minEllipseAspectRatio = 0.7;

% bandwidth of the meanshift filter. this is a quite critical parameter
% that determines the number of detected ellipses and their grouping.
meanShiftBandwidth = 25;

%%
% some more parameters do exist within the code below, but
% they should be somewhat less important.

% smooth the image a bit - increases reliability
Ig = imgaussfilt(I, gaussSigma);
G = rgb2gray(Ig);
E = edge(G,'canny', [edgeThMin, edgeThMax]);

params.minMajorAxis = minEllipseMajorAxis;
params.maxMajorAxis = maxEllipseMajorAxis;

params.minAspectRatio = minEllipseAspectRatio;

% there can be multiple correct hypotheses (filter later)
params.numBest = 200;

% pair with k other points N^2 -> k*N
% less randomization means more speed
params.randomize = 5;

% note that the edge (or gradient) image is used
% code from: https://www.mathworks.com/matlabcentral/fileexchange/33970-ellipse-detection-using-1d-hough-transform
bestFitHyp = ellipseDetection(E, params);

% a fit looks like: (ra,rb,ang,x0,y0,C,Nb)
fprintf('Output %d best fits.\n', size(bestFitHyp,1));
%
figure; image(I);
%ellipse drawing implementation: http://www.mathworks.com/matlabcentral/fileexchange/289
ellipse(bestFitHyp(:,3),bestFitHyp(:,4),bestFitHyp(:,5)*pi/180,bestFitHyp(:,1),bestFitHyp(:,2),'g');
title('Hough Ellipse Hypotheses');

% now cluster the ellipses that belong together using x0,y0 only.
% we use mean-shift clustering : https://de.mathworks.com/matlabcentral/fileexchange/10161-mean-shift-clustering
[~,idx,~] = MeanShiftCluster(bestFitHyp(:,1:2)',meanShiftBandwidth, 0);
numClusters = max(idx);
bestFits = zeros(numClusters, 6);
for i=1:numClusters % for each class
ind = find(idx==i);
members = bestFitHyp(ind, :);
for j=1:6 % for each component of an ellipse record the median
bestFits (i, j) = median(members(:,j));
end
end

figure; image(I);
%ellipse drawing implementation: http://www.mathworks.com/matlabcentral/fileexchange/289
ellipse(bestFits(:,3),bestFits(:,4),bestFits(:,5)*pi/180,bestFits(:,1),bestFits(:,2),'g');
title('Clustered Hypotheses');


To determine the cluster centers I use a median as this might be more robust than the mean alternative - you can try different things though. Let's look at the outputs of different steps.

The edges of the smoothed image:

Initially we allow for a large number of hypotheses to survive (~120). This initial result, together with the clustered hypotheses (final detections) look like: Of course this result is a rough detection. In other words, it is an outcome of voting and not an outcome of non-linear parameter refinement. To further improve these results, you can write an optimizer to snap the ellipses on top of the image edges. See here on descriptions of how to do that. You can also use ELSD edges instead of the Canny to ease the job of the Hough transform and to make the algorithm more robust.

It might not be the best but I hope this gives you a direction. Here are more sample outputs of running the method on coin photos fetched from Google Images: 