Using Dynamic Programming For Minimizing The Energy Of Active Contours In The Presence Of Hard Constraints

Abstract

Energy-Minimizing Active Contour Models (snakes) have recently been proposed by Kass et al. [8] as a top-down mechanism for locating features of interest in images. The Kass et al.’s algorithm involves four steps: setting up a variational integral on the continuous plane, deriving a pair of Euler equations, discretizing them, and solving the discrete equations iteratively until convergence. This algorithm suffers from a number of problems. We discuss these problems and present an algoIithm for active contours based on dynamic programming. The optimization problem is set up as a discrete multi-stage decision process and is solved by a “time-delayed” discrete dynamic programming algorithm. This formulation leads to a stable behavior for the active contours over iterations, in addition to allowing for hard constraints to be enforced on the behavior of the solution. Results of the application of the proposed algorithm to real images is presented.