Fast hierarchical backprojection method for imaging

Details Fast hierarchical backprojection method for imaging Fast hierarchical backprojection method for imaging

1999-10-15

2001-08-28

Bruce, David V. (Department: 2882)

X-ray or gamma ray systems or devices

Specific application

Computerized tomography

C378S004000, C378S901000

Reexamination Certificate

active

06282257

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to imaging, and more particularly, to a method for reconstructing tomographic images from projections.
BACKGROUND OF THE INVENTION
The reconstruction problem in 2D axial computed tomography (CT) is one of recovering an image from a set of its line-integral projections at different angles. The type of algorithm used to address the reconstruction problem depends almost exclusively on how much of the line-integral information is available. When line-integrals are available from all possible directions, and the measurement noise is negligible, the Filtered BackProjection (FBP) reconstruction technique (also known as the Convolution BackProjection technique, or CBP) is a popular method. Based on a discretization of an inverse formula for the Radon transform, the FBP consists of filtering each projection by a prespecified filter, followed by a backprojection operation. The filtering operation requires O(N
2
log N) operations when implemented by an FFT, or as little as O(N
2
) operations when implemented as a convolution with a fixed impulse response. In contrast, the backprojection operation, which computes for each pixel in the reconstructed image the sum of all line integrals that pass through that pixel, requires O(N
3
) operations, assuming a reconstruction of N
2
pixels, and projections at O(N) angles. Backprojection, therefore, by far dominates the computational cost of FBP (or CBP) reconstruction.
Traditionally, for medical applications, backprojection has been accomplished by special hardware that exploits parallelism of the backprojection process to try and achieve near real-time reconstruction of a single slice. See, e.g., U.S. Pat. No. 4,042,811 and U.S. Pat. No. 4,491,932. However, there still exists a lag in reconstruction time that is becoming increasingly important as technologies that are able to acquire data at ever faster rates are being introduced. With the increasing data rates, the FBP has become the bottleneck in the reconstruction and display process, and presents a barrier to real-time imaging.
Existing fast algorithms for reconstruction are based on either the Fourier Slice Theorem, or on a multi-resolution resampling of the backprojection, such as Brandt's method of U.S. Pat. No. 5,778,038, which is incorporated by reference in its entirety. Algorithms based on the Fourier Slice Theorem use interpolations to transform the Fourier projection data from a polar to a Cartesian grid, from which the reconstruction can be obtained by an inverse FFT. These fast algorithms, known as Fourier reconstruction algorithms (FRA), generally have O(N
2
log N) complexity. J. Schomberg and J. Timmer, “The Gridding Method for Image Reconstruction by Fourier Transformation”, IEEE Trans. Med. Imag., vol. 14, September 1995. Unfortunately, the interpolation step generally requires a large number of computations to avoid the introduction of artifacts into the reconstruction. Experimental evidence indicates that for reasonable image sizes N≦10
3
, the realized performance gain of algorithms based on the Fourier Slice Theorem over the more straightforward FBP is significantly less than the potential N/log N speedup. This also generally comes at a loss in reconstruction quality as well.
Brandt's method uses different nonuniformly sampled grids to efficiently represent the projections at different stages of the backprojection. The resulting algorithm has O (N
2
log N) complexity. The algorithm generates blurred reconstructions, so a postprocessing step involving a deconvolution with a Gaussian approximation to the point spread function is necessary to counteract the blurring. This deconvolution stop is not fully effective, and can lead to further artifacts. This algorithm, although potentially fast, does not achieve the accuracy of conventional FBP. Thus, there is a need for faster and accurate algorithms for reconstruction of tomographic images.
Accordingly, one object of this invention is to provide new and improved reconstruction methods for creating images from projections.
Another object is to provide new and improved methods for reconstructing tomographic images which are faster than existing methods.
Yet another object is to provide new and improved methods for tomographic backprojection for use in all applications where existing methods are used, but which are faster than existing methods.
SUMMARY OF THE INVENTION
In keeping with one aspect of this invention, a method for backprojecting sinograms to images includes the steps of dividing a filtered sinogram into a plurality of subdivisions, each a smaller sinogram. The smaller sinograms are successively subdivided until the divisions represent a subimage as small as one pixel. The subsinograms are backprojected to create subimages, and the subimages are successively aggregated to create the image for display.
The method uses two algorithms to subdivide the sinogram. For one algorithm subdivision is exact, and for the other algorithm the subdivision is an approximation. The first algorithm is accurate, but relatively slow, and the second algorithm is faster, but less accurate. By performing some subdivisions with the exact decomposition algorithm and some subdivisions with the approximation decomposition algorithm, switching between the two algorithms in one of a number of suitable ways, an accurate result can be obtained quickly.


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
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), Brunett 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 a.
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: 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), Sochet
patent: 611181 (1994-08-01), None
Stephan Nilsson; Fast Backprojection; Dept. Of Electrical Eng., Linkopings universitet, Sweden, pp 1-8; Jul. 4, 1996.
Per-Erik Danielsson; Iterative Techniques for Projection and Back-Projection and Back-Projection; Dept. Of Electrical Eng., Linkopings universitet, Sweden, pp 1-28, Jun. 10, 1997.
Stephan Nilsson; Application of fast backprojection techniques for some inverse problems of intergral geometry; Dept. Of Mathematics., Liknopings universitet, Sweden, Jun. 19, 1997.
Cobb et al; “Real-time Image Formation Effort Using Quadtree Backprojection and Reconfigurable Processing”; Third Annual Federated Laboratory 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.
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.
C

Affiliated with

Also associated with

Rating

Fast hierarchical backprojection method for imaging 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 method for imaging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast hierarchical backprojection method for imaging will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2496837