X-ray or gamma ray systems or devices – Specific application – Computerized tomography
Reexamination Certificate
2002-02-26
2003-05-27
Bruce, David Vernon (Department: 2882)
X-ray or gamma ray systems or devices
Specific application
Computerized tomography
C378S019000, C378S901000
Reexamination Certificate
active
06570952
ABSTRACT:
BACKGROUND
1. Technical Field
The present invention generally relates to three-dimensional imaging and, in particular, to a memory efficient shear-warp volume rendering method.
2. Background Description Shear-warp volume rendering algorithms transform a volume to an intermediate coordinate system, referred to as the “sheared object space”, in which voxel data can be projected efficiently. The transposed dataset having the set of slices most perpendicular to the viewing direction is projected in sheared object space, and then the resulting intermediate image is warped back from sheared object coordinates to image coordinates to produce the final output image.
Conventional shear-warp algorithms by Klein et al., Lacroute et al., Cameron et al., and so forth, transpose voxel data so that parallel slices can be sheared into an intermediate image. Two additional transposed copies of the voxel data are generated, usually during a pre-processing step, leading to triple redundancy of data in memory. The shear-warp algorithm of Klein et al., is described in “A Prebuffer Algorithm for Instant Display of Volume Data”, Proceedings of SPIE (Architectures and Algorithms for Digital Image Processing), Vol. 596, pp. 54-58, 1985. The shear-warp algorithm of Lacroute et al. is described in “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transform”, ACM SIGGRAPH Computer Graphics Proceedings, Annual Conferences Series, July, pp. 451-458, 1994. The shear-warp algorithm of Cameron et al., is described in “Rendering Volumetric Medial Image Data on a SIMD Architecture Computer”, Proceedings of the Third Eurographics Workshop on Rendering, Bristol, UK, pp. 135-145, 1992.
Accordingly, it would be desirable and highly advantageous to have a shear-warp method that eliminates the two additional and redundant transposed datasets and that always traverses the original dataset in a slice-by-slice fashion, without having to generate transposed data.
SUMMARY OF THE INVENTION
The problems stated above, as well as other related problems of the prior art, are solved by the present invention, a memory efficient shear-warp method.
Advantageously, the method of the present invention produces results at least identical to existing shear-warp algorithms with respect to image rendering, but with the following advantages over the existing shear-warp algorithms. The pre-processing time to generate transposed slices is not needed. Moreover, the triple redundancy of allocated memory for transposed data is not needed. Further, it is not necessary to access memory addresses in transposed order (which also would require all the volume slices to be located in memory).
The method of the present invention has very low memory requirements since, for example, the original voxel data is preferably always accessed in a slice-by-slice fashion. Therefore, as long as the computer has enough memory to hold one slice of data, volumes with an unlimited number of slices can be rendered.
According to an embodiment of the present invention, 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 is provided, 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.
According to another embodiment of the present invention, 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, 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.
A method is also 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: 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.
According to still another aspect of the invention, a program storage device is provided, the 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, 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.
These and other aspects, features and advantages of the present invention will become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings.
REFERENCES:
patent: 5787889 (1998-08-01), Edwards et al.
patent: 6407737 (2002-06-01), Zhao et al.
patent: 2003/0012419
Bruce David Vernon
F. Chau & Associates LLP
Paschburg Donald B.
Siemens Corporate Research Inc.
LandOfFree
Memory efficient shear-warp voxel projection algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory efficient shear-warp voxel projection algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory efficient shear-warp voxel projection algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065415