Automatic configuration of universal variable length code for video coding
AssigneeTexas Instruments Incorporated
InventorsNgai-Man Cheung, Yuji Itoh
Life of this patent
Estimating the term…
Abstract
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.
Claims12
A method of selecting variable length codes for encoding a plurality of symbols in a data stream comprising the steps of:
- determining a mapping of symbols to variable length codes as a bitstring;
- selecting an initial population of a predetermined number of the bitstrings;
- calculating 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;
- applying a termination condition to the current population of bitstrings;
- if the current population of bitstrings passes the termination condition, selecting the variable length codes corresponding to the bitstring having the least number of bits needed for encoding the data stream;
- and
- if the current population of bitstrings fails the termination condition
- forming a next current population of bitstrings from the prior current population of bit strings by genetic manipulation of bitstrings of the current population,
- calculating for each bitstring of the current population of bitstrings the number of bits needed for encoding the data stream,
- applying the termination condition to the current population of bitstrings, and
- repeating the steps of forming a next current population of bitstrings, calculating the number of bits needed for encoding the data stream, and applying the termination condition and until the current population of bitstrings passes the termination condition.
A method of selecting variable length codes for encoding a plurality of symbols in each frame of a video stream of a plurality of frames of more than one type, comprising the steps for each frame of:
- determining if there has been a prior selection of variable length codes for a frame of the type of the current frame;
- if there has been a prior selection of variable length codes for a frame of the type of the current frame, then
- comparing the prior frame with the current frame, and
- selecting the variable length codes selected for the prior frame for the current frame if the current frame is sufficiently similar to the prior frame;
- if there has been no prior selection of variable length codes for a frame of the type of the current frame or if there has been such a selection and the current frame is not sufficiently similar to the prior frame, then
- determining a mapping of symbols to variable length codes as a bitstring;
- selecting an initial population of a predetermined number of the bitstrings;
- calculating 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;
- applying a termination condition to the current population of bitstrings;
- if the current population of bitstrings passes the termination condition, selecting the variable length codes corresponding to the bitstring having the least number of bits needed for encoding the data stream;
- and
- if the current population of bitstrings fails the termination condition
- forming a next current population of bitstrings from the prior current population of bit strings by genetic manipulation of bitstrings of the current population,
- calculating for each bitstring of the current population of bitstrings the number of bits needed for encoding the data stream,
- applying the termination condition to the current population of bitstrings, and
- repeating the steps of forming a next current population of bitstrings, calculating the number of bits needed for encoding the data stream, and applying the termination condition and until the current population of bitstrings passes the termination condition.
Dependencies are inferred from the claim text.