pour obtenir le grade de

Joan Solà

Description

Niveau: Supérieur, Doctorat, Bac+8
École Doctorale Systèmes Thèse pour obtenir le grade de Docteur de l'Institut National Politechnique de Toulouse Spécialité: Systèmes Automatiques présentée et soutenue publiquement le 2 février 2007 Towards Visual Localization, Mapping and Moving Objects Tracking by a Mobile Robot: a Geometric and Probabilistic Approach Joan Solà Ortega Préparée au Laboratoire d'Analyse et d'Architecture de Systèmes du CNRS sous la direction de M. André Monin et M. Michel Devy Jury M. Jean-Yves Fourniols Président M. Andrew Davison Rapporteur M. Patrick Rives Rapporteur M. Raja Chatila Examinateur M. Gérard Favier Examinateur M. Alberto Sanfeliu Examinateur M. André Monin Directeur de Thèse M. Michel Devy Codirecteur de Thèse

• basic feature-based


• extended kalman


• exactly-sparse extended


• detection mechanisms


• scalable slam algorithms


• filter


• camera slam


• feature detection

Sujets

• Favier
• Davison
• Sanfeliu
• Filter

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 février 2007
• Nombre de lectures: 58
• Langue: Français
• Poids de l'ouvrage: 6 Mo

Extrait

École Doctorale Systèmes
Thèse
pour obtenir le grade de
Docteur de l’Institut National Politechnique de Toulouse
Spécialité: Systèmes Automatiques
présentée et soutenue publiquement le 2 février 2007
Towards Visual Localization, Mapping and Moving Objects
Tracking by a Mobile Robot: a Geometric and Probabilistic
Approach
Joan Solà Ortega
Préparée au Laboratoire d’Analyse et d’Architecture de Systèmes du CNRS
sous la direction de M. André Monin et M. Michel Devy
Jury
M. Jean-Yves Fourniols Président
M. Andrew Davison Rapporteur
M. Patrick Rives Rapp
M. Raja Chatila Examinateur
M. Gérard Favierinateur
M. Alberto Sanfeliu Examinateur
M. André Monin Directeur de Thèse
M. Michel Devy Codirecteur de ThèseTowards Visual Localization, Mapping
and Moving Objects Tracking
by a Mobile Robot:
a Geometric and Probabilistic Approach.
Joan Solà
February 2, 2007Contents
List of Symbols 5
Introduction 9
A (very short) reading guide 15
I Introductory material 17
1 Kinematics 19
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 Rigid body motions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.1 Frame conventions and notation. . . . . . . . . . . . . . . . . . . . . . . 20
1.2.2 Frame transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.3 Manipulating different rotation representations in a unique project . . . 28
1.2.4 The homogeneous matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.5 Composition of transformations . . . . . . . . . . . . . . . . . . . . . . . 29
1.3 Dynamic scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.3.1 From continuous-time to discrete-time . . . . . . . . . . . . . . . . . . . 30
1.3.2 Odometry models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.3 Dynamic models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2 Vision 35
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Perspective cameras: a geometrical model . . . . . . . . . . . . . . . . . . . . . 36
2.2.1 The pin-hole camera model . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.2 The thin lens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.3 Distortion in the real lens camera . . . . . . . . . . . . . . . . . . . . . . 40
2.2.4 The image in pixel coordinates . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.5 Summary of the perspective camera model . . . . . . . . . . . . . . . . . 43
2.3 The perspective camera inverse model . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.1 Inversion of the pixel mapping . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Distortion correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Back-projection from the normalized camera. . . . . . . . . . . . . . . . 49
2.3.4 Summary of the perspective camera inverse model . . . . . . . . . . . . 49
2.4 Basic feature-based image processing . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4.1 The Harris corner detector and some variations . . . . . . . . . . . . . . 52
12 CONTENTS
2.4.2 Correlation-based feature matching . . . . . . . . . . . . . . . . . . . . . 54
3 Filtering 59
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.1.1 Some brief notions from the Theory of Probabilities . . . . . . . . . . . 60
3.1.2 The filtering problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.3 Incremental filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 The Kalman and Extended Kalman Filters . . . . . . . . . . . . . . . . . . . . 66
3.2.1 The Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.2 The Extended Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3 The Gaussian Sum Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 The Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4 Simultaneous Localization And Mapping 77
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2 Extended Kalman Filter SLAM . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.2 Algorithm complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3 Scalable SLAM algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.1 Exactly-Sparse Extended Information Filter SLAM . . . . . . . . . . . . 82
4.3.2 FastSLAM2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4 Alternatives to incremental formulations . . . . . . . . . . . . . . . . . . . . . . 83
II Vision based SLAM 85
5 Probabilistic vision 87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 The conic ray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3 Knowledge composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.1 Motion: Convolution-like composition . . . . . . . . . . . . . . . . . . . 91
5.3.2 Observation: Product-like composition . . . . . . . . . . . . . . . . . . . 92
5.4 3D observability from vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.5 Active feature search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6 Mono-camera SLAM 97
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Delayed versus undelayed initializations . . . . . . . . . . . . . . . . . . . . . . 98
6.3 Implications of an undelayed initialization . . . . . . . . . . . . . . . . . . . . . 101
6.3.1 Unmeasured depth and initialization in EKF . . . . . . . . . . . . . . . 101
6.3.2 On the two main stochastic approaches . . . . . . . . . . . . . . . . . . 102
6.3.3 Gaussian multi-hypothesized depth landmark initialization . . . . . . . . 103
6.4 Federated Information Sharing SLAM . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.1 The ray: a geometric series of Gaussians . . . . . . . . . . . . . . . . . . 105
6.4.2 The FIS algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.4.3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.5 Feature detection and matching using vision . . . . . . . . . . . . . . . . . . . . 117CONTENTS 3
6.5.1 Landmarks model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5.2 Feature Detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.5.3 F Matching (FM) . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.6.1 Outdoors, the ‘Boxes’ experiment . . . . . . . . . . . . . . . . . . . . . . 122
6.6.2 Indoors, the ‘White-board’ experiment . . . . . . . . . . . . . . . . . . . 124
6.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7 Bi-camera SLAM 129
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.2 Landmarks initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2.1 Observability evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2.2 Conditional landmark initializations . . . . . . . . . . . . . . . . . . . . 133
7.3 Stereo rig self-calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.4 Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.6 Conclusion and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8 Vision based SLAM with Moving Objects Tracking 143
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.2 Precedents and our general position . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.3 Observability analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.3.1 Bearings-only sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.3.2 Range-and-bearing sensing. . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.4 The Filtering side: Moving Objects Tracking . . . . . . . . . . . . . . . . . . . 148
8.4.1 Uncorrelated moving objects . . . . . . . . . . . . . . . . . . . . . . . . 148
8.4.2 Global localization or local tracking? . . . . . . . . . . . . . . . . . . . . 149
8.4.3 System set-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.4.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8.5 The Perception side: Moving Objects Detection . . . . . . . . . . . . . . . . . . 156
8.5.1 Detection Mechanisms (DM) . . . . . . . . . . . . . . . . . . . . . . . . 157
8.5.2 Priority-based Detection Selector (PbDS) . . . . . . . . . . . . . . . . . 161
8.6 Some results . . . . . . . . . . . . . . . . .