4

我有一些图像的一组区域（边界框），例如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 2 ) 复杂性。我可以写一些更聪明的东西，但我的印象是这种算法已经存在，我不想重新发明轮子。任何帮助表示赞赏。

4

1 回答 1

0

这是您的问题“有 n 个框（不一定// 到 xy 轴），并且您想找到所有重叠的框并在它们存在时合并它们吗？”

我还想不出线性算法，但我有一个比 O(n^2) 更快的粗略想法，也许 O(n lg n) 描述如下：

  1. 给每个盒子一个id，也为每个边缘，标记它属于盒子
  2. 使用扫线算法查找所有交点
  3. 在扫线算法中，一旦报告了一个交点，你就知道哪两个框是重叠的，使用 disjoint-set 之类的东西对它们进行分组。
  4. 最后线性扫描不相交集，对于每个集合，不断更新最左边、最右边、最顶部、最底部的点，以制作一个更大的框来将它们全部绑定（在这里合并完成，请注意，如果一个框与其他框没有重叠，则该集合只会包含它自己）

我希望这个方法能行得通，它应该比 O(n^2) 快，但即使它确实行得通，它在第 4 步仍然存在一些问题，其中较大的合并框必须是 // 到 xy 轴，即不是必须的。

编辑：对不起，我只是再次通过 OP，并且了解上述解决方案并没有解决“距离 < x 的合并框”，它甚至只解决了部分重叠框问题。

此外，合并框过程不是 1-pass 工作，它是一种递归，例如框 A 和框 B 合并成为框 C，然后框 C 可能与框 D 重叠/距离 < x ..等等.

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

于 2014-02-21T04:26:35.623 回答