A Discriminatively Trained, Multiscale, Deformable Part Model

“A Discriminatively Trained, Multiscale, Deformable Part Model” by Pedro Felzenszwalb (University of Chicago), David McAllester (Toyota Technological Institute at Chicago) and Deva Ramanan (UC Irvine) was presented at the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) in Anchorage in June 2008. It introduced the detector that became known as the deformable part model (DPM): a coarse HOG template for the whole object plus six part templates at twice the resolution, each free to move at a learned cost, scanned over an image pyramid and trained from bounding boxes alone. Its two training ideas were the latent SVM and a margin-sensitive way of data-mining hard negatives. On PASCAL VOC the system doubled the best 2006 person-detection AP and, against the entries of the 2007 challenge, had the best AP in 10 of 20 classes. This article covers the 2008 paper as published; the subject article covers the model family as it developed through the 2010 journal paper and five code releases. We read the paper in the authors’ copy on Felzenszwalb’s home page; the IEEE Xplore text was not accessible to us, so we have not compared the two.

Problem

Part-based models had a long history. Fischler and Elschlager’s pictorial structures (1973) represent an object as parts joined by spring-like connections, and Felzenszwalb and Huttenlocher (2005) had made matching such models efficient with dynamic programming and distance transforms. The paper calls deformable part models conceptually elegant but notes that their value was hard to establish in practice: on difficult datasets they were often beaten by “conceptually weaker” models, namely rigid templates such as Dalal and Triggs’s HOG detector and bag-of-features classifiers such as that of Zhang et al. (see bag of visual words). Closing this performance gap is stated as one of the main goals.

The paper also frames a learning problem. PASCAL annotations give only a box per object, so the positions of parts are unknown, and the box itself is an imprecise guide to where a detection window should sit. Earlier discriminatively trained part models are cited, but the authors distinguish their system as semi-supervised, trained in a max-margin framework, and not reliant on feature (interest-point) detection. They contrast its training time, 3 hours per model on one CPU in the introduction, with computationally demanding weakly supervised part learning.

Contribution

The introduction describes three contributions:

1. The model. A multiscale star-shaped part model built on HOG: a root filter, equivalent to a Dalal–Triggs template, plus part filters on features of twice the spatial resolution, with a spatial model per part.
2. Latent SVM. A generalization of the SVM in which each example is scored by maximizing a linear function over latent values, here the part placements and the exact root position. The training problem is not convex, but it is semi-convex: it becomes convex once the latent values of the positive examples are fixed. The paper contrasts this with the hidden CRF of Quattoni et al., which also leads to a non-convex problem but lacks this property.
3. Data-mining hard negatives. An iterative cache scheme that trains on hard examples only and, with a margin-sensitive definition of “hard”, comes with a theoretical guarantee, stated without proof, of reaching the solution for the full training set.

The abstract ends with the expectation that these training methods would allow richer latent structure, naming hierarchical (grammar) models and latent three-dimensional pose.

Method

Features. The paper follows Dalal and Triggs’s construction on $8 \times 8$-pixel cells: each pixel votes into one of nine orientation bins with a weight depending on gradient magnitude, taking for colour images the channel with the largest gradient, and each cell’s histogram is normalized separately by the energy of each of the four $2 \times 2$-cell blocks that contain it. A cell is therefore described by $9 \times 4 = 36$ numbers, and a $w \times h$ filter has $w \times h \times 36$ weights. The 2008 text mentions no truncation of normalized values, no pyramid scale step, and no non-maximum suppression procedure.

Model. A model with $n$ parts is a root filter $F_0$ and part models $P_i = (F_i, v_i, s_i, a_i, b_i)$, where $v_i$ is the centre of a box of allowed positions relative to the root, $s_i$ its size, and $a_i, b_i$ two-dimensional coefficient vectors. Part filters sit at the pyramid level whose cells are half the size of the root’s. A placement $z = (p_0, \dots, p_n)$, with $p_i = (x_i, y_i, l_i)$, scores

