HBST (Hamming Binary Search Tree)

HBST(Schlegel & Grisetti, 2018)는 이진 디스크립터(ORB, BRIEF, BRISK, FREAK)를 위한 이진 탐색 트리로, 해밍 공간에서 로그 비용으로 근사 최근접 이웃 쿼리에 답하며 — SLAM에 있어 결정적으로 — 탐색 중 증분 삽입을 지원합니다. 이는 루프 클로저 검출을 위한 가볍고 어휘집(vocabulary)이 필요 없는 대안으로 제안되었으며, 시각 단어 가방(bag-of-visual-words, DBoW2)이나 FLANN-LSH를 대체합니다: 미리 학습된 어휘집에 대해 디스크립터를 양자화하는 대신, 궤적이 도착하는 대로 원본 디스크립터를 그대로 색인합니다.

트리는 어떻게 구축되는가

이진 디스크립터는 고정 길이의 비트 문자열 $\mathbf{d} \in \{0,1\}^D$ (예: ORB의 경우 $D = 256$ )이며, XOR + popcount로 계산되는 해밍 거리(서로 다른 비트의 개수)로 비교됩니다.

각 내부 노드는 단일 비트 인덱스 $k \in \{0, \dots, D-1\}$ 을 저장합니다. 디스크립터는 비트 $k$ 가 0이면 왼쪽으로, 1이면 오른쪽으로 라우팅됩니다.
각 리프는 디스크립터 집합을 저장합니다(페이로드 포함 — SLAM에서는 그 디스크립터가 유래한 이미지/키프레임 인덱스와 키포인트).
리프가 최대 크기를 초과하면 분할됩니다: 해당 리프가 보유한 디스크립터들에 대해 분할 비트가 선택되고, 두 자식으로 재분배됩니다.

분할 비트는 균형을 위해 선택됩니다: 리프 안의 디스크립터들에 대해 모든 후보 비트의 평균값 $\bar{d}_k$ 를 계산하고, 평균이 $0.5$ 에 가장 가까운 비트, 즉 집합을 가장 균등하게 나누는 비트를 선택합니다. $N$ 개의 디스크립터에 대해 균형 잡힌 트리는 깊이가 $\log_2 N$ 정도이며, 각 쿼리는 루트-리프 경로 하나만 거칩니다.

탐색 — 그리고 왜 이것이 근사적인가

쿼리 디스크립터 $\mathbf{q}$ 는 각 노드의 인덱스에 해당하는 자신의 비트를 읽으며 트리를 내려가고(깊이 $h$ 에 대해 $h$ 번의 비트 검사), 하나의 리프에 도달하여 오직 그 리프의 디스크립터들에 대해서만 해밍 거리로 전수 매칭됩니다(거리 임계값 $\tau$ 미만의 매칭을 수락). 총 비용은 리프 크기 $L$ 에 대해 $O(\log N + L)$ 이며, 브루트 포스의 $O(N)$ 과 대조됩니다.

그 대가는 근사성입니다: 쿼리와 분할에 사용된 비트 중 하나에서 다른 값을 가지는 진짜 매칭 후보는 다른 리프로 라우팅되어 놓치게 됩니다. 이 확률은 트리 깊이와 디스크립터 잡음에 따라 커집니다. HBST가 이를 받아들이는 이유는 장소 인식이 모든 매칭을 필요로 하지 않기 때문입니다 — 올바른 키프레임에 투표할 만큼 충분히 일관된 매칭만 있으면 되며, 이후 기하학적 검증이 나머지를 정리해줍니다.

증분적인 탐색-삽입

HBST가 SLAM의 온라인 환경에 잘 맞는 이유가 되는 연산입니다: 새 이미지가 들어올 때마다 그 디스크립터들이 트리에 한 번 내려가며, 같은 과정에서 트리는 (1) 지금까지 색인된 모든 것에 대한 매칭을 보고하고 (2) 새 디스크립터를 삽입합니다(넘치는 리프는 분할합니다). 데이터베이스는 오프라인 학습 단계, 어휘집 파일, 주기적인 재구축 없이 궤적과 함께 성장합니다. 매칭은 과거 이미지별로 집계됩니다 — 매칭된 각 디스크립터는 자신이 속한 키프레임에 투표를 던지며 — 득표 수가 높은 키프레임이 루프 클로저 후보가 되고, 이후 기하학적으로(예: 에센셜 행렬 또는 RANSAC 내 PnP) 검증됩니다.

최대 리프 크기 $L$ 을 가진 $N$ 개 디스크립터의 데이터베이스에 대한 비용을 정리하면:

삽입: 루트-리프 하강 한 번, $O(\log N)$ , 그리고 간혹 리프 분할.
쿼리: $O(\log N)$ 의 비트 검사 + 리프 내에서 $O(L)$ 의 해밍 비교.
메모리: 원본 디스크립터와 내부 노드당 비트 인덱스 하나 — 해시 테이블도 어휘집도 없습니다.
조절 값: 최대 리프 크기 $L$ (더 깊은 트리와 더 빠른 리프 vs. 더 나은 재현율) 및 매칭 임계값 $\tau$ .

대안들과 비교했을 때의 위치

브루트 포스 매칭은 정확하지만 데이터베이스 크기에 대해 선형입니다 — 두 프레임에는 괜찮지만 수천 개의 키프레임에는 절망적입니다.
**BoW(DBoW2/DBoW3)**는 미리 학습된 어휘집이 필요하며, 양자화로 디스크립터의 세부 정보를 잃지만, 역인덱스(inverted index)는 매우 빠르고 메모리 효율적입니다.
FLANN-LSH도 이진 디스크립터를 증분적으로 처리할 수 있지만, 일반적인 루프 클로저 워크로드에서는 여러 개의 해시 테이블과 더 높은 메모리/지연 시간을 필요로 합니다.
HBST는 통제된 만큼의 재현율을 희생하는 대신, 매우 빠른 쿼리와 학습 없이 디스크립터 수준의 직접 매칭(키포인트 대응이 무료로 얻어지며 기하학적 검증에 곧바로 사용 가능)을 얻습니다.

SLAM에서의 의미

루프 클로저 검출은 “이걸 전에 본 적이 있는가?”라는 질문을 몇 프레임마다 실시간 예산 안에서 계속 커지는 데이터베이스에 던져야 합니다. HBST는 이미 이진 디스크립터를 계산하는 특징 기반 시스템에 대해 깔끔하고 자체 완결적인 답을 제공합니다: 어휘집을 배포할 필요가 없고(DBoW2 ORB 어휘집은 큰 바이너리 아티팩트입니다), 하나의 구조에서 이미지 수준과 키포인트 수준의 대응 관계를 모두 얻으며, 궤적을 따라 쿼리 시간이 로그적으로 증가합니다. 또한 해밍 공간을 색인화할 때의 정확도-속도 트레이드오프를 보여주는 유익한 사례 연구이기도 합니다 — LSH와 BoW와 비교해 보면 세 가지 모두에 대한 이해가 명확해집니다.