[FIXED] Efficient way to calculate all IoUs of two lists

Issue

I have a function to calculate the IoU of two rectangles/bounding boxes.

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

Now I want to calculate all IoUs of bboxes of one list with bboxes of another list, i.e. if list A containts 4 bboxes and list B contains 3 bboxes, then I want a 4x3 matrix with all possible IoUs as a result.

Of course I can do this with two loops like this

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])

but this approach is very slow, especially when the lists become very big.

I'm struggling to find a more efficient way. There has to be a way to utilize numpy to get rid of the loops, but I don't get it. Also the complexity right now is O(m*n). Is there a possibility to reduce the complexity?

Solution

vectorize:

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])

complexity:

Since you are calculating M x N values reducing complexity below M x N is impossible unless most of the values are zero and a sparse representation of the matrix is acceptable.

This can be done by argsorting (separately for x and y) all the ends of A and B. That's O((M+N) log(M+N)) EDIT As the coordinates are integer linear complexity may be possible here. EDIT ends This can then be used to prefilter A x B. The complexity of filtering and computing the nonzeros would be O(M + N + number of nonzeros).

Answered By - Paul Panzer