Lossless Video Data Compression

Consider the following contiguous stream of luminance bytes taken from a bitmap graphic:
00101011
00101011
00101011
00101011
00101011
00101011
00101100
00101100
00101100
00101100
00101100

There must be a more efficient way of coding this! ‘Six lots of 00101011 followed by five lots of 00101100’ springs to mind. Like this:
00000110
00101011
00000101
00101100

This is the essence of a compression technique known as run-length encoding (RLE). RLE works really well, but it has a problem; if a data file is comprised of data that is predominantly non-repetitive data, RLE actually makes the file bigger! RLE must therefore be made adaptive so that it is only applied to strings of similar data (where redundancy is high), and when the coder detects continuously changing data (where entropy is high) it simply reverts back to sending the bytes in an uncompressed form. Evidently it also has to insert a small information overhead to instruct the decoder when it is (and isn’t) applying the compression algorithm.

Another lossless compression technique is known as Huffman coding, and is suitable for use with signals in which sample values appear with a known statistical frequency. The analogy with Morse code is often drawn, where letters that appear frequently are allocated simple patterns and letters that appear rarely are allocated more complex patterns. A similar technique, known by the splendid name of the Lempel-Ziv-Welch (LZW) algorithm, is based on the coding of repeated data chains or patterns. A bit like Huffman’s coding, LZW sets up a table of common patterns and codespecific instances of patterns in terms of ‘pointers’ that refer to much longer sequences in the table. The algorithm doesn’t use a pre-defined set of patterns, but instead builds up a table of patterns which it ‘sees’ from the incoming data. (The GIF image-file format employs this type of compression.)

LZW is an effective technique – even better than RLE. But for the really high compression ratios made necessary by the transmission and storage of television pictures down low bandwidth links, different approaches are required. These are described below.

QuestTel shall have no liability for any error or damage of any kind resulting from the use of this document.

Related Products