JPH10200413A - Variable length code generator and generating method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To generate an efficient variable length code in image encoding. SOLUTION: In a variable length encoding device 3, a run code generating part 10 defines a run group to which the run length of an inputted discrete cosine transformation coefficient belongs, generates a run variable length code that represents the defined group, also generates a run fixed length code that represents a run length and generates a run code. Similarly, a level code generating part 12 independently generates a level code from the level of the DCT coefficient. A synthesizing part 13 generates a final variable length code.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to image coding, and more particularly to DC coding.
The present invention relates to generation of a variable length code from a T coefficient or the like.

[0002]

2. Description of the Related Art In image coding, D
CT (Discrete Cosine Transform
)) Is widely used. This method has an effect of dividing into components sensitive to human vision (low-frequency components) and components not sensitive to human vision (high-frequency components). The components after DCT are called DCT coefficients. By transmitting the low-frequency components preferentially, a visually natural image can be transmitted with a small amount of information. The DCT coefficient is represented by a combination of a run length representing the frequency (more precisely, a distance from the immediately preceding component on the low frequency side) and a level representing the signal strength, that is, (run length, level). Normally, since the DCT is applied to an area of 8 × 8 pixels (this is called a block), the run length is from 0 to 63.
And the level takes a value from -127 to +127.

In order to reduce the overall transmission code amount, variable length coding (also referred to as entropy coding) is performed by using the property that the smaller the absolute value of a run length and the level, the higher the probability of occurrence of a coefficient. ). First, a variable length code having a length corresponding to the appearance probability of each (run length, level) is determined, and the correspondence is previously stored in a table. (This is called the Huffman table). Normal,
A shorter code is assigned to a coefficient having a higher appearance probability to reduce the overall code amount. At the time of encoding, a variable length code corresponding to the (run length, level) of the DCT coefficient is read from a Huffman table (usually composed of about 120 elements) and output (this is referred to as a table). The Huffman table has EOB (End Of B
There is a special code called lock), which indicates a block boundary by inserting it immediately after the last coefficient in the block. In image coding, this series of processing is performed on all blocks in an image.

However, when a standardized image coding method is used, a Huffman table specified in the method must be used, and it may not be possible to flexibly cope with various situations. For example, if the DCT coefficients are not transmitted in most blocks even though the EOB is a 4-bit code, about 4 bits are consumed per block. If the EOB is set to 2 bits, it is possible to reduce 2 bits per block, and the compression effect is improved. However, in the current standard, the best solution is to allow at most two types of Huffman tables to be selected, and more flexible handling is not possible.

Another problem arises when a plurality of Huffman tables are prepared. That is, both the encoder and the decoder need to hold the Huffman table in the memory (storage element), which requires a large memory capacity. On the decoder side, a Huffman code is used to return the bit string, which is a chain of variable length codes, to the original (run length, level) representation.
It is necessary to search the table, and the time required for decoding increases in proportion to the number of elements in the table.
As described above, there are various problems in variable-length coding of DCT coefficients. In other words, if a predetermined Huffman table is used, it is not possible to flexibly cope with changes in the type of image and changes in encoding parameters. Further, if a plurality of Huffman tables are prepared to solve this problem, the complexity of the apparatus increases in proportion to the number of elements, and the operation speed also decreases.

An object of the present invention is to provide a function capable of flexibly responding to changes in image types and coding parameters while reducing the number of elements in a Huffman table.
Thus, simplification of the encoding / decoding device and speeding up of the decoding process can be achieved at the same time. Another object of the present invention is to simplify a variable length coding and decoding part in an image coding apparatus mounted on a portable terminal that performs image transmission using a communication band of a narrow band (64 kilobits per second or less),
And to provide a function for speeding up.

[0007]

