THESE - seborga1.free.frseborga1.free.fr/TIPE/Autres/these.pdf · Département d’Electronique Faculté des Sciences de l’Ingénieur Université de Batna Pour l’obtention du

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIREMinistère de l’Enseignement Supérieur et de la Recherche Scientifique

THESEPrésentée au

Département d’ElectroniqueFaculté des Sciences de l’Ingénieur

Université de Batna

Pour l’obtention du diplôme deDoctorat Es-Sciences en Electronique Industrielle

Option : Contrôle

Par

BOUTARFA Abdelhalim

Thème

RECONNAISSANCE DE FORMES 3DPAR APPROCHE NEURONALE ASSOCIANT LA TRANSFORMEE DE HOUGH

EN ROBOTIQUE MOBILEAPPLICATION A LA PRODUCTIQUE

Soutenue le, / / 2006 devant le jury composé de :

Professeur Ameur Soltane Univ. Tizi-ouzou PrésidentProfesseur Bouguechal N-Eddine Univ. Batna RapporteurProfesseur Emptoz Hubert INSA de Lyon ExaminateurProfesseur Batouche Md.Chawki Univ. Constantine ExaminateurProfesseur Chikouche Djamel Univ. Sétif ExaminateurDocteur Slimane N-Eddine Univ. Batna ExaminateurDocteur Abdessemed Yacine Univ. Batna Invité

FOLIO ADMINISTRATIF

Nom : BOUTARFA Date de SoutenancePrénoms : AbdelhalimTITRE :

RECONNAISSANCE DE FORMES 3D PAR APPROCHENEURONALE ASSOCIANT LA TRANSFORMEE DE HOUGH

EN ROBOTIQUE MOBILEAPPLICATION A LA PRODUCTIQUE

Nature : Doctorat es-sciencesFormation doctorale : Electronique industrielleOption : Contrôle

RESUMELa problématique générale de cette recherche est l’extraction de caractéristiques

d’ensembles cohérents de primitives diverses, ainsi que la représentation adéquate de cesensembles. En robotique mobile et particulièrement en stéréovision, le calcul d’orientation desprimitives est une donnée importante dans le processus de modélisation du milieu dans destâches de localisation et de navigation, notre robot mobile évoluant dans un environnement debureau où d’atelier. L'objectif est de fournir des informations suffisamment pertinentes etconcises afin de faciliter les traitements ultérieurs notamment pour la reconnaissance d’objets.Deux aspects complémentaires sont explorés, d’une part par l’extraction et la représentationdes attributs en vue d’une reconnaissance des formes et d’autre part par une application enproductique basée sur le contrôle automatique de pièces manufacturées.

En effet et en amont nous proposons un système hybride de reconnaissance de formes 3Dmoyennant une approche neuromimétique associant la Transformée de Hough. Des testsvalident notre approche.

En aval, cette méthode porte sur une application en productique qui est l’inspectionautomatique d’objets comportant des surfaces complexes à partir de leur modèle CAO et dedonnées 3D provenant, soit d’un capteur télémétrique, soit d’une machine à mesurer.

Nous présentons d’abord un état de l’art complet et récent sur l’inspection visuelleautomatique. Nous sélectionnons deux modèles surfaciques : un modèle triangulé et unmodèle exact NURBS découpées, pour lesquels nous développons un calcul de distancepoint/modèle.

Nous détaillons ensuite comment obtenir les données 3D à partir d’images fournies par uncapteur télémétrique. Nous proposons une méthode de mise en correspondance généraleentre des données 3D et un modèle CAO, qui a l’avantage d’être robuste (jusqu’à 80% depoints parasites), automatique, et qui fonctionne quelque soit la position initiale des données etdu modèle. Nous avons exploité plusieurs applications à cette méthode, parmi lesquelles lareconnaissance de formes, mais surtout l’inspection automatique d’objets de forme complexe.

Nous présentons une méthode d’inspection de ce type d’objet, d’une part quantitative avecune approche globale et locale, et d’autre part qualitative utilisant différents procédés devisualisation que nous avons développés. A partir de ces outils, un opérateur ou un systèmerobotisé peut rapidement identifier des pièces défectueuses, ou une dérive du procédé defabrication, sur une ligne de production.

Mots Clés:Vision, Robotique mobile, Reconnaissance des formes, Réseaux de neuronesTransformée de Hough, , Segmentation, Appariement, Extraction de primitives,Optimisation, Contrôle dimensionnel , Inspection.

Laboratoires de recherches d’affiliation:

§ Laboratoire D’électronique Avancée (LEA), Université de Batna.§ Laboratoire de vision artificielle, Centre des technologies Avancées, Alger.§ Laboratoire de Reconnaissance des formes et Vision (RFV) au LIRIS, l'INSA de Lyon.§ Laboratoire d’Automatique Industrielle (LAI), l'INSA de Lyon.

Directeur de thèse : Professeur Bouguechal N, Directeur du LEA, Université de Batna.Président de jury : Professeur Ameur.S, Directeur du Lampa, Université de Tizi-ouzou.

Composition du jury :

M. Ameur Soltane Professeur Univ. Tizi-ouzou PrésidentM. Bouguechal N-Eddine Professeur Univ. Batna RapporteurM. Batouche Md.Chawki Professeur Univ. Constantine ExaminateurM. Chikouche Djamel Professeur Univ. Sétif ExaminateurM. Slimane N-Eddine Professeur Univ. Batna ExaminateurM. Abdessemed Yacine Docteur Univ. Batna Invité

i

Remerciements

Ce travail a été effectué dans le cadre d’une collaboration étroite de plusieurs années

avec :

• Le laboratoire d’électronique avancée de l’Université de Batna,

• Le laboratoire de Reconnaissance des Formes et vision RFV au LIRIS-CNRS à

l’INSA de Lyon,

• Le laboratoire de Vision Robotique et d’Intelligence Artificielle au Centre des

Technologies Avancées de Baba-Hassen à Alger.

Je tiens tout d’abord à remercier mon Directeur de thèse, Professeur Bouguechal

Noureddine pour l’intérêt qu’il a porté à mes travaux depuis mes débuts dans ce monde

fascinant de la recherche. Ses conseils m’ont été particulièrement précieux durant ma

vie scientifique dont il a assuré une direction motivante depuis plus d’une dizaine

d’années. Qu’il trouve ici toute ma reconnaissance et ma gratitude.

Je remercie vivement Professeur Ameur Soltane, Directeur de recherches du Lampa à

l’Université de Tizi-ouzou et associé à l’Université Paul Sabatier de Toulouse pour

m’avoir fait l’honneur de présider mon jury de thèse.

Je remercie également Messieurs Batouche Mohamed.Chawki, Professeur à l’Université

de Constantine, Chikouche Djamel, Professeur à l’Université de Sétif et Slimane

Noureddine, Maître de conférences à l’Université de Batna, pour l’intérêt qu’ils ont bien

voulu porter à mon travail en acceptant la lourde tâche d’examinateur. Merci infiniment

pour leurs regards critiques et pertinents.

Je voudrais exprimer ma reconnaissance au Professeur Hubert Emptoz, Directeur du

laboratoire de reconnaissance des formes et vision à l’INSA de LYON, pour l’accueil

qu’il m’a réservé au sein de son laboratoire, pour sa contribution scientifique, pour ses

encouragements et pour les remarques judicieuses dont il a fait part lors de la lecture de

ce manuscrit.

ii

Je remercie de même le Professeur Franck Lebourgeois du CNRS à l’INSA de LYON

pour les discussions constructives et enrichissantes qu’il m’a apportées et aussi pour

avoir été là dans les moments de doute.

Je tiens aussi à exprimer toute ma gratitude à Monsieur Achour Karim, Directeur de

recherches de la Division Productique-Robotique au Centre des Technologies Avancées

(CDTA) d’Alger, pour l’accueil chaleureux qu’il m’a prodigué et l’intérêt dont il m’a

témoigné en examinant tous mes travaux.

Mes vifs remerciements vont également au Docteur Abdessemed Yacine, Maître de

conférences à l’Université de Batna, par sa présence à ma soutenance en qualité de

membre invité et aussi pour ses judicieux conseils.

Que l’équipe Métrologie du CAST de l’INSA de Lyon et la société Hymarc (Ottawa)

soient également remerciées pour nous avoir fourni les pièces mécaniques utilisées dans

cette étude et pour nous avoir fourni les fichiers de points de mesure 3D de ces pièces.

Je tiens également à remercier tout particulièrement mes collègues du département

d’électronique pour l’amitié et le soutien qu’ils m’ont témoignés.

Je réserve mes derniers remerciements à toute ma famille pour leur dévouement, leurs

sacrifices et leur soutien indéfectible.

iii

Table des Matières

INTRODUCTION GENERALE.....................................................................................1

1 Historique ....................................................................................................................1

2 Problématique ..............................................................................................................2

3 Protocole d’investigations ............................................................................................5

4 Cadre et hypothèses de notre travail de recherche.........................................................6

5 Présentation de notre travail de recherche.....................................................................9

CHAPITRE 1

INTRODUCTION A LA RDF ET AUX RESEAUX DE NEURONES................11

1.1 Etat de l’art sur la RDF..............................................................................................11

1.1.1 Les deux grandes controverses.........................................................................13

1.1.2 Applications de la RDF....................................................................................14

1.2 Approche Neuronale .................................................................................................15

1.2.1 Introduction .....................................................................................................15

1.2.2 Caractéristiques architecturales d'un réseau neuronal .......................................19

1.2.3 Représentation de connaissances dans l’approche neuronale ............................23

1.2.4 Apprentissage connexionniste..........................................................................25

1.2.5 Avantages, inconvénients et applications des réseaux neuronaux ....................29

1.2.6 Applications de l'approche neuronale...............................................................31

I.3. Intérêt de l'hybridation ..............................................................................................32

I.4. Conclusion................................................................................................................33

CHAPITRE 2

LA TRANSFORMEE DE HOUGH ...........................................................................34

2.1 Etat de l’art ...............................................................................................................34

2.2 Principe de la Transformée de Hough........................................................................36

2.3 Dimension des paramètres de θ et ρ..........................................................................40

2.3.1 Champ de la dimension de θ ............................................................................40

2.3.2 Champ de dimension de ρ................................................................................41

iv

2.3.3 Propriétés de la Transformée de Hough ...........................................................42

2.4 Utilisation de la Transformée de Hough ....................................................................42

2.5 Implémentation de la Transformée de Hough ............................................................44

2.6 Etat de l’art : Evaluation en ligne d’Algorithmes de la TH.........................................49

2.6.1 Algorithme de H.Koshimizu et M.Numada ......................................................49

2.6.2 Algorithme de S.Tagzout et al........................................................................51

2.6.3 Algorithme proposé .........................................................................................52

2.7 Conclusion ................................................................................................................55

CHAPITRE 3

RECONNAISSANCE DE FORMES PAR APPROCHE HYBRIDE EN

ROBOTIQUE MOBILE...............................................................................................57

3.1 Robotique mobile : Etat de l’art.................................................................................57

3.2 Vision Stéréoscopique...............................................................................................58

3.3 Géométrie du système optique de stéréovision...........................................................59

3.4 Implémentation Neuronale ........................................................................................60

3.4.1. L’architecture du réseau..................................................................................60

3.4.2. La Règle Delta Généralisée..............................................................................62

3.4.3. Le momentum .................................................................................................62

3.5 Extraction des chaînes de points de contour...............................................................63

3.6 Application de la Transformée de Hough dans l’appariement des images ..................65

3.6.1 Algorithme d’appariement ...............................................................................66

3.6.2 Mise en correspondance par la modèle de Hopfield..........................................69

3.7 Résultats expérimentaux............................................................................................70

3.8 Discussion et Interprétation .......................................................................................76

3.9 Conclusion ................................................................................................................78

CHAPITRE 4

PRODUCTIQUE : CONTROLE AUTOMATIQUE DE PIECES

MANUFACTUREES .....................................................................................................80

4.1 Introduction...............................................................................................................80

4.2 Problématique ...........................................................................................................81

4.3 Etat de L’art ..............................................................................................................82

v

4.3.1 Planification de l’acquisition des images..........................................................83

4.3.2 Vérification automatique des tolérances...........................................................87

4.4 Sélection du bon modèle dans la base de données......................................................90

4.4.1 Les géons ........................................................................................................90

4.4.2 Représentation surfacique CAO – GÉONS ......................................................90

4.4.3 Extraction des géons de l’image d’illuminance ................................................90

4.4.4 Mémorisation associative.................................................................................91

4.5 Contrôle automatique ................................................................................................91

4.5.1 Le capteur 3D..................................................................................................91

4.5.2 La méthode de mise en registre........................................................................92

4.5.3 La segmentation des données 3D .....................................................................93

4.5.4 Calcul de la distance point 3D / NURBS..........................................................95

4.5.5 Propriétés géométriques locales .......................................................................95

4.6 L’inspection visuelle .................................................................................................97

4.7 Conclusion ..............................................................................................................100

CHAPITRE 5

APPLICATIONS .........................................................................................................101

5.1 Reconnaissance de formes.......................................................................................101

5.1.1 Polyèdres.......................................................................................................102

5.1.2 Supports ........................................................................................................103

5.2 Inspection d’objets industriels .................................................................................103

5.2.1 Procédés de visualisation ...............................................................................104

5.2.1.1 Coloration des triangles.....................................................................104

5.2.1.2 Carte de texture.................................................................................104

5.2.1.3 Tracé des segments d’erreur ..............................................................106

5.2.2 Exemples.......................................................................................................107

5.2.2.1 Polyèdre............................................................................................107

5.2.2.2 Plaque ...............................................................................................107

5.2.2.3 Support .............................................................................................108

5.2.2.4 Téléphone .........................................................................................116

5.2.2.5 IMS...................................................................................................117

5.2.2.6 Pièce C..............................................................................................118

vi

5.3 Préparation à la finition d’une pièce ébauchée .........................................................120

5.4 Conclusion ..............................................................................................................120

CONCLUSION GENERALE ET PERSPECTIVES..................................................122

1. Conclusion ................................................................................................................122

2. Contributions ............................................................................................................123

3. Perspectives ..............................................................................................................125

ANNEXES....................................................................................................................128

Annexe A : Conception des pièces .................................................................................128

Annexe B : Robot Mobile ATRV...................................................................................134

Annexe C : Robot Mobile ATRV...................................................................................134

1. L’impact des NTIC en vision industrielle.....................................................137

2. Le programme de contrôle automatisé..........................................................137

3. La maintenance préventive ..........................................................................140

4. L’exploitation des résultats ..........................................................................140

REFERENCES BIBLIOGRAPHIQUES....................................................................141

vii

Liste des Figures

Figure 1.1 Représentation simplifiée d'un neurone biologique....................................20

Figure 1.2 Neurone formel.........................................................................................20

Figure 1.3 Architectures de réseaux neuronaux ..........................................................22

Figure 1.4 Réseau à représentation locale...................................................................22

Figure 1.5 Exemple de codage semi distribué par micro-traits....................................22

Figure 1.6 Réseau à représentation distribué ..............................................................24

Figure 2.1 Structure pyramidale de la transformée de Hough hiérarchique .................36

Figure 2.2 Transformée de Hough..............................................................................37

Figure 2.3 Quantification du plan des paramètres (ab) ...............................................38

Figure 2.4 Paramétrage polaire d'une droite ...............................................................39

Figure 2.5 Quantification du plan des paramètres ) ...............................................39

Figure 2.6 Transformée de Hough..............................................................................40

Figure 2.7 Paramètres polaires de deux droites opposées ...........................................41

Figure 2.8 Le champ de la dimension de ρ .................................................................41

Figure 2.9 Le champ de la dimension de ρ .................................................................42

Figure 2.10 Le plan de Hough en relief ........................................................................43

Figure 2.11 Organigramme de la TH............................................................................45

Figure 2.12 Droites réelles et insignifiantes .................................................................46

Figure 2.13 Image en niveaux de gris...........................................................................46

Figure 2.14 Image contours .........................................................................................47

Figure 2.15 Images Résultats, tTr est le temps de traitement de la TH...........................48

Figure 3.1 Robot utilisant la stéréovision ...................................................................59

Figure 3.2 Image originale d’objets de formes cylindrique et polyédrique..................61

Figure 3.3 Image résultat : Fenêtre (5*5)...................................................................61

Figure 3.4 Image résultat : Fenêtre (3* 3)..................................................................61

Figure 3.5 Architecture du réseau ..............................................................................61

Figure 3.6 Image originale d’une scène d’intérieur de Laboratoire ............................64

Figure 3.7 Détection de contours par Deriche (α =1.5 ) .............................................64

viii

Figure 3.8 Tableau accumulateur ...............................................................................65

Figure 3.9 Construction de la fenêtre de recherche F (Si) ...........................................66

Figure 3.10 Contrainte de compatibilité entre les appariements....................................68

Figure 3.11 Cas de recouvrement entre deux segments de droites ................................68

Figure 3.12 Structure du Réseau de Hopfield ...............................................................69

Figure 3.13 La paire stéréo 3D Labo............................................................................72

Figure 3.14 La paire stéréo Ball ...................................................................................73

Figure 3.15 Couple stéréoscopique, images originales 3D Labo...................................73

Figure 3.16 Résultats de l’Algorithme appliqué sur l’image 3D gauche du Labo..........73

Figure 3.17 Résultats de l’Algorithme appliqué sur l’image 3D droite du Labo............74

Figure 3.18 Résultats de l’Algorithme appliqué sur des objets .....................................74

Figure 3.19 Taux de reconnaissance du classifieur hybride ..........................................75

Figure 3.20 Circuit FPGA réalisé.................................................................................75

Figure 3.21 Organigramme du processus de traitement ...............................................79

Figure 4.1 Architecture du projet ...............................................................................89

Figure 4.2 Triangulation optique qui utilise le principe d’auto-synchronisation..........92

Figure 4.3 Schéma fonctionnel de la segmentation.....................................................94

Figure 4.4 Fenêtre du menu principal.........................................................................97

Figure 4.5 Superposition du nuage de points et du modèle .........................................98

Figure 4.6 Surface 6 superposée au modèle...............................................................99

Figure 4.7 Exemple de rapports de contrôle sur la surface 6.......................................99

Figure 4.8 Variance en fonction de l’angle d’incidence..............................................99

Figure 5.1 Exemples de Texture Mapping................................................................105

Figure 5.2 Echelle de couleur...................................................................................108

Figure 5.3 Affichage des segments d’erreurs, Objet polyèdre...................................108

Figure 5.4 Objet polyèdre : Texture Mapping 1........................................................109

Figure 5.5 Objet polyèdre : Texture Mapping 2........................................................109

Figure 5.6 Visualisation de l’objet Plaque utilisant les triangles colorés ...................109

Figure 5.7 Visualisation de l’objet Plaque utilisant les segments colorés ..................110

Figure 5.8 Représentation avec triangles colorés de l’objet Support .........................111

Figure 5.9 Représentation par segments colorés .......................................................112

Figure 5.10 Objet Support : Texture Mapping 1.........................................................113

ix

Figure 5.11 Objet Support : Texture Mapping 2.........................................................113

Figure 5.12 Visualisation des erreurs avec les triangles colorés..................................114

Figure 5.13 Visualisation des segments : Inspection du perçage de droite .................114

Figure 5.14 Objet support : Mise en correspondance points 3D/modèle CAO STL.....115

Figure 5.15 Téléphone : Mise en Cor. de l’image 3D avec le modèle CAO STL ........116

Figure 5.16 Visualisation avec triangles colorés.........................................................116

Figure 5.17 Téléphone : Mise en Cor. des points 3D avec le modèle CAO STL .........117

Figure 5.18 Représentation par les triangles colorés...................................................118

Figure 5.19 Représentation par les triangles colorés sans affichage des points............119

Figure 5.20 Représentation par les triangles colorés avec affichage des points ...........119

Figure 5.21 Mise en correspondance des points de la pièce polyèdre..........................120

Figure A.1 Modèle STL en représentation filaire ......................................................129

Figure A.2 Exemple de Triangulation STL ...............................................................129

Figure A.3 Modèle NURBS......................................................................................131

Figure A.4 Surface NURBS découpée (haut), courbes de découpe (bas) ...................131

Figure A.5 Système de mesure 3D utilisant la triangulation .....................................132

Figure A.6 Images reconstruites à partir des informations géométriques ...................133

Figure A.7 Informations géométriques extraites........................................................133

Figure B.1 ATRV Mobile Robot On Packing Crate, Rear View................................135

Figure B.2 ATRV Mobile Robot Side View .............................................................135

Figure B.3 Robot mobile : (a) à l’arrêt et (b) en déplacement...................................136

Figure C.1 Guide de Programmation PPM................................................................139

x

Liste des Tableaux

Tableau 3.1 Résultats d’appariements ..........................................................................70

Tableau 3.2 Résultats obtenus par le logiciel ................................................................71

Tableau 3.3 L’occupation de l’espace FPGA................................................................76

Tableau 5.1 Distance moyenne obtenue pour chaque modèle CAO ............................102

Tableau 5.2 Distance moyenne pour chacun des modèles CAO..................................103

Tableau A1 Nombre de triangles STL en fonction de l'erreur .....................................130

Introduction générale

1

Introduction Générale

1. Historique

L'idée de construire des machines capables de simuler des êtres humains afin de les aider

dans certaines tâches, voire de les remplacer, était antérieure aux ordinateurs. Leur apparition

a permis d'étendre le spectre des tâches à simuler en ajoutant celles dont l'exécution relève de

facultés mentales comme la perception et le raisonnement. Dés les années quatre vingt se

sont vulgarisés deux axes de recherche, la vision par ordinateur et l’intelligence artificielle

ou réseaux de neurones.

La première essaye de développer le sens de la vision chez les robots pour améliorer leur

perception des objets ou de l’environnement en général, la seconde essaye de rendre les

robots plus intelligents de ce qu’ils étaient avant. On peut citer à titre d’exemples, certaines

applications de deux thématiques qui sont souvent utilisées simultanément:

• L’inspection des images médicales : entre autres l’étude des chromosomes, de tueurs,

des lésions par le traitement d’images d’électrophorèses, de scanner, de résonance

magnétique, d’échographie, etc.

• L’inspection d’images géologiques : reconstitution et étude des strates par analyse

d’images sismiques, etc.

• La télédétection : cartographie, interprétation automatique des images fournies par

satellite, etc.

• La communication entre l’homme et la machine : lecture optique, reconnaissance de

l’écriture, analyse automatique des documents, etc.

• Le contrôle et la navigation de robots mobiles : le but généralement poursuivi est alors

de construire un robot remplaçant au mieux l’homme pour des taches

répétitives:convoyage, surveillance, nettoyage industriel, suivi de routes, ou devant

évoluer dans un milieu hostile ou dangereux comme les mines, les milieu sous-marin,

les sites nucléaires contaminés, etc.


2

• L’étude du mouvement : suivi de cible, analyse de flux, trajectométrie, estimation du

déplacement, analyse de séquences d’images, etc.

• L’automatisation de processus industriels : reconnaissance d’objets isolés ou en vrac,

productique, saisie et assemblage de pièces, détection jets défectueux, etc.

En outre le domaine de l’inspection automatisée, indispensable pour assurer la qualité de

la production, demeure une tâche de l’activité manufacturière où l’automatisation présente

beaucoup de retard. Nous proposons dans notre projet de recherche un exemple

d’automatisation du contrôle tel qu’il peut être effectué en intégrant ensemble des

technologies de l’information et de la production.

2. Problématique

La problématique de la reconnaissance de formes est particulièrement riche et complexe. Il

existe en effet un grand nombre de problèmes différents à traiter dans lesquels les formes à

reconnaître sont nombreuses, soumises à une variabilité importante et donc sources de

confusions. De plus, les contraintes applicatives, et notamment celles résultant de la volonté

de diffusion des moyens informatiques au travers de l'informatique nomade (PDA, smart

phone…), font que la conception et l'adaptation de systèmes de reconnaissance à des

contextes précis d'utilisation sont particulièrement délicates. Pour faciliter cette mise au point

nous proposons une méthodologie de classification visant à réunir un ensemble de propriétés

rarement satisfaites dans une même approche : performances, généricité, fiabilité, robustesse,

compacité et interprétabilité. Ce dernier point est particulièrement important puisqu'il permet

au concepteur d'adapter, de maintenir et d'optimiser le système plus facilement. L'approche

proposée, centrée sur la notion de connaissances dans un classifieur, est entièrement guidée

par les données. L'originalité réside notamment dans l'exploitation conjointe de

connaissances intrinsèques et discriminantes extraites automatiquement et organisées sur

deux niveaux pour bénéficier au mieux de leur complémentarité. Le premier niveau modélise

les classes de façon explicite par des prototypes flous. Ceux-ci sont notamment utilisés pour

décomposer le problème initial en sous-problèmes dans lesquels les formes possèdant des

propriétés intrinsèques similaires sont regroupées. Le second niveau effectue ensuite une

discrimination ciblée sur ces sous-problèmes par des arbres de décision flous. L'ensemble est

formalisé de façon homogène par des systèmes d'inférence floue qui sont combinés pour la


3

classification. Cette approche a conduit à la réalisation du système Mélidis qui a été validé

sur plusieurs benchmarks dont des problèmes de reconnaissance de caractères manuscrits en

ligne.

Le problème que cherche à résoudre la reconnaissance des formes est d'associer une étiquette

à une donnée qui peut se présenter sous forme d'une image ou d'un signal. Des données

différentes peuvent recevoir la même étiquette, ces données sont les réalisations ou les

exemplaires de la classe identifiée par l'étiquette. Par exemple, le son /a/ prononcé par

différents locuteurs conduit à des signaux différents mais ces différences ne sont pas

significatives du point de vue de l'identification du son, ces signaux sont des réalisations de la

classe /a/. De même, l'écriture manuscrite du caractère A varie d'un scripteur à l'autre mais le

lecteur identifiera le caractère A pour chacune de ces réalisations.

L'idée de construire des machines capables de simuler des êtres humains afin de les aider

dans certaines tâches, voire de les remplacer, était antérieure aux ordinateurs. Leur apparition

a permis d'étendre le spectre des tâches à simuler en ajoutant celles dont l'exécution relève de

facultés mentales comme la perception et le raisonnement.

a. Pour résoudre une tache de perception visuelle donnée, nous devons résoudre ces

problèmes : quelle est l’information à extraire des images et quelles sont les

mathématiques qui le permettent?

b. Quelles sont les implantations possibles de ces méthodes et les expérimentations qui

les valident ?

c. Quelles sont les architectures informatiques qui permettent d’exécuter ces

algorithmes en temps réel au sens d’une application donnée ?

d. Problèmes théoriques : la perception des distances et des mouvements, la

représentation des formes d’objets, la reconnaissance d’objets ou de lieux, la

coopération entre modalités visuelles et inertielles, la relation entre apprentissage et

perception visuelle, la perception visuelle active.

Des méthodes générales ont été développées en reconnaissance des formes pour extraire

automatiquement des informations des données sensibles afin de caractériser les classes de


4

formes (apprentissage) et d'assigner automatiquement des données à ces classes

(reconnaissance). La mise en oeuvre de ces méthodes générales pour des problèmes

particuliers amène à introduire la notion de processus de reconnaissance qui pose la question

de l'intégration des méthodes de la reconnaissance de formes dans un système qui a pour but

de reconnaître des formes. Parallèlement aux travaux sur les méthodes de reconnaissance, se

développaient le traitement d'image, la vision par ordinateur, et le traitement de la parole. Ces

domaines ont focalisé le problème de la reconnaissance sur des données spécifiques, mais par

ailleurs ils ont permis de situer la reconnaissance dans un processus plus vaste

d'interprétation d'image ou de compréhension de la parole impliquant des niveaux de

perception et des connaissances propres au domaine.

Dans le processus de compréhension automatique, la reconnaissance des formes occupe une

position centrale. Elle fait suite aux procédures de traitement du signal de préparation des

données et de représentation de l'information et précède celles de l'intelligence artificielle.

Pour l'ingénieur, il s'agit de concevoir des algorithmes de décision qui vont reconnaître

automatiquement les formes présentes dans les images, les sons et les signaux mono ou

multi-dimensionnels. Le concepteur d'un système statistique de reconnaissance des formes

doit tout d'abord réunir un ensemble d'apprentissage, c'est-à-dire un ensemble de formes

représentées par des vecteurs dont il connaît la classe d'appartenance. Si les classes ne sont

pas connues, les méthodes dites de classification automatique séparent un nuage de points en

différentes classes. Les méthodes d'analyse de données permettent de visualiser l'ensemble

d'apprentissage et de réduire la dimension de l'espace de représentation en s'orientant vers les

mesures les plus pertinentes. Le système doit ensuite interpréter une forme inconnue comme

l'occurrence d'une des classes. Pour cela il s'appuiera sur la connaissance de la distribution

statistique des classes et fondera sa décision en maximisant un critère d'appartenance comme

dans les méthodes bayésiennes. D'autres méthodes cherchent directement les frontières qui

séparent au mieux les classes dans l'espace de représentation. L'allure générale des frontières

est déterminée par une équation dont on calcule les coefficients. Une autre approche en

reconnaissance de formes, l'approche structurelle, considère la structure d'une forme et les

relations entre ses composantes élémentaires. Les représentations sous forme de chaînes et de

graphes seront présentées, ainsi que les processus de décision qui leur sont associés tels que

la comparaison dynamique et la comparaison de graphes.


5

Les technologies de l’information façonnent les activités du monde contemporain. A cet

égard, l’informatique et les communications ont fait basculer l’économie du Canada qui est

passée d’une économie basée sur la transformation des matières premières à une économie

basée sur le savoir. La fabrication d’objets manufacturés n’échappe pas à cette tendance et de

nombreux outils informatiques facilitent la conception des pièces (C.A.O.) de même que, de

plus en plus, leur fabrication (F.A.O.). Ce foisonnement d’outils informatiques a permis de

diminuer considérablement les temps de conception et de fabrication de pièces en série.

La présente décennie est caractérisée par la nécessité de mettre en marché des produits de

qualité et ce, rapidement. Bien que plusieurs activités de conception et de fabrication

soient aujourd’hui assistées par ordinateur, le domaine de l’inspection automatisée,

indispensable pour assurer la qualité de la production, demeure une tâche de l’activité

manufacturière où beaucoup d’efforts doivent être déployés pour arriver au même niveau

d’automatisation.

L’inspection automatisée d’objets manufacturés, telle que nous l’avons définie, consiste à

comparer de façon automatique leur modèle de conception avec leur image 3D obtenue avec

un capteur télémétrique laser. Ce type de capteur très performant à l’heure actuelle, permet

d’obtenir un nuage de points 3D représentant l’objet analysé avec une précision de l’ordre de

5 microns à raison de 20 000 points par seconde. La mise en registre de ces deux

représentations permet de conclure si une pièce réalisée est conforme à son modèle

théorique défini lors de sa conception. La mise en correspondance est un problème difficile

compliqué par la nécessité de sélectionner le bon modèle dans une base de données CAO.

3. Protocole d’investigations

Notre protocole d’investigations s’est articulé autour de trois axes de recherche:

• Maîtrise et adaptation des techniques d'apprentissage. Jusqu'à présent notre domaine de

recherche a été la vision par ordinateur, il s'agira tout d'abord de maîtriser les techniques

d'apprentissage pour pouvoir sélectionner celles en meilleure adéquation avec nos problèmes.

Ensuite, il faudra adapter des théories et des algorithmes d'apprentissage afin qu'ils tiennent

compte des contraintes spécifiques de la vision. Il faut notamment développer des approches


6

capables de gérer de grandes quantités de données de haute dimensionnalité et de décrire des

espaces complexes.

• Amélioration des techniques de description d'images. De telles techniques sont

maintenant bien étudiées et nous avons à notre disposition des ``briques de base'', comme par

exemple les points d'intérêt affines. Il s'agit de les étendre pour pouvoir décrire des textures,

pour définir des mesures de similarité ainsi que des descripteurs de forme 2D et 3D.

• Construction de modèles pour la reconnaissance. Il s'agit de combiner les techniques

d'apprentissage et les techniques de description pour construire des modèles pour la

reconnaissance. Il faut pour cela sélectionner les techniques adéquates et pour l'apprentissage

et pour la description d'images. Initialement, cette sélection sera effectuée manuellement

pour chaque classe d'objets. À long terme on compte rendre ce choix automatique, au moins

partiellement par exemple en utilisant des techniques de sélection automatique de

descripteurs. On obtiendra donc de façon automatique une représentation adaptée pour un

ensemble de données d'apprentissage qui permettra en outre une reconnaissance efficace.

Notre projet aborde le problème de la reconnaissance d'objets et de l'interprétation de scènes

pour des images prises par un robot mobile utilisant la stéréovision. C'est un problème ouvert

de la vision par ordinateur: il est aujourd'hui impossible de déterminer de façon automatique

le contenu d'une image ou d'une séquence vidéo. La piste que nous suivons repose sur l'ajout

de l'apprentissage aux techniques de vision par ordinateur que est la description d'images et la

géométrie. Une solution, même partielle, au problème de la reconnaissance d'objets et de

l'interprétation de scènes a de nombreuses applications. Dans notre étude nous nous

intéressons en particulier aux applications en recherche d'images pour l’automatisation de

processus industriels, la reconnaissance d’objets isolés ou en vrac, la saisie et l’assemblage de

pièces, la détection de jets défectueux, etc.

4. Cadre et hypothèses de notre travail de recherche

La production croissante d’objets présentant des surfaces gauches, que ce soit pour des

raisons fonctionnelles ou de design, et l’évolution des techniques de fabrication, a créé un

besoin dans le domaine du contrôle automatique de pièces complexes. Ce type de contrôle


7

nécessite une définition géométrique très fidèle de l’objet inspecté, de nombreux points de

mesure suffisamment précis, et des règles d’inspection de ces surfaces clairement définies.

L’utilisation de machines à mesurer tridimensionnelles, dont la précision de mesure atteint le

micromètre, et l’avènement récent des capteurs télémétriques alliant précision de mesure et

rapidité d’acquisition, permettent d’obtenir des mesures 3D constituant une description

explicite des surfaces de l’objet. Par ailleurs, la connaissance du modèle CAO ayant servi à la

réalisation de l’objet fournit une description exacte et complète de sa géométrie.

Nous proposons donc une méthode de contrôle automatique de pièces comprenant surfaces

complexes, à partir d’un modèle CAO (format IGES ou STL) et de données 3D fournies par

un capteur télémétrique ou par une machine à mesurer. Nous choisissons dans un premier

temps un modèle géométrique permettant de représenter l’objet étudié. Pour cela, nous

établissons un état de l’art complet sur les modèles géométriques déformables ou non

-déformables existants, pour des applications spécifiques telles que la Vision et la CAO.

A partir de cette classification, nous sélectionnons deux modèles surfaciques : un modèle

exact et complexe (surface NURBS découpées) et un modèle triangulé simple, facile à

manipuler (STL). D’un autre coté, nous disposons d’un ensemble de points 3D, fourni soit

par une machine à mesurer tridimensionnelle, soit par la mise en correspondance mécanique

de différentes vues 3D acquises par un capteur télémétrique. Le modèle géométrique et les

données 3D sont exprimés initialement dans des repères indépendants (repère de

modélisation et repère de mesure). Afin de comparer ces deux formes, il est nécessaire de les

“superposer”, c’est-à-dire de minimiser la distance globale points 3D/modèle géométrique,

opération appelée « mise en correspondance ».

D’un point de vue mathématique, la mise en correspondance des points 3D avec le modèle

géométrique consiste à déterminer les paramètres de la transformation rigide (trois

paramètres pour la translation et trois paramètres pour la rotation) à appliquer sur les points

3D, de telle sorte que l’on minimise un critère de distance entre les deux formes; un état de

l’art concernant ces techniques est présenté. Nous proposons aussi une méthode de mise en

correspondance générale automatique, robuste (jusqu’à 80% de points aberrants) et capable

de mettre en correspondance deux formes quelconques dans des positions initiales relatives

quelconques. En fonction du type de formes manipulées, cette méthode nécessite la

connaissance du calcul de distances inter-primitives. Pour cela, nous définissons un calcul de


8

distance point/ensemble de triangles et point/surface NURBS découpées. Une fois établie la

mise en correspondance entre les données 3D et le modèle CAO, en fonction de l’erreur

constatée , de multiples conclusions et actions sont possibles.

En effet, on peut envisager plusieurs stratégies d’exploitation des résultats de la mise en

correspondance, à savoir :

1. La pièce est conforme ; elle est donc acceptée comme bonne et exploitée dans la suite du

processus.

2. Des erreurs sont constatées, indiquant une dégradation du procédé de fabrication (usure

des outils, dérive,...). Le procédé de fabrication est rectifié en conséquence.

3. Non-conformité de la pièce due à une non prise en compte d’impératifs de fabrication

(retrait des pièces moulées,...). Le modèle CAO est modifié, pour que les futures pièces

usinées soient conformes.

4. La pièce est reconnue parmi une famille d’objets (reconnaissance de formes).

Nous nous sommes limités dans notre travail aux conclusions issues de la mise en

correspondance, sans rétroaction sur les paramètres du procédé ou sur le modèle CAO. En

particulier, une application importante de la mise en correspondance réside dans l’inspection

automatique d’objets présentant des surfaces complexes ou non complexes. Nous établissons,

dans un premier temps, un état de l’art dans les domaines de la vérification des tolérances et

de l’inspection visuelle automatique.

Nous présentons ensuite notre propre méthode de contrôle d’objets présentant des surfaces

complexes. L’étude bibliographique a montré que les méthodes existantes se contentent le

plus souvent de tester que la distance entre chaque point et sa surface nominale,

contrairement à notre méthode qui réalise une inspection complète des objets. Cette phase

d’inspection se décompose en une inspection globale, vérifiant les tolérances du

positionnement, de l’orientation et de la forme des surfaces de l’objet, et en une inspection

locale, comparant les courbures et normales en chaque point 3D avec sa surface nominale.

Nous présentons également une méthode d’inspection des objets comportant des surfaces

simples (plans, portions de cylindre), basée sur le respect des cotes et des différentes

tolérances (forme, position, orientation). Un rapport d’inspection est finalement engendré

pour chacune des pièces inspectées; on dispose également de la possibilité de visualiser

graphiquement la localisation des erreurs.


9

A partir de la mise en correspondance des deux formes, d’autres applications sont possibles.

L’une des plus simples est la reconnaissance de formes : disposant des données 3D d’un objet

à reconnaître parmi une famille d’objets, nous réalisons leur mise en correspondance avec

chacun des modèles géométriques disponibles. Le classifieur de type distance euclidienne,

qui donne la plus petite distance, permet de déterminer l’objet à reconnaître.

L’intégration de ces différentes parties dans le processus d’inspection automatique

industrielle, ou de reconnaissance de formes est illustrée par la figure 0.1. Les rectangles

grisés correspondent aux contributions de notre travail de thèse.

5. Présentation de notre travail de recherche

Le premier chapitre nous permet de présenter un état de l’art sur la reconnaissance de formes,

suivi d’une étude sur les approches connexionnistes en faisant le point sur l’intérêt de leur

hybridation.

Le deuxième chapitre est consacré à la présentation d’un état de l’art sur la Transformée de

Hough, technique associée à notre processus de reconnaissance de formes. Les concepts de

base liés au champ de dimension de θ et de ρ sont abordés, ainsi que son implémentation

hardware.

Dans le chapitre suivant un état de l’art sur la robotique mobile est exposé. L’objectif est de

proposer un système de reconnaissance des formes pour mieux cerner les problèmes

inhérents à la vision artificielle Nous exposons notre choix d’une méthode de stéréovision

pour notre application particulière d’aide à la navigation d’un robot mobile, ce robot évoluant

dans un environnement de bureau ou d’atelier.

Le logiciel élaboré à cet effet est constitué de plusieurs modules permettant une interaction

entre les processus de traitements mis en uvre.

• Détection des objets dans la scène par la rétro-propagation du gradient,

• Extraction des chaînes de points de contours par le filtre de Deriche

• Application de la TH dans l’appariement des images,

• Mise en correspondance par le modèle de Hoppfield.


10

Au chapitre 4, après aussi un état de l’art exhaustif sur l’inspection visuelle automatique,

nous proposons un exemple d’automatisation du contrôle tel qu’il peut être effectué en

intégrant ensemble des technologies de l’information et de la production

Entre autres nous évaluons les capacités de cette méthode de mise en correspondance utilisée,

en fonction de ses paramètres internes et du type de données manipulées.

Le dernier chapitre est essentiellement consacré aux applications liées à la Reconnaissance

de formes et au contrôle industriel en productique.

Nous terminons notre thèse par une conclusion générale en évoquant les points forts de notre

approche. Comme aucune machine ne peut égaler les performances humaines dans le

domaine de la reconnaissance des formes, plusieurs perspectives restent envisageables pour

faire évoluer les propositions que nous avons défendues dans notre travail de recherche.

La présentation de ce manuscrit est suivie d’une bibliographie et d’annexes contenant la

conception des pièces, les entités IGES, et le robot mobile ATRV utilisé pendant

l’expérimentation.

Figure 0.1. Processus d’inspection automatique industrielle.

Chapitre 1 Introduction à la RDF et aux réseaux de neurones

11

CHAPITRE 1

Introduction à la RDF et aux

Réseaux de Neurones

1. Historique et Etat de l’art sur la RDF

La reconnaissance des formes est une discipline née au milieu des années cinquante à

partir des mathématiques (calcul des probabilités, algèbre linéaire, géométrie intégrale,…)

de l'informatique et des sciences pour l’ingénieur. Il existait antérieurement un ensemble

de travaux en traitement du signal (forme 1D) regroupés sous le vocable de détection et

dont les applications (radar, sonar, démodulation…) remontent aux années quarante.

Ultérieurement, son développement a été lié à celui de l'Intelligence artificielle dont on

l'a considérée pendant longtemps comme une composante. La reconnaissance des formes a

conservé les traces de cette double origine, à la fois dans sa méthodologie et dans ses

thèmes. Les problèmes de détection, classiques en traitement du signal ont servi de bases

pour le développement de nombreuses méthodes qui, par la suite, ont pu être intégrées et

généralisées pour d'autres données que des signaux.

Par exemple, supposons que nous cherchions à détecter la présence d'un signal s(t)

parfaitement connu mais noyé dans un bruit additif b(t) et cela sur un intervalle de temps

[0,T]; nous observons en fait le signal r(t) et deux hypothèses sont en présence :

Hypothèse 0 : r(t) = b(t) (le signal s est absent)

Hypothèse 1 : r(t) = s(t) + b(t) (le signal s est présent)

En discrétisant le temps, on va former un vecteur de dimension n :

R = (r(0), r(a), r(2a),…, r((n – 1)a))

Si nous possédons des informations sur la nature du bruit b(t), par exemple s'il est

gaussien de matrice de covariance connue, nous pourrons construire une fonction de

détection F de Rn dans R telle que notre décision sera :


12

Si F(R) > 0, décider en faveur de l'hypothèse 0

Si F(R) < 0, décider en faveur de l'hypothèse 1

Ce type d'approche sera utilisé en RDF sur des vecteurs représentatifs de formes à

reconnaître et non plus sur des signaux échantillonnés. Ces vecteurs seront par exemple

constitués des moments géométriques ou d'autres descripteurs. La fonction F pourra être

une fonction discriminante linéaire, un réseau de neurones formels ou un classifieur

statistique. Les premiers travaux que l'on peut qualifier de primaires au sens actuel ont eu

lieu à partir du début des années soixante. Dans ces travaux, on retrouve les deux

disciplines fondatrices (il est d'ailleurs parfois difficile de déterminer une frontière très

nette) : mathématique (pour le cadre théorique, pour l'analyse et la généralisation des

méthodes) et informatique (pour la construction et l'implémentation logicielle ou même

matérielle des algorithmes, pour leur parallélisation). D'autres disciplines de la branche

comme l'électronique, l'optique et même la mécanique ont aussi joué un certain rôle depuis

trente ans dans la construction de la RDF. C'est parfois en exportant des modèles (verres

de spin —> réseaux de Hoppfield, modèles mécaniques de déformation) ou des méthodes

(physique statistique —> machine de Boltzmann). L'inspiration biologique et surtout

neurophysiologique et psychophysique a aussi été importante (modèles de la perception

visuelle, théories épigénétiques,…).

A partir des années quatre-vingt, l'impact de l'informatique s'est considérablement accru

jusqu'à faire considérer la RDF comme une branche de l'informatique alors qu'elle était

plutôt une branche des mathématiques (probabilité - statistique surtout) dans la période

précédente. La raison de ce changement est la diminution prodigieuse du coût des

ordinateurs (et donc leur dissémination) et la croissance exponentielle des performances,

en capacité de stockage et en vitesse. La puissance de calcul ne résout pas tous les

problèmes, néanmoins, l'espace des méthodes répondant rapidement ne cesse de s'étendre;

on sait aussi que l'approche qui consiste à explorer presque toutes les possibilités pour

décider de la manière optimale n'a pas un grand avenir mais la puissance accrue des

machines recule sans cesse les limites de ce que l'on peut faire tout en améliorant (ce qui

est loin d'être négligeable) l'environnement de travail du développeur (adieu les cartes de

contrôle, les rubans perforés, les compilations quotidiennes,…).

Aujourd'hui, on peut trouver des logiciels de reconnaissance de caractères assez

efficaces sur des micro-ordinateurs à plus de 500 caractères par seconde. Des ordinateurs

de petite taille sont dotés de modules de reconnaissance on line de l'écriture manuscrite


13

(caractères isolés). En reconnaissance de la parole, les progrès ont été aussi très

importants, même si l'écart entre ce qui avait été extrapolé à une date donnée à partir de ce

que l'on savait faire et là aujourd’hui quelques années après est parfois étonnante.

1.1. Les deux grandes controverses

Nous aborderons enfin très brièvement deux thèmes quasi philosophiques assimilables à

des controverses. Sans espérer être complet, il nous a semblé en effet important de parler

un peu de deux grandes interrogations qui animent la RDF depuis de nombreuses années.

Leur trait commun est de placer la RDF sous l'éclairage des sciences cognitives, c'est-à-

dire des sciences qui s'interrogent sur les modalités, les objets et les structures de la

