Modular Programming With Functions

Modular Programming With Functions

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

Recently Viewed Presentations

  • Communication Systems : Prof. Ravi Warrier AMPLITUDE MODULATION

    Communication Systems : Prof. Ravi Warrier AMPLITUDE MODULATION

    To produce SSB signal from DSB signal ideal filters should be used to split the spectrum in the middle so that the bandwidth of bandpass signal is reduced by one half. In VSB system one sideband and a vestige of...
  • Help with Paraphrasing - Wayne St Social Work

    Help with Paraphrasing - Wayne St Social Work

    Step 1: Before you begin to even write the paraphrase, read the original several times. Step 2: Before writing, say the main ideas to yourself out loud or explain them to a friend. Being able to talk about the idea...
  • The Interplay Between Research Innovation and Federal ...

    The Interplay Between Research Innovation and Federal ...

    NBC election night prediction model. Small area estimation. Elliott and Little on census adjustment Singh, Folsom, and Vaish Example 2: Log-linear Models Deming-Stephan iterative proportional fitting algorithm (raking). Log-linear models and MLEs: margins are minimal sufficient statistics. implications for statistical...
  • Pan-Africanism and Independence Movements

    Pan-Africanism and Independence Movements

    An example of African nationalism was the Pan-African movement that began in the late 1800s. The movement believed that all Africans shared a common heritage and should work together for their freedom. The Pan-African movement's principles actually dated back to...
  • Machine Learning Algorithms for Choosing Compiler Heuristics

    Machine Learning Algorithms for Choosing Compiler Heuristics

    Efficient Program Compilation through Machine Learning Techniques. Gennady . Pekhimenko. IBM Canada. Angela . Demke. Brown. University of Toronto
  • The Claytronics Project and Domain-Specific Languages Nels Beckman

    The Claytronics Project and Domain-Specific Languages Nels Beckman

    Should transactions be local or distributed? End 2/6/2006 SSSG Presentation; Claytronics and DSLs The Claytronics Project and Domain-Specific Languages Nels Beckman SSSG Presentation February 6th, 2006 Introduction to the Claytronics Project Goal: Use large numbers of nano-scale robots to create...
  • GR / Service Entry MB01 - Create GRN

    GR / Service Entry MB01 - Create GRN

    GR / Service Entry MB01 - Create GRN MIGO - Create GRN ML81N - Creation of Service Entry Please note: Buyer has to ensure that there should be no changes in PO post making GRN and before Invoice Processing Vendor...
  • Process Improvement: Is It Always Worth It? Damon

    Process Improvement: Is It Always Worth It? Damon

    Data-driven approach to eliminate defects in a process. Strives to eliminate variability. ASQ Black Belt. Certification involving six sigma principles. Kaizen. Japanese word for improvement. Continuous improvement involving all levels of employees.