Interactive segmentation of non-star-shaped contours by dynamic programming

In this paper we present the Rack algorithm for the detection of optimal non-star-shaped contours in images. It is based on the combination of a user-driven image transformation and dynamic programming. The fundamental idea is to interactively specify and edit the general shape of the desired object by using a rack. This rack is used to model the image as a directed acyclic weighted graph that contains a path corresponding to the expected contour. In this graph, the shortest path with respect to an adequate cost function can be calculated efficiently via dynamic programming. The experimental results indicate the algorithm's ability of combining an acceptable amount of user interaction with generally good segmentation results.