Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1999-08-17
2003-04-29
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Transform coding
C382S232000, C382S250000
Reexamination Certificate
active
06556719
ABSTRACT:
TECHNICAL FIELD
The present invention relates to image compression and particularly, although not exclusively, to a progressive block-based embedded DCT coder, and to a method of encoding.
BACKGROUND OF THE INVENTION
The JPEG baseline method for still image coding uses the Discrete Cosine Transform (DCT) in a fixed 8×8 pixel partition. Through a linear quantization table and zig-zag scanning of DCT coefficients, the redundancy and band width characteristics of the DCT are exploited over a range of compressions. Recently, however, it has become clear that the JPEG coder is not particularly efficient at higher compression ratios, and other methods such as wavelets have produced better results while having the advantage of being fully embedded. Some researchers have also attempted to combine DCT with zerotree quantization, usually associated with wavelet transforms: see
Xiong, Guleryuz and Orchard, ‘A DCT
-
Based Image Coder’, IEEE Sig. Proc. Lett.,
Vol 3, No 11, November 1996, p289.
It is an object of the present invention to advance the field of image compression generally, and in particular to provide an improved method of image compression which is capable of use with well understood transforms such as the DCT.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention this is provided a method of image compression comprising:
(a) dividing an image to be compressed into a plurality of image blocks;
(b) carrying out a two-dimensional block transform on each block to produce a corresponding plurality of coefficient blocks;
(c) bitwise digitizing the coefficients within each coefficient block to define a plurality of bit planes for each coefficient block;
(d) defining a group of one or more consecutive bit planes starting with the most significant bit plane;
(e) selecting those coefficients which first become significant within the group;
(f) flagging the said selected coefficients;
(g) transmitting information representative of the positions of the said selected coefficients; and transmitting the bits within the group of the said coefficients; and
(h) repeating (d) to (g) one or more times, with each new group starting with the most significant bit plane not previously dealt with; and, at each repeated pass, also transmitting the bits within the current group of those coefficients which were previously flagged on an earlier pass.
Such a method could also be applied using the one-dimensional DCT to audio recording.
According to a second aspect of the invention there is provided a coder for encoding images, comprising:
(a) means for dividing an image to be compressed into a plurality of image blocks;
(b) means for carrying out a two-dimensional block transform on each block to produce a corresponding plurality of coefficient blocks;
(c) means for bitwise digitizing the coefficients within each coefficient block to define a plurality of bit planes for each coefficient block;
(d) means for defining a group of one or more consecutive bit planes starting with the most significant bit plane;
(e) means for selecting those coefficients which first become significant within the group;
(f) means for flagging the said selected coefficients;
(g) means for transmitting information representative of the positions of the said selected coefficients, and for transmitting the bits within the group of the said coefficients; and
(h) means for repeating (d) to (g) one or more times, with each new group starting with the most significant bit plane not previously dealt with; and means for transmitting, at each repeated pass, the bits within the current group of those coefficients which were previously flagged on an earlier pass.
Preferably, the encoder provides for significance switching of DCT coefficients in block-based embedded DCT image compression. The encoder provides output on one or more data streams that may be terminated within a few bits of any point.
The invention also extends to a video coder/decoder including a coder as claimed in claim
17
and an associated decoder, the decoder being arranged to maintain a running record, as transmission between the coder and the decoder proceeds, of the coefficients which are currently significant.
The preferred two-dimensional block transform of the present invention is the Discrete Cosine Transform, although other transforms such as the Fast Fourier Transform (FFT) or the Lapped Orthogonal Transform could be used.
It will be appreciated that in the method of the present invention the order of transmission is not significant. It is therefore to be understood, except where logic requires, that the various parts of the method are not necessarily carried out sequentially in the order specified in section (d) of claim
1
. For example, the bits from the newly selected coefficients could be transmitted either before or after the bits of those coefficients which were previously flagged on an earlier path. Similarly, the bits of those coefficients which were previously flagged on an earlier path could be transmitted either before or after the new coefficients are selected for flagging.
The bit planes are swept consecutively from the most significant bit plane to the least significant bit plane. This may either be repeated separately for each image block, or alternatively all blocks may be dealt with at the first bit plane, then all blocks dealt with at the second bit plane, and so on.
The philosophy of significance switching, as used in the present invention, is that the overheads introduced will be compensated for by the savings in not transmitting bits for small coefficients until they are switched on. Good performance might naturally be expected at high compression ratios, but what is surprising is the excellent performance both for lossless compression and for compression at low ratios. The coder of the present invention is preferably embedded, in other words the bit stream can be stopped within a few bits of any point while still guaranteeing the least possible distortion overall. When used with an appropriate decoder, either coder or decoder can terminate the bit stream as needed, dependent upon the available bandwidth or the available bit budget.
The coder of the present invention has been found to out-perform the base-line JPEG method in peak signal to noise ratio (PSNR) at any compression ratio, and is similar to state-of-the-art wavelet coders. The results show that block transform (for example DCT) coding is competitive across the whole range of compression ratios, including lossless, so that a significance-switched block coder would be capable of meeting the requirements of future image compression standards in an evolutionary manner.
REFERENCES:
patent: 5563960 (1996-10-01), Shapiro
patent: 5768437 (1998-06-01), Monro et al.
patent: 5818877 (1998-10-01), Tsai et al.
patent: 0 327 931 (1989-08-01), None
patent: 0 551 672 (1993-07-01), None
“A DCT-Based Image Coder,” Xiong, Guleryuz and Orchard, IEEE Sig. Proc. Lett., vol. 3, No. 11, Nov. 1996, p. 289.
“The JPEG Still Picture compression Standard,” Wallace, G.K., Comm. ACM, vol. 34, No. 4, pp. 30-44, 1991.
“Image Compression Using the Spatial-Orientation Tree,” Said, A. and Pearlman, W.A., IEEE International Symposium on Circuits and Systems, 1993, (694), pp. 279-282.
“The JPEG Still Picture Compression Standard,” Wallace, G.K.,Communications of the Association For Computing Machinery, vol. 34, No. 4, Apr. 1, 1991, pp. 30-44 XP000228786.
“JPEG: Still Image Data Compression Standard,” Pennebaker, W.B., Mitchell, J.L., 1993, Van Nostrand Reinhold, New York, NY USA XP00206756.
“Progressive Coding and Transmission of Digital Diagnostic Pictures,” Elnahas, S.E. et al.,IEEE Transactions on Medical Imaging, Jun. 1986, USA, vol. MI-5, No. 2 pp. 73-83, XP002067594.
“Bit-Plane Encoding: A Technique For Source Encoding,” Schwartz, J.W., Barker, R.C.,IEEE Transactions on Aerospace and Electornic Systems, vol. 2, No. 4, 1966, pp. 385-392, XP002067595.
“Prioritized DCT For Compression and Progressive Transmission of Images,” Yunming H.,IEEE Transactions on Image Processing, vol. 1
Do Anh Hong
University of Bath
Wallenstein & Wagner Ltd.
LandOfFree
Progressive block-based coding for image 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 Progressive block-based coding for image compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Progressive block-based coding for image compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3059936