Voir la source de Transformée en cosinus discrète

La '''transformée en cosinus discrète''' ou '''TCD''' (de l'[[anglais]] : '''DCT''' ou '''''{{Langue|en|Discrete Cosine Transform}}''''') est une transformation proche de la [[Transformation de Fourier discrète|transformée de Fourier discrète]] (DFT). Le noyau de projection est un cosinus et crée donc des coefficients réels, contrairement à la DFT, dont le noyau est une exponentielle complexe et qui crée 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 discrète est la DCT type-{{II}}, souvent simplement appelée « la DCT ». Son inverse, qui correspond au type-{{III}} est souvent simplement appelée « IDCT ».

[[Image:Phalaenopsis fft dct.png|thumb|200px|right|Une DCT 2D comparée à une [[transformée de Fourier discrète|DFT]]. Les zones claires représentent les coefficients non nuls]]

== 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 [[Analyse en composantes principales|transformée de Karhunen-Loève]] qui fournit une décorrélation optimale des coefficients pour un signal [[Chaîne de Markov|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 [[Chaîne de Markov|markovien]] et approximent la [[Analyse en composantes principales|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 matière 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 [[Moving Picture Experts Group|MPEG]], qui utilisent une {{nobr|DCT 2D}} sur des blocs de pixels de {{nobr|taille 8×8}} (pour des raisons de complexité).

Les formats de compression de son avec perte [[Advanced Audio Coding|AAC]], [[Vorbis]] et [[MP3]] utilisent une version modifiée de cette technique<!-- « Indeo Audio Coder » l’utilise également selon l’article « Indeo » sur WP:EN -->, la {{lien|lang=en|trad=Modified discrete cosine transform|fr=transformée en cosinus discrète 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.

== Définition ==
La DCT est une fonction [[Application linéaire|linéaire]] inversible '''R'''{{Exp|''N''}} → '''R'''<sup>''N''</sup>  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.

Le développement des algorithmes de calcul rapide des transformées DCT se basent sur la possibilité de décomposer la matrice de définition sous forme d'un produit de matrices dont le calcul est plus simple, et permet de réduire le nombre de multiplications scalaires, en profitant des identités remarquables de [[Fonction périodique|périodicité]] et [[symétrie]]s des fonctions sinusoïdales. Ainsi, on peut décomposer toute transformée DCT de '''R'''{{Exp|''N''}} en transformées plus simples en décomposant ''N'' en [[Décomposition en produit de facteurs premiers|produit de facteurs premiers]], et en composant des sous-transformées dans '''R'''{{Exp|''n''}} où ''n'' est l'un de ces facteurs. En particulier, de nombreuses optimisations ont été développées quand ''N'' est une puissance de 2.

Cela revient à réécrire la matrice ''N'' × ''N'' sous forme de produit de sous-matrices identiques (disposées en [[Pavage du plan|pavage]] régulier et utilisant donc des coefficients réels communs ou différenciés uniquement par leur signe) et de matrices à coefficients unitaires ou nuls (-1, 0 ou 1), ces dernières ne nécessitant pas de multiplication.

=== DCT-{{I}} ===
:<math>X_k = \frac{1}{2} \left( x_0 + (-1)^k x_{N-1} \right) + \sum_{n=1}^{N-2}{x_n \cos\left[ \frac{\pi}{N-1} n k \right]}</math>

On peut rendre cette transformée [[Matrice orthogonale|orthogonale]] (à une constante multiplicative près) en multipliant ''x''<sub>0</sub> et ''x''<sub>''N''-1</sub> par √2 et réciproquement ''X''<sub>0</sub> et ''X''<sub>''N''-1</sub> par 1/√2. Cette normalisation casse toutefois la correspondance avec une [[Transformation de Fourier discrète|DFT]].

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

=== DCT-{{II}} ===
:<math>X_k = \sum_{n=0}^{N-1}{x_n \cos\left[ \frac{\pi}{N} \left( n + \frac{1}{2} \right) k \right]}</math>

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 [[Matrice orthogonale|orthogonale]] en multipliant ''X''<sub>0</sub> par 1/√2. Cette forme normalisée est très utilisée en pratique mais casse la correspondance avec la [[Transformation de Fourier discrète|DFT]].

==== Exemple pour N = 8 ====
Un développement optimisé de cette transformée pour le cas N=8 (utilisé dans JPEG et MPEG) est obtenu en réécrivant la transformée sous forme matricielle et en factorisant la décomposition, pour réduire le nombre de multiplications scalaires nécessaires. Par exemple, la décomposition suivante est utilisée pour la factorisation par l'algorithme de Chen<ref>W. Chen, C.H. Smith, and S.C. Fralick, « A fast computational algorithm for the discrete cosine transform », ''IEEE Trans. Commun.'', Vol. COM-25, p. 1004-1009, Sep. 1977.</ref>, ici orthogonalisée (voir remarque ci-dessus) :

;Coefficients constants de calcul
:<math>
\begin{pmatrix} C_1 \\ C_2 \\ C_3 \\ C_4 \\ C_5 \\ C_6 \\ C_7 \end{pmatrix}
= \sqrt{\frac{2}{N}} . \begin{pmatrix}
\cos{\frac{ \pi}{16}} \\
\cos{\frac{2\pi}{16}} \\
\cos{\frac{3\pi}{16}} \\
\cos{\frac{4\pi}{16}} \\
\cos{\frac{5\pi}{16}} \\
\cos{\frac{6\pi}{16}} \\
\cos{\frac{7\pi}{16}} \\
\end{pmatrix} \approx
\begin{pmatrix} 0,49039 \\ 0,46194 \\ 0,41573 \\ 0,35355 \\ 0,27779 \\ 0,19134 \\ 0,09755 \end{pmatrix}
</math>
  
;DCT(8) (méthode de calcul rapide)
:<math>
\begin{pmatrix} X_0 \\ X_2 \\ X_4 \\ X_6 \end{pmatrix} =
\begin{bmatrix}
C_4 &  C_4 &  C_4 &  C_4 \\
C_2 &  C_6 & -C_6 & -C_2 \\
C_4 & -C_4 & -C_4 &  C_4 \\
C_6 & -C_2 &  C_2 & -C_6
\end{bmatrix} .
\begin{pmatrix} x_0 + x_7 \\ x_1 + x_6 \\ x_2 + x_5 \\ x_3 + x_4 \end{pmatrix}
</math>
:<math>
\begin{pmatrix} X_1 \\ X_3 \\ X_5 \\ X_7 \end{pmatrix} =
\begin{bmatrix}
C_1 &  C_3 &  C_5 &  C_7 \\
C_3 & -C_7 & -C_1 & -C_5 \\
C_5 & -C_1 &  C_7 &  C_3 \\
C_7 & -C_5 &  C_3 & -C_1
\end{bmatrix} .
\begin{pmatrix} x_0 - x_7 \\ x_1 - x_6 \\ x_2 - x_5 \\ x_3 - x_4 \end{pmatrix}
</math>

La formule optimisée pour une DCT unidimensionnelle est souvent utilisée telle quelle pour son utilisation dans l'espace bidimensionnel (par transposition et composition) ; cette formule permet de réduire de façon remarquable le calcul de 1024 multiplications (formule de base) à 512 multiplications seulement dans le traitement d'un bloc image 8×8 (deux passes de 32 multiplications pour chaque ligne de 8 valeurs, qui font 512 multiplications) ; cependant, des optimisations sont encore possibles en optimisant la composition elle-même des deux passes (horizontale et verticale) pour réduire encore de 256 à 91 multiplications seulement (voire moins selon des recherches plus récentes).

On notera aussi que la première matrice ci-dessus permet aussi une réécriture de nombreuses multiplications communes (et donc la formule ci-dessus nécessite beaucoup moins que les 32 multiplications, 16 si on regroupe les sous-expressions communes). On pourrait encore décomposer facilement la première matrice car elle est elle-même une transformée DCT dans '''R'''{{exp|''4''}}, décomposable en deux sous-matrices de '''R'''{{exp|''2''}}.

De nombreuses études ont montré comment cette transformée peut être optimisée en fonction des contraintes, notamment quand la transformée est utilisée pour la [[Compression d'image|compression]], car la transformée permet de concentrer l'essentiel de l'énergie dans les coefficients obtenus ''x''{{ind|''i''}} d'indice faible, les autres concentrant peu d'énergie ont une contribution faible sur le signal spatial initial et sont réduits à zéro lors des étapes de [[Quantification (signal)|quantification]]. Ainsi, la précision nécessaire pour représenter les derniers coefficients est plus faible voire nulle, et les coefficients constants ''C''{{ind|''i''}} utilisés pour le calcul des multiplications scalaires peuvent faire l'objet d'optimisation spécifique, en fixant leur précision, et en utilisant des techniques de multiplication par un nombre réduit d'additions-décalages sans avoir besoin d'utiliser une multiplication générique.

Néanmoins, cet algorithme de calcul (présenté tel quel, il calcule la DCT unidimensionnelle à 8 points avec 16 multiplications) est à la base de toutes les optimisations suivantes par factorisation des sous-matrices. L'algorithme de Loeffler<ref>C. Loeffler, A. Ligtenberg et G. Moschytz, « Practical Fast 1D DCT Algorithms With 11 Multiplications », dans ''Proceedings of the International Conference on Acoustics, Speech, and Signal Processing'', p. 988--991, 1989</ref> est actuellement le plus efficace ayant été publié (avec 11 multiplications pour la même DCT à 8 points au lieu de 16 avec l'algorithme de Chen, toutefois certains coefficients subissent deux multiplications et cela pourrait rendre l'algorithme moins stable). Il a même été démontré que le nombre minimum théorique de multiplications nécessaires pour la transformation DCT à 8 points ne peut être inférieur à 11, ce qui fait que les algorithmes à 11 multiplications scalaires sont optimums en matière de performance brute (ils se différencient seulement en termes de stabilité suivant l'ordre dans lequel les multiplications sont réalisées, et la précision dès lors nécessaire pour les produits intermédiaires).

Cependant l'algorithme de Loeffler regroupe 8 des 11 multiplications scalaires sur les sorties, ce qui permet de regrouper ces multiplications avec l'étape suivante de quantification (ce qui en fait tout l'intérêt) : pour une transformée 2D 8×8, il faut 8×11 multiplications pour la transformée des lignes, et seulement 8×3 multiplications pour les colonnes, soit un total de 112 multiplications (au lieu de 256 avec l'algorithme de Chen) si les 64 dernières multiplications scalaires sont effectuées avec la quantification. Plus de détails sont disponibles dans les normes de compression [[JPEG]] et [[MPEG]].

=== DCT-{{III}} ===
:<math>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]}</math>

La DCT-{{III}} est la transformée inverse de la DCT-II. Elle est plus connue sous le nom de « DCT Inverse » et son [[Acronymie|acronyme]] (anglais)  "IDCT".

De la même manière que pour la DCT-I, on peut rendre cette transformation [[Matrice orthogonale|orthogonale]] en multipliant ''x''<sub>0</sub> par √2. Cette forme normalisée est très utilisée en pratique mais casse la correspondance avec la [[transformée de Fourier discrète|DFT]].

==== Exemple pour N = 8 ====
En reprenant l'exemple ci-dessus, on obtient une décomposition inverse (ici orthogonalisée) également utilisée dans l'algorithme de Chen :

;IDCT(8) (méthode de calcul rapide)
:<math>
\begin{pmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{pmatrix}
=
\begin{bmatrix}
C_4 &  C_2 &  C_4 &  C_6 \\
C_4 &  C_6 & -C_4 & -C_2 \\
C_4 & -C_6 & -C_4 &  C_2 \\
C_4 & -C_2 &  C_4 & -C_6
\end{bmatrix}
.
\begin{pmatrix} X_0 \\ X_2 \\ X_4 \\ X_6 \end{pmatrix}
+
\begin{bmatrix}
C_1 &  C_3 &  C_5 &  C_7 \\
C_3 & -C_7 & -C_1 & -C_5 \\
C_5 & -C_1 &  C_7 &  C_3 \\
C_7 & -C_5 &  C_3 & -C_1
\end{bmatrix}
.
\begin{pmatrix} X_1 \\ X_3 \\ X_5 \\ X_7 \end{pmatrix}
</math>
:<math>
\begin{pmatrix} x_7 \\ x_6 \\ x_5 \\ x_4 \end{pmatrix}
=
\begin{bmatrix}
C_4 &  C_2 &  C_4 &  C_6 \\
C_4 &  C_6 & -C_4 & -C_2 \\
C_4 & -C_6 & -C_4 &  C_2 \\
C_4 & -C_2 &  C_4 & -C_6
\end{bmatrix}
.
\begin{pmatrix} X_0 \\ X_2 \\ X_4 \\ X_6 \end{pmatrix}
-
\begin{bmatrix}
C_1 &  C_3 &  C_5 &  C_7 \\
C_3 & -C_7 & -C_1 & -C_5 \\
C_5 & -C_1 &  C_7 &  C_3 \\
C_7 & -C_5 &  C_3 & -C_1
\end{bmatrix}
.
\begin{pmatrix} X_1 \\ X_3 \\ X_5 \\ X_7 \end{pmatrix}
</math>

Là aussi, l'évaluation scalaire de ce [[produit matriciel]] contient de nombreuses sous-expressions communes permettant des réductions du nombre de multiplications scalaires nécessaires.

=== DCT-{{IV}} ===
:<math>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]}</math>

La DCT-{{IV}} est une matrice [[Matrice orthogonale|orthogonale]].

== Références ==
<references />
* {{en}} {{pdf}}''[http://www.dt.e-technik.tu-dortmund.de/publikationen/documents/EUSIPCO2006_Heyne.pdf A computationally efficient high-quality Cordic-based DCT]''[http://www.dt.e-technik.tu-dortmund.de/publikationen/documents/EUSIPCO2006_Heyne.pdf , B. Heyne, C. C. Sun, J. Goetze et S. J. Ruan] : amélioration de l'algorithme de calcul de Loeffler par la transformation de Cordic, analyse de complexité et comparaison des performances obtenues, pour le calcul de la transformée DCT à 8 points (PDF).

== Bibliographie ==
* 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 ([[Licence publique générale GNU|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, "[http://fftw.org/fftw-paper-ieee.pdf 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).

== Voir aussi ==
* [[Transformation de Fourier|Transformée de Fourier]]
* [[Transformation de Fourier discrète|Transformée de Fourier discrète]]
* [[JPEG|Compression JPEG]] - DCT appliquée au format JPEG

== Liens externes ==

{{Portail|mathématiques|imagerie numérique}}

[[Catégorie:Analyse harmonique discrète]]
[[Catégorie:Compression d'image]]
[[Catégorie:Transformée du signal|Cosinus discrète]]
[[Catégorie:Transformation de suite|Cosinus discrète]]