Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Detecting overlapping circles

Hi all,

This is my first post in this forum, and it could be that i'm totally in the wrong place. But i give it a shot..

I'm a biologist tasked with detecting yeast colonies on a nutrient plate. The colonies are circular and about 3-5 mm in diameter. My problem comes from that several colonies might overlap so that you have shapes consisting of 2-5 partially overlapping circles. I need to detect the position and size of all such circles.

I know nothing about computer vision/pattern recognition, but this is my naive approach so far:

1) Find the edges of the shapes. I do this by calculating the color variance for each pixel and its surrounding neighbours. This gives a map where edges have high values and the background has zero (after some filtering)

2) Find all the individual shapes (connected non-zero regions in the map above)

3) a) For each shape select a random connected subset of the shape (corresponding to a partial circle segment). Fit a circle to these points by least squares. b) Repeat a) several times to get coverage for the whole edge of the shape. c) Cluster the calculated circle geometries from above. The number of clusters should then give the number of overlapping circles and the mean och each cluster should give the geometry.

4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)

This whole thing works reasonably well if the circles are few and only slightly overlapping, but not well for complex shapes with several circles. It's also slow because of the fitting of random arcs. It also feels like too much of a home made brute force solution and i'm sure there are many more clever ways to do it. For example, could you count the number of times some fitted shape (spline or something) goes from concave to convex as you go along the edge of the shape? That should give the number of circles and their approximate intersection points.

All of this is done in Matlab, but anything else would work as well. Here is an image which shows how the colonies might look:

Any help is very welcome! Feeling rather lost in this field :)