Discrete Cosine Transforms

Assignment given out in Graphics class for April 1 2004 - and a bit more.
You should especially check out the basis functions in two dimensions - very cool.

1. Plot the rows of the DCT matrix for n=4.

n = 4;
dct  =  
        Table[ Cos[(Pi/n) j (k + (1/2))], {j, 0, n - 1}, {k, 0, 
              n - 1}] // N;
dct // MatrixForm

Do[ 
ListPlot[dct[[j, All]], 
        PlotJoined -> True],  
{j, 1, 
        4}
]

2. Do the DCT on several vectors and explain result.

The first vector is {3,3,3,3}, which is just a multiple of the first row.  The DCT will have zero amounts of the other three.

dct  .  {3, 3, 3, 3}

The second vector is {-10,10,-10,10}.  The DCT is mostly high frequency.

dct  .  {-10, 10, -10, 10}

The third vector is {1,2,3,4}.  This has a strong constant offset, then a fair amount of the next basis, and little of high frequencies.

dct  .  {1, 2, 3, 4}

3. Show that the rows of the DCT have zero dot product.

The basic idea here is that any two cosine basis vectors of different frequencies are perpendicular.

dct[[2, All]]  .  dct[[4, All]]

This is perhaps less than convincing with Mathematica doing all the work.
The "dot" notation is actually doing this calculation

dct[[2, 1]] dct[[4, 1]]  +  
      dct[[2, 2]] dct[[4, 2]]  +  
      dct[[2, 3]] dct[[4, 3]]  +  
      dct[[2, 4]] dct[[4, 4]]

4. What does the inverse transform look like?

idct  =  Inverse[dct]

% // MatrixForm

idct  .  {12, 0, 0, 0}

5. How does this work on two dimensional data ?

If the data is also a 4x4 matrix, then we apply the DCT transform to each row and each column.  Doing the columns is just mutiplying the whole matrix by the DCT matrix.  To do the rows, we turn them into columns by transposing the matrix.

Here are two functions that perform the forward and backward transform on two dimensional data.

twoDimDct[data_] := 
        Transpose[ dct  .  Transpose[ dct  .  data ]];

invTwoDimDct[dctData_] := 
        Transpose[idct  .  Transpose[idct  .  dctData]];

And here's an example of the transform of a four by four block of ones.  The result is nearly zero everywhere but in the top left.

ones  =  {1. , 1. , 1. , 1. };
onesMap  =  {ones, ones, ones, ones};
onesMap // MatrixForm

twoDimDct[onesMap] // MatrixForm

invTwoDimDct[twoDimDct[onesMap]] // MatrixForm

6. What are the basis functions in two dimensions?

They look like this.

Do[
Print[j, k]; 
ListPlot3D[
        Outer[Times, dct[[j, All]], 
          dct[[k, All]]]], 
{j, 1, n}, {k, 1, 
        n}
]

dct

dct // N // MatrixForm

idct // MatrixForm