Rapport de projet, module de Traitement de l'image

 

Modélisation et synthèse de textures par lois conjointes des coefficients de transformée en ondelettes complexes

 

 

Karim Belhani, Ibrahim Boumezrag, Josselin Huaulmé

DEA MVA - 2002-2003

 

Introduction

 

Il s'agissait dans ce projet d'étudier le travail de Javier Portilla et Eero P Simoncelli sur la modélisation et la synthèse de textures. Leur approche est explicitée dans l'article : « Texture modeling and synthesis using joint statistics of Complex Wavelet Coefficients » que l'on peut trouver sur le site suivant (il est préférable de prendre la version de décembre 2000 qui présente un jeu de statistiques qui caractérise correctement un ensemble de textures plus large):

 

http://decsai.ugr.es/~javier/

 

            Par ailleurs une implémentation en langage Matlab  des algorithmes d'extraction de la caractérisation d'une texture et de synthèse d'une texture à partir d'une caractérisation est disponible à l'adresse suivante (Software/textureSynth) ainsi que l'implémentation de la  transformée en ondelettes utilisée (Software/PyrTools):

 

http://www.cns.nyu.edu/~lcv/index.html

 

Un autre site utile pour charger des exemples de textures est le suivant:

 

http://graphics.stanford.edu/projects/texture/links.html

 

 

            Nous poserons dans un premier temps un cadre général pour l'analyse-synthèse de textures. Nous regarderons ensuite les choix opérés par les auteurs : statistiques utilisées pour caractériser une texture et méthode d'analyse-synthèse. Ces 2 premières parties sont en fait un résumé de l'article. La dernière partie sur laquelle nous insisterons plus est l'étude de l'influence des différentes statistiques sur la qualité des extrapolations obtenues sur des exemples de textures.

 

 

L'analyse-synthèse de textures : à la recherche d'un jeu de statistiques caractéristique

 

On explique ici le but que l'on se donne quand on fait de l'analyse-synthèse de textures.

 

On représente mathématiquement une texture, comme une image, par un vecteur aléatoire X(n,m) où .

 

Conjecture de Julesz

 

 appelées fonctions de contrainte telles que

 

(toutes les réalisations de 2 textures X et Y sont perceptuellement indiscernables)

ó

()

 

Note1 : Cette conjecture exprime l'hypothèse qu'il existe un nombre fini de statistiques nécessaire et suffisant pour caractériser toutes les textures (au « yeux » de la perception humaine). Le but de l'analyse de texture devient alors d'isoler ce jeu de statistiques.

 

Note2 : On se contente en pratique de trouver un jeu suffisant de statistiques (on ne cherche pas le plus petit jeu de statistiques).

 

Note3 : On utilise dans la pratique les moyennes empiriques au lieu des espérances, par exemple pour les statistiques d'ordre 1 :

(où  est la valeur entre « crochet » modulo N et (N,M) sont les dimensions de l'image). Sous l'hypothèse d'ergodicité de X et pour L suffisamment grand c'est équivalent.

 

On cherche donc un jeu de statistiques tels que l'égalité de leur moyenne empirique sur 2 textures implique l'indiscernabilité perceptuelle de celles-ci. L'analyse d'une texture se ramènera alors au calcul des moyennes empiriques des  et la synthèse à la génération aléatoire d'un élément de l'ensemble des images dont les moyennes empiriques des  seront égales à celles spécifiées.

 

Un modèle de texture comprendra donc:

·        la définition des statistiques , c'est-à-dire la méthode utilisée pour calculer les  à partir d'une occurrence  de la texture

·        la méthode utilisée pour générer aléatoirement une occurrence de la texture à partir des

 

Nous allons maintenant pouvoir regarder les choix opérés par les auteurs.

Choix des auteurs

 

            Il n'y a pas de méthode pour choisir le jeu de statistiques qui va à la fois être suffisant pour caractériser un ensemble de textures et minimum (en nombre de paramètres). D'ailleurs les auteurs de l'article semblent avoir eut du mal à fixer ce jeu de statistiques puisque celui-ci a changé entre les versions de l'article et que les statistiques utilisées dans l'implémentation Matlab sont encore différentes. Il y a une constante néanmoins : elles sont basées sur une représentation en « pyramide mobile ». Nous présenterons donc cette représentation dans une première partie, avant de lister sommairement les statistiques utilisées dans l'article le plus récent (décembre 2000) et enfin la méthode de synthèse sera explicitée.

 

 

 Décomposition d'une image en « pyramide  mobile»

 

 

            La décomposition-reconstruction d'image en « pyramide mobile » se fait selon le schéma ci-dessous . Le bloc entouré en tirets doit être reporté récursivement à la place du point noir pour obtenir la structure pyramidale.

 

            La première étape sépare par convolution (domaine spatial) ou produit (domaine fréquentiel) à l'aide de filtres passe-haut (H0) et passe-bas (L0) les composantes de hautes et basses fréquences dans l'image. Les basses fréquences sont à nouveau filtrées en « hautes » fréquences et basse fréquences après sous échantillonnage (sans perte d'information puisqu'il ne reste que les basse fréquences) grâce aux filtres B1 (en fait un passe-bande puisque les hautes fréquences ont déjà été séparées) et L1 (passe-bas). On peut à nouveau sous-échantillonner, puis filtrer à l'aide de nouveaux filtres B2, L2…

 

 

 

            En fait les filtres L0, L1 … n'apparaissent pas dans la pratique, seuls H0, B1, …, Bn et Ln sont utilisés. De plus le pavage du plan des fréquences se fait radialement. On obtient donc un pavage tel que ci-dessous, l'espace à l'extérieur correspond à H0, le premier anneau à B1, le deuxième à B2, B3… jusqu'au disque intérieur correspondant à Ln. Le choix d'un pavage radial n'est pas anodin il va nous permettre de subdiviser selon les directions pour obtenir un nouveau pavage (les parties grisées dans le graphe ci-dessous sont les parties du plan fréquence couvertes par un filtre):

 

 

Le bloc-diagram d'une telle décomposition (avec séparation selon K directions) devient:

 

 

 

Un tel pavage est réalisé par exemple par les filtres décrits ci-après, où N est le nombre de sous-bandes et K le nombre de directions utilisées dans la décomposition. Attention il ne s'agit pas d'une base (les fonctions sur lesquelles est construite la représentation ne sont pas orthogonales) mais bien d'une frame :

 

 

 

avec  si  et 0 sinon

et si  et 0 sinon

 

Filtres auxquels on ajoute les 2 filtres passe-haut et passe-bas qui eux ne sont pas subdivisés selon les directions :

 si  et 1 si r supérieur et 0 si inférieur.

 

 si  et 0 si r supérieur et 1 si inférieur.

 

            Les spectres correspondant sont (pour 3 sous-bandes et 4 orientations) :

 

 

 

            En spatial cela donne (on ne représente qu'une sous-bande) :

 

 

            Enfin il nous reste à ajouter que pour avoir une information de phase nous utiliserons des filtres complexes (ó 2 filtres tels que décrits précédemment en quadrature de phase).

 

            La décomposition de l'image d'un disque suivant le schéma maintenant complet donne (pour 4 directions et 3 sous-bandes avec la partie réelle à gauche et imaginaire à droite) :

 

 

 

Les statistiques utilisées

 

 

            Nous listons sommairement ci-dessous les statistiques utilisées dans le modèle de texture des auteurs (cf article de décembre 2000).

 

1.      Statistiques sur l'image originale et les reconstructions à chaque échelle de la « pyramide mobile », c'est-à-dire l'image aux différentes résolutions

·        à l'ordre 1 on prend pour l'image originale les 4 premiers « moments » : moyenne, variance, skewness et kurtosis, ainsi les minimum et maximum (6 paramètres). Auxquels on ajoute les skewness et kurtosis des images reconstruites à chaque échelle (sans la dernière qui correspond à l'image originale mais avec le résidu aux basses fréquences) ce qui fait 2(N+1) paramètres supplémentaires. Les auteurs prennent aussi surprenament la variance du résidu haute fréquence (?).

·        à l'ordre 2 on prend la restriction de la matrice d'autocorrélation à un voisinage de pixels pour les N+1 images reconstruites (sans la reconstruction complète mais avec le résidu basses fréquences), soient  paramètres en prenant en compte la symétrie de la matrice d'autocorrélation.

2.      Statistiques sur les sous-bandes

·        Corrélations entre les modules de coefficients de sous-bandes à des positions (autocorrélation), échelles ou orientations proches (intercorrélations). Pour calculer l'intercorrélation à des deux échelles différentes on interpole et suréchantillonne la sous-bande d'échelle plus grossière. Le nombre de nouveaux paramètres introduits est  pour l'autocorrélation de chaque orientation de chaque sous-bande (la matrice est à nouveau restreinte à un bloc de ),   pour la corrélation à chaque sous-bande d'une orientation avec les autres,  pour la corrélation aux N-1 sous-bandes les plus fines avec toutes les orientations à la sous-bande d'échelle supérieure.

·        Afin de capturer une information de phase les auteurs utilisent aussi le terme de corrélation  où et sont des coefficients de la représentation en « pyramide mobile » aux mêmes positions et orientations mais à deux échelles consécutives (pour l'échelle grossière (coarse) et pour l'échelle fine (fine)). Le terme de l'échelle grossière est porté au carré pour avoir des variations comparables de la phase aux deux échelles (puisque l'ondelette utilisée à l'échelle grossière correspond à celle de l'échelle fine dilatée d'un rapport deux). On retrouve le décompte de nouveaux paramètres précédent mais cette fois-ci les termes sont complexes donc il faut multiplier par 2 pour les parties réelles et complexes : .

 

 

Algorithme d'analyse-synthèse de textures

 

 

Problème

 

            On appelle l'ensemble des images de taille N×M, on dispose de statistiques  sur les éléments de.

 

On dispose de une texture particulière et des valeurs de statistiques correspondant : .

 

On cherche :

 

1.      à évaluer les

2.      à générer de nouvelles images qui aient les mêmes valeurs de statistiques . Si les statistiques ont été bien choisies (ó sont suffisantes pour caractériser les textures que l'on cherche à caractériser), les images obtenues sont visuellement proches de celles de départ.

 

Méthode

 

            Le point 1 du problème que l'on s'est donné ne pose pas de problème, on évalue les  en utilisant des moyennes empiriques des statistiques, comme indiqué en première partie sous certaines hypothèses (ergodicité, taille de l'image sur laquelle se fait l'évaluation) cela se justifie.

 

            Le point 2 est plus délicat. Pour aboutir on part d'une image générée aléatoirement  (généralement un bruit blanc gaussien) et à chaque itération et pour chaque statistique on calcule son gradient en le point correspondant à l'image courante et on se déplace selon la direction du gradient pour avoir une valeur  le plus proche possible de   ó on cherche. La nouvelle image pour la statistique ou itération suivante devient alors.

 

            Il reste à calculer le gradient de la statistique  en le point et surtout à choisir la valeur  du déplacement, le long du vecteur de gradient. On explicitera cela pour différents  dans le paragraphe suivant.

 

Note1 : il est intéressant de noter que la convergence de la méthode décrite ci-dessus n'est pas assurée théoriquement mais semble bien vérifiée en pratique.

 

 

En pratique

 

 

 

 

Le gradient a pour composantes :

Le déplacement le long du gradient est quand à lui solution de l'équation du sixième degré suivante (où s'il n'y a pas de solution on prend le déplacement qui donnera la valeur du polynôme la plus proche de 0) :

où

où

et enfin où les  sont les moments d'ordre n et ,  respectivement la skewness de l'image courante et la skewness souhaitée.

 

 

 

Le gradient de la composante  de la restriction de la matrice d'autocorrélation (on a) a pour composantes :

                  La nouvelle image aura donc la forme :

Où N est le voisinage sur lequel est restreint la matrice d'autocorrélation, cela peut aussi s'écrire :

                  Où est la convolution circulaire.

Le noyau de convolution est approché en résolvant l'autre équation de convolution :  où et sont respectivement les matrices d'autocorrélation de l'image courante et celle souhaitée. On prend ensuite dans le domaine fréquentiel.

                       


Quelques exemples et importance des différentes statistiques

 

Pour essayer d'évaluer l'impact de chaque contrainte statistique sur la qualité du rendu des textures nous avons opérer l'analyse de textures récupérées sur le site spécifié précédemment, puis nous avons généré des textures respectant une partie des contraintes statistiques listées. Nous avons obtenu les résultats ci-dessous. Les contraintes statistiques d'ordre 1 sont bien évidemment insuffisantes, elles ne donnent qu'une information de luminosité aux différentes résolutions, seules des textures très simples (cf plastique) sont bien rendues. Une fois que l'on prend toutes les contraintes sur les corrélations aux différentes résolutions et entre sous-bandes et orientations on obtient un résultat déjà très bon. On voit en effet que les structures géométriques sont parfaitement rendues (cf échiquier ou Dents de scie), cependant les auteurs ont essayé d'obtenir un meilleur rendu du relief sur certaines textures (cf raisins ou noix). Pour cela ils ont introduit le terme de corrélation qui capture la phase, et en effet le résultat est notable pour certaines textures (cf raisins) mais reste insuffisant pour d'autres (cf noix ou mâche) qui sont à la limite de la notion de texture (l'œil est capable d'y repérer des objets particuliers). A noter aussi la difficulté que représente le rendu de polygones irréguliers (cf plastique 2).