Diffusion d'erreur

La diffusion d'erreur est une technique d'amélioration du rendu des images infographiques en cas de diminution du nombre de codes de couleurs. Elle se combine à l'anticrénelage. Elle sert dans les systèmes informatiques capables d'afficher seulement un petit nombre de couleurs, et dans les imprimantes, pour lesquelles les pixels n'ont que deux valeurs, avec du toner ou sans.

Elle consiste à répartir sur les pixels voisins les erreurs de quantification issues de l'assimilation de la couleur d'un pixel à une couleur prise dans une gamme réduite.

Elle limite l'apparition de motifs tels que le banding (rendu graduel de la luminosité ou de la teinte) dans les images au prix d'une augmentation du bruit^{[réf. souhaitée]}.

En audio, la réduction du bruit de quantification se fait par application d'un signal aléatoire appelé dither, anglicisme officiellement traduit par vibration et tremblement ou signal de superposition. Le même terme s'applique parfois à la diffusion d'erreurs en raison d'une histoire commune. Le tramage utilisé en similigravure a aussi servi de modèle, et son nom est aussi quelquefois employé pour les techniques de quantification de la couleur en informatique.

Principe

Mélange optique des couleurs. Plus le pixel est petit, plus la zone semble d'une couleur unie intermédiaire entre les couleurs des éléments.

La diffusion d'erreur sert en infographie à donner l'illusion d'une profondeur de couleur supérieure en utilisant d'une palette couleurs limitée (quantification de couleur). On approche les couleurs non disponibles de la palette en faisant en sorte que la couleur moyenne d'un groupe de pixels soit celle de l'aire correspondante de l'original. L'œil humain perçoit la juxtaposition de petits éléments colorés comme un mélange de couleurs. Les écrans informatique ou de télévision utilisent cette propriété de fusion des couleurs pour afficher une image en couleurs avec des luminophores de seulement trois couleurs. Pour réaliser simplement ce procédé, l'algorithme de diffusion d'erreur enregistre pour chaque pixel la différence entre le code de couleur le plus proche dans la palette de sortie et celui d'origine, et ajoute cette différence aux pixels voisins, avant de rechercher la couleur la plus proche.

Le processus de réduire les couleurs disponibles à une palette couleurs est une quantification. La perte d'une certaine quantité d'informations cause des erreurs d'arrondi. En répartissant ces erreurs, l'algorithme les rend moins évidentes.

Photographie numérique et traitement d'images

Des images réduites à un petit nombre de couleurs par diffusion d'erreur peuvent souvent être distinguées par leur grain ou leur apparence mouchetée^{[réf. souhaitée]}.

La diffusion d'erreurs étant un procédé qui nécessite beaucoup^[Quoi ?] de calculs, plusieurs constructeurs avaient développé, à une époque, des gestionnaires qui n'utilisaient que des couleurs unies, avec une incidence sur la qualité. Ainsi en fonction des applications, la qualité de l'image pouvait beaucoup varier^{[réf. nécessaire]}.

Historiquement, le procédé de diffusion d'erreur a été mis en œuvre dans les logiciels de retouche d'image pour un affichage en 16 millions de couleurs alors que le mode^[Quoi ?] n'en proposait que 256. Chaque nuance manquante était simulée par la juxtaposition de plusieurs points diversement colorés^{[réf. nécessaire]}.

Certains constructeurs de cartes graphiques avaient mis en œuvre une « power palette » qui permettait de remplacer la teinte manquante par la couleur de la palette la plus approchante. Dans cette technologie, l'affichage était plus rapide, car de fait la diffusion d'erreur dynamique disparaît, mais le rendu des couleurs était nettement moins bon^{[réf. nécessaire]}.

Exemple

Réduire la profondeur de couleur d'une image peut souvent avoir d'importants effets secondaires. Si l'original est une photographie, elle a probablement des milliers ou même des millions de codes de couleur distincts^{[réf. souhaitée]}.

Plusieurs facteurs peuvent affecter la qualité d'une image dont le nombre de couleurs a été réduit. Peut-être le plus important est la palette couleurs qui sera utilisée pour une image réduite. Par exemple, une image originale (figure 1) peut être réduite aux 216 couleurs de la palette couleurs garantie pour le Web (Web-safe). Si les couleurs des pixels originaux sont simplement traduites par les couleurs disponibles les plus proches dans la palette, aucune diffusion d'erreur n'est effectuée (figure 2). Typiquement, cette approche se traduit dans des zones planes (sans profondeur de couleurs) par une perte de détails, pouvant produire des taches dont les couleurs sont différentes de l'image originale. Les zones ombragées ou de dégradé peuvent apparaître sous la forme de bandes de couleur, pouvant être dérangeantes. L'utilisation de la diffusion d'erreur peut contribuer à minimiser ces artéfacts visuels, et se traduit généralement par un résultat de meilleure qualité (figure 3). Il permet de réduire les bandes de couleur et le manque de profondeur^{[réf. souhaitée]}.

La sélection de couleurs d'une palette fixe contient souvent une quantité de nuances inutiles ; par exemple, les nuances de vert ou bien les couleurs vives ne servent pas pour une image qui n'en contient pas. Les couleurs d'une palette optimisée sont choisies sur la base de leur fréquence d'utilisation dans l'image originale servant de source. Si la réduction de l'image est réalisée sur la base d'une palette optimisée, le résultat est souvent bien plus proche de l'original (figure 4)^{[réf. souhaitée]}.

Le nombre de couleurs disponibles dans la palette est aussi un facteur contributif. Avec une palette limitée à 16 couleurs, l'image traitée peut perdre des détails, et avoir des problèmes encore plus visibles liés à leur manque de profondeur et de graduation (figure 5). Une fois de plus, la diffusion d'erreur peut aider à réduire de tels artefacts (figure 6).

• 
  Figure 1. Image originale.
• 
  Figure 2. Image originale utilisant une palette couleurs Web-safe sans diffusion d'erreur.
• 
  Figure 3. Image originale utilisant une palette couleurs Web-safe avec diffusion d'erreur.
• 
  Figure 4. Image originale utilisant une palette couleurs optimisée de 256 couleurs avec diffusion d'erreur.
• 
  Figure 5. Image originale utilisant une palette couleurs optimisée de 16 couleurs sans diffusion d'erreur.
• 
  Figure 6. Image originale utilisant une palette couleurs optimisée de 16 couleurs avec diffusion d'erreur.

Applications

Les appareils graphiques, incluant les premières cartes graphiques d'ordinateur et de nombreux afficheurs LCD utilisés dans les téléphones portables et les appareils photo numérique d'entrée de gamme, offrent une profondeur de couleurs plus faible que sur ceux plus récents^{[réf. souhaitée]}. Une application courante de la diffusion d'erreur est d'afficher plus précisément des graphiques contenant un nombre de couleurs plus grand que l'appareil n'est capable d'en afficher. Elle peut être utilisée afin d'afficher une image photographique contenant potentiellement un million de couleurs avec des cartes graphiques qui ne sont capables d'en restituer que 256 à la fois. Ces 256 couleurs sont utilisées pour créer une approximation de l'image originale. Sans cela, les couleurs de l'image originale seraient simplement approchées par les couleurs les plus proches disponibles, donnant comme résultat une nouvelle image qui serait une médiocre représentation du modèle. La diffusion d'erreur utilise la tendance de l'œil humain à "mélanger" deux couleurs proches l'une de l'autre.

Un tel procédé, pour lequel le matériel d'affichage informatique est la principale limite de la profondeur des couleurs, est habituellement employé dans les logiciels comme les navigateurs web. Puisqu'un navigateur peut afficher des images provenant d'une source externe, il peut lui être nécessaire d'effectuer une réduction sur celles ayant trop de couleurs par rapport à celles disponibles sur la palette. C'est pour éviter les problèmes liés au calcul de diffusion d'erreur qu'une palette couleurs appelée Web-safe color a été définie, ne permettant de sélectionner que celles qui ne soient pas tramées sur les moniteurs ne permettant d'en afficher que 256.

Toutefois, même quand le nombre total de couleurs disponibles du matériel d'affichage est suffisamment élevé pour le rendu des photos numériques en couleur comme celles de 15 et 16 bits RVB Hicolor offrant entre 32 768 et 65 536 couleurs, des bandes peuvent être visibles pour l'œil, en particulier dans les grandes zones de dégradé des ombres (bien qu'elles n'apparaissent pas sur le fichier de l'image d'origine). Réduit à un niveau de 32 ou 64 bits RVB, le rendu donnera une bonne approximation d'un affichage pseudo truecolor, que l'œil n'interprétera pas comme granuleux. De plus, une image affichée sur du matériel supportant le 24-bits RVB (8 bits par couleur primaire) peut être réduite pour simuler une profondeur de couleurs un peu plus grande et/ou pour minimiser la perte de teintes disponibles après une correction gamma.

Une autre utilisation utile de la diffusion d'erreur est pour les cas dans lesquels le format graphique des fichiers est le facteur limitant. En particulier, le format GIF d'usage courant est restreint à l'utilisation de 256 couleurs ou moins dans de nombreux programmes d'édition graphique. Des images dans d'autres formats de fichier, tel que le PNG, peut également avoir de telles restrictions imposées en vue de la réduction de la taille des fichiers. De telles images ont une palette couleurs fixée définissant toutes les couleurs que l'image peut utiliser. Dans ces situations, les éditeurs d'image matricielle peuvent prendre en charge la réduction du nombre de couleurs des images avant de les enregistrer dans ces formats restrictifs.

Algorithmes

Plusieurs algorithmes permettent de réaliser la réduction du nombre de couleurs.

Seuillage

La méthode la plus simple pour réduire le nombre de couleurs est l'assimilation à la couleur la plus proche, parmi celles disponibles.

En noir et blanc, on opère la réduction par moyenne ou seuillage (thresholding) qui compare chaque valeur de couleur de pixel à un seuil fixé.

Il s'agit peut-être de l'algorithme de réduction du nombre de couleurs le plus simple, mais il cause une grande perte de détails et de contours. La méthode d'Otsu permet de déterminer le seuil adéquat par analyse de l'histogramme des valeurs de l'image

Dithering

Le tremblotement (dithering) est une méthode classique en audionumérique. Goodal l'appliqua dès 1951, sous le nom de noise encoding pour remédier aux inconvénients du seuillage pour l'image (Alain 2009, p. 18). Il compare la valeur de chaque pixel à un seuil aléatoire. Bien que cette méthode très rapide ne génère pas d'artefacts répétitifs, le bruit tend à déborder sur les détails de l'image. La méthode a un rendu analogue à la manière noire utilisée dans la gravure.

Tramage

Le tramage applique le principe de la trame d'imprimerie qui combine les pixels dans une forme répétitive. Il permet de reproduire le nombre de couleurs de la palette, multiplié par le nombre de pixels du motif répété. La couleur résultante est la moyenne des couleurs affichées dans le motif. La résolution est réduite à celle du motif.

Différents motifs peuvent créer des effets de tramage complètement différents :

• le tramage en demi-teinte (halftone, halftoning) qui ressemble à l'impression dite en demi-teinte ou en similigravure (traduit en halftone en anglais) des journaux. Il s'agit d'une forme de tramage par grappes, dans lesquels les points tendent à être regroupés. Cela permet de masquer les effets secondaires de pixels flous affichés sur d'ancien périphériques d'affichage^{[réf. souhaitée]} ;
• le tramage ordonné ou tramage de Bayer génère un motif de hachures. Il s'agit d'une forme de tramage dispersé. Parce que les points ne sont pas regroupés en grappes, le résultat obtenu est beaucoup moins granuleux^{[réf. souhaitée]}.

(Original)	Seuillage	Aléatoire (Dither)	Demi-teinte ou similigravure (Halftone)	Ordonné

Diffusion d'erreurs

L'algorithme de Floyd-Steinberg, développé en 1975, est le plus connu et un des tout premiers algorithmes de diffusion d'erreur. Il calcule la différence algébrique entre la couleur demandée pour un pixel et la couleur disponible la plus proche, et ajoute cette différence pondérée par une matrice aux quatre pixels voisins non encore traités.

Tout en restant simple, cet algorithme minimise les artefacts visuels ; les algorithmes de diffusion d'erreur produisent des images plus proches de l'originale que des algorithmes plus simples.

D'autres algorithmes procèdent de façon similaire :

• l’algorithme Jarvis, Judice & Ninke diffuse les erreurs aux pixels un peu plus éloignés. Ce procédé génère moins d'artefacts visuels, au prix d'une réduction du détail. Il est plus lent que le précédent parce qu'il distribue les erreurs jusqu'aux douzièmes pixels au lieu des quatrièmes pour le Floyd–Steinberg ;
• l’algorithme Stucki qui est basé sur le Jarvis, Judiec & Ninke mais est un peu plus rapide. Son résultat tend à être propre et précis ;
• l’algorithme Burkes est une forme simplifiée du Stucki plus rapide mais moins propre ;
• l’algorithme Scolorq est un algorithme expérimental de quantification de couleur spatiale qui combine la quantification de couleur et la diffusion d'erreurs pour produire une image optimale. À cause de sa nature, l'image d'exemple ci-dessous n'est pas strictement en noir & blanc, mais à deux tons de gris ;

Floyd–Steinberg	Jarvis, Judice & Ninke	Stucki	Burkes

• l’algorithme Sierra est basé sur celui de Jarvis, Judice & Ninke, il est plus rapide tout en rendant des résultats similaires.
• l’algorithme Two-row Sierra est une variante du Sierra par son auteur pour améliorer sa rapidité.
• l’algorithme Filter Lite est un algorithme créé par Sierra qui est plus simple et plus rapide que le Floyd–Steinberg, bien que donnant des résultats similaires.
• l’algorithme Atkinson ressemble au tramage Jarvis, Judice & Ninke et Sierra mais est plus rapide. Une autre différence est qu'il ne diffuse pas intégralement l'erreur de quantification, mais seulement les trois-quarts. Il tend à bien préserver les détails, mais les zones très claires ou très sombres peuvent apparaître comme soufflées.
• l’algorithme Hilbert–Peano est une variante du tramage Riemersma et est utilisé par Imagemagick.

Sierra	Two-row Sierra	Filter Lite	Atkinson

.

Annexes

Bibliographie

• Benoît Alain, Rendu d’images en demi-tons par diffusion d’erreur sensible à la structure : Mémoire M.Sc. Université de Montréal, 2009 (lire en ligne)
• Jianghao Chang, Le rendu en demi-ton avec sensibilité à la structure : Mémoire M.Sc. Université de Montréal, 2011 (lire en ligne)
• Victor Ostromoukhov, Reproduction couleur par trames irrégulières et semi-irrégulières : Mémoire de doctorat Université de Lausanne, 1995 (lire en ligne)
• Thierry Gervais, « La similigravure », Nouvelles de l’estampe, n^o 229,‎ 2010 (DOI https://doi.org/10.4000/estampe.1337, lire en ligne)

Articles connexes

• Trame (imprimerie)
• Dither (audio)
• Segmentation d'image
• Quantification de couleur (en)