O'Reilly logo

Architectures for Computer Vision: From Algorithm to Chip with Verilog by Hong Jeong

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required