Fast hierarchical backprojection for 3D Radon transform

Details Fast hierarchical backprojection for 3D Radon transform Fast hierarchical backprojection for 3D Radon transform

2000-03-30

2001-10-23

Bruce, David V. (Department: 2882)

X-ray or gamma ray systems or devices

Specific application

Computerized tomography

C378S004000, C378S901000

Reexamination Certificate

active

06307911

ABSTRACT:

FIELD OF THE INVENTION
The present invention generally concerns imaging. More specifically, the present invention concerns a method of reconstructing three-dimensional tomographic volumes from projections.
BACKGROUND OF THE INVENTION
Tomographic volumes are created from line integral measurements of an unknown object at a variety of orientations. These line integral measurements, which may represent measurements of density, reflectivity, etc., are then processed to yield a volume that represents the unknown object. Data generated in this manner is collected into a sinogram, and the sinogram is processed and backprojected to create two-dimensional images or three-dimensional volumes.
The process of backprojection of three-dimensional (3D) Radon transform data is a key step in the reconstruction of volumes from tomographic data. The 3D Radon transform underlies a number of existing and emerging technologies, such as Synthetic Aperture Radar (SAR), volumetric Magnetic Resonance Imaging (MRI), cone-beam X-ray tomography, etc. The backprojection step is intensive from a computation standpoint, and slow. Thus, there is a need for methods for backprojecting 3D Radon data which are less costly and less time consuming.
Accordingly, one object of this invention is to provide new and improved imaging methods.
Another object is to provide new and improved methods for backprojecting 3D volume data.
Still another object is to provide new and improved methods for backprojecting 3D volume data which are less costly in terms of hardware and computational expense, and faster than known methods.
SUMMARY OF THE INVENTION
Data representing a 3D sinogram (array of numbers) is backprojected to reconstruct a 3D volume. The transformation requires N
3
log
2
N operations.
An input sinogram is subdivided into a plurality of subsinograms using decomposition algorithms. The subsinograms are repeatedly subdivided until they represent volumes as small as one voxel. The smallest subsinograms are backprojected using the direct approach to form a plurality of subvolumes, and the subvolumes are aggregated to form a final volume.
Two subdivision algorithms are used. The first is an exact decomposition algorithm, which is accurate, but slow. The second is an approximate decomposition algorithm which is less accurate, but fast. By using both subdivision algorithms appropriately, high quality backprojections are computed significantly faster than existing techniques.


