Optimisation de la compression d’image
Transition, transformation, conversion.
Transition, transformation, conversion. Optimisation de la compression d’image 1 / 17
Problématique
Comment construire un algorithme de compression d’image performant ?
Transition, transformation, conversion. Optimisation de la compression d’image 2 / 17
Sommaire
1 Introduction
2 Décomposition en produit de matrices
3 Transformée en cosinus discrète
4 Analyse des performances
5 Conclusion
Transition, transformation, conversion. Optimisation de la compression d’image 3 / 17
Sommaire
1 Introduction
2 Décomposition en produit de matrices
Première approche : diagonalisation
Algorithme de décomposition en valeurs singulières
3 Transformée en cosinus discrète
4 Analyse des performances
5 Conclusion
Transition, transformation, conversion. Optimisation de la compression d’image 4 / 17
Compression matricielle
Première approche
( )
Soit M = mij 1≤i,j≤n la matrice des pixels l’image en nuance de gris:
∀i, j ∈ [|1, n|], mij ∈ [0, 255]
M est carrée, de taille n × n
Transition, transformation, conversion. Optimisation de la compression d’image 5 / 17
Compression matricielle
Première approche
On suppose que la matrice M est diagonalisable :
M = P DP −1
avec :
λ1 0 · · · 0
| | | 0 λ2 · · · 0
P = v 1 v 2 · · · vn et D = . .. . . ..
.. . . .
| | |
0 0 ··· λn
(v1 , ..., vn ) les vecteurs propres de M
λ1 ≥ ... ≥ λn les valeurs propres de M
Transition, transformation, conversion. Optimisation de la compression d’image 6 / 17
Compression matricielle
Première approche
Notons Mk la matrice approximative de M obtenue par compression.
−1
Mk = Pn,k · Dk,k · Pk,n
avec :
▶ Pn,k la matrice P réduite à la taille n lignes et k colonnes.
▶ Dk,k la matrice D réduite aux k plus grandes valeurs propres de M .
Transition, transformation, conversion. Optimisation de la compression d’image 7 / 17
Compression matricielle
Première approche
Figure: Image (1024 × 1024) associée à la matrice M1020 .
Problème : la matrice M n’est pas forcément diagonalisable
Transition, transformation, conversion. Optimisation de la compression d’image 8 / 17
Compression matricielle
Meilleure approche
On utilise donc une décomposition en valeurs singulières (SVD):
Théorème : Décomposition en valeurs singulières
Soit M ∈ Mn (R), alors:
M = U DV T
avec :
▶ U, V orthogonales de tailles n × n
▶ D = diag(σ1 , ..., σn ) et σ1 ≥ ... ≥ σn
Transition, transformation, conversion. Optimisation de la compression d’image 9 / 17
Compression matricielle
Meilleure approche
On redéfinit donc Mk :
Mk = Un,k · Dk,k · (V T )k,n
On obtient:
Figure: Image (1024 × 1024) associée à la matrice M50
Transition, transformation, conversion. Optimisation de la compression d’image 10 / 17
Sommaire
1 Introduction
2 Problématique
3 Décomposition en produit de matrices
4 Transformée en cosinus discrète
Définition
Présentation de l’algorithme
5 Analyse des performances
6 Conclusion
Transition, transformation, conversion. Optimisation de la compression d’image 11 / 17
Transformée en cosinus discrète
Définition
Définition DCT
La Transformée en Cosinus Discrète (DCT) de M est :
∑
n ∑
n
(DCT(M ))ij = mpq ·Tp (i)·Tq (j)
p=1 q=1
avec:
√
1, si k = 0
∀u ∈ [|1, n|] : Tk (u) = √ ( )
n
2 cos πk(2u+1) , si k > 0
n 2n
Transition, transformation, conversion. Optimisation de la compression d’image 12 / 17
Transformée en cosinus discrète
Définition
Définition IDCT
La Transformée en Cosinus Discrète inverse (IDCT) de M est :
∑
n ∑
n
(IDCT(M ))ij = DCT(M )pq · Ti (p) · Tj (q)
p=1 q=1
Transition, transformation, conversion. Optimisation de la compression d’image 13 / 17
Transformée en cosinus discrète
Application de la matrice de quantification
On définit la matrice de quantification comme
Qij = (i + j + 1) · k
Application de la formule sur une matrice B:
⌊ ⌋
Bij
B’ij = · Qij
Qij
où Qij est l’élément correspondant dans la matrice de quantification.
Transition, transformation, conversion. Optimisation de la compression d’image 14 / 17
Transformée en cosinus discrète
Exemple avec une matrice 3 × 3
Pour une matrice B de taille 3 × 3:
10 20 30 1 2 3
B = 40 50 60 , Q = 2 3 4
70 80 90 3 4 5
On obtient la matrice quantifié B ′ :
10 20 30
B’ = 40 48 60
69 80 90
Transition, transformation, conversion. Optimisation de la compression d’image 15 / 17
Transformée en cosinus discrète
Algorithme
▶ Appliquer la DCT
▶ Création de la matrice de quantification
▶ Quantification des coefficients de la DCT
▶ Appliquer l’Inverse de la DCT à la matrice quantifiée
Transition, transformation, conversion. Optimisation de la compression d’image 16 / 17
Sommaire
1 Introduction
2 Problématique
3 Décomposition en produit de matrices
4 Transformée en cosinus discrète
5 Analyse des performances
Coefficient d’efficacité
Utilisation d’un réseau KNN
6 Conclusion
Transition, transformation, conversion. Optimisation de la compression d’image 17 / 17
