OpenCV Q&A Forum - RSS feedhttp://answers.opencv.org/questions/OpenCV answersenCopyright <a href="http://www.opencv.org">OpenCV foundation</a>, 2012-2018.Thu, 21 Apr 2016 23:53:55 -0500Detecting overlapping circleshttp://answers.opencv.org/question/43195/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: http://medicine.emory.edu/id/labs/lyon/yeast.bmp
Any help is very welcome! Feeling rather lost in this field :)Tue, 30 Sep 2014 01:14:44 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/Comment by Rasmus for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43234#post-id-43234Thanks 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...Tue, 30 Sep 2014 08:02:39 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43234#post-id-43234Comment by Rasmus for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43235#post-id-43235...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.. :)Tue, 30 Sep 2014 08:05:34 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43235#post-id-43235Comment by Haris for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43264#post-id-43264Have a look on [Morphology Transformations](http://docs.opencv.org/doc/tutorials/imgproc/opening_closing_hats/opening_closing_hats.html), you need to proceed like, threshold->morphology->contour analysis etc...Tue, 30 Sep 2014 21:34:15 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43264#post-id-43264Comment by Rasmus for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43236#post-id-43236Sorry, small number of closely aligned points I mean. So that only some small fraction of the circle is actually covered.Tue, 30 Sep 2014 08:06:48 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43236#post-id-43236Comment by thdrksdfthmn for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43222#post-id-43222Have you tried the [hough_circles](http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_circle/hough_circle.html)? Or a kind of binarization and then [fitellipse](http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rotated_ellipses/bounding_rotated_ellipses.html); if it is too elliptic/long, then there are more circles (approximatively hi_ray/lo_ray)? Tue, 30 Sep 2014 04:58:02 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=43222#post-id-43222Answer by Rasmus for <p>Hi all,</p>
<p>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..</p>
<p>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.</p>
<p>I know nothing about computer vision/pattern recognition, but this is my naive approach so far:</p>
<p>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)</p>
<p>2) Find all the individual shapes (connected non-zero regions in the map above)</p>
<p>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.</p>
<p>4) (Optional. Use the input from 3) to perform a constrained heuristic optimization to fine tune the fittings.)</p>
<p>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.</p>
<p>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: <a href="http://medicine.emory.edu/id/labs/lyon/yeast.bmp">http://medicine.emory.edu/id/labs/lyon/yeast.bmp</a></p>
<p>Any help is very welcome! Feeling rather lost in this field :)</p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?answer=45545#post-id-45545I 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](/upfiles/14143194886479089.jpg)
After circle detection (green objects with black fitted circles)
![image description](/upfiles/1414319525873745.jpg)Sun, 26 Oct 2014 04:58:15 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?answer=45545#post-id-45545Comment by mrmashal for <p>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:</p>
<p>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</p>
<p>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. </p>
<p>Here's an example:</p>
<p>Original</p>
<p><img alt="image description" src="/upfiles/14143194886479089.jpg"></p>
<p>After circle detection (green objects with black fitted circles)</p>
<p><img alt="image description" src="/upfiles/1414319525873745.jpg"></p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=93443#post-id-93443Great job! Would you mind also sharing your code? I didn't quite understand how you find the distances.Thu, 21 Apr 2016 23:53:55 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=93443#post-id-93443Comment by Rasmus for <p>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:</p>
<p>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</p>
<p>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. </p>
<p>Here's an example:</p>
<p>Original</p>
<p><img alt="image description" src="/upfiles/14143194886479089.jpg"></p>
<p>After circle detection (green objects with black fitted circles)</p>
<p><img alt="image description" src="/upfiles/1414319525873745.jpg"></p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=45549#post-id-45549Sure, see aboveSun, 26 Oct 2014 05:33:44 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=45549#post-id-45549Comment by FooBar for <p>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:</p>
<p>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</p>
<p>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. </p>
<p>Here's an example:</p>
<p>Original</p>
<p><img alt="image description" src="/upfiles/14143194886479089.jpg"></p>
<p>After circle detection (green objects with black fitted circles)</p>
<p><img alt="image description" src="/upfiles/1414319525873745.jpg"></p>
http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=45548#post-id-45548That sound interesting. Could you post some images of your result?Sun, 26 Oct 2014 05:21:55 -0500http://answers.opencv.org/question/43195/detecting-overlapping-circles/?comment=45548#post-id-45548