$$\sum_{i=0}^{n} F_i \cdot \phi(H, p_i) + \sum_{i=1}^{n} a_i \cdot (\tilde{x}_i, \tilde{y}_i) + b_i \cdot (\tilde{x}_i^2, \tilde{y}_i^2), \qquad (\tilde{x}_i, \tilde{y}_i) = \frac{(x_i, y_i) - 2(x_0, y_0) + v_i}{s_i},$$

with $(\tilde{x}_i, \tilde{y}_i)$ required to lie in $[-1, 1]$, so each part moves inside a box. As printed, the offset adds $v_i$ where the journal version subtracts the anchor. There is no bias term. The paper points out that $a_i$ and $b_i$ may be negative, which it presents as more general than the usual quadratic spring cost. In our reading, the spatial term is a free quadratic in the normalized displacement: with $b_i$ negative it penalizes displacement like a spring, and with $b_i$ positive it would reward it. Matching uses dynamic programming and generalized distance transforms in $O(nk)$ time for $k$ pyramid cells; the subject article describes the algorithm. The score is a dot product $\beta \cdot \psi(H, z)$ between the stacked filters and spatial coefficients and the stacked features and displacement terms, which is what makes it trainable as a linear classifier.

Latent SVM. Each example $x$ comes with a set $Z(x)$ of valid placements and is scored by $f_\beta(x) = \max_{z \in Z(x)} \beta \cdot \Phi(x, z)$. The 2008 objective is

$$\beta^*(D) = \arg\min_\beta \; \lambda \lVert \beta \rVert^2 + \sum_{i=1}^{n} \max\big(0,\, 1 - y_i f_\beta(x_i)\big).$$

A positive example is a training box, with $Z(x)$ restricted to root placements overlapping the box by at least 50%. Every root placement in an image without the class is a negative. Coordinate descent alternates between choosing each positive’s best latent value and solving the convex problem that remains; the paper states, without proof, that neither step worsens the objective.

Hard negatives. The 2008 paper defines the hard instances of a training set as those with $y f_\beta(x) \le 1$, that is, misclassified or on or inside the margin, and states three theorems, with proofs omitted for space:

1. If $C \subseteq D$ contains all hard instances of $D$ relative to $\beta^*(D)$, then $\beta^*(C) = \beta^*(D)$.
2. A fixed point of retraining on the hard instances is the full-data solution: if $\beta^*(M(\beta, D)) = \beta$, then $\beta = \beta^*(D)$, where $M(\beta, D)$ is the set of hard instances.
3. An algorithm that trains on a cache $C$, shrinks it to its hard instances, then grows it with hard instances from $D$ up to a memory limit $L$, converges to $\beta^*(D)$ in finite time provided $|C| < L$ after every shrink.

The theorems apply to ordinary SVMs and to the convex step of latent SVM training.

Training as implemented. The paper says plainly that many of these ideas were only approximately implemented. Each latent SVM iteration fixed every example’s latent value and ran SVMLight on the resulting feature vectors; the journal version later describes this as optimizing a heuristic approximation of the objective. The schedule was:

• Root filter initialization. The root’s aspect ratio is the most common one among the training boxes, and its size the largest not larger than 80% of them, a heuristic chosen by cross-validation over 5 classes. An initial root is trained as a standard SVM on unoccluded positives, scaled anisotropically to the filter, against random negative windows.
• Root filter update. For each training box, the best-scoring root placement that overlaps it significantly, found in the unscaled image, becomes the new positive; the root is retrained twice this way.
• Part initialization. Six parts, each of area $a$ with $6a$ equal to 80% of the root’s area, are placed greedily on the rectangles of the root filter with the most positive energy, zeroing each chosen region before picking the next. Part filters are interpolated from the root weights, with initial coefficients $a_i = (0, 0)$ and $b_i = -(1, 1)$, a squared-distance cost.
• Model update, 10 times. Positives take the highest-scoring placement at any position and scale with at least 50% overlap; hard negatives from negative images fill a cache up to file-size limits, keeping the previous cache’s hard instances. By the final iterations the cache held every hard instance.

