Acceleration of 3D, nonlinear warping using standard video graphics hardware: implementation and initial validation

https://doi.org/10.1016/j.compmedimag.2004.07.005Get rights and content

Abstract

Thin Plate Spline (TPS) transformations are used in many medical imaging algorithms, but are time-prohibitive for iterative or interactive use. We have utilized current generation consumer 3D graphics cards to accelerate the application of the TPS nonlinear transformation by combining hardware accelerated 3D textures, vertex shaders and trilinear interpolation. Our hardware accelerated algorithm warped a 512×512×173 Computed Tomography (CT) dataset in 2.3 s, and the same study, scaled to 256×256×173, in 0.5 s, using a set of 92 landmarks. An accelerated software implementation of the TPS transformation warped the 512×512×173 study in 32.9 s and the 256×256×173 study in 9.5 s. Subtracted images were used for qualitative analysis of the warp and the Mutual Information (MI) and Sum of Absolute Difference (SAD) similarity metrics were used to quantitatively compare the output of the hardware accelerated algorithm to that of the software algorithm. The hardware accelerated algorithm provided a 7–65 times performance increase when compared to the software algorithm, and produced output of comparable quality (MI>300 and SAD <1.75%).

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)

  • Lal Shimpi A. 3DLabs' P10 Visual processing unit—when a CPU and GPU collide. www.anandtech.com; 2002. AnandTech....
  • K. Proudfoot et al.

    A real-time procedural shading system for programmable graphics hardware

    (2001)
  • E. Lindholm et al.

    A user-programmable vertex engine. Proceedings of the 28th annual conference on computer graphics and interactive techniques

    (2001)
  • Microsoft. DirectX Programming Guide. www.microsoft.com; 2003. Microsoft....
  • Cited by (13)

    View all citing articles on Scopus

    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.

    View full text