La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Informations
Publié par | Thesee |
Nombre de lectures | 63 |
Langue | Français |
Poids de l'ouvrage | 6 Mo |
Extrait
AVERTISSEMENT
Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.
Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.
➢ Contact SCD Nancy 1 : theses.sciences@scd.uhp-nancy.fr
LIENS
Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm Departement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
UFR Sciences et Technologies
Etude des courbes discretes :
applications en analyse d’images
THESE
presentee et soutenue publiquement le
pour l’obtention du
Doctorat de l’universite Henri Poincare { Nancy 1
(specialite informatique)
par
Thanh Phuong Nguyen
Composition du jury
Rapporteurs : Jean Pierre Reveilles, LAIC, Professeur emerite, Universite Clermont-Ferrand 1
Eric Andres, SIC, Professeur, Universite de Poitiers
Examinateurs : Philippe Even, LORIA, Professeur, Universite Nancy I
Laurent Wendling, LIPADE, Professeur, Universite Paris V
David Coeurjolly, LIRIS, Charge de recherche (HDR), CNRS
Directrice de
Isabelle Debled-Rennesson, LORIA, Ma^ tre de conferences (HDR), Universite Nancy I
these :
Laboratoire Lorrain de Recherche en Informatique et ses Applications | UMR 7503Mis en page avec la classe thloria.Remerciements
Les remerciements...
iiiA mes parents, ma femme et mon fils.
iiiivTable des matières
Introduction 1
Chapitre 1 Notions de base 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Espace discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Discrétisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Les primitives discrètes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Droite discrète 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.2 Droite 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.3 Segment flou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.4 Etude de l’algorithme de reconnaissance d’un segment flou . . . . . . . . . 19
1.6.5 Segment flou 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.6 Cercle discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.6.7 Plan discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.8 Morceau flou de plan discret . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Chapitre 2 Estimation des propriétés locales 33
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Estimation de la courbure . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.2 de la torsion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 Evolution d’un segment flou d’épaisseur . . . . . . . . . . . . . . . . . . . . . . 42
2.3.1 Maintenance de l’enveloppe convexe . . . . . . . . . . . . . . . . . . . . . 42
2.3.2 Détermination de l’épaisseur de l’enveloppe convexe . . . . . . . . . . . . 44
2.4 Segment flou maximal d’épaisseur . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.4.1 Notion de segment flou maximal . . . . . . . . . . . . . . . . . . . . . . . 45
vTable des matières
2.4.2 Une propriété importante de la suite des segments flous maximaux d’une
courbe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.4.3 Détermination de la suite des segments flous maximaux d’une courbe . . . 45
2.5 Courbure discrète d’épaisseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5.2 Estimation de la courbure d’épaisseur en chaque point C de C . . . . . 47k
2.6 Torsion discrète d’épaisseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.6.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.6.2 Torsion discrète . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.7 Expérimentations et comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.7.1 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.7.2 Comparaisons avec les méthodes existantes . . . . . . . . . . . . . . . . . 57
2.8 Conclusions et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Chapitre 3 Détection de points dominants et représentation polygonale 63
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.1 Les méthodes de détection de points dominants . . . . . . . . . . . . . . . 64
3.2.2 Les approches multi-échelle, multi-épaisseur . . . . . . . . . . . . . . . . . 68
3.3 Critères d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.1 Les critères existants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.2 Un nouveau critère alternatif d’évaluation pour les courbes bruitées . . . . 69
3.4 Détection de points dominants avec un paramètre d’épaisseur . . . . . . . . . . 72
3.4.1 Points dominants et région de support (ROS) . . . . . . . . . . . . . . . . 72
3.4.2 Relation entre les points dominants et la séquence de segments flous maxi-
maux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.4.3 Algorithme proposé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.4.4 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4.5 Discussion sur le nouveau critère d’évaluation . . . . . . . . . . . . . . . . 86
3.5 Approches multi-épaisseurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.1 Uneméthodemulti-épaisseurpourlareprésentationpolygonaledescourbes
bruitées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.2 Méthode adaptative multi-échelle reposant sur une stratégie de découpage-
et-fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.3 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
viChapitre 4 Cercle discret et applications 103
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.2.1 Reconnaissance des cercles discrets . . . . . . . . . . . . . . . . . . . . . . 105
4.2.2 Mesure de circularité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.2.3 Décomposition d’une courbe en arcs et segments de droite . . . . . . . . . 107
4.3 Reconnaissance des cercles discrets . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.3.1 Représentation des arcs dans l’espace des tangentes . . . . . . . . . . . . 108
4.3.2 Propriétés d’un arc dans la représentation modifiée de l’espace des tangentes108
4.3.3 Détection des arcs/cercles discrets . . . . . . . . . . . . . . . . . . . . . . 111
4.3.4 Approximation de l’erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.3.5 Segmentation en arcs discrets . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.3.6 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.4 Segmentation d’une courbe bruitée en arcs discrets . . . . . . . . . . . . . . . . . 120
4.4.1 Détection du bruit non-supervisée . . . . . . . . . . . . . . . . . . . . . . 120
4.4.2 des arcs dans une courbe bruitée . . . . . . . . . . . . . . . . . 127
4.4.3 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.5 Décomposition d’une courbe en arcs et segments de droite . . . . . . . . . . . . . 133
4.5.1 Idée principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.5.2 Analyse des configurations . . . . . . . . . . . . . . . . . . . . . . .