circle detection algorithm?

May 20, 2006 7:19 AM

computer vision: i need an algorithm to extract statistics about the diameters (in pixels) of some roughly-circular objects from an image file.

i have many, many files that are grayscale images of some spherical objects. they are relatively high-contrast and so i should be able to do some kind of easy thresholding and/or edge detection to bring out the edges. but what i need to do is parameterize the circles - i need a count of circles in each picture, and a measurement of each circle's radius so that i can get an idea of the size distribution.

i understand that the hough transform can be used to parameterize lines and circles, but for the circles you need to know the expected radius beforehand. i could brute-force it and simply feed in a range of expected radii and have it step through each one, but that's both computationally demanding and i am particularly interested in the outliers, which this method might miss.

can anyone point me to an algorithm that might do what i'm looking for? is such a thing in the machine vision canon? it's been a long time since i took this course. thanks, askme!

posted by sergeant sandwich to computers & internet (15 comments total)

Sounds like you want to apply morphological thinning to an acquired image to reduce your data to something more tractible.
posted by plinth at 7:22 AM on May 20, 2006

well. okay. thinning is probably a good idea and would make the circles clearer, but how does it get me the radius?
posted by sergeant sandwich at 7:47 AM on May 20, 2006

Just off the top of my head, a partial heuristic. You could quantize the image into significant threshold steps, and do this after applying a Gaussian blur at increasing diameters. Differenceing this set of images one from the other will show highest values at the most non-round features. Use this to mask content from the original picture, then morphologically thin the results down. A secondary scheme could be used to detect two or more circles with overlapping perimeters.
posted by StickyCarpet at 7:58 AM on May 20, 2006

Once you've thresholded the image, if it's clean (and the circles don't overlap!), you can cluster the points in the circles and then, assuming each cluster corresponds to a circle, just find the distance between the two farthest points in each cluster, which will be each circle's diameter. If the circles do overlap, then the problem will be a lot more serious.

To cluster the thresholded points, pick one and recursively add all adjacent points that are also ON (or OFF, depending on whether the circles are in the figure or ground). Once you've created a cluster, remove all the points in it from the list of available points.
posted by driveler at 8:03 AM on May 20, 2006

The magnitude of the individual hierarchical blur differences I mentioned, usually called a Laplacian pyramid, could give indications of the diameter of the roundness at progressive diameters. Use the Hough transform to search the appropriate range of diameters for each detected roundness level. (you would actually be detecting non-roundness and subtracting.)
posted by StickyCarpet at 8:17 AM on May 20, 2006

I did a bit of circle fitting a couple of years ago, and learned a little. Fitting circles accurately is a hard problem, so bear with the long post:

Once you have the edge points, fitting the circle is usually* done with a least squares algorithm, that is, minimizing the sum of the squares of the distance between the center and each point, minus the radius:

f(x0, y0, R) = sum[(sqrt{(x0-xi)^2+(y0-yi)}-R)^2]

You can probably tell from all the brackets that this isn't a linear problem, so you have to solve it iteratively. The fastest and most reliable nonlinear least-squares algorithm is the Levenberg Marquardt method, of which you can find free implementations in Fortran, and Python, C (and probably other languages).

Unfortunately, f(x0, y0, R) has some pretty steep cliffs, and flat valleys that can confuse iterative solvers. Luckily you can smooth out the objective function by refactoring it as f(A, B, C) as described in Chernov & Lesort. This is what I ended up using, and have had very good results.

If you have edge data that's evenly distributed around the entire circumference, you can get away with minimizing the square of the distances between the center and each point

f = sum[(xi - x0)^2 + (yi-y0)^2 - R^2)^2]

This is called the "Algebraic Fit", and it can be reduced to a linear function which you can solve in one step by inverting a matrix. Careful, if your points are not evenly distributed this method will bias your center point towards the denser points.

*There's another approach to circle fitting called the "Minimum Width Annulus" method. This is a bit harder to calculate, as you need to know about Voronoi diagrams, aka, Delaunay Triangulation. But if you can put it together (I never did), this method will find a global solution without having to have an initial guess for the center point & radius.

Unfortunately I can't help you find the edge points. I haven't had to do that yet ;)
posted by Popular Ethics at 8:26 AM on May 20, 2006

um.... how about counting the pixels in each circle and from that knowing the area, then calculate the diameter from that? question is, how rough are these circles?
posted by garethspor at 9:08 AM on May 20, 2006

If you can assume that all objects are circles (you don't say if there are other objects in the picture) then you can estimate the diameter of each one by measuring the area, which is as simple as counting pixels.
posted by cillit bang at 9:08 AM on May 20, 2006

What's your budget? Image Pro Plus should be able to handle this. We use it to threshold and find centroids of markers to determine strain fields non-invasively. I don't remember exactly, but I think we probably paid $5k or so.
posted by mbd1mbd1 at 9:51 AM on May 20, 2006

Do you have access to Matlab? It's got great image processing tools, including nice-n-easy Hough transform. A google search for "matlab circle detection" reveals this function, as well as links to many others.

And! If you have non-circular objects (or even if you don't), here's a script written by mathworks that'll identify roundish objects first. You can certainly derive the diameters from this.

In sum, I vote Matlab.
posted by metaculpa at 10:03 AM on May 20, 2006

I don't know if it has what you are looking for or not, but you might want to check out ImageJ and it's various plugins. I know that it's predecessor, NIH image, had all sorts of powerful scientific image analysis tools a decade ago.
posted by Good Brain at 11:19 AM on May 20, 2006

Maybe this cell counter plugin?
posted by Good Brain at 11:21 AM on May 20, 2006

We've had very good luck with this implementation of the circular Hough transform in Matlab. It's pretty fast - it can find all circular objects between 5 and 35 pixels in diameter in a 600x700 pixel image in about 10 sec on a PC.

The outliers may still be a problem, as you mention, but perhaps if your images are simple enough you can just look for residuals in the image unexplained by what the Hough transform has found.
posted by pombe at 1:05 PM on May 20, 2006

thanks everyone. there are some excellent ideas here!
posted by sergeant sandwich at 2:30 PM on May 21, 2006

The least-squares algorithm I posted is a little more complex than some of the others proposed above, but it has the following advantages:

• You don't have to recognize every pixel belonging to the objects, as you would with an area counting method.
  
• You can get accurate results with overlapping or partial images.
  
• Even if your edge detection is weak, as long as the detected points are randomly distributed around the true edge, the fit will still be accurate
  
• The result will give you error bars on each parameter (center x, center y, radius)

These advantages may not outweigh the extra calculation for your specific task (you still have to do edge detection & object isolation), but if you're interested I have some Python code for doing the fitting (email is in my profile).
posted by Popular Ethics at 4:56 PM on May 21, 2006