What is the difference between a Fourier transform and a cosine transform?

Question

In speech recognition, the front end generally does signal processing to allow feature extraction from the audio stream. A discrete Fourier transform (DFT) is applied twice in this process. The first time is after windowing; after this Mel binning is applied and then another Fourier transform.

I've noticed however, that it is common in speech recognizers (the default front end in CMU Sphinx, for example) to use a discrete cosine transform (DCT) instead of a DFT for the second operation. What is the difference between these two operations? Why would you do DFT the first time and then a DCT the second time?

Answer 1

The Discrete Fourier Transform (DFT) and Discrete Cosine Transform (DCT) perform similar functions: they both decompose a finite-length discrete-time vector into a sum of scaled-and-shifted basis functions. The difference between the two is the type of basis function used by each transform; the DFT uses a set of harmonically-related complex exponential functions, while the DCT uses only (real-valued) cosine functions.

The DFT is widely used for general spectral analysis applications that find their way into a range of fields. It is also used as a building block for techniques that take advantage of properties of signals' frequency-domain representation, such as the overlap-save and overlap-add fast convolution algorithms.

The DCT is frequently used in lossy data compression applications, such as the JPEG image format. The property of the DCT that makes it quite suitable for compression is its high degree of "spectral compaction;" at a qualitative level, a signal's DCT representation tends to have more of its energy concentrated in a small number of coefficients when compared to other transforms like the DFT. This is desirable for a compression algorithm; if you can approximately represent the original (time- or spatial-domain) signal using a relatively small set of DCT coefficients, then you can reduce your data storage requirement by only storing the DCT outputs that contain significant amounts of energy.

Answer 2

The reason why you see Fourier transformation applied two times in the feature extraction process is that the features are based on a concept called cepstrum. Cepstrum is a play on the word spectrum - essentially the idea is to transform a signal to frequency domain by Fourier transform, and then perform another transform as if the frequency spectrum was a signal.

While frequency spectrum describes the amplitude and phase of each frequency band, cepstrum characterizes variations between the frequency bands. Features derived from cepstrum are found to better describe speech than features taken directly from the frequency spectrum.

There are a couple of slightly different definitions. Originally cepstrum transform was defined as Fourier transform -> complex logarithm -> Fourier transform [1]. Another definition is Fourier transform -> complex logarithm -> inverse Fourier transform [2]. The motivation for the latter definition is in its ability to separate convolved signals (human speech is often modelled as the convolution of an excitation and a vocal tract).

A popular choice that has been found to perform well in speech recognition systems is to apply a non-linear filter bank in frequency domain (the mel binning you're referring to) [3]. The particular algorithm is defined as Fourier transform -> square of magnitude -> mel filter bank -> real logarithm -> discrete cosine transform.

Here DCT can be selected as the second transform, because for real-valued input, the real part of the DFT is a kind of DCT. The reason why DCT is preferred is that the output is approximately decorrelated. Decorrelated features can be modelled efficiently as a Gaussian distribution with a diagonal covariance matrix.

[1] Bogert, B., Healy, M., and Tukey, J. (1963). The Quefrency Alanysis of Time Series for Echoes: Cepstrum, Pseudo-Autocovariance, Cross-Cepstrum and Saphe Cracking. In Proceedings of the Symposium on Time Series Analysis, p. 209-243.

[2] Oppenheim, A., and Schafer, R. (1968). Homomorphic Analysis of Speech. In IEEE Transactions on Audio and Electroacoustics 16, p. 221-226.

[3] Davis, S., and Mermelstein, P. (1980). Comparison of Parametric Representations for Monosyllabic Word Recognition in Continuously Spoken Sentences. In IEEE Transactions on Acoustics, Speech and Signal Processing 28, p. 357-366.

Answer 3

I found that some of the details in the DCT wiki (also shared by Pearsonartphoto) point out that the DCT is well-suited for compression applications. The end of the Informal overview section is helpful (bolding is mine).

In particular, it is well known that any discontinuities in a function reduce the rate of convergence of the Fourier series...the smoother the function is, the fewer terms in its DFT or DCT are required to represent it accurately, and the more it can be compressed... However, the implicit periodicity of the DFT means that discontinuities usually occur at the boundaries... In contrast, a DCT where both boundaries are even always yields a continuous extension at the boundaries. This is why DCTs...generally perform better for signal compression than DFTs and DSTs. In practice, a type-II DCT is usually preferred for such applications, in part for reasons of computational convenience.

Additionally, you may find that this answer is useful too (from math.stackexchange.com). It states:

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).

Answer 4

The difference between a Discrete Fourier Transform and a Discrete Cosine transformation is that the DCT uses only real numbers, while a Fourier transform can use complex numbers. The most common use of a DCT is compression. It is equivalent to a FFT of twice the length.