Computer vision: Intersection over union of two boxes

IoU is the basic measure of how well a predicted box matches the real one.

What to build

A program that computes the IoU of pairs of boxes.

Requirements

  • Boxes are x1 y1 x2 y2 with x1 < x2 and y1 < y2; the area is (x2 − x1) × (y2 − y1).
  • Print each IoU with three decimal places.

Input

Line 1: N. Then N lines of eight numbers: the first box, then the second.

Output

N lines.

Constraints

N ≤ 100; coordinates are whole numbers from 0 to 10000.

Example

Input:

2
0 0 2 2 1 1 3 3
0 0 4 4 0 0 4 4

Output:

0.143
1.000

Why it works

The overlap rectangle is bounded by the larger of the left and top edges and the smaller of the right and bottom edges, and dividing it by the union measures agreement on a scale from 0 to 1.

Examples

Example 1 · Input
2
0 0 2 2 1 1 3 3
0 0 4 4 0 0 4 4
Expected output
0.143
1.000
Example 2 · Input
2
0 0 1 1 2 2 3 3
0 0 4 2 2 0 6 2
Expected output
0.000
0.333

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The overlap width is min(x2, x2′) − max(x1, x1′); use 0 if it is negative, and the same for the height.

Hint 2

union = area A + area B − overlap.

Solution

Show one correct solution (try it yourself first)
for _ in range(int(input())):
    v = list(map(int, input().split()))
    a, b = v[:4], v[4:]
    w = max(0, min(a[2], b[2]) - max(a[0], b[0]))
    h = max(0, min(a[3], b[3]) - max(a[1], b[1]))
    inter = w * h
    union = (a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - inter
    print(f"{inter / union:.3f}")

Lesson: Object detection metrics and segmentation →