Deformable Part Models

Deformable part models (DPMs) are the object detectors built by Pedro Felzenszwalb, David McAllester, Deva Ramanan and Ross Girshick between 2007, when a preliminary version was entered in the PASCAL VOC challenge, and 2012. Each object class is a mixture of a few star-shaped models. Every component has a coarse root filter that covers the whole object, like the single template of Dalal and Triggs’s pedestrian detector, plus a handful of part filters at twice the spatial resolution, each of which may move away from its expected position at a quadratic cost. All filters are linear templates on a pyramid of histogram of oriented gradients (HOG) features, scanned over every position and scale as in sliding window detection. The best placement of every part for every root position is found exactly with generalized distance transforms, and the model is trained from bounding boxes alone with a latent SVM, which treats the part positions, the precise root position and the mixture component as hidden variables. The model was introduced in the CVPR 2008 paper “A Discriminatively Trained, Multiscale, Deformable Part Model” by Felzenszwalb, McAllester and Ramanan, and described in full, with mixtures, in the 2010 TPAMI paper by Felzenszwalb, Girshick, McAllester and Ramanan; the authors’ code went through five public releases.

Problem Addressed

A single HOG template scores a window as a rigid layout of oriented edges, so an object whose parts move, such as a person with a raised arm, a horse with a turned head or a cyclist doing a wheelie, matches poorly unless the template is blurred to tolerate every pose. Part-based models had long offered a way out. In the pictorial structures of Fischler and Elschlager (1973), which Felzenszwalb and Huttenlocher (2005) turned into an efficient statistical framework, an object is a set of parts, each with its own appearance model, connected by spring-like deformation costs. The TPAMI paper states the gap plainly: such models were popular but had not shown their value on difficult benchmarks such as PASCAL VOC, where simpler rigid templates and bag-of-features models often outperformed them.

Two difficulties stood in the way. Matching a model with many parts looks like a search over an exponential number of configurations at every position and scale. And PASCAL labels give only a box per object, so the part positions, and even which sub-type of the object a box shows, are unknown during training. DPMs solved the first with dynamic programming and distance transforms on a star-shaped model, and the second with discriminative training that treats the missing labels as latent variables.

Architecture

A DPM scores root locations in a HOG feature pyramid. Each level of an image pyramid, obtained by repeated smoothing and subsampling, is turned into a feature map: an array with one $d$-dimensional feature vector per $8 \times 8$-pixel cell. The scale step is set by $\lambda$, the number of levels per octave, so neighbouring levels differ by a factor $2^{1/\lambda}$; the TPAMI paper used $\lambda = 5$ for training and $\lambda = 10$ for testing and found fine scale sampling important. The features are the 31-dimensional HOG variant described in the HOG article; the 2008 paper had used 36-dimensional HOG features.

A filter $F$ is a $w \times h$ array of $d$-dimensional weight vectors. Its score at position $p = (x, y, l)$, the top-left cell of a window in level $l$, is a dot product with the window’s features,

$$F' \cdot \phi(H, p),$$

where $\phi(H, p)$ concatenates the feature vectors of the $w \times h$ window of the pyramid $H$ and $F'$ concatenates the weights in the same order. Over a whole level, these scores are a cross-correlation of the filter with the feature map.

Root filter

The root filter approximately covers the object and defines the detection window: the pixels that contribute to the cells it covers. On its own, a root filter is the Dalal–Triggs detector. Its dimensions are chosen per component from the training boxes (see Training).

Part filters and deformation costs

A model with $n$ parts is the tuple $(F_0, P_1, \dots, P_n, b)$: a root filter $F_0$, part models $P_i = (F_i, v_i, d_i)$ and a bias $b$. Part filter $F_i$ is applied $\lambda$ levels below the root, at twice the root’s spatial resolution; $v_i$ is the part’s anchor, its ideal position relative to the root, and $d_i \in \mathbb{R}^4$ holds the coefficients of a quadratic deformation cost. A hypothesis $z = (p_0, \dots, p_n)$ places every filter, with $l_i = l_0 - \lambda$ for the parts, and scores

$$\operatorname{score}(p_0, \dots, p_n) = \sum_{i=0}^{n} F_i' \cdot \phi(H, p_i) \;-\; \sum_{i=1}^{n} d_i \cdot \phi_d(dx_i, dy_i) \;+\; b,$$ $$(dx_i, dy_i) = (x_i, y_i) - \big(2(x_0, y_0) + v_i\big), \qquad \phi_d(dx, dy) = (dx,\, dy,\, dx^2,\, dy^2).$$

The factor 2 converts root coordinates to the finer part level. With $d_i = (0, 0, 1, 1)$ the cost is the squared distance from the anchor; in general it is any separable quadratic in the displacement, and the linear terms let the cheapest position sit off the anchor. The bias makes the scores of different mixture components comparable.

The authors found the finer part resolution essential: parts at twice the resolution capture smaller structures and localize them more precisely, while the root captures the coarse outline. The parts interact only through the root, giving a star-structured pictorial structure; the TPAMI paper notes that it does not model interactions between overlapping parts.

The score is linear in the model parameters. Writing

$$\beta = (F_0', \dots, F_n', d_1, \dots, d_n, b), \qquad \psi(H, z) = \big(\phi(H, p_0), \dots, \phi(H, p_n), -\phi_d(dx_1, dy_1), \dots, -\phi_d(dx_n, dy_n), 1\big),$$

the score of $z$ is $\beta \cdot \psi(H, z)$, a linear classifier on a feature vector that depends on the hidden placement $z$. This is what lets the model be trained as a latent SVM.

Mixture components

