REALISATION DE LA LIGNE DE PARTAGE DES EAUX PAR FILE D’ATTENTE HIERARCHIQUE PARALLELE

d tail, on rappellera la d finition de la LPE ainsi que ses deux grands modes

d'utilisation, selon qu'elle est contr l e par marqueurs ou non. Les algorithmes

classiques de LPE seront galement rappel s, car ils permettent de mettre le doigt sur

diff rents probl mes de fond relatifs cette transformation (notamment son caract re

non local), probl mes qui influencent la vitesse de r alisation et l'exactitude du

r sultat final. On d crira ensuite la file d'attente hi rarchique (FAH), l'algorithme qui

sert de point de d part aux d veloppements actuels. Ces d veloppements visent

parall liser l'algorithme par FAH. Plusieurs solutions seront d crites : d coupage de

l'image en imagettes et traitement parall le de ces imagettes, traitement en parall le

de plusieurs pixels sur la file d'attente, traitement en parall le de marqueurs. Ces

diff rentes solutions ne sont pas incompatibles. Elles peuvent tre combin es,

d'autant qu'on s'efforcera de montrer au cours de ce rapport que les performances

d pendent fortement de la nature des images trait es et qu'une solution unique ne

saurait tre la plus efficace. On essaiera de comparer les diff rentes solutions

propos es et de donner une id e des gains de vitesse envisageables, bien que ces

estimations n'aient pas encore t test es sur des cas concrets. Ces tests seront r alis s

la suite de l'int gration de ces diff rentes approches dans l'environnement de

d veloppement Ptolemy. Cet environnement, d velopp par lUniversit de

Berkeley, permet de valider la fonctionnalit dalgorithmes parall les.

2. D finition, construction et utilisation de la LPE

2.1 D finition

Soit f une fonction num rique quelconque, qui peut tre, par exemple, la

repr sentation d'une image niveaux de gris. Pour introduire la ligne de partage des

eaux de f, not e LPE(f), nous allons consid rer simplement la surface topographique

limit e par le sous-graphe G(f) de f. Cette fronti re de G(f) pr sente un certain

nombre de structures topographiques caract ristiques : d mes, vall es, lignes de

cr tes ou de thalwegs, etc.. Parmi ces structures, deux nous int ressent plus

particuli rement : les minima r gionaux et les bassins versants de la topographie. Les

minima de f sont les composantes connexes de la surface topographique formant des

creux ou cuvettes Figure 1: Minima et plateaux d'une fonction.

4

Figure 1: Minima et plateaux d'une fonction

Imaginons donc que cette surface topographique soit trou e aux emplacements des

minima. Plongeons alors lentement cette surface dans un lac ( tendue d'eau

suppos e infinie pour la commodit de l'exp rience). l'eau va passer par les trous en

commen ant par ceux qui percent les minima les plus profonds et va

progressivement inonder le relief. A tout moment de l'inondation, les diff rents lacs

d limit s sur la topographie seront la m me altitude (Figure 2). Ce fait est

fondamental, nous y reviendrons par la suite.

Figure 2: Inondation de la surface topographique d finie par une fonction

Supposons de plus que l'on emp che les eaux provenant de lacs diff rents (donc de

minima diff rents) de se m langer en construisant sur la surface topographique un

barrage toutes les fois o une telle ventualit pourrait se produire (Figure 3).

5

Figure 3: Construction d'un barrage (ligne de partage des eaux) entre les

diff rents bassins versants

Lorsque la totalit de la surface topographique aura t engloutie, seuls les barrages

mergeront, d limitant des lacs en nombre gal au nombre de minima de la fonction

f. Ces barrages constituent ce qu'on appelle la ligne de partage des eaux de f. Quant

aux lacs, ce sont les bassins versants associ s aux minima de f (Figure 4).

Figure 4: Ligne de partage des eaux (LPE) et bassins versants d'une fonction

On remarque imm diatement qu'il n'est pas n cessaire de faire appara tre r ellement

6

les lignes de barrage. On pourrait imaginer de colorier diff remment les eaux

appartenant des bassins versants diff rents. Cette op ration s'assimile un

tiquetage et les lignes de partage des eaux sont alors d' paisseur nulle. Ces deux

variantes conduisent des algorithmes diff rents. L'algorithme de construction de la

LPE classique appartient la premi re variante. On verra que l'algorithme par file

d'attente utilis comme point de d part de l' tude algorithmique proc de de la

