Les Bases du Traitement d'Image

Le « Traitement » proprement dit, appelé également « Opérateur » comporte deux parties :

• le balayage des données : les pixels sont examinés les uns après les autres, selon un certain ordre. Pour plus de simplicité, mais également d'efficacité, nous choisissons le balayage vidéo(7) ;
• le traitement du pixel courant, c'est-à-dire de la donnée.

Pour un opérateur simple, le traitement du pixel courant ne nécessite que la connaissance du pixel courant lui-même. Ainsi, le balayage vidéo simple suffit. Celui-ci consiste à parcourir l'image, pixel par pixel selon le balayage vidéo précédemment décrit, c'est-à-dire dans l'ordre où sont stockés les pixels de l'image. Nous verrons dans une série d'articles suivante, que ce balayage des données peut être réalisé selon une implantation temporellement optimisée, c'est-à-dire plus rapide.

Pour une image de résolution nlig lignes x ncol colonnes, le balayage s'effectue ligne à ligne de y = 0 à y = nlig - 1, et pour chaque colonne de x = 0 à x = ncol - 1.

L'algorithme du balayage vidéo simple de l'image est le suivant, il nécessite deux boucles POUR (8) imbriquées :

* Pour y = 0 à y = nlig - 1
* Pour x = 0 à x = ncol - 1
   ° I(x,y) = a     /* Exemple d'Ecriture du pixel */
   ° a = I(x,y)     /* Exemple de Lecture du pixel */

Remarquons l'indentation (i.e. le retrait des instructions) proposée pour le balayage vidéo. En algorithmie classique, la boucle POUR interne portant sur la variable x, serait indentée (donc en retrait), par rapport à la boucle POUR externe portant sur la variable y. Ici, nous considérons que la structure algorithmique n'est pas la boucle POUR, mais le balayage vidéo composé des deux boucles POUR, d'où la non-indentation de la boucle POUR interne.

Lors du traitement du pixel courant, l'opérateur va alors devoir parcourir les pixels de son voisinage. Mais il falloir faire attention avec les pixels appartenant aux premières et dernières lignes et colonnes de l'image. En effet, pour ces pixels, le voisinage n'est a priori pas dans l'image.

Le voisinage 3 x 3 centré s'étend sur trois lignes : la ligne précédente, la ligne courante (celle du pixel courant) et la ligne suivante. Ainsi un pixel de la première ligne aura la première ligne de son voisinage en dehors de l'image, avant le premier pixel (cf. figure n° 7). Il en sera de même pour un pixel de la dernière ligne de l'image, dont la dernière ligne de son voisinage sera également en dehors de l'image, mais après le dernier pixel. Dans ces deux cas, la tentative d'accès à un pixel en dehors de l'image, c'est-à-dire hors de la mémoire dynamiquement allouée aura l'effet catastrophique de planter le programme.

Pour les pixels de la première et de la dernière colonne, le problème est légèrement différent. En effet, compte tenu du rebouclage « torique » de l'image, induit par son stockage mono dimensionnel, ligne à ligne en mémoire :

• le voisin de la colonne précédente d'un pixel de la première colonne se retrouve en dernière colonne de la ligne précédente ;
• le voisin de la colonne suivante d'un pixel de la dernière colonne se retrouve en première colonne de la ligne suivante.

Il n'y a donc plus d'accès hors de l'image, mais le voisinage n'est pas correct.

Ainsi, l'opérateur n'effectuera pas le traitement des pixels

des premières et dernières lignes et colonnes.

L'image de résolution ncol colonnes x nlig lignes sera donc balayée :

• en Y : de 1 à nlig - 2 ;
• en X : de 1 à ncol - 2.

Pour faciliter l'examen du voisinage 3 x 3 du pixel courant, un système d'axes (O,i,j), relatif à ce voisinage va lui être attaché (cf. figure n° 8), (i,j) Є [0,2]². Le point courant a pour coordonnées réelles (x,y) dans l'image et relatives (1,1) dans le voisinage 3 x 3 centré. Le point voisin a pour coordonnées réelles (x_v,y_v) dans l'image et relatives (i,j) Є [0,2]² dans le voisinage. Les relations entre (x_v,y_v), (x,y) et (i,j) sont :

° x_v = x + i - 1

Vérifions ces formules. Pour le point courant :

° i = 1,    soit      xv = x  
° j = 1,               yv = y

et pour le point voisin en haut et à gauche, origine du voisinage :

° i = 0,     soit     xv = x - 1  
° j = 0,         yv = y - 1

L'algorithme du balayage vidéo de l'image, avec examen du voisinage 3 x 3 centré, comporte donc quatre boucles POUR imbriquées :

• deux réalisant le balayage vidéo de l'image, sauf les bords :

  • y allant de 1 à nlig - 2,
  • x allant de 1 à ncol - 2 ;

• deux réalisant le balayage vidéo du voisinage :

  • j allant de 0 à 2,
  • i allant de 0 à 2.

L'algorithme est le suivant(11) :

* Pour y = 1 à y = nlig - 2
* Pour x = 1 à x = ncol - 2
   °  ...
   ° Pour j = 0 à j = 2
   ° Pour i = 0 à i = 2
      > xv = x + i - 1
      > yv = y + j - 1
      > I(xv,yv) = a     /* Exemple d'écriture du pixel voisin */
      > a = I(xv,yv)     /* Exemple de lecture du pixel voisin */

