La lecture en ligne est gratuite
Télécharger
PresentationParititnoSsgeemtntanSiouctrretu´esGe´moqirtSseucurtsToptureiqueologs/1
Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC)
Luc Brun
32
Partitionsetstructuresnonhi´erarchiques
eserPontitiarnPioatntutcuGsermoe´rte´egsSntmeioattrnSpologoqieusiquesStructuresT/223
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
serPrtPaioittaenontioligoTopuqseesStriquuresructserutcurte´moe´GengmSensStontita
P={R1    Rn} i6=j RiRj=P=Fin=1Ri
/33
Partition
bmeledadonn´eedunensesenoe´dteinlrapUnareptiti regionscouvrantlensembledelimageetdisjointes2a`2. ´ 0 1 2 3 4 5 0 1 2 3 4 5
2
enesPrsnoititraPnoitateSmgneatitnotSurcturesG´eom´etriseuqurtSrutcoTselopoqugies
R`egebaludelmumixamluntloi:Sioctonefrued´esni´enrleel toutes les cellules de dimension maximum.
eC dim(e)<dimmaxl(e) =xemaSt(eC)l(e) dim(e) =dimmax
Partitions et Topologie de Kovalevsky
n Si=1Ri
Exemple >> >
{R1    Rn}
23/4
meegatnttitisSonerute´GsSnoicurttaoiPnraPerestnsrtqimoe´rtcueuSssToptureiqueolog
Structurationdesfonti`eres
eCdim(e) = 0est un noeud⇔ |l(St(eC))| ≥3
niomal3sslebeuNo:dopnietdlnolt´etoilecontientau die´rents.
0 1 2 3 4 5
0 1 2 3 4 5
rtneei`nteserelgnrosf/siltnlepeioumdmmaxiuitent:SegmeS deux noeuds.
5/32
2301452301taoiSnrtcuuterGsartitionsSegmentutcuTserlopoqigoom´etr´eueiqtrsSues45PresentationPnisulcnoiufaLsiondedeuxr´egiosndaajectnseseutioegr´neexnncon(23/6.)e
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:´DeinitnodnupenoititraP={R1    Rn} v´eriantuncertaincrite`re: t´edn´eiog´eHomige´noahcereuq i∈ {1    n}P(Ri) =vrainimisitaM´energie:iondune P=argminPPE(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
selopoqugiurctToesuqsetSuroe´mteircturesG´tionStruatnemgeSsnoititrPaontitaenesPr
Definition {R1    Rn}est une segmentation deIrrpa`artpoapnurctie`er dhomogeneit´ePssi : ´ ´ 1.{R1    Rn}forme une partition deI:I=Fni=1Ri 2.r´ensexennocsnoigei∈ {1    n}Riest connexe 3.om`gteoheseni∈ {1    n}P(Ri) =vrai 4.rcespropmalespouire´´tseixam i∈ {1    n}2Rii6jda=RjjP(RiRj) =faux
Segmentation selon Horowitz
3/29
opoTigolseuqserPetm´eoG´esurctruserutcurtSseuqiritioParttionentanotSatitmgnesneS013/2
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.melbEsnpixeedesunerlsdm(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`eritnoedrfnfimaorsdPa 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