Image Modeling Using Tree Structured Conditional Random Fields

1 Introduction

Probabilistic modeling techniques have been used effectively in several computer vision related tasks such as image segmentation, classification, object detection etc. These tasks typically require processing information available at different levels of granularity. In this work we propose a probabilistic framework that can incorporate image information at various scales in a meaningful and tractable model. Our framework, like many of the existing image modeling approaches, is built on Random field theory. Random field theory models the uncertain information by encoding it in terms of a set S of random variables and an underlying graph structure G. The graph structure represents the dependence relationship among these variables. We are interested in the problem of inferencing which can be stated as: Given the values taken by some subset X ∈ S, estimate the most probable values for another subset Y ∈ S. Conventionally, we define the variables in the set X as observations and the variables in the set Y as labels.

The information relevant for constructing an accurate model of the image can be broadly classified into two categories widely known as bottom-up cues and top-down cues.

∗Part of this work was done while the author was at IIT Madras.

Balaraman Ravindran

Dept. of CSE IIT Madras

ravi@cs.iitm.ernet.in

Bottom-up cues refer to the statistical properties of individual pixels or a group of pixels derived from the outputs of various filters. Top-down cues refer to the contextual features present in the image. This information represents the interactions that exist among the labels in the set Y. These top-down cues need to be captured at different levels of scale for different tasks as described in [Kumar and Hebert, 2005]. Bottom-up cues such as color and texture features of the image are insufficient and ambiguous for discriminating the pixels with similar spectral signatures. With reference to Figure 1 taken from the Corel image database, it can be observed that {rhino, land} and {sea, sky} pixels are closely related in terms of their spectral properties. However, an expanded context window can resolve the ambiguity. It also obviates the improbable configurations like the occurrence of a boundary between snow and water pixels. Further enlarging the context window captures expected global relationships such as 1) polar bear surrounded by snow and 2) sky at the top of the image while water at the bottom. Any system that fails to capture them is likely to make a large number of errors on difficult test images. In this work we try to model these relationships by proposing a discriminative hierarchical framework.

1.1 RelatedWork

In the past, [Geman and Geman, 1984] have proposed Markov Random Field (MRF) based models for joint modeling of the variables X and Y. The generative nature of MRFs restricts the underlying graph structure to a simple two dimensional lattice which can capture only local relationships among neighboring pixels, e.g. within a 4 × 4 or a 8 × 8 window. The computational complexity of the training and inference procedures for MRFs rules out the possibility of using a larger window size. Multiscale Random Fields (MSRFs) [Bouman and Shapiro, 1994] try to remove this limitation by capturing the interactions among labels in a hierarchical framework. Similar approach has been proposed by [Feng et al., 2002] using Tree Structured Bayesian Networks (TSBNs). These approaches have the ability to capture long range label relationships. In-spite of the advantage offered by the hierarchical nature, these methods suffer from the same limitations of the generative models, namely,

• Strong independence assumptions among the observations X.
• Introduction of a large number of parameters by modeling the joint probability P(Y,X).
• Need for large training data.

Recently, with the introduction of Conditional Random Fields (CRFs), the use of discriminative models for classification tasks has become popular [Lafferty et al., 2001]. CRFs offer a lot of advantages over the generative approaches by directly modeling the conditional probability P(Y |X). Since no assumption is made about the underlying structure of the observations X, the model is able to incorporate a rich set of non-independent overlapping features of the observations. In the context of images, various authors have successfully applied CRFs for classification tasks and have reported significant improvement over the MRF based generative models [He et al., 2004; Kumar and Hebert, 2003].

Discriminative Random Fields (DRFs) which closely resemble CRFs have been applied for the task of detecting manmade structures in real world images [Kumar and Hebert, 2003]. Though the model outperforms traditional MRFs, it is not strong enough to capture long range correlations among the labels due to the rigid lattice based structure which allows for only pairwise interactions. [He et al., 2004] propose Multiscale Conditional Random Fields (mCRFs) which are capable of modeling interactions among the labels over multiple scales. Their work consists of a combination of three different classifiers operating at local, regional and global contexts respectively. However, it suffers from two main drawbacks

• Including additional classifiers operating at different scales into the mCRF framework introduces a large number of model parameters.
• The model assumes conditional independence of hidden variables given the label field.

Though a number of generative hierarchical models have been proposed, similar work involving discriminative frameworks is limited [Kumar and Hebert, 2005]. In this paper we propose a Tree Structured Conditional Random Field (TCRF) for modeling images. Our results demonstrate that TCRF is able to capture long range label relationships and is robust enough to be applied to different classification tasks. The primary contribution of our work is a method which combines the advantages offered by hierarchical models and discriminative approaches in a single framework. The rest of the paper is organized as follows: We formally present our framework in Section 2. In the section we also discuss the graph structure and the form of the probability distribution. Training and inference for a TCRF are discussed in sections 3 and 4 respectively. We present the results of our model on two different tasks in section 5. A few possible extensions to our framework are discussed in section 6. We finally conclude in section 7.

2 Tree Structured Conditional RandomField

Let X be the observations and Y the corresponding labels. Before presenting our framework we first state the definition of Conditional Random Fields as given by [Lafferty et al., 2001].

2.1 CRF Definition

Let G = (V,E) be a graph such that Y is indexed by the vertices of G. Then (X,Y) is a conditional random field if, when conditioned on X, the random variables yi ∈ Y obey the Markov property with respect to the graph: p(yi |X, yj, i ̸= j) = p(yi |X, yj, i ∼ j). Here i ∼ j implies that yi and yj are neighbors in G.

By applying the Hammersley-Clifford theorem [Li, 2001], the conditional probability p(Y | X) factors into a product of potential functions. These real valued functions are defined over the cliques of the graph G.

In the above equation C is the set of cliques of the graph G, yc is the set of variables in Y which belong to the clique c and Z is a normalization factor.

2.2 TCRFGraph Structure

Consider a 2 ×2 neighborhood of pixels as shown in Figure 2. One way to model the association between the labels of these pixels is to introduce a weight vector for every edge (u, v) which represents the compatibility between the labels of the nodes u and v (Figure 2a). An alternative is to introduce a hidden variable H which is connected to all the 4 nodes. For every value which variable H takes, it induces a probability distribution over the labels of the nodes connected to it (Figure 2b).

Dividing the whole image into regions of size m×m and introducing a hidden variable for each of them gives a layer of hidden variables over the given label field. In such a configuration each label node is associated with a hidden variable in the layer above. The main advantage of following such an approach is that long range correlations among non-neighboring pixels can be easily modeled as associations among the hidden variables in the layer above. Another attractive feature is that the resulting graph structure induced is a tree which allows inference to be carried out in a time linear in the number of pixels [Felzenszwalb and Huttenlocher, 2004]. Motivated by this, we introduce multiple layers of hidden variables over the given label field. Each layer of hidden variables tries to capture label relationships at a different level of scale by affecting the values of the hidden variables in the layer below. In our work we take the value of m to be equal to 2. The quadtree structure of our model is shown in Figure 3.

Formally, let Y be the set of label nodes, X the set of observations and H be the set of hidden variables. We call ({Y,H},X) a TCRF if the following conditions hold:

1. There exists a connected acyclic graph G = (V , E) whose vertices are in one-to-one correspondence with the variables in Y ∪ H, and whose number of edges |E| = |V | - 1.
2. The node set V can be partitioned into subsets (V1 , V2 , . . . , VL) such that ⋃i Vi = V , Vi ∩ Vj = ∅ and the vertices in VL correspond to the variables in Y.
3. deg(v) = 1, ∀v ∈ VL.

Similar to CRFs, the conditional probability P(Y,H|X) of a TCRF factors into a product of potential functions. We next describe the form of these functions.

2.3 Potential Functions

Since the underlying graph for a TCRF is a tree, the set of cliques C corresponds to nodes and edges of this graph. We define two kinds of potentials over these cliques:

Local Potential

This is intended to represent the influence of the observations X on the label nodes Y. For every yi ∈ Y this function takes the form exp(Γi(yi,X)). Γi(yi,X) can be defined as

Let L be the number of classes and F be the number of image statistics for each block. Then yi is a vector of length L, W is a matrix of weights of size L × F estimated from the training data and f(.) is a transformation (possibly nonlinear) applied to the observations. Another approach is to take Γi(yi,X) = logP(yi |X), where P(yi |X) is the probability estimate output by a separately trained local classifier [He et al., 2006].

Edge Potential

This is defined over the edges of the tree. Let φt,b be a matrix of weights of size L × L which represents the compatibility between the values of a hidden variable at level t and its bth neighbor at level t+1. For our quad-tree structure b = 1, 2, 3 or 4. Let L denote the number of levels in the tree, with the root node at level 1 and the image sites at level L and Ht denote the set of hidden variables present at level t. Then for every edge (hi, yj) such that hi ∈ HL-1 and yj ∈ Y the edge potential can be defined as exp(hTi φL-1,byj). In a similar manner the edge potential between the node hi at level t and its bth neighbor hj at level t + 1 can be represented as exp(hTi φt,bhj).

The overall joint probability distribution which is a product of the potentials defined above can be written as

3 Parameter Estimation

Given a set of training images T = {(Y1, X1) . . . (YN , XN)} we want to estimate the parameters Θ = {W, Φ}. A standard way to do this is to maximize the conditional log-likelihood of the training data. This is equivalent to minimizing the Kullback-Leibler (KL) divergence between the model distribution P(Y|X,Θ) and the empirical distribution Q(Y|X) defined by the training set. The above approach, requires calculating expectations under the model distribution. These expectations are approximated using Markov Chain Monte Carlo (MCMC) methods. As pointed by [Hinton, 2002], these methods suffer from two main drawbacks

1. The Markov chain takes a long time to reach the equilibrium distribution.
2. The estimated gradients tend to be noisy, i.e. they have a high variance.

Contrastive Divergence (CD) is an approximate learning method which overcomes this problem by minimizing a different objective function [Hinton, 2002]. In this work we use CD learning for estimating the parameters.