Certains algorithmes utilisent la notion de Présent, Passé et Futur du voisinage 3 x 3 centré (cf. figure n° 9). Cette notion est relative au balayage vidéo de l'image. Ainsi, lors du traitement du pixel courant :

• les trois pixels de la ligne précédente du voisinage, ainsi que le pixel de gauche ont déjà été traités : ils constituent le voisinage Passé ;
• les trois pixels de la ligne suivante du voisinage, ainsi que le pixel de droite n'ont pas été traités : ils constituent le voisinage Futur ;
• le pixel courant est en cours de traitement : c'est le Présent.

Le code source ci-dessous est l'implantation en Langage C, du balayage vidéo simple, en imagerie N&B, dans l'environnement logiciel de traitement d'image, conçu en 1992 pour les besoins en enseignement évoqués ci-dessus, repris pour le projet de recherche CLEOPATRE, puis mis à jour et traduit en anglais pour le projet Européen EDUMEC, dont cette série d'articles reprend les travaux.

Notons que le balayage vidéo est implanté à l'aide de deux boucles for, la boucle externe portant sur les lignes, et interne sur les colonnes. La boucle interne étant la seule instruction de la boucle externe, elle n'est pas incluse dans un bloc d'instructions matérialisé par des accolades : {…}.

L'indentation des codes sources ci-dessous reproduit l'indentation des algorithmes correspondants. La structure algorithmique étant le balayage vidéo de l'image ou du voisinage du pixel, la boucle for interne, sur la variable POINT_X(point) n'est pas indentée par rapport à la boucle for externe sur la variable POINT_Y(point).

for(POINT_Y(point) = 0; POINT_Y(point) < NLIG(image); POINT_Y(point)++)
for(POINT_X(point) = 0; POINT_X(point) < NCOL(image); POINT_X(point)++)
{
    ...        
    ... = PIXEL(image, point); // Lecture du Pixel : image source
    ...
    PIXEL(imres, point) = ... ;    // Ecriture du Pixel : image  resultat
}

Attention à une difficulté portant sur la condition de rebouclage. La ligne suivante de l'algorithme, correspondant à la boucle externe sur les lignes :

* Pour y = 0 à y = nlig - 1

s'implante de la manière suivante, et il en est de même pour la boucle interne sur les colonnes.

for(POINT_Y(point) = 0; POINT_Y(point) < NLIG(image); POINT_Y(point)++)

On valide bien que la condition : POINT_Y(point) < NLIG(image); permet à la variable POINT_Y(point) d'aller jusqu'à NLIG(image) - 1.

Le code source ci-dessous est l'implantation en Langage C, du balayage vidéo avec examen du voisinage 3 x 3 centré, en imagerie N&B, dans l'environnement logiciel EdEnviTI. Notons qu'il est implanté à l'aide de quatre boucles for.

Les deux boucles externes portant sur les variables POINT_Y(point) et POINT_X(point) constituent le balayage vidéo de l'image, sauf les bords. Les deux boucles internes portant sur les variables j et i constituent le balayage vidéo du voisinage 3 x 3 centré. La boucle de variable j porte sur les lignes, celle de variable i sur les colonnes.

Les coordonnées du point voisin pointv sont calculées à partir des coordonnées du point courant point et des coordonnées relatives (i,j) du point dans le voisinage.

for(POINT_Y(point) = 1; POINT_Y(point) < NLIG(image) - 1; 
           POINT_Y(point)++)
for(POINT_X(point) = 1; POINT_X(point) < NCOL(image) - 1; 
           POINT_X(point)++)
{
    ...
/* --- Balayage Video du voisinage 3x3 --- */
    for(j = 0; j < 3; j++)
    for(i = 0; i < 3; i++)
    {
      /* calcul des coordonnees absolues du point voisin */
      POINT_X(pointv) = POINT_X(point) + i - 1;
      POINT_Y(pointv) = POINT_Y(point) + j - 1;    
      ...        
      ... = PIXEL(image, pointv); // Lecture du Pixel Voisin : image source
    } /* --- fin du balayage du voisinage --- */
    ...
    PIXEL(imres, point) = ... ;// Ecriture du Pixel Courant : image resultat
}

Le code source ci-dessous est l'implantation en Langage C, du balayage vidéo simple, en imagerie couleur RVB, dans l'environnement logiciel EdEnviTI. Notons que le parcours du pixel courant est identique au balayage en imagerie N&B. Seule différence : l'accès aux composantes rouge, verte et bleue du pixel courant :

for(POINT_Y(point) = 0; POINT_Y(point) < NLIG(image); POINT_Y(point)++)
for(POINT_X(point) = 0; POINT_X(point) < NCOL(image); POINT_X(point)++)
{
    ...        
    ... = PIXEL_R(image, point);     // Lecture du Pixel Rouge: image source
    ... = PIXEL_V(image, point);     // Lecture du Pixel Vert: image source
    ... = PIXEL_B(image, point);     // Lecture du Pixel Bleu: image source
    PIXEL_R(imres, point) = ... ;    // Ecriture du Pixel Rouge: image resultat
    PIXEL_V(imres, point) = ... ;    // Ecriture du Pixel Vert: image resultat
    PIXEL_B(imres, point) = ... ;    // Ecriture du Pixel Bleu: image resultat
}

