使用Union-Find划分边界框

Question

我想划分一个边界框数组(坐标为[ymin, xmin, ymax, xmax])，就像本文[https://arxiv.org/pdf/1710.06677.pdf][1]中描述的那样。我的阈值将是将两个边界框分组在一起的交集超过并集。

我理解了Union-Find数据结构，并用一些简单的列表示例对其进行了测试。但是，这些列表只包含整数作为列表元素，而不是边界框，并且我的边界框分区实现不起作用。

我认为问题出在创建集合上。因为对于一个简单的列表，我可以将一个整数赋给一个列表索引。但是我不能使用边界框做到这一点，因此示例不适用于我的情况。

有没有人可以帮我实现边界框的联合查找数据结构？

我得到帮助的来源：

https://medium.com/100-days-of-algorithms/day-41-union-find-d0027148376d

https://www.geeksforgeeks.org/union-find/

https://www.cs.cmu.edu/~avrim/451f13/lectures/lect0912.pdf

A set union find algorithm

Answer 1

我设法让它工作了。首先，我计算了所有边界框之间的IOU，并将大于0.9的边界框标记为我的图的边。但是，此实现在边界框数量较多的情况下会出现RecursionError: maximum recursion depth exceeded in comparison错误。

我在代码中使用了来自https://medium.com/100-days-of-algorithms/day-41-union-find-d0027148376d 的实现

def find(data, i):
   if i != data[i]:
       data[i] = find(data, data[i])
   return data[i]

def union(data, i, j):
   pi, pj = find(data, i), find(data, j)
   if pi != pj:
       data[pi] = pj

connections = []
for i in range(len(boxes)):
   for j in range(i + 1, len(boxes)):
       iou = compute_iou(boxes[i], boxes[j])

       if iou >= 0.9:
          connections.append((i,j))

# data is a representation of the bounding to make it
# possible to create Union-Find sets   
data = [bb for bb in range(len(boxes))] 


for i, j in connections:
    union(data, i, j)