8
$\begingroup$

What are the differences between a (discrete) cosine transform and a (discrete) Fourier transform? I know the former is used in JPEG encoding, while the latter plays a big part in signal and image processing. How related are they?

$\endgroup$
  • 1
    $\begingroup$ They are basically the same thing, and it is very easy to translate between the two using the identity cos x = (e^{ix} + e^{-ix})/2. $\endgroup$ – Qiaochu Yuan Jul 29 '10 at 20:34
  • 5
    $\begingroup$ I think this question is kinda of vague, and the wikipedia article seems to already do a fair amount of comparison. Could explain what confuses about the wikipedia article, or what is lacking there you would like more description with? $\endgroup$ – Jonathan Fischoff Jul 29 '10 at 20:52
9
$\begingroup$

Cosine transforms are nothing more than shortcuts for computing the Fourier transform of a sequence with special symmetry (e.g. if the sequence represents samples from an even function).

To give a concrete example in Mathematica ($VersionNumber >= 6), consider the sequence

smp = {1., 2., 3., 4., 5., 4., 3., 2.};

The sequence has redundancy (e.g. smp[[2]] == smp[[8]], but note that in usual Fourier work, the indexing is taken to be from $0$ to $n-1$ instead of $1$ to $n$). A sequence like smp is termed an even sequence. The discrete Fourier transform of smp can be expected to have redundancy as well:

Fourier[smp] // Chop
{8.48528137423857, -2.414213562373095, 0, -0.4142135623730949, 0,
-0.4142135623730949, 0, -2.414213562373095}

and the discrete Fourier transform is itself even. One could hope to have a way to compute the discrete Fourier transform without redundancy, and this is where the type I discrete cosine transform (DCT-I) comes in:

FourierDCT[Take[smp, Length[smp]/2 + 1], 1] // Chop
{8.48528137423857, -2.414213562373095, 0., -0.4142135623730949, 0.}

The more usual type II discrete cosine transform (DCT-II) is the redundancy-free method for computing the Fourier transform of a so-called "quarter wave even" sequence (with an additional transformation to make the results entirely real for real inputs). A quarter wave even sequence looks like this:

smp = {1., 2., 3., 4., 4., 3., 2., 1.};

and the correspondence (e.g. smp[[2]] == smp[[7]]) is easily seen. DCT-II requires only half of the given sequence to do its job:

Exp[2 Pi I Range[0, 7]/16] Fourier[smp]/Sqrt[2] // Chop
{4.999999999999999, -1.5771610149494746, 0, -0.11208538229199128, 0, 
 0.11208538229199126, 0, 1.5771610149494748}

FourierDCT[Take[smp, Length[smp]/2], 2] // Chop
{5., -1.577161014949475, 0, -0.11208538229199139}

(We see in this example that the exploitation of symmetry in this case led to a slightly more accurate result.)

The other two types of discrete cosine transforms, as well as the four types of discrete sine transforms, are intended to be redundancy-free methods for computing discrete Fourier transforms. For DCT-I, one can deal with a sequence of length $\frac{N}{2}+1$ instead of a sequence of length $N$, while for DCT-II, only a length $\frac{N}{2}$ sequence is required. This represents a savings in computational time and effort. (I assume the case of even length here; a similar symmetry property can be established for the case of odd length.)

In any event, I wish to point out two good references on how FFT and the DCTs/DSTs are related: Van Loan's Computational Frameworks for the Fast Fourier Transform and Briggs/Henson's The DFT: an owner's manual for the discrete Fourier transform.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.