Globally optimal image segmentation with an elastic shape prior

So far global optimization techniques have been developed independently for the tasks of shape matching and image segmentation. In this paper we show that both tasks can in fact be solved simultaneously using global optimization. By computing cycles of minimal ratio in a large graph spanned by the product of the input image and a shape template, we are able to compute globally optimal segmentations of the image which are similar to a familiar shape and located in places of strong gradient. The presented approach is translation-invariant and robust to local and global scaling and rotation of the given shape. We show how it can be extended to incorporate invariance to similarity transformations. The particular structure of the graph allows for run-time and memory efficient implementations. Highly parallel implementations on graphics cards allow to produce globally optimal solutions in a few seconds only.