计算两个列表的所有 IoU 的有效方法

Question

我有一个函数来计算两个矩形/边界框的 IoU。

def intersection_over_union(boxA, boxB):
    # determine the (x, y)-coordinates of the intersection rectangle
    xA = max(boxA[0], boxB[0])
    yA = max(boxA[1], boxB[1])
    xB = min(boxA[2], boxB[2])
    yB = min(boxA[3], boxB[3])

    # compute the area of intersection rectangle
    interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)

    # compute the area of both the prediction and ground-truth
    # rectangles
    boxAArea = (boxA[2] - boxA[0] + 1) * (boxA[3] - boxA[1] + 1)
    boxBArea = (boxB[2] - boxB[0] + 1) * (boxB[3] - boxB[1] + 1)

    # compute the intersection over union by taking the intersection
    # area and dividing it by the sum of prediction + ground-truth
    # areas - the interesection area
    iou = interArea / float(boxAArea + boxBArea - interArea)

    # return the intersection over union value
    return iou

现在我想用另一个列表的 bbox 计算一个列表的 bbox 的所有 IoU，即如果列表 A 包含 4 个 bbox，列表 B 包含 3 个 bbox，那么我想要一个 4x3 矩阵，结果是所有可能的 IoU。

当然我可以用两个这样的循环来做到这一点

import numpy as np

n_i = len(bboxes_a)
n_j = len(bboxes_b)
iou_mat = np.empty((n_i, n_j))
for i in range(n_i):
    for j in range(n_j):
        iou_mat[i, j] = intersection_over_union(bboxes_a[i], bboxes_b[j])

但是这种方法很慢，尤其是当列表变得非常大时。

我正在努力寻找更有效的方法。必须有一种方法可以利用 numpy 来摆脱循环，但我不明白。现在的复杂度也是 O(m*n)。有没有可能降低复杂性？

Answer 1

矢量化：

low = np.s_[...,:2]
high = np.s_[...,2:]

def iou(A,B):
    A,B = A.copy(),B.copy()
    A[high] += 1; B[high] += 1
    intrs = (np.maximum(0,np.minimum(A[high],B[high])
                        -np.maximum(A[low],B[low]))).prod(-1)
    return intrs / ((A[high]-A[low]).prod(-1)+(B[high]-B[low]).prod(-1)-intrs)

AB = iou(A[:,None],B[None])

复杂：

由于您正在计算 M x N 值，除非大多数值为零并且矩阵的稀疏表示是可以接受的，否则不可能将复杂性降低到 M x N 以下。

这可以通过对 A 和 B 的所有末端进行 argsorting（分别用于 x 和 y）来完成。这是 O((M+N) log(M+N))编辑因为坐标是整数线性复杂度在这里可能是可能的。编辑结束然后这可以用于预过滤 A x B。过滤和计算非零值的复杂性将是 O(M + N + 非零值的数量)。