  Superpixels have become prevalent in computer vision. They have been used to
achieve satisfactory performance at a significantly smaller computational cost
for various tasks. People have also combined superpixels with Markov random
field (MRF) models. However, it often takes additional effort to formulate MRF
on superpixel-level, and to the best of our knowledge there exists no
principled approach to obtain this formulation. In this paper, we show how
generic pixel-level binary MRF model can be solved in the superpixel space. As
the main contribution of this paper, we show that a superpixel-level MRF can be
derived from the pixel-level MRF by substituting the superpixel representation
of the pixelwise label into the original pixel-level MRF energy. The resultant
superpixel-level MRF energy also remains submodular for a submodular
pixel-level MRF. The derived formula hence gives us a handy way to formulate
MRF energy in superpixel-level. In the experiments, we demonstrate the efficacy
of our approach on several computer vision problems.
