0

I want to partition an array of bounding boxes (with coordinates [ymin, xmin, ymax, xmax]) as it is described in this paper [https://arxiv.org/pdf/1710.06677.pdf][1]. My threshold will be intersection over union for grouping two bounding boxes together.

I understood the Union-Find data structure, and tested it with some easy list examples. However, those lists contain just integers as list elements as opposed to bounding boxes, and my bounding box partitioning implementation does not work.

I think the problem is with creating the set. Because with a simple list, I can assign an integer to a list index. But I can't do this with bounding boxes, hence the examples don't work for my case.

Is there anyone who could help me implement a Union-Find data structure for bounding boxes?

Sources I got help:

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

kneazle
  • 335
  • 4
  • 14

1 Answers1

0

I managed to make it work. First I computed IOU between all bounding boxes, and marked the ones > 0.9 as an edge to my graph. However this implementation gets RecursionError: maximum recursion depth exceeded in comparison error with high number of bounding boxes.

I used the implementation from https://medium.com/100-days-of-algorithms/day-41-union-find-d0027148376d for my code

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)
kneazle
  • 335
  • 4
  • 14