  Energies with high-order non-submodular interactions have been shown to be
very useful in vision due to their high modeling power. Optimization of such
energies, however, is generally NP-hard. A naive approach that works for small
problem instances is exhaustive search, that is, enumeration of all possible
labelings of the underlying graph. We propose a general minimization approach
for large graphs based on enumeration of labelings of certain small patches.
This partial enumeration technique reduces complex high-order energy
formulations to pairwise Constraint Satisfaction Problems with unary costs
(uCSP), which can be efficiently solved using standard methods like TRW-S. Our
approach outperforms a number of existing state-of-the-art algorithms on well
known difficult problems (e.g. curvature regularization, stereo,
deconvolution); it gives near global minimum and better speed.
  Our main application of interest is curvature regularization. In the context
of segmentation, our partial enumeration technique allows to evaluate curvature
directly on small patches using a novel integral geometry approach.
