Efficient multigrid solver for the 3D random walker algorithm

Xin Wang; Tobias Heimann; Arne Naegel; Gabriel Wittum; Hans-Peter Meinzer

doi:10.1117/12.812821

27 March 2009 Efficient multigrid solver for the 3D random walker algorithm

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

Proceedings Volume 7259, Medical Imaging 2009: Image Processing; 72593R (2009) https://doi.org/10.1117/12.812821
Event: SPIE Medical Imaging, 2009, Lake Buena Vista (Orlando Area), Florida, United States

Abstract

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.

Citation Download Citation

Xin Wang, Tobias Heimann, Arne Naegel, Gabriel Wittum, and Hans-Peter Meinzer "Efficient multigrid solver for the 3D random walker algorithm", Proc. SPIE 7259, Medical Imaging 2009: Image Processing, 72593R (27 March 2009); https://doi.org/10.1117/12.812821

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available