DOC PREVIEW
UW-Madison ECE 533 - Introduction to Image and Video Coding Algorithms

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Image and Video Coding AlgorithmsOutlineTransform-based Image CodingLinear TransformBlock-based Image CodingJPEG Image Coding AlgorithmsJPEG DecodingPre-ProcessingDiscrete Cosine TransformInverse DCT (IDCT)DCT Basis FunctionsQuantization of DCT CoefficientsDPCM of DC coefficientsHuffman Entropy CodingHuffman Encoding of DC CoefficientsJPEG Huffman Table: CategoriesJPEG DC Entropy CodingAC CoefficientsAC Coefficients Huffman EncodingHuffman DecodingVideo CodingMPEG EncodingMPEG DecodingMotion EstimationForward Motion EstimationBlock Motion EstimationVideo sequence : Tennis frame 0Video sequence : Tennis frame 1Frame DifferenceWhat is motion estimation?What is motion compensation ?Motion Compensated Frame Difference6-Level Nested Do Loop© 2002-2003 by Yu Hen Hu1ECE533 Digital Image ProcessingIntroduction to Image and Video Coding Algorithms© 2002-2003 by Yu Hen Hu2ECE533 Digital Image ProcessingOutlineTransform-based Image and Video CodingLinear Transformation – DCTQuantization»Scalar Quantization»Vector QuantizationEntropy CodingVideo Coding – Motion Compensation© 2002-2003 by Yu Hen Hu3ECE533 Digital Image ProcessingTransform-based Image CodingLinearTransformQuanti-zatioinEntropy CodingBinary bitstreamInputImage© 2002-2003 by Yu Hen Hu4ECE533 Digital Image ProcessingLinear TransformIf the signal is formatted as a vector, a linear transform can be formulated as a matrix-vector product that transform the signal into a different domain. Examples:»K-L Expansion»Discrete Fourier Transform»Discrete cosine transform»Discrete wavelet transformEnergy compaction property: The transformed signal vector has few, large coefficients and many nearly zero small coefficients. These few large coefficients can be encoded efficiently with few bits while retaining the majority of energy of the original signal.© 2002-2003 by Yu Hen Hu5ECE533 Digital Image ProcessingBlock-based Image CodingAn image is a 2D signal of pixel intensities (including colors).A block-based image coding scheme partitions the entire image into 8 by 8 or 16 by 16 (or other size) blocks. Then the coding algorithm is applied to individual blocks independently.Blocks may be overlapping or non-overlapping. Advantage: parallel processing can be applied to process individual blocks in parallel. For hand-held devices, only one block needs be loaded into main memory each time.© 2002-2003 by Yu Hen Hu6ECE533 Digital Image ProcessingJPEG Image Coding AlgorithmsDCT QDPCMZig Zag ScanDC HuffmanAC Huffman8x8 blockQuantization MatrixCode booksJPEG Encoding ProcessDCAC© 2002-2003 by Yu Hen Hu7ECE533 Digital Image ProcessingJPEG DecodingIDCTIDPCMDC HuffmanAC Huffman8x8 blockJPEG Decoding ProcessDCACIQ© 2002-2003 by Yu Hen Hu8ECE533 Digital Image ProcessingPre-ProcessingColor sub-sampling»A color image is converted from RGB to YUV color space. Each pixel in each dimension is 1 byte. »Sub-sample U-V planes: 4:1:1 scheme.»For every 16 by 16 block of a color image, six 8 by 8 blocks are encoded.Level shifting: Each pixel value is subtracted by 128 so it ranges (–128, 127).Four 88 blocks of luminance pixels, plus two 88 sub-sampled chrominance components makes a 16 by 16 macro-block© 2002-2003 by Yu Hen Hu9ECE533 Digital Image ProcessingDiscrete Cosine Transform88 two-dimensional separable DCT:DCT is chosen because it leads to superior energy compaction for natural images.F(0,0): DC coefficient ranges (-128x64/4,127x16) needs 12 bits to represent (including sign bit). 12 bits are more than enough for the remaining AC coefficients (u > 0, or v > 0)  .0;7,016)12(cos16)12(cos),(81;0),(41),(70707070vuvuvnumnmfvunmfvuFm mm n© 2002-2003 by Yu Hen Hu10ECE533 Digital Image ProcessingInverse DCT (IDCT)88 two-dimensional separable IDCT:IDCT can be computed using the same routine as DCT7 70 07 70 01 (2 1) (2 1)( , ) cos cos 0;4 16 16( , )1 (2 1) (2 1)( , ) cos cos 0 , 7; 0.8 16 16u vu vm u n vF u v m nf m nm u n vF u v m n m np pp p= == =+ +�= =��=�+ +�� � + >������© 2002-2003 by Yu Hen Hu11ECE533 Digital Image ProcessingDCT Basis Functions© 2002-2003 by Yu Hen Hu12ECE533 Digital Image ProcessingQuantization of DCT Coefficients© 2002-2003 by Yu Hen Hu13ECE533 Digital Image ProcessingDPCM of DC coefficientsDC coding: All DC coefficients of each 8 by 8 blocks of the entire image are combined to make a sequence of DC coefficients. Next, DPCM is applied:DiffDC(blocki) = DC(blocki) – DC(blocki–1)Then DiffDCs will be encoded using Hoffman entropyExample: Original: 1216  1232  1224  1248  1248  1208After DPCM:1216  +16  -8  +24  0  -40 121612481232124812241208© 2002-2003 by Yu Hen Hu14ECE533 Digital Image ProcessingHuffman Entropy CodingEntropy coding: »Task: to assign a variable-length binary code to a finite set of alphabets. »Goal: to minimize the average length (number of bits) per alphabet. »Approach: Shorter code for alphabet occurred more frequently. Longer for infrequent ones. Optimal solution: »When the averaged code length approaches the entropy of the source. Huffman coding: »Code words are derived from a (perhaps) un-balanced binary tree. Arithmetic coding is another entropy coding method.© 2002-2003 by Yu Hen Hu15ECE533 Digital Image ProcessingHuffman Encoding of DC CoefficientsEncoding and decoding of Huffman code is done via look-up table.In JPEG, DC coefficients (after DPCM) are first grouped according to their magnitudes. Each category is assigned as a symbol and a Hoffman table is given. For example, –7 to –4 and 4 to 7 are listed as category 3 which has a code "00“. If the number is positive, the binary representation of the number will be append to the Hoffman code of the category number directly. For example, 6 is encoded as 00 110. If the number is negative, the appended code is the 1’s complement of that number. For example, -5 is encoded as 00 010. Question: Given such a table, how to devise a dedicated hardware to implement the encoding procedure?© 2002-2003 by Yu Hen Hu16ECE533 Digital Image ProcessingJPEG Huffman Table: Categories© 2002-2003 by Yu Hen Hu17ECE533 Digital Image ProcessingJPEG DC Entropy CodingExample:»-9: category 4. Hence Base code = 101»1’s complement of (-9) = 1C(1001) = 0110»Code word = 101 + 0110 =


View Full Document

UW-Madison ECE 533 - Introduction to Image and Video Coding Algorithms

Documents in this Course
Load more
Download Introduction to Image and Video Coding Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Image and Video Coding Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Image and Video Coding Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?