Le tramage est une des méthodes qui permettent de réduire le nombre de couleurs utilisées pour la représentation d'une image. Ses applications sont encore nombreuses, même à l'époque des écrans et des cartes graphiques affichant des nombres de couleurs infinis. On pourra citer en exemple certains formats de fichiers tels que le gif très utilisé sur le web qui ont des palettes de couleurs limitées. Bien sur la principale application du tramage reste l'imprimerie où le nombre de teintes disponibles est très faible (à la limite 2 pour les impressions noir et blanc).

Le tramage utilise un phénomène de moyennage optique. A  haute fréquence, l'oeil réalise une moyenne des points d'un même voisinage. Ainsi, une succession de bandes rouges et bleues, si elles sont suffisamment rapprochées, donne une impression visuelle similaire à un plan uni violet.

Différentes méthodes de tramage existent. On pourra en particulier  trouver un exposé similaire à celui-ci sur le tramage par seuil aléatoire dans la bibliothèque d'exemple BETI. Nous allons étudier le tramage utilisé dans la plupart des browsers web qui est le tramage de Floyd et Steinberg. Il donne des résultats très satisfaisants pour une complexité réduite.
 

Principe de l'algorithme :

Le tramage est réalisé par propagation de l'erreur de quantification :
Lorsqu'on veut afficher un point, on choisit parmi la palette des couleurs disponibles celle qui est la plus proche de la couleur exacte du pixel. L'erreur induite par cette approximation est ensuite reportée sur les pixels voisins du pixel traité. En pratique, seule une partie des voisins est utilisée (cf schéma). Ceci permet de traiter l'image en une seule passe.  

L'erreur est ensuite divisée entre chaque voisin et ajoutée à leur valeur. C est cette valeur actualisée qui sera utilisée quand viendra leur tour d'être approximés. Pour tenir compte de leur position respectives, les corrections apportées à chaque voisin sont pondérées différemment.

Un algorithme réalisant le tramage de Floyd et Steinberg serait le suivant :

for i=0 to NI-1 do begin  
    for j=0 to NJ-1 do begin

        x = coul(i,j);  (lire une couleur)
        k = proche(x);  (trouver la couleur la plus proche)
        Nouvelle_couleur(i,j) = k;   (mettre a jour l'image quantifiee)

        Erreur = dist (x, k)   (Erreur de quantification)
 
        Coul(i-1,j+1) = Coul(i-1,j+1) + Erreur*3/16;  (Distribution de l'erreur)
        Coul(i,j+1) = Coul(i,j+1) + Erreur*5/16;
        Coul(i+1,j+1) = Coul(i+1,j+1) + Erreur*1/16;
        Coul(i+1,j) = Coul(i+1,j) + Erreur*7/16;

    end
end
                  

Binarisation d'une image noir et blanc :

Voici une image en noir et blanc, ou plus précisemment en noir et blanc et gris très clair, et gris clair, et... Bref, une image en niveaux de gris. Nous désirons la binariser.
          

Voici, le résultat que nous obtenons en appliquant le tramage de Floyd & Steinberg  sur une photo de top-model..

Malgré la forte contrainte imposée (seulement deux couleurs !) le résultat est très honorable. On pourra le comparer aux résultats obtenus par d'autres méthodes (differents seuillages aléatoires).
Voir les résultats sur une mire est aussi intéressant.          

On peut remarquer que le couple d'images au dessus represente une belle mire de reglage du Gamma de votre écran.
Malgré ce que l'on pourrait croire à priori, le gris de l'image de droite est plus "vrai" que celui de l'image de gauche.
En effet, la courbe de réponse d'un écran n'est pas lineaire.  Le filtre que l'on doit appliquer sur une image pour tenir compte de cette transformation s'appelle la correction du gamma. L'image de droite qui elle s'appuie sur le sommage statistique des couleurs n'a pas ce probleme. Un gris à 50% sera représenté par une succession régulière de points noirs et de points blancs. En moyennant, on obtient la "vraie" valeur du gris.

Ainsi, la valeur du gamma de l'écran est celle pour laquelle les deux images sont le plus similaires à l'oeil.
 

Quantification d'une image couleur.

Voici maintenant un problème un peu plus complexe. Quantifier une image couleur par l'algorithme de Floyd et Steinberg est moins immédiat. En effet, dans l'espace des couleurs la notions de distance n'est pas clairement définie. Comment alors considérer qu'une couleur est plus près qu'une autre et faire la différence entre deux couleurs ? Le choix de l'espace de représentation est primordial.

Pour éviter de complexifier le traitement nous allons nous placer dans l'espace des couleurs RVB qui est celui utilisé dans la plupart des systèmes informatiques. On pourrais lui préférer l'espace LAB qui
devrait donner des résultats légèrement meilleurs. Dans cet espace nous allons nous limiter à 8 couleurs, c est-à-dire aux coins du cube rvb. Si l'on prend une distance de type L1 dans cet espace, on se rend assez rapidement compte que quantifier l'image revient à quantifier chaque canal de couleur indépendamment puis de sommer les résultats.

Voici les résultats que nous obtenons :
 tout d'abord sur une mire :
           

Puis sur une photo, (de notre star préférée par exemple) :
         Ouf, notre idole est encore reconnaissable.
 

Le programme.

Voici le programme  qui nous a servi à réaliser les images ci-dessus. Les indications pour l'installer, et l'utiliser se trouvent dans le fichier README.
Il est capable de lire les images au format PGM et Targa.