According to the present invention, a run group to which a value of a run length of an input DCT coefficient belongs is determined, a run variable length code representing the determined group is generated, and the run A run code generation unit that generates a run fixed length code representing a length value, and synthesizes the run variable length code and the run fixed length code to generate a run code; and a level value of an input DCT coefficient , And a level variable length code representing the defined group is generated, and a level fixed length code representing the level value is generated, and the level variable length code and the level fixed length code are generated. Variable length including a level code generation unit that generates a level code by synthesizing the run code and a variable length code based on the run code and the level code Providing over de generator.

[0008] Also, DCT is performed by DCT conversion from the pixel signal.
A variable-length code generation method for generating a coefficient and outputting a variable-length code from the generated DCT coefficient, wherein the code indicates that the code is the last DCT coefficient in the block, or the DCT coefficient continues in the block. A variable-length code generation method including the step of adding one of the codes indicating that the code exists and adding the code according to the number of DCT coefficients in the block, and outputting the variable-length code. Further, there is provided a variable length code generation method for combining a variable length portion and a fixed length portion and outputting the variable length code as a variable length code,
The bits forming the variable-length portion corresponding to the group to which the numerical value to be represented belongs and the bits forming the fixed-length portion corresponding to the numerical value to be expressed are alternately folded at a fixed ratio and synthesized, and the synthesized bits A variable length code generation method includes a step of outputting a group as a variable length code.

In one embodiment, there is no Huffman table and instead about ten "code seeds" are defined. Then, at the time of encoding, as many as 16,000 types of codes are configured by combinations of “code types”. In the conventional method, 120 codes out of 16,000 kinds are represented by a Huffman table, and the other codes use an escape sequence. In this method, a DCT coefficient having a low appearance probability is represented by a fixed length code (run length is 6 bits and level is 8 bits) representing a run length and a level following an escape code (a 7-bit variable length code). is there. At this time, the variable length encoder uses
16,000 to determine whether to use the code
An additional table equivalent to bits is required. In contrast,
By using a combination of "code types", the memory capacity for expressing a code table equivalent to the Huffman table can be reduced to 1/50 or less.

[0010] Further, by assigning an EOB representing a block boundary to one of "code types" and making the code length variable, it is possible to flexibly cope with a change in the number of DCT coefficients in a block. As a special case of this EOB code,
nEOB (negative EOB) is defined as a code indicating that DCT coefficients to be encoded / decoded exist in the block. This makes it possible to cope with a situation where the average DCT coefficient per block is close to 1 (occurs when encoding at a low bit rate, etc.). Then, the run length and the level are encoded and decoded independently. At this time, the apparatus can be simplified by adopting the same code configuration for both the run length and the level and sharing the "code type". As a result, the decoding side can perform a maximum of a total of 20 verifications using a run length and a level, which has conventionally required a maximum of 120 verifications for one DCT coefficient, and reduces the time required for decoding to about 1/6. It is possible to reduce up to.

As a secondary effect, there is expandability to DCT of 16 × 16 pixels (currently, 8 × 8 pixels). In other words, in the case of DCT in units of 16 × 16 pixels, the maximum run length is 255, but the predetermined Huffman table cannot cope with a run length of 63 or more. In the present invention,
Only by adding two “code seeds” can the response be made.
Also, a method of generating a variable-length code that can be decoded in both directions is provided. If an error occurs in the bit string on the transmission line, the error is avoided and the process skips to the next known code (this is called a synchronization code), and performs decoding in the reverse direction (that is, the direction going back in the past). . This makes it possible to recover an undecodable bit string that had to be discarded in the past, and to minimize the effects of errors.

[0012]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a block diagram illustrating a configuration example of an image encoding device to which the variable length encoding according to the present invention is applied. In FIG. 1, a DCT unit 1 performs a DCT (discrete cosine transform) process on an 8 × 8 pixel block, and a quantization unit 2 accurately quantizes low-frequency components so that the DCT coefficients match human vision. . Then, the variable length coding unit 3 converts each DCT coefficient represented by (run length, level) into a variable length code. An encoding control unit 4 connected to the variable length encoding unit 3 determines an optimal encoding mode for each image. The nEOB flag and the EOB code length shown as outputs from the encoding control unit 4 indicate a mode in which the code amount is minimized, and are switched in units of normal images. On the other hand, the block boundary signal shown as an output from the quantization unit 2 is not intended for code amount control, but is uniquely determined from the distribution of DCT coefficients in the block.

