Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-03-17
2003-12-02
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S239000, C382S247000, C375S240190
Reexamination Certificate
active
06658159
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of digital image compression, and in particular to image compression based on embedded block coding with optimized truncation (EBCOT).
BACKGROUND OF THE INVENTION
Entropy or arithmetic coding is a form of data coding that can be used to compactly represent data, and may be used in one phase of an image compression algorithm. For example, a proposed image compression standard referred to as JPEG 2000 employs entropy coding as a final data coding process in an algorithm for still image compression. The JPEG 2000 algorithm is described, for example, in the Joint Photographic Experts Group JPEG 2000 Image Coding System document (ITU-T Rec. T.800 (1999 CDV1.0)/ISO/IEC CD15444-1: 1999(V1.0, Dec. 9, 1999)), the disclosure of which is incorporated herein by reference. The JPEG 2000 image compression system is used as a basis upon which to describe the operation of the present invention, and is thus introduced briefly hereinbelow.
Referring to
FIG. 1
, raw image data
10
to be compressed is first decomposed into components (step
12
). For example, an image represented in an RGB color format may be decomposed into three separate color components. The image components are then each divided into tiles (step
14
). The tiles are rectangular arrays applied in the same manner to each of the image components. The tile-components are further decomposed into different decomposition levels using a wavelet transform (step
16
). The wavelet transform decomposition levels contain a number of sub-bands populated with coefficients that describe horizontal and vertical spatial frequency characteristics of the original tile-component planes (step
18
). The coefficients provide local frequency information, and each wavelet decomposition level is related to the next decomposition level by spatial powers of two. In other words, each successive decomposition level of the sub-bands has approximately half of the horizontal and half of the vertical resolution as the previous level.
Even though there may be as many wavelet transform coefficients as original image samples, the information content following the wavelet transform tends to be concentrated into a relatively few coefficients. Using quantization, the information content can be further concentrated in the wavelet transform coefficients. Following quantization, the individual sub-bands of a tile component are divided into rectangular arrays of coefficients, referred to as code-blocks (step
20
). The individual bit-planes of the coefficients in a code block are then entropy coded in three coding passes (step
22
). Each of the coding passes collects contextual information about the bit-plane data and the arithmetic coder uses the contextual information and its internal state to generate coded data
24
that can then be formed into a compressed bit-stream (step
26
).
SUMMARY OF THE INVENTION
It is desirable in some circumstances to reduce the complexity required of the arithmetic coding process, which can have some beneficial effects including reduced computational requirements for both encoding and decoding the data and thus reduced encoding/decoding time. One method described herein involves bypassing the arithmetic coding procedure for certain lower significance bit-planes of each code-block. Then, the raw binary digits from these bit-planes can be interleaved into the arithmetically coded bit-stream. As a result, both the average number of arithmetically coded symbols and the maximum number of coding passes per code-block can be significantly reduced.
In accordance with the principles of the present invention, there is provided a method for compressing image data in which the image data is decomposed into code-blocks of coefficients using a transform. Each code-block comprising a plurality of bit-planes from a most significant bit-plane to a least significant bit-plane. An encoded bit-stream is formed by coding bit-planes of coefficient data in the code-blocks according to an arithmetic coding scheme in order to form an encoded bit-stream, wherein coefficient data from at least one bit-plane is included in the encoded bit-stream without arithmetic coding.
The arithmetic coding scheme may operate in a plurality of coding passes, wherein at least one of the arithmetic coding passes for the coefficient data from the at least one bit-plane is not performed during the image data compression. For example, the coefficient data from bit-planes
p<p
0
−K
may be written directly into the encoded bit-stream without arithmetic coding, wherein p
0
denotes the most significant bit-plane of the code block in which any sample therein becomes contextually significant during arithmetic coding and K is an integer parameter. In one preferred implementation of the invention K set equal to 3.
The present invention also provides an image data compression system having a decomposition processor which decomposes the image data into code-blocks of coefficients using a transform, each code-block comprising a plurality of bit-planes from a most significant bit-plane to a least significant bit-plane. An arithmetic coder is coupled to the decomposition processor, which forms an encoded bit-stream by coding bit-planes of coefficient data in the code-blocks according to an arithmetic coding scheme. The arithmetic coder is constructed such that coefficient data from at least one bit-plane is not subjected to said arithmetic coding scheme so as to be included in the encoded bit-stream without arithmetic coding.
The present invention further provides, in particular, a compressed image data bit-stream formed from transform coefficients of image data, wherein the bit-stream data structure includes arithmetically coded data interleaved with raw transform coefficient data.
REFERENCES:
patent: 5815097 (1998-09-01), Schwartz et al.
patent: 2002/0080408 (2002-06-01), Budge et al.
Chen Wenpeng
Hewlett--Packard Development Company, L.P.
LandOfFree
Block entropy coding in embedded block coding with optimized... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block entropy coding in embedded block coding with optimized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block entropy coding in embedded block coding with optimized... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159011