Multigrid Geometric Active Contours


Figure 1. Texture segmentation example

Overview

Geometric active contour/snake models are very popular partial differential equation-based tools in image analysis and computer vision, with numerous applications such as image segmentation and moving object tracking. These models are conveniently implemented with level sets, but traditional level-set-based implementations have been notoriously slow.

We have developed novel multigrid algorithms for the fast evolution of level-set-based geometric active contours, which allow real-time performance on conventional PCs. We overcome the main bottleneck associated with most numerical implementations of geometric active contours, namely the need for very small time steps to avoid instability, by employing a very stable fully 2-D implicit-explicit time integration numerical scheme. The proposed scheme is more accurate and has improved rotational invariance properties compared with alternative split schemes, particularly when big time steps are utilized. We then apply properly designed multigrid methods to efficiently solve the occurring sparse linear system. The combined algorithm allows for the rapid evolution of the contour and convergence to its final configuration after very few iterations.

Key for the efficiency of the technique is the solution of a big sparse linear system with multigrid techniques, which attack the problem at multiple resolutions, in one of the schedules depicted on Figure 2:

Figure 2. Alternative multigrid schedules (MetaPost routine to generate similar graphs: mggraphs.mp).

The technique is applicable to a wide range of geometric active contour segmentation models; for example,

edge-based models such as Geodesic Active Contours,
texture-based models such as Region Competition or Geometric Active Regions — see Figure 1,
region-based models such as the Mumford-Shah or the Chan-Vese model — see Figure 3,
active contour models with prior information

can all be solved very efficiently with the proposed method.


Figure 3. Segmentation of the vocal tract

People

Publications

G. Papandreou and P. Maragos,
Multigrid Geometric Active Contour Models,
IEEE Transactions on Image Processing, vol. 16, no. 1, pp. 229-240, Jan. 2007.[pdf] [bib]
G. Papandreou and P. Maragos,
A Fast Multigrid Implicit Algorithm for the Evolution of Geodesic Active Contours,
Proc. Int’l Conf. on Computer Vision and Pattern Recognition (CVPR-2004), Washington DC, June 2004.[pdf] [bib]

Software

GAC++, a C++ toolbox for geometric active contours and other related PDE-based computer vision models, implements these ideas and can be found here.