Object Detection

In two lessons the question was always the same: what is in the image. The answer was a single number, and the model did not need to find the block, only to say which way it points. Yet a box sits inside the fiction: for every image the block’s row, column, height, and width are written down. This lesson changes the question — where is the object.

When the question changes, the metric changes too. Accuracy cannot say how well two boxes match, because the answer is not right or wrong but partly right: the predicted box may have missed the ground-truth box by one cell or may have covered half of it. The first job of this lesson is to build the metric that turns this partiality into a single number, and the second is to show how misleading that number is on its own.

• CV16. The image fiction has not changed; what changes is the part that is used. In place of the label, each image’s ground-truth box is read: row, column, height, width.
• CV17. Every image has exactly one object. This makes the task a pure localization problem; detection is localization plus the decision “is there an object, should a box be published,” and it is added in the last section.
• CV18. The metric is intersection over union: the area of the intersection of two bounding boxes divided by the area of their union. Zero is no contact at all, one is an exact overlap. Its direction is bigger is better.
• CV19. Success cannot be counted until an overlap threshold is chosen. The threshold is read separately at 0.3, 0.5, and 0.7, and all three are printed.
• CV20. The domain baseline is the fixed box: a single box of the mean box size in the training set, placed in the middle of the grid, stated as is for every image. This procedure never looks at the image.
• CV21. Precision and recall were defined in the Supervised Learning course and are not repeated. The only thing added in this lesson is the overlap threshold required for a prediction to count as correct.
• CV22. Confidence threshold candidates are read from the scores of the validation set; the test set is used only for reporting.

Intersection over Union and the Fixed Box

# box.py — MODEL: Same image fiction; in this lesson not the label but each
# image's GROUND-TRUTH BOX is used: (row, column, height, width).
import statistics

SEED, M32, SIZE = 20260218, 0xFFFFFFFF, 12
MIN_SIDE, MAX_SIDE = 2, 6


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def image(no):
    r = rng(SEED + 700000 + no)
    background, contrast = 30 + int(r() * 70), 20 + int(r() * 36)
    height = MIN_SIDE + int(r() * (MAX_SIDE - MIN_SIDE + 1))
    width = MIN_SIDE + int(r() * (MAX_SIDE - MIN_SIDE + 1))
    while width == height:
        width = MIN_SIDE + int(r() * (MAX_SIDE - MIN_SIDE + 1))
    i = int((r() + r() + r()) / 3 * (SIZE - height + 1))
    j = int((r() + r() + r()) / 3 * (SIZE - width + 1))
    g = [[0] * SIZE for _ in range(SIZE)]
    for a in range(SIZE):
        for b in range(SIZE):
            v = background + (contrast if i <= a < i + height and j <= b < j + width else 0)
            v += int(r() * 61) - 30
            g[a][b] = 0 if v < 0 else (255 if v > 255 else v)
    return g, (i, j, height, width), (1 if width > height else 0)