REFERENCES:
patent: 4042811 (1977-08-01), Brunnett et al.
patent: 4149247 (1979-04-01), Pavkovich et al.
patent: 4217641 (1980-08-01), Naparstek
patent: 4491932 (1985-01-01), Ruhman et al.
patent: 4616318 (1986-10-01), Crawford
patent: 4626991 (1986-12-01), Crawford et al.
patent: 4709333 (1987-11-01), Crawford
patent: 4714997 (1987-12-01), Crawford et al.
patent: 4858128 (1989-08-01), Nowak
patent: 4930076 (1990-05-01), Meckley
patent: 4991093 (1991-02-01), Roberge et al.
patent: 5008822 (1991-04-01), Brunnett et al.
patent: 5136660 (1992-08-01), Flickner et al.
patent: 5224037 (1993-06-01), Jones et al.
patent: 5229934 (1993-07-01), Mattson et al.
patent: 5243664 (1993-09-01), Tuy
patent: 5300782 (1994-04-01), Johnston et al.
patent: 5375156 (1994-12-01), Kuo-Petravic et al.
patent: 5396528 (1995-03-01), Hu et al.
patent: 5438602 (1995-08-01), Crawford et al.
patent: 5552605 (1996-09-01), Arata
patent: 5559335 (1996-09-01), Zeng et al.
patent: 5579358 (1996-11-01), Lin
patent: 5625190 (1997-04-01), Crandall
patent: 5654820 (1997-08-01), Lu et al.
patent: 5727041 (1998-03-01), Hsieh
patent: 5778038 (1998-07-01), Brandt et al.
patent: 5796803 (1998-08-01), Flohr et al.
patent: 5805098 (1998-09-01), McCorkle
patent: 5848114 (1998-12-01), Kawai et al.
patent: 5862198 (1999-01-01), Samarasekera et al.
patent: 5901196 (1999-05-01), Sauer et al.
patent: 6028907 (2000-02-01), Adler et al.
patent: 6108007 (2000-08-01), Shochet
patent: 611181 (1994-08-01), None
Martin L. Brady; “A Fast Discrete Approximation Algorithm for the Radon Transform”;SIAM J. Comput.vol. 27, No. 1, pp. 107-119; Feb. 1998.
A. Brandt et al.; “Fast Calculation of Multiple Line Integrals”;SIAM J. Sci. Comput., vol. 20, No. 4, pp. 1517-1429; 1999.
Achi Brandt et al.; :A Fast and Accurate Multilevel Inversion of the Radon Transform;SIAM J. Appl. Math., vol. 60, No. 2, pp. 437-462; 1999.
Carl R. Crawford; “Reprojection Using a Parallel Backprojector”; Elscint Ltd., P.O. Box 5258, Haifa, Israel; Mar. 12, 1986.
Carl R. Crawford et al.; “High Speed Reprojection and its Applications”;SPIE vol. 914 Medical Imaging II; 1988.
Per-Erik Danielsson et al.; Backprojection in O(N2logtN) Time; IEEE Medial Imaging Conference, Albuquerque, NM; Nov. 12-15, 1997.
Alexander H. Delaney; “A Fast and Accurate Fourier Algorithm for Iterative Parallel-Beam Tomography”;IEEE Transactions on Image Processing, vol. 5, No. 5, pp. 740-753; May 1996.
E.C. Frey et al.; “A Fast Projector-Backprojector Pair Modeling the Asymmetric, Spatially Varying Scatter Response Function for Scatter Compensation in SPECT Imaging”;IEEE Transactions on Nuclear Science, vol. 40, No. 4, pp. 1192-1197; Aug. 1993.
Sung-Cheng Huang et al.; “Capability Evaluation of a Sinogram Error Detection and Correction Method in Computed Tomography”;IEEE Transactions on Nuclear Science, vol. 39, No. 4, pp. 1106-1110; 1992.
Eric Michielssen; “A Multilevel Matrix Decomposition Algorithm for Analyzing Scattering from Large Structures”;IEEE Transactions on Antennas and Propagation, vol. 44, No. 8, pp. 1086-1093; Aug. 1996.
John M. Ollinger; “Iterative Reconstruction-Reprojection and the Expectation-Maximization Algorithm”;IEEE Transactions on Medical Imaging, vol. 9, No. 1, pp. 94-98; Mar. 1990.
John M. Ollinger; “Reconstruction-Reprojection Processing of Transmission Scans and the Variance of PET Images”;IEEE Transactions on Nuclear Science, vol. 39, No. 4, pp. 1122-1125; 1992.
T.M. Peters; “Algorithms for Fast Back-and-Re-Projection in Computed Tomography”;IEEE Transactions on Nuclear Science, voll NS-28, No. 4, pp. 3641-3646; Aug. 1981.
Jorge L.C. Sanz; “Computing Projections of Digital Images in Image Processing Pipeline Architectures”;IEEE Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-35, No. 2, pp. 198-207; Feb. 1987.
Herman Schomberg et al.; “The Gridding Method for Image Reconstruction by Fourier Transformation”;IEEE Transactions on Medical Imaging, vol. 14, No. 3, pp. 596-607; Sep. 1995.
Dan-Chu Yu et al.; “Study of Reprojection Methods in Terms of Their Resolution Loss and Sampling Errors”;IEEE Transactions on Nuclear Science, vol. 40, No. 4, pp. 1174-1178; Aug. 1993.
G.L. Zeng; “A Rotating and Warping Projector/Backprojector for Fan-Beam and Cone-Beam Iterative Algorithm”;IEEE Transactions on Nuclear Science, vol. 41, No. 6, pp. 2807-2811; Dec. 1994.
Gary H. Glover et al.; “An Algorithm for the Reduction of Metal Clip Artifacts in CT Reconstructions”;Medical Physics, vol. 8, No. 6, pp. 799-807; Nov./Dec. 1981.
Cobb et al; “Real-time Image Formation Effort Using Quadtree Backprojection and Reconfigurable Processing”;Third Annual Federated Laboratory Symposium on Advanced Sensors; pp. 133-137; Feb. 2-4, 1999.
Oh et al.; “Multi-resolution Mixed-radix Quadtree SAR Image Focusing Algorithms”; Third Annual Federated Laboratory Symposium on Advanced Sensors; pp. 139-143; Feb. 2-4, 1999.
Marr et al; “On two approaches to 3D reconstruction in NMR Zeumatography”;Mathematical Aspects of Computerized Tomography Proceedings, Oberwolfach, pp 225-240; Feb. 10-16, 1980.
Axelsson et al.; Three-dimensional reconstruction from cone-beam data in O(N3log N) time;Phys. Med. Biol. 39, pp 477-491; 1994.
Clack et al.; “Cone-beam reconstruction by the use of Radon transform intermediate functions”;Journal of the Optical Society of AmericaA/vol. 11, No. 2, pp 580-585; Feb. 1994.
Nicolas J. Dusaussoy; VOIR: A Volumetric Image Reconstruction Algorithm Based on Fourier Techniques for Inversion of the 3-D Radon Transform;IEEE Transactions on Image Processing, vol. 5, No. 1, pp 121-131; Jan. 1996.
V. P. Palamadov; Localization of Harmonic Decomposition of

Affiliated with

Also associated with

Rating

Fast hierarchical backprojection for 3D Radon transform does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast hierarchical backprojection for 3D Radon transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast hierarchical backprojection for 3D Radon transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2611430