One star model covers one aspect: side and frontal views of a car, or the many shapes of bicycles, differ too much for one root to deform between them. A mixture of $m$ components $(M_1, \dots, M_m)$ scores a location by the best component, and a hypothesis now includes the component label $c$. In the parameter vector, the components’ $\beta_c$ are concatenated and $\psi(H, z)$ is zero outside the block of the chosen component, so $\beta \cdot \psi(H, z) = \beta_c \cdot \psi(H, z')$. The TPAMI system used two components per class, each symmetric about its vertical axis. From release 4 on, each class had three asymmetric components, each also matched in mirrored form, so six in effect (see Variants).

Ancestry: pictorial structures

Felzenszwalb and Huttenlocher (2005) define a pictorial structure match as the configuration $L = (l_1, \dots, l_n)$ that minimizes

$$\sum_{i=1}^{n} m_i(l_i) + \sum_{(v_i, v_j) \in E} d_{ij}(l_i, l_j),$$

with $m_i$ the mismatch of part $i$ at location $l_i$ and $d_{ij}$ the deformation of the spring between connected parts. For a tree of connections, dynamic programming finds the global minimum in $O(h^2 n)$ time for $h$ locations per part; when each $d_{ij}$ is a Mahalanobis distance between transformed locations with a diagonal matrix, distance transforms make the cost essentially linear in $h$. They also showed that the same energy is the negative log of a posterior under a tree-structured Markov random field. A DPM keeps the star tree and the quadratic springs, replaces the generative appearance models with HOG filters and maximizes a learned score instead of minimizing an energy; the deformation cost is the spring, with its stiffness learned.

Training

Training needs only images with class-labelled boxes, and negative images that do not contain the class.

The latent SVM

A latent SVM scores an example $x$ by maximizing over the latent values $Z(x)$, here the placements (and component) of the model:

$$f_\beta(x) = \max_{z \in Z(x)} \beta \cdot \Phi(x, z),$$

and is trained with the SVM objective

$$L_D(\beta) = \frac{1}{2} \lVert \beta \rVert^2 + C \sum_{i=1}^{N} \max\big(0,\, 1 - y_i f_\beta(x_i)\big), \qquad y_i \in \{-1, 1\}.$$

A positive example is a labelled box, and $Z(x)$ contains the root placements whose detection window overlaps the box by at least 50%, at any scale; the authors found that letting the detector choose the exact window helps with noisy box labels. Every root location in a negative image is a separate negative example.

$f_\beta$ is a maximum of linear functions, so it is convex in $\beta$, and the hinge loss of a negative example, $\max(0, 1 + f_\beta(x))$, is convex. The loss of a positive example is not. The authors call this property of the loss semi-convexity; it means that once the latent value of every positive is fixed, the objective becomes convex. Training is a coordinate descent on $L_D(\beta, Z_p)$, which bounds $L_D(\beta)$ from above:

1. Relabel positives. With $\beta$ fixed, choose the highest-scoring latent value for each positive: the best window, component and part placement.
2. Optimize $\beta$. With those values fixed, solve the convex problem; negatives still maximize over all their latent values.

Neither step can raise the auxiliary objective. The paper points out that fixing the negatives’ latent values too would be a mistake: $L_D(\beta)$ maximizes over them, so a model trained with them fixed could score badly under the true objective. A latent SVM is a reformulation of the MI-SVM approach to multiple-instance learning, and differs from a hidden CRF by maximizing rather than marginalizing over latent values and using the hinge loss. The TPAMI system solved step 2 by stochastic subgradient descent; the 2008 system had used SVMLight on a heuristic approximation of the objective, and release 5 replaced the subgradient solver with L-BFGS.

Data-mining hard negatives

A single negative image gives on the order of $10^5$ windows, so not all negatives can be held at once. The common remedy, described in sliding window detection, is bootstrapping: train, collect the negatives the model gets wrong, retrain. The DPM papers make it exact for SVM training by defining hard and easy examples relative to the margin,

$$H(\beta, D) = \{\langle x, y \rangle \in D \mid y f_\beta(x) < 1\}, \qquad E(\beta, D) = \{\langle x, y \rangle \in D \mid y f_\beta(x) > 1\}.$$

Starting from a cache $C_1 \subseteq D$, the TPAMI algorithm trains $\beta_t = \beta^*(C_t)$; stops if every hard example of the full set is already in the cache; otherwise removes some easy examples and adds new hard ones, at least one. Two theorems show that the stopping model equals $\beta^*(D)$, the model trained on all of $D$, and that the loop terminates; the 2008 paper stated related theorems without proofs. For the latent SVM the cache holds feature vectors $\Phi(x, z)$ rather than examples, so several placements of the same negative can be cached, and the guarantee holds for the convex step with the positives’ latent values fixed.

In the implementation, the outer loop runs a fixed number of relabelling rounds and the inner loop a fixed number of mining rounds. Each mining round scans negative images until a memory limit is reached, keeping every detection that scores above $-(1 + \delta)$, retrains, then drops the cached vectors that score below $-(1 + \delta)$. The paper also constrains the quadratic deformation coefficients to be at least 0.01, so costs stay convex and not too flat, and makes each model left–right symmetric, which halves the parameters.

Initialization

Coordinate descent finds a local optimum, so the TPAMI system initializes in three phases:

1. Root filters. Sort the positive boxes by aspect ratio and split them into $m$ equal groups. For each group, pick the mean aspect ratio and the largest area not larger than 80% of the boxes, and train a root filter with a standard SVM on warped positives and random negative windows, as Dalal and Triggs did.
2. Merging components. Combine the roots into one mixture without parts and train it with latent SVM on the unwarped data; the component label and root position are the latent variables. The authors describe this as a discriminative clustering that alternates between assigning examples to components and estimating each component’s filter.
3. Parts. Place six parts per component greedily over the regions of the root filter with the most positive weight, using a small pool of rectangular shapes, centred or in symmetric pairs; initialize each part filter by interpolating the root filter to twice the resolution, and its deformation to $d_i = (0, 0, 0.1, 0.1)$. Then train the full model.

The paper reports about 4 hours to train a model on PASCAL VOC 2007 trainval on an 8-core desktop.

Inference

Matching with distance transforms

For each root location, the best placement of each part can be chosen independently, because parts interact only through the root. Let $R_{i,l}(x, y) = F_i' \cdot \phi(H, (x, y, l))$ be the response of filter $i$ in level $l$. Each part response is transformed to allow for spatial uncertainty,

$$D_{i,l}(x, y) = \max_{dx,\, dy} \Big( R_{i,l}(x + dx,\, y + dy) - d_i \cdot \phi_d(dx, dy) \Big),$$

so that $D_{i,l}(x, y)$ is the largest contribution part $i$ can make when its anchor falls at $(x, y)$. The score of every root location is then a sum of shifted arrays,

$$\operatorname{score}(x_0, y_0, l_0) = R_{0,l_0}(x_0, y_0) + \sum_{i=1}^{n} D_{i,\, l_0 - \lambda}\big(2(x_0, y_0) + v_i\big) + b,$$

and a mixture takes the maximum over components. The same computation records, for every anchor position, the displacement that achieved the maximum, so the part positions of a detection are a table lookup. The whole matching costs $O(nk)$ once the filter responses are known, for $n$ parts and $k$ positions in the pyramid. High-scoring root locations are the detections, one per location at most, which makes the DPM a sliding-window detector whose window score includes the best part configuration.

$D_{i,l}$ is a generalized distance transform, in the terminology of Felzenszwalb and Huttenlocher. For a function $f$ on a grid, they define

$$\mathcal{D}_f(p) = \min_{q} \big( d(p, q) + f(q) \big),$$

which reduces to the classical distance transform of a binary image when $f$ is 0 on the feature points and $\infty$ elsewhere. It is a min-convolution of $f$ with the distance function. For the squared distance in one dimension, $\mathcal{D}_f$ is the lower envelope of $n$ parabolas $(p - q)^2 + f(q)$ rooted at the grid points. Since all have the same shape and arrive in order of their vertices, the envelope can be built left to right in $O(n)$ time: the parabolas from $q < r$ intersect at

$$s = \frac{\big(f(r) + r^2\big) - \big(f(q) + q^2\big)}{2r - 2q},$$

and each new parabola deletes the envelope parabolas it covers before being appended, each parabola being added and deleted at most once. A separable cost in two dimensions is one 1-D pass along every column followed by one along every row, $O(N)$ for $N$ grid points in all. The DPM’s transform is the same computation applied to $-R$ with a general separable quadratic. In our reading, the max form is also a grayscale dilation of the response map by a quadratic structuring function, with the learned $d_i$ setting its shape. One implementation detail: the dt.cc routine in the voc-release5 code uses a simpler $O(n \log n)$ divide-and-conquer method rather than the linear one, as a comment in the source says.

The 1-D algorithm below follows Felzenszwalb and Huttenlocher’s pseudocode, with the deformation weights $(a, b)$ of a DPM part in place of the unit parabola, and is checked against brute-force maximization over every displacement on a random $40 \times 60$ response map.

import numpy as np

def dt1d(f, a, b):
    """Generalized distance transform of a 1-D array, in the max form used by DPM:
         D[p] = max_q  f[q] - a*(q - p)**2 - b*(q - p),   a > 0,
    with q - p the part's displacement from its anchor p. Computed as the upper
    envelope of n parabolas (Felzenszwalb & Huttenlocher's lower-envelope algorithm
    applied to -f), in O(n). Returns D and the maximizing q for every p."""
    n = len(f)
    g = -np.asarray(f, float)                 # minimize g[q] + a*(p-q)**2 - b*(p-q)
    h = g + a * np.arange(n) ** 2 + b * np.arange(n)   # parabola "heights" for intersections
    v = np.zeros(n, int)                      # grid positions of parabolas in the envelope
    z = np.full(n + 1, np.inf); z[0] = -np.inf  # boundaries between envelope parabolas
    k = 0
    for q in range(1, n):
        s = (h[q] - h[v[k]]) / (2 * a * (q - v[k]))   # where parabola q overtakes v[k]
        while s <= z[k]:
            k -= 1
            s = (h[q] - h[v[k]]) / (2 * a * (q - v[k]))
        k += 1
        v[k], z[k], z[k + 1] = q, s, np.inf
    D, arg = np.empty(n), np.empty(n, int)
    k = 0
    for p in range(n):                        # read the envelope off at every grid point
        while z[k + 1] < p:
            k += 1
        q = v[k]
        D[p], arg[p] = f[q] - a * (q - p) ** 2 - b * (q - p), q
    return D, arg

def dt2d(R, ax, bx, ay, by):
    """Separable 2-D transform: columns (y) first, then rows (x).
    Returns D and, for every anchor (y, x), the best part position (qy, qx)."""
    H, W = R.shape
    tmp, iy = np.empty((H, W)), np.empty((H, W), int)
    for x in range(W):
        tmp[:, x], iy[:, x] = dt1d(R[:, x], ay, by)
    D, ix = np.empty((H, W)), np.empty((H, W), int)
    for y in range(H):
        D[y], ix[y] = dt1d(tmp[y], ax, bx)
    qy = iy[np.arange(H)[:, None], ix]        # row of the best position, in the best column
    return D, qy, ix

def dt2d_brute(R, ax, bx, ay, by):
    """Same quantity by trying every displacement: O((HW)^2)."""
    H, W = R.shape
    Y, X = np.mgrid[0:H, 0:W]
    D, qy, qx = np.empty((H, W)), np.empty((H, W), int), np.empty((H, W), int)
    for y in range(H):
        for x in range(W):
            dy, dx = Y - y, X - x
            val = R - ax * dx**2 - bx * dx - ay * dy**2 - by * dy
            i = np.argmax(val)
            D[y, x], qy[y, x], qx[y, x] = val.flat[i], Y.flat[i], X.flat[i]
    return D, qy, qx

rng = np.random.default_rng(0)
R = rng.standard_normal((40, 60))             # a stand-in part-filter response map
for ax, bx, ay, by in [(0.1, 0.0, 0.1, 0.0), (0.05, 0.3, 0.2, -0.1), (2.0, 0.0, 2.0, 0.0)]:
    D, qy, qx = dt2d(R, ax, bx, ay, by)
    Db, qyb, qxb = dt2d_brute(R, ax, bx, ay, by)
    moved = np.mean((qy != np.arange(40)[:, None]) | (qx != np.arange(60)[None, :]))
    print(f"a=({ax}, {ay}) b=({bx}, {by}): max |fast - brute| = {np.abs(D - Db).max():.1e}, "
          f"same argmax {np.mean((qy == qyb) & (qx == qxb)):.0%}, anchors whose best part moved {moved:.0%}")

Output:

a=(0.1, 0.1) b=(0.0, 0.0): max |fast - brute| = 2.2e-16, same argmax 100%, anchors whose best part moved 92%
a=(0.05, 0.2) b=(0.3, -0.1): max |fast - brute| = 8.9e-16, same argmax 100%, anchors whose best part moved 97%
a=(2.0, 2.0) b=(0.0, 0.0): max |fast - brute| = 0.0e+00, same argmax 100%, anchors whose best part moved 21%

The linear-time transform agrees with the brute force to rounding error, and returns the same best displacement for every anchor, including with unequal weights per axis and nonzero linear terms that move the cheapest position off the anchor. The last column shows what the weights do: soft costs let almost every anchor borrow a better response from somewhere nearby, while stiff costs ($a = 2$, where one cell of displacement costs 2 standard deviations of the response) keep most parts at their anchors. The brute force costs $O(N^2)$ for $N$ positions against $O(N)$ for the transform.

Example: rigid versus deformable templates

The second block continues from the first. It renders stick figures 96 pixels tall in $256 \times 384$ scenes with intensities in $[0, 1]$, over clutter made of smooth texture, 60 random bars and 40 loose heads and limbs scattered as decoys. Each figure’s head, arms and legs slide independently by up to $\pm A$ pixels relative to its torso. Features are a toy version of HOG: four unsigned orientation channels of gradient magnitude per cell, L2-normalized with a regularizing constant, on 8-pixel cells for the root and 4-pixel cells for the parts, so the parts sit at twice the root’s resolution. Instead of latent SVM training, the root and the five part filters are cut from the feature maps of one undeformed figure and made zero-mean and unit-norm. Four detectors share these filters: the root alone; root plus rigid parts, fixed at their anchors; root plus parts free to move within $\pm 3$ fine cells at no cost; and the DPM score with deformation cost $d_i = (0, 0, a, a)$, $a = 0.05$ per squared fine cell, computed with dt2d. The script runs at one pyramid level, with figures placed on the 8-pixel grid, so the comparison isolates deformation from scale and alignment. For each scene it computes the average precision of ranking the six true root positions above all root positions whose windows do not overlap a figure, over seeds 0 to 9.

from scipy import ndimage

WH, WW = 96, 48                     # figure window: 96 rows x 48 columns of pixels
FINE, COARSE = 4, 8                 # part filters on 4-px cells, root filter on 8-px cells
TORSO = [(22, 24, 56, 24)]          # segments (r0, c0, r1, c1) in window coordinates
PARTS = {  # segments of each part, and the part filter's box (r0, r1, c0, c1) in pixels
    "head":      ([(14, 24, 14, 24)], (4, 24, 16, 32)),
    "left arm":  ([(26, 24, 46, 10)], (24, 48, 4, 28)),
    "right arm": ([(26, 24, 46, 38)], (24, 48, 20, 44)),
    "left leg":  ([(56, 24, 88, 14)], (52, 92, 8, 32)),
    "right leg": ([(56, 24, 88, 34)], (52, 92, 16, 40)),
}

def draw(img, segs, r, c, width, value=0.1):
    """Paint anti-aliased thick segments, offset by (r, c), with one intensity."""
    rr, cc = np.mgrid[0:img.shape[0], 0:img.shape[1]].astype(float)
    for r0, c0, r1, c1 in segs:
        d = np.array([r1 - r0, c1 - c0], float)
        t = np.clip(((rr - r - r0) * d[0] + (cc - c - c0) * d[1]) / max(d @ d, 1e-9), 0, 1)
        dist = np.hypot(rr - r - r0 - t * d[0], cc - c - c0 - t * d[1])
        cover = np.clip(width / 2 - dist + 0.5, 0, 1)
        img[:] = img * (1 - cover) + value * cover

def figure(img, r, c, shifts):
    """Stick figure with its window's top-left at (r, c); each part slides by shifts[p]."""
    draw(img, TORSO, r, c, 4)
    for p, (segs, _) in PARTS.items():
        dr, dc = shifts[p]
        draw(img, segs, r + dr, c + dc, 14 if p == "head" else 4)

def clutter(rng, H, W, n_bars=60, n_debris=40):
    """Smooth texture, random bars, and loose figure parts (heads and limbs) as decoys."""
    img = 0.5 + 1.5 * ndimage.gaussian_filter(rng.standard_normal((H, W)), 6)
    for _ in range(n_bars):         # random bars of random intensity and width
        r0, c0, a, L = rng.uniform(0, H), rng.uniform(0, W), rng.uniform(0, np.pi), rng.uniform(8, 40)
        draw(img, [(r0, c0, r0 + L * np.sin(a), c0 + L * np.cos(a))], 0, 0, rng.uniform(2, 5),
             rng.uniform(0.1, 0.9))
    names = list(PARTS)
    for _ in range(n_debris):       # a random part, dropped at a random place
        p = names[rng.integers(len(names))]
        draw(img, PARTS[p][0], rng.uniform(-40, H), rng.uniform(-40, W), 14 if p == "head" else 4)
    return np.clip(img, 0, 1)

def features(img, cell):
    """Toy oriented-gradient cells (see the HOG article for the real descriptor):
    4 unsigned orientation channels of gradient magnitude, summed per cell, L2-normalized."""
    gr, gc = np.zeros_like(img), np.zeros_like(img)
    gr[1:-1] = img[2:] - img[:-2]; gc[:, 1:-1] = img[:, 2:] - img[:, :-2]
    mag, ang = np.hypot(gr, gc), np.arctan2(gr, gc) % np.pi
    b = np.minimum((ang / (np.pi / 4)).astype(int), 3)
    H, W = img.shape[0] // cell, img.shape[1] // cell
    f = np.zeros((H, W, 4))
    rows, cols = np.mgrid[0:H * cell, 0:W * cell]
    np.add.at(f, (rows // cell, cols // cell, b[:H * cell, :W * cell]), mag[:H * cell, :W * cell])
    return f / np.sqrt((f**2).sum(2, keepdims=True) + 1.0)

def correlate(fmap, filt):
    """Filter response at every top-left position (valid cross-correlation, summed over channels)."""
    win = np.lib.stride_tricks.sliding_window_view(fmap, filt.shape[:2], axis=(0, 1))
    return np.einsum("yxcij,ijc->yx", win, filt)

# Filters cut from the feature maps of one undeformed figure on a flat background,
# made zero-mean and unit-norm (a stand-in for latent SVM training).
proto = np.full((WH, WW), 0.5); figure(proto, 0, 0, {p: (0, 0) for p in PARTS})
unit = lambda w: (w - w.mean()) / np.linalg.norm(w - w.mean())
root = unit(features(proto, COARSE))                    # 12 x 6 cells
fine = features(proto, FINE)                            # 24 x 12 cells
part_filters, anchors = {}, {}
for p, (_, (r0, r1, c0, c1)) in PARTS.items():
    part_filters[p] = unit(fine[r0 // FINE:r1 // FINE, c0 // FINE:c1 // FINE])
    anchors[p] = (r0 // FINE, c0 // FINE)               # v_i, in fine cells from 2 x root position

def score_map(img, mode, a=0.05):
    """Score of every root position (coarse cells). mode: root only, rigid parts,
    quadratic deformation costs (DPM), or free parts within +-3 cells and no cost."""
    S = correlate(features(img, COARSE), root)
    if mode == "root":
        return S, None
    F, best = features(img, FINE), {}
    ys, xs = np.mgrid[0:S.shape[0], 0:S.shape[1]]
    for p, filt in part_filters.items():
        Rp = correlate(F, filt)
        if mode == "rigid":
            D = Rp
        elif mode == "DPM":
            D, qy, qx = dt2d(Rp, a, 0.0, a, 0.0)       # d_i = (0, 0, a, a)
        else:  # "free": max over a 7 x 7 cell window, i.e. no deformation cost
            D = ndimage.maximum_filter(Rp, size=7, mode="constant", cval=-np.inf)
        S = S + D[2 * ys + anchors[p][0], 2 * xs + anchors[p][1]]   # anchor 2*(x0, y0) + v_i
        if mode == "DPM":
            best[p] = (qy, qx)
    return S, best

def scene(seed, amp, n_fig=6, H=256, W=384):
    """Clutter plus n_fig figures on the 8-px grid; each part slides by up to +-amp px."""
    rng = np.random.default_rng(seed)
    img = clutter(rng, H, W)
    slots = rng.choice(12, n_fig, replace=False)     # 2 rows x 6 columns of slots
    figs = []
    for s in slots:
        r, c = 8 * ((s // 6) * 16 + rng.integers(0, 2)), 8 * ((s % 6) * 7 + rng.integers(0, 2))
        shifts = {p: tuple(rng.integers(-amp, amp + 1, 2)) for p in PARTS}
        figure(img, r, c, shifts)
        figs.append((r // COARSE, c // COARSE, shifts))
    return img, figs

def ranking_ap(S, figs):
    """Average precision of ranking the figures' windows above every root position
    whose window does not overlap a figure (no NMS, no IoU matching: a pure ranking score)."""
    ys, xs = np.mgrid[0:S.shape[0], 0:S.shape[1]]
    near = np.zeros(S.shape, bool)
    for y, x, _ in figs:
        near |= (np.abs(ys - y) < WH // COARSE) & (np.abs(xs - x) < WW // COARSE)
    neg = S[~near]
    pos = np.sort([S[y, x] for y, x, _ in figs])[::-1]
    return np.mean([(i + 1) / (i + 1 + np.sum(neg >= s)) for i, s in enumerate(pos)])

modes, amps, seeds = ["root", "rigid", "free", "DPM"], [0, 8, 12, 16], range(10)
print("ranking AP, mean (min-max) over scenes with seeds 0-9, 6 figures per scene")
print("part shift" + "".join(f"{m:>18s}" for m in modes))
errs = []
for amp in amps:
    res = {m: [] for m in modes}
    for seed in seeds:
        img, figs = scene(seed, amp)
        for m in modes:
            S, best = score_map(img, m)
            res[m].append(ranking_ap(S, figs))
            if m == "DPM" and amp == 8:   # where did each part end up, versus its true shift?
                for y, x, shifts in figs:
                    for p in PARTS:
                        qy, qx = best[p]
                        ay, ax = 2 * y + anchors[p][0], 2 * x + anchors[p][1]
                        found = np.array([qy[ay, ax] - ay, qx[ay, ax] - ax]) * FINE
                        errs.append(np.abs(found - np.array(shifts[p])).max())
    print(f"+-{amp:2d} px  " + "".join(
        f"{np.mean(res[m]):.2f} ({min(res[m]):.2f}-{max(res[m]):.2f})".rjust(18) for m in modes))
errs = np.array(errs)
print(f"DPM at +-8 px: recovered part shift within one fine cell (4 px) for {np.mean(errs <= 4):.0%} "
      f"of {errs.size} parts, median error {np.median(errs):.0f} px")
for amp in (12, 16):               # the deformation weight: from nearly free to nearly rigid
    scenes = [scene(seed, amp) for seed in seeds]
    row = {a: np.mean([ranking_ap(score_map(img, "DPM", a)[0], figs) for img, figs in scenes])
           for a in (0.005, 0.05, 0.5)}
    print(f"DPM at +-{amp} px, mean AP for a = " + ", ".join(f"{a}: {v:.2f}" for a, v in row.items()))

Output:

ranking AP, mean (min-max) over scenes with seeds 0-9, 6 figures per scene
part shift              root             rigid              free               DPM
+- 0 px    1.00 (1.00-1.00)  1.00 (1.00-1.00)  1.00 (1.00-1.00)  1.00 (1.00-1.00)
+- 8 px    0.95 (0.84-1.00)  0.89 (0.71-1.00)  0.97 (0.85-1.00)  0.99 (0.86-1.00)
+-12 px    0.74 (0.54-0.98)  0.59 (0.32-0.89)  0.90 (0.52-1.00)  0.92 (0.66-1.00)
+-16 px    0.52 (0.23-0.95)  0.48 (0.18-1.00)  0.79 (0.27-1.00)  0.80 (0.36-1.00)
DPM at +-8 px: recovered part shift within one fine cell (4 px) for 70% of 300 parts, median error 2 px
DPM at +-12 px, mean AP for a = 0.005: 0.85, 0.05: 0.92, 0.5: 0.78
DPM at +-16 px, mean AP for a = 0.005: 0.70, 0.05: 0.80, 0.5: 0.56

With undeformed figures every detector ranks all of them first, so the clutter alone does not fool the templates. As the parts move, the rigid detectors lose them: the root alone falls to a mean AP of 0.52 at $\pm 16$ pixels. Adding rigid parts makes things worse, not better, presumably because the fine-resolution parts are more sensitive to displacement than the coarse root, so a displaced part adds misplaced evidence. Letting the same parts move restores most of the loss. The quadratic cost does at least as well on average as a hard window with no cost, though the differences are small, and its worst scene is better at $\pm 12$ and $\pm 16$ pixels (0.66 against 0.52, and 0.36 against 0.27). The weight sweep shows that both extremes lose. With $a = 0.005$ a part can reach far at almost no cost; our reading is that it then collects decoy responses at background positions and raises their scores. With $a = 0.5$ every cell of displacement is expensive, and the parts behave almost as if rigid. The spread over seeds is wide, which we attribute to each scene having only six positives. The part positions come for free from the argmax tables: at $\pm 8$ pixels, 70% of parts are located within one fine cell of their true shift. In a real DPM the deformation weights, like the filters, are learned, which this example does not attempt; $a = 0.05$ is the best of the three values in the sweep, so the DPM column is tuned on the same scenes it is scored on.

Post-processing

Three steps follow matching in the TPAMI system.

• Bounding-box prediction. The box from the root alone ignores the better-localized parts. For each component, four linear functions map a $2n + 3$-dimensional vector, the root width in pixels (for scale) and the top-left corner of every filter, to the box corners $(x_1, y_1, x_2, y_2)$, fitted by least squares on the detector’s outputs for the training objects. The paper calls the gains small but noticeable for some classes.
• Non-maximum suppression. Detections are sorted by score and accepted greedily, skipping any whose box is at least 50% covered by an already accepted box; the non-maximum suppression article compares this overlap measure with IoU.
• Context rescoring. With detectors for $k$ classes run on an image, each detection gets a new score from a class-specific SVM with a quadratic kernel on the 25-dimensional vector (for $k = 20$)

$$g = \big(\sigma(s),\, x_1,\, y_1,\, x_2,\, y_2,\, c(I)\big), \qquad c(I) = \big(\sigma(s_1), \dots, \sigma(s_k)\big), \qquad \sigma(x) = \frac{1}{1 + e^{-2x}},$$

where $s$ is the detection’s own score, the box coordinates are normalized to $[0, 1]$ by the image size, and $s_j$ is the best score of class $j$’s detector anywhere in the image. The rescoring classifiers were trained on the same data as the models.

The TPAMI paper reports about 3 hours to evaluate a model on the 4,952 VOC 2007 test images, roughly 2 seconds per image, on a 2.8 GHz 8-core Mac Pro that computed filter responses in parallel.

The star cascade

Felzenszwalb, Girshick and McAllester (CVPR 2010) observed that the bottleneck of matching is evaluating the filters’ appearance models at every location, while only root locations with a final score above a threshold $T$ matter. Their star-cascade orders the parts and evaluates a root location in stages: after adding part $i$, a hypothesis whose partial score is below a threshold $t_i$ is pruned, and within each stage a displacement $\delta$ is skipped if the partial score minus its deformation cost falls below a second threshold $t_i'$. Filter responses are computed lazily and memoized, because neighbouring root locations ask for the same part positions. With admissible thresholds the cascade returns exactly the detections of the full algorithm; in practice the thresholds are set to the smallest partial scores observed on $m$ positive examples. Calling thresholds $(\epsilon, \delta)$ probably approximately admissible when, with probability at least $1 - \delta$, they wrongly prune at most a fraction $\epsilon$ of high-scoring positive examples, they proved that

$$m \ge \frac{2n}{\epsilon} \ln \frac{2n}{\delta}$$

samples suffice for a model with $n$ non-root parts. A second hierarchy first runs every part with a cheap appearance model, the projection of the 31-dimensional features and filters onto the top 5 principal components, about 6 times faster to evaluate, and only then replaces each with the full filter.

On the 20 VOC 2007 classes, with the six-component models of the UoC-TTI entry in the 2009 challenge, and on INRIA person with a one-component model, the cascade was 22.0 times faster than the baseline on average over these 21 test sets, single-threaded and excluding feature computation, with the global threshold set where precision equals recall, and 14.3 times faster with the threshold set to reach precision 0.05, at essentially unchanged AP. Without the PCA filters the mean speedup at the first setting fell to 8.7. Computing the feature pyramid took 459 ms per image on PASCAL, a cost the cascade does not reduce.

Performance

Results below are average precision, as printed by the authors; the PASCAL VOC results follow the comp3 protocol, training on the year’s own trainval data.

TPAMI paper (two components, six parts each). Tables 1 to 3 give per-class AP on VOC 2006, 2007 and 2008 for the base system, with bounding-box prediction, and with both bounding-box prediction and context. Averaged over the 20 VOC 2007 classes (the paper prints no mean; the averages are ours), these are 26.3%, 26.8% and 29.1%. On VOC 2008 the system had the best AP among that year’s competition entries in 9 of the 20 classes and the second best in 8, with the entry of a preliminary version of the system excluded from the ranking. Context helped some classes markedly (cat from 16.3% to 21.3% on VOC 2007) and hurt a few (table on VOC 2008 from 12.4% to 8.7%). On the INRIA person dataset, scored with the PASCAL development kit on the full test set, a one-component model reached AP 0.869. The paper attributes the 20 highest-scoring false positives for cats to the cat-face component, whose boxes are too small for the overlap criterion.

Ablation on VOC 2006 (TPAMI Figure 8). For persons, AP rose from 0.24 with one or two root-only components to 0.38 with one component with parts, and 0.39 with two components, parts and box prediction; for cars it rose from 0.48 (one root) to 0.58 (two roots), 0.62 (two components with parts) and 0.64 with box prediction. Mixtures mattered for cars but not for persons.

Across releases (VOC 2007 test). The release pages report each version’s models on the same test set:

Version	Model	Without context	With context
CVPR 2008 paper	1 component, 6 parts	21.3 (our average of Table 1)	—
voc-release2 (2008 VOC entry)	mixture model	26.5 (our average)	28.4 (our average)
voc-release3 (TPAMI system)	2 components, 6 parts	26.8 (our average)	29.1 (our average)
voc-release4	3 × 2 mirrored components, 8 parts	32.3	34.1
voc-release5	as release 4, retrained	33.7	35.4

The release-3 rows are identical, class by class, to the TPAMI paper’s VOC 2007 Table 2 rows with box prediction and with context. Release 5 also reports 29.6% on VOC 2010 test without context, 32.2% with context and 33.4% with context and an extra octave of features, and 88.0 AP on INRIA person. The 33.7% and 33.4% figures are the DPM v5 results that the R-CNN paper compared against.

The PASCAL organizers’ retrospective calls the DPM the reference method for detection in VOC 2008–2012 and records teams led by Felzenszwalb as joint winners of the detection challenge in 2008 and 2009 (Everingham et al., 2015). At the VOC 2010 workshop the organizers awarded a “lifetime achievement” prize to Felzenszwalb, Girshick, McAllester and Ramanan for the method, known to participants as the UoCTTI detector, which the workshop page says was first submitted in 2007 and had become a core component of many other submissions.

Strengths

• Exact inference over all configurations. Distance transforms give the best part placement for every root location at a cost linear in the number of positions, so the deformable model costs about as much as scanning its filters.
• Weak supervision. Only boxes are needed; part positions, the exact window and the component are discovered by the latent SVM.
• Coarse-to-fine appearance. The root sees the overall shape, the parts see details at twice the resolution, and the deformation costs say how far details may stray.
• Interpretable models. Filters can be drawn as oriented-edge templates and deformation costs as heat maps, and a detection comes with its part positions.
• Released code. Complete training and detection code with trained models accompanied every version, and the retrospective notes that this made the method widely used and extended.

Limitations

• Hand-designed features. Everything rests on HOG; colour, texture and learned features are absent unless added, as later DPM variants did.
• Few aspects and rigid parts. Two to six components and a single layer of rectangular parts cover pose variation coarsely; a part cannot rotate, and parts cannot be shared between components or classes, which the authors themselves named as motivation for grammar models.
• Non-convex training. The latent SVM reaches a local optimum and depends on the initialization heuristics; the authors describe this sensitivity as common to methods with latent information.
• Speed. Without the cascade, about 2 seconds per image and class with filter responses computed on 8 cores (TPAMI), or 8 to 10 seconds single-threaded for the person and motorbike baselines of the cascade paper, and a separate model for every class.
• Boxes from windows. Detections are root windows corrected by a linear regression; a component that fires on a distinctive sub-region, like the cat face, produces boxes that are too small.

Historical Importance

By their authors’ account, DPMs were the first deformable part models to show their value on a benchmark as difficult as PASCAL VOC. They were the reference detector of the VOC challenges from 2008 to 2012 and the baseline that convolutional networks were measured against in 2014. In our reading, several of their ideas outlived HOG: latent variables for the information a box does not give, margin-based hard-negative mining with a convergence guarantee, mixtures of components split by aspect ratio, bounding-box regression from a detection’s internal state, and context rescoring from other detectors’ scores.

The first large deep-learning result in detection was measured against them: the R-CNN paper reported 53.7% mAP on VOC 2010 test against 33.4% for DPM v5, and 58.5% on VOC 2007 test with box regression against 33.7%. Girshick, Iandola, Darrell and Malik (CVPR 2015) then showed that a DPM is itself a convolutional neural network. Unrolling the matching algorithm for a fixed model gives a fixed-depth network: convolutions with the root and part filters; a distance transform pooling layer, which generalizes max pooling by replacing the hard window with the learned quadratic penalty; an “object geometry” convolution with a sparse filter that adds each transformed part map at its anchor offset; and a maxout unit that takes the maximum over components. Replacing HOG with the conv5 features of an ImageNet-trained network gave their DeepPyramid DPM. In their VOC 2007 test comparison, a root-only DeepPyramid DPM on max-filtered conv5 features reached 45.2% mAP, against 33.7% for the HOG DPM with six components and eight parts, 25.2% for the HOG DPM without parts, and 44.2% for R-CNN on pool5 features without fine-tuning, the most comparable R-CNN variant; fine-tuned R-CNN with box regression reached 58.5%. They report running about 20 times faster than that comparable R-CNN, 0.6 s against 12 s per image. Parts helped conv5 features much less than HOG in their table: adding four parts to a three-component model raised mAP by 0.9 points, where parts add 8.5 points to the HOG DPM. This, with feature visualizations, led them to the hypothesis that the conv5 filters already act as shared parts.

Variants

The model changed over five public releases, each documented on its project page:

• voc-release1. Detection code and VOC 2006 models for the system of the CVPR 2008 paper (one root filter and six parts); the learning code was announced for later.
• voc-release2 (2008). Detection code and models for the system entered in the VOC 2008 challenge, a mixture of deformable part models extending the 2008 paper; learning and context-rescoring code were announced for later.
• voc-release3 (2009). The system of the TPAMI paper: two-component mixtures, the 31-dimensional features, box prediction and context rescoring, with learning code.
• voc-release4 (April 21, 2010; 4.01 in November 2011). Three components per class, each asymmetric and matched in both orientations, with left and right poses separated by a constrained clustering of the training boxes and their mirror images; eight $6 \times 6$ parts per component; a per-cell feature marking positions outside the image, so filters can learn how to score truncated objects; and a regularizer on the largest component norm instead of the whole parameter vector. The release notes say some of these changes formed the UoC-TTI entry in the VOC 2009 challenge. Models were structured with the grammar formalism of Felzenszwalb and McAllester’s technical report on object detection grammars, and the star-cascade code was released separately.
• voc-release5 (September 5, 2012; GitHub tags 5.0 to 5.02). L-BFGS instead of the subgradient solver, a rewritten in-memory feature cache, weak-label structural SVM training, learnable scale priors, an optional extra octave of features on $2 \times 2$-pixel cells for small objects, the person grammar model and the star-cascade included. The README calls it the companion code of Girshick’s dissertation.

Grammar models. Girshick, Felzenszwalb and McAllester (NIPS 2011) generalized the mixture of stars to a grammar in which parts have subparts, parts can be optional, and an explicit occluder symbol explains why the lower parts of a person are missing. Six person parts can stop after the first $k$, the occluder filling the rest, and the first two parts carry deformable subparts at two resolutions. They trained it with a weak-label structural SVM, which scores outputs against the box label with a loss rather than a binary decision. On VOC 2010 test (comp3), the person grammar scored 47.5% AP without post-processing against 44.4% for the UoC-TTI mixture model that won the person category that year, and 49.5% with context rescoring. Box prediction did not help the grammar, which the authors attribute to the occlusion model reducing near misses.

Other extensions. The VOC retrospective describes the 2010 winners from the Chinese Academy of Sciences adding local binary pattern features and more context to a DPM, and an MIT/UCLA system with a three-layer hierarchy of root, parts and subparts. Tree-structured part models with the same matching machinery are also a classic approach to human pose estimation, where the parts are body segments; Felzenszwalb and Huttenlocher (2005) already matched an articulated person model whose parts have position, orientation and foreshortening.

Faster DPMs and successors. Besides the star cascade, a GPU implementation of DPM running at 30 frames per second was, at low accuracy, the only real-time detector the YOLO paper knew of besides its own. DeepPyramid DPM (above) is the bridge to network-based detectors, and in our reading the DPM’s ingredients survive in them: feature pyramids in the feature pyramid network, box regression and hard-example selection in two-stage detectors, and mixture components as a crude form of the multiple anchor shapes per position.

Implementations

• voc-release5 (MATLAB with C++ MEX helpers, tested with MATLAB R2011a according to the project page), released under an MIT-like licence with pretrained models for VOC 2007, VOC 2010 and INRIA person. As of October 2026, the project page links a GitHub repository, rbgirshick/voc-dpm, that includes bug fixes and speed improvements and, the page warns, gives results that differ slightly from its tables; the repository’s tags are voc-release5.0 to voc-release5.02 (2013) and its last commit dates from 2017. In the 5.02 code, the feature pyramid uses $\lambda = 5$ levels per octave for training positives and 4 for negatives, and 10 for evaluation; features have 32 channels, the 31 HOG dimensions plus the boundary feature introduced in release 4; and the training script builds $2n$ components from $n$ aspect-ratio groups, with 8 parts of $6 \times 6$ cells per component.
• OpenCV. The dpm module of opencv_contrib (4.14.0, and still present in 5.0.0 as of October 2026) implements the cascade detector in C++ for models stored as XML files. It has no training code.
• Earlier releases. The pages for releases 1 to 4 remain online, with their code and results tables.