0

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)?

Akiiino
  • 1,050
  • 1
  • 10
  • 28
  • You can also check if the circumference points count is close to `2*Pi*r` where `r` is radius in pixels (half of bounding box size) ... no need to check distance for all points ... the same goes for area ... Also take a look at http://stackoverflow.com/a/37858301/2521214 – Spektre Jun 18 '16 at 07:38
  • The bounding box is absolutely not robust, for instance a thin line detected in the region will make the bounding box much larger and will cause the circle detection to fail. – galinette Jun 23 '16 at 11:10

1 Answers1

3

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.

galinette
  • 8,896
  • 2
  • 36
  • 87
  • This actually worked really well even without finding the border, because average of all points' distances from center is 2/3R. And with 95% tolerances I got a perfect recognition! – Akiiino Jun 20 '16 at 23:59
  • Good point, avoids the hassle of border detection which is difficult to make robust! I have edited the answer to include your idea. – galinette Jun 23 '16 at 11:15