The whole procedure took 3 to 4 hours per PASCAL class on a single CPU, including part initialization, and detection took about 2 seconds per image. The paper gives no processor or image size for either figure.

Results

All results are average precision under the PASCAL VOC 2006 and 2007 comp3 protocols. In comp3, as the VOC2007 development kit defines it, systems are trained only on the challenge’s own train and validation data; a detection counts as correct when its area of overlap with a ground-truth box, measured as intersection over union, exceeds 50%.

VOC 2007 (Table 1). The table compares the system’s AP in each of the 20 classes with the entries to the official 2007 competition:

Class	aero	bike	bird	boat	bottle	bus	car	cat	chair	cow
AP	.180	.411	.092	.098	.249	.349	.396	.110	.155	.165
Printed rank	3	1	2	1	1	2	2	4	1	1

Class	table	dog	horse	mbike	person	plant	sheep	sofa	train	tv
AP	.110	.062	.301	.337	.267	.140	.141	.156	.206	.336
Printed rank	1	4	2	2	1	1	2	1	4	1

Bold marks the classes in which the paper’s system has the best AP. The paper prints no mean; the 20 values average to 21.3% (our arithmetic). The text says the system has the highest score in 10 classes and the second highest in 6; the abstract mentions only the first figure, “ten out of twenty categories”. Recomputing the ranks from the table’s own numbers, all agree except dog, where four entries in the table score above .062 (.071, .126, .141 and .162), which would place the system fifth rather than the printed fourth. The comparison set also leaves out the authors’ own competition entry. A preliminary version of the system, entered as UoCTTI, had the best score in 6 classes in the official competition, which the official VOC2007 results page confirms (boat, bottle, chair, cow, potted plant and tv monitor). Its 20 values on that page average to 17.1% (our arithmetic), and it beats the paper’s system in aeroplane (.206 against .180) and narrowly in bird and sheep. The authors also observe that the system works for rigid classes such as cars and sofas and deformable ones such as people and horses, and with roughly 4,700 positive training examples (person) as well as 250 (sofa).

VOC 2006 person (Figure 6). Components were evaluated on the 2006 person data. The best AP in the 2006 competition, .16, came from a rigid HOG template, and the best previous result, .19, from Ramanan’s addition of segmentation-based verification (2007). The paper’s variants scored:

Model	AP
Root only (equivalent to Dalal–Triggs)	.18
Root, latent window placement	.24
Parts, latent placement, no root	.29
Root, parts, latent placement	.34

Choosing the window position and scale of each positive as a latent variable helped even a rigid template, which the authors attribute to the detection window adjusting itself to the training examples. The parts-only model’s deficit illustrates, according to the authors, the value of the multiscale representation. The abstract’s “two-fold improvement” compares .34 with the competition’s .16; the text’s “a factor of two above the best previous score” sits next to the .19 result, a ratio of about 1.8 (our arithmetic).

A second experiment varied the part box size $s_i$, in HOG cells, with no deformation cost (except in the last column):

$s_i$	0	1	2	3	2, with quadratic cost
AP	.27	.33	.31	.31	.34

Rigid high-resolution parts ($s_i = 0$) already beat the root-alone model; the text compares their .27 with .24, the score Figure 6 gives to the root with latent placement rather than to the plain root model (.18). Performance peaked at $s_i = 1$; the authors note that larger displacements without a deformation cost start to approach a bag-of-features model. The best setting allowed larger boxes with an explicit deformation cost.

The authors also argue against the false-positives-per-window curves then common in pedestrian detection, which use cropped positives, depend on the scan resolution and ignore non-maximum suppression. They regard PASCAL’s AP on whole images as the more reliable measure.

Versions