Le code source ci-dessous est l'implantation en Langage C, du balayage vidéo avec examen du voisinage 3 x3 centré, en imagerie couleur RVB, dans l'environnement logiciel EdEnviTI. Compte tenu de tout ce qui vient d'être vu, sa compréhension ne devrait pas poser de problème :

for(POINT_Y(point) = 1; POINT_Y(point) < NLIG(image) - 1; 
           POINT_Y(point)++)
for(POINT_X(point) = 1; POINT_X(point) < NCOL(image) - 1; 
           POINT_X(point)++)
{
    ...
/* --- Balayage Video du voisinage 3x3 --- */
    for(j = 0; j < 3; j++)
    for(i = 0; i < 3; i++)
    {
      /* calcul des coordonnees absolues du point voisin */
      POINT_X(pointv) = POINT_X(point) + i - 1;
      POINT_Y(pointv) = POINT_Y(point) + j - 1;    
      ...        
      ... = PIXEL_R(image, pointv); // Lecture du Pixel Rouge: image source
      ... = PIXEL_V(image, pointv); // Lecture du Pixel Vert: image source
      ... = PIXEL_B(image, pointv); // Lecture du Pixel Bleu: image source
    } /* --- fin du balayage du voisinage --- */
    ...
    PIXEL_R(imres, point) = ... ;    // Ecriture du Pixel Rouge: image resultat
    PIXEL_V(imres, point) = ... ;    // Ecriture du Pixel Vert: image resultat
    PIXEL_B(imres, point) = ... ;    // Ecriture du Pixel Bleu: image resultat
}

Coder un opérateur revient à reprendre l'un des quatre exemples précédents et à l'adapter.

L'Histogramme est l'un des rares outils dont nous disposons pour interpréter le contenu photométrique (i.e. la répartition des niveaux de gris des pixels) de l'image. C'est un outil d'interprétation global, car même un histogramme local (i.e. dans le voisinage d'un point) doit comporter suffisamment de pixels. Son principal inconvénient est de ne pas tenir compte de la répartition spatiale des pixels, ce que l'on a généralement besoin pour une analyse plus fine, telle que pour l'analyse de texture(13). Mais nous n'aborderons pas cette notion dans cet ouvrage.

L'histogramme est un tableau mono dimensionnel de 256 valeurs, H(n) pour n є [0, 255], dont chacune est le nombre de fois où le niveau de gris n apparaît dans l'image. Il suffit donc d'effectuer un balayage vidéo de l'image, et de compter chaque valeur des pixels.

L'algorithme est le suivant :

* Histo[256] : tableau de 256 valeurs, initialisées à 0
    * Pour y = 0 à y = Nlig - 1
    * Pour x = 0 à x = Ncol - 1
            ° Histo[I(x,y)]++

Qu'apprenons-nous en regardant l'histogramme de l'image de Lenna (figure n° 11 : image (a), histogramme (b)). En regardant la partie gauche de l'histogramme : n proche de 0, il n'y a pas ou peu de pixels noirs (0 à 10 par exemple) dans cette image. De la même manière en regardant à l'autre extrémité n є [245,255], il n'y a pas ou peu de pixels blancs. En revanche, le reste de la dynamique est bien réparti. L'image est agréable à l'œil de par sa photométrie, en plus de son contenu.

Pour cette même image, donc pour un même contenu, comprimons la dynamique d'un facteur 2, en divisant l'intensité de chaque pixel de l'image par ce facteur. Nous obtenons une image sombre et faiblement contrastée (figure n° 11 : image (c), histogramme (d)), nettement moins agréable à l'œil. Ajoutons maintenant 128 à la dynamique, en additionnant cette valeur à l'intensité de chacun des pixels de l'image. Nous obtenons une image claire, mais toujours faiblement contrastée, et également nettement moins agréable à l'œil (figure n° 11 : image (e), histogramme (f)).

Nous pouvons conclure très simplement que la qualité visuelle d'une image est intimement liée à l'étendue de sa dynamique, ou à la répartition des niveaux de gris de ses pixels. Une image dont la dynamique est faible est peu contrastée et pas très agréable à l'œil. Pour la rendre plus agréable, il est possible de lui appliquer un traitement dit de Rehaussement des Contrastes.

Nous verrons lors du quatrième article de cette série, intitulé « Première Chaîne Complète de Segmentation » une autre utilisation de l'histogramme, pour déterminer les valeurs de seuil dans une procédure de seuillage.

La réalisation de l'histogramme est obtenue grâce à la commande EdHistogramme qui nécessite le code des parties :

• interface utilisateur, contenu dans le fichier EdHistogramme.c ;
• opérateur, contenu dans le fichier EdLibHistogramme.c.

Les modifications de la dynamique des images ont été réalisées par les commandes contenues dans les fichiers EdDivideDynamic.c et EdTranslateDynamic.c et les traitements dans EdLibPointOperation.c.

