1. Objective : Reduce the amount of data required to represent an image.
2. It is both an art and a science.
3. It is useful and commercially successful technology in DIP.
4. Need: Reduce the memory and help in increased data transfer per second.
5. Benefits of compression :
a. A 2 hour movie stored without compression in a DVD requires 27 dual layer DVDs of 8.5GB capacity.
b. The time required to transmit a small 128x128x24bit full-colour image over a 56kbps or 12Mbps(broadband) is from 7.0 to 0.03 secs.
6. Compression can reduce transmission time by a factor of 2 to 100 or more.
7. Other areas : televideo conferencing, remote sensing, document and medical imaging, FAX.
8. We study only the most frequently used compression techniques and some industry standards that make them useful.
9. Data compression is the process of reducing the amount of data required to represent a given quantity of information.
10. Data and information are not the same thing.
11. Data are the means by which the information is conveyed.
12. Various amounts of data can be used to represent the same amount of information.
13. Redundant data : representations that contain irrelevant and/or repeated information.
14. Relative data redundancy is obtained from compression ration C ( = b/b’ ) as R = 1 – 1/C where b and b’ represent the number of bits of the same picture before and after compression.
15. Data redundancy in 2D intensity arrays is :
a. Coding redundancy : The 8-bit codes that are used to represent the intensities in most 2-D intensity arrays contain more bits than are needed to represent the intensities.
b. Spatial and temporal redundancy : Pixels of most 2D arrays are spatially correlated. Also in a video, the pixels are temporally correlated.
c. Irrelevant information : Most 2D arrays contain information that is ignored by the human visual system.
16. Coding redundancy is present when the codes assigned to a set of events (such as intensity values) do not take full advantage of the probability of the events.
17. Coding redundancy is almost always present when the intensities of an image are represented using a natural binary code. The reason is that most images are composed of objects that have a regular and somewhat predictable morphology (shape) and reflectance, and are sampled so that the objects being depicted are much larger than the picture elements.
18. The natural consequence is that for most image, certain intensities are more probable than others.
19. A natural binary encoding assigns the same number of bits to both the mot and the least probable values, failing to minimize and resulting in coding redundancy.
20. The compression results from assigning fewer bits to the more probable intensity values than to the less probable one. In the resulting ‘variable length code’ , the image’s most probable intensity is assigned the 1-bit code word while the least probable occurring intensity is assigned the 3-bit code word. Note that the best fixed-length code that can be assigned to the intensities of the image in Eg 8-1 is the natural 2-bit counting sequence but the resulting compression is 4:1 not 4.42:1 which is about 10% less than the 4.42:1 compression of the variable length code.
21. Spatial and temporal redundancy : When an image cannot be compressed by variable length coding alone and when all intensity levels have equal probability but when observations reveal spatial redundancy that can be eliminated by representing the image as a sequency of run-length pairs where each run-length pair specifies the start of a new intensity and the number of consecutive pixels that have that intensity.
22. In most images , pixels are correlated spatially (in both x and y) and in time(t) when the image is part of a video sequence.
23. To reduce the redundancy associated with spatially and temporally correlated pixels , a 2-D intensity array must be transformed into a more efficient but usually ‘non-visual’ representation.
24. When 2D intensity array is converted to run-lengths or the differences between adjacent pixels is used, the transformation is called mapping.
25. A mapping is reversible if the pixels of the original 2D intensity array can be constructed without error from the transformed data set; otherwise the mapping is said to be irreversible.
26. Irrelevant information : Compression by removing ‘superfluous’ data from the set. Eg. A homogeneous gray image can be represented by its average intensity alone – a single 8-bit value.
27. Whether or not this information should be preserved is application dependent. If the information is important (like digital X-ray archive), it should not be omitted; otherwise , the information is redundant and can be excluded for the sake of compression performance.
28. How to decide the bits that are actually needed to represent the information in an image ? Information theory helps.
29. Information theory : Generation of information can be modeled as a probabilistic process that can be measured in a manner that agrees with intuition.
30. A random event E with probability P(E) contains I(E) units of information where I(E) = -log P(E).
31. If an event occurs always P(E) = 1 and hence no information is attached to it.
32. The base of the logarithm decides the units used to measure the information. If base = 2 and P(E) = 0.5, I(E) = 1 bit. Meaning : 1 bit is the amount of information conveyed when one of two possible equally likely events occurs.
33. The entropy of the intensity source H~ = negative summation of Pr(rk)log2Pr(rk) from k=0 to L-1.
34. The amount of entropy and thus information in an image is far from intuitive.
35. Shannon’s first theorem or noiseless coding theorem :
Lim as n tends to infinity of [Lavg,n / n] = H where Lavg,n is the average number of code symbols required to represent all n-symbol groups.
36. Fidelity criteria: Removal of “irrelevant visual” information involves a loss of real or quantitative image information. How to quantify this loss ? There are two ways
a. Objective fidelity criteria
b. Subjective fidelity criteria
37. Objective fidelity criteria : The information loss can be expressed as a mathematical function of the input and output of a compression process. Eg. RMS error between two images. This is a simple and convenient way to evaluate information loss but not meaningful for human.
38. Subjective fidelity criteria : Measuring image quality by subjective evaluations of people by presenting a decompressed image to a cross section of viewers and averaging their evaluation.
39. Subjective evaluations can be as follows : { -3,-2,-1,0,1,2,3} for {much worse, worse, slightly worse, same, slightly better, better, much better} respectively.
40. Care must be taken while choosing the results of the above two criteria. Because, a low rms error may also be due to an artificially generated image.
41. Image compression models : The model of a image compression and decompression consists of two distinct functional components : an encoder and a decoder. This can be done using hardware and/or software.
42. Codec : A device/program capable of both encoding and decoding.
43. Compression process has three independent operations : mapping , quantizing and symbol coding.
a. Mapping is a reversible process and transforms f(x,y) to a non-visual format designed to reduce spatial and temporal redundancy.
b. Quantising is an irreversible process to reduce accuracy of the mapper output in accordance with a preestablished fidelity criterion. The goal is to keep irrelevant information out of the compressed representation.
c. Symbol coder is reversible and generates a fixed-length or variable-length code to represent the quantiser output and maps the output according to the code.
44. Shortest code words are assigned the most frequently occurring quantizer output values – thus minimizing coding redundancy.
45. The decoder contains symbol decoder and inverse mapper. Obviously there is no de-quantiser as it is an irreversible process.
46. In video applications, decoded output frames are maintained in an internal frame store and used to reinsert the temporal redundancy that was removed at the encoder.
47. Image formats, containers and compression standards :
a. Image file format is a standard way to organize and store image data. It defines how the data is arranged and the type of compression – if any – that is used.
b. Image container is similar to a file format but handles multiple types of image data.
c. Image compression standards define procedures for compressing and decompressing images.
48. Standards for continuous tone still image : JPEG, JPEG-LS, JPEG 2000, BMP, GIF, PDF, PNG, TIFF.
49. VIDEO Standards : DV, H.261, H.262, H.263, H.264, MPEG-1, MPEG-2, MPEG-4, MPEG-4 AVC, AVS, HDV, M-JPEG, QUICK-TIME, VC-1, WMV9.
50. BASIC COMPRESSION STANDARDS :
a. Huffman coding
b. Golomb coding
c. Arithmetic coding
d. Lempel-Ziv-Welch (LZW) coding
e. Run-Length coding
f. Bit-plane coding
g. Block Transform coding
h. Predictive coding :- (i) lossless (ii) lossy
i. Wavelet coding
