Filage d'image et tracé de droites pour un rendu artistique

Projet réalisé dans le cadre du cours VISI201_CMI_:_visite_de_laboratoire

Étudiants : Goralczyk Elliot, Lhéoté Anaïs

Tuteur : Jacques-Olivier Lachaud

Introduction

Un filage d'image est la reproduction d'une image à partir de clous sur une planche et d'un fil noir pour retracer l'image. Lors de ce projet, nous avons reproduit cette technique artistique à l'aide de Python pour voir jusqu'où nous pourrions pousser la ressemblance avec une image donnée, tout en gardant l'esprit du filage. Pour cela nous avons dû comprendre le principe en lui-même, et nous avons ensuite élaboré plusieurs techniques pour parvenir au meilleur résultat possible.

Placer les clous

Pour commencer un filage, il nous faut avant tout une planche et des clous.

Le placement des clous va définir l'ensemble des droites qu'il va nous être possible de tracer. Par exemple, les quatre clous gris sur l'image ci-dessous permettent de tracer uniquement les six droites en rouge.

Il est donc important de bien placer les clous pour obtenir un résultat satisfaisant. Nous avons utilisé trois techniques différentes pour placer les clous au cours de ce projet.

Représentation d'un clou

Avant de pouvoir placer un clou, il faut savoir comment le représenter. Nous avons fait le choix de le représenter par un triplet : (coordonnée x, coordonnée y, côté). Le côté est utilisé pour déterminer si il est possible de relier deux clous ; on considère qu'on ne peut pas relier deux clous situés d'un même côté. Un clou est donc associé à un pixel de l'image, et l'ensemble de ces clous est stocké dans une liste.

Faire le tour de l'image

Notre première approche a été de simplement placer des clous tous les 10 pixels autour de l'image. Cela permet d'avoir de nombreuses possibilités pour tracer les droites, et de pouvoir atteindre une grande majorité des pixels de l'image.

L'inconvénient de cette méthode est que les droites vont forcément d'un bord à l'autre de l'image, et ne peuvent pas s'arrêter au milieu, ce qui réduit les possibilités de représenter des détails.

Voici un exemple au ralenti de la génération de clous avec cette approche, sur une image carrée de 101 pixels de côté :

Placer des clous aléatoires

Pour pallier au problème de ne pas pouvoir arrêter une droite ailleurs que sur un bord, nous avons décidé de rajouter des clous dont la position a été générée aléatoirement. Pour ce faire, nous générons aléatoirement pour chaque clou sa coordonnée x (respectivement : y) un nombre entre 20 et la longueur (respectivement : hauteur) de l'image - 20, pour qu'il ne soit pas trop près du bord. Étant donné qu'un clou au centre de l'image doit pouvoir être relié à tous les autres, nous incrémentons à chaque clou la valeur de son côté, pour que chacun des clous générés aléatoirement ait un côté différent.

Cette méthode permet d'obtenir plus de détails, mais leur qualité repose sur des variables entièrement aléatoires, ce qui n'est pas idéal.

Voici un exemple au ralenti de la génération de clous avec cette approche, sur une image carrée de 101 pixels de côté, avec 20 clous aléatoires :

Utiliser les contours

Afin d'obtenir des images plus détaillées, nous souhaitons placer les clous autour des formes visibles dans nos images. Cela permettra de mieux en délimiter les contours, et donc de les faire ressortir et de les dessiner plus fidèlement. Pour y parvenir, nous utilisons un système de probabilités. Cela signifie que chaque pixel possède un poids, et que plus ce poids est grand, plus il est probable que ce pixel soit choisi.

Pour déterminer ce poids, nous utilisons de la détection de contours. En utilisant un filtre sur une image (dans notre cas le filtre FIND_EDGES de la bibliothèque Python Pillow), on peut obtenir une image sur laquelle les contours des formes de l'image de départ ressortent en blanc, et le reste en noir, comme sur l'exemple ci-dessous.

Nous pouvons ensuite déterminer les probabilités à partir de cette image. Pour ce faire, on commence par récupérer la valeur de chaque pixel de l'image dans une matrice de dimension (h, l), avec h la hauteur en pixels de l'image, et l sa longueur. La valeur d'un pixel dans une image en nuances de gris correspond à sa luminosité : 0 correspond au noir, 255 au blanc, et 127 à un gris moyen.

Voici un exemple d'une image en niveaux de gris et de la matrice correspondante :

À partir de cette matrice, on va créer une matrice de dimension identique, dans lequel chaque élément sera la somme de la valeur du pixel correspondant dans la matrice précédente et la valeur de l'élément précédent.

Voici ce que donnerait cette nouvelle matrice en reprenant l'exemple précédent :

Une fois que nous avons cette matrice, nous pouvons générer un nombre aléatoire situé entre 0 et la dernière valeur de la matrice que nous allons appeler r. Il ne nous reste plus qu'à parcourir la matrice jusqu'à tomber sur un nombre plus grand que r. Les coordonnées de ce nombre dans la matrice, et donc celles du pixel auquel il est associé seront associées à un nouveau clou. Par exemple, si on obtient r = 268, un clou sera placé en bas à gauche, car le nombre en bas à gauche de la deuxième matrice est le premier à être plus grand que 268.

Plus des pixels seront des contours marqués, plus ils seront clairs une fois le filtre appliqué. Ils auront donc plus de chances d'être tirés au sort, comme illustré ci-dessous.

Il ne nous reste plus qu'à placer autant de clous que l'on veut, et nous avons notre liste de clous. Nous ne plaçons pas manuellement de clous sur le bord de l'image avec cette méthode, et la notion de "côté" est peu utile ; on considère que tous les clous peuvent-être reliés entre eux, chaque clou possède donc un "côté" différent.

Voici un exemple de l'utilisation de cette technique, durant lequel on génère un nombre volontairement grand de clous à partir de ce coeur en origami :

On observe comme prévu de nombreux clous sur les bords du coeur ainsi que sur les motifs blancs à l'intérieur de celui-ci.

Trouver la droite à tracer

Maintenant que nos clous sont placés, il faut savoir lesquels relier entre eux. Nous aurons toujours un clou de départ, qui pour la première droite sera le premier clou de la liste, et pour les droites suivantes, le clou d'arrivée de la dernière droite tracée.

Mesurer la différence entre deux images

Pour décider à quel clou nous devons relier notre clou de départ, nous commençons par choisir aléatoirement une liste de clous à tester. On garde aléatoirement la moitié des clous, pour diviser par deux le nombre de calculs, tout en gardant un grand nombre de possibilités.

Pour chacun de ces clous, on calcule la liste des pixels que la droite allant du clou de départ à ce clou d'arrivée traverse. On compare ensuite pour chaque pixel de cette liste sa valeur dans notre image résultat provisoire et dans l'image de départ en niveau de gris. En faisant la somme de la valeur absolue de la différence entre les valeurs de chaque pixel de notre liste sur les deux images, et en la divisant par le nombre de pixels de la droite, on obtient la valeur de la différence moyenne par pixel entre les deux images.

Voici un exemple illustré, en calculant la différence sur les quatres pixels des images :

Une fois que nous avons calculé cette différence, il faut calculer la différence que l'on obtiendrait si la droite était tracée. On répète donc les opérations précédentes, en modifiant la valeur des pixels de notre image résultat provisoire. On soustrait à cette nouvelle différence le résultat obtenu précédemment, et cela nous donne la valeur de la réduction moyenne de la différence par pixel que l'on obtiendrait si on traçait la droite. Plus ce résultat est faible, plus la droite rapproche notre résultat de l'image de départ. Si ce résultat est positif, cela signifie que notre résultat s'éloigne de l'image originale.

On observe par exemple que si on assombrit le pixel en haut à gauche de l'image de droite (par rapport à l'image de droite du calcul au dessus), la différence entre les deux images va diminuer, et l'image de droite va donc se rapprocher de celle de gauche :

La différence entre l'image de gauche et celle de droite diminue donc d'une valeur de 77 - 32 = 45 par pixel en moyenne.

On calcule donc ce résultat pour toutes nos droites, et on trouve le clou qui réduit le plus l'erreur. On trace donc une droite jusqu'à ce clou, puis on cherche de nouveau le meilleur clou, et ainsi de suite. Mais alors, à quel moment faut-il s'arrêter ?

La condition d'arrêt

Dans notre implémentation de cet algorithme, nous avons fait le choix de nous arrêter lorsque la meilleure droite éloigne notre résultat de l'image de départ trois fois d'affilé. Nous n'arrêtons pas dès que le résultat s'éloigne car il arrive souvent qu'une droite qui éloigne notre résultat de l'image de départ permette ensuite de tracer une meilleure droite, qui va améliorer notre résultat.

Tracer la droite

Pour pouvoir trouver la meilleure droite, encore faut-il savoir par quels pixels cette droite passe.

Représenter une image

Et avant de savoir par quels pixels elle passe, il faut d'abord représenter ces pixels.

Durant ce projet, nous avons travaillé uniquement sur des images en niveaux de gris, nous représentons donc une image par une matrice de dimension identique à cette image, dans laquelle chaque élément de la matrice représente un pixel, comme vu dans la partie précédente. Pour importer une image, on la convertit donc en niveaux de gris, puis on récupère la valeur de chaque pixel pour en faire une matrice. Pour créer une image blanche, on crée une matrice de la taille souhaitée et on initialise toutes les valeurs à 255, la valeur du blanc.

Calculer la liste des pixels traversés

Pour connaître la liste des pixels traversés par une droite, on utilise son équation de type y = ax + b où y est une ordonnée (une coordonnée y), x une abscisse (une coordonnée x), a le coefficient directeur de la droite, et b son ordonnée à l'origine (la valeur de y quand x vaut 0).

Pour calculer les valeurs a et b, on utilise les coordonnées des deux points (des deux clous) que la droite traverse. On nomme x1 et y1 les coordonnées du clou de départ, et x2 et y2 le coordonnées du clou d'arrivée. Excepté le cas des droites verticales, on a a = (y2 - y1) / (x2 - x1) et b = y1 - x1 * a .

Deux cas apparaissent alors, celui dans lequel a appartient à [-1, 1], et celui dans lequel il n'est pas dedans. Dans le premier cas, la droite va être plus proche de l'axe des abscisses que de l'axe des ordonnées, et inversement dans le second cas.

Voici quelques exemples :

On peut observer que dans le premier cas (en bleu), il y a plusieurs pixels par ligne, et un seul par colonne, et inversement dans le deuxième cas (en rouge).

On traite donc ces deux cas différemment :

- Dans le premier cas, on détermine y pour chaque valeur de x entre x1 et x2 grâce au résultat de l'opération ax + b que l'on arrondit pour obtenir les coordonnées d'un pixel.

- Dans le second cas, on détermine x pour chaque valeur de y entre y1 et y2 grâce au résultat de l'opération (y - b) / a que l'on arrondit également.

Dans le cas des droites verticales, a n'est pas défini car il faudrait diviser par 0. On fabrique donc la liste de pixels en laissant la coordonnée x constante, et en ajoutant toutes les coordonnées y entre y1 et y2.

Une fois que nous avons notre liste de pixels, on modifie la valeur de chaque pixel dans la liste pour tracer la droite. Nous avons fait le choix de modifier de 51 la valeur des pixels, pour obtenir 6 niveaux de gris qui sont du plus foncé au plus clair : 255 -> 204 -> 153 -> 102 -> 51 -> 0.

Utiliser le format SVG

Pour obtenir un résultat moins pixelisé, nous utilisons le format SVG. Ce format est un format vectoriel, ce qui signifie qu'il ne stocke pas des pixels mais des formes et leurs coordonnées. Cela permet de pouvoir zoomer sur une image sans percevoir les pixels.

Nous utilisons ce format uniquement pour le résultat, les calculs utilisent toujours des matrices de pixels. Afin de rester cohérents avec les six niveaux de gris, les droites tracées ont une opacité de 20%.

Voici une comparaison de la même image de 10 pixels de côté en PNG à gauche, et en SVG à droite :

Évolution de l'algorithme

Maintenant que nous avons tous les éléments pour filer une image, nous pouvons comparer les différentes techniques.

Pour ces comparaisons, nous allons utiliser la photo suivante :

De plus, le temps de création des images est donné à titre indicatif, il peut varier selon les spécifications de la machine sur laquelle le programme tourne.

Placement des clous tout autour de l'image

La première technique de placement des clous ne permet pas de créer des images détaillées, mais est très rapide avec une petite résolution, car le nombre de clou créé est bas. On va se rendre compte au fil des versions que le nombre de clous et la taille de l'image sont les deux principaux facteurs de la variation du temps de calcul.

Cette image est un carré de 400 pixels de côté, en PNG. Elle comprend 1092 droites, et son temps de calcul a été de 17 secondes.

Placement des clous aléatoire

Cette seconde technique permet d'obtenir plus de détails mais reste imparfaite. De plus, avec une taille et un nombre de clous égaux, elle n'est pas plus rapide que la technique suivante, qui produit de meilleurs résultats.

Cette image est un carré de 400 pixels de côté, en PNG. Elle comprend 2403 droites, 300 clous, et son temps de calcul a été de 70 secondes.

Placement des clous avec la détection de contours

Cette dernière technique de placement des clous est celle qui permet d'obtenir le plus de détails. Sur des petites images, elle peut être beaucoup plus longue que la première technique, car elle va demander plus de clous. Cependant, cet écart se réduit lorsque la taille de l'image augmente, car son nombre de clou n'augmente pas obligatoirement, contrairement à la première technique.

Cette image est un carré de 400 pixels de côté, en PNG. Elle comprend 2900 droites, 300 clous, et son temps de calcul a été de 68 secondes.

Cette image est un carré de 3072 pixels de côté, en SVG. Elle comprend 23092 droites, 300 clous, et son temps de calcul a été de 8379 secondes (2 heures, 19 minutes, 39 secondes). En raison de l'impossibilité de téléverser des SVG sur le wiki, cette image et les autres SVG qui vont suivre seront des captures d'écran des fichiers SVG.

Fils blancs sur fond noir

Durant ce projet, nous avons également essayé de remplacer le fil noir par un fil blanc, et le fond blanc par un fond noir.

Les résultats obtenus paraissent moins ressemblants aux images de départ. Nous ignorons si cela vient du fait que nous n'avons pas testé avec des images adaptées, ou si cela vient de la perception de notre cerveau qui n'est pas habitué à voir des dessins en blanc sur noir.

Ces images utilisaient souvent plus de droites, et donc plus de temps que les images avec un fil noir.

Cette image est un carré de 400 pixels de côté, en PNG. Elle comprend 5957 droites, 300 clous, et son temps de calcul a été de 149 secondes.

Histogrammes d'erreurs

Pour chacune des quatre images ci-dessus, nous avons récupéré la liste de la valeur de la réduction de la différence pour chaque droite, puis nous avons tracé un histogramme pour visualiser à quel niveau de réduction il y avait le plus de droites. On remarque à chaque fois un pic à -51 (qui est pour rappel la valeur de laquelle on modifie un pixel à chaque fois), puis une baisse jusqu'à -40, et enfin une hausse proche de 0, particulièrement marquée sur l'image en blanc sur noir.

Voici les histogrammes, dans l'ordre des images précédentes :

Résultats finaux

Après de nombreux essais, voici les résultats que nous obtenons en utilisant la détection de contours pour placer nos clous et le format SVG pour un résultat plus net.

Photographie du hibou:

Photographie de Louciane:

Photographie des pommes:

Image originale trouvée sur Pexels

Time-lapses

Pour terminer, voici deux time-lapses, celui de la création d'un coeur, et celui de la création d'un hibou :

Remerciements et code source

Nous remercions tout d'abord M. Lachaud d'avoir proposé le sujet et de nous avoir accompagnés tout au long de son déroulement.

Nous remercions également Louciane Mangala qui a accepté de nous servir de modèle.

Notre reconnaissance va aussi aux mystérieuses personnes qui ont placé et habillé le hibou de la salle CMI, notre principal sujet d'expérimentation.

Pour les personnes désirant tester le programme ou en étudier le code source, il est disponlible ici : Répertoire GitHub

Si vous avez des questions, vous pouvez nous joindre par mail via notre adresse universitaire qui suit le format : Prenom.Nom<at>etu.univ-smb.fr