Variable Length Encoding Method and Apparatus for Differential Motion Vector Values Using an Improved Differential Motion Code Table

1. Field of the Invention

The present invention relates to a variable-length encoding method and apparatus for a differential motion vector value using a differential motion code table. More particularly it relates to a variable-length encoding method and apparatus for a differential motion vector value using an improved differential motion code table, in which an amount of data generated due to encoding of motion vector values can be reduced by improving the differential motion code table for variable-length-encoding a differential value between adjacent motion vector values within an image frame.

2. Description of Related Art

Generally, if an analog image signal is converted into digital data, the amount of data to be processed is increased. For this reason a variety of methods are used to reduce the total amount of image signal data by removing redundant data included in the digital data image.

Among these methods, there is a prediction encoding method for encoding image data using differential values of image data between adjacent frames. The prediction encoding method uses a motion vector for performing a motion-compensation operation with respect to a predetermined image block. The motion vector is obtained by motion-estimation between adjacent image frames. When one image frame is composed of i x j image blocks, the number of motion vectors per frame generated by motion estimation is i x j. An encoder uses such a motion vector for motion-compensation with respect to the image blocks, and then transmits the motion vector to a decoder for decoding the encoded image data. The encoder encodes the motion vector before transmitting it to the decoder, in order to reduce the amount of the transmission data for the motion vector.

The method for encoding the motion vector obtains a differential value between the motion vectors corresponding to two sequentially generated motion vectors, that is, two respectively adjacent macroblocks, and then allocates a variable-length code to the differential value. To variable-length-encode the differential motion vector value, which is the differential value between the motion vector values, a differential motion code table, which is used in "ISO/IEC 11172-2", is shown in FIG. 1.

FIG. 1 shows variable-length codes when a differential motion vector value ranges from -16 to 16. As a whole, since magnitudes of the motion vector values between the adjacent macroblocks are similar to each other, the differential value is close to zero. Thus, the frequency with which the differential value between the motion vector values is close to zero becomes high, while the frequency with which the differential value between the motion vector values is large becomes low. The table of FIG. 1, which is based on such statistical characteristics shows that a relatively short code is assigned to a differential value close to zero, which has a high frequency of occurrence, and a relatively long code is assigned to a differential value having a low frequency.

FIGS. 2A through 2C show other conventional differential motion code tables, respectively, which are different from the table of FIG. 1, and which have been used for variable-length-encoding the differential motion vector value. The differential motion code tables of FIGS. 2A through 2C are based on the FIG. 1 differential motion code table according to a table makeup method presented in "ISO/IEC 11172-2", and the differential motion vector values generated in the image frame have ranges different from that of the table of FIG. 1.

FIG. 2A shows a differential motion code table for a case where the differential motion vector values, obtained from the motion vector values generated in the image frame, range from -29 to 29. In the table shown in FIG. 2A, in the case of the "differential values" listed on the left-hand side of the column, the variable-length codes are identical to those of the differential motion code table of FIG. 1. For the "differential values" listed on the right-hand side of the column, a modulus of "32" is added thereto or subtracted therefrom, and the variable-length codes listed on the left-hand side of the column corresponding to the value obtained by addition or subtraction, are assigned as variable-length codes corresponding to the differential motion vector value. For example, the differential motion vector value of "29 " is assigned a variable-length code corresponding to "-3" which is obtained by subtracting a modulus of "32" from "29". The differential motion vector value of "-29 " is assigned a variable-length code corresponding to which is obtained by adding a modulus of "32" to "-29". If the differential motion vector values are variable-length-encoded by using the variable-length code assigned in this way, the variable-length-encoded vector values can be decoded by using the modulus information for performing addition or subtraction, to reproduce the differential motion vector value corresponding to the variable-length code.

