Projet: Implémentation de PatchMatch

Pour projet, le sujet qui a été choisi est l'implémentation du célèbre algorithme PatchMatch pour trouver un Nearest Neighbour Field (NNF), c'est-à-dire un tableau de correspondance entre les patch d'une première image et leur plus proche voisin dans une seconde. À partir de cet algorithme, il est possible d'accélérer plusieurs autres algorithmes de modification d'image.

Partie 1: Trouver le NNF

Description

PatchMatch est un algorithme stochastique et itératif. C'est-à-dire que l'algorithme commence à partir d'une hypothèse aléatoire et raffine celle-ci à travers un processus itératif. PatchMatch contient trois étapes principales décrites ci-dessous :

Résultats

En mettant la photo de la tour Eiffel en provenance et la même photo en destination , nous pouvons tester la force de notre algorithme. Regardons tout d'abord la reconstruction qualitative de la tour Eiffel :

Photo d'entréeReconstruction

Nous voyons que le résultat est vrm bon pour un algo qui ne fait que chercher des correspondance aléatoirement. Il y a quelques artéfacts restant dû à la taille de la fenêtre et à l'algorithme, mais la carte NNF est assez précise pour plusieurs applications subséquentes. Nous pouvons maintenant afficher l'erreur de reconstruction que nous définissons ici comme étant la distance entre les pixels de l'image d'origine et des pixels correspondants dans l'image de reconstruite. Ainsi, nous pouvons avoir une erreur en lien avec notre algorithme. Nous voyons si notre algorithme a réussi à trouver la bonne patch.

Le résultat est impressionnant, nous pouvons voir que l'erreur est basse presque partout sauf sur la tour eiffel où il les groupement sont plus petits (plus de détails) et où la propagation et la random search pouvait moins bien foncitonner.


Maintenant, regardons si notre algorithme sera capable de reconstruire la tour Eiffel avec une autre photo.

Image de provenanceImage de destination

Non seulement l'image est plus petite, mais elle a une teinte différente. Malgré cela, nous obtenons l'image suivante :

Malgré les difficultés, la reconstruction est impressionnante et nous pouvons dire que notre algorithme remplit l'objectif. Or, nous voyons plus d'artéfact. Le dégradé du ciel dans l'image 1 inexistant dans le ciel uniforme de l'image 2 est crée à partir de de différentes teintes. Le blanc du ciel provient du Trocadéro et explique non seulement le blanc éclatant du résultat, mais également la fusion entre le bas du ciel et le Trocadéro.


Testons la même chose, mais avec une image du Parlement de Québec.

Photo d'entrée
Reconstruction

Encore une fois, le résultat est concluant. Même si nous avons des artéfacts et que le résultat final est de texture pastel, notre algorithme a trouvé les bons plus proches voisins de la scène initiale. Nous pouvons afficher l'erreur en distance pour nous convaincre quantitativement :

Nous voyons encore que l'erreur est très basse lorsqu'il y a de gros groupements et plus élevée lorsque la texture est plus complexe.


Nous pouvons faire comme avec la tour Eiffel et tenter de reconstruire le parlement avec une autre photo.

Photo d'entrée
Photo de destination

Nous arrivons au résultat suivant :

Nous voyons que la tâche est plus difficile, car il y a plus d'artéfact. Par contre, le résultat est vraiment intéressant. Nous pouvons voir que l'algorithme a quand même repéré la structure de l'image.


Conclusion

Nous voyons que PatchMatch est un algorithme extrêmement efficace pour trouver des plus proches voisins avec une paire d'images. Notre implémentation a montré la bonne performance de l'algorithme et les résultats sont convaincants.

Or, l'objectif initial du projet était de faire un programme pour enlever des objets dans une image à l'aide de PatchMatch. Même si PatchMatch est plus rapide que les autres algorithmes de son type, l'implémentation a dû être faite en C pour avoir une plus grande performance. Cet effort supplémentaire a grugé du temps précieux en cette semaine d'examen et la partie 2 n'a pas pu être complétée. Vous trouverez par contre du code supplémentaire pour les débuts de la partie 2 et les essais, en python et en C.