Maximum Inscribed Circle using Distance Transform

Maximum Inscribed Circle

Or in other words, "largest inner circle" , "maximum empty circle" etc.

This is a very common problem in computational geometry, and it is not simple to solve efficiently.

Addressing 2D image/contour processing, I couldn't find a good implementation on the web. Generally, the reasonable way of solving this problem is to make use of Voronoi Diagrams, which are generally O(nlogn).

After analyzing the problem a bit, I noticed that the problem can easily and approximately be solved using well-known distance transform.

Here is how:

The computational aim can be written as:

(x, y) maximizes r = min_{i} r_{i}
where r_i = ||(x_i, y_i) − (x, y)|| and d_i = r_i − r

(x_i, y_i): Pairs data points
(x, y), r : Pair, scalar circle centre and radius

In non-mathematical terms:

1. The center of the maximum inscribed circle will lie inside the polygon
2. The center of such a circle will be furthest from any point on the edges of the polygon.

So we seek for the point that lies inside the polygon and has maximal distance to the closest edge. This is exactly the maximum value of the pixel (of DT) that lies inside the contour.

Notice that this approach is completely in-precise. It is only pixel-precise and never subpixel accurate. However, unlike optimization approaches, it does guarantee a global convergence. In the case of ambiguity, any of the solutions will be valid.

To detect the points inside the region, inpolygon remains very slow. So, I make use of the great code of Darren Engwirda, here. As well as being contained in this package, it can also be downloaded from:
http://www.mathworks.com/matlabcentral/fileexchange/10391-fast-points-in-polygon-test

Here are other implemnatations, which are more accurate, but much slower than my approach (only slower in Matalb of course!)

http://www.mathworks.com/matlabcentral/fileexchange/2794-cvoronoi

Using "Largest pixel that doesn't cross any point" approach:
http://www.mathworks.com/matlabcentral/newsreader/view_thread/283296

--------

Here is a sample call:

I=imread('hand_contour.png');
[R cx cy]=max_inscribed_circle(I)

The max_inscribed_circle function, finds the boundaries of the image, traces them and retrieves a boundary, where neighboring pixels follow each other. It uses the points on the boundary to compute the maximum inscribed circle

Cheers,