  Most image labeling problems such as segmentation and image reconstruction
are fundamentally ill-posed and suffer from ambiguities and noise. Higher order
image priors encode high level structural dependencies between pixels and are
key to overcoming these problems. However, these priors in general lead to
computationally intractable models. This paper addresses the problem of
discovering compact representations of higher order priors which allow
efficient inference. We propose a framework for solving this problem which uses
a recently proposed representation of higher order functions where they are
encoded as lower envelopes of linear functions. Maximum a Posterior inference
on our learned models reduces to minimizing a pairwise function of discrete
variables, which can be done approximately using standard methods. Although
this is a primarily theoretical paper, we also demonstrate the practical
effectiveness of our framework on the problem of learning a shape prior for
image segmentation and reconstruction. We show that our framework can learn a
compact representation that approximates a prior that encourages low curvature
shapes. We evaluate the approximation accuracy, discuss properties of the
trained model, and show various results for shape inpainting and image
segmentation.
