Sliding Window Detection

Sliding window detection turns object detection into many small classification problems. A classifier trained to answer “is there an object of this class in this $w \times h$ window?” is run at every position of the image, a few pixels apart, and on every level of an image pyramid so that objects larger than the window shrink until they fit. Windows the classifier accepts become detections, and overlapping detections of the same object are merged into one. Face detectors in the Viola–Jones style and the pedestrian detector of Dalal and Triggs, built on histograms of oriented gradients (HOG), worked this way; the technique is also called scanning-window detection or exhaustive window search.

The object detection hub places sliding windows in the history of detectors; this article covers the scan itself, its cost, how its detections are merged, and what replaced it.

Purpose

A classifier on a fixed-size window is much easier to build than a detector: it sees one normalized crop and gives one score, and its training data are crops, positives centred and scaled to the window and negatives cut from images without the object. Scanning lifts it to whole images with any number of objects at any position and, through the pyramid, any scale, and the window that fired is the box.

When to Use It

Sliding windows suit problems where the objects have a nearly fixed shape and aspect ratio, such as upright pedestrians, frontal faces, road signs or a printed part on a conveyor belt, and where the window classifier is cheap or can reject most windows early. They also suit settings with no training data at all, such as matching a single template.

They suit poorly objects whose aspect ratio varies with viewpoint or articulation, since one window shape cannot fit them all, and expensive classifiers, since the cost grows with the number of windows. For general object categories, one-stage and two-stage networks replaced it.

How It Works

Positions: the stride

At one scale, the window’s top-left corner steps through a grid with a stride $\Delta$ in pixels. On an image of $W \times H$ pixels, a $w \times h$ window has

$$N(W, H) = \left(\left\lfloor \frac{W - w}{\Delta} \right\rfloor + 1\right)\left(\left\lfloor \frac{H - h}{\Delta} \right\rfloor + 1\right)$$

positions. An object is rarely aligned with the grid; the nearest window is off by up to $\Delta/2$ pixels in each direction, and the classifier must still accept it. So the stride must be small compared with how quickly the classifier’s score falls off as the window slides off the object, not only compared with the window. Dalal’s thesis found that strides larger than HOG’s 8-pixel cell reduced performance markedly.

Scales: the pyramid and its scale step

A classifier trained on one window size finds objects of about that size. To find larger objects, the image is shrunk by a scale step $r > 1$ again and again, giving levels at scales $s_k = r^k$, and the same window is scanned over each level until it no longer fits. A window at $(x, y)$ on level $k$ maps back to the box from $(s_k x,\, s_k y)$ to $(s_k (x + w),\, s_k (y + h))$ in the original image. The number of levels is

$$K + 1 = \left\lfloor \frac{\ln \min(W / w,\; H / h)}{\ln r} \right\rfloor + 1.$$

An object whose size falls between two levels is off by up to a factor $\sqrt{r}$ from the nearer one, a mismatch the classifier must also tolerate. This is a pyramid with steps finer than an octave: the image pyramid article’s dyadic pyramid has $r = 2$, while detectors use steps such as 1.25 or 1.05.

A stride of $\Delta$ pixels on level $k$ is a step of $s_k \Delta$ pixels in the original image, so the step grows with the object size and stays the same fraction of the window. Viola and Jones (2001) reached the same spacing from the other direction: they kept the image and scaled the detector itself, by factors 1.25 apart, shifting it by $[s\Delta]$ pixels at scale $s$, with $[\cdot]$ denoting rounding. Their rectangle features can be evaluated at any scale with the same cost, the reason they gave for scaling the detector rather than the image.

Window shape

The window has one aspect ratio, chosen for the class: square $24 \times 24$ windows for Viola and Jones’s frontal faces, and $64 \times 128$ for Dalal and Triggs’s upright people. Their window included about 16 pixels of margin around the person on each side; shrinking the margin to 8 pixels (a $48 \times 112$ window) lowered performance by 6% at $10^{-4}$ false positives per window (the caption of their Figure 4(e) says about 3%), so the window is a context region, not a tight box around the object. Classes with several shapes need several windows or a classifier per shape, which multiplies the scan.

Classifying each window

Each window is mapped to a feature vector and scored by a binary classifier. Classic pairs were Haar-like rectangle features with a boosted cascade (Viola–Jones) and HOG with a linear support vector machine (Dalal and Triggs). The training set reflects the scan: almost every window in an image is background, so negatives are first sampled at random from object-free images, then the trained classifier is scanned over those images and the windows it wrongly accepts, the hard negatives, are added before retraining. Dalal and Triggs retrained once in this way, which improved their default detector by 5% at $10^{-4}$ false positives per window; Viola and Jones collected the false positives of the partial cascade to train each new stage.

