Difference between revisions of "Projects:GroupwiseRegistration"

From NAMIC Wiki
Jump to: navigation, search
Line 1: Line 1:
  Back to [[NA-MIC_Collaborations|NA-MIC_Collaboration]], [[Algorithm:MGH|MGH Algorithms]], [[Algorithm:MIT|MIT Algorithms]]
+
  Back to [[NA-MIC_Collaborations|NA-MIC_Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
  
= Groupwise Registration =
+
= Optimal Mass Transport Registration =
  
Image registration is an important tool in medical image analysis. Medical experts traditionally rely on manual comparisons of images, but the abundance of information due to technological advances makes this task a challenging one. We present a fully automatic procedure which achieves correspondence among anatomical structures in medical images. Our registration procedure runs in a simultaneous fashion, with every member of the population approaching the central tendency of the population at the same time. Compared to pairwise algorithms we eliminate the need for selecting a particular reference frame a priori. Therefore, our algorithm can generate unbiased atlases.  
+
The aim of this project to provide a computationaly efficient non-rigid/elastic image registration algorithm based on the Optimal Mass Transport theory. We use the Monge-Kantorovich formulation of the Optimal Mass Transport problem and implement the solution proposed by Haker et al. using multi-resolution and multigrid techniques to speed up the convergence. We also leverage the computation power of general purpose graphics processing units available on standard desktop computing machines to exploit the inherent parallelism in our algorithm.
  
= Description =  
+
= Description =
  
A problem associated with the use of pairwise image registration is that the atlas created is dependent on the choice of the reference subject. If there is wide variation within the population the reference subject might not be good representative of the population. Instead of choosing a reference subject and performing pairwise registration, we propose a groupwise non-rigid registration algorithm to simultaneously register all subjects in a population to a common reference coordinate system. By registering all the images simultaneously, the resulting deformation fields contain information about the variability across the population. Using the resulting deformation fields we obtain a dense and consistent correspondence across the population which allows for the creation of population-specific atlases.
+
The Optimal Mass Transport problem was first formulated by a Frech engineer Gasper Monge in 1781, and was given a modern formulation in the work of Kantorovich and, therefore, is now known as the Monge-Kantorovich problem. We extend the work by Haker et al. who compute the optimal warp from a first order partial differential equation, an improvement over earlier proposed higher order methods and those based on linear programming. We implement the algorithm using a coarse-to-fine strategy resulting in phenomenol improvement in convergence. The algorithm also involves inverting the Laplacian in each iteration, which we perform using multigrid methods for even faster per iteration computation times. This method has a number of distinguishing characteristics:
 +
 
 +
# It is a parameter free method.
 +
# It utillizes all of the grayscale data in both images.
 +
# It is symmetrical; the optimal mapping from image A to image B is the inverse of the optimal mapping from B to A.
 +
# No landmarks need to be specified.
 +
# The minimizer of the functional involved is unique; there are no local minimizers.
 +
# The algorithm is designed to take into account changes in densities that result from changes in area or volume.
  
 
''Algorithm''
 
''Algorithm''
  
The method we propose uses the congealing framework with an information theoretic objective function. The congealing technique was introduced to capture the central tendency of a collection of input images for classification purposes [1]. We adapt the congealing framework to a population of grayscale-valued 3D data volumes and provide a computationally efficient implementation via a stochastic gradient-based optimization procedure in a multi-resolution framework.
+
The flowchart of the algorithm is shown in the following figure.  
 +
 
 +
[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]
 +
 
 +
<br/>
  
In the congealing framework we use the sum of voxel-wise entropies as a joint alignment criterion. If the images are aligned properly, intensity values at corresponding coordinate locations from all the inputs form a low entropy distribution; hence, the objective function achieves a minimum. This statement holds even if the intensity values are not identical. Therefore, an entropy-based objective function makes the algorithm considerably robust to noise and bias fields. As B-Spline based non-rigid deformations with dense control points can overfit the data, we add a term to our objective function penalizing non-affine deformations (similar to [2]).
+
''Multi-resolution Approach''
  
To find the set of non-rigid transformations that aligns all subjects to a common reference coordinate system, B-Spline control points are overlayed uniformly over the image sets. The directions of movement of the B-Spline control points are found by calculating the gradient of the objective function with respect to the control point displacements. The control points are updated using gradient descents until the objective function converges to a local minimum. While minimizing the objective function we constrain the sum of all the deformations to be zero to force the mean scale of the registered images to be the same as the original images. Therefore, the gradient of the objective function is projected onto the constraint surface after each iteration. To reduce the computational time of the algorithm we make use of stochastic subsampling in a multiresolution setting (similar to that of [3]). To estimate the entropy measure from the samples, we use the Parzen windowing method [4].  
+
Performing image registration using a multi-resolution approach is widely used to improve speed, accuracy and robustness. Registration is first performed at a coarse scale. The spatial mapping determined at coarse scale is then used to initialize registration at the next finer scale. This process is repeated until it reaches the finest scale. Our coarse-to-fine hierarchy comprises of three levels and we use bi-cubic interpolation to interpolate results from coarse to fine grid. This process is depicted in the following figure.
 +
<br/>
  
Prior to non-rigid registration, affine congealing [5] is performed on the data to obtain a good initialization for B-Splines. Afterwards, B-Spline based nonrigid deformations are used to obtain a dense deformation field on the data set. We embed both registrations in a multiresolution setting to avoid the deformation fields to be trapped by local minima. Our implementation of groupwise non-rigid registration is based on open source Insight Toolkit(ITK) and is publicly available [6].
+
[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]
  
 
''Progress''
 
''Progress''
  
We present the results of our algorithm on two synthetic data sets. The first data set is generated by applying 30 random affine transformations to an MRI data set of size 256x256x128. The original images were recovered by our algorithm. The second data set was created by applying 30 random B-Spline based nonrigid deformations to the same image. As the mean images indicate the original images are obtained accurately.
+
Below we show the results from registration of two 3D brain MRI datasets. The first data set was pre-operative while the second data set was acquired during surgery (craniotomy). Both were resampled to 256*256*256 for uniform voxel size and the skull was removed. We show the results from two axial slices of the 3D brain volumes. The sag and compression areas can easily be seen in the deformed grid shown below. The reults shown are after 3600 iterations, requiring less than 15 minutes of computation time (Dual Xeon 1.6GHz + nVidia GeForce 8800 GX GPU. The optimal computation time was found to occur for a grid size of 128*128*128 where about 1000 iterations execute in less than 15 seconds. This is due to the memory limitations on the graphics card used.
  
<br>
+
* [[Image:Results_brain_sag.JPG | Visual Results | 1000px]]  
<p>
 
<table width="612" border="1" align="center" >
 
<caption> <b> Affine registration on synthetic data </b> </caption>
 
<tr>
 
  <td width="306" align="center"> [[Image:serdarAffineOrig.jpg]] <p>Central slice of the mean of synthetic data</p> </td>
 
  <td width="306" align="center"> [[Image:serdarAffineRegister.jpg]] <p>Central slice of the mean after affine registration</p> </td>
 
</tr>
 
<tr>
 
<td colspan="2">
 
<b>Left</b>: The central slice of the mean of the synthetic data is shown on
 
left. The images were created by 30 random affine
 
transformations. <b>Right</b>: The central slice of the mean of the registered
 
images.
 
<td>
 
</tr>
 
</table>
 
</p>
 
  
<br>
+
3D Registration Results on axial slices. We visualize the optimal transport map (right) in the form of a vector field corresponding to the directions of deformation between pre-op (left)
<p>
+
and post-op (center) brains. Data size 256*256*256.
<table width="612" border="1" align="center" >
 
<caption> <b> Non-rigid registration on synthetic data </b> </caption>
 
<tr>
 
  <td width="306" align="center"> [[Image:serdarBSplineOrig.jpg]] <p>Central slice of the mean of the synthetic data </p></td>
 
<td width="306" align="center">  [[Image:serdarBSplineRegister.jpg]] <p>Central slice of the mean after B-Spline registration </p></td>
 
</tr>
 
<tr>
 
<td colspan="2">
 
<b>Left:</b> The central slice of the mean of the synthetic data is shown on
 
left. The images were created by 30 random B-Spline
 
transformations. <b>Right:</b> The central slice of the mean of the registered
 
images.
 
<td>
 
</tr>
 
</table>
 
</p>
 
  
<!--
+
''Project Status''
<br>
+
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
<p>
+
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
<table width="612" border="1" align="center" >
+
* Currently working on validating 3D registration results.
<caption> <b> Grouwise registration results on real data </b> </caption>
 
<tr>
 
  <td width="306" align="center"> [[Image:MeanOriginal.png]] <p>Central slice of the mean of the real data (50 subjects)</p></td>
 
  <td width="306" align="center"> [[Image:MeanRegisteredAffine.png]] <p>Central slice of the mean after afffine registration </p></td>
 
  <td width="306" align="center"> [[Image:MeanRegisteredBspline.png]] <p>Central slice of the mean after B-Spline registration </p></td>
 
</tr>
 
<tr>
 
<td colspan="3">
 
<b>Left:</b> The central slice of the mean of the real data is shown on
 
left. The images are MRI scans <b>Right:</b> The central slice of the mean of the registered
 
<b>Right:</b> The central slice of the mean of the registered
 
images.
 
<td>
 
</tr>
 
</table>
 
</p>
 
-->
 
  
''Software''
+
= Key Investigators =
  
Our algorithm is implemented using ITK. The source code is publicly available through ITK's svn servers. The project is located under the folder NAMICSandBox/trunk/MultiImageRegistration. [[http://www.na-mic.org/websvn/listing.php?repname=NAMICSandBox&amp;path=%2Ftrunk%2FMultiImageRegistration%2F&amp;rev=0&amp;sc=| source code]]
+
* Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Allen Tannenbaum
 
 
* Current implementation supports groupwise registration using
 
** congealing
 
** registering to the mean
 
** registering all pairs to all pairs
 
** joint entropy
 
* An efficient implementation of B-Splines is provided
 
* All methods have a fast multithreaded implementation
 
  
 
= Publications =
 
= Publications =
  
* E. Miller, N. Matsakis and P. Viola. Learning from One Example through Shared Densities on Transforms. In <em> IEEE Computer Society Conference on Computer Vision and Pattern Recognition </em>, vol. 1, pp. 464-471, 2000.
+
''In press''
* D. Rueckert, L. Sonodo, I.C. Hayes, D.L.G. Hill, M.O. Leach, D.J. Hawkes. Nonrigid Registration Using Free-Form Deformations: Application to Breast MR Images. In <em>IEEE Transactions on Medical Imaging</em>, vol. 18, n. 8, pp. 712-721, 1999.
 
* W.M. Wells, P. Viola, H. Atsumi, S. Nakajima and R. Kikinis. Multimodality Image Registration by Maximization of Mutual Information. In <em> Medical Image Analysis </em>, vol. 1, n. 1, pp. 35-51, 1996.
 
* R.O. Duda, P.E. Hart and D.G. Stork. Pattern Classification. New York John Wiley, 2001.
 
* L. Zollei, E. Learned-Miller, E. Grimson and W. Wells. Efficient Population Registration of 3D Data. In <em>ICCV 2005 </em>, vol. 3765 of LNCS. pp. 291-301, 2005.
 
* The Insight Segmentation and Registration Toolkit, http://www.itk.org.
 
 
 
= Key Investigators =
 
  
= Links =
+
* T. Rehman and A. Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. SPIE Computation Imaging V, 2007
 +
* T. Rehman, G. Pryor and A. Tannenbaum. GPU Enhanced Multigrid Optimal Mass Transport for Image Registration and Morphing. Publication in submission.
 +
* T. Rehman, G. Pryor, J. Melonakos and A. Tannenbaum. Multiresolution 3D Nonrigid Registration via Optimal Mass Transport. Publication in submission.

Revision as of 18:51, 9 November 2007

Home < Projects:GroupwiseRegistration
Back to NA-MIC_Collaborations, Georgia Tech Algorithms

Optimal Mass Transport Registration

The aim of this project to provide a computationaly efficient non-rigid/elastic image registration algorithm based on the Optimal Mass Transport theory. We use the Monge-Kantorovich formulation of the Optimal Mass Transport problem and implement the solution proposed by Haker et al. using multi-resolution and multigrid techniques to speed up the convergence. We also leverage the computation power of general purpose graphics processing units available on standard desktop computing machines to exploit the inherent parallelism in our algorithm.

Description

The Optimal Mass Transport problem was first formulated by a Frech engineer Gasper Monge in 1781, and was given a modern formulation in the work of Kantorovich and, therefore, is now known as the Monge-Kantorovich problem. We extend the work by Haker et al. who compute the optimal warp from a first order partial differential equation, an improvement over earlier proposed higher order methods and those based on linear programming. We implement the algorithm using a coarse-to-fine strategy resulting in phenomenol improvement in convergence. The algorithm also involves inverting the Laplacian in each iteration, which we perform using multigrid methods for even faster per iteration computation times. This method has a number of distinguishing characteristics:

  1. It is a parameter free method.
  2. It utillizes all of the grayscale data in both images.
  3. It is symmetrical; the optimal mapping from image A to image B is the inverse of the optimal mapping from B to A.
  4. No landmarks need to be specified.
  5. The minimizer of the functional involved is unique; there are no local minimizers.
  6. The algorithm is designed to take into account changes in densities that result from changes in area or volume.

Algorithm

The flowchart of the algorithm is shown in the following figure.

Optimal Mass Transport Algorithm


Multi-resolution Approach

Performing image registration using a multi-resolution approach is widely used to improve speed, accuracy and robustness. Registration is first performed at a coarse scale. The spatial mapping determined at coarse scale is then used to initialize registration at the next finer scale. This process is repeated until it reaches the finest scale. Our coarse-to-fine hierarchy comprises of three levels and we use bi-cubic interpolation to interpolate results from coarse to fine grid. This process is depicted in the following figure.

Multi-resolution Implementation

Progress

Below we show the results from registration of two 3D brain MRI datasets. The first data set was pre-operative while the second data set was acquired during surgery (craniotomy). Both were resampled to 256*256*256 for uniform voxel size and the skull was removed. We show the results from two axial slices of the 3D brain volumes. The sag and compression areas can easily be seen in the deformed grid shown below. The reults shown are after 3600 iterations, requiring less than 15 minutes of computation time (Dual Xeon 1.6GHz + nVidia GeForce 8800 GX GPU. The optimal computation time was found to occur for a grid size of 128*128*128 where about 1000 iterations execute in less than 15 seconds. This is due to the memory limitations on the graphics card used.

  • Visual Results

3D Registration Results on axial slices. We visualize the optimal transport map (right) in the form of a vector field corresponding to the directions of deformation between pre-op (left) and post-op (center) brains. Data size 256*256*256.

Project Status

  • 2D Multi-resolution Registration using Optimal Mass Transport implemented.
  • 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
  • Currently working on validating 3D registration results.

Key Investigators

  • Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Allen Tannenbaum

Publications

In press

  • T. Rehman and A. Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. SPIE Computation Imaging V, 2007
  • T. Rehman, G. Pryor and A. Tannenbaum. GPU Enhanced Multigrid Optimal Mass Transport for Image Registration and Morphing. Publication in submission.
  • T. Rehman, G. Pryor, J. Melonakos and A. Tannenbaum. Multiresolution 3D Nonrigid Registration via Optimal Mass Transport. Publication in submission.