7

I am using OpenCV to detect ellipses in a binary image as shown below. In the image, there are eight ellipses to be detected. I can use findContours to obtain a lot of contours including the eight ellipses. The problem is: how can I judge and which one is ellipse which one is not? How to remove all the other false detections?

enter image description here enter image description here

Shiyu
  • 455
  • 4
  • 9

4 Answers4

8

In this specific case, the Hough Circle Transform is probably the easiest solution.

Copy the code from the tutorial and change the parameters of cv::HoughCircles() to:

/// Apply the Hough Transform to find the circles
HoughCircles( src_gray, circles, CV_HOUGH_GRADIENT, 1, 10, 40, 30, 0, 0 );

Output:

enter image description here

But I loved @George's idea, go with it, it's more robust than specifying hardcoded constants. My approach works great for this image, but if you have images with different sizes of circles and stuff, you want to use cv::minEnclosingCircle().

karlphillip
  • 92,053
  • 36
  • 243
  • 426
7

One option is a bit hacky: On top of findContours use minEnclosingCircle and filter contours by min. enclosing radius based on a threshold value (remove smaller than radius A (remove tiny blobs) and greater than radius B( remove huge blobs)). You can also try minAreaRect and check width/height ratio to look for uniform blobs rather than tall/wide ones.

The less hacky solution is to use Hough transforms. Have a look at the hough circle and the tutorial

George Profenza
  • 50,687
  • 19
  • 144
  • 218
  • Thank you. I think it is useful to remove too large or too small ones. In fact, I have an idea that using Hu's moments to remove false detection. That means: first compute Hu's moments of a number of training ellipses. Then for each contour, compute its Hu's moments, if they are very different from the training ones, then we can exclude that contour. Do you think this idea is useful? – Shiyu Apr 16 '13 at 13:21
  • I haven't used Hough moments myself so can't advise from experience. hough circles sounds like it does what you need. sorry I can't be of much more assistance – George Profenza Apr 16 '13 at 13:40
  • @George Profenza: Thank you anyway. – Shiyu Apr 17 '13 at 01:41
1

Now I think I have successfully solve the problem using my own algo. Just post it for future reference.

As shown below, all the ellipses can be accurately located. And false detections are successfully removed. On the other hand, the algo is very time efficient: 0.03s for all image processing on my normal desktop. Image size: 448x336 pixel

Procedure of the algo:

  1. detect contours from the binary image using function findContours
  2. remove too small ones by setting a threshold of the minimum size of a contour
  3. detect ellipses using the function fitEllipse
  4. compare the contour with the corresponding ellipse. Specifically, substitute all the contour points into the general ellipse equation (see http://www.maa.org/joma/volume8/kalman/general.html). Then compute the algebraic error. If the error is smaller than a threshold, then exclude that contour.

enter image description here

EDIT: Comments on George Profenza and karlphillip's answers. Thank George Profenza and karlphillip for their answers. However, their answers can not solve the problem well. The first idea given by George Profenza is to set threshold for the size of the contours. In fact, I have used that in my algo. But obviously that is an preliminary step of the algo. There are many false detections of "good" size. The second idea of George Profenza is to use HoughCircles, which is also proposed by karlphillip. The problem of HoughCircles is: (a) it is slow, while I need to implement the algo in real time in embedded systems. (b) it can only detect circles but not ellipses. Of course, when the ellipse is close to a circle, it also works. But for general cases, it doesn't. Moreover, my method above cannot detect the "figure 8". It is a big problem and I am still working on it.

Shiyu
  • 455
  • 4
  • 9
  • It appears your algorithm missed the two ellipses in the lower right corner (the "figure 8"). Is this a problem? Note that the Hough method found them. – Throwback1986 Apr 23 '13 at 04:08
  • 1
    Yes. I'm curious as to whether you used Hough circle. This problem seems like the right problem for it as suggested by George and Karl above. In general, methods such as Hough transform tends to be more robust than just simple heuristics. – lightalchemist Apr 23 '13 at 04:17
  • @Throwback1986: Thanks for your comments. First of all, the reasons I don't use HoughCirlces is because: (a) it is slow (right?), while I need real-time implementation in embedded systems. (b) it can only find circles but not ellipse (right?). Of course, it can also find ellipses when the ellipse is close to a circle. Second of all, the "figure 8" is a big problem indeed. In fact, I am still working on it. Any ideas for that? – Shiyu Apr 23 '13 at 06:17
  • @lightalchemist: thanks for your comments. Please see my response above. – Shiyu Apr 23 '13 at 06:18
  • 1
    @Shiyu: Have you confirmed that the Hough circles technique is too slow for your application? – Throwback1986 Apr 24 '13 at 00:28
  • @Throwback1986: Just now I tested the houghcircles on several images. It turns out I was wrong and HoughCircles is not very slow. On my desktop, the computational time of this function is 0.03-0.09 sec. But the problem is it cannot detect ellipses. I'm think how possibly it can be integrated into my algo. – Shiyu Apr 24 '13 at 02:11
  • @Shiyu Thank you for sharing your algorithm. Regarding the figure 8, I'm not sure if it will work, but could you also a apply an [erode, then a dilate filter](http://docs.opencv.org/doc/tutorials/imgproc/erosion_dilatation/erosion_dilatation.html) ? I'm hoping the erode will separate the 8 into two elements and the later dilate will get them close to the original size. It's worth adding a couple of trackbars to easily fiddle with the values a bit first until finding the right range/balance between erode and dilate amounts. HTH – George Profenza Apr 24 '13 at 07:07
  • @George Profenza: Thank you. In fact, I have included erode and dilate (open when combined) in my algo. I just used them to remove tiny noises. Also I can use them to try to avoid the connected cases. But since my algo is supposed to be workable in various conditions, it is necessary to solve the "figure 8" problem anyway. – Shiyu Apr 24 '13 at 12:31
1

Although another answer has been previously accepted, there are several options to be explored, so I'll add another answer. Assuming that a Hough method is fast enough for your application, here are some interesting alternatives:

  1. Ellipse detection with OpenCV
  2. http://toyhouse.cc/profiles/blogs/modified-hough-ellipse-transform-detecting-ellipse-in-an-accurate
  3. http://www.codeforge.com/article/131943
  4. And the paper I added in the comments above: http://www.bmva.org/bmvc/1988/avc-88-041.pdf

I might also add that Hough is likely to be the "right" way to proceed in reliably detecting ellipses, but you may run into additional challenges. You indicate that Hough circles is fast enough on your desktop, but how well does the performance of the desktop match that embedded system? Does the embedded system have a floating point unit? If not, don't be too alarmed by the performance exhibited by software-emulated floating point. You may still be able to implement the Hough algorithm satisfactorily using fixed-point math, lookup-tables, etc.

Community
  • 1
  • 1
Throwback1986
  • 5,887
  • 1
  • 30
  • 22