Adaptive coding
Encyclopedia
Adaptive coding refers to variants of entropy encoding
methods of lossless data compression
. They are particularly suited to streaming data, as they adapt to localized changes in the characteristics of the data, and don't require a first pass over the data to calculate a probability model. The cost paid for these advantages is that the encoder and decoder must be more complex to keep their states synchronized, and more computational power is needed to keep adapting the encoder/decoder state.
Almost all data compression
methods involve the use of a model, a prediction of the composition of the data. When the data matches the prediction made by the model, the encoder can usually transmit the content of the data at a lower information cost, by making reference to the model.
This general statement is a bit misleading as general data compression algorithm would include the popular LZW
and LZ77 algorithms,
which are hardly comparable to compression techniques typically called adaptive.
Run length encoding and the typical JPEG
compression with run length encoding and predefined Huffman codes do not transmit a model.
A lot other methods adapt their model to the current file and need to transmit it in addition to the encoded data, because both the encoder and the decoder need to use the model.
In adaptive coding, the encoder and decoder are instead equipped with a predefined meta-model about how they will alter their models in response to the actual content of the data, and otherwise start with a blank slate, meaning that no initial model needs to be transmitted. As the data is transmitted, both encoder and decoder adapt their models, so that unless the character of the data changes radically, the model becomes better-adapted to the data its handling and compresses it more efficiently approaching the efficiency of the static coding.
Any adaptive coding method has a corresponding static model method, in which the data model is precalculated and then transmitted with the data.
craft to relay images from Saturn
. Only about 5% of the images show any visual signs of damage. As the spacecraft has an error correcting Flash drive
and long timeframes between image taking events, damaged images like this can be resent. It is assumed that the number of damaged, but unrecoverable images from the Cassini mission is about 0.01% or less.
Cassini Lossless Compression
Entropy encoding
In information theory an entropy encoding is a lossless data compression scheme that is independent of the specific characteristics of the medium....
methods of lossless data compression
Lossless data compression
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be reconstructed, in exchange...
. They are particularly suited to streaming data, as they adapt to localized changes in the characteristics of the data, and don't require a first pass over the data to calculate a probability model. The cost paid for these advantages is that the encoder and decoder must be more complex to keep their states synchronized, and more computational power is needed to keep adapting the encoder/decoder state.
Almost all data compression
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
methods involve the use of a model, a prediction of the composition of the data. When the data matches the prediction made by the model, the encoder can usually transmit the content of the data at a lower information cost, by making reference to the model.
This general statement is a bit misleading as general data compression algorithm would include the popular LZW
LZW
Lempel–Ziv–Welch is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978...
and LZ77 algorithms,
which are hardly comparable to compression techniques typically called adaptive.
Run length encoding and the typical JPEG
JPEG
In computing, JPEG . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality....
compression with run length encoding and predefined Huffman codes do not transmit a model.
A lot other methods adapt their model to the current file and need to transmit it in addition to the encoded data, because both the encoder and the decoder need to use the model.
In adaptive coding, the encoder and decoder are instead equipped with a predefined meta-model about how they will alter their models in response to the actual content of the data, and otherwise start with a blank slate, meaning that no initial model needs to be transmitted. As the data is transmitted, both encoder and decoder adapt their models, so that unless the character of the data changes radically, the model becomes better-adapted to the data its handling and compresses it more efficiently approaching the efficiency of the static coding.
Encoder
- Initialize the data model as per agreement.
- While there is more data to send
- Encode the next symbol using the data model and send it.
- Modify the data model based on the last symbol.
Decoder
- Initialize the data model as per agreement.
- While there is more data to receive
- Decode the next symbol using the data model and output it.
- Modify the data model based on the decoded symbol.
Any adaptive coding method has a corresponding static model method, in which the data model is precalculated and then transmitted with the data.
Encoder
- Initialize the data model based on a first pass over the data.
- Transmit the data model.
- While there is more data to send
- Encode the next symbol using the data model and send it.
Decoder
- Receive the data model.
- While there is more data to receive
- Decode the next symbol using the data model and output it.
Examples
Adaptive image coding is currently being used by the Cassini-HuygensCassini-Huygens
Cassini–Huygens is a joint NASA/ESA/ASI spacecraft mission studying the planet Saturn and its many natural satellites since 2004. Launched in 1997 after nearly two decades of gestation, it includes a Saturn orbiter and an atmospheric probe/lander for the moon Titan, although it has also returned...
craft to relay images from Saturn
Saturn
Saturn is the sixth planet from the Sun and the second largest planet in the Solar System, after Jupiter. Saturn is named after the Roman god Saturn, equated to the Greek Cronus , the Babylonian Ninurta and the Hindu Shani. Saturn's astronomical symbol represents the Roman god's sickle.Saturn,...
. Only about 5% of the images show any visual signs of damage. As the spacecraft has an error correcting Flash drive
Solid-state drive
A solid-state drive , sometimes called a solid-state disk or electronic disk, is a data storage device that uses solid-state memory to store persistent data with the intention of providing access in the same manner of a traditional block i/o hard disk drive...
and long timeframes between image taking events, damaged images like this can be resent. It is assumed that the number of damaged, but unrecoverable images from the Cassini mission is about 0.01% or less.
Cassini Lossless Compression
- Both converted (8-bit) and unconverted (12-bit) data can be losslessly compressed. The Cassini hardware data compressor uses a modified Huffman encoding scheme as part of its adaptive compressor.
- Each compressed image can be reconstructed on the ground with no loss to the information content of the image, provided the image entropy does not exceed the threshold where 2:1 compression is reached.
- Due to camera problems and the need to reduce file size, there is a slight modification to the image coding scheme so that each compressed line is effectively bandwidth limited on the number of bits available to encode it.