The full journal paper, “Object Detection with Discriminatively Trained Part-Based Models” by Felzenszwalb, Girshick, McAllester and Ramanan, appeared in IEEE TPAMI in 2010 and calls the 2008 system a preliminary version. It lists the differences: mixtures of components; the true latent SVM objective, optimized by stochastic gradient descent, instead of an SVM package applied to a heuristic approximation; new 31-dimensional features; and bounding-box prediction and context rescoring, where the 2008 system had reported root-filter boxes. Comparing the texts shows more: the journal model has a bias term and writes the deformation cost on unnormalized displacements from an anchor, and its data-mining section defines hard examples with a strict inequality ($y f_\beta(x) < 1$), adds a set of easy examples, and replaces the 2008 fixed-point and memory-limit theorems with a stopping theorem and a termination theorem, both proved. A footnote says the authors defined the latent SVM in 2008 before realizing its relationship to MI-SVM. The deformable part models article describes the journal system and its results.

Code

The first public release accompanied this paper: MATLAB detection code with C++ helpers, under the MIT licence, with models for 10 VOC 2006 classes; models for 2007 and the learning code were announced for later. Its page reports VOC 2006 comp3 test AP for those classes, including 0.322 for person, a little below the paper’s .34. Four further releases followed, through voc-release5 in 2012; the subject article gives their history and results.

Impact

The 2008 paper started the line of detectors that the PASCAL VOC organizers’ retrospective, citing the journal form, calls the reference method for detection in VOC 2008–2012; the retrospective also records teams led by Felzenszwalb as joint winners in 2008 and 2009 and credits the released code with the method’s wide use (Everingham et al., 2015). At the VOC 2010 workshop the organizers gave 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 submissions. The PAMI Technical Committee lists the paper as the 2018 recipient of the Longuet-Higgins Prize, which is awarded at CVPR to CVPR papers from ten years earlier that have had significant impact on computer vision research.

In our reading, three ideas of the paper spread beyond HOG templates: treating information missing from the annotation, such as part positions and the exact window, as latent variables in a max-margin objective; the semi-convexity argument that justifies alternating between relabelling positives and convex training; and margin-based hard-negative mining with a guarantee of reaching the full-data solution.

Limitations

• Theory ahead of implementation. The theorems are stated without proofs, and the system as run fixed all latent values and used SVMLight on that approximation, with caches bounded by file sizes; the paper says the ideas are only approximately implemented.
• One component per class. A single star model must cover every view of a class, and the deformation box limits parts to small shifts. The discussion names mixture models (frontal versus side cars), deeper part hierarchies and three-dimensional pose as next steps.
• Boxes from the root alone. As the journal paper notes, the 2008 system reported boxes derived from root-filter locations; the better-localized parts did not refine the box.
• Comparison conditions. Table 1 compares a system finished after the competition with the 2007 entries, leaving out the authors’ own entry, and the challenge page records the annotated test data as public from 6 November 2007. In our reading, the ranks are therefore not results obtained under the competition’s conditions, although the paper gives no sign of tuning on the test set.
• Small inconsistencies. Training time is 3 hours in the introduction and 3 to 4 hours in Section 3.4; the printed dog rank does not match the table’s numbers; and the $s_i$ experiment calls .24 the root-only score.
• Hand-designed features and speed. Everything rests on HOG, and detection took about 2 seconds per image; since each class has its own model, we read this as the cost of one class.

What Came After

The 2008 system grew into mixtures of components in the VOC 2008 entry and the 2010 journal paper, then into star cascades and grammar models, all covered in the deformable part models article. In 2014 the R-CNN paper measured CNN features on region proposals against the fifth DPM release, reporting 58.5% mAP on VOC 2007 test against 33.7%. Girshick, Iandola, Darrell and Malik (2015) then showed that a DPM can be written as a convolutional neural network, with distance-transform pooling in place of max pooling. The object detection article places the DPM between the HOG detector and region-based networks, and sliding window detection covers the scanning and hard-negative mining it shares with the HOG detector.