Minimizing Energy Functions on 4-Connected Lattices Using Elimination
Here, we present an algorithm which is capable of handling any pseduo-boolean energy function, as long as it is defined over the standard four-connect neighbourhood. Our algorithm produces an approximate minimum configuration (recall that energy minimization is NP-hard in general) by eliminating variables from the energy function. After each elimination, the resulting expression becomes more complex (and typically contains higher order terms), which makes successive eliminations infeasible. Instead, we approximate the resulting energy expression as a particular quadratic pseduo-boolean function. The algorithm has a similar run-time to that of graph cuts/max-flow, and achieves good experimental results in practice.