FIG. 2 is a block diagram for explaining the variable length coding unit of FIG. The variable-length encoding unit independently encodes the run length and the level, synthesizes the respective codes in the order of the run length and the level, and outputs a final variable-length code. The code is generated in two steps for both the run length and the level. First, in the first stage, a group to which an input value belongs is obtained, and a variable length code representing the group is output. In the second stage, a fixed length code representing the input value itself is output. That is, the run code representing the run length is composed of a variable run length code and a fixed run length code, and the level code representing the level is composed of a variable level length code and a fixed level length code. That is, the run code generation unit 10 generates a run variable length code and a fixed run length code in accordance with the code table based on the run length input from the quantization unit 2, and sends the combined run code to the synthesis unit 13. level·
The code generation unit 12 generates a level variable length code and a fixed level length code in accordance with the code table based on the level input from the quantization unit 2, and sends a level code obtained by synthesizing them to the synthesis unit 13. In synthesizing the respective codes, it is not always necessary to transmit the codes in the order of the run length and the level. This order may be reversed. Alternatively, the run length may be transmitted one block (up to 64 blocks) sequentially from the low frequency side, and then the same number of levels may be transmitted in correspondence with the run length order. It is possible. It is also possible to transmit the run length and the level collectively in an image unit instead of a block unit.

The advantages of independently encoding the run length and the level are as follows. The run length is more important when the run length and level representing the DCT coefficient are considered from the viewpoint of error resistance (a function for preventing a fatal effect on a decoded image when an error occurs). Therefore, a method of changing the error correction strength (the degree of ability to detect and correct an error when it occurs) based on the run length and the level is effective. In this case, it is necessary to increase the error correction strength of the run length, which is important information (this also increases the number of redundant bits and lowers the coding efficiency), thereby efficiently improving the error resilience. Can be. For example, assuming a certain DCT coefficient (R, L), a case where the run length is shifted by 1 (R + 1, L) and a case where the level is shifted by 1 (R, L + 1) are considered. When two coefficients in which an error has occurred are subjected to inverse DCT (a process of converting DCT coefficients into a block image) and compared, (R, L + 1) is close to the original image in which (R, L) has been subjected to inverse DCT. It is. In other words, if a strong error resistance is applied to the run length, errors in the run length hardly occur, and even if an error occurs in the level, it does not have as fatal influence as an error in the run length.

