Implémentation d’un algorithme simple de dithering: Floyd–Steinberg dithering
Il y a tout juste 1 semaine, nous avons organisé en tant que BDE à 42 un Week-end de désintégration en Auvergne.
Pour ce week-end, on a fait face à un problème technique qu’on a pas réussi à résoudre. Un de nos partenaires pour la création de t-shirts nous a demandé notre logo au format vectoriel et nous avions seulement notre logo au format PNG. De ce fait, notre premier réflexe a était de rechercher “Convert PNG to SVG” sur Google et les résultats étaient décevants. 99% des convertisseurs que l’on peut trouver sur le WEB sont mauvais.
Je me suis mis à chercher de mon côté comment on pouvait réaliser ce type de convertisseur de manière efficace. La documentation sur ça est très pauvre si on ne plonge pas dans la littérature scientifique. La réalisation d’un tel convertisseur demande l’implémentation de plusieurs algorithmes et l’un d’eux est le dithering.
L’algorithme de dithering
A la base, le dithering permet de convertir des images ayant un spectre de couleur continue vers une image qui prend en compte un nombre fini de couleurs. Dans notre implémentation il y aura 2 couleurs dans notre spectre, du noir et du blanc.
Quel est le but du dithering dans la vectorisation d’une image ?
Pour faire simple, l’algorithme de dithering nous permettra de créer des points qu’on reliera ensuite en triangle pour former une image vectorisée. De ce fait, la qualité de l’algorithme de dithering va être déterminant dans le résultat final car celui-ci doit conserver les détails de l’image d’origine.
Floyd–Steinberg dithering
L’algorithme va déterminer pour chaque pixel si celui ci doit valoir 0 ou 1. Une manière assez naïve de faire serait de mettre un threshold à 0.5. Tout ce qui est compris entre 0.5 et 1 sera noir et le reste blanc. Mais cette méthode ne prend pas en compte l’erreur faite sur le niveau de détail de l’image.
Imaginons que tout nos pixels sont gris. Un algorithme simple comme décrit plus haut construira une image toute noire et toute l’information sur le gris sera donc perdu. De ce fait, il nous faut un algorithme qui propage cet erreur sur les pixels voisins dès qu’un pixel est colorisé.
C’est exactement ce que propose l’algorithme de Floyd-Steinberg. Dès qu’un pixel est définit comme noir ou blanc, on change la valeur des pixels avoisinants selon certaines constantes prédéfinies.
Voici comment les valeurs changent pour une image simple composée uniquement de pixels gris (0.5):
Voici un exemple réel de résultat sur une photo:
Notes sur l’implémentation
J’ai décidé de faire une implémentation de cet algorithme en Go pour plusieurs raisons:
- Cela permettra une implémentation potentiel sur le WEB assez facilement
- On peut gagner du temps d’éxecution avec un bon multi-threading et des algorithmes bien optimisés comparé à un language comme Python
- Je voulais tester un nouveau language
Les deux seuls soucis à l’utilisation de GO serait le nombre de castings à faire, on doit constamment changer de type pour concorder à l’algorithme. De plus, ce n’est pas un language optimisé pour des formules mathématiques et cela posera peut-être problème lorsqu’on plongera dans des algorithmes plus complexes.
Si vous voulez check l’implémentation de cet algorithme (main.go): https://github.com/msiesse/SimpleDither
Vous pouvez me suivre sur les réseaux sociaux: