Différentes textures ont été utilisées afin de tester les approches susmentionnées. En plus des trois textures obligatoires, nous avons sélectionné huit autres textures variées. Ces textures sont présentées ici. Toutes les textures utilisées comme image source dans le cadre de ce travail font moins de 250x250 pixels (la plupart de ces textures ont été redimensionnées et rognées afin de diminuer leur taille avant de les fournir à l'algorithme). La source de chacune des textures est spécifiée en bas de chaque image.

Échantillonage aléatoire

L'échantillonage aléatoire est l'approche la plus simple. Pour chacune des blocs B, un rectangle de la dimension voulue est sélectionné aléatoirement dans l'image source S. Le processus est répété jusqu'à remplir totalement l'image de destination D.

Échantillonage avec recouvrement

L'échantillonage avec recouvrement agit aussi de manière stochastique, mais en ajoutant une contrainte : la minimisation de la différence visuelle entre le nouveau bloc et les blocs déjà en place. Cela est mis en place en ajoutant un recouvrement entre les blocs, qui "débordent" un peu sur leurs voisins, d'un nombre de pixels R. L'algorithme utilise cette bande de recouvrement pour chercher dans l'image source S un bloc minimisant la différence des pixels. La métrique retenue est une simple moyenne des différences au carré (MSD, Mean Squared Difference). Ainsi, l'algorithme va comme suit :

1. Pour le premier bloc B (en haut à gauche de l'image), aucune contrainte n'est présente, et le choix est totalement aléatoire.
2. Le bloc immédiatement à droite du premier bloc est aussi choisi aléatoirement, mais uniquement parmi les n blocs dont les R premières colonnes minimisent la distance avec les R dernières colonnes du premier bloc.
3. La première ligne est remplie en répétant l'étape précédente.
4. Les lignes subséquentes sont remplies en répétant la même étape, mais en tenant compte aussi du bloc au-dessus d'elles (c'est-à-dire qu'un recouvrement vertical de R est également appliqué)

Échantillonage avec recouvrement et recherche de joint optimal

L'échantillonage avec recherche de joint optimal utilise la même technique que l'échantillonage avec recouvrement, mais en y ajoutant une amélioration subtile. Si on observe l'algorithme précédent, on s'aperçoit que dans les zones de recouvrement, chaque pixel peut prendre deux valeurs (celle du bloc déjà présent, et celle du bloc que l'on colle par la suite). Dans ce cas, le nouveau bloc écrase systématiquement les valeurs du précédent, créant ainsi une frontière rectiligne.

Or, cette frontière n'est pas forcément le meilleur endroit pour "couper" entre les blocs, et contribue à créer une impression de lignes verticales et horizontales. Ce dernier problème est aggravé par le fait que ces frontières sont verticalement et horizontalement alignées entre elles, et traversent donc l'image au complet. Afin de réduire cet effet, l'idée de la recherche de joint est de choisir une frontière non plus rectiligne et systématique, mais passant par le chemin optimal pour une telle division. Ce chemin optimal est défini comme étant celui qui minimise la différence entre les deux blocs. En d'autres termes, la coupure est faite à l'endroit où elle se remarque le moins.

L'algorithme est donc similaire à celui précédemment introduit, avec l'ajout de cette recherche de frontière :

1. Pour le premier bloc B (en haut à gauche de l'image), aucune contrainte n'est présente, et le choix est totalement aléatoire.
2. Comme dans l'algorithme précédent, le bloc à droite du premier est sélectionné en minimisant la distance avec ce dernier dans la bande de recouvrement.
3. Dans la bande de recouvrement, le chemin de coupure optimal est calculé. Tous les pixels à gauche de cette frontière sont pris dans le premier bloc, alors que ceux à droite de la frontière proviennent du bloc nouvellement ajouté. La valeur des pixels de la frontière elle-même est définie comme la moyenne des pixels des deux blocs.
4. La première ligne est remplie en répétant l'étape précédente.
5. Les lignes subséquentes sont remplies en répétant la même étape, mais en tenant compte aussi du bloc au-dessus d'elles (c'est-à-dire qu'un recouvrement vertical de R est également appliqué). Dans ce cas, deux frontières sont calculées, l'une verticale et l'autre horizontale.

Note sur la parallélisation

La recherche de blocs similaires par calcul de la différence au carré des pixels est une opération très lourde dans ce cas-ci, puisqu'elle doit être appliquée itérativement sur toutes les positions possibles de la texture source, soit une complexité de O(n²). Le calcul de la MSD étant elle même en O(n²), et cette recherche devant être faite pour chaque case (hormis la première), on arrive vite à une complexité suffisamment importante pour que la synthèse de texture requiert plusieurs heures.

Afin de mitiger quelque peu ce problème, l'implémentation des deux derniers algorithmes est parallélisée pour la recherche de blocs similaires. La texture source est simplement divisée en un nombre arbitraire de tranches, qui peuvent être traitées indépendamment. Sur 4 coeurs, cette parallélisation amène un gain temporel d'environ 3.8x pour l'échantillonage avec recouvrement, et 3.2x pour l'échantillonage avec recherche de joint (ce résultat plus faible étant expliqué par la recherche de chemin qui n'est pas parallélisée).

Résultats et comparaison

Pour chaque texture, chaque méthode a été utilisée pour produire une image de taille D de 500x500 pixels. Les résultats sont présentés plus bas, redimensionnés en 370x370. La taille des blocs B a été ajustée entre 20 et 40 selon les textures : dans certains cas (comme la texture "Briques"), une taille de bloc trop petite posait problème puisque même avec recouvrement, les blocs étaient trop petits pour contenir un segment répétable de l'image. De même, dans certains cas (comme la texture "Yogourt"), une taille de bloc trop grande posait problème à cause de la très petite taille de la texture source.

Le recouvrement (overlap) a été choisi en fonction de contraintes de temps de calcul : si un trop petit recouvrement pose problème puisque le calcul de similarité n'est alors plus assez précis, un recouvrement trop important augmente de beaucoup le temps de traitement (parce qu'il implique un plus grand nombre de blocs pour remplir le même espace). Lors des expérimentations, nous avons constaté qu'un recouvrement R de 5 était suffisant pour la plupart des textures, hormis certaines textures possédant une structure régulière et espacée (par exemple un mur de brique). Dans ce cas particulier, un recouvrement de 10 a été utilisé.

Le facteur de tolérance a quant à lui été utilisé différement de l'énoncé. Au lieu de donner une tolérance sur le résultat du calcul de similarité entre les blocs, qui est difficile à quantifier à cause de sa grande variabilité, nous avons préféré utiliser ce facteur comme un nombre entier spécifiant le nombre de blocs à considérer lors du choix aléatoire parmi les blocs les plus similaires. Plus ce nombre est bas, plus grande est la similarité. Un facteur de tolérance trop bas a toutefois comme conséquence de réduire la diversité parmi les blocs et de répéter souvent le même motif. Au contraire, un facteur de tolérance trop élevé est associé à de grande dissimilarités entre les blocs, ce qui n'est pas souhaitables non plus. Dans nos expériences, nous avons utilisé un facteur variant entre 5 et 10, selon la texture.

---

---

---

---

---

---

---

---

---

---

---

L'approche utilisée pour la synthèse de textures peut également être utilisée pour plaquer une texture sur une image existante (par exemple un portrait). Dans ce cas, la métrique permettant la sélection des blocs n'utilise plus uniquement les blocs déjà ajoutés, mais aussi une image de fond avec laquelle elle essaie de minimiser la distance. Un facteur de pondération a permet d'ajuster l'importance donnée d'une part à la reconstruction de l'image de fond, et d'autre part à la qualité des joints entre les blocs.

Parmi les résultats, on remarque que l'approche fonctionne mal lorsque l'image cible est peu détaillée (par exemple le bonhomme de neige). Dans les autres cas, la texture est relativement bien appliquée (dans la limite des possibilités de la texture). D'autres mesures de distance que la différence au carré ont été testées, en particulier la différence au carré des images filtrées par un filtre de Sobel pour en extraire les bords, mais avec peu de succès. La précision et la qualité du résultat peuvent toutefois être améliorés en utilisant de plus petits blocs B (ce qui augmente par contre aussi considérablement la durée du traitement). On remarque par ailleurs que certaines textures ne comprenant pas de blocs sombres (comme la texture "Sapin") ont de la difficulté à s'adapter aux arrière-plans sombres.

Finalement, on voit bien l'influence de la taille des blocs B dans les résultats sur la photo de Feynman : de gros blocs permettent de mieux rendre la texture, alors que de petits blocs offrent un niveau de détail plus élevé dans le rendu des éléments de l'image cible.

---

---

---

Une version itérative du transfert de texture (tel que décrit dans l'article d'Efros et Freeman) a également été implémentée. Celle-ci commence avec une taille de bloc B importante, puis réduit celle-ci itérativement. À chaque itération, les blocs trouvés doivent s'approcher de l'image générée à l'itération précédente. Le paramètre a est aussi ajusté à chaque itération selon les indications d'Efros et Freeman.

Les résultats obtenus sont relativement mauvais, bien que, dans le cas de la première image, on puisse voir une amélioration dans le rendu de la texture. Il est possible que l'utilisation d'une texture plus grande (qui aurait par conséquent permis plus d'itérations, étant donné que la taille des blocs B doit être divisée par 3 à chaque itération) permettrait l'obtention de meilleurs résultats.

---