Image analysis – Image compression or coding
Reexamination Certificate
2000-09-01
2004-07-27
Chang, Jon (Department: 2621)
Image analysis
Image compression or coding
C382S248000
Reexamination Certificate
active
06768817
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data compression. More specifically, the invention relates to a new cubic-spline interpolation (CSI) for both 1-D and 2-D signals to sub-sample signal and image compression data.
BACKGROUND OF THE INVENTION
In most multimedia systems the amount of image data is so large that the use of image data compression is almost mandatory. Image data compression allows the image to be transmitted over the Internet in real time. Also it reduces the requirements for image storage. Presently both spatial and temporal data reduction techniques are available and continue to improve the performance of image data compression. The fundamental problem of image data compression is to increase the compression ratio and to reduce the computational complexity within an acceptable fidelity.
Interpolation is one of the more important functions that can be used in the process of estimating the intermediate values of a set of discrete sampling points. Interpolation is used extensively in image data compression to magnify or reduce images and to correct spatial distortions. For example, see R. G. Keys, “Cubic Convolution Interpolation for Digital Image Processing,” IEEE
Trans. on Acoustics, Speech, and Signal Processing
, vol. ASSP-29, no.6, pp. 1153-1160, December 1981, [1], the contents of which are hereby expressly incorporated by reference. In general, the process of decreasing the data rate is called decimation and the process of increasing data samples is called interpolation as described in H. S. Hou, and H. C. Andrews, “Cubic Splines for Image Interpolation and Digital Filtering,”
IEEE Trans. on Acoustics, Speech, and Signal Processing
, vol. ASSP-26, no.6, pp.508-517, December 1978, [2], the contents of which are hereby expressly incorporated by reference.
It is well known that several interpolation functions such as linear interpolation (see, W. K. Pratt,
Digital Image Processing
, second edition, John Wiley & Sons, Inc., New York, 1991, [3], the contents of which are hereby expressly incorporated by reference.) cubic-convolution interpolation (see [1], and [3]), cubic B-spline interpolation (described to C. de Boor,
A Practical Guide to Splines
. New York: Springer-Verlag, 1978, [4]; M. Unser, A. Aldroubi, and M. Eden, “B-Spline Signal Processing: Part II-Efficient Design and Applications,”
IEEE Trans. on Signal Processing
, vol.41, pp.834-848, February 1993, [5]; M. Unser, A. Aldroubi, and M. Eden, “Enlargement or Reduction of Digital Images with Minimum Loss of Information,”
IEEE Trans. on Image Processing
, vol.4, pp.247-258, March 1995, [6]; and [2]) can be used in the image data compression process.
The disadvantage of these interpolation schemes is that in general they are not designed to minimize the error between the original image and its reconstructed image. In 1981 Reed (I. S. Reed,
Notes on Image Data Compression Using Linear Spline Interpolation
, Department of Electrical Engineering, University of Southern California, Los Angeles, Calif., 90089-2565, U.S.A., November 1981 [7], the contents of which are hereby incorporated by reference) and in 1998 Reed and Yu (I. S. Reed and A. Yu,
Optimal Spline Interpolation for Image Compression
, U.S. Pat. No. 5,822,456, Oct. 13, 1998 [8], the contents of which are hereby incorporated by reference) developed a linear spline interpolation scheme for re-sampling the image data. This linear spline interpolation is based on the least-squares method with the linear interpolation function.
Using an extension of the ideas of Reed in [7,8], a modified linear spline interpolation algorithm, called the cubic-spline interpolation (CSI) algorithm, is developed in this invention for the sub-sampling of image data. (The linear spline interpolation explained in [8]and used by America On Line™ (AOL) will be called the “AOL algorithm” in this document from hereon.)
It follows from [1]that the cubic-convolution interpolation, which is different from the B-spline interpolation, can be performed much more efficiently than that of the cubic B-spline interpolation method. In this invention, the new CSI scheme combines the least-squares method with a cubic-spline function developed by Keys [1]for the decimation process. Also the cubic-spline reconstruction is used in the interpolation process. Therefore, the CSI constitutes a new scheme that is quite different from both cubic B-spline interpolation [2,-6]and cubic-convolution interpolation [1,3].
The concept of the CSI for both 1-D and 2-D signals is describes and demonstrated in the following sections. In addition, it is shown by computer simulation that the CSI scheme obtains a better subjective quality for the reconstructed image than linear interpolation, cubic-convolution interpolation, cubic B-spline interpolation and linear spline interpolation. An important advantage of this new CSI scheme is that it can be computed by a use of the FFT technique. The complexity of the calculation of the CSI scheme is substantially less than other conventional means.
W. B. Pennebaker and J. L. Mitchell,
JPEG Still Image Data Compression Standard
, Van Nostrand Reinhold, New York, 1993, [9], the contents of which are hereby incorporated by reference, describes the JPEG still image data compression standard. It is well known that the JPEG (see [9]) algorithm is the international compression standard for still-images. The disadvantage of the conventional JPEG algorithm is that it causes visually disturbing blocking effects when high quantization parameter is used to obtain a high compression ratio. One embodiment of this invention includes a simpler and modified JPEG encoder-decoder to improve the JPEG standard with a high compression ratio and still maintain a good quality reconstructed image.
Recently, the authors in T. K. Truong, L. J. Wang, I. S. Reed, W. S. Hsieh, and T. C. Cheng “Image data compression using cubic convolution spline interpolation,” accepted for publication in
IEEE Transactions on Image Processing
[10], the contents of which are hereby incorporated by reference, proposed the modified JPEG encoder-decoder for &tgr;=2 that utilizes the CSI scheme with a compression ratio of 4 to 1 as a pre-processing stage of the JPEG encoder and the cubic-spline reconstruction with a ratio of 1 to 4 as a post-processing stage of the inverse JPEG decoder to achieve a high compression ratio.
In such a modified JPEG encoder the CSI scheme is the pre-processing stage of the JPEG encoder. It can be implemented by the use of the FFT algorithm. In addition, the output of the modified JPEG encoder represents the compressed data to be transmitted. It can be pre-computed and stored. In such a modified JPEG decoder, the cubic-spline reconstruction constitutes the post-processing stage of the JPEG decoder. This post-processing stage is different from the conventional post-processing algorithms that were proposed to reduce the blocking effects of block-based coding in B. Ramamurthi and A. Gersho, “Nonlinear space variant post-processing of block coded images,”
IEEE Trans. on Acoustics, Speech, Signal Processing
, vol. ASSP-34, pp.1258-1267, 1986, [11], Y. Yang, N. Galatsanos, and A. Katsaggelos, “Projection-based spatially adaptive reconstruction of block-transform compressed images,”
IEEE Trans. on Image Processing
, vol.4, pp.896-908, July 1995 [12], the contents of which are hereby incorporated by reference.
The proposed post-processing stage is an interpolation process that uses the cubic-convolution interpolation. In [10], a computer simulation shows that the modified JPEG encoder-decoder for &tgr;=2 obtains a better subjective quality and an objective PSNR of the reconstructed image than the JPEG algorithm described in T. Lane, Independent JPEG Group's free JPEG software, 1998, [13], the contents of which are hereby
Cheng Tsen Chung
Hsieh Wen S.
Reed Irving S.
Truong Truieu K.
Wang Lung J.
Chang Jon
Christie Parker & Hale LLP
LaRose Colin
Truong, T.K./ Chen, T.C.
LandOfFree
Fast and efficient computation of cubic-spline interpolation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast and efficient computation of cubic-spline interpolation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and efficient computation of cubic-spline interpolation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253026