Number of windows and cost

Each pyramid level holds about $1/r^2$ as many windows as the one below, so the total is close to a geometric series:

$$N_{\text{total}} = \sum_{k=0}^{K} N\!\left(\frac{W}{r^k}, \frac{H}{r^k}\right) \;\lesssim\; \frac{N(W, H)}{1 - r^{-2}}.$$

This bound is our own; it holds whenever the stride is no larger than the window, and it overestimates slightly, because subtracting the window size removes a larger share of each coarser level. Halving the stride multiplies the cost by about four; the scale step matters through $1/(1 - r^{-2})$, which is 1.33 for $r = 2$, 2.78 for $r = 1.25$ and 10.8 for $r = 1.05$. The cost of the whole detector is this count times the cost per window, and both have been attacked: the per-window cost by cascades that reject most windows after a few cheap tests, and the count by the replacements in the Variants section.

Reported figures give a sense of scale. Viola and Jones scanned 75,081,800 sub-windows over the 130 images of the MIT+CMU face test set with $\Delta = 1.0$ and a starting scale of 1.0; their cascade evaluated on average 10 of its 6,061 features per window, and a $384 \times 288$ image took about 0.067 s on a 700 MHz Pentium III with a starting scale of 1.25 and $\Delta = 1.5$. Dalal’s thesis counts about 26.9 million windows over the INRIA person test images with a scale step of 1.05 and a stride of 8 pixels, and 1,976 million with 1.01 and 2.

Merging detections

A good window classifier is tolerant to small shifts and rescalings, which is what lets a coarse grid find objects at all, so each object fires a cluster of neighbouring windows across positions and adjacent scales. Viola and Jones partitioned the detections into disjoint subsets, putting two detections in the same subset when their regions overlapped, and returned the average corners of each subset. Dalal’s thesis treated the detections as points in position and log-scale, weighted by their clipped SVM scores, and took the modes of their kernel density as found by mean shift. Most later systems use greedy non-maximum suppression, which keeps the highest-scoring window and removes the windows that overlap it beyond an IoU threshold.

How to Apply It

The example renders a $384 \times 256$ scene with intensities in $[0, 1]$: 60 random strokes and 8 rings as clutter, Gaussian noise, and five upright stick figures with slightly jittered limbs, whose $w \times h$ boxes, with $w = h/2$, are 44, 62, 90, 128 and 176 pixels tall. The window classifier is the zero-mean normalized cross-correlation (NCC) with a $20 \times 40$ stick-figure template, the simplest form of template matching, with a threshold of 0.45. For speed, NCC is computed at every position by FFT correlation, and the stride selects the windows that are kept and counted. Greedy NMS at IoU 0.3 merges the detections, and a detection is correct when it overlaps an unmatched figure’s box with IoU at least 0.5. The script scans one scene with stride 2 and scale step 1.25, checks the best-placed windows at stride 8, then scans five scenes (seeds 0 to 4) for four strides and four scale steps.

import numpy as np
from scipy import ndimage, signal

def stroke(img, p, q, width):
    """Draw an anti-aliased line segment from p to q, given as (x, y), at intensity 1."""
    y, x = np.mgrid[0:img.shape[0], 0:img.shape[1]]
    p, d = np.asarray(p, float), np.asarray(q, float) - np.asarray(p, float)
    t = np.clip(((x - p[0]) * d[0] + (y - p[1]) * d[1]) / (d @ d), 0, 1)
    dist = np.hypot(x - p[0] - t * d[0], y - p[1] - t * d[1])
    np.maximum(img, np.clip(width / 2 + 0.5 - dist, 0, 1), out=img)

def ring(img, c, r, width):
    y, x = np.mgrid[0:img.shape[0], 0:img.shape[1]]
    dist = np.abs(np.hypot(x - c[0], y - c[1]) - r)
    np.maximum(img, np.clip(width / 2 + 0.5 - dist, 0, 1), out=img)

