Acceleration of 3D, nonlinear warping using standard video graphics hardware: implementation and initial validation
Introduction
The ability to compare multiple medical imaging scans, acquired from single or multiple modalities, allows a physician to review a combination of anatomical and functional information simultaneously. It also allows them to estimate the differences between two images more easily. This can further increase their ability to make an accurate diagnosis. A major difficulty arises when scans are acquired at different times. Misalignment of the two images can make their comparison too inaccurate to be of use. Volume-based image registration algorithms have been investigated as a means to correct for these misalignments, making direct comparisons of two such scans possible [1].
There are two types of image registration algorithm, linear and nonlinear. Due to the flexible nature of soft tissue, organs such as the heart and the lungs tend to deform nonlinearly rather than just be misaligned [2]. Compensating for these deformities requires a nonlinear approach to registration [2]. The Thin Plate Spline (TPS) algorithm is a common nonlinear transformation used to solve such problems. Three dimensional TPS has been successfully used to register lung studies [2], prostate and pelvic Magnetic Resonance Imaging (MRI) volumes [3] and contrast and non-contrast Digital Subtraction Angiography (DSA) images [4]. Unfortunately, the long runtimes of current TPS algorithms are prohibitive for iterative or interactive use [2], [3], [5].
Although software optimization and approximation can offer some increase in speed, an alternative avenue for accelerating nonlinear warping is consumer graphics hardware. Driven by the increase in popularity and complexity of interactive video games, several companies have released computer graphics cards which accelerate many 3D operations such as trilinear interpolation and texture mapping [6], [7]. Experiments performed by the Interactive Visualization Group at the University of Erlangen have shown that graphics hardware can be used to accelerate nonlinear warping of a volume set by treating the nonlinear transformation as a series of piecewise, linear transformations [8], [9]. By exploiting hardware-based 3D texture mapping and trilinear interpolation, order of magnitude time enhancements are possible [8].
The newest development in consumer graphics chips, or Visual Processing Units (VPU) is the ability to customize the 3D rendering pipeline [10]. Prior to the current generation of graphics processors, the rendering pipeline was a fixed structure, accepting vertices and textures as data and then acting upon that data using a set of predetermined operations. Extending the pipeline with custom operations was impossible. New advances in consumer graphics hardware, such as shaders, have removed this limitation. Shaders are custom assembly programs which are executed as data moves through the rendering pipeline [11], [12]. Combinations of shaders can be used to create a custom rendering pipeline that performs non-standard operations on vertices and pixels as they move through the rasterization process. Shaders have recently been introduced to consumer level graphics cards by ATI and Nvidia [11] and are supported by the DirectX [13] and OpenGL [14] application programming interfaces (APIs).
In this work we have exploited the programmability of this graphics hardware to accelerate a nonlinear warping algorithm that approximates the TPS transformation. We extended upon the previous research in this area [8], [9] by comparing this warping algorithm to an accepted software implementation of the TPS transformation in terms of speed and image quality. This was done in order to provide initial validation for its use in medical imaging applications. Furthermore, all the presented results were obtained on inexpensive consumer level graphics cards. Hardware accelerated warping could be used in image registration algorithms that require iterative warping of volume data. It could also be used to allow interactive, nonlinear warping in a clinical setting.
Section snippets
Methods
The hardware accelerated TPS algorithm can be divided into two distinct sections: the calculation of the TPS transformation and the application of this transformation to volume data.
Results
Fig. 4 shows the results of warping both test studies using the HW algorithm. A target image is shown for comparison since landmarks were chosen to produce a warped volume that approximated the target volume. After warping, the MI between the warped and target volumes was calculated to be 174.2 for Study 1 and 52.4 for Study 2 (Table 3). The calculated SAD values were 11.8% for Study 1 and 52.7% for Study 2 (Table 3). The similarity metrics were also computed between volumes warped using the
Quality comparison of hardware and software TPS
Several interesting observations can be made from the quality measurements performed on the HW algorithm When the HW and the SWG algorithms were compared to the SW algorithm, it became evident that at lower grid spacing the SWG algorithm was a slightly closer match to the SW algorithm (Fig. 7). However, as grid spacing was increased (∼≥64×64), the HW algorithm started to better approximate the SW algorithm (Fig. 7). This is due to the explicit triangulation of the HW grid. The added midpoint
Conclusion
We have shown that TPS volume warping can be significantly accelerated using the latest advancements in consumer graphics hardware. Furthermore, we have shown, both quantitatively and qualitatively, that the results of this hardware accelerated TPS algorithm are of comparable quality to those produced by two different software algorithms. This generic method will allow dramatic acceleration of a wide variety of medical imaging algorithms that utilize 3D image warping. Consequently, it could be
Summary
We have exploited the latest consumer 3D graphics hardware in order to implement a high performance Thin Plate Spline (TPS) nonlinear volume warping algorithm. Accelerated nonlinear warping could be used in iterative image registration algorithms or in interactive clinical applications. Hardware accelerated 3D texturing and trilinear interpolation were combined with OpenGL vertex programs to implement a modified grid transform algorithm. This algorithm was used to apply the TPS transformation
David Levin received his BSc in Computer Science and Biology from the University of Western Ontario, Canada in 2002 and has begun studying for his MSc in Medical Biophysics at the Robarts Research Institute. His main interests are interactive 3D graphics, image processing and analysis.
References (28)
- et al.
A comparative study of warping and rigid body registration for the prostate and pelvic MR volumes
Comput Med Imaging Graph
(2003) - et al.
An invariant approach for image registration in digital subtraction angiography
Pattern Recognit
(2002) - et al.
Generalized 3D nonlinear transformations for medical imaging: an object-oriented implementation in VTK
Comput Med Imaging Graph
(2003) - et al.
Mutual-information-based registration of medical images: a survey
IEEE Trans Med Imaging
(2003) - et al.
Automated 3-dimensional registration of stand-alone (18)F-FDG whole-body PET with CT
J Nucl Med
(2003) - et al.
PET-CT image registration in the chest using free-form deformations
IEEE Trans Med Imaging
(2003) - Spitzer J. Nvidia OpenGL Performance FAQ. www.nvidia.com; 2002. Nvidia....
- ATI. Radeon 9500/9600/9700/9800 OpenGL Programming and Optimization Guide. www.ati.com; 2004. ATI....
- Rezk-Salama C, Hastreiter P, Greiner G, Ertl T. Non-linear registration of pre-and intraoperative volume data based on...
- et al.
Fast volumetric deformation on general purpose hardware
(2001)
A real-time procedural shading system for programmable graphics hardware
A user-programmable vertex engine. Proceedings of the 28th annual conference on computer graphics and interactive techniques
Cited by (13)
An optimised radial basis function algorithm for fast non-rigid registration of medical images
2010, Computers in Biology and MedicineCitation Excerpt :When applying the Fast RBF in software, we notice a speedup factor of about 2 for the TPS for 8 training landmarks and a speedup factor of nearly 10 when 44 landmarks are used. When implemented in hardware, there is no significant difference for 8 training landmarks amongst the brute force, fast RBF and Levin-13 [11] methods. However, when 44 landmarks are used, the fast RBF hardware shows a significantly faster performance than all its competitors.
Non-Rigid Image Registration based on Parameterized Surfaces: Application to 3D Cardiac Motion Image Analysis
2022, International Journal of Image and GraphicsRegularized surface and point landmarks based efficient non-rigid medical image registration
2018, Computing and InformaticsNonrigid Medical Image Registration Based on Curves
2017, International Journal of Image and GraphicsAffine Medical Image Registration Using the Graphics Processing Unit
2016, Image Processing in Radiation TherapyMulti-GPU acceleration of DARTEL (early detection of Alzheimer)
2014, 2014 IEEE International Conference on Cluster Computing, CLUSTER 2014
David Levin received his BSc in Computer Science and Biology from the University of Western Ontario, Canada in 2002 and has begun studying for his MSc in Medical Biophysics at the Robarts Research Institute. His main interests are interactive 3D graphics, image processing and analysis.
Damini Dey received her BSc Honours in Physics at the University of Saskatchewan, Canada in 1988, and her MSc and PhD in Medical Physics at the University of Calgary, Canada in 1992 and 1998. She did her Post-Doctoral training at the Imaging Research Laboratories, Robarts Research Institute, University of Western Ontario, Canada in image-guided neurosurgery. She is currently a Research Scientist at the Cedars Sinai Medical Center, Los Angeles, CA. Her research areas are in-vivo plaque imaging and quantification, and image registration and fusion.
Piotr J. Slomka received his MASc in Computer Engineering from the Warsaw University of Technology, Poland, in 1989 and his PhD in Medical Physics from the University of Western Ontario, Canada in 1995. He is currently a faculty scientist with the Cedars Sinai Medical Center, Los Angeles, CA and is an Associate Professor of Medicine at the University of California, Los Angeles. His principal research areas are image registration, fusion, and automated medical image analysis.