BUG: box_iou_batch inefficient for 1-to-1 iou calculation

[Ashp116]

Search before asking

• I have searched the Supervision issues and found no similar bug report.

Bug

The function box_iou_batch is inefficient when computing the IoU between just two individual bounding boxes. In such cases, it takes approximately twice as long as a simple one-to-one IoU function optimized for single-pair comparisons. Please review the link below for a benchmark that shows the performance difference. Although the time to compute a single IoU is minimal, the overhead becomes significant when running many iterations. In my setup, where I was constructing a DAG, using box_iou_batch nearly doubled the total computation time.

Environment

• Supervision 0.25.0
• Windows 11
• Python 3.12.6

Minimal Reproducible Example

To reproduce this issue, run a benchmark between the box_iou_batch and the function below. Refer to this link to see my benchmarking results.

def box_iou(box1: np.ndarray, box2: np.ndarray) -> float:
    """
    Compute the Intersection over Union (IoU) between two bounding boxes.

    Args:
        box1 (np.ndarray): A bounding box represented as [x1, y1, x2, y2].
        box2 (np.ndarray): A bounding box represented as [x1, y1, x2, y2].

    Returns:
        float: The IoU value between box1 and box2.
               Ranges from 0.0 (no overlap) to 1.0 (perfect overlap).
    """
    inter_x1 = max(box1[0], box2[0])
    inter_y1 = max(box1[1], box2[1])
    inter_x2 = min(box1[2], box2[2])
    inter_y2 = min(box1[3], box2[3])

    inter_w = max(0, inter_x2 - inter_x1)
    inter_h = max(0, inter_y2 - inter_y1)

    inter_area = inter_w * inter_h

    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])

    union_area = area1 + area2 - inter_area

    return inter_area / union_area + 1e-6

Additional

I propose to have one function that does a non-vectorized single iou calculation

Are you willing to submit a PR?

• Yes I'd like to help by submitting a PR!

[soumik12345]

Hi @Ashp116, thanks for reporting the issue!

As you mentioned

Although the time to compute a single IoU is minimal, the overhead becomes significant when running many iterations. In my setup, where I was constructing a DAG, using box_iou_batch nearly doubled the total computation time.

Do you think one possible way to go around this is to pre-compute IoU for all pairs of detections in adjacent frames, especially in roboflow/trackers#89?

[Ashp116]

Hi @soumik12345,

It's possible to precompute all the IoUs for every pair of detections in adjacent frames, but this is extremely memory-inefficient. For the sake of clarity, let's assume we're using "people-walking.mp4", which has a maximum of 39 detections across the entire video when using YOLOv11x.

If we precompute, each node would need to calculate IoU with up to 39 detections from frame t+1. Even if we store this in a list or any other data structure, simply retrieving and storing the IoUs still takes O(n) time. A better approach is to compute the IoU at the moment the edge is created. This not only reduces memory usage but also simplifies the logic and avoids unnecessary computation.

Regarding box_iou_batch, it is vectorized to compute pairwise IoUs between two sets of boxes. It takes boxes_true of shape (N, 4) and boxes_detection of shape (M, 4) and returns a (N, M) matrix of IoUs. However, using this for 1-to-1 comparisons adds unnecessary overhead by transposing and then computing, when a simple IoU function for two boxes would suffice.

In practice, it's more effective to use a simple function that computes IoU between a single pair of bounding boxes. For the use case I'm presenting, this is significantly faster and more memory-friendly. It’s similar to arithmetic—while it's theoretically faster to batch operations, doing simple calculations like addition or division on demand can often be more efficient.

[SkalskiP]

Hi @Ashp116 your PR got merged today. I'm closing the issue. Feel free to reopen it if you'll have more questions.