FIG. 2B shows a differential motion code table for a case where the differential motion vector values, obtained from the motion vector values generated in the image frame, range from -48 to 48. A process for generating the table shown in FIG. 2B is described below for which a parameter (f) for selecting a motion vector range, is three and for the case in which the motion vector value ranges from "-48" to "45". First, a modulus of "94", which is determined by the range of the motion vector values is added to or subtracted from the differential motion vector value, in order to generate the differential motion vector values within a range of "-48" and "45" which is the motion vector value range. If these values are reduced differential motion vector values (mvd), then a value of "{mvd+sign(mvd)(f-I)}" is calculated with respect to the parameter (f) and the respectively reduced differential motion vector (mvd), and the calculation result is divided by the parameter (f). The quotient, having a sign obtained by the division operation, corresponds to the variable-length code which is the same as the differential motion vector value in the table of FIG. 1. The variable-length code is concatenated with a predetermined code so as to correspond to an absolute value of the residue to form a single perfect codeword. The table shown in FIG. 2B is generated in this manner, and has a residual code for discriminating between six differential motion vector values corresponding to the same variable-length code. The differential motion vector values which are not discriminated by the residual code are discriminated by the addition or subtraction of the modulus. If the differential motion vector value is variable-length-encoded by using the coding table, a codeword generated by the variable-length-encoding operation is composed of a variable-length code corresponding to the differential motion vector value and a residual code concatenated to the variable-length code. The residual code is placed in the same column as that of the differential motion vector value. For example, when the differential motion vector value is "7", the variable-length code codeword is "0001 00" which is obtained by concatenating a code "0001 0" corresponding to the differential motion vector value "7" with a residual code "0" which is the residual value shown in the same column as that of the differential motion vector value. When the differential value is "59," the codeword becomes "0000 0100 00110" which is obtained by concatenating the corresponding variable-length code "0000 01 00 001" with the residual code "10" which is the residual value for the column in which "59" appears. Looking at the right three columns for the differential motion vector values, it can be seen that the differential values having relatively large absolute values, such as "90", "91", "-92"and "-93", have a very low frequency of occurrence and are assigned with relatively short variable-length codes, while the differential values having relatively small absolute values such as "46", "47", "-49" and "50"have a relatively high frequency of occurrence and are assigned with relatively long variable-length codes. Encoding of the motion vector values as described with respect to an image using such a table increases a quantity of generated bits.

FIG. 2C shows a differential motion code table for the case where the differential motion vector values obtained from the motion vector values generated in the image frame, range from -80 to 75. A process of generating the table shown in FIG. 2C is the same process as that for generating the table of FIG. 2B when the motion vector range selection parameter (f) is "5" and in the case where the motion vector value ranges from "-80" to "75". The table shown in FIG. 2C generated in this manner, has a residual code for discriminating ten differential motion vector values corresponding to the same variable-length code. The differential motion vector values which are not discriminated by the residual code are discriminated by addition or subtraction of the modulus. The differential motion vector values of the left five columns are assigned with shorter variable-length codes as the differential motion vector values, as they have a lower frequency of occurrence, while the differential motion vector values of the right five columns are assigned with longer variable-length codes with respect to the differential motion vector values having the low frequency of occurrence.

As described above, when the differential motion vector values are variable-length-encoded using conventional differential motion code tables, the differential motion vector values outside the range of the motion vector values are assigned with long variable-length codes even though the differential motion vector values occur with a high frequency. Accordingly, since the amount of data generated by the variable-length coding becomes large, the total encoding efficiency is lowered.

Therefore, to solve the above problems, it is an object of the present invention to provide a method for efficiently variable-length-encoding a differential motion vector value, by improving a method of assigning a variable-length code with respect to a differential motion vector value of the conventional differential motion code table.

It is another object of the present invention to provide an apparatus for efficiently variable-length-encoding a differential motion vector value, by improving a method of assigning a variable-length code with respect to a differential motion vector value of the conventional differential motion code table.

To accomplish the above object of the present invention, there is provided a method for variable-length-coding a motion vector value for use in motion compensation comprising the steps of:

(i) altering a differential motion code table so that a shorter variable-length code is assigned to second differential motion vector values beyond the range of the motion vector values as the magnitudes of the second differential motion vector values are smaller, while a longer variable-length code is assigned to the second differential motion vector values beyond the range of the motion vector values as the magnitudes of the second differential motion vector values are larger, among a differential motion code table made by the steps of adding a modulus determined by the range of the motion vector values, to differential motion vector values beyond a range of the motion vector values among first differential motion vector values of the motion vector values generated in an image or subtracting the former from latter, thereby producing the second differential motion vector values of which the magnitudes are altered into those of the motion vector values, and maintaining third differential motion vector values which are not departed from the range of the motion vector values as being in the case, thereby altering the range so that all first differential motion vector values are within the range of the motion vector values, calculating a quotient having a sign and an absolute value of a residue by substituting a vector range selection parameter (f) which is determined with respect to the range altered differential motion vector value (mvd) and the one image into an expression ›mvd+(sign(mvd)x(f-1)!/f, and assigning a variable-length codeword with respect to each first differential motion vector value by using a predetermined residual code in correspondence to a variable-length code in the reference difference motion code table corresponding to the quotient having the sign, and the absolute value of the residue which is concatenated to the variable-length code;

(ii) delaying a received motion vector value until a next motion vector value is applied and outputting the delayed motion vector value;

(iii) calculating a differential motion vector value between the delayed motion vector value and the next motion vector value; and

(iv) receiving the differential motion vector value of step (iii) and variable-length-coding the received differential motion vector value based on the altered differential motion code table of step (i),

whereby variable-length-coding a differential motion vector value between motion vector values using a differential motion code table which is newly made on the basis of a reference differential motion code table for variable-length-coding the differential motion vector values.

To accomplish the above other object of the present invention, there is provided an apparatus for variable-length-coding a motion vector value for use in motion compensation comprising:

delay means for delaying a received motion vector value until a next motion vector value is applied and outputting the delayed motion vector value;

subtracter means for calculating a differential motion vector value between the delayed motion vector value and the next motion vector value; and

a variable-length coder for storing an altered differential motion code table, receiving the differential motion vector value from subtracter means and variable-length-coding the differential motion vector value based on the stored altered differential motion code table, so that a shorter variable-length code is assigned to the second differential motion vector values beyond the range of the motion vector values as the magnitudes of the second differential motion vector values are smaller, while a longer variable-length code is assigned to the second differential motion vector values beyond the range of the motion vector values as the magnitudes of the second differential motion vector values are larger, among a differential motion code table made by a step of adding a modulus determined by the range of the motion vector values, to differential motion vector values beyond a range of the motion vector values among first differential motion vector values of the motion vector values generated in an image or subtracting the former from latter, thereby producing second differential motion vector values of which the magnitudes are altered into those of the motion vector values, and maintaining third differential motion vector values which are not departed from the range of the motion vector values as being in the case, thereby altering the range so that all first differential motion vector values are within the range of the motion vector values, a step of calculating a quotient having a sign and an absolute value of a residue by substituting a vector range selection parameter (f) which is determined with respect to the range altered differential motion vector value (mvd) and the one image into an expression ›mvd+sign(mvd)x(f-1)!/f, and a step of assigning a variable-length codeword with respect to each first differential motion vector value by using a predetermined residual code in correspondence to a variable-length code in the reference difference motion code table corresponding to the quotient having the sign, and the absolute value of the residue which is concatenated to the variable-length code,

whereby variable-length-coding a differential motion vector value between motion vector values using a differential motion code table which is newly made on the basis of a reference differential motion code table for variable-length-coding the differential motion vector values.

FIG. 1 shows a differential motion code table for the case where the differential motion vector values range from -16 to 16.

FIGS. 2A through 2C show conventional differential motion code tables generated based on the differential motion code table of FIG. 1, respectively.

FIGS. 3A through 3C show differential motion code tables according to embodiments of the present invention, respectively.

FIG. 4 is a block diagram of a motion vector encoder having an altered differential motion code table according to the present invention.

Preferred embodiments of the present invention are described below in more detail with reference to the accompanying FIGS. 3A through 3C and 4.

FIGS. 3A through 3C respectively show differential motion code tables according to preferred embodiments of the present invention. These tables are obtained by modifying the tables of FIGS. 2A through 2C, respectively. In the case of the differential motion vector values belonging to the same range as that of the motion vector values in a single frame, the same variable-length codes and/or the same residual codes as those of the corresponding tables shown in FIGS. 2A through, 2C are assigned thereto. On the other hand, in the case of the differential motion vector values which are outside the range of the motion vector values in a single frame, the variable-length code and the residual code are assigned thereto on the basis of the following method.

First, in the case of a differential motion vector value outside the range of the motion vector values, a shorter variable-length code is assigned when the magnitude of the absolute value of the differential motion vector is smaller, while a longer variable-length code is assigned when the magnitude of the absolute value of the differential motion vector is larger. More specifically, in the case of the largest positive differential motion vector value among all the differential motion vector values, the variable-length code and the residual code that is within the range of the motion vector value and corresponding to the largest negative differential motion vector value is assigned thereto. Then, in the case of the second largest positive differential motion vector value, the variable-length code and the residual code within the range of the motion vector values and which corresponds to the second largest negative differential motion vector value, is assigned thereto. In this manner the respective corresponding variable-length codes and residual codes are assigned to all the positive differential motion vector values outside the range of the motion vector values.

In the case of the negative differential motion vector values which are outside the range of the motion vector values, the variable-length code and the residual code within the range of the motion vector values and which corresponds to the largest positive differential motion vector value is assigned to the largest negative differential motion vector value. Similarly, variable-length code and the residual code within the range of the motion vector values and which corresponds to the second largest positive differential motion vector value, is assigned to the second largest negative differential motion vector value. In this manner, the respective corresponding variable-length codes and residual codes are assigned to all the negative differential motion vector values which are outside the range of the motion vector values.

In the differential motion code table of FIG. 3A, generated based on the above method, the differential values "-16" through "15" which are listed on the left-hand side of the "differential values" column and which are within the range of the motion vector values, have the same relationship between the differential motion vector values and the variable-length codes as those of FIG. 2A. However, the differential values "16 " through "29" and "-17" through "-29" which are listed on the right-hand side of the "differential values" column and are outside the range of the motion vector values, are assigned with the variable-length codes and residual codes according to the above-described method, which is different from that of FIG. 2A. That is, the differential values listed on the right-hand side of the "differential values" column are assigned with relatively long variable-length codes, since the magnitude of the absolute value thereof is larger than that of the values listed on the left-side of the column. In such a coding table, a shorter variable-length code is assigned to the differential motion vector value having a high frequency of occurrence, while a longer variable-length code is assigned to the differential motion vector value having a low frequency of occurrence. Accordingly, the total amount of data transmitted from the image signal encoder to the image signal decoder can be reduced.

In the table shown in FIG. 3B, the differential motion vector values within the range of "-48" to "45" which is the range of the motion vector values, are assigned with variable-length codes and residual codes in the same manner as that of FIG. 2B. On the other hand, in case of differential motion vector values listed in the three right-hand columns, a relatively short variable-length code is assigned to a smaller differential motion vector value having a high frequency of occurrence, while a relatively large variable-length code is assigned to a relatively larger differential motion vector value having a low frequency of occurrence.

In the table shown in FIG. 3C, similarly to FIGS. 3A and 3B, the differential motion vector values within the range of "-80" to "75", which is the range of the motion vector values and which corresponds to the five right-hand columns, are assigned with the same variable-length codes and residual codes as those of FIG. 2C. In the other differential motion vector values, a longer variable-length code is assigned to a differential motion vector value having a larger absolute value, while a shorter variable-length code is assigned to a differential motion vector value having a smaller absolute value.

FIG. 4 shows a motion vector encoder having an altered differential motion code table according to the present invention. The encoder shown in FIG. 4 performs an encoding operation with respect to the motion vector values generated with respect to a single image or frame. The motion vector values are used for motion estimation and motion compensation between a adjacent images. However, since generation of the motion vector values is known to one having ordinary skill in the art, the detailed descriptions will be omitted.

The construction and the operation of the apparatus as shown in FIG. 4 is described below. A delay 1 delays an input motion vector value and outputs the delayed motion vector value. An interval of time for delaying the motion vector value extends until a next motion vector value is input to the apparatus shown in FIG. 4. A subtracter 2 calculates a difference value between the delayed motion vector value and the next motion vector input to the apparatus of FIG. 4, and outputs the calculated result. A variable-length coder 3 stores one of the differential motion code tables shown in FIGS. 3A through 3C and variable-length-encodes the differential motion vector values input from subtracter 2 to generate a codeword. The differential motion code table stored in variable-length coder 3 can be established in advance according to the features of the images, or can be selected according to particular information relating to the motion vector values generated in the image frame. The codeword generated by variable-length coder 3 is transmitted to a decoder together with parity information indicating if a modulus is added to or subtracted from the differential motion vector value. Besides the parity information, motion vector range selection information (f) with respect to the image frame can also be inserted, when various differential motion code tables are used. Thus, a decoder detects a variable-length code and a residual code from the received codeword, and determines an original differential motion vector value among two differential motion vector values corresponding to the identical variable-length codes using the parity information and addition or subtraction of the modulus.

As described above, the variable-length encoding method and apparatus of the differential motion vector values using an improved differential motion code table according to the present invention can use standards of coding the motion vector values set forth in "ISO/IEC 11172-2" without any modification. That is, since the differential motion vector values are encoded in the same manner as that of the conventional art, by simply using a newly assigned table from a relationship of the differential motion vector value to the variable-length code and residual code in the differential motion code table, the motion vector values can be more efficiently encoded than that of using the existing table, without modifying the existing hardware structure.

While only certain embodiments of the invention have been specifically described herein, it will apparent that numerous modifications may be made thereto without departing from the spirit and scope of the invention.