Superdifferential Cuts for Binary Energies

Tatsunori Taniai1  Yasuyuki Matsushita2  Takeshi Naemura1
1The University of Tokyo, Japan
2Osaka University, Japan

CVPR 2015

Method overview



We propose an efficient and general purpose energy optimization method for binary variable energies used in various low-level vision tasks. Our method can be used for broad classes of higher-order and pairwise nonsubmodular functions. We first revisit a submodularsupermodular procedure (SSP) [Narasimhan05], which is previously studied for higher-order energy optimization. We then present our method as generalization of SSP, which is further shown to generalize several state-of-the-art techniques for higher-order and pairwise non-submodular functions [Ayed13, Gorelick14, Tang14]. In the experiments, we apply our method to image segmentation, deconvolution, and binarization, and show improvements over state-of-the-art methods.

Code is now availabe at GitHub.
See also Meng et al. "Pseudo-Bound Optimization for Binary Energies" (ECCV 2014) for data and code.

Paper PDF
Poster PDF

Supplementary Video


Generalization to prior methods

Proposed bound

Segmentation results via color histogram matching (Higher-order energies)

Segmentation results

Deconvolution results (Nonsubmodular pairwise energies)

Deconvolution results

Curvature-regularization results (Nonsubmodular pairwise energies)

Curvature-regularization results