There are two types of coding: Entropy coding and Source coding.

In entropy coding, a characteristic called redundancy is used to decrease the size of the file. There are usually many repeating characters in a file, and in entropy coding, these repeated symbols are just noted down and instead of repeating them at every pixel, the positions of these pixels are recorded and they are all noted to have the same symbol (this is only an example of entropy coding, called run-length encoding, RLE). Thus, there is no loss of information in entropy coding. This kind of coding is also called non-lossy coding. For more information, go to the related links section. Two examples of entropy coding are given below.

In Run-Length Encoding, which is a special kind of entropy coding, repetitive symbols/characters are collected and the pixels/positions where they are repeated are written down into the coded file. In the case of video files, repeatedly unchanging scenes can be encoded together. We can use differential encoding, as shown below.
 

This is a very smart non-lossy technique. To illustrate this procedure, consider a sequence of frames. For example, if in a sequence of images, Homer Simpson is walking through Springfield on a very quiet day, the rest of Springfield (the pixels) can be coded into the file with the information that those pixels do not change for a few frames, while Homer's position is changing from pixel to pixel. In differential encoding, as the name suggests, this is done by noting down the change between frames, instead of the actual values of, for example, the colours. This means, for example, that we could just have a lot of zeroes in the coded images, and this can now be further compressed by using RLE!!!
 

• This type of coding is an example of variable length encoding (VLE), in which different symbols have codes that aren't of the same length. The general principle: frequently occurring characters are coded with shorter patterns (the Morse Code is an example of Huffman encoding)
• The major problem in VLE: If there are some codes which have the same ending as the beginning as some other codes, we can't differentiate between codes!
• Solution: Make no code be a prefix of another code. An example is shown below, and this is used in Huffman encoding

Suppose that we have the five symbols A, B, C, D and E recurring in a file, with the percentage of recurrence 30%, 30%, 10%, 15% and 15% respectively. The most recurring symbols are given the MSB (most significant bit), and this is the first `1', as shown below for A and B). Since in this particular example they have equal probability of recurrence, it doesn't matter which one of them gets the higher LSB (lowest significant bit). A is thus assigned the code 11 and B is assigned the code 10. There is no repitition. For example, if the string of symbols ABDC occurs somewhere in the file, it will be translated into 11,10,010,011. Since there are no symbols that have the code `1', we know that the first code is UNIQUELY for A, and since there are no symbols that have the code `01', we know that the third code is for D, and so on.

In source coding, information is reduced by taking advantage of the limitations of the human eye and ear. An example is the YUV colour system, which encodes the chrominance (U & V, the changes in colour) with lesser resolution than the luminance (Y, the changes in brightness), because the human eye is less sensitive to chrominance than luminance. There is always loss in information in source coding (hence `lossy'), meaning that the decompressed file will not have all the information that the original file had. As far as I know, .tiff (tagged image file format) files use only entropy coding, so they retain all the information of the original file, and thus are also very very big in size on disk. JPEG files use a kind of coding which is a mixture of entropy and source coding. The last step in these compression algorithms is always entropy coding. This sort of coding is called hybrid coding. The different methods are shown in the picture above, with examples for each type of coding.
 

As an illustration for entropy coding, consider the red image below. It is just a picture of a red background, meaning each pixel has the same RGB value, so from the above text we would imagine that the encoded image would be very very small, with just the pixel numbers all included with the same symbol. To show this, I use Winzip to compress this file. As mentioned previously, compression software such as this and gzip and tar HAVE to use entropy coding, otherwise information from text files will also be lost, which is not desirable for this application. So this is an example of entropy coding.

Now, also compare two .jpg files of similar size on disk....
 
 

The red image above has a file size of 32.2 KB and a picture of me taken in 1999 has a file size of 32.5 KB.
When zipped using Winzip (try this yourself!), the sizes are reduced to 0.663 KB and 32.5 KB (almost no change in the second one, and a drastic change in the first one). This illustrates how entropy coding can use pixel redundancy to its advantage - the first image is just a red background, so each pixel is the same, so that a zipped file should just contain the information that there are NxM pixels, and each pixel has the same colour, so that on uncompressing this file, you will definitely get back the original image.

All file compression utilities HAVE to use entropy coding if we need the file to be retrieved in its entirety on uncompression!

Just to prove the point that the JPEG format itself uses compression: the first image has actually been reduced to HALF of its actual size to fit in this window (if you download this image and load it in another page, you will see for yourself how big it is!), while the second image - the picture of me - has smaller dimensions but still has enough information in it so that it can not be compressed by as large an amount as the first image was.

As an example of the advantage of lossy coding, consider a sound file. Speech is the variation of amplitude and frequency with time. If this is Fourier transformed, we get variation of the amplitude of Fourier modes. Consider the largest contributing Fourier amplitudes (about 3-5 usually). These are normally enough to fool the human ear into thinking that the original file has been reproduced! These amplitudes are called the formants for compression.
 
 

• This is a lossy technique, writes Y and (UV) as cosine series (``low frequency'' = average colour of the picture, ``high frequency'' = peaks and sharp changes in brightness and/or colour)
• First few peaks satisfactorily reproduce image (usually!)
• This transform is the basis of JPEG and MPEG-1 standards. For more information on the DCT, follow this link.

Go to the next page, or use one of the following quick links:

Main Page
Motivation For Compression - Some True Stories
A Brief History of Compression (heheh - brief, compress... get it?)
Requirements From Any Compression Algorithm
Data Compression Fundamentals
Some Compression Techniques
Video Compression Techniques: The MPEG-1 Standard
The Future: MPEG-4 And MPEG-7
Related Links
 
 
 

Contact Me: sundar@pha.jhu.edu
Copyright © Sundar Srinivasan 2002