Slide #1.

The Frequency Domain Light and the DCT Pierre-Auguste Renoir: La Moulin de la Galette from http://en.wikipedia.org/wiki/File:Renoir21.jpg
More slides like this


Slide #2.

DCT (1D)  Discrete cosine transform  The strength of the ‘u’ sinusoid is given by C(u)    2 Project f onto the basis function All samples of f contribute the coefficient C(0) is the zero-frequency component – the average value!
More slides like this


Slide #3.

DCT (1D) Consider a digital image such that one row has the following samples  Index 0 1 2 3 4 5 6 7 Value 20 12 18 56 83 10 104 114  There are 8 samples so N=8   u is in [0, N-1] or [0, 7] Must compute 8 DCT coefficients: C(0), C(1), …, C(7)  Start with C(0) 3
More slides like this


Slide #4.

DCT (1D) 4
More slides like this


Slide #5.

DCT (1D)  Repeating the computation for all u we obtain the following coefficients Spatial domain Frequency domain 5
More slides like this


Slide #6.

DCT (1D) implementation   Since the DCT coefficients are reals, use array of floats This approach is O(?) public static float[] forwardDCT(float[] data) final float alpha0 = (float) Math.sqrt(1.0 / final float alphaN = (float) Math.sqrt(2.0 / float[] result = new float[data.length]; } { data.length); data.length); for (int u = 0; u < result.length; u++) { for (int x = 0; x < data.length; x++) { result[u] += data[x]*(float)Math.cos((2*x+1)*u*Math.PI/(2*data.length)); } result[u] *= (u == 0 ? alpha0 : alphaN); } return result; 6
More slides like this


Slide #7.

DCT (2D)  The 2D DCT is given below where the definition for alpha is the same as before  For an MxN image there are MxN coefficients Each image sample contributes to each coefficient Each (u,v) pair corresponds to a ‘pattern’ or ‘basis function’   7
More slides like this


Slide #8.

DCT basis functions (patterns) Basis functions 8 Basis patterns (imaged functions)
More slides like this


Slide #9.

Separability  The DCT is separable   9 The coefficients can be obtained by computing the 1D coefficients for each row Using the row-coefficients to compute the coefficients of each column (using the 1D forward transform)
More slides like this


Slide #10.

Invertability  The DCT is invertible  10 Spatial samples can be recovered from the DCT coefficients
More slides like this


Slide #11.

Summary of DCT  The DCT provides energy compaction     Low frequency coefficients have larger magnitude (typically) High frequency coefficients have smaller magnitude (typically) Most information is compacted into the lower frequency coefficients (those coefficients at the ‘upper-left’) Compaction can be leveraged for compression  11  Use the DCT coefficients to store image data but discard a certain percentage of the high-frequency coefficients! JPEG does this
More slides like this


Slide #12.

DCT Compaction and Compression source 12 discarding 95% of dct discarding 99% of dct
More slides like this


Slide #13.

Implementation 13
More slides like this