Tramage (informatique)

Pour les articles homonymes, voir Tramage.

Le tramage est une technique d'amélioration de données numériques sonores et visuelles basée sur la correction des défauts par une application volontaire de bruit rendant aléatoire les distorsions.

Le tramage est une forme de bruit volontairement appliqué pour rendre aléatoire les erreurs de quantification, ce qui empêche les modèles à grande échelle tels que le banding (rendu graduel de la luminosité ou de la teinte) dans les images, ou de bruit à des fréquences discrètes dans un enregistrement audio, qui sont plus désagréables que le bruit non corrélé. Le tramage est couramment utilisé dans le traitement de ces deux types de données audio et vidéo numériques, et est souvent l'une des dernières étapes de la production audio d'un disque compact.

Le traitement de données numériques et l'analyse des formes ondulatoires

Le Tramage est souvent employé dans le traitement des données numériques audio et vidéo, où il s'applique aux conversions du taux d'échantillonnage et à la transition au niveau des bits ; il est utilisé dans différents et nombreux domaines où le traitement et l'analyse des données est de rigueur - plus particulièrement l'analyse des formes ondulatoires. Cette utilisation comprend les systèmes utilisant le traitement numérique du signal, comme le son numérique, la vidéo numérique, la photographie numérique, la sismologie, le radar, les systèmes de prévision météorologique et beaucoup d'autres.

La proposition de départ est que la quantification et la re-quantification de données numériques produisent des erreurs. Si l'erreur est récurrente et est corrélée au signal, elle sera répétitive, cyclique et mathématiquement prévisible. Dans quelques domaines, précisément quand le récepteur est sensible à de tels artefacts, les erreurs cycliques en produisent d'indésirables. Dans les domaines suivants, le tramage permet de les transformer de façon à ce qu'ils soient moins génants. Le domaine du son en est un bon exemple - l'oreille humaine fonctionne comme une transformation de Fourier, dans laquelle les fréquences sont entendues individuellement. L'oreille est donc très sensible à la distorsion, ou au contenu par addition de fréquence qui "colore" le son différemment, mais est beaucoup moins sensible au bruit aléatoire quelle que soit la fréquence.

Tramage d'un signal sonore

Article détaillé : Quantification.

Dans un article fructueux, Lipshitz et Vanderkooy soulignèrent que différents types de bruits, avec différentes densités de probabilité se comportent différemment quand ils sont utilisés comme signal tramé, et suggérèrent un niveau de tramage optimal pour les signaux sonores^[1]'^[2].

« Dans un système analogique, le signal est continu, mais dans un système numérique par modulation d'impulsion codée, l'amplitude du signal sortant du système numérique est limitée à l'un des ensembles de valeurs ou de nombres fixés. Ce processus est appelé quantification. chaque valeur codée est un niveau discret… si un signal est quantifié sans utiliser de tramage, il y aura une distorsion liée au signal d'entrée d'origine… Afin d'éviter cela, le signal est tramé, un processus qui mathématiquement supprime entièrement les harmoniques ou les autres distortions indésirables, et qui les remplace par une constante, un niveau de bruit fixe »^[3].

La version finale d'un enregistrement sonore qui est destinée à un compact disc contient seulement 16 bits par échantillon, toutefois au cours du processus de production une quantité plus importante d'information est utilisée pour le réprésenter. Au final, les données numériques doivent être réduites à 16 bits pour le gravage et la distribution.

De multiple façons existent pour faire cela. Il est possible par exemple de supprimer les 'bits' en trop - procédé appelé troncature. Il est également possible d’arrondir ces bits excessifs à la valeur la plus proche. Chacune de ces méthodes, cependant, conduisent à des erreurs dans le résultat, déterminables et prévisibles. Prenons par exemple un signal composé des valeurs suivantes :

1   2   3   4   5   6   7   8

Si nous réduisons l'onde de, disons de 20%, alors nous obtenons les valeurs suivantes :

0.8 1.6 2.4 3.2 4.0 4.8 5.6 6.4

Si nous tronquons ces valeurs nous obtenons les valeurs ci-dessous :

0   1   2   3   4   4   5   6

Si au lieu de cela nous arrondissons ces valeurs nous obtenons les valeurs suivantes :

1   2   2   3   4   5   6   6

Quelle que soit la forme d'onde initiale, le processus de réduction de l'amplitude de l'onde de 20% se traduit par des erreurs régulières. Prenez par exemple une onde sinusoïdale qui, pour une certaine portion, correspond aux valeurs ci-dessus. Chaque fois que la valeur de l'onde sinusoïdale atteint une valeur de "3,2", le résultat sera tronqué au plus de 0,2, comme dans l'exemple de données ci-dessus. Chaque fois que cette onde atteint la valeur "4,00", il n'y aura pas d'erreur liée à la troncature car l'écart sera nul, exemple également montré ci-dessus. L'ampleur de ces erreurs change régulièrement et à maintes reprises tout au long du cycle de l'onde sinusoïdale. C'est précisément cette erreur qui se manifeste comme une distorsion. Ce que l'oreille entend comme de la distorsion est du contenu additionnel à des fréquences discrètes créé par une erreur de quantification de façon régulière et répétée.

Une solution plausible serait de prendre le nombre à 2 chiffres (par exemple, 4,8) et l'arrondir dans un sens ou dans l'autre. Par exemple, nous pourrions l'arrondir à 5 une fois et puis à 4, la fois suivante. Cela donnerait une moyenne à long terme de 4,5 au lieu de 4, de sorte que sur le long terme, cette valeur est plus proche de sa valeur réelle. Cela, d'autre part, génère toujours une erreur déterminable (bien que plus complexe). Une fois sur deux quand la valeur 4,8 apparaît cela entraîne une erreur de 0,2 et une fois sur deux elle est de -0,8. Cela a pour conséquence de répéter une erreur quantifiable.

Une autre solution plausible serait de prendre 4,8 et de l'arrondir de telle façon les quatre premières fois sur cinq, il soit arrondi à 5, et la cinquième fois à 4. Une moyenne de 4,8 serait atteinte sur le long terme. Malheureusement, cette solution génère toujours des erreurs reproductibles et déterminables qui se manifestent par des distorsions à l'oreille (bien qu'un suréchantillonnage peut les diminuer).

Cela conduit à la solution de tramage. Plutôt que d'arrondir à la hausse ou à la baisse de façon prévisible en un motif répétitif, qu'arriverait-il si nous arrondissions de façon aléatoire ? Si nous trouvions un moyen pour transformer au hasard nos résultats entre 4 et 5 de sorte que 80% du temps, il se retrouve à 5 alors nous aurions en moyenne 4,8 sur le long terme, mais de façon aléatoire, sans erreur récurrente dans le résultat. Cela se fait par "tramage".

Exemple sonore :

Fichier audio
16-bit sine wave (info) Des problèmes pour écouter le fichier ?

Nous calculons une série de nombres aléatoires compris entre 0,0 et 0,9 (ex: 0,6 ; 0,1 ; 0,3 ; 0,6 ; 0,9 ; etc) et on additionne ces nombres aléatoires pour les résultats de notre équation. Deux fois sur dix, le résultat obtenu sera tronqué à 4 (si 0,0 ou 0,1 sont ajoutés à 4,8) et le reste du temps il sera tronqué à 5, mais chaque situation donnée a une chance aléatoire de 20% d'obtenir un arrondi à 4 ou 80 % de chance d'avoir un arrondi à 5. À long terme cela se traduira dans les résultats par une moyenne à 4,8 et une erreur de quantification - ou bruit - qui est aléatoire. Le «bruit» résultant est moins choquant à l'oreille que la distorsion déterminable qui serait obtenu autrement.

Utilisation

Le tramage devrait être utilisé pour un signal périodique de fréquence élevé et de faible amplitude avant toute quantification ou processus de re-quantification, afin de décorréler le bruit de quantification du signal d'entrée et d'éviter les comportements non-linéaire (distorsion) ; moins la profondeur de bit est élevée et plus le tramage doit être efficace. Tout processus de réduction de bits devrait ajouter un tramage à la forme d'onde.

Les différents types de tramage

RPDF est l'acronyme de (en) "Rectangular Probability Density Function" (densité de probabilité rectangulaire), équivalent à un lancé de dé. Tous les nombres ont une probabilité de tirage équivalente.

TPDF signifie (en) "Triangular Probability Density Function" (densité de probabilité triangulaire) ou Loi triangulaire, et est l'équivalent d'un lancé de deux dés (la somme de deux échantillons indépendants d'une RPDF).

Gaussien PDF (densité de probabilité gaussienne) est équivalent au lancement d'un grand nombre de dés. La relation des probabilités de résultats suite à une forme de cloche, ou courbe de Gauss, typique d'un tramage généré par des sources analogiques, tels que des préamplificateurs de micro. Si la profondeur de bits d'un enregistrement est suffisamment grande, le bruit sera suffisant pour trammer l'enregistrement.

Tramage coloré est parfois mentionné comme un tramage qui a été filtré pour être différent d'un bruit blanc. Des algorithmes de tramage utilise des bruits qui ont plus d'énergie dans les hautes fréquences de manière à la réduire dans la bande audio critique.

Noise Shaping est un processus de rétroaction qui intègre un tramage. Il est généralement utilisé dans les travaux audio pour générer un tramage coloré utilisant son énergie essentiellement dans les hautes fréquences, donc les moins audibles.

Quel type de tramage utiliser ?

Si le signal devant être tramé devait subir d'autres traitements, alors il devrait être traité avec la méthode TPDF qui a une amplitude de quantification de deux niveaux (de sorte que les valeurs de tramage calculées s'étendent de -1 à +1 ou de O à 2)^[2]. Il s'agit du tramage idéal à la plus faible puissance, à partir duquel aucun bruit de modulation (bruit plancher constant) n'est introduit et qui élimine les distorsions harmoniques provenant de la quantification. Si le tramage coloré est utilisé à ce niveau intermédiaire de traitements alors le contenu d'une fréquence peut "baver" sur une autre, sur une gamme de fréquence importante et devenir passablement audible.

Si le signal étant tramé ne subissait pas d'autres traitement - c'est-à-dire devrait être tramé pour son utilisation final avant transmission - alors le tramage coloré ou le traitement noise shaping sont appropriés, et peuvent effectivement abaisser le niveau de bruit audible dans des gammes de fréquence où il est le moins préjudiciable.

Photographie numérique et traitement de l'image

Illustration du tramage. Couleur rouge et couleur bleu. Plus le pixel devient petit, plus la zone semble de couleur violet.

Le tramage est une technique utilisée en infographie pour donner l'illusion de la profondeur de couleur d'une image à partir d'une palette couleurs limitée (quantification de couleur). Dans une image trammée, les couleurs non disponibles de la palette sont approchées par une diffusion de pixels colorés à partir de celle présente. L'œil humain perçoit la diffusion comme un mélange de couleurs (vision des couleurs). Le tramage est analogue à la technique du halftone utilisée dans l'impression. Des images tramées, spécifiquement celles avec relativement peu de couleurs, peuvent souvent être distinguées par leur grain ou leur apparence mouchetée.

Le tramage est un procédé permettant de simuler des couleurs non disponibles en juxtaposant des points diversement colorés. Ce procédé est également appelé « couleur indexée ». Par exemple sur un écran vidéo l'affichage d'une photo « True Color » dans un mode vidéo n'offrant que 256 couleurs impliquait le tramage des couleurs absentes de la palette couleurs du système.

Le tramage étant un procédé qui nécessite beaucoup 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é du tramage pouvait beaucoup varier.

Historiquement, le procédé de tramage avait donc été mis en œuvre dans les logiciels de retouche d'image pour un affichage en 16 millions de couleurs alors que le mode n'en proposait que 256. Chaque nuance manquante était simulée par la juxtaposition de plusieurs points diversement colorés.

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 le tramage dynamique disparaît, mais le rendu des couleurs était nettement moins bon.

Exemple

Réduire la profondeur de couleur d'une image peut souvent avoir d'important effets secondaires. Si l'original est une photographie, elle a probablement des milliers ou même des millions de couleurs distinctes. Le processus de réduire les couleurs disponibles à une palette couleurs effectivement fait perdre une certaine quantité d'informations les concernant.

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 Web-safe. Si les couleurs des pixels originaux sont simplement traduits par les couleurs disponibles les plus proches dans la palette, aucun tramage n'est effectué (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érangeante. L'utilisation du tramage peut contribuer à minimiser ces artéfacts visuels, et se traduit généralement par un résultat de meilleur qualité (figure3). Il permet permet de réduire les bandes de couleur et le manque de profondeur.

Un des problèmes lié à l'utilisation d'une palette couleurs fixe est que beaucoup de couleurs nécessaires peuvent ne pas être disponibles, et beaucoup d'autres présentes peuvent ne pas servir ; par exemple, une palette couleurs fixe contenant principalement des nuances de vert ne serait pas adaptée à une image ne contenant pas ces nuances. L'utilisation d'une palette couleurs optimisée peut être bénéfique dans de tels cas. Une palette couleurs est dite optimisée quand les couleurs à disposition 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).

Le nombre de couleurs disponibles dans la palette est aussi un facteur contributif. Si, par exemple, la palette est limitée à seulement 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 - cf. (en) color banding - (Figure 5). Une fois de plus, le tramage peut aider à réduire de tels artefacts (Figure 6).

• 

  Figure 1. image originale.

• 

  Figure 2. image originale utilisant une palette de couleur web-safe sans tramage.

• 

  Figure 3. image originale utilisant une palette de couleur web-safe avec tramage.

• 

  Figure 4. image originale utilisant une palette optimisée de 256 couleurs avec tramage.

• 

  Figure 5. image originale utilisant une palette optimisée de 16 couleurs sans tramage.

• 

  Figure 6. image originale utilisant une palette optimisée de 16 couleurs avec tramage.

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. Une application courante du tramage 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. Par exemple, le tramage, peut être utilisé afin d'afficher une image photographique contenant un millions de couleurs sur des monitors vidéo qui ne sont capables que d'en restituer 256 à la fois. Ces 256 couleurs sont utilisées pour créer une approximation tramée de l'image originale. Sans cela, les couleurs de l'image original seraient simplement approximé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. Le tramage utilise la tendance de l'œil humain à "mélanger" deux couleurs proches l'une de l'autre.

Des écrans à cristaux liquides utilisent le tramage temporel pour obtenir des effets similaires. En alternant rapidement chacune des valeurs des couleurs des pixels entre deux couleurs approximatives de la palette (connu également sous le nom de contrôle du taux d'affichage), un moniteur qui supporte nativement des couleurs de 18-bit (six bits par canaux) peut afficher une image en 24 bits true color (8 bits par canaux)^[4].

Un tel tramage, 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 un tramage sur celles ayant trop de couleurs par rapport à celles disponibles sur la palette. C'est pour les problèmes liés au tramage 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 Rouge vert bleu 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). Tramé à 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 tramée 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 du tramage 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 programme d'édition graphique. Des images dans d'autres formats de fichier, tel que le PNG, peut également avoir de telles restrictions imposées au nom 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 le tramage des images avant de les enregistrer dans ces formats restrictifs.

Algorithmes

Plusieurs algorithmes permettent de réaliser le tramage. Le plus connu et un des tout premiers, développé en 1975, est l'algorithme de Floyd-Steinberg qui utilise une diffusion de l'erreur d'un pixel à ses voisins via une matrice. Un des atouts de cet algorithme est qu'il minimise les artefacts visuels grâce à un processus d'erreur diffusion ; les algorithmes d'erreur diffusion (du type Halftoning) produisent des images plus proches de l'original que des algorithmes plus simples de tramage^[5].

Les méthodes de tramage comprennent :

• Thresholding (également appelé tramage moyen^[6] : chaque valeur de couleur de pixel est comparé à un seuil fixé. Il s'agit peut-être du plus simple algorithme de tramage existant, mais il est la cause d'une grande perte de détails et de contours^[5].
• Le tramage aléatoire était le premier essai (du moins dès 1951) à remédier aux inconvénients du thresholding. Chaque valeur des pixels est comparée à un seuil aléatoire d'une image fixe. Bien que cette méthode ne génère pas d'artéfacts répétitifs, le bruit tend à déborder sur les détails de l'image. La méthode est analogue à la manière noire utilisée dans la gravure^[5].
• Le tramage par modèle utilisant un modèle fixé. Pour chaque pixel dans l'image la valeur du "modèle" à la position correspondante est utilisée comme seuil. Différents modèles peuvent créer des effets de tramage complètement différents.
  • Le tramage Halftone ressemble à l'impression halftone des journaux. Il s'agit d'une forme de tramage par cluster, dans lesquels les points tend à être regroupés. Cela permet de masquer les effets secondaires de pixels flous affichés sur d'ancien périphériques d'affichage.
  • Le tramage ordonné ou 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 clusters, le résultat obtenu est beaucoup moins granuleux.

(Original)	Threshold	Aléatoire	Halftone	Bayer (ordonné)

• Le tramage par erreur-diffusion diffuse les erreurs de quantification au pixels voisins.
  • Le tramage Floyd-Steinberg diffuse l'erreur uniquement aux pixels voisins. Il en résulte un tramage très fin.
  • Le tramage jarvis, Judice, and Ninke diffuse les erreurs aux pixels un peu plus éloignés. Ce tramage est plus grossier, mais génère moins d'artefacts visuels. Il est plus lent que le précédent parce qu'il distribue les erreurs jusqu'aux douzième pixels au lieu du quatrième pour le Floyd-Steinberg.
  • Le tramage Stucki est basé sur le précédent, mais est un peu plus rapide. Son résultat tend à être propre et précis.
  • Le tramage Burkes est une forme simplifiée du tramage Stuki qui est plus rapide mais moins propre.
  • Scolorq est un algorithme expérimental de quantification de couleur spatiale qui combine la quantification de couleur et le tramage pour produire une image optimale. A cause de sa nature, l'image d'exemple ci-dessous n'est pas strictement en noir et blanc, mais à deux tons de gris^[7].

Floyd–Steinberg	Jarvis, Judice & Ninke	Stucki	Burkes	Scolorq
				Fichier:Michelangelo's David - Scolorq.png

• Tramage par erreur-diffusion (suite) :
  • Le tramage Sierra est basé sur celui de Jarvis, il est plus rapide tout en rendant des résultats similaires.
  • Le tramage Two-row Sierra est une variante du précédent par son auteur pour améliorer sa rapidité.
  • Le Filtre 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.
  • Le tramage Atkinson ressemble au tramage Jarvis 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é".
  • Le tramage Hilbert-Peano est une variante^[8] du tramage Riemersma et est utilisé par Imagemagick^[9].

Sierra	Two-row Sierra	Filter Lite	Atkinson	Hilbert-Peano
				Fichier:Michelangelo's David - Hilbert-Peano.png

.

Notes et références

1. ↑ (en) Stanley P Lipshitz, John Vanderkooy, Robert A. Wannamaker, Minimally Audible Noise Shaping, J. Audio Eng. Soc., vol.36, n°11, p.836-852, novembre 1991 dernier accès le 28/10/2009 [lire en ligne]
2. ↑ ^{a et b} (en) Stanley P Lipshitz, John Vanderkooy, Robert A. Wannamaker, Dither in digital audio, J. Audio Eng. Soc., vol.35, n°12, p.966-975, décembre 1987 dernier accès le 28/10/2009 [lire en ligne]
3. ↑ (en) Bob Katz, Mastering Audio : The Art and the Science, pages 49-50, (ISBN 978-0-24-080545-0)
4. ↑ (en) 6-Bit vs. 8-Bit....PVA/MVA vs. TN+Film Are Things Changing?, www.tfcentral.co.uk [lire en ligne]
5. ↑ ^{a, b et c} (en) Lee Daniel, Boulay Paul, Morra Mike, Digital halftoning, www.efg2.com, dernier accès le 10/09/2007 [lire en ligne]
6. ↑ (en) Aristófanes Correia Silva, Lucena Paula Salgado, Figuerola Wilfredo Blanco, Average Dithering, Visgraf Lab, Image Based Artistic Dithering, 13/12/2000 consulté le 10/09/2007 [lire en ligne]
7. ↑ (en) scolorq : A Spatial Color Quantization Utility, www.cs.berkeley.edu, consulté le 26/04/2010 [lire en ligne]
8. ↑ (en) Error Correction Dithering, www.imagemagick.org, consulté le 28/04/2010 [lire en ligne]
9. ↑ Voir le lien suivant montrant le code sourde d'Imagemagick, le fichier magick/quantize.c, et le manuel d'utilisation en ligne qui mentionne le nom de la méthode de tramage : (en) command-line-options, www.imagemagick.org, consulté le 28/04/2010 [lire en ligne]

Annexes

Articles connexes

Liens externes

• (en) Stephen Dawson , What is Dither ?, 21/08/2003, [lire en ligne]
• (en) Aldrich Nika, Dither Explained, 25/04/2002 [lire en ligne]

Bibliographie

• (en) Nika Aldrich, Digital audio explained : for the audio engineer, Ed. Paperback, 2004, (ISBN 1-4196-0001-X)