Architectures for Computer Vision: From Algorithm to Chip with Verilog

10 Belief Propagation and Graph Cuts for Energy Minimization

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 ...