def stick_figure(img, x0, y0, h, rng):
    """Upright stick figure in the (h/2) x h box with top-left corner (x0, y0);
    the figure is 3/4 of the box height, the rest is a margin of context."""
    u, cx, top, lw = 0.75 * h, x0 + h / 4, y0 + h / 8, max(1.0, h / 22)
    j = lambda: rng.uniform(-0.04, 0.04) * u                 # small pose jitter
    hip = (cx, top + 0.58 * u)
    ring(img, (cx, top + 0.1 * u), 0.1 * u, lw)                # head
    stroke(img, (cx, top + 0.22 * u), hip, lw)                 # torso
    for s in (-1, 1):
        stroke(img, (cx, top + 0.28 * u), (cx + s * 0.22 * u + j(), top + 0.5 * u + j()), lw)  # arm
        stroke(img, hip, (cx + s * 0.17 * u + j(), top + u + j()), lw)                         # leg

def make_scene(seed, H=256, W=384):
    """Five figures (box heights 44 to 176 px) among random strokes and rings; values in [0, 1]."""
    rng = np.random.default_rng(seed)
    ink = np.zeros((H, W))
    for _ in range(60):
        p = rng.uniform([0, 0], [W, H])
        stroke(ink, p, p + rng.normal(0, 25, 2), rng.uniform(1, 4))
    for _ in range(8):
        ring(ink, rng.uniform([0, 0], [W, H]), rng.uniform(4, 15), 2)
    gt = []
    for x0, h in zip((10, 70, 140, 220, 300), (44, 62, 90, 128, 176)):
        y0 = rng.integers(0, H - h + 1)
        stick_figure(ink, x0, y0, h, rng)
        gt.append([x0, y0, x0 + h / 2, y0 + h])
    return np.clip(0.2 + 0.6 * ink + rng.normal(0, 0.08, (H, W)), 0, 1), np.array(gt)

# Window classifier: zero-mean normalized cross-correlation (NCC) with a 20 x 40 template.
w, h = 20, 40
tmpl = np.zeros((h, w)); stick_figure(tmpl, 0, 0, h, np.random.default_rng(99))
T = (tmpl - tmpl.mean()) / np.linalg.norm(tmpl - tmpl.mean())

def ncc(level):
    """NCC score of every w x h window of one pyramid level, at stride 1."""
    corr = lambda a, k: signal.correlate(a, k, mode="valid", method="fft")
    s1, s2 = corr(level, np.ones((h, w))), corr(level ** 2, np.ones((h, w)))
    return corr(level, T) / np.sqrt(np.maximum(s2 - s1 ** 2 / (w * h), 1e-9))

def pyramid(img, r):
    """Yield (scale, level): the image shrunk by r, r^2, ... (smoothed first) while the window fits."""
    s = 1.0
    while img.shape[0] / s >= h and img.shape[1] / s >= w:
        smooth = ndimage.gaussian_filter(img, 0.5 * (s - 1)) if s > 1 else img
        yield s, ndimage.zoom(smooth, 1 / s, order=1)
        s *= r

def detect(img, stride, r, thr=0.45):
    """Score windows at the given stride on every level; return boxes (in image pixels), scores,
    and the number of windows evaluated per level."""
    boxes, scores, counts = [], [], []
    for s, level in pyramid(img, r):
        m = ncc(level)[::stride, ::stride]     # computed densely, but only these windows count
        counts.append(m.size)
        ys, xs = np.nonzero(m > thr)
        boxes += [[x * stride * s, y * stride * s, (x * stride + w) * s, (y * stride + h) * s]
                  for y, x in zip(ys, xs)]
        scores += list(m[ys, xs])
    return np.array(boxes).reshape(-1, 4), np.array(scores), counts

def iou(b, B):
    iw = np.clip(np.minimum(b[2], B[:, 2]) - np.maximum(b[0], B[:, 0]), 0, None)
    ih = np.clip(np.minimum(b[3], B[:, 3]) - np.maximum(b[1], B[:, 1]), 0, None)
    return iw * ih / ((b[2] - b[0]) * (b[3] - b[1]) + (B[:, 2] - B[:, 0]) * (B[:, 3] - B[:, 1]) - iw * ih)

def nms(boxes, scores, t=0.3):                 # greedy non-maximum suppression
    order, keep = np.argsort(-scores), []
    while len(order):
        keep.append(order[0])
        order = order[1:][iou(boxes[order[0]], boxes[order[1:]]) <= t]
    return np.array(keep, int)

def evaluate(boxes, scores, gt):               # in score order, each figure matched once at IoU >= 0.5
    used = np.zeros(len(gt), bool)
    for b in boxes[np.argsort(-scores)]:
        o = np.where(used, 0, iou(b, gt))
        if o.max() >= 0.5:
            used[o.argmax()] = True
    return used.sum(), len(boxes) - used.sum()

