Image Recognition Algorithm

[softwaremonkey]

Hi, I have a number of still images containing concentric circles and I would like to be able to detect the centre point of the circles. Are there any algorithms out there that would allow me to do this? Cheers, Tony

[Luc Pattyn]

the "Generalised Hough transform" may help havent seen the code tho. :)

Luc Pattyn [My Articles]

[Nathan Addy]

So if you're not familiar (or comfortable with making yourself familiar) with complex numbers, this may be a little useless, but here is my first guess as to how to do it. You should be able to find a conformal mapping (look it up on wikipedia, it's basically a function that takes lines to lines and circles to circles, preserving angles, if I remember correctly), and I actually think you want a specific type of conformal mapping called a Mobius Transformation (also look that up on wikipedia - it's a function of the form f(z) = (az + b)/(cz+d), where a,b,c, and d are complex numbers and ad - bc != 0). Moreover, I think the function is just 1/z (where z is a complex number), but you'd want to double check that. Anyway, there should be a Mobius Transformation that will transform your image so that your concentric circles are mapped to parallel lines, which I would imagine would be much easier to find, especially if the concentric circles are regularly spaced out. From there, you could either find the center point on your mapped image, and then take its inverse under your Mobius Transformation to find the original point, or you could find the lines and map those back through the Mobius Transformation. Then you'd basically have explicit equations for each of the circles that you could use to find your center points. So check out these Mobius Transformations; if you've got the math background, I suspect they would make your problem much easier. Mobius Transformation followed by the basic Hough Transform referenced above (not the generalized form necessarily -- if you do that, you shouldn't have to do any of this MT stuff) should solve your problem, for instance.

[Rilhas]

Some ideas given here seem good, but they will tend to be computationally heavy. My work involves real time image processing in many domains, and in general most algorithms that are called "transform" are usually unacceptably slow (even for modern computers or DSP's). This, of course, depends on wether or not you can distribute the algorithm through various machines. In general I can't. Anyway, without more details on your case I simply imagine white sheets of paper with concentric circles drawn in them. If this is the case then finding the center is a very fast and efficient operation. Simply compute the mass center of all "pen" pixels. For example, if they are black then just sum the positions where you find them (keep X and Y separate) and in the end just divide the result by the image size. For example: mass_center_x=0; mass_center_y=0; total_found=0; for(y=0; y<image_size_y; y++) { for(x=0; x<image_size_x; x++) { if (Pixel(x, y)==BLACK) { mass_center_x+=x; mass_center_y+=y; total_found++; } } } if (total_found>0) { mass_center_x/=total_found; mass_center_y/=total_found; } At this point the "mass_center_x" and "mass_center_y" contain the coordinates of the center of the concentric circles. This algorithm is very fast because each pixel is analyzed only once, and so runs in an amount of time directly proportional to the number of pixels. Also note that Y is the outer loop so as to exploit the CPU cache in the most efficient manner. I hope this helps, Rilhas -- modified at 8:28 Sunday 20th May, 2007