image - 找到适合图像上绘制的多边形的最大正方形的最佳方法

Question

我正在使用 OpenCV 将一堆视点匹配到全景图中。结果是黑色背景上的一堆图像(有点像多边形)。我想要做的是裁剪这个多边形，使生成的图像中没有黑色。是否有好的算法可以做到这一点？

我想的天真的方法是从图像中间的一个小方 block 开始向上扩展直到我碰到黑色，然后左右扩展。

我想要的解决方案是使填充区域的总面积最大化的解决方案。

编辑:多边形是凹的，所以我们需要对此进行检查——我认为尝试每个顶点对的O(N^2) 算法是可行的，因为N 很小。但是我们需要检查区域边界是否被填充，我想这可以在 O(N) 中完成，方法是检查每个顶点以查看它是否位于我们选择的顶点对定义的矩形边界内。这给了我们一个O(N^3) 算法

Answer 1

天真的解决方案可能效果不佳，因为通常使矩形变高会限制其宽度，因此您不会获得最佳解决方案。

如果您在多边形上没有太多顶点，则以下方法可能有效:尝试选取顶部和底部边缘的每种组合。为简化起见，假设它们将始终包含多边形的顶点之一。指定顶部和底部后，可以确定边，因此对于每对顶部/底部，您可以计算面积。选择给出最大面积的解决方案。

上面的简化可能会给出次优的结果，但应该不会太糟糕。