M. Pawan Kumar 
HOME

Notation
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 V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise potential for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Similarly, the optimization variable corresponding to a random variable V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise optimization variable for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Integer Programming Formulation
The variable x_{a}(i) is equal to 1 if V_{a} takes the label l_{i} 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.
