Method, apparatus and computer program product for image data compression and decompression capable of high-speed processing

A compression and decompression apparatus, method and computer program product, wherein compression and decompression of image data is performed via a combination of two-dimensional reversible wavelet transform processing, context model processing, and binary entropy encode/decode processing. Faster processing, as compared to conventional devices and methods, is achieved by performing the context model processing and the binary entropy encoding/decoding processing in parallel, such that two-story pipeline processing is performed, resulting in a reduction of a basic cycle time.

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 inFIG. 1. These processing blocks include, for example, a two-dimensional reversible wavelet transform section10, a context model section20, a binary entropy encoder/decoder30, and an integration order generation section50perform 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/decoder30.

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 section10, image data of one tile is spatially divided into frequency bands, for example, as shown inFIGS. 2A–2D, and coefficient data of each frequency band is provided to the context model section20. Because a low frequency band is recursively spatially divided, coefficient data of each frequency band shown inFIG. 2Dis obtained when image data is transformed into three levels.

In the integration order generation section50, 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 section20, context data is created based on the state of the bits (i.e., each bit of a context template shown inFIG. 3) around the target bit, and the binary entropy encoder/decoder30receives the generated context data.

In the binary entropy encoder/decoder30, 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 section40.

In a wavelet transform, coefficient data, corresponding only to the coefficient data of a high frequency band (DS, SD, DD) shown via shading inFIGS. 2B,2C and2D, 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 inFIG. 2Dis encoded, and the coefficient data of a low frequency band (SS3) 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 section50, based on tag information at the header of a codestream. Then, context data is created in the context model section20based on a state of the bits (i.e., which have already been encoded) around the target bit.

In the binary entropy encoder/decoder30, 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 section20. Thus, coefficient data of each frequency band is restored. The coefficient data is reverse transformed by the two-dimensional reversible wavelet transform section10, and image data of one tile is reconstructed.

The tag processing section40adds 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 section40combines a plurality of components formed in one tile in a predetermined order, so as to generate one codestream. The tag processing section40then adds tag information to the header of the codestream. In a decompression (i.e., decoding) process, the tag processing section40interprets 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 inFIG. 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 toFIG. 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 inFIG. 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 inFIG. 6in each bit plane. Accordingly, the target bit moves in a zigzag order of T0, T1, T2, and T3in a left most 2×2 pixel region. Then, the target bit moves in a zigzag order of T4, T5, T6, and T7in 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 section20and between the context model section20and the binary entropy encoder/decoder30is arranged in series, as shown inFIGS. 7 and 8. Further, the context model section20and the binary entropy encoder/decoder30are serially operated as shown inFIG. 9A.

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 template in a decoding operation, a feedback loop, shown as a dotted line inFIG. 8, is required, which makes it difficult to shorten the basic cycle time.

In order to shorten a processing time required for compression and decompression, two or more sets of the context model section20and the two-element entropy encoder/decoder30might be employed so as to operate them in parallel. However, simply operating such device in parallel typically cannot reduce the number of processing cycles, resulting in deterioration of compression efficiency.

SUMMARY OF THE INVENTION

The present invention has been made in view of the above and other problems and addresses the same.

The present invention advantageously provides a novel compression and decompression apparatus, method and computer program product, wherein compression and decompression of image data is performed via a combination of two-dimensional reversible wavelet transform processing, context model processing, and binary entropy encode/decode processing. Faster processing, as compared to conventional devices and methods, is achieved according to the present invention by performing the context model processing and the binary entropy encoding/decoding processing in parallel, such that two-story pipeline processing is performed, resulting in a reduction of a basic cycle time.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views, which illustrate various embodiments of the present invention, as will now be described.

According to an embodiment of the present invention, a compression and decompression apparatus, constructed as shown inFIG. 1, includes a context model section20configured as shown inFIGS. 10 and 11. The context model section20and a binary entropy encoder/decoder30operate in parallel and perform a two-story pipeline processing as shown inFIG. 9B.FIGS. 10 and 11explain relationships between input and output signals during encoding and decoding, respectively.FIG. 12is a timing diagram for illustrating the decoding process.

The binary entropy encoder/decoder30inFIGS. 1,10and11is implemented, for example, as a FSM (Fine State Machine) coder. The context model section20includes a 4-line buffer201for temporarily storing, for example, four lines of coefficient data as shown inFIGS. 6,10and11. The context model section20further includes a context address generation section202, a context table209accessed by using a context address output from the context address generation section202. A context flow control section206controls the flow for context model processing. A multiplexer208is provided for performing context address generation. A register207is provided for latching a next state indication received from the context flow control section206. A register210is provided for latching a generated context address. A register211is provided for latching context data read from a context table209. The context address output from the context address generation section202is provided to the context table209as a read address. The context address is also sent to the context table209as a write address after being latched by the register210. The context data latched by the register211is fed back to the binary entropy encoder/decoder30.

