Wiki du LAMA (UMR 5127) - Contributions [fr]

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

2026-05-10T21:14:38Z

Lheote : /* Résultats finaux */

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

'''Étudiants :''' [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Utilisateur:Goralczyk Goralczyk Elliot], [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Utilisateur:Lheote Lhéoté Anaïs]

'''Tuteur :''' [https://jacquesolivierlachaud.github.io/ Jacques-Olivier Lachaud]

= Introduction =
Un [https://en.wikipedia.org/wiki/String_art 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.

[[Fichier:Exemple-importance-palcement-clous.png|center|100px]]

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é :

[[Fichier:Generation-clous-autour-de-l-image.gif|center|202px]]

=== 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écider 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'ils ne soient 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 :

[[Fichier:Generation-clous-aleatoires.gif|center|202px]]

=== Utiliser les contours ===

Afin d'obtenir des images plus détaillées, nous souhaitons placer les clous autour 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 [https://github.com/python-pillow/Pillow/blob/main/src/PIL/ImageFilter.py#L327 FIND_EDGES] de la bibliothèque Python [https://github.com/python-pillow/Pillow/ 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.

[[Fichier:Filtre-laplacien.png|center]]

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 :

[[Fichier:Schema-passage-pixels-matrice.png|center]]

À 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 :

[[Fichier:Schema-passage-pixels-matrice-somme-cumulative.png|center]]

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.

[[Fichier:Schema-probas-pixels-laplacien.png|center]]

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.

= 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 :

[[Fichier:Exemple-calcul-difference-images.png|center]]

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, la différence entre les deux images va diminuer, et l'image de droite va donc se rapprocher de celle de gauche :

[[Fichier:Exemple-calcul-difference-images-2.png|center]]

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 note implémentation de cet algorithme, nous avons fait le choix de s'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 touts 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 :

[[Fichier:Schema-intervalle-a.png|center]]

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 pixel, 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 [https://fr.wikipedia.org/wiki/Scalable_Vector_Graphics 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 :

[[Fichier:Comparaison-png-svg.png|center]]

= Évolution de l'algorithme =

= Résultats finaux =
Après de nombreux essais, voici les résultats que nous obtenons en utilisant le laplacien pour tracer nos droites, des clous qui sont sur le contour de l'image et le svg pour un résultat plus net.

Photographie du hibou:

[[Fichier:Hiboux_original.png|360px|left]]
[[Fichier:Hiboux_svg.png|360px|right]]

Photographie de Louciane:

[[Fichier:Louciane_originale.jpg|360px|left]]
[[Fichier:Louciane_svg.png|360px|right]]

Photographie des pommes:

[[Fichier:Pommes_originale.jpg|left]] [[Fichier:Pomme_svg.png|360px|right]]

Fichier:Pommes originale.jpg

2026-05-10T20:58:18Z

Lheote : Photographie originale des pommes.

== Description ==
Photographie originale des pommes.

Fichier:Louciane originale.jpg

2026-05-10T20:57:39Z

Lheote : Photographie originale de notre camarade.

== Description ==
Photographie originale de notre camarade.

Fichier:Hibou original.png

2026-05-10T20:56:36Z

Lheote : /* Description */

== Description ==
Photographie originale du hibou.

Fichier:Hibou original.png

2026-05-10T20:56:07Z

Lheote : Photographie originale du hiboux.

== Description ==
Photographie originale du hiboux.

Fichier:Pomme svg.png

2026-05-10T20:52:14Z

Lheote : Rendu final de la photo des pommes en svg, et utilisant le laplacien.

== Description ==
Rendu final de la photo des pommes en svg, et utilisant le laplacien.

Fichier:Louciane svg.png

2026-05-10T20:51:36Z

Lheote : Rendu final de la photo de notre camarade en svg, et utilisant le laplacien.

== Description ==
Rendu final de la photo de notre camarade en svg, et utilisant le laplacien.

Fichier:Hiboux svg.png

2026-05-10T20:50:12Z

Lheote : Rendu final du hiboux en svg, et utilisant le laplacien.

== Description ==
Rendu final du hiboux en svg, et utilisant le laplacien.

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

2026-05-10T15:44:10Z

Lheote : /* Introduction */

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

'''Étudiants :''' [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Utilisateur:Goralczyk Goralczyk Elliot], [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Utilisateur:Lheote Lhéoté Anaïs]

'''Tuteur :''' [https://jacquesolivierlachaud.github.io/ 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.
Pour cela nous avons du comprendre le principe en lui-même et nous avons ensuite élaboré plusieurs techniques pour pavenir au meilleur résultat possible.

= Placer les 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.

[[Fichier:Exemple-importance-palcement-clous.png|center|100px]]

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é :

[[Fichier:Generation-clous-autour-de-l-image.gif|center|202px]]

=== 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écider 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'ils ne soient 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 :

[[Fichier:Generation-clous-aleatoires.gif|center|202px]]

=== Utiliser les contours ===

Afin d'obtenir des images plus détaillées, nous souhaitons placer les clous autour 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 [https://github.com/python-pillow/Pillow/blob/main/src/PIL/ImageFilter.py#L327 FIND_EDGES] de la bibliothèque Python [https://github.com/python-pillow/Pillow/ Pillow]), on peut obtenir une image sur laquelle les contours de l'image de départ ressortent en blanc, et le reste en noir, comme sur l'exemple ci-dessous.

[[Fichier:Filtre-laplacien.png|center]]

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 <math>(h, l)</math>, avec <math> h </math> la hauteur en pixels de l'image, et <math> l </math> 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 :

[[Fichier:Schema-passage-pixels-matrice.png|center]]

À 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 :

[[Fichier:Schema-passage-pixels-matrice-somme-cumulative.png|center]]

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 <math>r</math>.
Il ne nous reste plus qu'à parcourir la matrice jusqu'à tomber sur un nombre plus grand que <math>r</math>.
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 <math>r = 268</math>, 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.

[[Fichier:Schema-probas-pixels-laplacien.png|center]]

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.

= 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 on doit 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 :

[[Fichier:Exemple-calcul-difference-images.png|center]]

Une fois que nous avons calculé cette différence, il faut calculer la différence que l'on obtiendrait si la droite eé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, la différence entre les deux images va diminuer, et l'image de droite va donc se rapprocher de celle de gauche :

[[Fichier:Exemple-calcul-difference-images-2.png|center]]

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 note implémentation de cet algorithme, nous avons fait le choix de s'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 touts 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 :

[[Fichier:Schema-intervalle-a.png|center]]

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 pixel, 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 [https://fr.wikipedia.org/wiki/Scalable_Vector_Graphics 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 :

[[Fichier:Comparaison-png-svg.png|center]]

= Évolution de l'algorithme =

= Résultats finaux =