Joint compatibility branch and bound (JCBB) is a data association algorithm used in simultaneous localization and mapping (SLAM) and computer vision to match observed features against a known map or model. It was introduced by José Neira and Juan D. Tardós in 2001 in their paper "Data Association in Stochastic Mapping Using Joint Compatibility". The algorithm addresses the problem of determining which sensor measurements correspond to which landmarks or map features, a critical step for accurate state estimation in mobile robotics.
Unlike simpler nearest-neighbor approaches that evaluate individual feature matches independently, JCBB evaluates the joint compatibility of a set of matches by considering the statistical correlations between all features in the set. This joint test is more robust against false matches, especially in environments with repetitive or ambiguous features. The algorithm searches the space of possible match sets using a branch-and-bound strategy, which systematically prunes branches that cannot lead to a better solution, ensuring that the found set is the largest one that is jointly compatible.
Algorithm Overview
JCBB operates on a set of predicted features (from the current map) and a set of observed features (from sensor data). Each observation can be assigned to at most one predicted feature, and each predicted feature can be matched to at most one observation. The goal is to find the maximum cardinality set of matches such that the joint innovation vector (the difference between observed and predicted measurements) is within a chi-square threshold, accounting for the full covariance matrix.
The branch-and-bound search builds a tree where each node represents a partial assignment of observations to features. At each step, the algorithm expands the node by considering the next unassigned observation and testing its compatibility with each remaining feature, both individually and jointly with the already assigned matches. If the joint compatibility test fails, that branch is pruned. The search continues until all nodes are explored, and the best (largest) set is returned. To improve efficiency, the algorithm uses a heuristic ordering of observations, typically by their individual compatibility, to find good solutions early and prune more aggressively.
Joint Compatibility Test
The core of JCBB is the joint compatibility test. Given a set of matches, the test computes the joint innovation vector and its covariance matrix. The Mahalanobis distance of this vector is compared against a chi-square threshold with degrees of freedom equal to the dimension of the innovation vector. If the distance is below the threshold, the set is considered jointly compatible. This test is more powerful than individual tests because it captures the correlations between features, which arise from the robot's pose uncertainty and the map's covariance. For example, two features that are individually compatible with different map points might be jointly incompatible if the relative geometry between them does not match the map.
Applications and Extensions
JCBB has been widely applied in SLAM systems, particularly in indoor and outdoor mobile robotics. It is often used as a front-end data association module before optimization or filtering. The algorithm has also been adapted for use in visual SLAM, where features are keypoints detected in camera images, and in 3D point cloud registration. Extensions include combining JCBB with random sample consensus (RANSAC) for initial pose estimation, and using it in a hierarchical framework to handle large maps. In practice, JCBB can be computationally expensive for large numbers of features, so variants have been proposed to reduce the search space, such as using a compatibility graph and maximum clique algorithms, which are equivalent to JCBB in terms of the solution but can be faster.
Relation to Other Methods
JCBB is often compared to other data association techniques like individual compatibility nearest neighbor (ICNN), which is fast but prone to false matches, and to graph-based methods that solve the maximum clique problem. The branch-and-bound approach guarantees finding the globally optimal solution under the joint compatibility criterion, whereas heuristic methods may settle for suboptimal sets. However, the optimality comes at a cost of higher computational complexity, making JCBB suitable for offline processing or for environments with a moderate number of features. In modern SLAM systems, JCBB is sometimes replaced by learned methods based on Machine learning or Deep learning for feature matching, but it remains a foundational algorithm in the field.
See Also
References
- 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.