  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.
  The above constrained energy minimization problem is NP-hard in general, and
is usually solved using Linear Programming formulations, which relax the
integrality constraints. This paper proposes a novel method that finds the
discrete optimal solution of such problems by maximizing the corresponding
Lagrangian dual. This method can be applied to any constrained energy
minimization problem whose unconstrained version is polynomial time solvable,
and can handle multiple, equality or inequality, and linear or non-linear
constraints. We demonstrate the efficacy of our method on the
foreground/background image segmentation problem, and show that it produces
impressive segmentation results with less error, and runs more than 20 times
faster than the state-of-the-art LP relaxation based approaches.
