Inherently More Efficient
InstaRecon’s algorithms for image reconstruction is inherently more efficient than conventional algorithms. For an NxN image, InstaRecon’s algorithms reduce computational complexity of backprojection from the traditional O(N3) to O(N2 log N). Similarly, for 3D reconstruction of an NxNxN volume, the complexity of backprojection is reduced from O(N4) to O(N3 log N).
For typical image sizes, with N=512, we see an unparalleled 20 to 100-fold speedup. Similar speedups are available for reprojection, which is used in beam-hardening correction in CT, and in iterative algorithms. Furthermore, the speedup relative to conventional backprojection increases as N / log N, or almost proportionally to image size.
Targeted Performance Improvements
Backprojection / reprojection is the bottleneck operation in tomographic reconstruction, as the other steps in tomographic reconstruction take only a small fraction of the computation (and this fraction becomes even smaller for larger images). Therefore the speedups provided by InstaRecon’s backprojection / reprojection algorithms significantly impact the total speed of reconstruction algorithms. Such speedups are critical for next-generation real-time imaging systems in medical, security, and industrial imaging.
Superior to other methods
Efforts aimed at speeding up the reconstruction rate with current algorithms have typically used more powerful hardware: faster and / or more processors. In contrast, InstaRecon’s technology provides a speedup algorithmically, that is, by use of a more advanced mathematical algorithm. Such speedup can be provided for any hardware configuration.
This acceleration translates to a proportional reduction in the hardware required to achieve a given speed and resolution objective. This reduction in hardware required can lead to significant reduction in cost and / or improved accuracy, resolution, and speed specs for the scanner.
Many applications that currently require expensive and inflexible special-purpose hardware to achieve acceptable speed can be satisfied by software-based solutions on standard off-the-shelf single or multi-processor PCs. This provides an inexpensive upgrade path, as processor technology continues to follow Moore’s Law.
The dramatically faster image reconstructions enabled by InstaRecon algorithms benefits all tomographic acquisition modalities:
- Computed tomography (CT): Single- and multi-slice spiral, cone-beam cine, and cone-beam spiral partial and whole-body scans
- Positron emission tomography (PET) and single-photon computed tomography (SPECT): Iterative and cone-beam reconstruction methods
- Magnetic resonance imaging (MRI): Projection reconstruction methods
- Micro CT scanners: Small-animal scans for drug assays in the pharmaceutical industry or for other biomedical research
By reconstructing tomograms faster than do current methods, these algorithms dramatically increase the number of items that can be scanned per hour (i.e., throughput), eliminating the “image reconstruction bottleneck” and significantly reducing manufacturing/ inspections costs. These algorithms can be used with any industry inspection using CT scans:
- Aerospace: Aircraft and spacecraft parts such as turbine blades
- Automotive: Engine parts
- Electronics: Circuit boards and semiconductors
- Logging: Quality assessment of logs and optimum cutting of lumber
- Other applications: Materials characterization, nuclear reactors
The faster imaging speeds enabled by these algorithms offers dramatic improvements in 3-D CT inspection of baggage or containers for the detection of weapons, explosives, or other hazardous materials.
A. Boag, Y. Besler, and E. Michielssen, “A multilvel domain decomposition algorithm for fast O(n^2\log n) reprojection of tomographic images,” IEEE Trans. Image Process., vol. 9, pp. 1573-1582, Sep. 2000. (PDF)
S. Basu and Y. Bresler, “An O(n^2 log n) filtered backprojection reconstruction algorithm for tomography,” IEEE Trans. Image Process., vol. 9, pp. 1760-1773, Oct. 2000. (PDF)
S. Basu and Y. Bresler, “Error analysis and performance optimization in fast hierarchical backprojection algorihtms,” IEEE Trans. Image Process., vol. 10, no. 7, pp. 1103-1117, July 2001.(PDF)
S. Basu and Y. Bresler, “O(N^3 log N) backprojection algorithm for the 3D Radon transform,”IEEE Trans. Med. Imag., vol. 21, no. 2, pp. 76-88, Feb. 2002.(PDF)
S. Xiao, Y. Bresler, and D.C. Munson, “O(n^2 log n) native fan-beam tomographic reconstruction,” Proc. 1st IEEE Int. Symp. Biomedical Imaging, ISBI-2002, Washington, DC, pp. 824–827, July 2002.(PDF)
S. Xiao, Y. Bresler, and D.C. Munson, “Fast feldkamp algorithm for cone-beam computer tomography,” Proc. Int. Conf. Image Processing, ICIP-2003, Barcelona, Spain, vol. 2, pp. 819–822, Sept. 2003.(PDF)
Y. Bresler and J. Brokish, “Fast hierarchical backprojection for helical cone-beam tomography,” Proc. Int. Conf. Image Processing, ICIP-2003, vol. 2, pp. 815–818 Barcelona, Spain, Sept. 2003 .(PDF)
Y. Bresler and J. Brokish, “A hierarchical algorithm for fast backprojection in helical cone-beam tomography,” in Proc. 2nd IEEE Int. Symp. Biomedical Imaging, ISBI-2002, Washington DC, pp. 1420-1423, April 2004.(PDF)
J. Brokish and Y. Bresler, “Noise Performance of Fast Hierarchical 3D Backprojection for Helical Cone-Beam Tomography,” in Proc. 2005 IEEE Medical Imaging Conference, IEEE Nuclear Science Symposium Conference Record, 2005.(PDF)
J. Brokish and Y. Bresler, “Sampling of Shifted Fan Beam Projections for Region of Interest Reconstruction,” in Proc. 2005 IEEE Medical Imaging Conference, IEEE Nuclear Science Symposium Conference Record, 2005.(PDF)
J. Brokish and Y. Bresler, “Sampling Requirements for Circular Cone Beam Tomography,” in Proc. 2006 IEEE Medical Imaging Conference, IEEE Nuclear Science Symposium Conference Record, 2006.(PDF)
J. Brokish and Y. Bresler, “Combined Algorithmic and Hardware Acceleration for Ultra-Fast Backprojection,” in Proc. 2007 IEEE Medical Imaging Conference, IEEE Nuclear Science Symposium Conference Record, 2007.(PDF)
J. Brokish and Y. Bresler, “Ultra-Fast Hierarchical Backprojection for Micro-CT Reconstruction,” in Proc. 2007 IEEE Medical Imaging Conference, IEEE Nuclear Science Symposium Conference Record, 2007.(PDF)
J. Brokish, D. Keesing, and Y. Bresler, “Iterative Circular Cone-Beam CT Reconstruction using Fast Hierarchical Backprojection/Reprojection Operators,” in SPIE Medical Imaging: Physics of Medical Imaging, vol 7622, 2010.(PDF)
J. Brokish, P. Sack, and Y. Bresler, “Combined Algorithmic and GPU Acceleration for Ultra-Fast Circular Cone-Beam Backprojection,” in SPIE Medical Imaging: Physics of Medical Imaging, vol 7622, 2010.(PDF)
J. Brokish, H. Guo, P. Sack, D. Keesing, and Y. Bresler, “Iterative Helical Cone-Beam CT Reconstruction using Fast Hierarchical Backprojection/Reprojection,” in Proc. 2nd CT Meeting, 2012.(PDF)
InstaRecon technology is covered by numerous issued and pending US and foreign patents.