Return home

Discrete Cosine Transform Tutorial

Discrete cosine transform (DCT) can linearly transform data into the frequency domain, where the data can be represented by a set of coefficients. The advantage of DCT is that the energy of the original data may be concentrated in only a few low frequency components of DCT depending on the correlation in the data.

 

DCT express a signal (a set of numbers) in terms of a sum of cosine functions with different frequencies. For example, given a set A of n values,

 

one dimensional discrete cosine transform coefficients (actually the weights)  are given by

To make DCT values orthogonal, we multiply the terms by scale factors  and .  Remember that if two lines are orthogonal if they are perpendicular at their point of intersection. Similarly, two vectors are orthogonal if and only if their dot product (, where  denotes the length or magnitude of ) is zero.  Two vectors in an inner product space are orthonormal if they are orthogonal and both of unit length. This boring stuff are all related to DCT, but you can simply ignore if you are not interested in.

 

Let us rewrite  for k=0 in the expanded form,



The first coefficient  is called as DC (direct current, zero frequency) coefficient, and     is simply the mean of the set .

Let us rewrite the formulation for the rest of the coefficients (they are called as AC, alternative current coefficients):

 

If A consists of correlated values, then most of the DCT coefficients ( and ) produced will be zero or small numbers, and only a few are large. The early DCT coefficients (e.g., ) corresponds to low-frequency components of the image information. The low-frequency components usually contain the important image information. The later coefficients (e.g., ) contain the less-important (high-frequency components) image information.

 

Let’s do an experiment. Given the set A, where elements of A are correlated numbers. If we apply DCT to a set, it will result in 8 DCT coefficients.

 

A=[1        2           3     4           5     6           7     8      ]

WA=[12.7279 -6.4423     0     -0.6735     0     -0.2009     0     -0.0507]

 

Let us ignore the coefficients with absolute values smaller than one.

WA'=[12.7279 -6.4423    0     0           0     0           0     0     ]

 

If we apply the inverse1 DCT transform to W', we can reconstruct the original data set A with a small mean square error (0.4965).

A=[1        2           3           4           5           6           7           8      ]

A=[1.3407   1.8217      2.7104      3.8716      5.1284      6.2896      7.1783      7.6593 ]

 

The energy of A is concentrated by DCT in only two coefficients because the elements in A are correlated.

 

Here is the Matlab code for this experiment.

A   = 1:8;

W   = dct(A);

W_q = W;

W_q(abs(W_q)<1) = 0;

A_q = idct(W_q);

mse = mean(sum((A-A_q).^2))

 

 

 

On the other hand, if we apply DCT to a set of uncorrelated numbers, it will result in coefficients with large values. Consider the set B given below. If we apply DCT to B, the total energy (sum of the absolute values of the coefficients) of DCT coefficients is 42.0907.

 

B =[1 5 -9 -8 7 1 0 9]

WB =[2.1213   -6.0855    7.5688    5.2571    4.2426  -11.8857   -3.9005    1.0293]

Therefore, if you plan to use DCT for data compression, you should first find a good way to represent your data where the elements are correlated. For example, let us naively sort the elements of B and then apply DCT to the sorted set.

B_s = [ -9    -8     0     1     1     5     7     9 ]

WB_­s = [2.1213  -16.4520   -2.0719   -3.5681   -0.7071    1.8680    2.3890    0.3323]

 

In this case, the total energy is 29.5097.

 

Here is the Matlab code for this experiment.

B   = [1 5 -9 -8 7 1 0 9];

W   = dct(B);

sumW = sum(abs(W));

B_s = sort(B);

W_s = dct(B_s);

sumW_s = sum(abs(W_s));

 

One interesting feature of DCT is that the value of n (number of the elements in the data set) plays a critical role in the calculations. Most applications employing the DCT use 8 as the value of n. The table below shows the value of    in degrees for n=8, t=0,..,n-1, and k=0,..,n-1.

 

k\t

0

1

2

3

4

5

6

7

low freq. (DC)

0

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

1

11.25

33.75

56.25

78.75

101.25

123.75

146.25

168.75

2

22.50

67.50

112.50

157.50

202.50

247.50

292.50

337.50

3

33.75

101.25

168.75

236.25

303.75

11.25

78.75

146.25

4

45.00

135.00

225.00

315.00

45.00

135.00

225.00

315.00

5

56.25

168.75

281.25

33.75

146.25

258.75

11.25

123.75

6

67.50

202.50

337.50

112.50

247.50

22.50

157.50

292.50

high freq.

7

78.75

236.25

33.75

191.25

348.75

146.25

303.75

101.25

 

 

We us the first row to calculate  and similarly use the second row to calculate , and so on so forth. When we calculate DCT coefficients, we have a set of n input numbers and we have n coefficients. For each DCT coefficients, we have a base frequency f. If we draw the cosine values, it will be very clear how the cosine signal changes with increasing frequency.

 

 

 

Here is the Matlab code for this experiment.

clear all;

close all;

clc;

n=8;

step = 0.1;

t=0:step:n-1;

f=0:n-1;

cosval = zeros(size(f,2),size(t,2));

angle  = zeros(size(f,2),size(t,2));

for fr=1:size(f,2)

    for i=1:size(t,2)

        frequency   = fr-1;

        angle(fr,i) = rad2deg(((2*t(i)+1)*frequency*pi)/(2*n));

       cosval(fr,i) = cos(deg2rad(angle(fr,i)));

    end

end

line='-'

plot(cosval(1,:),['r' line]),hold on;

plot(cosval(2,:),['g' line])

plot(cosval(3,:),['b' line])

plot(cosval(4,:),['m' line])

 

hleg1 = legend('f_0','f_1', 'f_2', 'f_3')

grid on;

figure,

plot(cosval(5,:),['r' line]),hold on;

plot(cosval(6,:),['g' line])

plot(cosval(7,:),['b' line])

plot(cosval(8,:),['m' line])

 

hleg1 = legend('f_4','f_5','f_6','f_7');

grid on;

 

Let us look at the DCT more deeply. I have the vector A of 8 numbers and I use 8 cosine signal vectors with increasing frequencies:

 

One by one, I multiply each cosine signal by my input A to compute the DCT coefficients.


So, I kind of take samples of the input at different points for each coefficient and compute some kind of mean of the sample. Let us multiply A=[ 1     2     3     4     5     6     7     8] by  to compute the coefficient  .

Here is the Matlab code for this experiment.

clear all;

close all;

clc;

A=1:0.1:8;

n=8;

step = 0.1;

t=0:step:n-1;

f=0:n-1;

cosval = zeros(size(f,2),size(t,2));

angle  = zeros(size(f,2),size(t,2));

for fr=1:size(f,2)

    for i=1:size(t,2)

        frequency   = fr-1;

        angle(fr,i) = rad2deg(((2*t(i)+1)*frequency*pi)/(2*n));

       cosval(fr,i) = cos(deg2rad(angle(fr,i)));

    end

end

line='-'

 

plot(A,['m' line]),hold on;

plot(cosval(4,:),['r' line])

plot(A.*cosval(4,:))

hleg1 = legend('A', 'f_5', 'A*f_5')

grid on;

 

 

 

 

1Inverse DCT is defined as:

2You can use anthing here on your website as long as you give credit and provide a noticeable link to www.haberdar.org

3Hakan Haberdar: "Discrete Cosine Transform Tutorial", www.haberdar.org, 2012.