Discriminative Random Fields: A Discriminative Framework for ContextualInteraction in ClassificationSanjiv Kumar and Martial HebertThe Robotics Institute, Carnegie Mellon UniversityPittsburgh, PA 15213, USA, {skumar, hebert}@ri.cmu.eduAbstractIn this work we present Discriminative Random Fields(DRFs), a discriminative framework for the classification ofimage regions by incorporating neighborhood interactionsin the labels as well as the observed data. The discrimi-native random fields offer several advantages over the con-ventional Markov Random Field (MRF) framework. First,the DRFs allow to relax the strong assumption of condi-tional independence of the observed data generally used inthe MRF framework for tractability. This assumption is toorestrictive for a large number of applications in vision. Sec-ond, the DRFs derive their classification power by exploit-ing the probabilistic discriminative models instead of thegenerative models used in the MRF framework. Finally, allthe parameters in the DRF model are estimated simulta-neously from the training data unlike the MRF frameworkwhere likelihood parameters are usually learned separatelyfrom the field parameters. We illustrate the advantages ofthe DRFs over the MRF framework in an application ofman-made structure detection in natural images taken fromthe Corel database.1. IntroductionThe problem of region classification, i.e. segmentationand labeling of image regions is of fundamental interestin computer vision. For the analysis of natural images, itis important to use the contextual information in the formof spatial dependencies in the images. Markov RandomField (MRF) models have been used extensively for vari-ous segmentation and labeling applications in vision, whichallow one to incorporate contextual constraints in a princi-pled manner [15].MRFs are generally used in a probabilistic generativeframework that models the joint probability of the observeddata and the corresponding labels. In other words, let y bethe observed data from an input image, where y = {yi}i∈S,yiis the data from the ithsite, and S is the set of sites.Let the corresponding labels at the image sites be given byx = {xi}i∈S. In the MRF framework, the posterior overthe labels given the data is expressed using the Bayes’ ruleas,P (x|y) ∝ p(x, y) = P (x)p(y|x)where the prior over labels, P (x) is modeled as a MRF.For computational tractability, the observation or likeli-hood model, p(y|x) is assumed to have a factorized form,i.e. p(y|x) =Qi∈Sp(yi|xi) [1][4][15][22]. However, asnoted by several researchers [2][13][18][20], this assump-tion is too restrictive for several applications in vision. Forexample, consider a class that contains man-made structures(e.g. buildings). The data belonging to such a class is highlydependent on its neighbors. This is because, in man-madestructures, the lines or edges at spatially adjoining sites fol-low some underlying organization rules rather than beingrandom (See Figure 1 (a)). This is also true for a large num-ber of texture classes that are made of structured patterns.In this work we have chosen the application of man-madestructure detection purely as a source of data to show the ad-vantages of the Discriminative Random Field (DRF) model.Some efforts have been made in the past to model thedependencies in the data. In [11], a technique has been pre-sented that assumes the noise in the data at neighboring sitesto be correlated, which is modeled using an auto-normalmodel. However, the authors do not specify a field overthe labels and classify a site by maximizing the local poste-rior over labels given the data and the neighborhood labels.In probabilistic relaxation labeling, either the labels are as-sumed to be independent given the relational measurementsat two or more sites [3] or conditionally independent in lo-cal neighborhood of a site given its label [10]. In the contextof hierarchical texture segmentation, Won and Derin [21]model the local joint distribution of the data contained inthe neighborhood of a site assuming all the neighbors fromthe same class. They further approximate the overall likeli-hood to be factored over the local joint distributions. Wil-son and Li [20] assume the difference between observationsfrom the neighboring sites to be conditionally independentgiven the label field.In the context of multiscale random field, Cheng andBouman [2] make a more general assumption. They as-sume the difference between the data at a given site andthe linear combination of the data from that site’s parentsto be conditionally independent given the label at the cur-rent scale. All the above techniques make simplifying as-sumptions to get some sort of factored approximation of thelikelihood for tractability. This precludes capturing strongerrelationships in the observations in the form of arbitrarilycomplex features that might be desired to discriminate be-tween different classes. A novel pairwise MRF model issuggested in [18] to avoid the problem of explicit modelingof the likelihood, p(y|x). They model the joint p(x, y) asa MRF in which the label field P (x) is not necessarily aMRF. But this shifts the problem to the modeling of pairs(x, y). The authors model the pair by assuming the ob-servations to be the true underlying binary field corruptedby correlated noise. However, for most of the real-worldapplications, this assumption is too simplistic. In our previ-ous work [13], we modeled the data dependencies using apseudolikelihood approximation of a conditional MRF forcomputational tractability. In this work, we explore alter-native ways of modeling data dependencies which permiteliminating these approximations in a principled manner.Now considering a different point of view, for classifica-tion purposes, we are interested in estimating the posteriorover labels given the observations, i.e., P (x|y). In a gener-ative framework, one expends efforts to model the joint dis-tribution p(x, y), which involves implicit modeling of theobservations. In a discriminative framework, one modelsthe distribution P (x|y) directly. As noted in [4], a poten-tial advantage of using the discriminative approach is thatthe true underlying generative model may be quite complexeven though the class posterior is simple. This means thatthe generative approach may spend a lot of resources onmodeling the generative models which are not particularlyrelevant to the task of inferring the class labels. Moreover,learning the class density