Mode d'emploi
Contents
1. Kb ch 25 50324 gGESRSESSESERAHEGEN HERBESERGIE e ee de ss ses 1 ELT mima uaa prex O Serge BEUCHER Mines ParisTech DILATATIONS GEODESIQUES NUMERIQUES Soit f et g deux fonctions images teintes de gris g lt Consid rons les sections niveau h de f et de g La dilatation g od sique ensembliste de taille de chaque section au niveau h de 9 l int rieur de la section correspondante de f g n re sur g une dilatation g Le sous graphe de g est l ensemble des points du sous graphe de f qui sont reli s g par un chemin horizontal de longueur lt O Serge BEUCHER Mines ParisTech EROSIONS GEODESIQUES NUMERIQUES L rosion g od sique num rique de f par g avec g 2 f se d duit de la dilatation g od sique par la dualit engendr e par l inversion autour d une valeur pivot m g m Gel g Le r sultat est ind pendant de la valeur pivot m O Serge BEUCHER Mines ParisTech 24 O Serge BEUCHER Mines ParisTech UNE MACHINE OUTIL LA LIGNE DE PARTAGE DES EAUX LPE En MM la segmentation d image s articule autour d une transformation la ligne de partage des eaux 1979 L introduction de marqueurs a augment spectaculairement l efficacit de la LPE 1982 Cette transformation fait2. Fond gt LPE du sup des 9 a images invers AA v E 4 7 DAP e UN 2 S Cette LPE est une LPE contr l e par marqueurs les marqueurs de la LPE sont les marqueurs des gouttes O Serge BEUCHER Mines ParisTech 2 APPLICATIONS 7 LPE finale gauche La kl m me LPE superpos e aux diff rentes sections droite i 5 2 Pour trouver la meilleure section une LPE du gradient contr l e par marqueurs est r alis e sur chaque section avec le m me ensemble marqueur r sultat en bleu et le meilleur ajustement avec le a um contour pr c dent est d termin La section correspondante donne la coordonn e z de la goutte n Serge BEUCHER Mines ParisTech 2 APPLICATIONS 8 segmentation de voies de circulation Les marqueurs des voies sont obtenus gr ce un seuillage automatique Le marqueur du fond est le compl mentaire d une dilatation A partir d une s quence de n images f gt deux images sont g n r es La moyenne Xf i n La moyenne des diff rences absolues If Serge BEUCHER Mines ParisTech 3 APPLICATIONS 9 Extraction du marquage au sol par une transformation chapeau haut de forme Calcul de la fonction distance du marquage au sol entre les marqueurs des voies LPE de la fonction distance Serge BEUCHER Mines ParisTech APPLICATIONS 10 Segme
3. R it rer jusqu a idempotence Serge BEUCHER Mines ParisTech G CORRECTION DE LA QUASI DISTANCE Quasi distances brute et corrig e Image initiale Quasi distance brute Quasi distance corrig e O Serge BEUCHER Mines ParisTech 65 QUASI DISTANCES La quasi distance corrig e sur une image teintes de gris indique la taille des r gions relativement plates homog nes gt Marqueurs d une segmentation bas e sur la taille et la forme Les quasi distances sont calcul es la fois sur l image et son compl ment d e Sup des r sultats gt h sup d d Extraction des marqueurs maxima ou seuil e LPE de h Serge BEUCHER Mines ParisTech 66 N AVEC DES QUASI DISTANCES O Serge BEUCHER Mines ParisTech 67 AUTRE EXEMPLE Quasi distance Quasi distance de l image invers e O Serge BEUCHER Mines ParisTech nn AUTRE EXEMPLE 2 A OM ES er HHL gt LEE Marqueurs des r gions gauche EM se e LPE du sup des quasi distances re 4 4 852 en haut droite lt Les r gions en mouvement sont n d tect es en bas droite Ya ef EE M GRADIENT ET QUASI DISTANCE La quasi distance peut tre calcul e sur le gradient invers Une seule quasi distance est calcul e Hi rarchie des r gions bas e
4. partir du minimum m Au cours du remplissage de 1 un d bordement vers CB2 se produit S maintenant nous remplissons CB2 le premier d bordement s effectue vers Dans ce cas les d bordements cascades sont sym triques On peut donc supprimer la ligne de partage s parant et CB2 et r unir les lacs de et CB2 101 preserved WL CASCADES 2 WL 8 O Serge BEUCHER Mines ParisTech WL Si le processus d inondation est it r le flot envahit CB3 qui en retour lorsqu il est inond se d verse dans la r union des bassins et CB2 Ici encore les cascades sont sym triques et CB3 est rattach l inondation Etape par tape et parce que chaque fois les cascades sont sym triques tous les bassins versants num rot s de 1 6 sont r unis Mais quand l inondation se d verse dans la situation change 51 maintenant nous inondons CB7 la cascade n est plus sym trique On doit donc conserver la ligne de partage des eaux s parant CB7 de la r union des autres bassins versants 102 BV ARCS SIGNIFICATIFS RECONSTRUCTION WL 5 4 CAS Le processus pr c dent ne 7 3 9 fonctionne pas si part de n importe quel bassin Cependant d 227 remarque que l inondation finit par atteindre les BVs significatifs m m Fonction marqueur reconstruction La Sous bassins versants Les inondations successives g n re
5. c dente DK O Serge BEUCHER Mines ParisTech Phase DK non APPLICATIONS DETAILLEES 6 Les pixels appartenant au contours de la voie sont s lectionn es O Serge BEUCHER Mines ParisTech 82 Phase non APPLICATIONS DETAILLEES 6 et utilis s pour ajuster un mod le de volie O Serge BEUCHER Mines ParisTech 83 APPLICATIONS DETAILLEES 6 Phase II Le modele de voie EM ILL permet de g n rer un nouveau marqueur non O Serge BEUCHER Mines ParisTech Si APPLICATIONS DETAILLEES 6 Phase II S Si aucune erreur n est d tect e traitement de 3 l image suivante O Serge BEUCHER Mines ParisTech Phase non APPLICATIONS DETAILLEES 6 Le marqueur pr c dent est utilis pour segmenter l image courante O Serge BEUCHER Mines ParisTech 86 Phase DK non APPLICATIONS DETAILLEES 6 2 m i Le marqueur pr c dent est utilis pour segmenter l image courante O Serge BEUCHER Mines ParisTech 97 Phase non APPLICATIONS DETAILLEES 6 Et un nouvel ajustement du mod le de voie est r alis O Serge BEUCHER Mines ParisTech 88 APPLICATIONS DETAILLEES 6 Phase II Illustration du processus sur une s quence compl te mod le de chauss e trois voies Noto
6. d images de Berkeley O Serge BEUCHER Mines ParisTech 126 CONCLUSION METHODOLOGIE EVOLUTIVE M thodologie fructueuse Extension au monde Extension aux graphes e Nouveaux d veloppements r sidus Ces outils sont presque ais ment compr hensibles et pratiques n y a usuellement pas de changement d espace espace image e La boite outils s est enrichie de nouvelles transformations Les performances s am liorent spectaculairement e Nouveaux algorithmes en particulier pour les segmentations hi rarchiques Vitesse des algorithmes permettant du temps r el Nouveaux outils disponibles O Serge BEUCHER Mines ParisTech 127 BIBLIOGRAPHIE e S BEUCHER C LANTUEJOUL Use of watersheds in contour detection International Workshop on image processing real time edge and motion detection estimation Rennes Sept 1979 disponible en t l chargement S BEUCHER Segmentation d images et morphologie math matique Doctorate thesis Ecole des Mines de Paris Cahiers du centre de Morphologie Math matique Fascicule n 10 Juin 1990 disponible en t l chargement e F MEYER S BEUCHER Morphological segmentation Journal of Visual Communication and Image Representation 1 Vol 1 Oct 1990 e S BEUCHER F MEYER The Morphological approach of segmentation the watershed transformation In Dougherty E Editor Mathematical Morphology in Image Processing Marcel Dekker New
7. taille est proportionnelle taille du bloc O Serge BEUCHER Mines ParisTech SEGMENTATION DES BLOCS Les marqueurs extraits de la fonction granulometrique fournissent des germes pr cieux pour la segmentation par LPE contr l e par ces marqueurs des crit res de taille et de contraste peuvent tre m lang s e 8 4 v NS uU TA S b Nw E 8 A p We a L 7 ei 3 pi e P e e ms 2927 77 gt 4 E r lt Se dit AVIS f A t e A Phu 1 M 2 dee i SX Xa M P423 4 b 748 rh S z gt e 1 7 K a A lt e SZ 2 7 EL As AR Ae 5 i m Ca P gt d A 5 gt tes c DK S af O ad b ee A e Pa um d V A uy de dia 54 4 A P bs gt 2 n e ig A lt S gt a E a ki PF 3 277 L Serge BEUCHER Mines ParisTech Ger Des distances perch es apparaissent La quasi distance n est pas 1 Lipschitzienne On peut rendre la quasi distance 1 Lipschitzienne par un op rateur it ratif de descente des distances perch es En tout point x o 4 elq x gt l faire q x dal 1
8. d extrema minima maxima filtrage ouvertures et fermetures par reconstruction ligne de partage des eaux modification d homotopie cascades dl 5 RECONSTRUCTION GEODE ub 2 La reconstruction g od sique est capitale pour r aliser et comprendre la ligne de partage des eaux ut Une reconstruction duale peut galement tre d finie elle utilise les rosions v od siques O Serge BEUCHER Mines ParisTech al MODIFICATION D HOMOTOPIE Swamping Bas sur la reconstruction la modification d homotopie permet de construire une nouvelle fonction dont les minima correspondent HULL OUT Ensemble marqueur g 1 Une fonction marqueur 2 La reconstruction de h au est definie dessus de inf g h est h x 1 M r alis e Z may Sinon gt R fonction modifi e O Serge BEUCHER Mines ParisTech POSITION DES MARQUEURS Segmentation obtenue image de droite avec une LPE du gradient contr l e par marqueurs marqueurs gauche LPE attendue Quand les minima sont remplac s par des marqueurs il est crucial de contr ler la position de ces marqueurs LPE erron e Image apr s modification O Serge BEUCHER Mines ParisTech 43 POSITION DES MARQUEURS 2 Question f Sion remplace les minima originaux par des marqueurs o placer les ma
9. hi rarchique associ e la segmentation sS Reconstruction 108 O Serge BEUCHER Mines ParisTech Image initiale f et son gradient g So W g So o 5 N niveaux hi rarchiques avec S est difficile de choisir un bon niveau de hi rarchie D autres probl mes cruciaux apparaissent Serge BEUCHER Mines ParisTech 109 PROBLEMES AVEC LES CASCADES C est une approche non param trique L algortithme des cascades peut tre it r ce qui conduit de possibles niveaux sup rieurs de hi rarchie mais Un crit re d arr t n est pas disponible Les niveaux successifs de hi rarchie sont loin d tre pertinents Myopie aux hi rarchies de niveaux diff rents erreurs de 110 Serge BEUCHER Mines ParisTech PROBLEMES AVEC LES CASCADES C est une approche param trique L algortithme des cascades peut tre it r ce qui conduit de possibles niveaux sup rieurs de hi rarchie mais Un crit re d arr t n est pas disponible Les niveaux successifs de hi rarchie sont loin d tre pertinents Myopie aux hi rarchies de niveaux diff rents erreurs de 111 Serge BEUCHER Mines ParisTech PROBLEMES AVEC LES CASCADES C est une approche non param trique L algortithme des cascades peut tre it r qui conduit de possibles niveaux sup rieurs de hi rarchi
10. SEGMENTATION D IMAGE amp MORPHOLOGIE MARTHEMATIQUE Cours du Master OIV St Etienne Serge BEUCHER CMM Mines ParisTech Janvier 2010 Serge BEUCHER Mines ParisTech REMARQUES PRELIMINAIRES n y a pas de d finition g n rale de la segmentation d image L approche morphologique de la segmentation est pragmatique N anmoins cette approche propose une m thodologie de la segmentation un guide d utilisation des outils de la segmentation e est important de garder l esprit les diverses propri t s de ces outils pour viter quelques pi ges Leur implan tation doit tre aussi pr cise que possible pour garantir des r sultats de qualit O Serge BEUCHER Mines ParisTech DE QUOI SERA T IL QUESTION La ligne de partage des eaux l outil de segmentation en MM Definition description Comment la construire Biais probl mes inexactitudes e Comment segmenter avec la LPE L id e initiale Pourquoi cela ne marche pas bien La LPE contr l e par marqueurs La bo te outils de segmentation et son manuel EXEMPLES d utilisation D APPLICATIONS Outils anciens et r cents e Segmentation hi rarchique L algorithme des cascades L algorithme P Mais avant cela rappel de morphologie math matique Serge BEUCHER Mines ParisTech RAPPELS DE MORPHOLOGIE La morphologie math matique c est Une
11. York 1992 disponible en telechargement S BEUCHER Watershed hierarchical segmentation and waterfall algorithm Proc Mathematical Morphology and its Applications to Image Processing Fontainebleau Sept 1994 Jean Serra and Pierre Soille Eds Kluwer Ac Publ Nld 1994 pp 69 76 e S BEUCHER Transformations r siduelles en Morphologie Num rique Note interne CMM n 04 04 MM Mars 2004 disponible en t l chargement e S BEUCHER MARCOTEGUL P algorithm a dramatic enhancement of the waterfall transformation Web document September 2009 disponible en t l chargement O Serge BEUCHER Mines ParisTech 128 OUTILS LOGICIELS Diff rentes librairies logicielles existent pour pratiquer les outils morphologiques http www mamba image org MAMBA est une librairie multi plateformes Linux Windows distribu e sous licence libre X11 MIT Elle a t d velopp e par Nicolas en collaboration avec le CMM MAMBA est la suite libre du logiciel Micromorph Elle est crite en C et tourne sous Python Serge BEUCHER Mines ParisTech 129
12. assin versant chaque sommet est valu par la valuation de l arc d finie dans le gradient mosaique Dans cette repr sentation les arcs entourant le m me bassin versant sont adjacents Des arcs minimaux peuvent donc tre connect s bien que ce ne soit pas le cas dans le gradient mosaique comme illustr ci dessus les sommets en Jaune correspondent des arcs minimaux Serge BEUCHER Mines ParisTech 25 DEFINITION D UN GRAPHE LPE ASSOCIEE 2 Les contours les plus significatifs de l image mosa que correspondent ceux separant des r gions marqu es par des arcs minimaux Ils sont les lignes de partage des eaux dela LPE d finie sur le graphe pr c dent Inondation 1 tape 2 me tape deux BV 3 me tape premiers en bleu en bleu et vert Barrages en rouge Serge BEUCHER Mines ParisTech DEFINITION D UN LPE ASSOCIEE 3 Arcs du gradient mosa que correspondant aux lignes de partage des eaux 4 me tape LPE finale O Serge BEUCHER Mines ParisTech 97 D UN GRAPHE 3D A UN GRAPHE PLANAIRE Le graphe d fini pr c demment est un eraphe valu 3D pas facile manipuler BV Ce graphe peut tre transform en un graphe planaire gr ce la proc dure suivante e Un nouveau sommet est ajout l int rieur de chaque bassin versant Les ar tes pr c dentes sont remplac es par deux ar tes successives reliant l
13. contours sont l int rieur de maxima de l image hi rarchique Ces maxima sont alors eux m me r introduits Ils peuvent alors intervenir dans le classement des hi rarchies Serge BEUCHER Mines ParisTech 120 O Serge BEUCHER Mines ParisTech D O Serge BEUCHER Mines ParisTech i acera dla el G Y lt T Ly R P O Serge BEUCHER Mines ParisTech HU 4 C d E T rr rl 1 gt pg WA Ll T Len 7 T ru A E Pz SI ud di n LEA T nu r ma mme 1 1 n Gel AR a 1 Em Serge BEUCHER Mines ParisTech eT SCT M WER m T D or ru 1 E DE O Serge BEUCHER Mines ParisTech PERSPECTIVES LIEES L ALGORITHME P L algorithme P est un algorithme auto bloquant et non param trique e Une caract ristique remarquable l algorithme P est sa capacit s parer les formes du fond Cette caract ristique fait de l algorithme un outil puissant de perception de structures Gestalt Travaux actuels entre autres Explication du r le de l algorithme P en relation avec certains m canismes de perception ancrage articulation Probl me de la comparaison des r sultats pour le moment elle reste tr s subjective Utilisation de la base de segmentation
14. e mais Un crit re d arr t n est pas disponible Les niveaux successifs de hi rarchie sont loin d tre pertinents Myopie aux hi rarchies de niveaux diff rents erreurs de 1 112 Serge BEUCHER Mines ParisTech PROBLEMES AVEC LES CASCADES C est une approche non param trique L algortithme des cascades peut tre it r qui conduit de possibles niveaux sup rieurs de hi rarchie mais Un crit re d arr t n est pas disponible Les niveaux successifs de hi rarchie sont loin d tre pertinents Myopie aux hi rarchies de niveaux diff rents erreurs de 1 113 Serge BEUCHER Mines ParisTech PROBLEMES AVEC LES CASCADES C est une approche non param trique L algortithme des cascades peut tre it r ce qui conduit de possibles niveaux sup rieurs de hi rarchie mais Un crit re d arr t n est pas disponible Les niveaux successifs de hi rarchie sont loin d tre pertinents Myopie aux hi rarchies de niveaux diff rents erreurs de 114 Serge BEUCHER Mines ParisTech MYOPIE DES CASCADES Image hi rarchique h en rouge En gris les contours qui sont limin s par l algorithme des cascades Trois diff rents types de contours supprim s apparaissent 1 Contours dont l altitude est sup rieure ou gale UR 2 Contours dont l altitude est inf rie
15. e s lectionn es les marqueurs et une LPE contr l e par ces marqueurs peut tre r alis e Les images gradient sont souvent bruit es et contiennent un grand nombre de minima Chaque minimum g n re un bassin versant dans la LPE Initial image O Serge BEUCHER Mines ParisTech 3 EXEMPLE DE LIGNE DE PARTAGE DES EAUX CONTROLEE PAR MARQUEURS segmentation de route Y I d d i d ar gt radient Za Y 4 ios SUPR FI A Image originale marqueurs Z LPE contr l e par marqueurs du gradient 38 LPE CONTROLEE PAR MARQUEURS ALGORITHMES e Inondation niveau par niveau A di 27 5 M ensemble marqueur LPE W SKIZ W Z 1 U UM 3 2 a Cet algorithme est plus simple Vei que l algorithme classique il n y ul a d a d L at ei De Ia FC Wei eg E EC L a pas de d tection de minima Files d attentes hi rarchiques Un jeton au niveau 1 lt niveau courant peut appara tre Dans ce cas 1l est trait comme un jeton au niveau jJ la file de niveau n existant plus Avec la LPE contr l e par marqueurs le d bordement est la r gle et non plus l exception O Serge BEUCHER Mines ParisTech 39 RECONSTRUCTION GEODESIQUE La reconstruction g od sique est largement utilis e en morphologie math matique d tection
16. es sommets originaux en passant par le nouveau sommet La valuation du nouveau sommet est donn e min v Ou les vij sont les valuations des arcs entourant le bassin versant O Serge BEUCHER Mines ParisTech 79 L image hi rarchique Une image nomm e image hi rarchique peut tre construite partir du graphe planaire Les bassins versants du gradient mosa que sont remplis avec des valeurs de gris correspondant aux valuations des nouveaux sommets ajout s La LPE de l image hi rarchique fournit le niveau de hi rarchie sup rieur avec quelques restrictions image hi rarchique O Serge BEUCHER Mines ParisTech dd ZONES DE PREMIER ZPD Appel es aussi improprement zones selles Les ZPD n ont rien de commun avec les zones selles classiques Ce n est pas une notion locale et comme la LPE il n y a aucun moyen de savoir a priori si un point donn appartient ou non une ZPD APE a Premier d bordement e s Notion de sous bassin versant C est la partie du bassin versant inond e avant le premier d bordement par la ZPD la moins lev e O Serge BEUCHER Mines ParisTech 100 CASCADES Introduction mi 1 ITI f m 3 2 WL 5 61 7 3 9 1 f WL Serge BEUCHER Mines ParisTech Consid rons la fonction f et sa LPE Les diff rents bassins versants sont num rot s de 1 9 Consid rons l inondation
17. l algorithme classique SKIZ avec des paississements en rotation L usage d l ments structurants en e rotation dans le SKIZ g n re une inondation des plateaux non isotrope files d attente hi rarchiques ordre a priori d fini dans la file Les Jetons appartenant la m me pile devraient tre trait s en m me temps LPE bas e sur des graphes La plupart des algorithmes de LPE sont biais s O Serge BEUCHER Mines ParisTech d BIAIS ET INEXACTITUDES AU SUJET DE LA LPE Pour diverses raisons complexit vitesse de traitement paresse les algorithmes de LPE sans biais sont rarement utilis s KS X e Comparaison entre une LPE exacte gauche et le r sultat d un algorithme classique cause de ces biais LPE n est pas UNIQUE elle devrait l tre Ces biais peuvent avoir de spectaculaires cons quences pour les approches hi rarchiques bas es sur la comparaison de bassins versants adjacents O Serge BEUCHER Mines ParisTech Be d o C d d 2A Plateau O Serge BEUCHER Mines ParisTech BIAIS ET INEXACTITUDES AU SUJET DE LA LPE 2 La ligne de partage des eaux n est pas locale En particulier elle n est pas li e des structures locales lignes de cr te escarpement La LPE n est pas un concept LOCAL Vous ne pouvez pas avec la seule connaissance locale du voisinage d un point r pondre la que
18. l image mosaique L PE du gradient Pour chaque minimum du gradient d terminer la valeur de gris corres pondante Remplir le bassin versant avec cette valeur Minima du gradient O Serge BEUCHER Mines ParisTech 02 SUR SEGMENTATION PERCEPTION DES IMAGES Une illustration simple utilisant une image mosa que En d pit du fait que l image soit sur segment e la tache blanche se d tache ais ment du fond parce que simultan ment les fronti res entre les r gions l int rieur de la tache et les fronti res l int rieur du fond sont moins contrast es que les fronti res qui s parent la tache du fond La tache comme le fond sont marqu s par des fronti res avec un contraste minimal Serge BEUCHER Mines ParisTech 93 DEFINITION D UN GRAPHE Arcs de hauteur minimale Dans l image mosa que chaque arc s pare deux bassins versants et La valuation Vi de l arc est donn e par Minimum V 18 78 1 o etg sont les valeurs de gris dans les bassins versants Un arc c est dit minimal si sa valuation est inf rieure celles des autres arcs entourant Cb et Minimum Serge BEUCHER Mines ParisTech DEFINITION D UN GRAPHE ET LPE ASSOCIEE D finition d un nouveau graphe ses sommets correspondent aux arcs du gradient mosaique ses ar tes joignent tous les arcs entourant le m me b
19. le du gradient mosaique par les ZPD minimales Image gradient mosaique Image hi rarchique Image des cascades O Serge BEUCHER Mines ParisTech 105 SEGMENTATION HIERARCHIQUE EXEMPLE LE M ctr a b J A Lt Fur a VE i bu das vis qa ACT ales LB Doi d M ag et rca s E d Dr Bares LPE initiale Premier niveau de hi rarchie Image originale 106 EXEMPLES D APPLICATION Liz juste une LPE au dessus de la LPE xa CARCER e Yo SES P ler e AI Leick n e vA os Wu A m EL CN d CAL a REA L Xu s CE PEE DOSE incus RAT ti moe E aA ei LSU erus e HAL Re ADEM GL Ma LCD SECH dd RE up E OUT D IE S a dr UU TES v MAT 145276 x Ge tr F DM i5 d DAR M 027 E SC WEI SR uU EUR ARE CO segmentation hi rarchique produit un nouveau bassin versant en vert qui peut tre utilis comme marqueur de la route Le marqueur ext rieur peut alors tre choisi parmi les autres bassins versants significatifs 107 USAGE DES CASCADES Protocole On part d une LPE valu e initiale s Un processus it ratif fournit les segmentations hi rarchiques successives S s w h o h est l image
20. limin s Ces contours sont l int rieur de maxima de l image hi rarchique Ces maxima sont alors eux m me r introduits 15 peuvent alors intervenir dans le classement des hi rarchies Serge BEUCHER Mines ParisTech 118 LIMITATIONS ET ALGORITHME Dernier niveau JAMAIS vide Proc dure auto bloquante Lorsque des maxima de l image hi rarchique apparaissent la LPE les fait dispara tre transform e semi homotopique Ils ne contribuent plus la gen se des hi rarchies L algorithme P Une variante un bogue de l algorithme standard consiste comparer la hauteur des contours de s au lieu de s e R introduction de contours d j limin s Ces contours sont l int rieur de maxima de l image hi rarchique Ces maxima sont alors eux m me r introduits 15 peuvent alors intervenir dans le classement des hi rarchies Serge BEUCHER Mines ParisTech 119 LIMITATIONS ET ALGORITHME Dernier niveau JAMAIS vide Proc dure auto bloquante Lorsque des maxima de l image hi rarchique apparaissent la LPE les fait dispara tre transform e semi homotopique Ils ne contribuent plus la gen se des hi rarchies R sultat final de l algorithme standard L algorithme P Une variante un bogue de l algorithme standard consiste comparer la hauteur des contours de s au lieu de s e R introduction de contours d j limin s Ces
21. m thodologie de traitement d images bas e sur des concepts ensemblistes Des briques de base op rateurs l mentaires Un assemblage des op rateurs produisant des op rateurs de plus en plus complexes Un contexte math matique vari Un ensemble d outils d analyse d images applicables dans de nombreux domaines Des librairies de traitement d images r unissant ces deux fonctionnalit s bo te outils et mode d emploi de la MM O Serge BEUCHER Mines ParisTech LES BRIQUES ELEMENTAIRES Les objets d tude sont les ensembles XCE La morphologie math matique les d crit en associant tout un ensemble test B muni d une origine et appel l ment structurant Deux types d v nements peuvent tre test s lorsque l l ment structurant B balaie l espace E L l ment structurant B coupe t il l ensemble X gt DILATATION L l ment structurant B est il inclus dans l ensemble X EROSION Serge BEUCHER Mines ParisTech El ment structurant Dilatation O Serge BEUCHER Mines ParisTech El ment structurant Erosion O Serge BEUCHER Mines ParisTech EXTENSION AUX FONCTIONS Toute fonction num rique f sur un ensemble E peut tre consid r e de mani re quivalente comme une pile d ensembles d croissants Chaque ensemble est la section du sous graphe de f par le plan de cote X 2 lt gt f x sup xe Kell Pour toute fonctio
22. n Azu D Ka 7 Fonction Empilement d ensembles Ensembles Fonction Fonction gt Ensembles Ensembles gt Fonction Serge BEUCHER Mines ParisTech Intensit 60 gt Dilatation 50 2 Original 40 d Erosion l structurant 0 2 0 40 Echantillon Serge BEUCHER Mines ParisTech ELABORATION COMPLEXES De nombreux op rateurs complexes peuvent tre construits par assemblage d op rateurs de base et appliqu s sur des images binaires niveaux de gris couleur en 2D 3D 4D sur des images en mouvement Ouvertures fermetures filtres Transformations en Tout ou Rien HMT paississements amincissements squelettes Op rateurs de contraste Op rateurs r siduels Op rateurs de segmentation Etc O Serge BEUCHER Mines ParisTech PROPRIETES DES TRANSFORMATIONS e Croissance XcY gt y X cylY e Extensivit anti extensivit x cw X e Idempotence v v X wev Xx 2v x O Serge BEUCHER Mines ParisTech 11 COMPOSANTES CONNEXES Ensemble connexe Un espace topologique X est connexe s il n est pas la r union de deux ouverts non vides disjoints ou de deux ferm s non vides disjoints Ensemble connexe par arcs u 8 Un ensemble X est connexe par arcs si et seulement si tout couple de points de X est reli par un chemin Une partie Y de E e
23. ns que malgr son apparente complexit cette phase est plus rapide que la phase I pas de segmentation hi rarchique O Serge BEUCHER Mines ParisTech 89 non SEGMENTATION HIERARCHIQUE CASCADES Probl mes non r solus Il n est pas toujours possible d viter la sur segmentation l aide d une LPE contr l e par marqueurs car il n est pas toujours possible de trouver de bons marqueurs et ou de bons crit res de segmentation D autres approches de la segmentation qui ne sont pas bas es sur une s lection a priori des marqueurs peut donc tre utile Diff rents algorithmes existent Ils ont tous pour but de d finir une hi rarchie de segmentations Hi rarchie bas e sur des valeurs d extinction Hi rarchie bas e sur les cascades Hi rarchie bas e sur des empilements O Serge BEUCHER Mines ParisTech d LIGNE DE PARTAGE DES EAUX VALUEE LPE Valu e La LPE d une fonction g est un ensemble W g La LPE valu e est la fonction d finie sur W et gale g en chaque point de W 2 Initial image Gradient g O Serge BEUCHER Mines ParisTech E H SEH E P E gt ur RENT Az ipt Tz CSS cues L A don ihe t P E D LE t PO t x FES Fn 4 4 RS eun Je py 2 GA ZS Do S h MERE Eh EI LA r CHA r 4 t 91 IMAGE MOSAIQUE ET SON GRADIENT Construction de
24. nt les sous bassins versants associ s chaque BV inondation juste avant le d bordement par la ZPD Zones selles Cette construction peut tre r alis e directement par une reconstruction duale de la fonction initiale par les ZPD O Serge BEUCHER Mines ParisTech 103 RECONSTRUCTION ET IMAGE HIERARCHIQUE Au lieu d utiliser les ZPD difficiles mettre en vidence l ensemble des lignes de partage des eaux peut tre utilis Le r sultat sera identique car la ZPD est la r gion bordant le bassin versant l altitude la plus basse f fonction initiale d finissons g x f x si et seulement si x appartient aux lignes de partage de f g x max sinon e h R g r sultat de la reconstruction duale de f par g encore appel e image hi rarchique e W h LPE de h g n re la segmentation hi rarchique de niveau sup rieur Lower catchment basins Quand f est une LPE valu e cette image hi rarchique est la m me que celle d finie pr c demment O Serge BEUCHER Mines ParisTech 104 CASCADES ET IMAGES MOSAIOUES Dans ce cas l approche hi rarchique et l approche par les cascades sont identiques L algorithme des cascades est la g n ralisation n importe quelle fonction de l approche hi rarchique La valuation minimale du bassin versant correspond la hauteur de la ZPD minimale La valuation produit un r sultat identique la reconstruction dua
25. ntations 3D bas es sur les fonctions distance Mousse de polyester fi O Serge BEUCHER Mines ParisTech APPLICATIONS 11 Segmentations 3D bas es sur les gradients Image IRM 3D du cerveau Serge BEUCHER Mines ParisTech 58 CRITERES BASES SUR DES RESIDUS NUMERIQUES Partant de deux suites de transformations V et avec 7 B C on d finit deux op rateurs La transformation r siduelle 5 up 7 icl e Sa fonction associ e 0 arg max w p 4 Vi _ est appel ouvert ultime 4 q est la fonction granulometrique 47 1 1 qest appel e quasi distance O Serge BEUCHER Mines ParisTech OUVERT ULTIME ENSEMBLISTE Fonction associ e l ouvert ultime d un ensemble Ouvert ultime num rique et fonction associ e O Serge BEUCHER Mines ParisTech pu OUVERT ULTIME FONCTION GRANULOMETRIQUE E 1 e Re F E 46 d i a Fa i i d Rochers en T En tout point x q x est gal l unit pr s au rayon du plus cylindre significatif Fonction granulometrique Serge BEUCHER Mines ParisTech GENERATION DES MARQUEURS Chaque seuil de la fonction eranulometrique q est rod par un disque de taille k k lt 1 Cette op ration g n re des marqueurs des blocs dont la
26. on O Serge BEUCHER Mines ParisTech L Le projet PROMETHE APPLICATIONS DETAILLEES 4 5 A A Segmentation de route et d tection d obstacle Deux phases segmentation primaire de la route ou de la voie LPE hi rarchique Aucune information n est partag e entre les images de la s quence D finition d un mod le de route voie parfois tr s l mentaire et utilisation de ce mod le pour construire des marqueurs utilis s dans la segmentation de l image suivante 74 APPLICATIONS DETAILLEES 5 Premi re Phase Image initiale O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 5 Premi re Phase Premi re segmentation O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 5 Premi re Phase Second niveau de hi rarchie et extraction du marqueur O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 5 Premi re Phase Segmentation de la voie MECI ma i compl te O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 5 Premi re Phase Segmentation finale O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 6 Phase II Image de la s quence DK NE l instant 1 non O Serge BEUCHER Mines ParisTech ER APPLICATIONS DETAILLEES 6 Phase II Segmentation de la voie par LPE marqueur non par l image pr
27. on distance Les maxima sont filtr s pour viter la sur segmentation des probl mes de parit 48 APPLICATIONS 2 Grains de nitrate d argent sur un film Probl me segmentation des grains m me superpos s E SH Masque des grains 2 me marqueur marqueur fond est ajout Ensemble marqueur final lers marqueurs maxima LPE de la fonction de la fonction distance distance Serge Mines ParisTech M APPLICATIONS 3 Gradient 4 1 F lt ei E E Va 2 20 e ja 4 m epo ur R sultat final Ligne de partage des eaux 50 O Serge BEUCHER Mines ParisTech APPLICATIONS 4 Restitution 3D de gouttes d eau partir d un hologramme Une image 3D d un a rosol brouillard artificiel est g n r e partir d un hologramme Les diverses sections de l image 3D sont obtenues avec une cam ra faible profondeur de champ n sections T trouver le meilleur contour e position z de chaque goutte volume O Serge BEUCHER Mines ParisTech 2 5 Crit re Sup des gradients gradients 5 DH D EE NE ME fall fal E Y Fonction modifi e arqueurs O Serge BEUCHER Mines ParisTech 32 APPLICATIONS 6 Marqueurs Gouttes maxima significatifs du sup filtr de toutes les sections
28. partie de la famille des op rateurs morphologiques et en particulier de la classe des transformations c od siques La LPE peut tre r alis e sur diverses structures ou repr sentations d images images 3D vid os graphes etc Cette capacit a g n r des solutions de segmentation hi rarchique 1990 D veloppements r cents nouveaux outils hi rarchiques nouveaux crit res de segmentation 2005 2007 uines ParisTech 26 L ALGORITHME CLASSIQUE DE L P E C est un processus d inondation Les sources d inondation sont les minima de la fonction Deux hi rarchies apparaissent e progression de l inondation avec l altitude processus s quenciel inondation des plateaux ou zones plates processus parall le Le r sultat est une partition de l image en bassins versants et en lignes de partage des eaux barrages Serge BEUCHER Mines ParisTech L ALGORITHME CLASSIQUE DE L P E 2 La transformation peut tre construite l aide des niveaux successifs Z de la fonction f j W m f a Les bassins versants au niveau 0 sont les minima ce niveau EE Minimum au niveau 1 1 Ligne de 1 18 2 VOL Um 9 SKIZ g od sique simule m Z R mu mu 2 ka O propagation de l inondation R est la reconstruction g od sique sans m lange des eaux O Serge BEUCHER Mines ParisTech 28 ALGORITHMES DE L P E
29. rqueurs pour s assurer que la LPE finale sera identique Zone selle Notion de sous bassin versant C est la partie du bassin versant inond e avant le premier d bordement par la zone selle la moins lev e Zones selle Solution les marqueurs doivent tre inclus dans les sous bassins versants Une correspondance biunivoque n est pas indispensable pourvu que les marqueurs inclus dans le m me bassin versant aient la m me tiquette Serge BEUCHER Mines ParisTech in LE PARADIGME DE LA SEGMENTATION Marqueurs M Fonctions 4 LPE f Serge BEUCHER Mines ParisTech QUELS e Crit res de contraste Gradient Transformation chapeau haut de forme Crit res de taille et de forme Fonction distance Fonction granulom trique Quasi distance Combinaison de plusieurs crit res O Serge BEUCHER Mines ParisTech FONCTION DISTANCE amp EROSION ULTIME La fonction distance est construite par empilement des rod s successifs de X L rod ultime correspond alors aux maxima de cette fonction distance L rod ultime est un op rateur r siduel O Serge BEUCHER Mines ParisTech APPLICATIONS Grains de caf La fonction distance de l ensemble est calcul e Cette fonction distance est invers e et sa LPE est construite L ensemble marqueur est constitu des maxima de la fonction distance La LPE est r alis e sur le support de la foncti
30. s a e E lim 16 Y dx Y Cet op rateur permet la reconstruction de toutes les composantes connexes de X marqu es par Y reconstruction de X par Y O Serge BEUCHER Mines ParisTech SKIZ GEODESIQUE Ensemble Y form de composantes connexes et inclus dans un espace g od sique X Zone d influence d une composante connexe ensemble des points de X une distance g od sique finie de la composante connexe et plus proche de celle ci que de tout autre composante connexe xe X d MES lt AE vj Serge BEUCHER Mines 21 1214561456128614 d FTTTETIETTEITTET Gua SE Ry EE ORC o m mo ORO ne ccn GLELLELLELZLELZELSE 4 TE 1 Ren rh hom d h d 1 SSIIIHFIEFIEFIETISEISPISTTEFTI FITITCIUPIEPIETUTTUTTT ibid idoneae doe b du d PRIBLIELIELAILIdJELRALEAIZSERIEL SES EE EE LAERPRZJERAE dm d bcl EELER ETC d b D dl PTR TTH Er Tes en gen ge g AA SL oo eo el LR EA BEREARAGEAL LELSULSULELLELU FErTENTErTTET 1 gt ALISREISESI 1 7 E D DE K LZELSELSU PFETITEETTETT een send
31. st connexe par arcs si et seulement si tout couple de points de Y est reli par un chemin restant dans Y Composante connexe La plus grande partie connexe d un ensemble X contenant un point x s appelle composante connexe de x dans X tre connect d finit une relation d quivalence TRANSFORMATIONS Une transformation w est homotopique si l ensemble de d part X et d arriv e Y w X sont homotopes c est dire s il existe une transformation bicontinue pour passer de l un l autre telle que chaque composante connexe de X contient le m me nombre de trous que son transform Y chaque trou de X contient le m me nombre de composantes connexes que son transform L homotopie d crit l organisation des composantes connexes et des trous entre eux ZONES D INFLUENCE SKIZ X ensemble form de composantes connexes X Zone d influence Z X de A ensemble des points plus proches de X que de toute autre composante connexe de z X x V j zi X al X Le SKIZ peut tre construit l aide d paississements O Serge BEUCHER Mines ParisTech LES GEODESIQUES En MM les l ments structurants peuvent tre d finis de diff rentes mani res Par leur g om trie e fa on explicite liste de points l aide d une distance Z m M d z y lt Trivial lorsqu on
32. stion Ce point appartient il une ligne de partage des eaux O Serge BEUCHER Mines ParisTech 24 BIAIS ET INEXACTITUDES AU SUJET DE LPE 3 L inondation est elle toujours un ph nom ne ascendant En d autres termes quand l inondation est la hauteur h est il vrai que TOUS les points une altitude inf rieure ont t inond s La r ponse est NON Contre exemple la boutonni re 33 TR m non Inond e In 4 m 4 barrage m etape suivante 2 Serge BEUCHER Mines ParisTech USAGE M LIGNE DE PARTAGE DES EAUX La ligne de partage des eaux est utilis e en segmentation e Segmentation d images fonction La LPE du module du 0 gradient correspond aux contours des objets gradient g e Segmentation d ensemble D coupage d objets en une union d objets convexes l aide de la LPE de la fonction distance O Serge BEUCHER Mines ParisTech a LE GRADIENT RAPPEL g f f B f D autres gradients morphologiques demi gradients peuvent galement tre d finis g f f O B g f f B f Gradients pais g f f B Gradients r gularis s O Serge BEUCHER Mines ParisTech LPE CONTROLEE PAR MARQUEURS La LPE du gradient est sur segmente e Pour viter cette sur segmentation d e de nombreuses sources d inondation seules certaines d entre elles peuvent tr
33. sur leur contraste realatif comme dans l algorithme des cascades La forme des r gions est prise en compte fermeture des r gions pas totalement ferm es O Serge BEUCHER Mines ParisTech bs APPLICATIONS DETAILLEES Fractures de clivage dans des images MEB d acier Pen V DES OUR LES x lt h Km i ba p Sr m ou y E E E Premi re LPE Barrages communs aux deux LPE E be i LE E d i Fonction contraste Seconde LPE O Serge BEUCHER Mines ParisTech 1 APPLICATIONS DETA AT E p d En 4 s F i vi D los d D E w H i 1 5 E E B X 75 a mal R EN 1 ke EN 3 D L r E ke 3 A kad e dc ik H 1 M E L E gt b d k H 3 zl de 4 CT 62 d Eh o uh as Marqueurs de la Azimuts de la Paire st r oscopique premi re image fonction distance N 4 et migrent selon la plus 4 X grande pente pour donner les nouveaux marqueurs en vert 72 O Serge BEUCHER Mines ParisTech APPLICATIONS DETAILLEES 3 A droite contours de facettes sur la premi re image et leurs homologues sur la seconde image Ci dessous le d placement d une facette qui peut tre mesur permettant ainsi le calcul de son l vati
34. ure h mais plus proche de l image hi rarchique h que de 0 3 Contours dont l altitude est proche de 0 Seule la suppression du dernier type de contour se justifie Serge BEUCHER Mines ParisTech 115 ES mn O Serge BEUCHER Mines ParisTech LIMITATIONS ET ALGORITHME Dernier niveau JAMAIS vide Proc dure auto bloquante Lorsque des maxima de l image hi rarchique apparaissent la LPE les fait dispara tre transform e semi homotopique Ils ne contribuent plus la gen se des hi rarchies L algorithme P Une variante un bogue de l algorithme standard consiste comparer la hauteur des contours de s au lieu de s e R introduction de contours d j limin s Ces contours sont l int rieur de maxima de l image hi rarchique Ces maxima sont alors eux m me r introduits Ils peuvent alors intervenir dans le classement des hi rarchies Serge BEUCHER Mines ParisTech 117 LIMITATIONS ET ALGORITHME Dernier niveau JAMAIS vide Proc dure auto bloquante Lorsque des maxima de l image hi rarchique apparaissent la LPE les fait dispara tre transform e semi homotopique Ils ne contribuent plus la gen se des hi rarchies L algorithme P Une variante un bogue de l algorithme standard consiste comparer la hauteur des contours de s au lieu de s e R introduction de contours d j
35. utilise la distance euclidienne Beaucoup plus int ressant lorsqu on utilise une distance non euclidienne g od sique O Serge BEUCHER Mines ParisTech CHEMIN amp DISTANCE SIL MS Si X est un espace topologique et si x et y sont deux points de X on appelle chemin d origine x et d extr mit y toute application continue y 0 1 gt E telle que y 0 x et y 1 y La distance g od sique dy E x E est d finie dans l espace g od sique X par dy x y Inf des longueurs des chemins d extr mit s x et y inclus dans X d x y oo si aucun chemin n existe X lC d x z 4 BOULES GEODESIQUES L introduction d une distance Bx 1 z g od sique permet de d finir la notion de boule g od sique 2 dx Z y lt Quand le rayon augmente la fronti re des boules dessine un front de propagation dans le m dium X Pour un rayon donn les boules B peuvent s interpr ter comme H des l ments structurants dont la forme varie de place en place O Serge BEUCHER Mines ParisTech EES Samu EE CEE E E E E EEE E EEE DEER Serge BEUCHER Mines ParisTech Serge BEUCHER Mines ParisTech RECONSTRUCTION GEODESIQUE It ration de dilatation
Download Pdf Manuals
Related Search