Architectures for Computer Vision: From Algorithm to Chip with Verilog

9 Dynamic Programming for Energy Minimization

As is the case with the relaxation algorithm and the BP algorithm, dynamic programming (DP) (Bellman 1954) is an important algorithm that can solve, under general settings, many problems in energy functions (Amini et al. 1990; Felzenszwalb and Zabih 2011). Dynamic programming is extremely fast and uses less memory space than other algorithms, but unfortunately, DP can only solve one-dimensional problems, such as line-by-line processing, until it finds local optimal solutions. Given that DP can only solve one-dimensional problems, this type of algorithm is especially useful for stereo matching, where the search space is limited to the epipolar line (Gong and Yang 2005; Jeong and Yuns 2000; Ohta and Kanade 1985). DP is also an important construct of the hidden Markov model (HMM), where hidden states must be recovered in decoding problems.

In this chapter, we study DP as a method for solving energy minimization problems. In addition to standard DP, we study various forms of DP: parallel DP, serial DP, and extended DP (EDP). Parallel and serial DPs are designed for extracting multiple best solutions in parallel and in series, respectively. The extended DP is tailored to solve multiple image lines by introducing the product space. We also study HMM and the inside-outside algorithm, which can be used in higher-level processing, such as image interpretation or image understanding.

In this chapter, we will examine the computation structures ...