RSS
Twitter
Facebook
The hybrid compression techniques
often used on audio and video data in multimedia systems are themselves
composed of several different techniques. For example,
Run-Length Coding
Data often contains sequences of
identical bytes. By replacing these repeated byte sequences with the number of
occurrences, a substantial reduction of data can be achieved. This is known as
run-length coding. A special marker M is needed in the data that does
not occur as part of the data stream itself. This M-byte can also be
realized if all 256 possible
bytes can occur in the data stream by using byte stuffing. To illustrate
this, we define the exclamation mark to be the M-byte. A single occurrence of
an excla-mation mark is interpreted as the M-byte during decompression. Two
consecutive exclamation marks are interpreted as an exclamation mark occurring
within the data.
The M-byte can thus be used to
mark the beginning of a run-length coding. The technique can be
described precisely as follows: if a byte occurs at least four times in a row,
then the number of occurrences is counted. The compressed data contain the
byte, followed by the M-byte and the number of occurrences of the byte.
Remembering that we are compressing at least four consecutive bytes, the number
of occurrences can be offset by –4. This allows the compression of between four
and 258 bytes into only three bytes. (Depending on the algorithm, one or more
bytes can be used to indicate the length; the same convention must be used
during coding and decoding.)
In the following example, the
character C occurs eight times in a row and is compressed to the three
characters C!4:
Uncompressed data: ABCCCCCCCCDEFGGG
Run-length coded: ABC!4DEFGGG
Zero Suppression
Run-length coding is a
generalization of zero suppression, which assumes that just one symbol
appears particularly often in sequences. The blank (space) character in text is
such a symbol; single blanks or pairs of blanks are ignored. Starting with sequences
of three bytes, they are replaced by an M-byte and a byte specifying the number
of blanks in the sequence. The number of occurrences can again be offset (by –3).
Sequences of between three and 257 bytes can thus be reduced to two bytes.
Further variations are tabulators used to replace a specific number of null
bytes and the definition of different M-bytes to specify different numbers of
null bytes. For example, an M5-byte could replace 16 null bytes, while an
M4-byte could replace 8 null bytes. An M5-byte followed by an M4-byte would
then represent 24 null bytes.
Vector
Quantization
In the case of vector
quantization, a data stream is divided into blocks of n bytes each (n>1).
A predefined table contains a set of patterns. For each block, the table is consulted
to find the most similar pattern (according to a fixed criterion). Each pattern
in the table is associated with an index. Thus, each block can be assigned an
index. Such a table can also be multidimensional, in which case the index will
be a vector. The corresponding decoder has the same table and uses the vector
to generate an approxi-mation of the original data stream. For further details
see [Gra84] for example.
Pattern
Substitution
A technique that can be used for
text compression substitutes single bytes for patterns that occur frequently.
This pattern substitution can be used to code, for example, the terminal
symbols of high-level languages (begin, end, if). By using an M-byte, a larger
number of words can be encoded–the M-byte indicates that the next byte is an index
representing one of 256 words. The same technique can be applied to still images,
video, and audio. In these media, it is not easy to identify small sets of frequently
occur-ring patterns. It is thus better to perform an approximation that looks for
the most simi-lar (instead of the same) pattern. This is the above described
vector quantization.
0 comments