 |
    |
Pseudo-bound Optimization for Binary Energies
Meng Tang1, Ismail Ben Ayed1, 2, and Yuri Boykov1
1University of Western Ontario, Canada
2GE Healthcare, Canada
Abstract. High-order and non-submodular pairwise energies are important for image segmentation, surface matching, deconvolution, tracking and other computer vision problems. Minimization of such energies is generally NP-hard. One standard approximation approach is to optimize an auxiliary function - an upper bound of the original energy across the entire solution space. This bound must be amenable to fast global solvers. Ideally, it should also closely approximate the original functional, but it is very difficult to find such upper bounds in practice.
Our main idea is to relax the upper-bound condition for an auxiliary function and to replace it with a family of pseudo-bounds, which can better approximate the original energy. We use fast polynomial parametric maxflow approach to explore all global minima for our family of submodular pseudo-bounds. The best solution is guaranteed to decrease the original energy because the family includes at least one auxiliary function. Our Pseudo-Bound Cuts algorithm improves the state-of-the-art in many applications: appearance entropy minimization, target distribution matching, curvature regularization, image deconvolution and interactive segmentation.
Keywords: Binary energy minimization, high-order and non-submodular functions, auxiliary functions, parametric maxflow, pseudo-bounds
LNCS 8693, p. 691 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014