ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 1 ECE160 Multimedia Lecture 8: Spring 2011 Lossy Compression Algorithms No Lectures next weekECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 2 Vector Quantization (VQ) • According to Shannon's original work on information theory, any compression system performs better if it operates on vectors or groups of samples rather than individual symbols or samples. • Form vectors of input samples by simply concatenating a number of consecutive samples into a single vector. • Instead of single reconstruction values as in scalar quantization, in VQ code vectors with n components are used. A collection of these code vectors form the codebook.ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 3 Vector QuantizationECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 4 Transform Coding The rationale behind transform coding: • If Y is the result of a linear transform T of the input vector X in such a way that the components of Y are much less correlated, then Y can be coded more efficiently than X. • If most information is accurately described by the first few components of a transformed vector, then the remaining components can be coarsely quantized, or even set to zero, with little signal distortion. – Discrete Cosine Transform (DCT) will be studied first. – In addition, we will examine the Karhunen-Loeve Transform (KLT) which optimally decorrelates the components of the input X.ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 5 Spatial Frequency and DCT • Spatial frequency indicates how many times pixel values change across an image block. • The DCT formalizes this notion with a measure of how much the image contents change in correspondence to the number of cycles of a cosine wave per block. • The role of the DCT is to decompose the original signal into its DC and AC components; the role of the IDCT is to reconstruct (re-compose) the signal. • JPEG and MPEG use image blocks of 8x8 pixelsECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 6 DCT • Given an input function f(i,j) over two integer variables i and j (a piece of an image), the 2D DCT transforms it into a new function F(u,v), with integer u and v running over the same range as i and j. The general definition of the transform is: • where i,u = 0,1,…,M − 1; j,v = 0,1,…, N − 1; and the constants C(u) and C(v) are determined byECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 7 1D Discrete Cosine Transform (1D DCT) with inverseECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 8 1D Discrete Cosine Transform (1D DCT)ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 9 1D Discrete Cosine Transform (1D DCT)ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 10 1D Discrete Cosine Transform (1D DCT)ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 11 1D Discrete Cosine Transform (1D DCT)ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 12 2D Discrete Cosine Transform (2D DCT) with inverseECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 13 2D Discrete Cosine Transform (2D DCT)ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 14 DCT Artifact Original Shading Luminosity Signal Signal after DCT Shading after DCTECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 15 Karhunen-Loeve Transform (KLT) • The Karhunen-Loeve transform is a reversible linear transform that exploits the statistical properties of the vector representation. • It optimally decorrelates the input signal. • To understand the optimality of the KLT, consider the autocorrelation matrix RX of the input vector X defined as:ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 16 KLT Example • To illustrate the mechanics of the KLT, consider the four 3D input vectors x1 = (4,4,5), x2 = (3,2,5), x3 = (5,7,6), and x4 = (6,7,7). • Estimate the mean: • Estimate the autocorrelation matrix of the input:ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 17 KLT Example • The eigenvalues of RX are λ1 = 6.1963, λ2 = 0.2147, and λ3 = 0.0264. The corresponding eigenvectors are: • The KLT is given by the matrixECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 18 KLT Example • Subtracting the mean vector from each input vector and apply the KLT • Since the rows of T are orthonormal vectors, the inverse transform is just the transpose: T−1 = TT, and x = TTy+mx • In general, after the KLT most of the “energy" of the transform coefficients are concentrated within the first few components. This is the “energy compaction" property of the KLT.ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 19 Wavelet-Based Coding • The objective of the wavelet transform is to decompose the input signal into components that are easier to deal with, have special interpretations, or have some components that can be thresholded away, for compression purposes. • We want to be able to at least approximately reconstruct the original signal given these components. • The basis functions of the wavelet transform are localized in space, time and frequency. • There are two types of wavelet transforms: the continuous wavelet transform (CWT) and the discrete wavelet transform (DWT).ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 20 The Discrete Wavelet Transform • Discrete wavelets are formed from a mother wavelet, with scale and shift in discrete steps. • The DWT makes the connection between wavelets in the continuous time domain and “filter banks" in the discrete time domain in a multiresolution analysis framework. • It is possible to show that the dilated and translated family of wavelets form an orthonormal basis of L2(R).ECE160 Spring 2011 Lecture 9 Lossy Compression Algorithms 21 Multiresolution Analysis in the Wavelet Domain • Multiresolution analysis provides the tool to adapt signal resolution to only relevant details for a particular task. • The approximation component is then recursively decomposed into approximation and detail at