Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-09-28
2001-06-12
Au, Amelia M. (Department: 2723)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S249000
Reexamination Certificate
active
06246798
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of digital compression with particular application to digital image compression. More particularly, the present invention discloses a modified discrete wavelet transform for odd length data appropriate for image and video compression applications.
BACKGROUND OF THE INVENTION
The field of digital data compression and in particular digital image compression has attracted great interest for some time.
In the field of digital image compression, many different techniques have been utilised. In particular, one popular technique is the JPEG standard which utilises the Discrete Cosine Transform to transform standard size blocks of an image into corresponding cosine components. In this respect, the higher frequency cosine components are heavily quantised so as to assist in obtaining substantial compression factors. The heavy quantisation is an example of a “lossy” technique of image compression. The JPEG standard also provides for the subsequent “lossless” compression of the transformed coefficients.
Recently, the field of wavelet transforms has gained great attention as an alternative form of data compression. The wavelet transform has been found to be highly suitable in representing data having discontinuities such as sharp edges. Such discontinuities are often present in image data or the like.
Although the preferred embodiments of the present invention will be described with reference to the compression of image data, it will be readily evident that the preferred embodiment is not limited thereto. For examples of the many different applications of Wavelet analysis to signals, reference is made to a survey article entitled “Wavelet Analysis” by Bruce et. al. appearing in IEEE Spectrum, October 1996 page 26-35. For a discussion of the different applications of wavelets in computer graphics, reference is made to “Wavelets for Computer Graphics”, I. Stollinitz et. al. published 1996 by Morgan Kaufmann Publishers, Inc.
Unfortunately, the standard techniques are normally ideally utilised on wavelet data having dimensions that are normally a binary power of 2. As such, this data represents an idealised case in that not all image data will be conveniently sized to be a power of 2 especially where multilevel Wavelet decompositions are carried out. Given that high degrees of compression are the objective, it is unclear how one should deal with image data that does not fit into a certain number of limited sizes.
SUMMARY OF THE INVENTION
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
In accordance with a first aspect of the present invention there is provided a method of producing a transform decomposition of data having an odd length, the method comprising the steps of (i) dividing the data into a portion having an even length and an odd length of one element; (ii) performing a discrete wavelet transform on the even length data to produce low frequency subband data and high frequency subband data; (iii) adding the difference of the one element and an adjacent element to the high frequency subband data.
In accordance with a second aspect of the present invention there is provided a method of producing an inverse transform composition of data, where said data includes low frequency subband data values, high frequency subband data values and a difference data value, the method including the steps of: (i) performing an inverse discrete wavelet transform on the low frequency subband data values and the high frequency subband data values to produce original data values; (ii) adding the difference data value to one of said original data values to produce a further original data value; and (iii) appending to the original data values said further original data value.
In accordance with a third aspect of the present invention there is provided an apparatus for producing a transform decomposition of data having an odd length, said apparatus including: means for dividing the data into a portion having an even length and an odd length of one element; means for performing a discrete wavelet transform on said even length data to produce low frequency subband data and high frequency subband data; means for adding the difference of said one element and an adjacent element to the high frequency subband data.
In accordance with a fourth aspect of the present invention there is provided an apparatus for producing an inverse transform composition of data, where said data includes low frequency subband data values, high frequency subband data values and a difference data value, the apparatus including: means for performing an inverse discrete wavelet transform on the low frequency subband data values and the high frequency subband data values to produce original data values; means for adding the difference data value to one of said original data values to produce a further original data value; and means for appending to the original data values said further original data value.
In accordance with a fifth aspect of the present invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for producing a transform decomposition of data having an odd length, the computer program product including: means for dividing the data into a portion having an even length and an odd length of one element; means for performing a discrete wavelet transform on said even length data to produce low frequency subband data and high frequency subband data; means for adding the difference of said one element and an adjacent element to the high frequency subband data.
In accordance with a sixth aspect of the present invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for producing an inverse transform composition of data, where said data includes low frequency subband data values, high frequency subband data values and a difference data value, the computer program product including: means for performing an inverse discrete wavelet transform on the low frequency subband data values and the high frequency subband data values to produce original data values; means for adding the difference data value to one of said original data values to produce a further original data value; and means for appending to the original data values said further original data value.
REFERENCES:
patent: 5966465 (1999-10-01), Keith et al.
patent: 5999656 (1999-12-01), Zandi et al.
Hartenstein “Parametrization of discrete of discrete finite biorthogonal wavelets with linear phase” IEEE International Conf. on Acoustics, Speech, adn Signal Processing, 1997 vol. 3, pp2441-2444, Apr. 1997.*
Bi et al. “Fast odd-factor algorithm for discrete W transform” Electronic Letters vol. 34, pp 431-433, Mar. 1998.*
Bradley “A wavelet visible difference predictor” IEEE Trasaction on Image Processing vol. 8, pp 717-730, May 1999.*
Chan etal. “Fast algorithms for computing the discrete W transforms” IEEE Region 10 Conference on Computer and Communication Systems, 1990 vol. 1, pp. 183-185, Sep. 1990.*
Bruce, Andrew, et al., “Wavelet Analysis”, IEEE Spectrum, Oct. 1996, pp. 26-35.
Stollnitz, Eric J., et al., “Wavelets for Computer Graphics: A Primer, Part 1”, IEEE Computer Graphics and Applications, May 1995, pp. 76-84.
Stollnitz, Eric J., et al., “Wavelets for Computer Graphics: A Primer, Part 2”, IEEE Computer Graphics and Applications, Jul. 1995, pp. 75-85.
Andrew James Philip
Bradley Andrew Peter
Au Amelia M.
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Wu Jingge
LandOfFree
Modified discrete wavelet transform for odd length data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modified discrete wavelet transform for odd length data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modified discrete wavelet transform for odd length data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441539