An Adaptive Level Set Segmentation on a Triangulated Mesh

Meihe Xu, Paul M. Thompson, Arthur W. Toga

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


Level set methods offer highly robust and accurate methods for detecting interfaces of complex structures. Efficient techniques are required to transform an interface to a globally defined level set function. In this paper, a novel level set method based on an adaptive triangular mesh is proposed for segmentation of medical images. Special attention is paid to an adaptive mesh refinement and redistancing technique for level set propagation, in order to achieve higher resolution at the interface with minimum expense. First, a narrow band around the interface is built in an upwind fashion. An active square technique is used to determine the shortest distance correspondence (SDC) for each grid vertex. Simultaneously, we also give an efficient approach for signing the distance field. Then, an adaptive improvement algorithm is proposed, which essentially combines two basic techniques: a long-edge-based vertex insertion strategy, and a local improvement. These guarantee that the refined triangulation is related to features along the front and has elements with appropriate size and shape, which fit the front well. We propose a short-edge elimination scheme to coarsen the refined triangular mesh, in order to reduce the extra storage. Finally, we reformulate the general evolution equation by updating 1) the velocities and 2) the gradient of level sets on the triangulated mesh. We give an approach for tracing contours from the level set on the triangulated mesh. Given a two-dimensional image with N grids along a side, the proposed algorithms run in O(kN) time at each iteration. Quantitative analysis shows that our algorithm is of first order accuracy; and when the interface-fitted property is involved in the mesh refinement, both the convergence speed and numerical accuracy are greatly improved. We also analyze the effect of redistancing frequency upon convergence speed and accuracy. Numerical examples include the extraction of inner and outer surfaces of the cerebral cortex from magnetic resonance imaging brain images.

Original languageEnglish
Pages (from-to)191-201
Number of pages11
JournalIEEE Transactions on Medical Imaging
Issue number2
StatePublished - Feb 2004
Externally publishedYes


  • Adaptive improvement
  • Level set
  • MRI
  • Segmentation
  • Triangular mesh


Dive into the research topics of 'An Adaptive Level Set Segmentation on a Triangulated Mesh'. Together they form a unique fingerprint.

Cite this