seconde variante, en produisant des lignes de partage des eaux d' paisseur nulle.

2.2 Construction de la LPE : l'algorithme classique

Cette d finition de la ligne de partage des eaux en termes d'inondation pr sente

galement l'avantage d' tre op ratoire et de fournir un algorithme direct pour sa

construction. Cet algorithme est bas sur la reconstruction des seuils successifs de la

fonction f l'aide d'une transformation morphologique appel e squelette par zones

d'influence g od sique (SKIZ g od sique). D crivons-le l'aide d'un exemple.

Soit f une fonction digitalis e, et d signons par Zi (f) l'ensemble des points x

d'altitude inf rieure ou gale i.

Zi(f)={x : f(x) d i}

Consid rons la plus petite altitude i0 correspondant un seuil Zi0(f) non vide. Zi0(f)

peut avoir plusieurs composantes connexes, chacune d'elles tant alors par d finition

un minimum r gional de f. Examinons alors le seuil Zi0 + 1(f) imm diatement

sup rieur. Ce dernier seuil contient videmment le pr c dent. Soit Z, une

composante connexe de Zi0 + 1(f). Il y a trois relations possibles entre Z et Zi0(f).

(Erreur ! Source du renvoi introuvable.).

Figure 5: Relations entre les composantes connexes de deux seuils successifs d'une

fonction

• Ou bien, Z ) Zi0(f). Dans ce cas, Z est un minimum r gional de f l'altitude i0.
• Ou encore, Z ) Zi0(f) est non vide et connexe. Dans ce cas, Z repr sente le niveau

7

(i0+1) du lac produit par l'inondation du minimum r gional Z ) Zi0(f).

• Enfin Z ) Zi0(f) peut tre non vide et form de plusieurs composantes connexes.

Dans ce cas, Z est la r union des eaux provenant des diff rents minima r gionaux

composant Z ) Zi0(f). Comme cette jonction n'est pas autoris e, il faut donc

construire la ligne de partage des eaux s parant ces diff rents lacs.

Pour cela, on construit les zones d'influence g od siques de Z ) Zi0(f) dans Z (Figure

6).

Figure 6: Construction de la LPE par SKIZ g od sique - tape initiale (a), SKIZ

g od sique du seuil i dans le seuil i+1 (b), ajout des minima ce niveau (c)

Une zone d'influence d'une composante connexe de Z ) Zi0(f) est constitu e des

points de Z plus proches au sens de la distance g od sique de cette composante

connexe que de tout autre composante connexe de Z ) Zi0(f). Chaque zone

d'influence constitue alors un bassin versant, ou du moins sa restriction au niveau i0

+ 1, associ chaque minimum r gional (composante connexe) de Z ) Zi0(f).

Reprenons alors la totalit du seuil Zi0 + 1(f). Comme ce qui vaut pour une

composante connexe de Zi0 + 1(f). vaut pour toutes, les bassins versants de f au niveau

i0+1 seront constitu s des zones d'influence g od siques de Zi0 (f) dans Zi0 + 1(f)

auxquelles viennent s'ajouter les minima r gionaux au niveau i0 +1, c'est- -dire les

composantes connexes de Zi0 + 1(f). d'intersection vide avec Zi0 (f).

Il suffit alors de r it rer cette proc dure de construction pour les niveaux i0 +2, i0+3,

etc.. De fa on plus formelle, on peut d crire cet algorithme l'aide de

l'ordinogramme suivant (f sera suppos e prendre ses valeurs entre 0 et N).

8

A la fin de la proc dure, W repr sente les bassins versants de f, et LPE(f)=Wc.

2.3 La LPE contr l e par marqueurs

Dans la d finition classique de la LPE, l'inondation de la surface topographique

engendr e par la fonction f se fait partir des minima de cette fonction. Cependant,

rien n'interdit de construire une LPE o l'inondation ne serait plus amorc e par les

minima mais par un ensemble quelconque de sources d'inondation. En reprenant

l'analogie pr c dente, au lieu de percer la surface topographique l'aplomb des

minima de f, on peut le faire l'aplomb de chaque composante connexe d'un

ensemble quelconque M. Cet ensemble est appel ensemble marqueur. L'inondation

s'effectuant alors partir de chaque composante connexe g n rera autant de bassins

versants correspondants. Par rapport l'algorithme pr c dent, on remarquera que

l'eau, bien que restant tout instant au m me niveau peut tre amen e se d verser

dans des cuvettes non marqu es (Figure 7). En reprenant l'algorithme de

