Modeling Inter- and Intra-Part Deformations for Object Structure Parsing

1 Introduction

Given a target object in the image, structure parsing refers to inferring the structural information, which is useful for applications such as object matching and alignment. It typically works under a coarse-to-fine manner, where bounding boxes are first detected by running a specific object detector to provide coarse information of object locations, and then fine parsing models, e.g., [Fidler et al., 2009], [Zhu et al., 2010] and [Yang and Ramanan, 2011], are built to attain accurate object structures, parts, subparts and key points. In general, parsing of rigid objects works well by using simple geometry representations [Viola and Jones, 2001]. However, difficulties raise when facing deformable objects, like face [Felzenszwalb and Huttenlocher, 2005], pedestrian [Dalal and Triggs, 2005] and horse [Zhu et al., 2010]. The key challenge lies in the difficulty to achieve a robust and unified geometry representation for deformable objects. In such a circumstance, a fine-gained analysis of object parts and detailed structures is highly required.

Back Track

Figure 1: Two-layer deformation model for parsing object structure. The inter-part layer (the top layer) handles deformations among object parts, and the intra-part layer (the base layer) makes some local adjustments to characterize small local deformations.

In this paper, we investigate the feasibility of parsing highly deformable objects, which remains as an open problem. Specifically, we take a systematic understanding of the object deformation, and then conduct a flexible modeling for both inter- and intra-part deformations. Taking eyes and mouth in a face for instance, relative position changes between eyes and mouth belong to inter-part deformations, while appearance changes, like close eyes and open mouth, belong to intra-part deformations. Notably, most existing parsing models [Zhu et al., 2010; Yang and Ramanan, 2011] are based on the independence assumption of two kinds of deformations. Typically, they concentrate on either constructing the deformable model to deal with inter-part deformations or encoding feature to comprise intra-part deformations. For modeling intra-part deformations, there exist a few approaches [Wu et al., 2010], which yet cannot extract the invariance hidden in large deformations.

In this paper, we propose a novel two-layer model to jointly consider two kinds of deformations. To the best of our knowledge, there is not existing work targeting at modeling both inter-part and intra-part deformations, which is therefore unable to explore complicated object structures. As shown in Fig. 1, it contains two layers: the base layer accounts for local intra-part deformations, which is consisted of a set of local nodes that match feature bases in small image regions to generate low-dimensional descriptors for image patches. The top layer handles inter-part deformations, which is modeled as a Markov Random Field (MRF) whose nodes correspond to the object parts of potentially large deformations, described by the feature descriptors obtained from the base layer.

The proposed two-layer model merits in a joint inference of both abstract and detailed deformation of object parts. It enables to further localize the key feature points and sketch the finer object structures. Moreover, we design a layer-wise learning algorithm which employs belief propagation for inference, which enjoys a low computational complexity by eliminating the superfluous training samples. To learn our model, active basis sparse coding is carried out to learn the nodes as bases at the base layers, while the edge weights are estimated by deploying a structural support vector machine.

The rest of this paper is organized as follows. Sec. 2 summarizes the related work. Sec. 3 builds the architecture of the proposed parsing model, including the inter- and intra-part deformation layers. Sec. 4 describes a procedure for learning the model parameters, and Sec. 5 gives an efficient algorithm for optimal structure inference. Sec. 6 presents the experimental results, and Sec. 7 draws the conclusion.

2 RelatedWork

Mixture models, e.g., Gaussian Mixture Model (GMM) [Dempster et al., 1977], are commonly used for modeling object structures. In that sense, one object can be considered as a combination of multiple conventional structure types, and the structure estimation refers to matching the unknown structure with the most similar types. Gu and Ren [Gu and Ren, 2010] employed multiple templates to detect objects in different views. In [Park et al., 2010], multiple detectors at different scales are combined into a mixture model.

Compared to mixture models, tree-based models [Awasth et al., 2007] are more flexible in characterizing the correlations among mixture components. A typical tree structure contains no loop, so the message passing algorithm [Kschischang et al., 2001] can be applied to identify the optimal configuration. Felzenszwalb and Huttenlocher [Felzenszwalb and Huttenlocher, 2005] proposed a Pictorial Structure (PS) tree model to recognize the face structure and estimate the face pose in an image.

A branch of work has been motivated from the PS model. For example, the Articulated Model (AM) [Ramanan and Sminchisescu, 2006] employs Conditional Random Fields (CRFs) [Kumar and Hebert, 2003; Awasth et al., 2007] to handle inter-part deformations. The Deformable Part Model (DPM) [Felzenszwalb et al., 2010] extends the AMmodel to allow for more flexible spatial correlations. Nodes of DPM can be enlarged to force a more accurate parsing. For example, the Mixtures of Parts Model (MPM) in [Yang and Ramanan, 2011] exploits 26 nodes corresponding to human joints (shoulder, elbow, hand, etc.) for pose estimation, and the DPM in [Zhu and Ramanan, 2012] exploits 99 nodes to locate face landmarks.

However, increasing the number of nodes results in higher dimension of the encoded features as well as more training samples needed, which typically compromises the detection accuracy due to the increase of inference uncertainty. One solution is to reduce the number of parts by aggregating connected parts into a larger one. Another solution is to construct a multiple layer model [Fidler et al., 2010] and allocate nodes for each layer. In this way, the high-dimensional feature space can be decomposed into multiple low-dimensional ones. In [Zhu et al., 2010], Zhu et al. introduced the hierarchical deformable template to group every three nodes at one layer. The later hierarchical AOT model [Si and Zhu, 2013] is configured as a deep mixing of And-Or nodes to represent the compositions of parts and structural variations.

Although our proposed model is relevant to two recent multi-layer models, Hierarchical Deformable Template (HDT) [Zhu et al., 2010] and And-Or Template (AOT) [Si and Zhu, 2013], our model differs from and merits over them in terms of robustly dealing with appearance variations and shape deformations. First, the HDT model [Zhu et al., 2010] imposes a restriction on the number of child nodes, i.e., each node can only have three child nodes at one layer. Notably, our model discards this restriction so that each node can associate an arbitrary number of child nodes. Second, unlike the independence assumption adopted in AOT [Si and Zhu, 2013], our model encodes visual appearances with geometry deformations in a joint feature encoding function, therefore allows for capturing large non-rigid deformations.

3 The ProposedModel

Considering that object structure varies significantly with poses and view points, we anticipate the proposed parsing model to deal with such variances. Unlike the HDT [Zhu et al., 2010], MPM [Yang and Ramanan, 2011] and AOT [Si and Zhu, 2013], we use two deformation layers to model both inter- and intra-part deformations.As shown in Fig. 1, the top layer consists of a few nodes to represent key object parts and describes global inter-part deformations with an undirected graph. The nodes at the base layer are divided into different types of part templates, which have connections with the corresponding parent nodes at the top layer. Unlike the part detectors in [Yang and Ramanan, 2011; Zhu and Ramanan, 2012; Gu and Ren, 2010], the part templates in our model are not fixed, but are composed of many nodes which make minor adjustments independently and locally represent the distinguished sub-part regions. Such a design enables us to accurately characterize complicated intrapart deformations.

We assume that an object structure Z is composed of N parts, Z = (z1, . . . , zN). Each part zi is a node vi ∈ V of a graph G = (V, E), and the undirected edge eij = (vi, vj) ∈ E connecting two nodes encodes their pairwise interaction. In our model, zi is denoted as a triple set 〈xi, yi, ti〉 where (xi, yi) is its pixel location and ti ∈ {1, 2, . . . , T} indicates which type of part template is activated, e.g., the horse head may go up and down and thus has multiple types based on the head position relative to the body. Given a feature map J of the image I (J in our experiment is set as the Gabor feature map by convoluting I with rotational Gabor filters), we define a MRF to evaluate the posterior probability of an object structure configuration Z under the unary and pairwise potential weighting parameter set w = (w1, . . . ,wN, . . . ,wij, . . .) and the template set D = (D1, . . . ,DN),

