查找具有最大表面积（不包括交叉区域）的边界框轮廓

Question

我有一组来自对象检测系统的边界框。它们的格式如下：

[[x,y], [x,y], [x,y], [x,y]]

我想找到最大的边界框，该边界框既不与任何其他提供的框相交，也​​不位于排除的框内。

我正在使用 python，但欢迎使用任何编程语言进行回复:)

视觉示例

我如何尝试但未能解决这个问题。

方法一。

迭代每个点并找到 x 和 y 的最小值和最大值。

然后使用这些坐标裁剪为多边形。

问题是示例图像上的算法会删除图像的顶部部分，但没有必要这样做，因为我们“错过”了左上角和右上角的框。

方法二。

尝试选择一次仅裁剪一侧，因为通常在我的数据集中要排除的内容都在一侧。例如删除顶部 100px

所以我像以前一样计算了 x 和 y 的最小值和最大值。然后计算每个可能切割的面积 - 左、右、上、下，并选择面积最小的一个。

当图片两侧（如左右两侧）都有方框时，这种方法很快就会失败

Answer 1

考虑进行一次完整的重新调整（最初是整个图片）并拿走一个排除的盒子。你将得到 2x2x2x2=16 个可能的矩形细分，例如这个。

\n

  \xe2\x94\x8c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n  \xe2\x94\x82                        \xe2\x94\x82\n  \xe2\x94\x82                        \xe2\x94\x82\n  \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xa4\n  \xe2\x94\x82       \xe2\x94\x82  exc  \xe2\x94\x82        \xe2\x94\x82\n  \xe2\x94\x82       \xe2\x94\x82 lude  \xe2\x94\x82        \xe2\x94\x82\n  \xe2\x94\x82       \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xa4\n  \xe2\x94\x82       \xe2\x94\x82                \xe2\x94\x82\n  \xe2\x94\x82       \xe2\x94\x82                \xe2\x94\x82\n  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

对于细分中的每个框，去掉下一个排除的框。\n执行此操作 N 次，并取最后一步中最大的框。

\n