CHAPITRE I LA COMPRESSION D’IMAGE

1
𝑇𝑐 = 𝑡𝑎𝑢𝑥𝑐 = (1 − ) ∗ 100
𝑟𝑎𝑝𝑝𝑜𝑟𝑡 𝑑𝑒 𝑐𝑜𝑚𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛

Cela indique : Qu'un fichier compressé indique à sa taille originale aura un taux de
compression de 0 %. Un fichier réduit à 0 octet, aura un taux de compression de 100%.

I-7-4-2. Entropie :
L'entropie H(S) d'une source simple [S]N associée à une loi de probabilité [P]N est
définie selon la formule suivante :
𝑁

𝐻(𝑆) = − ∑(P(Si)𝑙𝑜𝑔2 (𝑃(𝑆𝑖)) bits

𝑖=1

Dans une image, l’entropie est une grandeur qui caractérise la qualité de l’information
que contient cette dernière. Par exemple, une image dont tous les pixels ont la même valeur
contient très peu d’information car elle est extrêmement redondante, son entropie est faible.

En revanche, une image dont tous les pixels ont une valeur aléatoire contient beaucoup
d’information, son entropie est forte.

En pratique, l’entropie d’une image numérique est inversement liée à la probabilité

d’apparition des niveaux de gris dans l’image. Par définition, l’entropie d’ordre zéro H0est
donnée par :
2ᴿ−1

𝐻0 = − ∑ (P(k)𝑙𝑜𝑔2 (𝑃(𝑘)) bpp

𝑘=1

Avec : P(k) est la probabilité d’apparition des niveaux de gris dans l’image, k est la valeur de
gris et R est le nombre de bits par pixels.

L’entropie H0 d’une image originale fournit le débit minimal qu’il est possible
d’atteindre par compression, pixel par pixel sans dégrader l’image, et par la même, un taux de
compression sans perte maximal.

[Link] de distorsion :

Pour mesurer la distorsion entre l'image reconstruite et l'image originale (Mesure de la

qualité visuelle de l'image reconstruite) on utilise l'Erreur Quadratique Moyenne MSE (Mean
Square Error) ou le rapport signal à bruit PSNR (Peak Signal to Noise Ratio).

Etant donnée une image originale composée de pixels ai(i=1, ..., N)et l'image décodée
composée de pixels a’i(i=1, ..., N).

~ 12 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES(SVD)

[Link] :
La décomposition en valeurs singulières généralise la notion de valeurs propres aux
matrices rectangulaires. C’est un outil de factorisation de telles matrices, et peut être vu
comme le procédée de diagonalisation pour les matrices carrées. Nous utiliserons dans toute
la suite de ce document le sigle SVD pour parler de la décomposition en valeurs singulières
(Singular Values Decomposition pour les anglophones, acronyme largement répandu). Bien
que la SVD s’applique aussi bien aux matrices réelles que complexes, nous ne traiterons
qu’avec des matrices à coefficients réels qui sont celles rencontrées dans les divers champs
d’application de ce calcul de SVD. Néanmoins, tout théorème ou définition générale liée à la
SVD sera énoncé au sens large, et donc pour des matrices à coefficients complexes.
La réduction de matrices rectangulaires par le calcul de la SVD est assez classique
dans la littérature d’aujourd’hui, puisque traitée depuis le milieu des années 1960 par
l’informaticien Gene Howard Golub (auteur du très bon livre Matrix Computations[19]) et le
mathématicien William Morton Kahan, qui proposent en 1965 le premier algorithme pour
calculer la SVD. Cependant, le procédé d’approximation de rang faible consistant au calcul
d’une SVD tronquée, bien connu également au 20èmesiècle, permet plus récemment de fournir
des résultats en analyse de données avec par exemple la complétion de matrices aux données
manquantes. Ce travail qui revient à résoudre un problème d’optimisation convexe est plutôt à
la mode depuis le début des années 2000.
La compression d’images numériques a connu une évolution incessante,parallèlement
à celle des télécommunications et du multimédia, depuis les années [Link] permet de réduire
la taille d’une image dans le but d’augmenter la capacité des supports de stockages (limités en
capacité) et d’optimiser l’utilisation de la bande passante d’un réseau. Depuis la normalisation
de l’algorithme JPEG basé sur la transformée en cosinus discrète, le volume des données
multimédias (son, image, vidéo, etc.) n’a cessé d’augmenter. La norme JPEG2000 basée sur
la transformée par ondelettes a permis d’augmenter le taux de compression des images avec
une qualité supérieure à celle de JPEG.
La SV consistedécomposer une matrice en un produit de 3 matrices U, S et V(Sest
appelée matrice desvaleurs singulières). Chen ainsi qu’Abrahamsen [1]ont déjà proposé une
méthodesimple de compression d’images à niveaux de gris ne retenant que les k
premièresvaleurs singulières. Des améliorations ont été proposées en utilisant l’algorithme
SVD standard. D’autres applications de la décomposition en valeurs singulières comme la
compression et la reconnaissance faciale ont montré que la SVDestutilisée dans plusieurs
domaines de l’imagerie. En ce qui concerne les images encouleurs, Adams et Cooper[17]ont
proposé une méthode qui applique lacompression SVDà chaque composante R, V et B.

[Link] décomposition en valeurs singulières SVD :

Une matrice est un tableau de nombres dont il est parfois difficile d'extraire les
caractéristiques intéressantes pour résoudre un problème donné. Une stratégie efficace pour
mettre en évidence les propriétés d'une matrice est de la décomposer (ou factoriser) en un

~ 15 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES (SVD)

produit de matrices plus simples et dont les caractéristiques sont clairement identifiables et
interprétables. La factorisation la plus générale, et peut-être la plus utile, est la SVD.

La théorie de la décomposition en valeurs singulières a été établie pour les matrices

réelles carrées dans les armées 1870 par Beltrami et Jordan et pour les matrices complexes par
Autonne en 1902. Récemment, la décomposition en valeurs singulières a été utilisée dans
différentes applications du traitement d'image telle que la compression, la dissimulation de
l'information et la réduction du bruit.

Le traitement d'image est une forme de traitement d'information, dans lequel l'entrée
est une [Link] traitement des images étudie comment transformer,stocker, récupérer
l'image. Image digitale,le traitement est l'utilisation d'algorithmes informatiques poureffectuer
un traitement d'image sur des images numé[Link] de techniques de traitement
d'imageont été développées avec des applications comme le traitement d’mage satellitaire à
satelliteimagerie, l’imagerie médicale, la reconnaissance d'objets,et l’amélioration de la photo.
Avec la disponibilité d'ordinateurs et de processeurs rapides pour le traitement de signal dans
lesannées 2000, le traitement numérique des images est devenula forme la plus courante de
traitement d'image,et est généralement utilisé parce que ce n’est pas seulement laméthode la
plus polyvalente, mais aussi la moins chère.

II-2-1. Principe :
L’idée essentielle de la SVD est de décomposer la matrice de données en trois
matrices simples : deux orthogonales et une diagonale. Du fait qu’elle produise une estimation
aux moindres carrés de la matrice de données de même dimension et d’un rang inférieur.
L’un des avantages de la SVD est son pouvoir de réduction des données après leur
blanchissement. En effet, cette technique fournit une description plus compacte des données
contenues dans une matrice, exprimée par les premiers modes statistiques. Elle peut être
considérée comme une méthode permettant de construire une partition de la variance d’une
base de données, c’est à dire qu’elle fournit la base orthogonale qui maximise la variance au
sens des moindres carrés.
La décomposition en valeurs singulières utilise la décomposition en valeurs propres
d’une matrice semi définie positive obtenue par la multiplication d’une matrice par sa
transposée, pour dériver une décomposition similaire applicable à toutes les matrices
rectangulaires composées de nombres réels.

Toute matrice A de taillem×n de rangrpeut être décomposée en une somme, pondérée

de matrices unitaires m × npar Décomposition en Valeurs Singulières.
Lesmatrices U et V sont unitaires et Apeut donc s’écrire :
𝑛

𝐴 = 𝑈𝑆𝑉 = ∑(σ𝑖 u𝑖 𝑣𝑖𝑇 )

𝑇

𝑖=1

~ 16 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES (SVD)

Où S est une matrice diagonale dont lesr-premiers termes diagonaux sont positifs, tous
les autres étant nuls. Les r-termes σ𝑖 non nuls sont appelés valeurs singulières (SV) de A.

Avec :σ1 ≥ σ2 ≥ ⋯ ≥ σ𝑟 et σ𝑟+1 ≥ σ𝑟+2 ≥ ⋯ ≥ σ𝑛 = 0

II-2-2. La décomposition :

Formellement, si A est une matrice rectangulaire, son SVD la décompose comme suit :
𝐴 = 𝑈𝑆𝑉 𝑇
U est la matrice des vecteurs propres normalisés de la matrice 𝐴𝐴ᵀ, c'est-à-dire 𝑈ᵀ 𝑈 = 𝐼.
Les colonnes de 𝑆 sont appelées les vecteurs singuliers gauches de𝐴.
𝑉 est la matrice des vecteurs propres normalisés de la matrice 𝐴𝑇 𝐴,c'est-à-dire 𝑉ᵀ𝑉 = 𝐼.
Les colonnes de 𝑉 sont appelées les vecteurs singuliers droits de𝐴.
𝑆est la matrice diagonale des valeurs singulières.

La SVD a l’importante propriété de donner la meilleure approximation d’une matrice

rectangulaire par une autre matrice de même dimension mais de rang inférieur, au sens des
moindres carrées. Précisément, si « A » est de dimension (m×n)et de rang « 𝑟 », donc « 𝐴 » a
« 𝑟 » valeurs singulières non [Link] décomposition en valeurs singulières (SVD) offre un
nouveau moyen d’extraire des caractéristiques d'une image.

Les principales propriétés théoriques de la SVD relatives à la compression d’image sont :

 La SVD d'une image présente une bonne stabilité. Quand une petite perturbation est
ajoutée à une image, une grande variance de ses (SV) ne se produit pas.
 Les valeurs singulières représentent les caractéristiques dominantes d'une image.

[Link]éorie de La décomposition en valeurs singulières SVD :

[Link] de décomposition en valeurs singulières :

La décomposition en valeurs singulières (SVD)est considérée comme étant un sujet

important en algèbre linéaire par beaucoupmathématiciens. SVD a beaucoupvaleurs pratiques
et thé[Link] particularité de SVD est qu'il peut être effectué sur toutematrice (𝑚, 𝑛)réelle.
Disons que nous avons une matrice 𝐴 avec 𝑚 lignes et 𝑛 colonnes, avec rang 𝑟 et𝑟 ≤ 𝑛 ≤
𝑚 . Alors la matrice 𝐴 peut être factorisée en trois matrices :
𝐴 = 𝑈𝑆𝑉ᵀ (1.1)

~ 17 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES (SVD)

Figure [Link] de factorisation de 𝐴 à 𝑈𝑆𝑉ᵀ

Où la matrice 𝑈(𝑚 ×𝑚) est une matrice orthogonale

𝑈 = [𝑢1 , 𝑢2 , . . . 𝑢𝑟 , 𝑢𝑟+1 , . . . , 𝑢𝑚 ] (1.2)

Les vecteurs de colonne𝑢𝑖 , pour 𝑖 = 1, 2, … , 𝑚,forment unensemble orthonormé :

1 𝑠𝑖 𝑖=𝑗
𝑢𝑖𝑇 𝑢𝑗 =𝛿𝑖𝑗 = { (1.3)
0 𝑠𝑖 𝑖 ≠𝑗

Et la matrice 𝑉(𝑛 ×𝑛) est une matrice orthogonale

𝑉 = [𝑣1 , 𝑣2 , . . . 𝑣𝑟 , 𝑣𝑟+1 , . . . , 𝑣𝑛 ] (1.4)

Les vecteurs de colonne vi, pour i = 1, 2,…, n, forment un ensemble orthonormé:

1 𝑠𝑖 𝑖 = 𝑗
𝑣𝑖𝑇 𝑣𝑗 = 𝛿𝑖𝑗 = { (1.5)
0 𝑠𝑖 𝑖 ≠ 𝑗

Ici, 𝑆(𝑚 ×𝑛) est une matrice diagonale avec les valeurs singulières (SV) sur la diagonale.
La matrice 𝑆 peut être montrée dans la suite

σ1 0⋯ 0
𝑆= [⋮ σ2 ⋱ ⋮] (1.6)
0 0⋯ σn

Pour𝑖 = 1, 2, … , 𝑛, les𝜎𝑖 sont appelées valeurs singulières(SVs) de la matrice A.

On peut prouver que :
σ1 ≥ σ2 ≥ ⋯ ≥ σ𝑟 > 0 et σ𝑟+1 = σ𝑟+2 = ⋯ = σ𝑛 = 0 (1.7)

Pour𝑖 = 1, 2, … , 𝑛,, les𝜎𝑖 sont appelées valeurs singulières(SVs) de la matrice𝐴.

Les 𝑣𝑖 et 𝑢𝑖 sont appelés vecteurs singuliers droits et gauchesde la matrice 𝐴 .[18]

II-3-2 Propriétés du SVD :

 Les valeurs singulières σ1 , σ2 , … , σ𝑛 sont uniques, cependant, les matrices 𝑈 et 𝑉 ne

sont pas uniques.

~ 18 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES (SVD)

 Puisque 𝐴ᵀ𝐴 =𝑉𝑆ᵀ𝑆𝑉ᵀ, donc 𝑉 diagonalise 𝐴ᵀ𝐴, il s’ensuit que les 𝑣𝑗 sont les vecteurs
propres de𝐴ᵀ𝐴.

 Puisque 𝐴𝐴ᵀ = 𝑈𝑆𝑆ᵀ𝑈ᵀ,il en résulte que 𝑈diagonalise 𝐴𝐴ᵀ et que les 𝑢𝑗 sont les
vecteurs propres de𝐴𝐴ᵀ.

 Le rang de la matrice 𝐴 est égal aunombre de ses valeurs singulières non nulles.
 La norme L2 et la norme de Frobenius d’une matrice 𝐴 ∈ 𝑅 𝑚𝑥𝑛 de rang rsont
données respectivement par :
‖𝐴‖2 = 𝜎1 , (1.8)
𝑒𝑡
1
‖𝐴‖𝐹 = (∑𝑟𝑖=1 𝜎𝑖2 )2 , (1.9)
 Si Aest de rang r, alorsV.1 , V.2 , . . . , V.r forment une base orthonormale pour l’espace
Im(𝐴ᵀ)et U.1 , U.2 , . . . , U.r forment une base orthonormale pour l’espace Im(A).
 Le rang de la matrice A est égal au nombre de ses valeurs singulières non nulles [27].

𝐴 = 𝑈𝑆𝑉 𝑇 = ∑𝑛𝑖=1(σ𝑖 u𝑖 𝑣𝑖𝑇 ) (1.10)

II-3-3 Exemple de SVD :

Soit la matrice positive A,

3 10 7
𝐴= [ ]
4 2 1

Nous voulons trouver la décomposition SVD de A,

On a
25 38 25
𝐴𝑇 𝐴 = [38 104 72],
25 72 50

D’après (1.1) , on obtient :

168.3242 0 0
𝐴𝑇 𝐴 = 𝑉 [ 0 10.6758 0] 𝑉 𝑇
0 0 0
Où
−0.3024 0.9485 0.0944
𝑉 = [−0.7846 −0.1915 −0.5897] = [𝑣1 𝑣2 𝑣3]
−0.5412 −0.2524 0.8021

D’où, les valeurs singulières non nulles de A sont : 𝜎1 = √168.3242 = 12.9740

Et 𝜎2 = √10.6758 = 3.2674
Maintenant, d’après (1.1), nous avons 𝑈Σ = 𝐴𝑉, où

~ 19 ~
CHAPITRE II LA DECOMPOSITION EN VALEURS SINGULIERES (SVD)

𝑈Σ = [𝜎1 𝑢1 𝜎2 𝑢2 0] = [12.9740𝑢1 3.2674𝑢2 0],

Et

−12.5420 −0.8361 0
𝐴=[ ]
−3.3201 3.1586 0

Donc
1 −12.5420 −0.9667 1 −0.8361 −0.2559
𝑢1 = 12.9740 [ ]= [ ] , 𝑢2 = 3.2674 [ ]= [ ]
−3.3201 −0.2559 3.1586 −0.9667

Et
−0.9667 −0.2559
𝑈 = [𝑢1 𝑢2 ] = [ ]
−02559 −0.9667

On a aussi, d’après (1.8) et (1.9)

1
‖𝐴‖2 = 𝜎1 = 12.9740 et‖𝐴‖𝐹 = (𝜎12 + 𝜎22 )2 = √179 = 13.3791

II-4.Méthodologie de SVD appliquée en traitement d’images :

II-4-1. Approche SVD pour la compression d'image :

La compression d’image traite le problème de réduction de la quantité de données

nécessaires pour représenter une image numérique. La compression est atteinte par la
suppression de trois données de base redondances:
a) La redondance du codage, qui est présente quand elle n’est pas optimale ;
b) La redondance interpixel qui résulte de la corrélation entre les pixels ;
c) La redondance psychovisuelle, due à des données ignorées par la vision humaine [24].

La propriété de SVD dit « Lerang de la matrice 𝐴 est égal au nombre de ses valeurs
singulières non nulles ». Dans de nombreuses applications, les valeurs singulières d'une
matrice diminuent rapidement avec un rang croissant. Cette propriété nous permet de réduire
le bruit ou compresser les données de la matrice en éliminant les petites valeurs singulières ou
les rangs plus élevés.
Quand une image est transformée en SVD, ce n’est pas compressé, mais les données
prennent une forme dans laquelle la première valeur singulière a une grande quantité
d’informations sur l'image. Avec cela, nous ne pouvons utiliser que quelques valeurs
singulières pour représenter l'image avec de petites différences par rapport à l'originale.
Pour compresser une image par SVD, nous montrons les procédures de détail :
𝑛

𝐴 = 𝑈𝑆𝑉 𝑇 = ∑(σ𝑖 u𝑖 𝑣𝑖𝑇 )

𝑖=1

~ 20 ~