Bag of Visual Words

**Bag of Visual Words (BoVW)**는 텍스트 검색 아이디어를 이미지에 적용한다 (Sivic & Zisserman, 2003): 지역 특징 디스크립터를 “시각적 단어(visual words)“의 이산적인 어휘로 양자화하고, 이미지를 단어 등장 히스토그램으로 표현한 뒤 히스토그램을 비교하여 이미지를 비교한다. 이는 SLAM에서 루프 클로저 감지와 재지역화의 배후에 있는 고전적인 엔진이다 (예: ORB-SLAM의 DBoW2).

파이프라인

어휘 구성 (오프라인). 학습 코퍼스로부터 지역 디스크립터(예: ORB, SIFT)의 대규모 집합을 수집하고 k-평균으로 군집화하여 $K$ 개의 군집 중심 — 시각적 단어 — 을 만든다. 이진 디스크립터의 경우, 군집 중심은 유클리드 평균이 아니라 해밍 공간의 중앙값으로 계산된다.
이미지 표현. 각 새 이미지에 대해 디스크립터를 추출하고 각각을 가장 가까운 시각적 단어에 할당한다. 이미지는 $K$ 차원 히스토그램 $\mathbf{v}$ 가 되며, 빈 $k$ 는 단어 $k$ 에 할당된 키포인트 수를 센다. 모든 공간적 배치는 버려진다 — 그래서 “가방(bag)“이라 부른다.
TF-IDF 가중. 모든 단어가 동등하게 유용한 것은 아니다. 각 빈은 단어 빈도와 역문서 빈도의 곱으로 가중된다:

$v_k = \frac{n_{k,d}}{n_d} \cdot \log\frac{N}{n_k}$

여기서 $n_{k,d}$ 는 이미지 $d$ 에서 단어 $k$ 의 출현 수, $n_d$ 는 이미지의 전체 단어 수, $N$ 은 데이터베이스 이미지 수, $n_k$ 는 단어 $k$ 를 포함하는 데이터베이스 이미지 수다. 어디에나 등장하는 단어들(바닥 텍스처, 나뭇잎)은 가중이 낮아지고, 희소하고 구별력 있는 단어들이 점수를 지배한다.

검색. 가중된 히스토그램을 정규화하고 유사도를 점수화한다 — DBoW2는 L1 기반 점수를 사용한다:

$s(\mathbf{v}_1, \mathbf{v}_2) = 1 - \frac{1}{2}\left\lVert \frac{\mathbf{v}_1}{\lVert \mathbf{v}_1 \rVert} - \frac{\mathbf{v}_2}{\lVert \mathbf{v}_2 \rVert} \right\rVert_1$

— 그리고 가장 높은 점수를 받은 데이터베이스 이미지들을 루프 클로저 후보로 반환한다.

계층적 어휘 트리

평면적인 어휘는 각 디스크립터를 할당하는 데 $O(K)$ 번의 거리 계산이 필요하며, 이는 판별력 있는 검색에 필요한 $K \sim 10^5$ – $10^6$ 개의 단어에는 너무 느리다. DBoW2/DBoW3는 계층적 k-평균으로 구축된 **어휘 트리(vocabulary tree)**에 단어들을 배치한다: 노드당 $k$ 개의 가지, $L$ 개의 레벨로, 리프 단어 $K = k^L$ 개를 만든다. 디스크립터를 할당하는 것은 레벨마다 $k$ 개의 자식과 비교하며 트리를 걷는 것이다 — $O(kL)$ , 즉 $K$ 에 대해 로그 스케일이다.

두 가지 색인 구조가 검색과 검증을 빠르게 만든다:

역색인(inverted index): 각 단어에 대해, 그 단어를 포함하는 데이터베이스 이미지 목록(가중치 포함). 질의를 점수화할 때는 적어도 하나의 단어를 공유하는 이미지만 건드린다.
직접 색인(direct index): 각 이미지에 대해, 특정 중간 레벨의 트리 노드별로 그룹화된 특징들. 후보가 검색되면, 기하학적 검증을 위한 대응점은 같은 노드에 속한 특징만 매칭하여 찾는다 — 브루트 포스 디스크립터 매칭보다 훨씬 빠르다.

실전 노트

어휘 크기가 중요하다: 어휘가 작으면 서로 다른 특징들이 같은 단어로 충돌한다(구별력이 낮음). 너무 크면 매칭되는 특징들이 여러 단어로 갈라진다(재현율이 낮음). 검색 시스템은 계층적 트리가 할당을 값싸게 유지해 주기 때문에 정확히 큰 어휘를 사용한다.
루프 클로저를 위한 정규화: 원시 점수는 장면의 텍스처 풍부함에 의존하므로, ORB-SLAM 같은 시스템은 질의의 공동 가시(covisible) 키프레임들 중 최고 점수로 후보의 점수를 정규화하여, 절대 임계값을 환경에 걸쳐 이식 가능한 상대적 임계값으로 바꾼다.
어디서나 동일한 어휘: 사전 학습된, 환경에 독립적인 어휘(예: ORB-SLAM에 함께 제공되는 ORB 어휘)는 실제로 놀랄 만큼 잘 작동하여, 배포마다 학습을 다시 할 필요를 없앤다.

한계와 검증 단계

BoVW는 기하 정보를 버리므로, 유사한 텍스처 통계를 가진 두 이미지가 같은 장소를 담고 있지 않아도 높은 점수를 받을 수 있다 (지각 모호성(perceptual aliasing) — 복도, 벽돌 벽). 그래서 실용적인 루프 클로저 파이프라인은 BoVW 출력을 후보로만 취급하고 기하학적 검증으로 확인한다: 특징을 매칭하고, RANSAC으로 본질/기본 행렬 또는 PnP 자세를 추정하며, 충분한 인라이어가 일관된 기하를 지지할 때만 루프를 승인한다. 시간적 일관성 검사(여러 연속 프레임이 매칭될 것을 요구)는 거짓 양성을 더욱 억제한다. 하나의 시각적 도메인에서 학습된 어휘는 매우 다른 환경으로는 완벽하게 전이되지 않는다.

SLAM에서의 의미

오도메트리는 표류(drift)한다. 루프 클로저는 SLAM을 단순한 데드 레코닝 이상으로 만드는 요소이며, BoVW는 맵 크기와 무관하게 상수 시간으로 루프를 찾는 고전적인 방법이다. 또한 추적 실패 후 재지역화와 다중 세션 맵 정렬에도 동력을 제공한다. 학습된 전역 디스크립터(NetVLAD와 그 후속작들)가 최신 시스템에서 검색 단계를 대체하고 있음에도, BoVW 아키텍처 — 양자화, 가중, 역색인, 검증 — 는 여전히 참조 설계로 남아 있으며, DBoW2 스타일의 어휘는 빠르고 컴팩트하며 CPU만으로 작동하기 때문에 지금도 많은 배포된 시스템에서 실행되고 있다.

실습

전역 특징 검출