where the first term h(zi, zj,wij) is the pairwise potential that quantifies the spatial relationship of zi and zj, and is responsible for modeling the inter-part deformation, as detailed in Sec. 3.1. The second term g(zi, J, wi, Di) is the unary potential that collects the local image evidence for the part zi in J given the template Di of part i. Indeed, g can be regarded as a part template to locate a certain object part in the feature map J, as detailed in Sec. 3.2. The weighting parameters wi and wij control the contribution of g and h.

3.1 Inter-Part Deformation Layer

The inter-part deformation derives from the relative location changes among parts. Following [Yang and Ramanan, 2011; Zhu and Ramanan, 2012; Felzenszwalb et al., 2010], we assume the relative location is dependent on the type ti. That is, the relative location between them have T 2 combinations. When a part zi is given, the other part zj can be estimated by the posterior probability p(zj|zi,wij). We rewrite p(zj |zi, wij ) as p(tj |zi, wij )p(xj , yj |tj , zi, wij ), and approximate it using two exponential functions, i.e.,

where wij = (w(111) ij , . . . ,wT 2 (3) ij ). ∆xtitj ij and ∆ytitj ij are the x- and y-directional mean displacements of parts zi and zj respectively. For simplification, we define vxtitj ij = -(xi - xj - ∆xtitj ij )2 and vytitj ij = -(yi - yj -∆ytitj ij )2 Note that Eq. 1 is an exponential function. We then define the inter-part deformation term p(zj|zi,wij) by exp (h(zi, zj,wij)), i.e., h(zi, zj,wij) is written as

3.2 Intra-Part Deformation Layer

In models presented in [Yang and Ramanan, 2011; Zhu and Ramanan, 2012; Gu and Ren, 2010; Park et al., 2010], the invariance to intra-part deformations relies on the feature encoding scheme by using, e.g., the HOG descriptor. However, the dimension of HOG is linearly related to the part's area, which would result in a high dimensional feature vector if the node at the inter-part deformation layer covers a large object part region. In addition, HOG encodes the gradient information of the block instead of the pixel, which cannot provide accurate localization information.

In contrast, active basis sparse coding [Wu et al., 2010] can produce a lower dimensional feature vector by projecting image patches onto feature bases. Unlike the invariance in the HOG encoding, Matching pursuit (MP) provides another way of invariance by searching the local optimal matching for the node of template. MP has been used in [Wu et al., 2010] to construct the part template and encode image patches as the sum of active bases.

In this work, we utilize MP at the intra-part deformation layer to handle local deformations and achieve the local invariance. It can be formulated as:

where q means a candidate from the candidate set φ of MP. In practice, the more candidates in φ, the larger deformation is allowed, yet the accuracy might decrease. The result of MP can be considered as a local image evidence of the object part zi. It is employed as a child node of zi at the base layer. To prevent overfitting, we restrict each part zi to T × K child nodes at the base layer, which form T types of part templates with K members, i.e., Di = (d11 i , . . . , dTK i ). Based on the type variable ti of zi, the connections of K nodes of the tith type are activated. Unlike the dependent nodes at the top layer, the nodes at the base layer are independent from each other for an effective representation and inference. Thus, the unary potential g of Eq. 1 is defined as the sum of contributions of K nodes:

where wi = (w(11) i , . . . , wTK i ), and wtik i weights the contribution of the node dtik i . The function ϕ takes zi and dtik i as parameters and produces the candidate set φ of MP, and it is introduced in Sec. 3.3.

3.3 Feature Map

The intra-deformation layer is constructed with the feature map J of the original image I. Here, we define J as the whitening normalization of the contentional Gabor feature map introduced in [Wu et al., 2010]. It normalizes the response of Gabor filtering over a number of pixels and orientation directions to make the feature map comparable among images.

