This thesis develops a new geometric optimisation framework that can provide significant improvements over both traditional active contour and graph-based approaches to image segmentation. It combines active contour and graph-based methods to produce powerful image segmentation methods sharing their strengths: continuity and reliability.
We begin by reviewing the relevant literature in image segmentation and in geometric optimisation. This includes the role of image derivatives in segmentation, active contour methods such as snakes and level sets, and graph-based methods such as shortest paths and minimum cuts. We also discuss hybrid methods which combine the best properties of active contours and graph-based methods. Finally we introduce a previously unsolved problem that is central to this thesis: the computation of globally minimal surfaces in continuous spaces.
We then investigate the recursive computation of derivatives in finite and discrete images. Previous approaches to recursive filtering are reviewed including convolution and Fourier methods. A matrix viewpoint is put forward which deals naturally with image boundaries. We give an efficient decomposition and solution for this matrix formulation. It is proven to exist for stable filters and shown both in theory and practice to have good accuracy in finite precision implementations. We demonstrate its application to the fast computation of image derivatives at arbitrary scales.
Next we consider in detail the segmentation of planar images by optimal curves. First we give a simple technique for object segmentation by a minimal convex polygon. We then extend this technique to continuous curves, convoluted boundaries, and oriented metrics. Experiments demonstrate that the optimality of these techniques produces significantly more accurate and robust segmentations than standard active contour methods. An application is given to the segmentation of the left ventricle in the heart from multiple-slice magnetic resonance image sequences.
Finally, we propose a general method for segmentation by globally minimal surfaces in higher dimensions. This method is based on the computation of a continuous maximal flow whose bottleneck forms the globally minimal surface. We investigate its behaviour in planar images and show that it is equivalent to our method for obtaining optimal continuous curves. We also develop a general scheme for removing the bias of minimal surfaces toward small objects. Unlike existing graph-based or active contour methods the new minimal surface method is simultaneously optimal and grid-invariant whilst being more efficient than either method. Results in 2D and 3D image segmentation and in stereo reconstruction demonstrate the practical benefits which are predicted by the theoretical properties of globally minimal surfaces. An application is given to the segmentation of physiological structures in the brain from volumetric magnetic resonance images.