largest inscribed rectangle in arbitrary polygon

Question

I've worked with OpenCV Stitching for a while. Now I want to do the last step of stitching: crop image. This leads to find the largest inscribed axis-parallel rectangle in general polygon.

I've already googled it and found some answers (How do I crop to largest interior bounding box in OpenCV?). The quality of output image is good despite the program run slowly (it takes 15 sec to crop image quite takes only 47 sec to stitch 36 1600x1200 pictures into 1 panorama) since the used algorithm have bad time complexity (for each point in the contour, it scan all point in same row/column).

Any way to improve this? Thanks.

P/S: I also found this book:

Finding the Largest Area Axis-Parallel Rectangle in a Polygon

Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,

Division of Applied Sciences,

Center for Research in Computing Technology,

Cambridge, MA 02138.

June 1995

but I didn't have any idea to implement the theory into code :v

Answer 1

You probably don't want to implement that algorithm; it would take quite a while, and I suspect that you would be disappointed with the performance in spite of the big-O bound.

It sounds as though you're working with a raster anyway, so you could use a linear-time algorithm for finding the largest rectangle of zeros in a binary matrix.