Dynamic programming on the multidimensional grid and fast search algorithm for energy minimization in stereo and optical flow
In this paper, a recursive algorithm that considerably reduces the computational complexity of the minimum search problem is presented. The mentioned reduction is particularly signi cant if the disparity space is 2D or 3D. The proposed method can be applied in the well-known dynamic programming (DP) approach for stereo and motion. In this case the general 2D problem of the global discrete energy minimization is reduced to several mutually independent sub-problems of the one-dimensional minimization and the exact solution is obtained for each sub-problem. A new modi cation of the DP techniques that we call extended dynamic programming for energy minimization (EDP) is also presented in this paper. The EDP method is used, if the approximation of the general 2D discrete energy minimization problem is considered. Then the proposed recursive minimum search (RMS) algorithm is an essential part of the EDP method. Using the EDP algorithm we obtain a lower energy than the graph cuts expansion technique on stereo and motion problems. The proposed calculation scheme possesses natural parallelism and can be realized on the graphics processing unit (GPU) platform, and potentially can be restricted further by the number of scanlines in the image plane. Furthermore, the RMS and EDP methods can be used in any optimization problem, which objective function meets speci c conditions in the smoothness term.