Kd-Tree

kd-트리(k-차원 트리, Bentley 1975)는 $\mathbb{R}^d$ 안의 점들을 위한 이진 공간 분할 구조로, 최근접 이웃 쿼리를 평균적으로 준선형(sub-linear) 비용으로 만들어줍니다. 이는 저차원 기하 데이터 — 무엇보다 3D 포인트 클라우드 — 에서 “가장 가까운 점(들)을 찾아라”라는 질문에 대한 기본 답이며, 무작위 포레스트 형태로는 고차원 부동소수점 디스크립터를 근사적으로 매칭하는 실용적인 도구입니다.

구축

각 내부 노드는 축에 정렬된 초평면(hyperplane)으로 점 집합을 분할합니다:

분할 차원을 선택합니다 — 고전적으로는 깊이에 따라 차원을 순환하며( $x, y, z, x, \dots$ ), 더 나은 방법으로는 노드 안의 점들이 가장 큰 분산/퍼짐을 갖는 차원을 선택합니다.
분할 값을 선택합니다 — 보통 중앙값 좌표를 사용하며, 이는 깊이 $O(\log n)$ 의 균형 잡힌 트리를 보장합니다.
노드가 리프 크기 임계값보다 적은 점을 가질 때까지 두 절반에 대해 재귀합니다.

중앙값의 중앙값(median-of-medians)이나 사전 정렬을 이용하면 구축 비용은 $O(n \log n)$ 이며, 트리는 각 점을 한 번씩 저장합니다.

최근접 이웃 탐색

쿼리 $\mathbf{q}$ 는 먼저 그것을 포함하는 리프까지 내려가며( $O(\log n)$ 번의 비교), 그곳에서 찾은 가장 좋은 점을 거리 $r_{\text{best}}$ 의 현재 후보로 취합니다. 그런 다음 탐색은 되돌아갑니다(backtrack): 위로 올라가는 각 노드에서, 분할 평면이 현재 최선보다 더 가까운 경우, 즉

|q_k - s| < r_{\text{best}}

인 경우에만 다른 서브트리를 방문해야 합니다. 여기서 $q_k$ 는 노드의 분할 차원 $k$ 에서의 쿼리 좌표이고 $s$ 는 분할 값입니다 — 기하학적으로는, $\mathbf{q}$ 를 중심으로 반지름 $r_{\text{best}}$ 인 초구(hypersphere)가 그 평면과 교차하는 경우에만 해당합니다. 그렇지 않으면 전체 서브트리는 가지치기(pruning)됩니다. 같은 방식으로 k-최근접 이웃 쿼리(상위 $k$ 개의 최선값에 대한 힙을 유지)와 반경 탐색도 수행할 수 있습니다.

저차원( $d \lesssim 10$ )에서는 가지치기가 효과적이며 평균 쿼리 비용은 $O(\log n)$ 입니다.

차원의 저주

$d$ 가 커지면 거리들이 밀집되기 시작합니다 — 가장 가까운 이웃과 가장 먼 이웃의 거리가 상대적으로 비슷해집니다 — 그리고 가지치기 구(球)가 거의 모든 분할 평면과 교차하게 되어, 탐색은 트리 순회의 오버헤드를 지불하면서도 전체 선형 스캔에 가까워집니다. 대략적인 규칙으로, 정확한 kd-트리 탐색이 브루트 포스를 이기려면 $n \gg 2^d$ 가 필요합니다. SIFT의 128차원은 정확한 탐색이 통하는 영역을 훨씬 벗어납니다. 현대적인 실무는 두 가지 해결책으로 정의됩니다:

최선 빈 우선(Best-bin-first, BBF)(Beis & Lowe, 1997): 우선순위 큐를 사용하여 쿼리와의 거리 순서로 노드를 탐색하고, 고정된 예산의 리프 검사 후에 멈추어, 찾은 최선의 후보를 반환합니다. 이는 kd-트리를 조절 가능한 정확도/속도 다이얼을 가진 근사 방법으로 바꿔줍니다 — 바로 SIFT 매칭을 위해 도입되었습니다.
무작위 kd-트리 포레스트: (분산이 큰 상위 차원들 중에서) 무작위로 선택된 분할 차원을 가진 여러 개의 트리를 구축하고, 하나의 공유 우선순위 큐를 통해 탐색합니다; 한 트리의 나쁜 분할 뒤에 “숨어 있는” 이웃도 다른 트리를 통해 발견됩니다. 이는 FLANN의 핵심 인덱스 중 하나입니다.

kd-트리는 L2 거리 아래에서 원시 벡터를 비교한다는 점에 주의하세요 — 해밍 거리 아래의 이진 디스크립터에는 LSH나 HBST가 적절한 구조입니다.

SLAM에서 kd-트리가 등장하는 곳

ICP와 포인트 클라우드 정합: 대응 관계 탐색 단계 — 매 반복마다 씬의 각 점에 대해 가장 가까운 모델 점을 찾는 것 — 는 3D 최근접 이웃 쿼리의 배치입니다; PCL, Open3D, libpointmatcher는 모두 kd-트리를 사용합니다(FAST-LIO2는 맵이 커질 때 재구축을 피하기 위해 증분적으로 업데이트 가능한 변형인 ikd-Tree를 구축합니다).
디스크립터 매칭: SfM과 재위치추정(relocalization) 파이프라인에서 SIFT/SuperPoint 스타일 디스크립터에 대한 근사 최근접 이웃(FLANN을 통해).
맵 쿼리: 로컬 맵 추출을 위한 반경 탐색, 법선 추정 인접 영역, 키프레임 위치 조회, 메시/서펠(surfel) 인접 탐색.

SLAM에서의 의미

최근접 이웃 탐색은 SLAM 시스템에서 가장 자주 실행되는 기본 연산 중 하나입니다 — LiDAR나 RGB-D 파이프라인의 모든 ICP 반복 안에서, 특징 파이프라인의 모든 매칭 단계 안에서, 법선 추정과 다운샘플링 같은 매핑 연산 안에서입니다. kd-트리의 동작 원리를 아는 것은 언제 이것이 올바른 도구인지(3D 점: 훌륭함; 128차원 디스크립터: 근사/포레스트 형태로만; 이진 디스크립터: 잘못된 도구) 알려주며, 그 위에 구축된 라이브러리들(FLANN의 인덱스, PCL의 검색 모듈, ikd-Tree)의 설계를 설명해줍니다. 이는 또한 반복해서 등장하는 시스템 병목이기도 합니다: 커지는 맵에 대한 재구축-대-업데이트 전략은 실시간 LiDAR 오도메트리의 아키텍처를 직접적으로 좌우합니다.

Kd-Tree

구축

최근접 이웃 탐색

차원의 저주

SLAM에서 kd-트리가 등장하는 곳

SLAM에서의 의미

관련 문서