Transform Coding and JPEGOverview and LogisticsClarifications: “Dimension” in different contextSummary and ReviewSummary and Review (cont’d)Exercise:Review: 1-D DCTRevisit: Example of 1-D DCT with N=82-D Transform: General Case2-D Separable Unitary Transf.Basis Images for Separable TransformExercise on Basis Images2-D DCTRevisit: 2-D DFTVisualizing Fourier Basis Images8x8 DFT Basis ImagesTransform CodingTransform CodingZonal Coding and Threshold CodingDetermining Block SizeBlock-based Transform CodingReview: List of Common Compression ToolsHow to Encode Quantized Coeff. in Each BlockPut Basic Tools Together: JPEG Image Compression StandardJPEG Compression Standard (early 1990s)Baseline JPEG AlgorithmBlock Diagram of JPEG BaselineSlide 33Y U V (Y Cb Cr) ComponentsLossless Coding Part in JPEGLossy Part in JPEGQuantization Table Recommended in JPEGSlide 40JPEG Compression (Q=75% & 30%)Y Cb Cr After JPEG (Q=30%)Lossless Coding Part in Baseline JPEG: DetailsSlide 44Summary of Today’s LectureRecap: JPEG Still Image CodingSlide 47Slide 48M. Wu: ENEE631 Digital Image Processing (Spring'09)Transform Coding and JPEGTransform Coding and JPEGSpring ’09 Instructor: Min Wu Electrical and Computer Engineering Department, University of Maryland, College Park bb.eng.umd.edu (select ENEE631 S’09) [email protected] Spring’09ENEE631 Spring’09Lecture 11 (3/2/2009)Lecture 11 (3/2/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [2]Overview and LogisticsOverview and LogisticsLast Time:–Unitary transform and properties–DCT transformToday:–Wrap up 2-D unitary transform and basis images–Transform coding–Putting together: JPEG compression standardLogistics–Assignment #3 posted last Friday. Due Friday noon March 13.–Mid-term: Wednesday March 25 in class.UMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [3]Clarifications: “Dimension” in different contextClarifications: “Dimension” in different contextDimension of a signal ~ # of index variables –Audio and speech is 1-D signal: over time or sampled time index–Image is 2-D: over two spatial indices (horizontal and vertical)–Video is 3-D: over two spatial indices and one time indexDimension of an image ~ size of digital image–How many pixels along each row and column: e.g. 512x512 lena image–Also referred to as the “resolution” of an imageDimension of a vector space ~ # of basis vectors in it–[ x(1), …, x(N) ]T ~ # of elements in the vectorM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [4]Summary and ReviewSummary and Review1-D transform of a vector–Represent an N-sample sequence as a vector in N-dimension vector space–TransformDifferent representation of this vector in the space via different basise.g., 1-D DFT from time domain to frequency domain–Forward transformIn the form of inner product Project a vector onto a new set of basis to obtain N “coefficients”–Inverse transformUse linear combination of basis vectors weighted by transform coefficients to represent the original signal2-D transform of a matrix–Generally can rewrite the matrix into a long vector & apply 1-D transform–Separable transform allows applying transform to rows then columnsUMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [5]Summary and Review (cont’d)Summary and Review (cont’d)Vector/matrix representation of 1-D & 2-D sampled signal–Representing an image as a matrix or sometimes as a long vectorBasis functions/vectors and orthonormal basis–Used for representing the space via their linear combinations–Many possible sets of basis and orthonormal basisUnitary transform on input x ~ A-1 = A*T –y = A x x = A-1 y = A*T y = ai*T y(i) ~ represented by basis vectors {ai*T}–Rows (and columns) of a unitary matrix form an orthonormal basisGeneral 2-D transform and separable unitary 2-D transform–2-D transform involves O(N4) computation–Separable: Y = A X AT = (A X) AT ~ O(N3) computationApply 1-D transform to all columns, then apply 1-D transform to rows–For non-square image of size MxN: Y = AMxM X ATNxN ; basis images MxNUMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [7]Exercise:Exercise:Is each matrix here unitary or orthogonal?–If yes, what are the basis vectors?cossinsincos5A212121214A21323A1: n; 2: y. inv(A3) = [2, –3; -1, 2]; Check A A’ = I ?UMCP ENEE631 Slides (created by M.Wu © 2001/2004)11212jjA221jjAM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [8]Review: 1-D DCTReview: 1-D DCTLinear transform matrix C is real and orthogonalc(k,n) = (0) for k=0 ; c(k,n) = (k) cos[(2n+1)/2N] for k>0–rows of C form an orthonormal basis–Relation and comparison with DFT: C is not symmetricDCT is related to DFT of a symmetrically extended signal, which gives less discontinuity at boundaries and better energy compaction1..., 1,kfor 2)( ;1)0(2)12(cos)()()(2)12(cos)()()(1010NNkNNknkkZnzNknknzkZNkNnUMCP ENEE631 Slides (created by M.Wu © 2001/2004)Figure is from slides at Gonzalez/ Woods DIP book website (Chapter 8)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [10]UMCP ENEE631 Slides (created by M.Wu © 2001)Revisit: Example of 1-D DCT with N=8Revisit: Example of 1-D DCT with N=8kZ(k)Transform coeff.1.00.0-1.01.00.0-1.01.00.0-1.01.00.0-1.01.00.0-1.01.00.0-1.01.00.0-1.01.00.0-1.0Basis vectors1000-1001000-1001000-1001000-1001000-1001000-1001000-1001000-100u=0u=0 to 1u=0 to 4u=0 to 5u=0 to 2u=0 to 3u=0 to 6u=0 to 7 Reconstructionsnz(n)Original signalFrom Ken Lam’s DCT talk 2001 (HK Polytech)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec11 – Transf. Coding & JPEG [11]2-D Transform: General Case2-D Transform: General CaseA general 2-D linear transform with kernel {ak,l(m,n)}–y(k,l) is a
View Full Document