Extraction et reconnaissance de primitives dans les façades de Paris à l'aide d'appariement de graphes, Extraction and recognition of object in the facades of Paris using graph matching

De
Publié par

Sous la direction de Sylvie Philipp-Foliguet, Philippe-Henri Gosselin, Frédéric Precioso
Thèse soutenue le 17 décembre 2010: Cergy Pontoise
Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement.
-Appariement inexact de graphe
-Graphe Relationnel Attribué
-Similarité de graphes
-Noyau sur graphe
-Fenêtres et façades
This last decade, modeling of 3D city became one of the challenges of multimedia search and an important focus in object recognition. In this thesis we are interested to locate various primitive, especially the windows, in the facades of Paris. At first, we present an analysis of the facades and windows properties. Then we propose an algorithm able to extract automatically window candidates. In a second part, we discuss about extraction and recognition primitives using graph matching of contours. Indeed an image of contours is readable by the human eye, which uses perceptual grouping and makes distinction between entities present in the scene. It is this mechanism that we have tried to replicate. The image is represented as a graph of adjacency of segments of contours, valued by information orientation and proximity to edge segments. For the inexact matching of graphs, we propose several variants of a new similarity based on sets of paths, able to group several contours and robust to scale changes. The similarity between paths takes into account the similarity of sets of segments of contours and the similarity of the regions defined by these paths. The selection of images from a database containing a particular object is done using a KNN or SVM classifier.
-Inexact graph matching
-Attributed Relational Graph
-Graph similarity
-Graph kernel
-Windows and facades
Source: http://www.theses.fr/2010CERG0497/document
Publié le : lundi 31 octobre 2011
Lecture(s) : 41
Nombre de pages : 150
Voir plus Voir moins

du
le
à
P
PRECIOSO
our
M.
obtenir
le
le
PHILIPP-F
grade
Co-directeur
de
Rapp
:
façades
Do
de

2010
en
de
Science
thèse
de
M.
l'Univ
Christine
ersité

de
BR
Cergy-P
THÈSE
on
P
toise
de
Sp
Souten
écialité

:
an
Sciences

et
Mme.
T

ec
F
hnologies
de
de
e-Henri
l'Information
thèse
et
Présiden
de
M.
la
LAMBER
Comm
M.
unication
Rapp
P
CORD
ar
les
Jean-Emman
de
uel
aris
HA
l'aide
UGEARD
similarités
Équip
graphes
e
ue

17
:
bre
Équip
dev
es
t
T
jury
raitemen
osé
t
:
de
Sylvie
l'Information
OLIGUET
et
de
Systèmes
M.
CNRS

UMR
Co-directeur
8051,
thèse
ENSEA,
Philipp
Univ
GOSSELIN
ersité
de
Cergy-P
Mme.
on
FERNANDEZ-MALOIGNE
toise
te
Titre
jury
de
P
la
k
thèse
T
:
orteur
Extraction

et
UN

orteur
de
Matthieu
primitiv
Examinateur
es
dansy
in
à
Cette
is
dernière


h
la
extract
mo
this
délisation
similarit
des

villes
of
3D
e
est
the
dev

en
mak
ue
presen
l'un
matc
des
to
enjeux
y
de
dans
la
d'appariemen

the
herc
in
he
arious
m
rst,
ultimédia
w
et
part,
un

axe
e,
imp
tities
ortan
e
t
segmen
en
to

sev
d'ob
to
jets.
et
Dans
segmen

paths.
thèse
using
nous
système
nous
hemins
sommes
last
in
b
téressés
m
à
ortan
lo
In

to
diéren
ecially
tes
P
primitiv
t
es,
ws
plus
an
particulièremen

t
ab
les
graph
fenêtres,
image
dans
the
les
p
façades
et
de
the
P
w
aris.
The
Dans
graph
un
tours,
premier
and
temps,
F
nous
w
présen
ts
tons
sets
une

analyse
The
des
tak
façades
y
et
tours
des
dened
diéren
images
tes
ob
propriétés
SVM
des
utilise
fenêtres.
v
Nous
des
en
par
déduisons

et
mo
prop

osons
one
ensuite
hallenges
un
timedia
algorithme
an

fo
d'ex-

traire
thesis
automatiquemen
in
t

des
e,
h
windo
yp

othèses
A
de
e
fenêtres.
analysis
Dans
and
une
erties.
deuxième
prop
partie,
able
nous
windo
ab
a
ordons
e
l'extraction
extraction
et
es
la
hing

Indeed
des

primitiv
b
es
uman
à
h
l'aide
grouping
d'appa-

riemen
een
t
t
de
It
graphes
hanism
de
ha

to
tours.
is
En
as
eet

une
of
image
alued
de
orien

ximit
tours
segmen
est
the
lisible
of
par
prop
l'o
v
eil
a
h
based
umain
paths,
qui
sev
eectue
and
un

group
y
emen
een
t
in
p
the

sets
et
of
distingue
the
les
the
en
y
tités

pré-
a
sen
a
tes
is
dans
KNN
la
Résumé
scène.
l'image
C'est
un

de

ote
que
partir
nous

a

v
l'algorithme
ons
t.

This
herc


deling
à
3D
repro
y
duire.
ecame
L'image
of
est

représen
of
tée
ul-
sous

la
and
forme
imp
d'un
t
graphe


ob
de

segmen
this
ts
w
de
are

terested
tours,
lo
v
v
alué
primitiv
par
esp
des
the
informations
ws,
d'orien
the
tation
of
et
aris.
de
t
pro
w
ximité
presen
des
an
segmen
of
ts

de
windo

prop
tours.
Then
P
e
our
ose
la
algorithm
mise
to
en


w
ondance
In
inexacte

des
w
graphes,
discuss
nous
out
prop
and
osons
primitiv
plusieurs
using
v
matc
arian
of
tes
tours.
d'une
an
nouv
of
elle
tours
similarité
readable
basée
y
sur
h
des
ey
ensem
whic
bles
uses
de


and
hemins
es
tracés
b
sur
w
les
en
graphes,
presen

in
d'eectuer
scene.
les
is
group

emen
that
ts
e
des
v

tried
tours
replicate.
et
image
ro-
re-
bustes
ted
aux
a

of
hangemen
of
ts
ts
d'éc

helle.
v
La
b
similarité
information
en
tation
tre
pro

y
hemins
edge
prend
ts.
en
or

inexact
la
hing
similarité
graphs,
des
e
ensem
ose
bles
eral
de
arian
segmen
of
ts
new
de
y

on
tours
of
et
able
la
group
similarité
eral
des
tours
régions
robust
dénies
scale
par
hanges.

similarit

b
hemins.
w
La
paths

es
des
to
images
t
d'une
similarit
base
of

of
tenan
ts
t

un
and
ob
similarit
jet
of
particulier
regions
s'eectue
b
à
these
l'aide
The
d'un
of

from
SVM
database
ou
taining
kpp
particular
v.

La
done
lo
a

or
des

ob
jets,
Régine,
et
ts
u
Je
mes
tiens
sert
à
t'in
remercier
:
en
Erbao
tout
Precioso
premier
question
lieu
m'on
Sylvie
breuses
Philipp-F
tours,
oliguet,
v
F
Thomas,

P
Precioso
même
et
de
Philipp
Je
e-Henri

Gosselin
a
qui
t
on
de
t
t

qui

ail
thèse.
tu
Duran
ouv
t
informatique,

Sh
3
Jean-
années,
Emman
ils
Ju-
on
p
t
rigolen
su
l'équip
orien

ter

mes
famille

mes
herc
t
hes
es
sur
thèse
de
Je
b
tophe
onnes
et
v
man
oies.
Clémen
Malgré
endan
des
te
emplois
ton
du
à
temps
sur
très


sur
hargés,
ma
ils
te
on
tique,
t
erso
trouv
vid
é
Alexis,
du
Ludo
temps
Jonathan,
à
Sylv
me
Da

A
p

our
tous
éc
nouv
hanger
qui
des
pas
idées
Je
et
p
redonner

des
F
p
our
etits
leur

pas
de
ts,
"b
eur...)
o
non-
ost".
qui
Je
oser
remercie
tu
les
ou
rapp

orteurs

de
thèse

plus
thèse
remercier

Audrey
Brun
héb
et
u
P


ainsi
k
Elise
Lam
qui
b

ert

p
Enn,
our
toi
la
herc
rapidité
ou
a
vraimen
v
tra
ec
y
laquelle
de
ils
des
on
que
t
des
lu

mon
ma
man
est

et
et
ondrai
l'in
plaisir.
térêt
blague
qu'ils
.bash_p
on
...)
t
Da
p
G.,
orté
uji,
à
Justine,
mon
Sonia,
tra

v
Christophe,
ail.
Guy
Merci
Auguste,
égalemen
ain,
t
uel,
aux
vid
autres
.,
mem
yman,
bres
lien,
du
Babar,
jury
et
qui
les
on
etits
t
eaux,


de
ne
juger
t

à
tra
blagues.
v
remercie
ail
e
:
édagogique
Christine
l'ENSEA,
F
hel
ernandez-Maloigne
et
et

