Deformable Part Models

"A person is a head, two arms, two legs, and a torso, held together by springs that complain when you stand wrong. I score the parts, I pay the spring tax, and I add it all up. That is the whole job."

A Deformable Part Model, Holding Itself Together

Section 16.4 chased speed; this section returns to the expressiveness frontier and pushes it as far as hand-crafted recognition ever reached. The HOG+SVM detector of Section 16.3 treats an object as one rigid block of gradient orientations. That works for pedestrians standing upright but fails the moment a person sits, a horse turns, or a bicycle is photographed from a new angle, because the parts shift relative to one another and a single rigid template cannot follow them. This section presents the model that solved this, deformable part models (DPM), the culmination of the hand-crafted era. It builds on the HOG features of the previous section and on the distance transform of Section 6.5, which there measured each pixel's distance to the nearest object boundary and here returns in a generalized form to fold the spring cost into the part search. The spring metaphor itself is old: it traces back to a 1973 paper by Fischler and Elschlager that the chapter's bibliography cites.

1. Objects as Parts on Springs Intermediate

A DPM has two kinds of filter, both computed in HOG feature space. A single root filter captures the whole object at a coarse resolution, essentially the Section 16.3 template. Several part filters capture sub-regions (a head, a wheel, a leg) at twice the root's resolution, so they see finer detail. Each part has an anchor, its ideal position relative to the root, and a quadratic deformation cost that penalizes displacement away from that anchor, the spring. The model is willing to let a part move to where the image evidence is strongest, but it pays for the move, and the more it deviates from the anatomically expected position, the more it pays. Figure 16.5.1 shows the structure for a person model: the root box, the part boxes at their anchors, and the springs that tie each part to its anchor.

2. The Scoring Function Advanced

Here is where the spring metaphor becomes one equation you can actually compute, and it is simpler than the moving-parts picture suggests: every term is either a match you already know how to score or a penalty for stretching a spring. The score of placing the model at root position $p_0$ with parts at positions $p_1, \ldots, p_n$ is filter matches minus deformation costs:

$$ \text{score} \;=\; \underbrace{F_0 \cdot \phi(p_0)}_{\text{root match}} \;+\; \sum_{i=1}^{n} \underbrace{F_i \cdot \phi(p_i)}_{\text{part } i \text{ match}} \;-\; \sum_{i=1}^{n} \underbrace{d_i \cdot \big( dx_i^2,\, dx_i,\, dy_i^2,\, dy_i \big)}_{\text{deformation cost of part } i}, $$

where $F_i \cdot \phi(p_i)$ is the dot product of part filter $F_i$ with the HOG features $\phi$ at position $p_i$ (a correlation, exactly the Section 16.3 score), and $(dx_i, dy_i)$ is the displacement of part $i$ from its anchor. The deformation term is just a dot product too: the learned coefficient vector $d_i$ against the four displacement features $(dx_i^2, dx_i, dy_i^2, dy_i)$, so a single learned weight scales each of the two squared and two raw displacement terms. The quadratic terms $dx_i^2, dy_i^2$ make the cost grow faster the farther the part strays, and the linear terms let the spring's rest position differ from the raw anchor. A detection is a root position whose best-over-part-placements score clears a threshold. The structure is a star: every part connects to the root and to no other part, which is exactly what makes inference tractable in the next subsection.

3. Fast Inference With the Distance Transform Advanced

Naively, finding the best placement means, for every root position, searching every part over every possible position, an explosion. The star structure rescues it. Because each part connects only to the root, the best position of part $i$ given a root location can be computed independently of the other parts. For each part we want, at every possible root position, the maximum over part positions of (part match at that position) minus (quadratic spring cost to reach it). That is precisely a generalized distance transform: a single operation that, given the part's match-score map, produces a new map giving the best achievable part-plus-spring score for each anchor location, in time linear in the number of pixels. Felzenszwalb and Huttenlocher's distance transform turns the inner search from quadratic to linear, and it is what made DPM inference fast enough to scan a pyramid. The pseudocode below assembles the score from the root response and the distance-transformed part responses.

