Re: {JPEG}Discrete Cosine Transformation

From: Brian Stone (no.more.spam_at_stoneentertainment.com)
Date: 07/14/04 

Date: 14 Jul 2004 11:17:58 -0700

davem@cs.ubc.ca (Dave Martindale) wrote in message news:<ccvv3u$2qn$5@mughi.cs.ubc.ca>...
> hoffmann@fho-emden.de (Gernot Hoffmann) writes:
>
> >in at least one of the URLs in the other posts the DCT is considered
> >as the cosine part of the discrete Fourier series. Thatīs wrong.
> >The cosines in the DCT have a phase shift.
> >Some illustrations are here:
> >http://www.fho-emden.de/~hoffmann/jpeg131200.pdf
> >The graphics may help to understand the SHAPES of the functions in the
> >function system.
>
> In addition, the discrete Fourier transform assumes that the input
> function is periodic in a very simple way: copies of the input image are
> effectively tiled out to infinity in all directions, but each tile has
> the same orientation. This means there are often abrupt discontinuities
> at the tile boundaries, where left edge of one copy meets right edge of
> the adjacent tile, and so on. This in turn means there is sometimes
> lots of high-frequency content, which is difficult to compress.
>
> The discrete cosine transform assumes a more complex tiling, where the
> original image is mirror-imaged across each tile boundary. This means
> the input is mathematically an even function, so if you did a Fourier
> transform of the double-sized mirrored and reflected image it would have
> zero imaginary component to every coefficient. This also makes the DCT
> coefficients compress better than FFT coefficients.
>
> Dave

I just want to enhance the answers here. It's important to have a
fundamental understanding of what the Frequency domain is, and how it
represents a complex signal. As you may know, any analog signal can
be represented as the sum of an infinite set of waveforms...

   w(t) = a * cos(t + T) + b * sin(t + T)

Where a and b are constant coefficients that define the shape of the
sine wave, (T+t) is the period of the wave at time t. This equation
is known as a "waveform".

A signal is the sum of multiple waveforms...
  
                      n
                     ___
                     \
    W(t) = k * / a[i] * cos(2*pi + t + T) + b[i] * sin(2*pi +
t + T)
                    ---
                    i=0

This summation is called the Fourier Series. If n = infinity, then
this Fourier Series is "continuous", if n = some finite number, then
the Fourier series is "discrete". There is a pair of coefficients (a
and b) for every waveform, which are known in this form as the Fourier
Coefficients. Using this equation, we can reproduce any signal as
long as we have the set of the Fourier coefficients.

But, what if we just have the signal, and we want to figure out what
the coefficients are? This is EXACTLY what the Fourier Transform
does. It takes in a signal and outputs the Fourier coefficients of
each waveform that makes up that signal.

Why is this important to image processing? Because, most of the
visual information that our brains can process correlates well with
low-frequency waveform patterns. That is, waveforms that have
relatively small values for a and b. By transforming an image to the
Fourier domain, we can filter out the high-frequency waveforms,
leaving only the low-frequency waveforms. This leaves us with a much
less noisy signal that compresses much, much better.

So, this leads us to the Discrete Cosine Transform. The DCT is simply
the Fourier Transform, but with the Sine component phase-shifted by 90
degrees. That's it! That's all it is. The following equation is
known as the Cosine Series...

                      n
                     ___
                     \
    W(t) = k * / a[i] * cos(2*pi + t + T) + b[i] * cos(pi + t
+ T)
                    ---
                    i=0

There are two reasons why the DCT is important to the JPEG algorithm.
First, it shifts the origin o the data to a[0], b[0], where as the
origin of the DFT is always at a[T/2], b[T/2]. The output of the DCT
is a triangular matrix, with increasing frequency radiating outwards
from a[0], b[0] to a[T], b[T]. This makes it particularly easy to
filter out those high-frequencies.

The second reason why the DCT is important is that there is 1/4 less
information to deal with versus the DFT. If you read Guido's and
Dave's messages, you'll learn that the reason is due to internal
scaling that takes place somewhat mysteriously. There's nothing
mysterious about it, and the concept is very, very, very well known
(Take a discrete math course Guido!). If you take the DFT and simply
fold in quadrants 1, 2, and 3 onto quadrant 4... then you have a DCT.
The end result of which is, rather un mysteriously, 1/4 of the
information required to represent the signal with just as much
accuracy as the larger DFT.

Relevant Pages

  • Re: {JPEG}Discrete Cosine Transformation
    ... >>as the cosine part of the discrete Fourier series. ... >>The cosines in the DCT have a phase shift. ... A signal is the sum of multiple waveforms... ...
    (comp.programming)
  • Re: Proving the relationships between FSCTFT and CTFTDTFT
    ... Continuous-Time Fourier Transform. ... multiplication by an infinite Dirac comb samples the infinite real line to ... You end up with periodic, or aliased, frequencies. ... You end up with the finite discrete FT. ...
    (comp.dsp)
  • Re: Confused about DFT and Fourier Series and Fourier Transform?
    ... time and two have discrete time which is another yes/no pair. ... frequencies can only take on discrete values and if the time is ... FS, or Fourier Series, is the Fourier Transform of rotation angles. ... > since all of these are orthonormal transforms and maintain the same signal ...
    (sci.math)
  • Re: Problem with Discrete Fourier block
    ... I have look under the mask for the fourier block (not the ... from the help section the angle should ... does the discrete version of this works the ...
    (comp.soft-sys.matlab)
  • Re: Query DCT and DFT
    ... So to compute the fourier series, ... For DFT, ... For DCT, the sequence is mirrored and then ... applications) or of type-I corresponds to even boundary conditions at ...
    (sci.image.processing)