L'algorithme de compatibilité conjointe par branchement et élagage (JCBB) est un algorithme d'association de données utilisé en localisation et cartographie simultanées (SLAM) et en vision par ordinateur pour faire correspondre des caractéristiques observées à une carte ou un modèle connu. Il a été introduit par José Neira et Juan D. Tardós en 2001 dans leur article « Data Association in Stochastic Mapping Using Joint Compatibility ». L'algorithme résout le problème de la détermination des mesures de capteurs qui correspondent à quels repères ou caractéristiques de la carte, une étape cruciale pour une estimation précise de l'état en robotique mobile.
Contrairement aux approches plus simples du plus proche voisin qui évaluent indépendamment les correspondances de caractéristiques individuelles, le JCBB évalue la compatibilité conjointe d'un ensemble de correspondances en tenant compte des corrélations statistiques entre toutes les caractéristiques de l'ensemble. Ce test conjoint est plus robuste contre les fausses correspondances, en particulier dans des environnements présentant des caractéristiques répétitives ou ambiguës. L'algorithme explore l'espace des ensembles de correspondances possibles à l'aide d'une stratégie de branchement et d'élagage, qui élimine systématiquement les branches qui ne peuvent pas mener à une meilleure solution, garantissant ainsi que l'ensemble trouvé est le plus grand qui soit conjointement compatible.
Aperçu de l'algorithme
Le JCBB opère sur un ensemble de caractéristiques prédites (issues de la carte actuelle) et un ensemble de caractéristiques observées (issues des données du capteur). Chaque observation peut être attribuée à au plus une caractéristique prédite, et chaque caractéristique prédite peut être associée à au plus une observation. L'objectif est de trouver l'ensemble de correspondances de cardinalité maximale tel que le vecteur d'innovation conjoint (la différence entre les mesures observées et prédites) se situe dans un seuil du chi-carré, en tenant compte de la matrice de covariance complète.
La recherche par branchement et élagage construit un arbre où chaque nœud représente une affectation partielle des observations aux caractéristiques. À chaque étape, l'algorithme développe le nœud en considérant l'observation non assignée suivante et en testant sa compatibilité avec chaque caractéristique restante, à la fois individuellement et conjointement avec les correspondances déjà assignées. Si le test de compatibilité conjointe échoue, cette branche est élaguée. La recherche se poursuit jusqu'à ce que tous les nœuds soient explorés, et le meilleur ensemble (le plus grand) est renvoyé. Pour améliorer l'efficacité, l'algorithme utilise un ordre heuristique des observations, généralement basé sur leur compatibilité individuelle, afin de trouver de bonnes solutions tôt et d'élaguer plus agressivement.
Test de compatibilité conjointe
Le cœur du JCBB est le test de compatibilité conjointe. Pour un ensemble de correspondances donné, le test calcule le vecteur d'innovation conjoint et sa matrice de covariance. La distance de Mahalanobis de ce vecteur est comparée à un seuil du chi-carré avec des degrés de liberté égaux à la dimension du vecteur d'innovation. Si la distance est inférieure au seuil, l'ensemble est considéré comme conjointement compatible. Ce test est plus puissant que les tests individuels car il capture les corrélations entre les caractéristiques, qui proviennent de l'incertitude de la pose du robot et de la covariance de la carte. Par exemple, deux caractéristiques individuellement compatibles avec différents points de la carte pourraient être conjointement incompatibles si la géométrie relative entre elles ne correspond pas à la carte.
Applications et extensions
Le JCBB a été largement appliqué dans les systèmes SLAM, en particulier en robotique mobile intérieure et extérieure. Il est souvent utilisé comme module d'association de données en amont avant l'optimisation ou le filtrage. L'algorithme a également été adapté pour une utilisation en SLAM visuel, où les caractéristiques sont des points d'intérêt détectés dans les images de caméra, et dans l'enregistrement de nuages de points 3D. Les extensions incluent la combinaison du JCBB avec l'échantillonnage aléatoire de consensus (RANSAC) pour l'estimation initiale de la pose, et son utilisation dans un cadre hiérarchique pour gérer de grandes cartes. En pratique, le JCBB peut être coûteux en calcul pour un grand nombre de caractéristiques, c'est pourquoi des variantes ont été proposées pour réduire l'espace de recherche, comme l'utilisation d'un graphe de compatibilité et d'algorithmes de clique maximale, qui sont équivalents au JCBB en termes de solution mais peuvent être plus rapides.
Relation avec d'autres méthodes
Le JCBB est souvent comparé à d'autres techniques d'association de données comme le plus proche voisin par compatibilité individuelle (ICNN), qui est rapide mais sujet aux fausses correspondances, et aux méthodes basées sur des graphes qui résolvent le problème de la clique maximale. L'approche par branchement et élagage garantit de trouver la solution globalement optimale selon le critère de compatibilité conjointe, alors que les méthodes heuristiques peuvent se contenter d'ensembles sous-optimaux. Cependant, l'optimalité a un coût en complexité de calcul plus élevée, ce qui rend le JCBB adapté au traitement hors ligne ou aux environnements avec un nombre modéré de caractéristiques. Dans les systèmes SLAM modernes, le JCBB est parfois remplacé par des méthodes apprises basées sur l'apprentissage automatique ou l'apprentissage profond pour la correspondance de caractéristiques, mais il reste un algorithme fondamental dans le domaine.
Voir aussi
- intelligence artificielle
- apprentissage automatique
- réseau neuronal
- réseau résiduel
- augmentation de données
Références
- Neira, J., & Tardós, J. D. (2001). Data association in stochastic mapping using joint compatibility. IEEE Transactions on Robotics and Automation, 17(6), 890-897.