Slides are available by following the link.
Curvature is a high order non-submodular regularizer known to be very useful in vision.
We propose a new discrete MRF model for approximating curvature using small patches either on a pixel grid or a cell complex. In case of a grid, our patches use a novel integral geometry approach to evaluate curvature. In case of a complex, our patches use standard geometry similar to previous methods for curvature. We propose a very simple and efficient optimization technique using "partial enumeration" to reduce our high-order curvature energy to a pairwise Constraint Satisfaction Problem with unary costs (uCSP). We evaluate a number of existing algorithms applicable to this NP-hard pairwise optimization problem. Our efficient modification of TRW-S for uCSP gave the best results: near global minimum and better speed when compared to previous MRF-based models. In general, partial enumeration and reduction to uCSP are easy to implement and apply to other high-order problems, e.g. they generate state-of-the-art results for second-order stereo and deconvolution energies known to be difficult.
This is a joint work with Carl Olsson.