Image Formats 1 Color representation An image = a collection of picture elements (pixels) Different types of pixels Each pixel has a color Binary (1 bit): black/white Grayscale (8 bits) Color (3 colors, 8 bits each): red, green, blue A 1024x768 image requires 1024x768X3 bytes 2 Compression: to lose or not to lose? Goal: reduce redundancy Originally developed for fax transmission Send the same information using fewer bits

Send high quality documents in short calls Two basic strategies: Lossless: can reconstruct exactly Lossy: cant reconstruct, but looks the same 3 Run length encoding Opportunity: Large regions of a single color are common Approach: Record # of consecutive pixels for each color An example of lossless encoding Uncompressed 000000000000000000000111 111111111100000000000001 111111111111111111111 RLE Row 1, 21:0,13:1;13:0;22:1 LZW, etc. use algorithms in addition to RLE 01010101010101010101 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 4 PGM (Portable Gray Map) Represents grayscale images P2 24 7 15 0 0 0 0 3 3 0 3 0 0 3 3 0 3 0 0 3 0 0 0 0 0 3 0 3

0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 7 7 7 7 0 0 7 0 7 0 7

0 0 7 0 7 0 7 0 0 7 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 11 11 11 0 11 0 0 0 0 11 11 11 0 0 11 0 0 0 0 11 11 11 11 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 15 15 15 15 0 15 0 0 15 0 15 15 15 15 0 15 0 0 0 0 15 0 0 0 0 0 0 0 0 0 5 PPM Represents Color Images P3 4 4 15 0 0 0 0 0 0 0 0 0 15 0 15 0 0 0 0 15 7 0 0 0 0 0 0 0 0 0 0 0 0 0 15 7 0 0 0 15 0 0 0

0 15 0 0 0 0 0 0 6 Palette selection Opportunity: 24 bits can represent 16 million colors No picture uses all 16 million colors Human eye does not see small differences Approach: Select a palette of 256 colors Indicate which palette entry to use for each pixel Look up each color in the palette 7 GIF (Graphics Interchange Format) Palette selection, then lossless compression Opportunity: Common colors are sent more often Approach: Use fewer bits to represent common colors. Example:

1 Blue 75% 75x1= 75 75x2=150 01 White 20% 20x2= 40 20x2= 40 001 Red 5% 5x3= 15 5x2= 10 130 200 8 Fact about JPEG Compression JPEG stands for Joint Photographic Experts Group JPEG compression is used with .jpg and can be embedded in .tiff and .eps files. Used on 24-bit color files. Works well on photographic images. Although it is a lossy compression technique, it yields an excellent quality image with high compression rates. 9 The JPEG Compression 7A.5 JPEG Compression Algorithm 10 The JPEG Compression Algorithm

11 Block Encoding DC component 139 144 150 159 144 151 155 161 149 153 160 162 153 156 163 160 original image DCT 1260 -1 -12 -23 -17 -6 -11 -9 -2 -7 -2 0 AC components 79 0 -2 -1 -1 -1 0 0 -1 0 0 0 0 0 0 0 run-length code

0 1 0 0 0 2 0 -5 -3 2 1 79 -2 -1 -1 -1 -1 0 Huffman code zigzag Quantize 79 -2 -1 0 0 -1 -1 0 -1 0 0

0 0 0 0 0 10011011100011... 12 The JPEG Compression Algorithm Col n Row m u v 1 if u 0, u 2M 1 if v 0, v 2N 1 otherwise M 1 otherwise N Time Domain M 1N1 ( 2m 1)u (2n 1)v A [ u

, v ] x [ m , n ] cos cos u v 2M 2N m 0 n 0 M 1N1 (2m 1)u ( 2n 1)v x[m, n] A [ u , v

] cos cos u v 2M 2N u 0 v 0 13 The JPEG Compression Algorithm Col v Row u Frequency Domain u v 1 if u 0, u 2M 1 if v 0, v 2N 1

otherwise M 1 otherwise N M 1N1 ( 2m 1)u (2n 1)v A [ u , v ] x [ m , n ] cos cos u v 2M 2N

m 0 n 0 M 1N1 (2m 1)u ( 2n 1)v x[m, n] A [ u , v ] cos cos u v 2M 2N u 0 v 0 14 The JPEG Compression Algorithm Lowest frequencies A