img, gt = make_scene(0)
boxes, scores, counts = detect(img, stride=2, r=1.25)
print("stride 2, scale step 1.25: windows per level", counts)
print(f"  total {sum(counts)}; level 0 / (1 - 1.25^-2) = {counts[0] / (1 - 1.25 ** -2):.0f}")
print(f"  raw detections {len(boxes)}, per figure at IoU >= 0.5:",
      [int((iou(g, boxes) >= 0.5).sum()) for g in gt], "-> TP %d, FP %d" % evaluate(boxes, scores, gt))
keep = nms(boxes, scores)
print(f"  after NMS {len(keep)}: TP %d, FP %d" % evaluate(boxes[keep], scores[keep], gt),
      "scores", np.round(scores[keep], 2))
boxes, scores, counts = detect(img, stride=8, r=1.25, thr=-1)    # keep every window
print("stride 8, scale step 1.25: best score of a window at IoU >= 0.5, per figure",
      [round(float(scores[iou(g, boxes) >= 0.5].max()), 2) for g in gt])

print("\nfive scenes (seeds 0-4, 25 figures): windows per image / missed figures / false positives after NMS")
print("stride " + "".join(f"{f'r = {r}':>20}" for r in (1.1, 1.25, 1.5, 2.0)))
for stride in (1, 2, 4, 8):
    row = []
    for r in (1.1, 1.25, 1.5, 2.0):
        n = tp = fp = 0
        for seed in range(5):
            img, gt = make_scene(seed)
            boxes, scores, counts = detect(img, stride, r)
            k = nms(boxes, scores)
            a, b = evaluate(boxes[k], scores[k], gt)
            n, tp, fp = n + sum(counts), tp + a, fp + b
        row.append(f"{n // 5:>10d} / {25 - tp:2d} / {fp:2d}")
    print(f"{stride:6d} " + "".join(row))

Output:

stride 2, scale step 1.25: windows per level [19947, 11952, 7182, 4094, 2277, 1242, 574, 248, 46]
  total 47562; level 0 / (1 - 1.25^-2) = 55408
  raw detections 22, per figure at IoU >= 0.5: [2, 5, 4, 5, 2] -> TP 5, FP 17
  after NMS 5: TP 5, FP 0 scores [0.82 0.7  0.69 0.67 0.5 ]
stride 8, scale step 1.25: best score of a window at IoU >= 0.5, per figure [0.2, 0.26, 0.7, 0.51, 0.67]

five scenes (seeds 0-4, 25 figures): windows per image / missed figures / false positives after NMS
stride              r = 1.1            r = 1.25             r = 1.5             r = 2.0
     1     383139 /  0 /  5    189093 /  0 /  2    126088 /  0 /  1     96527 /  1 /  3
     2      96293 /  1 /  2     47562 /  1 /  2     31775 /  1 /  1     24369 /  2 /  3
     4      24429 /  2 /  1     12085 /  2 /  0      8047 / 10 /  0      6212 /  9 /  1
     8       6298 / 10 /  0      3096 / 15 /  0      2064 / 22 /  0      1592 / 24 /  0

On the first scene, the window count falls by a factor of about 0.6 per level, a little faster than $1/r^2 = 0.64$ because every level loses a window’s width and height at its border, so the total stays below the bound. The scan accepts 22 windows, 2 to 5 of them on each figure, and since each figure can be matched once, 17 count as false positives; NMS reduces them to one detection per figure with none left over.

The grid shows the trade-off between cost and misses. Going from stride 1 to stride 8 cuts the windows about 61-fold, close to $8^2$, and going from a scale step of 1.1 to 2.0 cuts them about 4-fold, close to the ratio of the factors $1/(1 - r^{-2})$. With stride 1 or 2 almost every figure is found at any scale step, while stride 8 misses 10 to 24 of the 25. The misses are failures of the classifier, not of the geometry: on the first scene at stride 8, every figure still has a window at IoU 0.5 or more, but for the two smallest figures the best such window scores 0.2 and 0.26. In our reading, thin strokes correlate well only when they line up within a pixel or two, so the score drops below the threshold between grid points and between levels; a classifier that tolerates more misalignment, such as HOG with its pooled histograms, would allow a coarser scan. False positives go the other way: the densest scans give clutter the most chances to cross the threshold, with 5 false positives at stride 1 and scale step 1.1 against none on the coarsest scans.

