Fast hierarchical backprojection for 3D Radon transform

• US 6,307,911 B1
• Filed: 03/30/2000
• Issued: 10/23/2001
• Est. Priority Date: 06/23/1999
• Status: Expired due to Term

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Bresler, Yoram, Basu, Samit
• Primary Examiner(s): BRUCE, DAVID VERNON
• Application Number:
  US09/539,074
• Time in Patent Office: 572 Days
• Field of Search: 378/4, 378/8, 378/15, 378/901
• US Class Current: 378/15
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/006 Inverse problem, transformation from projection-space into object-space, e.g. transform methods, back-projection, algebraic methods
• CPC Class Codes: Y10S 378/901 Computer tomography program or processor

Abstract

Data representing a three-dimensional (3D) sinogram (array of numbers) is backprojected to reconstruct a 3D volume. The transformation requires N³ log₂ N operations. An input sinogram is subdivided into a plurality of subsinograms using either an exact or approximate decomposition algorithm. The subsinograms are repeatedly subdivided until they represent volumes as small as one voxel. The smallest subsinograrns 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.

Claims

1. A process for generating a three-dimensional electronic volume from a sinogram comprising the steps of

subdividing the sinogram into a plurality of subsinograms;

backprojecting each of said subsinograms to produce a plurality of corresponding sub-volumes, and

aggregating said sub-volumes to create the electronic volume.

2. The method of claim 1 wherein said subdividing step includes performing a number of approximate subdivisions.

3. The method of claim 1 wherein said subdividing step includes performing a number of exact subdivisions.

4. The method of claim 1 wherein said sinogram is subdivided into a plurality of subsinograms in a recursive manner, wherein said subdividing steps include a number of exact subdivisions and a number of approximate subdivisions.

5. The method of claim 1 wherein said aggregation step is performed in a recursive manner.

6. The method of claim 1 wherein said electronic volume is a tomographic volume.

7. The method of claim 1 further comprising preprocessing in which angular and radial oversampling are used to improve the accuracy of the electronic volume.

8. The method of claim 1 wherein said sinograms are subdivided in a recursive manner, until each subsinogram represents a volume of a desired size.

9. The method of claim 8 wherein said subsinograms correspond to volumes as small as one voxel in size.

10. The method of claim 1 wherein the sinogram includes filtered projections.

20. The method of claim 2 wherein said approximate subdivision steps include radial truncation and shifting, and angular decimation of the sinogram.

21. The method of claim 3 wherein said exact subdivision steps include radial truncation and shifting.

11. Apparatus for generating a three-dimensional electronic volume of an object comprising:

means for scanning the object to generate data representing a volume of the object;

means for processing said data to generate a sinogram which includes a plurality of filtered projections;

means for subdividing said sinogram into a plurality of subsinograms;

means for backprojecting each of said subsinograms to produce a plurality of corresponding subvolumes;

means for aggregating said subvolumes to create the electronic volume; and

means for displaying the electronic volume.

12. The apparatus of claim 11 wherein said means for subdividing performs a number of approximate subdivisions.

13. The apparatus of claim 11 wherein said means for subdividing performs a number of exact subdivisions.

14. The apparatus of claim 11 wherein said sinograms are subdivided into a plurality of subsinograms in a recursive manner, wherein said means for subdividing performs a number of exact subdivisions and a number of approximate subdivisions.

15. The apparatus of claim 11 wherein said means for aggregating operates in a recursive manner.

16. The apparatus of claim 11 wherein said electronic volume is a tomographic volume.

17. The apparatus of claim 11 wherein said means for processing performs angular and radial oversampling to improve the accuracy of the electronic volume.

18. The apparatus of claim 11 wherein said means for subdividing operates in a recursive manner, until each subsinogram represents a volume of a desired size.

19. The apparatus of claim 18 wherein said subsinograms correspond to volumes as small as one voxel in size.

22. The apparatus of claim 12 wherein said approximate subdivisions include radial truncation and shifting, and angular decimation of the sinogram.

23. The apparatus of claim 13 wherein said exact subdivisions include radial truncation and shifting.