Projet image 2016 : Synthèse de textures dynamiques

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Synthèse de textures dynamiques
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Marianne Clausel

Étudiants

Contexte

Exemples de textures dynamiques
Extrait du film "Le Livre de la jungle" 2016

Dans ce projet de spécialité, nous manipulons des textures dynamiques. Une texture dynamique est un phénomène présentant une régularité spatiale et temporelle.

Cette définition regroupe de nombreux phénomènes, naturels ou non tels que : un champ d’herbe ondulant, les vagues de la mer, un drapeau dans le vent, le mouvement d’arbres dans une forêt, de la fumée, du feu, une cascade ...


Les textures dynamiques représentent un thème de recherche actuel. Le nombre de publications portant sur la caractérisation de textures dynamiques est en forte augmentation ces dernières années.

Pour réaliser notre projet, nous partons d'un article de recherche portant que la Synthèse (génération) de textures dynamiques. Cet article de recherche propose une méthode de modélisation et de génération de textures dynamiques. L'algorithme se fait en deux temps : apprentissage statistique du phénomène et prédiction. Il utilise des notions complexes en mathématiques telles que l'utilisation de multi-noyaux gaussiens. On peut trouver le code écrit en Matlab sur le Github suivant.


Il faut comprendre que l'algorithme ne génère pas à partir de rien des textures dynamiques mais part d'une vidéo de texture dynamique et génère la suite vraisemblable de la vidéo. Ceci a beaucoup d'application dans le monde du numérique, par exemple dans le film "Le livre de la Jungle", on assiste à plusieurs scènes avec en fond un phénomène naturel, ici la cascade. Il est très utile de pouvoir générer par ordinateur la cascade en arrière plan.

Objectif

Le but du projet est d’étendre la méthode proposée en se basant sur l’utilisation d’ondelettes spatio–temporelles. Ce projet s'inscrit complétement dans le cadre la recherche : le sujet est nouveau, personne n'a déjà réalisé le travail que nous effectuons. Nous ne savons si nos travaux de recherche donneront un résultat exploitable au niveau de la vidéo. Pour terminer, le cadre de recherche n'est pas défini, c'est à nous d'explorer les pistes qui nous semblent judicieuses et intéressantes.

Ondelette spatio-temporelle

Tout signal vidéo pour se décomposer dans une base de la façon suivante :  f[n] = \sum_{k=0}^{N-1} c_{j,k} \psi_{j,k}[n] .

Ce qui nous intéresse ici, sont les coefficients d'ondelettes, autrement dit les  c_k. Décomposer le signal revient à coder l'information (le signal vidéo) d'une autre manière que dans un tableau stockant les valeurs des pixels. Cette autre représentation permet d'appliquer différentes opérations utiles en traitement d'image.


Pourquoi utiliser les coefficients d'ondelette ? L'avantage à utiliser les coefficients d'ondelette est double :

-Tout d'abord, cela permet une compression de l'information : en effet les coefficients d'ondelettes étant définis récursivement pour coder des détails de plus en plus fins d'une image, on peut en supprimer un certain nombre tout en gardant une quantité d'information importante.

Capture-7.png

-Ensuite, l'utilisation d'ondelette permet de coder l'information de manière plus intelligente que de stocker tous les pixels dans une matrice. Grâce aux coefficients, nous pouvons séparer plus facilement les éléments de bruit, de contours,...

Capture-8.png

Objectifs du projet

Comme dit précédemment, l'objectif principal est de générer une texture dynamique à partir de l'algorithme d'apprentissage donné en utilisant les ondelettes spatio-temporelles. L'avantage sera d'étendre l'algorithme et d'utiliser les avantages des ondelettes comme la compression ou le débruitage.

Cependant, le sujet étant très libre, nous pouvons aussi regarder la notion d'ondelettes hyperboliques. Nous pouvons aussi essayer de générer des textures dynamiques en utilisant le RGB ou d'autres espaces couleurs commme la luminance chrominance.


Diagramme du process initial et final

Un but secondaire mais néanmoins très intéressant est de comprendre les ondelettes spatio-temporelles. En effet, là est la coeur de la compréhension de notre projet et Matlab donne des fonctions utilisables en l'état qui décomposent un signal (1D ou 2D) en coefficients d'ondelettes. Cependant, cela nous est donné directement et nous utilisons ces fonctions en boîte noire. Ainsi,dans un second temps, nous voulons recoder à partir de zéro les fonctions permettant de décomposer le signal en coefficients. Le langage choisi pour recoder ces fonctions est le C++. Au départ, nous comptions si nous en avions le temps retranscrire aussi l'algorithme d'apprentissage en C++ mais cela n'était pas possible compte tenu des délais.

Implémentation et résultats

Avant d'implémenter, nous avons eu une longue phase de recherche bibliographique afin de comprendre la notion d'ondelette et de manipuler l'algorithme donné.

Un conseil que nous pouvons donner est d'être sûr d'avoir compris la nouvelle notion, d'avoir tout mis au clair sur papier avant de commencer à implémenter une partie.

Algorithme d'apprentissage

Résultats et problèmes rencontrés

Dans un premier temps nous avons du adapter l'algorithme pour pouvoir l'utiliser sur les ordinateurs de l'ENSIMAG. Aussi, nous avons d'abord appris à manipuler les coefficients d'ondelettes d'abord sur des signaux 1D(son), puis 2D (image), puis 3D (vidéo).

Nous avons ensuite adapté l'entrée de l'algorithme en passant non plus des pixels mais des coefficients d'ondelettes.

Suite à cela, nous obtenons un résultat visuellement moins bon que lorsque l'on passe les pixels mais le résultat ressemble tout de même à un texture dynamique ! Ceci représente une certaine satisfaction quand à l'objectif initial car il n'est pas du tout évident que l'algorithme d'apprentissage statistique sur des pixels donne une prédiction vraisemblable avec des coefficients d'ondelettes.

Ici le problème rencontré est l'addition de bruit sur le signal vidéo de sortie. Aussi, l'algorithme lancé sur une vidéo de 250 frames et sur une résolution de pixels de 90x120 peut prendre une trentaine de minute.

Pour finir, avec l'algorithme initial, les images des vidéos sont converties en noir et blanc.

Vous pouvez trouver ci-joint les fichiers vidéos obtenus :


- Vidéo initiale de texture dynamique: Média:text_vague.avi

- Vidéo générée par l'algorithme d'apprentissage en passant par les pixels :Média:text_vague_generee.avi

- Vidéo générée par l'algorithme d'apprentissage en passant par les coefficients : Média:text_vague_coeff.avi

Pour les vidéos générées, le fichier joint est la juxtaposition du signal initial et du signal généré.

La vidéo initiale durant 10 secondes, la vidéo générée est identique sur les 10 premières secondes, de 10 à 16 secondes, on observe la texture générée par l'algorithme.

Pistes explorées

Types d'ondelettes et moments nuls
Quand nous avons eu ces problèmes d'artéfacs nous avons d'abord essayé d'utiliser différents types d'ondelettes : Coiflet, Daubechies, Haar. Nous avons aussi fait varier le nombre de moments nuls pour ces ondelettes, mais nous n'avons pas obtenu de meilleur résultat en changeant ces différents paramètres.


Réduction du signal
Nous avons aussi essayé de réduire le nombre de frames en entrée car nous nous étions dit que sur un signal plus court, le bruit généré serait plus faible. Cependant, en dessous de 250 frames, l'algorithme ne détecte pas de texture dynamique.


Autres bases de décomposition
Nous avons aussi décomposer le signal dans d'autres bases comme la Discrete Cosinus Transform (DCT) ou avec la transformée de Fourier (FFT). La DCT donne un résultat avec des artéfacs mais reste assez bon en comparaison en celui obtenu avec les coefficients d'ondelettes. La FFT ne donne pas de résultat exploitable.


Post Processing avec les ondelettes
Le signal en sortie présente des artéfacs à motif géométrique particulier. Nous avons interprété ces artéfacs comme du bruit amplifié. En effet, si on regarde la vidéo initiale en noir et blanc, on observe des lignes horizontales et verticales dûes à la mauvaise résolution de la vidéo. Nous nous sommes donc dit que l'algorithme amplifiait ce bruit dans le signal et qu'il était difficile de l'en empêcher. Nous avons donc essayé de traiter le résultat obtenu en débruitant les images par les ondelettes spatio-temporelles.

En gardant 5% des plus grands coefficients d'ondelettes, on obtient le résultat suivant : Média:V1_5p.avi


Ondelettes hyperboliques

La volonté de travailler avec des ondelettes hyperboliques vient du constat suivant : on applique ici des transformées en ondelettes en 2 dimensions mais c'est bien une vidéo qu'on traite et non pas simplement une suite d'images, il y a donc la présence d'une régularité dans dimension temporelle qui n'est pas traitée de prime abord.

Théoriquement, il s'agit ainsi d'un produit tensoriel entre ondelette 2D pour l'image et ondelette 1D pour le temps.

Concrètement, la mise en place est la suivante : après avoir avoir appliqué la transformée 2D pour chaque frame, on va appliquer une transformée 1D mais sur des paquets de frames. (et bien sûr la transformée inverse après l'algorithme).


Travail local - Groupement par échelle

Comme vu précédemment, les coefficients d'ondelettes ont 2 indices, dont un correspondant à l'échelle. Si les pixels d'une image peuvent tous être mis sur "un pied d'égalité", ce n'est pas le cas des coefficients d'ondelettes, qui ont des particularités en fonction justement de leur échelle.

Capture-11.png


Découpage d'une image par echelle


L'approche ici est donc la suivante : travailler localement en donnant à l'algorithme les coefficients échelle par échelle.


Périodisation de l'image

Passage en entrée des pixels en RGB
Dans l'algorithme initial, le signal est converti en niveaux de gris pour n'avoir qu'une image 2D par frames. À la base, le signal est stocké en RGB, c'est à dire qu'une image est stockée dans 3 matrices.
Ainsi, nous avons fait une boucle pour i allant de 1 à 3 (les 3 composantes RGB) sur l'algorithme avec en entreé les pixels dans la base RGB.
L'algorithme qui génère des kernels mutli-gaussiens n'a pas réussi à terminer la process à cause de problèmes numériques (matrice non définie positive).


Passage en entrée des pixels dans l'espace couleur YCBCR
En décomposant le signal dans l'espace couleur de la [chrominance], nous avons obtenu le même problème que précédemment.

Implémentation des ondelettes

Comme énoncé plus tôt, l'un des buts secondaires, mais nous tenant à cœur, du projet, était de bien comprendre le fonctionnement interne de la décomposition en ondelettes. L'utilisation de fonctions Matlab et l'étude de différents documents scientifiques concernant les ondelettes nous ayant laissés sur notre faim, nous avons décidé de re-coder tout le processus de décomposition d'un signal, d'une image puis d'une séquence d'images en coefficients d'ondelettes dans un vrai langage : le C++. Tous les fichiers source ainsi qu'un makefile seront fournis à la fin.

La décomposition en coefficients d'ondelettes continue

Avant de vous décrire les procédés, nous allons rapidement vous parler de la décomposition en coefficients d'ondelettes, ici en 1D dans l'espace des réels :

  • La transformée en coefficients d'ondelettes est très similaire à une transformée de Fourier, mais la base dans laquelle on se situe est composée d'ondelettes.
  • Une ondelette est une fonction \psi correspondant à une petite oscillation, de moyenne nulle. Elle est localisée en temps et en fréquence. Nous utiliserons ici l'ondelette de Daubechies 2.
  • On peut former une base d'ondelettes en faisant varier les paramètres de temps et de fréquence. Celle-ci se définit de manière suivante :

\psi_{i,n}(x) = 2^{-\frac{i}{2}} \psi(2^{i}t-n) (Nous utilisons dès maintenant la translation en puissances de 2 car elle nous sera utile par la suite)

  • Une fonction f peut se décomposer dans cette base de la manière suivante :

\forall x, f(x) = \sum_{i=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} <f,\psi_{i,n}> \psi_{i,n}(t), avec <f,\psi_{i,n}> le produit scalaire de f et de \psi_{i,n}, défini par <f, \psi_{i,n}> = \int_{-\infty}^{\infty} f (t) \psi_{i,n}(t)\,dt.
On notera d_{n}^{i} ce produit scalaire, qui correspondra alors au coefficient d'ondelette de la fonction pour \psi_{i,n}


Le but ici est donc d'obtenir ces différents d_{n}^{i}

Méthode naïve

Nous avons tout d'abord essayé de foncer tête baissée en essayant de coder en C++ la plupart des opérations sur les fonctions permettant d'obtenir ces coefficients (produits intégrales, multiplication...) : nous avons pour cela créé une classe de fonction échantillonnées sur lesquelles nous pouvons aisément appliquer ces opérations. Cependant, bien que ceci soit bien pratique pour représenter des fonctions 1D, cela commence à poser problème lorsque l'on essaie d'atteindre notre objectif premier : décomposer une fonction en ondelettes.
Premièrement, définir explicitement une ondelette comme celle de Haar n'est pas difficile, mais pour une ondelette telle que celle de Daubechies 4, l'établissement de la fonction explicite est loin d'être aisé.
Ensuite, le calcul intégral prend beaucoup trop de temps pour que celui-ci soit viable lorsque le nombre d'échantillons sur les fonctions devient trop grand, et les erreurs de calculs dues à la représentation des nombres flottants par le système s'accumulent bien trop rapidement.
Enfin, il est difficile de savoir quels coefficients sélectionner. Après avoir transformé notre signal d'entrée en signal continu, on se retrouve avec une infinité de coefficients, ce qui n'est pas ce qu'il y a de plus pratique à traiter. On peut supposer que l'on se débarrasse des coefficients plus petits qu'un certain seuil arbitraire, mais une fois encore, comment le définir ? Est-on sûrs qu'il n'y a pas une infinité de coefficients supérieurs à ce seuil ?

La solution : transformée en ondelettes discrètes, algorithme pyramidal

Nous allons donc utiliser une méthode bien plus adaptée à la représentation discrète de nos données.
Le principe reste le même, mais nous nous plaçons cette fois sur les espaces ayant un nombre fini de valeurs, et nous savons donc qu'il n'y a qu'un nombre fini de coefficients (égal au nombre de valeurs des données initiales). De plus, il existe pour cela des algorithmes permettant de faire ces calculs avec une complexité très faible O(\log (N)).
Nous allons donc implémenter l'algorithme pyramidal de Mallat pour ce faire.

Sans entrer dans les détails, nous utilisons pour cela une paire de filtres, g et h, qui sont des filtres passe-haut et passe-bas.
L'avantage de ces filtres est qu'ils sont représentés par un nombre fini et raisonnable de valeurs N. (Par exemple  N = 4 pour la fonction Daubechies 4.) Ces filtres sont calculés par produits scalaires entre les différentes échelles des fonctions d'ondelettes, mais tout ceci a déjà été fait et ils nous sont donnés sur des banques telles que celle-ci.

On va ensuite implémenter l'algorithme pyramidal de Mallat, qui est un algorithme multi-résolution, et que l'on peut représenter de la manière suivante :

Wavelets - Filter Bank.png

Pour expliquer rapidement ce schéma : nous partons initialement du signal x[n], qui correspond à l'ensemble discret de nos données.
Ensuite nous appliquons nos 2 filtres à ce signal, par convolution, et nous obtenons ensuite les signaux filtrés en passe-haut et en passe-bas, dont nous n'allons ensuite prendre qu'un coefficient sur deux. Comme une formule vaut mieux qu'une explication douteuse, voici comment nous procédons en théorie :  \forall k,  y_{high}[k] = \sum_{n} x[n] g[2k-n] et  \forall k,  y_{low}[k] = \sum_{n} x[n] h[2k-n]
Les y_{low}[k] correspondent aux d_{0}^{k}. On va donc garder toutes ces valeurs, puis ensuite ré-appliquer récursivement ces filtres sur le nouveau signal y_{high}[k], de cardinal \frac{N}{2} pour obtenir les d_{1}^{k} et ainsi de suite jusqu'à épuisement du nombre de valeurs en entrée.
Ainsi, les coefficients d'ondelettes du niveau i sont au nombre de \frac{N}{2^{i}}.

Nous pouvons enfin reconstruire le signal d'entrée par la formule suivante : \forall n, x[n] = \sum_{k=-\infty}^{\infty} ( (y_{high}[k] g[2k-n])+(y_{low}[k] h[2h-n]) )

C'est donc cet algorithme que nous allons implémenter en C++.

Implémentation en C++

Nous allons tout d'abord implémenter cet algorithme en 1 dimension. L'implémentation de l'algorithme en lui-même ne pose pas de réel problème car celui-ci est assez bien documenté. Cependant, certaines contraintes s'appliquent : à partir de quel moment commence-t-on la convolution ? Comment gérer les extrémités du tableau ?
Après beaucoup de recherches, de tests, et de filtrage d'informations contradictoires, nous en avons conclu que le plus simple est de périodiser le signal initial, et d'appliquer les filtres sur chacun des éléments.
Par soucis de performance, cet algorithme a été implémenté en itératif, et les coefficients calculés sont générés par dessus le tableau correspondant au signal d'entrée.

Une fois cet algorithme implémenté, nous avons pu commencer à jouer avec les coefficients d'ondelettes sur des fonctions à une dimension. Par exemple ici, nous avons compressé une fonction sinus échantillonnée sur 1024 valeurs en seulement une trentaine de coefficients d'ondelettes, à laquelle nous avons ensuite appliqué la transformée inverse :
Très sinus.png

Nous avons ensuite pu adapter cet algorithme à des tableaux en 2 dimensions, en s'occupant d'abord de faire la transformée sur chaque ligne, puis sur chaque colonne de coefficients. C'est une méthode efficace et très proche de la transformée en ondelettes en 2 dimensions, et c'est celle employée lors de la compression JPEG par exemple.

Une fois que la transformée en ondelettes en 2 dimensions était fonctionnelle, nous avons voulu implémenter la transformée en ondelettes hyperboliques.
Rapidement, les ondelettes hyperboliques permettent de prendre en compte les similarités temporelles d'une séquence d'images, en appliquant une transformée en ondelettes coefficient par coefficient sur toute la succession d'image, en faisant varier le temps.
On peut donc s'en servir par exemple pour faire de la compression temporelle, qui permet de gagner en volume sur des séquences d'images assez similaires.

Par exemple, sur une séquence d'images très inspirées, où l'on compresse à la fois l'espace et le temps :

Hyperboliques.png


On a ainsi pu obtenir un taux de compression de près de 95% sur cette séquence.


Vous pourrez retrouver l'ensemble du code source ainsi qu'un makefile dans la section Livrables ci-dessous.

Livrables

C++

Vous pouvez retrouver les fichiers source, ainsi qu'un makefile et une séquence d'exemple dans l'archive suivante : Fichier:Ondelettes c++.tar.gz

Matlab

Nous avons réalisé un fichier de démonstration qui vous permet de tester les options suivantes :

  • Choix de la vidéo de base
  • Application des ondelettes classiques
  • Application des ondelettes hyperboliques
  • Découpage en blocs
  • Post-processing d'échelle
  • Post-processing de débruitage

ainsi qu'un fichier de démonstration pour la couleur et un pour jouer avec des images.

Conclusion

Résumé

Dans ce projet de recherche, nous avons étendu un algorithme de synthèse de textures dynamiques en utilisant les coefficients d'ondelettes spatio-temporelles. Après avoir obtenu présentant de artéfacs, nous avons concentré nos efforts sur l'amélioration du rendu visuel. En parallèle nous avons établi en C++ un programme permettant de décomposer une image en ondelettes spatio-temporelles et hyperboliques.

Perspectives

Même après post processing,nous n'obtenons tout de même pas un aussi bon rendu visuel qu'avec les pixels en entrée. Une amélioration possible serait de continuer à chercher d'où viennent ces artéfacs au motif géométrique.
Pour la partie implémentée en C++, il pourrait être très intéressant de traduire l'algorithme de synthèse de texture (donnée en Matlab) en C++. Ainsi, le code serait accessible à tout le monde, Matlab étant payant.

Bilan personnel

Nous avons beaucoup appris en autonomie. Ce sujet étant très libre et l'objectif n'étant pas certain d'être atteignable, nous avons dû prendre du recul pour manipuler des nouveaux outils mathématiques. Nous avons du faire preuve de rigueur afin de tester de manière empirique toutes les pistes présentées. Aussi, nous avons apprécié la liberté qui nous était accordée. Ceci nous a permis de privilégier des pistes en fonction de nos intérêts.


Aussi, nous avons acquis de solides compétences en traitement d'image que ce soit dans de nouvelles notions mathématiques comme les ondelettes (spatio-temporelles ou hyperboliques) ou manipulation d'image (filtres couleur etc).

Références

Dynamic texture modeling and synthesis using multi-kernel Gaussian process dynamic model
Débruitage de séquences d’images dynamiques par ondelettes espace-temps hyperboliques
Luminance-Chrominance
Fichier:Introduction à l’analyse en ondelettes.pdf
Fichier:Rfia2012 submission 54.pdf
Fichier:Rapport benhamadi.pdf