System and method for fast parallel cone-beam reconstruction using one or more microprocessors

• US 6,477,221 B1
• Filed: 02/16/2001
• Issued: 11/05/2002
• Est. Priority Date: 02/16/2001
• Status: Active Grant

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Ning, Ruola
• Primary Examiner(s): BRUCE, DAVID VERNON
• Application Number:
  US09/784,331
• Publication Number:
  US 20020154727A1
• Time in Patent Office: 627 Days
• Field of Search: 378/4, 378/15, 378/901
• US Class Current: 378/4
• CPC Class Codes: A61B 6/032 Transmission computed tomography [CT]
• CPC Class Codes: A61B 6/4085 Cone-beams
• CPC Class Codes: A61B 6/583 using calibration phantoms
• CPC Class Codes: G01N 2223/419 computed tomograph
• CPC Class Codes: G01N 23/046 using tomography, e.g. computed tomography [CT]
• 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: G06T 2211/428 Real-time
• CPC Class Codes: Y10S 378/901 Computer tomography program or processor

Abstract

Cone-beam reconstruction is performed within a practically acceptable time on a computer having one or more microprocessors. The calculations involved in the reconstruction are divided into calculations to be performed on the MMX, ALU and SSE units of each of the microprocessors. For pure floating-point data, it is preferred to use the MMX unit to adjust the data address and map data and to use the SSE unit to perform the backprojection. The data are partitioned by z-line so that the data to be processed in each stage of the backprojection fit within the L1 cache.

Claims

1. A system for generating a three-dimensional image representative of an interior portion of an object, the system comprising:

a radiation scanner which generates projection signals by passing a radiation through the object onto a detector; and

a computer, receiving the projection signals, for generating the three-dimensional image by performing a plurality of calculations on the projection signals, the computer comprising at least one fixed-point processing unit and at least one floating-point processing unit, the at least one fixed-point processing unit operating in parallel with the at least one floating-point processing unit, the computer dividing the plurality of calculations into a first plurality of calculations to be performed in the at least one fixed-point processing unit and a second plurality of calculations to be performed in the at least one floating-point processing unit.

2. The system of claim 1, wherein the radiation scanner is a radiation cone-beam scanner, the radiation beam is a radiation come beam, and the projection signals are cone-beam projection signals.

3. The system of claim 2, wherein:

the first plurality of calculations comprise generation of a projection map; and

the second plurality of calculations comprise backprojection of the cone-beam projection signals in accordance with the projection map to produce the image.

4. The system of claim 3, wherein:

the generation of the projection map comprises mapping a world coordinate system (x, y, z) to a coordinate system (u, t, s) of the detector, where u is independent of z;

the computer organizes the cone-beam projection signals into z-lines for which varies but x and y are constant; and

the computer performs the backprojection for each of the z-lines.

5. The system of claim 3, wherein, after the computer has performed the backprojection for all of the z-lines to form the image as a plurality of voxels, the computer performs a three-dimensional transpose operation on the voxels in the image to organize the voxels into x-lines for which x varies but y and z are constant.

6. The system of claim 4, wherein the computer further comprises a cache which is large enough to hold one of the z-lines.

7. The system of claim 1, wherein the projection signals are processed as pure floating-point data.

8. The system of claim 1, wherein the projection signals are processed as a mixture of floating-point and fixed-point data.

9. The system of claim 1, wherein the computer comprises a microprocessor on which the at least one fixed-point processing unit which can process more than one 16 bit or 32 bit integer data within one instruction set and the at least one floating-point processing unit which can process more than one single-precision 32 bit float point data within one instruction set are implemented.

10. The system of claim 9, wherein the computer comprises a plurality of said microprocessors, each of which comprises at least one said fixed-point processing unit which can process more than one 16 bit or 32 bit integer data within one instruction set and at least one said floating-point processing unit which can process more than one single-precision 32 bit float point data within one instruction set.

11. The system of claim 1, wherein the image is a linear attenuation coefficient distribution of the interior portion of the object.

12. The system of claim 1, wherein:

a boundary of the object is known a priori; and

the three-dimensional image is generated only within the boundary.

26. The method of claim 12, wherein the object comprises soft tissue.

27. The method of claim 26, wherein the image is used to detect cancer in the soft tissue.

28. The method of claim 12, wherein step (b) is performed using manually written assembly language. one single-precision 32 bit float point data within one instruction set.

31. The method of claim 12, wherein step (b) is performed through multi-threading only when a plurality of processors are available.

13. A method of generating a three-dimensional image representative of an interior portion of an object, the method comprising:

(a) passing a through the object onto a detector to generate projection signals; and

(b) receiving the projection signals and generating the three-dimensional image by performing a plurality of calculations on the projection signals;

wherein step (b) is performed on a computer comprising at least one fixed-point processing unit and at least one floating-point processing unit, the at least one fixed-point processing unit operating in parallel with the at least one floating-point processing unit, the computer dividing the plurality of calculations into a first plurality of calculations to be performed in the at least one fixed-point processing unit and a second plurality of calculations to be performed in the at least one floating-point processing unit.

14. The method of claim 13, wherein the beam is a cone beam and the projection signals are cone-beam projection signals.

15. The method of claim 14, wherein:

the first plurality of calculations comprise generation of a projection map; and

the second plurality of calculations comprise backprojection of the cone-beam projection signals in accordance with the projection map to produce the reconstructed image.

16. The method of claim 15, wherein:

the generation of the projection map comprises mapping a world coordinate system (x, y, z) to a coordinate system (u, t, s) of the detector, where u is independent of z;

the computer organizes the cone-beam projection signals into z-lines for which z varies but x and y are constant; and

the computer performs the backprojection for each of the z-lines.

17. The method of claim 16, wherein the computer further comprises a cache which is large enough to hold one of the z-lines.

18. The method of claim 16, wherein, after the computer has performed the backprojection for all of the z-lines to form the image as a plurality of voxels, the computer performs a three-dimensional transpose operation on the voxels in the

19. The method of claim 14, wherein step (b) is performed using a filtered backprojection cone beam reconstruction algorithm.

20. The method of claim 19, wherein a filtered backprojection cone beam reconstruction algorithm is carried out using hybrid computing utilizing a single instruction multiple data technique.

21. The method of claim 20, wherein a filtered backprojection cone beam reconstruction algorithm is carried out using multi-threading over a plurality of processors. image to organize the voxels into x-lines for which x varies but y and z are constant.

22. The method of claim 14, wherein step (b) is performed through Feldkamp cone-beam reconstruction by:

(i) performing hybrid computing utilizing single instruction multiple data (SIMD) over a plurality of execution units;

(ii) using multi-thread and fiber support in an operating system so as to automatically enable reconstruction parallelism in a multi-processor environment effective datat I/O; and

(iii) optimizing memory and cache access through data partitioning.

23. The method of claim 14, wherein step (b) is performed by parallel processing on a single microprocessor or multiple processors using hybrid computing to accelerate cone-beam reconstruction for reconstruction of soft tissue.

24. The method of claim 13, wherein the computer comprises a microprocessor on which the at least one fixed-point processing unit which can process more than one 16 bit or 32 bit integer data within one instruction set and the at least one floating-point processing unit which can process more than one single-precision 32 bit float point data within one instruction set are implemented.

25. The method of claim 24, wherein the computer comprises a plurality of the microprocessors, each of which comprises at least one said fixed-point processing unit which can process more than one 16 bit or 32 bit integer data within one instruction set and at least one said floating-point processing unit which can process more than

29. The method of claim 13, wherein the image is a linear attenuation coefficient distribution of the interior portion of the object.

30. The method of claim 13, wherein the projection signals are processed as a mixture of floating-point and fixed-point data.

32. The method of claim 13, wherein the projection signals are processed as pure floating-point data.

33. The method of claim 13, wherein:

a boundary of the object is known apriori; and

the three-dimensional image is generated only within the boundary.