{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lesson 40: Object Detection from Sliding Windows\n", "\n", "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. \n", "\n", "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.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "b9296e38", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import torch\n", "import torch.nn as nn\n", "import torch.nn.functional as F\n", "import matplotlib.pyplot as plt\n", "import matplotlib.patches as patches" ] }, { "cell_type": "markdown", "id": "d56bd578", "metadata": {}, "source": [ "## Step 1: a synthetic \"face\" and a window classifier\n", "\n", "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?" ] }, { "cell_type": "code", "execution_count": null, "id": "4aa51ab8", "metadata": {}, "outputs": [], "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", "\n", "def 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", "\n", "rng = np.random.default_rng(11)\n", "N = 200\n", "faces = np.array([make_face(rng=rng) for _ in range(N)])\n", "nonfaces = np.array([make_nonface(rng=rng) for _ in range(N)])\n", "X = np.concatenate([faces, nonfaces])\n", "y = np.concatenate([np.ones(N), np.zeros(N)]).astype(np.float32)\n", "perm = rng.permutation(len(X))\n", "X, y = X[perm], y[perm]\n", "split = int(0.8 * len(X))\n", "Xtr, ytr, Xte, yte = X[:split], y[:split], X[split:], y[split:]\n", "\n", "fig, axes = plt.subplots(1, 6, figsize=(11, 2))\n", "for 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')\n", "plt.show()" ] }, { "cell_type": "code", "execution_count": null, "id": "c65c6880", "metadata": {}, "outputs": [], "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", "\n", "torch.manual_seed(0)\n", "model = WindowClassifier()\n", "opt = torch.optim.Adam(model.parameters(), lr=0.01)\n", "Xt = torch.tensor(Xtr).unsqueeze(1); yt = torch.tensor(ytr)\n", "for _ 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", "\n", "with torch.no_grad():\n", " Xte_t = torch.tensor(Xte).unsqueeze(1)\n", " acc = ((model(Xte_t) > 0).float() == torch.tensor(yte)).float().mean().item()\n", "print(f'window classifier test accuracy: {acc:.1%}')" ] }, { "cell_type": "markdown", "id": "a03fdf83", "metadata": {}, "source": [ "## Step 2: slide the window across a scene\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "4f3e277d", "metadata": {}, "outputs": [], "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", " corners = []\n", " tries = 0\n", " while len(corners) < 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 corners):\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", " corners.append((x0, y0))\n", " # report boxes by center, not top-left corner; cast to plain float so printing doesn't show np.float64(...)\n", " centers = [(float(x0 + face_size / 2), float(y0 + face_size / 2)) for x0, y0 in corners]\n", " return scene, centers\n", "\n", "scene_rng = np.random.default_rng(21)\n", "scene, true_boxes = make_scene(scene_rng)\n", "print(f'true face centers: {true_boxes}')\n", "\n", "def sliding_window_scores(model, scene, win=16, stride=1):\n", " half = win // 2\n", " scores = np.full(scene.shape, np.nan, dtype=np.float32) # NaN = no window centered here (too close to the border)\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 + half, x0 + half] = model(torch.tensor(patch[None, None]).float()).item()\n", " return scores\n", "\n", "score_map = sliding_window_scores(model, scene)\n", "\n", "cmap = plt.cm.hot.copy()\n", "cmap.set_bad(color='gray') # border pixels with no score (NaN) render as gray, not as an arbitrary color-scale value\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(9, 4))\n", "axes[0].imshow(scene, cmap='gray')\n", "for cx, cy in true_boxes:\n", " axes[0].add_patch(patches.Rectangle((cx - 8, cy - 8), 16, 16, edgecolor='lime', facecolor='none', linewidth=2))\n", "axes[0].set_title('scene (true faces in green)'); axes[0].axis('off')\n", "im = axes[1].imshow(score_map, cmap=cmap)\n", "axes[1].set_title('window classifier score, by window center\\n(gray border = no window fits there)'); axes[1].axis('off')\n", "plt.colorbar(im, ax=axes[1], fraction=0.046)\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "ebd16fd3", "metadata": {}, "source": [ "## Step 3: threshold, then merge duplicates\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "2fbe9666", "metadata": {}, "outputs": [], "source": [ "def iou(a, b):\n", " acx, acy, aw, ah = a[:4]; bcx, bcy, bw, bh = b[:4]\n", " ax0, ay0, ax1, ay1 = acx - aw / 2, acy - ah / 2, acx + aw / 2, acy + ah / 2\n", " bx0, by0, bx1, by1 = bcx - bw / 2, bcy - bh / 2, bcx + bw / 2, bcy + bh / 2\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", "\n", "def 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\n", "valid = ~np.isnan(score_map)\n", "threshold = np.percentile(score_map[valid], 97.5)\n", "raw_detections = [(cx, cy, 16, 16, score_map[cy, cx]) # (cx, cy) is already the window's center\n", " for cy, cx in zip(*np.where(valid)) if score_map[cy, cx] > threshold]\n", "final_detections = nms(raw_detections)\n", "\n", "print(f'threshold (97.5th percentile of all window scores): {threshold:.2f}')\n", "print(f'raw detections above threshold: {len(raw_detections)}')\n", "print(f'detections after NMS: {len(final_detections)}')\n", "for cx, cy, w, h, s in final_detections:\n", " print(f' box=(cx={cx:.0f}, cy={cy:.0f}, w={w}, h={h}) score={s:.2f}')" ] }, { "cell_type": "code", "execution_count": null, "id": "823b09bc", "metadata": {}, "outputs": [], "source": [ "fig, ax = plt.subplots(figsize=(5, 5))\n", "ax.imshow(scene, cmap='gray')\n", "for cx, cy in true_boxes:\n", " ax.add_patch(patches.Rectangle((cx - 8, cy - 8), 16, 16, edgecolor='lime', facecolor='none', linewidth=3, label='ground truth'))\n", "for cx, cy, w, h, s in final_detections:\n", " ax.add_patch(patches.Rectangle((cx - w / 2, cy - h / 2), w, h, edgecolor='red', facecolor='none', linewidth=1.5, linestyle='--', label='detection'))\n", "handles, labels = ax.get_legend_handles_labels()\n", "by_label = dict(zip(labels, handles))\n", "ax.legend(by_label.values(), by_label.keys(), fontsize=8, loc='upper right')\n", "ax.set_title(f'{len(final_detections)} detections after NMS vs. {len(true_boxes)} true faces')\n", "ax.axis('off')\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "41ab27d4", "metadata": {}, "source": [ "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.\n", "\n", "## Handling scale: the image pyramid\n", "\n", "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.\n", "\n", "## Viola-Jones\n", "\n", "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.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "40b0d8c7", "metadata": {}, "outputs": [], "source": [ "import urllib.request\n", "from pathlib import Path\n", "import cv2\n", "\n", "CACHE_DIR = Path.home() / '.cache' / 'cvintro'\n", "CASCADE_URL = 'https://raw.githubusercontent.com/opencv/opencv/4.x/data/haarcascades/haarcascade_frontalface_default.xml'\n", "CASCADE_PATH = CACHE_DIR / 'haarcascade_frontalface_default.xml'\n", "\n", "def ensure_cascade():\n", " if CASCADE_PATH.exists():\n", " return\n", " CACHE_DIR.mkdir(parents=True, exist_ok=True)\n", " print('Downloading the Viola-Jones frontal-face cascade (one-time, cached under ~/.cache/cvintro)...')\n", " urllib.request.urlretrieve(CASCADE_URL, CASCADE_PATH)\n", "\n", "ensure_cascade()\n", "\n", "cascade = cv2.CascadeClassifier(str(CASCADE_PATH))\n", "photo = cv2.imread('../img/apollo11_crew.jpg')\n", "gray = cv2.cvtColor(photo, cv2.COLOR_BGR2GRAY)\n", "\n", "faces = cascade.detectMultiScale(gray, scaleFactor=1.1, minNeighbors=5, minSize=(60, 60))\n", "print(f'{len(faces)} detections')\n", "\n", "photo_rgb = cv2.cvtColor(photo, cv2.COLOR_BGR2RGB)\n", "fig, ax = plt.subplots(figsize=(8, 6))\n", "ax.imshow(photo_rgb)\n", "for (x, y, w, h) in faces:\n", " ax.add_patch(patches.Rectangle((x, y), w, h, edgecolor='lime', facecolor='none', linewidth=2))\n", "ax.set_title(f'cv2.CascadeClassifier: {len(faces)} detections')\n", "ax.axis('off')\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "0274791d", "metadata": {}, "source": [ "

Image source: NASA (public domain), via Wikimedia Commons

" ] }, { "cell_type": "markdown", "id": "b8c87cf2", "metadata": {}, "source": "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." }, { "cell_type": "markdown", "id": "50ffa468", "metadata": {}, "source": [ "### Exercises\n", "\n", "1. 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.\n", "2. 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.\n", "3. 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?\n", "4. Lower `minNeighbors` on the real Viola-Jones cascade from `5` to `2` and rerun. Does the fabric false positive get worse, or do new false positives appear elsewhere? Then try raising `minNeighbors` to `8` — does it clean up the false positive, and does it cost any true detections?" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.10.0" } }, "nbformat": 4, "nbformat_minor": 5 }