Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-09-28
2002-05-14
Britton, Howard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240120, C375S240190
Reexamination Certificate
active
06389074
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of computer data compression with particular application to digital image compression. The present invention further provides for a spatially adaptive quantisation using quadtrees of discrete wavelet transform image and video data.
BACKGROUND OF INVENTION
The field of digital data compression and in particular digital image compression and digital video 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.
Further, digital compression techniques applied to video streams are also well known. For example, compression techniques relying on the video frame difference signals are also well known.
For objective and subjective reasons, better compression of digital signals can be obtained by varying the amount of quantisation of each region as compared to using a fixed amount of quantisation across a whole signal. Of course, usually some coding overhead will be required to indicate how the quantisation has been varied across the signal.
In the past, adaptive quantisation has been employed, for example, in the video compression standard MPEG and its various implementations.
It would be desirable to provide for a more adaptive form of quantisation of a signal rather than the fixed techniques presently known.
ASPECTS OF 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 compressing digital data including the steps of (a) transforming the data utilising a discrete wavelet transform to produce corresponding transformed data; (b) quantising the transformed data utilising a variable quantisation determined by a corresponding quadtree structure wherein each of the quadtree leaf nodes has an associated quantisation factor utilised in the quantising of the transformed data.
In accordance with a second aspect of the present invention there is provided a method of decompressing digital data, which digital data includes encoded quantized coefficients and associated quantization and quadtree information, the method including the steps of: (a) decoding said quantization and quadtree information; (b) decoding said encoded quantized coefficents; (c) inverse quantizing the decoded quantized coefficients in accordance with the quantization and quadtree information, wherein each quadtree leaf node has an associated quantization factor utilised in said inverse quantising of said decoded quantized coefficients; and (d) inverse transforming the inverse quantized coefficients.
In accordance with a third aspect of the present invention there is provided an apparatus for compressing digital data including the apparatus including: transformation means for transforming said data utilising a discrete wavelet transform to produce corresponding transformed data; quantization means for quantizing said transformed data utilising a variable quantisation determined by a corresponding quadtree structure wherein each of said quadtree leaf nodes has an associated quantisation factor utilised in said quantising of said transformed data.
In accordance with a fourth aspect of the present invention there is provided an apparatus for decompressing digital data, which digital data includes encoded quantized coefficients and associated quantization and quadtree information, the apparatus including; means for decoding said quantization and quadtree information; means for decoding said encoded quantized coefficents; means for inverse quantizing the decoded quantized coefficients in accordance with the quantization and quadtree information, wherein each quadtree leaf node has an associated quantization factor utilised in said inverse quantising of said decoded quantized coefficients; and means for inverse transforming the inverse quantized coefficients.
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 compressing digital data, the computer program product including: transformation means for transforming said data utilising a discrete wavelet transform to produce corresponding transformed data; quantization means for quantizing said transformed data utilising a variable quantisation determined by a corresponding quadtree structure wherein each of said quadtree leaf nodes has an associated quantisation factor utilised in said quantising of said transformed 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 decompressing digital data, which digital data includes encoded quantized coefficients and associated quantization and quadtree information, the computer program product including: means for decoding said quantization and quadtree information; means for decoding said encoded quantized coefficents; means for inverse quantizing the decoded quantized coefficients in accordance with the quantization and quadtree information, wherein each quadtree leaf node has an associated quantization factor utilised in said inverse quantising of said decoded quantized coefficients; and means for inverse transforming the inverse quantized coefficients.
REFERENCES:
patent: 5446806 (1995-08-01), Ran et al.
patent: 5812788 (1998-09-01), Agarwal
patent: 5835147 (1998-11-01), Florentin et al.
patent: 5841473 (1998-11-01), Chui et al.
patent: 5848195 (1998-12-01), Romriell
patent: 5917943 (1999-06-01), Washizawa
patent: 5937097 (1999-08-01), Lennon
patent: 6084908 (2000-07-01), Chiang et al.
patent: 6160846 (2000-12-01), Chiang et al.
patent: 6195456 (2001-02-01), Balasubramanian et al.
Bruce et al., “Wavelet Analysis”, IEEE Spectrum, Oct. 1996, pp. 26-35.
Hanan Samet, “The Quadtree and Related Hierarchical Data Structures”, ACM Computing Surveys, vol. 16, No. 2, Jun. 1984, pp. 187-260.
Eric J. Stollnitz et al., “Wavelets for Computer Graphics: A Primer, Part 1”, IEEE Computer Graphics and Applications, May 1995, pp. 76-84.
Eric J. Stollnitz et al., “Wavelets for Computer Graphics: A Primer, Part 2”, IEEE Computer Graphics and Applications, Jul. 1995, pp. 75-85.
Britton Howard
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Method and apparatus for digital data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for digital data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for digital data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2832801