Data Compression

Khalid Sayood
University of Nebraska, Lincoln

I. INTRODUCTION III. LOSSY COMPRESSION

II. LOSSLESS COMPRESSION IV. FURTHER INFORMATION

I. INTRODUCTION words to represent letters that occur more frequently,

thus lowering the average number of bits required to
Data compression involves the development of a com- represent each letter.
pact representation of information. Most representa- Compression in all its forms exploits structure, or
tions of information contain large amounts of redun- redundancy, in the data to achieve a compact repre-
dancy. Redundancy can exist in various forms. It may sentation. The design of a compression algorithm in-
exist in the form of correlation: spatially close pixels in volves understanding the types of redundancy present
an image are generally also close in value. The redun- in the data and then developing strategies for ex-
dancy might be due to context: the number of possi- ploiting these redundancies to obtain a compact rep-
bilities for a particular letter in a piece of English text resentation of the data. People have come up with
is drastically reduced if the previous letter is a q. It can many ingenious ways of characterizing and using the
be probabilistic in nature: the letter e is much more different types of redundancies present in different
likely to occur in a piece of English text than the letter kinds of technologies from the telegraph to the
q. It can be a result of how the information-bearing se- cellular phone and digital movies.
quence was generated: voiced speech has a periodic One way of classifying compression schemes is by
structure. Or, the redundancy can be a function of the the model used to characterize the redundancy. How-
user of the information: when looking at an image we ever, more popularly, compression schemes are di-
cannot see above a certain spatial frequency; therefore, vided into two main groups: lossless compression and
the high-frequency information is redundant for this lossy compression. Lossless compression preserves all
application. Redundancy is defined by the Merriam- the information in the data being compressed, and
Webster Dictionary as “the part of the message that can the reconstruction is identical to the original data. In
be eliminated without the loss of essential informa- lossy compression some of the information contained
tion.” Therefore, one aspect of data compression is re- in the original data is irretrievably lost. The loss in in-
dundancy removal. Characterization of redundancy in- formation is, in some sense, a payment for achieving
volves some form of modeling. Hence, this step in the higher levels of compression. We begin our examina-
compression process is also known as modeling. For tion of data compression schemes by first looking at
historical reasons another name applied to this process lossless compression techniques.
is decorrelation.
After the redundancy removal process the infor-
mation needs to be encoded into a binary represen- II. LOSSLESS COMPRESSION
tation. At this stage we make use of the fact that if the
information is represented using a particular alpha- Lossless compression involves finding a representation
bet some letters may occur with higher probability which will exactly represent the source. There should
than others. In the coding step we use shorter code be no loss of information, and the decompressed, or

Encyclopedia of Information Systems, Volume 1

Copyright 2003, Elsevier Science (USA). All rights reserved. 423
424 Data Compression

reconstructed, sequence should be identical to the is 2 e, or 10. The average amount of information as-
original sequence. The requirement that there be no sociated with the experiment is called the entropy H:
loss of information puts a limit on how much com- M M
1
pression we can get. We can get some idea about this H  E[i(A)]   i(Ak)P(Ak)   P(Ak) log 
P(Ak)
limit by looking at some concepts from information k1 k1

theory. M
 
k1
P(Ak) log P(Ak) (1)

A. Information and Entropy Suppose the “experiment” is the generation of a let-

ter by a source, and further suppose the source gen-
In one sense it is impossible to denote anyone as the erates each letter independently according to some
parent of data compression: people have been finding probability model. Then H as defined in Eq. (1) is
compact ways of representing information since the called the entropy of the source. Shannon showed
dawn of recorded history. One could argue that the that if we compute the entropy in bits (use logarithm
drawings on the cave walls are representations of a sig- base 2) the entropy is the smallest average number of
nificant amount of information and therefore qualify as bits needed to represent the source output.
a form of data compression. Significantly less contro- We can get an intuitive feel for this connection be-
versial would be the characterizing of the Morse code tween the entropy of a source and the average num-
as a form of data compression. Samuel Morse took ad- ber of bits needed to represent its output (denoted by
vantage of the fact that certain letters such as e and a rate) by performing a couple of experiments.
occur more frequently in the English language than q Suppose we have a source which puts out one of
or z to assign shorter code words to the more frequently four letters {A1, A2, A3, A4}. In order to ascertain the
occurring letters. This results in lower average trans- outcome of the experiment we are allowed to ask a
mission time per letter. The first person to put data predetermined sequence of questions which can be
compression on a sound theoretical footing was Claude answered with a yes or a no. Consider first the case of
E. Shannon (1948). He developed a quantitative notion a source which puts out each letter with equal proba-
of information that formed the basis of a mathematical bility, that is,
representation of the communication process.
1
Suppose we conduct a series of independent ex- P(Ak)   k  1,2,3,4
periments where each experiment has outcomes A1, 4
A2, . . ., AM. Shannon associated with each outcome a From Eq. (1) the entropy of this source is two bits. The
quantity called self information, defined as sequence of questions can be represented as a flow-
chart as shown in Fig. 1. Notice that we need to ask two
1
i(Ak)  log  questions in order to determine the output of the
P(Ak)
source. Each answer can be represented by a single bit
The units of self-information are bits, nats, or Hart- (1 for yes and 0 for no); therefore, we need two bits to
leys, depending on whether the base of the logarithm represent each output of the source. Now consider a

Figure 1 Sequence of questions for equiprobable source.

Data Compression 425

slightly different situation in which the source puts out probability will substantially decrease the compres-
the four different letters with different probabilities: sion efficiency of the procedure.
The creation of a binary representation for the
1 1 1 1
P(A1)  , P(A2)  , P(A3)  , P(A4)   source output, or the generation of a code for a source,
2 4 8 8 is the topic of the next section.
The entropy of this source is 1.75 bits.
Armed with the information about the source, we
construct a different sequence of questions shown in B. Coding
Fig. 2. Notice that when the output of the source is A1
we need ask only one question. Because P(A1)  12 on In the second example of the previous section the way
the average this will happen half the time. If the source we obtained an efficient representation was to use
output is A2 we need to ask two questions. This will fewer bits to represent letters that occurred more fre-
happen a quarter of the time. If the source output is quently—the same idea that Samuel Morse had. It is
A3 or A4 we will need to ask three questions. This too a simple idea, but in order to use it we need an algo-
will happen a quarter of the time. Thus, half the time rithm for systematically generating variable length
we can represent the output of the source with one code words for a given source. David Huffman (1951)
bit, a quarter of the time with two bits, and another created such an algorithm for a class project. We de-
quarter of the time with three bits. Therefore, on the scribe this algorithm below. Another coding algorithm
average we will need 1.75 bits to represent the output which is fast gaining popularity is the arithmetic cod-
of the source. We should note that if our information ing algorithm. We will also describe the arithmetic
about the frequency with which the letters occur is coding algorithm in this section.
wrong we will end up using more bits than if we had
used the question sequence of Fig. 1. We can easily
1. Huffman Coding
see this effect by switching the probabilities of A1 and
A2 and keeping the questioning strategy of Fig. 2. Huffman began with two rather obvious conditions
Both these examples demonstrate the link between on the code and then added a third that allowed for
average information, or entropy of the source, and the construction of the code. The conditions were:
the average number of bits, or the rate, required to
represent the output of the source. They also demon- 1. The codes corresponding to the higher
strate the need for taking into account the proba- probability letters could not be longer than the
bilistic structure of the source when creating a repre- code words associated with the lower probability
sentation. Note that incorrect estimates of the letters.

Figure 2 Sequence of questions for second source.

426 Data Compression

2. The two lowest probability letters had to have

code words of the same length.

He added a third condition to generate a practical

compression scheme.

3. The two lowest probability letters have codes that

are identical except for the last bit.

It is easy to visualize these conditions if we think of the

code words as the path through a binary tree: a zero
bit denoting a left branch and a one bit denoting a
right branch. The two lowest probability letters would
then be the two leaves of a node at the lowest level of
the tree. We can consider the parent node of these
Figure 3 Huffman code for the five letter alphabet.
leaves as a letter in a reduced alphabet which is ob-
tained as a combination of the two lowest probability
symbols. The probability of the letter corresponding to
this node would be the sum of the probabilities of the for pmax  0.5 the upper bound for the Huffman code
two individual letters. Now, we can find the two lowest is H(S)  pmax, while for pmax  0.5, the upper bound
probability symbols of the reduced alphabet and treat is H(S)  pmax  0.086. If instead of coding each let-
them as the two leaves of a common node. We can con- ter separately we group the letters into blocks con-
tinue in this fashion until we have completed the tree. taining n letters, then the rate is guaranteed to be
We can see this process best through an example. even closer to the entropy of the source. Using our
looser bound we can show that the bounds on the av-
EXAMPLE 1: HUFFMAN CODING
erage length of the code will be
Suppose we have a source alphabet with five letters
{a1,a2,a3,a4,a5} with probabilities of occurrence P(a1) 1
H  R  
 0.15, P(a2)  0.04, P(a3)  0.26, P(a4)  0.05, and n
P(a5)  0.50. We can calculate the entropy to be
However, blocking letters together means an expo-
5
nential increase in the size of the alphabet. There-
H  P(ai) log P(ai)  1.817684 bits
i1 fore, in many situations this particular approach is
not very practical.
If we sort the probabilities in descending order we can
see that the two letters with the lowest probabilities are
a2 and a4. These will become the leaves on the lowest 2. Arithmetic Coding
level of the binary tree. The parent node of these
Practical arithmetic coding came into existence in
leaves will have a probability of 0.09. If we consider the
1976 through the work of Risannen (1976) and Pasco
parent node as a letter in a reduced alphabet it will be
(1976). However, the basic ideas of arithmetic coding
one of the two letters with the lowest probability: the
have their origins in the original work of Shannon
other one being a1. Continuing in this manner we get
the binary tree shown in Fig. 3. The code is (1948). (For a brief history see Sayood, 2000). Arith-
metic coding relies on the fact that there are an un-
a1 110 countably infinite number of numbers between 0 and
a2 1111 1 (or any other nonzero interval on the real number
a3 10 line). Therefore, we can assign a unique number from
a4 1110 the unit interval to any sequence of symbols from a fi-
a5 0 nite alphabet. We can then encode the entire se-
It can be shown that, for a sequence of independent quence with this single number which acts as a label
letters, or a memoryless source, the rate of the Huff- or tag for this sequence. In other words, this number
man code will always be within one bit of the entropy. is a code for this sequence: a binary representation of
this number is a binary code for this sequence. Be-
HR1 cause this tag is unique, in theory, given the tag the
In fact we can show that (Gallagher, 1978) if pmax is decoder can reconstruct the entire sequence. In or-
the largest probability in the probability model, then der to implement this idea we need a mapping from
Data Compression 427

the sequence to the tag and an inverse mapping from letter a2, and so on. As the second letter of the se-
the tag to the sequence. quence under consideration is a1, the tag interval
One particular mapping is the cumulative density would be the first subinterval, which is [0.6,0.72).
function of the sequence. Let us view the sequence to Note that the tag interval for the two-letter sequence
be encoded as the realization of a sequence of ran- is wholly contained in the tag interval corresponding
dom variables {X1, X2, } and represent the set of all to the first letter. Furthermore, note that the size of
possible realizations which have nonzero probability the interval is p4p1  0.12. Continuing in this manner
of occurrence in lexicographic order by {Xi}. Given a for the three-letter sequence, we can compute
particular realization FX1,X2,X3(a4,a1,a2)  0.672 and FX1,X2,X3(a4,a1,a1) 
0.648. Thus, the tag interval is (0.648,0.672]. Again
Xk  xk,1,xk,2,
notice that the tag interval for the three letter se-
the cumulative distribution function FX(xk,1,xk,2, ) is quence is entirely contained within the tag interval
a number between 0 and 1. Furthermore, as we are for the two-letter sequence, and the size of the inter-
only dealing with sequences with nonzero probability, val has been reduced to p4p1p2  0.024. This pro-
this number is unique to the sequence Xk. In fact, we gression is shown in Fig. 4. If we represent the upper
can uniquely assign the half-open interval [FX(Xk1), limit of the tag interval at time n by u(n) and the lower
FX(Xk1)) to the sequence Xk. Any number in this in- limit by l(n), we can show that
terval, which we will refer to as the tag interval for Xk,
can be used as a label or tag for the sequence Xk. The l(n)  l(n1)  (u(n1)  l(n1)) FX(xn  1) (2)
arithmetic coding algorithm is essentially the calcula-
u(n)  l(n1)  (u(n1)  l(n1)) FX(xn). (3)
tion of the end points of this tag interval. Before we
describe the algorithm for computing these end Notice that as the sequence length increases, the tag
points let us look at an example for a sequence of interval is always a subset of the previous tag interval.
manageable length. However, the number of digits required to represent
Suppose we have an iid sequence with letters from the tag intervals increases as well. This was one of the
an alphabet A  {a1,a2,a3,a4}. The probability of oc- problems with the initial formulation of arithmetic
currence of the letters are given by p0  0.3, p1  0.1, coding. Another was the fact that you could not send
p2  0.2, and p4  0.4. Ordering the letters from the the code until the last element of the sequence was
smallest to the largest index, we have FX(a1)  0.3, encoded. Both these problems can be partially re-
FX(a2)  0.4, FX(a3)  0.6, and FX(a4)  1.0. We will solved by noting that if we use a binary alphabet, once
find the tag interval for the sequence a4,a1,a2,a4. We the interval is complete in either the upper or lower
begin with a sequence that consists of a single letter half of the unit interval the most significant digits of
a4. Given that FX(a4)  1.0 and FX(a3)  0.6, the tag the upper and lower limits of the tag interval are iden-
interval is [0.6,1.0). Now consider the two-letter se- tical. Furthermore, there is no possibility of the tag in-
quence a4, a1. If we impose a lexicographic ordering, terval migrating from the half of the unit interval in
which it is contained to the other half of the unit in-
FX1,X2(X1  a4, X2  a1) terval. Therefore, we can send the most significant bit
3 4 of the upper and lower intervals as the tag for the se-
   Pr[X1  ai,X2  aj]  Pr[X1  a4,X2  a1] quence. At the same time we can shift the most sig-
i1 j1 nificant bit out of the upper and lower limits, effec-
 FX(a3)  Pr[X1  a4,X2  a1] tively doubling the size of the tag interval. Thus, each
time the tag interval is trapped in either the upper or
 0.6  0.4 0.3  0.72
lower half of the unit interval, we obtain one more bit
The two-letter sequence prior to a4, a1 in the lexico- of the code and we expand the interval. This way we
graphic ordering is a3, a4. We can compute FX1,X2(X1 prevent the necessity for increasing precision as long
 a3,X2  a4)  0.6; therefore, the tag interval is as the tag interval resides entirely within the top or bottom
(0.6,0.72]. Another way of obtaining the tag interval half of the unit interval. We can also start transmitting
would be to partition the single letter tag interval the code before the entire sequence has been en-
[0.6,1) in the same proportions as the partitioning of coded. We have to use a slightly more complicated
the unit interval. As in the case of the unit interval, strategy when the tag interval straddles the midpoint
the first subpartition would correspond to the letter of the unit interval. We leave the details to Sayood
a1, the second subpartition would correspond to the (2000).
428 Data Compression

1.0
1.0 0.720 0.6720

a4

0.6 0.84 0.672 0.6624

a3
0.4 0.76 0.648 0.6576
a2
0.3 0.72 0.636 0.6552

a1

0.0 0.6 0.600 0.648

Figure 4 Narrowing of the tag interval for the sequence a4a0a2a4.

C. Sources with Memory probability that the pixel under consideration would
have a similar value would be quite high. If, in fact,
Throughout our discussion we have been assuming the pixel had a value close to its neighbors, encoding
that each symbol in a sequence occurs independently it in this context would require many fewer bits than
of the previous sequence. In other words, there is no encoding it independent of its neighbors (Memon
memory in the sequence. Most sequences of interest to and Sayood, 1995).
us are not made up of independently occurring sym- Shannon (1948) incorporated this dependence
bols. In such cases an assumption of independence in the definition of entropy in the following manner.
would give us an incorrect estimate of the probability Define
of occurrence of that symbol, thus leading to an inef- i1m i2m inm

ficient code. By taking account of the dependencies Gn    

i m i m

in1
1 2
in the sequence we can significantly improve the
amount of compression available. Consider the letter P(X1  i1,X2  i2, . . ., Xn  in)
u in a piece of English text. The frequency of occur- log P(X1  i1,X2  i2,. . . ,Xn  in)
rence of the letter u occurring in a piece of English
text is approximately 0.018. If we had to encode the where {X1,X2, . . .,Xn} is a sequence of length n gen-
letter u and we used this value as our estimate of the erated by a source S. Then the entropy of the source
probability of the letter, we would need approximately is defined as
log2 0.018   6 bits. However, if we knew the previous
1


1
letter was q our estimate of the probability of the let- H(S)  lim  Gn
n→ n
ter u would be substantially more than 0.018 and thus
encoding u would require fewer bits. Another way of There are a large number of compression schemes
looking at this is by noting that if we have an accurate that make use of this dependence.
estimate of the probability of occurrence of particular
symbols we can obtain a much more efficient code. If
we know the preceding letter(s) we can obtain a more D. Context-Based Coding
accurate estimate of the probabilities of occurrence
of the letters that follow. Similarly, if we look at pixel The most direct approach to using this dependence
values in a natural image and assume that the pixels is to code each symbol based on the probabilities pro-
occur independently, then our estimate of the proba- vided by the context. If we are to sequentially encode
bility of the values that each pixel could take on would the sequence x1,x2, . . .,xn, we need  log i0 n1

be approximately the same (and small). If we took p(xi1|x1,x2, . . .,xn) bits (Weinberger et al., 1995). The
into account the values of the neighboring pixels, the history of the sequence makes up its context. In prac-
Data Compression 429

tice, if we had these probabilities available they could text he. If i has not appeared in this context either, we
be used by an arithmetic coder to code the particular reduce the context size to one and look to see how of-
symbol. To use the entire history of the sequence as ten i has occurred in the context of e. If this is zero,
the context is generally not feasible. Therefore, the we again send an escape and use the zero order con-
context is made up of some subset of the history. It text. The zero order context is simply the frequency
generally consists of those symbols that our knowl- of occurrence of i in the history. If i has never oc-
edge of the source tells us will have an affect on the curred before, we send another escape symbol and
probability of the symbol being encoded and which encode i, assuming an equally likely occurrence of
are available to both the encoder and the decoder. each letter of the alphabet.
For example, in the binary image coding standard We can see that if the symbol has occurred in the
JBIG, the context may consist of the pixels in the im- longest context, it will likely have a high probability
mediate neighborhood of the pixel being encoded and will require few bits. However, if it has not, we pay
along with a pixel some distance away which reflects a price in the shape of the escape symbol. Thus, there
the periodicity in half-tone images. Some of the most is a tradeoff here. Longer contexts may mean higher
popular context-based schemes today are ppm (pre- probabilities or a long sequence of escape symbols.
diction with partial match) schemes. One way out of this has been proposed by Cleary and
Teahan (1997) under the name ppm*. In ppm* we
look at the longest context that has appeared in the
1. Prediction with Partial Match history. It is very likely that this context will be fol-
In general, the larger the size of a context, the higher lowed by the symbol we are attempting to encode. If
the probability that we can accurately predict the sym- so, we encode the symbol with very few bits. If not, we
bol to be encoded. Suppose we are encoding the drop to a relatively short context length and continue
fourth letter of the sequence their. The probability of with the standard ppm algorithm. There are a number
the letter i is approximately 0.053. It is not substan- of variants of the ppm* algorithm, with the most pop-
tially changed when we use the single letter context e, ular being ppmz developed by Bloom. It can be found
as e is often followed by most letters of the alphabet. at [Link]
In just this paragraph it has been followed by d, i, l,
n, q, r, t, and x. If we increase the context to two let-
ters he, the probability of i following he increases. It in- E. Predictive Coding
creases even more when we go to the three-letter con-
text the. Thus, the larger the context, the better off we If the data we are attempting to compress consists of
usually are. However, all the contexts and the proba- numerical values, such as images, using context-based
bilities associated with the contexts have to be avail- approaches directly can be problematic. There are
able to both the encoder and the decoder. The num- several reasons for this. Most context-based schemes
ber of contexts increases exponentially with the size exploit exact reoccurrence of patterns. Images are
of the context. This puts a limit on the size of the con- usually acquired using sensors that have a small
text we can use. Furthermore, there is the matter of amount of noise. While this noise may not be per-
obtaining the probabilities relative to the contexts. ceptible, it is sufficient to reduce the occurrence of
The most efficient approach is to obtain the frequency exact repetitions of patterns. A simple alternative to
of occurrence in each context from the past history using the context approach is to generate a predic-
of the sequence. If the history is not very large, or the tion for the value to be encoded and encode the pre-
symbol is an infrequent one, it is quite possible that diction error. If there is considerable dependence
the symbol to be encoded has not occurred in this among the values with high probability, the predic-
particular context. tion will be close to the actual value and the predic-
The ppm algorithm initially proposed by Cleary and tion error will be a small number. We can encode this
Witten (1984) starts out by using a large context of small number, which as it occurs with high probabil-
predetermined size. If the symbol to be encoded has ity will require fewer bits to encode. An example of
not occurred in this context, an escape symbol is sent this is shown in Fig. 5. The plot on the left of Fig. 5 is
and the size of the context is reduced. For example, the histogram of the pixel values of the sensin image,
when encoding i in the example above we could start while the plot on the right is the histogram of the dif-
out with a context size of three and use the context ferences between neighboring pixels. We can see that
the. If i has not appeared in this context, we would the small differences occur much more frequently
send an escape symbol and use the second order con- and therefore can be encoded using fewer bits. As
430 Data Compression

Figure 5 Histograms of pixel values in the sensin image and of the differences between neighboring pixels.

opposed to this, the actual pixel values have a much This prediction is then refined by using an estimate
more uniform distribution. of how much the prediction differed from the actual
Because of the strong correlation between pixels in value in similar situations in the past. The “situation”
a neighborhood, predictive coding has been highly is characterized by an activity measure which is ob-
effective for image compression. It is used in the cur- tained using the differences of the pixels in the neigh-
rent state-of-the-art algorithm CALIC (Wu and borhood. The differences NE  N, N  NW, and NW
Memon, 1996) and forms the basis of JPEG-LS, which  W are compared against thresholds which can be
is the standard for lossless image compression. defined by the user and a number between 0 and 364
and a SIGN parameter which takes on the values 1
and 1. The sign parameter is used to decide whether
1. JPEG-LS the correction should be added or subtracted from
The JPEG-LS standard uses a two-stage prediction the original prediction. The difference between the
scheme followed by a context-based coder to encode pixel value and its prediction is mapped into the range
the difference between the pixel value and the pre- of values occupied by the pixel and encoded using
diction. For a given pixel the prediction is generated Golomb codes. For details, see Sayood (2000) and
in the following manner. Suppose we have a pixel Weinberger et al. (1998).
with four neighboring pixels as shown in Fig. 6. The
initial prediction X is obtained as 2. Burrows-Wheeler Transform
if NW  max(W,N) The Burrows-Wheeler transform (BWT) uses the
X  max(W,N) memory in a sequence in a somewhat different man-
else ner than either of the two techniques described pre-
{ viously. In this technique the entire sequence to be
if NW  min(W,N) encoded is read in and all possible cyclic shifts of the
X  min(W,N) sequence are generated. These are then sorted in lex-
else icographic order. The last letter of each sorted cycli-
X  W  N  NW cally shifted sequence is then transmitted along with
} the location of the original sequence in the sorted
list. The sorting results in long sequences of identical
letters in the transmitted sequence. This structure can
be used to provide a very efficient representation of
the transmitted sequence. The easiest way to under-
stand the BWT algorithm is through an example.
EXAMPLE: BWT
Suppose we wish to encode the sequence
RINTINTIN. We first obtain all cyclical shifts of this se-
quence and then sort them in lexicographic order as
shown in Fig. 7.
Figure 6 Labeling of pixels in the neighborhood of a pixel to We transmit the string consisting of the last letters
be encoded. in the lexicographically ordered set and the position
Data Compression 431

F. Dictionary Coding
One of the earliest forms of compression is to create
a dictionary of commonly occurring patterns which is
available to both the encoder and the decoder. When
this pattern occurs in a sequence to be encoded it can
be replaced by the index of its entry in the dictionary.
A problem with this approach is that a dictionary that
Figure 7 Cyclically shifted versions of the original sequence
and lexicographically order set of the cyclical shifts. works well for one sequence may not work well for an-
other sequence. In 1977 and 1978, Jacob Ziv and Abra-
ham Lempel (1977, 1978) described two different ways
of the original string in the lexicographically ordered of making the dictionary adapt to the sequence being
set. For this example the transmitted sequence would encoded. These two approaches form the basis for
be the string TTRIIINNN and the index 7. Notice that many of the popular compression programs of today.
the string to be transmitted contains relatively long
strings of the same letter. If our example string had 1. LZ77
been realistically long, the runs of identical letters
would have been correspondingly long. Such a string The 1977 algorithm commonly referred to as LZ77
is easy to compress. The method of choice for BWT is uses the past of the sequence as the dictionary. When-
move-to-front coding (Burrows and Wheeler, 1994; ever a pattern recurs within a predetermined window,
Nelson, 1996; Sayood, 2000). it is replaced by a pointer to the beginning of its pre-
Once the string and the index have been received, vious occurrence and the length of the pattern. Con-
we decode them by working backwards. We know the sider the following (admittedly weird) sequence:
last letter in the string is its seventh element which is N. a mild fork for miles vorkosigan
To find the letter before N we need to generate the
string containing the first letters of the lexicographi- We repeat this sentence in Fig. 8 with recurrences re-
cally ordered set. This can be easily obtained as II- placed by pointers. If there were sufficient recurrences
INNNRTT by lexicographically ordering the received of long patterns, we can see how this might result in
sequence. We will refer to this sequence of first letters a compressed representation. In Fig. 8 we can see that
as the F sequence and the sequence of last letters as the the “compressed” representation consists of both
L sequence. Note that given a particular string and its pointers and fragments of text that have not been en-
cyclic shift, the last letter of the string becomes the first countered previously. We need to inform the decoder
letter of the cyclically shifted version, and the last letter when a group of bits is to be interpreted as a pointer
of the cyclically shifted version is the letter prior to the and when it is to be interpreted as text. There are a
last letter in the original sequence. Armed with this fact number of different ways in which this can be done.
and the knowledge of where the original sequence was The original LZ77 algorithm used a sequence of
in the lexicographically ordered set, we can decode the triples <o,l,c> to encode the source output, where o is
received sequence. We know the original sequence was the offset or distance to the previous recurrence, l is
seventh in the lexicographically ordered set; therefore, the length of the pattern, and c corresponds to the
the last letter of the sequence has to be N. This is the character following the recurrence. In this approach
first N in L. Looking in F we see that the first N appears when a symbol was encountered for the first time (in
in the fourth location. The fourth element in L is I. the encoding window) the values for o and l were set
Therefore, the letter preceding N in our decoded se- to 0. Storer and Syzmanski (1982) suggested using a
quence is I. This I is the first I in L; therefore, we look one bit flag to differentiate between pointers and sym-
for the first I in F. The first I occurs in the first location. bols which had not occurred previously in the coding
The letter in the first location in L is T. Therefore, the
decoded sequence becomes TIN. Continuing in this
fashion we can decode the entire sequence.
The BWT is the basis for the compression utilities bzip a mi l d f o r k e s v g n
and bzip2. For more details on BWT compression, see
Burrows and Wheeler (1994), Nelson and Gailly
(1996), and Sayood (2000). Figure 8 Illustration for LZ77.
432 Data Compression

window. In their variant, commonly known as LZSS, sion schemes that can provide a much higher level of
the one bit flag is followed by either a pair (<o,l>) or compression. However, it should be kept in mind that
the code word of the new symbol. There are a num- we generally pay for higher compression by increased
ber of variants of both the LZ77 and the LZSS algo- information loss. Therefore, we measure the perfor-
rithms which are the basis for several popularly used mance of the compression system using two metrics. We
compression utilities. Included among them are gzip measure the amount of compression as before; how-
and PNG (portable network graphics). ever, we also measure the amount of distortion intro-
duced by the loss of information. The measure of dis-
tortion is generally some variant of the mean squared
2. LZ78
error. If at all possible, it is more useful to let the ap-
The 1978 algorithm requires actually building a dy- plication define the distortion.
namic dictionary based on the past symbols in the se- In this section we describe a number of compres-
quence. The sequence is encoded using pairs of code sion techniques that allow loss of information, hence
words <i,c>, where i is the index to a pattern in the the name lossy compression. We begin with a look at
dictionary and c is the code word of the character fol- quantization which, in one way or another, is at the
lowing the current symbol. The most popular variant heart of all lossy compression schemes.
of the LZ78 algorithm is the LZW algorithm devel-
oped by Terry Welch (1984). In this variation the dic-
tionary initially contains all the individual letters of A. Quantization
the source alphabet. The encoder operates on the se-
quence by collecting the symbols in the sequence into Quantization is the process of representing the out-
a pattern p until such time as the addition of another put of a source with a large (possibly infinite) alpha-
symbol will result in a pattern which is not con- bet with a small alphabet. It is a many-to-one mapping
tained in the dictionary. The index to p is then trans- and therefore irreversible. Quantization can be per-
mitted, the pattern p concatenated with is added as formed on a sample-by-sample basis or it can be per-
the next entry in the dictionary, and a new pattern p formed on a group of samples. The former is called
is begun with as the first symbol. scalar quantization and the latter is called vector quan-
Variants of the LZW algorithm are used in the UNIX tization. We look at each in turn.
compress command as part of the graphic interchange
format (GIF) and for the modem protocol v. 42bis.
1. Scalar Quantization
Let us, for the moment, assume that the output al-
III. LOSSY COMPRESSION phabet of the source is all or some portion of the real
number line. Thus, the size of the source alphabet is
The requirement that no information be lost in the infinite. We would like to represent the source output
compression process puts a limit on the amount of com- using a finite number of code words M. The quantizer
pression we can obtain. The lowest number of bits per consists of two processes: an encoding process that
sample is the entropy of the source. This is a quantity maps the output of the source into one of the M code
over which we generally have no control. In many ap- words, and a decoding process that maps each code
plications this requirement of no loss is excessive. For word into a reconstruction value. The encoding
example, there is high-frequency information in an im- process can be viewed as a partition of the source al-
age which cannot be perceived by the human visual sys- phabet, while the decoding process consists of ob-
tem. It makes no sense to preserve this information for taining representation values for each partition. An
images that are destined for human consumption. Sim- example for a quantizer with an alphabet size of four
ilarly, when we listen to sampled speech we cannot per- is shown in Fig. 9. If the quantizer output alphabet in-
ceive the exact numerical value of each sample. There- cludes 0, the quantizer is called a midtread quantizer.
fore, it makes no sense to expend coding resources to Otherwise, it is called a midrise quantizer.
preserve the exact value of each speech sample. In The simplest case is when the partitions are of the
short, there are numerous applications in which the same size. Quantizers with same size partitions are
preservation of all information present in the source called uniform quantizers. If the source is uniformly dis-
output is not necessary. For these applications we relax tributed between A and A, the size of the partition
the requirement that the reconstructed signal be iden- or quantization interval  is 2A/M. The reconstruc-
tical to the original. This allows us to create compres- tion values are located in the middle of each quanti-
Data Compression 433

Reconstruction region is “spread out” so as to make use of multiple

values quantization intervals. The mapping is reversed after
the quantizer. For a companding function c(x) and a
source which lies between xmax, the variance of the
quantization noise is
x2max

xmax
fX(x)
2q    dx. (6)
Partitions 3M2 xmax (c(x))2
Figure 9 Quantizer with alphabet size of four. If a variable length code such as a Huffman code or
arithmetic coding is used to encode the output of the
quantizer, Gish and Pierce (1968) showed that the opti-
mum quantizer is a uniform quantizer which covers the
zation interval. If we define the difference between
entire range of the source output. If the range is large
the input x and the output Q(x) to be the quantiza-
and our desired distortion is small, the number of quan-
tion noise, we can show that the variance of the quan-
tizer levels can become quite large. In these situations we
tization noise in this situation is 2/12. If the distrib-
can use a quantizer with a limited output alphabet called
ution of the source output is other than uniform, we
a recursively indexed quantizer (Sayood and Na, 1992).
can optimize the value of  for the particular distrib-
The JPEG algorithm uses a set of uniform scalar
ution (Gersho and Gray, 1991; Max, 1960).
quantizers for quantizing the coefficients used to rep-
Often, the distribution of the quantizer input is a
resent the image. The quantizer levels are then en-
peaked distribution modeled as a Gaussian or Laplacian
coded using a variable length code.
distribution. If the encoder is going to use a fixed length
code, that is, each quantizer output is encoded using the
same number of bits, we can get a lower average distor- 2. Vector Quantization
tion if we use smaller partitions corresponding to the
The idea of representing groups of samples rather
lower value inputs. Such a quantizer is called a nonuni-
than individual samples has been present since Shan-
form quantizer and is specified by the boundary values of
non’s original papers (1948). There are several ad-
the partition bi and the reconstruction levels yi. If we
vantages to representing sequences. Consider the sam-
know the probability density function fX(x), the bound-
ples of the signal shown in Fig. 11. The values vary
ary and reconstruction values for an M-level quantizer
approximately between 4 and 4. We could quantize
which minimizes the mean squared error can be ob-
these samples with an eight-level scalar quantizer with
tained by iteratively solving the following equations.
  1. So the reconstruction values would be {12, 32,

 52, 72}. If we were to use a fixed length code we

bj
xfX(x)dx} would need three bits to represent the eight quan-
bj1
y  (4)

j bj tizer outputs. If we look at the output of the quantizer
fX(x)dx in pairs, we get 64 possible reconstruction values.
bj1
These are represented by the larger filled circles in
Fig. 12. However, if we plot the samples of the signal
yj1  yj
bj   (5) as pairs (as in Fig. 13) we see that the samples are
2
clustered along a line in the first and third quadrants.
Rather than changing the size of the quantization in- This is due to the fact that there is a high degree of
tervals, we can also implement a nonuniform quan- correlation between neighboring samples, which
tizer as shown in Fig. 10. The high-probability input means that in two dimensions the samples will cluster

Figure 10 Companded quantization.

434 Data Compression

Figure 11 Samples of a signal.

around the y  x line. Looking from a two-dimen- tizer, we need to block the input samples into “vec-
sional point of view, it makes much more sense to tors” and then compare them against all the possible
place all the 64 output points of the quantizer close quantizer output values. For three bits per sample
to the y  x line. For a fixed length encoding, we and two dimensions this translates to 64 possible com-
would need six bits to represent the 64 different quan- pares. However, for the same number of bits and a
tizer outputs. As each quantizer output is a represen- block size, or vector dimension, of 10, the number of
tation of two samples, we would end up with three bits quantizer outputs would be 23 10 which is
per sample. Therefore, for the same number of bits, 1,073,741,824! As it generally requires a large block
we would get a more accurate representation of the size to get the full advantage of a vector quantizer, this
input and, therefore, incur less distortion. We pay for means that the rate at which a vector quantizer (VQ)
this decrease in distortion in several different ways. operates (i.e., bits per sample) is usually quite low.
The first is through an increase in the complexity of The second way we pay is because of the fact that
the encoder. The scalar quantizer has a very simple the quantizer becomes tuned to our assumptions
encoder. In the case of the two-dimensional quan- about the source. For example, if we put all our quan-

-1.0

-2.0

-3.0

-4.0

Figure 12 Two-dimensional view of an eight-level scalar Figure 13 Two-dimensional view of an eight-level scalar
quantizer. quantizer.
Data Compression 435

tizer output values along the y  x line and then we the development of differential pulse code modula-
started getting input vectors which lay in the second tion (DPCM) (Cutler, 1952). A version of DPCM is
or fourth quadrants, we would end up with substan- the algorithm used in the International Telecom-
tial distortion in the reconstruction. munication Union (ITU) standard G.726 for speech
The operation of a VQ can be summarized as fol- coding.
lows (see Fig. 14). Both the encoder and the decoder The DPCM system consists of two blocks as shown
have copies of the VQ codebook. The codebook con- in Fig. 15. The function of the predictor is to obtain
sists of the quantizer reconstruction vectors. The en- an estimate of the current sample based on the recon-
coder blocks the input into an N sample vector and structed values of the past sample. The difference be-
finds the vector in the codebook which is closest (usu- tween this estimate, or prediction, and the actual value
ally in the Euclidean sense) to the input. The encoder is quantized, encoded, and transmitted to the receiver.
then sends the index of the closest match. The de- The decoder generates an estimate identical to the
coder, upon receiving the index, performs a table encoder, which is then added on to generate the re-
lookup and obtains the reconstruction vector. constructed value. The requirement that the predic-
The VQ codebook is usually obtained using a clus- tion algorithm use only the reconstructed values is to
tering algorithm popularized by Linde, Buzo, and ensure that the prediction at both the encoder and
Gray (1980). It is generally referred to by the initials the decoder are identical. The reconstructed values
of the three authors (LBG). The LBG algorithm ob- used by the predictor, and the prediction algorithm,
tains a nearest neighbor partition of the source out- are dependent on the nature of the data being en-
put space by making use of a training set. Selection coded. For example, for speech coding the predictor
of the training set can be an important aspect of the often uses the immediate past several values of the se-
design of the VQ as it embodies our assumptions quence, along with a sample that is a pitch period
about the source output. Details of the LBG algo- away, to form the prediction. In image compression
rithm can be found in a number of places (see the predictor may use the same set of pixels used by
Gersho and Gray, 1991; Linde, Buzo, and Gray, 1980; the JPEG-LS algorithm to form the prediction.
Sayood, 2000). The predictor generally used in a DPCM scheme is
There are a number of variations on the basic VQ a linear predictor. That is, the predicted value is ob-
described above. The most well known is the tree tained as a weighted sum of past reconstructed values.
structured vector quantizer (TSVQ). Details on these
can be found in Gersho and Gray (1991).
pn   ai xi
iI

where I is an index set corresponding to the samples

to be used for prediction. The coefficients ai are gen-
B. Predictive Coding erally referred to as the predictor coefficients. If we as-
sume the source output to be wide sense stationary, the
If we have a sequence with sample values that vary predictor coefficients can be obtained as a solution of
slowly as in the signal shown in Fig. 11, knowledge the discrete form of the Weiner-Hopf equations
of the previous samples gives us a lot of information
A  R1P
about the current sample. This knowledge can be
used in a number of different ways. One of the ear- where A is an M 1 vector of predictor coefficients,
liest attempts at exploiting this redundancy was in R is the M M autocorrelation matrix of the set of

Encoder Decoder

Figure 14 Operation of a vector quantizer.

436 Data Compression

Figure 15 Block diagram of a DPCM system.

samples used to form the prediction, and P is the M selected to compact most of the energy into as few co-
1 vector of autocorrelation coefficients between the el- efficients as possible. The coefficients are then quan-
ements of the index set and the value to be estimated. tized with different quantizers for each coefficient. Fi-
Both the quantizer and the predictor in the DPCM nally, the quantizer labels are encoded.
system can be adaptive. The most common form of Transform coding generally involves linear trans-
adaptivity for DPCM in speech coding is based on the forms. Consider the situation where the data is
reconstruction values. This allows both the encoder blocked into vectors of length M. The transform co-
and the decoder, in the absence of channel errors, to efficients can be obtained by multiplying the data
adapt using the same information. with a transform matrix of dimension M M.
In Fig. 16 we show the results of encoding the sensin
  AX
image using a simple fixed predictor and a recursively
indexed quantizer with entropy coding. where X is a vector of size M 1 containing the data,
and  is the M 1 vector of transform coefficients. The
data can be recovered by taking the inverse transform:
C. Transform Coding X  A1
Transform coding first became popular in the early In most transforms of interest the transform matrix is
1970s as a way of performing vector quantization unitary, that is,
(Huang and Schultheiss, 1963). Transform coding
A1  AT
consists of three steps. The data to be compressed is
divided into blocks, and the data in each block is If the data is stationary we can show that the optimum
transformed to a set of coefficients. The transform is transform in terms of providing the most energy com-

Figure 16 (a) The original sensin image and (b) the sensin image coded at one bit per pixel using DPCM and the
recursively indexed quantizer.
Data Compression 437

paction is the Karhunen-Loeve transform (KLT). The transforms. These are transforms which can be imple-
KLT transform matrix is constructed from the eigen- mented by first taking the transform of the rows and
vectors of the autocorrelation matrix. Therefore, the then taking the transform of the columns (or vice
transform is data dependent. Different sets of data might versa). The popular JPEG image compression standard
require different transform matrices. In practice, unless uses a separable 8 8 DCT as its transform. The im-
the size of the transform is small relative to the data, it age is divided into 8 8 blocks. These blocks are then
generally costs too many bits to send the transform ma- transformed to obtain 8 8 blocks of coefficients.
trix to the decoder for the KLT to be feasible. The prac- The coefficients have different statistical character-
tical alternative to the KLT has been the discrete cosine istics and may be of differing importance to the end
transform (DCT). The DCT provides comparable com- user. Therefore, they are quantized using different
pression to the KLT for most sources and has a fixed quantizers. In image compression the lower order co-
transform matrix whose elements are given by: efficients are more important in terms of human per-
 ception and are therefore quantized using quantizers
  cos
1

(2j  1)i

2M i  0, j  0,1, , M  1
 M with smaller step sizes (and hence less quantization
[A]i,j   (7) noise) than the higher order, higher frequency coef-
 cos
2

(2j  1)i}

2M i  1,2, , M  1,
M ficients. A sample set of step sizes recommended by
j  0,1, , M  1
the JPEG committee (Pennebaker and Mitchell, 1993)
The rows of the transform matrix are shown in graph- is shown in Fig. 18.
ical form in Fig. 17. We can see that the rows repre- Each quantized value Q(i,j) is represented by a label
sent signals of increasing frequency. Thus, the DCT
breaks the signal up into its frequency components.
As most natural sources, such as speech, have higher
li,j 
 ij

Qij 
 .5

low-frequency content the lower order coefficients where Qij is the step size in the ith row and jth column
usually contain most of the information about a par- and   indicates truncation to an integer value. The
ticular block. We obtain compression by discarding reconstruction is obtained from the label by multi-
those coefficients which contain little or no energy. plying it with the step size.
When coding two-dimensional sources such as im- The final step involves coding the quantization
ages, most transform coding schemes use separable levels. The JPEG image compression standard uses a

0 3 6

1
4

2 5

Figure 17 Basis set for the DCT. The numbers in the circles correspond to the row of the transform matrix.
438 Data Compression

D. Subband/Wavelet Coding
Transform coding at low rates tends to give the re-
constructed image a blocky appearance. The image in
Fig. 21 has been coded at 0.25 bits per pixel using the
JPEG algorithm. The blocky appearance is clearly ap-
parent. This has led to the increasing popularity of
subband and wavelet-based schemes. The implemen-
Figure 18 Sample quantization table. tation for both subband and wavelet-based schemes is
similar. The input is filtered through a bank of filters,
called the analysis filterbank. The filters cover the en-
minor variation of a scheme by Chen and Pratt (1984). tire frequency range of the signal. As the bandwidth
The lowest order coefficient, commonly referred to as of each filter is only a fraction of the bandwidth of the
the DC coefficient, has been found to be correlated original signal, the Nyquist criterion dictates that the
from block to block. It is therefore coded differen- number of samples required at the output of the fil-
tially. The remaining coefficients are scanned in zigzag ter be less than the number of samples per second re-
order as shown in Fig. 19. As most of the higher fre- quired at the input of the filter. The output of the fil-
quency coefficients are generally small and the step ters is subsampled or decimated and encoded. The
sizes used to quantize them are relatively large, most decimated output values are quantized, and the quan-
of the labels at the tail end of the scan are zero. We tization labels are encoded. At the decoder, after the
take advantage of this fact by sending an end of block received samples are decoded they are upsampled by
symbol after the last nonzero label on the scan. Thus, the insertion of zeros between the received samples
a large number of coefficients are represented using and filtered using a bank of reconstruction filters. A
a single code word. We represent the remaining co- two-band subband coding scheme is shown in Fig. 22.
efficients using a code which is indexed by the mag- The major components of the design of subband cod-
nitude of the coefficient and the number of zero val- ing schemes are the selection of the filters and the en-
ued labels preceding it. Details of the coding can be coding method used for the subbands. In order to de-
found in a number of places including Pennebaker termine the latter, it may be necessary to allocate a
and Mitchell (1993) and Sayood (2000). predetermined bit budget between the various bands.
In Fig. 20 we show the sensin image coded at 0.5 Notice that in the system shown in Fig. 22 if the fil-
bits per pixel using JPEG. ters are not ideal filters then at least one of the two
analysis filters will have a bandwidth greater than half
the bandwidth of the source output. If the source is
initially sampled at the Nyquist rate, then when we
subsample by two that particular filter output will ef-
fectively be sampled at less the Nyquist rate, thus in-
troducing aliasing. One of the objectives of the design
of the analysis and synthesis filterbanks is to remove
the effect of aliasing.
If we ignore the quantization and coding for the
moment, we can determine conditions on the analy-
sis and synthesis filterbanks such that the reconstruc-
tion is a delayed version of the source output. If we
represent the samples of the source sequence by x(n)
and the reconstruction sequence by x(n), then this re-
quirement known as the perfect reconstruction (PR) re-
quirement can be written as
x(n)  cx(n  n0) (8)
where c is a constant. In terms of the Z transforms of
the sequences, we can write the PR requirement as
Figure 19 The zigzag scanning pattern for an 8 8
transform. X(z)  czn0X(z) (9)
Data Compression 439

Figure 20 (a) The original sensin image and (b) the sensin image coded at 0.5 bits per pixel using JPEG.

Let H1(z) and H2(z) be the transfer functions for the K1(z)  H2(z) (13)
analysis filters and K1(z) and K2(z) be the transfer
K2(z)  H1(z) (14)
functions of the synthesis filters. Then we can show
(Sayood, 2000) that To satisfy the second equation we can select H2(z) as
(Mintzer, 1985; Smith and Barnwell, 1984)
1
X(z)   [H1(z)K1(z)  H2(z)K2(z)]X(z)
2 H2(z)  zN H1(z1) (15)
1 Thus, all four filters can be expressed in terms of one
  [H1(z)K1(z)  H2(z)K2(z)]X(z) (10)
2 prototype filter. We can show that this prototype filter
Examining this equation we can see that in order for should have an impulse response satisfying
the perfect reconstruction condition to be satisfied, N
we need 
k0
hkhk2n  n (16)
H1(z)K1(z)  H2(z)K2(z)  0 (11) We can arrive at the same requirement on the filter
H1(z)K1(z)  H2(z)K2(z)  czn0 (12) coefficients using a wavelet formulation. Once we
have obtained the coefficients for the filters, the com-
The first equation is satisfied if we pick the synthesis pression approach using wavelets is similar. After the
filters as source output has been decomposed the next step is
the quantization and coding of the coefficients. The
two most popular approaches to quantization and
coding for image compression are the embedded ze-
rotree (EZW) (Shapiro, 1993) and the set partition-
ing in hierarchical trees (SPIHT) (Said and Pearl-
man, 1996) approaches.
Both these approaches make use of the fact that
there is a relationship between the various subbands.
A natural image is essentially a low-pass signal. There-
fore, most of the energy in a wavelet or subband de-
composition is concentrated in the LL band. One ef-
fect of this is that if the coefficient representing a
particular pixel in the LL band is less than a specified
threshold, the coefficients corresponding to the same
pixel in the other bands will also have a magnitude
smaller than that threshold. Thus, during coding we
Figure 21 The sensin image coded at 0.25 bits per pixel using can scan the coefficients in the LL band first and
JPEG. compare them against a sequence of decreasing
440 Data Compression

Source

Figure 22 A two-band subband coding scheme.

thresholds. If the coefficient is less than the threshold E. Analysis-Synthesis Schemes

we can check to see if the corresponding coefficients
in the other bands are also less than this threshold. When possible, one of the most effective means of
This information is then transmitted to the decoder. compression is to transmit instructions on how to re-
If the coefficients in the other band are also less than construct the source rather than transmitting the
the threshold this is a highly efficient code. Note that source samples. In order to do this we should have a
the efficiency is dependent on the image being low fairly good idea about how the source samples were
pass. For more high-pass images, such as remotely generated. One particular source for which this is
sensed images, this strategy is not very effective. true is human speech.
In Fig. 23 we have the sensin image coded at rates Human speech can be modeled as the output of a
of 0.5 bits per pixel and 0.25 bits per pixel using the linear filter which is excited by either white noise or
SPIHT algorithm. Comparing the 0.25 bits per pixel a periodic input or a combination of the two. One of
reconstruction to Fig. 21 we can see the absence of the earliest modern compression algorithms made
blockiness. However, there are different artifacts that use of this fact to provide a very high compression of
have taken the place of the blockiness. Neither re- speech. The technique, known as linear predictive
construction is very good at this rate. coding, has its best known embodiment in the (now
A descendant of these techniques, known as outdated) U.S. Government standard LPC-10. Some
EBCOT (Taubman, 2000), is the basis for the new of the basic aspects of this standard are still alive, al-
JPEG 2000 image compression standard. Detailed in- beit in modified form in today’s standards.
formation about these techniques can be found in The LPC-10 standard assumes a model of speech
Said and Pearlman (1996), Sayood (2000), and pictured in Fig. 24. The speech is divided into frames.
Shapiro (1993). Each frame is classified as voiced or unvoiced. For the

Figure 23 The sensin image coded at (a) 0.5 bits per pixel and (b) 0.25 bits per pixel using SPIHT.
Data Compression 441

compress each frame separately. This is the point of

view adopted by M-JPEG, or motion JPEG, in which
each frame is compressed using the JPEG algorithm.
However, we know that in most video sequences
there is a substantial amount of correlation between
frames. It is much more efficient to send differences
between the frames rather than the frames themselves.
Figure 24 Speech synthesis model used by LPC-10. This idea is the basis for several international stan-
dards in video compression. In the following we briefly
look at some of the compression algorithms used in
these standards. Note that the standards contain much
voiced speech the pitch period for the speech sample more than just the compression algorithms.
is extracted. The parameters of the vocal tract filter The ITU H.261 and its descendant ITU H.2631 are
are also extracted and quantized. All this information international standards developed by the ITU, which
is sent to the decoder. The decoder synthesizes the is a part of the United Nations organization. A block
speech samples yn as diagram of the H.261 video coding algorithm is shown
M in Fig. 25. The image is divided into blocks of size 8
yn   biyni  Gn
i1
(17) 8. The previous frame is used to predict the values
of the pixels in the block being encoded. As the ob-
where {bi} is the coefficient of the vocal tract filter. The jects in each frame may have been offset from the pre-
input to the filter, the sequence {n}, is either the out- vious frame, the block in the identical location is not
put of a noise generator or a periodic pulse train, always used. Instead the block of size 8 8 in the pre-
where the period of the pulse train is the pitch period. vious frame which is closest to the block being en-
Since the introduction of the LPC-10 standard there coded in the current frame is used as the predicted
has been a considerable increase in the sophistication value. In order to reduce computations the search
of speech coders. In code excited linear prediction area for the closest match is restricted to lie within a
(CELP) the vocal tract filter is excited by elements of prescribed region around the location of the block
an excitation codebook. The entries of the codebook being encoded. This form of prediction is known as
are used as input to a vocal filter of the form motion compensated prediction. The offset of the block
10 used for prediction from the block being encoded is
yn   biyni  ynP  Gn
i1
(18) referred to as the motion vector and is transmitted to
the decoder. The loop filter is used to prevent sharp
where P is the pitch period. The synthesized speech transitions in the previous frame from generating
is compared with the actual speech, and the code- high frequency components in the difference.
book entry that provides the closest perceptual match The difference is encoded using transform coding.
is selected. The index for this entry is sent to the de- The DCT is used followed by uniform quantization.
coder along with the vocal tract filter parameters. The DC coefficient is quantized using a scalar quan-
Mixed excitation linear prediction (MELP) uses a tizer with a step size of 8. The other coefficients are
somewhat more complex approach to generating the quantized with 1 of 31 other quantizers, all of which
excitation signal. The input is subjected to a multi- are midtread quantizers, with step sizes between 2
band voicing analysis using five filters. The results of and 62. The selection of the quantizer depends in
the analysis are used with a complex pitch detection part on the availability of transmission resources. If
strategy to obtain a rich excitation signal. higher compression is needed (fewer bits available),
a larger step size is selected. If less compression is ac-
ceptable, a smaller step size is selected. The quantiza-
F. Video Compression tion labels are scanned in a zigzag fashion and en-
coded in a manner similar to (though not the same
Currently, the source that requires the most resources as) JPEG.
in terms of bits and, therefore, has benefitted the most
from compression is video. We can think of video as a
sequence of images. With this view video compression 1
Originally published in 1996; an update published in 1998 is
becomes repetitive image compression and we can commonly referred to as H.263.
442 Data Compression

+
–

Motion
vector

Loop filter
status

Figure 25 Block diagram of the ITU-T H.261 video compression algorithm.

The coding algorithm for ITU-T H.263 is similar to also allows for greater control over quality of regions
that used for H.261 with some improvements. The im- in the reconstruction. The H.263 standard also allows
provements include: for bidirectional prediction.
As the H.261 algorithm was designed for video-
• Better motion compensated prediction conferencing, there was no consideration given to the
• Better coding need for random access. The MPEG standards incor-
• Increased number of formats porate this need by requiring that at fixed intervals a
• Increased error resilience frame of an image be encoded without reference to
past frames. The MPEG-1 standard defines three dif-
There are a number of other improvements that are ferent kinds of frames: I frames, P frames, and B
not essential for the compression algorithm. As men- frames. An I frame is coded without reference to pre-
tioned before, there are two versions of H.263. As the vious frames, that is, no use is made of prediction
earlier version is a subset of the latter one; we only de- from previous frames. The use of the I frames allows
scribe the later version. random access. If such frames did not exist in the
The prediction is enhanced in H.263 in a number video sequence, then to view any given frame we would
of ways. By interpolating between neighboring pixels have to decompress all previous frames, as the recon-
in the frame being searched, a “larger image” is cre- struction of each frame would be dependent on the
ated. This essentially allows motion compensation dis- prediction from previous frames. The use of periodic
placement of half pixel steps rather than integer num- I frames is also necessary if the standard is to be used
ber of pixels. There is an unrestricted motion vector for compressing television programming. A viewer
mode that allows references to areas outside the pic- should have the ability to turn on the television (and
ture, where the outside areas are generated by dupli- the MPEG decoder) at more or less any time during
cating the pixels at the image boundaries. Finally, in the broadcast. If there are periodic I frames available,
H.263 the prediction can be generated by a frame then the decoder can start decoding from the first I
that is not the previous frame. An independent seg- frame. Without the redundancy removal provided via
ment decoding mode allows the frame to be broken prediction the compression obtained with I frames is
into segments where each segment can be decoded less than would have been possible if prediction had
independently. This prevents error propagation and been used.
Data Compression 443

The P frame is similar to frames in the H.261 stan- IV. FURTHER INFORMATION
dard in that it is generated based on prediction from
previous reconstructed frames. The similarity is closer We have described a number of compression techniques.
to H.263, as the MPEG-1 standard allows for half pixel How they compare relative to each other depends on
shifts during motion compensated prediction. the performance criteria, which in turn depend on the
The B frame was introduced in the MPEG-1 stan- application. An excellent resource for people interested
dard to offset the loss of compression efficiency occa- in comparisons between the multitude of compression
sioned by the I frames. The B frame is generated us- programs available for different applications is the
ing prediction from the previous P or I frame and the Archive Compression Test maintained by Jeff Gilchrist at
nearest future P or I frame. This results in extremely [Link] Another excellent resource on the In-
good prediction and a high level of compression. The ternet is the data compression page maintained by Mark
B frames are not used to predict other frames, there- Nelson at [Link] This
fore, the B frames can tolerate more error. This also page contains links to many other data compression re-
permits higher levels of compression. sources, including programs and a set of informative ar-
The various frames are organized together in a ticles by Mark Nelson. Programs implementing some of
group of pictures (GOP). A GOP is the smallest random the techniques described here can also be obtained at
access unit in the video sequence. Therefore, it has to [Link]
contain at least one I frame. Furthermore, the first I
frame in a GOP is either the first frame of the GOP
or is preceded by B frames which use motion com- SEE ALSO THE FOLLOWING ARTICLES
pensated prediction only from this I frame. A possible
GOP is shown in Fig. 26. Notice that in order to re- Desktop Publishing • Electronic Data Interchange • Error
construct frames 2, 3, and 4, which are B frames, we Detecting and Correcting Codes • Multimedia
need to have the I and P frames. Therefore, the or-
der in which these frames are transmitted is different
from the order in which they are displayed.
The MPEG-2 standard extends the MPEG-1 stan-
BIBLIOGRAPHY
dard to higher bit rates, bigger picture sizes, and in-
Burrows, M., and Wheeler, D. J. (1994). A Block Sorting Data
terlaced frames. Where MPEG-1 allows half pixel dis- Compression Algorithm. Technical Report SRC 124, Digital
placements, the MPEG-2 standard requires half pixel Systems Research Center.
displacements for motion compensation. Further- Chen, W.-H., and Pratt, W. K. (March 1984). Scene Adaptive
more, the MPEG-2 standard contains several addi- Coder. IEEE Trans. Communications. COM-32:225–232.
tional modes of prediction. A full description of any Cleary, J. G., and Witten, I. H. (1984). Data compression using
of these standards is well beyond the scope of this ar- adaptive coding and partial string matching. IEEE Trans.
Communications. 32(4):396–402.
ticle. For details the readers are referred to the stan-
Cleary, J. G., and Teahan, W. J. (February 1997). Unbounded
dards ISO/IEC IS 11172, 13818, and 14496 and books length contexts for PPM. Computer Journal, 40:30–74.
Gibson et al. (1998), Mitchell et al. (1997), and Sayood Cutler, C. C. (July 29, 1952). Differential Quantization for Tele-
(2000). vision Signals. U.S. Patent 2 605 361.
Gallagher, R. G. (November 1978). Variations on a theme by
Huffman. IEEE Trans. Information Theory. IT-
24(6):668–674.
Gersho, A., and Gray, R. M. (1991). Vector Quantization and Sig-
I-frame
nal Compression. Dordrecht/Norwell, MA: Kluwer Academic.
Bidirectional prediction P-frame Gibson, J. D., Berger, T., Lookabaugh, T., Lindbergh, D., and
B-frame Baker, R. (1998). Digital Compression for Multimedia: Principles
and Standards. San Mateo, CA: Morgan Kaufmann.
Gish, H., and Pierce, J. N. (September 1968). Asymptotically ef-
ficient quantization. IEEE Trans. Information Theory. IT-
14:676–683.
Huang, J.-Y., and Schultheiss, P. M. (September 1963). Block
quantization of correlated gaussian random variables. IEEE
Trans. Communication Systems. CS-11:289–296.
Huffman, D. A. (1951). A method for the construction of min-
Forward prediction
imum redundancy codes. Proc. IRE. 40:1098–1101.
Figure 26 A possible arrangement for a GOP. ISO/IECIS 11172. Information Technology—Coding of Moving
444 Data Compression

Pictures and Associated Audio for Digital Storage Media Up Sayood, K., and Na, S. (November 1992). Recursively indexed
To About 1.5 Mbits/s. quantization of memoryless sources. IEEE Trans. Informa-
ISO/IECIS 13818. Information Technology—Generic Coding tion Theory. IT-38:1602–1609.
of Moving Pictures and Associated Audio Information. Shannon, C. E. (1948). A mathematical theory of communica-
ISO/IECIS 14496. Coding of Moving Pictures and Audio. tion. Bell System Technical J. 27:379–423,623–656.
Linde, Y., Buzo, A., and Gray, R. M. (January 1980). An algo- Shapiro, J. M. (December 1993). Embedded image coding us-
rithm for vector quantization design. IEEE Trans. Commu- ing zerotrees of wavelet coefficients. IEEE Trans. Signal Pro-
nications. COM-28:84–95. cessing. SP-41:3445–3462.
Max, J. (January 1960). Quantizing for minimum distortion. Smith, M. J. T., and Barnwell, T. P., III. (1984). A Procedure for
IRE Trans. Information Theory. IT-6:7–12. Designing Exact Reconstruction Filter Banks for Tree Struc-
Memon, N. D., and Sayood, K. (1995). Lossless Image Com- tured Subband Coders. In Proceedings IEEE International Con-
pression: A Comparitive Study. In Proceedings SPIE Conference ference on Acoustics Speech and Signal Processing. IEEE.
on Electronic Imaging. SPIE. Storer, J. A., and Syzmanski, T. G. (1982). Data compression via
Mintzer, F. (June 1985). Filters for distortion-free two-band textual substitution. J. ACM. 29:928–951.
multirate filter banks. IEEE Trans. Acoustics, Speech, and Sig- Taubman, D. (July 2000). High performance scalable image
nal Processing. ASSP-33:626–630. motion compression with EBCOT. IEEE Trans. Image Pro-
Mitchell, J. L., Pennebaker, W. B., Fogg, C. E., and LeGall, cessing. IP-9:1158–1170.
D. J. (1997). MPEG Video Compression Standard. London/New Weinberger, M., Seroussi, G., and Sapiro, G. (November 1998).
York: Chapman & Hall. The LOCO-I Lossless Compression Algorithm: Principles
Nelson, M. (September 1996). Data compression with the Bur- and Standardization into JPEG-LS. Technical Report HPL-
rows-Wheeler transform. Dr. Dobbs Journal. 98-193, Hewlett-Packard Laboratory.
Nelson, M., and Gailly, J.-L. (1996). The Data Compression Book. Weinberger, M. J., Rissanen, J. J., and Arps, R. (1995). Applica-
California: M&T Books. tions of Universal Context Modeling to Lossless Compres-
Pasco, R. (1976). Source Coding Algorithms for Fast Data Com- sion of Gray-Scale Images. In Proc. Asilomar Conference on Sig-
pression. Ph.D. thesis, Stanford University. nals, Systems and Computers, pp. 229–233. IEEE.
Pennebaker, W. B., and Mitchell, J. L. (1993). JPEG Still Image Welch, T. A. (June 1984). A technique for high-performance
Data Compression Standard. New York: Van Nostrand- data compression. IEEE Computer. 8–19.
Reinhold. Wu, X., and Memon, N. D. (May 1996). CALIC—A context
Rissanen, J. J. (May 1976). Generalized Kraft inequality and based adaptive lossless image coding scheme. IEEE Trans.
arithmetic coding. IBM J. Research and Development. Communications.
20:198–203. Ziv, J., and Lempel, A. (May 1977). A universal algorithm for
Said, A., and Pearlman, W. A. (June 1996). A new fast and effi- data compression. IEEE Trans. Information Theory. IT-
cient coder based on set partitioning in hierarchical trees. 23(3):337–343.
IEEE Trans. Circuits and Systems for Video Technologies. 243–250. Ziv, J., and Lempel, A. (September 1978). Compression of in-
Sayood, K. (2000). Introduction to Data Compression, Second Edi- dividual sequences via variable-rate coding. IEEE Trans. In-
tion. San Mateo, CA: Morgan Kauffman/Academic Press. formation Theory. IT-24(5):530–536.