In this embodiment, E represents a block boundary.
The OB code is assigned as one of the level variable length codes. Changing the EOB code length corresponds to a change in the number of DCT coefficients in the block. The determination of the EOB code length is performed by the encoding control unit 4 (encoding side), and the discrimination between intra-image encoding and inter-image encoding, the type of the target image and the encoding rate (consumable code amount), etc. Take this into consideration. In general, the number of DCT coefficients increases as the content of an image becomes more complicated and as the coding rate increases. In such a case, the EOB code length is increased.
In most cases, it works properly if the EOB code length is set to 3 or 4 bits for intra-picture coding and 2 bits for inter-picture coding. Switching of the EOB code length in intra-picture coding is probabilistic if a determination criterion is used in which the number of DCT coefficients in a block is 3 bits if the average number is less than 8, and 4 bits if the average number is 8 or more. Appropriate in some sense.
In the normal mode (called the EOB mode, in which the nEOB flag is OFF), the EOB code is inserted between the run code and the level code when the block boundary signal is ON. Note that this block boundary signal is turned ON only when it is the last DCT coefficient in the block.
That is, in the quantization unit 2, the DCT coefficients in the block are sequentially set one by one from the low frequency side (a maximum of 6
(4 DCT coefficients are output one by one) to the variable-length coding unit 3. When processing of a certain block is started, the block boundary signal is always turned off, and when the last DCT coefficient is turned on, the block boundary signal is turned on.

That is, in FIG. 2, the EOB code generator 1
1 is an nEOB flag input from the encoding control unit 4;
An EOB code is generated based on the OB code length according to the code table, and sent to the synthesizing unit 13. Generation of the EOB code will be described later. Then, the final variable length code is output from the synthesizing unit 13. The determination of the code of the run length and the level and the generation of the EOB code in this embodiment will be described below.

In this embodiment, the following model is assumed for the appearance probability of the DCT coefficient, and the codes of the run length and the level are determined. (1) Run length probability model A variable length code representing run length = 0 is set to 0 (probability of occurrence 1
/ 2). Hereinafter, the run length in the range represented by the power of 2 is set as one group, and 1 is added to the variable length code. (2) Level Probability Model The variable length code representing the absolute value of the level = 1 is set to 0 (corresponding to 1/2 the occurrence probability). Hereinafter, the absolute value level in the range represented by the power of 2 is set as one group, and 1 is added to the variable length code.

Although this model is not optimized as much as the Huffman table, the performance of DCT coefficients with a high frequency of appearance (that is, both run length and absolute value level are small) is almost similar to that of the Huffman table. Is shown. Tables 1 and 2 show a code table of run lengths and levels (combination table of "code types") based on the above model. In this table, the EOB code length is set to 3 bits in order to adapt to intra-picture encoding in which DCT coefficients in a block are relatively large. For example, consider a case where DCT coefficients (3, -5) are variable-length coded. From Table 1, the run variable length code of group 2 including run value 3 is “110”, the run fixed length code is “1” (a bit string excluding the most significant bit of binary number “11” representing 3), and the run is -Code "1101" is obtained. Also, from Table 2, group 2 including level value -5
Is "1110", the fixed-level code is "101" (the most significant bit indicates negative), and
The level code “1110101” is obtained. When the run code and the level code are combined in this order, the DCT
Variable length code “1101111” representing coefficient (3, −5)
0101 ". If this is the last coefficient (block boundary) in the block, the run code and the level code
Insert the EOB code “110” between the codes and enter “110”
11101110101 ".

In the case of DCT coefficients (2, -5) belonging to the same run group 2 and having different run lengths (run values 2), only the fixed run length code differs from the DCT coefficients (3, -5). Will be. That is, the run fixed-length code is “0” (a bit string excluding the most significant bit of the binary number “10” representing 2), the variable-length code representing the DCT coefficient (2, −5) is “11001110101”, Only the fourth bit from the beginning is different from the variable length code representing the DCT coefficient (3, -5). Table 3 shows the DC in the block.
In order to adapt to inter-picture coding with relatively few T coefficients,
This indicates a "code type" in which the EOB code length is set to 2 bits. As described above, optimization can be performed by changing the EOB code length for each image, and furthermore, this can be realized only by replacing the level variable length code including eight “code types”. If the EOB code length is changed by a conventional method using a Huffman table, it is necessary to replace all the variable length codes, and after all, a plurality of tables must be provided.

[0020]

[Table 1]

[0021]

[Table 2]

[0022]

[Table 3]

Next, an effective measure for a case where the average number of DCT coefficients in a block is close to 1 will be considered. This situation tends to occur particularly when inter-coding is performed at a low coding rate. Table 4 shows a distribution example of DCT coefficients in four blocks, and shows a case where three of four blocks have one DCT coefficient and the remaining one has two DCT coefficients. As described above, when the EOB code length is set to 2 bits, two bits are required to indicate a block boundary when there is one DCT coefficient in the block. EOB
The code length of 2 bits is unsuitable in a probabilistic sense, assuming that the average number of DCT coefficients in a block is about 4. Table 5 shows the results of variable-length coding of the DCT coefficients of Table 4 without taking any measures.

[0024]

[Table 4]

[Table 5]

As a countermeasure described above, a code having a meaning opposite to that of EOB is defined to reduce the number of bits required to indicate a block boundary. This is called nEOB (negative EO).
Call it B) and use the same code as EOB. E
Switching between OB mode and nEOB mode in image units
This is performed by the encoding control unit (encoding side). In the nEOB mode, if the DCT coefficient in the block is 1, there is no need to send the nEOB code. That is, the nEOB code is inserted as a code representing “continuation” only when there are two or more DCT coefficients. Table 6 shows D in Table 4 according to the nEOB mode.
The result of variable length coding of the CT coefficient is shown. From the results of Tables 5 and 6, as shown in Table 4, when the average number of DCT coefficients in a block is close to 1, the code amount of the nEOB mode can be reduced by about 20% as compared with the EOB mode. In the nEOB mode (the nEOB flag is ON), when the block boundary signal is OFF, an EOB code is inserted between the run code and the level code.