3.1 Contrastive Divergence Learning

Let P be the model distribution and Q0 be the empirical distribution of label variables. CD learning tries to minimize the contrastive divergence which is defined as

where Q ‖ P = ∑y∈Y Q(y) log Q(y) P(y) is the KullbackLeibler divergence between Q & P. Q1 is the distribution defined by the one step reconstruction of the training data vectors [Hinton, 2002]. For any weight wij ,

where η is the learning rate. Let Y1 be the one step reconstruction of training set Y0 . The weight update equations specific to our model are

4 Inference

The problem of inference is to find the optimal label field Y∗ = argmaxYP(Y|X). This can be done using the maximum posterior marginals (MPM) criterion which minimizes the expected number of incorrectly labeled sites. According to theMPMcriterion, the optimal label for pixel i, y∗i is given as

Due to the tree structure of our model the probability value P(yi |X) can be exactly calculated using Belief Propagation [Pearl, 1988].

5 Experiments and Results

In order to evaluate the performance of our model, we applied it to two different classification tasks, namely, object detection and image labeling. Our main aim was to demonstrate the ability of TCRF in capturing the label relationships. We have also compared our approach with the existing techniques both qualitatively and quantitatively. The predicted label for each block is assigned to all the pixels contained within it. This is done in order to compare the performance against models like mCRF which operate directly at the pixel level. We use a common set of local features as described next.

5.1 Feature Extraction

Visual contents of an image such as color, texture, and spatial layout are vital discriminatory features when considering real world images. For extracting the color information we calculate the first three color moments of an image patch in the CIEL∗a∗ b∗ color space.

We incorporate the entropy of a region to account for its randomness. A uniform image patch has a significantly lower entropy value as compared to a non-uniform patch. Entropy is calculated as shown in Equation 10

where, p contains the histogram counts. Texture is extracted using the discrete wavelet transform [Mallat, 1996]. Spatial layout is accounted for by including the coordinates of every image site. This in all accounts for a total of 20 statistics corresponding to one image region.

5.2 Object Detection

We apply our model to the task of detecting man-made structures in a set of natural images from the Corel image database. Each image is 256 × 384 pixels. We divide each image into blocks of size 8 × 12. Each block is labeled as either structured or unstructured. These blocks correspond to the leaf nodes of the TCRF. In order to compare our performance with DRFs, we use the same set of 108 training and 129 testing images as used by [Kumar and Hebert, 2003]. We also implement a simple Logistic Regression (LR) based classifier in order to demonstrate the performance improvement obtained by capturing label relationships. As shown in Table 1, TCRF achieves significant improvement over the LR based classifier which considers only local image statistics into account. Figure 4 shows some the results obtained by our model.

5.3 Image Labeling

We now demonstrate the performance of our model on labeling real world images. We took a set of 100 images consisting of wildlife scenes from the Corel database. The dataset contains a total of 7 class labels: rhino/hippo, polar bear, vegetation, sky, water, snow and ground. This is a data set with high variability among images. Each image is 128 × 192 pixels. We divide each image into blocks of size 4 × 6. A total of 60 images were chosen at random for training. The remaining

1 This score as reported by [Kumar and Hebert, 2003] was obtained by using a different region size.

40 images were used for testing. We compare our results with that of a logistic classifier and our own implementation of the mCRF [He et al., 2004]. It can be observed from Table 2 that TCRF significantly improves over the logistic classifier by modeling the label interactions. Our model also outperforms the mCRF on the given test set. Qualitative results on some of the test images are shown in Figure 5.

6 Discussion

The framework proposed in this paper falls into the category of multiscale models which have been successfully applied by various authors [Bouman and Shapiro, 1994; Feng et al., 2002]. The novelty of our work is that we extend earlier hierarchical approaches to incorporate them into a discriminative framework based on conditional random fields. There are several immediate extensions possible to the basic model presented in this work. One of them concerns with the "blocky" nature of the labelings obtained. The reason for this is the fixed region size which is used in our experiments. This behavior is typical of tree based models like TSBNs. One solution to this problem is to directly model image pixels as the leaves of the TCRF. This would require increasing the number of levels of the tree. Although the number of model parameters increase only linearly with the number of levels, training and inference times can increase exponentially with the number of levels. Recently, He et al. have reported good results by applying their model over a super-pixelized representation of the image [He et al., 2006]. This approach reduces the number of image sites and at the same time does not define rigid region sizes. We are currently exploring the possibility of incorporating super-pixelization into the TCRF framework.

7 Conclusions

We have presented TCRF, a novel hierarchical model based on CRFs for incorporating contextual features at several levels of granularity. The discriminative nature of CRFs combined with the tree like structure gives TCRFs several advantages over other proposed multiscale models. TCRFs yield a general framework which can be applied to a variety of image classification tasks. We have empirically demonstrated that a TCRF outperforms existing approaches on two such tasks. In future we wish to explore other training methods which can handle larger number of parameters. Further we need to study how our framework can be adapted for other image classification tasks.