High-order and nonsubmodular 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 optimizean auxiliary function - an upper bound of the original energy across the entire solution space, which must be amenable to fast global solvers. Ideally, this bound 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 max-flow 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 one proper auxiliary function. Our Pseudo-Bound Cuts method improves the state-of-the-art in many examples: entropy minimization, target distribution matching, curvature regularization, and interactive segmentation (grab-cut database).