Application à la compression d’images

 

C'est un photo d’ Emmy Noether : mathématicienne très connue, comprimé de trois manières différentes

 

Introduction  Une fois recherchées de l'Internet, les images digitales prennent un temps considérable pour télécharger et utilisent une grande proportion de mémoire de l’ordinateur. Les ondelettes  de Haar  que nous discuterons dans cette application représentent une façon  de comprimer des images digitales de manière qu’elles prennent moins d'espace une fois stockées.

 

L'idée fondamentale derrière cette méthode de compression est de traiter une image digitale comme un arrangement rectangulaire des nombres ou une matrice. Chaque image se compose d'un nombre assez grand de petites carrés appelés  Pixels (Picture Elements en anglais). La matrice correspondant à une image digitale associe un nombre entier à chaque Pixel. Par exemple, une image grise de dimension 256x256,  est stockée comme une matrice du format 256x256, avec chaque élément de la matrice est un nombre entier entre 0 (pour le noir) à 225 (pour le blanc). La technique de compression de JPEG divise une image en blocs 8x8 et assigne une matrice à chaque bloc. On peut employer quelques techniques d'algèbre linéaire pour maximiser la compression de l'image et en même temps maintenir un niveau acceptable de détail.

 

 

 

Transformations des vecteurs par les Ondelettes de Haar Avant d’expliquer la transformation d’une matrice, voyons tout d’abord comment les ondelettes transforment les vecteurs (lignes d’une matrice). Supposez que

 

est une ligne d’une matrice 8x8. En géneral, si le vecteur a 2k composantes,  alors le processus de transformation consiste en k étapes. Dans notre cas, le vecteur a 8=23 composantes, et par suite il y aura trois étapes.  

Nous effectuons les opérations suivantes sur les entrées du vecteur r:

1.      Divisez les entrées de r en quatre paires :  

(420, 680), (448, 708), (1260, 1410), (1600, 600).

 

2.      Formez la moyenne de chacune de ces paires:

 

 

 

      Ceux-ci formeront les quatre premières entrées du prochain vecteur r1.

 

3.      Soustrayez chaque moyenne de la première entrée de la paire pour obtenir les nombres:

.

 

      Ceux-ci formeront les quatre premières entrées du prochain vecteur r1.

 

4.      Formez le nouveau vecteur:

 

 

.

 

 

      Notez que le vecteur r1 peut être obtenu à partir de r en multipliant r à droite par la matrice:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Les quatre premières entrées de r1 s’appellent les coefficients d’approximation et les quatre dernières entrées s’appellent les coefficients de détail.

 

Pour notre prochaine étape, nous regardons les quatre premières entrées de r1 en tant que deux paires que nous prenons leurs moyennes comme dans l'étape 1 ci-dessus. Ceci donne les deux premières entrées: 564, 1470 du nouveau vecteur r2. Ce sont nos nouveaux coefficients d'approximation. La troisième et la quatrièmes entrée de r2 sont obtenues en soustrayant ces moyennes du premier élément de chaque paire. Ceci donne les nouveaux coefficients de détail: -14, -130. Les quatre dernières entrées de r2 sont identiques aux coefficients de détail de r1:

 

 

 

 

Ici, le vecteur r2 peut être obtenu de r1 en multipliant à droite par la matrice :

 

 

 

 

 

 

 

 

 

Pour la dernière étape, faites la moyenne des deux premières entrées de r2, et comme avant, soustrayez la réponse de la première entrée. Ceci a comme conséquence le vecteur suivant:

 

 

 

 

Comme avant, le vecteur  r3 peut être obtenu de r1 en multipliant à droite par la matrice :

 

 

 

 

 

 

 

 

 

Par conséquent, on obtient r3 immédiatement de r en utilisant l'équation suivante :

 

 

 

 

 

Posons

 

.

 

 

 

 

 

Noter les faits suivant:

 

 

 

Le fait que W est inversible nous permet de rechercher notre image de la forme comprimée en utilisant la relation :

 

 

 

Supposez que A est la matrice correspondante à une certaine image. La transformation de  Haar consiste à faire la moyenne et la différence de chaque ligne de la matrice A et puis répéter les mêmes opérations sur les colonnes de la matrice résultante. Les transformations sur les lignes donnent la matrice AW. La matrice obtenue en faisant la moyenne et différence sur les colonnes de AW  est obtenue en multipliant AW à gauche par la matrice WT (la transposée de W). Ainsi, la transformation de  Haar ``stocke`` une matrice comme WTAW. Soit S la matrice transformée:

 

 

 

 

En utilisant les propriétés des inverses matricielles, on peut retrouver la matrice originale :

 

*  

 

Ceci nous permet de voir l'image originale (décomprimant l'image comprimée).

 

Il est temps maintenant pour un exemple.

 

 

Exemple  Supposez que nous avons une image 8x8 représentée par la matrice :

 

 

 

 

 

 

Les transformations sur les lignes de A  donne la matrice :

 

 

 

 

 

 

 

En prenant les moyennes et les différences sur les colonnes de of L, on obtient la matrice suivante :

 

 

 

 

 

 

 

 

 

L’idée de la transformation de Haar est que les secteurs de la matrice originale qui contient peu de variation finiront d’être nuls dans la matrice transformée. Une matrice est considérée clairsemée si elle a une proportion élevée d'entrées nulles. Les matrices clairsemées prennent beaucoup moins de mémoire une fois stockées. Puisque nous ne pouvons pas nous attendre à ce que les matrices transformées toujours soient clairsemées, nous décidons d'une valeur- seuil non négative connue comme ε, et nous laissons ensuite n'importe quelle entrée dans la matrice transformée dont la valeur absolue est moins que ε d’être remis à zéro. Ceci nous laissera avec un genre de matrice clairsemée. Si ε est zéro, toutes les entrées de la matrice demeurent inchangées.

 

Chaque fois que vous cliquez une image pour la télécharger de l'Internet, l'ordinateur de source rappelle la matrice transformée de sa mémoire. Il envoie d'abord les coefficients globaux d'approximation et de plus grands coefficients de détail et un peu plus tard les coefficients plus petits de détail. Pendant que votre ordinateur reçoit l'information, il commence à reconstruire progressivement les détails jusqu'à ce que l'image originale soit entièrement reconstruite.

 

L'algèbre linéaire peut rendre le processus de compression plus rapide, plus efficace

Commençons par rappeler qu’une matrice carrée de format nxn s'appelle orthogonale si ses colonnes forment une base orthonormale de Rn. En d’autres mots, les colonnes de A sont deux à deux orthogonales et la longueur de chaque vecteur colonne est 1. D'une manière équivalente, A est orthogonal si son inverse est égal à sa transposée. Cette dernière propriété rend le processus de rechercher l'image transformée par l'intermédiaire de l'équation

 

 

beaucoup plus rapide.

 

 

Une autre propriété puissante des matrices orthogonales est qu'elles préservent la grandeur. En d'autres termes, si v est un vecteur de Rn et A est une matrice orthogonale, alors ||Av||=||v||. Voici comment cela fonctionne :

 

 

 

 

 

Ceci montre ||Av||=||v||. Aussi, la transformation qui utilise une matrice orthogonale préserve  l’angle: rappelez-vous que le cosinus de l'angle entre deux vecteurs u et v est donné par:

 

 

Si A est une matrice orthogonale et ψ est l’angle entre les deux vecteurs Au et Av, alors

 

 

 

Comme la grandeur et l'angle sont préservés, il y a sensiblement moins de déformation produite dans l'image reconstruite quand une matrice orthogonale est employée. Puisque la matrice W de transformation est le produit de trois autres matrices, on peut normaliser W en normalisant chacune des trois matrices. La version normale de W est :

 

 

 

 

 

 

 

 

 

 

 

Remarque Si vous regardez de plus proche le processus que nous avons décrit ci-dessus, vous noterez que la matrice W n'est rien qu’une matrice de changement de base pour R8. En d'autres termes, les colonnes de W forment une nouvelle base (``très utile``) de R8. Ainsi quand vous multipliez un vecteur v (écrit dans la base standard) de R8 par W, vous obtenez  les coordonnées de v dans cette nouvelle base. Certaines de ces coordonnées peuvent être ``négligées`` en utilisant notre seuil et ceci permet à la matrice transformée d'être plus facile et plus rapide à stocker.

 

La valeur- seuil Si nous choisissons notre valeur- seuil ε de sorte qu’elle soit strictement positive (non-nulle), alors quelques entrées de la matrice transformée seront remises à zéro et donc un certain détail sera perdu quand l'image est décomprimée. La question clé est alors comment choisir ε de sorte que la compression soit faite efficacement avec une déformation minimale à l'image. Nous définissons le rapport de compression comme étant le rapport des entrées non-nulles dans la matrice transformée (S=WTAW) au nombre d'entrées non-nulles dans la matrice comprimée obtenue à partir de S en appliquant le seuil ε.