In energy minimization, belief propagation (BP) (Pearl 1982; Yedidia *et al.* 2003) and graph cut (GC) (Boykov *et al.* 2001; Felzenszwalb and Zabih 2011) are two important algorithms that can be used to solve many intermediate vision problems. These two algorithms are general problem solvers, showing duality and, in many aspects, evolving competitively in performance, computational speed, and generality. BP is an excellent general solver, especially for MRF factor graphs because it guarantees reasonable solutions even for loopy graphs. This method models the system as a joint pmf given by the energy function, estimates marginals, and iteratively propagates messages between neighbors to enhance beliefs. Upon convergence, each node contains a belief that is the score of the marginal states. The computational structure is inherently parallel because all the operations are local and concurrent. However, because of the vector variables and matrix priors, this method involves significant computation and storage, which are usually beyond the capacities of serial computers, for real-time computation.

GC is an excellent general solver for graph problems and returns remarkably accurate solutions. It models the system as a flow graph, in which a graph cut is equivalent to the energy, and thus searches for the min-cut using the standard max-flow min-cut algorithms. It solves the problem of multiple labels by first converting the ...

Start Free Trial

No credit card required