# Score a deformable part model at every root position: add the coarse root
# response to each part's response after a generalized distance transform
# folds in the quadratic spring cost, so the part search stays linear-time.
import numpy as np
from scipy.ndimage import distance_transform_edt   # stand-in for the generalized DT

def dpm_score(hog_pyramid, root_filter, part_filters, anchors, spring):
    """Score a DPM at every root position using distance-transformed parts."""
    # Root response: correlate the root filter with coarse-level HOG features.
    root_resp = correlate_hog(hog_pyramid["coarse"], root_filter)
    total = root_resp.copy()

    for F_i, anchor, d_i in zip(part_filters, anchors, spring):
        # Part response at the fine level (twice root resolution).
        part_resp = correlate_hog(hog_pyramid["fine"], F_i)
        # Generalized distance transform: best part score minus quadratic
        # spring cost, evaluated for every anchor location, in O(pixels).
        dt = generalized_distance_transform(part_resp, d_i)
        # Shift the transformed part map to the part's anchor and add it in.
        total += shift_to_anchor(dt, anchor)

    return total   # one score per root position; threshold and run NMS

scores = dpm_score(hog_pyr, root, parts, anchors, springs)
print(f"peak DPM score: {scores.max():.3f}")
# peak DPM score: 1.27

The result map has one score per root placement; thresholding it and running the non-maximum suppression of Section 16.3 yields the final detections. Crucially, when a part lands away from its anchor, the recovered displacement tells you something semantic: a high-scoring detection whose leg parts spread wide is a walking person, whose arm part rose is a waving one. DPM does not just detect; it recovers a coarse pose for free, a property the bibliography's "DPMs are CNNs" paper later exploits.

4. Training With Latent Positions Advanced

Training a DPM faces a chicken-and-egg problem. The labels say only "there is a person in this box"; they do not say where the head part or the leg parts are. The part positions are latent: unknown during training, to be inferred. The fix is the latent SVM, which alternates two steps in the spirit of expectation-maximization (the standard recipe for fitting a model with hidden variables: guess the hidden values, refit the model, repeat, the same alternating loop that drives the k-means vocabulary of Section 16.2). First, with the filters fixed, infer the best part placement for each positive example (the latent step, using the Section 3 inference). Second, with those placements fixed, the problem becomes an ordinary SVM over the now-complete feature vectors, so update the root filter, part filters, and spring coefficients by maximum-margin training. Iterate.

Wrapped around that alternating loop is one more familiar step. Hard negative mining (Section 16.3 again) runs throughout, mining false positives from negative images and adding them to the training set, because detection's background-imbalance problem does not go away.

A single root filter still cannot cover a car seen from the front and the same car seen from the side; the gradient patterns are too different. DPM handles this with mixture components: several root-plus-parts models per object class, each specializing in a viewpoint or aspect (frontal car, side car, three-quarter car), with the detector taking the max over components. The component assignment is itself latent, inferred during training. With mixtures, latent parts, and hard negatives, the full DPM was the detector to beat for half a decade.

5. The Bridge to Convolutional Networks Intermediate

DPM is where hand-crafted recognition got as expressive as it ever would, and it is also where the bridge to deep learning is most visible. In 2015 Girshick and colleagues showed that DPM inference can be rewritten exactly as a convolutional neural network: the filter correlations are convolution layers, the max over part positions is a form of max pooling, and the distance transform is a special pooling layer. A trained DPM is a CNN with a particular, hand-designed architecture. The difference is that the DPM's structure (how many parts, where the anchors sit, the spring form) was designed by humans and only the filter weights were learned, whereas a CNN learns the structure too, from data, with many more layers. Figure 16.5.2 lines up the correspondence stage by stage, the clearest single picture of why deep learning subsumed rather than replaced the classical pipeline.

# DPM's modern successor in three lines: a pretrained YOLO detector that
# learned the part structure, deformation tolerance, and viewpoint mixtures
# DPM encoded by hand, returning boxes, classes, and scores in one call.
from ultralytics import YOLO
model = YOLO("yolo11n.pt")             # pretrained detector, learned end to end
results = model("street.jpg")           # boxes, classes, scores in one call
# The backbone learns parts, deformation, and viewpoint mixtures implicitly.