Partitions et structures non hiérarchiques
67
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
67
pages
Français
Ebook
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partitions et structures non hi´erarchiques
Luc Brun
Groupe de Recherche en Informatique,
Image, Automatique et Instrumentation
de Caen (GREYC)
1/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Plan
1
Presentation1section.1 2Partitions1section.2
3Segmentation2section.3 4Structures G´eom´etriques3section.4 4L.1es
tableaux de labels3subsection.4.1 4L.2e codage par
plage4subsection.4.2 4L.3e codage par axe m´edian4subsection.4.3
4L.4es fronti`eres4subsection.4.4 5Structures Topologiques5section.5
5L.1es graphes simples5subsection.5.1 5L.2es graphes
duaux6subsection.5.2 5L.3es cartes combinatoires8subsection.5.3
2/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partition
◮ Une partition est d´efinie par la donn´ee d’un ensemble de
r´egions couvrant l’ensemble de l’image et disjointes 2 `a 2.
0 1 2 3 4 5
0
1P ={R ,...,R }1 n
2
∀i = j R ∩R =∅ 3i jFn 4P = R ,ii=1 5
3/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partitions et Topologie de Kovalevsky
◮ R`egle du label maximum : Soit l une fonction r´eelle d´efinie sur
toutes les cellules de dimension maximum.
′∀e∈ C dim(e)< dim l(e) = max l(e )max ′e ∈ St(e,C),
′dim(e ) = dimmax
◮ Exemple > > >
Sn{R ,...,R } ∂R1 n ii=1
4/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures ...
Voir
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partitions et structures non hi´erarchiques
Luc Brun
Groupe de Recherche en Informatique,
Image, Automatique et Instrumentation
de Caen (GREYC)
1/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Plan
1
Presentation1section.1 2Partitions1section.2
3Segmentation2section.3 4Structures G´eom´etriques3section.4 4L.1es
tableaux de labels3subsection.4.1 4L.2e codage par
plage4subsection.4.2 4L.3e codage par axe m´edian4subsection.4.3
4L.4es fronti`eres4subsection.4.4 5Structures Topologiques5section.5
5L.1es graphes simples5subsection.5.1 5L.2es graphes
duaux6subsection.5.2 5L.3es cartes combinatoires8subsection.5.3
2/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partition
◮ Une partition est d´efinie par la donn´ee d’un ensemble de
r´egions couvrant l’ensemble de l’image et disjointes 2 `a 2.
0 1 2 3 4 5
0
1P ={R ,...,R }1 n
2
∀i = j R ∩R =∅ 3i jFn 4P = R ,ii=1 5
3/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures Topologiques
Partitions et Topologie de Kovalevsky
◮ R`egle du label maximum : Soit l une fonction r´eelle d´efinie sur
toutes les cellules de dimension maximum.
′∀e∈ C dim(e)< dim l(e) = max l(e )max ′e ∈ St(e,C),
′dim(e ) = dimmax
◮ Exemple > > >
Sn{R ,...,R } ∂R1 n ii=1
4/32 Presentation
Partitions
Segmentation
Structures G´eom´etriques
Structures ...
Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC)
Luc Brun
32
Partitionsetstructuresnonhi´erarchiques
Plan
1 Presentation1section.1 2Partitions1section.2 3Segmentation2section.34StructuresGe´om´etriques3section.44L.e1s tableauxdelabels3subsection.4.14L.e2codagepar plage4subsection.4.24L.e3codageparaxem´edian4subsection.4.3 4L.4esfrontie`res4subsection.4.45StructuresTopologiques5section.5 5L.1esgraphessimples5subsection.5.15L.e2sgraphes duaux6subsection.5.25L.e3scartescombinatoires8subsection.5.3
P={R1 Rn} ∀i6=j Ri∩Rj=∅ P=Fin=1Ri
/33
Partition
◮bmeledadonn´eed’unensesenoe´dteinfilrapUnareptiti regionscouvrantl’ensembledel’imageetdisjointes2a`2. ´ 0 1 2 3 4 5 0 1 2 3 4 5
2
◮R`egebaludelmumixamluntloi:Sioctonefruefid´esni´enrleel toutes les cellules de dimension maximum.
∀e∈C dim(e)<dimmaxl(e) =xema′∈St(eC)l(e′) dim(e′) =dimmax
Partitions et Topologie de Kovalevsky
n Si=1∂Ri
◮Exemple >> >
{R1 Rn}
23/4
Structurationdesfonti`eres
∀e∈Cdim(e) = 0est un noeud⇔ |l(St(eC))| ≥3
◮niomal3sslebeuNo:dopnietdlnolt´’etoilecontientau diffe´rents.
0 1 2 3 4 5
0 1 2 3 4 5
◮rtneei`nteserelgnrosf/siltnlepeioumdmmaxiuitent:SegmeS deux noeuds.
5/32
Adjacence
2 segment
◮nestignorxe´atjdssnoDeudtnegatrme´le´sessteenacpaesllie frontie`resdedimension1(i.e.aumoinsunsegment). ◮s.iscastronsleseadectndaajostnioegetnsLr´es 0 1 2 3 4 5 0 1 2 3 4 5 0 0 1 1 2 2 3 3 4 4 5 5 1 segment
Composante connexe
◮Une composante connexe de la partition est un ensemble de re´gionsadjacentes(maisnonincluses)includansunere´gion de la partition. 0 1 2 3 4 5 0 1 ◮E emples :2 x3 4 5
0 1 2 3 4 5 0 1 2 3 4 5
/327PoiPnraiterestntamentatiotionsSegmoe´GserutcurtSntuuctrsSueiqtr´eeusgoqipoloerTs
Segmentation et Partitions ◮Segmentation:´Dfieinitno’dnupenoititraP={R1 Rn} v´erifiantuncertaincrite`re: ◮t´edn´eiog´eHomige´noahcereuq ∀i∈ {1 n}P(Ri) =vrai ◮nimisitaM´energie:iond’une P=argminP∈PE(P) ◮Partition binaire : trouver S minimisant : R∂)dλ h(S) =Sw(λ minRSw′(xy)dxdyRΩ−Sw′(xy)dxdy
23/8
Siw=w′= 1 et Ω =R2etaorvurealofmrde`tneiveralec, p´erim`etreminimaletdevolumemaximal(i.e.ledisque). Proble`memet´erieriqusipo. ´ ◮ . . .
PrenesesG´cturetrieom´tSuruqseseoTtcruPaontitansioitrtatnemgeSurtSnoitlopoqugies
Definition {R1 Rn}est une segmentation deIrrpa`artpoapnurctie`er d’homogeneit´ePssi : ´ ´ 1.{R1 Rn}forme une partition deI:I=Fni=1Ri 2.r´ensexennocsnoige∀i∈ {1 n}Riest connexe 3.om`gteohesen∀i∈ {1 n}P(Ri) =vrai 4.rcespropmalespouire´´tseixam ∀i∈ {1 n}2Rii6jda=RjjP(Ri∪Rj) =faux
Segmentation selon Horowitz
3/29
Segmentation et partitions ◮Les algorithmes de segmentation ont besoin : 1.d’extraire des informations d’une partition 2.de modifier celle-ci ◮reeignooisnrunuinformates:Toutete´muqirsnoioe´gfoInatrm ´ quipeutsed´eduireuniquementdelar´egion(sansfaire intervenir la partition). 1.melbEsnpixeedesunerlsd’m(noige´v,enneyoe,nciaar forme,. . .), 2.Appartenance d’un point, 3.`itn.ere..Fro ◮informations Topologiques : Toute information qui n’a de sens que dans le cadre d’une partition. 1.eentrederonti`ersn,xu´rgeoiF 2.,noieges´negr´nsioblemeseda`serenuajdatnec 3.mpcoesedscteanoslbmesnener´ansun,egioexisnoenesdscnul 4.coneosmpteannncoge´rinoiulcnutnaxe.e..
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1
1 1 1 1 1 1
Les tableaux de labels 0 1 2 3 4 5 0 1 2 3 4 5 ◮Avantages : ◮Extremement simple ˆ ◮edt´rijormfoines´gsnoitairte´moecA`csaeluaqmsea` ◮snt´vnoeinecnI ◮noite`eritnoedrfnf’imaorsdPa ◮Pas compacte ◮Remarque : Levels sets :sgn(φ(x)) : 2 labels.
1 1 1 1 1 1
0 0 0 0 0 0
/1231re`itnorfseLnaidesgaLeralpgapecedoem´earaxagepecodseuqtseLopoTigolabelsLelleabxdau´Goe´mteurtcruseructuresriquesStserPatitnotSsneSmgnePartitioentation
