[PDF] Lignes de partage des eaux discr`etes : théorie et application `a la

View - Download Lignes de partage des eaux discr`etes : théorie et application `a la

Previous PDF

Next PDF

>G A/, ?H@yjdd9jde ?iiTb,ff?HXb+B2M+2f?H@yjdd9jde

GB;M2 /2 T`i;2 /2b 2mt biQ+?biB[m2 T` Q`/`2b /2

T2`KmiiBQM

hQ +Bi2 i?Bb p2`bBQM, Ligne de partage des eaux stochastique par ordres de permutation

Olivier L

´ezoray

Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France olivier.lezoray@unicaen.fr R

´esum´e -La ligne de partage des eaux stochastique est une approche morphologique de la segmentation qui r´ep`ete l"application d"une LPE`a

partirdes

qui repose sur plusieurs ordres de permutation obtenus par des chemins Hamiltoniens sur graphe. Contrairement

`a la LPE stochastique classique, notre approche permet de prendre en compte n"importe quelles caract

´eristiques associ´ees aux pixels.

Abstract -The stochastic watershed is a morphological approach to segmentation that repeats the application of a seeded watershed from series

of uniform random markers to construct a probability density function. We propose an alternative approach that relies on several permutation

orderings obtained by Hamiltonian path on graphs. In contrast to the classical stochastic watershed, our approach enables to take into account

any features associated to pixels. 1

Intr oduction

est une m ´ethode de morphologie math´ematique (MM) tr`es po- pulaire. Partant des minima du gradient, la LPE effectue une croissance de r

´egions sur une image de gradient. La LPE est

sensible au bruit et produit une forte sur-segmentation [1]. An- gulo et Jeulin on propos

´e une solution`a ce probl`eme par la LPE

stochastique [2]. Ils consid `erent, au lieu du gradient, une fonc- tion qui r ´eduit les minima`a l"int´erieur des objets et rehausse les contours. La LPE est alors r

´ep´et´ee avec comme germes des

marqueurs al ´eatoires uniformes. Les contours obtenus par les segmentations sont ensuite combin

´es pour construire une fonc-

tiondedensit de converger vers la probabilit

´e que les germes tombent des

deux c ˆot´es de chaque contour. Dans cet article nous proposons une approche alternative. Dans [2], chaque simulation est ef- fectu ´ee par des germes al´eatoires sur une image de gradient [3] qui ne tient compte que de diff

´erences de couleur qui ne permet

pas de consid ´erer des caract´eristiques de pixel de plus haut ni- veau, tel que des patchs. Nous pr

´esentons une approche pour

construire une pdf qui peut consid

´erer n"importe quelle ca-

ract ´eristique d´ecrivant un pixel. Notre approche repose sur plu- sieurs ordres de permutation obtenus par des chemins Hamilto- niens sur graphe [4]. Dans la section 2, nous pr

´esentons com-

ment construire de tels chemins Hamiltoniens stochastiques et construire une pdf. Dans la section 3, nous pr

´esentons quelques

r ´esultats et comparaisons. La derni`ere section conclut. 2

Ligne departagedeseauxstochastique

par ordres de permutation 2.1

Notations

Nousconsid

´eronsledomaine

del"imagecommeungraphe G= (V;E)dont les noeudsV=fv1;:::;vmgsont les pixels et les ar ˆeteseij= (vi;vj)les connectent. Les images sont alorsrepr ´esent´ees comme des signaux sur graphes [5] qui associent un vecteur aux noeuds :f:V!Rn.`A chaque noeud est as- soci ´e un vecteurvi=f(vi), et on d´efinitT=fv1;;vmg avec la notationT[i] =vi. Le grapheGutilis´e pour repr´esenter une image peut ˆetre : i) Un graphe deB-adjacence (not´eGB) o `u chaque noeudviest connect´e`a ceux contenus dans un carr´e de taille(2B+ 1)(2B+ 1)autour devi. Un graphe grille en8-adjacence sera not´eG1. ii) Un graphe desK-plus proches voisins (not ´eGK) o`u chaque noeudviest connect´e`a sesKplus proches voisins (en terme de distance spectrale) parmi l"en- semble de tous les noeuds. Le premier type de graphe consid `ere uniquement la proximit

´e spatiale pour connecter les noeuds

alors que le second consid `ere uniquement la proximit´e spec- trale. 2.2

T reilliscomplets

Laconstructionclassiquedesop

´erateursalg´ebriquesmorpholo-

giques repose sur des treillis complets [6]. Un treillis complet (T;) est un ensemble non vide´equip´e d"une relation d"ordre total, tel que chaque sous-ensemble non videPdeTa une borne inf ´erieure^Pet une borne sup´erieure_P. Si la MM est bien d ´efinie pour les fonctions scalaires, il n"existe pas d"ex- tension g ´en´erale admise sur les vecteurs puisqu"il n"existe pas d"ordre naturel des vecteurs. Si de nombreuses approches ont et´e propos´ees pour les images couleur [7], tr`es peu traitent des patchs. Dans cet article, nous d

