Using Dynamic Programming for Solving Variational Problems in Vision

Abstract

Variational approaches have been proposed for solving many inverse problems in early vision, such as in the computation of optical flow, shape from shading, and energy-minimizing active contour models. In general however, variational approaches do not guarantee global optimality of the solution, require estimates of higher order derivatives of the discrete data, and do not allow direct and natural enforcement of constraints.

In this paper we discuss dynamic programming as a novel approach to solving variational problems in vision. Dynamic programming ensures global optimality of the solution, it is numerically stable, and it allows for hard constraints to be enforced on the behavior of the solution within a natural and straightforward structure. As a specific example of the efficacy of the proposed approach, application of dynamic programming to the energy-minimizing active contours is described. The optimization problem is set up as a discrete multistage decision process and is solved by a "time-delayed" discrete dynamic programming algorithm. A parallel procedure is discussed that can result in savings in computational costs.