Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
2000-11-02
2004-09-14
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Predictive coding
Reexamination Certificate
active
06792150
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image processing system, and more particularly, to a method, apparatus and computer program product for compressing and decompressing image data.
2. Discussion of the Background
Japanese Patent Laid-Open Publications Nos. 10-084484, 11-168633, and 11-266162 describe compression and decompression of image data by a combination of two-dimensional reversible wavelet transform processing, context model processing, and binary entropy encoding/decoding processing. Such compression and decompression devices and those according to the present invention generally include five processing blocks, as shown in FIG.
1
. These processing blocks include, for example, a two-dimensional reversible wavelet transform section
10
, a context model section
20
, a binary entropy encoder/decoder
30
, and an integration order generation section
50
perform compression and decompression of image data. For example, a FSM (Finite State Machine) coder based on a finite state machine is used as the binary entropy encoder/decoder
30
.
The operation of such compression and decompression devices will now be explained. It is assumed that each device divides one component image (e.g., one of a Red, Green and Blue image) into tiles, and performs tile-by-tile image processing. First, the operation of the device in encoding (i.e., compressing) image data will be described. Based on an order transformation, performed by the two-dimensional reversible wavelet transform section
10
, image data of one tile is spatially divided into frequency bands, for example, as shown in
FIGS. 2A-2D
, and coefficient data of each frequency band is provided to the context model section
20
. Because a low frequency band is recursively spatially divided, coefficient data of each frequency band shown in
FIG. 2D
is obtained when image data is transformed into three levels.
In the integration order generation section
50
, a bit to be encoded (hereinafter referred to as a target bit) is determined based on order of alignment information (i.e., information which indicates the order of encoding) designated by a user. In the context model section
20
, context data is created based on the state of the bits (i.e., each bit of a context template shown in
FIG. 3
) around the target bit, and the binary entropy encoder/decoder
30
receives the generated context data.
In the binary entropy encoder/decoder
30
, the target bit is encoded using probability estimation based on the context data and the target bit so as to generate a code word. Then, a code stream of one tile is output after tag information, including a compression condition, has been added to a header of the code word via a tag processing section
40
.
In a wavelet transform, coefficient data, corresponding only to the coefficient data of a high frequency band (DS, SD, DD) shown via shading in
FIG. 2B
,
2
C and
2
D, is encoded. Then, the coefficient data of a low frequency band (SS) is output without encoding into a code stream. In a three-level wavelet transformation, the coefficient data of a high frequency band shown via shading in
FIG. 2D
is encoded, and the coefficient data of a low frequency band (SS
3
) is not encoded.
Decoding is performed via a method similar to the above-described encoding method. In addition, the encoding and decoding of the coefficient data is performed from the most significant bit data to the least significant bit data, at every bit plane.
In a decompression (i.e., decoding) process, image data of one tile is created from a code stream of one tile and is the reverse of a compression (i.e., encoding) process. In this case, a target bit position is determined in an integration order generation section
50
, based on tag information at the header of a codestream. Then, context data is created in the context model section
20
based on a state of the bits (i.e., which have already been encoded) around the target bit.
In the binary entropy encoder/decoder
30
, decoding is performed using probability estimation based on the context data and the codestream, and the decoded bit is output. The decoded bit is written into a target bit position of a buffer in the context model section
20
. Thus, coefficient data of each frequency band is restored. The coefficient data is reverse transformed by the two-dimensional reversible wavelet transform section
10
, and image data of one tile is reconstructed.
The tag processing section
40
adds tag information to a compressed codestream and interprets the tag information added to the codestream. In a compression (i.e., encoding) process, the tag processing section
40
combines a plurality of components formed in one tile in a predetermined order, so as to generate one codestream. The tag processing section
40
then adds tag information to the header of the codestream. In a decompression (i.e., decoding) process, the tag processing section
40
interprets tag information and resolves one codestream into a plurality of components in one tile.
In such devices as described above, wavelet transformed coefficient data is encoded with a bit-significance representation, as shown in FIG.
4
. Generally, in “2's complement” and “sign+ magnitude” representations, the sign is represented by the uppermost bit. In contrast, in a bit-significance representation, an absolute value of a coefficient value is examined from an upper bit to a lower bit to determine the first logic “1” bit (e.g., referred to as a “1” head bit). The sign bit is encoded right after the encoding of the “1” head bit. Bits having logic values of “0” and located at higher bit positions than the “1” header bit are referred to as “0” header bits. Bits having logic values of “0” or “1” and located at lower bit positions than the “1” head bit are referred to as tail bits.
Referring to
FIG. 5
, a bit from each high frequency band (i.e., one of DS, SD, and DD) is examined with respect to a coefficient word of a pixel (i.e., in a depth direction) from MSB (the most significant bit) to LSB (the least significant bit). When the “1” head bit (i.e., the bit circled in
FIG. 5
) is a target bit, a sign bit S of the coefficient word is encoded (or decoded), immediately after the “1” head bit is encoded (or decoded). Then, a bit in the next target position is encoded (or decoded). When a target bit is a bit (i.e., including tail bits) other than the “1” head bit, the next target bit is encoded (or decoded) instead of the sign bit S, after the target bit has been encoded (or decoded). Namely, a sign bit is encoded (or decode) together with the “1” head bit.
As described above, encoding (or decoding) of each high frequency band is performed in order of significant bits at every bit plane. However, a target bit moves in the order as shown in
FIG. 6
in each bit plane. Accordingly, the target bit moves in a zigzag order of T
0
, T
1
, T
2
, and T
3
in a left most 2×2 pixel region. Then, the target bit moves in a zigzag order of T
4
, T
5
, T
6
, and T
7
in the next 2×2 pixel region. This process is repeated until all the bits are encoded (or decoded).
Such devices as discussed above, generally, are implemented via specific hardware, when processing speed higher than that of an implementation using software and a personal computer or workstation is required. In addition, dataflow in the context model section
20
and between the context model section
20
and the binary entropy encoder/decoder
30
is arranged in series, as shown in
FIGS. 7 and 8
. Further, the context model section
20
and the binary entropy encoder/decoder
30
are serially operated as shown in FIG.
9
A.
In such devices, processing time required for compression and decompression is determined by multiplying a basic cycle time by the number of processing cycles. However, the shortening of the basic cycle time is limited because the processing is performed in series, as described above. In addition, in contrast to the encoding operation, because a decoded bit is used as a context t
Couso Jose L.
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
Ricoh & Company, Ltd.
LandOfFree
Method, apparatus and computer program product for image... 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, apparatus and computer program product for image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and computer program product for image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211026