The feature of a point qk in J is denoted as qk = (xk, yk, ok), where (xk, yk) and ok are its spatial location and orientation, respectively. Though small deformations cause some perturbations in qk, MP can search for the best match in the candidate set which collects feasible locations to offset these perturbations. In Eq. 6, the candidate set φ is generated by the function ϕ with two parameters zi and dtik i , i.e.,

where dtik i = (xtik i , ytik i , otik i ) is the tik-th child node of zi, and two predefined parameters △d and △o controlling the size of the candidate set.

4 Model Learning

Given the labeled positive samples {(J1,Z1), . . . , (JM+,ZM+)} and the unlabeled negative samples {JM++1, . . . , JM }, the model learning is to estimate w and D, in which the parameter set w balances the contributions of the unary and pairwise potentials, while the D localizes the object parts in the feature map. Here, we follow the assumption in [Zhu et al., 2010; Yang and Ramanan, 2011; Dalal and Triggs, 2005; Zhu and Ramanan, 2012] that inter-part and intra-part deformations are independent. Therefore w and D can be learned separately from the training samples. According to the model architecture, the base layer, i.e., intra-part deformation, should be learned prior to the top layer, i.e., the inter-part deformation, to generate the template set D. Then, the learning procedure in the top layer only estimates the weighting vectors w.

4.1 Learning Intra-Part Deformation Layer

At the intra-part deformation layer, the set D includes N × T × K Gabor feature bases {d(11) 1 , . . . , dTK N } as the base layer nodes. According to Eq. 7, the location of the base layer node is determined by its parent node zi and its offset location (xtik i , ytik i ). Thus, we collect feature maps from the same part and the same type, and search for K distinguished Gabor feature bases to construct a type of part template of Di. For each type of part, MP is used to search the feature map for the maximum filtering response over all locations, which pools a probability distribution. Then, projection pursuit (PP) extracts the first K feature bases with highest probabilities to form a part template. For more details about learning Di, the reader is encouraged to refer to [Wu et al., 2010].

Notably, we assume each training sample is assigned a label zi composed of the part location (xi, yi) and the part type ti. However, it is difficult to give unambiguous definitions of the part's location and type, i.e., xi, yi and ti cannot be directly labeled by hand.With these key points, active shape model (ASM) [Ginneken et al., 2002] is adopted to align the root part and project key points onto a uniform coordinate. Then, K-means is used to generate clusters for each object part. The center of a cluster is considered as the part location (xi, yi) , and the cluster label as its type ti.

4.2 Learning Inter-Part Deformation Layer

For simplicity, we rewrite Eq. 1 as the inner product of the weighting vector w and the feature function F(Z, J, D):

where

and utik i denotes MP (J, ϕ(zi, dtik i )).

Based on the structural support vector machine [Tsochantaridis et al., 2005], the weighting vector w can be estimated by maximizing the margin between positive samples and negative samples:

The constraints make the learned model assign large scores and small scores to positive samples and negative samples, respectively. The training samples violating these principles result in the penalty variables ξm > 0. Moreover, the cuttingplane method [Joachims et al., 2009] is employed to search for those active constraints and ignore inactive ones.

5 Inference

Given the feature map J, the two-layer deformation model defined in Eq. 1 can be applied to make a confidence score for an arbitrary structure Z. However, for a simple object with only 5 parts and 5 mixture types in a 320 × 240 image, the number of possible configuration is (320 × 240 × 5)5 , hence it is impractical to adopt the brute-force search. Instead, we propose to conduct an efficient inference to determine the optimal configuration Z∗ , i.e.,

