Memory efficient shear-warp voxel projection algorithm
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
26 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
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 yo 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 xo, 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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
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 yo 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 xo 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
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.
-
Specification