A Multigrid Approach For Minimizing A Nonlinear Functional For Digital Image Matching

Kristian Witsch
Stefan Henn
Heinrich Heine Universität Düsseldorf, Germany }


We consider an application of multilevel methods to medical imaging. The specific problem arises in the processing of images of the human brain. Two different 3D grey scale images have to be matched: the first one is a histological, high resolution image with distortions called the template T(x). The other one a MRT image called the reference R(x) which provides only macroscopical resolution, but the true geometry. One looks for a displacement field u which yields optimally matched images. The difference of the two images is measured by their L2 difference:

D(u) = IntegralOmega (T( x - u(x) ) - R(x))2 dOmega,
and should be minimized. This yields an ill conditioned inverse problem for the displacement field u. Due to physical considerations, a regularizing term proportional to the elastic energy a(u,u) of the deformation is added. Therefore a functional of the form
J(u) = a(u,u) + D(u)
has to be minimized. The corresponding Euler equations are a nonlinear coupled system of boundary value problems. It is discretized by finite differences. We describe numerical results for different treatments of the nonlinearity (e.g. steepest descent methods with 1D minimization, FAS and different relaxation methods) coupled with a multigrid method.

Since the functional may have many local minima a multilevel nested iteration approach is essential to find suitable - hopefully global - minima. In this case the images were be transformed on a coarser resolution. On this resolution only the low frequencies of the images were presented. Now we start the minimization process on this resolution and interpolate the resulting displacement fields on the next finer resolution level, where the minimization process is performed again. This procedure is repeated until the finest level is reached. Now we have a suitable starting point on the finest resolution and the minimization process can be finished.

This approach has resulted in a substantial reduction of computing times and has made possible to treat the 3D problem. Further reduction of the processing time is possible by parallelization. We describe results for an implementation using KeLP as a basic tool.