[0026]

[Table 6]

A comparison will be made between the complexity and processing speed of the variable-length coding device using the present invention and the conventional Huffman table. In the present invention, the required memory capacity is 1/50 or less on the encoding side and 1/50 on the decoding side, as compared with the conventional method using the Huffman table.
It can be reduced to about / 10. Regarding the processing speed, in the present invention, as compared with the conventional method, the encoding side is equivalent,
Whereas the decoding side conventionally required a maximum of 120 checks for one DCT coefficient, the present invention can realize a total of 15 checks for the run length and level, and can improve the speed by about 8 times. . Next, a second embodiment of the present invention will be described. In this embodiment, a DCT of 16 × 16 pixels is used.
(Currently, 8 × 8 pixel units).
In other words, in the case of DCT of 16 × 16 pixels, the run length is a maximum of 255, but the predetermined Huffman table cannot cope with a run length of 63 or more. According to the present invention, it is possible to cope with the situation simply by adding two “code types”.

Table 7 shows a 16 × 16 DCT extended version run code table. Similarly, D in a larger block unit
It can be extended to CT.

[Table 7]

The level can be expanded simply by adding a "code type". Table 8 shows the absolute value of 255.
Here is a code table of the levels corresponding to the levels up to and including:

[Table 8]

An experiment using a computer was performed to evaluate the performance of this embodiment. For comparison, H.264, which is a video transmission standard at a low bit rate, is used. 263 was used. In this embodiment, the EOB code length is set to 3 bits in the EOB mode in intra-picture coding, and the EOB code length is set to 2 bits in the nEOB (negative EOB) mode in inter-picture coding. As test images, two standard images, Mother & Daughter and Foreman, were used. Table 9 shows the number of bits required to encode DCT coefficients in each image.

[Table 9]

From this result, the present embodiment is based on the conventional standard H.264. As compared with H.263, the performance improvement of 1 to 3% can be confirmed for both intra-picture coding and inter-picture coding. Even if the performances are equivalent, it can be determined that the present embodiment, which can achieve the simplification of the encoding device and the improvement of the processing speed, is more advantageous.
H. The Huffman table of H.263 has been optimized for inter-picture coding, but this embodiment further exceeds it. This is because the nEOB mode is working effectively.

Next, FIG. 3 shows a decoding process in the case where a bit string is affected by a noise component on a transmission path and an error occurs in a variable length code according to the fourth aspect of the present invention. FIG. 11A shows a decoding process using only a variable length code that can be decoded in one direction (forward direction) and only error avoidance. When an error occurs in the bit string, the decoding side decodes the code as another variable length code, or stops decoding because there is no corresponding variable length code. In the former case, if the code length is correct, no error is propagated, but in most cases, the latter case will eventually be reached. In the latter case, decoding is resumed by searching for the next synchronization code. However, conventional variable-length codes that can only be decoded in the forward direction cannot be decoded in the reverse direction from the synchronization code, so the bit string from the error occurrence point to the synchronization code must be discarded. Even so, they are affected by errors. In this example, the variable length codes a to e are discarded.