construction seuil par seuil pr c demment utilis , cette LPE est paradoxalement plus

simple mettre en oeuvre.

L'initialisation de l'algorithme consiste prendre l'ensemble M des marqueurs

comme initiateur des bassins versants :

W0=M

Puis l'inondation au niveau i des bassins versants Wi+1 s'effectue par squelette par

zones d'influence g od sique des bassins versants au niveau i dans l'espace

Zi+1(f)*M. La Figure 8 illustre l'algorithme.

9

Figure 7: D bordement d'un bassin versant actif (marqu ) dans un bassin versant

non marqu

Figure 8: Algorithme de ligne de partage des eaux avec marqueurs impos s.

Inondation des sections successives de la fonction

Deux diff rences essentielles existent entre cet algorithme et celui de la LPE

classique: d'abord le SKIZ g od sique s'effectue dans Zi+1(f)*M et non dans Zi+1(f).

En effet, Wi doit tre inclus dans l'espace g od sique. Or comme :

M = W0 Wi

on n'est pas assur que Wi soit inclus dans Zi (f), d'o l'adjonction de M ce niveau

10

de seuil. La deuxi me diff rence est qu'on n'adjoint pas Wi les minima de f apparus

au niveau i. En effet, ces minima ne sont plus les sources de l'inondation. Cette

diff rence explique galement pourquoi cet algorithme est plus simple que

l'algorithme classique. En effet ce dernier combine la fois la construction de la LPE

chaque niveau de seuil et l'extraction des ventuels minima ce niveau.

L'algorithme classique appara t alors comme un cas particulier de la LPE contr l e

par marqueurs. Il suffit en fait de d tecter les minima de la fonction f et de prendre

ces minima comme ensemble marqueur M. C'est pourquoi, les algorithmes de LPE

analys s dans cette tude sont uniquement des algorithmes de LPE contr l es par

marqueurs.

2.4 Caract ristiques fondamentales de la LPE

Certaines caract ristiques fondamentales de la LPE tant au niveau de sa d finition

que de sa r alisation doivent tre soulign es. Ce sont essentiellement le caract re non

local de la transformation et la hi rarchie particuli re engendr e par le processus

d'inondation notamment sur les plateaux.

2.4.1 La non-localit de la LPE

Une ligne de partage des eaux est un objet non local. Cela signifie qu'il est impossible

d'affirmer qu'un pixel donn d'une image appartient la LPE par une simple

observation locale de son environnement (m me si on tend l'analyse au del de ses

voisins imm diats). La meilleure preuve de cette impossibilit est que l'on peut

construire relativement facilement des configurations de voisinage d'un pixel de

taille aussi grande que l'on veut telles que l'une fera du pixel central un point de la

LPE et pas l'autre. La seule fa on d'affirmer sans ambigu t qu'un pixel appartient

la LPE est de constater que ce pixel s pare plusieurs eaux provenant de sources

diff rentes. Il faut donc propager l'inondation. Ce caract re non local de la LPE

explique galement pourquoi cette ligne ne suit pas obligatoirement les lignes de

cr te de la surface topographique dessin e par la fonction f. C'est m me parfois le

contraire dans le cas par exemple de structures en boutonni re (Figure 9).

Figure 9: Structure en demi-boutonni re - La LPE passe par le thalweg entre les

deux cr tes

11

On peut noter que le caract re non local de la LPE n'est pas compl tement g r par

les algorithmes pr sent s plus haut. En effet, le SKIZ g od sique est r alis par le

biais de transformations morphologiques locales (des paississements

homotopiques) et l'it ration de ces transformations ne conduit pas n cessairement

une v ritable LPE s parant des bassins versants diff rents. C'est le cas par exemple

de la fonction pr sent e la Figure 10. L'arc AB s pare le m me bassin versant. Une

telle ligne de partage est appel e ligne de partage locale.

Figure 10: Ligne de partage locale engendr e pendant la construction de la LPE

Cette caract ristique fondamentale de la LPE constitue un probl me majeur pour sa

parall lisation. En effet, la parall lisation d'algorithmes consiste souvent r aliser en

m me temps un certain nombre de transformations locales, l'union de ces

transformations fournissant le r sultat recherch sur l'ensemble de l'image.

Il existe cependant une classe particuli re de fonctions o l'observation locale des

configurations de pixels permet de mettre en vidence des points appartenant la

LPE (points-selles). Ces fonctions ont la propri t de ne pas poss der de zones plates.

