13
$\begingroup$

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

enter image description here

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)

enter image description here

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?

$\endgroup$
  • 2
    $\begingroup$ Is this helpful? mathworks.com/matlabcentral/fileexchange/… $\endgroup$ – Atul Ingle Mar 12 '13 at 5:31
  • $\begingroup$ @AtulIngle Extactly! Thanks. Could you add the answer so I can accept it? I will then try to edit the answer to elaborate more on the algorithm - but I don't want to just answer my own question using the link you provided... $\endgroup$ – Libor Mar 12 '13 at 23:40
  • $\begingroup$ Great! I'll look forward to reading your elaborate answer as I haven't read through the code. $\endgroup$ – Atul Ingle Mar 15 '13 at 19:28
  • $\begingroup$ @AtulIngle OK, I have added some discussion in the answer and link to a full article of mine. $\endgroup$ – Libor Mar 16 '13 at 23:49
9
$\begingroup$

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

enter image description here

The sample binary mask and computed map look like this:

enter image description here enter image description here

Taking maximum in the map reveals the largest inscribed square:

enter image description here

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:

enter image description here enter image description here

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.

enter image description here

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

enter image description here

$\endgroup$

protected by datageist Nov 21 '16 at 5:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.