SLAM d'un point de vue algorithmique (2e partie)

Comme nous l'avons vu dans la 1re partie, la technique SLAM consiste à estimer la position d'un véhicule robotique dans une zone inconnue tout en créant progressivement une carte de cette zone. Les algorithmes SLAM peuvent être classés selon trois techniques principales : algorithmes SLAM basés sur filtre, basés sur graphique et basés sur l'apprentissage profond.

Les algorithmes SLAM basés sur filtre traitent le SLAM comme un problème d'estimation d'état. Ici, un filtre probabiliste, comme le filtre de Kalman étendu (EKF) ou le filtre de Kalman sans parfum (UKF), est généralement utilisé pour estimer de façon récurrente l'état du robot et mettre à jour la carte en fonction des mesures de capteurs. Le filtre prédit l'état suivant du robot en se basant sur son modèle de mouvement, puis corrige ces prévisions grâce aux mesures des capteurs.

Dans la technique SLAM basée sur graphique, contrairement à celle basée sur filtre, le problème est traité comme un problème d'optimisation de graphique. Le problème SLAM est ainsi formulé sous forme de graphique, où les points représentent les positions du robot ou les repères dans l'environnement, et où les lignes représentent les mesures ou les contraintes entre ces points. Le but de la technique SLAM basée sur graphique est d'optimiser les positions du robot et des repères de manière à ce que les contraintes mesurées (comme les distances entre les repères, les positions relatives entre les différentes positions connues du robot) soient aussi précises que possible.

Les méthodes SLAM basées sur l'apprentissage profond utilisent des réseaux neuronaux pour apprendre les représentations de l'environnement directement à partir des données des capteurs, sans dépendre de caractéristiques ou de modèles réalisés à la main. Ces méthodes peuvent apprendre des cartographies complexes entre les mesures de capteurs et la position ou la carte du robot, ce qui permet d'avoir des solutions SLAM de bout en bout.

Les fonctionnalités SLAM de base, à savoir la cartographie et la localisation, sont étroitement liées : le robot met à jour sa carte en permanence en fonction des données des capteurs et ajuste l'estimation de sa position en conséquence. En tant qu'un outil modulaire, le SLAM et ses concepts permettent d'effectuer des remplacements et des modifications tout au long du processus. Ainsi, très souvent, plusieurs algorithmes sont développés et utilisés conjointement, ce qui rend difficile la généralisation et l'explication de SLAM en tant qu'algorithme unique. Le meilleur moyen de bien comprendre le SLAM est donc de cibler une implémentation SLAM en particulier. Cela étant dit, abordons en détail le SLAM visuel (vSLAM) basé sur filtre.

SLAM visuel

Comme son nom l'indique, le vSLAM utilise un capteur visuel (une caméra) comme capteur principal. Il peut également utiliser des codeurs, une unité de mesure inertielle (IMU) et d'autres capteurs. Un schéma fonctionnel générique de l'implémentation est disponible à la Figure 1.

Figure 1 : Schéma fonctionnel générique simplifié du processus SLAM basé sur des caractéristiques. (Reproduit à partir de kudan.io)

Mesure de la caméra

