Algorithme de remplissage par diffusion

From Wikipédia
Jump to navigation Jump to search

L'algorithme de remplissage par diffusion est un algorithme classique en infographie qui change la couleur d'un ensemble connexe de pixels de même couleur délimités par des contours. Il est fréquemment utilisé par les programmes de manipulation d'images matricielles comme Paint. Il trouve également son application dans certains jeux tels que le démineur, Puyo Puyo et Lumines afin de déterminer quels éléments du plateau de jeu sont à révéler.

Principe général[edit | edit source]

L'algorithme de remplissage par diffusion prend trois paramètres pour une image donnée : la position du pixel de départ (appelé aussi germe), la couleur ciblée (colcible) et la couleur de remplacement (colrep). L'algorithme recense tous les pixels de l'image qui sont connectés au germe par un chemin de la couleur ciblée et substitue à cette dernière la couleur de remplacement. Il y a plusieurs manières de structurer cet algorithme mais elles font toutes appel à une pile de manière implicite ou explicite pour effectuer le calcul.

Formulation récursive[edit | edit source]

La formulation récursive utilise une pile de manière implicite.

Variante 4-connexe[edit | edit source]

Si l'image est constituée de manière classique de pixels carrés ou rectangulaire, La variante 4-connexe considère les 4 voisins d'un pixel ayant en commun un bord avec ce dernier. La formulation de l'algorithme est la suivante :

Variante 4-connexe
 remplissage4(pixel, colcible, colrep) 
 début
   si couleur(pixel) = colcible 
   alors
      couleur(pixel) ← colrep
      remplissage4(pixel au nord, colcible, colrep)
      remplissage4(pixel au sud, colcible, colrep)
      remplissage4(pixel à l'est, colcible, colrep)
      remplissage4(pixel à l'ouest, colcible, colrep)
   finsi
 fin

Algorithmes à pile explicite[edit | edit source]

La formulation recursive précédente, si elle possède l'avantage d'être intuitive par sa formulation, est souvent inemployée en pratique, en particulier dans des environnements d'exécution où la pile d'appel des fonctions est fortement contrainte ou réduite. Il convient alors de créer sa propre pile dans laquelle seront stockés les pixels à explorer. L'algorithme pour la variante 4-connexe est alors le suivant :

 remplissage4(pixel, colcible, colrep)
 début
   Soit P une pile vide
   si couleur(pixel) ≠ colcible alors sortir finsi
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     couleur(n) ← colrep
     si couleur(n nord) = colcible alors Empiler n nord sur P finsi
     si couleur(n sud)  = colcible alors Empiler n sud  sur P finsi
     si couleur(n est)  = colcible alors Empiler n est  sur P finsi
     si couleur(n ouest)= colcible alors Empiler n ouest sur P finsi
   fintantque
 fin

Optimisations[edit | edit source]

En bouclant vers l'est et vers l'ouest[edit | edit source]

La plupart des implémentations utilisent une boucle se propageant à la fois vers "l'est" et vers "l'ouest" afin d'alléger la gestion de la pile. L'algorithme utilisé est alors :

 remplissage4(pixel, colcible, colrep)
 début
   Soit P une pile vide
   si couleur(pixel) ≠ colcible alors sortir de la fonction
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     si  couleur(n) = colcible
     alors 
       wn
       en
       Déplacer w vers l'ouest jusqu'à ce que couleur(w) ≠ colcible
       Déplacer e vers l'est   jusqu'à ce que couleur(e) ≠ colcible
       Pour tout pixel p entre w et e
       Faire
         couleur(p) ← colrep
         si couleur(p nord) = colcible alors Empiler p nord sur P finsi
         si couleur(p sud ) = colcible alors Empiler p sud  sur P finsi
       finpour
     finsi
   fintantque
 fin

En balayant les lignes[edit | edit source]

L'algorithme peut être accéléré en remplissant directement des lignes. Au lieu d'empiler chaque nouveau pixel potentiel, il suffit d'inspecter les lignes suivantes et précédentes qui seront coloriées lors d'une future passe. Les coordonnées des extrémités du segment à colorier sont alors empilées. Dans la plupart des cas, cette variante de l'algorithme s'avère plus rapide que la version se basant sur les pixels.

Voir aussi[edit | edit source]

Articles connexes[edit | edit source]

Liens externes[edit | edit source]