Image analysis – Image compression or coding
Reexamination Certificate
1998-09-29
2001-07-17
Couso, Jose L. (Department: 2724)
Image analysis
Image compression or coding
C382S248000
Reexamination Certificate
active
06263110
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to the field of digital data compression with particular application to digital image compression and digital video compression. In particular, the present invention relates to the effective quantisation of transform image coefficients for image compression methods that employ bit plane encoding and includes the efficient rounding prior to bit plane encoding of transformed image and video signals.
2. Description of the Related Art
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 (DCT) 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.
Many efficient methods of image compression use a bit plane encoding of the transform image data. For example, the following coding methods effectively employ bit plane coding of transform (usually discrete wavelet transform) image data: the embedded zero-tree wavelet (EZW) family of methods U.S. Pat. Nos. 5,412,741, 5,315,670 and 5,321,776, and binary context entropy coding of transform image bit planes. All of these methods offer some of the most competitive performance currently available in terms of the rate/distortion/complexity tradeoff.
With bit plane coding techniques, usually not all the bit planes are coded. Only the most significant bit plane down to a predetermined minimum bit plane is coded. For example, consider the coding of the coefficient 135, which has an 8-bit binary representation 10000111, with a bit plane coding of this coefficient down to and including bit plane
3
(Numbering beginning from bit plane
0
, the least significant bit). The coefficient is coded with the bits 10000 being the bits in bit plane
7
,
6
,
5
,
4
and
3
respectively. The decoder, receiving this information, then can replicate these bits in bit planes
7
,
6
,
5
,
4
and
3
but does not know the bits in the lower bit planes. Instead of assuming the bits are all zero in the lower bit planes, in which case
135
is decoded as 10000000 binary (128 decimal) the decoder can assume a 1 in bit plane
2
and zeros in the other lower bit planes, in which case
135
is decoded as 10000100 binary (132 decimal). This is a generalised form of rounding, and generally offers better results because it reduces the (average) difference between the decoded coefficient and the original.
As an alternative this generalised rounding an be performed at the encoder. A 1 in bit plane
2
can be added to 135 (10000111+00000100=10001011 or 139 decimal) prior to coding. With ensuing coding down to bit plane
3
, the coefficient is coded as 10001 and decoded as 10001000 or 136 decimal. In fact, this is simply a form of uniform quantisation.
For efficient bit plane coding techniques, such as SWEET (see below) and the EZW family, rounding at the encoder (or uniform quantisation) is not efficient, and degrades the compression performance. The reasons behind this are discussed hereinafter.
SUMMARY OF THE INVENTION
It is an object of the invention to ameliorate one or more disadvantages of the prior art.
According to a first aspect of the invention, there is provided a method of encoding data including: transforming the data into a series of components having different frequency characteristics, said components each including a series of coefficients; encoding said coefficients in a compact form, said coefficients including a binary string and said encoding including providing a first efficient encoding technique to encode the number of leading zeros in said binary string, and rounding said coefficients such that a rounded coefficient does not alter its number of leading zeros.
According to a second aspect of the invention, there is provided a method of encoding data including: transforming the data into a series of components having different frequency characteristics, said components each including a series of coefficients; dividing said components into predetermined blocks; encoding for each of said blocks, said coefficients in a compact form, said coefficients including a binary string and said encoding including providing a first efficient encoding technique to encode the number of leading zeros of the largest magnitude coefficient in each block, and said rounding including ensuring that a rounded coefficient does not alter the number of leading zeros within a largest magnitude rounded coefficient in said block.
According to a third aspect of the invention, there is provided an apparatus for encoding data including: transformation means for transforming the data into a series of components having different frequency characteristics, said components each including a series of coefficients; encoder means for encoding said coefficients in a compact form, said coefficients including a binary string and said encoding including providing a first efficient encoding technique to encode the number of leading zeros in said binary string, and rounding said coefficients such that a rounded coefficient does not alter its number of leading zeros.
According to a fourth aspect of the invention, there is provided an apparatus for encoding data including: transformation means for transforming the data into a series of components having different frequency characteristics, said components each including a series of coefficients; division means for dividing said components into predetermined blocks; encoder means for encoding, for each of said blocks, said coefficients in a compact form, said coefficients including a binary string and said encoding including providing a first efficient encoding technique to encode the number of leading zeros of the largest magnitude coefficient in each block, and said rounding including ensuring that a rounded coefficient does not alter the number of leading zeros within a largest magnitude rounded coefficient in said block.
According to a fifth aspect of the invention, there is provided a computer program product including a computer readable medium having recorded thereon a computer program for encoding data, the computer program product including: transformation means for transforming the data into a series of components having different frequency characteristics, said components each including a series of coefficients; encoder means for encoding said coefficients in a compact form, said coefficients including a binary string and said encoding including providing a first efficient encoding technique to encode the number of leading zeros in said binary string, and rounding said coefficients such that a rounded coefficient does not
Andrew James Philip
Bradley Andrew Peter
Canon Kabushiki Kaisha
Couso Jose L.
Do Anh Hong
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Method for 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 for data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2563067