Matthieu
p
Cord.
leur
Je
et
tiens
aide.
aussi
n'oublie
à
ma
remercier
(paren
tous
frère
les
so
mem
et
bres
amis
du
do
pro
ts
jet
aimen
iT
p
o
la
wns.
"alors
J'ai
trouv
eu
?"
plaisir
"ça
à
v
tra
ta
v
?",
ailler
quoi
au
ta
sein
?".
du
tiens
lab
particulièremen
oratoire
à
ETIS
Chris-
et
et
plus
qui
particuliè-
t
remen
ergé
t
souten
a
lors
v
la
ec
du
l'équip

e
que
MIDI.
Etienne,
Une
et
p
t
ensée
m'on
nostalgique
aussi
p
p
our
t
tous
nom
les
années.
do
je

remercie
ts

a

v
he
ec
nom
qui
qui
j'ai
téresse
partagé
t
de
mon
b
v
ons
(no
momen
aux
ts
graphes
(blagues,



ho
fenêtres).

he

si
resto
as
univ
questions
ersi-
le
taire,
ten
billard,
de
p
thèse,
ok
"fenêtre"
er,
grande
barb
erte
ecue,
je
fo
rép
otball,
a
ph
ec
ysique
Remerciemen
quan38
de
20
able
.
des
.
matières
Résultats
T
.
able
.
des
.
gures
.
v
.
Publications
.
1
.
1
Nev
Con
34
texte
.
et
.
motiv
tissage
ation
20
3
.
1.1
.
iT
.
o
.
wns
.
.
.
.
par
.
notre
.
.
.
limites
.
tours
.
2.2.1
.
.
.
ts
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
25
.
.
.
.
.
2.1.3.2
.
.
.
28
.
l'algorithme
.
.
.
.
.
30
3
.
1.2
A
La
.

.
d'ob
.
jets
.
et
.
l'indexation
p
d'
.
images
.
.
.
.
.
.
2.1.1.5
.
fenêtres
.
.
.
.
.
.
.
Conclusion
6
.
1.3
.
Notre
.
démarc
.
he
.
.
Notre
.
.
.
.
.
.
.
.
.
.
.
.
.
21
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
La
.
.
.
.
.
.
.
.
.
.
.
de
.
o
.
.
.
.
.
Comparaison
.
et
.
Lee
10
.
2
.
Analyse
.
et
.
représen
.
tation
Conclusion
des
notre
images
.
de
Graphe
façades
de
15
.
2.1
.

.
d'h
.
yp
et
othèses
.
de
.
fenêtres
.
.
.
.
.
.
T
.
oin
.
3D
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
.
Appren
.
des
.
.
.
.
15
.
2.1.1
.
Etat
.
de
.
l'art
.
.
2.1.1.6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.2
.
appro
.
he
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
.
2.1.1.1
2.1.3
A
.

.
ulation
.
et
.
histogrammes
.
des
.
gradien
.
ts
.
v
.
er-
.

.
et
.
horizon
.
taux
.
.
2.1.3.1
.
base
.
données
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
.

.
fenêtres
.
b
.
osting
16
.
2.1.1.2
.

.
de
.
manière
2.1.3.3

de
hique
algorithme
.
de
.
de
.
et
.
atia
.
.
.
.
.
.
.
.
16
.
2.1.1.3
.

.
de
.
fenêtres
.
basée
2.1.3.4
sur
et
un
de
mo
algorithme
dèle
.
impli-
.

2.2
de
Relationnel
forme
ttribué
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
.
Dénitions
.
notations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
.
2.1.1.4
i
Densité
des.
.
graphes
able
4.3.2
des
.
matières
prop
2.2.2
fenêtres
Notre
.
représen
.
tation
SVM
en
70
graphe
.
de
et

92
tours
.
.
y
.
aux
.
hemins
.
.
.
.
.
.
.
.
.
.
.
4.2.1
41
.
2.2.2.1
.
A
no
ttributs
.
de
.
sommet
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
prop
.
prop
.
.
.
y
.
70
.
.
.
des
42
similaires
2.2.2.2
.
A
d'in
ttributs
Appro
d'arête,
.
Relations
.
top
.
ologiques
.
.
.
.
.
.
graphes
.
T
.
Com
45
.
2.3
.
Conclusion
.
.
.
.
.
.
.
.
59
.
.
.
.
.
.
.
y
.
.
.
.
.
y
.
.
.
.
.
à
.
.
.
.
.
66
.
de
.
y
.
.
.
.
.
.
.
au
.
hemins
.
.
.
au
.
.
.
.
.
4.1.3
.
de
.
herc
46
de
3
dans
Etat
.
de
Région
l'art
.
:
.
appariemen
t
t
.
de
.
graphes
.
47
85
3.1
.
Appariemen
de
t
tal
de
.
graphe
.
(graph
.
matc
.
hing)
.
.
no
.
.
.
.
.
.
.
58
.
de
.
.
.
.
.
.
.
.
.
.
.
3.2.6
.
sur
.
.
49
.
3.1.1
.
Métho
.
des
.
exactes
.
.
No
.
graphes
.
.
.
.
.
.
.
.
.
.
.
3.2.7.1
.
sur
.
.
.
.
.
.
.
.
.
3.2.7.2
.
non
.
.
.
.
.
.
.
.
.
3.3
.
aste
.
.
.
.
49
.
3.1.2
.
Métho
.
des
Métho
inexactes
de
.
en
.
4.1
.
sur
.
.
.
.
.
.
.
.
.
.
.
.
.
No
.
graphes,
.
sur
.
.
.
.
.
.
.
No
.

.
.
.
.
.
.
.
.
.
.
51
:
3.1.2.1
yp

.
d'édition
4.2
.
de
.
des
.
tours
.
de
.
façades
.
.
.
.
.
80
.

.
.
.
.
.
.
.
81
.
he
.

.
gions
.
.
51
.
3.1.2.2
.
Métho
.
des
.
sp
.
ectrales

.
appren
.
.
.
4.3
.
hemins
.
au
.
.
.
.
.
.
.
Théorie
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
nouv
3.1.2.3
aux
Métho
.
des
.
à
.
no
95
y
.
aux
.
.
.
.
3.2.5
.
binaison
.
no
.
aux
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
59
.
No
.
aux
52

3.1.3
.
Discussions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.2.7
.
y
.
sur
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
60
.
No
52
aux
3.2

Les
.
no
.
y
.
aux
.
.
.
.
.
.
.
.
.
.
62
.
No
.
aux
.
dénis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
64
.
Séparateurs
.
V
.
Marge
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
54
4
3.2.1
des
No
osées
y

aux
similarité
de
tre
Mercer
69
.
No
.
au
.
graphes
.
osé
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1.1
.
y
.
sur
.
no
.
aux
.

.
.
54
.
3.2.2
.
Dénitions
.
.
.
.
.
.
4.1.2
.
y
.
sur
.
hemins
.
osé
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
72
.
Application
.

.
h
.
othèses
.
fenêtres
.
.
.
76
.

.
he
.
sous-graphes
.
dans
55
graphes
3.2.3

No
80
y
Extraction
aux
fenêtres
non
les
dénis
.
.
.
.
.
.
.
.
.
.
.
.
4.2.1.1
.
de
.
hemin
.
térêt
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2.1.2
.

.
mélangan
.
information
.
tours
.
ré-
.
.
57
.
3.2.3.1
.
Matrice
.
de
.
Gram
.
et
.
ensem
.
ble
.
de
.
données
.
.
.
.
.
.
4.2.1.3
.
des
.
par
57
tissage
3.2.3.2
.

.
de
89
Krein

.

.
et
.
y
.

.
.
.
.
.
.
.
.
.
.
.
.
.
4.3.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
58
.
3.2.4
.
No
.
y
.
aux
.
usuels
.
sur
.
v
93
ecteurs
Deux
.
eaux
.
y
.
sur
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ii
.
.dans
session
5.2.3
able
.
des
y
matières
.
4.4
105
Conclusions

.
hemins
.
.
.
111
.
.
.
.
.

.
5.2.2
.
d'images
.
5.2.2.2
.
.
.
des
.
.
.

.
.
.

.
.
.
.
.
ectiv
.
de
.
.
.
.
.
no
.
la
.
aluation
.
au
.
la
.
.
.
aluation
.
ort
.
.
96
.
5
.
Implémen
rapide
tation
.
et

résultats
.
99
111
5.1
.
Représen
.
tation
114
par
he
arbre
.
de
Conclusions

133
herc
Proto
he
ulation
.
.
.
.
.
.
.
.
.
aluation
.
aux
.
p
.
herc
.
5.2.2.1
.
p
.
no
.
.
.
aluation
.
des
.
.
.
.
99
5.2.2.3
5.1.1
notre
L'arbre
par
de
d'autres

.
herc
.
he
.
.
.
.
.
.
.
.
herc
.
l'aide
.

.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
Résultats
.

.
.
100
.
5.1.2
.
Application
.
de
p
l'algorithme
121
d'"év
T
aluation
5.2.1
et

séparation"
sim
sur
in
les
e
no
.
y
.
aux
.
sur
.

.
hemins
.
.
105
.
Ev
.
des
.
y
.
sur
.
hemins
.
our
.

.
he
.
107
.
Ev
.
des
.
ondérations
.
notre
.
y
.
.
.
107
100
Ev
5.1.2.1
de

taille
des

no
.
y
.
aux
.
.
.
.
107
.
Ev
.
de
.
no
.
au
.
rapp
.
à
.
métho
.
.
.
.
.
.
.
.
.
.
.
.
101
.
5.1.2.2
.
Notre
.
implémen
.
tation
.
.
109
.

.
he
.
à
.
de
.
de
.
hemins
.
.
.
.
.
5.2.3.1
.
de
.
hemins
.
.
.
.
.
.
102
.
5.2
.
Ev
.
aluation
.
.
5.2.3.2
.
de
.
hemins
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2.4
.
de
.
de
.
herc
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
115
.
et
.
ersp
.
es
.
Bibliographie
.
iii
.
.matières
T
iv
able
des

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi