62 Digital CCTV
1. Vector quantization is a lossy compression that looks at an
array of data and generalizes what it sees. Redundant data is
compressed, preserving enough information to recreate the
original intent.
2. Fractal compression, also a lossy compression, detects similari-
ties within sections of an image and uses a fractal algorithm to
generate the sections. Fractals and vector quantization require
signiﬁ cant computing resources for compression but are quick
at decompression.
3. DCT samples an image, analyzes the frequency components,
and discards those that do not affect the image. Like DCT,
discrete wavelet transform (DWT) mathematically transforms
an image into frequency components. DCT is the basis of stan-
dards such as JPEG, MPEG, H.261, and H.263.
4. Wavelet mathematically transforms an entire image into fre-
quency components that work on smaller pieces of data, result-
ing in a hierarchical representation of an image, where each
layer represents a frequency band.
COMPRESSION SCHEMES
The principle behind compression is a simple one—convert data
(using a recipe or algorithm) into a format requiring fewer bits
than the original for transmission and storage. The data must be
able to be returned to a good approximation of its original state.
There are many popular general-purpose lossless compression
techniques that can be applied to any type of data. We will examine
a few here. Please do not expect to fully understand the intricacies
of these techniques from the very brief explanations and examples;
rather take from them the concept of various types of coding
methods. In the future, when you see these or other terms relating
to compression formats, you will understand the theories if not
the speciﬁ c complexities.
Run-length Encoding Run-length encoding (RLE) is a simple
form of data compression where strings of data occur consecu-
Compression—The Simple Version 63
tively and are stored as single data values rather than as the
original string. This compression technique works by replacing
consecutive incidences of a character with the character coming
rst and followed by the number of times the character is repeated
consecutively. For example, the string 2222211111000000 is repre-
sented by 251506. The character or symbol 2 is followed by a 5
indicating the 2 appears 5 times, the 1 is followed by 5 for the 5
times it appears, and the 0 is followed by 6 for 6 times.
Clearly this compression technique is most useful where
symbols appear in long runs. RLE replaces consecutive occur-
rences of a symbol with the symbol, followed by the number of
times it is repeated. This system uses the idea that when a very
long string of identical symbols appear, one can replace this long
string by saying X appears 10 times. Stated another way, it replaces
multiple occurrences of one value by one occurrence and the
number of repetitions.
RLE takes advantage of the fact that data streams contain
long strings of ones and long strings of zeros. RLE compresses the
data by sending a pre-arranged code for string of ones or string of
zeros followed by a number for the length of the string. The space
indicated by the arrow in the following string of code represents
the amount of compression achieved:
Original: 0001 0000 1111 1111 1111 1111 1111 1111 1111 1111
1111 1111 0001 0000 0001
Compressed: 0 × 3, 1, 0 × 4, 1 × 40, 0 × 3, 1, 0 × 7, 1
This compression technique is most useful where symbols appear
in long runs. RLE would not be as efﬁ cient if the symbols were
not repetitious as in the following example, which shows the
coded version as longer than the original version.
Original: 0 11 0 0 01 1 111 1 0 0 00 101 00
Compressed: 0, 1 × 2, 0, 0, 01, 1, 1 × 3, 1, 0, 0, 0 × 2, 101, 0 × 2
Relative Encoding Relative encoding is a transmission tech-
nique that improves efﬁ ciency by transmitting the difference
< >
<>

Get Digital CCTV now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.