Open Source Robotics

Une collection organisée de projets, outils et logiciels robotiques open source de haute qualité.

RANSAC

  • Aussi appelé: Random Sample Consensus
  • Catégorie: Sensing › Perception outputs
  • Mots-clés: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting

Random Sample Consensus : méthode d'ajustement robuste qui ajuste à plusieurs reprises un modèle sur de petits sous-ensembles aléatoires des données et conserve le modèle en accord avec le plus grand nombre de points, en ignorant les valeurs aberrantes.

Définition

RANSAC (Random Sample Consensus), introduit par Fischler et Bolles en 1981, estime les paramètres d'un modèle à partir de données contenant de nombreuses valeurs aberrantes. L'ajustement par moindres carrés utilise tous les points, de sorte que quelques erreurs grossières peuvent éloigner fortement le résultat de la vérité. RANSAC répète plutôt une boucle simple : tirer le nombre minimal de points nécessaire pour définir le modèle (deux pour une droite, trois pour un plan, un petit nombre fixe pour une pose de caméra ou une matrice fondamentale), ajuster le modèle sur ces points, et compter combien de points parmi toutes les données se trouvent à moins d'un seuil de celui-ci. Ces points forment l'ensemble de consensus, ou inliers. Après un certain nombre d'itérations, le modèle ayant le plus grand ensemble de consensus est conservé et généralement réajusté par moindres carrés sur tous ses inliers.

Le nombre d'itérations découle des probabilités. Si w est la proportion d'inliers et s la taille de l'échantillon, un échantillon aléatoire ne contient que des inliers avec la probabilité wˢ, donc le nombre d'itérations k nécessaire pour tirer au moins un échantillon propre avec une confiance p est k = log(1 − p) / log(1 − wˢ). Ce nombre croît rapidement quand la proportion d'inliers baisse ou que la taille de l'échantillon augmente, ce qui explique l'importance en vision des solveurs minimaux qui demandent moins de points, comme la pose relative à cinq points. Le seuil d'inlier est l'autre paramètre clé : il doit correspondre au bruit attendu des vrais inliers et doit être fixé dans les unités du résidu mesuré.

De nombreuses variantes améliorent la boucle de base. MSAC et MLESAC notent les hypothèses avec un coût robuste plutôt qu'avec un simple décompte d'inliers, PROSAC échantillonne d'abord les appariements les plus prometteurs, LO-RANSAC affine localement les bonnes hypothèses, et des versions adaptatives mettent à jour k à mesure que la proportion d'inliers est estimée. En robotique, RANSAC sert à la segmentation de plans et de primitives dans les nuages de points, au filtrage des appariements de caractéristiques en odométrie visuelle et en SLAM, à l'estimation de pose par Perspective-n-Point, au recalage de nuages de points à partir de correspondances de caractéristiques et à l'étalonnage. Comme la procédure est aléatoire, les résultats peuvent différer d'une exécution à l'autre si la graine aléatoire n'est pas fixée.

Pourquoi c'est important

Les données réelles des capteurs regorgent de valeurs aberrantes : appariements de caractéristiques erronés, reflets, objets en mouvement et points appartenant à d'autres surfaces. RANSAC est la manière standard d'ajuster des modèles géométriques malgré elles, et il se trouve au cœur de la plupart des chaînes de traitement d'odométrie visuelle, de SLAM, d'étalonnage et de segmentation de nuages de points.

Applications principales

  • Segmentation de plans, de cylindres et de sphères dans les nuages de points
  • Rejet des valeurs aberrantes parmi les appariements de caractéristiques en odométrie visuelle et en SLAM
  • Estimation de la pose de la caméra avec Perspective-n-Point
  • Estimation des matrices fondamentale, essentielle et d'homographie
  • Recalage global de nuages de points à partir de correspondances de caractéristiques
  • Ajustement de droites et de modèles d'étalonnage sur des données de capteurs bruitées

En pratique

Un manipulateur mobile doit trouver le plateau d'une table dans le nuage de points d'une caméra de profondeur avant de poser des objets. Le logiciel sous-échantillonne le nuage et exécute un ajustement de plan par RANSAC : il choisit à plusieurs reprises trois points, calcule le plan qui passe par eux et compte les points situés à moins d'un seuil de distance fixé légèrement au-dessus du bruit de profondeur du capteur. Le plan ayant le plus d'inliers est réajusté par moindres carrés, ses inliers sont retirés, et les points restants au-dessus de lui sont regroupés en objets. Les ingénieurs vérifient que la normale du plan pointe à peu près vers le haut, car avec un grand mur ou un sol dans le champ de vue, RANSAC peut renvoyer cette surface à la place, et ils fixent la graine aléatoire dans les tests pour que les résultats soient reproductibles.

Idées reçues

  • RANSAC trouve le modèle optimal — il renvoie la meilleure hypothèse qu'il a échantillonnée par hasard, de sorte que les résultats sont probabilistes et peuvent différer d'une exécution à l'autre
  • Davantage d'itérations compensent un mauvais seuil — le seuil décide de ce qui compte comme accord, et un mauvais choix biaise le résultat quel que soit le nombre d'itérations
  • RANSAC supporte n'importe quelle proportion de valeurs aberrantes — le nombre d'itérations requis croît rapidement quand la proportion d'inliers baisse, et avec très peu d'inliers il peut échouer ou se fixer sur une structure parasite
  • RANSAC ne peut trouver qu'un seul modèle — l'algorithme de base en trouve un, mais les variantes séquentielles et multi-modèles extraient plusieurs structures en retirant les inliers et en recommençant

Qui devrait le savoir

  • Ingénieurs en perception et en vision par ordinateur
  • Développeurs SLAM et d'odométrie visuelle
  • Ingénieurs qui traitent des nuages de points pour la manipulation
  • Ingénieurs en étalonnage et en métrologie

Technologies associées

  • Ajustement par moindres carrés (Least-Squares Fitting)
  • M-estimateurs (M-Estimators)
  • MSAC et MLESAC
  • PROSAC
  • Transformée de Hough (Hough Transform)
  • Point Cloud Library

Termes associés

  • Point Cloud
  • Perspective-n-Point
  • Visual Odometry
  • Iterative Closest Point
  • Bundle Adjustment
  • Extrinsic Calibration

Projets associés

  • pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
  • AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
  • MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
  • PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
  • OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying

Vidéos

  • RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
  • Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision

Ce site nécessite JavaScript. Veuillez activer JavaScript pour explorer nos projets de robotique open source.