Résumé

L'objectif de ce travail est d'implémenter les algorithmes de synthèse et de transfert de textures décrits dans l'article SIGGRAPH 2001 d'Efros et Freeman. La synthèse de textures est la création d'une grande image de texture à partir d'un plus petit échantillon. Le transfert de textures permet de modifier l'apparence d'un objet en lui donnant la même texture que celle d'un échantillon, tout en préservant sa forme de base (voir le visage dans la rôtie ci-dessus). Pour la synthèse de texture, l'idée principale est d'échantillonner des blocs de pixels et de les aligner dans la nouvelle image afin qu'ils se chevauchent, de façon à ce que les zones qui se chevauchent soient similaires. Quand les régions qui se chevauchent ne correspondent pas exactement, cela génère des discontinuités visibles. Pour résoudre ce problème, vous devrez calculer un chemin à travers la zone de chevauchement avec des pixels d'intensités semblables et l'utiliser pour déterminer un découpage optimal. Le transfert de textures est obtenu en favorisant l'échantillonnage de blocs ayant une apparence similaire à une image cible donnée, ainsi qu'en associant les régions se chevauchant à des blocs déjà échantillonnés. Dans ce travail, vous allez implémenter des techniques importantes comme le "template matching", la recherche de joint et l'utilisation de masques. Ces techniques sont également utiles pour l'assemblage d'images ("image stitching"), le remplissage d'images ("image completion"), le reciblage d'image ("image retargeting") et le mélange d'images ("blending"). Le travail se divise en plusieurs étapes décrites ci-dessous.

Overview

The goal of this assignment is to implement the image quilting algorithm for texture synthesis and transfer, described in this SIGGRAPH 2001 paper by Efros and Freeman. Texture synthesis is the creation of a larger texture image from a small sample. Texture transfer is giving an object the appearance of having the same texture as a sample while preserving its basic shape (see the face on toast image above). For texture synthesis, the main idea is to sample patches and lay them down in overlapping patterns, such that the overlapping regions are similar. The overlapping regions may not match exactly, which will result in noticeable edges. To fix this, you will compute a path along pixels with similar intensities through the overlapping region and use it to select which overlapping patch from which to draw each pixel. Texture transfer is achieved by encouraging sampled patches to have similar appearance to a given target image, as well as matching overlapping regions of already sampled patches. In this homework, you will apply important techniques such as template matching, finding seams, and masking. These techniques are also useful for image stitching, image completion, image retargeting, and blending. You will implement the homework in several steps, described below.

1. Texture échantillonnée aléatoirement, sans chevauchement (10%)

Créez une fonction quilt_random(sample, outsize, patchsize) qui échantillonne aléatoirement des blocs carrés sample de taille patchsize afin de créer une image de sortie de taille outsize. Commencez par le coin supérieur gauche et remplissez l'image un bloc à la fois, sans chevauchement. C'est la méthode la plus simple, mais la moins efficace. Utilisez vos résultats sur les images fournies afin de comparer cette approche avec les deux suivantes.

1. Randomly sampled texture, no overlap (10%)

Create a function quilt_random(sample, outsize, patchsize) that randomly samples square patches of size patchsize from sample in order to create an output image of size outsize. Start from the upper-left corner, and tile samples without overlapping them until the image is full. This is the simplest but least effective method. Use your results on the sample images to compare this approach to the next two methods.

2. Chevauchement de blocs (25%)

Implémenter un algorithme qui sélectionne un nouveau bloc en fonction de sa ressemblance avec le bloc précédent. Pour ce faire, les blocs ajoutés chevaucheront deux déjà présents dans l'image de sortie.

Créez une fonction quilt_simple(sample, outsize, patchsize, overlap, tol) dans laquelle sample, outsize et patchsize représentent encore respectivement l'image dans laquelle l'échantillonnage s'effectuera, la taille de l'image de sortie, ainsi que la taille des blocs à échantillonner. overlap est le paramètre indiquant le nombre de pixels de chevauchement entre deux blocs, et tol indique le niveau de tolérance sur la ressemblance des blocs à ajouter.

Dans la fonction quilt_simple, vous devez, en premier lieu, échantillonner d'abord un bloc aléatoirement et le mettre dans le coin en haut à gauche de votre image de sortie vide. Ensuite, pour le prochain emplacement, déterminer quels pixels seront écrasés par le nouveau bloc; pour le reste de l'énoncé, ces pixels seront dans la zone de chevauchement. Sélectionnez les pixels dans cette zone de chevauchement et calculez la somme des différences aux carrées (SDC) entre ces pixels et toutes les positions possibles dans sample. Rappel: une valeur faible de SDC représente une grande similarité. Ensuite, sélectionnez aléatoirement parmi les positions ayant un score relativement bas le nouveau bloc à ajouter à l'image de texture. Attention, lorsque vous aurez rempli une première ligne, vos blocs chevaucheront des blocs existants à l'horizontale et à la verticale.

Pour savoir ce qu'est "un score relativement bas", nous vous suggérons de trouver le score minimum (minc) et ensuite d'échantillonner un bloc parmi tous ceux dont le score suit l'équation suivante: [y, x] = find(cost < minc*(1+tol)). Faites attention, pour les premiers blocs, minc=0, ce qui peut nuire à la variété de blocs à sélectionner. Pour contrer cela, il serait peut-être plus ingénieux de fixer minc à une valeur plus grande, e.g., minc=max(minc,small_cost_value). Autrement, vous pouvez toujours simplement sélectionner une des K blocs avec le score le plus bas.

Notez qu'il est très facile de faire des erreurs d'alignement que ce soit lors du calcul du coût pour chaque bloc, lors de l'échantillonnage du bloc au cout le plus bas et lors de la copie du bloc de la source à l'image de sortie. Nous vous suggérons donc d'attribuer une valeur impaire à patchsize pour que le centre du bloc soit bien défini. Afin de tester votre algorithme, essayez de générer une petite image de texture avec une faible tolérance (ex.: 0.00001), avec le premier bloc échantillonné sur le coin supérieur gauche de l'image source. Cela devrait produire une copie partielle de l'image source. Une fois que l'implémentation fonctionne, sauvegarder vos résultats (avec de plus hautes valeurs de tolérance pour une texture plus stochastique) générez à partir des mêmes exemples que pour la méthode purement aléatoire.

Pour optimiser cette fonction, vous pouvez aussi utiliser des méthodes de filtrage. Plus précisément, vous pouvez calculer la corrélation entre votre zone de chevauchement et la texture à échantillonner. Dans ce cas, le score maximal sera le meilleur.

2. Overlapping Patches (25%)

For this step, you must implement an algorithm that will sample similar square patches to create the texture. In this case, the added patches will overlap those already present in the output image.

Create a quilt_simple function(sample, outsize, patchsize, overlap, tol) in which sample, outsize and patchsize respectively represent the image to sample, the size of the output image, and the size of the patches to be sampled. overlap determines the size of the overlap region (in pixels), and tol indicates what tolerance level of similarity is acceptable for a patch to be sampled.

In the function quilt_sample, you must first sample a random patch and put it in the top left corner of your empty output image. Then, for the next location, determine which pixels will be overlap with the new patch. Select the pixels in the overlap region and calculate the sum of squared differences (SSD) between these pixels and all possible positions in the sample. Reminder: a low SSD means a high similarity. Then, select a random patch in positions having a relatively low score to add it to the texture image. Be careful, when you are filling the output image past the first line, your patches will overlap horizontally as well as vertically.

To know what "a relatively low score" means, we suggest you find the minimum score (minc) and then sample a patch among those whose score follows the following equation:[y, x] = find(cost < minc*(1+tol)). Be careful: for the first patches, minc will be 0 which would adversely affect the variety of choices to select from. To counter this, it might be wiser to set minc to a larger (but still small) value, eg, minc = max(minc, small_cost_value). Otherwise, you can always just select one of the K patchs with the lowest score.

Note that it is very easy to make alignment mistakes when computing the cost of each patch, sampling a low-cost patch, and copying the patch from the source to the output. I suggest using an odd value of patchsize so that its center is well-defined. As a sanity check, try generating a small texture image with low tolerance (e.g., 0.00001), with the first patch sampled from the upper-left of the source image. This should produce a partial copy of the source image. Once you have this function working, save a result (with higher tolerance for more stochastic texture) generated from the same sample as used for the random method.

To optimize this function, you can also use filtering methods. Specifically, you can calculate the correlation between your overlapping area and the texture to sample. In this case, the maximum score will be the most similar.

3. Recherche de joint (25%)

Ensuite, implémentez la recherche de joint dans le but de supprimer les artefacts sur les bordures des blocs se chevauchant (section 2.1 de l'article). Créez une fonction cut(bndcost) qui trouve le chemin contigu au coût minimum à partir de la gauche jusqu'à la droite du bloc en considérant le coût indiqué par bndcost. Le coût d'un chemin à travers chaque pixel est la différence au carré (sommée sur RGB pour les images couleur) entre l'image de sortie et le nouveau bloc. Utilisez la programmation dynamique pour trouver le chemin au coût minimum. Ensuite, utilisez ce chemin pour définir le masque binaire qui spécifie quels pixels devraient être conservés pour chaque bloc. Notez que si un bloc est chevauché en haut et à gauche, vous devrez calculer deux joints; le masque peut être défini comme l'intersection des masques pour chaque joint ( masque1 & masque2 ).

Créez une fonction quilt_cut qui intègre la recherche de joint et utilisez celle-ci pour créer un résultat dans le but de comparer les deux méthodes précédentes.

3. Seam Finding (25%)

Next, implement the seam finding to remove edge artifacts from the overlapping patches (section 2.1 of the paper). Create a function cut(bndcost) that finds the min-cost contiguous path from the left to right side of the patch according to the cost indicated by bndcost. The cost of a path through each pixel is the square differences (summed over RGB for color images) of the output image and the newly sampled patch. Use dynamic programming to find the min-cost path. Use this path to define a binary mask that specifies which pixels to copy from the newly sampled patch. Note that if a patch has top and left overlaps, you will need to compute two seams, and the mask can be defined as the intersection of the masks for each seam (mask1&mask2).

Create a function quilt_cut that incorporates the seam finding and use it to create a result to compare to the previous two methods.

4. Transfert de texture (25%)

Votre dernière tâche est de créer une fonction texture_transfer, basée sur votre quilt_cut, afin de créer un échantillon de texture guidé par une image cible (section 3 de l'article). Vous n'avez pas besoin d'implémenter la méthode itérative décrite dans le document (vous pouvez le faire pour des points supplémentaires---voir la section suivante). La principale différence entre cette fonction et quilt_cut est qu'il y a un terme de coût supplémentaire basé sur la différence entre le bloc source échantillonné et le bloc de destination dans l'image cible.

4. Texture transfer (25%)

Your final task is to create a function texture_transfer, based on your quilt_cut function for creating a texture sample that is guided by a pair of sample/target correspondence images (section 3 of the paper). You do not need to implement the iterative method described in the paper (you can do so for extra points---see Bells and Whistles). The main difference between this function and quilt_cut is that there is an additional cost term based on the difference between the sampled source patch and the target patch at the location to be filled.

5. Vos photos (5%)

Transférez une (ou plusieurs) textures sur votre propre visage!

5. Your photos (5%)

Crédits supplémentaires

Essayez une de ces idées pour approfondir vos connaissances (et augmenter votre note):

• (jusqu'à 15 pts) Implémentez la méthode de transfert de texture itérative décrite dans l'article. Comparez-la avec la méthode non itérative avec un minimum de deux exemples.
• (jusqu'à 20 pts) Utilisez une combinaison de transfert de la texture et de mélange pour créer une image de visage-dans-une-toast comme celui dans le haut de la page. Vous n'avez pas à utiliser cette texture---vous pourriez mettre votre visage dans un mur de briques ou une autre surface texturée. Pour obtenir la totalité des points, vous devez utiliser un certain type de mélange tel que du "feathering" ou du mélange par pyramide laplacienne. Notez que la texture doit avoir une grande variété d'intensités.
• (jusqu'à 40 pts) Améliorez votre méthode pour faire du remplissage de trous (de formes arbitraires) pour faire du remplissage d'image. Dans ce cas, les blocs sont tirés d'autres parties de l'image cible. Pour avoir tous les 40 pts, vous devriez implémenter une "smart priority function" (e.g., similaire à Criminisi et al.).

Bells & whistles

Try one of these ideas to increase your understanding on this subject (and increase your score):

• (up to 15 pts) Implement the iterative texture transfer method described in the paper. Compare to the non-iterative method for at least two examples.
• (up to 20 pts) Use a combination of texture transfer and blending to create a face-in-toast image like the one on top. You don't have to use toast - you could put your face in a brick wall or some other textured surface. To get full points, you must use some type of blending, such as feathering or Laplacian pyramid blending. Note that the texture needs to have a variety of intensities.
• (up to 40 pts) Extend your method to fill holes of arbitrary shape for image completion. In this case, patches are drawn from other parts of the target image. For the full 40 pts, you should implement a smart priority function (e.g., similar to Criminisi et al.).

Conseils d'implémentation

• Utilisez im2double pour travailler avec des images avec une plage de valeurs entre [0 1]. Cela permettra de réduire le risque d'erreurs d'arrondi (ou toutes autres erreurs du même genre).
• Oubliez l'efficacité pour commencer. Assurez-vous que tout soit en ordre avant d'optimiser votre code.

Implementation tips

• Use im2double to work with image with a range of values between [0 1]. It will lessen the chance of rounding errors (or any similar kind of errors).
• Forget about efficiency at first. Be sure everything is in working order before optimizing your code.

Évaluation

Ce travail est évalué sur 100 points. La répartition des points va comme suit:

• (10 pts) Implémentez l'algorithme de création de texture échantillonnée aléatoirement. Montrez des exemples.
• (25 pts) Implémentez l'algorithme de création de texture qui utilise des blocs échantillonnés aléatoirement avec chevauchement. Faites varier les paramètres overlap et tol lors de vos expérimentations. Montrez des exemples et commentez sur vos résultats.
• (25 pts) Implémentez l'algorithme de création de texture qui utilise des blocs échantillonnés aléatoirement avec de la recherche de joint. Montrez des exemples et commentez sur vos résultats.
• Pour les trois algorithmes ci-dessus, vous devez nous montrer des résultats sur toutes les textures suivantes, ainsi que sur au moins trois textures additionnelles que vous aurez trouvées sur Internet. N'oubliez pas de citer vos sources.
• (25 pts) Implémentez l'algorithme de transfert de texture. Montrez des exemples et commentez sur vos résultats. Vous devez obligatoirement utiliser ces images, ainsi qu'au moins deux autres images que vous aurez trouvées sur Internet. N'oubliez pas de citer vos sources.
• (5 pts) Transférez une texture sur une photo de vous-même (ex: votre visage). Soyez créatifs!
• (N pts) Éblouissez-nous avec vos crédits supplémentaires. Rappel: vous devez livrer au moins 10 pts de crédits supplémentaires.

Evaluation

This assignment is evaluated on 100 points, as follows:

• (10 pts) Implement a randomly sampled texture quilting algorithm. Show examples.
• (25 pts) Implement a quilting algorithm which uses randomly sampled overlapping patches. Vary the overlap and tol parameters in your experimentations. Show examples and comment on your results.
• (25 pts) Implement a quilting algorithm which uses randomly sampled overlapping patches and seam finding. Show examples and comment on your results.
• For all three algorithms above, you must show us results obtained on all these textures. In addition, show us results on at least three additional textures that you will find online. Don't forget to cite your sources.
• (25 pts) Implement a texture transfer algorithm. Show examples and comment on your results. You must use these images, as well as at least two additional images that you fill find online. Don't forget to cite your sources.
• (5 pts) Transfer a texture on a photograph of yourself (ex: your face). Be creative!
• (N pts) Dazzle us with any bells and/or whistles you've added in. Reminder: you must add at least 10 pts worth of bells and whistles.

Livrables

Comme pour le TP précédent, vous devrez soumettre votre code et une page web simple illustrant vos résultats et contenant une courte discussion sur ceux-ci. Pour vous aider, nous vous fournissons une ébauche de page web (facultative). L'apparence esthétique du site Web ne sera pas évaluée, mais il est important que les informations soient clairement présentées.

Plus précisément, la page devrait contenir:

• Explication de chaque algorithme implémenté. Illustrez (au besoin) les étapes des algorithmes.
• Montrez vos résultats (bons ou mauvais) sur les images que nous vous avons fournies (synthèse, transfert), de même que sur des images que vous aurez trouvées en ligne (au minimum: 3 pour synthèse, 2 pour transfert). Expliquez vos résultats.
• Expliquez les crédits supplémentaires que vous avez implémentés. Illustrez ces explications. Aussi, si cela s'applique, montrez le "avant" et le "après".

Deliverables

For this project you must turn in both your code and a project webpage in which you will put your results and a short discussion on these. We provide a webpage template (optional). The aesthetic appearance of the website will not be evaluated, but it is important to clearly present the information.

More precisely, the webpage should contain:

• Explain each algorithm you have implemented. Illustrate the process if you think it is needed.
• Show your results (good and bad) on the images that we have provided (synthesis, transfer), as well as images you will find online (at least: 3 for synthesis, 2 for transfer). Explain these results.
• Explain all the bells and whistles you have implemented. Illustrate these explanations. Also, if applicable, show the "before" and "after".

Remise

Pour la remise de votre travail, créez un fichier tp2.zip qui contient:

• Votre rapport en format HTML dans un dossier tp2/web. Vos images doivent être dans un dossier tp2/web/images.
• Votre page principale doit être tp2/web/index.html. De plus, assurez-vous qu'il n'y a aucun caractère spécial (accent, ponctuation, espace, etc.) dans les noms de vos fichiers, images, etc.
• Votre code Matlab doit être dans un dossier tp2/code. N'incluez pas les images que vous avez utilisées pour produire vos résultats dans ce dossier dans le but de ne pas alourdir le fichier.

Finalement, veuillez téléverser votre fichier tp2.zip sur pixel (http://pixel.fsg.ulaval.ca) avant la date limite. La politique des retards mentionnée dans le plan de cours sera appliquée. Pour toutes questions concernant la procédure de remise ou le travail lui-même, posez vos questions sur Piazza!

Attention! La taille limite permise sur Pixel est de 50MB. Assurez-vous que la taille du fichier tp2.zip n'excède pas 50MB.

Handing in procedure

For this homework, you must create a tp2.zip file. In this file you'll put:

• Your report in an HTML format inside a folder named tp2/web. Your images for this web page should be inside a folder named tp2/web/images.
• Your main page has to be tp2/web/index.html. Make sure none of the files have special characters (e.g. accents, punctuation, spaces, etc.) in their filenames.
• Your Matlab code should be put inside the folder tp2/code. Do not include the images you have used to generate your results inside this folder, as this will likely generate huge files.

Finally, you should upload this file (tp2.zip) on pixel (http://pixel.fsg.ulaval.ca) before the deadline. The late submission policy described in the course plan will be applied. For any question regarding the submission process or the project as such, ask your questions on Piazza!

Beware! File size limit on Pixel is 50MB. Make sure that your tp2.zip file size does not exceed 50MB.

Liens rapides

• Ébauche de page web;
• Images sur lesquelles vous devez obligatoirement tester vos algorithmes de synthèse de textures.
• Images sur lesquelles vous devez obligatoirement tester votre algorithme de transfert de textures.

Quick links

• Webpage template;
• Images on which you are required to test your texture synthesis algorithms.
• Images on which you are required to test your texture transfer algorithm.

Remerciements

Merci à Derek Hoiem d'avoir créé le TP original qui a servi d'inspiration pour celui-ci, ainsi qu'à James Hays pour l'illustration ci-haut!

Thanks

Many thanks to Derek Hoiem for creating the assignment which inspired this one, and to James Hays for the picture above.