Transformée en cosinus discrète

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant l'analyse (branche des mathématiques), vous pouvez partager vos connaissances en le modifiant.

La Transformée en cosinus discrète ou TCD (de l'anglais : DCT ou Discrete Cosine Transform) est une transformation proche de la transformée de Fourier discrète (DFT). Le noyau de projection est un cosinus et génère donc des coefficients réels, contrairement à la DFT, dont le noyau est une exponentielle complexe et qui génère donc des coefficients complexes. On peut cependant exprimer la DCT en fonction de la DFT, qui est alors appliquée sur le signal symétrisé.

La variante la plus courante de la transformée en cosinus discret est la DCT type-II, souvent simplement appelée "la DCT". Son inverse, qui correspond au type-III est souvent simplement appelée "IDCT".

Une DCT 2D comparée à une DFT. Les zones claires représentent les coefficients non-nuls

[modifier] Applications

La DCT, et en particulier la DCT-II est très utilisée en traitement du signal et de l'image, et spécialement en compression. La DCT possède en effet une excellente propriété de "regroupement" de l'énergie : l'information est essentiellement portée par les coefficients basses fréquences. Pour les images naturelles, la DCT est la transformation qui se rapproche le plus de la transformée de Karhunen-Loève qui fournit une décorrélation optimale des coefficients pour un signal markovien. En pratique, les procédés de compression font donc l'hypothèse qu'une image naturelle peut être modélisée comme la réalisation d'un processus markovien et approximent la transformée de Karhunen-Loève, trop complexe en calcul et dépendante des données, par une DCT. L'intérêt d'une transformation se voit particulièrement bien sur une figure (voir ci-contre). Seuls un petit nombre de coefficients sont non-nuls, et peuvent être utilisés pour reconstruire l'image par transformée inverse (IDCT) lors de la décompression. Le gain en terme de compression vient de la suppression des coefficients nuls ou proches de zéro. Ce genre de mécanisme est utilisé dans les standards JPEG et MPEG, qui utilisent une DCT 2D sur des blocs de pixels de taille 8x8 (pour des raisons de complexité).

Les formats de compression de son avec perte AAC, Vorbis et MP3 utilisent une version modifiée de cette technique, la transformée en cosinus discret modifiée, TCDM (MDCT en anglais).
La DCT est aussi employée pour la résolution de systèmes d'équations différentielles par des méthodes spectrales.

[modifier] définition

La DCT est une fonction linéaire inversible R^N -> R^N ou de manière équivalente une matrice carrée N × N inversible. Il existe plusieurs légères variantes de la DCT. Voici les quatre types les plus connus.

[modifier] DCT-I

$X_k = \frac{1}{2} (x_0 + (-1)^k x_{N-1}) + \sum_{n=1}^{N-2} x_n \cos \left[\frac{\pi}{N-1} n k \right]$

On peut rendre cette transformée orthogonale (à une constante multiplicative près) en multipliant x₀ et x_N-1 par √2 et réciproquement X₀ et X_N-1 par 1/√2. Cette normalisation casse toutefois la correspondance avec une DFT.

On peut noter que la DCT-I n'est pas définie pour $N \le 2$ , contrairement aux autres types qui sont définis pour tout N positif.

[modifier] DCT-II

$X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) k \right]$

Cette variante DCT est la plus courante et la plus utilisée. Elle est généralement simplement appelée "la DCT". De la même manière que pour la DCT-I, on peut rendre cette transformation orthogonale en multipliant X₀ par 1/√2. Cette forme normalisée est très utilisée en pratique mais casse la correspondance avec la DFT.

[modifier] DCT-III

$X_k = \frac{1}{2} x_0 + \sum_{n=1}^{N-1} x_n \cos \left[\frac{\pi}{N} n \left(k+\frac{1}{2}\right) \right]$

La DCT-III est la transformée inverse de la DCT-II. Elle est plus connue sous le nom de "DCT Inverse" et son acronyme (anglais) "IDCT".

De la même manière que pour la DCT-I, on peut rendre cette transformation orthogonale en multipliant x₀ par √2. Cette forme normalisée est très utilisée en pratique mais casse la correspondance avec la DFT.

[modifier] DCT-IV

$X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right]$

La DCT-IV est une matrice orthogonale.

[modifier] Références

K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantages, Applications (Academic Press, Boston, 1990).
A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-Time Signal Processing, second edition (Prentice-Hall, New Jersey, 1999).
S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Sig. Processing SP-42, 1038-1051 (1994).
Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. A free (GPL) C library that can compute fast DCTs (types I-IV) in one or more dimensions, of arbitrary size. Also M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005).
E. Feig, S. Winograd. "Fast algorithms for the discrete cosine transform," IEEE Transactions on Signal Processing 40 (9), 2174-2193 (1992).
P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing 19, 259–299 (1990).
John Makhoul, "A fast cosine transform in one and two dimensions," IEEE Trans. Acoust. Speech Sig. Proc. 28 (1), 27-34 (1980).