To this end, we consider the graph G as a simple tree structure, so that belief propagation (BP) [Kschischang et al., 2001; Felzenszwalb and Huttenlocher, 2005] can be applied with a linear time complexity. BP inference includes three steps: messages passing from leaves to the root, optimal root configuration determination, and message backtracking to determine the optimal configuration of other parts. Without loss of generality, we define the root part as z1, and each non-root part zi has only one parent part zpa(i). Each zi sends a message Bi to its parent zpa(i), that is

Starting from leaf parts, every non-root part sends a message to its parent, and the propagation procedure continues until the root part receives all messages. Then, the optimal configuration z∗ 1 of the root part is determined as the one with the highest score, i.e.,

At last, we can backtrack the messages sending to z∗ 1 by performing a reverse propagation, through which we can find the optimal configurations of non-root parts z∗ i = arg max zi (Bi(zpa(i))). Continuing to backtrack to the base layer, the optimal configuration of the k-th child node of part z∗ i is written as :

The tree structure used in our model is simple and loopfree. We can easily extend the tree structure to a loopy graphical model. Accordingly, the loopy belief propagation [Weiss, 2000] is run to approximately infer the optimal configuration.

6 Experiments

The proposed model 1 is evaluated on Kaggle face dataset [KAG, 2013] and the Weizmann horse dataset [Borenstein and Ullman, 2008]. These two datesets provide test images with key points to quantitatively evaluate the performance of parsing models in [Zhu et al., 2010; Wu et al., 2010; Yang and Ramanan, 2011; Si and Zhu, 2013], especially the horse dataset which present many complicated structures, with large intra- and inter-part deformations. The effectiveness of our model is addressed through comparing to these popular and state-of-the-art deformation models. For the evaluation protocol, the average pixel distance between the predicted key points and the ground truth, namely Average Position Error (APE), is calculated for each model.

1 MATLAB codes can be downloaded from Ling Cai's homepage at: https://sites.google.com/site/lingcai2006sjtu/parsing

Table 1: The average position error of object parts on two datasets.

6.1 Face Structure Parsing

Face is composed of six basic parts (two eyes, two eyebrows, a nose and a mouth) set up in a spatial structure configuration. In the Kaggle face dataset, some parts present the intra-part deformations, e.g., the mouth shape undergoes its movement when human is speaking. However, the facial expressions elicit the inter-part deformation. In addition, some accessories, like beard and eyeglasses, cause enormous difficulties for the deformation model. We test our performance on the Kaggle face dataset [KAG, 2013] to parse face images and localize the facial key points. Each image includes 15 key points of 6 facial parts. Even the same person can exhibit varying facial appearances according to his pose, the camera position or the illumination. As a result, the facial keypoint detection is actually quite challenging for the parsing models.

In our parsing model, the top layer includes 6 nodes with one type (T = 1) to represent the corresponding face parts, and each one has 20 child nodes at the base layer to offset the intra-part deformations. The nearest node at the base layer is used to predict the key point by adding a displacement vector. Moreover, 100 facial images are used to estimate the model parameter D and w. Test is made on 250 images, and the results from our model are visualized in the first row of Fig. 2. As can be seen, for each part, the nodes at the base layer are mainly scattered around the key point to effectively encode the local region, while the node at the top layer allows the big movement to handle the inter-part deformations. Unlike two deformation layers in our model, the single intra-deformation layer in ABM cannot overcome the inter-part deformation, which generates larger positioning errors as shown in the second row. Though the grid graph in AOT can approximate the inter-part deformations, it often uses two nodes to represent one object part. Consequently intra-part deformations at the base layer are handled by the nodes at the top layer, e.g., two key points at the eyebrows shown in the last row of Fig. 2.

6.2 Horse Structure Parsing

