Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
2000-12-01
2004-02-03
Ahmed, Samir (Department: 2623)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S280000, C345S606000, C708S403000
Reexamination Certificate
active
06687422
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to digital images and image processing and, more particularly, to a method of interpolating missing elements from originally sampled images and generating an interpolated image therefrom.
BACKGROUND OF THE INVENTION
With continuous improvements of imaging and computing technologies, more and more medical images are provided in digital form. Digital images can be easily manipulated on a computer to enhance or extract some properties which are clinically valuable, but may not be available with conventional images on films. In advanced radiotherapy treatment planning for instance, the computer tomography (CT) number in a voxel is used to determine the tissue attenuation which affects the radiation deposition in the tissue. In many clinical applications, such as visualization, quantitative measurements, and analysis, it is frequently necessary to interpolate an image so that different image properties can be explored.
Image interpolation is a process used to estimate the missing elements from the original sampling grid or image. If the sampling rate of a data set satisfies the Nyquist sampling criterion, the missing data in principle can be fully recovered by convoluting the discrete data with the continuous interpolating function (sinc function). Since the sinc function is an infinite function while digital images are always confined within a finite field, the interpolation can only be approximated. A major drawback in image implementation using the sinc function however is the computation efficiency.
In order to improve the computation efficiency with acceptable interpolation quality, different interpolation approaches have been developed. The most popular scheme is based on convolution techniques with selected kernels. The simplest kernel is the nearest-neighbor function, where the values of the interpolating points are copied from the nearest samples. Another widely used kernel is the first order polynomial function, where the value at an interpolating point is a linear combination of the adjacent samples. A major problem with these kernels is the unsatisfactory interpolation quality with staircase (i.e., blocky) artifacts in the resulting images. More complex kernels in this category are the quadratic and cubic spline functions. It has been showed that a spline function approximates a truncated version of the sinc function. Since a spline function is a piecewise continuous polynomial function, complexity and computing efficiency are the drawbacks. Improper selection of the spline function parameters may also significantly blur the resulting image. Alternatively, wavelet-based and Gaussian kernels have also been proposed. These can be summarized as attempts to improve the approximation of the truncated sinc function. Another class of image interpolation techniques is based on object connectivity and relative displacement. All of the aforementioned processing techniques suffer from the undesirable effects of long computation times and computational inefficiency that make these approaches impractical in routine clinical applications. Consequently, an image process method that does not suffer from such disadvantages is highly desirable.
SUMMARY OF THE INVENTION
According to one embodiment of the present invention, an image interpolation method based on a sub-unity coordinate shift technique is provided. In the approach, an original digital image in the spatial domain (e.g., Cartesian coordinate system (x,y)) is transformed into a frequency domain representation via a Fourier transform. The Fourier transform representation is then modified by phase shift terms corresponding to image shifts in the spatial domain with sub-unity distances matching the locations where the image values need to be restored. The original and the shifted images are then interspersed together, yielding an interpolated image. The present approach can achieve an interpolation quality as good as that with the sinc function since the sub-unity shift in Fourier domain is equivalent to shifting the sinc function in spatial domain, while the efficiency, thanks to the fast Fourier transform (FFT), is very much improved. In comparison to the conventional interpolation techniques such as linear or cubic B-spline interpolation, the interpolation accuracy is significantly enhanced. The method is especially applicable to two and three-dimensional computer tomography (CT) and magnetic resonance imaging (MRI) images, as well as other medical and non-medical digital images.
It is therefore an advantage of the present invention to provide a method for interpolating digital images to recover lost image data due to digitization.
It is a further advantage of this invention to provide a method for processing digital images that is computationally efficient.
It is yet a further advantage of the present invention to provide a method for processing digital images that is particularly suited to medical images such as, for example, computer tomography (CT) and magnetic resonance imaging (MRI).
REFERENCES:
patent: 5170170 (1992-12-01), Soumekh
patent: 5481275 (1996-01-01), Mical et al.
patent: 5566284 (1996-10-01), Wakayama
patent: 5917940 (1999-06-01), Okajima et al.
patent: 6178271 (2001-01-01), Maas, III
patent: 6181135 (2001-01-01), Shen
patent: 6456745 (2002-09-01), Bruton et al.
patent: 6507859 (2003-01-01), Omori et al.
“Image Approximation by Variable Knot Bicubic Splines.” Dennis G. McCaughey, and Harry C. Andrews, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-3, No. 3, May 1981, pp. 299-310.
“Simple Algorithms and Architectures for B-Spline Interpolation.” P.V. Sankar and L.A. Ferrari, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, No. 2, Mar. 1988, pp. 271-276.
“Fast B-Spline Transforms for Continuous Image Representation and Interpolation.” Michael Unser, Akram Aldroubi, Murray Eden, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, No. 3, Mar. 1991, pp. 277-285.
“Quadratic Interpolation for Image Resampling.” Neil A. Dodgson, IEEE Transactions on Image Processing, vol. 6, No. 9, Sep., 1997, pp. 1322-1326.
“Interpolation Using Wavelet Bases.” Alex P. Pentland, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, No. 4, Apr. 1994, pp. 410-414.
“A New Approach to the Interpolation of Sampled Data.” C. Robert Appledorn, IEEE Transactions on Medical Imaging, vol. 15, No. 3, Jun. 1996, pp. 369-376.
“Fast Surface Interpolation Using Multiresolution Wavelet Transform.” Ming-Haw Yaou and Wen-Thong Chang, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, No. 7, Jul. 1994, pp. 673-688.
“Directional Interpolation for Magnetic Resonance Angiography Data.” Mehran Moshfeghi, IEEE Transaction on Medical Imaging, vol. 12, No. 2, Jun. 1993, pp. 366-379.
“Shape-Based Interpolation of Tree-Like Structures in Three-Dimensional Images.” W.E. Higgins, C. Morice, and E. L. Ritman, IEEE Transactions on Medical Imaging, vol. 12, No. 3, Sep. 1993, pp. 439-450.
“Shape-Based Interpolation of Multidimensional Grey-Level Images.” George J. Grevera and Jayaram K. Udupa, IEEE Transactions on Medical Imaging, vol. 15, No. 6, Dec. 1996, pp. 881-890.
“Nonlinear Filtering Approach to 3-D Grey-Scale Image Interpolation.” William E. Higgins, Christopher J. Orlick, and Brian E. Ledell, IEEE Transactions on Medical Imaging, vol. 15, No. 4, Aug. 1996, pp. 580-587.
“Convolution-Based Interpolation for Fast, High-Quality Rotation of Images.” Michael Unser, Philippe Thévenaz, and Leonid Yaroslavsky, IEEE Transactions on Image Processing, vol. 4, No. 10, Oct. 1995, pp. 1371-1381.
“Sequential Linear Interpolation of Multidimensional Functions.” James Z. Chang, Jan P. Allebach, and Charles A. Bouman, IEEE Transactions and Image Processing, vol. 6, No. 9, Sep. 1997, pp. 1231-1245.
“A Novel Approach for Multidimensional Interpolation.” Xiaochuan Pan, IEEE Signal Processing Letters, vol. 6, No. 2, Feb. 1999, pp. 38-40.
“A Task-Specific Evaluation of Three-Dimensional Image Interpolation Techniqu
Chen Qin-Sheng
Weinhous Martin S.
Ahmed Samir
Bhatnagar Anand
Calfee Halter & Griswold LLP
Pejic Ned
The Cleveland Clinic Foundation
LandOfFree
Discrete image data interpolation using sub-unity shift does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Discrete image data interpolation using sub-unity shift, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete image data interpolation using sub-unity shift will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3281274