Discrete Cosine Transformation (DCT)

[Max]

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 (1.62 KiB) Viewed 237 times

DCT Encoding
The general equation for a 1D (N data items) DCT is defined by the following equation:

img26.gif (1.94 KiB) Viewed 237 times

and the corresponding inverse 1D DCT transform is simple F^(-1)(u), i.e.:

where

img27.gif (1.07 KiB) Viewed 237 times

The general equation for a 2D (N by M image) DCT is defined by the following equation:

img28.gif (3.44 KiB) Viewed 237 times

and the corresponding inverse 2D DCT transform is simple F^(-1)(u,v), i.e.:

where  

img29.gif (1.08 KiB) Viewed 237 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 (1.08 KiB) Viewed 237 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 (68.17 KiB) Viewed 237 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 (4.12 KiB) Viewed 237 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 (2.1 KiB) Viewed 237 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.
    

[Downrange]

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.
 

The 2-D form is also affected.

(Link Removed)

[Max]

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

I think it is right as Sigma i is used and refer to
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.