Réalisation de la LPE par FAH parallèle
Contents
1. 1 actif 54 5 5 4 5 30 15 211 2 4111 15 10 3 4 1 2 1411 3 11 30 20 12 etc 4 1 3 1 2 1 1 4 1 3 5 1 2 1 1 20 6 5 4 4 4 ge 3 4 mage margueur 2 4 2 7 2 2 2 1 11 8 9 tape 4 52 Activit des processeurs Situation des FAH 1 5 4 5 5 4 5 30 15 3 2 be 4252 2 actif 41 12 15 10 3 4 1 2 1 411 3 1 1 30 20 12 etc 4 1 3 1 2 1 1 4 1 3 5 12 1 1 20 6 5 4 44 3 4 Image marqueur 2 4 g q 2 3 7 2 2 SI 11 8 9 Propagation tape 5 53 5 5 5 191919101910 15 15 15 15 5 10 5 1191919101010 19 15 15 15 515 5 10 10 10 10 10 15 1515 15 15 10 10 10 10 15 15 15 15 15 15 15 15 15 Image marqueur Propagation tape 6 54 Activit des processeurs actif Situation des FAH 5 5 4 3 4 2 4 1 15 1 4 1 3 30 20 0 N re NU R D 5 4 44 3 4 24 23 22 2 1 Activit des processeurs Situation2. m moire M moire ep FAH LABEL 3 m moire rocesseur NG m moire FAH F e Figure 32 un processeur par pixel de la File d Attente courante En ce qui concerne le bus d change nous proposons de se baser sur le principe des anneaux de processeurs tel que celui illustr dans la Figure 33 chaque processeur re oit des jetons venant des processeurs situ s sa gauche Chaque processeur met vers les processeurs situ s sa droite les jetons qui venaient de sa gauche et qui ne lui taient pas destin s ainsi que ses propres jetons processeur 1 processeur 8 processeur 2 Le processeur 7 processeur 3 AR processeur 4 lt processeur 6 processeur 5 Figure 33 anneau de processeurs 39 Cette architecture permet de r partir uniform ment la charge de travail concernant Tempilement et le d pilement quel que soit le type d image Il reste r soudre le probl me de contention de bus au niveau de l acc s la m moire LABEL 4 6 Conclusion La solution consistant partager l image de d part en imagette est la seule qui permette de distribuer compl tement la m moire sur les processeurs C est la raison qui a motiv le d cision d tudier plus sp cifiquement l algorithme sous jacent cette architecture 5 Parall lisation par imagettes traitement parall le di
3. 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 Barrage 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 Bassins versants Minima Ligne de partage des eaux 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 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
4. me diff rence est qu on n adjoint pasa 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 alsgorithme 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 24 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 construir
5. tiquet ou e dans le cas o V n est pas encore tiquet alors e tiquetage de V par le label de pc e empilage de l adresse de V dans FAH Cela signifie que pour traiter dans le cas o V n est pas encore tiquet il faut acc der deux fois la m moire image LABEL en lecture puis en criture une fois la m moire image NG et une fois la m moire FAH Dans le cas o V n appartient pas la m me imagette que pc il est donc pr f rable que V soit trait par le processeur associ V partir d une requ te faite par le processeur qui a d pil pc Notons P V le processeur traitant l imagette contenant Pour que P V puisse tiqueter et l empiler dans sa FAH il faut qu il connaisse e l adresse de V le label de pc Avant de d terminer les informations envoyer au processeur r cepteur consid rons les diff rents cas d change de pixels entre processeurs illustr s dans la Figure 28 Dans la Figure 28 a nous avons repr sent le cas des pixels situ s aux angles des imagettes Dans ce cas le processeur traitant pc doit envoyer une requ te ces trois processeurs voisins pour qu ils tiquettent les pixels les concernant et adjacents pc La majorit des cas est repr sent par la Figure 28 b Le processeur traitant pc doit faire une requ te son processeur voisin pour qu il traite les 3 pixels voisins de pc le concernant Afin de r duire les changes entre proces
6. 3 5 1 2 1 1 20 6 4 5 3 5 P 2 5 Image margueur 14 7 actif 12 1 5 1 1 30 12 8 9 Propagation tape 9 57 Activit des processeurs Situation des FAH 1 54 5 5 4 5 30 15 359 2 5 1 5 3 4 44 4 3 42 2 41 15 3 4 actif etc 4 1 3 1 2 1 1 4 1 3 5 1 2 1 1 20 6 Image marqueur 7 actif 1 5 30 5 1 4 1 8 31 1 1 2 1 30 13 9 Propagation tape 10 58 Activit des processeurs Situation des FAH 1 5 4 5 5 4 5 30 15 3 5 2 5 1 5 3 4 44 4 3 4 2 2 4 1 15 3 4 actif 5 6 Image marqueur 7 1 5 30 9 2 ete 4 2 8 actif 12132 1 1 2 2 30 14 9 Propagation tape 11 59 Activit des processeurs Situation des FAH 5 4 5 5 4 5 30 15 3 5 2 5 1 5 3 4 44 43 42 i SM 15 3 4 actif 5 6 Image margueur 7 1 5 30 5 2 42 S 1 213 2 1 1 2 2 30 14 9 Propagation tape 12 60
7. aboutissant un blocage Nous avons donc d cid de baser l change de pixels sur le principe de la boite aux lettres Cela signifie que les pixels mis par les processeurs voisins sont stock s dans une zone tampon en attendant d tre trait s Chaque processeur doit regarder r guli rement si sa Zone tampon n est pas vide Si c est le cas il doit traiter les pixels re us jusqu que la zone tampon soit vide Le moment o les pixels re us doivent tre trait s par rapport au pixel de la file d attente locale n a pas d importance En effet on a vu que les pixels d un m me niveau de gris o la m me distance du bord descendant dans un niveau de gris donn peuvent tre trait s dans n importe quel ordre On donc le choix de les traiter e apr s avoir d pil o empil un pixel de la FA courante e apr s avoir d pil un pixel et trait tous ses pixels voisins e au moment o le processeur a vid sa FA courante N anmoins plus on privil gie le traitement des pixels de la FA locale par rapport aux pixels re us plus la taille de la zone tampon doit tre importante 4 3 7 Perspectives Dans le cas d un partage selon une matrice carr e les processeurs qui traitent les imagettes non situ es au bord de l image globale changent des pixels avec 8 processeurs voisins comme ceci est illustr dans la Figure 30 Cependant comme nous l avons montr dans la Figure 28 a les liens diagonaux entre
8. 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 s
9. courante au moment o le processeur commence d piler son premier pixel La hi rarchie li e la distance g od sique impose qu un processeur ne traite que les x premiers pixels de la file d attente m me si d autres pixels sont venus dans cette m me file d attente On dira alors que le processeur est inactif bien que sa file d attente courante ne soit pas vide Une fois dans cet tat un processeur ne peut redevenir actif et traiter les pixels suivant que si tous les autres processeurs sont galement inactifs Ce processus se r p te jusqu ce que les files d attente courantes de tous les processeurs soient vides On passe alors au niveau de gris suivant Nous avons tout d abord envisag d effectuer ces deux contr les au moyen dun contr leur centralis Ce contr leur re oit l tat d activit de tous les processeurs 27 ainsi que l tat de leur file d attente courante Suivant l tat des processeurs il renvoie chaque processeur un signal de contr le les faisant passer de l tat inactif l tat actif Le contr leur a alors une structure qui d pend du nombre de processeurs qui n est pas en accord avec une architecture volutive en fonction de ce nombre de processeurs C est la raison pour laquelle nous avons galement tudi le cas d un contr le distribu Ces deux solutions sont pr sent es dans le chapitre 5 3 dans le cas de la parall lisation un processeur par imagette 4 2 2 P
10. de r duire leur nombre aux pixels appartenant aux fronti res des r gions tiquet s Ces jetons transportent une seule information les coordonn es du pixel correspondant dans f ou 3 2 2 2 Fonctionnement Le fonctionnement de la FAH peut se r sumer par le diagramme suivant Tant que la FAH n est pas vide faire extraire un jeton x de la FAH d terminer les pixels voisins de x qui n ont pas d tiquette dans g pour chaque voisin y non tiquet faire assigner y dans l image g m me tiquette que ins rer le jeton y dans la file d attente de la FAH de priorit correspondant au niveau de gris de y dans f si elle existe ou la file d attente de plus forte priorit existant encore 3 2 2 3 Illustration La Figure 21 montre comment l algorithme fonctionne sur un exemple 21 monodimensionnel tr s simple On repr sent gauche la surface topographique f ainsi que l image label g Dans cet exemple la source est simplement constitu e par les minima de f La partie droite montre l volution de la FAH 22 abedelehijk 3 2 1 8g abcdefghijk viv N C Bib gt LPE b 0 abcdefghijk abcdefghi jk abcdefghi k Figure 21 Exemple de fonctionnement de la FAH lors de la r alisation de la LPE Initialisation Une est cr e avec quatre niveaux de priorit correspondant aux quatre niveaux 23 de gris de l image f Les points fronti re des minima
11. des FAH l 5 4 5 5 4 5 30 15 3 4 44 4 3 10 4 2124 2 actif 41114 15 10 3 4 1 2 1 411 3 1 1 30 20 12 etc 4 1 3 1 2 1 1 4 1 3 5 12 1 1 20 6 5 4 44 3 4 Image marqueur 2 4 2 3 7 22 2 1 11 8 9 Propagation tape 7 55 Activit des processeurs Situation des FAH 1 5 4 5 5 5 i1d1d 14 10 1d 1d 15 15 15 15 15 15 5 5 4 5 5 o 5 1919101010101 15 15 15 15 15 515 15 1d 10 10 10 10 1515115 1915 15 15 25 19 10 10 109 15 15 151515 19 15 15 19 15 15 ia 1 44 43 EN 42 2 actif 41 15 3 4 1 2 14 13 11 30 20 12 etc 4 1 3 1 21 1 4 13 5 1 2 1 1 20 6 5 4 4 4 3 4 Image marqueur 24 2 3 7 2 2 2 1 11 8 9 tape 8 56 Activit des processeurs Situation des FAH 1 5 4 5 5 4 5 30 15 3 5 2 5 1 5 3 4 44 4 3 42 2 4 1 15 3 4 1 2 1 411 3 1 1 30 20 12 etc 4 1 3 1 2 1 1 4 1
12. et empiler V n 1 Vn 1 tant le voisin dont le label et le niveau de gris ont t lus avant le voisin Vn Ainsi lorsque le traitement du voisinage du pixel Pn 1 est termin on peut aussit t commencer traiter le voisinage du pixel de la File d Attente courante 4 3 Un processeur par imagettes 4 3 1 Introduction Le mod le de parall lisation pr sent ci dessous est un mod le de parall lisme spatial l image est divis e un nombre de blocs appel s galement imagettes gal au nombre de processeurs Ainsi chaque processeur ex cute l algorithme de ZPE par FAH sur son propre bloc 4 3 2 Repr sentation de cette solution Dans cette repr sentation nous avons choisi le cas d un partage de l image en horizontal et en vertical Ainsi chaque processeur traite une imagette de 2K N colonnes par 2L N lignes K et L tant respectivement le nombre de colonnes et de lignes de l image de d part et N le nombre de processeurs 9 dans notre exemple Cette parall lisation est repr sent e la Figure 24 image niveaux de gris image des labels Figure 24 parall lisation en 9 imagettes 29 Dans cette parall lisation les m moires de l image LABEL de l image niveau de gris et de la FAH sont distribu es sur les N processeurs On a alors pour chaque processeur l architecture repr sent e la Figure 25 La propagation des marqueurs consiste propager
13. leur File d Attente L adresse des pixels dans chaque imagette t repr sent e de la mani re suivante ligne colonne Voici quelques commentaires sur chacune des tapes 30 Image niveau de gris Image margueur Figure 26 image niveaux de gris et image marqueur de l exemple Initialisation chaque processeur stocke dans sa FAH les adresses des pixels d j marqu s et voisins de pixels non marqu s Seules les imagettes 1 5 et 7 ont des marqueurs donc seuls les processeurs 1 5 et 7 stockent des pixels dans leur FAH Propagation tape 1 ce sont les pixels de niveau de gris 0 qui sont trait s Seul le processeur 1 est actif I d pile le pixel d adresse 2 2 propage le marqueur 1 vers tous les voisins et les empile dans la FAH Propagation tape 2 il n y a pas de niveau de gris entre 0 et 5 Durant cette tape c est donc le niveau de gris 5 qui est trait par les processeurs 1 et 5 Ce sont des pixels de niveau de gris 10 qui sont tiquet s et empil s dans les Files d Attente FA Propagation tape 3 il n y a pas de niveau de gris entre 5 et 10 Ce sont donc les pixels de niveau de gris 10 qui sont maintenant trait s Trois processeurs sont simultan ment actifs 1 5 et 7 Propagation tape 4 c est toujours les pixels de niveau de gris 10 qui sont t
14. m me temps les pixels appartenant des imagettes diff rentes traiter en m me temps les pixels appartenant des sources d inondation marqueurs diff rents r partir sans consid ration sur leur position et leur sources d inondation tous les pixels traiter sur l ensemble des processeurs disponibles Ce sont ces diff rentes approches que nous allons d tailler dans la suite de ce document Signalons enfin qu il est galement possible d acc l rer le traitement en chercher parall liser ou pipe liner le traitement r alis par chaque processeur de la FAH sur chaque jeton 4 Parall lisation de LPE bas e sur FAH 4 1 Point de d part et Choix g n raux Comme nous l avons dit pr c demment l algorithme de zone de partage des eaux bas sur la FAH servira de point de d part la parall lisation Il s agit de produire une image compos e d un ensemble de r gions tiquet es s par es par une LPE d paisseur nulle Le nombre d op rations effectuer est nettement moins important pour la ZPE que pour la LPE Dans le cadre d une architecture multiprocesseur l implantation de la LPE n cessite une grande quantit d change entre les processeurs ce qui risque de ralentir consid rablement le processus En effet il faut conna tre les labels de tous les voisins du pixel d pil pour pouvoir l tiqueter Inversement il faut conna tre le label du pixel d pil pour savoir s il faut empi
15. m moires FAH LABEL Niveaux de Gris sont distribu es sur l ensemble des processeurs e un processeur par marqueur il y a une FAH par processeur Dans chacune d elles sont empil s les pixels ayant la m me valeur de label m me marqueur L tape d tiquetage se simplifie puisqu il n y a plus d terminer la valeur du label du pixel courant d pil Les processeurs n ont pas de zone m moire pr d termin e sur laquelle ils effectuent la propagation L image LABEL sera donc partag e l ensemble des processeurs L image Niveaux de Gris est uniquement acc d e lecture et pourra donc tre dupliqu e au niveau de chaque processeur e r partition uniforme des pixels de la File d Attente courante sur processeurs il a une FAH par processeur Une phase d initialisation r partit les pixels appartenant aux marqueurs initiaux de mani re uniforme sur l ensemble des processeurs Lors du processus de propagation chaque processeur r partit uniform ment les pixels empiler sur les autres processeurs Pour la m me raison que pr c demment l image LABEL devra tre partag e par l ensemble des processeurs et l image Niveaux de Gris est dupliqu e au niveau de chaque processeur 26 parall lisation du traitement des n pikels situ s dans la file d attente courante Un processeur Un processeur R partition uniforme par margueur par imagette des pixels empil s sur n pr
16. quentiel et parall le Il est s quentiel car un ordre d inondation doit tre respect la fois dans la propagation le long du relief et des plateaux Mais ce processus est galement parall le car un niveau de priorit donn ce sont tous les pixels appartenant ce niveau qui se propagent en m me temps Or c est pr cis ment ce parall lisme qu il faut installer dans 24 l algorithme de FAH si l on veut accro tre les vitesses de traitement Il faut donc parall liser le traitement des pixels de la file d attente qui appartiennent au m me niveau de priorit Cette approche a un double avantage elle seule permet de r aliser une LPE respectant les r gles hi rarchiques pr c demment nonc es cette fa on de faire supprime l ordre de traitement artificiel des pixels introduits par les autres algorithmes classique ou FAH Elle est donc plus proche du ph nom ne naturel d inondation et donc susceptible de r duire sinon d liminer les biais apparaissant dans les LPE actuelles Une fois ceci tabli il existe plusieurs fa ons de s lectionner les pixels ou les jetons de m me niveau de priorit qui conduisent plusieurs types d architectures diff rentes et diverses contraintes d utilisation et de partage de la FAH de la m moire image et de la m moire label On peut en effet s lectionner les pixels selon leur position dans l image Cela revient d couper l image en plusieurs imagettes et traiter en
17. 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 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 fonctionne b a 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
18. sont stock s dans la avec une priorit correspondant leur niveaux de gris Les points b et c avec la priorit 0 le point g avec la priorit 1 L image label contient deux composantes connexes de valeurs respectives 1 et 2 Construction de la LPE Le point b de priorit maximale quitte la Son seul voisin sans tiquette est le point a Ce point prend donc l tiquette 1 crite dans la m moire g et est plac dans la file d attente de priorit 1 Le jeton c est alors d pil Son seul voisin non tiquet est prend l tiquette 2 et le jeton de niveau de gris gal 2 est plac dans le file de priorit 2 La file de priorit 0 tant alors vide est supprim e Le prochain jeton quittant la file est le jeton g Ses voisins f et h n tant pas tiquet s ils re oivent l tiquette 2 et sont stock s respectivement dans les files de priorit 3 et 2 Le traitement de la FAH se poursuit a est d pil et n empile aucun voisin La file de priorit 1 tant alors vide le d pilage de la file de priorit 2 commence par le traitement du jeton d qui empile son voisin e tiquet 1 suivi du d pilage du jeton h qui empile sur la m me file d attente son voisin 1 1 est alors d pil son tour Ce jeton empile son voisin j sur la file de plus faible priorit Cette file est alors trait e Les jetons f puis puis j sont d pil s ce dernier tant le seul empiler le jeton A la fin du traitement l i
19. transferts d informations entre processeurs pour r aliser une LPE exacte sur de telles images de grande taille La suite de l tude sera consacr e l implantation de ces algorithmes dans l environnement Ptolemy Elle devra aider finaliser l architecture d finitive et elle fournira des indications de performance et les gains de vitesse esp r s en fonction du type de segmentation et du type d images analys es 7 Annexe Cette annexe montre un exemple de propagation des marqueurs dans le cas d un partage de l image neuf imagettes chaque tape est illustr l tat des FAH associ es chaque processeur L tape d initialisation et les cinq premi res tapes de propagation sont expliqu es au paragraphe 4 3 3 47 15 15 15 15 20 20 20 25 25 20 20 20 16 16 15 Image niveau de gris Image margueur Initialisation 48 Activit des processeurs Situation des FAH 2 2 3 3 ei D rz D LA Activit des processeurs Situation des FAH 3 3 3 2 3 1 2
20. un jeton peut tre ins r dans la file de priorit correspondante Au contraire seule la file de plus forte priorit peut tre vid e Le jeton qui peut tre extrait est le jeton de plus forte priorit arriv le premier dans la file D s que la file de plus forte priorit est vide elle est supprim e et c est la file de priorit imm diatement inf rieure qui peut tre vid e son tour La Figure 20 illustre la derni re caract ristique du fonctionnement d une FAH un jeton de forte priorit arrive apr s que la file de priorit correspondante ait disparue Le jeton est alors ins r au sommet de la file courante de plus forte priorit jeton de priorit 0 d File de priorit 1 Figure 20 Prise en compte d un jeton de priorit plus forte que la priorit de la file d attente courante dans la FAH 20 3 2 2 Utilisation dune FAH pour la LPE La FAH peut tre utilis e pour r aliser rapidement une LPE d une fonction f contr l e par un ensemble de marqueurs M Chaque marqueur est tiquet Chaque r gion ou bassin versant en cours de construction conservera l tiquette du marqueur qui l aura g n r Un marqueur peut tre scind en plusieurs composantes connexes d s lors que chacune de ces composantes connexes a une tiquette commune La r alisation de la LPE peut tre effectu e selon deux variantes Dans la premi re les bassins versants se touchent On d signe cette version par le te
21. 00000000000000 000000000000 000000000000 0ene 25 4 1 POINT DE DEPART ET CHOIX nane eaaa 25 4 2 OU EST CE QUI EST PARALLELISABLE TN 26 4 2 1 Parall lisation des jetons situ s dans pile de niveau de priorit courant 26 4 2 2 Parall lisation du cycle de traitement d un pixel ss 28 4 3 UN PROCESSEUR PAR IMAGETTES essence seeeererrenseececeenenenneeececeeserenneee secs eserences cesse 29 E ME 29 4 3 2 Repr sentation de cette solution 29 4 3 3 Exemple de propagation des marqueurs inserer 30 4 3 4 ChoixXdupartag del images nn AM a EE aga a ai 32 4 3 5 Traitement des pixels appartenant aux bords des ss 33 4 3 6 Gestion de l change des pixels rennes 34 4 3 7 Perspectives sn ag aaa Na dns a en ee sde nn AKA A NG nd en Pure a a a nie 35 E EE 36 4 4 UN PROCESSEUR PAR MARQUEUR ne naeennan 36 EE 36 4 4 2 Communication 38 38 4 5 REPARTITION UNIFORME DES PIXELS EMPILER SUR N PROCESSEURS esse 38 G CONCEUSION E EE aa Na a ner rarement KA ak rene et ag dan entrer GEESS Pa aa Nn da es 40 5 PARALLELISATION PAR IMAGETTES TRAITEMENT PARALLELE 40 L INTRODUCTION AP NEE 40 5 2 ALGORITHME DE TRAITEMENT
22. 3 F3 actif 1 acti 12 1 1 5 2 3 Image niveau de gris 4 3 3 5 6 5 3 5 2 5 1 4 3 4 1 3 3 7 3 2 Image marqueur 31 10 8 9 Propagation tape 1 49 Activit des processeurs Situation des FAH 1 actif kaa Image niveau de gris 5 actif D RD PDO R pa Image margueur 7 3 O Un un ei D NU p Propagation tape 2 50 Activit des processeurs Situation des FAH 5 1 52 3 1 actif 54 25 5 5 45 1 5 5 5 5 i1d14 149 109 1d 1d 15 15 15 15 15 15 30 15 10 5 10 5 191910101010 19 15 15 19 15 19 515 5 10 10 10 10 10 1519 1515 15 15 15 14 10 19 14 15 15 15 15 15 19 15 15 15 15 15 2 3 Image niveau de gris 4 etc 4 1 3 1 21 1 4 13 5 actif 1 2 1 1 20 6 5 4 44 3 4 24 Image marqueur 2 3 7 actif 2 9 21 11 8 9 Propagation tape 3 51 Activit des processeurs Situation des FAH
23. LPE F Partie m canique 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 ts te ral ANG K AE ee Le VA DB 080 S E SZ Ge PRE r SE gr Ge d Ar Ur Ca CH a 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 17 d signant d une part la chauss e et d autre part l ext rieur la segmentation obtenue est tout fait satisfaisante Figure 17b b 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 segmentati
24. REALISATION DE LA LIGNE DE PARTAGE DES EAUX PAR FILE D ATTENTE HIERARCHIQUE PARALLELE Etude algorithmique Auteurs BEUCHER Serge LEMONNIER Fabrice SASPORTAS Rapha l 17 Juin 1997 1 INTRODUCTION NB NONA WA AGE NANG GA NE 3 2 DEFINITION CONSTRUCTION ET UTILISATION DE LA LPE 600000000000000000 00000000000000 0000 0000000000000000 4 2 1 BID INU DOIN EE 4 2 2 CONSTRUCTION DE LA LPE L ALGORITHME CLASSIQUE 7 2 3 LA LPE CONTROLEE PAR MARQUEURS eee AGENG aE EN PN NGE ag ga NAN A AG Ga EEE PAN Ng e aeS pa a aaa gan 9 2 4 CARACTERISTIQUES FONDAMENTALES DE LA LBE 11 2 4 1 La non localit de la EE 11 2 4 2 Les hi rarchies dans le ph nom ne d inondation ss 12 2 4 3 Les autres biais de l algorithmique ss 15 DI COMMENT UTILISER GABRIEL aa na panata Op nt retient A Vi BE aa aa dires edel aa ea paeka 16 3 PARALLELISATION DE LPE essesssessossoossocssoceoccssesosecssesosessossocsocessesossesocosesesessosssosoocssecssceoseesssessosssse 19 3 1 QUELQUES SOLUTIONS AU PROBLEME DE LA VITESSE DE LA 19 3 2 LA FILE D ATTENTE HIERARCHIQUE PRESENTATION ET FONCTIONNEMENT eines 19 3 2 1 Fonctionnement de FAP 19 3 2 2 Utilisation d une FAH pour la LE 21 PARALLELISATION DE LA FAH rronin a sa a a ag SN a a dde EE 24 4 PARALLELISATION DE LA LPE BASEE SUR FAH 60000000000000
25. 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 Zj l ensemble des points x d altitude inf rieure ou gale i Zi f x f x lt i Consid rons la plus petite altitude io correspondant un seuil Zio f non vide Zio f peut avoir plusieurs composantes connexes chacune d elles tant alors par d finition un minimum r gional de f Examinons alors le seuil Zio 1 f imm diatement sup rieur Ce dernier seuil contient videmment le pr c dent Soit Z une composante connexe de Zio 1 f a trois relations possibles entre Z et Zio f Erreur Source du renvoi introuvable Z Z 2 00 b Figure 5 Relations entre les composantes
26. arall lisation du cycle de traitement d un pixel Les op rations effectuer pour traiter un pixel sont les suivantes e d piler un pixel de la m moire FAH e lire la m moire LABEL pour conna tre le label du pixel d pil Pour chaque voisin du pixel d pil e lire la m moire LABEL Si le pixel voisin n est pas tiquet alors e crire dans la m moire LABEL e empiler dans la m moire FAH File d Attente lire la d piler un adresse Pn A courante D Pn NGNE LABEL label Pn op rations ex cut es en parall le lire 1 label Pn 1 adresse Vn wah label Vn adresse Pn 1 LABEL lire la m moire NG adresse Vn M adresse Vn 1 empiler ng Vn 1 dans la A adresse Vn 1 enre dans 555321 m moire label Pn 1 LABEL propager le label vers les pixels voisins Figure 23 parall lisation du traitement d un pixel Les n pixels situ s dans la file d attente courante au d but de son traitement peuvent tre trait simultan ment Nous proposons donc d effectuer deux traitements en parall le e d piler un pixel et lire son label label Pn 28 e propager le label du pixel d pil avant Pn Pn 1 vers son voisinage Cette tape peut elle m me tre parall lis e en deux tapes e lire le label et le niveau de gris dun voisin label Vn et ng Vn e crire le label de Pn 1 l adresse du voisin Vn 1
27. archiques Diverses pistes ont t explor es Avant de les d crire en 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 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 gratio
28. cesseurs Il n y a donc pas de temps perdu dans la communication inter processeur 4 4 3 Contrainte L inconv nient de cette architecture est que ses performances sont d pendantes du nombre de marqueurs On doit donc d terminer une image marqueur avec le plus de marqueurs possibles et au maximum un nombre gal au nombre de processeurs 4 5 R partition uniforme des pixels empiler sur n processeurs Le sch ma cette architecture est repr sent dans la Figure 32 s agit de r partir les pixels empiler uniform ment dans la FAH locale chaque processeur Le traitement des pixels est alors ex cut en deux phases 1 re phase en parall le chaque processeur d pile les pixels situ s dans sa file d attente courante et envoie sur le bus d change les pixels empiler sous la forme de jetons Un jeton est constitu de l adresse du pixel de son label et du num ro du processeur destinataire Le num ro du processeur destinataire est incr ment chaque fois qu un jeton est mis ce qui permet de r partir uniform ment les pixels sur les FAH locales Chaque processeur re oit les jetons dans une bo te aux lettres e 2 me phase une fois que les processeurs ont vid leur file d attente ils empilent dans leur FAH locale les jetons situ s dans leur bo te aux lettres 38 m moire rocesseur 1 m moire FAH m moire rocesseur 2 NG bus d change
29. connexes de deux seuils successifs d une fonction Ou bien Z A Zio f Dans ce cas Z est un minimum r gional de l altitude 1 Ou encore Z Zio f est non vide et connexe Dans ce cas Z repr sente le niveau i 1 du lac produit par l inondation du minimum r gional Z A Zio f Enfin Z A Zio 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 A Zio 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 A Zio f dans Z Figure 6 SKIZ Minimum au niveau 1 b WO O Figure 6 Construction de la 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 A Zio 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 Zio f Chaque zone d influence constitue alors un bassin versant ou du moins sa restriction au niveau 1 1 associ chaque minimum r gional composante connexe de Z A Zio f Reprenons alors la totalit du seuil Zio 1 f Comme ce qui vaut pour une composante connexe de Zio 1 f vaut pour toutes l
30. e gr ver fortement la qualit et l exactitude du r sultat Elle a permis galement de d gager les parties du processus o l effort de parall lisation pouvait tre entrepris L analyse d taill e des diff rentes approches possibles a montr que le d coupage en imagettes comme l approche de processeurs distribu s par marqueurs pouvaient se montrer d un rendement d cevant notamment lorsqu on doit r aliser une LPE contr l e par marqueurs parce que dans ce cas il y a la fois peu de marqueurs et les zones inonder donc les pixels de m me priorit ont peu de chance de se retrouver quitablement r partis entre toutes les imagettes L approche distribu e semble donc la plus prometteuse m me si elle est la plus complexe mettre en oeuvre en ce qui concerne la gestion des FAH de la m moire image et de la m moire label Il est probable cependant que l augmentation de la vitesse de r alisation de la LPE n cessitera une combinaison de ces trois approches associ e une structure de type au niveau de chaque processeur L approche imagette notamment a de l int r t ne serait ce que parce qu il faudra bien pour des raisons de co t et complexit de r alisation limiter la taille des images trait es L unique moyen de d passer cette limitation sera alors de d couper les grandes images en imagettes Il faut donc quelque soit l architecture finalement retenue tre capable de g rer ce d coupage et d organiser les
31. e r activer qu un sous ensemble de processeurs pour qui les files d attente locales pr c demment trait es ne sont pas vides On notera par ready un indicateur d tat positionn true par chaque processeur qui a termin de traiter une file d attente On notera galement par start_samei et start deux indicateurs autorisant un processeur traiter soit la file d attente pr c demment trait e soit la file d attente de priorit gale la priorit de la file 41 d attente pr c demment trait e plus un Les quations qui r gissent ces deux indicateurs sont start_nexti N readyi O queue_emptyi start_samei N queue_emptyi L algorithme 2 d crit l utilisation de ces indicateurs synchro readyij lt true wait until start_next or start_samei true readyi lt false if start_nexti true then call traitement else current_priority lt current_priority 1 call traitement end if end wait goto synchro algorithme 2 synchronisation Les deux types de contr le que l on peut adopter pour g n rer les signaux start_nexti et start_samei sont d crits dans les paragraphes ci dessous 5 3 1 Contr le global centralis Ce contr le est illustr par la Figure 34 Le contr leur global re oit les signaux read et queue_emptyi renvoie tous les processeurs les signaux start_next et start_same L algorithme du contr leur est le su
32. e 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 cons
33. ervant 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 SE 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 v
34. es bassins versants de f au niveau 17 1 seront constitu s des zones d influence g od siques de Zio f dans Zio 1 f auxquelles viennent s ajouter les minima r gionaux au niveau i 1 c est dire les composantes connexes de Zio 1 f d intersection vide avec Zio f suffit alors de r it rer cette proc dure de construction pour les niveaux 1 2 1 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 Initialis ation W 1 0 SELE g od sique de W dans X kW d tection des minima au niveau i de Minima aqout s W dilatation g od sique de W dans X gt Minima X Z W Bassins versants la fin de la proc dure W repr sente les bassins versants de f et LPE f WE 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 ef
35. es 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 fonction distance g od sique de Figure 12 Plateau A de bord descendant Yo Distance g od sigue d finie sur le plateau 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
36. fectuant 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 W M Puis l inondation au niveau des bassins versants W 1 s effectue par squelette par zones d influence g od sique des bassins versants au niveau 1 dans l espace Zi UM La Figure 8 illustre l algorithme Figure 7 D bordement d un bassin versant actif marqu dans un bassin versant non marqu 1 2 LPE 21 Marqueurs eg 06 Figure 8 Algorithme de ligne de partage des eaux avec marqueurs impos s Inondation des sections successives de la fonction 4 a 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 UM et non dans Zi 1 f En effet W doit tre inclus dans l espace g od sique Or comme on n est pas assur que soit inclus dans Z f d o l adjonction de ce niveau 10 de seuil La deuxi
37. it dans cette image La m moire FAH est distribu e au niveau de chaque processeur N anmoins ne connaissant pas a priori la surface occup e par chaque marqueur les FAH locales devront avoir une taille quivalente celle n cessaire pour une architecture monoprocesseur Dans chacune d elle sont stock s des pixels de m me label L image niveau de gris tant uniquement acc d e en lecture elle peut tre dupliqu e au niveau de chaque processeur Cette r partition des pixels suivant leur label permet de simplifier l algorithme de ZPE de d part Celui ci est alors le suivant e cr ation de la FAH associ e au label elle contient autant de piles qu il y a de niveaux de gris dans l image segmenter e initialisation de la FAH associ e au label on empile dans les pixels appartenant aux marqueurs de label k qui sont voisins de pixels non marqu s e gestion de la processus de propagation elle consiste it rer les deux tapes suivantes jusqu ce que la FAH soit vide d pile le premier pixel de la file d attente courante Appelons ce pixel 37 e on empile dans la File d Attente correspondant leur niveau de gris tous les pixels voisins de Po qui n ont pas d j t tiquet s et on leur affecte le label k 4 4 2 Communication inter processeur L image LABEL tant partag e entre les processeurs il n est plus n cessaire changer des labels entre pro
38. ite 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 l re tape de compl tude TANT DO OO ETA NEEN e Fl chage compl t 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 alsgorithme 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 zon
39. ivant ctrl_gb start_next lt false start_same lt false wait until mreadyij true if Nqueue_empty i true then start_next lt true else start_same lt true end if end wait goto ctrl_gb algorithme 3 contr leur 42 Contr leur global Figure 34 Contr le centralis 5 3 2 Contr le global distribu Ce contr le est illustr par la Figure 35 Les signaux start_next et start_same sont g n r s par le processeur Poo Ce dernier comporte un module de contr le qui ex cute l algorithme suivant ctrl_dt start_next lt false start_same lt false wait until readyr1 71 true if queue_emptyr1 71 true then start_next lt true else start_same lt true end if end wait goto ctrl_ dt algorithme 4 contr le distribu 43 ucs unit de calcul et de synchronisation Figure 35 Contr le distribu 5 4 Communication Quand un ou plusieurs processeurs d pilent des pixels appartenant au bord de leurs sous images ils doivent communiquer la position de ces pixels ainsi que leurs labels aux processeurs ayant une fronti re commune Les proc dures de communication sont d crites par la Figure 3 Chaque processeur communique avec chacun de ces huit voisins au moyen de deux tampons un tampon d mission et un tampon de r ception Les tampons pour les communications horizontales et vertica
40. le label du pixel d pil vers ses pixels voisins non encore tiquet s Dans le cas o le pixel d pil appartient au bord de l imagette certains pixels voisins n appartiennent pas la m me zone m moire que le pixel d pil faudra donc changer des donn es entre processeurs pour propager le marqueur entre les pixels du bord des imagettes ceci est mat rialis par le bus de donn es inter processeur dans la Figure 25 D autre part le contr le global assurant que les processeurs traitent tous le m me niveau de gris ou la m me distance l int rieur d un niveau de gris donn est repr sent par le bus de contr le inter processeur dans la Figure 25 m moire bus de contr le imagette LABEL inter processeur bus de donn es inter processeur m moire imagette NG m moire imagette FAH Figure 25 Interconnection d un processeur 4 3 3 Exemple de propagation des marqueurs Dans cette section nous proposons un exemple de propagation des marqueurs avec 9 processeurs et un partage de l image selon une matrice carr e Les images de d part sont repr sent es dans la Figure 26 Les processeurs ont t num rot s de 1 9 de la gauche vers la droite et de haut en bas L tape d initialisation et les premi res tapes de propagation sont donn es en annexe Sur deux colonnes nous avons repr sent pour chaque processeur l tat de leur activit et l tat de
41. ler les pixels voisins non encore tiquet s 29 Dans cette tude nous nous sommes donc concentr s sur la parall lisation de la ZPE Rappelons que nous avons postul que la propagation des marqueurs se faisait vitesse constante ce qui impose de propager les marqueurs l int rieur de chaque niveau de gris plateaux suivant la distance g od sique partir des bords descendants 42 Qu est ce qui est parall lisable Nous avons d termin que seuls deux types de parall lisation sont possibles e traiter les pixels situ s dans la file d attente courante en m me temps e _ parall liser les tapes de traitement d un pixel d piler tiqueter empiler L avantage de ces deux techniques est qu elles peuvent tre combin es car la premi re approche permet de traiter plusieurs pixels en m me temps alors que la deuxi me approche permet d acc l rer le traitement de chaque pixel Nous allons d tailler les diff rentes architectures envisag es pour r aliser ces deux types de parall lisation 4 2 1 Parall lisation des n jetons situ s dans la pile de niveau de priorit courant 4 2 1 1 Les trois types d architectures envisag es Nous avons envisag trois voies de parall lisation voir Figure 22 un processeur par imagette une zone de l image de d part imagette est affect e chaque processeur Chaque processeur effectue le processus de propagation uniquement dans cette zone Les trois
42. les ont des tailles gales aux longueurs des bords des sous images Pour les communications diagonales les tampons ont une taille unitaire Les notations utilis es pour les communications sont donn es dans Tableau 2 _5 1 mettre les donn es x et y dans le tampon d mission receive tampon_rx1 r ceptionner les donn es x et y du tampon de r ception tampon Full indicateur positionn true si le tampon de r ception k 1 nest pas vide i Tableau 2 notations pour les communications Les indices k et 1 sont relatifs au processeur D 44 0 1 1 1 GTA 4 1 0 1 1 1 1 1 1 1 1 j 1 send_process for each V p V p a Emi for each if p em send tampon_sk1 if for for receive_process while tampon_fullk true receive tampon_rKl for each V x a Lmi if Yij p 0 then Yij p lt in_HQi p Xij level HO j Kij p lt level_HQ Xi p 1 end if end for end while if level HQ current_priority 0 then queue_emptyi lt true else queue_emptyi lt false end if current_priority lt current_priority 1 algorithme 5 proc dures de communication 5 5 L algorithme complet L algorithme 6 d crit l initialisation des files d attente On notera par it un indicateur autorisant un processeur Pij initialise
43. mage label g contient les deux bassins versants associ s aux deux marqueurs originaux 3 2 24 Discussion Cet algorithme est rapide puisque chaque pixel n est trait qu une fois contrairement l algorithme classique qui repasse sur la totalit de l image chaque it ration Cet algorithme respecte galement les hi rarchies qui ont t mises en vidence pr c demment La mont e uniforme de l inondation est garantie par le fait qu une file de priorit donn e n est trait e qu partir du moment o les files de priorit sup rieure sont vides La hi rarchie de la propagation sur les plateaux est galement respect e du fait que les premiers voisins des points des bords descendants des plateaux sont tous trait s avant les deuxi mes voisins puisqu ils sont empil s les premiers Les deuxi mes voisins ne pourront tre empil s que lorsque les premiers voisins seront d pil s Cependant cet algorithme comme l algorithme classique bas sur des paississements direction par direction produit un biais puisqu il introduit un ordre de traitement arbitraire des pixels de m me priorit Ainsi dans l exemple pr c dent on aurait tr s bien pu empiler le jeton c avant le jeton b 3 3 Parall lisation de la FAH Comment acc l rer la construction de LPE en parall lisant la FAH Si on se r f re nouveau au processus d inondation qui constitue la d finition op ratoire de la LPE on constate que ce processus est la fois s
44. 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 La 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 un
45. mptyi indicateur positionn true par le processeur Pi lorsque la file d attente qu il a finie de traiter est vide 40 Tableau 1 notations Le traitement ex cut par chaque processeur sur sa file d attente locale est d crit l algorithme 1 Les notations utilis es sont pr cis es dans le Tableau 1 La proc dure send_ process est d taill e dans la section 4 traitement nb dep lt for iin 1 to nb dep do lt out HQ current_priority level_HQ current_priority lt level_HQ current_priority 1 for each V p a Lmij if Yij p 0 then Yij p lt in HO dp _ level HO j Kij p lt level HO j Kij p 1 end if end for call for if level 0 then lt true else queue_empty lt false end if current_priority lt current_priority 1 algorithme 1 traitement 5 3 Synchronisation Nous avons vu que le probl me pos par le traitement parall le de la FAH tait celui de la synchronisation des processeurs Autrement dit lorsque les processeurs ont termin de traiter leurs files d attente locales de priorit k il faut pouvoir d terminer cette terminaison pour r activer tous les processeurs afin qu ils traitent leur file d attente de priorit k 1 ou n
46. n de ces diff rentes approches dans l environnement de d veloppement Ptolemy Cet environnement d velopp par l Universit de Berkeley permet de valider la fonctionnalit d algorithmes 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 GO 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 Minimum 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 tout moment de l inondation les diff rents lacs d
47. nier champ d application qu elle a su montrer son efficacit la LPE se pr te bien aux techniques de segmentation hi rarchique Les r gions obtenues par un premier niveau de segmentation peuvent tre trait es nouveau par LPE afin de rassembler les r gions homologues Cependant c t de ces ind niables qualit s qui expliquent que ses domaines d utilisation ne cessent de s tendre elle pr sente quelques inconv nients au premier rang desquels se situe sa relative lenteur coupl e certains pi ges li s sa mise en oeuvre algorithmique Ces difficult s ont amen depuis d j quelques ann es le CMM a s int resser des am liorations d algorithmes qui ont permis des gains de vitesse d un facteur 100 par rapport aux implantations initiales Ces gains ne sont malheureusement pas encore suffisant si l on envisage l emploi de la LPE dans les traitements temps r el C est pourquoi le CMM en collaboration avec THOMSON CSF OPTRONIQUE s efforce dans le cadre d un contrat financ par la DGA DRET contrat N 95 520 de d finir des algorithmiques et des architectures parall les qui permettrait d atteindre des vitesses de traitement beaucoup plus grandes Ce rapport interm diaire d crit les travaux de nature algorithmique qui ont t entrepris dans le cadre de ce contrat Ces travaux s efforcent de d finir de nouvelles approches parall les partir d algorithmes existant d j en particulier les files d attente hi r
48. ocesseurs m moire FAH distribu e m moire FAH distribu e m moire FAH distribu e m moire LABEL partag e m moire LABEL distribu e m moire LABEL partag e m moire NG dupliqu e m moire NG distribu e m moire NG dupliqu e Figure 22 Les diff rentes parall lisations envisag es Quelque soit la solution adopt e il faut r soudre les trois probl mes suivants e synchronisation inter processeur sur le niveau de gris des pixels trait s e synchronisation inter processeur sur la distance g od sique pour un niveau de gris donn e changes des pixels des bords dans le cas lt un processeur par imagette gt ou dans le cas R partition uniforme des pixels empil s sur n processeurs Les changes de pixels sont sp cifiques chaque architecture En revanche le contr le inter processeur en vue de respecter la double hi rarchie est commun aux trois architectures Voyons d s maintenant en quoi il consiste 4 2 1 2 Contr les inter processeur Nous avons vu que la n cessit de respecter la hi rarchie des niveaux de gris et la distance g od sique l int rieur des plateaux impose un contr le global sur l ensemble des processeurs Un processeur ne peut passer au niveau de gris suivant que si e sa file d attente courante est vide e les files d attentes courantes de tous les autres processeurs sont galement vides Soit x le nombre de pixels situ s dans la file d attente
49. oire 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 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 OUTILS de la Morph Math Marqueurs Fonction Partie intelligente Modification d homotopie Segmentation
50. on 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 d 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 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
51. processeurs sont utilis s pour changer seulement deux pixels entre les deux processeurs 35 lt gt processeur Figure 30 maille d interconnexion des processeurs Pour viter d avoir un lien pour changer seulement deux pixels nous avons envisag d tudier une architecture utilisant seulement 4 liens inter processeur faudra alors d terminer une m thode pour changer les pixels situ s aux angles des imagettes au travers des 4 liens restants 4 3 8 Contraintes Afin d tre assur que cette architecture soit utilis e au maximum de ces performances il faut que les processeurs soient actifs en m me temps le plus souvent possible Pour cela on doit avoir qui r partition des marqueurs sur l ensemble de l image 4 4 Un processeur par marqueur 4 4 1 Pr sentation Un sch ma de cette architecture est donn e dans la Figure 31 36 m moire processeur NG associ au Se label k memoire FAH m moire processeur NG m moire TS m moire LABEL FAH m moire processeur NG associ au label 2 m moire FAH Figure 31 architecture issue de la parall lisation par marqueur La m moire LABEL est partag e entre les processeurs car e chaque processeur n a pas d espace d adressage pr d fini comme dans la solution un processeur par imagette e chaque processeur lit et cr
52. r ses files d attentes locales L indicateur end_init est positionn true lorsque le processeur a termin son tape d initialisation On notera par M et N les longueurs des cot s des imagettes L algorithme 7 regroupe l ensemble des algorithmes pr c dents 45 ini process end_initi lt false wait until initi true for pin i i M 1 j j N 1 do init_hq lt false if Y p 0 then for each V p if Y p 0 then init_hq lt true end if end for end if if init_hq true then in_HQ p Kij p level lt level 1 if for wait end_init lt true algorithme 6 initialisation call ini_process hq_process readyi lt true while start_nexti or start_samei or tampon_fullx1 true readyi lt false if start_nexti true then call traitement else if start_same true current_priority lt current_priority 1 call traitement else for each if tampon_fullx1 true call receive_process k l end if end for end if end if end while goto hq_process algorithme 7 traitement global 46 6 Conclusion L tude algorithmique de la parall lisation de la LPE effectu e partir de l algorithme de file d attente hi rarchique standard nous a permis de d gager les contraintes hi rarchiques que cette parall lisation doit absolument respecter sous peine d
53. rait s En effet durant l tape 3 ce sont les pixels de niveau de gris 10 et situ s une distance 1 du bord descendant qui taient d pil s Maintenant ce sont les pixels situ s une distance 2 du bord descendant Cette tape illustre la n cessit d un change entre processeur car il faut pouvoir propager le marqueur des pixels appartenant aux bords des imagettes vers les pixels voisins n appartenant pas la m me imagette Prenons par exemple le cas 31 du pixel dadresse 1 5 dans l imagette 1 Lorsque ce pixel est d pil son marqueur doit tre propag vers les pixels d adresses 1 1 et 2 1 de l imagette 2 Il faut galement empiler les adresses de ces pixels dans du processeur 2 afin qu il puisse son tour propager le marqueur 1 Nous verrons dans la suite de ce chapitre les solutions qui s offrent nous et plus particuli rement celle que nous avons choisie Propagation tape 5 les pixels de niveau de gris 10 empil s dans la FAH du processeur 2 ont d clench son activit Il propage alors son tour le marqueur 1 sur le plateau de niveau de gris 10 Les tapes suivantes suivent le m me principe que ces 5 premi res tapes Nous ne les avons donc pas d crites 4 3 4 Choix du partage de l image Quel type de d coupage faut il envisager horizontal vertical ou en imagettes Pour partager l image nous avons deux solutions e selon une matrice carr e e bandes horizontale
54. rme de ZPE zone de partage des eaux car la fronti re entre les bassins versants n est pas d finie sur les pixels mais passe entre eux dans la zone entre les pixels Dans la deuxi me variante les fronti res sont mat rialis es par certains pixels de l image On ne s est int ress dans cette tude qu la premi re variante ZPE L alsgorithme de LPE FAH comprend deux phases une phase d initialisation et une phase de fonctionnement 3 2 2 1 L initialisation Une file d attente hi rarchique est cr e avec autant de niveaux de priorit qu il y a de niveaux de gris dans l image f Associ e cette FAH se trouvent deux m moires d images la premi re contient l image f C est donc par essence la m moire qui stocke les priorit s niveaux de gris des pixels La deuxi me m moire est la m moire contenant les tiquettes des pixels trait s Elle est encore appel e m moire label et sera not e g Ces deux m moires sont initialis es au d but du processus La m moire image ne sera pas modifi e en cours de traitement elle est en lecture seule tandis que la m moire label sera lue pour alimenter la FAH et crite au cours du traitement pour mettre jour les tiquettes C est elle qui contiendra les bassins versants tiquet s la fin de la proc dure La est initialis e en stockant dans les files d attente respectives les jetons correspondant aux pixels tiquet s dans l image g ou plus simplement ceci afin
55. s ou verticales Ces deux types de partage sont repr sent s dans la Figure 27 partage selon une matrice carr e partage en bandes horizontales partage en bandes verticales Figure 27 types de partage des images pour un m me nombre de processeurs 32 La diff rence essentielle entre ces deux types de partage est la longueur des bords en contact avec d autres imagettes Soit L et le nombre de lignes et de colonnes de l image de d part et N le nombre de processeurs Dans le cas g n ral imagette situ e au bord de l image globale le nombre de pixels appartenant aux bords d une imagette est e 2 K L N 4 dans le cas de la matrice carr e e 2 ou 2 L dans le cas respectivement du partage en bandes horizontales ou verticales Pour un nombre de processeurs sup rieur quatre le partage de l image selon une matrice carr e est pr f rable en ce qui concerne la quantit d changes de pixels Dans la suite de ce rapport nous avons consid r le cas du partage selon une matrice carr e car il est ensuite tr s facile de se ramener au cas du partage en bandes 4 3 5 Traitement des pixels appartenant aux bords des imagettes Reprenons le processus de traitement d un pixel voisin V du pixel d pil pc e obtention du label de V pour savoir s il est d j
56. seurs et viter d envoyer au processeur r cepteur les adresses des pixels voisins de c est l adresse de pc qui est envoy e et c est au processeur r cepteur de calculer les adresses des pixels voisins de pc qu il 33 doit tiqueter et empiler dans sa Ainsi les donn es envoy es dans une requ te sont e l adresse du pixel d pil pc le label de pc fronti res entre imagettes Figure 28 deux cas d change de pixels entre processeurs 4 3 6 Gestion de l change des pixels Nous avons envisag deux solutions pour effectuer les requ tes entre processeur e parinterruption e selon le principe de la bo te aux lettres La solution bas e sur des interruptions a deux inconv nients e lorsqu un processeur envoie une requ te il doit attendre d avoir l acquittement du processeur r cepteur pour effectuer sa requ te Cela implique des d lais suppl mentaires sur les temps de traitement e dans le cas d un partage de l image selon une matrice carr e il existe des configurations dans lesquelles les processeurs vont s attendre les uns les autres ce qui aboutit un dead lock Cette situation est repr sent e dans la Figure 29 Dans ce cas les processeurs vont s attendre les uns les autres Notons que type de bouclage n existe pas dans le cas d un partage de l image en bandes 34 regu te processeur Figure 29 configuration de requ te
57. stribu 5 1 Introduction L objet de ce chapitre est de d crire sous forme d algorithmes un traitement parall le distribu du processus d inondation par File d Attente Hi rarchique Chaque processeur traite une file d attente hi rarchique locale pour segmenter un sous ensemble de l image Ce chapitre est organis selon le plan suivant dans la section 1 nous pr sentons l algorithme de traitement ex cut par chaque processeur Les sections 2 et 3 d crivent les algorithmes de synchronisation et de communication L algorithme d initialisation des files d attente hi rarchiques locales est d crit dans la section 4 L algorithme complet est d crit dans la section 5 Pour l ensemble de ces algorithmes nous consid rons le cas g n ral d une matrice de processeurs Dans la suite on notera par Pij i e 0 1 1 j 0 J 1 un processeur de la matrice I J 5 2 Algorithme de traitement Sa 55 5 Xij p niveau de gris de p dans la sous image segmenter Xi Y p dans la sous image des labels y empiler x dans la file d attente de priorit du processeur Pij d piler de la file d attente de priorit du processeur level nombre d l ments dans la file d attente de priorit du processeur Pij espace d adressage du processeur queue_e
58. titue 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 v
59. urnes NGENE SEA Be NG UN NE PNGEN E NENEKA NG ENE EE Nan greng a KUN NG en 40 923 SYNCHRONISATION ee EE EE aa 41 KOR d ER KE e 43 44 9 91 ALGORITHME COMPLET 45 CONCLUSION PE A 47 TANNEXE E 47 1 Introduction La ligne de partage des eaux en abr g LPE est une transformation largement utilis e depuis une quinzaine d ann es en segmentation d image Elle pr sente par rapport aux techniques de segmentation concurrentes de nombreux avantages qui expliquent son succ s Parmi ces avantages on peut citer sans que cette liste soit exhaustive les caract ristiques suivantes c est une transformation facile comprendre travaillant directement sur l image sans passer dans le domaine spectral ou par des repr sentations complexes c est une transformation qui vient avec son mode d emploi La LPE permet en effet de s parer en deux tapes distinctes la t che de d signation des objets segmenter de la t che de segmentation et de d limitation proprement dite la LPE est une transformation non param trique n y nul besoin de fixer les valeurs de nombreux param tres pour la r aliser cette transformation s emploie aussi bien sur les images fixes que sur les s quences sur les images niveaux de gris que sur les images couleur ou multi spectrales sur les images 2D ou 3D C est en particulier dans ce der
Download Pdf Manuals
Related Search