Highest frequencies Great, but we still need to represent these values digitall Big numbers are localized to a small part of the matrix Is all this precision for each number really necessary? 15 The JPEG Compression Algorithm 231 => 11100111 11100000 (224) 62 => 0111110 1000000 (64) 9 => 1001 1000 (8) Worry only about storing the red bits! 16 The JPEG Compression Algorithm Throwing away trailing bits is easy How many bits should we keep? divide by some number and discard fraction Check the variance among blocks for each coefficient lower variance == less bits Create a corresponding

quantization matrix that tells us how by much to divide each coefficient in every block 16 11 10 16 24 40 51 61 12 12 14 19 26 58 60 55 14 13 16

24 40 57 69 56 14 17 22 29 51 87 80 62 18 22 37 56 68 10 9 10 3

77 24 35 55 64 81 10 4 11 3 92 49 64 78 87 10 3 12 1 12 0 10 1 72

92 95 98 11 2 10 0 10 3 99 17 The JPEG Compression Algorithm ./ 16 11 10 16 24 40 51 61 12 12

14 19 26 58 60 55 14 13 16 24 40 57 69 56 14 17 22 29 51 87 80

62 18 22 37 56 68 109 103 77 24 35 55 64 81 104 113 92 49 64 78 87

103 121 120 101 72 92 95 98 112 100 103 99 DCT coefficient matrix element-wise divided by quantization matrix (after rounding) = 18 Zig-Zag Scan Why? -- to group low frequency coefficients in top of vector and high frequency coefficients at the bottom Maps 8 x 8 matrix to a 1 x 64 vector 8x8 ... 1x64

19 The JPEG Compression Algorithm When we store these numbers, we must also keep track of how many zeros belong after each number: 14 = 1110 => represents the number 11100000 = 224 Store zero entries with just a single bit! Encode this using Huffman or other lossless scheme 20 The JPEG Compression Algorithm Rendering the compressed image Remultiply by the quantization matrix to get the coefficients Calculate IDCT M 1N1 ( 2m 1)u (2n 1)v A [ u , v ] x [ m , n ]

cos cos u v 2M 2N m 0 n 0 M 1N1 (2m 1)u ( 2n 1)v x[m, n] u v A[u , v] cos cos 2M 2N u 0 v 0 Matrix of pixel intensities Reassemble blocks

21 Image Examples 248 X 324 X 3B 22 JPEG Compression Examples 28:1 Compression Original Compressed Quality still reasonable Some loss of fine detail 23 JPEG Compression Examples 66:1 Quality drops dramatically as increase compression ratio Throws out color information first 24 JPEG Compression Examples 101:1 86:1 25

DCT Quantization BlowEffects Up Sections of Low Quality Images See 8 X 8 blocks Only low frequency coefficients for Y Extreme subsampling for U, V Single value for 16 X 8 pixels 26 JPEG Modes Lossless Mode: Truly lossless It is a predictive coding mechanism as opposed to the baseline mechanism which is based on DCT and quantization(the source of the loss). Here is the simple block diagram of the technique: Predictive Difference Huffman EnCoder Lossless Coding 27 Lossless Mode

For each pixel a predictor (one of 7 possible) is used that best predicts the value contained in the pixel The difference between the predicted value and the actual value is used as the predictive difference to represent the pixel. The predictor along with the predictive difference are encoded The series of pixel values are encoded using huffman coding C B A X Predicto r Prediction P1 A P2 B P3 C P4 A+B-C

P5 A + (B-C)/2 P6 B + (A-C)/2 P7 (A+B)/2 28 Progressive Mode It allows a coarse version of an image to be transmitted at a low rate, which is then progressively improved over subsequent transmissions. Spectral Selection : Send DC component and first few AC coefficients first, then gradually some more ACs. Spectral Selection: First Scan: Second Scan: Third Scan: . . Nth Scan: Image Pixels 29 Progressive Mode Successive Approximation : All the DCT components are sent few bits at a time: For example, send n1 (say,4) bits (starting with MSB) of all pixels in the first scan, the next n2(say 1) bits of all pixels in the second and so on.

Pixels ordered (zig-zag-wise) MSB 7 6 5 4 3 2 1 0 LSB One Pixel ... First Scan: Second Scan: Third Scan: 5th Scan: ... ... . . . . ... 30