Using dynamic programming for solving variational problems in vision: applications involving deformable models for contours and surfaces.
Amir A. Amini, Terry E. Weymouth, David J. Anderson · Deep Blue (University of Michigan) · 1990
Two separate vision problems are considered in this thesis. The problem of extracting image contours, and the problem of reconstruction of surfaces from stereo disparities. The central concepts in this study are dynamic programming, and deformable models. For both contour extraction and surface reconstruction, appropriate deformable models are introduced, and the models are optimized using dynamic programming. A new class of deformable contours is described. These contours, dubbed inflating/deflating contours have the capability of growing or shrinking and thus attaching to object boundaries from the inside or attaching to object boundaries from the outside. The dynamic programming formulation leads to a stable behavior for the contours over iterations, in addition to allowing for hard constraints to be enforced on the behavior of the solution. We illustrate experimental results in order to quantify the applicability of the inflating/deflating contour algorithm. Extension of dynamic programming to two dimensions is discussed. Based on the extension of the theory to two dimensions, a discrete algorithm for reconstruction of surfaces from stereo disparities is developed. Discontinuity preserving surface reconstruction is accomplished in two stages. In the first stage, using an extension of an algorithm due to Blake, local discontinuities in sparse depth data are located. In the second stage, the minimal energy surface which corresponds to the shortest route in a network of nodes is reconstructed using the output of the first stage of the algorithm as hard constraints in the reconstruction. Within this framework, the set of admissible surfaces is created with deformable signals. A possible method for parallel implementation of dynamic programming applicable to both contours and surfaces is also discussed.