AI.Cruz - Learn AI Through Interactive Visualizations

COMPUTER VISION

Sliding Window Detection: Exhaustive Search, Pyramids and NMS

Sliding window exhaustively classifies every fixed-size crop of an image. Image pyramids handle scale variation. Non-maximum suppression collapses duplicate detections into one.

1The Exhaustive Search Problem

Object detection must answer: where are the objects? Unlike classification (one label per image), detection requires finding every instance at an unknown location. The brute-force solution is simple: slide a fixed-size window across the entire image, run a classifier on each crop, and report every location that scores above a threshold. This is exactly what the Viola-Jones face detector (2001) and the HOG+SVM pedestrian detector (Dalal & Triggs, 2005) did, and they were state-of-the-art for nearly a decade.

Classic pipeline: (1) Compute HOG features for the image. (2) Slide a 128×64 (person-sized) window at every position with stride s. (3) Extract the HOG descriptor for that crop. (4) Run it through a linear SVM. (5) If score > threshold, record the bounding box + score. (6) Apply NMS to remove duplicates. This pipeline is fully deterministic and interpretable, but slow: O(H × W / s²) classifier calls per pyramid level.

2Image Pyramids for Multi-Scale Detection

A fixed window finds objects only at one size. A person 2 metres away occupies fewer pixels than one 1 metre away. The solution is an image pyramid: repeatedly downsample the image by a scale factor (typically 0.75 or 0.5) and run the same fixed-size window at each level. The window effectively sees the object at progressively larger scales. A bounding box detected at pyramid level k is rescaled by 1/scale^k to map back to original image coordinates.

Pyramid construction
Start at full resolution. Multiply both dimensions by scale (e.g., 0.75) each step. Stop when image is smaller than the window. A 640×480 image with scale 0.75 produces roughly 5 levels before a 128×128 window no longer fits.

Total windows
Summing across all pyramid levels, a typical setup produces thousands of candidate windows. Each requires a full feature extraction + classifier call. This is why CNN-based detectors replaced sliding window: they share computation across all positions via convolution.

3Non-Maximum Suppression (NMS)

A detected object triggers high scores at many adjacent windows — all slightly overlapping boxes around the same person. NMS reduces these to a single best box. The algorithm is greedy: sort all detections by score descending, keep the highest-scoring box, suppress (remove) all other boxes whose Intersection-over-Union (IoU) with the kept box exceeds a threshold (typically 0.5), then repeat on the remaining boxes.

NMS step-by-step: (1) Compute score for each candidate box. (2) Sort boxes by score, highest first. (3) Take the top box — it's a confirmed detection. (4) Compute IoU between it and all remaining boxes. (5) Discard any box with IoU > 0.5 (they overlap the same object). (6) Move to the next surviving box and repeat. Result: one box per distinct object, the highest-confidence one. IoU = area of intersection / area of union.

4Why Modern Detectors Replaced Sliding Window

Sliding window is conceptually clean but computationally redundant: adjacent windows share almost all pixels yet each is processed independently. Modern detectors eliminate this waste with shared convolutional features.

R-CNN (2014)
Run selective search to get ~2000 region proposals first, then warp each to fixed size and run CNN. 2000 forward passes per image — still slow.

Fast R-CNN / Faster R-CNN
Compute feature map once for the full image. For each region proposal, use RoI Pooling to extract a fixed-size feature from the shared map — no redundant computation.

YOLO / SSD (2016+)
One forward pass predicts all boxes simultaneously. Anchor boxes at every spatial position and scale replace the pyramid entirely. Real-time at 30+ FPS on GPU.

IoU & NMS →Anchor Boxes →Object Detection →

Sliding window: count candidates across strides and pyramid levels

import numpy as np

def sliding_window(image_h, image_w, window_h, window_w, stride):
    windows = []
    r = 0
    while r + window_h <= image_h:
        c = 0
        while c + window_w <= image_w:
            windows.append((r, c))
            c += stride
        r += stride
    return windows

img_h, img_w = 480, 640
win_h, win_w = 128, 128

print("Sliding Window Analysis")
print("Image: " + str(img_w) + "x" + str(img_h) + "  Window: " + str(win_w) + "x" + str(win_h))
print()

print("Effect of stride on candidate count:")
for stride in [16, 32, 64, 128]:
    wins = sliding_window(img_h, img_w, win_h, win_w, stride)
    print("  stride=" + str(stride).rjust(3) + "  ->  " + str(len(wins)).rjust(5) + " windows")

print()
print("Image pyramid (scale=0.75 per level, stride=64):")
scale = 1.0
level = 0
total = 0
while True:
    h = int(img_h * scale)
    w = int(img_w * scale)
    if h < win_h or w < win_w:
        break
    wins = sliding_window(h, w, win_h, win_w, 64)
    total += len(wins)
    print("  Level " + str(level) + ": " + str(w) + "x" + str(h) +
          "  ->  " + str(len(wins)) + " windows")
    scale *= 0.75
    level += 1

print("  Total across pyramid: " + str(total) + " windows")
print()

# NMS simulation: greedy IoU suppression
def iou_1d(a, b):
    lo = max(a[0], b[0])
    hi = min(a[1], b[1])
    intersection = max(0, hi - lo)
    union = (a[1] - a[0]) + (b[1] - b[0]) - intersection
    return intersection / union if union > 0 else 0.0

# 1D boxes (start, end) with scores
boxes = [(10, 50, 0.95), (15, 55, 0.82), (12, 52, 0.77), (80, 130, 0.91), (85, 135, 0.74)]
sorted_boxes = sorted(boxes, key=lambda x: -x[2])

kept = []
suppressed = set()
for i, (s, e, score) in enumerate(sorted_boxes):
    if i in suppressed:
        continue
    kept.append((s, e, score))
    for j in range(i + 1, len(sorted_boxes)):
        s2, e2, _ = sorted_boxes[j]
        if iou_1d((s, e), (s2, e2)) > 0.5:
            suppressed.add(j)

print("NMS demo (1D boxes as (start, end, score)):")
print("  Before NMS: " + str(len(boxes)) + " boxes")
print("  After  NMS: " + str(len(kept)) + " boxes kept")
for s, e, sc in kept:
    print("    box [" + str(s) + ", " + str(e) + "]  score=" + str(sc))

Sliding Window Detection: Exhaustive Search, Pyramids and NMS

1The Exhaustive Search Problem

2Image Pyramids for Multi-Scale Detection

3Non-Maximum Suppression (NMS)

4Why Modern Detectors Replaced Sliding Window

Recall check