Context-adaptive binary arithmetic coding (CABAC) is a form of
entropy encoding
In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...
used in the
H.264/MPEG-4 AVC and
High Efficiency Video Coding
High Efficiency Video Coding (HEVC), also known as H.265 and MPEG-H Part 2, is a video compression standard designed as part of the MPEG-H project as a successor to the widely used Advanced Video Coding (AVC, H.264, or MPEG-4 Part 10). In compar ...
(HEVC) standards. It is a
lossless compression
Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
technique, although the video coding standards in which it is used are typically for
lossy compression
In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size ...
applications. CABAC is notable for providing much better
compression
Compression may refer to:
Physical science
*Compression (physics), size reduction due to forces
*Compression member, a structural element such as a column
*Compressibility, susceptibility to compression
* Gas compression
*Compression ratio, of a ...
than most other entropy encoding algorithms used in video encoding, and it is one of the key elements that provides the H.264/AVC encoding scheme with better compression capability than its predecessors.
In
H.264/MPEG-4 AVC, CABAC is only supported in the Main and higher
profiles (but not the extended profile) of the standard, as it requires a larger amount of processing to decode than the simpler scheme known as
context-adaptive variable-length coding
Context-adaptive variable-length coding (CAVLC) is a form of entropy coding used in H.264/MPEG-4 AVC video encoding. It is an inherently lossless compression technique, like almost all entropy-coders. In H.264/MPEG-4 AVC, it is used to encode r ...
(CAVLC) that is used in the standard's Baseline profile. CABAC is also difficult to parallelize and vectorize, so other forms of parallelism (such as spatial region parallelism) may be coupled with its use. In HEVC, CABAC is used in all profiles of the standard.
Algorithm
CABAC is based on
arithmetic coding
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
, with a few innovations and changes to adapt it to the needs of video encoding standards:
* It encodes binary symbols, which keeps the complexity low and allows probability modelling for more frequently used bits of any symbol.
* The probability models are selected adaptively based on local context, allowing better modelling of probabilities, because coding modes are usually locally well correlated.
* It uses a multiplication-free range division by the use of
quantized probability ranges and probability states.
CABAC has multiple
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
modes for different contexts. It first converts all non-
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
symbols to binary. Then, for each bit, the coder selects which probability model to use, then uses information from nearby elements to optimize the probability estimate.
Arithmetic coding
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
is finally applied to compress the data.
![CABAC Encoder Workflow Diagram](https://upload.wikimedia.org/wikipedia/commons/1/13/CABAC_Encoder_Workflow_Diagram.png)
The context modeling provides estimates of conditional probabilities of the coding symbols. Utilizing suitable context models, a given inter-symbol redundancy can be exploited by switching between different probability models according to already-coded symbols in the neighborhood of the current symbol to encode. The context modeling is responsible for most of CABAC's roughly 10% savings in
bit rate
In telecommunications and computing, bit rate (bitrate or as a variable ''R'') is the number of bits that are conveyed or processed per unit of time.
The bit rate is expressed in the unit bit per second (symbol: bit/s), often in conjunction w ...
over the
CAVLC
Context-adaptive variable-length coding (CAVLC) is a form of entropy coding used in H.264/MPEG-4 AVC video encoding. It is an inherently lossless compression technique, like almost all entropy-coders. In H.264/MPEG-4 AVC, it is used to encode re ...
entropy coding method.
Coding a data symbol involves the following stages.
* Binarization: CABAC uses Binary Arithmetic Coding which means that only binary decisions (1 or 0) are encoded. A non-binary-valued symbol (e.g. a transform coefficient or motion vector) is "binarized" or converted into a binary code prior to arithmetic coding. This process is similar to the process of converting a data symbol into a variable length code but the binary code is further encoded (by the arithmetic coder) prior to transmission.
* Stages are repeated for each bit (or "bin") of the binarized symbol.
* Context model selection: A "context model" is a probability model for one or more bins of the binarized symbol. This model may be chosen from a selection of available models depending on the statistics of recently coded data symbols. The context model stores the probability of each bin being "1" or "0".
* Arithmetic encoding: An arithmetic coder encodes each bin according to the selected probability model. Note that there are just two sub-ranges for each bin (corresponding to "0" and "1").
* Probability update: The selected context model is updated based on the actual coded value (e.g. if the bin value was "1", the frequency count of "1"s is increased).
Example
1. Binarize the value MVDx, the motion vector difference in the direction.
The first bit of the binarized codeword is bin 1; the second bit is bin 2; and so on.
2. Choose a context model for each bin. One of 3 models is selected for bin 1, based on previous coded MVD values. The L1 norm of two previously-coded values, e
k, is calculated:
If e
k is small, then there is a high probability that the current MVD will have a small magnitude; conversely, if e
k is large then it is more likely that the current MVD will have a large magnitude. We select a probability table (context model) accordingly. The remaining bins are coded using one of 4 further context models:
3. Encode each bin. The selected context model supplies two probability estimates: the probability that the bin contains “1” and the probability that the bin contains “0”. These estimates determine the two sub-ranges that the arithmetic coder uses to encode the bin.
4. Update the context models. For example, if context model 2 was selected for bin 1 and the value of bin 1 was “0”, the frequency count of “0”s is incremented. This means that the next time this model is selected, the probability of a “0” will be slightly higher. When the total number of occurrences of a model exceeds a threshold value, the frequency counts for “0” and “1” will be scaled down, which in effect gives higher priority to recent observations.
The arithmetic decoding engine
The arithmetic decoder is described in some detail in the Standard. It has three distinct properties:
#Probability estimation is performed by a transition process between 64 separate probability states for "Least Probable Symbol" (LPS, the least probable of the two binary decisions "0" or "1").
#The range representing the current state of the arithmetic coder is quantized to a small range of pre-set values before calculating the new range at each step, making it possible to calculate the new range using a look-up table (i.e. multiplication-free).
#A simplified encoding and decoding process is defined for data symbols with a near uniform probability distribution.
The definition of the decoding process is designed to facilitate low-complexity
implementations of arithmetic encoding and decoding. Overall, CABAC provides
improved coding efficiency compared with CAVLC-based coding, at the expense of greater
computational complexity.
History
In 1986,
IBM researchers Kottappuram M. A. Mohiuddin and Jorma Johannen Rissanen filed a
patent
A patent is a type of intellectual property that gives its owner the legal right to exclude others from making, using, or selling an invention for a limited period of time in exchange for publishing an enabling disclosure of the invention."A p ...
for a multiplication-free binary arithmetic coding algorithm.
In 1988, an IBM research team including R.B. Arps, T.K. Truong, D.J. Lu, W. B. Pennebaker, L. Mitchell and G. G. Langdon presented an adaptive binary arithmetic coding (ABAC) algorithm called Q-Coder.
The above patents and research papers, along several others from IBM and
Mitsubishi Electric
, established on 15 January 1921, is a Japanese multinational electronics and electrical equipment manufacturing company headquartered in Tokyo, Japan. It is one of the core companies of Mitsubishi. The products from MELCO include elevators an ...
, were later cited by the
CCITT
The ITU Telecommunication Standardization Sector (ITU-T) is one of the three sectors (divisions or units) of the International Telecommunication Union (ITU). It is responsible for coordinating standards for telecommunications and Information Commu ...
and
Joint Photographic Experts Group
The Joint Photographic Experts Group (JPEG) is the joint committee between ISO/IEC JTC 1/SC 29 and ITU-T Study Group 16 that created and maintains the JPEG, JPEG 2000, JPEG XR, JPEG XT, JPEG XS, JPEG XL, and related digital image standards. It ...
as the basis for the
JPEG
JPEG ( ) is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography. The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and imag ...
image compression
Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior r ...
format's adaptive binary arithmetic coding algorithm in 1992.
However, encoders and decoders of the JPEG file format, which has options for both
Huffman encoding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algori ...
and arithmetic coding, typically only support the Huffman encoding option, which was originally because of patent concerns, although JPEG's arithmetic coding patents have since expired due to the age of the JPEG standard.
In 1999, Youngjun Yoo (
Texas Instruments
Texas Instruments Incorporated (TI) is an American technology company headquartered in Dallas, Texas, that designs and manufactures semiconductors and various integrated circuits, which it sells to electronics designers and manufacturers globall ...
), Young Gap Kwon and Antonio Ortega (
University of Southern California
The University of Southern California (USC, SC, or Southern Cal) is a Private university, private research university in Los Angeles, California, United States. Founded in 1880 by Robert M. Widney, it is the oldest private research university in C ...
) presented a context-adaptive form of binary arithmetic coding. The modern context-adaptive binary arithmetic coding (CABAC) algorithm was commercially introduced with the
H.264/MPEG-4 AVC format in 2003.
The majority of patents for the AVC format are held by
Panasonic
formerly between 1935 and 2008 and the first incarnation of between 2008 and 2022, is a major Japanese multinational corporation, multinational Conglomerate (company), conglomerate corporation, headquartered in Kadoma, Osaka, Kadoma, Osaka P ...
,
Godo Kaisha IP Bridge and
LG Electronics
LG Electronics Inc. () is a South Korean multinational electronics company headquartered in Yeouido-dong, Seoul, South Korea. LG Electronics is a part of LG Corporation, the fourth largest '' chaebol'' in South Korea, and often considered a ...
.
See also
*
Arithmetic coding
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
*
Data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
*
Lossless compression
Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
*
Context-adaptive variable-length coding (CAVLC)
References
{{Reflist,
refs=
[Richardson, Iain E. G.]
H.264 / MPEG-4 Part 10 White Paper
17 October 2002.
[{{cite book , last = Richardson , first = Iain E. G. , title = H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia , publisher = John Wiley & Sons Ltd. , year = 2003 , location = Chichester]
[Marpe, D., Schwarz, H., and Wiegand, T.]
Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard
''IEEE Trans. Circuits and Systems for Video Technology'', Vol. 13, No. 7, pp. 620–636, July, 2003.
Lossless compression algorithms
MPEG
Video compression