1.1 The 3D Image Reconstruction Problem
Also referred to as Computed Tomography (CT), 3D image reconstruction is an imaging technique that provides cross sections of an object from measurements taken from different angular positions around the object (Figure 1). Sound descriptions of the principles and underlying mathematics have been the topic of numerous books and publications (Kak 1988, Herman 1980, Kalender 2005, Natterer 1989). CT is commonly used in medical imaging for diagnostic purposes, in luggage scanning, as well as in industrial non-destructive testing applications. Since Hounsfield (1972) patented the first CT scanner, new X-ray source-detector technologies have made a revolutionary impact on the possibilities of Computed Tomography.
Figure 1. Principle of Computed Tomography. The object to be reconstructed is illuminated from different angles by a fan beam of X-ray photons. The absorption of X-ray photons is measured from every angle
From the pure mathematical point of view, the solution to the inverse problem of image reconstruction had been found for the two dimensional case by Johann Radon in 1917 (Radon 1986). Nevertheless, the use of an ever-improving technology fuels the research community. As a result, there seems to be an endless stream of new reconstruction algorithms.
Image reconstruction is known to be a very compute-intensive problem. In its simplest form, the computational load is a function of O(M × N3)1, where M represents the number of measurements taken around the object and N is the dimension of the object. Both values typically lie in the range between 500 and 1500. Only through the use of High Performance Computing (HPC) platforms the reconstruction can be performed in a delay that is compatible with the requirements of the above-mentioned applications. Moreover, CT scanners have entered the stage of wide deployment, and the requirements for processing power for implementing the new algorithms has steadily been above Moore’s law. As a consequence, one cannot expect to run modern reconstruction algorithms on commonly available computers. Therefore, high-performance computing solutions are commonly used to solve the computational problem of image reconstruction.
Nevertheless, there are significant variations in the size of the reconstruction problem. Even for a given application, e.g. medical imaging, the selected values for M and N can vary depending on several factors, such as the region of interest and the desired image quality. By nature, the reconstruction problem exhibits inherent independence between subsets of input samples and between subparts of the reconstructed volume, making it suitable for parallelization techniques. Indeed the ultimate HPC platforms, as they are required for high-performance image reconstruction (HPIR), must provide powerful processing blocks that allow for parallelization. In addition, HPC platforms also need to remain flexible enough to enable the architecture to scale to address the different problem sizes without undue reduction in the efficiency.
The quality of a given CT implementation is also measured against the quality of the reconstructed volume. The quality is evaluated against gold reference standards. It largely depends on the reconstruction algorithm and, for a given algorithm, on the accuracy and the precision at which the different processing steps have been carried out. Inaccurate and imprecise operations can introduce all kinds of reconstruction artifacts, easily recognizable in the resulting volume.
In order to reach the desired image quality, several factors need to be considered when implementing the different processing steps. Firstly, the quality of the measured samples plays an important role. Although the analysis of the samples’ quality is beyond the scope of this chapter, it is worth noticing that they influence the complexity of the de-noising algorithms, which in turn influence the selection of the HPC platform for running the appropriate de-noising algorithms. Secondly, the precision at which the computation has to be carried out also depends on the size of the problem, i.e. the number of voxels to reconstruct as well as the desired spatial resolution. Since a big part of the problem consists in computing coordinates, one must ensure that the computation uses enough bits to accurately compute those coordinates.
Due to the large variety in the type of reconstruction problems, there is also a wide spectrum of possible HPC platforms to consider. However, considering the inherent properties of the problem, there are only a few families of devices which can be used for solving the problem in a time and cost effective way. Firstly, the size of the problem is fairly large, but the individual data sets are also independent from each other. This naturally calls for a high degree of parallelism. Secondly, the size of the problem and the desired resolution influence the number of bits at which the computation has to take place. Ideally this number should be variable. Thirdly, the performance requirements of the final application also dictate the number of processing elements needed to meet the processing time.
There are several families of devices that can be looked at to efficiently design an HPC platform: the Application Specific Integrated Circuit (ASIC), the Field Programmable Gate Array (FPGA), the multicore processor architecture and General-Purpose Graphics Processing Units (GPGPUs). All these devices exhibit, to a certain extent, the desired properties for building at least a part of the HPC reconstruction platform. They all have been successfully used in existing designs. Furthermore, significant hardware design is in progress for these device families. They all have a dense roadmap so that one can trustfully consider designing future HPC platforms for 3D reconstruction using future versions of those devices.