Lesson 40: Object Detection from Sliding Windows¶
Every classifier so far has focused on images as a whole rather than image patches. In other words, they asked, "what is this image?" — assuming that the image already contains exactly one thing, centered and cropped.
Object detection asks a harder question: given an image that contains zero, one, or several objects at unknown locations and scales, find the location of each one.
The classic approach is the sliding window: train a classifier for a fixed-size image patch, then slide the classifier across the image to run it at every location (and scale). Rowley, Baluja, and Kanade (1996) did exactly this with a small neural network as the window classifier. This idea was truly ahead of its time — one of the first successful uses of a neural net for a real vision task, more than a decade before deep learning's resurgence (Lesson 37). This lesson builds the approach end to end: a small window classifier, applied at every position, followed by a key step 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¶
To demonstrate the mechanics, real data isn't needed — 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, which is recorded at that window's center. Since windows can't be centered within win // 2 pixels of the border (a window close to the edge doesn't fit inside the image), the score is not computed within a border strip, shown in gray.
def make_scene(rng, size=64, face_size=16, n_faces=2):
scene = rng.uniform(0, 0.5, (size, size)).astype(np.float32)
corners = []
tries = 0
while len(corners) < 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 corners):
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)
corners.append((x0, y0))
# report boxes by center, not top-left corner; cast to plain float so printing doesn't show np.float64(...)
centers = [(float(x0 + face_size / 2), float(y0 + face_size / 2)) for x0, y0 in corners]
return scene, centers
scene_rng = np.random.default_rng(21)
scene, true_boxes = make_scene(scene_rng)
print(f'true face centers: {true_boxes}')
def sliding_window_scores(model, scene, win=16, stride=1):
half = win // 2
scores = np.full(scene.shape, np.nan, dtype=np.float32) # NaN = no window centered here (too close to the border)
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 + half, x0 + half] = model(torch.tensor(patch[None, None]).float()).item()
return scores
score_map = sliding_window_scores(model, scene)
cmap = plt.cm.hot.copy()
cmap.set_bad(color='gray') # border pixels with no score (NaN) render as gray, not as an arbitrary color-scale value
fig, axes = plt.subplots(1, 2, figsize=(9, 4))
axes[0].imshow(scene, cmap='gray')
for cx, cy in true_boxes:
axes[0].add_patch(patches.Rectangle((cx - 8, cy - 8), 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=cmap)
axes[1].set_title('window classifier score, by window center\n(gray border = no window fits there)'); 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 near the true faces, but thresholding produces a cluster of detections around each face — every window that overlaps a face heavily enough scores above threshold. This is precisely the duplicate-detection problem Lesson 12 first raised for both Canny and the Hough transform: 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):
acx, acy, aw, ah = a[:4]; bcx, bcy, bw, bh = b[:4]
ax0, ay0, ax1, ay1 = acx - aw / 2, acy - ah / 2, acx + aw / 2, acy + ah / 2
bx0, by0, bx1, by1 = bcx - bw / 2, bcy - bh / 2, bcx + bw / 2, bcy + bh / 2
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
valid = ~np.isnan(score_map)
threshold = np.percentile(score_map[valid], 97.5)
raw_detections = [(cx, cy, 16, 16, score_map[cy, cx]) # (cx, cy) is already the window's center
for cy, cx in zip(*np.where(valid)) if score_map[cy, cx] > 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 cx, cy, w, h, s in final_detections:
print(f' box=(cx={cx:.0f}, cy={cy:.0f}, w={w}, h={h}) score={s:.2f}')
fig, ax = plt.subplots(figsize=(5, 5))
ax.imshow(scene, cmap='gray')
for cx, cy in true_boxes:
ax.add_patch(patches.Rectangle((cx - 8, cy - 8), 16, 16, edgecolor='lime', facecolor='none', linewidth=3, label='ground truth'))
for cx, cy, w, h, s in final_detections:
ax.add_patch(patches.Rectangle((cx - w / 2, cy - h / 2), 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()
With this threshold and iou_thresh=0.3, NMS collapses the raw detections down to two boxes that closely match the two true face locations (one lands exactly on a true center, the other within a couple of pixels). As the exercises below explore, results on other scenes and seeds yield false positives and false negatives, depending on the threshold and other parameter choices.
Handling scale: the image pyramid¶
Everything above assumes faces are always exactly 16x16, but real faces appear at unknown scales. The solution is Lesson 11's Gaussian pyramid (cv2.pyrDown): 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 the same.
Viola-Jones¶
The Rowley-Baluja-Kanade window classifier (what this lesson just built, in miniature) was computationally heavy at the time. In 1996 (pre-GPUs) evaluating a small neural network at every position and scale of every pyramid level was slow. Viola and Jones (2001) modified the same sliding-window idea to run in real time by replacing the neural network with a cascade of extremely cheap Haar-like features (the same local sum/difference idea as Lesson 16's Haar wavelet, applied to 2D rectangular regions): 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 windows pay for the full cascade of classifiers. As a result, the cascade's average cost per window is tiny — which is why Viola-Jones is the algorithm that ended up running live on 2000s-era digital cameras.
OpenCV ships the Viola-Jones cascade as cv2.CascadeClassifier, pretrained on real faces. Just load an XML file of learned cascade stages and run it.
import urllib.request
from pathlib import Path
import cv2
CACHE_DIR = Path.home() / '.cache' / 'cvintro'
CASCADE_URL = 'https://raw.githubusercontent.com/opencv/opencv/4.x/data/haarcascades/haarcascade_frontalface_default.xml'
CASCADE_PATH = CACHE_DIR / 'haarcascade_frontalface_default.xml'
def ensure_cascade():
if CASCADE_PATH.exists():
return
CACHE_DIR.mkdir(parents=True, exist_ok=True)
print('Downloading the Viola-Jones frontal-face cascade (one-time, cached under ~/.cache/cvintro)...')
urllib.request.urlretrieve(CASCADE_URL, CASCADE_PATH)
ensure_cascade()
cascade = cv2.CascadeClassifier(str(CASCADE_PATH))
photo = cv2.imread('../img/apollo11_crew.jpg')
gray = cv2.cvtColor(photo, cv2.COLOR_BGR2GRAY)
faces = cascade.detectMultiScale(gray, scaleFactor=1.1, minNeighbors=5, minSize=(60, 60))
print(f'{len(faces)} detections')
photo_rgb = cv2.cvtColor(photo, cv2.COLOR_BGR2RGB)
fig, ax = plt.subplots(figsize=(8, 6))
ax.imshow(photo_rgb)
for (x, y, w, h) in faces:
ax.add_patch(patches.Rectangle((x, y), w, h, edgecolor='lime', facecolor='none', linewidth=2))
ax.set_title(f'cv2.CascadeClassifier: {len(faces)} detections')
ax.axis('off')
plt.show()
Image source: NASA (public domain), via Wikimedia Commons
All three astronauts' faces (Armstrong, Collins, Aldrin) are found correctly, plus a small false positive on the fabric texture on Aldrin's sleeve. minNeighbors (how many overlapping detections a region must have) and scaleFactor (how coarsely the image pyramid steps between scales) trade off false positives against missed faces, playing a role similar to this lesson's NMS threshold.
Exercises¶
- 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? - Lower
minNeighborson the real Viola-Jones cascade from5to2and rerun. Does the fabric false positive get worse, or do new false positives appear elsewhere? Then try raisingminNeighborsto8— does it clean up the false positive, and does it cost any true detections?