Video compression has become ever more important in multimedia and game development. This is even more so with the introduction of a new generation of web devices like iPhones, iTunes and many Wi Fi handheld devices. Such products have employed video compression technologies to save storage space or transmission bandwidth. A video clip could hardly be played in any toy if it were not compressed. Currently, the leading video compression standards are MPEG-4 visual and H.264. These standards and the associated technologies are the result of the effort and work of tens of thousands of people over many years. We are fortunate and thankful that these methodologies are disclosed and could be found in many open literatures. In this chapter, we give you a step-by-step guide on compressing video data so that you can customize the compression method for your own game application. ( At this point, we only present the video compression technologies, dismissing the part involving audio. We shall discuss audio compression in a later Chapter. )
Before you read on, try to answer the question: "What is information?" Like most programmers, you may be surprised to find that after so many years of studying or working in the area of information, you really could not answer the question unless you have taken a course in information theory or have studied the subject before. To understand how data compression works, we need to first understand what information is.
Many people confuse information with data and may mistaken that information is the same as data. Actually, data is different from information. Data are used to represent information. We can have a large amount of data which contains very little information. For example, we can use a pseudo random number generator to generate an abundant amount of data, tens of millions of bytes. However, all these data contain very little information because if we want to transmit the information represented by these data to another person, all we need to do is to transmit the simple equation of the pseudo random number generator. The receiver can generate the huge amount of data identical to ours. As another example, when we watch news, we feel that we receive a significant amount of information if the news gives us surprises, informing us something unexpected. On the other hand, if your friend tells you that she will eat dinner tomorrow, you do not feel receiving much information as that's what you expect. For instance, consider the following two sentences,
- India will elect her next governing party by universal suffrage.
- China will elect her next governing party by universal suffrage.
These two sentences have exactly the same amount of data ( characters ). However, there is a big difference in information the two sentences would convey. Should the event happen, the first one does not give us any surprise and would not appear in any newspaper as that's what we would expect. However, the second one would give a big shock to the world and every newspaper would report the event; it gives us a significant amount of information. So from these examples, we can see that information relates to unpredictability and surprises. A perfectly predictable message conveys no information. To quantify the measure of information, scientists borrow the concept of entropy from physics. We know that in physics, entropy is a measure of disorder or unpredictability. In information systems, we also refer to information carried by a message as entropy.
In 1948, Shannon defined the information I(E) conveyed by an event E, measured in bits as
Shannon defines entropy in terms of a discrete random variable X, with possible states (or outcomes) x1,...,xn as:
where 
is the probability of the ith outcome of X.
To define the entropy of an information system more precisely, we need to establish some models to represent the system. One of the simplest model that people often use is referred to as discrete memoryless source ( DMS ) which is a generator sending out symbols, one at a time; the set of symbols is known as an alphabet. Each symbol's probability of occurrence is known and we can calculate its information using Shannon's formula presented above. In this case, if symbol si occurs, we obtain an amount of information equal to
| si | p(si) | I(si) |
|---|---|---|
| a | 0.7 | 0.515 bits |
| b | 0.1 | 3.322 |
| c | 0.2 | 2.322 |
| d | 0.2 | 2.322 |
The entropy H(S) of an information source S such as a DMS can be regarded as the average amount of information conveyed by each symbol output by the source and is defined as
p(si) I(si)
=
- p(si) log ( p(si))
DMS can be regarded as a zeroth order Markov source, which is restrictive for many applications. A more general type of information source is one in which the occurrence of a source symbol si may depend upon m preceding symbols. Such a source is referred to as mth-order Markov source. For a first-order Markov source (one in which the probability of selecting a symbol is dependent only on the immediately preceding symbol ), the entropy is defined as:
For a second order Markov source, the entropy is
A video consists of a sequence of images ( we ignore the sound component in all our discussion here ). An image can be regarded as a tool to convey information. An image may consist of a lot of data but as we have discussed above it may not carry much information. We have learned that the more accurate we can predict the occurrence of a symbol ( or data ), the less information it conveys. There could be a lot of redundancies in an image and we can predict most of the rest of the features by examining part of it. Also there could be a lot of correlations between several consecutive images and we can make a fairly good prediction of one from the others. Moreover, as you'll see later, an image can also be expressed in the frequency domain. Our eyes are not very sensitive to the high frequency components and we can throw away them without causing much visual distortion; since information is lost in the compression process, we refer to this kind of compression as lossy compression, in which the exact original data cannot be recovered. On the other hand if no information is loss in the process, it is referred to as lossless compression and the exact original data can be recovered.