def shuffle(n, seed):
    r, s = rng(seed), list(range(n))
    for i in range(n - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return s


RAW = [image(i) for i in range(400)]
DATA = [RAW[i] for i in shuffle(400, SEED + 40000)]
TRAIN, VAL, TEST = DATA[:160], DATA[160:240], DATA[240:]


def overlap(a, b):
    """Intersection over union: intersection area divided by union area."""
    di = max(0, min(a[0] + a[2], b[0] + b[2]) - max(a[0], b[0]))
    dj = max(0, min(a[1] + a[3], b[1] + b[3]) - max(a[1], b[1]))
    inter = di * dj
    return inter / (a[2] * a[3] + b[2] * b[3] - inter)


def inside(k, a, b):
    return k[0] <= a < k[0] + k[2] and k[1] <= b < k[1] + k[3]


sy = round(statistics.mean(k[2] for _, k, _ in TRAIN))
sx = round(statistics.mean(k[3] for _, k, _ in TRAIN))
FIXED = ((SIZE - sy) // 2, (SIZE - sx) // 2, sy, sx)
THRESHOLDS = (0.3, 0.5, 0.7)


def report(name, boxes):
    o = [overlap(k, g) for k, (_, g, _) in zip(boxes, TEST)]
    print(f"{name:<32}{statistics.mean(o):>13.4f}"
          + "".join(f"{sum(1 for v in o if v >= e) / len(o):>10.4f}" for e in THRESHOLDS))
    return o


g0, k0, _ = TEST[0]
print(f"mean box in the training set {sy}x{sx}; fixed box {FIXED}")
print(f"example: ground-truth box {k0}; X intersection, g ground truth only, f fixed only")
for a in range(SIZE):
    print("   " + "".join("Xgf."[(0 if inside(FIXED, a, b) else 1)
                                 if inside(k0, a, b)
                                 else (2 if inside(FIXED, a, b) else 3)]
                          for b in range(SIZE)))
print(f"in this example the intersection over union is {overlap(FIXED, k0):.4f}")
print(f"\n{'domain baseline':<32}{'mean overlap':>13}"
      + "".join(f"{'thr ' + str(e):>10}" for e in THRESHOLDS))
FIXED_O = report("fixed box (ignores the image)", [FIXED] * len(TEST))

mean box in the training set 4x4; fixed box (4, 4, 4, 4)
example: ground-truth box (3, 6, 6, 5); X intersection, g ground truth only, f fixed only
   ............
   ............
   ............
   ......ggggg.
   ....ffXXggg.
   ....ffXXggg.
   ....ffXXggg.
   ....ffXXggg.
   ......ggggg.
   ............
   ............
   ............
in this example the intersection over union is 0.2105

domain baseline                  mean overlap   thr 0.3   thr 0.5   thr 0.7
fixed box (ignores the image)          0.3011    0.5125    0.1938    0.0125

The drawing shows the definition of the metric cell by cell. The intersection is 8 cells, and the union is 38 cells: the 30 cells of the ground-truth box plus the 16 cells of the fixed box, minus the intersection. The ratio is 8/38 = 0.2105. This is a single example, and the boxes are quite far apart.

The bottom row is where the second claim of this course is paid off. The fixed box looks at no image, reads no pixel, learns nothing: the only information it takes from the training set is the mean box size, and its position is the middle of the grid. This procedure gets a mean overlap of 0.3011 and counts as a detection in 0.5125 of the test images at a threshold of 0.3 — in more than half of them.

The source of the number is not the metric but the fiction, and the fiction carries it on purpose. Because the block’s position is chosen by the mean of three independent draws, the objects gather in the middle of the grid. In real image sets too the object is mostly in the middle, and this is enough for a procedure that has learned nothing to look good on the overlap metric. When the threshold is raised, the same procedure falls to 0.1938 and 0.0125: the same box, the same test set, and the only thing that changed is the reading threshold.

What the Search Adds

# window.py — MODEL: Sliding window: the score of each candidate box is the sum of the
# normalized pixels inside it divided by the square root of the area.
# The sums are read in constant time from the cumulative sum table.
def norm_t(g):
    x = [v for s in g for v in s]
    m = sum(x) / len(x)
    sd = (sum((v - m) ** 2 for v in x) / len(x)) ** 0.5
    return [[(v - m) / sd for v in s] for s in g]


def sum_table(x):
    T = [[0.0] * (SIZE + 1) for _ in range(SIZE + 1)]
    for a in range(SIZE):
        for b in range(SIZE):
            T[a + 1][b + 1] = x[a][b] + T[a][b + 1] + T[a + 1][b] - T[a][b]
    return T


def search(x, sizes):
    T, best, box = sum_table(x), None, FIXED
    for h, w in sizes:
        root = (h * w) ** 0.5
        for a in range(SIZE - h + 1):
            for b in range(SIZE - w + 1):
                p = (T[a + h][b + w] - T[a][b + w] - T[a + h][b] + T[a][b]) / root
                if best is None or p > best:
                    best, box = p, (a, b, h, w)
    return box, best


ONE = [(FIXED[2], FIXED[3])]
ALL = [(h, w) for h in range(MIN_SIDE, MAX_SIDE + 1)
       for w in range(MIN_SIDE, MAX_SIDE + 1)]
TEST_N = [norm_t(g) for g, _, _ in TEST]


def candidate_count(sizes):
    return sum((SIZE - h + 1) * (SIZE - w + 1) for h, w in sizes)


print(f"{'procedure':<32}{'mean overlap':>13}"
      + "".join(f"{'thr ' + str(e):>10}" for e in THRESHOLDS))
report("fixed box (ignores the image)", [FIXED] * len(TEST))
report("fixed-size sliding window", [search(x, ONE)[0] for x in TEST_N])
FULL = [search(x, ALL) for x in TEST_N]
report("window that also searches size", [k for k, _ in FULL])
print(f"candidate boxes: fixed-size {candidate_count(ONE)}, "
      f"also searching size {candidate_count(ALL)}")

procedure                        mean overlap   thr 0.3   thr 0.5   thr 0.7
fixed box (ignores the image)          0.3011    0.5125    0.1938    0.0125
fixed-size sliding window              0.5687    0.9750    0.6875    0.2375
window that also searches size         0.9076    0.9812    0.9625    0.8500
candidate boxes: fixed-size 81, also searching size 2025

The only difference between the two procedures is what is searched. The fixed-size window searches only position: the box’s height is fixed to the mean of the training set, and 81 positions are tried. The second also searches size and evaluates 2,025 candidates. The mean overlap rises from 0.5687 to 0.9076; a search space 25 times larger adds 0.3389.

The real number is not in the rows but in the gap between the columns. At a threshold of 0.3 the two windows read 0.9750 and 0.9812; the gap between them is 0.0062, which is to say it can be ignored. At a threshold of 0.7 the same two procedures read 0.2375 and 0.8500; the gap is 0.6125. The same two procedures, the same test set, the same family of metrics — only the threshold changes, and one becomes “nearly equal” and the other “three and a half times better.”

What the threshold means also changes from procedure to procedure. The fixed-size window finds the object but cannot match its size: when a 4x4 box standing at the right position meets a 6x5 ground-truth box, the intersection can be at most 16 cells and the union stays at 30 cells, so the overlap cannot exceed 16/30 = 0.5333 and structurally cannot pass the 0.7 threshold. A low threshold hides this flaw entirely. An overlap number cannot be carried around without writing at which threshold it was read.

The form of the score is also a decision, and it has a measurable consequence. If the raw pixel sum of the candidate boxes were used, the search would pick the largest box, because even though the background pixels are zero on average, the sum is inflated by noise that grows with the size of the box; if the mean inside the box were used, the search would pick a single bright noise cell, because the smallest box gives the highest mean. Dividing the sum by the square root of the area balances the two tendencies: the score measures how far the region stands out against the noise.

Confidence Threshold, Precision, and Recall

# confidence.py — Until now every procedure published one box per image. When
# no box is published while the score is below a confidence threshold, precision
# and recall separate. Threshold candidates are read from the scores of the
# VALIDATION set.
BOXES, SCORES = [k for k, _ in FULL], [p for _, p in FULL]
VAL_S = sorted(search(norm_t(g), ALL)[1] for g, _, _ in VAL)
CANDIDATES = [("all", 0.0)] + [(f"quartile {q}", VAL_S[len(VAL_S) * q // 4])
                               for q in (1, 2, 3)]


def precision_recall(confidence, threshold):
    published = [(k, g) for k, p, (_, g, _) in zip(BOXES, SCORES, TEST) if p >= confidence]
    correct = sum(1 for k, g in published if overlap(k, g) >= threshold)
    return (correct / len(published) if published else 0.0), correct / len(TEST)


print(f"{'confidence threshold':<22}{'published':>10}"
      + "".join(f"{f'{e} prec':>9}{f'{e} rec':>9}" for e in THRESHOLDS))
for name, confidence in CANDIDATES:
    share = sum(1 for p in SCORES if p >= confidence) / len(SCORES)
    print(f"{name:<22}{share:>10.4f}"
          + "".join(f"{p:>9.4f}{r:>9.4f}"
                    for p, r in (precision_recall(confidence, e) for e in THRESHOLDS)))
print(f"{'fixed box':<22}{1.0:>10.4f}"
      + "".join(f"{v:>9.4f}{v:>9.4f}"
                for v in (sum(1 for o in FIXED_O if o >= e) / len(FIXED_O)
                          for e in THRESHOLDS)))

confidence threshold   published 0.3 prec  0.3 rec 0.5 prec  0.5 rec 0.7 prec  0.7 rec
all                       1.0000   0.9812   0.9812   0.9625   0.9625   0.8500   0.8500
quartile 1                0.7063   1.0000   0.7063   1.0000   0.7063   0.9735   0.6875
quartile 2                0.4437   1.0000   0.4437   1.0000   0.4437   1.0000   0.4437
quartile 3                0.2625   1.0000   0.2625   1.0000   0.2625   1.0000   0.2625
fixed box                 1.0000   0.5125   0.5125   0.1938   0.1938   0.0125   0.0125

Until now every procedure published a box in every image; because it had to publish, precision and recall were the same number. The first row shows this: at a publish rate of 1.0000 both are 0.9812. When predictions with a low score are not published, the two separate. When the score of the lowest quarter of the validation set is taken as the threshold, a box is published in 0.7063 of the images, and at a threshold of 0.3 precision rises to 1.0000 while recall drops to 0.7063.

The Supervised Learning course set up this trade-off and its definitions are not repeated here. The only thing specific to images is this: there a prediction was “right” or “wrong,” while here an overlap threshold defines being right, and that threshold separates the columns of the table. At the quarter threshold the precision in the 0.7 column stays at 0.9735, because even a prediction with a high score can miss a 0.7 overlap. The score does not say that the box is right; it says that a bright cluster was found in that region.

The last row puts the baseline into the same table. Because the fixed box always publishes, its precision and recall are equal, and at a threshold of 0.3 they are 0.5125. Looking at the precision and saying “my procedure is 1.0000” says nothing unless it is written at which threshold and in how many images a box was published; and without the domain baseline written down, it counts as unmeasured.

Summary

• Intersection over union is the area of the intersection of two boxes divided by the area of their union; in the example the intersection is 8 cells, the union is 38 cells, and the ratio is 0.2105.
• The 4x4 fixed box placed in the middle of the grid gets a mean overlap of 0.3011 without looking at the image at all and counts as a detection in 0.5125 of the test images at a threshold of 0.3; its source is the center bias in the fiction.
• The same fixed box falls to 0.1938 at a threshold of 0.5 and to 0.0125 at 0.7: the number comes not from the procedure but from the threshold.
• The window with 81 candidates that searches only position gives a mean overlap of 0.5687, and the window with 2,025 candidates that also searches size gives 0.9076; a 25-fold search adds 0.3389.
• The two windows are separated by 0.0062 at a threshold of 0.3, and the gap rises to 0.6125 at a threshold of 0.7; a low threshold entirely hides the size error.
• When the confidence threshold is pulled to the score of the first quarter of the validation set, the publish rate becomes 0.7063, precision rises from 0.9812 to 1.0000, and recall drops to 0.7063.

Next Step

The box said where the object is, but it did not say which pixels are the object. Even when the window that also searches size gets a mean overlap of 0.9076, the answer it gives is a rectangle, and every pixel inside that rectangle counts as the object. In this fiction the object is already a rectangle, so most of the loss is invisible; when the edge of the object is not straight, the background pixels that fall inside the box are not counted at all. The next lesson takes the decision down to the pixel level, and its first job will again be to write the baseline: a procedure that assigns every pixel to the dominant class gets a surprisingly high number because of pixel imbalance.