Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2001-06-22
2003-06-03
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S233000, C382S248000, C382S260000, C382S277000
Reexamination Certificate
active
06574372
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to an image compression/decompression g technique, and more particularly to a wavelet transform coding/decoding technique for image blocks.
2. Description of the Related Art
A typical high quality digitized color image may use 24 bits per pixel (bpp)—8 bits for each of the three basic color components: red (R), green (G) and blue (B) in RGB color space or for each of the three basic luminance-chrominance components: luminance (Y), chrominance (C
b
) and chrominance (C
r
) in YC
b
C
r
color space. In the uncompressed state (i.e., in the spatial or pixel domain), such images are simply too costly and time consuming to transmit and store. The high transmission time and memory requirements for high quality color images is apparent when compared to gray-scale images that may use 8 bpp or bi-level images that use only 1 bpp. Thus, applications and devices which store or transmit high quality digitized color images typically do so in a compressed format, using one of the currently available compression techniques.
Various image compression techniques have been proposed to reduce the number of bits used to represent a digitized color image while, at the same time, providing quality image representation. These techniques generally seek to strike a balance between transmission time and memory requirements on the one hand and image quality on the other. Some of these techniques are “lossless,” meaning that they preserve all information of the original image so that it is reproduced exactly when the data is decompressed. Other techniques, commonly referred to as “lossy,” discard information which is visually insignificant. By only approximating the original image (rather than reproducing it exactly), lossy techniques are generally able to produce higher compression ratios than lossless techniques. In selecting the appropriate compression technique among those currently available, the user must consider the particular image to be compressed, the desired compression ratio and image quality as well as transmission time and memory requirements, with the understanding that higher compression ratios lead to lower transmission times and memory requirements but also produce lower quality images.
One of the problems with the currently available image compression techniques is that most tend to be designed for one type of data and generally do not work well on hybrid color images (that is, images containing text, graphics, as well as synthetic and natural images). Since different types of data have different frequency characteristics, it is difficult to achieve a high compression ratio by applying a single coding mode to a hybrid image without sacrificing image quality. In order to effectively compress hybrid images an adaptive coding technique is needed.
One such adaptive coding technique is proposed in U.S. Pat. No. 5,696,842 which provides a coding process that separates a document image into blocks and classifies them as “picture” blocks or “black-and-white” blocks using a block classification algorithm that employs a complex edge-detection mechanism. The blocks are then coded according to their classification. Arithmetic coding is used for “black-and-white” blocks and ADCT for “picture” blocks. While this coding system offers certain advantages over non-adaptive coding systems, it has certain disadvantages as well. For example, the block classification scheme is relatively complex and is not tied to the coding process itself, which makes for a relatively high overhead requirement. In addition, the adaptive coding technique of this patent does not offer guaranteed compression rate control.
3. Objects of the Invention
Therefore, it is an object of the present invention to overcome the aforementioned problems.
It is another object of the invention to provide a wavelet transform coding technique for 32×2 image blocks that is targeted for high-quality compression, has low computation complexity and offers exact rate control.
SUMMARY OF THE INVENTION
In one aspect of the invention, a digitized image is compressed and/or decompressed using a wavelet technique The underlying method of this technique comprises segmenting the image into a plurality of 32×2 blocks of pixel data, transforming each of these blocks of data into a corresponding block of subband coefficients, quantizing the subband coefficients; and coding the quantized subband coefficients. The transforming step comprises filtering each block of data using a 2-6 wavelet filter and a Haar filter for subband decomposition. The Haar filter is applied to each of the columns of data in each block and the 2-6 wavelet filter is applied to each of the rows of data in each block. The 2-6 wavelet filter is then repeatedly applied to the top row of data in each block to obtain a low pass coefficient for each block. The quantizing step comprises organizing the filtered subband coefficients together into 11 different groups using a tree structure in which each level of the tree corresponds to a particular level of resolution. The coding step comprises coding each of the different groups of subband coefficients using the same number of bits per coefficient, that number being determined so that the total number of bits used for a block is no more than a given budget.
The wavelet method may be carried out using an encoder/decoder system such as a simple block codec with wavelets (SBCW). In such a system an encoder comprises means for transforming each of a plurality of blocks of pixel data into a corresponding block of subband coefficients, a quantizer for quantizing the subband coefficients, and an entropy-encoder for coding the quantized subband coefficients to generate a bit stream of coded data representing the compressed image. A decoder, which includes an entropy decoder, a dequantizer and inverse transforming means, reverses the steps of the encoder by reconstructing blocks of pixel data from the compressed bit stream. The encoder and decoder may be configured separately to respectively compress or decompress a digitized image in accordance with this aspect of the invention.
The SBCW method may also be carried out using an article of manufacture which may be a computer, a computer peripheral device, a computer component such as a memory or processor, or a storage device such as a diskette or CD ROM. The article of manufacture has software or hardware embodied therein for compressing/decompressing the digitized image in accordance with this aspect of the invention.
REFERENCES:
patent: 5148498 (1992-09-01), Resnikoff et al.
patent: 5359676 (1994-10-01), Fan
patent: 5379122 (1995-01-01), Eschbach
patent: 5674012 (1997-10-01), Sasaki
patent: 5696842 (1997-12-01), Shirasawa et al.
patent: 5892847 (1999-04-01), Johnson
patent: 6005981 (1999-12-01), Ng et al.
patent: 6163626 (2000-12-01), Andrew
DeVore, et al. “Image Compression Through Wavelet Transform Coding”,IEEE Transactions On Information Theory, vol. 38, No. 2, pp 719-746 Mar. 1992.
Said, et al. “A New, Fast, And Efficient Image Codec Based On Set Partitioning In Hierarchical Trees”,IEEE Transactions On Circuits And Systems For Video Technology, vol. 6, No. 3, pp 243-249, Jun. 1996.
Shapiro, J.M. “Embedded Image Coding Using Zerotress Of Wavelet Coefficients”,IEEE Transactions On Signal Processing, vol. 41, No. 12, pp 3445-3462, Dec. 1993.
Villasenor, et al. “Wavelet Filter Evaluation For Image Compression”,IEEE Transactions On Image Processing, 2: 1053-1060, Aug. 1995.
Gabrik Michael T.
Seiko Epson Corporation
Tran Phuoc
LandOfFree
Wavelet transform coding technique does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wavelet transform coding technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wavelet transform coding technique will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3161841