connaissance (chez l'être humain).

Comment le cerveau, la mémoire, l'apprentissage, le raisonnement ? Existe-t-il un ??

(Logique) ?? (Interne) universel pour la pensée non verbale ? Comment s'élabore la

perception (visuelle ou auditive par exemple) ? Des chercheurs en RDF se posent aussi

ces questions, et surtout, sont convaincus qu'il faut se les poser pour progresser vraiment

dans la résolution pratique des problèmes les plus difficiles de la RDF. Concevoir (même

implicitement) la RDF uniquement comme un ensemble de recettes est une erreur.

1.1.1. Controverse cognitiviste / comportementaliste

La résolution d'un problème donné en RDF peut-il ou non se ramener à un ensemble

fini de règles explicites, à une suite de morceaux de connaissances verbalisables et

formalisables ? Faut-il plutôt s'inspirer de nos connaissances sur la perception humaine et

en particulier sur le fonctionnement du cerveau pour concevoir des systèmes de RDF

d'inspiration ?

Pour illustrer cette controverse, suivant D. R. Hofstadter, on peut poser la question

suivante : qu'est ce qui définit la lettre? Répondre n'est pas si simple si on songe à toutes

les polices de caractères plus ou moins fantaisistes utilisées par les graphistes; pourtant,

nous savons reconnaître un A et sans nous soucier du type de caractères employés.

Comment est-ce possible ? A AA A ALe cognitiviste va tenter de trouver les règles, aussi nombreuses soient-elles, aussi

complexes que puisse être leur enchevêtrement, qui détermine notre décision de

reconnaître ou pas un dans une forme. Le comportementaliste lui ne cherchera pas à


14

analyser le concept de ?? (son essence) mais tentera de collecter un maximum de

prototypes différents. Ensuite, en utilisant une boîte noire (un réseau connexionniste par

exemple), il essaiera de reproduire, d'imiter, la fonction et de l'étendre à des exemples

nouveaux. Est-ce une simple extrapolation ou bien une extraction de régularités ?

En caricaturant, disons que le cognitiviste (le chercheur en IA ?) cherche des règles

alors que le comportementaliste (le statisticien, le connexionniste ?) recherche des

régularités.

1.1.2. Controverse. Apprentissage / Représentation

Etant donné un ensemble de formes à reconnaître dont certaines ont été étiquetées par

un expert du domaine (l'ensemble d'apprentissage), faut-il chercher un codage, une

représentation, très sophistiqués de ces formes (en utilisant empiriquement l'ensemble

d'apprentissage mais aussi des connaissances explicites) ou plutôt concevoir des

techniques d'apprentissage extrêmement efficaces permettant d'obtenir de bonnes

performances sans un codage aussi spécifique ? Autrement dit, quel doit être le poids

respectif de la représentation des formes et du système de classification ? Cette

controverse correspond, suivant E. Bienenstock, à un dilemme bien connu en statistique,

celui du biais et de la variance.

La recherche de représentations permet souvent de réduire le nombre de dimensions des

vecteurs à classer. Cette réduction suppose cependant des connaissances a priori

spécifiques sur les propriétés d’invariance des classes. Nous savons par exemple que

l'épaisseur du trait ne joue pas de rôle dans la reconnaissance d'une lettre; cela nous

incitera peut-être à squelettiser l'image pour diminuer le nombre de points à coder.

Inversement, en faisant porter notre effort sur la classification en raffinant le plus

possible les techniques de comparaison des représentations (par des métriques très habiles

ou des fonctions discriminantes subtiles), nous essayons d'être moins spécifique, d'avoir

moins d'a priori, au risque d'être trop dépendant des prototypes que nous utiliserons.

1.2. Applications de la RDF

Nous ne parlerons ici que des thèmes relatifs aux formes planes. Le thème (au sens c'est

le fondement d'une croyance et en même temps partiellement une illusion…) le plus

souvent évoqué par les chercheurs est sans conteste la reconnaissance de l'écrit et en

particulier de l'écriture manuscrite (cursive). Ce thème a joué en reconnaissance des


15

formes le rôle du jeu d’échec ou de la compréhension automatique de texte en Intelligence

Artificielle. D'autres problèmes ont aussi excité la curiosité et l'activité des chercheurs :

identifier ou authentifier un visage, localiser des éléments artificiels (routes, bâtiments,

aérodromes) sur des images satellites, détecter et classer des anomalies dans des

matériaux, reconnaître des pièces manufacturées en productique, analyser des objets

biologiques (chromosomes, fibres,…).

Dans notre manuscrit, on trouvera deux exemples d’applications en temps réel qui

lèveront toute ambiguïté sur des aspects de la problématique en RDF. L’une en vision

robotique dans une perspective de navigation et l’autre en productique dans le contrôle où

l’inspection automatique de pièces industriels.

Nobostant ce qui est rapporté, il est en effet très difficile de faire ressortir les problèmes

généraux ou les méthodes à partir d'applications qui privilégient l'efficacité (en terme de

vitesse, d'espace mémoire et de coût). D'autre part, les sociétés qui ont investi de

nombreuses années pour résoudre un problème sont peu désireuses de divulguer leurs

technologies de manière détaillée; ne restent donc accessibles que des idées générales sur

leurs méthodes.

2. Approche neuronale

2.1. Introduction

Les méthodes connexionnistes ne sont pas destinées exclusivement, loin de là, à être

appliquées en reconnaissance des formes. Il faut signaler leur introduction en automatique

(commande de processus), en traitement du signal (compression, prédiction, filtrage), en

synthèse de la parole (NetTalk) et aussi dans certains domaines où les méthodes de

l'intelligence artificielle sont prédominantes. Nous cantonnerons nos propos aux notions

utiles de reconnaissance des formes.

Commençons par citer un extrait de la thèse de Yann Le Cun :

‘’Ces dernières années ont vu l'apparition de nouvelles techniques regroupées sous le

nom de « connexionnisme » dont le principe directeur est l'utilisation d'un réseau de

“processeurs” très simples interconnectés, et dont la connaissance réside précisément dans

les connexions. Cette idée est en fait très ancienne, pour ne pas dire plus ancienne que

l'informatique. L'idée sous-jacente et assez présomptueuse étant de copier le cerveau. Ce

dernier, qu'il soit humain ou animal est en effet le seul exemple de machine intelligente que


16

nous connaissions. Il peut donc paraître naturel de s'en inspirer non seulement au niveau

fonctionnel, mais aussi au niveau architectural. Il est bon de mettre en garde le lecteur en

insistant sur le fait que les systèmes connexionnistes ne sont qu'un moyen de plus de

résoudre certains problèmes. La longue histoire des espoirs déçus de l'intelligence

artificielle conduit à une prudence extrême quant aux résultats possibles d'une nouvelle

technique, quelle qu'elle soit’’. Notre but n'est pas de jouer au jeu des définitions mais il est

important de bien cerner l'objet technique appelé réseau connexionniste. Cet objet est

entouré d'un rendant certes sa diffusion plus facile vers un vaste public, mais conduisant à

des excès d'enthousiasme que Yann Le Cun, de manière prémonitoire, dénonçait dès 1987.

Une certaine presse se jette sur la moindre, le plus petit, comme jadis sur les produits de

l'IA (intelligence artificielle).

Ainsi, aujourd’hui, ce n’est pas le paradigme neurobiologique qui contribue au

développement des réseaux de neurones formels : au contraire, ce sont les réseaux de

neurones formels qui contribuent, de plus en plus fréquemment, à la compréhension des

systèmes neuronaux vivants, car ils constituent des outils précieux pour en construire des

modèles, simples mais utiles. Peut-être cette situation changera-t-elle dans l’avenir : les

progrès réalisés dans l’analyse des systèmes vivants pourraient conduire, à leur tour, à la

conception de réseaux de neurones formels plus efficaces que ceux que nous décrivons

aujourd’hui. Il y a là un champ de recherche fascinant, complètement ouvert. On rêve,

jusque dans l'antre des grands décideurs (privés, publics, européens, nippons,…), de

machines extraordinaires, nouvelles pierres philosophales de l'intellect, d'engins

neuromimétiques bourrés de silicium, de circuits opto-électroniques ou même de

composants moléculaires; inutile même de les programmer, ces machines apprennent

quasiment seules, elles dépassent leurs maîtres si on leur fournit quelques bons exemples

de la tâche à accomplir, certaines fonctionnent même sans professeur.

Pour définir un réseau connexionniste spécifique, il y a trois éléments à fournir :

1) L'architecture : la manière dont les unités seront interconnectées et les contraintes

liant les poids.

2) La dynamique : comment les activités des unités sont couplées entre elles, comment

les signaux se propagent dans le réseau. Cette dynamique peut être déterministe ou bien

probabiliste.

3) L'apprentissage : les règles qui tentent de déterminer les valeurs (optimales) des

poids pour que le réseau accomplisse une certaine tâche. Cette tâche est caractérisée par


17

une relation prédéfinie (en général par une liste d'exemples) entre les activités de

certaines unités.

Pour rendre moins abstraites ces définitions, anticipons un peu sur l'algorithme du

perceptron de Rosenblatt et analysons-le en terme d'architecture, de dynamique et

d'apprentissage. L'architecture comprendra deux couches de cellules. La première couche

appelée entrée comprendra autant de cellules que de composantes au vecteur X (qui code la

forme). La seconde couche appelée sortie comprendra une seule cellule. Toutes les cellules

d'entrée sont connectées à la cellule de sortie par un arc dont le poids sera la

composante du vecteur A. La dynamique sera de type feed-forward (propagation vers

l'avant), la cellule de sortie aura pour activité une combinaison linéaire des activités des

cellules d'entrée:

xs = ∑i = 1

N + 1 ai x.i

où xi est l'activité de la cellule d'entrée n° i et ai le poids associé à la connexion entre la

cellule d'entrée n° i et la cellule de sortie.

La sortie du réseau ne sera pas xs mais Sgn(xs) où Sgn est la fonction signe. On aura

donc, en notant O la sortie : O = Sgn(xs) = Sgn( ∑i = 1

N + 1 ai.xi )

Notons que puisque la dernière composante vaut toujours + 1, on peut écrire :

O(X) = Sgn( ∑i = 1

N ai.xi + aN )

où aN peut être vu comme un seuil ou offset associé à la sortie. Cette expression est celle

proposée par MacCullogh et Pitts dans leurs travaux des années quarante sur les rapports

entre neurones formels et logique. Il s'agit d'un modèle ultra simplifié d'un neurone

biologique. Les coefficients ai représentent les poids synaptiques, le seuil et la fonction

signe modélisent l'activation du neurone. L'apprentissage consiste à faire coïncider la sortie

effective du réseau O(X) avec une sortie désirée, ici C(X) (qui vaut + 1 pour la classe 1 et

–1 pour la classe 2). On notera que le critère du perceptron est calculé à partir de


18

∑i = 1

N ai.xi + aN et non de la sortie O(X).

Néanmoins, la règle d'apprentissage est la suivante :

Tant qu'il y a des exemples X tels que O(X) C(X) :

Présenter un exemple X = (x1,…, xN, 1)

Calculer la sortie O(X) du réseau

Si : O(X) = C(X), pas de modification

Sinon : ai = ai + r.xi pour i = 1,…, N + 1

Nous venons de reformuler l'algorithme du perceptron sous une forme connexionniste

qui correspond aux intuitions initiales de F. Rosenblatt. De manière analogue, l'algorithme

de Widrow-Hoff a d'abord été présenté par les auteurs sous le nom d'Adaline (ADAptative

LINear Elements) vers 1960. Après quelques succès, le perceptron et l'Adaline plafonnent.

Comme une unité (neurone, automate) ne sait calculer qu'une somme pondérée de ses

entrées suivie d'un seuillage (plus ou moins brutal), un dispositif où une seule couche de

poids est modifiable (le fameux apprentissage) sera limité aux problèmes linéairement

séparables.

Les inventeurs ont bien sûr pensé à combiner ces éléments de manière plus complexe

(fonctions quadratiques et non linéaires, logiques majoritaires et non à seuil, multiple

adaline,…) mais si ces idées concernaient les points 1 et 2 (architecture & dynamique),

elles ne proposaient pas de solution efficace au point 3 (apprentissage). Hors ce point est

crucial, sauf si l'on dispose d'une technique permettant de définir directement (de manière

non itérative) les poids à partir des exemples.

Le livre de Minsky & Papert (1968), en montrant les limitations théoriques du

perceptron, a contribué à la mise en sommeil de ce domaine de recherche, au moins

pendant 15 ans. Les idées cybernetico-connexionnistes sont cependant restées vivantes

notamment dans la modélisation biologique (Caianiello, Amari,…), en automatique et

traitement du signal (Widrow,…), dans la théorie des mémoires associatives (Kohonen).

Le début des années quatre-vingt voit le redémarrage des travaux connexionnistes. En

Finlande, T. Kohonen introduit des cartes topologiques auto-organisatrices (connues

maintenant sous le nom de cartes de Kohonen). Le physicien J. Hopfield propose un

modèle à architecture complètement connectée (voisin de celui d'Amari) dont la

dynamique peut être caractérisée par une fonction énergie inspirée des états désordonnés

de la matière (on retrouve une des sources d'inspiration cybernétique: la physique


19

statistique). L'informaticien G. Hinton associé à Anderson et d'autres propose des modèles

distribués. En 1983, Hinton, Sejnowski et Ackley introduisent la machine de Boltzman

dont la dynamique et l'apprentissage sont probabilistes, et dont les performances

extrêmement intéressantes sont handicapées par des temps de convergence énormes.

En 1985-1986, Y. Le Cun, Parker et Rumelhart proposent indépendamment une

extension de l'Adaline (bien que tout le monde parlera de multi-perceptron) avec une

architecture multicouche, une dynamique feed-forward et surtout un algorithme

d'apprentissage des poids très efficace connu sous le nom de rétro-propagation (BP).

2.2. Caractéristiques architecturales d'un réseau neuronalLes réseaux connexionnistes sont des assemblages d'unités de calcul, les neurones

formels. Ces derniers ont pour origine un modèle du neurone biologique, dont ils ne

retiennent d'ailleurs qu'une vision fort simplifiée (voir figure 1.1). Le neurone, comme

toute cellule, est composé d'un corps (ou soma), qui contient son noyau et où se déroulent

les activités propres à sa vie cellulaire. Cependant, il est aussi doté d'un axone et de

dendrites, structures spécialisées dans la communication avec les autres neurones. Cette

communication entre cellules nerveuses s'effectue via des impulsions nerveuses. Les

impulsions sont générées à l'extrémité somatique de l'axone et vont vers les terminaisons

axonales. Là, elles affecteront tous les neurones reliés au neurone générateur, par

l'intermédiaire de jonctions entre les terminaisons axonales et les autres cellules. Cette

jonction est appelée synapse.

Cet héritage de la neurobiologie forme une composante importante de l'étude des réseaux

connexionnistes, et le souci de maintenir une certaine correspondance avec le système

nerveux humain a animé et continue à animer une part importante des recherches dans ce

domaine. Malgré cet héritage, l'essentiel des travaux d'aujourd'hui ont pour objet les

réseaux de neurones formels et non son corrélât neurobiologique. Vus comme des

systèmes de calcul, les réseaux de neurones possèdent plusieurs propriétés qui les rendent

intéressants d'un point de vue théorique, et fort utile en pratique.


20

Figure 1.1. Représentation simplifiée d'un neurone biologique

Un réseau neuronal est constitué par un graphe orienté et pondéré. Les noeuds de ce

graphe sont des automates simples nommés neurones formels (figure 1.2) ou tout

simplement unités du réseau, dotées d'un état interne, que l'on appelle état d'activation. Les

unités peuvent propager leur état d'activation aux autres unités du graphe en passant par

des arcs pondérés appelés connexions ou liens synaptiques dotés de poids synaptiques. La

règle qui détermine l'activation d'un neurone en fonction de l'influence venue de ses entrées

et de leurs poids respectifs s'appelle règle d'activation ou fonction d'activation.

Entrées ActivationDendrites (Prend en compte l ensemble des entrées et des poids associés)

X1X2

… Sortie (Axone et synapse vers d’autres unités)

XN

Poids synaptiques Fonction d activation(Effet d inhibition ou d excitation (Régulation de la sortie)sur l activation des signaux d entrées)

Figure 1.2. Neurone formel

L'architecture d'un réseau neuronal est donnée par le nombre et le type des neurones ainsi

que la connectivité dont les contraintes permettent de distinguer les différents modèles

(voir figure 1.3). Les architectures les plus importantes sont :


21

Réseaux à une seule couche : Les unités sont toutes sur le même niveau. Dans ce type

d'architectures, les unités sont connectées directement aux entrées et sont aussi les sorties

du réseau. Les réseaux à une seule couche ont normalement des connexions latérales (entre

les neurones d'une même couche). Un exemple de ce type d'architecture est le modèle de

Kohonen "Kohonen Feature Map" [Dav 93, Dre 04, Her 94, Jod 94a].

Réseaux à couches unidirectionnels : Les unités sont organisées en plusieurs niveaux

bien définis. En général, chaque unité d'une couche reçoit ses entrées à partir de la couche

précédente et envoie ses sorties vers la couche suivante (feed-forward nets). La figure 1.3-a

montre un exemple de réseaux à trois couches. Cette architecture à trois couches (entrée,

couche cachée et sortie) est très utilisée dans la pratique. Le célèbre modèle du Perceptron

Multi-Couches (PMC) [Dav 93, Dre 04, Her 94, Jod 94a, Jod 94b] se compose en général

d'une architecture de ce type, c'est-à-dire avec une seule couche cachée (hidden layer),

mais rien n'empêche d'avoir plus d'une seule couche cachée dans ce modèle. Un autre type

d'interconnexions dans les réseaux à couches sont les raccourcis (short-cuts) qui permettent

de lier des unités en passant à travers des niveaux. Ainsi, on peut sauter d'une couche à

l'autre avec les raccourcis, à condition de ne pas créer une boucle (voir figure 1.3-b).

Réseaux récurrents : Les réseaux récurrents [Dre 04, Her 94, Jod 94a, Jod 94b] peuvent

avoir une ou plusieurs couches, mais leur particularité est la présence d'interconnexions

depuis la sortie d'une unité vers une autre unité de la même couche ou d'une couche

inférieure. Ce type d'interconnexions permet de modéliser des aspects temporaux et des

comportements dynamiques, où la sortie d'une unité dépend de son état antérieur. Les

boucles internes rendent ces réseaux instables, ce qui oblige à utiliser des algorithmes plus

spécifiques (et généralement plus complexes) pour l'apprentissage. Un type particulier de

réseau récurrent sont les réseaux totalement connectés, tels que le modèle de Hoppfield

représenté dans la figure 1.3-d.

Réseaux d'ordre supérieur : Les unités de ce type permettent la connexion directe entre

deux entrées ou plus, avant d'appliquer la fonction de calcul de l'activation de l'unité

[OSO 98]. Ce type de réseau sert à modéliser les synapses de modulation, c'est-à-dire

quand une entrée peut moduler (agir sur) le signal provenant d'une autre entrée. Un modèle

particulier de réseaux d'ordre supérieur (high order neural net) est le réseau Sigma-Pi

représenté dans la figure 1.3-e.


22

Figure 1.3. Architectures de réseaux neuronaux

Figure 1.4. Réseau à représentation locale

Figure 1.5. Exemple de codage semi distribué par micro-traits


23

2.3. Représentation de connaissances dans l’approche neuronaleLe mode de représentation de connaissances le plus connu dans l'approche neuronale est

le mode distribué, c'est de ce mode qu'il est question quand il s'agit de définir ou de

caractériser l'approche neuronale. Il existe cependant deux autres modes, moins connus, le

codage local et le codage semi distribué [Jod 94a].

2.3.1. Réseaux à représentation locale: Dans un codage local, chaque neurone représente

un concept, autrement dit, une donnée élémentaire du problème. Lorsque le neurone

détecte la présence de ce concept, il est actif, sinon, il est inactif. Ce codage simple est

employé dans les réseaux dépourvus de mécanisme d'apprentissage parce qu'il est

relativement aisé d'établir les connexions entre les neurones selon l'interprétation qu'on

veut leur donner. Une représentation locale est souvent employée pour le codage des

sorties d'un réseau neuronal dans un problème de classification, par exemple. En effet, le

code de la sortie prend la forme d'un ensemble de vecteurs où seule la composante

représentant la classe voulue est non nulle. Ce mode de représentation peut d'ailleurs être

vu comme une sorte d'hybridation puisqu'il s'agit d'une représentation de concepts

symboliques sous forme d'un réseau de neurones. Considérons l'exemple de la figure 1.4, si

on présente "soleil" en entrée, la réponse en sortie sera invariablement "jour" parce que

nous avons relié le concept "soleil" avec le concept "jour".

Le codage local est simple et naturel, il est souvent utile dans le cas où les données à

représenter ne sont pas trop nombreuses et partagent des relations simples entre elles.

Cependant, dans les modèles complexes, cette technique de codage souffre de plusieurs

inconvénients [Jod 94a]. C'est une technique gourmande car le nombre de neurones

nécessaires est égal au nombre de concepts du domaine considéré, de plus, elle impose une

certaine duplication puisqu'elle ne permet pas de différencier les rôles que peut prendre un

concept donné. Les réseaux à représentation locale sont parfois appelés réseaux

transparents car leur comportement peut être expliqué pas à pas. Le modèle MAI de

McClelland et Rumelhart est l'un des exemples les plus représentatifs de ce type de

codage [Mcc 81].

2.3.2. Réseaux à représentation semi distribuée : À la différence des codages locaux, les

codages semi distribués répartissent la représentation d'une donnée parmi plusieurs

neurones [Jod 94a]. Il en résulte plus de souplesse mais moins de simplicité. L'une des


24

techniques les plus représentatives est le codage par micro-traits qui s'apparente aux

représentations locales où chaque neurone correspond à un trait descriptif des concepts du

domaine. La description d'un concept est effectuée par les traits qui le définissent.

Figure 1.6. Réseau à représentation distribué

A partir des traits de la figure 1.6, plusieurs concepts pourraient être représentés, par

exemple:

• Café = liquide, chaud, amer, noir

• Chocolat = solide, sucré, noir, froid

Cette technique est moins gourmande qu'un codage purement local, elle permet de

représenter de nouveaux concepts à partir de concepts connus ou d'assemblages originaux

de traits élémentaires. Ce codage module la description des concepts en dosant l'activation

des neurones traits et rend possible l'expression de la similarité entre concepts. Cependant,

ce codage présente des limites dues aux problèmes de structuration et aux possibilités

d'interférence entre des concepts proches.

2.3.3. Réseaux à représentation distribuée :

Dans les réseaux à représentation distribuée, la représentation d'un concept est distribuée

sur tous les neurones présents. Chaque concept est associé à un code dont les composantes

n'ont pas de signification intrinsèque. Elles ne sont pas interprétables directement comme

c'était le cas pour une représentation locale. A partir de plusieurs exemples, le réseau

développe une représentation interne: il apprend des configurations qui sont spécifiques à

chacun des concepts impliqués. Le réseau apprend ainsi à réaliser un codage interne, il

développe une représentation interne des données du problème. Puisqu'il n'existe pas de

lien explicite entre les neurones et la manière dont le concept est codé, il est très difficile

d'expliquer ce qui se passe à l'intérieur de ces réseaux, on les a d'ailleurs souvent comparés

à des boîtes noires.


25

Dans l'exemple de la figure 1.6, nous retrouvons la version distribuée de l'exemple de la

figure 1.4. En apprenant au réseau à répondre `jour' quand nous lui présentons `soleil' en

entrée, il a lui-même représenté le concept `jour' par le code distribué suivant: coloré, blanc,

blanc, coloré. Actuellement, ce sont surtout les réseaux à représentation distribuée qui sont

employés pour résoudre des problèmes de reconnaissance de formes.

Le principal inconvénient de l'utilisation de ce type de réseau est que la phase

d'apprentissage est coûteuse en temps et nécessite de grandes quantités de données

statistiquement réparties de manière uniforme. De plus, il est difficile d'expliquer le

comportement de ces modèles pas à pas.

2.4. Apprentissage connexionnisteUn des attraits principaux du formalisme des réseaux de neurones provient de sa capacité

d'apprentissage et de généralisation à partir d'exemples. L'apprentissage est vu comme

étant la possibilité de modifier la fonction d’un réseau en contrôlant ses coefficients

synaptiques pour adapter son comportement par retouches successives.

2.4.1. Niveaux de difficulté de l'apprentissage: Le but de l'apprentissage est d’améliorer

la réponse du réseau en modulant ses coefficients de contrôle selon un algorithme qui

présente trois niveaux de difficulté:

1er niveau. Exprimer le lien entre la réponse du système à améliorer et les paramètres qui

le définissent de façon à évaluer la direction suivant laquelle il est préférable d’évoluer. Ce

lien étant établi, il apparaît que l’information donnée par un seul exemple n’est pas

nécessairement pertinente. Il se peut, en effet, que plusieurs informations n’arrivent pas à

être départagées à la seule vue de cet exemple. Si l’on essaye, en réponse à ce problème, de

tenir compte simultanément de plusieurs exemples, il se peut alors que l’on obtienne des

informations contradictoires, que chaque exemple indique des directions d’amélioration

opposées et qu’aucune direction ne permette au système d’être simultanément amélioré sur

tous les points.

2ème niveau. Tenir compte de tous les exemples dont on dispose. Un algorithme

d’apprentissage doit tenir compte de ces deux niveaux de difficulté: le calcul de la

direction d’évolution permettant de tenir compte d’un exemple et le choix d’un compromis

pour tenir compte de tous les exemples.


26

3ème niveau. Ce niveau ne se situe pas sur le plan de l’algorithme, mais plutôt sur le plan

de sa mise en oeuvre. En effet, en fixant un graphe de connexion, on peut très bien, par

inadvertance, ne pas y inclure le système que l’on souhaite obtenir, ou, au contraire, se

donner un espace de recherche si grand que les quelques exemples dont on dispose ne sont

plus pertinents. Dans les deux cas, notre recherche ne peut aboutir: dans un espace trop

confiné, on ne peut qu’obtenir une machine réalisant un vague compromis et, avec trop de

liberté, on risque d’obtenir un réseau au comportement fort éloigné de celui souhaité aux

points non spécifiés comme exemples.

2.4.2. Types d'apprentissage: Il existe trois grandes classes d'apprentissage: non

supervisé, supervisé et semi-supervisé.

1. Apprentissage non supervisé. Les réseaux à apprentissage non supervisé (à capacité

acquise ou sans professeur) effectuent généralement des traitements comparables à

des techniques d'analyse de données (problèmes de classification). La modification

des poids synaptiques du réseau se fait en fonction d'un critère interne, indépendant

de l'adéquation entre le comportement du réseau et la tâche qu’il doit effectuer. La

règle d'apprentissage est en fonction du comportement local des neurones: on

renforce les connexions entre le neurone ayant le mieux reconnu un exemple et les

cellules d'entrée activées par cet exemple, ainsi, deux entrées proches produiront en

sortie deux valeurs proches. La première règle d'apprentissage connexionniste (règle

de Hebb) était non supervisée, elle était basée sur la proportionnalité entre la

modification de l'efficacité synaptique des connexions entre deux neurones et

l'activité simultanée de ces deux dernières.

2. Apprentissage supervisé. Le but de ce type d’apprentissage (à capacité enseignée ou

avec professeur) est d'inculquer un comportement de référence au réseau en

recherchant un jeu de poids synaptiques qui minimise l'erreur de sortie pour

l'ensemble des patrons afin d'améliorer graduellement le comportement du réseau.

• A chaque patron d'entrée, on associe une sortie désirée.

• Un patron est présenté en entrée, puis l'activité est propagée à travers le réseau.

Les sorties obtenues sont comparées aux sorties désirées.

• On détermine la correction à apporter aux poids du réseau en utilisant une

fonction permettant de calculer la modification à apporter aux poids en fonction

de l'erreur et d'un pas d'apprentissage constant.


27

En général, les règles d'apprentissage supervisé sont des formes de descente du gradient

où se pose le problème du choix du pas des itérations successives.

3. Apprentissage semi-supervisé. Ce type d'apprentissage, appelé aussi apprentissage

par renforcement (qualitatif ou pénalité-récompense) suppose qu'un comportement de

référence précis n'est pas disponible, mais, qu'en revanche, il est possible d'obtenir

des indications qualitatives (correct/incorrect) sur les performances du réseau. Le jeu

d'échecs est un exemple typique des problèmes d'apprentissage semi-supervisé. La

seule information dont dispose le système pour corriger l'ensemble des coups qui

constitue son environnement est l'évaluation finale de la partie.

2.4.3. Apprentissage par rétro-propagation du gradient

L'algorithme de rétro-propagation du gradient est l'aboutissement de l'évolution du

modèle à couches des réseaux de neurones. C'est probablement aujourd'hui l'algorithme le

plus utilisé, qui permet d'obtenir les résultats les plus satisfaisants dans beaucoup de

domaines d'application. Dans cette section nous nous limitons à une présentation intuitive,

le lecteur intéressé par une présentation plus formelle peut se référer à des documents tels

que [Dav 93, Jod 94a, Jod 94b, Her 94, Ors 95, Oso 98].

L'apprentissage est supervisé et fonctionne selon le principe suivant:

• On dispose d'un ensemble d'exemples qui sont les couples (entrées, sorties désirées).

A chaque étape, un exemple est présenté au réseau, une sortie réelle est calculée. Ce

calcul est effectué de proche en proche de la couche d'entrée à la couche de sortie.

Cette phase est appelée "propagation avant" ou "relaxation du réseau".

• Le réseau apprend en essayant de diminuer son erreur à chaque itération. Il le fait en

changeant l’intensité des connexions en sens inverse du signal d’erreur. Chaque

neurone de la couche de sortie calcule son signal d’erreur puis considère que les

cellules de la couche cachée sont responsables de cette erreur de manière

proportionnelle à leur contribution dans sa valeur. Par exemple, pour une cellule de la

couche cachée qui doit répondre avec la valeur 1 mais répond avec la valeur 0,

l’erreur consiste à n’avoir pas prêté assez attention aux cellules de la couche cachée

qui lui suggéraient d’être actives ou d’avoir trop prêté attention à celles qui lui

suggéraient d’être inactive. La solution est d’augmenter l’intensité des connexions

positives et de diminuer celle des connexions négatives en provenance des cellules

actives de la couche cachée.


28

• Le signal d’erreur des couches cachées n’est pas calculé directement, il doit être

évalué en fonction de l’erreur des cellules de la couche de sortie. Chaque cellule de la

couche cachée considère que son erreur peut s’estimer par la moyenne des erreurs

qu’elle a fait commettre aux neurones de sortie. L’importance de l’erreur dépend de

l’intensité de la connexion entre la cellule cachée et la cellule de sortie: il faut donc

pondérer l’erreur par l’intensité de la connexion reliant la cellule de la couche de

sortie puis renvoyer le signal d’erreur obtenu à la cellule de la couche cachée en

réutilisant les mêmes connexions mais dans le sens inverse, d’où le nom de Rétro-

propagation.

• Ce processus est répété, en présentant successivement chaque exemple. Si, pour tous

les exemples, l'erreur est inférieure à un seuil choisi, on dit que le réseau a convergé.

Bien que l'on ne dispose pas de preuve de sa convergence, cet algorithme donne de

bons résultats dans de nombreuses applications pratiques. En plus, il n'existe pas de

résultat théorique, ni de règle empirique satisfaisante, qui permette de dimensionner

correctement un réseau en fonction du problème à résoudre.

2.4.4. Problèmes d'apprentissage

Plusieurs problèmes peuvent intervenir au cours de l'apprentissage [Jod 94a]:

• Insuffisance de la règle d'apprentissage car rien ne garantit que la règle

d'apprentissage soit capable de tirer profit du potentiel du réseau.

• Minima locaux car la technique de descente du gradient, utilisée par la majorité des

apprentissages supervisé peut conduire à des solutions sous-optimales.

• Un mauvais choix de paramètres tels que le nombre de neurones cachés, par exemple,

peut compromettre l'apprentissage.

• Le sur-apprentissage (over-fitting) peut se produire quand l'apprentissage d'un réseau

est prolongé, ses poids reflèteront de trop près les particularités des exemples appris.

• Un mauvais échantillonnage du corpus d'apprentissage peut engendrer une mauvaise

généralisation.

• Oublis et interférences quand le corpus est grand ou que le comportement à

apprendre présente beaucoup de cas exceptionnels.


29

2.5. Avantages, inconvénients et applications des réseaux neuronauxL'intérêt porté aux réseaux de neurones tient sa justification dans les propriétés

intéressantes qu'ils possèdent; ils présentent aussi un certain nombre de limitations ou

d'inconvénients. A partir de ces propriétés, les applications potentielles de l'approche

neuronale peuvent être déduites [Dav 93, Hat 04, Oso 98].

2.5.1. Avantages de l'approche neuronale

L'exploitation de connaissances empiriques : L'apprentissage à partir d'exemples

(méthode d'apprentissage empirique) se fait d'une façon assez simple et permet d'obtenir de

bons résultats par rapport aux autres techniques d'apprentissage automatique.

La robustesse : Dans les réseaux de neurones, la mémoire est distribuée, elle correspond

à une carte d'activation de neurones. Cette carte est en quelque sorte un codage des faits

mémorisés ce qui attribue à ces réseaux l'avantage de résister aux bruits (pannes) car la

perte d'un élément ne correspond pas à la perte d'un fait mémorisé. Ainsi, un réseau peut

bien fonctionner même quand des unités sont en panne. De plus, de nombreux modèles de

réseaux donnent de bons résultats même quand leurs entrées sont bruitées.

La dégradation progressive : Les réseaux, de par leur nature continue, ne fonctionnent

pas

en tout ou rien et leurs performances ont plutôt tendance à diminuer progressivement en

cas de problème (bruit, panne, entrée inconnue...). Cette propriété est très recherchée car

les systèmes cognitifs vivants montrent une telle faculté. Les réseaux permettent de bien

généraliser les connaissances présentes dans la base d'apprentissage et sont moins sensibles

aux perturbations que les systèmes symboliques. Le fait de travailler sur une représentation

numérique des connaissances rend les réseaux plus adaptés pour manipuler des données

quantitatives (valeurs continues). Les réseaux de neurones sont moins vulnérables aux

données approximatives et à la présence de données incorrectes dans la base

d'apprentissage.

Le parallélisme massif : Les réseaux sont composés d'un ensemble d'unités de

traitement de l'information qui peuvent opérer en parallèle. Bien que la plupart des

implémentations des réseaux connexionnistes soient réalisées sur des simulateurs

séquentiels, il est possible de faire des implémentations (logicielles ou matérielles)

exploitant la possibilité d'activer simultanément les unités. La plupart des implémentations

des réseaux de neurones peuvent être facilement converties d'une version séquentielle vers

une version parallèle.


30

La prise en compte du non linéarité et du temps : Les réseaux de neurones artificiels

présentent l'intérêt de pouvoir prendre en compte la non linéarité (les fonctions d'activation

sont en général non linéaires). Certains réseaux peuvent aussi prendre en compte les

aspects temporels (cas des réseaux récurrents).

2.5.2. Inconvénients de l'approche neuronale

La difficulté de choix de l'architecture et des paramètres : Il n'existe pas de méthode

automatique pour choisir la meilleure architecture possible pour un problème donné. Il est

assez difficile de trouver la bonne topologie du réseau ainsi que les bons paramètres de

réglage de l'algorithme d'apprentissage. L'évolution du processus d'apprentissage est très

influencée par ces deux éléments (l'architecture du réseau et les paramètres de réglage) et

dépend beaucoup du type de problème traité. Le simple fait de changer la base

d'apprentissage utilisée, peut nous obliger à reconfigurer le réseau en entier.

Le problème d'initialisation et de codage : Les algorithmes d'apprentissage

connexionniste sont en général très dépendants de l'état initial du réseau (initialisation

aléatoire des poids) et de la configuration de la base d'apprentissage. Un mauvais choix des

poids employés pour initialiser le réseau, de la méthode de codage des données, ou même

de l'ordre des données, peut bloquer l'apprentissage ou poser des problèmes pour la

convergence du réseau vers une bonne solution;

Le manque d'explicabilité : Les connaissances acquises par le réseau sont codées par

l'ensemble des valeurs des poids synaptiques ainsi que par la façon dont les unités sont

interconnectées. Il est très difficile pour un être humain de les interpréter directement. Les

réseaux connexionnistes sont en général des boîtes noires, où les connaissances restent

enfermés et sont inintelligibles pour l'utilisateur ou pour l'expert. Un réseau ne peut pas

expliquer le raisonnement qui l'a amené à une solution spécifique.

Le manque d'exploitation de connaissances théoriques : Les réseaux classiques ne

permettent pas de profiter des connaissances théoriques disponibles sur le domaine du

problème traité. Ils sont dédiés à la manipulation de connaissances empiriques. Une façon

simpliste de profiter des connaissances théoriques consiste à convertir des règles en

exemples (prototypes). Cependant, cette méthode ne garantit pas que ces exemples vont

être bien représentés dans les connaissances du réseau à la fin de l'apprentissage, car nous

sommes obligés à passer pour une phase d'apprentissage où se mélangent sans distinction

des connaissances empiriques avec des connaissances théoriques codées par des exemples.


31

2.6. Applications de l'approche neuronaleVoici quelques unes des caractéristiques des problèmes bien adaptés à une résolution par

les réseaux de neurones:

• Les règles qui permettent de résoudre le problème sont inconnues ou très difficiles à

expliciter ou à formaliser. Cependant, on dispose d'un ensemble d'exemples qui

correspondent à des entrées du problème et à des solutions qui leurs sont données par

des experts.

• Le problème fait intervenir des données bruitées ou incomplètes.

• Le problème peut évoluer et nécessite une grande rapidité de traitement.

• Il n'y a pas de solutions technologiques courantes.

Grâce à ces caractéristiques, il est possible de retrouver les domaines privilégiés qui

constituent le coeur des applications des réseaux de neurones: la reconnaissance des formes

[BIS 95], la classification, la transformation de données (compression), la prédiction, le

contrôle de processus et l'approximation de fonctions. Ces tâches peuvent être regroupés en

deux catégories principales selon le type des sorties fournies par le réseau et le

comportement qui est recherché:

• Réseaux pour l'approximation de fonctions. Ce type de réseaux doit avoir une

sortie continue et sera employé pour l'approximation exacte (interpolation) ou pour

l'approximation approchée d'une fonction représentée par les données d'apprentissage

Ces réseaux sont capables d'apprendre une fonction de transformation (ou

d'association) des valeurs de sortie aux valeurs d'entrée. Cette fonction acquise par le

réseau permet de prédire les sorties étant données les entrées. On appelle ce type de

problème, un problème de régression. En général, les fonctions représentées sont des

fonctions avec des variables d'entrée et de sortie continues.

• Réseaux pour la classification. Ce type de réseau doit attribuer des classes (valeur

de sortie non continue) aux exemples qui lui sont fournis. La classification est un cas

particulier de l'approximation de fonctions où la valeur de sortie est discrète et

appartient à un ensemble limité de classes. Cet ensemble de classes peut être connu

d'avance dans le cas de l'apprentissage supervisé. Un réseau adapté à la classification

doit avoir des sorties discrètes ou implémenter des méthodes de discrétisation des

sorties (e.g. application d'un seuil de discrimination).


32

3. Intérêt de l'hybridationOn retrouve dans les recherches sur les systèmes hybrides l'ambivalence des approches

possibles en résolution de problèmes: certains veulent construire de meilleurs outils

informatiques pour résoudre des problèmes, d'autres veulent construire de meilleurs

modèles cognitifs et beaucoup ont des démarches intermédiaires en utilisant des idées

provenant des sciences cognitives pour obtenir de meilleurs outils informatiques [Ors 95].

Que ces recherches soient plutôt informatiques ou plutôt cognitives, elles ont un point

commun important: elles sont toutes motivées par l'incapacité actuelle d'un paradigme

donné (connexionniste, symbolique ou autre) à résoudre, à lui seul, des plusieurs types de

problèmes. Etant donné qu'il est très difficile d'inventer de toutes pièces un nouveau

paradigme plus satisfaisant, il serait avantageux de tirer parti des points forts de plusieurs

paradigmes et réaliser des systèmes ou modèles hybrides. Certains chercheurs vont encore

plus loin en donnant des justifications et des motivations cognitives à la réalisation de

modèles hybrides [Ors 95, Oso 98, Sun 97]:

• Il est indispensable de disposer de plusieurs modes complémentaires d'expression des

connaissances, de manière à pouvoir représenter le savoir-que et le savoir-faire

concernant un problème donné.

• Les systèmes hybrides sont une nécessité, en raison de la complexité des systèmes

cognitifs. Quand un chercheur examine les différents aspects d'un problème cognitif

et sélectionne les niveaux de description les plus utiles, le modèle qui émergera sera

un patchwork de composants de divers types, essentiellement symboliques et

connexionnistes, donc un modèle hybride.

Du point de vue de l'ingénieur des connaissances ou cogniticien, les arguments en faveur

de l'utilisation conjointe des techniques développées dans le cadre des approches

symbolique et connexionniste ne manquent pas [Gia 92]. Face aux problèmes posés par la

modélisation de la cognition humaine (et a fortiori, de l'expertise), il faut constater :

• L'échec de l'option 'tout-symbolique' tel que l'a révélé l'impossibilité de tenir les

promesses du programme de l'IA définies par les pères fondateurs.

• Le peu de chances d'aboutir, même à moyen terme, à des résultats probants si l'option

'tout-connexionniste' est choisie.

Hatzilygeroudis I., Prentzas J. [Hat 04] définissent deux sous-classes de l’approche

représentationnelle :


33

• Orientée connexionnisme : cette catégorie donne la prééminence aux concepts

connexionnistes (en offrant moins de capacités de modularité) comme c’est le cas des

systèmes experts connexionnistes.

• Orienté symbolique : cette catégorie donne la prééminence aux concepts symboliques

(en offrant moins de capacité de généralisation) comme c’est le cas des systèmes

experts connexionnistes.

Boudjemaa et al. [Boud 05] proposent une contribution à l’identification automatique de

personnes à partir de l’analyse texturale de l’image de l’iris de l’oeil. Le technique utilisée

consiste à extraire, tout d’abord, l’image de l’iris à partir de l’image globale de l’oeil saisie

par caméra en utilisant la transformation de Hough combinée avec l’opérateur de Canny.

Après une transformation de cette image en coordonnées polaires étirées, le filtre de Gabor

est, ensuite, appliqué à l’image rectangulaire obtenue.

4. ConclusionPlusieurs méthodes ont été développées en intelligence artificielle pour reproduire

certains aspects de l’intelligence humaine. Ces méthodes permettent de simuler les

processus de raisonnement en s’appuyant sur les connaissances de base disponible. Chaque

méthode comporte des points forts, mais aussi des limitations. Dans ce chapitre nous nous

sommes particulièrement intéressés à l’approche neuronale en mettant en évidence ses

principales propriétés, points forts et points faibles concernant la représentation et

l’acquisition des connaissances.

Notre étude nous a amené à mieux comprendre la tendance vers les systèmes hybrides

neuromimétiques depuis les années 90 ainsi que l’inexistence, du moins à notre

connaissance à travers la littérature, d’une orientation explicite vers ces approches dans un

domaine tel que celui de la RDF et plus particulièrement en productique.

Une autre façon de justifier l'utilisation conjointe des techniques et concepts développés

dans le cadre des approches hybrides émerge de l'étude de l'expertise et plus généralement

de la cognition humaine. Un être humain est hybride dans la mesure où ses concepts sont

hybrides. Ce constat a suscité notre intérêt en associant notre approche neuronale à la

Transformée de Hough que nous étudierons au chapitre 2.

Chapitre 2 La Transformée de Hough

34

CHAPITRE 2

La Transformée de Hough

1. Etat de l’art

La transformée de Hough est un outil de détection de courbes paramétriques dans

l’image, elle a été proposée par P.V.C Hough dans un brevet déposé en 1960 [Hou 62].

Inaperçu pendant plusieurs années, cette dernière a été vulgarisée par les travaux de

Rosenfield [Ros 69], Duda et Hart [Dud 72] au début des années 70 et fait l’objet par la

communauté scientifique depuis cette date à ce jour d’une particulière attention. Depuis les

années 80, elle a quitté les laboratoires de recherche pour trouver des champs

d’applications dans de nombreux domaines industriels [Off 85, Ill 88, Tzv 91] tels que la

vision par ordinateur et le traitement d’images. Elle est devenue une solution plus adaptée

au problème de détection des lignes droites, cercles ou tout autre forme paramétrique dans

l’image. Cependant, le calcul de la TH requiert de larges délais de traitement et beaucoup

d'espace mémoire, alors plusieurs nouveaux algorithme tels que la TH probabiliste, la TH

aléatoire, la TH hiérarchique, la TH incrémentale, ont été proposés pour améliorer ce

calcul, le rendre efficace et praticable pour son utilisation dans le traitement d’images en

temps réel.

Pour illustrer le principe de base de la TH, on considère par exemple, le problème de

détection d'un objet polyédrique dans une image, on doit avant toute détection, extraire les

traits de ce dernier puis reconstruire son image. Donc on est amené à extraire des lignes

droites où autrement dit les ensembles de points colinéaires. La méthode robuste qui peut

faire ce traitement doit tester la présence de droites formées par toutes les paires de points

de l'image, ce qui est extrêmement inefficace, vu que pour tester n points de l'image deux

par deux, on arriverait à un nombre exagéré d’itérations au moins supérieur à n².

Dans une image 512*512 cette méthode devient prohibitive [Sha 93]. La TH résout ce

problème car elle transforme les lignes du plan 2D de l'image en points dans le plan des


35

paramètres qui définit ces lignes, par conséquent elle convertit le problème de détection de

ligne en un autre plus simple celui de la détection des points d’intersection. Le principe

est de prendre toutes les paires de pixels appartenant aux contours de l'image et construire

un histogramme à deux dimensions appelé aussi le ‘’tableau accumulateur’’ qui servira à

enregistrer les droites ainsi trouvées pour chaque paire de pixel tirée. Tout point de l'image

faisant parti d'une de ces droites se voit incrémenter d'un crédit dans l'histogramme.

Tout en gardant la même idée principale du calcul de la TH citée ci dessus; ils existent

plusieurs façon de traiter les points de l’image, ce qui nous donne diverses techniques de la

TH. Celles-ci sont énumérées comme suit:

a) Transformée de Hough probabiliste

Contrairement à la transformée de Hough standard qui applique la TH pour tous les

pixels d’une image contours, la transformée de Hough probabiliste [Kir 91, Ber 91] affirme

qu’il suffit de calculer la TH seulement pour une portion α de pixels de cette

image ( )1000 <<α . Ces pixels sont choisis aléatoirement à partir de la densité de probabilité

uniforme définit sur l’image. Kiraty et al [Kir 91] préconisent d’utiliser une valeur α

comprise entre 10% et 20%, cette variation dépend de l’application.

b) Transformée de Hough aléatoire

La TH aléatoire est présenté dans [Kit 88] et les explications peuvent être aussi trouvé

dans [Air 94, Mur 95]. Brièvement, la TH aléatoire, utilise une autre technique pour

générer des valeurs dans le tableau accumulateur définit sur le plan de paramètres. Dans le

cas de la détection d’une ligne droite dans la TH standard, un pixel de l’image correspond

à une courbe dans le plan de paramètres, celui-ci est discrétisée et enregistré dans le

tableau accumulateur, par contre dans la TH aléatoire, une paire de pixels est choisit

aléatoirement et les paramètres de la ligne unique qui passe par ces pixels sont calculés.

Cette ligne est enregistrée comme la seule entrée dans le tableau accumulateur et les pixels

de cette dernière sont ensuite enlevés, et laissent une image simple à analyser. De cette

façon, les entrées sont accumulées dans l’espace des paramètres. Cet algorithme est ensuite

répété pour détecter les lignes suivantes un nombre de fois dans le temps, où le nombre des

itérations est beaucoup moins que le nombre de paires de pixels dans l’image.

L’algorithme s’arrête quand aucune ligne n’est détectée pour ce nombre d’itérations.

c) Transformée de Hough hiérarchique

La TH hiérarchique combine une structure pyramidale avec la transformée de Hough

(voir la figure 2.1). L’image est organisée en grille de sous-images et la TH est appliquée


36

sur chacune d’elle. Typiquement, chacune de ces sous-images va contenir au plus deux

lignes. Ces résultats sont propagés vers le haut à travers la pyramide. Pour chaque n ud du

prochain niveau, on prend le chevauchement à l’aide d’un masque 4*4 du niveau

précèdent. Les lignes de ces dernières sont fusionnées en utilisant l’algorithme de la TH.

Ces lignes sont propagées au prochain niveau hiérarchique. Cet algorithme est répété

jusqu’au niveau le plus haut de la pyramide, où on trouve un seul n ud. Ce n ud

représente alors l’image entière. Les détails sont donnés dans [Lot 94].

Figure 2.1. Structure pyramidale de la transformée de Hough hiérarchique

d) Transformée de Hough incrémental

Pour appliquer la TH dans les tâches de traitement d’image en temps réels, son calcul

doit être le plus court possible. Habituellement la TH dans le cas particulier des droites, est

définit par l’équation : ( ) 0sincos,,, =−−= θθρθρ yxyxf , donc son calcul réclame

l’utilisation des formules trigonométrique et des multiplications, ce qui nécessite un temps

de calcul énorme. Pour remédier à ce problème, on utilise la transformée de Hough

incrémental. Cette dernière utilise une autre expression de la TH, définit par des fonctions

d’additions et des décalages [Ach 04].

2. Principe de la transformée de Hough

Une droite est décrite dans le plan cartésien ( )xy par l’expression suivante :

f (y,x,a,b) = y – ax – b = 0 (1)

Sachant que a est la pente et b l’ordonnée à l’origine des abscisses.

Etant donné un ensemble de contours d’objets représentés par un ensemble de points

discrets Mi, nous cherchons à déterminer si un ou plusieurs sous-ensembles de points Mi

font partie d’une courbe dont les paramètres a et b restent à définir. Si nous cherchons à

level i

level i+1

Central Sub-images


37

tester les n points Mi deux par deux, nous arriverons à un nombre exagéré d’itérations au

moins supérieur à n2.

Hough puis Rosenfeld [Hou 62, Ros 69] ont proposé une méthode pour détecter les

droites à l’aide des points du plan (x,y). Son principe est de calculer pour chaque point Mi

de coordonnées ( xi , yi ), du contour d’un objet, l’ensemble des paramètres a qui vérifient

l’équation f ( yi , xi , a , b ) = 0 avec b fixé.

Pour chaque point Mi ( xi , yi ), de l'image, il y a un ensemble de valeurs possibles pour les

paramètres a et b. Cet ensemble forme une droite d'équation yaxb +−= dans l'espace des

paramètres (ab) appelé espace de Hough. Deux points ip et jp de cordonnées (xi , yi) et

(xj , yj ) respectivement, appartenant à la même droite, forment des droites dans l'espace

des paramètres (ab), qui se coupent au point N de coordonnées (a , b ). De cette façon tous

les points qui appartiennent à la même droite forment des droites dans le plan des

paramètres (ab) qui se coupent au même point. Ce concept est illustré dans les

figures 2.2.a et 2.2.b.

x i x j x

y i p i

p j

y j

a’ a

b = - a xi + yi

b’ N b = - a xj + yj

b

(a) (b)

Figure 2.2. Transformée de Hough

(a) Plan cartésien (xy)

(b) Plan des paramètres (ab)

Le traitement Hough consiste en une quantification du plan des paramètres en cellules

accumulatrices sur la figure. 2.3 où ( )maxmin ,aa et ( )maxmin ,bb sont les valeurs limites de

l’intervalle de la pente a et de l’ordonnée à l’origine des abscisses b.


38

bmin 0 bmax

amin b

0

amax

a

Figure 2.3. Quantification du plan des paramètres (ab)

Chaque cellule de coordonnées ( )ji, a une valeur accumulée ( )jiA , et correspond à la

cellule de coordonnées ( )ji ba , dans le plan des paramètres (ab). Initialement, ces cellules

sont mises à zéro. Pour chaque point de l’image de coordonnées ( )kk yx , , on calcule pour

chaque valeur de a quantifié a la valeur pa sur l’axe des a, son correspondant b en utilisant

l’équation suivante : kk yaxb +−= . La valeur résultante résultat b est arrondi à la valeur

la plus proche de b quantifiés qb sur l’axe des b. Si on obtient une valeur qb suite à pa

choisie, on incrémente la valeur de la cellule correspondante: ( ) ( ) 1,, += qpAqpA

A la fin de cette procédure, la valeur n de ( )jiA , dans une cellule ( )ji, correspond à n

points dans le plan ( )xy qui vérifient l’équation ji bxay += , donc il existe n points qui

appartient à la droite de pente ia et de l’ordonnée à l’origine des abscisses jb .

L’inconvénient majeur de cette procédure réside dans son incapacité de détecter les

droites verticales. Pour remédier à ce problème, un paramétrage polaire ( )θρ, est plus

satisfaisant. Ce paramétrage est illustré dans la figure 2.4.

Une droite est alors définie par l’équation suivante :

( ) 0sincos,,, =−−= θθρθρ yxyxf (2)

avec ρ la distance perpendiculaire à la droite de l’origine du plan ( )xy et θ l’angle entre

cette distance et l’axe des x.


39

Y

ρ

θ0 X

Figure 2.4. Paramétrage polaire d'une droite

L’utilisation de cette représentation dans la construction du tableau accumulateur est

identique à celle développée précédemment (représentation ab sur la figure 2.5).

On précisera que le choix de quantification de l’espace des paramètres ( ρ θ ) doit

porter sur les trois objectifs essentiels suivants:

1. Garantir une précision de détection aussi bonne que possible,

2. Diminuer la mémoire nécessaire au stockage des accumulateurs,

3. Accélérer les calculs.

θmin 0 θmax θρmin

0

ρmax

ρ

Figure 2.5. Quantification du plan des paramètres )

Chaque point iM de coordonnées ( )ii yx , d’une droite se transforme dans le plan des

paramètres (ab) en une sinusoïde d’équation : θθρ sincos ji yx += .


40

Donc une droite sera représentée par un ensemble de sinusoïdes qui se coupent en un seul

point de coordonnées polaires ( )00 ,θρ caractéristique de cette droite dans le plan des

paramètres (se référer aux figures 2.6-a et 2.6-b).

Y

M1

ρ0 M2

θ0

0 X

θπ

θ0

0

-π0 ρ 0.5 ρ0 1

(a) (b)

Figure 2.6. Transformée de Hough

(a) Plan cartésien (xy)

(b) Plan des paramètres (ab)

3. Dimension des paramètres et

3.1. Champ de la dimension de

Le champ de la dimension de θ est [ ]π2,0 . Pour un angle θ appartenant à cet intervalle,

toutes les droites s’expriment avec un ρ positif. Nous remarquons que les droites dont θ

appartenant à l’intervalle [ ]ππ 2, peuvent être vue comme des droites à ρ négatif, donc

l’intervalle de θ peut être réduit de moitié, c’est à dire le champ de θ sera [ ]π,0 et pour

chaque valeur θ appartenant à cet intervalle toutes les droites s’expriment avec un ρ pas

strictement positif. En effet si on considère la droite D2 avec les paramètres polaires

( )2,2 θρ avec : 12 +=

22 sin*+cos*=2 yx

( ) ( )112 sin*cos* yx +++=

( )112 sin*cos* yx +−=

12 −=


41

La droite D2 de la figure 2.7 est vue comme la droite D1 mais avec un ρ opposé

( )12 ρρ −= .

D1 Y

ρ1

θ1

Xθ2

ρ2

D2

Figure 2.7. Paramètres polaires de deux droites opposées

3.2. Champ de dimension de

Le champ de dimension de est défini selon la taille de l’image. Pour une image carrée

N*N. A partir de la figure 2.8, on trouve que le champ de dimension de est [ ]2,0 N .

0 N x

Max

N

y

Figure 2.8 Le champ de la dimension de ρ.

Si nous déplaçons l’origine O du repère du plan (x y) au centre de l’image, puis nous

examinons les valeurs Minρ et maxρ de la dimension de ρ .

- maxρ est donnée par la plus grande distance de la droite par rapport à l’origine o. Cette

droite est représentée par la droite D2 dans la figure 2.9 et2max

Max=ρ .


42

- minρ est la plus petite distance négative de la droite par rapport à l’origine O. Elle est

représentée par la droite D1 et2min

Max−=ρ .

Y M ax

ρmax

D 2

0 X

D 1

ρmin

M ax.

Figure 2.9 Le champ de la dimension de ρ.

3.3. Propriétés de la transformée de Hough

• Un point du plan cartésien correspond à une sinusoïde dans le plan des paramètres.

• Un point du plan des paramètres correspond à une droite dans le plan cartésien.

• Les points appartenant à la même droite dans le plan cartésien correspondent au point

d’intersection des courbes du plan des paramètres.

• Les points appartenant à la même courbe du plan des paramètres correspondent à des

droites du même point du plan cartésien.

4. Utilisation de la transformée de HoughL'extraction des lignes droites utilisant le tableau accumulateur de Hough est une tâche

qui nécessite la prise de certaines précautions car les n points, d'une cellule du tableau

accumulateur, n'indiquent pas s'ils sont approchés ou dispersés. Ceci induit le problème

d'extraction de fausses droites ou droites insignifiantes. Ce problème est accentué lorsqu'on

a une image trop éclairée (création de zones d’ombre) et une image qui possède un nuage

de points (une image trop bruitée).

Pour résoudre ce problème, on élimine d’abords tous les segments de droite ayant un

nombre de points réduit dans le tableau accumulateur, ensuite on scrute les cellules

accumulatrices de ce dernier en cherchant les droites significatives [Ati 92, Mar 97].


43

Ces droites sont des droites réelles qui existent dans l’image telles que les arrêtes d’un

objet quelconque dans cette image. Une droite significative se présente par un pic (sommet

d’une montagne). Lorsqu’on représente le tableau accumulateur en relief 3D sur la

figure 2.10, une droite significative doit avoir les caractéristiques suivantes:

• Sa longueur ne doit pas être trop petite devant un seuil donné (seuilH).

• La longueur des segments de droite qui forment cette droite ne doit pas être inférieure

à un seuil donné (seuilC), sinon ils seront éliminés.

• Les points qui forment ces segments de droite ne doivent pas être trop espacés, donc

la distance séparant deux points ne doit pas être supérieure à un troisième seuil

donné (seuilD).

Donc pour avoir une bonne détection des droites significatives, il faut faire un

compromis entre les trois seuils seuilH, seuilD et seuilC suivant le domaine d'application

utilisé.

Figure 2.10 Le plan de Hough en relief

Nous remarquons aussi qu'il y a présence des vallées et des montagnes avec leurs pics.

Les pics des montagnes correspondent aux droites réelles qui existent dans l'image, par

contre les vallées ne correspondent en réalité à rien car elles sont les conséquences du

calcul de la transformée de Hough.


44

5. Implémentation de la Transformée de HoughLa transformée de Hough est un outil puissant dans l'analyse des formes et utilisée aussi

pour l'extraction des traits globaux des formes dans l'image. Elle donne de bons résultats,

même en présence de bruits dans l'image. La transformée de Hough (TH) opère sur des

données binaires des points contours de l'image. Chaque point contour de coordonnées (xi ,

yi) de l'image est transformé en une sinusoïde dans le plan des paramètres ρθ.Elle

contribue dans ce plan par l'incrémentation de la cellule (ρj ,θj) du tableau accumulateur

crée par cette transformation où θj est une valeur discrète suivant la résolution choisie de θ

dans l'intervalle [0 , π]. Initialement les cellules du tableau accumulateur sont mises à zéro

[Pri 94, Tzv 91, Del94]. Les points contours colinéaires de l'image produisent des

sinusoïdes dans le plan des paramètres qui se croisent en un point commun (ρ , θ). Nous

affectons dans la cellule (ρ , θ) du tableau accumulateur, avec ρ la distance normale à la

droite qui porte ces points colinéaires de l'origine de l'image et θ l'angle entre cette distance

avec l'axe des x, le nombre de croisés des courbes au point d'intersection (ρ , θ) dans le

plan des paramètres. La quantification du plan des paramètres ρθ revient à quantifier

l'intervalle 0 ≤ θ < π pour la dimension de θ et l'intervalle -R ≤ ρ ≤ R pour la dimension

de ρ, avec R la moitié de la diagonale de l'image. De plus, si nous prenons :

ρk et θk pour pas de quantification des dimensions de ρ et θ .

nρ et nθ le nombre de valeurs discrètes dans les intervalles de ρ et θ .

Les valeurs de ρ et θ discrètisées s'écrivent comme suit :

θ = t * θk 0 ≤ t ≤ nθ (3)

ρ = -R + r * ρk 0 ≤ r ≤ nρ (4)

Avec n et nR

k kθ ρ

πθ ρ

= =2

(5)

Pour chaque point contour de coordonnées (x , y) de l'image, nous calculons pour chaque

valeur discrète de θ la valeur discrète de ρ suivant l'équation suivante :

ρ = x *cosθ + y *sinθ ,

Ensuite, nous incrémentons la cellule correspondante dans le tableau accumulateur. Nous

faisons la même chose pour tous les points contours de l'image.

L’organigramme ci-dessous de la figure 2.11 décrit ce calcul.


45

Début

initialisation dutableau accumulateur

y=0

x=0

nonIMG[x][y] un point

contour

ouit =0

θ = t* θkρréel = x*cos θ + y*sinθDiscrétisation de ρréel

dans l'intervalle[-R, R]

Incrementation dela cellule (ρ , θ)

t++

ouit ≤ nθ

non

x++

ouix ≤ MaxX

non

y++

ouiy ≤ MaxY

non

Fin

Figure 2.11 Organigramme de la TH


46

A la fin de ce calcul, une valeur M se trouvant dans une cellule quelconque (ρ , θ) du

tableau accumulateur indique que M points de l'image appartiennent à une même droite

dont les paramètres polaires sont ρ et θ. Mais, nous ne pouvons pas savoir que ces M

points de l'image sont rapprochés ou dispersés.

C'est le problème d'existence de fausses droites ou droites insignifiantes sur la figure 2.12.

droites réelles

droites insignifiantes

Figure 2.12. Droites réelles et insignifiantes

Donc pour avoir une bonne détection des droites significatives, il faut faire un

compromis entre les trois seuils seuilH, seuilD et seuilC suivant le domaine d'application.

Par des tests d’expérimentation nous avons implémenté la Transformée de Hough (TH)

sur la station Bull. DPX2000, en langage C sous Unix, et nous l'avons appliquée sur une

image en niveaux de gris de dimension 256*256 (figure 2.13).

Figure 2.13. Image en niveaux de gris


47

La détection de contours est faite par l'opérateur "Roberts" avec un seuil de 30 sur la

figure 2.14.

Figure 2.14. Image contour

Si nous reprenons nos tests et que l’on désire comparer le temps de traitement " tTr "

pour la détection des droites significatives, en d’autres termes plus équivoque entre le

temps de traitement qui tient compte de toutes les cellules accumulatrices du tableau

accumulateur, c'est-à-dire les cellules qui forment les vallées et les pics - (se référer aux

images résultats IM2, IM4, IM6 et IM8 de la figure 2.15) et le temps de traitement qui ne

tient compte que des cellules accumulatrices qui forment les pics, après élimination des

cellules accumulatrices qui forment les vallées - (images résultats IMM2, IMM4, IMM6 et

IMM8) pour les différentes valeurs du seuilD de la figure 2.15).

Nous constatons par conséquent que nous avons obtenu les résultats suivants:

Par hypothèse, nous prenons le seuilH égale au seuilC, égaux tous les deux à 10 pixels,

c'est à dire que nous ignorons toute droite ou segment de droite dont la longueur est

supérieure à 10 pixels, les pas de quantification de ρ et θ sont : ρk=1 et θk =10°.


48

IM2 IMM2 seuilD=2, tTr =5s seuilD=2, tTr=2s

IM4 IMM4 seuilD=4, tTr=5s seuilD=4, tTr=2s



Figure 2.15. Images Résultats

tTr est le temps de traitement de la TH


49

Nous remarquons aussi qu’en ignorant les cellules accumulatrices qui forment les vallées,

le temps de traitement de la détection des droites significatives diminue

considérablement. Ce temps de traitement diminue encore si nous augmentons le seuil

seuilH et le seuilC, éliminant ainsi les segments de droite de longueur moyenne.

6. Etat de l’art : Evaluation en ligne d’Algorithmes de la TH6.1 Algorithme de H.Koshimizu et M.Numada

L’algorithme de H.Koshimizu et M.Numada se présente comme suit :

ρn+1=ρn+ε.ρ’n 0≤ 1 <K/2-1 (1)

ρ’n+1=ρ’n-ε.ρn+1 K/2-1≤ n < K (2)

Sachant que n et k sont respectivement l’indice et le nombre de divisions de l’axe θ

dans l’espace des paramètres.

Dans le mode de traitement en ligne, à chaque cycle de calcul, les équations de

récurrence sur les entrées et les sorties sont données par :

ρn+1[J]=ρn+1[J-1]+rn+1[J].b-J (3)

ρn[J]=ρn[J-1]+rn[J].b-J (4)

ρ’n+1[J]=ρ’n+1[J-1]+r’n+1[J].b-J (5)

ρ’n[J]=ρ’n[J-1]+r’n[J].b-J (6)

L’expression de la sortie ρn+1 au pas J s’écrit :

ρn+1[J]=ρn[J]+ε.ρ’n[J] (7)

En remplaçant ρn+1[J],ρn[J], ρ’n[J] et ρ’n+1[J] par les systèmes (3), (4), (5) et (6), on

obtient le résidu partiel Res défini comme suit :

Res[J]=2-J.|2-p.( ρn[J]+ε.ρ’n [J])- ρn+1| (8)

Pour la convergence de l’algorithme, il faut que :

2-J.| Res[J]| ≤2-j/2

| Res[J]| ≤1/2 (9)

D’où

Res[J]=2.Res[J-1]+L[J]-rn+1[J] (10)


50

L’expression de l’accumulation partielle :

L[J]= 2-p.( rn[J]+ε.r’n [J])

Le calcul du résidu complet H[J] est alors défini comme suit:

H[J]= 2.Res[J-1]+L[J] (11)

Ou H[J]= 2.H[J-1]+L[J]-2. rn+1 [J-1] (12)

A partir de l’équation (9.), on aura:

-3/2≤H [J-1] ≤3/2

Le problème est de définir la valeur minimale du retard p pour lequel le processus de

calcul converge vers rn+1. Pour cela, il est nécessaire qu’à chaque cycle de calcul, la

condition d’arrondissement suivante soit vérifiée:

Max(H[J]) ≤3/2

Max (2.Res[J-1]+L[J]) ≤3/2

p≥log2(|2.Max( rn[J]+ε.r’n [J])|)

Avec Max(rn[J])=1

Et Max(r’n[J])=1

= /100ó = 2-5 = 0.0313

On aura p ≥ 1.0446 => p=2

Le même procédé mathématique sera appliqué à l’équation

ρ’n+1[J]=ρ’n [J]-ε.ρn+1[J]

Donc l’expression du retard p est donné par :

p≥log2(|2.Max( r’n[J]-ε.rn+1 [J])|) => p=2

Procédure de sélection :

A partir des équations (11) et (12), on peut déduire la procédure de sélection du bit

résultat rn+1 [J]:

H[J]= 2.H[j-1]+L[J]-2. rn+1 [J-1] (13)

rn+1 [J]=S(H[J]


51

6.2 Algorithme de S.Tagzout et al. [Tag 01].

Les nouvelles expressions de la TH incrémentale s ‘écrivent comme suit :

ρn+1=ρn+ε.ρn+K/2 (1)

ρn+1+K/2=ρn+K/2-ε.ρn (2)

Avec ρn+K/2=ρ’n ρ0=x et ρK/2=ρ’0= y

Dans le mode de calcul en ligne les expressions des entrées et sorties sont données par :

ρn+1[J]=ρn+1[J-1]+rn+1[J].b-J (3)

ρn[J]=ρn[J-1]+rn[J].b-J (4)

ρn+K/2[J]=ρn+K/2[J-1]+rn+K/2[J].b-J (5)

ρn+1+K/2[J]=ρn+K/2[J-1]+rn+1+K/2[J].b-J (6)

L’expression de la sortie ρn+1 au pas J s’écrit :

ρn+1[J]=ρn[J]+ ε.ρn+K/2[J] (7)

Le résidu partiel Res est défini comme suit :

Res[J]=2-J.|2-p.( ρn[J]+ε.ρn+K/2[J])- ρn+1| (8)

Pour la convergence de l’algorithme, il faut que :

2-J.| Res[J]| ≤2-j/2

| Res[J]| ≤1 (9)

D’où

Res[J]=2.Res[J-1]+L[J]-rn+1[J] (10)

L’expression de l’accumulation partielle :

L[J]= 2-p.( rn[J]+ε.rn+K/2 [J])

Le calcul du résidu complet H[J]est :

H[J]= 2.Res[J-1]+L[J] (11)

H[J]= 2.H[J-1]+L[J]-2. rn+1 [J-1] (12)

A partir de l’équation (9.), on aura

-3/2≤H[J-1] ≤3/2


52

La valeur minimale du retard p pour lequel le processus de calcul converge vers rn+1 est

définie à partir de la condition d’arrondissement suivante:

Max(H[J]) ≤3/2

Max(2.Res[j-1]+L[J]) ≤3/2

p≥log2(|2.Max( rn[J]+ε.rn+k/2 [J])|)

Avec Max(rn[J])=1

et Max(rn+k/2[J])=1

ε = /100ó = 2-5 = 0.0313

On aura p≥1.0446 => p=2

Le même procédé mathématique sera appliqué à l’équation

ρn+1+K/2=ρn+K/2-ε.ρn

donc l’expression du retard p est donné par :

p≥log2(|2.Max( rn+k/2[J]-ε.rn [J])|) => p =2

Procédure de sélection :

À partir des équations (11.) et (12.) on peut déduire la procédure de sélection du bit

résultat rn+1 [J]:

H[J]= 2.H[J-1]+L[J]-2. rn+1 [J-1] (13)

rn+1 [J]=S(H[J]

6.3 Algorithme proposé [Bou 06a].

Nous venons de voir dans les parties précédentes, la modélisation de la TH incrémentale

ainsi que l’algorithme de S.Tagzout et al dans le mode de traitement en ligne.

Nous venons de voir aussi dans le paragraphe précédent, que la TH incrémentale proposée

dans [Tag 01], conduit à l’utilisation de la TH standard pour corriger les erreurs de calcul,

ce qui nécessite l'utilisation des LUTs. De cela, on a essayé d’améliorer l’algorithme de

S.Tagzout et al afin d’optimiser les performances de calcul global de la TH pour l’utiliser

dans les applications en temps réels. Tout le travail a été concentré pour trouver un

algorithme qui n’utilise plus la TH standard et augmente le nombre de ρ générés pour des


53

intervalles très réduit de , ce qui permet d'éliminer l'utilisation des LUTs et de ne plus

effectuer des calculs trigonométriques au cours du traitement, ainsi l'espace occupé et le

temps globale de calcul seront réduits. L'idée de base de cet algorithme est de générer M

valeurs de ρ dans un intervalle réduit de θ , où les approximations sur sin et cos

n'engendrent pas d'erreurs significatives sur les résultas. En utilisant les mêmes

approximations sur cos et sin et les mêmes notations du paragraphe précédent, on obtient

pour chaque valeur de nθ , M valeurs de ρ générées en même temps dans l'intervalle

[ [Mπ,0 de θ .

Notre algorithme est défini par l'expression générale suivante:

≥−

<=

+

=

+=

<≤

≤<<≤

+++++

21

21

sin.cos.

..

0

10

21

Mmsi

Mmsi

MKmy

MKmx

MKn

KMetMm

MKm

KM

KmnM

KmnM

Kmn

α

εερ

ρεαρρ α

(1)

Avec :

- ε est la résolution deθ .

- M est le nombre de valeurs de ρ générées en même temps.

- K représente le nombre de division deθ .

- iρ est la valeur de ρ obtenue pour un angle iθ de l'axe deθ .

Cette expression peut être réarrangé pour aboutir au système d’équations suivant:


54

−

=

+

=

−=

+=

<≤<<<≤

+

++++++

+++++

εερ

εερ

ρερρ

ρερρ

..sin...cos.

..sin...cos.

.

.

01,2

0

2.

.

.2

.2

.1

2...1

MKmx

MKmy

MKmy

MKmx

MKnetKMMm

KM

Km

MKm

MKmnK

MKmnK

MKmn

KM

KmnM

KmnM

Kmn

(2)

Pour cette nouvelle expression, on note que:

- Les valeurs initiales sont calculées par les deux équations

MKmρ et

+

2K

MKmρ .

- Pour calculer la prochaine valeur de ρ ( )1+nρ dans l'intervalle

+

MKm

MKm .)1(

,.

on a

besoin de l'ancienne valeur de ρ ( )nρ calculée dans le même l'intervalle et l'ancienne

valeur de ρ

+2Kn calculée dans l'intervalle

+

++

2.)1(

,2

. KM

KmKM

Km en même

temps et vice versa.

- Les valeurs de ρ calculés dans les intervalles

+

MKm

MKm .)1(

,.

et

+

++

2.)1(

,2

. KM

KmKM

Km sont générées en même temps ce qui réduit le temps de calcul

global de la TH.

- La valeur de M doit être paire.

- La valeur de MK doit être entière.

- Si on prend M=2, on retrouve l'algorithme de S.Tagzout et al, cité précédemment.


55

7. ConclusionLa transformée de Hough est une méthode de vote très robuste. La version originale de la

méthode proposée par Hough a été modifiée par [Dud 72]. Depuis plusieurs variantes ont

été proposées [Kit 88]. Cette approche repose sur une discrétisation de l’espace des

paramètres. On obtient alors des hypercubes dans l’espace d’état auquel sont associés des

accumulateurs. Pour un jeu de données de taille minimale, les paramètres recherchés sont

estimés et l’accumulateur correspondant de l’hypercube est incrémenté. Ce processus est

itéré jusqu’à considérer toute les combinaisons possibles des données à disposition.

L’accumulateur ayant la valeur la plus importante correspond alors à la meilleure

estimation des paramètres.

La transformée de Hough est bien adaptée aux problèmes ayant un nombre important de

données par rapport aux nombre des paramètres à estimer. En effet, si les données et les

inconnues sont de taille équivalente, il est difficile de trouver un accumulateur

prépondérant par rapport aux autres. En plus, dû à la discrétisation et au bruit, il est

possible que l’optimum soit délocalisé. La transformée de Hough est très robuste car elle

effectue une recherche globale et exhaustive. Finalement, cette technique est capable de

segmenter les données en plusieurs populations qui vérifient le modèle de référence.

Toutefois, la transformée de Hough est très rarement utilisée seule en vision robotique car

pour des problèmes qui nécessitent l’estimation de plus de trois ou quatre paramètres, les

temps de calculs deviennent prohibitifs.

L'implémentation de la transformée de Hough sur un système informatique a l’avantage

de présenter un large éventail de tâches à exécuter en parallèle. Ce dernier peut exécuter

d'autres algorithmes en plus de la transformée de Hough et être capable de donner une

performance aux calculs antérieurs tels qu’une segmentation ou aussi une détection de

contours.

Dans ce chapitre, nous avons présenté l’évaluation de la transformée de Hough en

utilisant le mode de calcul en ligne. L’algorithme élaboré permet de générer tous les

paramètres de la transformée de Hough d’une manière très rapide et ceci grâce au mode de

présentation des données en série, poids forts en tête. Les performances de l’architecture

pipeline résident essentiellement dans la manière de génération des bits résultats rn+1 et

rn+1+k/2. Pour une meilleure illustration, nous avons implémenté notre algorithme sur un

circuit FPGA de Xilinx, plus précisément la famille Virtex2, qui contient un module de

génération des paramètres (ρ,θ) ainsi que le module nécessaire pour le processus de vote.


56

Cette dernière dispose de ressources dédiées aux opérations arithmétiques et aussi dans le

domaine de traitement de signal. Le circuit donne de très bons résultats en terme de

performances temporelles.

L’idée d’utiliser la TH est due à sa robustesse dans l’analyse de l’extraction des

primitives d’objets et aussi à ses propriétés d’implémentation hardware.

La Transformée de Hough Incrémentale Généralisée (THIG) permet d’optimiser en

temps et en espace le calcul global de la TH, ce qui justifie notre choix de l’étudier dans

notre projet.

Par conséquent, dans le chapitre qui va suivre, nous présentons un système de

reconnaissance de formes 3D moyennant un processus hybride basé sur une approche

connexionniste associant la TH. Cette étape est très importante pour notre

expérimentation .en vision robotique car elle solutionne un des aspects de la problématique

de la perception et de la compréhension automatiques de l’environnement.

Chapitre 3 Reconnaissance de formes par approche hybride en RM

57

CHAPITRE 3

Reconnaissance de formes

par approche hybride en

Robotique Mobile

1. Robotique mobile : Etat de l’artDu fait des progrès de l’informatique tant au point de vue logiciel que matériel, la

recherche sur les robots mobiles se poursuit actuellement de manière intensive. Les robots

mobiles représentent en fait un terrain d’essai formidable pour confronter les techniques de

Reconnaissances des Formes (RDF) et d’Intelligence Artificielle (IA) avec la complexité

du monde réel et les contraintes de la robotique.

ALVINN [Bat 96, Bal 96] (Autonomous Land Vehicle In a Neural Network) développé

en 1996 à l’Université de Carnegie Mellon aux USA est un système de perception qui

apprend à commander les véhicules de NAVLAB en observant une commande de

personne. La couche d'entrée du réseau est une "rétine" bidimensionnelle de l'unité 30x32

qui reçoit l'entrée de l'appareil photo visuel de véhicules. Chaque unité d'entrée est

entièrement reliée à une couche de cinq unités cachées qui alternativement sont

entièrement reliées à une couche de 30 unités de rendement. La couche de rendement est

une représentation linéaire de la direction que le véhicule devrait voyager afin de garder le

véhicule sur la route.

HILARE : [Fla 01, Dup 01]. Ce robot a été développé au Laboratoire d’Automatique et

d’Analyse des Systèmes du CNRS (LAAS) de Toulouse. Le calcul de localisation de

Hilare 2, consiste en une fusion de données odométriques et de positions calculées par

appariements de segments laser.

ORASIS : [Rem 05]. Le robot construit par l’INRIA Rocquencourt est muni de deux

caméras pour permettre l’acquisition de la distance par stéréovision. Ce dernier s’est vu


58

attribuer une caméra supplémentaire pour améliorer la qualité des résultats. D’autres

capteurs de proximité (ultra-sons) et de déplacement (capteurs sur les roues) interviennent

également.

Le cadre de notre étude est plus particulièrement la description tridimensionnelle d’une

scène observée par un robot mobile évoluant dans un environnement de laboratoire où

d’atelier, sous des conditions naturelles d’éclairage. Les limites inhérentes aux méthodes

actives d’acquisition de l’information 3D nous ont amené à préférer une méthode

d’acquisition passive, en l’occurrence la stéréovision car elle est la seule à fournir

l’information de distance absolue nécessaire pour connaître la position du robot mobile.

Néanmoins l’utilisation d’un capteur actif de type laser pour la reconnaissance et la

manipulation d’objets manufacturés productique est particulièrement efficace et fort

intéressante. Ce travail est décrit et validé dans les chapitres 4 et 5.

2. Vision StéréoscopiqueLa vision stéréoscopique est un outil privilégié pour calculer la géométrie

tridimensionnelle d’une scène observée par une ou deux caméras. La première étape du

calcul est la mise en correspondance des couples d’entités (primitives) liées, extraits des

deux images d’une paire stéréoscopique. L’appariement revient à établir une relation

biunivoque entre primitive d’une image et leurs homologues dans l’autre image. Cette

tâche aisée pour l’homme représente l’un des problèmes les plus importants et les plus

difficiles de la vision robotique du fait qu’une primitive donnée dans une image peut être à

première vue associée à plusieurs primitives dans la seconde image ayant les mêmes

propriétés. Se pose alors le problème du choix du bon candidat. Il est aussi possible que

quelques primitives visibles dans une image soient absentes dans l’autre image à cause de

la position de la caméra par rapport à la scène. Afin de lever les ambiguïtés et de permettre

de dégager un ensemble d’appariements corrects, un certain nombre de contraintes ont été

proposés [Mar 76] :

• Les contraintes globales, pour résoudre le problème de l’appariement de primitives

appelées loi d’unicité et loi de continuité. La première se traduit par le fait qu’une

primitive dans une image a au plus un homologue dans l’autre image. La seconde

s’appuie sur le fait que le monde physique est constitué de surfaces continues, elle

permet à partir d’un appariement initial de prédire d’autres appariements qui viennent

confirmer le premier.


59

• Les contraintes locales qui concernent l’orientation, la longueur de la primitive, son

intensité, etc.

• La contrainte épipolaire, qui permet une fois qu’une primitive d’une image est

sélectionnée, de réduire l’espace de recherche de son homologue dans l’autre image.

La recherche ne se fait plus dans toute l’image, mais sur la droite épipolaire.

Dans cette approche, nous utilisons la primitive segment de droite car elle présente un

meilleur compromis parmi les différents type de primitives en terme de robustesse,

d’invariance, temps de traitement, etc. Les segments de droites sont obtenus par

l’application de la transformée de Hough sur les images contours de la paire

stéréoscopique. Elle engendre deux listes de segments de droites, où chaque segment est

représenté par: sa distance perpendiculaire (ρ) par rapport au repère de l’image, son

orientation (θ) dans ce repère et les coordonnées de ses extrémités. Ensuite, chaque

segment de ces deux listes est étiqueté adjacent (voisin) lorsqu’il vérifie un critère de

proximité qui sera défini par la suite [Aya 84]. L’appariement, dans notre cas, consiste à

définir pour chaque segment de droite d’une image, une fenêtre de recherche dans l’autre

image. Cette fenêtre contient tous les candidats potentiels du segment de départ et un

coefficient de similitude est calculé pour chacun d’eux. L’homologue est retenu pour une

valeur maximum de ce coefficient.

3. Géométrie du système optique de stéréovisionL’inconvénient d’un système qui utilise plusieurs caméras est de devoir connaître d’une

part le réglage de chacune des caméras et d’autre part la géométrie du système

d’acquisition. La figure 3.1 nous montre notre robot mobile réalisé au CDTA d’Alger avec

un support horizontal mobile des caméras embarqué sur sa plateforme.

Figure 3.1. Robot utilisant la stéréovision

Caméra 1Caméra 2


60

La connaissance du système optique utilisé permet d’une part, de faciliter la mise en

correspondance et d’autre part, de calculer les coordonnées des points 3D de la scène. Pour

ce faire il faut connaître les modèles des caméras utilisés, ceux-ci sont déterminés lors

d’une étape de calibration. Ajouté à cela la géométrie épipolaire ainsi que les lois d’unicité

et de continuité qui contraignent la mise en correspondance La connaissance de la

géométrie épipolaire permet de définir les zones de correspondance privilégiées de deux

images. Ces zones ne dépendent que de la position relative des deux caméras. La

calibration de notre système a été réalisée au laboratoire de vision au CDTA d’Alger qui

nous a fourni les paramètres du banc stéréoscopique sous la forme suivante :

• Deux matrices de transformation perspective, une pour chaque image.

• Une matrice permettant, connaissant un point image d’une vue de trouver l’équation

de la droite épipolaire portant son homologue dans l’autre vue et une seconde matrice

pour le problème symétrique.

4. Implémentation NeuronaleLes méthodes neuronales sont nombreuses, chaque méthode a ses propres

caractéristiques incluant l’architecture, la convergence, le temps d’exécution et ses

résultats dans divers domaines. Cependant ces réseaux de neurones à plusieurs couches, de

connexions modifiables, sont confrontés à un problème qui s’énonce de la manière

suivante : Comment répercuter sur chacune des connexions le signal d’erreur qui n’a été

mesuré que sur la couche de sortie, après avoir traversé plusieurs étapes ?

Cette problématique a été levée par l’algorithme de rétro-propagation du gradient

[Nek 95, Fre 91]. Cette technique neuronale est implémentée dans notre processus de

traitement. Elle a le mérite d’avoir deux aspects essentiels: l’aspect parallèle en temps réel

.et les non linéarités du processus concernant la commande.

4.1 L’architecture du réseau

Notre réseau de neurones est un MLP (perceptron multicouche), souvent recommandé

dans les études sur la reconnaissance de formes, vu les résultats précis qu’il procure

[Gho 92, Nek 95]. Avec cette architecture, on utilise l’algorithme de la rétro-propagation

qui est basé sur la correction de l’erreur quadratique par une approximation d’une descente

du gradient, ainsi que la fonction sigmoïde sans biais : f(x)= 1/ 1+ exp (-x). Afin de

reproduire notre image ou de détecter les objets d'une scène, il est nécessaire de développer


61

un classifieur neuronal. Ce dernier consiste en une fenêtre d'un réseau multicouche à rétro-

propagation du gradient : Des essais multiples effectués en laboratoire avec des fenêtres de

tailles différentes ont montré que la fenêtre (3*3) est la plus adéquate Les figures ci-

dessous 3.2, 3.3 et 3.4 illustrent la pertinence de notre choix. [Bou 05a, Bou 05b]

Figure 3.2. Image originale d’objets de formes cylindrique et polyédrique

Figure 3.3. Image résultat : Fenêtre (5*5) Figure 3.4. Image résultat : Fenêtre (3* 3)

Réseau (25-15-5-1), T = 0.125 Réseau (9-6-3-1), T = 0.220

Input pattern

Image object Detected object

Output layer

Back- propagation

TargetList

Figure 3.5. Architecture du réseau


62

Nous avons opté pour un réseau à quatre couches, une couche d’entrée, deux couches

cachées et une couche de sortie. Le deuxième choix portera sur le nombre de neurones sur

chaque couche du réseau. Ce nombre dépendra du nombre de pixels que contiendra la

fenêtre utilisée sur l’image (dans notre cas 3*3) pour pouvoir reproduire celle-ci à la sortie

du réseau, après avoir balayé l’image entière pixel par pixel. Le réseau (9-6-3-1) sur la

figure 3.5 donne une meilleure généralisation pour l'image entière à l'entrée du réseau.

4.2. La Règle Delta Généralisée

La règle delta généralisée étant une description mathématique du réseau à rétro-

propagation du gradient est en fait l’algorithme d’apprentissage de notre réseau. Les

étapes de l’algorithme sont décrites ci-dessous :

1) Appliquer un vecteur d’entrée au réseau et calculer les valeurs des sorties

correspondantes.

2) Comparer les sorties actuelles avec les sorties réelles, puis déterminer l’erreur.

3) Rétro-propager l’erreur de toutes les couches intermédiaires cachées et calculer les

erreurs pour toutes les unités de ces couches.

4) Déterminer la variation des poids avec laquelle sera ajusté chaque poids de

connexion du réseau.

5) Appliquer les corrections aux poids des connexions du réseau.

6) Répéter les étapes de 1 à 5 avec tous les vecteurs d’exécution jusqu’à ce que l’erreur

de tous les vecteurs soit réduite à une valeur acceptable.

Notations :

x j( c ) = Sortie du jème neurone de la couche [c] ;

W ij ( c ) = Poids de la connexion entre le ième neurone de la couche [c-1] et le jème

neurone de la couche [c] ;

Aj( c ) = Entrée totale (somme pondérée des entrées) du jème neurone de la couche [c].

=)(cjA ∑

=

−

ni

ci

cji xw

...0

)1(* (1)

=)(cjx f( Aj

)(c ) (2)

4.3. Le momentum

Le concept de momentum a été introduit pour réaliser un compromis entre un coefficient

d'apprentissage faible et un temps d'apprentissage acceptable [11]. Le momentum agit

comme un filtre passe bas sur le terme de variation de poids, puisqu'il renforce la tendance

générale et diminue le risque d'oscillation, cela permet un apprentissage plus rapide avec


63

un coefficient d'apprentissage faible. L'équation de variation du poids est modifiée de telle

sorte qu'une partie de la variation de poids est réintroduite par itération.

∆ Wji(c ) (t +1) = Lcoef (t +1)*e j

(c) (t) * xi(c-1) (t) + Mom ( t+1 )* ∆ Wji

( c) (t) (3)

Il est essentiel d’améliorer la règle de la modification des poids dans l’algorithme de la

rétro-propagation par l’adjonction de la règle :

∆ W (t + l) = ∆ W (t) + 0.9 W (4)

Cette modification majeure améliore considérablement la fiabilité de l’algorithme. Les

meilleurs résultats sont obtenus avec un momentum de valeur 0.3 et un coefficient

d'apprentissage de valeur 0.02. Notre objectif est d'évaluer aussi la performance du

classifieur neuronal utilisé qui prend en entrée l'image en niveaux de gris. L’erreur a pu

être réduite jusqu’à l’ordre de 0.001. Le seuil T a été calculé avec la méthode de calcul de

la moyenne arithmétique.

5. Extraction des chaînes de points de contourA l’issue du filtrage (du type gradient ou laplacien), on est en présence d’une image dont

on veut extraire et organiser les points de contraste le long de chaînes de points de contour

qui marquent les frontières de régions à gradient plus ou moins homogène. Il s’agit donc de

déterminer ces chaînes de points de contour en suivant les maxima ou les zéros de la sortie

du filtre. La technique de seuillage par hystérésis a prouvé son utilité dans le cas du filtrage

de type gradient, en présence de bruit : il s’agit de ne commencer à suivre une chaîne de

contour que lorsque le gradient a une valeur supérieur à un seuil et d’abandonner le

chaînage lorsque le gradient tombe au dessous d’un seuil [Gir 87]. Cette technique a

l’avantage d’éliminer de nombreux maxima du signal dus au bruit. Notre choix s’est porté

sur le détecteur de Deriche [Der 87] pour ses performances pratiques.

Le filtre Deriche s’écrit : e1)xk((x) x-4

αα +=s (I) (5)

k est choisi de manière à obtenir un filtre discret normalisé soit :

( )e-e21

e-1 -k1(x)s 2--

2

4 ααα

α

+=⇔=∑

∞+

∞−

le filtre optimal de dérivation s’écrit comme suit :

d 4 (x) = - k e -α x (6)

( )ee1k -

2

α

− −=


64

Tout détecteur de contour est considéré comme étant un triplet (algorithme, paramètres,

précondition). La précondition est représentée par le contexte dans lequel le couple

(algorithme, paramètres) s’exécute correctement. Ce dernier est un opérateur de détection

de contour optimal basé sur le critère de Canny implémenté récursivement. Il apparaît que

le détecteur de Deriche semble être mieux adapté à la mise en évidence de contours peu

nets et de contours bruités (figures 3.6 et 3.7). D’ailleurs il fournit des contours mieux

localisés, et il engendre ainsi une plus faible erreur de localisation et d’omission. Ce qui

parachève le but recherché. Pour l’utilisation rationnelle de la TH, il est impératif d’avoir

pour notre système de vision des images contours binaires

Figure 3.6. Image originale d’une scène d’intérieurde Laboratoire

Figure 3.7 Détection de contours par Deriche (α =1.5 )


65

6. Application de la Transformée de Hough dans l’appariement des

imagesNous avons vu au chapitre précédent que l’extraction des segments de droites de l’image

contours se fait donc par une recherche des segments de droites portés sur chaque droite

significative détectée (ρi,θj) dans le tableau accumulateur (figure 3.8). Une droite

significative dans l’image contours se caractérise par un pic dans le tableau accumulateur

et pour chaque pic détecté on élimine l’effet des points appartenant à ce pic dans le tableau

accumulateur. Le résultat de l'extraction est une liste de segments de droites où chaque

segment est stocké avec la liste d’attributs suivants :

• Index : un entier qui caractérise sa position dans la liste des segments de droites,

• : sa distance perpendiculaire par rapport au repère de l’image,

• : son orientation dans ce repère, (x1,y1) et (x2,y2) : les coordonnées de ses extrémités.

Figure 3.8 Tableau accumulateur

Des relations de voisinage entre segments viennent s’ajouter aux attributs locaux cités ci-

dessus. Elles permettent de lier tous les segments de la scène entre eux. En effet, un

ensemble de segments voisins entre eux peuvent être issus d’un même objet. Pour

retrouver le voisinage des segments de droites, nous avons opté pour la méthode appliquée

par [Aya 85]. Elle consiste à découper l’image en un ensemble de fenêtres de forme carré

de dimension fixe, puis à rechercher pour chaque segment de droite l’ensemble des

fenêtres qu’il intersecte. Deux segments de droites sont dits voisins s’ils ont au moins une

fenêtre en commun. Les attributs qui vont s’ajouter aux attributs locaux sont :

- vois[lv] : liste de lv segments voisins dont on connaît les ρ, θ, (x1,y1) et (x2,y2) ainsi que

leur Index dans la liste des segments de droites.


66

Nous avons donc créé une structure de données qui regroupe tous les segments de droites

d’une image avec leurs propriétés locales ainsi que leurs voisinages. L’image est donc

représentée par un graphe d’adjacence dont les n uds sont des segments de droites

auxquels sont attachés des propriétés géométriques et dont les arêtes définissent des

relations de voisinage entre segments.

6.1. Algorithme d’appariement

L’initialisation de notre algorithme d’appariement se fait par tous les appariements entre

les segments de droites qui répondent aux contraintes locales suivantes :

a) Contrainte de voisinage

Cette contrainte remplace la contrainte epipolaire. Elle définit pour chaque segment Si

d’une image une fenêtre de recherche F(Si) de taille dynamique (ses dimensions dépendent

de la taille du segment courant Si et de la valeur du seuil Tfen) sur l’autre image [Rob 86].

Les segments de droites qui appartiennent à cette fenêtre sont des candidats potentiels

pour la mise en correspondance. La figure 3.9 montre bien la forme de la fenêtre de

recherche F(Si).

Segment Si

Tfen

Tfen

Tfen

Tfen

Figure 3.9. Construction de la fenêtre de recherche F(Si)

b) Contrainte d’orientation :

Deux segments sont dits d’orientation similaire si la différence de leur orientation est

inférieure à un certain seuil (seuil_teta).

c) Contrainte de longueur :

Deux segments sont dits de longueur similaire si la différence de leur longueur est

inférieure à un certain seuil (seuil_long).


67

d) Contrainte de distance :

Deux segments sont dits similaire si la différence de distance de leur milieu est inférieure

à un certain seuil (seuil_dis). Pour chaque segment d’une image, nous aurons un ensemble

de couples de segments potentiels. Nous affectons à chaque couple de segments potentiels

un coefficient “Q” qui met en uvre une comparaison des attributs de ce couple, et qui

sont : la longueur, l’orientation et la distance reliant les deux points milieu des segments du

couple. La valeur de ce coefficient est calculée comme suit :

Pour un couple de segments (Si, Sj) ,

.1

,___

jiji

SjSijijiji

QSim

disseuil

mmdist

tetaseuil

SSorient

longseuil

SSlongQ

=

−+

−+

−=

(7)

long |Si-Sj|, orient |Si-Sj| et dist |mSI-mSJ| représentent la différence des valeurs des

attributs : longueur, orientation et la distance entre les deux points milieu des

segments Si et Sj.

Seuil_long, seuil_teta et seuil_dis sont les erreurs sur les seuils permises sur les valeurs

des attributs du segment Sj homologue du segment Si respectivement pour la longueur,

l’orientation et la distance entre les deux points milieu des deux segments Si et Sj.

Enfin, nous en retenons que le couple de segments potentiels dont la valeur du coefficient

“Q” est minimale (la similitude “Sim” est maximale), et les autres couples des segments

potentiels seront rejetés. Le segment Sk dont la valeur du coefficient “Q” est minimale est

le segment homologue du segment Si. Cette procédure d’appariement permet d’obtenir

pour chaque segment d’une image, zéro ou un correspondant (homologue) dans l’autre

image. Ce processus est appliqué deux fois en inversant les rôles respectifs des deux

images de la paire stéréoscopique. On dispose alors de deux listes de segments appariés

résultats de l’appariement gauche-droite et droite-gauche. Mais ces deux listes ne sont pas

cohérentes, car nous pouvons avoir un segment de droite d’une image apparié a plusieurs

segments de droites dans la seconde image ayant les mêmes propriétés géométriques. Afin

de lever les ambiguïtés et de permettre de dégager un ensemble d’appariements corrects,

un certain nombre de contraintes ont été proposés :

e) Contrainte de compatibilité : Etant donné un appariement (S1, S2) :

- si S2 est apparié à S1 (appariement gauche-droite) et si S2 est apparié à S3 (appariement

droite-gauche) avec S3 voisin à S1, donc (S1, S2) est validé sur la figure 3.10-a.

- sinon (S1, S2) est rejeté sur la figure 3.10-b.


68

S1S2

S3

(a) Cas compatible

S1S2

S3

(b) Cas non compatible

Figure 3.10. Contrainte de compatibilité entre les appariements

gauche-droite et droite-gauche

Soulignons ici que les appariements gauche-droite et droite-gauche résultent de deux

processus d’appariement totalement indépendants. Le test de la contrainte de compatibilité

mutuelle des résultats obtenus offre donc une garantie supplémentaire de fiabilité des

appariements finalement retenus.

f) Contrainte d’unicité :

Cette contrainte impose que chaque primitive d’une image ait un seul correspondant dans

l’autre image. Ceci interdit donc les recouvrements entre segments de droites (figure 3.11).

Dans le cas d’un recouvrement entre deux segments de droites, nous supprimons celui

dont l’appariement est de qualité la moins bonne.

S1S2

S3

Figure 3.11. Cas de recouvrement entre deux segments de droites


69

6.2. Mise en correspondance par la modèle de Hopfield

Vu l’état de l’art, nous avons opté pour le modèle de Hopfield qui s’avère le plus

compatible pour notre application. On montre que le problème de mise en correspondance

peut être formulé comme une tâche d'optimisation où ou il faudra satisfaire les contraintes

de correspondance. Une fonction d’énergie représentant ces contraintes sur la solution est

réduite au minimum [Ach 98, Med 85]. Puis la matrice de connexion se déduit pour faire

évoluer le réseau vers son état stable [Cha 92]. La figure 3.12 montre la structure de

Hopfield à deux dimensions qui peut être assimilé à une matrice. Ce réseau est employé

pour trouver la correspondance entre les primitives de l'image gauche et ceux de l’image

droite. L'état (activé ou non) de chaque neurone dans le réseau représente une possibilité

d’appariement entre un segment dans l'image gauche avec son homologue dans l’image

droite. La fonction de Lyapunov pour un réseau binaire bidimensionnel de Hopfield

[[Hop 82, You 97] est donnée par:

∑∑∑ −−=lu

ulullu mv

vmululvm VIVVTE,, ,

21

(8)

Right image segmentsV Tvmvm m Ivm

Tulul Tulvm

l Iul U u v Left image segments

Figure 3.12. Structure du Réseau de Hopfield

Vul et Vvm représentent respectivement les états binaires (sorties) des neurones (u,l) et

(v,m), qui peuvent être à l’état 1 (actif) ou 0 (inactif). Tulvm est le poids de connexion entre

les deux neurones. Cette connexion est symétrique Tulvm = Tvmul. Il est démontré que pour

une stabilité du réseau, il faudrait que chaque neurone n’ait pas de connexion sur lui-même

autrementdit Tulul = 0 et Iul est l'entrée initiale à chaque neurone. Dans ce réseau nous

avons employé d’une part les contraintes d’intensité et de disparité, et d’autre part la loi

d’unicité et celle de l’ordonnancement.


70

7. Résultats expérimentaux

L’algorithme d’appariements stéréoscopiques implémenté en langage C++ sous Unix sur

une station de travail, a été testé sur plusieurs images. Nous présentons ici les résultats de

notre méthode appliquée sur 2 paires stéréoscopiques. Les contours binaires de chaque

image sont extraits par l’opérateur de Deriche. Les segments de droites sont détectés par la

transformée de Hough (TH) avec 10° pour pas de quantification de le dimension de θ et 1

pixel pour pas de quantification de la dimension de ρ. La TH est indépendante de la phase

suivante d’appariement et a été implantée sur une puce FPGA.. Les résultats de notre

méthode d’appariement ont été effectués avec un jeu de paramètres déterminé

expérimentalement, et qui sont :

• Tfen = 20,- seuil_dis = 1,- seuil_long = 10,- seuil_teta = 10°.

Nous donnons dans le tableau ci-dessous (Tableau 3.1) les principaux résultats

d’appariement obtenus sur nos 2 exemples des deux figures 3.13 et 3.14. Près de 67% de

segments de droites ont été appariés avec un taux d’erreurs inférieur à 1%.

Exemples d’images 3dlab Ball

Nombre de segments gauches 726 748

Nombre de segments droites 834 723

Nombre de segments appariés

gauche-droite

492 560

Nombre de segments appariés gauche-droite après

les contraintes de compatibilité et l unicité 426 515

Nombre de segments appariés

droite-gauche

562 543

Nombre de segments appariés droite-gauche après

les contraintes de compatibilité et l unicité 490 498

Tableau 3.1. Résultats d’appariements

Dans les figures 3.13 et 3.14, la partie supérieure en (a) représente les images gauche et

droite fournies par les caméras. Au-dessous en (b), nous avons représenté les segments de

droites détectés par la transformée de Hough à partir des images contours gauche et droite.

Enfin, dans la partie inférieure en (c) nous présentons les appariements gauche-droite et

droite-gauche résultats de la méthode d’appariement élaborée. Un petit nombre de

segments ne sont pas appariés parce qu’ils n’ont pas de véritable homologue.


71

Images 3DLAB_D 3DLAB_ G Objects

Size 256*256 256*256 256*256

ThH 3 3 3

Figures 3.17c 3.16c 3.18d

Nseg 207 203 259

Npeak 96 92 118

Tableau 3.2. Résultats obtenus par le logiciel

Le tableau illustre les résultats obtenus par notre logiciel sur les images 3.16a, 3.17a et

3.18a. Npeak, Nseg, and ThH sont respectivement, le nombre de pics détectées de

l'espace de Hough, le nombre de segments de droites détectés et la valeur de longueur de

seuil pour la détection des segments de droites.

(a) La paire stéréo en niveaux de gris

(b) Résultats de la segmentation de la paire stéréo


72

(c) Résultats des appariements gauche-droite et droite-gauche

Figure 3.13. La paire stéréo 3D Labo

(a) La paire stéréo en niveaux de gris

(b) Résultats de la segmentation de la paire stéréo


73

(c) Résultats des appariements gauche-droite et droite-gauche

Figure 3.14. La paire stéréo Ball

Figure 3.15. Couple stéréoscopique, images originales 3D Labo

(a) (b) (c)

Figure 3.16. Résultats de l’Algorithme appliqué sur l’image 3D gauche du Labo

(a) Gray-level image; (b) binary edge image; (c) recognition results


74

(a) (b) (c)

Figure 3.17. Résultats de l’Algorithme appliqué sur l’image 3D droite du Labo

(a) image initiale; (b) image contour binaire; (c) résultats de la reconnaissance

(a) (b)

(c) (d)

Figure 3.18. Résultats de l’Algorithme appliqué sur des objets

(a) image initiale; (b) Extraction des segments

(c) Espace de Hough; (d) résultats de la reconnaissance


75

Le classifieur hybride a été évalué sur la base de tests. La figure 3.19 précise l’évolution

du taux de reconnaissance en fonction du seuil d’ambiguïté et du seuil de confusion sur les

objets utilisés dans la base de données. On peut constater que plus le seuil de confusion est

élevé, plus le taux de reconnaissance augmente. Le taux de reconnaissance croît aussi avec

le seuil d’ambiguïté. Les figures 3.16c, 3.17c et 3.18d montrent l’efficacité de notre

logiciel de traitement sur des objets toutes formes confondues. Le taux de reconnaissance

est estimé à 97.8 %.

Figure 3.19. Taux de reconnaissance en % du classifieur hybride

en fonction des seuils de confusion et d’ambiguïté

• Implémentation sur FPGA

La figure 3.20 représente le circuit FPGA obtenu après l’implémentation de l’architecture

notre algorithme sur le circuit Xc250-5fg456C de Virtex.II de Xilinx.

L’occupation de l’espace FPGA est donnée par le tableau 3.3.

Figure 3.20. Circuit FPGA réalisé


76

Slices (CLBs) occupés 619/1536 Occupation de 38%

IOBs occupés 141/200 Occupation de 70%

RAM 20/24 Occupation de 82%

Tableau 3.3. L’occupation de l’espace FPGA

La fréquence de fonctionnement de ce circuit peut aller jusqu'à 606.081 MHz.

Quatre paramètres n correspondant à quatre n sont générés chaque 11,852 ns.

8. Discussion et InterprétationDans ce chapitre nous avons présenté un système de reconnaissance des formes par la

construction d’informations tridimensionnelles d’une scène à partir des couples de régions

homologues déterminés. La technique d’extraction d’attributs par les réseaux de neurones

(seuillage par la Rpg) a permis une maximalisation de la corrélation entre l’image originale

et l’image binaire produite. Ce qui est un des buts recherchés vu la robustesse de notre

algorithme. On observe aussi dans l’étape de détection de contours par le filtre de Deriche,

une réduction du bruit assez importante qui a atténué les erreurs de reconnaissance. Les

images résultats nous le confirment.

Notre contribution a permis de résoudre le problème de l’appariement des segments de

droites des images stéréoscopiques. Les points forts de notre approche résident d’une part

sur l’utilisation de plusieurs indices visuels (régions, contours,..) afin de bénéficier

d’informations plus riches, et d’autre part sur le renforcement de la segmentation à chaque

niveau du système. La méthode comprend l’application de contraintes locales pour cerner

les appariements les plus probables en utilisant une fenêtre de recherche et un critère de

compatibilité des appariements basé sur le graphe d’adjacence de segments de droites

contenus dans l’image.

Un coefficient de similitude est calculé pour chaque couple potentiel et nous retenons

pour homologue qu’un seul couple dont la valeur de ce coefficient est maximum.

Cette méthode a été implémentée sur une station de travail en langage C++ sous Unix

appliquée sur des paires d’images stéréoscopiques. Les résultats de cette technique sont

probants. Cette dernière se révèle trés robuste et efficace, qualités que l’on peut renforcer

encore en ajoutant d’autres critères tel que la luminance.


77

La méthode d’appariements stéréoscopiques, présenté dans ce travail a été utilisée (après

implémentation de la TH sur un circuit FPGA) pour des tâches de navigation et autres

moyennant la vision 3D pour le robot mobile autonome développé dans notre laboratoire.

Lors de son test de déplacement et malgré la présence de bruits d’origine diverse (reflets

dus à l’éclairage, etc.), notre robot mobile s’est accoutumé à l’environnement, ce qui

montre encore une fois les bonnes règles qui régissent son apprentissage. Il a pu

différencier entre des balises et les amers dans la scène (pilier, reflet). Ce qui est un des

indicateurs de la robustesse de notre algorithme. En fait notre contribution a montré les

limitations d’un traitement de bas-niveau sur les images et la nécessité d’inclure la

compétence de traitements de plus haut niveau. La méthode de stéréovision que nous avons

développé en est un exemple.

On observe avant de faire entrer notre robot mobile dans la salle du laboratoire que nous

lui modélisons le couloir par ses deux arêtes inférieures pour que ce dernier puisse se

localiser. En se référant à sa position, le robot doit aussi générer une trajectoire lui

permettant de se déplacer de sa position vers une position destination - le milieu des deux

arêtes détectées qui forment le couloir en fixant le bout du couloir. La détection des deux

arêtes du couloir se fait par la recherche de la plus grande valeur accumulée dans les

cellules du tableau accumulateur. L'arête gauche se distingue de l'arête droite par la valeur

de sa variable θ dans l'intervalle [0, π]. L'arête gauche a un θ compris entre 0° et 90° et

l'arête droite a un θ compris entre 90° et 180°. La mauvaise détection des arêtes de l'image

de la scène observée influe négativement sur la bonne génération de la trajectoire car le

robot mobile suppose que c'est un espace libre. Il peut donc heurter le mur de la salle de

laboratoire ou un éventuel obstacle. Ce qui nous fait remarquer que cette approche donne

de bons résultats si nous avons une bonne acquisition de l'image de la scène observée et si

le milieu d'évolution est bien éclairé.

Il en ressort de l’expérimentation d’affirmer que notre travail présente des performances

meilleures par comparaison à d’autres travaux édités dans les mêmes conditions

d’environnement (taille d’images, types d’objets) car elle de type coopératif et dirigé, et

la modification des attributs est effectuée par une règle probabiliste [Bal 96, Fna 97,

Cap 98, Son 99, Zaa 00].

Par exemple la référence [Fna 97] présente une approche complexe qui combine une

« appearance based technic avec un réseau de neurones suivi d’une technique

« multiresolution fusion decision »» qui permet d’assurer une robustesse du système au

prix d’un temps de calcul additif ??


78

Contrairement à notre travail qui nous a permis d’avoir un bon compromis entre

robustesse et temps de calcul qui sont d’ailleurs les indicateurs les plus importants de

performances pour des systèmes travaillant en temps réel [Pal 99, Tuy 03, Ach 04,

Bou 06].

9. ConclusionLors de cette application de stéréovision, notre solution a été de mettre en exergue une

interaction entre les traitements mis en uvre. Notre système non loin d’être un système

expert a pu permette les échanges dynamiques, contrôler le processus, avoir une base de

connaissances, et un moteur d’inférence. En pis, il peut être organisé en modules qui

seraient les suivants : extraction des primitives, segmentation, appariement, calcul des

informations 3D, recalage scène pour l’identification, localisation, navigation,

apprentissage. La perception de l’environnement par notre robot mobile est un problème

riche et étendu, dont nous avons proposé une approche, mais de nombreuses autres voies

restent ouvertes.

Cependant la force du paradigme neuronal dans le domaine de la RDF résulte

principalement da la distribution des connaissances. En effet les formes apprises sont

mémorisés à travers les poids des connexions du réseau, ce qui confère à ce dernier des

capacités remarquables de généralisation et de résistance au bruit. Cependant des reproches

peuvent être faits aux RN liés au caractère empirique de la conception de leur topologie.

La vision par ordinateur, discipline dans laquelle s’insère notre étude, est un sujet vaste

et passionnant et notre contribution à réaliser un système de stéréovision et à lever un des

aspects de la problématique de la RDF reste modeste.

La méthode RANSAC (Random Sample Consensus) est une méthode de vote

probabiliste qui parait être intéressante pour réduire les temps de calcul [Fis 81].

Cependant seulement son insertion dans un processus hybride pourrait nous éclairer

d’avantage quant aux performances de cette méthode.

Nous avons passé en revue les méthodes d’estimation robuste le plus utilisées en vision

robotique. L’utilisation de techniques de vote telles que la Transformée de Hough où la

méthode de consensus de Ransac, représente un bon compromis entre robustesse et

efficacité algorithmique en pis d’une vitesse de convergence réduite.


79

L’organigramme du processus de traitement est présenté sous forme explicite sur la

figure 3.21.

Sensors Gray level Image Binary Image

Figure 3.21. Organigramme du processus de traitement

Edge BinaryImage

Acquisition Rpg Dériche Detector

Generated Hough Transform Application

Accumulator TableCreation

PatternRecognition 3D

Decision

Matching Problemby Hopfield

Computer Integrated Manufacturing

Planified Tasks

Navigation Strategies

Chapitre 4 Application à la Productique

80

CHAPITRE 4

Application à la Productique

Contrôle automatique de pièces

manufacturées

1. IntroductionLes technologies de l’information façonnent les activités du monde contemporain. A cet égard,

l’informatique et les communications ont fait basculer l’économie mondiale qui est passée

d’une économie basée sur la transformation des matières premières à une économie basée sur le

savoir. Le domaine de l’inspection automatisée, indispensable pour assurer la qualité de la

production, demeure une tâche de l’activité manufacturière où l’automatisation présente

beaucoup de retard. La fabrication d’objets manufacturés n’échappe pas à cette tendance et de

nombreux outils informatiques facilitent la conception des pièces (C.A.O.) de même que, de

plus en plus, leur fabrication (F.A.O.). Ce foisonnement d’outils informatiques a permis de

diminuer considérablement les temps de conception et de fabrication de pièces en série. La

présente décennie est caractérisée par la nécessité de mettre en marché des produits de qualité et

ce, rapidement. Bien que plusieurs activités de conception et de fabrication soient aujourd’hui

assistées par ordinateur, le domaine de l’inspection automatisée, indispensable pour assurer la

qualité de la production, demeure une tâche de l’activité manufacturière où beaucoup d’efforts

doivent être déployés pour arriver au même niveau d’automatisation.


81

2. ProblématiquePuisque l’inspection d’une pièce manufacturée consiste à vérifier l’exactitude de la pièce par

rapport à un ensemble de spécifications (tolérances) données, il est nécessaire que la méthode

utilisée pour réaliser cette inspection soit elle-même très précise. Dans la méthode d’inspection

que nous présentons, nous allons comparer le modèle de conception de la pièce avec son image

3D. Afin d’obtenir un résultat fiable, il est nécessaire que le modèle de conception CAO

modélise la pièce de la manière la plus exacte possible, et que le nuage de points 3D qui

représente la mesure de cette pièce soit lui aussi précis que possible. L’imprécision inévitable

des procédés de mise en forme fait qu’une pièce ne peut pas être réalisée de façon

rigoureusement conforme aux dimensions fixées au préalable. Le concepteur d’une pièce,

conscient de ce problème, introduit des tolérances ou variations dans les dimensions, sur la

dimension effective de la pièce, afin qu’elle puisse réaliser correctement sa fonction. Le

contrôle ou inspection est l’opération par laquelle un produit réel est comparé, en entier ou en

partie, aux spécifications définies lors de sa conception. L’inspection cherche à assurer la

conformité aux espérances du client à ce qu’un produit devrait pouvoir faire.

L’interchangeabilité du produit, la compatibilité, la fiabilité sont quelques exemples des

demandes potentielles du client. Quelques caractéristiques pour lesquelles le contrôle

automatique est souhaitable sont:

• Les inspecteurs humains ne sont pas toujours constants dans l’évaluation des produits, en

partie à cause de la fatigue. Par conséquent l’uniformité de l’évaluation, appliquée

objectivement grâce au contrôle automatisé devrait permettre de prédire le niveau de

qualité de la production.

• Plusieurs taches de contrôle prennent beaucoup de temps, ce qui augments leur coût de

production. L’inspection automatique apporte une grande vitesse de traitement ainsi elle

peut égaler la vitesse de production, même lorsque plusieurs exécutions complexes sont

réalisées dans le même cycle.

• Le contrôle automatique permet d’inspecter les objets qui sont dans des endroits

inaccessibles et dangereux pour l’être humain.

Dans l’industrie le standard pour le contrôle de pièces est la machine à mesurer

tridimensionnelles. Une MMT est un système de mesure fiable et précis, composé de capteurs à

contact électroniques, d’un logiciel de saisie de données, et d’un système informatique.


82

Le principe de fonctionnement d’une MMT est d’enregistrer les points de contact entre le

capteur et la pièce. Ces points sont tracés et enregistrés dans le système référentiel de la machine.

Des algorithmes d’ajustement de données sont alors employés pour calculer la position et

l’emplacement des caractéristiques de la pièce. En conséquence, des tolérances peuvent être

calculées. Les MMTs ont été acceptées dans l’industrie pour leur souplesse à réaliser des tâches

d’inspection et de vérification. Cependant quelque soit le niveau technologique de la machine

utilisée, l’utilisation du capteur à contact a toujours l’inconvénient majeur de pouvoir

endommager la surface du produit. Par conséquent l’étude de systèmes de contrôle utilisant des

systèmes visuels, qui peuvent être mis en application pour des mesures sans contact, s’avère

nécessaire pour l’inspection des produits faits de matériaux mous. Par ailleurs, des systèmes

optiques tels que les capteurs basés sur des technologies laser, nous permettront d’avoir de

grandes densités des points de mesure, dans un court laps de temps, ce qui est presque

impossible avec les MMTs. Des systèmes de conception et de fabrication assistée par ordinateur

(CFAO) sont employés dans de nombreuses industries pour concevoir et créer des objets

physiques à partir de modèles numériques. Dans ce contexte, ayant cette connaissance sur la

géométrie de l’objet, l’inspection assistée par ordinateur consiste à comparer le modèle de

conception d’une pièce physique avec ses mesures 3D. L’intérêt d’utiliser des modèles CAO

provient du fait qu’ils constituent une description exacte de l’objet. En effet ceux-ci contiennent

à la fois une description mathématique de la forme de l’objet, incluant une paramétrisation

explicite de la forme des surfaces. Un autre avantage des modèles CAO est leur grande

flexibilité, qui permet par exemple d’ajouter sans problème un nouvel objet dans le système

d’inspection. La numérisation de surfaces dans les systèmes industriels de contrôle nécessite

une grande précision de mesure et une grande vitesse d’exécution. Les capteurs sans contact tels

que : les systèmes de stéréovision et les capteurs télémétriques ont des avantages importants par

rapport au MMT.

3. Etat de L’artL’état de l’art que nous avons réalisé est composé de deux parties. Dans l’une, section 3.1 nous

présentons la littérature concernant le problème de planification du placement du capteur pour

l’acquisition des images 3D. Dans l’autre, section 3.2, nous discutons des articles qui traitent du

problème d’inspection.


83

3.1. Planification de l’acquisition des imagesTarabanis [Tar 95a] a fait un compte rendu dans le domaine de la planification des capteurs

de vision (caméras, capteurs télémétriques, appareils d’illumination) basés sur des modèles. Il

classifie les travaux en trois groupes :

1. Le premier groupe traite de la détection des caractéristiques des objets. Ici plusieurs travaux

essaient de déterminer de façon automatique les paramètres des capteurs de vision pour une

caractéristique connues et qui satisfont quelques contraintes spécifiées lors de la

numérisation.

2. Dans le deuxième groupe Tarabanis présente les travaux qui développent des stratégies de

numérisation pour les taches de reconnaissance et de localisation des objets, basées sur des

modèles.

3. Finalement, le troisième groupe étudie le problème de la détermination de stratégies de

numérisation pour la reconstruction de pièces.

Notre travail se situe dans les deux premiers groupes car d’une part nous avons une

connaissance a priori des modèles des objets et d’autre part en inspection, on est souvent

intéressé à numériser que quelques surfaces sur lesquels on a défini des tolérances.

§ Travaux orientés vers la détection des caractéristiques et vers le contrôle des objets

Tarbox et Gottschlich : proposent le système IVIS (Integrated Volumetric Inspection System)

pour la planification d’un ensemble d’opérations qui mesurent complètement la surface d’une

pièce à inspecter. IVIS procede en deux étapes : une phase hors ligne, où un plan d’acquisition

est produit pour chaque objet de référence, et une phase en ligne où on exécute le plan

préplanifié [Tar 95c, Tar 95d].

Trucco et al : présentent le système GASP (General Automatic Sensor Planning) pour la

planification de capteur. GASP détermine les positions optimales pour la tâche d’inspection, en

ayant connaissance des modèles des capteurs et des pièces [Tru 97].

Mason et Grün : proposent une méthode de placement automatique d’un système de vision

passif multiposte, pour l’obtention des dimensions d’un objet 3D. Le terme ‘’poste‘’est

employé pour dénoter la position et l’orientation à laquelle une image est prise. Un système

multiposte est défini comme la mesure d’un objet quand toutes les régions d’intérêt apparaissent


84

et sont mesurables sur trois ou plusieurs images séparées dans l’espace. Un système multiposte

composé de quatre postes a été utilisé pour examiner une surface de 2mx1m, située dans une

zone de travail contenant un certain nombre d’obstructions, et l’exactitude de mesure exigée

était de ± 0.25mm [Mas 95].

Tarabanis et al : décrivent une méthode de planification nommée planification de système de

vision (Machine Vision Planning). Le système MVP détermine automatiquement les valeurs de

paramètres de capteur de vision qui répondent à certaines exigences des tâches de détectabilité

de caractéristiques [Tar 95b].

Abrams et al : ont développé un système capable de planifier les positions, les orientations et les

paramètres optiques d’une caméra pouvant être utilisée dans un milieu dynamique. Ce travail

peut être considéré comme une extension du travail de Tarabanis. Nous rappelons que dans un

milieu dynamique les pièces peuvent être en mouvement [Abr 97].

§ Travaux orientés vers les tâches de reconnaissance et de localisation

Les travaux dans ce groupe ont une connaissance à priori des objets à reconnaître ou à localiser,

elle est représentée par des modèles qui donnent une forme grossière des objets car leur intérêt

n’est pas l’inspection.

Whaite et Ferrie: définissent l’exploration autonome comme un processus dans lequel un

observateur peut agir avec son entourage en se déplaçant et en rassemblant de l’information afin

de se renseigner sur son environnement. Les auteurs utilisent des modéles volumiques (non

linéaires) pour représenter les surfaces dans une scène 3D [Wha 91, Wha 97].

Ye et Tsotsos : proposent une stratégie de planification de capteur par un robot équipé d’une

caméra pour la recherche d’un objet. La connaissance de l’emplacement de l’objet par la caméra

est codée comme une densité de probabilité discrète qui est mise à jour chaque fois qu’une

action de numérisation se produit. Chaque action de numérisation de la caméra est définie par un

point de vue, une direction de la vue, un champ visuel et l’application d’un algorithme

d’identification [Ye 95, Ye 99].

Kovacs et al : présentent une méthode de planification de séquences de vue pour l’identification

et la détermination de l’orientation des objets 3D de forme quelconque. La méthode se compose

d’une étape d’apprentissage et d’une étape dans laquelle l’identification réelle et la


85

détermination de l’orientation ont lieu. Les résultats sont montrés en utilisant un système

physique composé d’une plaque tournante motorisée et une caméra CCD [Kov 98].

§ Travaux orientés vers la reconstruction

Dans ces travaux, aucun modèle d’objet n’est connu et les systèmes planifient le prochain

point de vue de façon à reconstruire les objets tout en utilisant des propriétés géométriques

obtenues à partir des données qui ont été déjà acquises. Les problèmes d’occlusion et de

collision sont traités avec un intérêt particulier.

Pito : présente une solution au problème de la détermination automatique de la meilleure

position suivante (Next Best View) d’une caméra télémétrique pendant le processus de

numérisation d’une pièce pour sa reconstruction. Le système est composé d’une caméra laser,

d’une plaque tournante commandée par ordinateur et munie d’un gabarit de recalage sur lequel

la pièce à numériser est placée. L’algorithme trouve une NBV telle qu’elle numérise la plus

grande portion possible de pièce qui n’a pas encore été numérisée [Pit 96, Pit 97].

Papadopoulos : propose une méthode pour automatiser la numérisation géométrique des

surfaces tridimensionnelles à l’aide d’un capteur à triangulation active avec une faible

profondeur de champ. Le support physique du capteur est composé de quatre platines

mécaniques motorisées, fixées sur un banc de mesure en granit. Le capteur est orientable

manuellement autour de son axe, avec seulement quatre positions prédéfinies séparées de 90°.

Son objectif est la numérisation exhaustive de la géométrie de la scène [Pap 97a, Pap 97b].

Maver et Bajcsy : présentent une stratégie pour acquérir des données 3D dans une scène

inconnue. La scène est mesurée par un système de triangulation : une source lumineuse qui

produit un plan de lumière couplée à une caméra CCD Le problème de la numérisation de

pièces 3D est assujetti à deux difficultés dues à deux types d’occlusion : i. Occlusion de la

caméra qui surgit quand une partie de la surface éclairée de la scène est cachée à la caméra CCD

par une autre partie de la scène. ii. Occlusion des la lumière, qui apparaît quand le rayon de

lumière n’atteint pas une parie de la surface dans la scène parce qu’il est réfléchi par une autre

partie de la scène [Mav 95].

Banta : présente une système de numérisation capable de déterminer automatiquement les

meilleurs position et orientation suivantes pendant le processus de reconstruction d’une pièce.

L’espace de travail est représenté par un volume de 128x128x128 voxels étiquetés occupés ou


86

inoccupés à travers lesquels une projection de rayon permet de choisir parmi les trois

orientations celle qui traverse le plus de voxels occupés. Ceci n’a été appliqué qu’a des données

synthétiques [Ban 95].

ZHA et Al : propose une approche au problème de création des modèles 3D sur la base de la

planification du meilleur point de vue. Afin de modéliser l’objet, un bras de robot est utilisé pour

placer la pièce dans une position arbitraire par rapport à un capteur de profondeur fixe. L’image

de profondeur est prise par un système stéréo laser et un modèle initial de l’objet est produit. Un

algorithme pour résoudre le problème du meilleur point de vue est présenté. Il consiste en une

évaluation analytique ou heuristique des divers points de vue et détermine le meilleur point de

vue suivant [Zha 97].

Discussion

Nous avons vu que la définition et la mise en uvre d’un algorithme d’images 3D est un

problème complexe qui dépend de l’objectif que l’on s’est fixé. Au vu des travaux rapportés

dans l’état de l’art il apparaît que tous ces systèmes sont confrontés à des problèmes d’occlusion

et de collision. Les algorithmes diffèrent quant au type et au nombre de capteurs et de support

mécanique. Pour les types et le nombre de capteurs, on trouve les systèmes composés par un

capteur de profondeur [Pap 97a, Pit 97, Zha 97]; par une seule caméra CCD [Tar 95b, Kov 98];

par une caméra CCD couplée à une source lumineuse [Mav 95, Tar 95c]; et des systèmes

composés par une source lumineuse et plus d’une caméra CCD [Mas 95, Tru 97].

Pour le type de support mécanique, on trouve des systèmes qui utilisent des bras de robot

[Tar 95b, Zha 97]; des systèmes robotisés [Ye 95, Wha 97]; des systèmes composés par une

table de translation mécanique [Mas 95, Mav 95, Pap 97a, Tru 97] ou encore par une table de

rotation mécanique [Tar 95c, Pit 97, Kov 98]. Nous n’avons pas trouvé dans la littérature des

travaux qui dévelopent un algorithme d’acquisition d’images 3D pour des systèmes utilisant

comme support mécanique une machine à mesurer tridimensionnelle (MMT).

En fonction de l’objectif du système de numérisation chaque stratégie d’acquisition doit

respecter les différents contraintes imposées au système (topologie et dimensions de la pièce,

connaissance du modèle de la pièce, etc.). Dans notre travail nous allons définir et mettre en

uvre un algorithme d’acquisition d’images 3D, en utilisant des capteurs télémétriques de haute

précision montés soit sur une MMT, soit sur un bras de robot, l’objectif étant le contrôle des


87

tolérances de pièces industrielles. Par conséquent la principale variable est la précision des

données acquises. A notre connaissance, les stratégies de numérisation existantes n’optimisent

pas cette variable.

3.2. Vérification automatique des tolérancesBeaucoup de travaux utilisant des images 2D ont été réalisés pour l’inspection.

Moganti et Al : présentent une bonne revue des travaux d’inspection de PCB (Printed Card

Board). Il y a moins de travaux portant sur l’inspection de caractéristiques géométriques en

utilisant ce type d’images, la raison étant peut être du à la difficulté d’obtenir des données

adéquates [Mog 96].

Edinbarough et Al : présentent des modèles mathématiques et des algorithmes pour un système

visuel, d’inspection, de tolérances d’objets circulaires [Edi 95].

Chen et Su: présentent un système d’inspection qui mesure des dimensions et la concentricité

d’assemblage. Des images 2D sont prises avec une caméra. Après quelques traitements des

algorithmes pour la reconnaissance de la forme des trous intérieurs sont utilisés [Che 04].

Newman et Jain : présentent une revue très intéressante des systèmes et techniques dans le

domaine de l’inspection automatique. Ces techniques d’inspection sont classées selon deux

approches [New 95a]:

1. La première approche implique d’apparier un descripteur d’un modèle sans défaut (souvent

c’est une image synthétique) à l’image numérisée de l’objet examiné. Les objets qui n’ont

pas de défauts s’ajustent bien au modèle.

2. La deuxième approche implique d’extraire des caractéristiques de l’objet numérisé et de

comparer ces caractéristiques à une liste de règles qui décrivent un modèle idéal. Si toutes

les règles sont satisfaites, l’objet est considéré sans défaut.

Noble: présente les défis actuels des algorithmes de vision par ordinateur pour des applications

de fabrication. Le travail est concentré sur les traitements basés sur les descripteurs [Nob 95].

Tarbox et Gottschlich : présentent une approche de l’inspection visuelle automatisée basés sur

la comparaison d’un modèle volumique d’un objet de référence à un modèle volumique d’un

objet réel qui est crée itérativement à partir des données du capteur [Tar 95c].

Pahk et A : proposent un système pour inspecter la précision des moules ayant des

caractéristiques définies par le modèle CAO [Pah 95].

Tang et Davies : présentent l’interface DMIS (Dimensional Measuring Interface Specification)


88

pour l’intégration du système de planification de l’inspection INSPEX avec des MMT.

INSPEX est un système pour la préparation des plans d’inspection à partir des modèles CAO

tolérancés. DMIS est utilisé comme un format de données neutre, pour convertir les données de

sortie du logiciel INSPEX dans un format d’échange de données qui puisse être reçu par la

plupart des MMTs [Tan 95].

Roy: discute les critères pour évaluer les caractéristiques géométriques des pièces

manufacturées [Roy 95].

Redarce et Al : proposent un système d’inspection automatisé en utilisant un type de capteur de

profondeur nommé BIRIS. Au lieu d’utiliser la position du laser pour calculer les coordonnées

3D du point sur l’objet, deux vues ou plus peuvent être utilisées [Red 00].

Prieto et Al : développent une approche d’analyse basé sur le contrôle de tolérances afin

d’automatiser une phase importante de la production [Pri 03a].

Prieto et Al : proposent une stratégie qui produit automatiquement un plan d’action de

numérisation pour obtenir un nuage de points complet et exact d’une surface ou d’une

pièce [Pri 03b].

Prieto et Al : proposent une inspection non déterministe de pièces industrielles en

productique [Pri 04].

Discussion

Dans la littérature on trouve beaucoup de travaux utilisant des images 2D pour l’inspection

[Mog 96, Che 96, Edi 95]. Pour le contrôle des tolérances des pièces industrielles les images 2D

ne sont pas les plus adéquates car elles ne fournissent pas les informations relatives à la

profondeur. Les systèmes de vision basées sur le principe de la triangulation optique donnent

des informations 3D sur la topologie des pièces, par conséquent ceux-ci sont plus intéressants

pour le contrôle des pièces industrielles. En général l’inspection est faite par la comparaison

entre le modèle CAO et l’image 3D de la pièce après leur recalage. Dans l’inspection, le

principal inconvénient des systèmes de vision (par rapport aux MMTs) est la précision des

données.

L’inspection automatisée d’objets manufacturés, telle que nous l’avons définie, consiste à

comparer de façon automatique leur modèle de conception avec leur image 3D obtenue avec un

capteur télémétrique laser. Ce type de capteur très performant à l’heure actuelle, permet

d’obtenir un nuage de points 3D représentant l’objet analysé avec une précision de l’ordre de 25


89

microns à raison de 20 000 points par seconde. La mise en registre de ces deux représentations

permet de conclure si une pièce réalisée est conforme à son modèle théorique défini lors de sa

conception. La mise en correspondance est un problème difficile compliqué par la nécessité de

sélectionner le bon modèle dans une base de données CAO de grande taille qui contient la

description de toutes les pièces susceptibles de se trouver sur la chaîne d’inspection.

Une fois le modèle choisi et la mise en correspondance effectuée, on peut visuellement en

affichant sous différentes formes les résultats, mettre en évidence les zones où il y a des erreurs

(contrôle global) mais sans obtenir d'informations quantitatives ; ou alors utiliser les

informations de distance entre les points de l’image 3D et le modèle, obtenues après la mise en

registre effectuée précédemment, pour segmenter le nuage de points en sous-ensemble

représentant chacune des surfaces. Des traitements statistiques sur ces sous-ensembles vont

nous permettre d’obtenir des informations sur les différentes surfaces et de comparer celles-ci

(les informations) avec les tolérances géométriques, de formes et de cotations, affectées à l’objet

lors de sa conception. L’édition d’un rapport de contrôle tel que ceux obtenus avec les logiciels

de métrologie peut ensuite être envisagé [New 95b, Pri 98]. Afin d’améliorer sensiblement le

temps de réponse pour la sélection du bon modèle dans la base de données, nous proposons

d’établir des modèles visuels, tant des modèles CAO que de l’objet sous inspection.

L’architecture du système complet est présentée à la figure 4.1.

Figure 4.1. Architecture du projet


90

Nous proposons dans ce travail un exemple d’automatisation du contrôle tel qu’il peut être

effectué en intégrant ensemble des technologies de l’information et de la production. Nous

présentons ainsi la méthode utilisée pour rechercher le bon modèle dans la base de données et

nous détaillerons le contrôle automatique des objets.

4. Sélection du bon modèle dans la base de données4.1. Les géons

Les géons sont définis comme les constituantes volumétriques projetées d’un objet. Nous

utilisons la théorie de reconnaissance par composantes de Biederman [Bie 87] pour extraire de

l’image d’entrée les composantes volumétriques projetées, les "géons", et leur interrelation

spatiale.

4.2. Représentation surfacique CAO - GÉONS

Le modèle CAO d’une pièce mécanique décrit précisément les surfaces limites de celle-ci. Le

module CAO ® géons tente d’extraire les géons à partir de la description des surfaces limites.

Une seule méthode d’analyse a été implémentée jusqu’à présent, celle de séparation sur boucles

internes. La méthode consiste à identifier au préalable les boucles internes du modèle, puis à

amorcer un mécanisme d’hypothèse qui recherche un éventuel géon à partir de la boucle interne

(une boucle interne est toujours le lieu de jonction entre deux ou plusieurs géons). En cas

d’échec d’une hypothèse, le modèle est séparé sur la boucle interne, ce qui permet de faire

évoluer la connaissance de l’objet. Cette technique permet actuellement de reconnaître un peu

plus de 80% des géons de toutes les pièces expérimentales. Les géons manquants sont fournis

grâce à l’expertise humaine.

4.3. Extraction des géons de l’image d’illuminance

La mémoire associative qui identifie les modèles CAO les plus susceptibles de correspondre à

la pièce sous inspection est alimentée par les attributs de géons extraits de l’image d’illuminance.

Nous disposons présentement d’une banque d’images des pièces manufacturées acquises dans

des conditions variées et contrôlées d’éclairage et de positions sur la chaîne de montage. Les

travaux de conception des algorithmes d’extraction de géons ont été réalisés à l’INSA de Lyon.


91

4.4. Mémorisation associative

Pour établir la correspondance entre le modèle visuel de la pièce sous inspection et les divers

modèles de la base de données, nous adoptons une approche connexionniste au moyen d’une

mémoire associative, celle-ci recevant des représentations visuelles plus simples à manipuler.

Le réseau neuronique est entraîné au moyen des représentations par géons extraites des

modèles CAO de la base de données. En opération, les attributs des géons de l’image de caméra

CCD sont transmis à la mémoire au fur et à mesure qu’ils sont extraits et cette dernière affine les

sorties possibles au moyen d’une analyse syntaxique et contextuelle des attributs de géons.

5. Contrôle automatiqueNous avons défini le contrôle automatique comme étant la comparaison entre le modèle CAO

de l’objet et un nuage de points 3D de celui-ci, obtenu avec un capteur 3D. Cette comparaison

nous permet d’évaluer les erreurs locales et globales pouvant exister entre les modèles et les

pièces manufacturées. De plus, si pour obtenir une image 3D de l’objet nous utilisons un capteur

sans contact de type télémètre laser, à la place d’une machine traditionnelle de mesure, nous

obtiendrons des nuages de points beaucoup plus importants en un temps beaucoup plus court,

avec l’inconvénient cependant d’une précision un peu moins bonne.

5.1. Le capteur 3D 1

La géométrie du balayage synchronisé repose sur un miroir à deux faces qui est utilisé pour

projeter et détecter un faisceau laser concentré ou collimaté (figure 4.2). La source utilisée dans

les prototypes développés au CNRC est un laser habituellement couplé à une fibre optique. Le

miroir de balayage et un miroir fixe servent à projeter le faisceau laser sur la scène. La lumière

diffusée est recueillie par le même miroir de balayage que celui de la projection, et elle est

concentrée sur un DTC linéaire (voir partie gauche de la figure). À noter que le DTC est incliné

(condition de Scheimpflug) pour compenser la défocalisation à la détection [Ber 95].

Pour l'essentiel, la configuration illustrée sur cette figure représente un dispositif de mesure de

profil. Un deuxième miroir de balayage (non illustré sur la figure) peut être utilisé pour dévier

orthogonalement à la fois la lumière laser projetée et la lumière laser réfléchie, ou bien encore,

un dispositif de positionnement à support mobile du commerce, comme une machine à mesurer

les coordonnées (CMM) peut servir à déplacer mécaniquement l'ensemble du montage de


92

caméra. La société Hymarc Ltd. fabrique actuellement, en vertu d'un contrat de licence, un

numériseur 3D monté sur une machine CMM pour des applications de génie mécanique. C’est

ce type de capteur que nous avons utilisé pour nos expérimentations. Il nous permet de

numériser des objets avec une précision meilleure que 25 microns, à raison de 20000 points par

seconde.

Figure 4.2. Triangulation optique qui utilise le principe d’auto-synchronisation

Sonde CNRC

1. Cette section ainsi que la figure sont issues du site Web de l’IIT du CNRC à http://www.nrc.ca

5.2. La méthode de mise en registre

Après numérisation de la pièce, nous avons deux ensembles de données, le premier est le

fichier CAO issue de la conception et le second, le nuage de points 3D. Ces données étant

exprimées chacune dans leur propre repère, la première opération à effectuer est donc de

superposer ces deux ensembles en calculant la transformation (rotation + translation) à effectuer,

c’est ce que l’on appelle la mise en registre. [Mor 95] a développé une méthode de mise en

registre que nous avons utilisé dans ce travail. Celle-ci repose sur le travail bien connu de Besl

et McKay [Bes 92], qui en 1992 ont développé une méthode générale précise et facilement

implémentable de mise en registre de formes 3D, prenant en compte les surfaces gauches. La

méthode est basée sur l’algorithme ICP (Iterative Closest Point), qui ne nécessite qu’un calcul

de distance pour trouver le point le plus proche d’une forme géométrique à un point donné.

La transformation rigide est calculée en utilisant un quaternion-unité. Mais comme

l’estimation de la transformation est donnée par une distance au moindre carré, la méthode n’est

pas suffisamment robuste vis-à-vis des points n’appartenant pas à la forme (points dus au bruit

ou à la présence d’autres formes dans la scène). Comme solution à ce problème, Masuda et

http://www.nrc.ca


93

Yokoha [Mas 95], estiment la transformation entre deux images de profondeur de façon robuste

en intégrant l’algorithme ICP avec un échantillonnage aléatoire et une estimation de la médiane

au moindre carré (Least Median Square-LMS). Ils ont montré que la mise en registre entre deux

images se fait avec une très grande robustesse (jusqu’à 80% de points aberrants).

Moron [Mor 96] a implémenté un algorithme pour la mise en registre d’un nuage de points 3D

non-ordonnés, avec un modèle CAO au format STL ou NURBS reposant sur cette méthode.

Celle-ci peut se décomposer en trois étapes principales:

1. L’algorithme sélectionne de façon aléatoire Ns points 3D dans l’ensemble des données et

calcule une transformation rigide avec l’algorithme ICP à partir de ce sous ensemble. Cette

procédure est répétée Nt fois. Le problème est non linéaire et l’estimateur LMS donne une

solution qui n’est pas forcément la meilleure, mais celle-ci est obtenue très rapidement. La

probabilité de trouver une solution augmente quand Ns décroît ou Nt croît. Après chaque

exécution, la qualité de l’estimation de la transformation rigide est évaluée en calculant

l’erreur médiane au moindre carré.

2. La meilleure estimation de la transformation rigide, correspondant à la plus faible erreur

médiane, est appliquée à l’ensemble des points 3D ; puis l’ensemble des points est

segmenté en deux sous-ensembles, le premier correspondant aux points appartenant à la

pièce et le second aux points aberrants.

3. Un algorithme standard ICP au moindre carré est appliqué au sous-ensemble de points

appartenant à la pièce afin de trouver la transformation rigide, solution de notre problème.

Pour obtenir la solution globale du problème, il est nécessaire d’appliquer la méthode

plusieurs fois, avec des conditions initiales différentes. Nous choisissons alors la solution

correspondant à la meilleure estimation.

5.3. La segmentation des données 3D

Pour faire le contrôle tel que nous l’avons défini, il est nécessaire de connaître pour chaque

objet les différentes surfaces qui le composent. Autant cela ne pose aucun problème pour le

modèle CAO, autant cela est difficile avec le nuage de points 3D non-ordonné, image de l’objet

à contrôler. Nous avons donc développé une méthode de segmentation supervisée qui nous

permet de décomposer le nuage de points originel en autant de sous ensembles qu’il existe de

surfaces. La segmentation est faite en calculant la distance séparant chaque point du nuage 3D


94

Local GeometricProperties

Comparison

MarkedPoint

Closest SurfacePoint on the Surface

DistanceComputation

CAD Model(NURBS)

3D RegisteredPoint

de toutes les surfaces du modèle CAO, définies comme surfaces paramétriques NURBS ; et en

comparant certaines propriétés géométriques locales entre chaque point 3D du nuage et son

point le plus proche sur la surface [Masu 95].

Le problème du calcul de la distance point 3D / surface NURBS peut être formulé comme suit :

trouver le point sur la surface paramétrique tel que la distance entre le point 3D et celui

appartenant à la surface soit minimale dans la direction perpendiculaire au plan tangent au point

de la surface. Le problème est alors résolu comme étant un problème de minimisation. Les

propriétés locales que nous estimons sont : la normale à la surface, la courbure gaussienne et la

courbure moyenne. Pour le point appartenant à la surface, ces propriétés sont estimées à partir

de la surface paramétrique NURBS. Pour les points 3D, nous utilisons un polynôme

paramétrique du deuxième ordre calculé avec les points du voisinage. Un point 3D est étiqueté

avec le numéro de la surface dont il est le plus proche, si les propriétés locales de ce point sont

similaires à celles du point appartenant à la surface.

La figure 4.3 présente un schéma fonctionnel de la segmentation.

Figure 4.3. Schéma fonctionnel de la segmentation


95

5.4. Calcul de la distance point 3D / NURBS

Le problème de la mesure de distance d’un point à une surface NURBS peut être présenté

comme suit: Trouver un point dans l’espace paramétrique de la surface (u0,v0) tel que la distance

entre la surface S(u0,v0) et le point r est minimum dans la direction perpendiculaire au plan

tangent en ce point.

La fonction à minimiser est la suivante: minuo,vo2),( vuSr −

Si on l’on prend le développement en série de Taylor de la surface paramétrique S(u0,v0), nous

obtenons: )()(),(),( 0000 vvSv

uuSu

vuSvus −∂∂+−

∂∂+=

Le problème de minimisation devient: minuo,vo =

2

0000 )()(),( vvSv

uuSu

vuSr −∂∂

+−∂∂

+−

Cela peut s’exprimer sous forme matricielle par : minuo,vo=2

dwJ −

Où J la matrice Jacobienne de S(u, v) est égale à :

est égale à la variation de paramétrisation

Si d(u,v) est l’erreur de paramétrisation initiale de (ut ,vt ), le point le plus proche de la surface,

alors d(u,v) = r - S (u,v), la solution pour minimiser notre problème devient w (JT J) -1 JT d.

En utilisant une procédure itérative, on peut calculer la distance d’un point à une surface en un

maximum de cinq itérations.

5.5. Propriétés géométriques locales

Soit P un point 3D de l’image de profondeur et Q le point le plus proche appartenant à la

surface. Afin de terminer le processus de segmentation, nous comparons les caractéristiques

locales du point P avec celles du point Q; si elles sont suffisamment semblables alors le point P

appartiendra à la surface contenant Q. Afin de déterminer les propriétés locales d’un point, nous

utilisons la méthode mise au point par Boulanger [Boul 94].

−

−=

vvuu

w0

0

vz

uz

vy

uy

vx

ux

∂∂

∂∂

∂∂

∂∂

∂∂

∂∂


96

La normale à la surface n(u,v), la courbure gaussienne K(u,v) et la courbure moyenne H(u,v)

du point P(u,v) de la surface paramétrique (u,v) paramétrique peuvent être estimées à partir des

équations suivantes:

η =),(),(

),(),(

vurvur

vurvur

vu

vu

×

×

=),( vuK[ ][ ] [ ]

[ ]2

4vu

vuuvvuvvvuuu

rr

rrrrrrrrr

×

⋅⋅−⋅⋅⋅⋅

322),(

DCBAvuH −+

= où

[ ]vuuuvu rrrrrA )( ⋅= , [ ]vuvvvu rrrrrB )( ⋅=

[ ]vuuvvu rrrrrC )( ⋅= , )( vu rrD ⋅= et

urru ∂

∂= ,

vrrv ∂

∂= ,

urruu ∂

∂=

2

,vrrvv ∂

∂=

2

,vurruv ∂∂

∂=

2

Pour estimer les dérivées partielles premières et secondes au point P, nous utilisons un

polynôme paramétrique du second ordre. Il est obtenu en utilisant un voisinage N x N,

où r(u,v)= (x(u,v),y(u,v),z(u,v))T est un point du nuage obtenu avec le capteur 3D.

Soit Tzyx

i

j

j

iij vuhvuhvuhvuavu )),(),,(),,((),(

2

0

2

0

== ∑∑= =

η

où ai j est le coefficient de chaque composante de n(u,v); celui-ci est égale à zéro si i+j >2.

En utilisant ce polynôme, les dérivées partielles au point P sont obtenues comme indiqué ici

01102010 2 vauaau ++=η , 00201101 2 vauaav ++=η

202auu =η , 022auu =η , 11auv =η

où (u0,v0) sont les coordonnées paramétriques du centre du voisinage. Nous trouvons ces

paramètres par une méthode des moindres carrés.

Finalement, nous comparons les propriétés géométriques locales de Q estimées à partir des

surfaces NURBS avec celles de P des données 3D issues du capteur. Soit tol l’angle permis

entre la normale à la surface NS et la normale Nr aux données 3D au point P.


97

La condition ),( rNSNAngle < tol doit être respectée. Soit Ktol et Htol les variations acceptables

de la courbure gaussienne et de la courbure moyenne, alors les conditions rkSK − < Ktol, ,and

rHSH − < Htol doivent aussi être respectées afin d’étiqueter correctement le point.

6. L’inspection visuelleNous utilisons un capteur de profondeur sans contact (Hymarc), monté sur une machine à

mesurer, qui nous permet une grande précision lors des déplacements et donc une bonne mise en

registre des différentes vues afin d’obtenir un nuage de points très précis. Le résultat de la

numérisation est un nuage de points 3D, non-ordonnés, décrivant de façon précise les surfaces

externes de l’objet à contrôler.

Pour une visualisation rapide des défauts de la pièce, nous avons implémenté une interface

graphique simple, dont la fenêtre du menu principal est représentée sur la figure 4.4.

Figure 4.4. Fenêtre du menu principal

Une fois la segmentation effectuée, chaque point est étiqueté. Nous pouvons donc choisir

chaque surface et, à partir de ce menu, nous pouvons soit effectuer un contrôle local de l’objet,

soit un contrôle global [Bou 06b].


98

Avec le bouton “intervalle de tolérance” nous fixons les tolérances minimales et maximales

entre lesquelles les points doivent se trouver, afin de décider si l’objet est conforme au cahier

des charges ou à rejeter. Après avoir fixé ces valeurs, le logiciel recherche les points dans et hors

tolérance et termine par l’affichage à l’écran du nuage de points où ceux- ci sont représentés

avec des couleurs différentes. L’opérateur peut directement décider si la pièce est acceptée ou

rebutée. Cette opération peut se faire soit sur la pièce au complet soit uniquement sur une ou

plusieurs surfaces (figures 4.5 et 4.6).

Le bouton “Affic de segments” permet, pour une meilleure visibilité, d’afficher non pas un

point, mais le segment de droite reliant le point à la surface (cette longueur dépendra de la

distance séparant le modèle du nuage de points).

Le bouton “seuil” nous permet de choisir une valeur de seuil soit positive (trop de matière),

soit négative (manque de matière) et de visualiser, après calcul et affichage des points avec des

couleurs différentes, les zones où il y a trop de matière ou pas assez. Comme précédemment on

peut, pour améliorer la visibilité, afficher un segment.

Le bouton “Rap Geom Globale” permet d’éditer un fichier où pour chaque surface de l’objet

nous donnons le nombre de points la composant, le nombre de points hors-tolérance, la valeur

moyenne, la variance, l’écart-type, la valeur minimale et la valeur maximale.

Le bouton “Rap Geom Locale” permet d’éditer un fichier où pour chaque point sont consignés

la direction de sa normale, les courbure gaussienne et moyenne, ainsi que sa position dans

l’espace.

Figure 4.5. Superposition du nuage de points et du modèle


99

Figure 4.6. Surface 6 superposée au modèle

Figure 4.7. Exemple de rapport de contrôle sur la surface 6

La figure 4.7 montre un rapport de contrôle sur la surface N°6. Il en ressort tous les paramètres

tels que le nombre de points hors tolérance, la moyenne arithmétique, la variance, l’écart type

etc.

Figure 4.8. Variance en fonction de l’angle d’incidence dans la directiondu champ de laser Var (α ) = 3E-6e 0:07α

RAPPORT DE TOLERANCES SURFACE 6

Nombre de points : 253Moyenne arithmétique : 68.5632Nombre Points hors tolérance : 221Moyenne arithmétique : 0.276865Variance : 0.00954803Ecart type : 0.0982804Somme des carrées des écarts : 2.26551Ecart moyen : 0.0567812Valeur minimum : -0.254786Valeur maximum : 1.18122


100

L'angle d'incidence est mesuré dans la même direction que le champ de rayon du laser.

La figure 4.8, nous montre que la plus petite valeur de dispersion est produite pour un angle

d'incidence près du zéro degrés, ou normale à la surface. Les meilleurs placements de balayage

se font sur un intervalle [-35°, + 35°] du champ de rayon laser.

7. ConclusionNous avons présenté dans ce chapitre une méthode de contrôle de pièces manufacturées. En

premier lieu le système commence par effectuer une mise en registre automatique d’un nuage de

points 3D non-ordonnés, image d’un objet, avec son modèle CAO au format NURBS. Puis une

segmentation de ce nuage en surface indépendante est réalisée.

A partir de cette segmentation, en donnant des valeurs de tolérance ou de seuil, nous pouvons

effectuer un contrôle de la pièce à inspecter. Malgré la simplicité apparente des pièces, certaines

sont intéressantes du fait de la présence de symétrie qui rend la mise en registre délicate. En fait

plus la géométrie de l’objet est complexe, plus simple sera la mise en registre, car l’estimation

de la transformation rigide n’en sera que plus aisée.

La méthode de segmentation que nous avons développé est indépendante de la géométrie de

l’objet ; elle ne dépend que de la précision des points obtenus lors de sa numérisation et de la

densité de ceux-ci. Une grande densité est nécessaire si l’on veut obtenir une bonne estimation

des paramètres locaux de la surface. La précision de l’inspection ne dépend que de la précision

du capteur 3D qui numérise la pièce; à l’heure actuelle les capteurs 3D sans contact de type

télémètre laser ont une précision de l’ordre de 25 microns pour les meilleurs. Nous sommes

encore loin de la précision obtenue avec une machine à mesurer ; mais notre méthode de

contrôle peut s’appliquer à un nuage de points obtenu avec ce type de machine, le seul

inconvénient étant la lenteur de la numérisation.

Ce travail se poursuit actuellement par le développement d’une stratégie de numérisation, qui

permettra d’améliorer la précision des mesures, en contraignant le capteur à avoir certaine

direction de prise de vue au moment de la numérisation. De plus, nous envisageons de travailler

sur l’analyse des tolérances de formes à partir des propriétés locales obtenues lors de la

segmentation. Des exemples d’applications liées à la Reconnaissance des formes 3D et au

contrôle industriel avec une validation des résultats sont illustrés au chapitre 5.

Chapitre 5 Applications

101

CHAPITRE 5

Applications

Nous présentons dans ce chapitre différentes applications de notre méthode de mise en

correspondance :

• La reconnaissance de formes,

• L’inspection d’objets industriels,

• La vérification de la présence de matière suffisante après ébauche et avant finition d’une pièce.

La méthode de mise en correspondance ainsi que ses applications ont été implémentées sur

une station de travail Silicon Graphics Indy munie d’un processeur RISC Mips R5000SC 128

bits et programmées en C++ (Gnu g++).

1. Reconnaissance de formes

Il existe de nombreuses manières de résoudre les problèmes de reconnaissance de formes en

2D. L'une d'elles consiste à utiliser des modèles complexes associés à des classifieurs simples

(plus proches voisins, distance euclidienne) ; à l'opposé, on peut utiliser des modèles simples,

associés à des classifieurs plus complexes [Mil 93].

Pour reconnaître des objets 3D, on utilise généralement des méthodes de reconnaissance 2D,

en considérant toutes les vues potentielles de l'objet. L'inconvénient majeur de ces méthodes est

de multiplier d'une façon significative la quantité de données à traiter.

Lorsqu’on dispose de données 3D, il est intéressant d'utiliser la modélisation CAO (surfaces,

volumes, etc ...) pour décrire la géométrie des objets 3D à reconnaître. Notre méthode de mise


102

en correspondance [Données 3D/Modèle CAO], automatique et robuste, résout les problèmes

de mise en correspondance classiques crées par la grande quantité d'informations à traiter et par

la complexité des modèles utilisés.

Pour conforter notre propos, nous appliquons notre méthode de mise en correspondance à

deux ensembles d'objets en utilisant la méthode de modélisation STL. Le premier est constitué

de quatre objets paramétriques polyédriques (polyèdre 1, polyèdre 2, polyèdre 3, polyèdre 4)

tandis que le second est un ensemble de trois pièces plus complexes (Support 1, Support 2,

Support 3) se distinguant par deux perçages de diamètres différents.

Un objet de chaque famille a été numérisé (polyèdre 4 et Support 2). Le critère de

reconnaissance utilisé est la plus petite distance moyenne [données 3D/Modèles CAO NURBS

découpées], celle-ci étant la somme de toutes les distances Points (transformés par la

transformation rigide déterminée par l'algorithme de mise en correspondance)/Modèle CAO

divisée par le nombre de points utilisés.

1.1. PolyèdresLa méthode de mise en correspondance, utilisant les quaternions pour éviter les minimums

locaux, a été appliquée entre les données 3D issues de la numérisation et chacun des modèles

CAO triangulés. Le tableau 5.1 donne la distance moyenne obtenue, pour chaque modèle CAO

utilisé. La plus petite distance moyenne globale est obtenue pour le polyèdre4, qui était l'objet à

reconnaître et qui procure une mise en correspondance parfaite.

La non nullité de cette distance s'explique par l'existence d'erreurs d'usinage sur l'objet

numérisé, ainsi que par la présence de bruit sur les données capteur.

Polyédre 1

Distance Moyenne

(mm)

Polyédre 2

Distance Moyenne

(mm)

Polyédre 3

Distance Moyenne

(mm)

Polyédre 4

Distance Moyenne

(mm)

3.604 2.254 1.198 0.173

Tableau 5.1. Distance moyenne obtenue pour chaque modèle CAO


103

1.2. SupportsComme pour les objets polyédriques, la méthode de mise en correspondance utilisant les

quaternions a été utilisée ; les résultats obtenus figurent dans le tableau 5.2.

Support 1

Distance Moyenne

(mm)

Support 2

Distance Moyenne

(mm)

Support 3

Distance Moyenne

(mm)

0.147 0.0183 0.117

Tableau 5.2. Distance moyenne pour chacun des modèles CAO

Le support 2, qui présente la distance moyenne la plus faible, a été reconnu.

2. Inspection d’objets industrielsDifférents objets conçus en CAO ont été usinés, puis numérisés ; les données

correspondantes figurent en Annexe C. Une fois les points 3D mis en correspondance avec le

modèle CAO, chaque distance [point/Modèle CAO NURBS découpées] est calculée. Après

avoir proposé des outils permettant de réaliser une inspection quantitative, nous proposons

maintenant des outils pour une inspection graphique. Pour cela, nous faisons apparaître

graphiquement, par différents procédés, la localisation et la quantification des erreurs

points/modèle CAO relevées :

• Un premier procédé de visualisation consiste à attribuer à chaque triangle du modèle

CAO une couleur dépendant de la distance moyenne triangle/points voisins.

• La seconde consiste à représenter chaque segment point 3D/point associé du modèle

CAO avec une couleur dépendant de la distance entre les deux points ou une couleur

dépendant d’une valeur distance seuil.

• La troisième consiste à associer à chaque surface une carte de texture plus ou moins fine

dont la couleur locale dépend de la distance avec les points 3D voisins.

Dans ces trois cas (sauf pour le seuillage), il existe une correspondance entre la distance

représentée et la couleur utilisée (Figure 5.1).


104

Les couleurs s’échelonnent entre le bleu pour une erreur nulle et le rouge pour l’erreur

maximum, le vert représentant l’erreur maximale divisée par deux.

2.1. Procédés de visualisationNous détaillons maintenant les trois procédés de visualisation que nous avons utilisés.

2.1.1. Coloration des triangles

A chaque triangle est associé une couleur dépendant de la distance moyenne de ce triangle

avec ses points voisins. Les triangles pour lesquels il n’y a pas de points associés apparaissent en

gris. Cette représentation ne requiert pour la visualisation que le modèle STL de l’objet, le

fichier de points transformés et le fichier de couleur des triangles généré par le programme de

mise en correspondance. Son inconvénient provient de la limitation de la représentation STL qui,

à un plan de n’importe quelle dimension, va faire correspondre un faible nombre de triangles

quelque soit la valeur d’approximation STL. Ainsi, il est toujours difficile d’inspecter

localement une surface plane décrite par une triangulation STL. Nous proposons deux solutions

pour pallier cet inconvénient :

• Subdiviser chaque triangle en un ensemble de triangles tel que chaque surface soit décrite

de façon suffisamment précise.

• Utiliser directement un autre type de triangulation plus adapté (triangulation éléments

finis par exemple).

2.1.2. Carte de texture

Dans le domaine du graphisme par ordinateur, à chaque surface à afficher est associée une

carte de texture qui prend en compte la forme de la surface, les sources d’éclairage, et la texture

de l’objet observé (figure 5.1), et qui épouse la forme de la surface géométrique à afficher.


105

Figure 5.1. Exemples de Texture Mapping

Exemples extraits de“Open GL programming guide” Adison Wesley publishing Company

Nous proposons de modifier cette carte (grille) de texture de deux façons différentes :

• Texture Mapping 1 :

Pour chaque carreau élémentaire de la carte de texture, nous attribuons une couleur de

l’échelle de la figure 5.2, en fonction de la distance moyenne carreau/points voisins (voir figure

ci dessous).

P

{uo ,v0 } {u1 ,v0 }

{uo ,v1 } {u1 ,v1 }


106

• Texture Mapping 2 :

Chaque point 3D se projette sur la carte de texture sous forme d’un disque dont la couleur

dépend de la distance point/surface (figure ci-dessous).

P

Dans les deux cas, il s’agit de trouver un compromis sur la taille du carreau (disque) unité. Si

celui-ci est trop petit, il sera difficilement visible et s’il est trop gros, la localisation des erreurs

devient difficile. Pour le texture Mapping 2, il peut y avoir recouvrement des disques, et donc

moyennage des erreurs, l’interprétation de la visualisation devient alors plus difficile.

2.1.3. Tracé des segments d’erreur

Chaque point 3D est relié à son point le plus proche sur le modèle géométrique par un

segment de couleur, dont la couleur dépend de l’erreur locale (qui est également la longueur du

du segment). Nous avons implémenté deux façons d’afficher les couleurs :

• Seuillage : Une valeur de distance-seuil dseuil est fixée par l’opérateur de façon

interactive; l’affichage est modifié en temps réel. Pour les points dont la distance est

comprise entre 0 et dseuil , les segments apparaissent en bleu, les autres apparaissent en

rouge. C’est une façon simple de sélectionner les points hors tolérance de forme globale.

• De la même façon qu’au paragraphe précédent, deux valeurs extrêmes dmin et dmax sont

fixées par l’opérateur. Pour les points dont la distance est comprise entre ces deux bornes,

les segments apparaissent avec une couleur dépendant de l’échelle présentée figure 5.2,

s’étendant du bleu pour dmin au rouge pour dmax .

Q

{uo ,v1 } {u1 ,v1 }

{uo ,v0 } {u1 ,v0 }


107

Cette technique de visualisation permet d’adapter localement l’échelle de couleur et de

mieux apprécier les erreurs.

Nous présentons maintenant des résultats d’inspection utilisant toutes les méthodes

présentées dans ce manuscrit.

2.2. ExemplesLes objets qui seront inspectés graphiquement ont été numérisés.

2.2.1. Polyèdre

Données 3D : Objet "Polyèdre" numérisé

Modèle STL : 24 triangles

Nt : 10

Ns : 30

De ces différentes visualisations (figures 5.3, 5.4 et 5.5), nous déduisons qu’une des faces est

mal positionnée (erreur de 0,86 mm), à cause d’une erreur d’usinage.

2.2.2. Plaque

Données 3D : Objet "Plaque" numérisé à l’aide d’un capteur télémétrique


Nt : 10

Ns : 40

Temps de calcul : 8mn 12s

La visualisation (figures 5.6 (a et b) et 5.7 (a et b)) montre que cette plaque réalisée en

prototypage rapide présente une courbure progressive anormale sur sa face supérieure allant

jusqu’à une erreur de forme de 1,03 mm.

{

{


108

2.2.3. Support

Points 3D provenant du capteur télémétrique

Données 3D : Objet "Support" numérisé à l’aide d’un capteur télémétrique


Nt : 15

Ns : 200


Figure 5.2. Echelle de couleurLe bleu correspond à une erreur nulle et le rouge à l’erreur maximum

Figure 5.3. Affichage des segments d’erreursObjet polyèdre

Erreur maximum = 0,86 mm

{


109

Figure 5.4. Objet polyèdre : Texture Mapping 1

Figure 5.5. Objet polyèdre : Texture Mapping 2

Figure 5.6. Visualisation de l’objet Plaque utilisant les triangles colorés(a) Vue de dessus

Erreur maximale de 1,03 mm (rouge)


110

Figure 5.6. Visualisation de l’objet Plaque utilisant les triangles colorés(b) Vue de dessous

Erreur maximale de 1,03 mm (rouge)

Figure 5.7. Visualisation de l’objet Plaque utilisant les segments colorés(a) Vue de dessus

Erreur maximale de 1,03 mm


111

Figure 5.7. Visualisation de l’objet Plaque utilisant les segments colorés(b) Zoom sur les erreurs les plus importantes


Figure 5.8. Représentation avec triangles colorés de l’objet SupportErreur maximum/triangle de 0,28 mm


112

Figure 5.9. Représentation par segments colorés(a) Vue de dessus


Figure 5.9. Représentation par segments colorés(b) Vue de dessus avec agrandissement du perçage gauche



113

Figure 5.10. Objet SupportTexture Mapping 1

Figure 5.11. Objet Support(a) Texture Mapping 2


114

Figure 5.11. Objet Support avec agrandissement du perçage gauche(b) Texture Mapping 2

Figure 5.12. Visualisation des erreurs avec les triangles colorésErreur maximum de 0,52 mm

Figure 5.13. Visualisation des segments : Inspection du perçage de droiteErreur maximale de 0.56 mm


115

La figure 5.8 montre la représentation des erreurs avec les triangles colorés. Les figures 5.9

(a et b) montrent la représentation des erreurs avec les segments colorés et les figures 5.10 et

5.11 (a et b) avec les deux types de texture mapping.

Points 3D provenant de la machine à mesurer

Données 3D : Objet "Support" numérisé à l’aide d’une machine à mesurer


Nt : 15

Ns : 200


Figure 5.14. Objet Support : Mise en correspondance points 3D/modèle CAO STL

Les erreurs de fabrication sont mises en évidence dans les figures 5.12 et 5.13 en utilisant les

triangles et les segments colorés.

DiscussionA partir des deux types de points 3D, nous retrouvons graphiquement sur cet objet les mêmes

erreurs que celles signalées au chapitre précèdent.

• Inclinaison des deux lamages,

• Désaxage et forme elliptique des deux perçages,

• Mauvais positionnement en x des deux lamages.

Sur cet objet, on peut juger facilement de l’efficacité de chacune des méthodes de

visualisation. En effet, sur la face supérieure de l’objet est gravé un logo. Celui-ci ne figure pas

dans le modèle CAO. Il apparaît donc une erreur importante dans cette zone de gravure.

{


116

2.2.4. Téléphone

Données 3D : Objet "Téléphone" numérisé à l’aide d’une machine à mesurer


Nt : 10

Ns : 50

Pour cet objet, nous disposons de deux types de données : une seule image 3D, qui

correspond à une seule vue numérisée par le capteur télémétrique et des données 3D qui

résultent de la fusion de plusieurs images 3D.

Une seule image 3D

Figure 5.15. Téléphone : Mise en correspondance de l’image 3D avec le modèle CAO STL

On constate qu’une seule image 3D est facilement mise en correspondance avec le modèle

STL (figure 5.15). La visualisation des triangles colorés (figure 5.16), fait apparaître une

variation de couleur au centre de la face supérieure de la pièce, due à la présence d’un logo gravé

à cet endroit.

Figure 5.16. Visualisation avec triangles colorésMise en correspondance de l’image 3D avec le modèle CAO STL

Erreur maximum 0,12 mm

{


117

Données 3D complètes

Figure 5.17. Téléphone : Mise en correspondance des points 3Davec le modèle CAO STL

Mis à part les points qui appartiennent à la fixation de l’objet, on constate une erreur de 5 mm

sur le diamètre de la partie cylindrique gauche. On vérifie également que les points 3D

“parasites”, correspondant à la tige de fixation de la pièce lors de sa numérisation, ne gênent en

rien la mise en correspondance et prouvent la robustesse de la méthode.

2.2.5. IMS

Données 3D : Objet "Support" numérisé à l’aide d’un capteur télémétrique


Nt : 10

Ns : 30

Temps de calcul : 16mn

Sur cette pièce, on peut constater que la plaque-base est trop courte sur sa largeur ainsi que

sur sa longueur, et que les éléments figurant sur cette plaque (marches d’escalier...) référencés

par rapport aux extrémités de la pièce se trouvent légèrement décalés (2,3 mm).

{


118

(a) (b)

(c)

Figure 5.18. Représentation par les triangles colorés

2.2.6. Pièce C

Données 3D : Objet "Pièce C" numérisé à l’aide d’un capteur télémétrique


Nt : 10

Ns : 30{


119

On constate sur la figure ci-dessous, que la représentation par triangles colorés montre que

cette pièce présente une erreur de mise en correspondance nulle à une extrémité et importante à

l’autre extrémité.

Figure 5.19. Représentation par les triangles colorés sans affichage des points

Figure 5.20. Représentation par les triangles colorés avec affichage des points

extrémité de gauche (à gauche), extrémité de droite (à droite)


120

En visualisant la superposition des points aux deux extrémités, on s’aperçoit que la pièce est

courbée de plusieurs mm dans le sens de sa longueur, défaut lié à sa fabrication.

3. Préparation à la finition d’une pièce ébauchéeCette application particulière permet à partir de points 3D provenant de la numérisation

d’une pièce ébauchée de vérifier qu’il reste suffisamment de matière, avant d’aborder la phase

de finition (figure 5.21). Ceci nécessite, en plus des points 3D, de disposer du modèle CAO de la

pièce finie et du programme de mise en correspondance où tous les points 3D sont utilisés pour

la phase ICP. D’autre part, cette application est particulièrement intéressante pour des pièces de

forme complexe, telle qu’une aube de turbine, difficiles à mesurer par des moyens classiques.

Figure 5.21. Mise en correspondance des points de la pièce polyèdre ébauchée

avec le modèle CAO de la pièce finie

4. ConclusionNous avons montré dans ce chapitre que notre méthode de mise en correspondance, permet,

en choisissant un classifieur simple, de faire de la reconnaissance de formes sur des objets 3D

L’intérêt principal de notre méthode est de pouvoir superposer les données 3D de l’objet à

contrôler avec le modèle géométrique, créé lors de sa conception, et de mettre ainsi en évidence

les erreurs de fabrication. Cette phase d’inspection peut se faire de façon quantitative (chapitre

précédent).


121

Nous avons proposé également plusieurs techniques de visualisation qui permettent de

localiser les défauts :

• Triangles colorés : faciles à mettre en oeuvre, mais nécessitent une triangulation adaptée

pour mieux apprécier les défauts.

• Texture Mapping : Lourde à mettre en oeuvre, avec un compromis à trouver concernant la

visibilité des tâches d’erreur (compromis visibilité/moyennage des erreurs).

• Segments d’erreur : Obtenus soit par seuillage, soit par échelle d’erreur colorée, cette

méthode est la plus efficace car elle est vraiment locale (un segment par point) et son

échelle peut varier de façon interactive selon les choix de l’opérateur.

Conclusion générale

122

Conclusionet

Perspectives

1. ConclusionLe travail décrit dans cette thèse a porté sur deux thématiques imbriquées l’une dans l’autre

dont le robot mobile représente en fait un terrain d’essai formidable pour confronter ainsi les

techniques de Reconnaissance des Formes et d’Intelligence Artificielle avec la complexité du

monde réel et les contraintes de la robotique.

Ce travail s’est articulé autour du thème de la reconstruction 3D en vision par ordinateur et la

reconnaissance des données 3D en productique, et a apporté des contributions dans divers

domaines.

D’une part nous avons présenté un système de reconnaissance des formes par la construction

d’informations tridimensionnelles d’une scène à partir des couples de régions homologues

déterminés. Nous avons proposé une nouvelle approche pour résoudre le problème de

l’appariement des segments de droites des images stéréoscopiques. Les points forts de cette

dernière reposent d’une part sur l’utilisation de plusieurs indices visuels (régions, contours,..)

afin de bénéficier d’informations plus riches, et d’autre part sur le renforcement de la

segmentation à chaque niveau du système.

D’autre part ce travail fait en amont nous a conduit à découvrir un domaine en plein essor qui

est celui de la productique dont les paramètres rentabilité et productivité en sont les plus

quantifiés.

L’application industrielle proposée a été le contrôle automatique d’objets comportant des

surfaces complexes à partir de leur modèle CAO et de données 3D provenant d’un capteur

télémétrique.


123

Ce sujet étant nouveau pour l’équipe Robotique du laboratoire LEA, a nécessité un

important travail de recherche bibliographique, dans des domaines tels que la mise en

correspondance 3D, la reconstruction 3D, l’inspection automatique visuelle et les modèles

déformables,...

Ce modeste travail a été une première approche, vue par un automaticien, de la Métrologie

Assistée par Ordinateur.

Notre conclusion est qu’à l’heure actuelle la seule limitation à ce problème de contrôle, tel

que nous l’avons résolu, est surtout un problème de capteurs. Si l’on peut trouver un capteur

très précis (même précision que celle obtenue avec une MMT, soit le m), sans contact et

permettant des vitesses d’acquisition de l’ordre de 20000 points par seconde, alors il sera

possible de faire prendre des décisions sur la conformité d’une pièce par ordinateur.

Après avoir choisi deux types de modèles géométriques surfaciques représentant l’objet

étudié, nous avons détaillé la chaîne d’acquisition 3D permettant d’obtenir les données 3D.

Nous avons ensuite présenté notre méthode de mise en correspondance 3D générale, dont

nous avons détaillé les performances. Finalement, nous avons présenté quelques applications

à cette méthode, parmi lesquelles la Reconnaissance de formes et le contrôle automatique

d’objets de formes complexes. Notre méthode d’inspection de ce type d’objet a été, d’une

part quantitative avec une approche globale et locale, et d’autre part qualitative en utilisant

différents procédés de visualisation.

2. ContributionsNous avons contribué à ce travail dans les domaines suivants :

• Une synthèse bibliographique exhaustive dans les axes de recherche suivants :

- Modélisation 3D (modèles géométriques, modèles vision et modèles déformables).

- Mise en correspondance 3D.

- Reconstruction 3D et Vision Robotique.

- Inspection Visuelle Automatique.

• Elaboration d’un système hybride combinant les réseaux neuromimétiques et la

Transformée de Hough et par conséquent lever une problématique de la vision robotique

en temps réel en décelant les rapports étroits que lient les disciplines de la RDF et l’IA.


124

• Proposition d’une méthode de mise en correspondance générale entre des données 3D et

le modèle CAO associé, qui a l’avantage d’être robuste (tolérant jusqu’à 60% de points

parasites) automatique, et qui fonctionne quelque soit la position initiale des données et du

modèle. Cette méthode générale nécessite uniquement la définition de la distance entre

une entité donnée et une entité modèle.

• Définition du calcul de distance accéléré entre un point et un ensemble de triangles,

utilisant une subdivision de l’espace des triangles en voxels parallélépipédiques.

• Définition du calcul de distance entre un point et une surface NURBS découpée.

• A partir des modèles surfaciques NURBS découpées et triangulées, définition d’une

représentation hiérarchisée du modèle géométrique pour accélérer le calcul de distance

point/modèle.

• Développement d’outils pour l’inspection visuelle automatique d’objets de forme

complexe ou non complexe à partir de points 3D et d’un modèle géométrique.

La stratégie d’inspection que nous avons préconisée a été la suivante :

- Vérification des tolérances globales :

* Tolérances de positionnement et d’orientation de chaque surface,

* Tolérances de forme globale de chaque surface.

- Vérification des tolérances locales

* Tolérance sur la normale,

* Tolérance des courbures.

- Localisation des erreurs de fabrication, mises en évidence par différents procédés de

visualisation : * Segments colorés, * Triangles colorés, * Texture Mapping.

• Comparaison sur une pièce réelle, à partir de données 3D provenant d’une machine à

mesurer et d’un capteur télémétrique, de ces deux procédés d’acquisition.

Les algorithmes présentés dans ce mémoire, programmés en C++, constituent deux

programmes : Un programme de mise en correspondance entre un modèle CAO STL et/ou un

modèle CAO NURBS découpées et un ensemble de points 3D et un programme d’inspection

à partir des points 3D mis en correspondance avec le modèle CAO.

En conclusion, les travaux que nous avons menés nous permettent de dire que :

• La méthode de mise en correspondance que nous avons développée présente une erreur

calculatoire de 0,1 µm. L’erreur qui prédomine est l’erreur de modélisation STL, qu’il


125

convient de minimiser pour obtenir une meilleure précision finale (fonction de l’application

et de l’erreur d’acquisition des points 3D).

• A partir de points 3D provenant d’une machine à mesurer, nous pouvons déceler des

défauts de fabrication de l’ordre du millième de mm. Ils sont du centième de mm, lorsque les

points proviennent d’un capteur télémétrique.

3. PerspectivesLes perspectives de notre travail sont les suivantes :

• L’analyse de la précision des résultats. En particulier, nous pensons qu’il est important

d’avoir des mesures quantitatives sur la qualité de la reconstruction et de s’intéresser au

problème du choix des points pris en compte pour l’autocalibration. Sachant que le problème

discret de l’autocalibration du mouvement consiste à retrouver la translation et la rotation de

la caméra entre deux prises de vues (on suppose que la scène est statique).

• Réduction du temps de calcul de la méthode de mise en correspondance, afin que

celle-ci puisse être raisonnablement intégrée dans un concept manufacturier. L’objectif de

notre travail était avant tout, de démontrer le bon fonctionnement de la méthode que nous

avons proposée, nous avons montré qu’il est possible de diminuer les temps de calcul, mais

n’avons pas eu le temps d’implémenter les solutions.

• Améliorer la stratégie d’inspection.

• Concept de “station d’inspection intégrée” :

Ceci consiste à intégrer ensemble le capteur laser 3D, la base de données CAO et un

calculateur contenant les programmes de mise en correspondance, ainsi qu’un écran

permettant de visualiser graphiquement les erreurs des objets inspectés.

En outre, on peut ajouter que ce travail nous a amené à envisager plusieurs voies à explorer

par la suite, si l’on veut arriver à un produit industriel très fiable.

La première serait de travailler sur des logiciels CAO afin que ceux-ci puissent fournir

automatiquement, avec des données géométriques, les informations de cotation et de

tolérancement.

La deuxième voie serait de travailler sur la précision des capteurs, soit sur la partie matérielle,

soit sur la partie acquisition pour améliorer la précision des Données.

Un modèle fin de cette précision nous permettrait d’associer un facteur de position et


126

d’orientation au faisceau laser afin d’appliquer des facteurs correctifs sur les points acquis.

La dernière voie fournit un challenge qui consiste à convaincre les métrologistes de remettre

en cause les méthodes traditionnelles de contrôle afin de les remplacer par notre approche,

car l’utilisation de ces outils (capteur sans contact, modèle de l’objet) remet en cause les

méthodes traditionnelles de la mesure.

La recherche d’une amélioration des performances des systèmes de production peut être

engagée dans deux directions distinctes : d’une part par le choix d'une technologie et des

moyens de production, et d’autre part par l'organisation, la gestion et la conduite de

l'ensemble industriel. L'importance de cette deuxième direction est accentuée aujourd'hui par

l'exigence de flexibilité de la production pour répondre aux variations rapides de la demande

et à l'incertitude de l'environnement économique. L’organisation d’un système de gestion et

de conduite dépend de l'architecture et de la structure du système de production, mais aussi

du contexte et des objectifs de son exploitation ainsi que du nombre, des compétences et de

l’autonomie des acteurs et décideurs disponibles pour sa conduite. En général les relations

entre ces décideurs et leurs positions hiérarchiques caractérisent l'organisation du système

de conduite.

La superposition d'une structure hiérarchisée et décentralisée est le fondement d'une

organisation de Conduite Décentralisée Coordonnée "CODECO". Elle est formée par un

réseau de décideurs - les centres de décisions - qui sont répartis sur plusieurs niveaux

hiérarchiques. Leurs objectifs et leurs critères d’évaluation, leurs connaissances plus ou

moins étendues et leurs autonomies décisionnelles caractérisent le fonctionnement de chaque

centre mais aussi sa capacité de contribuer à la réalisation des objectives communs.

En descendant dans la hiérarchie de responsabilités et de compétences, un centre coordonne

plusieurs centres du niveau inférieurs en leurs assignant des objectifs à poursuivre. Selon son

autonomie chacun recherche la meilleure réalisation des objectifs assignés, en s’appuyant

aussi sur une coopération avec les centres voisins de même niveau. Cette coopération aide à

surmonter les difficultés passagères et peut aussi corriger une répartition déséquilibrée des

objectifs proposés par le coordinateur.

Ce sont ces difficultés à poursuivre les objectifs assignés à chaque centre, exprimées sous la

forme de distances mesurant les écarts, que le coordinateur doit utiliser pour améliorer ses

connaissances. Ainsi on réalise les objectifs globaux tout en profitant de la connaissance et


127

de l'intelligence répartie dans les centres respectifs du système de conduite. L'autonomie

décisionnelle des centres et leur coopération permet de compenser les perturbations et les

aléas du procédé réel et contribue à la robustesse de la conduite d'un ensemble industriel. Les

pannes ou les changements importants qui ne peuvent pas être compensés par une

coopération sont à reporter au niveau hiérarchique supérieur du coordinateur. Il va alors

comparer et proposer des solutions ou des structures alternatives. La représentation de ces

alternatives par plusieurs modèles poursuivant un même objectif cible est à la base des

centres de décision multiple ou multi-modèle. La structure de ces centres est générique et

ouverte aux divers types de modèles y compris aux bases de connaissances.

La mise en uvre des concepts de la Conduite Décentralisée Coordonnée dépend de la

représentation des connaissances et des modélisations spécifiques du procédé et des

systèmes industriels à conduire. Des outils de modélisation et de résolution algorithmique, de

manipulation des connaissances et d'expertises décisionnelles sont à choisir selon le contexte

réel et les possibilités d'implémentation dans un système d'aide à la décision existant.

Néanmoins les concepts issus de l'automatique et de l'approche systémique sont universels et

pourrait aider dans le développement, la mise en uvre et l'exploitation des systèmes de

gestion et de conduite des procédés industriels. Les premières applications de CODECO ont

concerné des procédés thermiques, chimiques et pétrochimiques suivis par des systèmes

manufacturiers.

Les travaux sur l'organisation et la gestion des ateliers en îlots et la conduite robuste des

ateliers à taches ont ensuite été poursuivis par le pilotage des lignes de production avec prise

en compte des coûts associés aux changements, et enfin par l'organisation et la gestion d’un

système de recyclage et la conduite d'un atelier de désassemblage.

Bibliographie

141

Bibliographie

[Abr 97] Abrams S., Allen P., Tarabanis K. "Computing camera viewpoints in an

active robot work-cell". Columbia University, Department of Computer

Science, New York, USA, 1995. 40p.

[Ach 98] Achour K, Benkhelif M. "3D Reconstruction using four references points

without camera calibrate for a mobile robot". International Conference

on Intelligent Robots and Systems, IROS'98, Victoria, Canada, October

13-17, 1998.

[Ach 02] Achour K., Djekoune O. "Localisation and guidance with an embarked

camera on a mobile robot". Advanced Robotics, (16:1), 2002.

[Ach 04] Achour K., Djekoune O. “Incremental Hough transform: an improved

algorithm for digital device implementation”. Real Time Imaging, Elsevier,

2004.

[Air 94] Airiau R., Gerge JM., Olive V. "Circuit Synthesis with VHDL3". Kluwer

Academic Publishers, 1994.

[Ati 92] Atiquzzaman M. "Multiresolution Hough transforms—an efficient method

of detecting pattern in images". IEEE Transactions on Pattern Analysis and

Machine Intelligence; 14(11):1090–5, 1992.

[Avi 61] Avizienis "Signed-Digit Number Representation for Fast Parallel

Arithmetic". IRE Trans. Electron. Comput. Vol. EC-10, pp. 389-400,

September 1961.

[Aya 84] Ayache N., Faugeras OD. ”A New Method for the Recognition and

Positioning of 2-D objects“. 7th ICPR, Montreal, Canada, pp.1274-1277,

July 1984.

[Aya 85] Ayache N., Faugeras OD., Faverjon B,.Toscani G, "Mise en correspondance

de cartes de profondeur obtenues par stéréoscopie passive“. AFCET, 1985.

[Bal 96] Baluja S. "Evolution of an artificial neural network based autonomous land

vehicle controller". IEEE Transactions on Systems, Man and Cybernetics,

Part B, Vol. 26, No. 3, pp. 450 – 463, June 1996.

Bibliographie

142

[Ban 95] Banta JE., Zhien Y., Wang XE., Zhang G. "A best-next-view, Algorithm for

three dimensional scene reconstruction using range images". In: Casasent,

SPIE 2588, pp. 418-429, 1995.

[Bat 96] Batavia P., Pomerleau D., Thorpe C. "Applying Advanced Learning

Algorithms to ALVINN". Tech. report CMU-RI-TR-96-31, Robotics

Institute, Carnegie Mellon University, October, 1996.

[Ber 88] Bertero M.,. Poggio TA., Torre V. "BI-posed problems in early vision".

Proc. IEEE, Vol. 76, pp. 869-889, August 1988.

[Ber 95] Beraldin JA., El-Hakim SF., Blais F. “Performance evaluation of three

active vision systems built at the NRC”. Proceedings of the Conference on

Optical 3D Measurement Techniques, Vienna, Austria, pp. 352-362,

October 1995.

[Ber 00] Beraldin J.A., Boulanger P., Blais F., Cournoyer L., Domey J., El-Hakim

S.F., Godin G., Rioux M.,Taylor, J. "Real world modeling through high

resolution digital 3D imaging of objects and structures". ISPRS Highlights,

2000.

[Bes 92] Besl PJ., McKay ND. “A method for registration of 3-D shapes”. IEEE

Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2,

February, pp. 239-256,1992.

[Bie 87] Biederman I. “Recognition by components: A theory of human image

understanding”. Psychological Review, Vol. 94, pp. 115-147, 1987.

[Bis 03] Bischof W, Boulanger P. "Spatial Navigation in Virtual Reality

Environments: An EEG Analyis". Journal of Cyberpsycology Behavior,

pp. 487-495, June 2003.

[Boud 05] Boudjemaa F., Djedjiga B., Diaf M. "Identification automatique de

personnes par l’iris de l’oeil utilisant la Transformée de Hough et les filtres

de Gabor". Ciia05, Congrès International en Informatique Appliquée,

Bordj-Bou-Arréridj, 19-21 Novembre, pp. 282-287, 2005.

[Boul 94] Boulanger P. “Extraction multi-échelle d’éléments géométriques”. PhD.

Dissertation: Génie Electrique, Université de Montréal, Canada, 1994.

[Bou 05a] Boutarfa A., Bouguechal N., Abdessemed Y. "An approach to beacons

recognition for a mobile robot using a neural network model". Revue des

Sciences et Technologie B, ISSN 1111-5041, Université de Constantine,

Juin 2005.

Bibliographie

143

[Bou 05b] Boutarfa A. "A New approach to beacons detection for a mobile robot using

a neural network model". RoMoCo’04, Proceedings of the fourth

international workshop on robot motion and control, June 17-20,

Puszczykowo, Poland, pp. 197-202, 2004.

[Bou 06a] Boutarfa A., Bouguechal N., Abdessemed Y., Emptoz H. "Pattern

Recognition with a New Hybrid method on Robotics". WSEAS

Transactions on Computers, Vol.5, No 2, pp. 285-293, ISSN 1109-2750,

February 2006.

[Bou 06b] Boutarfa A., Bouguechal N., Abdessemed Y., Redarce T. "Pattern

Recognition in computer integrated manufacturing". International Journal

of Engineering, Vol.57, No 1, pp. 28-35, ISSN 1335-3632, 2006.

[Cap 98] Caplier A., Luthon F. Dumantier C. "Real time implementations of an

mrf-based motion detection algorithm, special issue on real-time

motion analysis". Journal of real time imaging, Vol. 4, No. 1, pp. 41-54,

February, 1998.

[Cav 01] Cavallaro A, Ebrahimi T., “Video objects extraction based on adaptative

background and statistical change detection”. In SPIE electronics imaging,

San Jose, California, USA, 2001.

[Cha 92] Chaumette F., Bouthemy P., Juvin D. “Mise en correspondance de segments

de droites dans une séquence d'image”. I.N.R.I.A, Rapport de Recherche,

No. 1792, Novembre 1992.

[Che 04] Cheng I., Boulanger P. "Perception of Scale with Distance in 3D

Visualization". Siggraph, Los Angeles, USA, pp. 268-269, August 2004.

[Che 05a] Cheng I., Boulanger P. “Feature Extraction on 3D TexMesh Using Scale-

space Analysis and Perceptual Evaluation”. IEEE Transactions on Circuits

and Systems for Video Technology, Special Issue, October 2005.

[Che 05b] Cheng I., Boulanger P. "Adaptive Online Transmission of 3D TexMesh

Using Scale-space and Visual Perception analysis". IEEE Transactions on

Multimedia, 2005.

[Cho 91] Choudhary AN., Ponnusarry R. "Implementation and evaluation of Hough

transform algorithm on a shared—memory multiprocessor". Journal of

Parallel and Distributed Computing; 12:178–88, 1991.

[Dav 93] Davalo E., Naim P. "Des réseaux de neurones", Eyrolles, 1993.

Bibliographie

144

[Der 87] Deriche R., Cocquerez JP. "Extraction de composantes connexes basée sur

une détection optimale des contours". Actes du congrès MARI-87, pages 1-9,

Tome 2, Paris 1987.

[Derr 00] Derrode S., Mezhoud R., Ghorbel F. "Comparaison de deux familles

complètes de descripteurs de formes pour l'indexation de bases d'objets

à niveaux de gris". Annales des Télécommunications, Vol. 55, No.3-4,

pp. 184-193, Novembre 2000.

[Dje 01] Djekoune O., Achour K., Zoubiri H. "Segments matching using a neural

network approach". ACS/IEEE International conference on computer

systems and applications, AICCSA’ 01, Beirut, Lebanon. pp. 103–105,

June 25–29, 2001.

[Dol 94] Dolenc A. "An Overview of Rapid Prototyping Technologies in

Manufacturing ". Research report, Institute of Industrial Automation,

Helsinki University of Technology, July 1994.

[Dre 04] Dreyfus G et Al. "Réseaux de neurones, méthodologie et applications".

Eyrolles, 2004.

[Dud 72] Duda R.O., Hart PE. "Use of the Hough transformation to detect lines and

curves in pictures". Communication of ACM, 15:11-15, January 1972.

[Dup 01] Dupuis A., Vasseur P., Harp J. "Détection d'objets basée sur une approche

multi-primitives". In ORASIS 2001, Congrès francophone de vision, Cahors,

5-8 juin 2001, pages 223-232, IRIT, 118, route de Narbonne, 31062

Toulouse Cedex 4, France, juin 2001.

[Edi 95] Edinbarough RA., Nainar RA., Radhakrishnan P. "Automated visual

inspection of geometric tolerance in circular component ". International

Journal of Advanced Manufacturing Technology, Vol. 10, No. 6, pp. 367-

373, 1995.

[Eng 03] Grandchamp E., Marthon P. “Driving Segmentation and Recognition Phases

using multiscale characterization”. IGARSS 2003.

[Erc 91] Ercegovac MD. "On- line Arithmetic for Recurrence Problems". SPIE,

Vol. 1556, Adv. Sig. Proc. Alg. Arch. and Imp.II, 1991.

[Fau 86a] Faugeras OD., Hebert M. "The representation, Recognition and Locating of

3D objects". The International Journal of Robotics Research, Vol. 5, No. 3,

pp. 27-52, 1986.

Bibliographie

145

[Fau 86b] Faugeras OD., Toscani G. "Camera Calibration for 3D Computer Vision".

Proceedings of International Workshop on Machine Vision and Machine

Intelligence, Tokyo, 1987.

[Fig 05] Figueroa P., Bischof WF., Boulanger P., Hoover J. "Efficient comparison of

platform alternatives in interactive virtual reality applications". Int. J.

Human-Computer Studies 62, pp. 73–103, 2005.

[Fis 81] Fischler N., Bolles R.C. "Random sample consensus: A paradigm for model

fitting with application to image analysis and automated cartography".

Communication of the ACM, 24(6): pp. 381–395, June 1981.

[Fjo 97] Fjortoft R. “Analyse multi-échelle d’images". SAR: étude bibliographique,

1997.

[Fla 01] Flandin G., Chaumette F. "Fusion d'informations visuelles pour la

localisation d'objets complexes". In ORASIS 2001, Congrès francophone

de vision, Cahors, 5-8 juin 2001, pages 233-242, IRIT, 118, route de

Narbonne, 31062 Toulouse Cedex 4, France, juin 2001.

[Fna 97] Fnaiech F., Sayadi M., Najim M., "Factored and fast algorithms for training

feed forward neural networks". ESST de Tunis, 1997.

[Fre 91] Freeman James A., Skapura D. "Neural Networks". Algorithms,

Applications and programming Techniques. CNS : Computation and Neural

Systems Series, 1991.

[Ger 01] Gerner. “Génération d’un processus de désassemblage et Evaluation du

recyclage d’un produit“. Thèse de Doctorat de l'INP Grenoble, 2001.

[Gia 92] Giacometti A. "Modèles Hybrides de l’Expertise". Thèse de Doctorat en

Informatique et Réseaux, Lab. LIFIA-IMAG, Grenoble / ENST Paris,

France, 1992.

[Gho 92] Ghosh A., Sankar KP. "Neural Network, self organization, an object

extraction", Pattern Recognition Letters, Vol. 13, No. 5, May, 1992.

[God 02] Godin G., Beraldin JA., Taylor J., Cournoyer L., Rioux M., El-Hakim S.,

Baribeau R., Blais F., Boulanger P., Domey J., Picard M. “Active Optical

3D Imaging for Heritage Applications“. IEEE Journal of Computer

Graphics and Applications, Special Issues on Computer Graphics in Art

History and Archeology, pp. 24-36, September 2002.

Bibliographie

146

[Gra 05] Gradinariu M., Datta.A. “A short introduction to Failure Detectors for

Asynchronous Distributed Systems”. ACM Sigact News, Distributed

Computing Column, 36(1):53-70, November 2005.

[Hag 04] Hagras H., CallaghanV., Colley M. “Learning and adaptation of an

intelligent mobile robot navigator operating in unstructured environment

based on a novel online fuzzy-genetic system”. Fuzzy Sets and systems

141, pp. 107-160, 2004.

[Hak 97] El-Hakim SF., Godin G., Beraldin J.A., Boulanger P. "Two 3D sensors for

environment modeling and virtual reality: calibration and multi-view

registration". ISPRS Highlights, 2(1): 13-21; 1997.

[Hat 04] Hatzilygeroudis I., Prentzas J. "Neuro-symbolic approach for knowledge

representation in expert system". IJHIS, International Journal of Hybrid

Intelligent Systems, Vol. 1, No. 3-4, pp. 111-126, 2004.

[Her 94] Herault J., Jutten C. "Réseaux neuronaux et traitement du signal". Hermès,

1994.

[Hop 82] Hopfield J. "Neural networks and physical systems with emergent

collective computational abilities". Proc. Nat. Acad. Science, Vol. 79,

pp. 2554-2558, April 1982.

[Hop 85] Hopfield J., Tank D. W. "Neural computation of decisions in optimization

problems". Biol. Cyber, Vol. 52, pp. 141-152, 1985.

[Hou 62] Hough PVC. "Methods and Means for Recognizing Complex Patterns".

No.3, December 1962.

[Jod 94a] Jadouin JF. "Les réseaux de neurones : Principes et définitions". Hermès,

1994.

[Jod 94b] Jadouin JF. "Les réseaux neuromimétiques : Modèles et Applications".

Hermès, 1994.

[Kit 88] Kitter J., Illing J. "A survey of the Hough Transform". In computing Vision,

Graphics and Image Processing 44: (1), pp. 87-116, 1988.

[Koh 88] Kohonen T. "An introduction to neural networks", Neural Networks 1, 3-16,

1988.

[Kos 91] Koshimizu H., Numada M. “FIHT2 algorithm: a fast incremental Hough

transform”. IEICE Transactions; E74 (10), 1991.

Bibliographie

147

[Kov 98] Kovacis S., Leonardis A., Pernus F. "Planning sequences of views for 3D

objects recognition and pose determination". Pattern Recognition, Vol.31,

No.10, pp. 1407-1417, October, 1998.

[Kun 78] Kung SY., Leiserson CE. "Systolic Array for VLSI". Chapter 8.3, 1978.

[Lan 01] Landrieu A. “Logistique inverse et collecte de produits techniques en fin de

vie -Tournée de véhicules avec contraintes“. Thèse de Doctorat de l'INP

Grenoble, 2001.

[Lau 96] M. Laumy, M. Dhome., Lapresté JT. "Segments matching : Comparison

between a neural approach and a classical optimization way". IEEE,

Proceedings of ICPR' 96, pp. 261-265, 1996.

[Lot 94] Lotufo RA., Dagless EL., Milford DJ., Morgan AD., Morrissey JF. "Hough

Transform for transporters arrays". In: Proceedings of the third international

conference on image processing and its applications, IEEE proceedings,

London, pp. 122–33, 1994.

[Mar 97] Marion A. "Acquisition et Visualisation des Images". Eyrolles, 1997.

[Marr 76] Marr D., Poggio T. "Cooperative computation of stereo disparity". Science,

Vol. 194, pp. 283-287, 1976.

[Mas 95] Mason SO., Grun A. "Automatic Sensor Placement for Accurate

Dimensional Inspection". Computer Vision and Image Understanding,

Vol. 61, No.3, pp. 454-467, 1995.

[Masu 95] Masuda T., Yokoya N. "A robust method for registration and segmentation

of multiple range images". Computer Vision and Image Understanding,

Vol. 61, No.3, pp. 295-307, 1995.

[Mav 95] Maver J. "Collecting visual information using an active sensor system".

Ph.D. Dissertation : Department of Computer and Information Science,

University of Ljubljana, Slovenia, 1995, 115p.

[Mcc 81] McClelland JL., Rumelhart DE. "An interactive activation model of context

effects in letter perception". Psychological Review, Vol. 88, pp.375-407,

1981.

[Med 85] Medioni G., Nevatia R. “Segment-Based Stereo Matching ”. Computer

Vision, Graphics and Image Processing, No.31, pp 2-18, 1985.

[Mil 93] Millgram M. “Reconnaissance des Formes: Méthodes Numériques et

Connexionnistes“. Edition Armand Collin, 1993.

Bibliographie

148

[Mog 96] Moganti M., Ercal F., Dagli CH., Tsunekawa S. "Automatic PCB

inspection Algorithms: a survey". Computer Vision and Image

Understanding, Vol. 63, No. 2, pp. 287-313, 1996.

[Mor 96] Moron V., Boulanger P., Redarce HT, Jutard A. “3D range data/CAD

model comparison: industrial parts conformity verification”. In First

International Conference on Integrated Design and Manufacturing in

Mechanical Engineering, IDMME’96, pp.1023-1032, Nantes, France,

15-17 April, 1996.

[Mur 95] Murgai R., Brayton R., Sangiovanni-Vincentelli A. "Logic Synthesis for

Field Programmable Gate Array". Kluwer Academic Publishers, 1995.

[Nas 91] Nasrabadi NM., Li W. "Object recognition by a Hopfield neural network".

IEEE Trans. Syst. Man, Cybernetic, Vol. 21, 1991.

[Nas 92] Nasrabadi NM., Choo Chang Y. "Hopfield network for stereo vision

correspondence". IEEE Trans. On Neural Networks, Vol. 3, No.1, pp. 5-12,

January,1992.

[Nek 95] Nekovei Resa., Sun Ying. "Back-propagation network audits configuration

for blood vessel detection in angiograms". IEEE Transactions on neural

networks. Vol. 6, No. 1, January 1995.

[New 95a] Newman TS., Jain AK. “A survey of automated visual inspection”.

Computer Vision and Image Understanding, 61(2), pp.231-262, March 1995.

[New 95b] Newman TS., Jain AK. “A system for 3D CAD based inspection using

range images “. Pattern recognition, 28(10), pp.1555-1574, March 1995.

[Nob 95] Noble JA. "From inspection to process understanding and monitoring : a

view on computer vision in manufacturing". Image and Vision Computing,

Vol.13, No.3, pp. 197-214, April, 1995.

[Off 85] Offen RJ. "VLSI Image processing". In Mc Graw Hill Book Company New

York, St Louis, San Francisco, pp. 65-68, 1985.

[Ors 95] Orsier B. "Etude et Applications des Systèmes Hybrides Neuro-

Symboliques". Thèse de Doctorat en Informatique, Lab. LIFIA-IMAG,

UJF-Grenoble, France, 1995.

[Oso 98] Osorio F. "INSS, un système hybride neuro-symbolique pour

l’apprentissage automatique constructif". Thèse de Doctorat en Informatique,

Lab. LEIBNIZ-IMAG, INPG-Grenoble, France, 1998.

Bibliographie

149

[Oso 05] Osorio G., Boulanger P., Prieto F. "An Experimental Comparison of a

Hierarchical Range Image Segmentation Algorithm". 18th Canadian

Conference on Artificial Intelligence Graphics Interface in Victoria BC,

pp. 571-578, May 8-11, 2005.

[Pah 95] Pahk HJ., Jung MY., Hwang SW., Kim YH., Hong YS., Kim SG.

"Integrated precision inspection system for manufacturing moulds having

defined features". International Journal of Advanced Manufacturing

Technology, Vol. 10, No. 3, pp. 198-207, 1995.

[Pal 99] Paletta E., Pinz A. "Visual object detection for autonomous sewer robots".

IROS'99, Proc. IEEE/RSJ, International Conference on Intelligent

Robots and automated Systems, Kyougju, South Korea, pp. 1087-1093,

October 17-21,1999.

[Pap 97a] Papadopoulos-Orfanos D. “Numérisation géométrique automatique à l’aide

d’un capteur de précision à profondeur de champ réduite”. Ecole Nationale

Supérieure des Télécommunications, ENST, 1997, 135p.

[Pap 97b] Papadopoulos-Orfanos D., Schmitt F. “Automatic 3D digitization using a

laser range finder with a small field of view”. Proceedings of the

International Conference on Recent Advanced in 3D Digital Imaging and

Modelling, pp. 60–67, Ottawa, Canada, 1997.

[Pass 04] Passold F., Stemmer M.R. "Feedback error learning neural network applied

to a Scara robot''. RoMoCo’04, Proceedings of the fourth international

workshop on robot motion and control, June 17-20, Puszczykowo, Poland,

pp. 197 – 202, 2004.

[Per 03] Personnaz L., Rivals I. "Réseaux de neurones formels pour la modélisation,

la commande et la classification". CNRS éditions, collection Sciences et

Techniques de l’Ingénieur, 2003.

[Phi 94] Philip KP., Dove EL., McPherson DD., Gotteiner NL., Stanford W.,

Chandran KB. "The fuzzy Hough transforms feature extraction in medical

images". IEEE Transactions on Medical Imaging; 13(2):235–40, 1994.

[Pit 96] Pito R. “A sensor based solution to the next view problem”. 13th

International Conference on Pattern Recognition, pp.941-945, Vienna,

Austria, 25-30 August, 1996.

Bibliographie

150

[Pit 97] Pito R. “Automated surface acquisition using range cameras”. Ph.D.

Dissertation: Computer Information Science, University of Pennsylvania,

GRASP Laboratory, USA, 1997.

[Pra 85] Prazdny K. "Detection of binocular disparity", Biol. Cybernetic. Vol.52,

pp. 93-99, 1985.

[Pri 98] Prieto F., Boulanger P., Redarce H.T., Lepage R. "Visual System for Fast

and Automated Inspection of 3D Parts". International Journal of

CAD/CAM and Computer Graphic, Vol. 13, no 4, pp. 211-227, 1998.

[Pri 99] Prieto F., Redarce HT., Lepage R., Boulanger P. “A non contact CAD based

inspection system“. In Quality Control by Artificial Vision, Trois Rivières,

Canada, Québec, pp. 133–138, 18-21 May 1999.

[Pri 02a] Prieto F., Redarce HT., Lepage R., Boulanger P. “An automated Inspection

System”. International Journal of Advanced Manufacturing Technology, 19:

pp.917-925, 2002.

[Pri 02b] Prieto F., Boulanger P., Lepage R., Redarce HT. “Automated Inspection

System Using Range Data“. In Proceedings of 2002, IEEE International

Conference on Robotics & Automation, ICRA’02, Washington-DC, USA,

pp. 2557-2562, May 11-15, 2002.

[Pri 03a] Prieto F., Boulanger P., Redarce HT., Lepage R. "Control de tolerencia

geométricas usando imagen 3D". Journal Energia y Computacion, Vol X,

No. 1, 29-39, 2003.

[Pri 03b] Prieto F., Lepage R., Boulanger P., and Redarce HT. “A CAD-based 3D

data acquisition strategy for inspection“. Machine Vision & Applications

Journal, Vol. 15, No. 2, pp. 76-91, December 2003.

[Pri 04] Prieto F., Boulanger P. " Inspeccion no Determinista de Partes Usando im

Genes 3D de Alta Precision". Paper published in the Revista Dyna of the

Faculty of Mines, No. 142, pp. 77-84, July-2004.

[Red 00] Redarce HT., Prieto P., Boulanger P., Lepage R. "Accuracy improvement of

contactless sensor for dimensional inspection of industrial parts".

International Journal of CAD/CAM and Computer Graphics, Vol. 15,

pp. 345-366, December 2000.

[Rem 05] Remazeilles A., Chaumette F., Gros F. "Image based robot navigation in 3D

environments". In Int. Symp. On Optomechatronic Technologies, ISOT'05,

Décembre 2005.

Bibliographie

151

[Rio 97] Rioux M. “Laser range finder based on synchronized scanners”. In SPIE

Milestone Series, Optical Techniques for Industrial Inspection, pp 142-149,

Bellinghan, USA, 1997.

[Ris 89] Risse T. "Hough Transform for Line Recognition". Computer Vision and

Image Processing, Vol. 46, pp. 327-345, 1989.

[Rob 86] Robert A. ”Perception et modélisation de l’environnement d’un robot

mobile : Une approche par stéréovision”. Thèse de Doctorat au L.A.A.S,

Grenoble, Novembre 1986.

[Roj 96] Rojas R. "Neural Network". Springer, 1996.

[Ros 69] Rosenfield A. "Picture Processing by Computer". Academic, New York,

1969.

[Roy 95] Roy U. "Computational methodologies for evaluating form and positional

tolerances in a computer integrated manufacturing system". International

Journal of Advanced Manufacturing Technology, pp. 110-117, 1995.

[Rui 95] Ruichek Y., Postaire JG., Macaire L., Burie J-C. "Implantation neuronale

pour la mise en correspondance de primitives en stéréovision linéaire". Proc.

Intern. AMSE Confer. Communications, Signals & Systems, Rabat, Maroc,

Vol. 2, pp. 574-582, Octobre 9-11,1995.

[Rum 86] Rumelhart D.E., J.L. McClelland and PDP Research group, "Parallel

Distributed Processing". Explorations in the Microstructure of recognition,

Vol. 1, MIT Press, Cambridge, 1986.

[Sie 04] Siemieniak M. "Working time losses in production lines with hybrid

automation case–study''. RoMoCo’04, Proceedings of the fourth

international workshop on robot motion and control, June 17-20,

Puszczykowo, Poland, pp. 293 – 297, 2004.

[Shu 00] Shu C., Boulanger P. “Triangulating NURBS Surfaces, Curve and Surface

Design”. Vanderbilt University Press, Nashville, Tennessee, pp. 381—388,

2000.

[Son 99] Qing Song., Xiao Jizhong., Chai Soh Yeng. "Robust back propagation

training algorithm for multilayered neural tracking controller". IEEE

Transactions on Robotics and Automation, Vol. 10, No.5, September 1999.

[Sou 06] Souici-Meslati L., Sellami M. "A hybrid neuro-symbolic approach for arabic

handwritten word recognition". JACIII, Journal of Advanced Computational

Intelligence and Intelligent Informatics, Vol. 10, No.1, 2006.

Bibliographie

152

[Sun 97] Sun R. "An introduction to hybrid connectionist-symbolic models". In: Sun

R. & Alexander F. (Eds). Connectionist-Symbolic Integration: From Unified

to Hybrid Approaches. Chapter 1, Lawrence Erlbaum Associates, 1997.

[Tag 01] Tagzout S., Achour K., Djekoune O. "Hough transform for FPGA

implementation".Elsevier Journal, Signal Processing; 81(6):1295–301, 2001.

[Tan 95] Tang XQ., Davies BJ. "Integration of inspection planning system of CMM

via DMIS". International Journal of Advanced Manufacturing Technology,

Vol. 10, No. 6, pp. 422-426, 1995.

[Tar 95a] Tarabanis KA., Allen PK., Tsai RY. “A survey of sensor planning in

computer vision”. IEEE Transactions on Robotics and Automation, Vol. 11,

No. 1, pp.86-104, February, 1995.

[Tar 95b] Tarabanis KA., Tsai RY., Allen PK. "The MVP sensor planning system for

robotic vision tasks". IEEE Transactions on Robotics and Automation,

Vol. 11, No 1, pp. 72-85, February, 1995.

[Tar 95c] Tarbox GH., Gottschlich SN. "IVIS: An integrated volumetric inspection

system". Computer Vision and Image Understanding, 61(3): pp. 430-444,

May 1995.

[Tar 95d] Tarbox GH., Gottschlich SN. "Planning for complete sensor coverage in

inspection". Computer Vision and Image Understanding, 61(1), pp. 84-111,

January, 1995.

[Tru 97] Trucco E., Umasuthan M., Wallace AM., Roberto V. “Model-based

planning of optimal sensor placements for inspection”. IEEE Transactions

on Robotics and Automation, 13(2), pp.182–194, April 1997.

[Tuy 03] Tuytelaars T., Van Gool L. "Matching widely separated views based on

affinity invariant neighbourhoods". International Journal on Computer

Vision, July, 2003.

[Tzv 91] Tzvi Ben., Sandler M. "Analogue Implementation of the Hough Transform".

In. IEEE Proceeding-G, Vol. 138, No. 4, August 1991.

[Wha 91] Whaite P., Ferrie F. "From uncertainty to visual exploration". IEEE

Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 10,

pp.1038-1049, October, 1991.

[Wha 97] Whaite P., Ferrie F. "Autonomous exploration : driven by uncertainty".

IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19,

No. 3, pp.193-205, March, 1997.

Bibliographie

153

[Xil 98] Xilinx. "Synthesis and simulation Design Guide". Xilinx INC, USA.1998.

[Xil 02a] Xilinx. "VirtexTM -II Platform FPGAs: Introduction and Overview". advance

product specification, DS031-1, Vol. 9, September 26, 2002.

[Xil 02b] Xilinx. "Tutorial ISE Foundation". Lilian Boussuet, September 2002.

[Ye 95] Ye Y. "Sensor planning for 3D object search". In: IEEE International

Symposium for Computer Vision, Florida, USA, pp. 539-544,

November 1995.

[Ye 99] Ye Y., Tsotsos JK. "Where to look next in 3D object search". Computer

Vision and Image Understanding, Vol.73, No.2, pp. 145-168, February 1999.

[You 97] Young S., Scott P., Nasrabadi NM. "Object recognition multilayer Hopfield

Neural Network". IEEE Transations on image processing, Vol. 6, No. 3,

Marsh 1997.

[Zaa 00] Zaatri A., Tuytelaars T., Waarsing R., Van Brussel H., Gool L. "Supervised

intelligent function". In: Proceedings of IEEE, Conference on Robotics and

Automation, ICRA, pp. 3707–3712, 2000.

[Zha 97] Zha H., Morooka K., Hazegaya T., Nagata T. "Active modelling of 3D

objects : planning on the next best pose NPB for acquiring range images.

In: Computer Society Press, Proceedings of the International Conference on

Recent Advanced in 3D Digital Imaging and Modelling, Ottawa, Canada,

pp. 68-75, May 12-15, 1997.

[Zho 88] Zhou YT., Chellapa R., Vaid A., Jenkius BK. "Image restoration using a

neural network". IEEE Trans. Acoustic., Speech, Signal Processing, Vol. 36,

No. 7, July 1988.

[Zho 89] Zhou YT., Chellapa R. "Neural network algorithms for motion stereo". Proc.

IEEE Int. Joint. Conference on Neural Networks, Vol. 2, pp. 251-258.

June 1989.

[Zho 03] Zhong X, Liu P., Georganas N., Boulanger P. "Designing a vision based

collaborative augmented reality application for industrial training".

Informationtechnik und Technische Informatik, Oldnburg, Verlag, Inaugural

Issue. Invited Paper, pp. 7-18, January 2003.

Annexes

128

ANNEXE A

Conception des pièces

Afin de tester le système d’inspection nous avons conçu et usiné une banque de pièces

avec des surfaces simples et complexes. Nous avons introduit des côtes (tolérances

dimensionnelles) et des tolérances géométriques sur l’ensemble des pièces. Après le

tolérancement des pièces elles ont été dessinées à l’aide du logiciel Pro-Engineer. Après la

conception des pièces elles ont été toutes usinées. Le matériau utilisé a été l’aluminium car

malléable et facile a usiné. Les pièces avec des surfaces régulières ont été usinées à l’aide

d’un tour et d’une fraiseuse à commande numérique. Pour les pièces avec des surfaces

complexes, nous avons utilisé un logiciel permettant de commander la fraiseuse numérique

à partir du modèle CAO en format IGES.

En général toutes les pièces ont des dimensions comprises dans un volume 100mm x

100mm x 100mm. Pour chaque pièce de la Banque de pièces, nous avons obtenu en

utilisant le logiciel de CAO, deux modèles CAO différents.

• Le Modèle Triangulé (Format STL).

• Le Modèle Exact (Format NURBS).

1. Format STLIl représente la pièce par un ensemble de triangles approchant les surfaces. La préc ision

de représentation de la pièce est fonction du nombre des triangles utilisés. Le modèle STL

est alors constitué d’une liste de triangles définis par leurs trois sommets ainsi que par leur

normale orientée vers l’extérieur (figure A.1).

Annexes

129

La surface d’un objet peut aussi être représentée par un ensemble de triangles planaires

dont la tessélation respecte les règles de la triangulation STL dédiée à la stéréo-

lithographie [Dol 94].

Figure A.1. Modèle STL en représentation filaire

• Exemple de Triangulation STL

A partir de l'objet Cylindre défini en CAO, nous effectuons plusieurs conversions en

modèle STL, avec différentes valeurs d’approximation. Nous obtenons des modèles du

type de celui de la figure A.2 avec plus ou moins de triangles.

Figure A.2. Exemple de Triangulation STL

Annexes

130

Ci dessous, on peut constater l'évolution du nombre de triangles STL en fonction de

l'erreur maximale d’approximation souhaitée :

Erreurd’approximation

(mm)

Nombrede triangles

0.0005

0.001

0.005

0.01

0.05

0.1

0.5

1

2

8450

6854

4232

3026

1882

634

392

316

264

Tableau A.1. Nombre de triangles STL

en fonction de l'erreur d'interpolation souhaitée

D’un point de vue global, le nombre de triangles STL augmente lorsque l’erreur

d’approximation diminue, surtout dans les zones de faible courbure de surface.

Compte tenu des règles de modélisation STL à respecter, pour des erreurs

d’approximation proches, cette règle n’est pas toujours vérifiée (tableau A 1), ceci

s’explique par une réorganisation totale des triangles.

2. Format IGES (Modèle géométrique NURBS)Il représente les surfaces d’une pièce de façon exacte car il utilise pour la représentation

de la pièce des surfaces NURBS (Non Uniform Rational B-Spline). Le format IGES

(Initial Graphics Exchange Specification) est souvent utilisé grâce à sa grande capacité

descriptive et l’exactitude de représentation. L’utilisation de cette spécification permet

l’échange compatible de données entre divers systèmes de la CFAO. En effet, une sphère,

un plan, une ellipsoïde peuvent être représentées par une seule surface NURBS. Quand aux

objets complexes, ils peuvent être modélisés par un assemblage de plusieurs surfaces

NURBS découpées qui délimitent un volume fermé exact (figure A.2).

Annexes

131

Figure A.3. Modèle NURBS

• Exemple de Surface NURBS

Afin de mieux décrire les surfaces de l'objet modélisé, surtout au niveau des

raccordements de leurs surfaces ou des perçages, sans augmenter le degré des surfaces ou

le nombre de leurs paramètres, les surfaces NURBS sont découpées par des courbes de

découpe intérieures ou extérieures plus ou moins complexes (figure A.4).

Figure A.4. Surface NURBS découpée (haut), courbes de découpe (bas)

Annexes

132

3. Système d’acquisition des images 3DLe système d'acquisition 3D utilisé [Rioux 97] consiste en un système à triangulation

laser (figure A.5). Les performances de ce système sont optimisées par l'utilisation d'une

technique de synchronisation utilisant un galvanomètre à miroir, telle que la projection du

faisceau laser et sa détection s'effectuent de façon synchrone. Une particularité du système

est d'utiliser un miroir recouvert sur ses deux faces d'une couche réflectrice, la première

étant utilisée pour la projection du laser sur la scène, tandis que la deuxième assure la

synchronisation de la détection. Bien qu'une lumière incohérente puisse être utilisée pour la

projection, il est préférable de se servir d'une source laser afin de bénéficier de la très

grande profondeur de champ procurée par la cohérence spatiale.

Figure A.5. Système de mesure 3D utilisant la triangulation et l'auto-synchronisation

Nous avons utilisé dans cette étude un capteur commercialisé par la société Hymarc Ltd

(Hyscan-45c) disposant de la technologie développée au CNRS, d'une résolution de +/- 25

m pour une profondeur de champ de 100 mm, d'une largeur de balayage de 70 mm et

d'une vitesse d'acquisition de 20 000 points/s. Le fichier d'informations fourni par le

système d'acquisition contient l'ensemble de points numérisés non-ordonnés, ainsi que leur

intensité respective, et d'éventuelles informations de couleur.

A partir des informations géométriques et des intensités d'une image 3D, la scène peut

être reconstruite et visualiser en 3D à l'aide d'un éclairage artificiel (figure A.6).

Annexes

133

Figure A.6. Images reconstruites à partir des informations géométriques et d'intensité

d'objets numérisés

Des informations géométriques de l'image 3D de la figure A.6, on peut séparer celles

concernant les deux objets d'intérêt (figure A.7) du fond de l'image.

Figure A.7. Informations géométriques extraites

pour chaque objet de l'image 3D de la figure A.5

Annexes

134

ANNEXE B

Mobile Robot ATRV

1. Mobile Robot SpecificationsLength 105 cm , Width 80 cm , Height 65 cm, Clearance 7 ½ cm, Weight: 118 kg

Body Formed and welded aluminium

Speed 0 – 1.5 m/sec

Payload 100 kg

Run Time 4 to 6 hours, terrain dependent

Drive 4-wheel, PWM

Steering Skid Steering

Turn Radius Zero (turns on center)

Tires 31.75 cm pneumatic knobby

Batteries 4, 24V, 672 Watt/hr

Aux. Voltages Reg. +5, +12, & system battery voltage of 18–27V

2. Aux. Power PortsMotion Control IROBOT rFLEX System

Motors 2 high torque, 24V DC servo motors

Computer Single or dual Pentium lV computer

Software IROBOT Mobility Robot Infrastructure

I/O Ports Ethernet, RS-232, Joystick

Sensors Sonar: 12 (6 front, 2 each side, 2 rear)

Safety Motor enable key switch plus four emergencies kill buttons

Annexes

135

Figure B.1. ATRV Mobile Robot On Packing Crate, Rear View

Figure B.2. ATRV Mobile Robot Side View

3. AccessoriesChoice of Pentium-IV® Computer Systems

PR Triclops 3D Vision System

High performance vision system

Computerized pan-tilt unit

Camera and frame grabber options

Wireless communication (1-3 Mb/s Ethernet)

Integrated SICK proximity laser scanner

Annexes

136

ASCII-to-speech interface

Computerized navigation compass

Global Positioning System (GPS) receiver

Digital Global Positioning System (DGPS) receiver

Inertial sensors

Tactile sensing bumpers

PTZ (Pan-tilt-zoom) camera

Absolute Position Sensor

6-Axis Inertial Sensor

(a)

(b)

Figure B.3. Robot mobile utilisant la stéréovision

(a) à l’arrêt et (b) en déplacement

Annexes

137

ANNEXE C

1. L'impact des NTIC en vision industrielle

Les Nouvelles Technologies de l'Information et de la Communication s'immiscent

chaque jour davantage au c ur du monde industriel. A la vitesse modérée de notre

compréhension progressive des opportunités offertes par ces technologies, mais

inexorablement, cette révolution fluidifie les échanges d'informations. Entre hommes, entre

métiers, entre machines, entre hommes et machines, sur toute la planète. Cette révolution

en marche restera probablement la principale matrice des technologies de demain. On

s'intéresse ici spécifiquement à l'impact des NTIC sur les divers aspects de l'interface

homme-machine en vision industrielle, qu'il s'agisse de systèmes en ligne ou en bord de

ligne. On peut montrer sur des exemples concrets de quelle façon les NTIC modifient en

profondeur :

• La programmation des gammes de mesure (ou programmation pièces).

• Les opérations de maintenance préventive (réglages et vérifications périodiques).

• L’exploitation des résultats en local et à distance.

2. Le Programme de Contrôle Automatisé

Jusqu'à la déferlante des NTIC, les méthodes disponibles pour automatiser étaient

principalement, de la plus rigide à la plus souple :

a. Duplication. "Recopie un programme existant et modifie-le".

b. Interface graphique/dialogues paramétrables/menus.

c. µ- Langages de programmation, de plus ou moins haut niveau.

Depuis une quinzaine d'années, l'interface graphique est devenue la règle sur les PC, et

de fait ce modèle d'interface est très séduisant au départ. Son slogan, c'est "aucune

programmation n'est nécessaire pour automatiser, donc aucune compétence spécifique

n’est requise. Mais l'interface graphique rencontre ses limites dès que l'on sort de ce que le

Annexes

138

concepteur du programme a exactement prévu, et s'adapte mal à la complexité (syndrome

des "menus à tiroirs"). D'autre part, elle requiert en réalité une formation et une certaine

habitude de l'utilisateur, car il doit savoir où se cache telle ou telle fonction pour pouvoir

l'exploiter (syndrome des "logiciels exploités à moins de 5% de leur potentiel").Quant aux

langages de programmation, ils permettent au contraire une extensibilité infinie, mais ils

sont fermés aux non professionnels (syndrome de la "page blanche"). Face à cette

problématique, les NTIC ouvrent une voie nouvelle en permettant à l'utilisateur non

informaticien de réaliser son programme:

• De façon naturelle et sans risque d'erreur.

• Sans formation: aucune autre instruction à retenir que "Lancer l'aide au moyen du

menu Aide".

• Dans l'environnement familier de son navigateur Web.

• Et surtout sans aucune difficulté, même si le problème est complexe.

De cette façon, l'utilisateur n'a pas plus de mal à programmer sa gamme qu'à commander

un livre, et on proposent de le montrer ci-dessous sur un exemple concret et largement

illustré : la programmation d'une gamme de mesure par vision en vue d'un contrôle par

prélèvement.

a. Au départ, l'utilisateur dispose d'un exemplaire de la pièce, dont il veut automatiser le

contrôle. Il connaît les critères à contrôler, et il sait qu'il doit dérouler le menu Aide

pour tout projet sur sa machine de vision. Il remplit dès lors les conditions

nécessaires et suffisantes pour mener à bien ce travail.

b. Il va naviguer pas à pas d'instruction en instruction dans l'ordre requis par la

procédure. Chaque instruction est simple. A chaque étape, il va trouver toutes les

explications -et les éventuelles mises en garde- dont il a besoin pour réaliser son

travail sans erreur. Il sera guidé ensuite vers l'étape suivante, tout naturellement.

c. L'interface graphique, menu ou dialogue n'est pas proscrit. Simplement l'interface

devient "contextuelle". Elle ne concerne que l'étape en cours, et n'est donc pas

inutilement encombrée de toute la complexité du logiciel dans son ensemble. C'est

bien là qu'est sa place, c'est bien à ce stade qu'elle est utile, notamment pour les

débutants ou les utilisateurs occasionnels.

Annexes

139

Figure C.1. Guide de programmation PPM

Annexes

140

3. La Maintenance PréventiveLa maintenance préventive comporte souvent des réglages et des vérifications

périodiques, qui du fait de leur rareté supposent une organisation relativement coûteuse

(formation à chaque machine, gestion centralisée) -ou à l'inverse une désorganisation tout

aussi coûteuse. Là encore on comprend bien ce qu'apportent les NTIC, tant pour alerter

automatiquement sur la nécessité imminente d'une opération périodique, que pour

interfacer cette opération périodique elle-même, de A à Z. De ce fait, les NTIC vont

permettre de belles économies de formation, d'oublis et d'erreurs. Non seulement

l'opérateur de maintenance sera informé en temps utile des actions qu'il aura à mener, mais

en outre les opérations délicates ou répétitives peuvent -dans la même optique de sécurité

et de simplicité maximum- s'effectuer directement par l'intermédiaire de l'aide html,

comme dans l’exemple ci-dessous.

4. L’exploitation des RésultatsPar l'intermédiaire de l'aide html, l'utilisateur peut, on l'a vu et c'est essentiel, réaliser un

protocole complexe. Mais il peut aussi réaliser beaucoup d'autres opérations. Ainsi le

responsable du contrôle, depuis son propre ordinateur et en utilisant uniquement son

navigateur Web, consulte en toute sécurité les archives de résultats de tous les contrôles

effectués. Il peut ensuite, toujours via son navigateur html, sélectionner ou générer

dynamiquement les rapports de contrôle ou de capabilité, ou les courbes représentatives de

l'évolution de la qualité de la production. La machine de vision embarque un serveur Web,

ce qui est aujourd'hui banal : les informations ne sont plus prisonnières de la machine de

vision, elles sont accessibles dans les mêmes conditions depuis n'importe quel autre PC

muni d'un accès Internet et d'un navigateur Web. On l'aura compris, toutes ces facilités

modifient en profondeur le suivi de la qualité de production. L'exploitation des résultats

devient parfaitement simple et naturelle, et cela depuis n'importe quelle machine dans

l'usine, ou même depuis un site distant. Ça n'est plus qu'une question de choix, il n'y a

aucun obstacle technique, ni aucune infrastructure matérielle ou logicielle à installer

préalablement.

Résumé

La problématique générale de cette recherche est l’extraction de caractéristiquesd’ensembles cohérents de primitives diverses, ainsi que la représentation adéquate de cesensembles. En robotique mobile et particulièrement en stéréovision, le calcul d’orientationdes primitives est une donnée importante dans le processus de modélisation du milieu dansdes tâches de localisation et de navigation, notre robot mobile évoluant dans unenvironnement de bureau où d’atelier. L'objectif est de fournir des informations suffisammentpertinentes et concises afin de faciliter les traitements ultérieurs notamment pour lareconnaissance d’objets. Deux aspects complémentaires sont explorés, d’une part parl’extraction et la représentation des attributs en vue d’une reconnaissance des formes etd’autre part par une application en productique basée sur le contrôle automatique de piècesmanufacturées. En effet, en amont nous proposons un système hybride de reconnaissancede formes 3D moyennant une approche neuromimétique associant la Transformée deHough. Des tests valident notre approche. En aval, cette méthode porte sur une applicationen productique qui est l’inspection automatique d’objets comportant des surfaces complexesà partir de leur modèle CAO et de données 3D provenant, soit d’un capteur télémétrique, soitd’une machine à mesurer.

Mots Clés:Vision, Robotique mobile, Reconnaissance des formes, Réseaux de neurones,Transformée de Hough, Segmentation, Appariement, Extraction de primitives,Optimisation, Contrôle dimensionnel , Inspection.

Abstract

The research problems are the extraction of characteristics of coherent sets of variousprimitives, as well as the adequate representation of these sets. In mobile robotics andparticularly in stereovision, the calculation of orientation of the primitives is significant data inthe process of modelling of the medium in tasks of localization and navigation, our mobilerobot evolving/moving in an environment of office where of workshop. The objective is toprovide sufficiently relevant and concise information in order to facilitate the secondaryprocessing in particular for the recognition of objects. Two complementary aspects areexplored, on the one hand by the extraction and the representation of the attributes forpattern recognition and on the other hand by an application in computer-integratedmanufacturing based on the automatic check of manufactured parts. Indeed, upstream wepropose a hybrid system of pattern recognition 3D with the help of a neuromimetic approachassociating the Transform of Hough. Tests validate the approach. In downstream, thismethod relates to an application in computer-integrated manufacturing which is the automaticinspection of objects comprising complex surfaces starting from their model CAD and datacoming 3D, either of a telemetric sensor, or of a measuring machine.

Keys words:Robotic vision system, Pattern recognition, Neural networks, Hough Transform,Signal processing, Segments matching, Primitives extraction, Optimization,Dimensional control, Inspection.

,

. ,

.

HOUGH.

CAO"."

Documents

THESE - seborga1.free.frseborga1.free.fr/TIPE/Autres/these.pdf · Département d’Electronique Faculté des Sciences de l’Ingénieur Université de Batna Pour l’obtention du