Largest inscribed rectangle in an arbitrary polygon

Question

I have been working with OpenCV Stitching for a while. Now I want to take the last stitching step: crop the image. This allows you to find the largest inscribed axis-parallel rectangle in the general polygon.

I already looked through it and found the answers ( How to crop to the largest internal bounding box in OpenCV? ). The quality of the output image is good, despite the slow execution of the program (it takes 15 seconds to crop the image takes only 47 seconds to stitch 36 1600x1200 images into 1 panorama), since the algorithm used has a complex time complexity (for each point of the contour, it looks through everything dots in one row / column).

Any way to improve this? Thanks.

P / S: I also found this book:

Finding the largest axial parallel rectangle in a polygon

Karen Daniels and Victor Milenkovic Dan Roths Harvard University,

Department of Applied Sciences,

Center for Computer Science Research,

Cambridge, MA 02138.

June 1995

but I had no idea to inject the theory into code: v

Answer 1

You probably do not want to implement this algorithm; it will take quite a while, and I suspect that you will be disappointed with the performance, despite the fact that it is associated with OO.

It sounds like you are still working with the raster, so you can use the linear time algorithm to find the largest rectangle of zeros in the binary matrix.