Discrete Cosine Transformation (DCT)

Computer Graphics & Vision Topics
Post Reply
Max
Sergeant
Sergeant
Posts: 17
Joined: Tue Jul 21, 2009 3:31 pm

Discrete Cosine Transformation (DCT)

Post by Max » Wed Sep 30, 2009 2:35 am

The discrete cosine transformation (DCT) helps separate the image into parts (or spectral sub-bands) of differing importance (with respect to the image's visual quality). The DCT is similar to the discrete Fourier transform: it transforms a signal or image from the spatial domain to the frequency domain.
fig2.gif
fig2.gif (1.62 KiB) Viewed 10696 times
DCT Encoding
The general equation for a 1D (N data items) DCT is defined by the following equation:
img26.gif
img26.gif (1.94 KiB) Viewed 10696 times
and the corresponding inverse 1D DCT transform is simple F^(-1)(u), i.e.:

where
img27.gif
img27.gif (1.07 KiB) Viewed 10696 times
The general equation for a 2D (N by M image) DCT is defined by the following equation:
img28.gif
img28.gif (3.44 KiB) Viewed 10696 times
and the corresponding inverse 2D DCT transform is simple F^(-1)(u,v), i.e.:

where
img29.gif
img29.gif (1.08 KiB) Viewed 10696 times
The basic operation of the DCT is as follows:
  • The input image is N by M;
  • f(i,j) is the intensity of the pixel in row i and column j;
  • F(u,v) is the DCT coefficient in row k1 and column k2 of the DCT matrix.
  • For most images, much of the signal energy lies at low frequencies; these appear in the upper left corner of the DCT.
  • Compression is achieved since the lower right values represent higher frequencies, and are often small - small enough to be neglected with little visible distortion.
  • The DCT input is an 8 by 8 array of integers. This array contains each pixel's gray scale level;
  • 8 bit pixels have levels from 0 to 255.
  • Therefore an 8 point DCT would be:

    where
    img29.gif
    img29.gif (1.08 KiB) Viewed 10696 times
    Question: What is F[0,0]?

    answer: They define DC and AC components.
  • The output array of DCT coefficients contains integers; these can range from -1024 to 1023.
  • It is computationally easier to implement and more efficient to regard the DCT as a set of basis functions which given a known input array size (8 x 8) can be precomputed and stored. This involves simply computing values for a convolution mask (8 x8 window) that get applied (summ values x pixelthe window overlap with image apply window accros all rows/columns of image). The values as simply calculated from the DCT formula. The 64 (8 x 8) DCT basis functions are illustrated below.
    DCT.jpg
    DCT.jpg (68.17 KiB) Viewed 10696 times
    DCT basis functions
  • Why DCT not FFT?
    DCT is similar to the Fast Fourier Transform (FFT), but can approximate lines well with fewer coefficients.
    Topic5.fig_47.gif
    Topic5.fig_47.gif (4.12 KiB) Viewed 10696 times
    DCT/FFT Comparison
  • Computing the 2D DCT
    • Factoring reduces problem to a series of 1D DCTs:
      • apply 1D DCT (Vertically) to Columns
      • apply 1D DCT (Horizontally) to resultant Vertical DCT above.
      • or alternatively Horizontal to Vertical.
      The equations are given by:
      Topic5.fig_117.gif
      Topic5.fig_117.gif (2.1 KiB) Viewed 10696 times
    • Most software implementations use fixed point arithmetic. Some fast implementations approximate coefficients so all multiplies are shifts and adds.
    • World record is 11 multiplies and 29 adds.
User avatar
Downrange
Posts: 1
Joined: Thu Oct 15, 2009 3:08 am

Re: Discrete Cosine Transformation (DCT)

Post by Downrange » Thu Oct 15, 2009 5:29 pm

I believe the above representation of the DCT is incorrect. At a minimum, it does not produce the values given in the example under 'DCT basis functions'.

Lambda(i) should be Lambda(u) in the 1-D form.
Image

The 2-D form is also affected.

(Link Removed)
Max
Sergeant
Sergeant
Posts: 17
Joined: Tue Jul 21, 2009 3:31 pm

Re: Discrete Cosine Transformation (DCT)

Post by Max » Thu Oct 15, 2009 6:18 pm

Downrange wrote: Lambda(i) should be Lambda(u) in the 1-D form.
Image
I think it is right as Sigma i is used and refer to Image
Or else I do not understand your point. I'm open to discuss :)

Also, I have copied this article from a site as per request from a user. If you can explain DCT in a better way, you are welcome to add an article here.
Post Reply

Return to “Graphics & Vision”