Efficient multigrid solver for the 3D random walker algorithm

The random walker algorithm is a graph-based segmentation method that has become popular over the past fewyears. The basis of the algorithm is a large, sparsely occupied system of linear equations, whose size correspondsto 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 longersatisfactory. An alternative method that has been described previously for solving 2D random walker problemsis the geometrical multigrid method. In this paper, we present a geometrical multigrid approach for the 3Drandom walker problem. Our approach features an optimized calculation of the required Galerkin product anda robust smoothing using the ILU method. To reach better convergence rates, the multigrid solver is used as apreconditioner for the conjugate gradient solver. We co mpared the performance of our new multigrid approachwith the conjugate gradient solver on “ve MRI lung images with a resolution of 96 × 128 × 52 voxels. Initialresults show an increasing in speed of up to four times, reducing the average computation time from six minutesto less than two minutes when using our proposed approach. Employing a multigrid solver for the random walkeralgorithm thus permits accurate interactive segmentation with fewer delays.Keywords: segmentation, random walker, multigrid