75
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So several have explained the difference between the two processes. Does anyone know why the dft and the dct are used at different times in speech recognition? Is the output of the first dft considered symmetric? Or is the compression of the dct suited to packing more information in the first 13 points (speech processing generally only uses those)? $\endgroup$ – Nate Glenn Aug 17 '11 at 14:28
  • $\begingroup$ Is your question related to Mel-frequency cepstrum, which was asked in another question? $\endgroup$ – rwong Aug 17 '11 at 16:20
  • $\begingroup$ My question was 2 parts: the difference between DCT and DFT, and why DCT is often used for signal processing after DFT and Mel Binning are applied, instead of another DFT. $\endgroup$ – Nate Glenn Aug 18 '11 at 3:48
  • $\begingroup$ why in image processing, we don't use discrete sine transform instead of discrete cosine transform? $\endgroup$ – user7537 Jan 11 '14 at 20:41
  • $\begingroup$ Hi rimondo, this is a good question but you posted it as an answer. You should create a new question to ask it. $\endgroup$ – Nate Glenn Jan 12 '14 at 0:27
48
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ @JasonR "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." Hmmmm...Im not sure I completely agree with you on this - if only because the DFT already includes a cosine onto which a signal is going to be projected against - how can a DFT then not show as much of the strength of that projection and a DCT can? Thanks. $\endgroup$ – Spacey Dec 3 '11 at 5:25
  • 3
    $\begingroup$ This is a very well-known feature of the DCT, which explains its use in so many compression algorithms. I believe it has to do with the boundary conditions assumed by the DCT at the edges of the signal, which are different from the DFT's. $\endgroup$ – Jason R Dec 4 '11 at 16:54
23
$\begingroup$

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

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Re. PCA in feature extraction: a true PCA would be pointless here because it would be data dependent! If you compute the PCA of the mel-frequency log coefficients from one dataset, and then from another one, you will find a different basis - which would mean that if PCA was used in the feature extraction process, the features extracted on one signal wouldn't "mean the same" as the features extracted on the other signal. Now do this experiment: compute the PCA on a set of log Mel coef. extracted from 10 hrs of the most diverse audio. The basis you'll find is uncannily similar to the DCT basis. $\endgroup$ – pichenettes Feb 14 '12 at 9:13
  • 3
    $\begingroup$ Put in other words: to be useful in recognition application, the decorrelation transform at the end of the feature extraction process must be a sort of compromise suitable to "audio" in general, rather than data specific. It turns out that the DCT basis is very close to what you get when you run a PCA on a large set of audio! $\endgroup$ – pichenettes Feb 14 '12 at 9:16
  • $\begingroup$ I recently saw PCA used in the end of the feature extraction process in an experimental speech system. That system computed the PCA projection from the training data and used the same basis afterwards. $\endgroup$ – Seppo Enarvi Mar 22 '12 at 3:30
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It is however possible to conceive of the DCT/DST of a complex sequence, where one separately takes the DCT/DST of the real and imaginary parts. $\endgroup$ – user276 Dec 1 '11 at 4:52
  • $\begingroup$ so can we say that if I compute DFT I get DCT for free, all I need to do is remove the imaginary parts of the vector. Please correct me if I'm wrong. $\endgroup$ – Marek Oct 6 at 11:10
  • 1
    $\begingroup$ It's a little more complex than that, but it is possible to convert between a FFT and DCT fairly easily. $\endgroup$ – PearsonArtPhoto Oct 6 at 15:21

protected by jojek Mar 24 '16 at 8:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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