Ces opérateurs, comme tous ceux présentés dans la série d'articles sont programmés dans l'Environnement logiciel de Traitement d'Image EdEnviTI, et font partie de la bibliothèque EdVision, disponible sur le site web « Developpez.com ». Le détail des algorithmes et de l'implantation des opérateurs font l'objet des parties II (Algorithme) et III (Implantation) de l'ouvrage : « Les Bases du Traitement d'Image et de la Vision Industrielle et Robotique » disponible sur Lulu.com.

Pour trouver la plage ou l'étendue de la dynamique des pixels de l'image, une première idée consiste à calculer les valeurs minimale et maximale de l'intensité.

La Plage Utile s'étend de :

Min {I(x,y) / x є [0, ncol - 1], y є[0, nlig - 1]}

à Max {I(x,y) / x є [0, ncol - 1], y є [0, nlig - 1]}

Malheureusement, dans la plupart des images, il y aura toujours un pixel noir à quasiment 0 et un pixel blanc à 255, et l'étendue de la plage trouvée sera 0 - 255. La conclusion sera « Dynamique Correcte », même si en dehors de ces quelques points parasites le reste des valeurs des intensités des pixels reste très concentré, donnant une image sans contraste !

Ainsi, l'idée de la Plage Utile consiste à négliger 2*p pour cent du nombre de pixels : p pour cent foncés, et p pour cent clairs. La Plage utile sera comptabilisée à partir de 100 - 2 x p pour cent des intensités des pixels de l'image (cf. figure n° 12(a)). Elle est déterminée par la valeur des deux bornes n₁ et n₂, respectivement borne inférieure et supérieure.

Le rehaussement affine revient à effectuer en chaque pixel la modification de la valeur de sa luminance (ou intensité) par la fonction de transfert affine de la figure n° 12 (b)) :

          I'(x,y) = 0                     si  I(x,y) < n1
    I'(x,y) = 255 * (I(x,y) - n1) / (n2 - n1)    si n1 ≤ I(x,y) ≤ n2  
    I'(x,y) = 255                     si  I(x,y) > n2

Pour optimiser le temps de calcul, il faut éviter de calculer en chaque pixel la fonction de transfert ci-dessus nécessitant une multiplication et une division. Pour ce faire, une Table de Transcodage, c'est-à-dire un tableau mono dimensionnel de correspondance entre le niveau n de l'image originale I(x,y) et le niveau n' de l'image aux contrastes rehaussés I'(x,y) est calculé, soit :

Pour tout n Є [0,255], n' = Tab[n]

Ainsi le calcul de la table Tab[n] est effectué pour tout n Є [0,255] une seule fois en début. L'opération de rehaussement affine des contrastes réalisée en chaque pixel P(x,y) consiste à établir la correspondance soit : I'(x,y) = Tab[I(x,y)]

Le rehaussement affine des contrastes est obtenu grâce à la commande EdContrastEnhacement. Le code source de l'interface est contenu dans le fichier EdContrastEnhacement.c, et celui de l'opérateur dans le fichier EdLibPointOperation.c.

Les résultats de l'opérateur de Rehaussement des Contrastes sont présentés sur l'image « Lenna sombre » figure n° 13 (b). Comme 5 % ou 10 % des pixels sombres et clairs vont être négligés, les images résultantes du rehaussement des contrastes, respectivement figures n° 13 (c) et (d) vont être plus contrastées que l'image originale (a) qui ne comportait pas ou très peu de pixels noirs ou blancs.

Le rehaussement des contrastes n'apporte aucune information supplémentaire à l'image originale peu contrastée. Il présente seulement l'information d'une manière mieux adaptée à la visualisation d'un opérateur(14) . Un tel traitement n'a aucune utilité pour une procédure « automatique » de segmentation, où ce sont les paramètres de contrôle qui doivent s'adapter.

Les images de désert, notamment d'habitations en sable, sont très peu contrastées. Une autre méthode d'améliorer leur visualisation est de renforcer les contours peu marqués en ajoutant à l'image des hautes fréquences. Celles-ci sont obtenues par une détection de la norme du gradient (cf. le cinquième article de la série, intitulé « Segmentation en Contours »). Plusieurs combinaisons d'images renforcées par des hautes fréquences sont présentées au pilote de chasse, qui choisit celle qui lui permet d'accomplir au mieux sa mission.

La quantification sur n bit (n Є [0,8]) consiste à utiliser n bits pour coder la valeur de la luminance ou de l'intensité du pixel. Pour visualiser l'image quantifiée de manière classique, le codage s'effectue sur les n bits de poids fort d'un octet non signé, les (8 - n) bits de poids faible non utilisés étant mis à zéro.

Codons l'image de Lenna, initialement sur 8 bits, respectivement sur 7, 6, 5, 4, et 3 bits. La figure n° 15 présente les images quantifiées obtenues, ainsi qu'à titre de vérification l'histogramme correspondant.

Un codage sur 7 bits consiste à n'utiliser qu'un niveau de gris sur 2, - sur 6 bits : 1 sur 4, - sur 5 bits : 1 sur 8, - sur 4 bits : 1 sur 16 et enfin - sur 3 bits : 1 sur 32. Cette propriété se traduit sur l'histogramme par des raies (niveaux de gris utilisés) de plus en plus espacées.

Jusqu'à un codage sur 5 bits, notre œil ne voit pas la différence entre le codage sur n bits et l'image originale sur 8. Pour n = 4, la différence devient visible, notamment au niveau des dégradés des niveaux de gris sur le front et sur l'épaule. Pour n = 3 cette différence devient « gênante » à l'œil.

En conclusion : notre œil ne voit pas 256 niveaux de gris. Les bits de poids faible écrasés pourraient être utilisés à véhiculer une autre information, tel qu'un tatouage (trop) simple. Dans le cadre de la Robotique Mobile téléopérée, un codage sur 4 bits réduit d'un facteur 2 le nombre de données à transmettre, d'une manière simple à mettre en œuvre, sans pour autant gêner le téléopérateur.

La quantification est obtenue grâce à la commande EdQuantization. Le code source de l'interface est contenu dans le fichier EdQuantization.c, et celui de l'opérateur dans le fichier EdLibPointOperation.c.

La réduction d'un facteur red consiste à ne conserver qu'une ligne et qu'une colonne sur red, les images pouvant être de taille quelconque. La figure n° 16 présente une réduction d'un facteur 3. Ainsi un carré de 3 x 3 pixels va être remplacé par un seul pixel.

Nous proposons deux algorithmes :

• par sous-échantillonnage ;
• par moyenne locale de la zone.

La réduction par Sous-Échantillonnage est l'algorithme le plus simple de réduction. Elle consiste à ne garder la valeur de l'intensité que d'un seul pixel de l'image originale pour la zone correspondante, d'extension red x red pixels. Le plus simple est de ne garder que les pixels de l'image originale dont les numéros de lignes et de colonnes sont multiples entiers de red, c'est-à-dire le pixel en haut et à gauche de la zone concernée. Prendre un autre pixel, tel que le pixel central, ne change pas fondamentalement le résultat obtenu.

La réduction par Moyenne locale de la zone (ou plus simplement par Moyennage) consiste à effectuer la moyenne des intensités des pixels de l'image originale pour la zone correspondante, d'extension red x red pixels.

La zone à moyenner sur l'image originale s'étend :

• de x_red x red à (x_red + 1) x red - 1 sur x ;
• de y_red x red à (y_red + 1) x red - 1 sur y.

De manière à pouvoir réduire par moyenne locale une image par un facteur entier, quelle que soit la taille de l'image, et quel que soit le facteur de réduction, il faut vérifier que cette zone ne sorte pas de l'image source.

Remarque

C'est cette seconde réduction, par moyenne locale, qui simule le mieux les résultats obtenus par un capteur moins résolu. En effet, chaque pixel du capteur moins résolu intègre sur le champ de vue de plusieurs pixels d'un capteur plus résolu.

Résultats

La figure n° 17 présente les résultats d'une réduction d'un facteur 2 puis 4, sur l'image de Lenna. Les réductions sous échantillonnées (b) et (d) apparaissent plus bruitées que les réductions moyennées (c) et (e), donc plus désagréables à l'œil.

En effet, les pixels de l'image réduite sont à la résolution de l'image initiale, et l'information intermédiaire est enlevée par sous-échantillonnage. Alors que par moyenne locale, les pixels intègrent toute l'information en la dégradant.

Les réductions par sous-échantillonnage et moyenne sont obtenues par la commande EdReduction. Le code source de l'interface est contenu dans le fichier EdReduction.c, et celui des opérateurs dans le fichier EdLibReduction.c.

L'opérateur de Zoom Numérique est l'opérateur « dual »(15)  de l'opérateur de Réduction. Il consiste à créer une image plus grande, à partir d'une image plus petite (cf. figure n° 18). De manière à ne pas déformer le contenu géométrique de l'image, nous choisirons le même facteur de zoom sur les lignes et colonnes.