D'autre part, il est possible par le biais d'une op ration appel e fl chage de

transformer n'importe qu'elle fonction en une fonction sans zones plates ayant m me

LPE que la fonction initiale (Figure 11).

On pourrait penser alors qu'on tient l la solution au probl me de la non-localit de

la LPE. Malheureusement ce n'est pas le cas, car le fl chage est une op ration qui doit

tre effectu e par le biais d'un processus de propagation.

2.4.2 Les hi rarchies dans le ph nom ne d'inondation

2.4.2.1 Un premier niveau de hi rarchie

Il existe dans la construction de la LPE plusieurs niveaux hi rarchiques qu'il importe

de respecter quelque soit l'algorithme choisi, faute de quoi le r sultat sera fauss . On

a d j vu que les eaux inondant les bassins versants sont toujours la m me altitude.

On pourrait envisager de transgresser cette r gle en permettant certains bassins

versants de se remplir plus vite que d'autres. Cependant, on a vu plus haut que la

seule fa on d'obtenir la LPE est de mettre en vidence le contact des eaux provenant

12

de sources d'inondation diff rentes. Dans l'hypoth se d'une vitesse d'inondation

diff rente, cela signifie qu'il faudrait tre capable d'arr ter momentan ment

l'inondation d'un bassin versant lorsqu'on se rend compte qu'il risque de d border

dans un autre (voir Figure 7) parce que l'eau passe par dessus la LPE qui les s pare.

Or on a vu qu'on ne dispose d'aucun moyen de rep rer cet ventuel d bordement

cause de la non-localit de la LPE. Cette approche algorithmique est donc vou e

l' chec.

Figure 11: Fl chage d'une fonction - la compl tude du fl chage limine les zones

plates

2.4.2.2 Propagation le long des plateaux

La deuxi me caract ristique importante de la LPE concerne la propagation de

l'inondation sur les zones plates de la surface topographique. L'algorithme classique

est construit de mani re simuler une propagation vitesse constante : l'eau arrive

sur le bord descendant du plateau et inonde ce plateau en se propageant vitesse

constante partir du bord. Le front d'inondation est chaque instant et partout la

13

m me distance du bord et ceci pour l'ensemble des plateaux. Cette mod lisation de

l'inondation sur les zones plates est conforme la r alit . Bien entendu, si un plateau

est inond par plusieurs sources, les r gles de construction de la LPE doivent tre

respect es et celle-ci se construit sur le plateau en fonction des contacts des

diff rentes eaux provenant des diff rents lacs adjacents au plateau. Les distances

successives des fronts de propagation correspondent la distance g od sique des

bords descendants du plateau aux autres points dudit plateau (Figure 12).

Figure 12: Plateau X, de bord descendant Y0 - Distance g od sique d finie sur le

plateau X partir des bords descendants

Ce mod le de l'inondation des plateaux engendre une nouvelle hi rarchie qui

implique que les points du bords doivent tous tre trait s partout avant que les

points la distance 2 soient tous trait s leur tour, et ainsi de suite jusqu' ce que

tous les points du plateau aient t inond s. Comme les plateaux n'ont aucune raison

d'avoir la m me taille, on voit imm diatement que leur inondation ne s'ach vera pas

en m me temps. Cela signifie alors que les premiers plateaux inond s devront

attendre que tous les plateaux d'une m me hauteur aient t inond s pour que le

processus puisse se poursuivre vers les points de la surface topographique de

hauteur imm diatement sup rieure. On pourrait envisager de changer la r gle de

propagation en rempla ant le mod le vitesse constante par un mod le d bit

constant : les points des plateaux seraient trait s l'un apr s l'autre sans tenir compte

de leur distance au bord descendant. La propagation le long des petits plateaux serait

alors beaucoup plus rapide que sur les grands. Cette mod lisation n'est pas

int ressante pour plusieurs raisons :

• la r gle de propagation sur les plateaux n'est pas la m me que sur le reste de la

surface topographique. Il semble difficile de justifier pourquoi une inondation d bit

constant devrait tre la r gle sur les plateaux alors que ce n'est manifestement pas le

cas sur le reste de la surface topographique puisque la hauteur de l'inondation est la

m me pour tous les bassins versants et ceci quelque soit leur volume.

• Cette r gle induirait un positionnement diff rent de la LPE sur les plateaux qui a

toutes les chances d' tre biais .

• Le gain en vitesse serait illusoire puisque, quelque soit la r gle d'inondation, il est

indispensable d'attendre que l'ensemble des plateaux soient inond s pour poursuivre

le processus. Or dans tous les cas de Figures, le nombre de points des plateaux

traiter reste inchang .

14

2.4.3 Les autres biais de l'algorithmique

En dehors des erreurs grossi res qui peuvent entacher la LPE si l'algorithme utilis

fait table rase des hi rarchies de l'inondation d crites plus haut, il existe aussi des

biais engendr s par les transformations morphologiques utilis es et notamment par

les transformations homotopiques servant construire le SKIZ g od sique. Cette

transformation utilise des op rateurs appel s paississements r alis s l'aide

d' l ments structurants biphas s et anisotropes. Pour des raisons de simplicit

algorithmique, ces l ments structurants ne sont pas utilis s en m me temps mais

direction par direction. Cela g n re des biais comme l'illustre la Figure 13Figure 13o

ce type de transformation est utilis e pour effectuer le SKIZ de deux points.

Figure 13: Biais dans la r alisation du SKIZ d l'usage d' paississements non

isotropes

Comme l'op ration est it rative, les erreurs locales se propagent et peuvent produire

des d rives consid rables. La Figure 14 montre l'importance de ces variations dans la

construction de la LPE selon que l'on utilise un algorithme isotrope ( gauche) ou

direction par direction ( droite).

Figure 14: LPE exacte r alis e l'aide d'op rateurs isotropes (a) et LPE classique

biais e (b)

15

Paradoxalement et contrairement aux erreurs qui peuvent se produire si on ne

respecte pas les relations d'ordre impos es par l'inondation niveau par niveau puis

sur les plateaux, ces d fauts apparaissent car on introduit artificiellement ici un ordre

de traitement des pixels alors qu'il devraient tous tre trait s en m me temps. On

reviendra sur ce probl me lors de la pr sentation des algorithmes de parall lisation

afin d'envisager des solutions pour le r duire voire m me le supprimer. Remarquons

enfin que la LPE d'une image digitale devrait en toute rigueur avoir une paisseur

variable selon la parit des configurations : selon que l'on veut mat rialiser ou non

cette LPE, son paisseur pourrait tre de 0, 1 ou 2 pixels. L'utilisation

d' paississements direction par direction permet d'avoir une LPE d' paisseur

constante. On peut se demander si cette simplification algorithmique m rite les

d fauts importants qu'elle peut induire.

2.5 Comment utiliser la LPE?

Apr s avoir d crit la LPE, apr s avoir pass en revue ses caract ristiques et ses pi ges

et avant d'introduire l'algorithme de FAH qui servira de base l'approche parall le,

on peut illustrer bri vement l'utilisation de la LPE. On a vu en effet que les

performances de cette transformation seront fortement d pendantes de la nature des

images trait es. De plus, cet outil de segmentation vient avec son mode d'emploi.

Segmenter une image consiste en effet mettre en vidence un ensemble de

marqueurs M d signant les objets extraire dans l'image et une fonction f quantifiant

la nature des transitions entre les diff rents objets. Muni de ces deux l ments, la

segmentation consiste alors simplement effectuer la LPE de f contr l e par les

marqueurs M (Figure 15).

Figure 15: Principe g n ral de la segmentation par LPE.

16

Tr s souvent (mais pas exclusivement) la fonction f utilis e est le module du gradient

car les transitions entre les objets se caract risent par des variations plus ou moins

fortes de contraste. Les marqueurs M utilis s d pendent essentiellement de la nature

et des propri t s de luminance, de couleur, g om trique ou topologiques des objets

segmenter.

On illustrera l'utilisation de la LPE sur un probl me de segmentation automatique de

la chauss e partir d'une cam ra embarqu e dans un v hicule. La LPE du gradient

de l'image originale (Figure 16) produit une forte sur-segmentation.

Figure 16: Image de la chauss e (a) et LPE de son gradient (b)

Mais si cette LPE est contr l e par un ensemble de marqueurs (Figure 17a) d signant

d'une part la chauss e et d'autre part l'ext rieur, la segmentation obtenue est tout

fait satisfaisante (Figure 17b).

Figure 17: Marqueurs de la chauss e et de l'ext rieur d finis manuellement (a),

LPE du gradient contr l e par ces marqueurs (b)

17

Les marqueurs pr c dents ayant t introduits manuellement, il convient de d finir

une proc dure automatique permettant de les g n rer. Cette proc dure est bas e sur

une segmentation hi rarchique de la LPE initiale associ e une extraction du bassin

versant situ en bas de l'image qui apr s simplification et filtrage fournira les

marqueurs. La LPE finale sera identique celle obtenue avec les marqueurs d finis

la main (Figures 18a 18d).

Figure 18: Premi re segmentation hi rarchique de l'image (a), extraction d'un

marqueur de la chauss e (b), marqueur filtr et g n ration d'un marqueur

ext rieur (c), LPE du gradient contr l e par les marqueurs pr c dents (d)

Cet exemple illustre plusieurs aspects de l'utilisation de la LPE. Tr s souvent, on a

besoin la fois de LPE de bas niveau et de LPE contr l e par marqueurs. Si le

gradient est une fonction qui pr sente la fois beaucoup de minima et peu de

plateaux, la LPE contr l e par marqueur pr sente les caract ristiques inverses

(l'inondation des cuvettes non actives est quivalente la pr sence de plateaux). On

verra que ces deux aspects antagonistes conditionnent norm ment le rendement des

solutions algorithmiques propos es pour la parall lisation.

18

3. Parall lisation de la LPE

3.1 Quelques solutions au probl me de la vitesse de la LPE

L'algorithme classique est extr mement lent. Il fonctionne en effet avec des

op rateurs morphologiques qui travaillent sur toute l'image. Il a t crit pour tre

r alis sur une architecture de processeur bas e sur un voisinage de traitement local

et un balayage syst matique de l'image. Tous les points de l'image sont trait s

chaque it ration. Or seuls les points venant d' tre inond s et ceux susceptibles de

l' tre m ritent de l'int r t. Pour acc l rer l'algorithme classique, diverses solutions

ont t propos es. On peut r duire le nombre de niveaux de gris par des

anamorphoses. Cela r duit le nombre d'it rations mais pas le nombre de points

traiter. On peut galement sous- chantillonner l'image. Cette technique a t utilis e

avec succ s dans des cas bien pr cis. Elle ne saurait pr tendre tre g n rale. Enfin

d'autres approches algorithmiques ont t tudi es : fl chage, algorithmes r cursifs

et files d'attente hi rarchiques (FAH). La FAH constitue l'heure actuelle la

meilleure solution pour une implantation logicielle de la LPE. Ses performances sur

des machines standards en font une alternative s rieuse des processeurs d di s.

C'est pourquoi cette structure algorithmique a t choisie comme point de d part la

parall lisation de la LPE.

3.2 La file d'attente hi rarchique, pr sentation et fonctionnement

Une file d'attente hi rarchique peut tre consid r e comme une file d'attente

multiple. Les jetons arrivent dans la file et sont trait s par ordre de priorit . Chaque

jeton est plac la fin d'une file correspondant son niveau de priorit : il sera trait

apr s les jetons de m me priorit qui sont arriv s avant lui. Dans la FAH, un seul

jeton est trait la fois. D s qu'une file d'une priorit donn e est vide, elle est

supprim e et elle ne sera jamais reconstitu e dans la suite du processus. Si un jeton

de priorit sup rieure ou gale la priorit de la file qui a t supprim e arrive, ce

jeton sera plac la fin de la file de priorit la plus lev e existant encore au moment

de son arriv e. La sp cification fonctionnelle d'une FAH se fait par le biais d'un

nombre r duit d'items :

• la cr ation de la FAH.
• la destruction d'une FAH.
• l'insertion d'un jeton au sommet d'une file de priorit donn e.
• le d pilage (ou traitement) consistant fournir l'adresse et la priorit du jeton de

plus haute priorit arriv le premier (celui situ en bas de la pile de plus haute

priorit ).

3.2.1 Fonctionnement de la FAH

La Figure 19a montre comment une simple file d'attente fonctionne. Les jetons

arrivent par le haut et sont retir s par le bas (structure FIFO "First In First Out"). La

19

Figure 19b montre comment une FAH fonctionne.

Figure 19: File d'attente simple (a) et file d'attente hi rarchique (b)

Une FAH est simplement une s rie de files d'attente simples. Chaque file d'attente

simple a un niveau de priorit . Dans notre exemple la FAH a quatre niveaux de

priorit et la file de plus forte priorit est droite. Toutes les files sont ouvertes leur

sommet, ce qui signifie qu' tout moment un jeton peut tre ins r dans la file de

priorit correspondante. Au contraire, seul...