Variants

• Cascades. Increasingly expensive classifiers, each run only on the windows the previous ones accepted, as in Viola–Jones; Dalal and Triggs named a rejection-chain HOG detector as future work.
• Convolutional sliding windows. A convolutional network trained on fixed-size crops can be applied to a larger image directly: each convolution runs over the whole image, and the output is a feature map with one class prediction per window, the network’s receptive field, so overlapping windows share computation. OverFeat (Sermanet et al., 2014) ran its classification network this way at 6 input scales, with the fully connected layers treated as $1 \times 1$ convolutions. The authors give the network’s total subsampling ratio as $2 \times 3 \times 2 \times 3 = 36$, one output every 36 pixels; these factors are the strides of their accurate model (their Table 3), while the strides of the fast model in their Table 1 multiply to 32. Applying the last $3 \times 3$ pooling at each of its offsets brought the ratio down to 12. The one-stage object detectors article covers OverFeat as a detector.
• Region proposals. A class-agnostic method proposes a few thousand likely windows, and only those are classified, as in R-CNN. OverFeat’s authors noted that the top two other systems in ILSVRC 2013 detection used an initial segmentation step to cut the candidate windows from about 200,000 to 2,000. The two-stage object detectors article follows this line.
• Dense prediction on feature maps. One-stage detectors and Faster R-CNN’s region proposal network slide a small network over a convolutional feature map, predicting scores and offsets for several anchor boxes per position. In their ablation, Ren et al. (2015) emulated OverFeat with Fast R-CNN and the ZF network on about 20,000 dense windows of 3 scales and 3 aspect ratios, with features from 5 image scales, and reached 53.9% mAP on PASCAL VOC 2007 test (53.8% with one scale), against 58.7% for 300 proposals from their two-stage cascade (their Table 5). In our reading, box regression is what lets such a coarse grid produce precise boxes, which a plain window scan cannot.
• Template matching and tiled inference. Sliding windows remain wherever there is a fixed template, as in the example, and in tiling: an image too large for a detector’s input, such as an aerial or microscope image, is cut into overlapping tiles, the detector runs on each, and the results are merged. Slicing aided hyper inference (Akyon et al., 2022) slices the image into overlapping patches, resizes each, detects in each and merges the results with NMS, optionally together with a detection on the full image, to find small objects.

Best Practices

• Match the scan to the classifier’s tolerance. The stride should be at most the distance over which the classifier’s score stays high, about one feature cell for HOG; the scale step should keep the worst-case mismatch $\sqrt{r}$ within the range covered by the training crops.
• Count false positives per image, not only per window. A small rate per window becomes many false alarms per image over millions of windows: Dalal and Triggs equated $10^{-4}$ false positives per window to about 0.8 per $640 \times 480$ image before non-maximum suppression.

Pitfalls

• Objects smaller than the window are never found, since the pyramid only shrinks the image; upsampling the image first, at the cost of four times the windows per doubling, is the usual remedy.
• Objects at the image border are missed when no window fits around them, unless the image is padded.
• Merging that fuses neighbours. Grouping all overlapping windows, as Viola and Jones did, can merge two objects whose windows overlap; Dalal’s thesis gives the case of two people at very different scales, one detection inside the other, as an argument for merging in position and scale.

Evidence and Impact

Dalal’s thesis measured the scan settings directly for its HOG person detector on the INRIA test set. Average precision fell from 0.739 at a scale step of 1.05 to 0.708 at 1.10 and 0.618 at 1.30, and the best value came at 1.01, 0.015 higher than at 1.05. Over strides of 2, 4, 8, 12 and 16 pixels, maximum recall fell steadily from 0.856 to 0.742, and average precision was 0.747, 0.735, 0.739, 0.702 and 0.655. Scanning with a scale step of 1.01 and a stride of 2 raised average precision to 0.768 but tested 1,976 million windows instead of 26.9 million, while the classifier’s false-positive rate per window stayed the same; the thesis cites this to show that per-window error rates are not a direct measure of detector performance. Viola and Jones reported that raising $\Delta$ from 1.0 to 1.5 gave a significant speedup with only a slight decrease in accuracy.

In our reading, the technique’s parts survive in modern detectors: the image pyramid in the feature pyramid, the window grid in the positions and anchors of a dense head, hard-negative mining in sampling and loss reweighting, and merging in non-maximum suppression. What changed is that a network shares computation across windows and regresses boxes, so the grid no longer has to place a window on every object.