Décomposition en valeurs singulières

(SVD)

Introduction

Ce projet a pour but la restauration d’images par l’utilisation de la décomposition en valeurs singulières (SVD). Nous allons étudier cette technique en effectuant tout d’abord une approche mathématique de la SVD. Puis nous verrons quelles sont les influences sur une image des choix de valeurs propres lors de la SVD. Enfin nous verrons comment utiliser la SVD pour restaurer des images dégradées par un flou gaussien ou par un bruit blanc additif.

1. Présentation du problème

1.1. Introduction

Considérons une image couleur contenant lignes et colonnes. Sa matrice représentative est une matrice tridimensionnelle . Dans l’étude qui suit, nous nous limiterons à une image F en niveau de gris (i.e. une matrice). Pour traiter une image couleur, il suffira de traiter chacune des trois composantes RVB comme une composante monochrome.

1.2. Problème bidimensionnel

Notre image F a subi un défaut H linéaire et spatialement invariant (un flou gaussien par exemple). L’image dégradée G est obtenue par convolution de F avec H :

[1]

Possédant G, l’objectif est de retrouver l’image d’origine F connaissant le défaut H appliqué. Dans la pratique, on ne connaît pas le défaut H , on ne fait qu’une supposition (par exemple que le défaut est un flou gaussien mono-dimensionnel d’écart type 5 pixels).

Pour retrouver l’image F, il suffit d’inverser l’équation [1], ce qui est loin d’être trivial. H n’est pas inversible et de plus l’inversion d’un produit de convolution n’est pas aisée. On cherchera donc à se ramener à un problème de produit matriciel.

1.3. Problème mono-dimensionnel

1.3.1.

Considérons maintenant nos images comme des signaux mono-dimensionnels. Le vecteur f (id. g) associé à l’image F (id. G) est la mise bout à bout des lignes F (id. G):

[2]

L’équation [1] devient alors :

[3]

Où S est une matrice Toeplitz-bloc-Toeplitz de taille . L’annexe I démontre que S est une matrice Toeplitz-bloc-Toeplitz et en donne un aperçu.

1.3.2.

On cherche donc à résoudre le système [3], c’est-à-dire trouver une matrice K telle que

[4]

Des problèmes se posent assez rapidement puisque l’inversibilité de la matrice S n’est pas garantie, le système peut être bruité. De nombreuses méthodes existent pour résoudre de tels systèmes (avec approximation ou pas). Parmi celles-ci, la décomposition en valeurs singulières (SVD) reste la plus générale.

2. Approche algébrique de la SVD

2.1. Théorème général

Enoncé : Toute matrice S de dimension pour laquelle le nombre de lignes N est supérieur ou égal au nombre de colonnes M peut s’écrire sous la forme du produit d’une matrice orthonormée V de dimension , d’une matrice diagonale de dimension dont les éléments sont positifs ou nuls et de la transposée d’une matrice orthonormée U de dimension .

[5]

Remarques : Les matrices U et V sont orthonormées c-à-d. [6].

Les sont les valeurs singulières de la matrice H.

2.2. Observations pratiques

La matrice H est rectangulaire de dimension , elle est donc au plus de rang M. Supposons par la suite que H est de rang .

§ En utilisant [5], .

est une matrice de dimension dont les valeurs propres sont telles que :

et dont les M vecteurs propres associés sont les , colonnes de U.

§ De même, .

est une matrice de dimension dont les valeurs propres sont les mêmes que celles de et telles que :

et dont les M vecteurs propres associés sont les , colonnes de V.

§ On range les valeurs singulières par ordre décroissant de telle sorte que :

2.3. Résolution

Les éléments diagonaux de la matrice obtenue par la relation [5], peuvent être nuls. Afin de résoudre notre problème, il faut pouvoir inverser cette matrice. Nous sommes donc amenés à tronquer cette matrice afin de ne conserver que les termes strictement positifs. Dans la suite nous verrons qu’il arrive même que l’on tronque la matrice au-delà de ces valeurs. La résolution du système [5] conduit donc à la formule suivante :

d’où, [7].

