Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2001-12-12
2004-01-13
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
C341S051000, C341S067000, C341S063000
Reexamination Certificate
active
06677868
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data compression and, more particularly, to improved entropy coding of compressed data streams.
Digital video comprises individual images or frames that are displayed in rapid succession. Digital images are typically represented as an array of data expressing the intensities of a plurality of picture elements or pixels. Each pixel is a sample of the intensity of the image at a set of coordinates defined by a rectangular grid virtually overlaying the image. The analog signal obtained by sampling the image at the spatial coordinates of a pixel is quantized to a discrete value that is proportional to the amplitude of the intensity or luminosity of the sample. Typically, the data for a pixel comprises a value representing the intensities of a plurality of component or primary colors of the sample. The image can be reconstructed for viewing by “inverting” the quantized discrete sample values to produce a plurality of colored dots mapped to coordinates corresponding to the pixel locations in the original image.
While representing an image as an array of discrete pixel values is useful for image processing, the quantity of raw data required to represent an image is formidable. For example, a VHS based video display comprises a 320×480 rectangular array of pixels and a high definition television (HDTV) image comprises a 1360×1024 pixel array. If each color image pixel is represented by three bytes (8 bit color), approximately one-half megabyte (MB) is required to represent a single VHS based image and approximately four MBs is required for an HDTV image. A full length movie at VHS resolution would require approximately 100 gigabytes (GB) of data, far in excess of the seventeen GBs maximum capacity of a digital video disk (DVD). If digital image data were not compressed before storage or transmission, such large quantities of data would make digital video impractical for most applications.
Video compression standards and related compression techniques have been developed to reduce the quantities of data necessary for digital video to levels that make storage and transmission practical. These standards include the MPEG family of standards promulgated by Motion Picture Experts Group standards (e.g., (MPEG-2—video) ISO-13818-2, GENERIC CODING OF MOVING PICTURES AND ASSOCIATED AUDIO, International Standards Organization) and the H.26X family of standards developed or under development by the International Telecommunications Union (ITU) (e.g., ITU-T RECOMMENDATION 263, VERSION 2, Telecommunications Standardization Sector, International Telecommunications Union). Typically, the digital video compression techniques exploit similarities between pixels within an image, referred to as spatial or intraframe correlation, and similarities between successive video frames, referred to as temporal or interframe correlation, to compress the raw data describing the pixels of a video sequence.
A digital video compression system comprises an encoder for compressing the raw video data and a decoder (collectively, a codec) to reverse the encoding process and reconstruct the images in the video frames for display. Referring to
FIG. 1
, a digital video encoder
20
typically comprises some form of differential pulse code modulation (DPCM) encoder
22
(indicated by a bracket) that converts the data representing the pixels of a sequence of video frames
24
to a syntactical bitstream
23
of quantized transform coefficients
26
representing intracoded frames and differential frame content of intercoded frames, motion vectors
28
describing the displacement of content in interframe coded frames, and mode data
30
or instructions to the decoder concerning the nature of the data included in the bitstream
23
.
The output
23
of the DPCM encoder
22
is typically input to an entropy encoder
32
that applies one or more lossless compression processes to further compress the bitstream before it is stored or transmitted to a decoder
34
. The objective of entropy encoding is to reduce the symbols of the bit stream to only the minimum required to convey the information content of the bit stream. The entropy of a symbol in a source is a function of the probability of the symbol:
E
i
=−log
2
p
i
where:
E
i
=the entropy of the symbol i
p
i
=the probability that the symbol i will occur in the source
Entropy coding comprises modeling a bitstream to determine the probabilities of each possible symbol value and substitution of a codeword for a bit stream symbol according to the probability of the symbol in the model. The effectiveness of entropy coding in further compressing the bitstream is intimately connected to the probabilistic similarity between the bitstream output by the DPCM coder
22
, which varies for each video sequence, and the model bitstream utilized in the design of the entropy code. Entropy coding includes processes such as run length coding where sequences or runs of repeating symbols are replaced by a number indicating the number of repetitions in the run, variable length coding, and arithmetic coding.
One of the most common entropy coding techniques for video coding purposes is variable length coding. In variable length coding, compression is achieved by assigning shorter codewords (i.e., short sequences of bits) to bit stream symbols with higher probabilities of occurrence and longer codewords to symbols with lesser probabilities. The codewords and associated symbols are typically organized in a look up table or code book for use by the decoder. If the average codeword length is less than the average symbol length, the bitstream will have been compressed. The simplest form of variable length coding utilizes a static code in which a single code is used to code the symbols of a particular bitstream syntax. While static variable length codes have the advantage of simplicity and may be implemented with custom circuitry for rapid coding and decoding, the effectiveness of a static code suffers when the probability distribution of symbols in the bitstream being coded differs from the probability distribution in the model bitstream on which the design of the code is based. Adaptive variable length coding models the code to the probability statistics of the specific bitstream being compressed and provides good compression performance over a range of source data, but is more complex than static variable length coding since both the encoder and the decoder must track the changes in the variable length code as it adapts to changing bitstream probabilities. However, the efficiency of variable length coding, either static or adaptive, in compressing a bitstream is limited by the nature of the coding process. The optimal length of a variable length codeword equals the entropy of the coded symbol. If a symbol has a probability exceeding 0.5, the optimal length of the codeword is less than one bit. However, variable length codewords must include an integral number of bits. Since a high probability symbol will be inefficiently coded by variable length coding, a bit stream that includes the symbol will be either inefficiently compressed or even expanded.
Arithmetic coding provides an alternative to variable length coding. With this method it is possible to exactly represent the probabilities for symbols in the model bitstream with the result that performance does not suffer when the bitstream includes a frequently occurring symbol. An arithmetic coder is capable of achieving near optimal compression regardless of the probabilities of the symbols, but the performance of a static arithmetic coder still suffers when the bitstream statistics vary from those of the model bitstream on which the coder is based. An adaptive arithmetic coder can adapt the code to the statistics for the bitstream being coded, but this requires modeling several bit streams and updating the encoder and decoder as the arithmetic coder adapts to the changing statistics. However, arithmetic coders are more complex than variable length coders and ha
Kerofsky Louis J.
Sun Shijun
Chernoff Vilhauer McClung & Stenzel LLP
Mai Lam T.
Sharp Laboratories of America Inc.
Tokar Michael
LandOfFree
Entropy coding with adaptive syntax to replace high... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Entropy coding with adaptive syntax to replace high..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy coding with adaptive syntax to replace high... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198793