Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2002-02-15
2003-04-22
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C345S065000
Reexamination Certificate
active
06552674
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is variable length coding and particularly determination of the variable length coding code configuration used in video data compression.
BACKGROUND OF THE INVENTION
Variable length coding is a statistical coding technique that assigns symbols to codewords based on the occurrence frequency of the symbols. Symbols that occur more frequently are assigned short codewords while those that occur less frequently are assigned long codewords. Compression is achieved by the fact that overall the more frequent shorter codewords dominate. The variable length code (VLC) tables in video compression standards such as MPEG 1/2/4 and H.263 are fixed and optimized for a limited range of bit-rates. These fixed coding tables cannot handle a variety of applications. For example, in MPEG-2, the VLC tables for discrete cosine transform (DCT) coefficients are designed for broadcast quality video applications. These VLC tables cannot readily handle low bit-rate applications. Therefore, it is desirable to have a type of configurable VLC that can handle a wide range of applications and coding conditions. The universal variable length code (UVLC) proposed in Yuji Itoh, “Bi-directional motion vector coding using universal VLC,”
Signal Processing: Image Communication,
Vol. 14, pp. 541-557, May 1999 is a new scheme to encode syntax elements and offers such an advantage. The UVLC tables are constructed by a dozen of coarse codes and construction rules. The UVLC can handle a wide range of applications and different syntax elements by changing the construction rules.
Although the UVLC can be configured to handle a variety of applications and coding conditions, the issue of how to configure the UVLC has not been well explored. In the prior art, the UVLC tables were designed empirically. This technique relies heavily on the expertise of the coder and typically requires many trials. Even with a great effort the resulting tables may not be optimum. Current methods to automatically re-configure the UVLC use the probability of each symbol to construct a mapping table that re-orders the assignments of symbols to codewords. This is suitable for coding syntax elements which have only a few different symbols, such as the macroblock type in H.26L video standard which has only 9 different symbols. This is not practical for syntax elements like transform coefficients or motion vectors, which consist of a lot of symbols. Since the transform coefficients and motion vectors make up a significant portion of the total encoded bits, it is foremost important to have a method capable of automatically configuring the UVLC for these syntax elements in different types of applications.
SUMMARY OF THE INVENTION
This invention is a method to automatically configure the universal variable length coding (UVLC). The method is applicable to code the syntax elements with a lot of symbols like the transform coefficients and motion vectors. The configuration problem includes a configuration method based on a genetic algorithm (GA). The method can be applied to on-the-fly configuration of codewords during video encoding, or to off-line training of code tables. This invention also includes several techniques to reduce the required operations for applications which have only limited processing power.
This invention selects variable length codes for encoding a plurality of symbols in a data stream, such as a series of video frames. The method determines a mapping of symbols to variable length codes as a bitstring. The method selects an initial population of a predetermined number of the bitstrings. The method calculates for each bitstring of a current population of bitstrings a number of bits needed for encoding the data stream from the mapping of symbols to variable length codes and the frequency of occurrence of each symbol. The method applies a termination condition to the current population of bitstrings.
If the current population of bitstrings passes the termination condition, the method selects the variable length codes corresponding to the bitstring having the least number of bits needed for encoding the data stream.
If the current population of bitstrings fails the termination condition, the method repeats the following steps. The method forms a next current population of bitstrings from the prior current population of bit strings by genetic manipulation of bitstrings of the current population. The method calculates the number of bits needed for encoding the data stream. The method applies the termination condition to the current population of bitstrings. These steps repeat until the termination condition is satisfied.
There are several alternative terminations conditions. The first termination condition is a predetermined number of repeats. The second termination condition is whether the number of bits for encoding the data stream of the current population of bitstrings differs by less than a predetermined amount from the immediately prior population of bitstrings. The third termination conditions is whether number of bits needed for encoding the data stream of one bitstring is less than a predetermined amount.
This method can be used for each frame of a video stream of a plurality of frames of more than one type. If there has been a prior selection of variable length codes for a frame of the type of the current frame that is sufficiently similar to the prior frame, the variable length encoding of the prior frame is used. This comparison may be by a chi-square test.
The chi-square test may employ only the most significant symbols of the video data stream for the comparison.
REFERENCES:
patent: 6501801 (2002-12-01), Chujoh et al.
Cheung Ngai-Man
Itoh Yuji
Brady III W. James
Jean-Pierre Peguy
Lauture Joseph J
Marshall Robert D.
Telecky , Jr. Frederick J.
LandOfFree
Automatic configuration of universal variable length code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic configuration of universal variable length code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic configuration of universal variable length code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111451