브루트 포스 매칭
브루트 포스(BF) 매칭은 디스크립터 매칭에 대한 정확하고 전수적인 접근이다: 이미지 1의 모든 디스크립터를 이미지 2의 모든 디스크립터와 비교하고 최근접 이웃(또는 상위 개 이웃)을 유지한다. 개와 개의 키포인트, 디스크립터 차원 에 대해 비용은 다. 이는 모든 근사 방법(FLANN, kd-트리, LSH)이 비교되는 기준선이며 — 프레임 간 SLAM에서 흔히 나타나는 디스크립터 개수라면 종종 옳은 선택이다.
거리 척도
- 부동소수점 디스크립터 (SIFT, SuperPoint): 유클리드(L2) 거리
- 이진 디스크립터 (ORB, BRIEF, AKAZE의 M-LDB): 해밍 거리 — 서로 다른 비트의 수로, 다음과 같이 계산된다:
256비트 ORB 디스크립터는 단 32바이트만 차지하며, XOR + popcount는 단일 머신 명령어이므로, 완전한 해밍 비교는 몇 사이클 정도의 비용만 든다. 이것이 이진 디스크립터가 브루트 포스 매칭을 병목에서 CPU에서도 예사롭게, GPU에서는 자명하게 전수적으로 수행할 수 있는 무언가로 바꾼 이유다.
원시 매칭 필터링
최근접 이웃 거리만으로는 좋은 수락 기준이 되지 못한다. 모호하거나 잘못된 매칭을 제거하는 몇 가지 표준 필터가 있다:
- Lowe의 비율 테스트. 각 질의 디스크립터에 대해, 최근접 거리 과 두 번째로 가까운 거리 를 찾고, 다음을 만족할 때만 매칭을 받아들인다:
구별력 있고 정확한 매칭은 2등보다 훨씬 가까워야 한다. 만약 두 후보가 거의 같은 거리라면, 그 매칭은 모호하며(반복적인 텍스처) 폐기된다. 이 단일 테스트만으로도 거짓 매칭의 상당 부분이 제거된다.
- 교차 검사 (상호 최근접 이웃). 가 의 최근접 이웃이고 동시에 가 의 최근접 이웃일 때만 를 받아들인다. 단순한 대칭적 일관성 필터로, 이진 디스크립터에 대해서는 종종 비율 테스트 대신 쓰인다.
- 절대 거리 임계값. 이진 디스크립터의 경우, 해밍 거리가 어떤 컷오프를 넘는 매칭은 거부한다(비트가 상당수 다르다는 것은 패치들이 서로 관련이 없다는 뜻이다).
- 기하학적 검증. 디스크립터 필터링을 통과한 것에도 여전히 이상치가 남아 있다. 에피폴라 또는 호모그래피 모델에 대한 RANSAC이 최종 관문이다.
브루트 포스가 이길 때 — 그리고 이기지 못할 때
BF 매칭은 정확하고, 빌드 시간이나 튜닝 파라미터가 없으며, 당황스러울 정도로 병렬화하기 쉽다(SIMD, GPU). 각각 수천 개의 키포인트를 가진 두 프레임을 매칭할 때는 충분히 단순하고 빠르다. 근사 최근접 이웃 구조는 데이터베이스 쪽이 크고 많은 질의에 걸쳐 재사용될 때 — 장소 인식 데이터베이스, 큰 맵에 대한 재지역화, 수만 장의 이미지를 다루는 오프라인 SfM — 이득을 본다.
실제로 실행 중인 SLAM 시스템 안에서는, 브루트 포스조차 완전히 회피되는 경우가 많다: 모션 예측이 가능하면, 특징은 **투영 기반 탐색(projection-guided search)**으로 매칭된다 — 맵 점을 현재 프레임에 투영하고, 예측된 위치 주변의 작은 윈도우 안에서만 디스크립터를 비교한다. 이는 후보 집합을 “모든 특징”에서 “근처의 몇 개”로 줄여 주며, 어떤 전역 매칭보다도 더 빠르고 모호함이 적다.
SLAM에서의 의미
데이터 연관(data association)은 프론트엔드의 핵심 임무이며, 비율 테스트나 교차 검사를 곁들인 브루트 포스 매칭은 초기화, 넓은 기준선의 키프레임 매칭, 루프 클로저 검증을 위한 잠정적 대응점을 얻는 정석적인 방법이다. 그 비용 구조를 이해하는 것 — 그리고 이진 디스크립터와 해밍 거리가 어떻게 전수 탐색을 값싸게 만드는지 — 은 ORB-SLAM 같은 시스템의 주요 설계 선택을 설명해 주며, 근사 탐색(FLANN, LSH, 어휘 트리 조회)의 추가 복잡도가 언제 정당화되는지를 정확히 밝혀 준다.