Abstract

Energy minimization algorithms, such as graph cuts, enable the computation of the MAP solution under certain probabilistic models such as Markov random fields. However, for many computer vision problems, the MAP solution under the model is not the ground truth solution. In many problem scenarios, the system has access to certain statistics of the ground truth. For instance, in image segmentation, the area and boundary length of the object may be known. In these cases, we want to estimate the most probable solution that is consistent with such statistics, i.e., satisfies certain equality or inequality constraints. In this work, we propose novel algorithms for inferring the Maximum a Posteriori (MAP) solution of discrete pairwise random field models under multiple constraints. We show how this constrained discrete optimization problem can be formulated as a multi-dimensional parametric mincut problem via its Lagrangian dual, and prove that our algorithm isolates all constraint instances for which the problem can be solved exactly. These multiple solutions enable us to even deal with `soft constraints’ (higher order penalty functions). Moreover, we propose practical variants of our algorithm to solve problems with hard constraints. We also show how our method can be applied to solve various constrained discrete optimization problems such as submodular minimization and shortest path computation. We demonstrate the efficacy of our algorithms on the foreground/background image segmentation problem, and show that it produces impressive segmentation results with less error, and runs more than 10 times faster than the state-of-the-art LP relaxation based approaches. This is a joint work with Yongsub Lim and Pushmeet Kohli.