Compression JPEG et composantes principales

31 janvier 2023 — Transformée en cosinus, PCA

Pour compresser une image, la norme JPEG utilise une représentation intermédiaire obtenue par un changement de base orthogonale, la transformée en cosinus.

Sous certaines conditions, cette représentation présente une propriété de compaction : l’information est « concentrée » dans la nouvelle base sur un petit nombre de coefficients.

À partir des propriétés statistiques d’un signal, il est possible de construire une base orthogonale optimale du point de vue de la compaction : c’est la transformation de Karhunen–Loève, utilisée pour l’analyse en composantes principales.

Nous allons présenter ici la transformée en cosinus utilisée dans la norme JPEG et verrons comment l’analyse en composantes principales nous éclaire quant à l’efficacité d’une telle transformation.

La compression JPEG

Dans la norme JPEG, une image est divisée en blocs de $8 \times 8$ pixels, qui sont ensuite compressés individuellement.

Cette procédure repose sur un changement de base, utilisant la transformée en cosinus discrète bidimensionnelle.

Pour ce faire, un bloc est assimilé à un signal ${s: ⟦0, 7⟧ \times ⟦0, 7⟧ \rightarrow \R}$ que l’on va représenter dans une base différente.

En pratique, l’image est composée de plusieurs de ces signaux représentant les intensités en rouge, vert et bleu. Nous considérons ici un unique signal correspondant à une image en niveaux de gris.

Transformée en cosinus

La base choisie pour représenter le signal est celle de la transformée en cosinus bidimensionnelle, composée des $8 \times 8$ signaux $e_{u,v}$ définis par :

$e_{u,v}(i, j) = \cos(\frac{(2i + 1)u\pi}{16})\cos(\frac{(2j + 1)v\pi}{16})$

Cette base est orthogonale, ce qui signifie que la transformation s’obtient par un calcul de produit scalaire (en prenant soin de normaliser les vecteurs $e_{u,v}$).

Concrètement, voici une représentation des $64$ vecteurs de base obtenus :

La transformée en cosinus de $s$ est la fonction $\hat{s}$ définie par ${\hat{s}(u, v) = \cfrac{⟨s,e_{u,v}⟩}{\|e_{u,v}\|}}$.

Le code source de l’animation est disponible ici.

Quantification

La quantification est la phase de la compression JPEG durant laquelle de l’information est perdue.

On introduit une matrice de quantification $Q$, comme celle définie ci-dessous :

Chaque coefficient $\hat{s}_{u,v}$ de la transformée va être « réduit » par le coefficient $Q_{u,v}$ correspondant.

Concrètement, les coefficients de $\hat{s}$ aux positions correspondant à des grandes valeurs de $Q_{u,v}$ vont avoir tendance à être effacés.

Il s’agit (à peu près) des coefficients situés en bas et à droite de la matrice, qui correspondent à des fréquences plus élevées et donc à des détails plus fins.

Ces coefficients sont généralement plus faibles pour une image suffisamment régulière — sans variation brusque d’intensité entre pixels proches.

En traitement du signal, on parle de propriété de compaction d’énergie pour signifier que le signal concentre une grande partie de son « énergie » ${\|s\|^2 = \|\hat{s}\|^2 = \sum_{\substack{0 \leq u<8\\0 \leq v<8}} \hat{s}_{u,v}^2}$ dans un faible nombre de termes de cette somme.

Relation avec la DFT

La transformée de Fourier discrète (DFT) est une autre transformée reposant sur un changement de base orthogonale. Pourquoi ne pas l’utiliser directement ?

On montre en fait que la transformée en cosinus (DCT) correspond à une transformée de Fourier discrète d’un signal construit en symétrisant $s$.

Prendre directement la transformée de Fourier discrète du signal source introduirait des composantes de hautes fréquences du fait de la discontinuité entre deux extrémités du signal — qui n’est pas périodique.

Ces aspects sont notamment évoqués dans le cours de Stéphane Mallat au Collège de France.

