SPARSE FINITE ELEMENTS FOR GEODESIC CONTOURS WITH LEVEL-SETS
Martin Weber, Andrew Blake and Roberto Cipolla
May 2004
Level-set methods have been shown to be an effective way to solve optimisation problems that involve closed curves. They are well known for their capacity to deal with flexible topology and do not require manual initialisation. Computational complexity has previously been addressed by using banded algorithms which restrict computation to the vicinity of the zero set of the level-set function. So far, such schemes have used finite difference representations which suffer from limited accuracy and require re-initialisation procedures to stabilise the evolution.
This paper shows how banded computation can be achieved using finite elements. We give details of the novel representation and show how to build the signed distance constraint into the presented numerical scheme. We apply the algorithm to the geodesic contour problem (including the automatic detection of nested contours) and demonstrate its performance on a variety of images.
The resulting algorithm has several advantages which are demonstrated in the paper: it is inherently stable and avoids re-initialisation; it is convergent and more accurate because of the capabilities of finite elements; it achieves maximum sparsity because with finite elements the band can be effectively of width 1.
If you have difficulty viewing files that end '.gz',
which are gzip compressed, then you may be able to find
tools to uncompress them at the gzip
web site.
If you have difficulty viewing files that are in PostScript, (ending
'.ps' or '.ps.gz'), then you may be able to
find tools to view them at
the gsview
web site.
We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.