3. Influence des valeurs singulières sur une image

L’image de référence que nous prenons pour cette étude est celle de Lena :

image de référence : Lena.

Voyons maintenant quelle est l’influence des valeurs singulières sur cette image. Pour cela, nous effectuons la SVD de l’image et lors de la phase de reconstruction, nous ne conservons qu’un nombre N de valeurs singulières. Le code Matlab qui a permis ces manipulations se trouve en Annexe II.

Une première analyse nous montre que la photo de Lena de taille possède 507 valeurs singulières (V.S.) « significatives ». Le terme « significatives » se justifie par le fait que la 507^è V.S. vaut 0.73 tandis que la 508^è vaut 3.07.10^-11. Soit un rapport de 10^-10.

A noter que le précision de Matlab est de l’ordre de 5 chiffres significatifs. Donc les valeurs singulières significatives doivent avoir un rapport de moins de 10^-5 avec la valeur maximale () ; les autres étant considérées comme « erronées ». La 507^è V.S. vérifie bien cette condition.

En conservant presque toutes les valeurs singulières N=500, nous ne pouvons voir à l’œil nu les modifications créées . La carte des erreurs nous montre les pixels où ont eu lieu les changements.

image reconstituée avec 500 V.S. carte des erreurs.

Nous faisons de même en ne conservant maintenant que 250, 100, 50, 20 puis 10 V.S.

*nombre de* VS	*image reconstituée*	*carte des erreurs*
250
100
50
20
10

Cette étude nous montre que les valeurs singulières contiennent les informations de l’image. Cependant les valeurs singulières de faible amplitude contiennent peu d’information et leur influence n’est visible que si on en omet un grand nombre. Dans ce cas là, la présence des valeurs singulières à forte amplitude permet la bonne compréhension de l’image (avec seulement 10 valeurs singulières sur plus de 500, on voit très bien que l’image représente une tête !!). Seuls les détails ont disparu.

4. La SVD pour la restauration d’images

4.1. Cas d’un flou gaussien

4.1.1. Image d’étude

Maintenant nous allons mettre en application la décomposition en valeurs singulières pour la restauration d’images dégradées. Prenons comme image d’étude, l’image ci-dessous obtenue par convolution de l’image de Lena avec un flou gaussien bidimensionnel d’écart type 5 pixels et de largeur 24 pixels (ce qui permet d’avoir un rapport supérieur à 100 entre la valeur du centre et les bords du cache):

cache gaussien d’écart-type 5 pixels.

Lena floue.

Le cas du flou gaussien permet quelques simplifications. Le flou bidimensionnel est séparable en flous monodimensionnels comme suit :

Cela s’écrit matriciellement : .

L’inversion des matrices et n’est pas triviale. On s’en remet donc à la décomposition en valeurs singulières : .

La restauration de l’image s’obtient donc par : [8], ce qui permet de ne manipuler que des matrices de taille .

Le code Matlab pour la restauration de la photo précédente est présent en Annexe III.

4.1.2. Influence des valeurs singulières


130	120

110	100

90	80

50

Pour la restauration des images, nous avons considéré que nous connaissions exactement le flou appliqué, ce qui n’est pas le cas généralement. Malgré cela, la restauration est difficile et très sensible au nombre de valeurs singulières conservées. Si on ne garde pas assez de V.S., l’image se dégrade rapidement. Dans le cas contraire, un tramage apparaît sur l’image restaurée. Ce ramage s’explique par ce qui suit :

Le cache utilisé n’est pas infini. Il a été tronqué ce qui correspond à la convolution avec une fonction « Porte ». Lors de la reconstruction de l’image, cette « porte » se manifeste par un sinus cardinal responsable du tramage.

4.2. Cas d’une image bruitée

Prenons tout d’abord une image bruitée. Elle est obtenue à partir de l’image de référence par l’ajout d’un bruit blanc additif.

Image bruitée

L’objectif de cette partie est d’utiliser la SDV afin d’éliminer au maximum ce bruit tout en conservant une image claire.

Les valeurs singulières de l’image sont en quelque sorte les représentantes de l’image dans l’espace fréquentiel : à une valeur singulière correspond une fréquence discrète. Un bruit blanc (dans le domaine fréquentiel, l’amplitude du bruit blanc est constante) de faible amplitude est insignifiant devant l’importance des valeurs singulières de forte amplitude . Par contre ce bruit blanc biaise fortement les fréquences correspondant aux valeurs singulières de faible amplitude (de l’ordre du bruit blanc). Moyennant cette réflexion, nous pouvons tracer un graphe de la distance de l’image reconstruite à l’image originale en fonction du nombre de valeurs singulières considérées :

La difficulté de la restauration d’images bruitées réside donc dans le choix du nombre de valeurs singulières à conserver. En conserver plus de N conduit à obtenir une image encore bruitée, alors qu’en garder moins de N donne une image où on a perdu des informations qu’on aurait pu conserver.

On utilise le même code que lors de la partie 3 (code en Annexe II).

Voici les résultats obtenus :

*nombre de* *VS conservées*	*image reconstituée*	*carte des erreurs*
250
120
100
50

Pour 250 valeurs singulières conservées, l’image reste encore beaucoup bruitée. La carte des erreurs montre que l’on a effectivement enlevé un peu de bruit.

Lorsque l’on ne conserve que 50 valeurs singulières, le résultat est tout autre. L’image n’est pas nette. La carte des erreurs permet d’éclaircir cette situation. La reconstruction avec 50 V.S. a bien fait disparaître du bruit (les points) mais aussi de l’information (surtout des contours). D’ou cette impression de flou.

La difficulté du choix du nombre de V.S. à considérer s’illustre avec les cas 120 et 100. Dans le premier cas, beaucoup de bruit a déjà été retiré et toute l’information (à un iota près) a été conservée. Dans le second cas, on a purifié un peu plus l’image par rapport au bruit mais au détriment d’un peu d’information qui a été perdue en chemin (cf. carte des erreurs). Où se situe la limite qui permet la meilleure restauration ?

4.3. Cas d’une image dégradée par un flou gaussien et un bruit blanc

On met en application les deux techniques ci-dessus. A savoir, éliminer dans un premier temps le bruit blanc en sélectionnant un nombre adéquat de valeurs singulières, puis restaurer l’image en éliminant le flou gaussien grâce à la relation [8].

Conclusion

Les résultats obtenus par cette méthode de restauration d’une image par décomposition en valeurs singulières sont plus ou moins satisfaisants. Certes, il est toujours possible de récupérer une image assez proche de l’originale, mais pour cela il faut jouer sur le nombre de valeurs singulières conservées et la modélisation adoptée :

- Le traitement sur l’image témoin permet de vérifier la validité de notre modèle. En effet, nous avons mis en évidence que si l’ensemble des valeurs singulières était conservé, l’écart avec l’image témoin était quasi-nul et que la qualité de l’image restituée se détériore au fur et à mesure que l’on prend en considération un nombre plus restreint de valeurs singulières.

- Le même traitement appliqué à une image bruitée prouve que les petites valeurs singulières sont plus sensibles au bruit et que par conséquent leur prise en compte lors de la restauration dégrade le résultat obtenu et qu’il est donc préférable de tronquer la suite des valeurs singulières ; la difficulté étant de déterminer la valeur de troncature optimale.

- Enfin, les résultats obtenus sur une image distordue par un flou gaussien sont les moins probants. Effectivement, même s’il semble que le choix d’un optimum pour la troncature suive une loi similaire à celle qui régit la restitution d’une image bruitée, l’interprétation est plus hasardeuse. Malgré tout, une valeur moyenne pour la troncature permet toujours d’obtenir une image de meilleure qualité que l’image floue.

Annexe I : la matrice Toeplitz-bloc-Toeplitz S

Hypothèses :

[1]

[2]

[3]

Démonstration :

· Préliminaire

L’équation [1] donne . En utilisant la notation mono-dimensionnelle, la formule devient : [i]. Pour la démonstration on prend une matrice H bidimensionnelle infinie (ie ).