Разметка ограничивающих рамок с помощью Union-Find

Question

Я хочу разделить массив ограничивающих прямоугольников (с координатами [ymin, xmin, ymax, xmax]), как описано в этой статье [https://arxiv.org/pdf/1710.06677.pdf][1]. Мой порог будет пересечением по объединению для группировки двух ограничивающих прямоугольников.

Я понял структуру данных Union-Find и протестировал ее на нескольких простых примерах.Однако эти списки содержат только целые числа в качестве элементов списка, а не ограничивающие прямоугольники, и моя реализация разбиения ограничивающего прямоугольника не работает.

Думаю, проблема в создании набора.Потому что с помощью простого списка я могу назначить целое число на индекс списка.Но я не могу сделать это с помощью ограничительных блоков, поэтому примеры не работают для моего случая.

Есть ли кто-нибудь, кто мог бы помочь мне реализовать структуру данных 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

Алгоритм поиска объединенного множества

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)