How do I check if a region is a circle?

Question

So, I have an assignment: to use modification of Kruskal's algorithm to separate an image into regions and identify which of them are circles and print their radii.

Finding regions is relatively simple, I did that. Finding circles is trickier, though. My idea is to find all border points of a region, find average point – possible center of this circle – and compute distances between each border point and 'center'. Then, if they do not differ much, this indeed is a circle.

First of all, is this even viable? Secondly, this method will recognize very thin rings as circles as well, and I don't want that. How do I fix this?

UPD: How do I effectively find border points? Last layer of BFS? Points with less than 6 neighbours (looks like bruteforce to me, though)?

Answer 1

Once you have estimated the radius by averaging the distance of border points to the center, compute :

• The area A1 of the intersection of the region and the circle
• The area A2 of the circle
• The area A3 of the region

Then, ratios of these areas should be close to 1 if this is a disk. You may define some tolerances. For instance:

• A1/A2 > 0.98
• A1/A3 > 0.97

Alternatively, the radius can be estimated without having border points. Just compute the average distance of every region point to the center, and multiply by 3/2.