{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": "# Lesson 39: Object Detection I — Sliding Windows, from Rowley-Baluja-Kanade to Viola-Jones\n\nEvery 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.\n\nThe 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."
},
{
"cell_type": "code",
"id": "b9296e38",
"source": "import numpy as np\nimport torch\nimport torch.nn as nn\nimport torch.nn.functional as F\nimport matplotlib.pyplot as plt\nimport matplotlib.patches as patches",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"id": "d56bd578",
"source": "## Step 1: a synthetic \"face\" and a window classifier\n\nReal 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?",
"metadata": {}
},
{
"cell_type": "code",
"id": "4aa51ab8",
"source": "def make_face(size=16, rng=None):\n img = np.zeros((size, size), dtype=np.float32)\n cy, cx = size // 2, size // 2\n yy, xx = np.mgrid[0:size, 0:size]\n img[((xx - cx) ** 2 + (yy - cy) ** 2) <= (size * 0.42) ** 2] = 0.6 # head\n img[(np.abs(xx - (cx - 3)) <= 1) & (np.abs(yy - (cy - 2)) <= 1)] = 1.0 # left eye\n img[(np.abs(xx - (cx + 3)) <= 1) & (np.abs(yy - (cy - 2)) <= 1)] = 1.0 # right eye\n img[(np.abs(xx - cx) <= 2) & (np.abs(yy - (cy + 3)) <= 1)] = 0.9 # mouth\n if rng is not None:\n img = np.clip(img + rng.normal(0, 0.08, img.shape), 0, 1).astype(np.float32)\n return img\n\ndef make_nonface(size=16, rng=None):\n img = rng.uniform(0, 0.5, (size, size)).astype(np.float32)\n if rng.random() < 0.5:\n cy, cx = rng.integers(2, size - 2), rng.integers(2, size - 2)\n r = rng.integers(2, 5)\n yy, xx = np.mgrid[0:size, 0:size]\n img[((xx - cx) ** 2 + (yy - cy) ** 2) <= r ** 2] = rng.uniform(0.4, 0.9)\n return img\n\nrng = np.random.default_rng(11)\nN = 200\nfaces = np.array([make_face(rng=rng) for _ in range(N)])\nnonfaces = np.array([make_nonface(rng=rng) for _ in range(N)])\nX = np.concatenate([faces, nonfaces])\ny = np.concatenate([np.ones(N), np.zeros(N)]).astype(np.float32)\nperm = rng.permutation(len(X))\nX, y = X[perm], y[perm]\nsplit = int(0.8 * len(X))\nXtr, ytr, Xte, yte = X[:split], y[:split], X[split:], y[split:]\n\nfig, axes = plt.subplots(1, 6, figsize=(11, 2))\nfor ax, im, lbl in zip(axes, list(faces[:3]) + list(nonfaces[:3]), ['face']*3 + ['non-face']*3):\n ax.imshow(im, cmap='gray'); ax.set_title(lbl, fontsize=9); ax.axis('off')\nplt.show()",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"id": "c65c6880",
"source": "class WindowClassifier(nn.Module):\n def __init__(self):\n super().__init__()\n self.net = nn.Sequential(\n nn.Conv2d(1, 8, 3, padding=1), nn.ReLU(), nn.MaxPool2d(2),\n nn.Conv2d(8, 16, 3, padding=1), nn.ReLU(), nn.AdaptiveMaxPool2d(1),\n )\n self.fc = nn.Linear(16, 1)\n\n def forward(self, x):\n return self.fc(self.net(x).flatten(1)).squeeze(-1)\n\ntorch.manual_seed(0)\nmodel = WindowClassifier()\nopt = torch.optim.Adam(model.parameters(), lr=0.01)\nXt = torch.tensor(Xtr).unsqueeze(1); yt = torch.tensor(ytr)\nfor _ in range(300):\n opt.zero_grad()\n loss = F.binary_cross_entropy_with_logits(model(Xt), yt)\n loss.backward()\n opt.step()\n\nwith torch.no_grad():\n Xte_t = torch.tensor(Xte).unsqueeze(1)\n acc = ((model(Xte_t) > 0).float() == torch.tensor(yte)).float().mean().item()\nprint(f'window classifier test accuracy: {acc:.1%}')",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"id": "a03fdf83",
"source": "## Step 2: slide the window across a scene\n\nBuild 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.",
"metadata": {}
},
{
"cell_type": "code",
"id": "4f3e277d",
"source": "def make_scene(rng, size=64, face_size=16, n_faces=2):\n scene = rng.uniform(0, 0.5, (size, size)).astype(np.float32)\n placements = []\n tries = 0\n while len(placements) < n_faces and tries < 50:\n tries += 1\n x0 = rng.integers(0, size - face_size)\n y0 = rng.integers(0, size - face_size)\n if any(abs(x0 - px) < face_size and abs(y0 - py) < face_size for px, py in placements):\n continue\n face = make_face(size=face_size, rng=rng)\n scene[y0:y0+face_size, x0:x0+face_size] = np.maximum(scene[y0:y0+face_size, x0:x0+face_size], face)\n placements.append((x0, y0))\n return scene, placements\n\nscene_rng = np.random.default_rng(21)\nscene, true_boxes = make_scene(scene_rng)\nprint(f'true face top-left corners: {true_boxes}')\n\ndef sliding_window_scores(model, scene, win=16, stride=1):\n scores = np.full((scene.shape[0] - win + 1, scene.shape[1] - win + 1), -np.inf, dtype=np.float32)\n with torch.no_grad():\n for y0 in range(0, scene.shape[0] - win + 1, stride):\n for x0 in range(0, scene.shape[1] - win + 1, stride):\n patch = scene[y0:y0+win, x0:x0+win]\n scores[y0, x0] = model(torch.tensor(patch[None, None]).float()).item()\n return scores\n\nscore_map = sliding_window_scores(model, scene)\n\nfig, axes = plt.subplots(1, 2, figsize=(9, 4))\naxes[0].imshow(scene, cmap='gray')\nfor x0, y0 in true_boxes:\n axes[0].add_patch(patches.Rectangle((x0, y0), 16, 16, edgecolor='lime', facecolor='none', linewidth=2))\naxes[0].set_title('scene (true faces in green)'); axes[0].axis('off')\nim = axes[1].imshow(score_map, cmap='hot')\naxes[1].set_title('window classifier score, by top-left corner'); axes[1].axis('off')\nplt.colorbar(im, ax=axes[1], fraction=0.046)\nplt.show()",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"id": "ebd16fd3",
"source": "## Step 3: threshold, then merge duplicates\n\nThe 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.",
"metadata": {}
},
{
"cell_type": "code",
"id": "2fbe9666",
"source": "def iou(a, b):\n ax0, ay0, aw, ah = a[:4]; bx0, by0, bw, bh = b[:4]\n ax1, ay1 = ax0 + aw, ay0 + ah\n bx1, by1 = bx0 + bw, by0 + bh\n ix0, iy0 = max(ax0, bx0), max(ay0, by0)\n ix1, iy1 = min(ax1, bx1), min(ay1, by1)\n iw, ih = max(0, ix1 - ix0), max(0, iy1 - iy0)\n inter = iw * ih\n union = aw * ah + bw * bh - inter\n return inter / union if union > 0 else 0.0\n\ndef nms(detections, iou_thresh=0.3):\n dets = sorted(detections, key=lambda d: -d[4])\n keep = []\n while dets:\n best = dets.pop(0)\n keep.append(best)\n dets = [d for d in dets if iou(best, d) < iou_thresh]\n return keep\n\n# a threshold set from the background score distribution: well above typical background,\n# well below the score at a well-aligned face window\nthreshold = np.percentile(score_map[score_map > -np.inf], 97.5)\nraw_detections = [(x0, y0, 16, 16, score_map[y0, x0])\n for y0 in range(score_map.shape[0]) for x0 in range(score_map.shape[1])\n if score_map[y0, x0] > threshold]\nfinal_detections = nms(raw_detections)\n\nprint(f'threshold (97.5th percentile of all window scores): {threshold:.2f}')\nprint(f'raw detections above threshold: {len(raw_detections)}')\nprint(f'detections after NMS: {len(final_detections)}')\nfor x0, y0, w, h, s in final_detections:\n print(f' box=({x0},{y0},{w},{h}) score={s:.2f}')",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"id": "823b09bc",
"source": "fig, ax = plt.subplots(figsize=(5, 5))\nax.imshow(scene, cmap='gray')\nfor x0, y0 in true_boxes:\n ax.add_patch(patches.Rectangle((x0, y0), 16, 16, edgecolor='lime', facecolor='none', linewidth=3, label='ground truth'))\nfor x0, y0, w, h, s in final_detections:\n ax.add_patch(patches.Rectangle((x0, y0), w, h, edgecolor='red', facecolor='none', linewidth=1.5, linestyle='--', label='detection'))\nhandles, labels = ax.get_legend_handles_labels()\nby_label = dict(zip(labels, handles))\nax.legend(by_label.values(), by_label.keys(), fontsize=8, loc='upper right')\nax.set_title(f'{len(final_detections)} detections after NMS vs. {len(true_boxes)} true faces')\nax.axis('off')\nplt.show()",
"metadata": {},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"id": "41ab27d4",
"source": "NMS collapses the raw detections down to exactly two boxes, tightly matching the two true face locations.\n\n## Handling scale: the image pyramid\n\nEverything 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.\n\n## RBK vs. Viola-Jones\n\nRBK'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.\n\n### Exercise\n\n1. Change `iou_thresh` in `nms` from `0.3` to `0.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.\n2. 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.\n3. Increase `n_faces` in `make_scene` to 4 and shrink `size` to 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?",
"metadata": {}
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"name": "python",
"version": "3.10.0"
}
},
"nbformat": 4,
"nbformat_minor": 5
}