Patch Match by Ludovic CASTIGLIA

Ce qui est fourni dans le projet:

Est fournit dans ce projet le code d'une partie de mes anciennes tentatives infructueuses dans le dossier ./tentatives infrutueuses.

Vous pouvez également retrouver dans les dossiers portant les mêmes noms que les anciennes tentatives des photos illustrant le résultat avant/après pour que vous puissiez vous rendre compte de la progression sans avoir à les exécuter.

Vous avez également à la racine du projet, la version final de mon algorithme ainsi qu'un dossier ./asset et ./demo contenant des images et des démonstrations de l'algorithme.

Utilisation du projet:

Pour lancer la version final de l'algorithme en mode console, mettez-vous à la racine du projet. Puis lancez cette commande ./python selection.py. Ensuite, suivez les instructions écrites dans le terminal.

Pour lancer la version final de l'algorithme en mode gui, mettez-vous à la racine du projet. Puis lancez cette commande ./python interface.py. Puis suivez les instructions affiché via les box de dialogue.

En image, vous pouvez rentrer ./asset/vache.png et pour le masque, vous pouvez dessiner le vôtre ou utiliser ./asset/demo1_mask.png ou tout autre combo image et mask présent dans asset et demo ou dans votre disque dur (le programme accèpte les images .png .jpg .bmp ...).

Principe de l'algorithme:

Le principe de cet algorithme est assez simple à comprendre, mais son implémentation comporte quelques subtilités.
On commence cet algorithme avec une image et un mask (image booléene de même dimension que l'image). Dans un premier temp, on génère en boucle une version à chaque fois deux fois plus petite de l'image jusqu'a ce que la largeur ou la hauteur de l'image face 2 pixel. Ensuite, il suffirat de remplir le trou pour la première image (la plus réduite) puis de compléter les images suivantes à partir des précédentes jusqu'a obtenir l'image en résolution complête.
Mais la question est comment remplir ce trou et compléter l'image à partir des autres? Pour cela on vas venir trouver dans l'image actuel via une recherche par proximité géographique puis de manière random (plusieurs fois pour réduire les erreurs) un patch (un groupe de pixel) qui a une faible distance avec l'emplacement que l'on veut remplacer (distance dans le sens différence entre les valeurs des pixels). Une fois que l'on a trouver plusieurs patchs pour une zone, chaque patch vas voté pour la valeur des pixels en fonction d'un poid inversement proportionel à la distance (plus le patch est différent de la zone moins son vote a de l'importance).
On procède ainsi pour toutes les zones dans le troue jusqu'a obtenir l'image. Ensuite on recommence ce procèsse plusieurs fois pour chaque résolution de l'image (en prenant en modèle la version précédente de l'image pas la résolution précédente) afin de réduire la différence entre les patchs et ainsi augmenter la cohérence globale de l'image.
Le dernier point à développer est le calcule de la distance entre deux patchs. Pour cela, je viens calculer la différence élevé au carré des valeurs des pixels. Et lorsque le patch survol le mask ou est en dehors de l'image alors sa distance est la distance maximum (2552553) pour que le patch ne soit pas selectioné.

Exemple avant | après de l'algorithme:

Tentatives infructueuses:

knn:

Cet algorithme était plutôt simple, lorsque l'on a généré un trou, on vient le remplir en faisant un knn sur tous les pixels en périphérie de ce trou jusqu'à avoir recouvert entièrement le trou. Cet algorithme n'est adapté qu'au patch de forme rectangulaire et il ne marche bien que si le fond que l'on veut régénérer est plutôt lisse et sans texture.

PatchMatch2:

Dans cette tentative, j'ai implémenté très naïvement ce que je comprenais de l'algorithme patch match pour l'inpainting. Cependant, même si cet algorithme marche un peu mieux avec des fonds texturé, il crée tout de même une démarcation claire entre l'image de base et la masque.

smothPatch:

Pour palier au problème de démarcation claire entre patch, j'ai fusionné les deux algorithmes précédents. Je commence par recouvrir le masque de patch de l'extérieur vers l'intérieur jusqu'à ce que le masque soit entièrement recouvert. Puis entre toutes les bordures de patch, je viens appliquer l'algorithme knn sur la bordure pour faire une transition plus douce entre les patchs. À ce moment, je commençais à trouver ce résultat satisfaisant. Cependant, on voyait encore les démarcations entre le masque et le reste de l'image.

multiScale:

Pour cette implémentation, je suis repartie de PatchMatch2 que j'ai appliqué sur différentes tailles de résolution. Le résultat produit n'était pas très bon, car ma recherche de patch était défaillante. Cependant, malgré des résultats mitigés, on pouvait entrevoir du potentiel. J'ai donc décidé de partir de cette base pour réaliser la version final de mon algorithme qui en plus de la taille multiple, fait du multi masque (applique différents masques au même endroit pour faire réduire la variation).

Inspirations:

• https://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch.pdf
• https://www.youtube.com/watch?v=XTRO6yQOvJc
• https://helios2.mi.parisdescartes.fr/~jdelon/enseignement/tp_image/org/TP_inpainting.html
• https://wenfulee.github.io/CS-766-Computer-Vision/

Lien du dépot public code first:

https://codefirst.iut.uca.fr/git/ludovic.castiglia/patchMatch