FLANN (Fast Library for Approximate Nearest Neighbours)

FLANN (Muja & Lowe, 2009)은 고차원 공간에서 근사 최근접 이웃 검색을 수행하는 라이브러리로, 대규모 디스크립터 매칭을 실용적으로 만들기 위해 만들어졌습니다. 정확한 브루트 포스 매칭은 $n$ 개의 쿼리와 차원 $d$ 의 디스크립터 $m$ 개의 데이터베이스에 대해 $O(n \cdot m \cdot d)$ 의 비용이 들고, 고차원에서는 정확한 트리 탐색도 거의 선형 스캔 수준으로 무너집니다. FLANN의 입장은 실용적입니다: 진짜 최근접 이웃을 찾을 확률을 예컨대 95%로 낮추는 대신 한두 자릿수의 속도 향상을 얻는 것입니다 — 어차피 이후의 비율 테스트와 RANSAC이 나쁜 매칭을 걸러내기 때문에 특징 매칭에서는 이 트레이드오프가 충분히 감내할 만합니다.

두 가지 핵심 인덱스 구조

무작위 kd-트리 포레스트. 하나의 kd-트리를 전수 탐색하는 대신, FLANN은 분할 차원을 분산이 가장 큰 몇 개의 차원 중에서 무작위로 선택하여 여러 개의 트리를 구축합니다. 모든 트리는 분할 경계까지의 거리로 정렬된 단일 공유 우선순위 큐를 통해 동시에 탐색되며, 고정된 리프 검사 예산이 소진되면 탐색을 멈춥니다. 각 트리가 공간을 서로 다르게 분할하기 때문에, 한 트리에서 분할의 잘못된 쪽으로 떨어진 진짜 이웃도 대개 다른 트리에서는 발견됩니다. 이는 부동소수점 디스크립터(SIFT의 128차원, SuperPoint의 256차원)에 대해 선택되는 방법입니다.

우선순위 탐색 k-평균 트리. 데이터는 k-평균을 이용해 노드마다 $K$ 개의 클러스터(분기 계수)로 재귀적으로 분할되며, 축에 정렬된 절단이 아니라 데이터의 자연스러운 클러스터링을 반영하는 계층 구조를 구축합니다. 쿼리는 가장 가까운 클러스터로 내려간 다음, 아직 탐색하지 않은 분기들의 우선순위 큐를 통해 되돌아갑니다. 더 높은 정밀도가 필요할 때 이 방식이 자주 우세합니다.

이진 디스크립터(ORB, BRIEF)의 경우, FLANN은 대신 멀티-프로브 LSH 인덱스를 제공합니다 — 해밍 공간에는 의미 있는 축 정렬 분할이 존재하지 않지만, 비트 샘플링 해시 함수는 그곳에서 자연스럽게 지역성 민감(locality-sensitive) 특성을 갖습니다.

알고리즘 자동 설정

FLANN의 대표적인 기능은 알고리즘을 대신 골라주는 것입니다: 데이터셋, 목표 검색 정밀도(반환되는 진짜 최근접 이웃의 비율), 그리고 빌드 시간·메모리와 쿼리 시간 사이의 중요도를 나타내는 가중치가 주어지면, 데이터의 샘플에 대해 교차 검증을 수행하여 최적의 인덱스 유형과 파라미터(트리 개수, 분기 계수, 리프 검사 예산)를 반환합니다. 이는 최적의 구조가 실제로 데이터 분포와 요구되는 정밀도에 따라 달라지며 단 하나의 절대적인 승자가 없기 때문에 중요합니다.

중요한 조절 값들

자동으로 튜닝되든 수동으로 조정되든, FLANN의 동작은 몇 가지 파라미터로 결정됩니다:

트리 개수(무작위 kd-포레스트): 트리가 많을수록 동일한 리프 검사 예산 안에서 재현율(recall)이 올라가지만 메모리와 빌드 시간이 늘어납니다. 보통 몇 개의 트리를 사용합니다.
checks — 쿼리당 리프 방문 예산: 검색 시점에서 정확도/속도를 가장 직접적으로 조절하는 하나의 값입니다. 검사 횟수가 많아질수록 정확한 검색에 점근적으로 가까워집니다.
분기 계수와 반복 횟수(k-평균 트리): 계층 구조를 더 거칠게 할지 더 세밀하게 할지, 그리고 빌드 과정에서 k-평균이 얼마나 열심히 작업할지를 결정합니다.
목표 정밀도(자동 튜닝 모드): 진짜 최근접 이웃이 반환되어야 하는 쿼리의 비율입니다. FLANN은 이를 최소 비용으로 만족시키는 파라미터 공간을 탐색합니다.

유용한 사고 모델은 다음과 같습니다: 인덱스는 어떤 후보들이 검사되는지를 정의하고, checks는 몇 개나 검사되는지를 정의합니다 — 정확도 실패는 잘못된 거리로 나타나는 것이 아니라, 단순히 방문된 적이 없는 올바른 이웃으로 나타납니다.

매칭 파이프라인에서의 사용

FLANN을 사용하는 일반적인 SLAM/SfM 매칭 단계는 다음과 같습니다:

참조 이미지(또는 맵의 랜드마크 디스크립터)의 디스크립터에 대해 인덱스를 구축합니다.
각 쿼리 디스크립터에 대해 근사 최근접 이웃 2개를 검색합니다.
Lowe의 비율 테스트를 적용합니다 — $d_1 / d_2 < 0.8$ 인 경우에만 수락 — 모호한 매칭을 걸러냅니다.
남은 매칭을 기하학적 검증(에센셜 행렬 또는 PnP 모델에 대한 RANSAC)에 전달합니다.

OpenCV에서는 이것이 cv::FlannBasedMatcher이며, cv::BFMatcher를 그대로 대체할 수 있습니다. 다만 ORB의 경우 기본 kd-트리가 부동소수점 디스크립터를 가정하므로 LSH 인덱스로 구성해야 한다는 점에 주의해야 합니다. 근사에는 한 가지 유의점이 있습니다: 비율 테스트가 근사된 첫 번째와 두 번째 이웃을 비교하므로, 공격적인 속도 설정은 어떤 매칭이 살아남는지를 약간 바꿔 놓습니다.

SLAM에서의 의미

매칭 비용은 맵의 크기에 따라 커지며, SLAM 시스템은 끊임없이 매칭을 수행합니다: 특징-맵 추적, 루프 클로저 후보 검증, 수천 개의 키프레임에 대한 재위치추정(relocalization), 그리고 이미지 컬렉션 전체에 대한 오프라인 SfM 매칭(COLMAP은 FLANN 방식의 근사 검색을 사용합니다) 등입니다. 브루트 포스는 수천 개의 ORB 특징을 가진 두 이미지 사이에서는 괜찮지만(해밍 거리 + popcount는 매우 빠릅니다), 큰 맵이나 큰 어휘집(vocabulary)에 대해서는 준선형(sub-linear) 근사 검색이 프론트엔드를 실시간으로 유지하는 핵심입니다. FLANN은 또한 3D 포인트 클라우드에 대한 최근접 이웃 쿼리(PCL과의 통합을 통해)의 표준적인 해법이기도 합니다. 여기서는 kd-트리가 낮은 차원이라는 익숙한 영역에서 동작합니다 — 예를 들어 ICP 내부의 대응점 탐색입니다.