Flood fill

Flood fill

Algorithme de remplissage par diffusion

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. 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.

Sommaire

Principe général

L'algorithme de remplissage par diffusion prend 3 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ère de structurer cet algorithme mais elles font toutes appel à une pile de manière implicite ou explicite pour effectuer le calcul.

Formulation récursive

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

Variante 4-connexe

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) \leftarrow 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

Variante 8-connexe

Cette variante considère les 8 cases voisines du pixel dans l'image : les cases adjacentes et diagonales. La formulation est la suivante :

Variante 8-connexe
 remplissage8(pixel, colcible, colrep) 
 début
   si couleur(pixel) = colcible 
   alors
      couleur(pixel) \leftarrow colrep
      remplissage8(pixel N,  colcible, colrep)
      remplissage8(pixel S,  colcible, colrep)
      remplissage8(pixel E,  colcible, colrep)
      remplissage8(pixel O,  colcible, colrep)
      remplissage8(pixel NE, colcible, colrep)
      remplissage8(pixel NO, colcible, colrep)
      remplissage8(pixel SE, colcible, colrep)
      remplissage8(pixel SO, colcible, colrep)
   finsi
 fin

Cette variation de l'algorithme peut franchir certains contours qui sont des barrières pour la variante 4-connexe. Aussi, il convient de choisir l'algorithme à appliquer en fonction du résultat voulu.

Algorithmes à pile explicite

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) \neq colcible alors sortir finsi
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     couleur(n) \leftarrow 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

En bouclant vers l'est et vers l'ouest

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) \neq colcible alors sortir finsi
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     si  couleur(n) = colcible
     alors 
       w \leftarrow n 
       e \leftarrow n
       Déplacer w vers l'ouest jusqu'à ce que couleur(w) \neq colcible
       Déplacer e vers l'est   jusqu'à ce que couleur(e) \neq colcible
       Pour tout pixel p entre w et e
       Faire
         couleur(p) \leftarrow 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

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 extremité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

Liens externes

Ce document provient de « Algorithme de remplissage par diffusion ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Flood fill de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Flood fill — Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi dimensional array. It is used in the bucket fill tool of paint programs to determine which parts of a bitmap to fill with color, and… …   Wikipedia

  • flood fill — užpildiklis statusas T sritis informatika apibrėžtis ↑Piešyklės įrankis, užpildantis tos pačios spalvos piešinio sritį pasirinkta spalva. Užpildiklio piktogramos pavyzdį žr. priede. priedas( ai) Grafinis formatas atitikmenys: angl. flood fill… …   Enciklopedinis kompiuterijos žodynas

  • flood fill — noun A means of filling a discrete area with colour, based on colouring every pixel that can be recursively reached from a starting point. Syn: seed fill …   Wiktionary

  • Fill — may refer to:*Fill dirt, soil added to an area. *Fill (music), a short segment of instrumental music. *In textiles, the filling yarn is the same as weft, the yarn which is shuttled back and forth across the warp to create a woven fabric. *In… …   Wikipedia

  • flood — floodable, adj. flooder, n. floodless, adj. floodlike, adj. /flud/, n. 1. a great flowing or overflowing of water, esp. over land not usually submerged. 2. any great outpouring or stream: a flood of tears. 3. the Flood, the universal deluge… …   Universalium

  • flood — [[t]flʌd[/t]] n. 1) a great flowing or overflowing of water, esp. over land not usu. submerged 2) any great outpouring or stream: a flood of tears[/ex] 3) bib the Flood, a universal deluge mentioned in various ancient religions, esp. the deluge… …   From formal English to slang

  • flood — /flʌd / (say flud) noun 1. a great flowing or overflowing of water, especially over land not usually submerged. 2. any great outpouring or stream: a flood of words; a flood of tears; a flood of light; a flood of lava. 3. the flowing in of the… …  

  • Flood — Flood, v. t. [imp. & p. p. {Flooded}; p. pr. & vb. n. {Flooding}.] 1. To overflow; to inundate; to deluge; as, the swollen river flooded the valley. [1913 Webster] 2. To cause or permit to be inundated; to fill or cover with water or other fluid; …   The Collaborative International Dictionary of English

  • flood — [flud] n. [ME flode < OE flod, akin to Ger flut: for IE base see FLOW] 1. an overflowing of water on an area normally dry; inundation; deluge 2. the flowing in of water from the sea as the tide rises 3. a great flow or outpouring [a flood of… …   English World dictionary

  • flood — ► NOUN 1) an overflow of a large amount of water over dry land. 2) (the Flood) the biblical flood brought by God upon the earth because of the wickedness of the human race. 3) an overwhelming quantity of things or people appearing at once. 4) an… …   English terms dictionary

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”