Tramage d'une image

Introduction

En développant une application de lecture de cartes géographiques scannées, j'ai rencontré des problèmes avec ma vieille imprimante jet d'encre noir et blanc. Celle-ci ne gère pas les niveaux de gris et les impressions résultantes manquaient de nuances. Après quelques recherches, j'ai trouvé la solution, le tramage ou plutôt des solutions, car il existe plusieurs méthodes de tramage. Dans la suite de cet article, je vais présenter quelques algorithmes de tramage et discuter de leurs mérites respectifs.

Principe

Problème : comment représenter une couleur particulière avec un périphérique qui ne peut pas l'afficher?

Solution : juxtaposer plusieurs pixels de couleurs différentes pour obtenir une moyenne la plus proche de la couleur désirée. Par exemple, vous voulez obtenir un gris à 50 % avec uniquement du noir et du blanc. Vous mettrez alors un pixel sur deux en noir et l'autre moitié en blanc.
On observe que pour effectuer la moyenne, nous avons recours à plusieurs pixels, ce qui tend à mélanger les contributions des différents pixels. On peut alors analyser les performances des différents algorithmes de tramage suivant différents paramètres :

• respect des couleurs ;
• respect des formes ;
• facilité de mise en œuvre et rapidité.

Aléatoire

Pour chaque pixel, on réalise un tirage aléatoire pondéré entre les différentes approximations possibles. Si on travaille avec des niveaux de gris compris en 0 (noir) et 255 (blanc) qu'on veut approximer en noir et blanc, on tire au hasard une valeur entre 0 et 255 et on la compare à l'intensité du pixel étudié. Si elle est supérieure, on met du blanc. Si elle est inférieure, on passe en noir.

  if s<random(256) then // s ancienne valeur du pixel 
    nvx:=0 
  else 
    nvx:=255;

Matriciel

On prend l'image et on la découpe en petits carrés (ou matrices) de taille prédéfinie. Ensuite, à l'intérieur de chaque carré, on applique une valeur de seuil prédéfinie différente pour chaque case du carré.

Pour des carrés de taille 2, voici les valeurs prédéfinies :

Il faut adapter les coefficients à son problème (on a des valeurs qui vont de 1 à 4 alors que les niveaux de gris vont de 0 à 255). Toujours dans notre problème de niveaux de gris les coefficients deviennent (seuil:=n*64-32) :

En pratique, pour tous les pixels de coordonnées x paire et y paire on appliquera un seuil de 32. Si la valeur du pixel est en dessous du seuil, il devient noir. Au-dessus, il devient blanc.

Quand on passe en 3x3, on a :

Et ainsi de suite. Vous ne devez pas choisir les valeurs de la matrice au petit bonheur la chance, mais prendre celles qui sont fournies dans la littérature. J'ai fourni celles pour les matrices 2x2 et 3x3. On peut trouver une formule pour calculer les coefficients d'une matrice à partir de ceux d'une matrice deux fois plus petite.Ceci permet rapidement d'atteindre des matrices assez importantes.

Floyd et Steinberg

Cette méthode est souvent utilisée par les navigateurs web pour afficher les photos en couleurs quand on ne dispose que de 256 couleurs par exemple.

C'est un algorithme séquentiel dans lequel on traite les pixels les uns après les autres toujours dans le même sens. Dans la suite nous considérerons que le balayage s'effectue de gauche à droite dans chaque ligne et que les lignes sont traitées de haut en bas.
Quand on arrive sur un pixel, on recherche la couleur la plus proche. Ensuite, on calcule l'erreur entre la couleur trouvée et celle voulue et on reporte l'erreur sur les pixels voisins suivant le schéma ci-dessous :

En gris sombre, on a les pixels déjà traités. Au centre, le pixel en cours et en blanc les pixels où on reporte l'erreur. Par exemple, le pixel au centre vaut 170 (gris clair). On l'approxime en blanc (255). L'erreur est de 170-255=-85. Le report de l'erreur au pixel suivant à droite (7/16) donne -85*7 div 16 = -37. On retranche donc 37 au pixel suivant. En procédant de même sur l'ensemble des pixels, on répartit complètement l'erreur.

Pratique

La programmation des algorithmes ci-dessus avec Kylix et Delphi ne pose aucun problème. Je me suis concentré sur le cas d'une image en niveau de gris à approximer en noir et blanc. Pour accélérer les traitements, j'ai eu recours à scanline.

Le code source K2/D6 incluant l'image utilisée pour les essais : trame.zip (88 ko).

Résultats

J'ai mis les temps de calcul pour mon Celeron 375 MHz :

Le tramage aléatoire est certes très facile à mettre en œuvre, mais donne de mauvais résultats. La répartition des points est trop irrégulière pour conserver les formes. Éventuellement, des calculs de type Monté-Carlo pourraient homogénéiser le résultat. Mais ce n'est plus la même histoire.

Le tramage matriciel 2x2 est le plus rapide, mais manque de résolution dans les niveaux de gris (5 niveaux seulement, noir et blanc inclus).

Le tramage matriciel 3x3 a un meilleur respect des nuances (10 niveaux). En contrepartie, il introduit un flou sur le bord des formes et on voit apparaître un quadrillage peu esthétique.

D'une manière générale, plus la matrice est grande, meilleur est le rendu des nuances, mais plus grand est le flou. Et ces tramages qui sont périodiques peuvent avoir des comportements étranges s'il existe déjà un tramage sous-jacent dans l'image d'origine ou introduit par le périphérique comme pour mon imprimante en mode économique. On peut se retrouver avec des moirés, des zones toutes blanches ou toutes noires. Le 3x3 est moins sensible à ce genre de problème.

Enfin, le tramage de Floyd et Steinberg donne de bons résultats pour des temps de calcul équivalents au 3x3. Les nuances sont bien respectées sans trop altérer les formes.

Donc victoire pour Floyd et Steinberg ?
Oui pour l'exemple présenté, à savoir l'affichage d'une photo à l'écran.
Par contre, à l'impression, la résolution beaucoup plus élevée gomme les défauts du tramage matriciel. Dans le cas de mon exemple initial, à savoir une carte scannée (et déjà tramée en couleur), le résultat est bien meilleur avec un tramage matriciel 3x3. J'ai juste un moiré qui apparaît sur les étendues d'eau.

En conclusion, pour choisir son tramage, il faut tenir compte de la nature des images à afficher et du périphérique visé. Pour les photos, on s'orientera vers Floyd et Steinberg alors que pour les dessins au trait on préférera un tramage matriciel. Et rien ne vaut quelques essais.

Remarques

Pour des images en couleurs, le plus simple est de traiter séparément chaque canal comme une image en niveau de gris.

Le tramage doit être la dernière étape d'un traitement avant affichage. J'ai essayé une fois de faire un tramage avant un redimensionnement, le résultat est catastrophique.

Les tramages matriciels donnent de bonnes compressions quand ils sont enregistrés en png.

Code source

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants :