What is a fast way to find all circle sizes? [closed]

Question

Given a completely black and white picture (so the only colors are black or white no shades of grays), there are a lot of different sizes circles on it (in black), what is a fast way to find the center coordinate of the circles and the sizes of the circles and store them as a Dictionary entry? When I mean fast I mean by if I were to call this circle finding function 10 or 20 times per second it wouldn't lag too much. Also I did some researching and found out that I could find the center of a circle or radius by taking three points on the circle, can that help?

Answer 1

The first thing that comes to mind is to scan the image pixel by pixel, looking for black pixels. When you find one, start flood filling. Once the Flood fill finishes measure the left, right, top, and bottom extents, then derive the center point by dividing by 2. This assumes that none of the circles overlap. I'm sure there are probably some more optimized methods that may avoid flooding the entire circle.

optimization #1: Instead of flood filling, when you find the first black pixel, look for adjacent pixels along all 8 neighbors that have at least 1 white neighbor. Continue following those pixels until you hit the first pixel again. That should give you the outline, from there you can derive the width, height, and center point the same way as in my original answer.

optimization #2: If the circles have a minimum size you don't have to scan pixel by pixel. You can scan horizontal and vertical lines spaced by the minimum size looking for black pixels.

Answer 2

I think you cannot avoid having to check all the white pixels, so the algorithm's complexity will always be O(width*height). However, you definitely don't need to check all the black pixels.

Once you find an edge of a circle you can just walk horizontally until next edge, and then vertically until another edge. With these 3 points on the edge you can build a rectangle which will have the same center as the circle. Then just walk vertically or horizontally to find the circle's radius.