[PDF] [PDF] The Discrete Cosine Transform

[PDF] Image Compression and the Discrete Cosine Transform Introduction

The equation calculates one entry (i,jth) of the transformed image from the pixel values of the original image matrix For the standard 8x8 block that JPEG 

[PDF] The Discrete Cosine Transform

familiar matrices Key words cosine transform, orthogonality, signal processing matrix of cosines yields a Discrete Cosine Transform (DCT) There are four 

[PDF] DCT and Transform Coding

given covariance matrix of the underlying signal • Discrete Cosine Transform ( DCT) is close to KLT for images that can be modeled by a first order Markov 

The Discrete Cosine Transform (DCT)

The discrete cosine transform (DCT) is a well known example that is particularly quadratic, real-valued transformation matrix with the elements (cf Eqn (20 1))

[PDF] Digital Image Processing Lectures 11 & 12 - Colorado State University

2-D Discrete Fourier Transform Unified Matrix Representation Other Image Transforms Discrete Cosine Transform (DCT) Digital Image Processing Lectures 11 

[PDF] 3: Discrete Cosine Transform

3: Discrete Cosine Transform • DFT Problems • DCT + • Basis Functions • DCT of sine wave where M is an N × 2N matrix with mk,n = cos 2π(2n+1+N)(2k+1 

[PDF] On Algebras Related to the Discrete Cosine Transform - CORE

Each reference derives a fast DCT algorithm via a factorization (either explicit or implicit) of the DCT matrix Most algebraic approaches to explaining fast 

[PDF] Lecture 11 : Discrete Cosine Transform

figure(1) plot D1 stem(D1); Here we show how to compute the DCT from the basis functions bases is an 8×8 matrix, f an 1 

[PDF] Discrete Cosine Transform - Pages supplied by users

Algebraically: • F = Df, where D is the matrix of DCT coe cients • Inverse transform: f = D−1F 

[PDF] de gaulle algerian crisis

[PDF] de gaulle referendum algeria

[PDF] de l'acide éthanoïque

[PDF] de l'importance de l'orthographe

[PDF] de l'importance de la virgule

[PDF] deadlier strain of covid 19

[PDF] deadlier strain of smallpox

[PDF] deadlier strains of coronavirus

[PDF] deaths on aircraft carriers

[PDF] debugging performance issues in java

[PDF] deca case study

[PDF] deca competition guide

[PDF] deca event planning

[PDF] deca events

[PDF] deca finance

SIAM REVIEWc

1999 Society for Industrial and Applied Mathematics

Vol. 41, No. 1, pp. 135-147

The Discrete Cosine Transform

Gilbert Strang

y Abstract.Each discrete cosine transform (DCT) usesNreal basis vectors whose components are cosines. In the DCT-4, for example, thejth component ofv k is cos(j+ 1 2 )(k+ 1 2 N . These basis vectors are orthogonal and the transform is extremely useful in image processing. If the vectorxgives the intensities along a row of pixels, its cosine seriesPc k v k has the coecientsc k =(x;v k )=N. They are quickly computed from a Fast Fourier Transform. But a direct proof of orthogonality, by calculating inner products, does not reveal how natural these cosine vectors are. We prove orthogonality in a dierent way. Each DCT basis contains the eigenvectors of a symmetric \second dierence" matrix. By varying the boundary conditions we get the established transforms DCT-1 through DCT-4. Other combinations lead to four additional cosine transforms. The type of boundary condition (Dirichlet or Neumann, centered at a meshpoint or a midpoint) determines the applications that are appropriate for each transform. The centering also determines the period:N1orNin the established transforms,N 1 2 orN+ 1 2 in the other four. The key point is that all these \eigenvectors of cosines" come from simple and familiar matrices. Key words.cosine transform, orthogonality, signal processing

AMS subject classifications.42, 15

PII.S0036144598336745

Introduction.Just as the Fourier series is the starting point in transforming and analyzing periodic functions, the basic step for vectors is the Discrete Fourier Transform (DFT). It maps the \time domain" to the \frequency domain." A vector withNcomponents is written as a combination ofNspecial basis vectorsv k . Those are constructed from powers of the complex numberw=e 2i=N v k 1;w k ;w 2k ;:::;w (N1)k ;k=0;1;::;N1:

The vectorsv

k are the columns of the Fourier matrixF=F N .Those columns are orthogonal. So the inverse ofFis its conjugate transpose, divided bykv k k 2 =N.

The discrete Fourier seriesx=Pc

k v k isx=Fc. The inversec=F 1 xuses c k =(x;v k )=Nfor the (complex) Fourier coecients. Two points to mention, about orthogonality and speed, before we come to the purpose of this note. First, for these DFT basis vectors, a direct proof of orthogonality is veryecient: (v k ;v N1 X j=0 (w k j (w j =(w k w N 1 w k w 1: Received by the editors December 12, 1997; accepted for publication (in revised form) August

6, 1998; published electronically January 22, 1999.

y Massachusetts Institute of Technology, Department of Mathematics, Cambridge, MA 02139 (gs@math.mit.edu, http://www-math.mit.edu/gs).

136GILBERT STRANG

The numerator is zero becausew

N = 1. The denominator is nonzero becausek6=`.

This proof of (v

k ;v ) = 0 is short but not very revealing. I want to recommend a dierent proof, which recognizes thev k aseigenvectors. We could work with any circulant matrix, and we will choose below a symmetricA 0 . Then linear algebra guarantees that its eigenvectorsv k are orthogonal.

Actually this second proof, verifying thatA

0 v k k v k , brings out a central point of Fourier analysis. The Fourier basis diagonalizes every periodic constant coecient operator. Each frequencyk(or 2k=N) has its own frequency response k . The complex exponential vectorsv k are important in applied mathematics because they are eigenvectors! The second key point is speed of calculation. The matricesFandF 1 are full, which normally meansN 2 multiplications for the transform and the inverse transform: y=Fxandx=F 1 y. But the special formF jk =w jk of the Fourier matrix allows a factorization into very sparse and simple matrices. This is the Fast Fourier Transform (FFT). It is easiest whenNisapower2 L . The operation count drops fromN 2 to 1 2 NL, which is an enormous saving. But the matrix entries (powers ofw) are complex. The purpose of this note is to considerreal transforms that involve cosines.Each matrix of cosines yields a Discrete Cosine Transform (DCT). There are four established types, DCT-1 through DCT-4, which dier in the boundary conditions at the ends of the interval. (This dierence is crucial. The DCT-2 and DCT-4 are constantly applied in image processing; they have an FFT implementation and they are truly useful.) All four types of DCT are orthogonal transforms. The usual proof is a direct calculation of inner products of theNbasis vectors, using trigonometric identities. We want to prove this orthogonality in the second(indirect)way. The basis vectors of cosines are actually eigenvectors of symmetric second-dierence matrices. This proof seems more attractive, and ultimately more useful. It also leads us, by selecting dierent boundary conditions, to four less familiar cosine transforms. The complete set of eight DCTs was found in 1985 by Wang and Hunt [10], and we want to derive them in a simple way. We begin now with the DFT.

1. The Periodic Case and the DFT.The Fourier transform works perfectly for

periodic boundary conditions (and constant coecients). For a second dierence matrix, the constant diagonals contain1 and 2 and1. The diagonals with1 loop around to the upper right and lower left corners, by periodicity, to produce a circulant matrix: A 0 =2 6 6 6 6 64211
121
121
1123
7 7 7 7 75:

For this matrixA

0 , and every matrix throughout the paper, we look at three things:

1. the interiorrows,

2. the boundary rows (rows 0 andN1),

3. the eigenvectors.

The interior rows will be the same in every matrix! Thejth entry ofA 0 uis u j1 +2u j u j+1 , which corresponds tou 00 . This choice of sign makes each matrix positive denite(orat least semidenite). No eigenvalues are negative. At the rst and last rows (j= 0 andj=N1), this second dierence involves u 1 andu N . It reaches beyond the boundary. Then the periodicityu N =u 0 and u N1 =u 1 produces the1 entries that appear in the corners ofA 0

THE DISCRETE COSINE TRANSFORM137

Note:The numbering throughout this paper goes from0toN1, since SIAM is glad to be on very friendly terms with the IEEE. But we still useiforp 1! No problem anyway, since the DCT is real.

We now verify thatv

k =(1;w k ;w 2k ;:::;w (N1)k ) is an eigenvector ofA 0 .It is periodic becausew N = 1. Thejth component ofA 0 v k k v k is the second dierence: w (j1)k +2w jk w (j+1)k =w k +2w k w jk equotesdbs_dbs17.pdfusesText_23