Deformable Part Models are Convolutional Neural Networks

Introduction

Part-based representations are widely used for visual recognition tasks. In particular, deformable part models (DPMs) have been especially useful for generic object category detection. DPMs update pictorial structure models (which date back to the 1970s) with modern image features and machine learning algorithms. Convolutional neural networks (CNNs) are another influential class of models for visual recognition. CNNs also have a long history, and have come back into popular use in the last two years due to good performance on image classification and object detection tasks.

These two models, DPMs and CNNs, are typically viewed as distinct approaches to visual recognition. DPMs are graphical models (Markov random fields), while CNNs are “black-box” non-linear classifiers. In this paper we describe how a DPM can be formulated as an equivalent CNN, providing a novel synthesis of these ideas. This formulation (DPM-CNN) relies on a new CNN layer, distance transform pooling, that generalizes max pooling. Another innovation of our approach is that rather than using histograms of oriented gradients (HOG) features , we apply DPM-CNN to a feature pyramid that is computed by another CNN. Since the end-to-end system is the function composition of two networks, it is equivalent to a single, unified CNN. We call this end-to-end model DeepPyramid DPM.

We also show that DeepPyramid DPM works well in practice. In terms of object detection mean average precision, DeepPyramid DPM slightly outperforms a comparable version of the recently proposed R-CNN (specifically, R-CNN on the same $\textrm{conv}_{5}$ features, without fine-tuning), while running about 20x faster. This experimental investigation also provides a greater understanding of the relative merits of region-based detection methods, such as R-CNN, and sliding-window methods like DPM. We find that regions and sliding windows are complementary methods that will likely benefit each other if used in an ensemble.

HOG-based detectors are currently used in a wide range of models and applications, especially those where region-based methods are ill-suited (poselets being a prime example). Our results show that sliding-window detectors on deep feature pyramids significantly outperform equivalent models on HOG. Therefore, we believe that the model presented in this paper will be of great practical interest to the visual recognition community. An open-source implementation will be made available, which will allow researchers to easily build on our work.

DeepPyramid DPM

In this section we describe the DeepPyramid DPM architecture. DeepPyramid DPM is a convolutional neural network that takes as input an image pyramid and produces as output a pyramid of object detection scores. Although the model is a single CNN, for pedagogical reasons we describe it in terms of two smaller networks whose function composition yields the full network. A schematic diagram of the model is presented in Figure 1.

Objects appear at all scales in images. A standard technique for coping with this fact is to run a detector at multiple scales using an image pyramid. In the context of CNNs, this method dates back to (at least) early work on face detection in , and has been used in contemporary work including OverFeat , DetectorNet , and DenseNet . We follow this approach and use as our first CNN a network that maps an image pyramid to a feature pyramid. We use a standard single-scale architecture (Krizhevsky et al. ) and tie the network weights across all scales. Implementation details are given in Section 3.

2 DPM-CNN: Constructing an equivalent CNN from a DPM

In the DPM formalism, an object class is modeled as a mixture of “components”, each being responsible for modeling the appearance of an object sub-category (e.g., side views of cars, people doing handstands, bi-wing propeller planes). Each component, in turn, uses a low-resolution global appearance model of the sub-type (called a “root filter”), together with a small number (e.g., 8) of higher resolution “part filters” that capture the appearance of local regions of the sub-type. At test time, a DPM is run as a sliding-window detector over a feature pyramid, which is traditionally built using HOG features (alternatives have recently been explored in ). DPM assigns a score to each sliding-window location by optimizing a score function that trades off part deformation costs with image match scores. A global maximum of the score function is computed efficiently at all locations by sharing computation between neighboring positions using a dynamic programming algorithm. This algorithm is illustrated with all of the steps “unrolled” in Figure 4 of . The key observation in this section is that for any given DPM, its unrolled detection algorithm yields a specific network architecture with a fixed depth.

In order to realize DPM as a convolutional network, we first introduce the idea of distance transform (DT) pooling, which generalizes the familiar max-pooling operation used in CNNs. Given DT-pooling, a single-component DPM is constructed by composing part-filter convolution layers and DT-pooling layers with an “object geometry” layer that encodes the relative offsets of DPM parts. We call this architecture DPM-CNN; its construction is explained in Figure 2. To simplify the presentation, we consider the case where the DPM parts operate at the same resolution as the root filter. Multi-resolution models can be implemented by taking two scales as input and inserting a subsampling layer after each DT-pooling layer.

