Efficient multigrid solver for the 3D random walker algorithm

Xin Wang*, Tobias Heimann, Arne Naegel, Gabriel Wittum, Hans Peter Meinzer

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


The random walker algorithm is a graph-based segmentation method that has become popular over the past few years. The basis of the algorithm is a large, sparsely occupied system of linear equations, whose size corresponds to the number of voxels in the image. To solve these systems, typically comprised of millions of equations, the computational performance of conventional numerical solution methods (e.g. Gauss-Seidel) is no longer satisfactory. An alternative method that has been described previously for solving 2D random walker problems is the geometrical multigrid method. In this paper, we present a geometrical multigrid approach for the 3D random walker problem. Our approach features an optimized calculation of the required Galerkin product and a robust smoothing using the ILUβ method. To reach better convergence rates, the multigrid solver is used as a preconditioner for the conjugate gradient solver. We compared the performance of our new multigrid approach with the conjugate gradient solver on five MRI lung images with a resolution of 96 x 128 x 52 voxels. Initial results show an increasing in speed of up to four times, reducing the average computation time from six minutes to less than two minutes when using our proposed approach. Employing a multigrid solver for the random walker algorithm thus permits accurate interactive segmentation with fewer delays.

Original languageEnglish (US)
Title of host publicationMedical Imaging 2009 - Image Processing
StatePublished - 2009
Externally publishedYes
EventMedical Imaging 2009 - Image Processing - Lake Buena Vista, FL, United States
Duration: Feb 8 2009Feb 10 2009

Publication series

NameProgress in Biomedical Optics and Imaging - Proceedings of SPIE
ISSN (Print)1605-7422


OtherMedical Imaging 2009 - Image Processing
Country/TerritoryUnited States
CityLake Buena Vista, FL


  • Multigrid
  • Random walker
  • Segmentation

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Atomic and Molecular Physics, and Optics
  • Radiology Nuclear Medicine and imaging
  • Biomaterials


Dive into the research topics of 'Efficient multigrid solver for the 3D random walker algorithm'. Together they form a unique fingerprint.

Cite this