As a method for suppressing the influence of errors, FIG.
As shown in (b), a bidirectional decoding method in which a variable length code that can be bidirectionally decoded is used for decoding in the reverse direction (that is, the direction going back in the past) from a synchronous code has been studied. In this example, the variable length codes b to e can be decoded by backward decoding (error recovery), and only the variable length code a is discarded. However, in general, in the bidirectional decoding method, it is necessary to have separate Huffman tables for the forward direction and the backward direction, which complicates the decoding device.

Therefore, taking advantage of the above-described feature of the present invention that a variable length code to be transmitted is constituted by a combination of a "code type" and a fixed length code whose length is defined by the "code type", By alternately folding the fixed-length code at a fixed rate (for example, “code type” and the fixed-length code are superimposed one bit at a time), a bidirectionally decodable variable-length code is created. Table 1
0 shows an example of a variable length code obtained by alternately folding a "code type" (variable length portion) and a fixed length code (fixed length portion) one bit at a time. For example, the variable length code "0111
“0” indicates that the variable length portion is “010”, and the fixed length portion is “11”.
Therefore, 6 is represented. Example of creating a variable length code capable of bidirectional decoding using Table 10 (0,
2, 10, 5) are shown in FIG.

[0035]

[Table 10]

At this time, in all the variable length codes, the bit length of the variable length part: M and the bit length of the fixed length part: L have a linear relationship (ie, gM = hL + i, where g,
h is a natural number, i is an integer) and the variable length part is symmetric (equal in both forward and backward directions) Conditions for generating a bidirectionally decodable variable length code Becomes In the case of Table 10, the relationship is M = L + 1. The variable length code created under this condition is
The variable length portion and the fixed length portion are superposed at a ratio of h: g when viewed from both the front and rear directions. Although the embodiment has been described in detail as described above, the present invention is not limited to this.

[0037]

According to the present invention, when encoding / decoding image information, it is possible to provide a function that can flexibly respond to changes in the type of image and changes in encoding parameters. Simultaneous simplification of the apparatus and speeding up of the decoding process can be achieved. In addition, the effect of code amount reduction is equivalent to that of the current standard.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration example of an image coding apparatus to which a variable length code generation technique according to the present invention is applied.

FIG. 2 is a block diagram of a variable length encoding unit.

FIG. 3 is a view for explaining decoding processing using bidirectional decoding.

FIG. 4 is a diagram showing a variable length code capable of bidirectional decoding.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 DCT part 2 Quantization part 3 Variable length encoding part 4 Encoding control part 10 Run code generation part 11 EOB code generation part 12 Level code generation part 13 Synthesis part

Claims (4)

[Claims] 1. A run group to which a value of a run length of an input DCT coefficient belongs is determined, a run variable length code representing the defined group is generated, and a run fixed length code representing the run length value is generated. A run code generation unit that generates the run variable length code and the run fixed length code to generate a run code; and determines a level group to which the level value of the input DCT coefficient belongs. Generating a level variable length code representing the group, and generating a level fixed length code representing the value of the level, and combining the level variable length code and the level fixed length code to generate a level code. A variable length code generation device, comprising: a level code generation unit; and a synthesis unit that generates a variable length code based on the run code and the level code. 2. The variable length code generation device according to claim 1, further comprising an EOB code generation unit that generates a code representing a block boundary to be included in the variable length code. 3. A variable-length code generating method for generating a DCT coefficient from a pixel signal by DCT conversion and outputting a variable-length code from the generated DCT coefficient, which means that the variable-length code is the last DCT coefficient in a block. And adding a code indicating that DCT coefficients are continuously present in the block according to the number of DCT coefficients in the block and outputting the code as a variable length code. Long code generation method. 4. A variable length code generating method for combining a variable length portion and a fixed length portion and outputting the variable length code as a variable length code, comprising: a bit forming a variable length portion corresponding to a group to which a numerical value to be represented belongs; A variable length code generation method, comprising the steps of: alternately folding a fixed length portion corresponding to a numerical value to be represented and a bit constituting a fixed length portion at a fixed ratio to synthesize; and outputting the synthesized bit group as a variable length code.