9

What are the possible fast ways to detect circle in an image ?

For ex: i have an image with one Big Circle and has 6 small circles inside big Circle.

I need to find a big circle without using Hough Circles(OpencV).

Pixel
  • 419
  • 4
  • 7
  • 17
  • Do you know the size of the circles? Then a simple correlation approach might do the trick. – Herr von Wurst Apr 08 '13 at 11:51
  • No, we don't know the size of the circle and also please suggest idea how to find if we know the circle size :P – Pixel Apr 08 '13 at 11:59
  • Actually the hough transformation is very fast and maybe the only good solution. The hough transform of opencv uses the canny operator to get the edges. The canny operator is the bottleneck. Maybe you can handwrite a code to find the edges of your image. Correlation uses float values and multiplication. I would say correlation needs more time (for big objects really a lot of time) and is not more accurate. It can be that the hough transform of opencv isn t very well coded maybe you could rewrite it to make it faster. – jamk Apr 08 '13 at 12:12
  • As with any image processing question, please post an image (no matter how simple). To Georg's comment: it would help to know whether the circles can have a radius of 10 pixels, 100 pixels, 1000 pixels, or ten million pixels, even if you only have an order of magnitude estimate. – Rethunk Apr 09 '13 at 13:49
  • OpenCV actually has a sample application for circle detection using Hough. – Roger Rowland Apr 09 '13 at 14:08

2 Answers2

14

Standard algorithms to find circles are Hough (which jamk mentioned in the comments) and RANSAC. Parameterizing these algorithms will set a baseline speed for your application.

http://en.wikipedia.org/wiki/Hough_transform

http://en.wikipedia.org/wiki/RANSAC

To speed up these algorithms, you can look at your collection of images and decide whether limiting the search ranges will help speed up the search. That's straightforward enough: only search within a reasonable range for the radius. Since they take edge points as inputs, you can also look at methods to reduce the number of edge points checked.

However, there are a few other tricks to speed up processing.

  • Carefully set the range or ranges over which radii are checked. For example, you might not simply check from the smallest possible radius to the largest possible radius, but instead you might split the search into two different ranges: from radius R1 to R2, and then from radius R3 to R4.
  • Ditch the Canny edge detection in favor of the fastest possible edge detection your application can tolerate. (You can ditch Canny for lots of applications.)
  • Preprocess your image of edge points to eliminate outliers. The appropriate algorithm to eliminate outliers will be specific to your image set, but you'll probably be able to find an algorithm that eliminates obvious outliers and thereby saves some search time in the more expensive circle fit algorithms.
  • If your circles are very well defined, and all or nearly all points are present, figure out how you might match only a quarter circle or semicircle instead of a full circle.

Long story short: start with a complete implementation and benchmark it, then gradually tighten up parameter settings and limit search ranges while ensuring that you can still find circles for your application and your image set.

If your images are amenable to scaling, then one possibility is to create an image pyramid of images at different scales: 1/2 scale, 1/4 scale, 1/8 scale, etc. You'll need an edge-preserving scaling method at smaller scales.

Once you have your image pyramid, try the following:

  1. Find circles at the very smallest scale. The image will be small and the range of possible radii will be limited, so this should be a quick operation.
  2. If you find a circle using the initial fit at the small scale, improve the fit by testing in the next larger scale image -OR- go ahead and search in the full scale image.
  3. Check the next largest scale. Circles that weren't visible in the smaller scale image may suddenly "appear" in the current scale.
  4. Repeat the steps above through all scales in the image.

Image scaling will be a fast operation, and you can see that if at least one of your circles is present in a smaller scale image you should be able to reduce the total number of cycles by performing a rough circle fit in the small scale image and then optimizing the fit for those edge points alone in the full scale image.

Edge-preserving scaling can also make it possible to use correlation-type tools to find circles, but being able to do so depends on the content of your images, including the noise, how completely edge points represent circles, and so on.

Rethunk
  • 3,976
  • 18
  • 32
  • 1
    Good answer, although Hough is robust in the face of noise, it does require pretty "perfect" circles for good performance. +1 anyway. – Roger Rowland Apr 09 '13 at 14:07
  • 1
    Thanks, Roger. I'll sometimes tweak a Hough fit to allow for a bit of positional sloppiness for edge points that may lie +/- N pixels away from a true circle. Other ad hoc tweaks to the basic Hough technique have worked well for me in the past. – Rethunk Apr 10 '13 at 23:50
  • "tweak a Hough fit" do you mean by that modifying the openCV source code to fit your needs? – LandonZeKepitelOfGreytBritn Mar 04 '17 at 01:08
  • You could certaibly modifybtue OpenCV code, perhaps by copying and pasting, changing the function name, and then making modifications as needed. To understand how to modify Hough, though, I would recommend writing your own function from scratch. Test some ideas without worrying too much at first about optimizing for speed. Once you can write and modify a Hough algorithm from scratch, you'll be in a much better position to understand and modify the code in OpenCV or some other library. – Rethunk Mar 05 '17 at 03:00
1

Maybe, detect contours and check their properties, e.g. try to use cv::isContourConvex or another way could be to use the eigenvalues of the covariance matrix and check if contour's representative ellipse first eccentricity is ~0.

LovaBill
  • 5,107
  • 1
  • 24
  • 32