Analyse en composantes principales

La transformée en cosinus, utilisée par JPEG, a été introduite au début des années 1970 par Nasir Ahmed. Dans un article, il revient sur cette découverte et indique :

The results again showed that this transform performed better than all the others, and its performance compared very closely with that of the KLT.

KLT désigne ici la transformée de Karhunen–Loève, également connue dans le cas d’un signal discret comme l’analyse en composantes principales (PCA).

Cette transformation consiste à construire une base orthogonale dans laquelle représenter le signal, en s’appuyant sur les propriétés statistiques de celui-ci.

Principe de la PCA

On modélise un signal de taille $n$ comme une variable aléatoire ${X = (X_1, ..., X_n)}$ que l’on suppose centrée (i.e. ${\mathbb{E}[X_i] = 0}$ pour tout $i$).

La matrice de covariance $K$ de $X$ est la matrice $n \times n$ définie par :

Cette matrice est symétrique réelle positive, donc diagonalisable avec des valeurs propres réelles $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n \geq 0$ et une matrice de passage $P$ orthogonale.

Considérons la variable aléatoire $Y = PX$, qui correspond à la représentation de $X$ dans une base de vecteurs propres de $K$. La matrice de covariance de $Y$ est la matrice diagonale de coefficients diagonaux $\lambda_1, ..., \lambda_n$.

En particulier, on remarque que :

• les nouvelles coordonnées sont parfaitement décorrélées les unes des autres : $\mathbb{E}[Y_i Y_j] = 0$ pour $i \neq j$
• L’énergie moyenne du signal $\mathbb{E}[\|Y\|^2] = \mathbb{E}[Y_1^2 + ... + Y_n^2] = \lambda_1 + ... + \lambda_n$ est distribuée sur les différentes composantes par ordre décroissant

On retrouve la propriété de compaction de l’énergie, et on peut montrer que ce changement de base est optimal à cet égard (c’est abordé ici).

Pour cette raison, l’analyse en composantes principales est souvent utilisée pour de la réduction de dimension, c’est-à-dire pour représenter approximativement un signal de grande dimension $n$ avec un nombre $d < n$ de variables $Y_1, ..., Y_d$.

Notons qu’en pratique, la base de composantes principales n’est pas calculée en diagonalisant la matrice de covariance (trop grande) mais en calculant la décomposition en valeurs singulières du jeu de données.

C’est ainsi que procède par exemple la fonction PCA de scikit-learn.

PCA et compression d’images

L’analyse en composantes principales est optimale du point de vue de la compaction d’énergie — pourquoi alors ne pas l’utiliser pour la compression d’image ?

On peut par exemple considérer le jeu de données des sous-images $8 \times 8$ d’une image source et en déduire une base optimale pour la représentation de ces sous-images.

La base obtenue a de bonnes propriétés de compaction… mais elle dépend de l’image source. Cette méthode nécessite d’enregistrer les composantes principales en plus des représentations des sous-images, afin de pouvoir reconstruire l’image par transformation inverse.

Comme expliqué ici, la transformée en cosinus s’affranchit de ce problème en définissant une unique base commune.

Par ailleurs, il semble expérimentalement qu’elle fournisse des capacités de compaction proches de celles obtenues avec la PCA. Ceci peut également se justifier théoriquement en considérant que les images correspondent à des réalisations de processus stationnaires.

Un processus stationnaire est une séquence aléatoire dont les propriétés statistiques sont invariantes par translation. En particulier, le coefficient $K_{i,j}$ de la matrice de covariance ne dépend que de $|i-j|$ et la matrice $K$ est circulante.

Les matrices circulantes étant diagonalisées dans une base de vecteurs propres correspondant à la transformée de Fourier discrète, on retrouve pour ces processus des composantes principales se développant comme sommes de fonctions trigonométriques.

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• ← Transformée de Fourier discrète et multiplications
• Logique, arithmétique de Peano et incomplétude →