JCBB(결합 적합성 분기 한정법)은 동시적 위치 추정 및 지도 작성(SLAM)과 컴퓨터 비전에서 관측된 특징을 알려진 지도 또는 모델과 대응시키기 위해 사용되는 데이터 연관 알고리즘이다. 이 알고리즘은 2001년 José Neira와 Juan D. Tardós가 그들의 논문 "Data Association in Stochastic Mapping Using Joint Compatibility"에서 처음 소개했다. 이 알고리즘은 센서 측정값이 어떤 랜드마크 또는 지도 특징에 해당하는지 결정하는 문제를 다루며, 이는 이동 로봇 공학에서 정확한 상태 추정을 위한 중요한 단계이다.
개별 특징 일치를 독립적으로 평가하는 더 단순한 최근접 이웃 접근 방식과 달리, JCBB는 집합 내 모든 특징 간의 통계적 상관 관계를 고려하여 일치 집합의 결합 적합성을 평가한다. 이러한 결합 테스트는 특히 반복적이거나 모호한 특징이 있는 환경에서 잘못된 일치에 대해 더 강건하다. 이 알고리즘은 분기 한정 전략을 사용하여 가능한 일치 집합의 공간을 탐색하며, 더 나은 해로 이어질 수 없는 분기를 체계적으로 가지치기하여 발견된 집합이 결합 적합성을 만족하는 가장 큰 집합임을 보장한다.
알고리즘 개요
JCBB는 (현재 지도로부터의) 예측 특징 집합과 (센서 데이터로부터의) 관측 특징 집합에 대해 작동한다. 각 관측값은 최대 하나의 예측 특징에 할당될 수 있으며, 각 예측 특징은 최대 하나의 관측값과 일치될 수 있다. 목표는 전체 공분산 행렬을 고려하여 결합 혁신 벡터(관측 측정값과 예측 측정값의 차이)가 카이제곱 임계값 내에 있도록 하는 최대 카디널리티 일치 집합을 찾는 것이다.
분기 한정 탐색은 각 노드가 관측값과 특징의 부분 할당을 나타내는 트리를 구축한다. 각 단계에서 알고리즘은 다음 미할당 관측값을 고려하고 각 남은 특징과의 적합성을 개별적으로 그리고 이미 할당된 일치와 결합하여 테스트함으로써 노드를 확장한다. 결합 적합성 테스트가 실패하면 해당 분기는 가지치기된다. 탐색은 모든 노드가 탐색될 때까지 계속되며, 최상의(가장 큰) 집합이 반환된다. 효율성을 높이기 위해 알고리즘은 일반적으로 개별 적합성에 따른 관측값의 휴리스틱 순서를 사용하여 초기에 좋은 해를 찾고 더 공격적으로 가지치기한다.
결합 적합성 테스트
JCBB의 핵심은 결합 적합성 테스트이다. 일치 집합이 주어지면 테스트는 결합 혁신 벡터와 그 공분산 행렬을 계산한다. 이 벡터의 마할라노비스 거리는 혁신 벡터의 차원과 동일한 자유도를 가진 카이제곱 임계값과 비교된다. 거리가 임계값 미만이면 집합은 결합 적합성이 있는 것으로 간주된다. 이 테스트는 로봇의 자세 불확실성과 지도의 공분산에서 발생하는 특징 간의 상관 관계를 포착하기 때문에 개별 테스트보다 더 강력하다. 예를 들어, 두 특징이 각각 다른 지도 점과 개별적으로 적합하더라도 두 특징 간의 상대적 기하학이 지도와 일치하지 않으면 결합적으로 부적합할 수 있다.
응용 및 확장
JCBB는 특히 실내 및 실외 이동 로봇 공학의 SLAM 시스템에서 널리 적용되었다. 이는 종종 최적화 또는 필터링 전에 프런트 엔드 데이터 연관 모듈로 사용된다. 이 알고리즘은 특징이 카메라 이미지에서 감지된 키포인트인 시각적 SLAM과 3D 점군 정합에도 적용되도록 적응되었다. 확장에는 초기 자세 추정을 위한 RANSAC(랜덤 표본 합의)과의 결합, 대규모 지도를 처리하기 위한 계층적 프레임워크에서의 사용이 포함된다. 실제로 JCBB는 많은 수의 특징에 대해 계산 비용이 많이 들 수 있으므로, 적합성 그래프와 최대 클리크 알고리즘을 사용하는 변형이 제안되었으며, 이는 해 측면에서 JCBB와 동일하지만 더 빠를 수 있다.
다른 방법과의 관계
JCBB는 종종 빠르지만 잘못된 일치에 취약한 개별 적합성 최근접 이웃(ICNN) 및 최대 클리크 문제를 해결하는 그래프 기반 방법과 같은 다른 데이터 연관 기법과 비교된다. 분기 한정 접근 방식은 결합 적합성 기준 하에서 전역 최적 해를 찾는 것을 보장하는 반면, 휴리스틱 방법은 차선의 집합에 만족할 수 있다. 그러나 최적성은 더 높은 계산 복잡성이라는 비용을 수반하므로, JCBB는 오프라인 처리 또는 중간 정도의 특징 수를 가진 환경에 적합하다. 현대 SLAM 시스템에서는 JCBB가 때때로 특징 일치를 위한 Machine learning 또는 Deep learning 기반의 학습 방법으로 대체되지만, 이 분야에서 여전히 기초적인 알고리즘으로 남아 있다.
같이 보기
참고 문헌
- 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.