Ainsi, pour deux des trois zooms présentés, l'opérateur va recréer (nZoom -1) lignes par ligne de l'image à zoomer et (nZoom - 1) colonnes par colonne, nZoom étant le facteur de zoom (cf. les pixels marqués d'une croix « x » figure n° 18). Les images peuvent être de taille quelconque.

Il ne faut pas confondre le Zoom Numérique avec le Zoom Optique. En effet, le zoom numérique ne crée pas de nouvelle information : il n'apporte pas de détail à l'image, il grossit l'existant. En changeant la focale, le zoom optique apporte lui, par contre, de nouveaux détails.

Trois zooms numériques sont présentés :

• le premier : le plus simple, par Duplication du pixel. Il suffit de dupliquer le pixel de l'image originale ou à zoomer sur une zone de nZoom colonnes x nZoom lignes (cf. figure n°19 (a)) ;

• les deux autres, par interpolation. La valeur du pixel de l'image zoomée dépend de la valeur de ses voisins. Les deux interpolations, classées par complexité croissante sont :

  • par Interpolation au plus proche voisin : seul le voisin le plus proche des 4 (cas le plus général) est pris en compte. Deux implantations sont possibles : comme pour la duplication du pixel (cf. figure n° 19 (b)), ou en version simplifiée de l'interpolation bilinéaire (cf. figure n° 19 (c)),
  • par Interpolation Bilinéaire : l'interpolation prend en compte les 4 voisins (maille carrée) dans le cas général, 2 ou 1 dans les cas particuliers. La bilinéarité signifie que le pixel de l'image zoomée est obtenu par combinaison linéaire des 4 pixels voisins selon Ox et Oy de l'image originale (cf. figure n° 19 (d)).

L'interpolation par approximation au plus proche voisin revient également à une duplication du pixel de l'image à zoomer (cf. figure n° 19). Seule l'approximation bilinéaire présente de meilleurs résultats visuels.

Pour les trois opérateurs, le principe consiste à créer l'image zoomée, c'est-à-dire à calculer la valeur de l'intensité de chacun de ses pixels en :

• calculant la position correspondante du pixel dans l'image à zoomer ;
• en utilisant ensuite la méthode d'approximation ad hoc.

Calcul de la position correspondante du pixel de l'image zoomée dans l'image à zoomer :

La figure n° 20 (a) présente le contexte. Soit le pixel P(xZoom,yZoom) de l'image zoomée xZoom et yZoom sont des coordonnées entières), et sa position P_R(x_R,y_R) dans l'image à zoomer où ses coordonnées x_R et y_R sont des nombres réels.

Soient les 4 pixels (i.e. à coordonnées entières) les plus proches, de l'image à zoomer :

P₀(x_RInit,y_RInit), P₁(x_RInit + 1,y_RInit), P₂(x_RInit,y_RInit + 1) et P₃(x_RInit+1,y_RInit+1).

Soient (a, b) Є [0,1[². Les relations entre ces divers paramètres sont :

• x_R = xZoom / nZoom // Division en nombres réels
• y_R = yZoom / nZoom // Idem
• x_RInit = xZoom / nZoom // Division en nombres entiers (= E(x_R)c'est-à-dire la partie entière)
• y_RInit = yZoom / nZoom // Idem
• a = x_R - x_RInit
• b = y_R - y_RInit

Calcul de l'intensité dans l'image zoomée Iz(xZoom,yZoom) :

Il va dépendre de l'opérateur. Pour l'opérateur par duplication du pixel : Iz(xZoom,yZoom) = I(x_RInit,y_RInit)

Pour l'opérateur par interpolation au plus proche voisin, implanté comme pour une interpolation bilinéaire (cf. figure n° 19) :

Pour l'opérateur par interpolation bilinéaire : dans le cas général, les quatre plus proches voisins sont pris en considération, ainsi que leur distance selon les axes Ox et Oy au point à créer. Leur pondération va être d'autant plus importante que le voisin est proche.

Ainsi si a (a Є [0,1[) est la distance, (1 - a) va être la pondération.

Ainsi, si a = 0 ou si b = 0, seuls deux voisins sont pris en considération pour le calcul. Si a = 0 et b = 0, le point à créer de l'image zoomée se trouve physiquement sur le point de l'image à zoomer sa pondération sera de 1.

La formule de interpolation Bilinéaire est la suivante :

La figure n° 21 présente les résultats des opérateurs de zoom d'un facteur 2 sur l'image de Lenna. La difficulté est que les images sont réduites pour être présentées, ce qui estompe ce qui va être dit.

Nous pouvons conclure sur le peu de différence entre le zoom par duplication du pixel et le zoom par interpolation au plus proche voisin. Tous deux génèrent un effet de crénelure ou d'aliasing, visible notamment sur les bords du chapeau et de l'épaule de Lenna.

Le Zoom par interpolation bilinéaire assure une meilleure qualité du rendu : l'effet précédent est estompé.

Les zooms par duplication et interpolations au plus proche voisin et bilinéaires sont obtenus par la commande EdZoom. Le code source de l'interface est contenu dans le fichier EdZoom.c, et celui des opérateurs dans le fichier EdLibZoom.c.

Combinaison réduction / zoom :

La figure n° 22 présente les diverses combinaisons d'une réduction suivie d'un zoom.

Les deux types de réduction

• par sous-échantillonnage,
• par moyenne locale,

sont associés aux deux types de zoom

• par duplication du pixel,
• par interpolation bilinéaire.

ce qui représente quatre combinaisons possibles, que l'on peut utiliser, par exemple pour comprimer (par réduction) les données images pour une transmission ou un stockage, et les restituer par zoom.

La réduction d'un facteur 2 présentée figure n° 22, a un taux de compression de 4 (soit 2x2). Le zoom présenté a également un coefficient de 2, ce qui permet de revenir à la résolution de l'image originale.

Il est ainsi possible d'évaluer la perte en termes de qualité visuelle après une procédure de compression/décompression, par rapport à l'image originale.

La conclusion est évidente : la meilleure des réductions (par moyenne locale) associée au meilleur des zooms (par interpolation bilinéaire) donne de loin la meilleure restitution (image en bas à droite). Même pour la meilleure restitution, nous constatons la perte des détails, en comparant le résultat de la réduction suivie d'un zoom, à l'image originale. En effet, les détails perdus lors de la réduction ne sont pas recréés par le zoom numérique.

Combinée à la compression par quantification précédemment présentée, on obtient un taux de compression de 8, avec des algorithmes très simples et très rapides sur le plan de l'exécution.

Pour un lissage linéaire, comme pour tout autre lissage, une zone homogène est exempte de bruit. Elle doit par conséquent rester inchangée à l'issue du lissage. Cette condition a des répercussions sur les coefficients du masque de convolution, dont la somme des coefficients doit être égale à 1, soit :

Principe 

Le filtre moyen affecte au pixel courant la moyenne des intensités de son voisinage(18)

Ceci revient à effectuer une convolution, soit neuf multiplications et huit additions par pixel (sauf les bords), avec le masque ci-dessous, comportant une normalisation par un facteur valant 9.

Pourquoi « revient » ? Parce qu'une telle implantation serait ridicule, car d'une part une multiplication prend du temps, et d'autre part une multiplication par 1 est inutile. Le masque du lisseur moyen est :

Mais le calcul, effectué en chaque pixel est le suivant :

Cette formule est celle qui minimise le nombre de divisions. Elle revient bien à la convolution avec le masque précédemment présenté. On note également que la somme des coefficients du masque, normalisation incluse, est égale à l'unité, condition nécessaire d'un lisseur linéaire.

Le lissage moyen est obtenu par la commande EdMeanFiltering. Le code source de l'interface est contenu dans le fichier EdMeanFiltering.c, et celui de l'opérateur dans le fichier EdLibMeanFiltering.c.

Principe

Le filtre gaussien affecte au pixel courant la gaussienne des intensités de son voisinage.

Une gaussienne est une courbe en cloche (cf. figure n° 27) d'équations en 1D et 2D :

Le paramètre s est proportionnel à la largeur de la courbe à mi-hauteur L_H/2, plus exactement :

Une gaussienne peut être approximée en 1D par le masque [1 2 1]. Voici un masque approximant cette gaussienne en 2D :

La différence avec le lissage moyen est la pondération des pixels du voisinage 3 x 3 centré. En effet, pour le lissage moyen, la pondération de tous les pixels du voisinage est identique. Pour le lissage gaussien, le pixel central, c'est-à-dire là où l'on effectue le calcul, a une pondération supérieure. Le lisseur gaussien va de ce fait moins lisser que le lisseur moyen.

Cette différence suggère également une possibilité d'implantation, qui consiste à ajouter la valeur du pixel central du voisinage (ou courant) au calcul de la moyenne des intensités du voisinage, et ensuite de normaliser par 10 au lieu de 9, ce qui respecte la contrainte d'un lisseur linéaire.

La formule employée est alors la suivante :

Le lissage gaussien est obtenu par la commande EdGaussianFiltering. Le code source de l'interface est contenu dans le fichier EdGaussianFiltering.c, et celui de l'opérateur dans le fichier EdLibGaussianFiltering.c.

Principe 

Le filtre médian affecte au pixel courant la médiane des intensités de son voisinage.

La valeur médiane d'un ensemble de valeurs est la valeur pour laquelle, il y autant de valeurs plus grandes que de valeurs plus petites. Pour cela, l'algorithme (cf. figure n° 28) consiste à ranger les valeurs du voisinage dans un tableau mono dimensionnel, car plus facile à trier, et à le trier. Dans le cas du voisinage 3 x 3 le tableau Tab comportera neuf valeurs de Tab[0] à Tab[8](19). La valeur médiane, une fois le tableau trié est la cinquième, soit Tab[4], quel que soit l'ordre du tri : croissant ou décroissant.

La méthode de tri importe peu. Il existe certes des méthodes dites de Tri Rapide ou Quick Sort qui sont bien plus rapides lorsque le nombre de valeurs à trier est très important. Ici, pour neuf valeurs, nous suggérons la méthode simple du Tri à Bulle qui est la matérialisation du théorème mathématique :

«  Toute Permutation(20) peut être réalisée sous forme de Transpositions  (21) »

Le principe du Tri à Bulle consiste à parcourir le tableau, en considérant à chaque étape l'élément courant indicé k et suivant indicé (k+1). Les éléments sont transposés s'ils ne sont pas dans le bon ordre : par exemple si Tab[k] > Tab[k+1]. Un nouveau parcours du tableau est entrepris, si au moins une permutation a été réalisée lors du parcours précédent. Le tri s'arrête ainsi naturellement à la suite d'un parcours n'ayant donné lieu à aucune transposition.

Le filtre médian fait partie des filtres d'ordre comme les filtres Maximum et Minimum dont le principe est d'affecter au pixel courant les valeurs maximale et minimale des intensités du voisinage.

Le lissage médian est obtenu par la commande EdMedianFiltering. Le code source de l'interface est contenu dans le fichier EdMedianFiltering.c, et celui de l'opérateur dans le fichier EdLibMedianFiltering.c.

Examinons le comportement des opérateurs lisseurs moyen et médian sur des profils 1D de la figure n° 29. La moyenne ou la médiane sont calculées au point courant du profil 1D, en tenant compte des points précédent et suivant. Pour le filtre médian 1D sur un voisinage comportant trois valeurs, dès que deux des trois valeurs sont égales, la valeur médiane prend cette valeur commune.

Le comportement du filtre moyen est le suivant :

• le bruit est réduit en intensité, mais sa localisation est élargie ;
• la transition est également élargie. C'est l'effet de flou que nous visualiserons sur les images, au niveau des contours des objets.

Le comportement du filtre médian est le suivant :

• le bruit incohérent avec le reste du voisinage est purement et simplement entièrement supprimé. L'effet est parfait !
• la transition est inchangée. Ceci nous permet d'affirmer que le filtre médian ne floute pas les images.

Nous retrouvons également sur les images du bureau (cf. figure n° 30) et de Lenna (cf. figure n° 31) les conclusions énoncées ci-dessus. Nous comparons l'effet des trois filtrages : moyen (b), gaussien (c), et médian (d).

Pour comprendre les différents effets, que nous allons lister, il faut regarder à des endroits bien précis de l'image :

• la Réduction du Bruit : regarder les images dans leur globalité ;
• le Flou : regarder les contours des fenêtres pour l'image du bureau, le bord du chapeau, et le contour de l'épaule pour l'image de Lenna ;
• la Disparition des Détails , à ne pas assimiler à l'effet de flou. Il faut regarder les plumes, et le tissu du chapeau, sur l'image de Lenna.

Le filtre moyen (b) réduit « l'intensité » de la composante de bruit dans les images, mais il « étale » le bruit sur les pixels voisins.

Le filtre moyen étale les contours : il les floute. C'est un effet indésirable pour une chaîne de traitements automatiques, dont les étapes suivantes sont une segmentation en contours ou en régions. En effet, le flou diminue l'amplitude du contour, et réduit le contraste local entre les régions, ce qui pénalise les opérateurs de segmentation en Contours, et également en Régions. En revanche, c'est l'effet recherché par le graphiste qui cherche à réaliser une image artistique, par exemple d'un visage net avec un arrière-plan flou.

Le filtre gaussien (c) a un comportement semblable au filtre Moyen, mais légèrement moins accentué. Il filtre moins le bruit, et floute moins les contours, car il accorde une pondération plus importante au pixel central.

Ainsi grâce à ces opérateurs lisseurs moyen et gaussien(22) et au flou qu'ils induisent, il est possible en post traitement de réaliser un flou de défocalisation, bien connu des photographes, qui consiste à faire la mise au point sur le sujet, en utilisant un grand diaphragme (ouverture maxi = nombre mini), donc une faible profondeur de champ. Ainsi, tout objet dans un plan autre que le sujet sera flou.

Une différence fondamentale : le flou numérique est le même dans toute l'image. Ainsi, en retouche d'images, il est possible de :

• masquer le sujet, par un détourage manuel. Le flou ne s'appliquera pas sur le sujet ;
• combiner plusieurs opérateurs avec des flous plus ou moins marqués, en fonction de la distance (dans l'image) au sujet.

Le filtre médian ne floute pas les contours. C'est flagrant sur l'image du bureau (figure n° 30), où les contours sont nets, même plus que sur l'image originale. Le filtre médian est même qualifié parfois dans certains ouvrages d'être renforçateur des contours.

En revanche l'image de Lenna traitée par le filtre médian (cf. figure n° 31) paraît floue. En fait, il ne s'agit pas d'un effet de flou au sens précédemment énoncé, c'est-à-dire un élargissement de la zone de transition.

En effet, le filtre médian enlève les petits détails qui sont incohérents avec le reste du voisinage. Il ne fait bien évidemment pas la distinction entre le bruit et les petits détails. Ainsi, la perte d'un certain nombre de petits détails des plumes du chapeau explique cette sensation visuelle.

Nous retrouvons tous les éléments précédemment mentionnés sur la figure n° 32 des profils de l'image du bureau. L'effet de lissage est bien meilleur avec le lisseur médian qu'avec les lisseurs moyen et gaussien. Pour s'en convaincre, il faut regarder par exemple la partie cerclée de l'image (a). L'intensité sur l'image filtrée est bien plus constante avec le filtre médian.

Les neuf voisinages de Nagao, extraits du voisinage 5 x 5 :

Neuf voisinages sont extraits du voisinage 5 x5 centré (cf : figure n° 33)

• quatre cardinaux : nord, sud, est, ouest ;
• quatre diagonaux : nord-est, nord-ouest, sud-est, sud-ouest ;
• central.

Le filtre de Nagao moyen (respectivement médian) affecte au pixel courant la moyenne (resp. la médiane) du voisinage ayant la plus faible variance.

Nous présentons cet algorithme pour montrer un exemple de voisinages non 3 x 3 centrés.

Algorithme 

L'algorithme du filtre de Nagao moyen (resp. médian) est présenté ci-dessous :

Effet

Comme pour le filtre lisseur médian, cf. figure n° 34 le bruit impulsionnel incohérent avec son voisinage a totalement disparu. En revanche, l'image est modifiée. En propageant la valeur moyenne ou médiane du voisinage directionnel de plus faible écart-type, le filtre lisseur de Nagao propage les intensités des régions, et diminue la largeur de la zone de transition. Il renforce ainsi les contours. Il est qualifié dans la littérature de filtre renforçateur des contours.

Retrouvons cette propriété sur les profils de la figure n° 35. Le lissage a un effet plus accentué pour les filtres de Nagao, que pour le filtre lisseur médian.

Les lissages de Nagao moyen et médian sont obtenus par la commande EdNagaoFiltering. Le code source de l'interface est contenu dans le fichier EdNagaoFiltering.c, et celui des opérateurs dans le fichier EdLibNagaoFiltering.c.

Compte tenu de la quantité de calculs à effectuer en chaque pixel (à l'exception des bords : i.e. quatre lignes et quatre colonnes ne sont pas traitées), la réalisation des filtres de Nagao n'est pas « immédiate », même pour une image de faible résolution, par exemple l'image du bureau de résolution 256 x 256.