Here we show that distance transforms of sampled functions generalize max pooling.

Max pooling can be equivalently expressed as $M_{f}(p)=\max_{q\in\mathcal{G}}\left(f(q)-d_{\textrm{max}}(p-q)\right)$, where $d_{\textrm{max}}(r)$ is zero if $r\in\{-k,\ldots,k\}$ and $\infty$ otherwise. Expressing max pooling as the maximization of a function subject to a distance penalty $d_{\textrm{max}}$ makes the connection between distance transforms and max pooling clear. The distance transform generalizes max pooling and can introduce learnable parameters, as is the case in DPM. Note that unlike max pooling, the distance transform of $f$ at $p$ is taken over the entire domain $\mathcal{G}$. Therefore, rather than specifying a fixed pooling window a priori, the shape of the pooling region can be learned from the data.

In the construction of DPM-CNN, DT-pooling layers are inserted after each part filter convolution.

2.2 Object geometry filters

The score of a DPM component $c$ at each root filter location $s$ is given by adding the root filter score at $s$ to the distance transformed part scores at “anchor” locations offset from $s$. Each part $p$ has its own anchor offset that is specified by a 2D vector $v_{p}=(v_{px},v_{py})$.

Computing component scores at all root locations can be rephrased as a convolution. The idea is to stack the root filter score map together with the $P$ distance transformed part score maps to form a feature map with $P+1$ channels, and then convolve that feature map with a specially constructed filter that we call an “object geometry” filter. This name comes from the fact that the filter combines a spatial configuration of parts into a whole. The coefficients in the object geometry filter are all zero, except for a single coefficient set to one in each of the filter’s $P+1$ channels. The first channel corresponds to the root filter, and has a one in its upper-left corner (the root’s anchor is defined as $v_{0}=(0,0)$). Filter channel $p$ (counting from zero), has a one at index $v_{p}$ (using matrix-style indexing, where indices grow down and to the right). To clarify this description, an example object geometry filter for a DPM component with one root and one part is shown in the Figure 2 sidebar.

DPM is usually thought of as a flat model, but making the object geometry filter explicit reveals that DPM actually has a second, implicit convolutional layer. This insight shows that in principle one could train this filter discriminatively, rather than heuristically setting it to a sparse binary pattern. We revisit this idea when discussing our experiments in Section 4.1.

2.3 Combining mixture components with maxout

Each single-component DPM-CNN produces a score map for each pyramid level. Let $z_{sc}$ be the score for component $c$ at location $s$ in a pyramid level. In the DPM formalism, components compete with each other at each location. This competition is modeled as a max over component scores: $z_{s}=\max_{c}z_{sc}$, where the overall DPM score at $s$ is given by $z_{s}$. In DPM-CNN, $z_{sc}={\bf w}_{c}\cdot{\bf x}_{s}+b_{c}$, where ${\bf w}_{c}$ is component $c$’s object geometry filter (vectorized), ${\bf x}_{s}$ is the sub-array of root and part scores at $s$ (vectorized), and $b_{c}$ is the component’s scalar bias. Figure 3 shows the full multi-component DPM-CNN including the max non-linearity that combines component scores.

It is interesting to note that the max non-linearity used in DPM is mathematically equivalent to the “maxout” unit recently described by Goodfellow et al. . In the case of DPM, the maxout unit has a direct interpretation as a switch over the choice of model components.

2.4 Generalizations

For clarity, we constructed a DPM-CNN for the case of mixtures of star models. However, the construction is general and naturally extends to a variety of models such as object detection grammars and recent DPM variants, such as .

The CNN construction for these more complex models is analogous to the DPM-CNN construction: take the exact inference algorithm used for detection and explicitly unroll it (this can be done given a fixed model instance); express the resulting network in terms of convolutional layers (for appearance and geometry filters), distance transform pooling layers, subsampling layers, and maxout layers.

We also note that our construction is limited to models for which exact inference is possible with a non-iterative algorithm. Models with loopy graphical structures, such as Wang et al.’s hierarchical poselets model , require iterative, approximate inference algorithms that cannot be converted to equivalent fixed-depth CNNs.

3 Related work

Our work is most closely related to the deep pedestrian detection model of Ouyang and Wang . Their CNN is structured like a DPM and includes a “deformation layer” that takes a distance penalized global max within a detection window. Their work reveals some connections between single-component DPMs and CNNs, however since that is not the focus of their paper a clear mapping of generic DPMs to CNNs is not given. We extend their work by: developing object geometry filters, showing that multi-component models are implemented with maxout, describing how DPM inference over a whole image is efficiently computed in a CNN by distance transform pooling, and using a more powerful CNN front-end to generate the feature pyramid. Our DT-pooling layer differs from the “deformation layer” described in since it efficiently computes a distance transform over the entire input, rather than an independent global max for each window.

The idea of unrolling (or “time unfolding”) an inference algorithm in order to construct a fixed-depth network was explored by Gregor and LeCun in application to sparse coding . In sparse coding, inference algorithms are iterative and converge to a fixed point. Gregor and LeCun proposed to unroll an inference algorithm for a fixed number of iterations in order to define an approximator network. In the case of DPM (and similar low tree-width models), the inference algorithm is exact and non-iterative, making it possible to unroll it into a fixed-depth network without any approximations.

Boureau et al. study average and max pooling from theoretical and experimental perspectives. They discuss variants of pooling that parametrically transition from average to max. Distance transform pooling, unlike the pooling functions in , is interesting because it has a learnable pooling region. Jia et al. also address the problem of learning pooling regions by formulating it as a feature selection problem.

Our work is also related to several recent approaches to object detection using CNNs. OverFeat performs coarse sliding-window detection using a CNN. At each rough location, OverFeat uses a regressor to predict the bounding box of a nearby object. Another recent CNN-based object detector called DetectorNet also performs detection on a coarse set of sliding-window locations. At each location, DetectorNet predicts masks for the left, right, top, bottom, and whole object. These predicted masks are then clustered into object hypotheses. Currently, the most accurate object detection method for both ImageNet detection as well as PASCAL VOC is the Region-based CNN framework (R-CNN) . Unlike DetectorNet and OverFeat, R-CNN does not perform sliding-window detection; instead R-CNN begins by extracting a set of region proposals and classifies them with a linear SVM applied to CNN features.

Implementation details

We implemented our experiments by modifying the DPM voc-release5 code and using Caffe for CNN computation. We describe the most important implementation details in this section. Source code for the complete system will be available.

Our DeepPyramid DPM implementation starts by processing an input image with a truncated variant of the SuperVision CNN . We use the publicly available network weights that are distributed with R-CNN , which allows for a direct comparison. These weights were trained on the ILSVRC 2012 classification training dataset using Caffe (we do not use the detection fine-tuned weights).

Starting from this network, we made two structural modifications. The first was to remove the last max pooling layer ($\textrm{pool}_{5}$) and all of the fully-connected layers ($\textrm{fc}_{6}$, $\textrm{fc}_{7}$, $\textrm{fc}_{8}$, and softmax). The network’s output is, therefore, the feature map computed by the fifth convolutional layer ($\textrm{conv}_{5}$), which has 256 feature channels. The second modification is that before each convolutional or max pooling layer, with kernel size $k$, we zero-pad the layer’s input with $\lfloor k/2\rfloor$ zeros on all sides (top, bottom, left, and right). This padding implements “same” convolution (or pooling), where the input and output maps have the same spatial extent. With this padding, the mapping between image coordinates and CNN output coordinates is straightforward. A “pixel” (or cell) at zero-based index $(x,y)$ in the CNN’s $\textrm{conv}_{5}$ feature map has a receptive field centered on pixel $(16x,16y)$ in the input image. The $\textrm{conv}_{5}$ features, therefore, have a stride of 16 pixels in the input image with highly overlapping receptive fields of size $163\times 163$ pixels. Our experimental results show that even though the receptive fields are very large, the features are localized well enough for sliding-window detectors to precisely localize objects without regression (as in OverFeat and DetectorNet).

For simplicity, we process the image pyramid with a naive implementation in which each image pyramid level is embedded in the upper-left corner of a large ($1713\times 1713$ pixel) image. For the first image pyramid level, the original image is resized such that its largest dimension is 1713 pixels. For PASCAL VOC images, this results in up-sampling images by a factor of 3.4 on average. The first $\textrm{conv}_{5}$ pyramid level has 108 cells on its longest side. We use a pyramid with 7 levels, where the scale factor between levels is $2^{-1/2}$ (the pyramid spans three octaves). The entire $\textrm{conv}_{5}$ pyramid has roughly 25k output cells (sliding-window locations). For comparison, this is considerably more than the roughly 1,500 sliding-window locations used in OverFeat, but many fewer than the 250k commonly used in HOG feature pyramids. Computing the $\textrm{conv}_{5}$ feature pyramid as described above is fast, taking only 0.5 seconds on an NVIDIA Tesla K20c.

2 Parameter learning

DeepPyramid DPM is a single CNN that takes an image pyramid as input and outputs a pyramid of DPM detection scores. In principle, the entire network can be trained end-to-end using backpropagation by defining a loss function on the score pyramid. In this work we opt for a simpler approach in which DeepPyramid DPM is trained stage-wise, in two stages. The first stage trains the truncated SuperVision CNN. For this we simply use the publicly available model distributed with R-CNN. This model was trained for image classification on ILSVRC 2012 and was not fine-tuned for detection. In the second stage, we keep the SuperVision CNN parameters fixed and train a DPM on top of $\textrm{conv}_{5}$ feature pyramids using the standard latent SVM training algorithm used for training DPMs on HOG features. In the future, we plan to experiment with training the entire system with backpropagation.

3 DPM training and testing details

Compared to training DPM with HOG features, we found it necessary to make some changes to the standard DPM training procedure. First, we don’t use left/right mirrored pairs of mixture components. These components are easy to implement with HOG because model parameters can be explicitly “flipped” allowing them to be tied between mirrored components. Second, R-CNN and DPM use different non-maximum suppression functions and we found that the one used in R-CNN, which is based on intersection-over-union (IoU) overlap, performs slightly better with $\textrm{conv}_{5}$ features (it is worse for the baseline HOG-DPM). Lastly, we found that it’s very important to use poorly localized detections of ground-truth objects as negative examples. As in R-CNN, we define negative examples as all detections that have a max IoU overlap with a ground-truth object of less than 0.3. Using poorly localized positives as negative examples leads to substantially better results (Section 4.1.2) than just using negatives from negative images, which is the standard practice when training HOG-DPM.

Experiments

Deformable part models have been tuned for use with HOG features over several years. A priori, it’s unclear if the same structural choices that work well with HOG (e.g., the number of mixture components, number of parts, multi-resolution modeling, etc.) will also work well with very different features. We conducted several preliminary experiments on the PASCAL VOC 2007 dataset in order to find a DPM structure suited to $\textrm{conv}_{5}$ features.

In Table 1, rows 1-3, we show the effect of adding parts to a three component DPM (three was selected through cross-validation). As in HOG-based DPMs, the dimensions of root filters vary across categories and components, influenced by the aspect ratio distribution for each class. Our root filter sizes typically range from $4\times 12$ to $12\times 4$ feature cells. We start with a “root-only” model (i.e., no parts) and then show results after adding 4 or 8 parts (of size $3\times 3$) to each component. With 4 parts, mAP increases by 0.9 percentage points, with an improvement in 16 out of 20 classes. The effect size is small, but appears to be statistically significant ($p=0.016$) as judged by a paired-sample permutation test, a standard analysis tool used in the information retrieval community .

One significant difference between HOG and $\textrm{conv}_{5}$ features is that HOG describes scale-invariant local image statistics (intensity gradients), while $\textrm{conv}_{5}$ features describe large ($163\times 163$ pixel) image patches. The top two rows of Figure 4 illustrate this point. Each row shows a feature pyramid for an image of a face. The first is HOG and the second is the “face channel” of $\textrm{conv}_{5}$. In the HOG representation, the person’s face appears at all scales and one can imagine that for each level in the pyramid, it would be possible to define an appropriately sized template that would fire on the face. The $\textrm{conv}_{5}$ face channel is quite different. It only shows strong activity when the face is observed in a narrow range of scales. In the first several levels of the pyramid, the face feature responses are nearly all zero (black). The feature peaks in level 6 when the face is at the optimal scale.

Based on the previous experiments with parts and the feature visualizations, we decided to explore another hypothesis: that the convolution filters in $\textrm{conv}_{5}$ already act as a set of shared “parts” on top of the $\textrm{conv}_{4}$ features. This perspective suggests that one can spread the $\textrm{conv}_{5}$ features to introduce some local deformation invariance and then learn a root-only DPM to selectively combine them. This hypothesis is also supported by the features visualized in Figure 4. The heat maps are characteristic of part responses (cat head, person face, upper-left quarter of a circle) in that they select specific visual structures.

