CS 414 – Multimedia Systems Design Lecture 8 – JPEG Compression (Part 3)AdministrativeOutlineHybrid Coding (Usage of RLE/Huffman, Arithmetic Coding)Image Compression and FormatsUbiquitous use of digital imagesJPEG (Joint Photographic Experts Group)Slide 8JPEG Compression1. Image PreparationDivision of Source Image into PlanesComponents and their ResolutionsColor Transformation (optional)Image Preparation (Pixel Allocation)Image Preparation - BlocksData Unit OrderingExample of Interleaved Ordering2. Image ProcessingForward DCT1D Forward DCTUnderstanding DCT1D DCT Basic FunctionsVisualization of 1D DCT Basic Functions1D Inverse DCTExtend DCT from 1D to 2DEquations for 2D DCTVisualization of 2D DCT Basis FunctionsCoefficient Differentiation3. QuantizationDe facto Quantization Table4. Entropy EncodingDC EncodingDifference Coding applied to DC CoefficientsAC EncodingHuffman EncodingInterchange Format of JPEGExample - One Everyday PhotoSlide 38Slide 39Slide 40Slide 41Slide 42DiscussionCS 414 - Spring 2011CS 414 – Multimedia Systems Design Lecture 8 – JPEG Compression (Part 3)Klara NahrstedtSpring 2011CS 414 - Spring 2011Administrative MP1 is postedExtended Deadline of MP1 is February 18 Friday midnight – submit via compassHelp-session for MP1 – Wednesday, February 9, 7pm , Room: 1111 SCOutline Hybrid Coding: JPEG Coding Reading: Section 7.5 out of “Media Coding and Content Processing”, Steinmetz & Nahrstedt, Prentice Hall 2002CS 414 - Spring 2011Hybrid Coding (Usage of RLE/Huffman, Arithmetic Coding) CS 414 - Spring 2011RLE, HuffmanArithmeticCodingImage Compression and FormatsRLEHuffmanLZWGIFJPEG / JPEG-2000 (Hybrid Coding)FractalsTIFF, PICT, BMP, etc.CS 414 - Spring 2011Ubiquitous use of digital imagesCS 414 - Spring 2011JPEG (Joint Photographic Experts Group)Requirements:Very good compression ratio and good quality imageIndependent of image size Applicable to any image and pixel aspect ratioApplicable to any complexity (with any statistical characteristics)CS 414 - Spring 2011CS 414 - Spring 2011JPEG CompressionFDCTSourceImageQuantizerEntropyEncoderTableTableCompressedimage dataDCT-based encoding8x8 blocksRBGCS 414 - Spring 2011Image Preparation1. Image PreparationThe image preparation is NOT BASED on 9-bit YUV encodingFixed number of lines and columnsMapping of encoded chrominanceSource image consists of components (Ci) and to each component we assign YUV, RGB or TIQ signals. CS 414 - Spring 2011Division of Source Image into PlanesCS 414 - Spring 2011Components and their ResolutionsCS 414 - Spring 2011Color Transformation (optional)Down-sample chrominance componentscompress without loss of quality (color space)e.g., YUV 4:2:2 or 4:1:1Example: 640 x 480 RGB to YUV 4:1:1Y is 640x480U is 160x120V is 160x120CS 414 - Spring 2011Image Preparation (Pixel Allocation)Each pixel is presented by ‘p’ bits, value is in range of (0,2p-1)All pixels of all components within the same image are coded with the same number of bitsLossy modes use precision 8 or 12 bits per pixelLossless mode uses precision 2 up to 12 bits per pixelCS 414 - Spring 2011Image Preparation - BlocksImages are divided into data units, called blocks – definition comes from DCT transformation since DCT operates on blocksLossy mode – blocks of 8x8 pixels; lossless mode – data unit 1 pixelCS 414 - Spring 2011Data Unit OrderingNon-interlea ved: scan from left to right, top to bottom for each color componentInterleave d: compute one “unit” from each color component, then repeatfull color pixels after each step of decodingbut components may have different resolutionCS 414 - Spring 2011Example of Interleaved Ordering[Wallace, 1991]CS 414 - Spring 2011MCU: Minimum Coding Unit2. Image Processing Shift values [0, 2P - 1] to [-2P-1, 2P-1 - 1]e.g. if (P=8), shift [0, 255] to [-127, 127]DCT requires range be centered around 0Values in 8x8 pixel blocks are spatial values and there are 64 samples values in each block CS 414 - Spring 2011Forward DCTConvert from spatial to frequency domainconvert intensity function into weighted sum of periodic basis (cosine) functionsidentify bands of spectral information that can be thrown away without loss of qualityIntensity values in each color plane often change slowlyCS 414 - Spring 20111D Forward DCTGiven a list of n intensity values I(x),where x = 0, …, n-1Compute the n DCT coefficients:1...0,2)12(cos)()(2)(10nunxxIuCnuFnxotherwiseuforuCwhere1,021)(CS 414 - Spring 2011Understanding DCTFor example, in R3, we can write (5, 2, 9) as the sum of a set of basis vectorsBasic functions in R3: [(1,0,0), (0,1,0), (0,0,1)](5,2,9) = 5*(1,0,0) + 2*(0,1,0) + 9*(0,0,1)DCT is can be also composed as sum of set of basic functions CS 414 - Spring 20111D DCT Basic FunctionsDecompose the intensity function into a weighted sum of cosine basis functionsCS 414 - Spring 2011Visualization of 1D DCT Basic FunctionsCS 414 - Spring 2011F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7)1D Inverse DCTGiven a list of n DCT coefficients F(u),where u = 0, …, n-1Compute the n intensity values:otherwiseuforuCwhere1,021)(1...0,2)12(cos)()(2)(10nxnxuCuFnxInuCS 414 - Spring 2011Extend DCT from 1D to 2DPerform 1D DCT on each row of the blockAgain for each column of 1D coefficientsalternatively, transpose the matrix and perform DCT on the rowsXYEquations for 2D DCTForward DCT:Inverse DCT:mvynuxyxIvCuCnmvuFmynx2)12(cos*2)12(cos*),()()(2),(1010mvynuxvCuCuvFnmxyImvnu2)12(cos*2)12(cos)()(),(2),(1010Visualization of 2D DCT Basis FunctionsIncreasing frequencyIncreasing frequencyCS 414 - Spring 2011Coefficient Differentiation F(0,0) includes the lowest frequency in both directionsis called DC coefficient Determines fundamental color of the blockF(0,1) …. F(7,7) are called AC coefficientsTheir frequency is non-zero in one or both directionsCS 414 - Spring 20113. QuantizationThrow out bitsConsider example: 1011012 = 45 (6 bits)We can truncate this string to 4 bits: 10112 = 11 We can truncate this string to 3 bits: 1012 = 5 (original value
View Full Document