The context address generation section202includes an address generator203, which receives bits A, B, C0, C1, D and E of a context template (FIG. 3) from the 4-line buffer201, and generates a context address according to a state of each bit input. A multiplexer204receives bits C0and C1and provides an output to a table address generator205, which creates a context address (i.e., a table address) corresponding to an address allocation of the context table209. A next state indication latched by the register207is provided to the table address generator205. A decoding bit output from the binary entropy encoder/decoder30is provided to the context flow control section206.

A context address generated by the address generator203includes 1 bit or 2 bits of address information corresponding to each bit of A, B, D, and E in a context template (i.e., address A, address B, address D, and address E inFIGS. 10 and 11). The context address generated by the address generator203also includes 2 sets of 2-bit address information corresponding to bit C in the context template (i.e., address C0and address C1inFIG. 10and11). The address C0is the address information assuming that bit C input into the addresses generator203is “0”, and the address C1is the address information assuming that bit C is “1”. The address generator203simultaneously creates two context addresses. The first context address includes addresses A, B, C0, D and E for a case where the bit C is “0”. The second context address includes addresses A, B, C1, D, and E for a case where bit C is “1.”

The multiplexer204selects either address C0or address C1and provides the selected address to the table address generator205. Both of context addresses, for cases where bit C is “1” or “0”, are created. One of the context addresses is selected depending on whether the multiplexer204selects address C0or the address C1. The selected context address is output as a context address to the context table209via the table address generator205. Such a structure for context address generation, as described above, is effective, especially, during a decoding operation, as will now be described below.

An input selection of the multiplexer204is controlled by an output of the multiplexer208. A target bit moves in a Z-like manner, as preciously described with respect toFIG. 6. A selection of the input of the multiplexer208is controlled by a Z horizontal signal output corresponding to the Z-like movement of the target bit. During encoding, the Z horizontal signal is fixed, such that the multiplexer208always selects bit C (i.e., a bit positioned on the left side of the target bit) provided by the 4-line buffer201. During decoding, the selection of the multiplexer208changes according to the movement of the target bit, i.e., in a horizontal direction or in a slanting direction of the Z-like movement. The multiplexer208selects an appropriate decoding bit T output (i.e., the target bit one processing cycle prior, corresponding to decoded bit C positioned on the left side of the current target bit) from the binary entropy encoder/decoder30when the target bit moves in the horizontal direction. The multiplexer208selects an appropriate bit C provided by the 4-lien buffer201when the target bit moves in the slanting Z-like direction. The multiplexer204selects address C0when an output from the multiplexer208is “0” and address C1when the output from the multiplexer208is “1”.

During encoding, context data is read out from the context table209according to a context address formed by the context address generation section202, and is provided to the binary entropy encoder/decoder30through a register211. The binary entropy encoder/decoder30outputs a code word by encoding a target bit T provided by the 4-line buffer201and by using the given context data. The binary entropy encoder/decoder30also outputs renewal data. In the context table209, the data corresponding to the address designated by the register210, i.e. the data corresponding to the same address from which context data has been readout, is rewritten by the renewal data. The multiplexer208always selects bit C given by the 4-line buffer201, namely, a bit positioned on the left side of a target bit. Therefore, the multiplexer204selects address C0when bit C is “0”, and a context address when bit C being “0” is output from the table address generator205. When bit C is “1”, the multiplexer204selects address C1and a context address when bit C is “1” is output from the table address generator205.

In decoding, context data is read out from the context table209in accordance with a context address output from the context address generation section202, and is fed to the binary entropy encoder/decoder30through the register211. The binary entropy encoder/decoder30decodes a code word input from outside using the context data, and outputs a decoding bit as well as renewal data. The decoded bit is written in a corresponding bit position of the 4-line buffer201. The context table209is rewritten by the renewal data. The multiplexer208selects a decoding bit output from the binary entropy encoder/decoder30when a target bit moves in a horizontal direction. The decoding bit output indicates a state of the target bit one processing cycle before, i.e., it indicates a state of bit C positioned on the left side of the target bit in the current processing cycle. In a later step in a processing cycle, the multiplexer204selects address CO, when a decoding bit input is “0”, and selects address C1, when a decoding bit input is “1”. Then, the context address generation section202outputs a context address corresponding to the address selected by the multiplexer204.

As described above and referring toFIGS. 8 and 11, during decoding, a feedback loop problem occurs when a decoded bit is used again as bit C of a context template for a next target bit. According to an embodiment of the present invention, two context addresses for cases where bit C is “0” and “1” are created in advance focusing on the fact that the decoding bit is either “0” or “1”. When a decoded bit to be output from the binary entropy encoder/decoder30is determined, either of the two context addresses is selected and used depending on a state of the decoded bit output, while directly referring to a state of the decoding bit. Thus, a delay in creating a context address (i.e., which is equivalent to a delay caused by a feedback loop inFIG. 8), is prevented. Such as a delay is caused in a system in which a decoded bit is written once in the 4-line buffer201and then is fed back, as shown inFIG. 8, before creation of a context address. Accordingly, the present invention performs parallel operations of the context model section20and the binary entropy encoder/decoder30efficiently, resulting in increased processing speed.

The feedback loop problem, however, does not occur when a target bit moves in a slanting direction, because a decoded bit is not used as a context bit for the next processing cycle. In this case, bit C read out from the 4-line buffer201by the multiplexer208is selected as described above, and then, the multiplexer204selects either address C0or address C1according to a value of bit C.

As described above and referring toFIG. 5, when a target bit is a “1” head bit, encoding (or decoding) of sign bit S is performed immediately after the “1” head bit has been encoded (or decoded). For example, when encoding (or decoding) is performed in the order shown inFIG. 6, and when the encoded (or decoded) bit of T6is a “1” head bit, the context address of T7has already been created in the cycle. This is due to the two-story pipeline processing according to the present invention. Therefore, one-cycle delay cycle is inserted while the T6bit is retained. Then, encoding (or decoding) of sign bit S is performed after a context address for the sign bit S has been created, and the encoded (or decoded) bit of T7is invalidated. In the next cycle, the encoded (or decoded) bit of the sign bit S is activated, and a context address for T7is generated again. During decoding, the decoded bit of T6is used as the context bit C when a target bit moves in a horizontal direction, e.g. from T6to T7inFIG. 6.

FIG. 12shows a timing diagram of the decoding operation when T6is a “1” head bit. As shown inFIG. 12, the decoded bit of T7is invalidated, when a bit enable signal is at a low level, and a rewrite of the context table209is prohibited. Then, the sign bit S is decoded in the next cycle.

According to the first embodiment of the present invention, a RAM (Random Access Memory) with 2 ports or a register is used as the context table209, and a write-through operation can be performed when data is written to the context table209. That is, both a renewal of the identical address of the context table209and a readout of the renewed data can be performed in one processing cycle, and encoding and decoding processing time can be relatively shortened compared to when a single port RAM is used.

According to the second embodiment of the present invention, the context model section20of the compression and decompression apparatus is configured as shown inFIGS. 13 and 14. The apparatus performs two-story pipeline processing as shown inFIG. 9B, by operating the context model section20and the binary entropy encoder/decoder30in parallel.FIGS. 13 and 14are also used to explain a relation between input and output signals during encoding and decoding, respectively.

According to the second embodiment of the present invention, two context tables209_0and209_1are provided in the context model section20. The context table209_0is used to store context data when bit C of a context template is “0”. The contexts table209_1is used for storing context data when bit C of the context template is “1”. Both of the context tables include either a RAM with 2 ports or a register, and provide a write-through capability.

In the context address generation section202, one bit of the C0address and the C1address output from the address generators203is input to an AND gate220. The output from the AND gate220is input to the table address generator205. A context address output from the table address generator205is provided to the two context tables209_0and209_1as a read address, while being simultaneously provided to the context tables209_0and 209_1as a write address through the register210. A multiplexer221selects either of the remaining single bits of the C0address and the C1address. The multiplexer208control an input selection of the multiplexer221, in as similar manner as described with respect to the multiplexer204of the first embodiment.

A register222latches an output from the multiplexer221. A signal output from the register222is used as a write enable signal for the context table209_0. A signal, which is an output signal from the register222logically inverted by the inverter223, is used as a write enable signal to the context table209_1. Although data from the context tables209_0and209_1are simultaneously read out, a multiplexer224select only one of the two data read out. The register211latches the selected data as context data. A selection of input of the multiplexer224is controlled by an output of the multiplexer221.

During encoding or decoding, a context address, which is common to both when bit C is “0” or “1”, is output from the table address generator205. The context data when bit C is “0” is read out from the context table209_0, and the context data when bit C is “1” is also simultaneously read out from the context table209_1. During encoding, the multiplexer221selects 1 bit from address C0when bit C read out from the 4-line buffer201is “0”. As a result, the multiplexer224select the context data read out from the context table209_0. The selected context data is latched by the register211, and then is provided to the binary entropy encoder/decoder30. With a write enable signal being active, the context table209_0is rewritten with the renewal data output from the binary entropy encoder/decoder30. When bit C is “1”, data read out from the context table209_1is selected, and is provided to the binary entropy encoder/decoder30. The context table209_1is rewritten with the renewal data output from the binary entropy encoder/decoder30when the write enable signal is active.

During decoding, data read out from the context table209_0or 209_1is selected. Either of the data read out then is selected depending on whether a decoding bit output from the binary entropy encoder/decoder30is “0” or “1” corresponding to when a target bit moves in a horizontal direction in the Z-like movement. In addition, either of the data read out is selected depending on whether bit C provided by the 4-line buffer201is “0” or “1” corresponding to when a target bit moves in a slanting direction in the Z-like movement. Thus, the rewriting of data is effectuated.

Accordingly, two context data, for cases where a bit positioned on the left side of a target bit is “0” and “1”, are read out in advance from the context table209_0and209_1respectively, and one of the two data is selected. Therefore, reading of the context tables209_0and209_1is performed earlier than that of the first embodiment. Therefore, although a composition of the apparatus according to the second embodiment becomes relatively complicated compared with the composition in the first embodiment, processing speed is improved.

In a preferred embodiment of the present invention, the context model section20and the binary entropy encoder/decoder30are integrated onto a same IC chip. As described above, the context model section20and the binary entropy encoder/decoder30are closely related to each other, and bit information is frequently exchanged between them. This is advantageous for increasing a processing speed when both the context model section20and the binary entropy encoder/decoder30are placed on a same IC, because a wiring delay in exchanging the information can easily be reduced.

The result of a simulation as to how the processing speed can be increased by applying the present invention to an existing compression and decompression apparatus using a logical synthesis tool will now be described below. The following values represent a percentage of time spent in each processing step, assuming that a basic cycle time spent for encoding (or decoding) a target bit is 100%. Time spent for an integration order generation is included into a context address generation processing time.

(1) Processing time for generating context address: 33%.

(2) Readout time for reading out context table: 17%.

(3) Processing time for the binary entropy coder/decoder: 40%,

(4) Processing time for controlling context flow: 10%.

The above results show that 70% or more of the basic cycle time are spent during the context address generation process and the binary entropy encoding/decoding process. Consequently, it is considered that 1 processing cycle time can be shortened by about a half, when a 2-story pipeline processing is carried out by a parallel operation of the context model section20and the binary entropy encoder/decoder30.

It was confirmed that a processing time can be reduced by about 43% in the first embodiment and by about 50% in the second embodiment, respectively, according to the simulation performed based on the above-described precondition of the ratio of the processing time by using the same logical synthesis tool.

According to the present invention, because the processing performed by the tag processing section40, the integration order generation section50, and the two-dimensional reversible wavelet transform section10is performed on a byte-by-byte or a word-by-word basis, such processes typically have little effect on the processing speed of the device as a whole. Accordingly, such functions may be performed via software operating under control of a DSP (digital signal processor) or a CPU (central processing unit). In contrast, since the processing performed by the context model section20and the binary entropy encoder/decoder30is performed on a bit-by-bit basis, a specific hardware implementation is used to perform such functions when high-speed processing is required.

Further, in order to shorten a processing time required for compression and decompression, two or more sets of the context model section20and the two-element entropy encoder/decoder30might be employed so as to operate them in parallel. However, various functions (e.g., various quantization functions performed via bit plane encoding, a progressive reproduction/display function performed via bit plane transmission, etc), which are features of the compression and decompression apparatus of the present invention, typically cannot be performed via a simple parallel implementation approach in order to reduce the number of processing cycles. Therefore, a simple parallel implementation approach typically results in deterioration of compression efficiency.

The mechanisms and processes set forth in the present invention may be implemented using one or more conventional general purpose microprocessors and/or signal processors programmed according to the teachings in the present specification, as will be appreciated by those skilled in the relevant art(s). Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will also be apparent to those skilled in the relevant art(s). However, as will be readily apparent to those skilled in the art, the present invention also may be implemented by the preparation of application-specific integrated circuits, by interconnecting an appropriate network of conventional component circuits or by a combination thereof with one or more conventional general purpose microprocessors and/or signal processors programmed accordingly.

The present invention thus also includes a computer-based product which may be hosted on a storage medium and include instructions which can be used to program a microprocessor to perform a process in accordance with the present invention. This storage medium can include, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, flash memory, magnetic or optical cards, or any type of media suitable for storing electronic instructions.

This document claims priority and contains subject matter related to Japanese Patent Application No. 11-311919, filed on Nov. 2, 1999, the entire contents of which is incorporated by reference herein.