NAMIC Wiki - User contributions [en]

Projects:OptimalMassTransportRegistration

2009-04-13T04:14:59Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below. The resulting KKT system is solved using a MINRES iteration and multigrid preconditioning. When using a consistent discretization approach the resulting algorithm is a stable second order method requiring few iterations to reach convergence as shown in the results below.

* [[Image:Inexact_SQP.jpg | Inexact SQP | 500px | center]]

* [[Image:Synthetic_result1.jpg | Inexact SQP | 600px | center]]

* [[Image:Synthetic_result2.jpg | Inexact SQP | 600px | center]]

* Currently working on computation of the mass transport using OcTrees which can potentially result in an order of magnitude reduction in computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T04:12:29Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below. The resulting KKT system is solved using a MINRES iteration and multigrid preconditioning. When using a consistent discretization approach the resulting algorithm is a stable second order method requiring few iterations to reach convergence as shown in the results below.

* [[Image:Inexact_SQP.jpg | Inexact SQP | 500px | center]]

* [[Image:Synthetic_result1.jpg | Inexact SQP | 600px | center]]

* [[Image:Synthetic_result2.jpg | Inexact SQP | 600px | center]]

* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T04:11:26Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below. The resulting KKT system is solved using a MINRES iteration and multigrid preconditioning. When using a consistent discretization approach the resulting algorithm is a stable second order method requiring few iterations to reach convergence as shown in the results below.

* [[Image:Inexact_SQP.jpg | Inexact SQP | 500px | center]]

* [[Image:Synthetic_result1.jpg | Inexact SQP | 600px | center]]

* [[Image:Synthetic_result2.jpg | Inexact SQP | 500px | center]]

* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

File:Synthetic result2.jpg

2009-04-13T04:08:33Z

Tauseef:

File:Synthetic result1.jpg

2009-04-13T04:08:05Z

Tauseef:

Projects:OptimalMassTransportRegistration

2009-04-13T04:05:12Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below. The resulting KKT system is solved using a MINRES iteration and multigrid preconditioning. When using a consistent discretization approach the resulting algorithm is a stable second order method requiring few iterations to reach convergence as shown in the results below.

* [[Image:Inexact_SQP.jpg | Inexact SQP | 500px | center]]

* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T03:56:38Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below:

* [[Image:Inexact_SQP.jpg | Inexact SQP | 500px | center]]

* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T03:54:55Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint has been developed. The originally proposed method of integration of a time dependent PDE is replaced with a direct variational method. The projection step is computed using an Inexact Sequential Quadratic Programming (SQP) approach as shown below:

* [[Image:Inexact_SQP.jpg | Inexact SQP | 700px | center]]

* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

File:Inexact SQP.jpg

2009-04-13T03:50:40Z

Tauseef:

Projects:OptimalMassTransportRegistration

2009-04-13T03:41:01Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 700px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 700px | center]]
*
* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 900px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint completed. The projection step is done using a Modified Sequential Quadratic Programming (SQP) approach.
* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T03:39:39Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 600px | center]]

* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 1000px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint completed. The projection step is done using a Modified Sequential Quadratic Programming (SQP) approach.
* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2009-04-13T03:38:35Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.

* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.

* 3D Registration of White Matter MRI data and white matter atlas implemented. The proposed new algorithm and the preliminary results are shown below:

* [[Image:Wm_2_atlas_omt.jpg | Proposed Algorithm | 800px | center]]

* [[Image:Whitematter_tessalation.jpg | white matter to Atlas Registration Results | 800px | center]]

* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint completed. The projection step is done using a Modified Sequential Quadratic Programming (SQP) approach.
* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

File:Wm 2 atlas omt.jpg

2009-04-13T03:34:33Z

Tauseef:

File:Whitematter tessalation.jpg

2009-04-13T03:30:09Z

Tauseef: uploaded a new version of "File:Whitematter tessalation.jpg"

Projects:OptimalMassTransportRegistration

2009-04-13T03:17:25Z

Tauseef: /* Description */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* An Efficient Numerical Implementation of the OMT algorithm with explicit projections to the mass preserving constraint completed. The projection step is done using a Modified Sequential Quadratic Programming (SQP) approach.
* Working on development of computing the mass transport using OcTrees for reduced computational cost.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-12-09T21:22:09Z

Tauseef: /* Publications */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

# Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
# Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

# Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
# G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
# Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
# Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
# Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-12-09T21:21:46Z

Tauseef: /* Publications */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

## Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
## Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
## Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

## Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
## G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
## Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
## Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
## Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-12-09T21:21:24Z

Tauseef: /* Publications */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

# Journals

## Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
## Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
## Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

# Conference articles

## Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
## G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
## Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
## Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
## Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-12-09T21:17:31Z

Tauseef: /* Key Investigators */

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Ivan Kolesov, Gallagher Pryor, Eldad Haber, Allen Tannenbaum
* BWH: Sylvain Bouix, Yogesh Rathi, Ron Kikinis

= Publications =

Journals

1. Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
2. Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
3. Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

1. Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
2. G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
3. Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
4. Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
5. Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-12-09T21:15:15Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__
= Optimal Mass Transport =

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Kilian Pohl, Eldad Haber, Allen Tannenbaum
* BWH: Steven Haker, Ron Kikinis

= Publications =

Journals

1. Eldad Haber, Tauseef Rehman, and Allen Tannenbaum. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem. In submission - SIAM Journal of Scientific Computing, 2008.
2. Tauseef Rehman, Eldad Haber, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. 3D Nonrigid Registration via Optimal Mass Transport on the GPU. To appear in - Elsevier Journal of Medical Image Analysis, 2008.
3. Tauseef Rehman, Eldad Haber, Gallagher Pryor, and Allen Tannenbaum. Fast Optimal Mass Transport for 2D Image Registration and Morphing. Accepted for - Elsevier Journal of Image and Vision Computing, 2008.

Conference articles

1. Tauseef Rehman and Allen Tannenbaum. Multimodal Registration of White Matter Brain Data via Optimal Mass Transport. In Proceedings of Computational Biomechanics for Medicine-III, MICCAI, pages 27-35, 2008.
2. G. Pryor, T. Rehman, S. Lankton, P. Vela, and A. Tannenbaum. Fast Optimal Mass Transport for Dynamic Active Contour Tracking on the GPU. In CDC, 2007.
3. Tauseef Rehman, Gallagher Pryor, John Melonakos, and Allen Tannenbaum. Multi-resolution 3D Nonrigid Registration via Optimal Mass Transport on the GPU. In Proceedings of Computational Biomechanics for Medicine-II, MICCAI, pages 122-132, 2007.
4. Tauseef Rehman, Gallagher Pryor, and Allen Tannenbaum. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of British Machine Vision Conference, pages 102-111, 2007.
5. Tauseef Rehman and Allen Tannenbaum. Multigrid Optimal Mass Transport for Image Registration and Morphing. In Proceedings of SPIE Conference on Computational Imaging V, pages 649810, 2007.

