Automatic Cropping of Arbitrary Shapes

Question

I have an arbitrary shape defined by a binary mask (gray = shape, black = background).

I would like to find a largest possible rectangle containing only gray pixels (such rectangle is pictured in yellow):

The shape is always "one piece" but it is not necessarily convex (not all point pairs on the shape's boundary can be connected by a straight line going through the shape).

Sometimes many of such "maximum rectangles" exist and then further constrains can be introduced, such as:

• Taking the rectangle with its center nearest to shape's center of mass (or center of image)
• Taking rectangle with aspect ratio nearest to a predefined ratio (i.e. 4:3)

My first thought about the algorithm is the following:

1. Compute distance transform of the shape and find its center of mass
2. Grow square area while it contains only shape's pixels
3. Grow the rectangle (originally a square) in width or height while it contains only shape's pixels.

However, I think such algorithm would be slow and would not lead to optimal solution.

Any suggestions?

Answer 1

There is a code on Matlab Fileexchange that is relevant to your problem: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle/content/html/Inscribed_Rectangle_demo.html

Update

I wrote this tutorial article on computing largest inscribed rectangles based on the above link from Atul Ingle.

The algorithm first searches for largest squares on a binary mask. This is done using simple dynamic programming algorithm. Each new pixel is updated using the three neighbors already known:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

The sample binary mask and computed map look like this:

Taking maximum in the map reveals the largest inscribed square:

The rectangle searching algorithm than scans the mask two more times looking for two classes of rectangles:

• width greater than square's size (and height possibly smaller)
• height greater than square's size (and width possibly smaller)

Both classes are bounded by the largest squares since no rectangle at a given point can have both dimensions greater than the inscribed square (though one dimension can be larger).

One have to choose some metric for rectangle sizes, like area, circumference or weighted sum of dimensions.

Here is the resulting map for rectangles:

It is convenient to store position and size of the best rectangle found so far in a variable instead of building maps and then looking for maxima.

The practical application of this algorithm is cropping non-rectangular images. I have used this algorithm in my image stitching library SharpStitch: