|
Home Zaurus Debian RioUtil Projets Imac Atari mp3 |
| TNS: Binarisation Rééchantillonnage Java: Applets Ftp Divers: Calculatrice Killer Disk Usage | |
|
|
|
|
|
|
Binarisation d'images par diffusion d'erreurTraitement Numérique du Signal |
|
| Christophe Boyanique Emmanuel Pinard |
Mars 1999 |
L'utilisation courante d'applications utilisant des images nécessite la possibilité de pouvoir modifier le codage couleur des images: par exemple requantifier une image couleur en noir et blanc afin de l'imprimer sur une imprimante monochrome.
L'utilisation de différents algorithmes plus ou moins
évolués permet de minimiser la perte d'information
lors de la réduction du nombre de couleurs d'une image.
La requantification d'une image consiste à modifier
le nombre de bits de codage d'une couleur (c'est à dire
le nombre de valeurs possibles d'un pixel ou d'une composante
de pixel). Dans la majeure partie des cas, une diminution du
nombre de bits de codage de l'image entrainera une perte
d'information plus ou moins importante selon l'algorithme
utilisé.
La binarisition est l'algorithme le plus simple de
requantification. Chaque pixel de l'image est transformé
en un pixel noir ou blanc suivant sa valeur de départ.
Ainsi si la valeur d'un pixel est supérieure à
127 on lui associera la nouvelle valeur 255 (blanc), dans le
cas contraire on lui associera 0 (noir). Cette technique est
aussi appelée technique du seuil.
Dans le cas général de la requantification, on divise
la plage de valeurs de chaque pixel (de 0 à 255) en un nombre fini
de plage (fixé par le nombre de bits de codage).Chaque pixel est
ensuite classé dans une des plages suivant sa valeur en
utilisant la même technique.
Dans le cas d'image comportant plusieurs composantes (rouge, vert et
bleu), on traite chaque composante indépendamment des autres.
Dans les algorithmes précédents la perte
d'information est très importante en général. Il
est donc naturel de chercher un algorithme permettant de compenser
la perte d'information lorsque l'on quantifie la valeur d'un pixel.
L'algorithme le plus courant utilise la diffusion d'erreur:
lors de la quantification d'un pixel, on répartit sur les pixels voisins
non traités l'erreur algébrique introduite (nouvelle valeur
du pixel - ancienne valeur du pixel).
L'algorithme de Floyd-Steinberg (1975) répartit l'erreur sur les
quatres pixels les plus proches suivant une matrice:
Principe de la requantification
la binarisation
la requantification
diffusion d'erreur: algorithme de Floyd-Steinberg
| x | 7/16 | |
| 3/16 | 5/16 | 1/16 |
Il existe plein d'autres algorithmes basés sur la diffusion d'erreurs. Il suffit en effet de changer la matrice de répartition des erreurs pour obtenir un résultat différent.
On trouve entre autre les algorithmes suivants:
Algorithme de Stucki:
| x | 8/42 | 4/42 | ||
| 2/42 | 4/42 | 8/42 | 4/42 | 2/42 |
| 1/42 | 2/42 | 4/42 | 2/42 | 1/42 |
| x | 8/32 | 4/32 | ||
| 2/32 | 4/32 | 8/32 | 4/32 | 2/32 |
| x | 5/32 | 3/32 | ||
| 2/32 | 4/32 | 5/32 | 4/32 | 2/32 |
| 2/32 | 3/32 | 2/32 |
Les différents algorithmes de requantification ont été programmés en langage C ANSI. Ces programmes ne font que les conversions, il faudra donc utiliser un utilitaire externe pour visualiser les images. Les sources de ces programmes sont largement commentés.
Tous les programmes utilisent des fichiers au format PGM ASCII (PBM en 1bit, PGM en 256 niveaux de gris et PPM en 8 ou 24 bits).
Ce programme convertit un fichier 24 bits (donc 8 bits par composante) en un ficher 8 bits (3bits pour les composantes rouge et vert, 2 bits pour la composante bleu) et calcule le rapport signal/bruit.
La diffusion d'erreur est implémentée en utilisant un buffer de deux lignes sur lesquelles on répartit l'erreur de la ligne courante et de la ligne suivante.
Pour utiliser la binarisation brute:
./ppm24to8 -b input.ppm output.ppm
Pour utiliser la diffusion d'erreur:
./ppm24to8 -f input.ppm output.ppm
Le programme peut être appelé avec -F et -B au lieu de -f et -b pour créer des images sans header utilisables directement sans Scilab.
Ce programme convertit un fichier 256 niveaux de gris (PGM) en un fichier monochrome (PBM) et calcule le rapport signal/bruit.
La diffusion d'erreur est implémentée en utilisant un buffer de deux lignes sur lesquelles on répartit l'erreur de la ligne courante et de la ligne suivante.
Pour utiliser la binarisation brute:
./pgm2pbm -b input.pgm output.pbm
Pour utiliser la diffusion d'erreur:
./pgm2pbm -f input.pgm output.pbm
Le programme peut être appelé avec -F et -B au lieu de -f et -b pour créer des images sans header utilisables directement sans Scilab.
Ce programme permet de calculer le rapport signal/bruit de deux
images: fichier PGM (256 niveaux de gris) et
fichier PBM (monochrome) en entrée:
./sb input.pgm output.pbm
Application à différents types d'images:
Résultats d'exécution des programmes
On constate que le rapport signal/bruit suggère la qualité d'un algorithme: celui-ci est d'autant plus bas que l'image est meilleure.
L'algorithme de binarisation brute a tendance à faire disparaitre des morceaux d'images. L'algorithme de diffusion d'erreur donne une image plus complète mais fait apparaitre des motifs non présents dans l'image initiale.
L'image du dégradé 1 montre bien la perte d'information et les seuils lors de la binarisation brute. L'algorithme de diffusion d'erreur laisse apparaitre un léger phénomène de serpentins.
L'image du dégradé 2 montre encore mieux la perte d'information lors de la binarisation brute en monochrome. On constate aussi sur l'image issue de la diffusion d'erreur en monochrome l'apparition de points non présents sur l'image initiale dûs à la diffusion de l'erreur des points clairs sur les points sombres.
L'image du dégradé 3 laisse bien apparaitre le phénomène des serpentins.
On constate que l'effet des serpentins est peu visible sur une image de type photographie. Par contre, on ressent bien sur l'image issue de la diffusion d'erreur en couleur le déséquilibre entre les compostantes rouge/vert et bleu: les paliers étant différents il apparait des points tendant vers le bleu.
L'image de synthèse 1 permet de visualiser le phénomène des points bleux sur l'image issue de la diffusion d'erreur. Elle met bien en évidence aussi la différence de résultat entre les deux algorithmes.
L'image de synthèse 2 montre très bien les limites de la binarisation brute: l'image étant très claire, l'image binarisée se retrouve presque blanche. Il est possible d'atténuer ce problème en changeant le seuil (par exemple le mettre vers 100 au lieu de 127); mais cette manipulation est suggestive.
Ce type d'image uniforme montre bien le phénomène
d'apparition de points non présents dans l'image initiale lorsque
l'on a des brusques changements de couleurs (de bleu à blanc par
exemple). En monochrome on constate aussi l'apparition des serpentins
dûe à la diffusion d'erreur.
L'étude de ces deux algorithmes montre bien que la
manipulation d'images pose des problèmes délicats: si
on utilise la binarisation, la perte d'information est trop importante
dans la plupart des cas; si on utilise un algorithme de diffusion
d'erreur, on risque de diffuser l'erreur d'une zone d'image sur une
autre zone totalement différente (comme des points blancs sur
une surface noire par exemple).
On constate en plus que la quantification en 8 bits implique des
valeurs de codage différentes pour les composantes ce qui peut
entrainer des phénomènes de distorsion de couleur.
L'utilisation de la diffusion d'erreur est donc délicate
ce qui explique le nombre de matrices différentes: on peut
restreindre l'erreur aux points immédiatement voisins
(Floyd-Steinberg) ou la répartir sur un ensemble plus
élevé de points (Stucki).
Dans la plupart des cas on ne peut prévoir à l'avance
l'algorithme à utiliser sans une analyse de l'image.
Conclusion