我跟OpenCV的拼接工作了一段时间。现在，我想要做的拼接的最后一步：裁剪图像。这导致发现在一般的多边形的最大内切轴平行矩形。

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.

我已经用Google搜索了一下，发现了一些答案（How我农作物最大的内部边框在OpenCV中？）。输出图像的质量，尽管程序运行缓慢良好的（它需要15秒作物图像相当仅需47秒缝36 1600×1200的照片变成1全景）在外形上，因为所使用的算法有坏的时间复杂度（每个点，它扫描在同一行/列的所有点）。

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：我也发现了这本书：

P/S: I also found this book:

查找面积最大的轴平行矩形的多边形

Finding the Largest Area Axis-Parallel Rectangle in a Polygon

卡伦·丹尼尔斯Ÿ维克多Milenkovicz丹Rothx哈佛大学，

Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,

应用科学部

在计算技术研究中心，

剑桥，马萨诸塞州02138。

Cambridge, MA 02138.

1995年6月

但我没有任何想法来实现理论到code：v

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

推荐答案

您可能不想执行该算法;这将需要相当长一段时间，我怀疑你会很失望的表现，尽管在大O的限制。

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.

这听起来好像你正在使用的光栅，无论如何，这样你就可以使用linear-time算法寻找零的最大矩形的二进制矩阵。

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.