Every slide you need, in plain words, with every Huffman, arithmetic, LZW, RLE, Golomb and RMSE past question solved the way you write it in the answer script, and a step-by-step simulator next to each method.
Slide 3. Data compression is the process of reducing the amount of data required to represent a given quantity of information. Data and information are not the same thing: various amounts of data can represent the same information. Data that is irrelevant or repeated is called data redundancy.
Slide 4. The goal of image compression is to reduce the amount of data required to represent a digital image. It is very important for image storage and image transmission. Compression is achieved by encoding data with an appropriate encoding scheme.
Slide 5. Applications: internet, businesses, multimedia, satellite imaging, medical imaging.
SD TV, 2 hours, 720×480 colour frames at 30 frames/s, 3 bytes per pixel:
One second = 30 × (720 × 480) × 3 = 31,104,000 bytes ≈ 31 MB.
Two hours = 31,104,000 × 60² × 2 ≈ 2.24 × 1011 bytes = 224 GB. That needs twenty-seven 8.5 GB dual-layer DVDs, so the video must be compressed by a factor of about 26.3 to fit on one DVD.
HD TV (1920×1080) needs even higher compression. Web images of 128×128 colour take 7.0 to 0.03 s to download over 56 kbps to 12 Mbps links. A 1 GB flash memory holds only about 41 uncompressed 8-megapixel photos.
What is image compression? Why do we need it?
Image compression is the process of reducing the amount of data required to represent a digital image, by removing redundant (repeated or irrelevant) data while keeping the information.
We need it because raw images and videos are huge: for example a 2-hour SD video needs about 224 GB uncompressed, which is too big to store or send. Compression saves storage space and transmission time/bandwidth (internet, multimedia, satellite and medical imaging).
Slide 8. Data redundancy is unnecessary or repetitive data in an image file; removing it reduces the file size without losing essential information. It is a mathematically quantifiable entity. If n1 and n2 are the numbers of information-carrying units (e.g. bits) in the original and compressed data sets:
| case | CR | RD | meaning |
|---|---|---|---|
| n1 = n2 | 1 | 0 | the original contains no redundant data |
| n1 ≫ n2 | → ∞ | → 1 | highly compressed, highly redundant data |
| n1 ≪ n2 | → 0 | → −∞ | undesirable: the 'compressed' file is bigger |
Slide 9. A practical ratio such as CR = 10 (10:1) means the original has 10 bits for every 1 bit of the compressed data. Then RD = 1 − 1/10 = 0.9: 90% of the data in the original was redundant.
An uncompressed grayscale image is 512×512 with 8 bits/pixel. After compression the file is 64 KB. Compute the compression ratio.
n1 = 512 × 512 × 8 = 2,097,152 bits.
n2 = 64 KB = 64 × 1024 bytes × 8 = 524,288 bits.
CR = n1/n2 = 2,097,152 / 524,288 = 4, i.e. 4:1. (RD = 1 − 1/4 = 0.75: 75% of the original data was redundant.)
A 512×512, 8-bit image with entropy 5.3 bits/pixel is Huffman coded. What is the maximum compression that can be expected?
Entropy is the lower limit of the average code length: no lossless code can use fewer than H = 5.3 bits/pixel on average (slide 40). So the best possible Lavg is 5.3 bits/pixel.
Cmax = 8 / 5.3 = 1.509 (about 1.51:1). In bits: 512 × 512 × 8 = 2,097,152 bits against at least 512 × 512 × 5.3 ≈ 1,389,363 bits.
Slide 10. Three basic redundancies can be identified and exploited. Compression is achieved when one or more of them are reduced or eliminated:
Slide 11. Elements of an encoding scheme: code, a list of symbols (letters, numbers, bits); code word, a sequence of symbols that represents one piece of information or gray level; word length, the number of symbols in each code word. Example: 3-bit binary code 0 = 000, 1 = 001, …, 7 = 111.
If an image uses fixed-length codes for every pixel value although some values occur far more often than others, storage is wasted.
Slide 12. Idea: variable-length coding. Assign shorter code words to the most probable pixel values and longer code words to less probable ones. The process is reversible (lossless). The histogram gives the frequency of each gray level.
Slide 14. With p(rk) = nk/n and l(rk) bits for rk:
A computer-generated 256×256, 8-bit image uses only four gray levels:
| rk | pr(rk) | Code 1 | l1 | Code 2 | l2 |
|---|---|---|---|---|---|
| 87 | 0.25 | 01010111 | 8 | 01 | 2 |
| 128 | 0.47 | 10000000 | 8 | 1 | 1 |
| 186 | 0.25 | 11000100 | 8 | 000 | 3 |
| 255 | 0.03 | 11111111 | 8 | 001 | 3 |
| others | 0 | — | 8 | — | 0 |
Code 1 (fixed): 8 bits/pixel, total 256 × 256 × 8 bits.
Code 2 (variable): Lavg = 0.25×2 + 0.47×1 + 0.25×3 + 0.03×3 = 1.81 bits; total 256 × 256 × 1.81 bits.
C = 8/1.81 ≈ 4.42; RD = 1 − 1/4.42 = 0.774: 77.4% of the data in the first image was redundant.
| rk | pr(rk) | Code 1 | l1 | Code 2 | l2 |
|---|---|---|---|---|---|
| r0 = 0 | 0.19 | 000 | 3 | 11 | 2 |
| r1 = 1/7 | 0.25 | 001 | 3 | 01 | 2 |
| r2 = 2/7 | 0.21 | 010 | 3 | 10 | 2 |
| r3 = 3/7 | 0.16 | 011 | 3 | 001 | 3 |
| r4 = 4/7 | 0.08 | 100 | 3 | 0001 | 4 |
| r5 = 5/7 | 0.06 | 101 | 3 | 00001 | 5 |
| r6 = 6/7 | 0.03 | 110 | 3 | 000001 | 6 |
| r7 = 7/7 | 0.02 | 111 | 3 | 000000 | 6 |
Lavg = 2(0.19) + 2(0.25) + 2(0.21) + 3(0.16) + 4(0.08) + 5(0.06) + 6(0.03) + 6(0.02) = 2.7 bits.
CR = 3/2.7 = 1.11; RD = 1 − 1/1.11 = 0.099: 9.9% of the data was redundant.
When the value of a pixel can be obtained from its neighbouring pixels, the redundancy is called inter-pixel or spatial redundancy. Intensities of each pixel may correlate to their neighbours, so much information is unnecessarily replicated.
Slide 18. A computer-generated 256×256×8 image of horizontal lines: each line has one random gray level, so the histogram is uniform (all 256 levels equally likely). Pixels are maximally correlated horizontally but independent vertically. This image cannot be compressed with variable-length coding.
Slide 19. It can be represented as run-length pairs (intensity value, number of pixels with that intensity). Each of the 256 lines becomes one pair (value, 256):
Many images hold information that is ignored by the human visual system (HVS); try to remove this extraneous data. Slide 20: a 256×256×8 image that looks like one flat gray. Its histogram is a narrow spike, and it can be represented by a single average gray level:
Slide 21. However, this coarse quantization may remove useful "invisible" information: after histogram equalization the "flat" image shows a hidden pattern.
Slide 22. Summary: coding redundancy, the image does not need all 8 bits; spatial redundancy, information is unnecessarily replicated; irrelevant information, information that is not useful.
| type | removes | methods |
|---|---|---|
| Error-free (lossless) | coding redundancy | variable-length coding: Huffman, Golomb, arithmetic |
| Error-free (lossless) | spatial / inter-pixel redundancy | LZW coding, run-length coding |
| Lossy | irrelevant (psychovisual) information | information is lost; quality judged by fidelity criteria |
What is data redundancy in images? Name its three main types. Discuss the redundancy type that can be overcome using variable-length code words. How do you calculate relative data redundancy?
Data redundancy is unnecessary or repeated data in an image file which, when removed, reduces the file size without losing essential information. It is a mathematically quantifiable entity.
Three types: (1) coding redundancy, (2) spatial / inter-pixel redundancy, (3) psychovisual redundancy (irrelevant information).
Coding redundancy is overcome with variable-length codes. A fixed-length code gives every gray level the same number of bits (e.g. 8), although some levels occur much more often. Variable-length coding (e.g. Huffman) gives shorter code words to more probable gray levels and longer ones to rare levels, so the average length Lavg = Σ l(rk) p(rk) drops below 8. Example (slide 15): Lavg = 1.81 bits instead of 8. This is reversible, so lossless.
Relative data redundancy: with n1 and n2 the bits in the original and compressed data, CR = n1/n2 and RD = 1 − 1/CR. Example: CR = 8/1.81 = 4.42 gives RD = 0.774, so 77.4% of the data was redundant.
How many types of data redundancy are there in an image? Describe each briefly. How can compression be implemented? How do you calculate the percentage of redundant data after compression?
There are three types of data redundancy:
Implementation: compression is achieved when one or more of these redundancies are reduced or eliminated, by encoding the data with a suitable scheme (compress → store/transmit → decompress).
Percentage redundant: CR = n1/n2, RD = 1 − 1/CR, and the percentage of redundant data = RD × 100%. Example: CR = 10 → RD = 0.9 → 90% redundant.
Slide 24. Huffman coding is a lossless compression algorithm, the most popular technique for removing coding redundancy. It is variable-length: most frequent symbols get shorter codes, rare symbols longer codes. Widely used in JPEG. The resulting code is optimal.
Slide 25. Steps:
Probabilities: a1 = 0.1, a2 = 0.4, a3 = 0.06, a4 = 0.1, a5 = 0.04, a6 = 0.3. Find the Huffman code.
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 | Reduction 3 | Reduction 4 |
|---|---|---|---|---|---|---|
| a2 | 0.4 | 1 | 0.4 1 | 0.4 1 | 0.4 1 | 0.6 0 |
| a6 | 0.3 | 00 | 0.3 00 | 0.3 00 | 0.3 00 | 0.4 1 |
| a1 | 0.1 | 011 | 0.1 011 | 0.2 010 | 0.3 01 | |
| a4 | 0.1 | 0100 | 0.1 0100 | 0.1 011 | ||
| a3 | 0.06 | 01010 | 0.1 0101 | |||
| a5 | 0.04 | 01011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| a2 | 0.4 | 1 | 1 | 0.4 |
| a6 | 0.3 | 00 | 2 | 0.6 |
| a1 | 0.1 | 011 | 3 | 0.3 |
| a4 | 0.1 | 0100 | 4 | 0.4 |
| a3 | 0.06 | 01010 | 5 | 0.3 |
| a5 | 0.04 | 01011 | 5 | 0.2 |
Average length Lavg = Σ l·p = (0.4)(1) + (0.3)(2) + (0.1)(3) + (0.1)(4) + (0.06)(5) + (0.04)(5) = 2.2 bits/symbol.
Entropy H = −Σ p log2 p = −(0.4)log2(0.4) + −(0.3)log2(0.3) + −(0.1)log2(0.1) + −(0.1)log2(0.1) + −(0.06)log2(0.06) + −(0.04)log2(0.04) = 2.1435 bits/symbol.
Coding efficiency η = H / Lavg = 2.1435 / 2.2 = 97.43%.
Compression ratio CR = n1/n2 = 3 / 2.2 = 1.3636. Relative redundancy RD = 1 − 1/CR = 1 − 1/1.3636 = 0.2667 → 26.67% of the data was redundant.
As on slide 34: n1 = 3, n2 = 2.2, C = 3/2.2 = 1.364, RD = 0.267. 26.7% fewer bits: coding redundancy eliminated. Yes, it reduces the total bit count.
Try it, step by step: every sort, merge and re-sort, then the codes passed back column by column (slides 26–33).
Slide 35. Short-cut: draw the tree directly: join the two smallest, label the branches 0 (upper) and 1 (lower), keep joining, then read each code from the root down.
A 3-bit grayscale image has A (dark gray) 0.45, B (medium gray) 0.13, C (light gray) 0.12, D (white) 0.16, E (black) 0.09, F (very light gray) 0.05. Find the Huffman code.
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 | Reduction 3 | Reduction 4 |
|---|---|---|---|---|---|---|
| A | 0.45 | 1 | 0.45 1 | 0.45 1 | 0.45 1 | 0.55 0 |
| D | 0.16 | 000 | 0.16 000 | 0.25 01 | 0.3 00 | 0.45 1 |
| B | 0.13 | 010 | 0.14 001 | 0.16 000 | 0.25 01 | |
| C | 0.12 | 011 | 0.13 010 | 0.14 001 | ||
| E | 0.09 | 0010 | 0.12 011 | |||
| F | 0.05 | 0011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| A | 0.45 | 1 | 1 | 0.45 |
| B | 0.13 | 010 | 3 | 0.39 |
| C | 0.12 | 011 | 3 | 0.36 |
| D | 0.16 | 000 | 3 | 0.48 |
| E | 0.09 | 0010 | 4 | 0.36 |
| F | 0.05 | 0011 | 4 | 0.2 |
Average length Lavg = Σ l·p = (0.45)(1) + (0.13)(3) + (0.12)(3) + (0.16)(3) + (0.09)(4) + (0.05)(4) = 2.24 bits/symbol.
Entropy H = −Σ p log2 p = −(0.45)log2(0.45) + −(0.13)log2(0.13) + −(0.12)log2(0.12) + −(0.16)log2(0.16) + −(0.09)log2(0.09) + −(0.05)log2(0.05) = 2.2199 bits/symbol.
Coding efficiency η = H / Lavg = 2.2199 / 2.24 = 99.10%.
Compression ratio CR = n1/n2 = 3 / 2.24 = 1.3393. Relative redundancy RD = 1 − 1/CR = 1 − 1/1.3393 = 0.2533 → 25.33% of the data was redundant.
Try it, step by step: the slide 36 class work.
Slide 37. Applications: file compression (ZIP, GZIP), image compression (PNG), multimedia (part of MP3 and JPEG), data transmission (efficient coding for bandwidth-limited channels).
Slide 38. Is Huffman lossless? Yes. Every code word is unique and no code word is the prefix of another (prefix code), so the decoder reads the bits and recovers every symbol exactly. Nothing is thrown away; only the coding redundancy is removed.
Slide 39. Information theory. A random event E with probability P(E) carries
units of information. Higher uncertainty means higher information content. For a source of events a1 … aJ with probabilities P(aj), the average information per event is the entropy:
Slide 40. Treating pixel intensities as random events, the normalized histogram approximates the probabilities, and the image entropy is H̃ = −Σ Pr(rk) log2 Pr(rk) bits/pixel. Entropy is the measure of the average information in an image, and it is not possible to encode any image with fewer than H bits/pixel (losslessly).
H = −[0.25 log2 0.25 + 0.47 log2 0.47 + 0.25 log2 0.25 + 0.03 log2 0.03]
≈ −[0.25(−2) + 0.47(−1.09) + 0.25(−2) + 0.03(−5.06)] ≈ 1.6614 bits/pixel.
Compare: the variable-length code used 1.81 bits, close to this limit.
Slides 42–43. The star image has H = 1.6614, the random-lines image H = 8, the flat-looking image H = 1.566. Entropy (information) and visual impression are far from intuitive.
Uniform distribution, 3-bit image (L = 8), every level has p = 1/8: H = −Σ (1/8) log2(1/8) = 3 bits/pixel. The natural 3-bit code is already optimal; a uniform distribution has the highest entropy.
Certain event, every pixel is 2: p(2) = 1, so H = −(1) log2(1) = 0 bits/pixel. The gray level is known in advance, so one value codes the whole image.
Recipe for every image question: count each gray level → probability = count/N → Huffman table → code table → Lavg → entropy → CR = (original bits)/Lavg → RD. Lossless? Always yes for Huffman.
(ii) Encode the 1-D run AAAAABBBCCDAA with RLE (symbol, count). (iii) A row of 100 pixels alternates ABAB… (50 A, 50 B). Explain how RLE performs and compute the encoded length, the count stored as one byte. (iv) Symbols A: 0.4, B: 0.3, C: 0.2, D: 0.1. Build a Huffman code, compute the average code length and compare it with the entropy.
(ii) Group equal neighbours: AAAAA | BBB | CC | D | AA → (A,5) (B,3) (C,2) (D,1) (A,2). 13 symbols become 5 pairs.
(iii) Every run has length 1, so the row becomes 100 pairs (A,1)(B,1)(A,1)… With 1 byte for the symbol and 1 byte for the count, encoded length = 100 × 2 = 200 bytes against 100 bytes originally (one byte per pixel). CR = 100/200 = 0.5: the data doubles. RLE performs badly here: it only helps when there are long runs; small runs result in expansion instead of compression (slide 109).
(iv)
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 |
|---|---|---|---|---|
| A | 0.4 | 1 | 0.4 1 | 0.6 0 |
| B | 0.3 | 00 | 0.3 00 | 0.4 1 |
| C | 0.2 | 010 | 0.3 01 | |
| D | 0.1 | 011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| A | 0.4 | 1 | 1 | 0.4 |
| B | 0.3 | 00 | 2 | 0.6 |
| C | 0.2 | 010 | 3 | 0.6 |
| D | 0.1 | 011 | 3 | 0.3 |
Average length Lavg = Σ l·p = (0.4)(1) + (0.3)(2) + (0.2)(3) + (0.1)(3) = 1.9 bits/symbol.
Entropy H = −Σ p log2 p = −(0.4)log2(0.4) + −(0.3)log2(0.3) + −(0.2)log2(0.2) + −(0.1)log2(0.1) = 1.8464 bits/symbol.
Coding efficiency η = H / Lavg = 1.8464 / 1.9 = 97.18%.
Lavg = 1.9 is just above H = 1.8464: Huffman is within 0.0536 bits of the theoretical minimum (efficiency 97.18%). A fixed-length code would need 2 bits.
Try it, step by step: SP25 (iv).
Try it, step by step: SP25 (ii): the runs found one by one.
5×5, 8-bit image. (i) Table of frequencies and histogram (ii) minimum number of bits per symbol (iii) Huffman code for each symbol (iv) average number of bits per symbol.
| 180 | 160 | 160 | 140 | 120 |
| 110 | 110 | 120 | 140 | 120 |
| 110 | 140 | 120 | 120 | 140 |
| 120 | 160 | 160 | 170 | 170 |
| 170 | 120 | 110 | 140 | 110 |
(i) N = 25.
| Symbol (gray level) | Count | Probability = count/N |
|---|---|---|
| 120 | 7 | 7/25 = 0.28 |
| 110 | 5 | 5/25 = 0.2 |
| 140 | 5 | 5/25 = 0.2 |
| 160 | 4 | 4/25 = 0.16 |
| 170 | 3 | 3/25 = 0.12 |
| 180 | 1 | 1/25 = 0.04 |
(ii) 6 different gray levels appear, so a fixed-length code needs ⌈log2 6⌉ = 3 bits per symbol. The theoretical minimum average (entropy) is H = −Σ p log2 p = 2.4188 bits/symbol; no lossless code can do better.
(iii)–(iv)
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 | Reduction 3 | Reduction 4 |
|---|---|---|---|---|---|---|
| 120 | 0.28 | 01 | 0.28 01 | 0.32 00 | 0.4 1 | 0.6 0 |
| 110 | 0.2 | 10 | 0.2 10 | 0.28 01 | 0.32 00 | 0.4 1 |
| 140 | 0.2 | 11 | 0.2 11 | 0.2 10 | 0.28 01 | |
| 160 | 0.16 | 000 | 0.16 000 | 0.2 11 | ||
| 170 | 0.12 | 0010 | 0.16 001 | |||
| 180 | 0.04 | 0011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| 120 | 0.28 | 01 | 2 | 0.56 |
| 110 | 0.2 | 10 | 2 | 0.4 |
| 140 | 0.2 | 11 | 2 | 0.4 |
| 160 | 0.16 | 000 | 3 | 0.48 |
| 170 | 0.12 | 0010 | 4 | 0.48 |
| 180 | 0.04 | 0011 | 4 | 0.16 |
Average length Lavg = Σ l·p = (0.28)(2) + (0.2)(2) + (0.2)(2) + (0.16)(3) + (0.12)(4) + (0.04)(4) = 2.48 bits/symbol.
Entropy H = −Σ p log2 p = −(0.28)log2(0.28) + −(0.2)log2(0.2) + −(0.2)log2(0.2) + −(0.16)log2(0.16) + −(0.12)log2(0.12) + −(0.04)log2(0.04) = 2.4188 bits/symbol.
Coding efficiency η = H / Lavg = 2.4188 / 2.48 = 97.53%.
Compression ratio CR = n1/n2 = 8 / 2.48 = 3.2258. Relative redundancy RD = 1 − 1/CR = 1 − 1/3.2258 = 0.6900 → 69.00% of the data was redundant.
Try it, step by step: SP24, built from the counts (probabilities shown as count/25).
4×5, 6-bit image, every row [3, 10, 3, 21, 34]. (i) Compress with Huffman coding and calculate the compression ratio. (ii) How much data was redundant? Was any data lost? (iii) A 512×512 8-bit image with entropy 5.3 bits/pixel is Huffman coded: maximum compression expected?
(i) N = 20.
| Symbol (gray level) | Count | Probability = count/N |
|---|---|---|
| 3 | 8 | 8/20 = 0.4 |
| 10 | 4 | 4/20 = 0.2 |
| 21 | 4 | 4/20 = 0.2 |
| 34 | 4 | 4/20 = 0.2 |
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 |
|---|---|---|---|---|
| 3 | 0.4 | 1 | 0.4 1 | 0.6 0 |
| 10 | 0.2 | 01 | 0.4 00 | 0.4 1 |
| 21 | 0.2 | 000 | 0.2 01 | |
| 34 | 0.2 | 001 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| 3 | 0.4 | 1 | 1 | 0.4 |
| 10 | 0.2 | 01 | 2 | 0.4 |
| 21 | 0.2 | 000 | 3 | 0.6 |
| 34 | 0.2 | 001 | 3 | 0.6 |
Average length Lavg = Σ l·p = (0.4)(1) + (0.2)(2) + (0.2)(3) + (0.2)(3) = 2 bits/symbol.
Entropy H = −Σ p log2 p = −(0.4)log2(0.4) + −(0.2)log2(0.2) + −(0.2)log2(0.2) + −(0.2)log2(0.2) = 1.9219 bits/symbol.
Coding efficiency η = H / Lavg = 1.9219 / 2 = 96.10%.
Compression ratio CR = n1/n2 = 6 / 2 = 3.0000. Relative redundancy RD = 1 − 1/CR = 1 − 1/3.0000 = 0.6667 → 66.67% of the data was redundant.
Original = 20 × 6 = 120 bits; Huffman = 20 × 2 = 40 bits; CR = 3.0000.
(ii) RD = 1 − 1/3 = 0.6667: 66.7% of the data was redundant. No data was lost: Huffman coding is lossless (a prefix code, decoded exactly).
(iii) Cmax = 8/5.3 = 1.509 (see above).
Try it, step by step: SP23 (i).
4×5, 6-bit image. (i) Compress using Huffman coding (ii) compress using run-length coding (iii) compression ratio of (i) and (ii).
| 3 | 10 | 3 | 24 | 35 |
| 3 | 10 | 10 | 24 | 3 |
| 3 | 10 | 10 | 24 | 35 |
| 3 | 10 | 10 | 24 | 35 |
(i)
| Symbol (gray level) | Count | Probability = count/N |
|---|---|---|
| 10 | 7 | 7/20 = 0.35 |
| 3 | 6 | 6/20 = 0.3 |
| 24 | 4 | 4/20 = 0.2 |
| 35 | 3 | 3/20 = 0.15 |
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 |
|---|---|---|---|---|
| 10 | 0.35 | 1 | 0.35 1 | 0.65 0 |
| 3 | 0.3 | 01 | 0.35 00 | 0.35 1 |
| 24 | 0.2 | 000 | 0.3 01 | |
| 35 | 0.15 | 001 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| 10 | 0.35 | 1 | 1 | 0.35 |
| 3 | 0.3 | 01 | 2 | 0.6 |
| 24 | 0.2 | 000 | 3 | 0.6 |
| 35 | 0.15 | 001 | 3 | 0.45 |
Average length Lavg = Σ l·p = (0.35)(1) + (0.3)(2) + (0.2)(3) + (0.15)(3) = 2 bits/symbol.
Entropy H = −Σ p log2 p = −(0.35)log2(0.35) + −(0.3)log2(0.3) + −(0.2)log2(0.2) + −(0.15)log2(0.15) = 1.9261 bits/symbol.
Coding efficiency η = H / Lavg = 1.9261 / 2 = 96.31%.
Compression ratio CR = n1/n2 = 6 / 2 = 3.0000. Relative redundancy RD = 1 − 1/CR = 1 − 1/3.0000 = 0.6667 → 66.67% of the data was redundant.
(ii) Row by row (gray level, run length), each number stored in 6 bits:
| Row | (gray level, run length) pairs |
|---|---|
| Row 1 | (3,1) (10,1) (3,1) (24,1) (35,1) |
| Row 2 | (3,1) (10,2) (24,1) (3,1) |
| Row 3 | (3,1) (10,2) (24,1) (35,1) |
| Row 4 | (3,1) (10,2) (24,1) (35,1) |
17 pairs = 34 numbers, each stored in 6 bits. Original = 4×5×6 = 120 bits. RLE = 34×6 = 204 bits. CR = 120/204 = 0.5882.
(iii) Huffman: CR = 6/2 = 3.0000. RLE: CR = 0.5882, less than 1, so RLE expands this image (the runs are too short). Huffman is far better here.
Try it, step by step: F22 (i).
Try it, step by step: F22 (ii): every run, row by row.
3×3, 8-bit image [18 16 16; 11 11 14; 11 14 16]. (i) Illustrate Huffman encoding (ii) entropy (iii) which redundancy is reduced; is it lossless? (iv) Is compression achieved? Prove it.
(i)–(ii) N = 9.
| Symbol (gray level) | Count | Probability = count/N |
|---|---|---|
| 11 | 3 | 3/9 = 0.3333 |
| 16 | 3 | 3/9 = 0.3333 |
| 14 | 2 | 2/9 = 0.2222 |
| 18 | 1 | 1/9 = 0.1111 |
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 |
|---|---|---|---|---|
| 11 | 0.3333 | 1 | 0.3333 1 | 0.6667 0 |
| 16 | 0.3333 | 00 | 0.3333 00 | 0.3333 1 |
| 14 | 0.2222 | 010 | 0.3333 01 | |
| 18 | 0.1111 | 011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| 11 | 0.3333 | 1 | 1 | 0.3333 |
| 16 | 0.3333 | 00 | 2 | 0.6667 |
| 14 | 0.2222 | 010 | 3 | 0.6667 |
| 18 | 0.1111 | 011 | 3 | 0.3333 |
Average length Lavg = Σ l·p = (0.3333)(1) + (0.3333)(2) + (0.2222)(3) + (0.1111)(3) = 2 bits/symbol.
Entropy H = −Σ p log2 p = −(0.3333)log2(0.3333) + −(0.3333)log2(0.3333) + −(0.2222)log2(0.2222) + −(0.1111)log2(0.1111) = 1.8911 bits/symbol.
Coding efficiency η = H / Lavg = 1.8911 / 2 = 94.55%.
Compression ratio CR = n1/n2 = 8 / 2 = 4.0000. Relative redundancy RD = 1 − 1/CR = 1 − 1/4.0000 = 0.7500 → 75.00% of the data was redundant.
(iii) Huffman reduces coding redundancy. It is lossless: each code word is unique and prefix-free, so the image is recovered exactly.
(iv) Original = 9 × 8 = 72 bits. Huffman = Σ count × length = 18 bits. CR = 72/18 = 4.00 > 1, so yes, compression is achieved.
Try it, step by step: SP22 Q5(b).
5×5, 8-bit image. (i) Derive the entropy equation from information theory (ii) entropy (iii) Huffman codes (iv) compression ratio against 8-bit fixed length (v) relative data redundancy.
(i) An event E with probability P(E) carries I(E) = log2(1/P(E)) = −log2P(E) bits of information: the rarer the event, the more information. For a source with symbols a1 … aJ, symbol aj occurs with probability P(aj) and carries −log2P(aj) bits, so the average information per symbol is the weighted sum
For an image, P(aj) is the normalized histogram p(rk) = nk/N.
(ii)–(v) N = 25.
| Symbol (gray level) | Count | Probability = count/N |
|---|---|---|
| 12 | 7 | 7/25 = 0.28 |
| 11 | 5 | 5/25 = 0.2 |
| 14 | 5 | 5/25 = 0.2 |
| 16 | 4 | 4/25 = 0.16 |
| 17 | 3 | 3/25 = 0.12 |
| 18 | 1 | 1/25 = 0.04 |
Step 1, sort the probabilities largest first. Steps 2–4, add the two smallest and re-sort, until two values are left (a sum that ties with an existing value goes below it). Step 5, walk back from the last column: upper branch 0, lower branch 1.
| Symbol | Probability | Code | Reduction 1 | Reduction 2 | Reduction 3 | Reduction 4 |
|---|---|---|---|---|---|---|
| 12 | 0.28 | 01 | 0.28 01 | 0.32 00 | 0.4 1 | 0.6 0 |
| 11 | 0.2 | 10 | 0.2 10 | 0.28 01 | 0.32 00 | 0.4 1 |
| 14 | 0.2 | 11 | 0.2 11 | 0.2 10 | 0.28 01 | |
| 16 | 0.16 | 000 | 0.16 000 | 0.2 11 | ||
| 17 | 0.12 | 0010 | 0.16 001 | |||
| 18 | 0.04 | 0011 |
| Symbol | Probability p | Code | Length l | p × l |
|---|---|---|---|---|
| 12 | 0.28 | 01 | 2 | 0.56 |
| 11 | 0.2 | 10 | 2 | 0.4 |
| 14 | 0.2 | 11 | 2 | 0.4 |
| 16 | 0.16 | 000 | 3 | 0.48 |
| 17 | 0.12 | 0010 | 4 | 0.48 |
| 18 | 0.04 | 0011 | 4 | 0.16 |
Average length Lavg = Σ l·p = (0.28)(2) + (0.2)(2) + (0.2)(2) + (0.16)(3) + (0.12)(4) + (0.04)(4) = 2.48 bits/symbol.
Entropy H = −Σ p log2 p = −(0.28)log2(0.28) + −(0.2)log2(0.2) + −(0.2)log2(0.2) + −(0.16)log2(0.16) + −(0.12)log2(0.12) + −(0.04)log2(0.04) = 2.4188 bits/symbol.
Coding efficiency η = H / Lavg = 2.4188 / 2.48 = 97.53%.
Compression ratio CR = n1/n2 = 8 / 2.48 = 3.2258. Relative redundancy RD = 1 − 1/CR = 1 − 1/3.2258 = 0.6900 → 69.00% of the data was redundant.
Total bits: Huffman = 62 bits; fixed = 25 × 8 = 200 bits.
Try it, step by step: F21 (iii)–(v).
Slide 46. A lossless method, particularly effective when small values occur much more frequently than large ones. It can only represent non-negative integers, is computationally simpler than Huffman, and depends on a tunable parameter m that decides how numbers are split into quotient and remainder.
Slides 47–48. The Golomb code of n with respect to m, Gm(n), combines the unary code of the quotient ⌊n/m⌋ and the binary representation of the remainder n mod m:
Compute the Golomb code G4(9).
Step 1: q = ⌊9/4⌋ = 2 → unary code 110.
Step 2: k = ⌈log2 4⌉ = 2; c = 22 − 4 = 0; r = 9 mod 4 = 1. r = 1 ≥ c = 0 → r + c = 1 in k = 2 bits = 01.
Step 3: concatenate: 110 + 01 = G4(9) = 11001.
Try it, step by step: any n and m. Pick n and m from the menus; it opens on G4(9).
G4(7): q = 1 → 10; k = 2, c = 0, r = 3 ≥ 0 → r + c = 3 in 2 bits = 11 → 1011.
G5(12): q = ⌊12/5⌋ = 2 → 110; k = ⌈log2 5⌉ = 3, c = 8 − 5 = 3, r = 12 mod 5 = 2. r = 2 < c = 3 → r in k − 1 = 2 bits = 10. So G5(12) = 110 + 10 = 11010.
| n | G1(n) | G2(n) | G4(n) |
|---|---|---|---|
| 0 | 0 | 00 | 000 |
| 1 | 10 | 01 | 001 |
| 2 | 110 | 100 | 010 |
| 3 | 1110 | 101 | 011 |
| 4 | 11110 | 1100 | 1000 |
| 5 | 111110 | 1101 | 1001 |
| 6 | 1111110 | 11100 | 1010 |
| 7 | 11111110 | 11101 | 1011 |
m = 1: k = 0, so the code is just the unary code of n. m = 2: k = 1, c = 0, the remainder is 1 bit. m = 4: k = 2, c = 0, the remainder is 2 bits. Row 7 matches the slide (11111110, 11101, 1011).
Slide 52. Variable-length, error-free (lossless), non-block code: there is no one-to-one correspondence between symbols and code words. An entire sequence of source symbols is mapped to a single arithmetic number (code word), which defines an interval of real numbers between 0 and 1. It can achieve theoretically higher compression than Huffman.
Slide 53. It maintains an interval within [0, 1) based on the symbol probabilities.
Four-symbol source a1 = 0.2, a2 = 0.2, a3 = 0.4, a4 = 0.2. Encode the message a1 a2 a3 a3 a4.
| Symbol | Probability | Initial sub-interval |
|---|---|---|
| a1 | 0.2 | [0, 0.2) |
| a2 | 0.2 | [0.2, 0.4) |
| a3 | 0.4 | [0.4, 0.8) |
| a4 | 0.2 | [0.8, 1) |
For each symbol: width = high − low; new low = low + width × (symbol's low end); new high = low + width × (symbol's high end).
| Symbol | Current interval | Width | New low | New high |
|---|---|---|---|---|
| a1 | [0, 1) | 1 | 0 + 1×0 = 0 | 0 + 1×0.2 = 0.2 |
| a2 | [0, 0.2) | 0.2 | 0 + 0.2×0.2 = 0.04 | 0 + 0.2×0.4 = 0.08 |
| a3 | [0.04, 0.08) | 0.04 | 0.04 + 0.04×0.4 = 0.056 | 0.04 + 0.04×0.8 = 0.072 |
| a3 | [0.056, 0.072) | 0.016 | 0.056 + 0.016×0.4 = 0.0624 | 0.056 + 0.016×0.8 = 0.0688 |
| a4 | [0.0624, 0.0688) | 0.0064 | 0.0624 + 0.0064×0.8 = 0.06752 | 0.0624 + 0.0064×1 = 0.0688 |
Final interval: [0.06752, 0.0688). Any number in it encodes the message. Shortest decimal: 0.068.
The slide picks 0.068: the arithmetic code for a1a2a3a3a4.
Try it, step by step: slides 55–63: watch each symbol zoom into its slice.
The decoder knows the same sub-intervals. Take the code 0.068: it lies in [0, 0.2), so the first symbol is a1. Inside [0, 0.2) the slices are a1 [0, 0.04), a2 [0.04, 0.08), a3 [0.08, 0.16), a4 [0.16, 0.2): 0.068 lies in a2. Keep zooming: [0.04, 0.08) → a3 slice [0.056, 0.072); then a3 again [0.0624, 0.0688); then a4. Decoded: a1 a2 a3 a3 a4. (The decoder also needs the message length or an end symbol to know when to stop.)
Six-symbol source A 0.45, B 0.13, C 0.12, D 0.16, E 0.09, F 0.05 with sub-intervals A [0, 0.45), B [0.45, 0.58), C [0.58, 0.70), D [0.70, 0.86), E [0.86, 0.95), F [0.95, 1.00). Encode the message "ACEF". (The Huffman code of the same source is the slide 36 class work above.)
| Symbol | Probability | Initial sub-interval |
|---|---|---|
| A | 0.45 | [0, 0.45) |
| B | 0.13 | [0.45, 0.58) |
| C | 0.12 | [0.58, 0.7) |
| D | 0.16 | [0.7, 0.86) |
| E | 0.09 | [0.86, 0.95) |
| F | 0.05 | [0.95, 1) |
For each symbol: width = high − low; new low = low + width × (symbol's low end); new high = low + width × (symbol's high end).
| Symbol | Current interval | Width | New low | New high |
|---|---|---|---|---|
| A | [0, 1) | 1 | 0 + 1×0 = 0 | 0 + 1×0.45 = 0.45 |
| C | [0, 0.45) | 0.45 | 0 + 0.45×0.58 = 0.261 | 0 + 0.45×0.7 = 0.315 |
| E | [0.261, 0.315) | 0.054 | 0.261 + 0.054×0.86 = 0.30744 | 0.261 + 0.054×0.95 = 0.3123 |
| F | [0.30744, 0.3123) | 0.00486 | 0.30744 + 0.00486×0.95 = 0.312057 | 0.30744 + 0.00486×1 = 0.3123 |
Final interval: [0.312057, 0.3123). Any number in it encodes the message. Shortest decimal: 0.3121.
Try it, step by step: the slide 74 class work 'ACEF'.
Slide 75. Key features: lossless (no data lost); dictionary-based (builds a dictionary of sequences met in the input); a universal algorithm (text, images, other data); efficient: it removes spatial / inter-pixel redundancy, is simple to implement with high throughput, and needs no knowledge of the probability of occurrence. Used in GIF, TIFF and PDF.
Slide 76. Encoding: images are scanned left to right and top to bottom. The codebook (dictionary) is extended with new sequences met in the input, each assigned a fixed-length code word. For 8-bit monochrome images the first 256 words are the intensities 0, 1, …, 255; new gray-level sequences get entries from #256. With a 9-bit, 512-word dictionary, two pixels (16 bits) can be represented by 9 bits only.
Slide 77. Read input symbols and form longer sequences. If a sequence is already in the dictionary, continue extending it. If not, add the new sequence to the dictionary and output the code for the longest existing sequence.
| 39 | 39 | 126 | 126 |
| 39 | 39 | 126 | 126 |
| 39 | 39 | 126 | 126 |
| 39 | 39 | 126 | 126 |
Dictionary locations 0–255 already hold the 256 single gray levels; new sequences go from location 256. Read the pixels left to right, top to bottom. For each pixel: if currently recognized sequence + pixel is in the dictionary, keep growing it; otherwise output the code of the recognized sequence, add the longer sequence to the dictionary, and restart from the pixel.
| Currently recognized sequence | Pixel being processed | Encoded output | Dictionary location (code word) | Dictionary entry |
|---|---|---|---|---|
| 39 | ||||
| 39 | 39 | 39 | 256 | 39-39 |
| 39 | 126 | 39 | 257 | 39-126 |
| 126 | 126 | 126 | 258 | 126-126 |
| 126 | 39 | 126 | 259 | 126-39 |
| 39 | 39 | |||
| 39-39 | 126 | 256 | 260 | 39-39-126 |
| 126 | 126 | |||
| 126-126 | 39 | 258 | 261 | 126-126-39 |
| 39 | 39 | |||
| 39-39 | 126 | |||
| 39-39-126 | 126 | 260 | 262 | 39-39-126-126 |
| 126 | 39 | |||
| 126-39 | 39 | 259 | 263 | 126-39-39 |
| 39 | 126 | |||
| 39-126 | 126 | 257 | 264 | 39-126-126 |
| 126 | 126 |
Encoded output: 39 39 126 126 256 258 260 259 257 126 (10 code words).
Original = 16 pixels × 8 bits = 128 bits. Compressed = 10 codes × 9 bits = 90 bits. CR = 128/90 = 1.4222 (compression achieved).
Try it, step by step: the slide example, one pixel at a time (slides 78–95).
Slide 106. Compression ratio: the sequence 39-39-126 is replaced by code 260, i.e. 3 × 8 = 24 bits by 9 bits. Original 16 × 8 = 128 bits, compressed 10 × 9 = 90 bits, CR = 128 : 90 = 1.42 : 1.
The decoder rebuilds the same dictionary while it reads the codes. Each code is translated back into its sequence; after each code (from the second on) the entry previous-sequence + first pixel of the current sequence is added.
| code read | output pixels | dictionary entry added |
|---|---|---|
| 39 | 39 | — |
| 39 | 39 | 256: 39-39 |
| 126 | 126 | 257: 39-126 |
| 126 | 126 | 258: 126-126 |
| 256 | 39 39 | 259: 126-39 |
| 258 | 126 126 | 260: 39-39-126 |
| 260 | 39 39 126 | 261: 126-126-39 |
| 259 | 126 39 | 262: 39-39-126-126 |
| 257 | 39 126 | 263: 126-39-39 |
| 126 | 126 | 264: 39-126-126 |
Output: 39 39 126 126 / 39 39 126 126 / 39 39 126 126 / 39 39 126 126, the original image.
A collection of bitmap images with many repeating colours and patterns must be compressed with a lossless fixed-length coding algorithm. Name it and explain step-by-step encoding of the 4×4 8-bit image with every row [7 8 40 100].
Use LZW coding: lossless, fixed-length (9-bit) code words, and it removes the repeated patterns (spatial redundancy) without needing probabilities.
Dictionary locations 0–255 already hold the 256 single gray levels; new sequences go from location 256. Read the pixels left to right, top to bottom. For each pixel: if currently recognized sequence + pixel is in the dictionary, keep growing it; otherwise output the code of the recognized sequence, add the longer sequence to the dictionary, and restart from the pixel.
| Currently recognized sequence | Pixel being processed | Encoded output | Dictionary location (code word) | Dictionary entry |
|---|---|---|---|---|
| 7 | ||||
| 7 | 8 | 7 | 256 | 7-8 |
| 8 | 40 | 8 | 257 | 8-40 |
| 40 | 100 | 40 | 258 | 40-100 |
| 100 | 7 | 100 | 259 | 100-7 |
| 7 | 8 | |||
| 7-8 | 40 | 256 | 260 | 7-8-40 |
| 40 | 100 | |||
| 40-100 | 7 | 258 | 261 | 40-100-7 |
| 7 | 8 | |||
| 7-8 | 40 | |||
| 7-8-40 | 100 | 260 | 262 | 7-8-40-100 |
| 100 | 7 | |||
| 100-7 | 8 | 259 | 263 | 100-7-8 |
| 8 | 40 | |||
| 8-40 | 100 | 257 | 264 | 8-40-100 |
| 100 | 100 |
Encoded output: 7 8 40 100 256 258 260 259 257 100 (10 code words).
Original = 16 pixels × 8 bits = 128 bits. Compressed = 10 codes × 9 bits = 90 bits. CR = 128/90 = 1.4222 (compression achieved).
Try it, step by step: SP25.
Encode the 4×4 8-bit image with every row [5 8 40 120] using LZW, step by step; the codebook uses 9 bits.
Dictionary locations 0–255 already hold the 256 single gray levels; new sequences go from location 256. Read the pixels left to right, top to bottom. For each pixel: if currently recognized sequence + pixel is in the dictionary, keep growing it; otherwise output the code of the recognized sequence, add the longer sequence to the dictionary, and restart from the pixel.
| Currently recognized sequence | Pixel being processed | Encoded output | Dictionary location (code word) | Dictionary entry |
|---|---|---|---|---|
| 5 | ||||
| 5 | 8 | 5 | 256 | 5-8 |
| 8 | 40 | 8 | 257 | 8-40 |
| 40 | 120 | 40 | 258 | 40-120 |
| 120 | 5 | 120 | 259 | 120-5 |
| 5 | 8 | |||
| 5-8 | 40 | 256 | 260 | 5-8-40 |
| 40 | 120 | |||
| 40-120 | 5 | 258 | 261 | 40-120-5 |
| 5 | 8 | |||
| 5-8 | 40 | |||
| 5-8-40 | 120 | 260 | 262 | 5-8-40-120 |
| 120 | 5 | |||
| 120-5 | 8 | 259 | 263 | 120-5-8 |
| 8 | 40 | |||
| 8-40 | 120 | 257 | 264 | 8-40-120 |
| 120 | 120 |
Encoded output: 5 8 40 120 256 258 260 259 257 120 (10 code words).
Original = 16 pixels × 8 bits = 128 bits. Compressed = 10 codes × 9 bits = 90 bits. CR = 128/90 = 1.4222 (compression achieved).
Try it, step by step: F23.
3×3 8-bit image with every row [3 4 7]. (i) Generate a 9-bit codebook and LZW-encode it step by step. (ii) Which redundancy does it reduce? (iii) Is any compression achieved? Prove it.
(i)
Dictionary locations 0–255 already hold the 256 single gray levels; new sequences go from location 256. Read the pixels left to right, top to bottom. For each pixel: if currently recognized sequence + pixel is in the dictionary, keep growing it; otherwise output the code of the recognized sequence, add the longer sequence to the dictionary, and restart from the pixel.
| Currently recognized sequence | Pixel being processed | Encoded output | Dictionary location (code word) | Dictionary entry |
|---|---|---|---|---|
| 3 | ||||
| 3 | 4 | 3 | 256 | 3-4 |
| 4 | 7 | 4 | 257 | 4-7 |
| 7 | 3 | 7 | 258 | 7-3 |
| 3 | 4 | |||
| 3-4 | 7 | 256 | 259 | 3-4-7 |
| 7 | 3 | |||
| 7-3 | 4 | 258 | 260 | 7-3-4 |
| 4 | 7 | |||
| 4-7 | 257 |
Encoded output: 3 4 7 256 258 257 (6 code words).
Original = 9 pixels × 8 bits = 72 bits. Compressed = 6 codes × 9 bits = 54 bits. CR = 72/54 = 1.3333 (compression achieved).
(ii) LZW reduces spatial / inter-pixel redundancy: repeated pixel patterns (3-4, 4-7, 7-3 …) are replaced by single dictionary codes.
(iii) Yes: 72 bits are coded with 6 × 9 = 54 bits, CR = 72/54 = 1.33 > 1.
Try it, step by step: SP22.
Slides 107–108. Image features: in the line image all 256 gray levels are equally probable (uniform histogram), so variable-length coding cannot be applied. But the gray level of each line is chosen at random, so pixels are independent vertically and identical (completely dependent) horizontally: spatial redundancy.
The spatial redundancy is eliminated with run-length pairs (a mapping scheme). A run-length pair has two parts: the start of a new intensity and the number of consecutive pixels having that intensity. Each 256-pixel line is replaced by a single 8-bit intensity and the run length 256: CR = (256 × 256 × 8)/((256 + 256) × 8) = 128.
Slide 109. RLE uses run-length pairs, e.g. (0, 1), (1, 2), (0, 1), (1, 3), …. It eliminates small spatial redundancies. However, small runs result in expansion instead of compression.
| 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| 10 | 10 | 10 | 10 | 10 | 12 | 12 | 12 |
| 10 | 10 | 10 | 10 | 10 | 12 | 12 | 12 |
| 0 | 0 | 0 | 10 | 10 | 10 | 0 | 0 |
| 5 | 5 | 5 | 0 | 0 | 0 | 0 | 0 |
| 5 | 5 | 5 | 10 | 10 | 9 | 9 | 10 |
| 5 | 5 | 5 | 4 | 4 | 4 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Row | (gray level, run length) pairs |
|---|---|
| Row 1 | (10,8) |
| Row 2 | (10,5) (12,3) |
| Row 3 | (10,5) (12,3) |
| Row 4 | (0,3) (10,3) (0,2) |
| Row 5 | (5,3) (0,5) |
| Row 6 | (5,3) (10,2) (9,2) (10,1) |
| Row 7 | (5,3) (4,3) (0,2) |
| Row 8 | (0,8) |
18 pairs = 36 numbers, each stored in 4 bits. Original = 8×8×4 = 256 bits. RLE = 36×4 = 144 bits. CR = 256/144 = 1.7778.
As on slide 112: original 64 × 4 = 256 bits, compressed 36 × 4 = 144 bits, compression ratio 64:36 = 16:9.
Try it, step by step: Example 10.2.9, every run.
In binary images adjacent pixels are even more likely to be identical, so the image can be written as a sequence of run lengths only (e.g. 1b 2w 1b 3w 4b 1w → 121341). Scan each row left to right and code each contiguous run of 0s or 1s by its length. A convention fixes the value of the runs:
Example (slide 115): the 30-bit row 000001100000100000000101100000 has runs of 5, 2, 5, 1, 8, 1, 1, 2, 5. With the first convention it is written 0 5 2 5 1 8 1 1 2 5, where the leading 0 says "the first run is black (0)". With the second convention it is also 0 5 2 5 1 8 1 1 2 5, but now the leading 0 means "the first white run has length 0".
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Convention: the first number of each row is the number of zeros (black) in the first run, so a row that starts with 1 begins with 0.
| Row | RLC numbers |
|---|---|
| Row 1 | 8 |
| Row 2 | 0, 4, 4 |
| Row 3 | 1, 2, 5 |
| Row 4 | 1, 5, 2 |
| Row 5 | 1, 3, 2, 1, 1 |
| Row 6 | 2, 1, 2, 2, 1 |
| Row 7 | 0, 4, 1, 1, 2 |
| Row 8 | 8 |
Rows 2 and 7 begin with 0 because they start with a white run.
Slide 118. RLE in BMP combines an encoded mode (2-byte RLE: the first byte is the run length, the second the gray/colour index) and an absolute mode (first byte 0, the second byte is 0 end of line, 1 end of image, 2 move to a new position, 3–255 specify pixels individually). Either mode can appear anywhere in the image.
Slide 119. Removing irrelevant information also removes useful "invisible" information. Information is lost in many other lossy compression techniques. How do we assess the loss? With image fidelity criteria.
Slide 120. The goal of image compression is to reduce file size while keeping acceptable quality. Fidelity criteria define how closely the reconstructed image matches the original, i.e. the degree of exactness (measuring the quality). Two classes: (i) objective fidelity criteria (quantifiable, mathematically defined); (ii) subjective fidelity criteria (person dependent, based on human observers).
Slides 121–122. f(x,y) is compressed to g(x,y) and decompressed to f̂(x,y) = f(x,y) + e(x,y). The error is e(x,y) = f̂(x,y) − f(x,y), and the total error between the two images is ΣΣ [f̂(x,y) − f(x,y)].
Slide 123. Objective criteria: RMSE, signal-to-noise ratio (SNR), structural similarity index (SSIM), normalized cross-correlation (NCC).
Slide 124. RMSE measures the average squared difference between pixel values of the original and decompressed image: compute the squared differences pixel by pixel, average them and take the square root. The smaller the RMSE, the better the compressed image represents the original.
Original [100 150; 200 250], reconstructed [102 148; 198 255].
Step 1, differences: [−2 2; 2 −5]. Step 2, squares: [4 4; 4 25]. Step 3, mean: (4 + 4 + 4 + 25)/4 = 37/4 = 9.25. Step 4, root: RMSE = √9.25 ≈ 3.04.
Slide 126. Three approximations of one image have RMSE 5.17, 15.67 and 14.17: the first is closest to the original.
Slide 127. SNR expresses the ratio between the signal and the noise introduced by compression. The higher the SNR, the better the quality.
Slides 128–129 (short). SSIM evaluates similarity based on luminance, contrast and structure; it is often closer to human perception than MSE/PSNR; values from −1 to 1, where 1 is perfect similarity. NCC compares the correlation between original and compressed images and is invariant to linear changes in brightness and contrast; −1 (perfect negative) to 1 (perfect positive correlation).
Slides 130–131. Subjective criteria rely on human judgement: visual losslessness (indistinguishable to the eye), quality ratings (excellent, good, fair, poor), artifact evaluation (blockiness, blurring, colour banding). The Television Allocations Study Organization scale: 1 Excellent, 2 Fine, 3 Passable, 4 Marginal, 5 Inferior, 6 Unusable.
A 3×3, 3-bit image f(x,y) = [1 4 3; 2 3 4; 2 4 5] is compressed with a lossy technique; after decompression every pixel value increased by 2. Give the decompressed image f̂ and evaluate it with a suitable fidelity criterion (RMSE).
| 1 | 4 | 3 |
| 2 | 3 | 4 |
| 2 | 4 | 5 |
| 3 | 6 | 5 |
| 4 | 5 | 6 |
| 4 | 6 | 7 |
| 2 | 2 | 2 |
| 2 | 2 | 2 |
| 2 | 2 | 2 |
| 4 | 4 | 4 |
| 4 | 4 | 4 |
| 4 | 4 | 4 |
erms = [ (1/9) × (9 × 2²) ]1/2 = [ 36/9 ]1/2 = √4 = 2.
SNRms = Σ f̂² / Σ e² = 248 / 36 = 6.8889.
Every pixel is off by exactly 2 gray levels (out of 0–7), so the decompressed image is a brighter copy; the RMSE of 2 is large for a 3-bit image.
Try it, step by step: the RMSE, pixel by pixel.
A 3×3, 3-bit image [1,4,3,5,2,3,4,2,1] is lossy compressed; after decompression it becomes [3,6,5,7,4,5,6,4,3]. Calculate the RMSE.
Every pixel increased by 2, so e = 2 everywhere: erms = √((9 × 4)/9) = √4 = 2.
Try it, step by step: slide 132 class work.
| method | removes | lossless? | key formula / rule |
|---|---|---|---|
| Huffman | coding redundancy | yes | merge two smallest; Lavg = Σ l p |
| Golomb | coding redundancy | yes | unary(⌊n/m⌋) + truncated(n mod m) |
| Arithmetic | coding redundancy | yes | one number in the final interval |
| LZW | spatial / inter-pixel | yes | dictionary from 256, 9-bit codes |
| RLE | spatial / inter-pixel | yes | (value, run length) pairs |
| quantization | irrelevant information | no (lossy) | judge with RMSE, SNR |
| entropy | — | — | H = −Σ p log2 p, lower bound on Lavg |