寻找最大正方形以适应在图像绘制的多边形中的最佳方法

Question

我正在使用OpenCV将一堆视点匹配成全景图。结果是一堆黑色背景上的图片（类似于多边形形状）。我想做的是裁剪这个多边形，使得结果图像中没有黑色。有没有好的算法可以实现这个功能？

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

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

编辑：由于多边形是凹的，我们需要检查一下--我认为尝试每个顶点对的O(N^2)算法是可行的，因为N很小。但我们需要检查边界区域是否填充，我想可以通过检查每个顶点是否位于我们选择的顶点对定义的矩形边界内来以O(N)的时间完成。这给了我们一个O(N^3)的算法。

- user491880

Answer 1

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

如果多边形上没有太多顶点，则以下方法可能有效：尝试选择每个顶部和底部边缘的组合。为简化起见，假设它们总是包括多边形的一个顶点。当指定顶部和底部时，可以确定侧面，因此对于每对顶部/底部，可以计算出面积。选择给出最大面积的解决方案。

上述简化可能会导致次优结果，但不应太差。

- Gintautas Miliauskas

---

很酷的想法--然而问题在于对于任何给定的顶点对，可能没有填充区域。多边形通常是凹的。 - user491880

不安全的假设任何顶点。例如，多边形可能是一颗钻石。 - xan

Answer 2

假设多边形在离散的XY网格上是凸的。然后，多边形的整个形状可以由一个数组表示，每个Y坐标在网格中对应一个(x1,x2)对。通过跟踪多边形的边缘，您可以得到这个(x1,x2)对的数组。

你知道正方形至少要在两个对角点上接触多边形，要么是左上-右下，要么是左下-右上。

在每个左边缘点，您可以找到最靠近右侧、最靠近直接向上和向下的点，以及每个对角线上最近的点，即45度向上和向下。如果对角线上的距离小于或等于任何直角距离，则有一个适合多边形的正方形。可能会有多个，所以继续寻找最大的一个。

- Mike Dunlavey

Answer 3

考虑到全景图中可能存在的图片数量有限，您可以使用暴力方法并尝试所有可能的组合。用户永远无法察觉到差异，而且编写和维护该函数的速度可能会更快。但这样做就不那么有趣了。

- xpda

Answer 4

如果处理像素，请尝试距离变换，找到最大点，然后根据该位置扩展正方形/矩形以找到区域内的最大正方形，就像您提到的那样。

- Dave

Answer 5

似乎线性扫描算法很适合。从左边开始，以x增量为单位向右移动垂直线。在每个停止点，查看多边形内部的每条线段。（当它是凹多边形时可能会有多条线段）。考虑沿着线段的子线段。

然后从子线段的每个端点取水平线，并找到与多边形的交叉点（两个方向都要找），以找到包含该子线段的最大矩形。

性能可能是O(n_xn_y²)，但您可以通过启发式和自适应步长来减少它。

一种可能被太多假设或捷径忽略的情况是：

+------\    /---+
|       \  /    |
\        \/     /
 \             /
 /             \
/      /\       \
|     /  \      |
+----/    \-----+

- xan