We implemented this idea by applying a $3\times 3$ max filter to $\textrm{conv}_{5}$ and then training a root-only DPM with three components. The max filter is run with a stride of one to prevent subsampling the feature map, which would increase the sliding-window stride to a multiple of 16. We refer to the max-filtered $\textrm{conv}_{5}$ features as “$\textrm{max}_{5}$”. Note that this model does not have any explicit DPM parts and that the root filters can be thought of as a learned object geometry filters that combine the $\textrm{conv}_{5}$ “parts”. This approach (Table 1 row 4) outperforms the DPM variants that operate directly on $\textrm{conv}_{5}$ in terms of mAP as well as training and testing speed (since each model only has three filters).

We compare our approach to several other methods on the VOC 2007 dataset. The first notable comparison is to DPM on HOG features. We report results using the standard 6 component, 8 part configuration, which achieves a mAP of 33.7%. We also computed another HOG-DPM baseline using 6 components, but without parts. Removing parts decreases HOG-DPM performance to 25.2%. The $\textrm{max}_{5}$ variant of DeepPyramid DP, which uses $\textrm{conv}_{5}$ implicitly as a set of shared parts, has a mAP of 45.2%.

We also compare our method to the recently proposed R-CNN . The directly comparable version of R-CNN uses $\textrm{pool}_{5}$ features and no fine-tuning ($\textrm{pool}_{5}$ is the same as $\textrm{max}_{5}$, but with a stride of two instead of one). This comparison isolates differences to the use of a sliding-window method versus classifying warped selective search windows. We can see that for some classes where we expect segmentation to succeed, such as aeroplane and cat, R-CNN strongly outperforms DeepPyramid DPM. For classes where we expect segmentation might fail, such as bottle, chair, and person, DeepPyramid DPM strongly outperforms R-CNN. Performance is similar for most of the other categories, with DeepPyramid DPM edging out R-CNN $\textrm{pool}_{5}$ in terms of mAP. Of course, this represents the weakest variant of R-CNN, with significant improvements coming from fine-tuning for detection and incorporating a bounding-box (BB) regression stage.

We have shown that DeepPyramid DPM is competitive with R-CNN $\textrm{pool}_{5}$ without fine-tuning. The R-CNN results suggest that most of the gains from fine-tuning come in through the non-linear classifier (implemented via layers $\textrm{fc}_{6}$ and $\textrm{fc}_{7}$) applied to $\textrm{pool}_{5}$ features. This suggests that it might be possible to achieve similar levels of performance with DeepPyramid DPM through the use of a more powerful non-linear classifier.

1.2 Ablation study

To understand the effects of some of our design choices, we report mAP performance on VOC 2007 test using a few ablations of the DP-DPM $\textrm{max}_{5}$ model. First, we look at mAP versus the number of mixture components. Mean AP with {1, 2, 3} components is {39.9%, 45.1%, 45.2%}. For most classes, performance improves when going from 1 to 2 or 1 to 3 components because the variety of templates allows for more recall. We also looked at the effect of training with negative examples that come only from negative images (i.e., not using mislocalized positives as negative examples). Using negatives only from negative images decreases mAP by 6.3 percentage points to 38.8%. Using standard DPM non-maximum suppression decreases mAP by 1.3 percentage points.

2 Results on PASCAL VOC 2010-2012

We used the VOC 2007 dataset for model and hyperparameter selection, and now we report results on VOC 2010-2012 obtained using the official evaluation server. Table 2 compares DeepPyramid DPM with a variety of methods on VOC 2010. DeepPyramid DPM outperforms all recent methods other than the fine-tuned versions of R-CNN. Performance against HOG-DPM is especially strong. When comparing to R-CNN FT $\textrm{fc}_{7}$, without bounding-box regression (BB), DeepPyramid DPM manages better performance in two classes: bottle and person. This likely speaks to the weakness in the region proposals for those classes. The VOC 2011 and 2012 sets are the same and performance is similar to 2010, with a mAP of 41.6%.

Conclusion

We have presented a novel synthesis of deformable part models and convolutional neural networks. In particular, we demonstrated that any DPM can be expressed as an equivalent CNN by using distance transform pooling layers and maxout units. Distance transform pooling generalizes max pooling and relates the idea of deformable parts to max pooling. We also showed that a DPM-CNN can run on top a feature pyramid constructed by another CNN. The resulting model—which we call DeepPyramid DPM—is a single CNN that performs multi-scale object detection by mapping an image pyramid to a detection score pyramid. Our theoretical and experimental contributions bring new life to DPM and show the potential for replacing HOG templates in a wide range of visual recognition systems.

The GPUs used in this research were generously donated by the NVIDIA Corporation.

References