Implementations of the claimed invention generally may relate to schemes for encoding image information and, more particularly, to schemes for entropy encoding of image information.
Image entropy encoding, also known as “variable length coding,” may compress the data for chunks of an image into a stream of bits using various techniques (e.g., Huffman coding, pre-calculated Huffman-based coding (e.g., transform coefficients, motion vector difference, etc,), exponential Golomb coding, arithmetic coding, context-based arithmetic coding, etc.) to produce the fewest number of bits per chunk. As used herein, a “chunk” of image data may be understood to denote a portion of an image. In some implementations, and for ease of explanation herein, a chunk of an image may be a block (e.g., 4×4 pixels, 4×8 pixels, 8×8 pixels, etc.) of data according to any of a number of image and/or video compression standards (e.g., JPEG, MPEG-1, MPEG-2, MPEG-4, Advanced Video Coding (AVC) (e.g., MPEG-4, part 10 and ITU-T Recommendation H.264), Windows Media Video 9 (WMV-9), SMPTE's VC-1, etc.). In some implementations, a chunk of an image may be a fraction of a block of image data (e.g., ½, ¼, etc.) or a number of blocks of image data (e.g., 2 blocks, 4, blocks, a macroblock, etc.).
As one illustrative example, in H.264-encoded video, the block data may include multiple quantized coefficient levels, a quantization level, block type, and motion vectors. One technique for reducing the bits in encoded chunks or blocks may be to encode data dependently with regard to data in a preceding chunk or block when the data is similar in value. For example if the quantization level is the same value for n blocks, multiple bits may be used for the quantization value for the first block and a single bit that indicates no change may be used for the following blocks.
The data input to entropy coding may typically be represented in multiples of 8 bits, usually 8, 16, or 32 bit values, while the output may typically be a single stream of bits with sequences of bits whose lengths are dependent upon their value. Large values may be represented by relatively many bits while small values require may be represented by relatively few bits.
FIGS. 1A and 1B conceptually illustrate entropy encoding of eight blocks of image data as performed by a single processor. In FIG. 1A, the resulting intermediate results 110-0 through 110-7 (collectively “intermediate results 110”) are illustrated for the eight blocks 0 through 7. For each block that is entropy encoded, the processor may determine an appropriate quantization level (e.g., Q=26, 27, etc. out of a 0 to 51 quantization range for H.264). At that quantization level, the processor may also determine, in accordance with the particular entropy encoding scheme, the number of coefficients needed to represent a particular block (e.g., 4 coefficients for block 0; 1 coefficient for block 1; 0 coefficients for block 2, etc.).
It should be noted that the per-block data 110-0 through 110-7 shown in FIG. 1A is temporary, and may be immediately transformed to a stream of bits 120 while a particular block is processed. Intermediate result 110-0, for example, may be overwritten by the processor when the next block is processed to generate intermediate result 110-1. Hence, the results 110 shown in FIG. 1A have a temporal aspect to them, because not all results 110 may be present at the same time.
FIG. 1B illustrates a data stream 120 that the processor constructs from intermediate results 110. The “Skip” value may indicate the number of previous blocks that have no coefficients, and the differential quantization (dQ) value may indicate the change in quantization value from that of the previous block. For the first block, however, dQ may be its quantization value Q. The c0, c1, etc. values may represent the coefficient values for a given block. The processor 120 may generate stream 120 as it generates intermediate results 110, subject to any data dependencies. For example, the processor may not add the data for block 4 to stream 120 until after generating intermediate results 110 for blocks 2, 3, and 4.
Where other encoding steps (e.g., motion estimation) have been optimized, however, such serial entropy encoding by a single processor may consume an unacceptably large amount of the total encoding time.
USPTO Backgrounds
USPTO Backgrounds