M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

TALKS

TEACHING

CV

 

 

 

 

 

 

Notation

An example MRF with two random variables and two labels.
The optimization variables corresponding to the MRF.

 

The above example illustrates our notation. The random variables are shown as unfilled circles. The labels are shown as trellises over the random variables. Each branch of the trellis represents one label. The unary potential of a random variable Va taking a label li is shown next to the ith branch of the trellis on top of Va. The pairwise potential for variables Va and Vb taking labels li and lj respectively is shown next to the connection between the ith and jth branches of Va and Vb respectively.

Similarly, the optimization variable corresponding to a random variable Va taking a label li is shown next to the ith branch of the trellis on top of Va. The pairwise optimization variable for variables Va and Vb taking labels li and lj respectively is shown next to the connection between the ith and jth branches of Va and Vb respectively.

Integer Programming Formulation

Integer Program

 

The variable xa(i) is equal to 1 if Va takes the label li and -1 otherwise. The objective function represents the energy of the labeling specified by x. The first constraints ensures that each random variables is assigned exactly one label (here h is the number of labels). The other two constraints specify that the optimization variables should take integer values.