Memory efficient shear-warp voxel projection algorithm

• US 6,570,952 B2
• Filed: 02/26/2002
• Issued: 05/27/2003
• Est. Priority Date: 02/27/2001
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Paladini, Gianluca
• Primary Examiner(s): Bruce, David Vernon
• Application Number:
  US10/083,867
• Publication Number:
  US 20020181663A1
• Time in Patent Office: 455 Days
• Field of Search: 378/4, 378/8, 378/15, 378/901
• US Class Current: 378/4
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: Y10S 378/901 Computer tomography program or processor

Abstract

A method is provided for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, the method comprising the steps of: selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; and rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.

Claims

1. A method for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, said method comprising the steps of:

selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; and

rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.

2. The method of claim 1, further comprising the step of constructing a look-up table (LUT) having a plurality of entries for storing at least integer pixel locations of shear projection coordinates that represent sheared locations to be used in a sheared projection of the sample points onto an intermediate shear image buffer, and wherein said rendering step accesses the sample points according to the LUT.

3. The method of claim 2, wherein the integer pixel locations of the shear projection coordinates are stored in the LUT as memory offsets to a frame buffer.

4. The method of claim 2, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is a z_o axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping horizontally by a single pixel;

projecting each of the rows in a current slice, stepping vertically by the single pixel pixel;

projecting each of the plurality of slices, stepping by a current LUT increment specified in the LUT.

5. The method of claim 2, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is a y_o axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping horizontally by a single pixel;

projecting each of the rows in a current slice, stepping by a current LUT increment specified in the LUT;

adding a vertical offset to every LUT element in the LUT, and projecting a next slice.

6. The method of claim 2, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is an x_o, axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping by a current LUT increment specified in the LUT;

projecting each of the rows in a current slice, stepping vertically by a single pixel;

adding a horizontal offset to every LUT element in the LUT, and projecting a next slice.

7. The method of claim 1, wherein each of the scan lines have a same number of the sample points, and each of the plurality of slices have a same number of the scan lines.

8. The method of claim 1, wherein the two out of three dominant viewing directions consist of an x dominant viewing direction and a y dominant viewing direction.

9. The method of claim 1, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.

10. A method for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, said method comprising the steps of:

selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions;

constructing a look-up table (LUT) having a plurality of entries for storing integer pixel locations of shear projection coordinates that represent sheared locations to be used in a sheared projection of the sample points onto an intermediate shear image buffer; and

rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.

11. The method of claim 10, wherein the integer pixel locations of the shear projection coordinates are stored in the LUT as memory offsets to a frame buffer.

12. The method of claim 10, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is a z_o axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping horizontally by a single pixel;

projecting each of the rows in a current slice, stepping vertically by the single pixel pixel;

projecting each of the plurality of slices, stepping by a current LUT increment specified in the LUT.

13. The method of claim 10, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is a y_o axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping horizontally by a single pixel;

projecting each of the rows in a current slice, stepping by a current LUT increment specified in the LUT;

adding a vertical offset to every LUT element in the LUT, and projecting a next slice.

14. The method of claim 10, wherein each of the plurality of entries comprises a slice offset when a principal viewing axis of the image is an x_o axis, and said method comprises the steps of:

projecting every voxel of a current row, stepping by a current LUT increment specified in the LUT;

projecting each of the rows in a current slice, stepping vertically by a single pixel;

adding a horizontal offset to every LUT element in the LUT, and projecting a next slice.

15. The method of claim 10, wherein each of the scan lines have a same number of the sample points, and each of the plurality of slices have a same number of the scan lines.

16. The method of claim 10, wherein the two out of three dominant viewing directions consist of an x dominant viewing direction and a y dominant viewing direction.

17. The method of claim 10, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.

18. A method for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, said method comprising the steps of:

determining a dominant axis of a viewing transformation chosen for generating an image of the three-dimensional volume;

selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions;

factorizing a permuted viewing transformation to obtain shear and warp transformation matrices;

computing a size of an intermediate shear image buffer in which all of the sample points will be projected;

computing a set of shear projection coordinates that represent sheared locations to be used for a sheared projection of the sample points onto the intermediate shear image buffer, according to the shear transformation matrix;

determining an optimal traversal order through the sample points, based on a first determination of whether each of the plurality of slices are to be traversed sequentially front-to-back or back-to-front, a second determination of whether the scan lines are to be traversed sequentially top to bottom or bottom to top, and a third determination of whether the scan lines are to be traversed sequentially from left to right or from right to left;

traversing and projecting the sample points stored in each of the scan lines;

warping a resulting shear image buffer onto the image, according to the shear transformation matrix.

19. The method of claim 18, wherein for a z dominant viewing direction said traversing and projecting steps comprise the step of employing the set of shear projection coordinates as an origin of each of a plurality of projected slices.

20. The method of claim 18, wherein for the y dominant viewing direction, said traversing and projecting steps comprise the steps of:

employing the set of shear projection coordinates as an origin of each of the scan lines; and

incrementing the set of shear projection coordinates in a chosen slice direction.

21. The method of claim 18, wherein for a x dominant viewing direction, said traversing and projecting steps comprise the steps of:

employing the set of shear projection coordinates as a projection location of each of the sample points; and

incrementing the set of shear projection coordinates in a chosen scan line and a chosen slice direction after each of the scan lines has been projected.

22. The method of claim 18, further comprising the step of interpolating a new sample point value at a projected location in the shear image buffer, using destination-driven interpolation.

23. The method of claim 18, wherein each of the scan lines have a same number of the sample points, and each of the plurality of slices have a same number of the scan lines.

24. The method of claim 18, wherein the two out of three dominant viewing directions consist of an x dominant viewing direction and a y dominant viewing direction.

25. The method of claim 18, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.

26. A program storage device having a program executable by a computer for performing method steps for generating an image of a three-dimensional (3D) volume from a plurality of slices corresponding to a scan of the 3D volume, each of the plurality of slices comprising slice data for sample points within an image plane, each of the sample points being stored sequentially in rows of scan lines, said method comprising the steps of:

selecting a permutation matrix such that each of the sample points stored in the scan lines of all of the plurality of slices can be projected in a sequential order without requiring the slice data to be transposed for two out of three dominant viewing directions respectively corresponding to two of out of three dimensions; and

rendering the image by accessing the sample points in a voxel-by-voxel, row-by-row, and slice-by-slice sequence.