Data Compression Lec #3

The primary types of redundancy can be found in image:
1. Coding: Coding redundancy occurs when the data used to represent the image not utilized in an optimal manner. For example, if we have an 8 bits/ pixel image that allows 256 gray- level value, but the actual image contains only 16 gray-level values, this is a suboptimal coding, where only 4 bits/pixel are actually needed.
2. Interpixel (Spatial Redundancy): Interpixel redundancy occurs because adjacent pixels tend to be highly correlated. This is a result of the fact that in most images the brightness levels do not change rapidly, but change gradually, so that adjacent pixel values tend to be relatively close to each other in value (for video, or motion images, this concept can be extended to include interframe redundancy, redundancy between frames of image data).
3. Psychovisual redundancy: Psychovisual redundancy refers to the fact that some information is more important to the human visual system than other types of information. For example, we can only perceive spatial frequencies below about 50 cycles per degree so that any higher-frequency information is of little interest to us.

Entropy
Shannon borrowed the definition of entropy from statistical physics to capture the notion of how much information is contained in a and their probabilities. For a set of possible messages, Shannon defined entropy as,
. (1)
Where p(s) is the probability of message s. The definition of Entropy is very similar to that in statistical physics- in physics S is the set of possible states a system can be in and p(s) is the probability the system is in state (s). We might remember that the second law of thermodynamics basically says that the entropy of a system and its surroundings can only increase.
Getting back to messages, if we consider the individual messages , Shannon defined the notion of the self information of a message as
. (2)
This self information represents the number of bits of information contained in it and, roughly speaking, the number of bits we should use to send that message. The equation says that messages with higher probability will contain less information.
The entropy is simply a weighted average of the information of each message, and therefore the average number of bits of information in the set of messages. Larger entropies represent more information.
Here are some examples of entropies for different probability distributions over five messages.




Basic Concepts in Data Compression
In this section the basic concepts of data compression are shown:-

The Unary Code
The unary code of the non-negative integer n is defined as n-1 ones followed by one zero or, alternatively, as n-1 zeros followed by a single one.
Table : Some Unary Codes
N Code Alt. Code
1 0 1
2 10 01
3 110 001
4 1110 0001
5 11110 00001


Entropy Coding
We can define the entropy of a signal symbol ai as –Pi log2Pi. This is the smallest number of bits needed, on the average, to represent the symbol.
The amount of information contained in one, base-n symbol is:

This quantity is called the entropy of the data being transited.
The entropy of the data depends on the individual probabilities Pi, and is smallest when all n probabilities are equal.
Data Compression Strategies
There are different ways that data compression techniques can be categorized, smith gives a compression classification as below:
a. Lossless or Lossy
Lossless Lossy
RLE JPEG
Huffman MPEG
Arithmetic Vector quantization
Quadtree

b. Fixed or variable group size
Method Group Size
Input Output
Huffman Fixed Variable
Arithmetic Variable Variable
RLE, LZW Variable Fixed

Most data compression programs operate by taking a group of data from the original file and compressed it in some way, and then writing the compressed group to the output file.