Lesson 39: Object Detection I — Sliding Windows, from Rowley-Baluja-Kanade to Viola-Jones¶
Every classifier so far has answered "what is in this image?" for an image that already contains exactly one thing, centered and cropped. Object detection asks a harder question: given a scene that may contain zero, one, or several objects at unknown locations and scales, find where each one is.
The oldest and still-conceptually-clearest answer is the sliding window: turn a classifier for "is there a face right here, filling this window?" into a detector by running it at every location (and, in principle, every scale) in the image. Rowley, Baluja, and Kanade (1996) did exactly this with a small neural network as the window classifier — one of the first genuinely successful uses of a neural net for a real vision task, years before deep learning's resurgence (Lesson 35). Viola and Jones (2001) later made the same sliding-window idea fast enough for real-time video using a cascade of much cheaper features, which is why face detection first appeared in consumer cameras through their method rather than RBK's. This lesson builds RBK's approach end to end: a small window classifier, applied at every position, followed by the classic step neither original paper's core diagram shows but that any real system needs — merging duplicate detections.
import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F
import matplotlib.pyplot as plt
import matplotlib.patches as patches
Step 1: a synthetic "face" and a window classifier¶
Real face data isn't needed to demonstrate RBK's mechanics faithfully — only a class with consistent internal structure (a head outline, two eyes, a mouth, always in the same relative arrangement) versus clutter that lacks that structure. Train a small CNN as a pure window classifier: given a fixed-size crop, is there a face filling it, yes or no?
def make_face(size=16, rng=None):
img = np.zeros((size, size), dtype=np.float32)
cy, cx = size // 2, size // 2
yy, xx = np.mgrid[0:size, 0:size]
img[((xx - cx) ** 2 + (yy - cy) ** 2) <= (size * 0.42) ** 2] = 0.6 # head
img[(np.abs(xx - (cx - 3)) <= 1) & (np.abs(yy - (cy - 2)) <= 1)] = 1.0 # left eye
img[(np.abs(xx - (cx + 3)) <= 1) & (np.abs(yy - (cy - 2)) <= 1)] = 1.0 # right eye
img[(np.abs(xx - cx) <= 2) & (np.abs(yy - (cy + 3)) <= 1)] = 0.9 # mouth
if rng is not None:
img = np.clip(img + rng.normal(0, 0.08, img.shape), 0, 1).astype(np.float32)
return img
def make_nonface(size=16, rng=None):
img = rng.uniform(0, 0.5, (size, size)).astype(np.float32)
if rng.random() < 0.5:
cy, cx = rng.integers(2, size - 2), rng.integers(2, size - 2)
r = rng.integers(2, 5)
yy, xx = np.mgrid[0:size, 0:size]
img[((xx - cx) ** 2 + (yy - cy) ** 2) <= r ** 2] = rng.uniform(0.4, 0.9)
return img
rng = np.random.default_rng(11)
N = 200
faces = np.array([make_face(rng=rng) for _ in range(N)])
nonfaces = np.array([make_nonface(rng=rng) for _ in range(N)])
X = np.concatenate([faces, nonfaces])
y = np.concatenate([np.ones(N), np.zeros(N)]).astype(np.float32)
perm = rng.permutation(len(X))
X, y = X[perm], y[perm]
split = int(0.8 * len(X))
Xtr, ytr, Xte, yte = X[:split], y[:split], X[split:], y[split:]
fig, axes = plt.subplots(1, 6, figsize=(11, 2))
for ax, im, lbl in zip(axes, list(faces[:3]) + list(nonfaces[:3]), ['face']*3 + ['non-face']*3):
ax.imshow(im, cmap='gray'); ax.set_title(lbl, fontsize=9); ax.axis('off')
plt.show()
class WindowClassifier(nn.Module):
def __init__(self):
super().__init__()
self.net = nn.Sequential(
nn.Conv2d(1, 8, 3, padding=1), nn.ReLU(), nn.MaxPool2d(2),
nn.Conv2d(8, 16, 3, padding=1), nn.ReLU(), nn.AdaptiveMaxPool2d(1),
)
self.fc = nn.Linear(16, 1)
def forward(self, x):
return self.fc(self.net(x).flatten(1)).squeeze(-1)
torch.manual_seed(0)
model = WindowClassifier()
opt = torch.optim.Adam(model.parameters(), lr=0.01)
Xt = torch.tensor(Xtr).unsqueeze(1); yt = torch.tensor(ytr)
for _ in range(300):
opt.zero_grad()
loss = F.binary_cross_entropy_with_logits(model(Xt), yt)
loss.backward()
opt.step()
with torch.no_grad():
Xte_t = torch.tensor(Xte).unsqueeze(1)
acc = ((model(Xte_t) > 0).float() == torch.tensor(yte)).float().mean().item()
print(f'window classifier test accuracy: {acc:.1%}')
Step 2: slide the window across a scene¶
Build a larger scene containing two faces at unknown locations plus background clutter, then run the trained window classifier at every position on a dense grid (a sliding window). Each position gets a raw confidence score.
def make_scene(rng, size=64, face_size=16, n_faces=2):
scene = rng.uniform(0, 0.5, (size, size)).astype(np.float32)
placements = []
tries = 0
while len(placements) < n_faces and tries < 50:
tries += 1
x0 = rng.integers(0, size - face_size)
y0 = rng.integers(0, size - face_size)
if any(abs(x0 - px) < face_size and abs(y0 - py) < face_size for px, py in placements):
continue
face = make_face(size=face_size, rng=rng)
scene[y0:y0+face_size, x0:x0+face_size] = np.maximum(scene[y0:y0+face_size, x0:x0+face_size], face)
placements.append((x0, y0))
return scene, placements
scene_rng = np.random.default_rng(21)
scene, true_boxes = make_scene(scene_rng)
print(f'true face top-left corners: {true_boxes}')
def sliding_window_scores(model, scene, win=16, stride=1):
scores = np.full((scene.shape[0] - win + 1, scene.shape[1] - win + 1), -np.inf, dtype=np.float32)
with torch.no_grad():
for y0 in range(0, scene.shape[0] - win + 1, stride):
for x0 in range(0, scene.shape[1] - win + 1, stride):
patch = scene[y0:y0+win, x0:x0+win]
scores[y0, x0] = model(torch.tensor(patch[None, None]).float()).item()
return scores
score_map = sliding_window_scores(model, scene)
fig, axes = plt.subplots(1, 2, figsize=(9, 4))
axes[0].imshow(scene, cmap='gray')
for x0, y0 in true_boxes:
axes[0].add_patch(patches.Rectangle((x0, y0), 16, 16, edgecolor='lime', facecolor='none', linewidth=2))
axes[0].set_title('scene (true faces in green)'); axes[0].axis('off')
im = axes[1].imshow(score_map, cmap='hot')
axes[1].set_title('window classifier score, by top-left corner'); axes[1].axis('off')
plt.colorbar(im, ax=axes[1], fraction=0.046)
plt.show()
Step 3: threshold, then merge duplicates¶
The score map peaks exactly at the true face corners, but thresholding it produces a cluster of detections around each face, not one — every window that overlaps a face heavily enough scores above threshold. This is precisely the duplicate-detection problem Lesson 12 first raised for the Hough transform's accumulator peaks: many near-identical hypotheses need to collapse into one. The fix is non-maximum suppression (NMS): repeatedly keep the highest-scoring remaining detection and discard every other detection that overlaps it by more than an IoU (intersection-over-union) threshold.
def iou(a, b):
ax0, ay0, aw, ah = a[:4]; bx0, by0, bw, bh = b[:4]
ax1, ay1 = ax0 + aw, ay0 + ah
bx1, by1 = bx0 + bw, by0 + bh
ix0, iy0 = max(ax0, bx0), max(ay0, by0)
ix1, iy1 = min(ax1, bx1), min(ay1, by1)
iw, ih = max(0, ix1 - ix0), max(0, iy1 - iy0)
inter = iw * ih
union = aw * ah + bw * bh - inter
return inter / union if union > 0 else 0.0
def nms(detections, iou_thresh=0.3):
dets = sorted(detections, key=lambda d: -d[4])
keep = []
while dets:
best = dets.pop(0)
keep.append(best)
dets = [d for d in dets if iou(best, d) < iou_thresh]
return keep
# a threshold set from the background score distribution: well above typical background,
# well below the score at a well-aligned face window
threshold = np.percentile(score_map[score_map > -np.inf], 97.5)
raw_detections = [(x0, y0, 16, 16, score_map[y0, x0])
for y0 in range(score_map.shape[0]) for x0 in range(score_map.shape[1])
if score_map[y0, x0] > threshold]
final_detections = nms(raw_detections)
print(f'threshold (97.5th percentile of all window scores): {threshold:.2f}')
print(f'raw detections above threshold: {len(raw_detections)}')
print(f'detections after NMS: {len(final_detections)}')
for x0, y0, w, h, s in final_detections:
print(f' box=({x0},{y0},{w},{h}) score={s:.2f}')
fig, ax = plt.subplots(figsize=(5, 5))
ax.imshow(scene, cmap='gray')
for x0, y0 in true_boxes:
ax.add_patch(patches.Rectangle((x0, y0), 16, 16, edgecolor='lime', facecolor='none', linewidth=3, label='ground truth'))
for x0, y0, w, h, s in final_detections:
ax.add_patch(patches.Rectangle((x0, y0), w, h, edgecolor='red', facecolor='none', linewidth=1.5, linestyle='--', label='detection'))
handles, labels = ax.get_legend_handles_labels()
by_label = dict(zip(labels, handles))
ax.legend(by_label.values(), by_label.keys(), fontsize=8, loc='upper right')
ax.set_title(f'{len(final_detections)} detections after NMS vs. {len(true_boxes)} true faces')
ax.axis('off')
plt.show()
NMS collapses the raw detections down to exactly two boxes, tightly matching the two true face locations.
Handling scale: the image pyramid¶
Everything above assumes faces are always exactly 16x16. Real faces appear at unknown scales. RBK's solution is Lesson 11's Gaussian pyramid: build a stack of the image at multiple resolutions, and run the same fixed-size window classifier over every level. A face that's too big for the window at full resolution will fit the window at some coarser pyramid level, since shrinking the image is equivalent to enlarging the effective window size relative to image content. This lesson's scene only has one face scale, so the pyramid isn't demonstrated here directly — but the mechanism is exactly Lesson 11's cv2.pyrDown cascade, reused for detection instead of compression.
RBK vs. Viola-Jones¶
RBK's window classifier (what this lesson just built, in miniature) is accurate but computationally heavy for its era — evaluating a small neural network at every position and scale of every pyramid level was slow on 1996 hardware. Viola and Jones (2001) got the same sliding-window idea running in real time by replacing the neural network with a cascade of extremely cheap Haar-like features: a sequence of stages, each a simple threshold on a rectangular-region intensity difference, ordered so that the vast majority of non-face windows get rejected by the first stage or two, and only the rare promising window pays for the full cascade. The accuracy-per-window is lower than a neural net's, but because most windows are background, the cascade's average cost per window is tiny — which is exactly why Viola-Jones, not RBK, is the algorithm that ended up running live on 2000s-era digital cameras.
Exercise¶
- Change
iou_threshinnmsfrom0.3to0.7. Rerun detection on the scene. Does NMS now under-merge (report more than 2 boxes) or over-merge (miss a face)? Explain why in terms of how much overlap real duplicate detections around the same face actually have. - The threshold here is set from the 97.5th percentile of this scene's own score distribution — a form of cheating, since a real detector doesn't get to see the test scene's scores before deciding. Instead, compute a threshold from
Xte's known face/non-face scores only (e.g., the midpoint between the lowest true-face score and the highest true-nonface score), and check whether it still successfully detects both faces in the scene. - Increase
n_facesinmake_sceneto 4 and shrinksizeto 48 so faces are packed closer together. Does NMS still separate them correctly, or does IoU-based suppression start merging genuinely distinct nearby faces into one detection? At what spacing does it break down?