´efinissons la relation d"ordre

entre les vecteurs d"un ensembleTen utilisant lesh-ordres [8].

Cela correspond

`a d´efinir une transformation surjectivehde TversLo`uLest un treillis complet´equip´e de l"ordre total conditionnel [8]. Nous d

´esignons parhl"ordrehdonn´e par

h:T ! Letv!h(v);8(vi;vj)2 T T,vihvj, h(vi)h(vj). Il n"est alors plus n´ecessaire queTsoit un treillis complet, puisque l"ordre deTpeutˆetre induit surLau moyen deh. Lorsquehest bijective, cela correspond`a d´efinir une courbe de remplissage d"espace et nous utiliserons cette propri

´et´e dans la suite.

2.3Chemin Hamiltonien stochastique

Pour construire un treillis complet surT, nous construisons une courbe de remplissage d"espace sur un grapheGassoci´e`a l"image. Cela correspond `a la construction d"un chemin hamil- tonien sur l"image : un chemin qui passe par tous les sommets du graphe et qui traverse chaque sommet une seule fois. Cela revient `a d´efinir une permutation tri´eeP=PTdes vecteurs deTavecPune matrice de permutation de taillemm. Soit une permutation de l"ensemble d"indexJ=f1;;mg. Si (i) =j, alorsPij= 1et0sinon. La permutation induite est

Toute permutation n"est pas int

´eressante, et nous recherche-

rons une permutation lisse. Le caract `ere lisse d"un ensemble ordonn ´e est exprim´e par la variation totale de ses´el´ements kT k

TV=m1P

i=1kvivi+1k. La permutation optimale peut alors ˆetre obtenue en minimisantP= argminPkPT kTV. Ce probl `eme d"optimisation fournit une permutation telle que le chemin Hamiltonien correspondant est le plus court et

´equivaut

a la r´esolution du probl`eme du voyageur de commerce. Ce probl `eme peutˆetre r´esolu`a l"aide d"une version randomis´ee d"une heuristique de plus proches voisins pr

´esent´ee dans [9].

Cet algorithme part d"un sommet choisi al

´eatoirement, trouve

les deux sommets voisins inexplor

´es les plus proches et choi-

sit l"un d"eux au hasard. Ces deux choix al

´eatoires rendent

stochastique la permutation obtenue. Apr `es la construction de la permutation, nous d

´efinissons leh-ordre`a partir de la per-

mutation parh(vi) =(i). Partant d"un signal sur graphe f:V! T, une nouvelle repr´esentation est obtenue sous la forme d"une paire(I;P)avecI(vi) =(i).Pest l"en- semble desvitri´es (une palette) etIune image d"index. La

Figure 1 pr

´esente la construction d"un chemin Hamiltonien sur Le signal original sur graphefpeutˆetre directement recons- truit puisquef(vi) =P[I(vi)] =T[i] =vi. Il peutˆetre01 2021
23
2223
45
2425
6 2627
78
28
910
3029
11 367
1213
3132
1415
136
55
1617
37
1819
39

40414243

375

45475052

3334
5453

353638

59
60
44
6364
46
6667
4849
6970
51

717475

5657
76
58
7779
80
61
8182
62
120
259
83
65
8586
68

87888991

7273

939495

78

100101103

84
104
165
99
108
90
111

929697

116117

98
224
102

121123

105
124
106

125127

107110109

189

112113114115118119

139
161
122

142143144

126
145

128129130131132133

152
134

153154

135

155156

285

137138

249
140
160
366
141

162163164

146

166167

147148149150

170
151
171
284

157158159

179

182183184

168169

188

172173174175176177178

180181

200
241

201203

185186

204207

187
206
324
190

209210

191192

213

193194

214

195196197198199

218202

221222

205208211212

232

215216

237
217
266
219

239220

240
223

242245

225226

394
246

227228

248

229230231

250

233234235236

257
238
258

261260262

243244

263264

247
354
270
251

271272

quotesdbs_dbs35.pdfusesText_40

[PDF] comprendre un rapport d'expertise automobile

[PDF] ligne de partage des eaux traitement d'image

[PDF] le pianiste roman polanski

[PDF] relation intergénérationnelle sociologie

[PDF] intergénérationnel objectif

[PDF] famille intergénérationnelle définition

[PDF] les bienfaits de l'intergénérationnel

[PDF] solidarité intergénérationnelle sociologie

[PDF] qu'est ce que l'intergénérationnel

[PDF] les relations intergénérationnelles en france

[PDF] rapport jury agrégation philosophie 2017

[PDF] rapport jury agrégation philosophie 2015

[PDF] rapport jury agregation externe 2015

[PDF] rapports jury capes philosophie

[PDF] vecteur orthogonal ? une droite