将图像区域（边界框）在线性时间内合并

Question

我有一组针对某个图像的区域（边界框），以下是示例Python代码：

im = Image.open("single.png")
pix = np.array(im)
gray = rgb2grey(pix)
thresh = threshold_otsu(gray)
bw = closing(gray > thresh, square(1))

cleared = bw.copy()
clear_border(cleared)
borders = np.logical_xor(bw, cleared)
label_image = label(borders)

for region in regionprops(label_image, ['Area', 'BoundingBox']):
    #now i have bounding boxes in hand

我想做的是合并重叠的区域或bbox边缘之间的距离小于X。天真的方法是检查所有区域之间的距离，这具有O(n²)的复杂度。我可以写一些更聪明的东西，但我有印象这种算法已经存在了，我不想重新发明轮子。任何帮助都将不胜感激。

- mnowotka

---

你是如何测量边界框之间的“距离”的？您指的是“边界框中的每条边最多距离X”还是“边缘之间的总距离为X”？另外，您希望如何将它们合并在一起？有不同的方法可以做到这一点，但有些可能会导致“级联”效应，在合并两个框后，新框随后需要与第三个框进行合并。 - templatetypedef

@templatetypedef 距离被定义为两个不同边界框之间的最短距离。合并是在要合并的边界框周围创建边界框。 - mnowotka

如果你简单地将所有的盒子都增加(distance/2)的距离，那么距离问题就会变得容易得多。这至少可以将问题减少到“盒子是否重叠”的程度。 - kazagistar

Answer 1

你的问题是 "有 n 个盒子（不一定 // 到 x-y 轴），你想找到所有重叠的盒子并将它们合并，如果存在的话？"

我还想不出一个线性算法，但我有一个比 O(n^2) 更快的想法，可能可以描述为 O(n lg n)，如下：

1. 给每个盒子一个 id，对于每条边，标记它所属的盒子
2. 使用 sweeping line algorithm 来查找所有交点
3. 在扫描线算法中，一旦报告了一个交点，你就知道哪两个盒子重叠了，使用类似不相交集合的东西将它们分组。
4. 最后线性扫描不相交集合，对于每个集合，保持更新最左、最右、最上、最下的点，以使一个更大的盒子来限定它们所有人（合并在此处完成，请注意，如果一个盒子与其他盒子没有重叠，则该集合只包含它本身）。

我希望这种方法能够奏效，而且应该比O(n^2)更快，但即使它奏效了，在第4步仍然存在一些问题，即较大的合并框必须//到x-y轴，这不是必须的。

编辑：抱歉，我再次阅读原始帖子后，发现上述解决方案无法解决“合并距离小于x的框”，甚至只解决了部分重叠框的问题。

此外，合并框的过程不是一次性完成的，它有点像递归，例如，合并框A和框B变成框C，那么框C可能与框D重叠/距离

对我来说，要在线性时间内解决这个任务几乎是不可能的，因为预先计算所有成对框之间的距离已经很难在O(n)内完成...

- shole