Ask Your Question
2

Detecting overlapping circles

asked 2014-09-30 01:14:44 -0600

Rasmus gravatar image

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: http://medicine.emory.edu/id/labs/lyon/yeast.bmp

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

edit retag flag offensive close merge delete

Comments

1

Have you tried the hough_circles? Or a kind of binarization and then fitellipse; if it is too elliptic/long, then there are more circles (approximatively hi_ray/lo_ray)?

thdrksdfthmn gravatar imagethdrksdfthmn ( 2014-09-30 04:58:02 -0600 )edit
1

Thanks for your suggestions! It was not stated in the original question, but I actually use an elliptical fit just as you suggested in order to screen out the shapes which are simple circles. The above workflow is only applied to complex shapes.

I looked up Hough transform at Wikipedia, and it sounds rather similar to what I do. I take a random segment, fit a circle to it, clusters in parameter space and use the median in each cluster as representative. Hough transform iterates over each pixel, fits a circle to it and its surrounding and counts how ofter the resulting parameter combination occurs. The main difference seems to be that Hough does this for each pixel while I do it for some random number of segments. The counting also indicates that Hough requires some bounds on the...

Rasmus gravatar imageRasmus ( 2014-09-30 08:02:39 -0600 )edit

...parameter space. If so then my problem can maybe be reduced to how to fit circles to a small number of points. The reason I use larg(er) random segments is that the quadratic fitting tends to favor very small circles when only a small number of pixels are used. Is there maybe a clever way of doing this? I see unpleasent words such as eigenvectors coming up.. :)

Rasmus gravatar imageRasmus ( 2014-09-30 08:05:34 -0600 )edit

Sorry, small number of closely aligned points I mean. So that only some small fraction of the circle is actually covered.

Rasmus gravatar imageRasmus ( 2014-09-30 08:06:48 -0600 )edit
2

Have a look on Morphology Transformations, you need to proceed like, threshold->morphology->contour analysis etc...

Haris gravatar imageHaris ( 2014-09-30 21:34:15 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
7

answered 2014-10-26 04:58:15 -0600

Rasmus gravatar image

updated 2014-10-26 06:07:08 -0600

I came up with a solution which worked well for me. Hough transform, and the variant described above, was useful for finding the number of overlapping circles and their approximate centers, but significant optimization was required afterwards for finding the exact sizes. I also found that it was difficult to find parameter settings which worked well for all scales (in particular small circles partly overlapping large ones). Instead I did like this:

1) Get the outer contours for each connected component 2) Get the convex hull for the contour 3) Calculate the distance to the hull for each point in the contour 4) Local maxima in the distances correspond to intersection points between the circles. Split the contour at these points and fit a circle to each segment

I found this to be an easier and faster solution, but most importantly it seems to be much more robust. It typically finds all relevant circles, but there is a risk of duplicates which should be filtered out afterwards.

Here's an example:

Original

image description

After circle detection (green objects with black fitted circles)

image description

edit flag offensive delete link more

Comments

That sound interesting. Could you post some images of your result?

FooBar gravatar imageFooBar ( 2014-10-26 05:21:55 -0600 )edit
1

Sure, see above

Rasmus gravatar imageRasmus ( 2014-10-26 05:33:44 -0600 )edit

Great job! Would you mind also sharing your code? I didn't quite understand how you find the distances.

mrmashal gravatar imagemrmashal ( 2016-04-21 23:53:55 -0600 )edit

Question Tools

1 follower

Stats

Asked: 2014-09-30 01:14:44 -0600

Seen: 7,760 times

Last updated: Oct 26 '14