La caméra capture des images de l'environnement du robot, notamment des caractéristiques comme les points de repère, les bordures et les textures. Cependant, les images capturées nécessitent une correction de la distorsion, car la plupart des objectifs de caméra entraînent un certain niveau de distorsion. Les caméras utilisées peuvent être des caméras stéréo, monoculaires ou RGB-D avec capteurs de profondeur ToF (temps de vol). L'avantage des caméras stéréo et RGB-D est que les informations sur la profondeur sont facilement disponibles. De leur côté, les caméras monoculaires rencontrent des difficultés en raison de l'ambiguïté quant à l'échelle. En effet, le SLAM monoculaire ne peut pas identifier la longueur des mouvements de translation (facteur d'échelle) en se basant uniquement sur les correspondances des caractéristiques. Il existe néanmoins des moyens de réduire ce problème, mais cela n'entre pas dans le cadre de cet article.

Extraction des caractéristiques

Après avoir capturé les images à l'aide d'un capteur photo, il faut identifier l'image de manière unique en trouvant les caractéristiques d'une image en particulier afin de s'en servir comme référence future. Dans ce contexte, les caractéristiques correspondent aux pixels uniques qui peuvent être systématiquement identifiés. Il s'agit en fait de points distinctifs sur une image, qui ne sont pas impactés par la rotation, le changement d'échelle ou la distorsion, ce qui les rend faciles à ré-identifier même après des manipulations de l'image. En supposant que nous utilisons une caméra stéréo comme capteur principal, nous devrions pouvoir voir les caractéristiques qui se recoupent entre les images stéréo capturées par la caméra. Ces caractéristiques identiques peuvent ensuite être utilisées pour estimer la distance par rapport au capteur. Mais avant ça, il faut identifier des caractéristiques communes sur la paire d'images stéréo, comme indiqué précédemment. Cette opération se fait grâce à des détecteurs et des outils de mise en correspondance des caractéristiques. Parmi les exemples courants de détecteurs de caractéristiques figurent les détecteurs SIFT (Scale-Invariant Feature Transform), ORB (Oriented FAST and rotated BRIEF) et GFTT (Good Features to Track). La Figure 2 représente les caractéristiques identifiées à l'aide de détecteurs de caractéristiques populaires. Une fois les caractéristiques identifiées, on leur attribue une description en utilisant les mêmes détecteurs de caractéristiques. Ce processus permet de ré-identifier facilement ces caractéristiques par la suite.

Figure 2 : Points clés détectés sur la photo du robot XRP à l'aide des technologies a) GFTT et b) SIFT. (Source : SparkFun Electronics)

Une fois les points clés trouvés, ils sont mis en correspondance. Différents algorithmes de mise en correspondance des caractéristiques peuvent être utilisés, comme Brute Force Matcher ou Fast Library for Approximate Nearest Neighbors (FLANN). La Figure 3 montre une représentation visuelle de l'algorithme de mise en correspondance en action. Des lignes relient les points mis en correspondance, et comme nous avons utilisé des images miroirs, nous devrions idéalement avoir uniquement des lignes horizontales (parallèles), à condition que le système soit parfait. Malheureusement, les algorithmes de mise en correspondance sont difficilement parfaits et cela entraîne de mauvaises mises en correspondance (indiquées par des lignes inclinées). C'est la raison pour laquelle il convient d'utiliser des outils de rejet des anomalies comme Random Sample Consensus (RANSAC).

Figure 3 : Lignes indiquant les mises en correspondance de caractéristiques sur deux images inversées avec FLANN. (Source : SparkFun Electronics)

RANSAC

Des algorithmes comme RANSAC sont utilisés pour filtrer ces mises en correspondance incorrectes, garantissant ainsi que seules des mises en correspondance correctes sont utilisées pour les opérations de traitement ultérieures. RANSAC fonctionne en créant un modèle à partir d'un sous-ensemble aléatoire composé des données fournies. Certains points aléatoires sont ainsi considérés comme exacts et la mise en correspondance de tous les points restants se fait en fonction de ces quelques points sélectionnés. Ensuite, le degré de correspondance du modèle par rapport à l'ensemble de données entier est évalué. Ce processus est répété jusqu'à trouver un modèle qui décrit avec précision les données, avec un minimum d'erreurs, tel que déterminé par une fonction coût.

Association des caractéristiques et des données

Lors de cette étape, les caractéristiques détectées et leur position estimée dans l'espace sont utilisées pour créer une carte de ces caractéristiques. À mesure que le processus progresse et passe aux images suivantes, le système associe de nouvelles caractéristiques à des éléments connus sur la carte et rejette les caractéristiques incertaines.

Tandis que le mouvement de la caméra est suivi pour les images suivantes, des prévisions peuvent être faites en fonction des caractéristiques connues et des changements attendus liés au mouvement. Cependant, les ressources informatiques et les contraintes de temps, en particulier dans les applications en temps réel, imposent des limites sur SLAM. Étant donné que le système recueille de nouvelles mesures de caractéristiques et met à jour la localisation/position au fil du temps, il devient essentiel de limiter et d'optimiser la représentation de l'environnement.

Localisation, position et mise à jour de la carte

Filtre de Kalman

À mesure que le processus SLAM avance, il accumule du bruit et développe une incertitude entre les images capturées par la caméra et le mouvement de cette dernière. En générant des prévisions en continu, en mettant à jour et en peaufinant le modèle par rapport aux mesures observées, les filtres de Kalman peuvent réduire l'effet du bruit et de l'incertitude parmi les différentes mesures. Cela contribue à créer un modèle de système linéaire. Pour les implémentations SLAM réelles, des filtres de Kalman étendus (EKF) permettent d'utiliser des systèmes non linéaires et de linéariser les prévisions et les mesures autour de leur moyenne. Un filtre EKF peut intégrer des données de plusieurs capteurs en fusionnant des capteurs (par exemple, caméras, unités de mesure inertielle) afin d'améliorer la précision des estimations de l'état et de la carte. Cette fusion des sources de données permet d'obtenir des résultats SLAM plus fiables. Le vecteur d'état dans le SLAM basé EKF inclut la position du robot (position et orientation), ainsi que les positions des points de repère sur la carte.

Sélection des images clés

Des images clés (Keyframes) sont choisies parmi les images capturées afin de réduire les calculs intenses nécessaires pour traiter toutes les images capturées. Des images constituant une bonne représentation de l'environnement sont ainsi choisies, et elles seules sont utilisées pour les calculs. Cette méthode constitue là encore un compromis entre précision et rendement.

Correction des erreurs via la fermeture de boucle et la relocalisation

Au fil de l'avancée du processus de création d'un modèle pour l'environnement, erreurs de mesure et dérives de capteur s'accumulent progressivement, ce qui a un impact sur la carte générée. Ce problème peut être atténué dans une certaine mesure grâce à la fermeture de boucle. La fermeture de boucle se produit lorsque le système identifie qu'il est en train de réexaminer une zone précédemment cartographiée. En réalignant la carte actuelle avec la carte précédemment établie pour la même zone, le système SLAM peut corriger les erreurs accumulées.

Relocalisation

Une relocalisation est nécessaire lorsque le système perd sa position et son orientation. Il faut alors réestimer la position en utilisant les caractéristiques actuellement observables. Une fois que le système parvient à mettre en correspondance les caractéristiques actuellement disponibles par rapport à la carte disponible, le processus SLAM peut se poursuivre normalement.

Conclusion

La technique SLAM consiste à estimer la position d'un véhicule robotique tout en cartographiant une zone inconnue. Les techniques SLAM incluent des méthodes basées sur filtre, basées sur graphique et basées sur l'apprentissage profond (à l'aide de réseaux neuronaux). Le SLAM visuel utilise des caméras pour capturer des images, extraire des caractéristiques et les mettre en correspondance, et filtrer les mises en correspondance incorrectes. Le système crée une carte en associant de nouvelles caractéristiques à des éléments connus, en mettant à jour la localisation et la position du robot à l'aide de filtres de Kalman, en choisissant des images clés et en corrigeant les erreurs grâce à la fermeture de boucle et à la relocalisation.

Références

1. Remote Sensing | Free Full-Text | SLAM Overview: From Single Sensor to Heterogeneous Fusion (mdpi.com)
2. Understanding how V-SLAM (Visual SLAM) works | Kudan global
3. Feature-based visual simultaneous localization and mapping: a survey | Discover Applied Sciences (springer.com)
4. Introduction to Visual SLAM: Chapter 1 —Introduction to SLAM | by Daniel Casado | Medium
5. An Introduction to Key Algorithms Used in SLAM - Technical Articles (control.com)
6. What Is SLAM (Simultaneous Localization and Mapping) – MATLAB & Simulink - MATLAB & Simulink (mathworks.com)
7. A survey of state-of-the-art on visual SLAM - ScienceDirect