* [http://www.na-mic.org/pages/Special:Publications?text=Projects%3AOptimalMassTransportRegistration&submit=Search&words=all&title=checked&keywords=checked&authors=checked&abstract=checked&sponsors=checked&searchbytag=checked| NA-MIC Publications Database]

[[Category:Registration]] [[Category:MRI]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-27T13:30:53Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | thumb | 300px | OMT Deformation Grid on MRI ]]
|[[Image:Dwi_image_2.jpg | thumb | 300px | OMT Deformation Grid on DWI ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction.
* DWI and MRI image intensity normalization using CSF and White-Matter/Grey-Matter segmentations performed to make sure both image volumes are on same footing so that Mass Transport mapping is found without introducing structural distortions.
* Further experiments required to fine tune the normalization step.
* Slicer command line module created for interfacing with OMT Registration algorithm. A few issues with nrrd files being resolved.
* Discussions with Core 2 on existing infrastructure within ITK for non-rigid registration and re-use of demons diffeomorphic registration filter framework for OMT Registration filter.

</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-27T13:26:27Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | thumb | 300px | OMT Deformation Grid on MRI ]]
|[[Image:Dwi_image_2.jpg | thumb | 300px | OMT Deformation Grid on DWI ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction.
* DWI and MRI image intensity normalization using CSF and White Matter/Grey Matter segmentations was done to make sure both image volumes are on same footing so that Mass Transport happens without introducing structural distortions.
* Further experiments required to fine tune the normalization step.
* Slicer command line module created for interfacing with OMT Registration algorithm. A few issues with nrrd files being resolved.
* Discussions with Core 2 on existing infrastructure within ITK for non-rigid registration and re-use of demons diffeomorphic registration filter framework for OMT Registration filter.

</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-27T13:25:05Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | thumb | 300px | OMT Deformation Grid on MRI ]]
|[[Image:Dwi_image_2.jpg | thumb | 300px | OMT Deformation Grid on DWI ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction.
* DWI and MRI image intensity normalization using CSF and White Matter/Grey Matter segmentations was done to make sure both image volumes are on same footing so that Mass Transport happens without introducing structural distortions.
* Slicer command line module created for interfacing with OMT Registration algorithm. A few issues with nrrd files being resolved.
* Discussions with Core 2 on existing infrastructure within ITK for non-rigid registration and re-use of demons diffeomorphic registration filter framework for OMT Registration filter.

</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

Project Week 2008 Special topic breakout: Non-rigid Registration

2008-06-25T17:13:48Z

Tauseef:

[[2008_Summer_Project_Week#Agenda|Back to 2008 Summer Project Week Agenda]]
'''Non-Rigid Registration '''

Breakout session

= Summary of Current Status =

* Registration classes in ITK
** Multi-threading support
** Memory vs Speed Trade-offs
* Registration helper classes
* Slicer Registration Modules
** Problems addressed
** Testing, Testing, Testing

= NAMIC Community Needs =

* Anatomical Regions
** Brain
** Abdomen
** Chest

= Future Efforts =

* Documentation ?
* Presets ?

= Attendees =

(Please add your name here)

* Luis Ibanez
* Tauseef ur Rehman

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:47:41Z

Tauseef:

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:44:38Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | OMT Deformation Grid on MRI | 300px ]]
|[[Image:Dwi_image_2.jpg | OMT Deformation Grid on DWI | 300px ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

File:Dwi image 1.jpg

2008-06-18T20:43:25Z

Tauseef: uploaded a new version of "Image:Dwi image 1.jpg"

File:Dwi image 2.jpg

2008-06-18T20:42:56Z

Tauseef: uploaded a new version of "Image:Dwi image 2.jpg"

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:34:40Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | OMT Deformation Grid | 300px ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:34:23Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | OMT Deformation Grid | 200px ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:33:56Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image_1.jpg | OMT Deformation Grid | 500px ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:32:38Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|[[Image:Dwi_image1.jpg | Brain Sag Results | 500px ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:26:21Z

Tauseef:

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
[[Image:Dwi_image1.jpg | Brain Sag Results | 800px | center]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

File:Dwi image 1.jpg

2008-06-18T20:22:19Z

Tauseef:

File:Dwi image 2.jpg

2008-06-18T20:21:12Z

Tauseef:

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:20:19Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos (Georgia Tech)
* Marek Kubicki, Sylvain Bouix (BWH)

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:10:22Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos, Georgia Tech
* Marek Kubicki, Sylvain Bouix, BWH

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
* Currently the algorithm and registration framework is available in MATLAB
* Preliminary results with DWI baseline image correction
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:09:14Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos, Georgia Tech
* Marek Kubicki, Sylvain Bouix, BWH

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

* Conversations with Core 2 to analyze the project
* Discussions with Core 3 to see how to adapt the existing code for DWI Registration
* Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
Currently the algorithm is available in MATLAB
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T20:08:46Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos, Georgia Tech
* Marek Kubicki, Sylvain Bouix, BWH

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

- Conversations with Core 2 to analyze the project
- Discussions with Core 3 to see how to adapt the existing code for DWI Registration
- Make a project plan

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
Currently the algorithm is available in MATLAB
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T19:45:59Z

Tauseef: /* References */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos, Georgia Tech
* Marek Kubicki, Sylvain Bouix, BWH

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
Currently the algorithm is available in MATLAB
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:OptimalMassTransportRegistration | Optimal Mass Transport Registration Project Page]]

2008 Summer Project Week:DWIRegistrationOMT

2008-06-18T19:43:58Z

Tauseef: /* Key Investigators */

{|
|[[Image:ProjectWeek-2008.png|thumb|320px|Return to [[2008_Summer_Project_Week|Project Week Main Page]] ]]
|}

__NOTOC__

===Key Investigators===
* Allen Tannenbaum, Tauseef ur Rehman, John Melonakos, Georgia Tech
* Marek Kubicki, Sylvain Bouix, BWH

<div style="margin: 20px;">

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Objective</h1>
* To explore the portability of Optimal Mass Transport (OMT) Non-rigid Registration code to the NAMIC toolkit.
* To determine applicability of OMT registration algorithm for DWI Distortion Correction.
</div>

<div style="width: 27%; float: left; padding-right: 3%;">

<h1>Approach, Plan </h1>

</div>

<div style="width: 40%; float: left;">

<h1>Progress</h1>
Currently the algorithm is available in MATLAB
</div>

<br style="clear: both;" />

</div>

===References===
* [[Projects:GeodesicTractographySegmentation | Geodesic Tractography Segmentation Project Page]]

2008 Summer Project Week

2008-05-08T19:50:47Z

Tauseef: /* Attendee List */

Back to [[Engineering:Programming_Events|Programming/Project Events]]

[[Image:ProjectWeek-2008.png|thumb|220px|right|Summer 2008]]

== Logistics ==

'''Dates:''' June 23-27, 2008

'''Location:''' MIT. [[Meeting_Locations:MIT_Grier_A_%26B|Grier Rooms A & B: 34-401A & 34-401B]].

'''Registration Fee:''' $260 (this will cover the cost of breakfast, lunch and coffee breaks for the week). Due by Friday, June 13th, 2008. Please make checks out to "Massachusetts Institute of Technology" and mail to: Donna Kaufman, MIT, 77 Massachusetts Ave., 38-409b, Cambridge, MA 02139

If you are attending for one day only, the registration fee is not required.

'''Hotel:''' We have a group rate of TBD/night at the [http://www.hotelatmit.com Hotel at MIT]. (Use group code NAM.) Here is some information about several other Boston area hotels that are convenient to NA-MIC events: [[Boston_Hotels|Boston_Hotels]]. Summer is tourist season in Boston, so please book your rooms early.

([[Project Week Logistics Checklist|This is a checklist for the onsite planning items]])

==Introduction to NA-MIC Project Week==

NA-MIC Project Week is a hands on activity -- programming using the [[NA-MIC-Kit|NA-MIC Kit]], algorithm design, and clinical application -- that has become one of the major events in the [[NA-MIC-Kit|NA-MIC Kit]] calendar. This event is the seventh of the [[Engineering:Programming_Events|'''series''']]. It is held in the summer at MIT (typically the last week of June), and a shorter version is held in Salt Lake City in the winter (typically the second week of January).
The main goal of these events if to move forward the deliverables of NA-MIC. NA-MIC participants and their collaborators are welcome to attend.

* NA-MIC Members: Participation in this event is voluntary -- if you don't think this will help you move forward in your work, there is no obligation to attend.
* Ideal candidates are those who want to contribute to the [[NA-MIC-Kit|NA-MIC Kit]], and those who can help make it happen.
* This is not an introduction to the components of the [[NA-MIC-Kit|NA-MIC Kit]].
* NA-MIC Core 1 (Algorithms) - bring your algorithms and code to work on in the company of Core 2 engineers and Core 3 scientists.
* NA-MIC Core 2 (Engineering) - bring your code for infrastructure and applications to extend the [[NA-MIC-Kit|NA-MIC Kit]] capabilities, integrate Core 1 algorithms, and refine workflows for Core 3.
* NA-MIC Core 3 (DBP) - bring your data to work on with the [[NA-MIC-Kit|NA-MIC Kit]] and get assistance and provide feedback to Core 1 scientists and Core 2 engineers.
* External Collaborators - if you are working on a project that uses the [[NA-MIC-Kit|NA-MIC kit]], and want to participate to get help from NA-MIC Engineering, please send an email to Tina Kapur (tkapur at bwh.harvard.edu). Please note that the event is open to people outside NA-MIC, subject to availability.
* Everyone should '''bring a laptop'''. We will have four projectors.
* About half the time will be spent working on projects and the other half in project related discussions.
* You '''do''' need to be actively working on a NA-MIC related project in order to make this investment worthwhile for everyone.

=== Agenda===
* Monday
** noon-1pm lunch
**1pm: Welcome (Ron Kikinis)
** 1:05-3:30pm Introduce [[#Projects|Projects]] using templated wiki pages (all Project Leads) ([[NA-MIC/Projects/Theme/Template|Wiki Template]])
** 3:30-5:30pm Start project work
* Tuesday
** 8:30am breakfast
** 9:00-9:45am: NA-MIC Software Process
** 10-10:30am [[Project Week 2008 Slicer 3.0 Update|Slicer 3.0 Update]] (Jim Miller, Steve Pieper)
** noon lunch
** 2:30-3:30pm: [[Project Week 2008 Special topic breakout: Non-Linear Registration]]
** 5:30pm adjourn for day
* Wednesday
** 8:30am breakfast
** 9:00-12pm [[Project Week 2008 Special topic breakout: ITK]] (Luis Ibanez)
** noon lunch
** 2:30-3:30pm: [[Project Week 2008 Special topic breakout: XNAT Database]] (Daniel Marcus)
** 5:30pm adjourn for day
* Thursday
** 8:30am breakfast
** noon lunch
** 5:30pm adjourn for day
* Friday
** 8:30am breakfast
** 10am-noon: Project Progress using update [[#Projects|Project Wiki pages]]
** noon lunch boxes and adjourn. (Next one [[AHM_2009| in Utah the week of Jan 5, 2009]])

=== Preparation ===

# Please make sure that you are on the http://public.kitware.com/cgi-bin/mailman/listinfo/na-mic-project-week mailing list

# [[Engineering:TCON_2008|May 08 and May 15 TCON DBPs ONLY]] at 3pm ET to discuss NA-MIC DBP Projects ONLY.
# [[Engineering:TCON_2008|May 22 TCON#1]] at 3pm ET to discuss NA-MIC Engr Core Projects and Assign/Verify Teams
# [[Engineering:TCON_2008|May 29 TCON#2]] at 3pm ET to discuss NA-MIC ALGORITHMS Core Lead Projects. Project leads should sign up for a slot [[Engineering:TCON_2008|here]]. Projects will be discussed in order of the signups.
# [[Engineering:TCON_2008|June 5 TCON#3]] at 3pm ET to discuss NA-MIC EXTERNAL Collaborations. All NIH funded "collaborations with NCBC" leads should call. Project leads should sign up for a slot [[Engineering:TCON_2008|here]]. Projects will be discussed in order of the signups.
# [[Engineering:TCON_2008|June 12 TCON#4]] at 3pm ET to discuss NA-MIC EXTERNAL Collaborations. All other collaboration leads should call. Project leads should sign up for a slot [[Engineering:TCON_2008|here]]. Projects will be discussed in order of the signups.
# [[Engineering:TCON_2008|June 12 TCON#4]] at 3pm ET to tie loose ends. Anyone with un-addressed questions should call.
# By 3pm ET on June 12, 2008: [[NA-MIC/Projects/Theme/Template|Complete a templated wiki page for your project]]. Please do not edit the template page itself, but create a new page for your project and cut-and-paste the text from this template page. If you have questions, please send an email to tkapur at bwh.harvard.edu.
# By 3pm on June 19, 2008: Create a directory for each project on the [[Engineering:SandBox|NAMIC Sandbox]] (Zack)
## Commit on each sandbox directory the code examples/snippets that represent our first guesses of appropriate methods. (Luis and Steve will help with this, as needed)
## Gather test images in any of the Data sharing resources we have (e.g. the BIRN). These ones don't have to be many. At least three different cases, so we can get an idea of the modality-specific characteristics of these images. Put the IDs of these data sets on the wiki page. (the participants must do this.)
## Setup nightly tests on a separate Dashboard, where we will run the methods that we are experimenting with. The test should post result images and computation time. (Zack)
# Please note that by the time we get to the project event, we should be trying to close off a project milestone rather than starting to work on one...

== A History in Wiki Links ==

A history of all the programming/project events in NA-MIC is available by following [[Engineering:Programming_Events|this link]].

== Projects ==

===DBP II===
These are projects by the new set of DBPS:
#[[DBP2:Harvard|Velocardio Facial Syndrome (VCFS) as a Genetic Model for Schizophrenia]] (Harvard: Marek Kubicki, PI)
#[[DBP2:UNC|Longitudinal MRI Study of Early Brain Development in Autism]] (UNC: Heather Hazlett, Joseph Piven, PI)
#[[DBP2:MIND|Analysis of Brain Lesions in Lupus]] (MIND/UNM: Jeremy Bockholt, Charles Gasparovic PI)
#[[DBP2:JHU|Segmentation and Registration Tools for Robotic Prostate Intervention]] (Queens/JHU: Gabor Fichtinger, PI)

===Structural Analysis===

===Diffusion Image Analysis===

===Calibration/Validation===
This is a new category of projects jointly led by team members in Core 1, Core 3 and Core 5
# [[Projects/Diffusion/2007_Project_Week_Contrasting_Tractography_Measures]] (Westin, Gollub, Gerig, Whitaker, Pujol)

===NA-MIC Kit - Slicer 3===

===External Collaborations===

===Non-Medical Collaborations===

==Attendee List==
# Gary Christensen, The University of Iowa
# Jeffrey Hawley, Gary Christensen's student
# Kate Raising, Gary Christensen's student
# Nathan Fritze, Gary Christensen's student
# Paul Song, Gary Christensen's student
# Cheng Zhang, Gary Christensen's student
# Ying Wei, Gary Christensen's student
# Nathan Burnette, The University of Iowa
# Steve Pieper, Isomics, Core 2/6
# Dana C. Peters, BIDMC Harvard Medical
# Jason Taclas, Student, BIDMC Harvard Medical
# Nicole Aucoin, BWH, Core 2
# Will Schroeder, Kitware, Cores 2/4
# Sebastien Barre, Kitware, Core 2
# Julien Jomier, Kitware, Core 2
# Curtis Lisle, KnowledgeVis, Core 2
# Katie Hayes, BWH, Core 2
# Randy Gollub, MGH, Core 5
# Clement Vachet, UNC, Core 3
# Tauseef Rehman, GA Tech, Core 1

==Pictures==

Projects:OptimalMassTransportRegistration

2008-04-28T02:59:34Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP) approach.

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Kilian Pohl, Eldad Haber, 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. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. British Machine Vision Conference 2007.
* T. Rehman, G. Pryor, J. Melonakos and A. Tannenbaum. Multiresolution 3D Nonrigid Registration via Optimal Mass Transport. MICCAI workshop on Computational Biomechanics II.

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-04-28T02:58:39Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:Fig1_gpu_diagram1.jpg | Brain Sag 3D Results | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''Project Status''
* 2D Multi-resolution Registration using Optimal Mass Transport implemented.
* 3D Multi-resolution Registration using Optimal Mass Transport of Brain sag datasets implemented.
* 3D Registration of White Matter MRI data and white matter atlas implemented.
* Currently working on Non-rigid registration of baseline DWI to MRI Brain Data.
* Currently working on Efficient Numerical Impelmentation of the OMT algorithm with explicit projections to the mass preserving constraint. The projection step is done using Sequential Quadratic Programming (SQP).

= Key Investigators =

* Georgia Tech: Tauseef ur Rehman, Gallagher Pryor, John Melonakos, Kilian Pohl, Eldad Haber, 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. Fast Multigrid Optimal Mass Transport for Image Registration and Morphing. British Machine Vision Conference 2007.
* T. Rehman, G. Pryor, J. Melonakos and A. Tannenbaum. Multiresolution 3D Nonrigid Registration via Optimal Mass Transport. MICCAI workshop on Computational Biomechanics II.

[[Category:Registration]] [[Category:MRI]]

Projects:OptimalMassTransportRegistration

2008-04-28T02:47:57Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 500px | center]]

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 on an axial and a coronal slice 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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

The following figure shows the outline of processing for the OMT solver conducted on the GPU. Processing occurs in two major phases: evolution of the map from
source to target volumes and time step adjustment. Each gray rectangle represents one Cg kernel executed on the GPU. Arrows indicate the
flow of data volumes through the Cg kernels. The entire process in the figure, above is repeated left to right until convergence.

* [[Image:fig1_gpu_diagram.jpg | Brain Sag 3D Results | 600px | center]]

''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.

[[Category:Registration]] [[Category:MRI]]

File:Sphere case.jpg

2008-04-28T02:40:14Z

Tauseef:

Projects:OptimalMassTransportRegistration

2008-04-28T02:39:41Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

''Progress''

The algorithm was tested on a synthetic 3D dataset comprising of a sphere and deformed version of it. The deformation vector field for this experiment are shown below:

* [[Image:sphere_case.jpg | Synthetic Results | 800px | center]]

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. The results on an axial and coronal slice are shown below:

* [[Image:brain_sag2.jpg | Brain Sag Results | 800px | center]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

''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.

[[Category:Registration]] [[Category:MRI]]

File:Brain sag2.jpg

2008-04-28T02:31:42Z

Tauseef:

Projects:OptimalMassTransportRegistration

2008-04-28T02:27:41Z

Tauseef:

Back to [[NA-MIC_Internal_Collaborations:StructuralImageAnalysis|NA-MIC Collaborations]], [[Algorithm:GATech|Georgia Tech Algorithms]]
__NOTOC__

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:

# 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''

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

[[Image:OMT_Algorithm.jpg| Optimal Mass Transport Algorithm | center]]

<br/>

''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.
<br/>

[[Image:Multilevel_diagram.jpg| Multi-resolution Implementation | 800px | center]]

''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.

* [[Image:brain_sag_axial.jpg | Visual Results | 500px]] [[Image:brain_sag_coronal.jpg | Visual Results | 500px]]

* [[Image:brain_sag_3d.jpg | Brain Sag 3D Results | 600px | center]]

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.

[[Category:Registration]] [[Category:MRI]]

File:Fig3 gpu speeds.jpg

2008-04-28T02:09:22Z

Tauseef: