Abstract:
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.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application is a continuation application of Ser. No. 09/703,873 filed Nov. 2, 2000, now U.S. Pat. No. 6,792,150 and claims the benefit of priority from prior Japanese Patent Application No. 11-311919, filed Nov. 2, 1999, the entire contents which are incorporated herein by reference. 

   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  FIGS. 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 (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 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&#39;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. 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 in  FIG. 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 section  20  and the two-element entropy encoder/decoder  30  might 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. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete appreciation of the present invention and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein: 
       FIG. 1  is a block diagram illustrating a compression and decompression apparatus, according the present invention; 
       FIGS. 2A–2D  illustrate exemplary spatial division of a frequency band by a two-dimensional reversible wavelet transformation; 
       FIG. 3  is a diagram for illustrating the operation of a context template; 
       FIG. 4  is a table for illustrating data having a bit-significance representation; 
       FIG. 5  is a diagram for illustrating the operation of encoding or decoding a “1” head bit and sign bit; 
       FIG. 6  is a diagram for illustrating the processing of a target bit; 
       FIG. 7  is a block diagram illustrating dataflow during encoding in a background art image data compression and decompression system; 
       FIG. 8  is a block diagram illustrating dataflow during decoding in a background art image data compression and decompression system; 
       FIG. 9A  is a diagram for illustrating a decoding procedure in a background art image data compression and decompression system; 
       FIG. 9B  is a diagram for illustrating a decoding procedure, according to the present invention; 
       FIG. 10  is a block diagram of a context model section for illustrating a relation between input and output signals during encoding, according to an embodiment of the present invention; 
       FIG. 11  is a block diagram of a context model section for illustrating a relation between input and output signals during decoding, according to an embodiment of the present invention; 
       FIG. 12  is a timing diagram for describing a decoding operation, according to an embodiment of the present invention; 
       FIG. 13  is a block diagram of a context model section for illustrating a relation between input and output signals during encoding, according to another embodiment of the present invention; and 
       FIG. 14  is a block diagram of a context model section for illustrating a relation between input and output signals during decoding, according to another embodiment of the present invention. 
   

   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 in  FIG. 1 , includes a context model section  20  configured as shown in  FIGS. 10 and 11 . The context model section  20  and a binary entropy encoder/decoder  30  operate in parallel and perform a two-story pipeline processing as shown in  FIG. 9B .  FIGS. 10 and 11  explain relationships between input and output signals during encoding and decoding, respectively.  FIG. 12  is a timing diagram for illustrating the decoding process. 
   The binary entropy encoder/decoder  30  in  FIGS. 1 ,  10  and  11  is implemented, for example, as a FSM (Fine State Machine) coder. The context model section  20  includes a 4-line buffer  201  for temporarily storing, for example, four lines of coefficient data as shown in  FIGS. 6 ,  10  and  11 . The context model section  20  further includes a context address generation section  202 , a context table  209  accessed by using a context address output from the context address generation section  202 . A context flow control section  206  controls the flow for context model processing. A multiplexer  208  is provided for performing context address generation. A register  207  is provided for latching a next state indication received from the context flow control section  206 . A register  210  is provided for latching a generated context address. A register  211  is provided for latching context data read from a context table  209 . The context address output from the context address generation section  202  is provided to the context table  209  as a read address. The context address is also sent to the context table  209  as a write address after being latched by the register  210 . The context data latched by the register  211  is fed back to the binary entropy encoder/decoder  30 . 
   The context address generation section  202  includes an address generator  203 , which receives bits A, B, C 0 , C 1 , D and E of a context template ( FIG. 3 ) from the 4-line buffer  201 , and generates a context address according to a state of each bit input. A multiplexer  204  receives bits C 0  and C 1  and provides an output to a table address generator  205 , which creates a context address (i.e., a table address) corresponding to an address allocation of the context table  209 . A next state indication latched by the register  207  is provided to the table address generator  205 . A decoding bit output from the binary entropy encoder/decoder  30  is provided to the context flow control section  206 . 
   A context address generated by the address generator  203  includes 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 in  FIGS. 10 and 11 ). The context address generated by the address generator  203  also includes 2 sets of 2-bit address information corresponding to bit C in the context template (i.e., address C 0  and address C 1  in  FIG. 10  and  11 ). The address C 0  is the address information assuming that bit C input into the addresses generator  203  is “0”, and the address C 1  is the address information assuming that bit C is “1”. The address generator  203  simultaneously creates two context addresses. The first context address includes addresses A, B, C 0 , D and E for a case where the bit C is “0”. The second context address includes addresses A, B, C 1 , D, and E for a case where bit C is “1.” 
   The multiplexer  204  selects either address C 0  or address C 1  and provides the selected address to the table address generator  205 . 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 multiplexer  204  selects address C 0  or the address C 1 . The selected context address is output as a context address to the context table  209  via the table address generator  205 . 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 multiplexer  204  is controlled by an output of the multiplexer  208 . A target bit moves in a Z-like manner, as preciously described with respect to  FIG. 6 . A selection of the input of the multiplexer  208  is 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 multiplexer  208  always selects bit C (i.e., a bit positioned on the left side of the target bit) provided by the 4-line buffer  201 . During decoding, the selection of the multiplexer  208  changes 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 multiplexer  208  selects 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/decoder  30  when the target bit moves in the horizontal direction. The multiplexer  208  selects an appropriate bit C provided by the 4-lien buffer  201  when the target bit moves in the slanting Z-like direction. The multiplexer  204  selects address C 0  when an output from the multiplexer  208  is “0” and address C 1  when the output from the multiplexer  208  is “1”. 
   During encoding, context data is read out from the context table  209  according to a context address formed by the context address generation section  202 , and is provided to the binary entropy encoder/decoder  30  through a register  211 . The binary entropy encoder/decoder  30  outputs a code word by encoding a target bit T provided by the 4-line buffer  201  and by using the given context data. The binary entropy encoder/decoder  30  also outputs renewal data. In the context table  209 , the data corresponding to the address designated by the register  210 , i.e. the data corresponding to the same address from which context data has been readout, is rewritten by the renewal data. The multiplexer  208  always selects bit C given by the 4-line buffer  201 , namely, a bit positioned on the left side of a target bit. Therefore, the multiplexer  204  selects address C 0  when bit C is “0”, and a context address when bit C being “0” is output from the table address generator  205 . When bit C is “1”, the multiplexer  204  selects address C 1  and a context address when bit C is “1” is output from the table address generator  205 . 
   In decoding, context data is read out from the context table  209  in accordance with a context address output from the context address generation section  202 , and is fed to the binary entropy encoder/decoder  30  through the register  211 . The binary entropy encoder/decoder  30  decodes 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 buffer  201 . The context table  209  is rewritten by the renewal data. The multiplexer  208  selects a decoding bit output from the binary entropy encoder/decoder  30  when 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 multiplexer  204  selects address CO, when a decoding bit input is “0”, and selects address C 1 , when a decoding bit input is “1”. Then, the context address generation section  202  outputs a context address corresponding to the address selected by the multiplexer  204 . 
   As described above and referring to  FIGS. 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/decoder  30  is 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 in  FIG. 8 ), is prevented. Such as a delay is caused in a system in which a decoded bit is written once in the 4-line buffer  201  and then is fed back, as shown in  FIG. 8 , before creation of a context address. Accordingly, the present invention performs parallel operations of the context model section  20  and the binary entropy encoder/decoder  30  efficiently, 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 buffer  201  by the multiplexer  208  is selected as described above, and then, the multiplexer  204  selects either address C 0  or address C 1  according to a value of bit C. 
   As described above and referring to  FIG. 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 in  FIG. 6 , and when the encoded (or decoded) bit of T 6  is a “1” head bit, the context address of T 7  has 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 T 6  bit 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 T 7  is invalidated. In the next cycle, the encoded (or decoded) bit of the sign bit S is activated, and a context address for T 7  is generated again. During decoding, the decoded bit of T 6  is used as the context bit C when a target bit moves in a horizontal direction, e.g. from T 6  to T 7  in  FIG. 6 . 
     FIG. 12  shows a timing diagram of the decoding operation when T 6  is a “1” head bit. As shown in  FIG. 12 , the decoded bit of T 7  is invalidated, when a bit enable signal is at a low level, and a rewrite of the context table  209  is 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 table  209 , and a write-through operation can be performed when data is written to the context table  209 . That is, both a renewal of the identical address of the context table  209  and 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 section  20  of the compression and decompression apparatus is configured as shown in  FIGS. 13 and 14 . The apparatus performs two-story pipeline processing as shown in  FIG. 9B , by operating the context model section  20  and the binary entropy encoder/decoder  30  in parallel.  FIGS. 13 and 14  are 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 tables  209 _ 0  and  209 _ 1  are provided in the context model section  20 . The context table  209 _ 0  is used to store context data when bit C of a context template is “0”. The contexts table  209 _ 1  is 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 section  202 , one bit of the C 0  address and the C 1  address output from the address generators  203  is input to an AND gate  220 . The output from the AND gate  220  is input to the table address generator  205 . A context address output from the table address generator  205  is provided to the two context tables  209 _ 0  and  209 _ 1  as a read address, while being simultaneously provided to the context tables  209 _ 0  and 209_ 1  as a write address through the register  210 . A multiplexer  221  selects either of the remaining single bits of the C 0  address and the C 1  address. The multiplexer  208  control an input selection of the multiplexer  221 , in as similar manner as described with respect to the multiplexer  204  of the first embodiment. 
   A register  222  latches an output from the multiplexer  221 . A signal output from the register  222  is used as a write enable signal for the context table  209 _ 0 . A signal, which is an output signal from the register  222  logically inverted by the inverter  223 , is used as a write enable signal to the context table  209 _ 1 . Although data from the context tables  209 _ 0  and  209 _ 1  are simultaneously read out, a multiplexer  224  select only one of the two data read out. The register  211  latches the selected data as context data. A selection of input of the multiplexer  224  is controlled by an output of the multiplexer  221 . 
   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 generator  205 . The context data when bit C is “0” is read out from the context table  209 _ 0 , and the context data when bit C is “1” is also simultaneously read out from the context table  209 _ 1 . During encoding, the multiplexer  221  selects 1 bit from address C 0  when bit C read out from the 4-line buffer  201  is “0”. As a result, the multiplexer  224  select the context data read out from the context table  209 _ 0 . The selected context data is latched by the register  211 , and then is provided to the binary entropy encoder/decoder  30 . With a write enable signal being active, the context table  209 _ 0  is rewritten with the renewal data output from the binary entropy encoder/decoder  30 . When bit C is “1”, data read out from the context table  209 _ 1  is selected, and is provided to the binary entropy encoder/decoder  30 . The context table  209 _ 1  is rewritten with the renewal data output from the binary entropy encoder/decoder  30  when the write enable signal is active. 
   During decoding, data read out from the context table  209 _ 0  or 209_ 1  is selected. Either of the data read out then is selected depending on whether a decoding bit output from the binary entropy encoder/decoder  30  is “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 buffer  201  is “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 table  209 _ 0  and  209 _ 1  respectively, and one of the two data is selected. Therefore, reading of the context tables  209 _ 0  and  209 _ 1  is 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 section  20  and the binary entropy encoder/decoder  30  are integrated onto a same IC chip. As described above, the context model section  20  and the binary entropy encoder/decoder  30  are 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 section  20  and the binary entropy encoder/decoder  30  are 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 section  20  and the binary entropy encoder/decoder  30 . 
   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 section  40 , the integration order generation section  50 , and the two-dimensional reversible wavelet transform section  10  is 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 section  20  and the binary entropy encoder/decoder  30  is 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 section  20  and the two-element entropy encoder/decoder  30  might 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. 
   Numerous additional modifications and variations of the present invention are possible in light of the above teachings. It is therefore to be understood that within the scope of the appended claims, the present invention may be practiced otherwise than as specifically described herein. 
   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.