Compared to faces, the horses in the Weizmann horse dataset [Borenstein and Ullman, 2008] present more complicated structures, with more intra- and inter-part deformations. Firstly, the structure of a horse has been represented by four parts: the root part corresponding to the horse's body and three child parts being the head, the front legs and the hind legs. Secondly, we transformed all the training images to a uniform coordinate system by aligning the root parts, so that the scales and orientations are almost the same for the training samples. At last, the clustering approach is run to determine the part label. With the clusters of the object parts using PP, we constructed a template for each type of object parts. 164 images in the dataset have been considered as positive samples to impose positive constraints for the parameter w. To predict the specific key points on the horse, we employ the node in the intra-part layer as the anchor and a linear displacement vector to determine the positions of these points. Both ABM and our model use 80 Gabor features to represent object structure, while MPM and HDT detects 24 specific object parts as its structure.

Fig. 3 shows the comparison result of the five models for the horse parsing. The 1st row illustrates the results produced by our model, with the Gabor bases corresponding to the head, body, front legs and hind legs being drawn in green, red, blue and yellow line segments, respectively. Note that, some mixed colors appear in the overlap parts, e.g., the yellow segments in the neck region is the mixture of red and green. Without the inter-part deformation, ABM (2nd row of Fig. 3) fuses the simple similarity transform to learn a single template and fits it with different object structures, so it can only represent the most common structure and the others are considered as noise, shown in the second row. HOG gains better invariance to minor local deformations than Gabor feature, but it loses the capability of accurate position detection, e.g., the results in the 3rd row of Fig. 3 indicate that MPM cannot accurately determine some object parts, especially for the front and hind legs. To overcome the shortages of Gabor features, the intra-part deformation layer is constructed in our model to handle those local deformations. Similarly, the base layer in AOT deals with the intra-part deformations, but the top layer based on a grid graph present strict limitations on the part's size and position. Occasionally, an object part is represented by multiple nodes. Moreover, the grid graph does not allow the nodes for large movements. Therefore, to a certain extend, AOT is limited on describing some parts with large inter-part deformations, like head and legs as shown in the 4th row of Fig. 3. Unlike the two deformation layers in our model, HDT, based on the hierarchical structure, contains multiple deformation layers but can only include three nodes at each layers in order to construct an invariant triplet vector. As shown in the last row of Fig. 3, the structures from HDT parsing results are just composed of some key points, which is much less informative than the sparse representation produced by our model.

6.3 Quantitative Evaluation

APE is used to quantitatively evaluate the performance of different parsing models. There is no scale issue on the Kaggle face dataset [KAG, 2013] as all images have the same size, so we measure APE on the original images. Fig. 4 (a) shows the APE of 15 key points in 300 facial images. Table 1 (a) show the APE of parts and the total APE, respectively. It can be seen that our model achieves more accurate position results at almost all key points comparing against ABM and AOT, and has the total APE less than 5.

Unlike facial images, the horse images of the varying size should be noticed for the Weizmann horse dataset [Borenstein and Ullman, 2008]. To offset the scale variations, all test images are transformed to a unified coordinate system by aligning the body part. Compared to facial images, the horse images undergo larger intra- and inter-part deformations, which pose a greater challenge to the parsing model. The quantitative evaluation for the horse samples is illustrated in Fig. 4 (b). The APE of parts and the total APE of the five models are listed in Table 1 (b). It is clear that our model gives the smallest APE at 22 key points of 24 key points, and has the total APE less than 14.

7 Conclusion

In this paper, we proposed a novel two-layer object parsing model, which incorporates and jointly learns inter- and intrapart deformations towards robust object parsing. The base layer accounts for intra-part deformations, and carries out active basis sparse coding to encode an object part as a feature vector. The top layer captures inter-part deformations through employing a MRF to accommodate large deformations of object parts. By designing such a two-layer architecture, the optimal object structure can be effectively and efficiently inferred via our devised layer-wise learning algorithm. Extensive qualitative and quantitative experimental results corroborate that the proposed model can tolerate larger part deformations and characterize finer object structures than the stateof-the-art models.

Acknowledgments

This work is supported by China National Science Foundation (No. 61422210, No. 61373076 and No. 61175009). We would like to thank Dr. Fengna Wang and the anonymous reviewers for their valuable comments.