A Graph Reduction Method for 2D Snake Problems

Abstract

Energy-minimizing active contour models (snakes) have been proposed for solving many computer vision problems such as object segmentation, surface reconstruction, and object tracking. Dynamic programming which allows natural enforcement of constraints is an effective method for computing the global minima of energy functions. However, this method is only limited to snake problems with one dimensional (ID) topology (i.e., a contour) and cannot handle problems with two-dimensional (2D) topology. In this paper, we have extended the dynamic programming method to address the snake problems with 2D topology using a novel graph reduction algorithm. Given a 2D snake with first order energy terms, a set of reduction operations are defined and used to simplify the graph of the 2D snake into one single vertex while retaining the minimal energy of the snake. The proposed algorithm has a polynomial-time complexity bound and the optimality of the solution for a reducible 2D snake is guaranteed. However, not all types of 2D snakes can be reduced into one single vertex using the proposed algorithm. The reduction of general planar snakes is an NP-complete problem. The proposed method has been applied to optimize 2D building topology extracted from airborne LIDAR data to examine the effectiveness of the algorithm. The results demonstrate that the proposed approach successfully found the global optima for over 98% of building topology in a polynomial time.