This paper addresses the problem of exactly inferring the maximum a posteriori
solutions of discrete multi-label MRFs or CRFs with higher order cliques. We
present a framework to transform special classes of multi-label higher order
functions to submodular second order boolean functions (referred to as 
${\cal F}_s^2$), which can be minimized exactly using graph cuts and we
characterize those classes. The basic idea is to use two or more boolean
variables to encode the states of a single multi-label variable. There are many
ways in which this can be done and much interesting research lies in finding
ways which are optimal or minimal in some sense. We study the space of possible
encodings and find the ones that can transform the most general class of
functions to ${\cal F}_s^2$. Our main contributions are two-fold. First, we
extend the subclass of submodular energy functions that can be minimized exactly
using graph cuts. Second, we show how higher order potentials can be used to
improve single view 3D reconstruction results. We believe that our work on exact
minimization of higher order energy functions will lead to similar improvements
in solutions of other labelling problems.