KD-Tree
KD-Tree 위키피디아
k-d tree(k-dimensional tree)는 컴퓨터 비전 분야에서 "space-partitioning data structure for organizing points in a k-dimensional space"을 의미한다.
k-d tree는 모든 노드들이 k-차원 point로 구성된 이진트리이다.
leaf노드가 아닌 모든 노드들은 개념적으로 k-차원 공간을 둘로 분할하는 초평면(hyperplane)을 생성하는 것으로 생각할 수 있다.
KD-Tree를 만드는 방법은 아래와 같다.
1. 1번째 좌표값을 이용해 값들을 정렬.
2. 그 중 중간값을 부모노드로 설정하고 그보다 1번째 좌표값이 작은 점들은 왼쪽, 큰 점들은 오른쪽으로 내려보냄.
3. 양쪽에서 각각 2번째 좌표값을 이용해 값들을 정렬.
4. 중간값을 부모노드로 설정, 2번째 좌표값이 부모노드보다 작은 점들은 왼쪽, 큰 점들은 오른쪽으로 내려보냄.
5. 3번째 좌표값을 이용해 반복...
6. k번 반복해서 k번째 좌표값을 이용해 정렬한 다음에는 다시 1번째 좌표값을 이용해 반복.
7. 더이상 나눌 노드가 없어지면 종료.Nearest Neighbor search
k차원 점이 존재할 때, KD-Tree에 저장된 노드들 중 가장 가까운 점을 효율적(평균 시간복잡도 )으로 찾을 수 있다.
1. 루트 노드에서 시작. 루트노드와 point의 1번째 좌표값을 비교, 작으면 왼쪽, 크면 오른쪽으로 내려감.
2. 현재 노드와 point의 2번째 좌표값을 비교 작으면 왼쪽, 크면 오른쪽으로 내려감.
3. 리프노드에 도달할떄까지 반복. 리프노드에 도달하면, 해당 노드와 point 사이의 distance를 기록.
current best와 비교해 더 가깝다면 값을 갱신.
4. point가 지나온 노드들을 거슬러올라가면서 아래의 과정들을 거친다.
4-1 거슬러온 노드와 point의 distance가 current best보다 더 가깝다면 갱신.
4-2 분할된 평면 반대편에 current best보다 더 가까운 점이 있는 지 아래 과정을 통해 확인.
4-2-1 현재 노드에 의해서 생성되는 hyperplane과 point 사이의 distance와 current best를 비교.
current best가 더 크다면, 반대편에 nearer point가 존재할 가능성이 있다.
반대편 branch를 따라 내려가면서 2번 과정을 수행함.
4-2-2 current best가 더 작다면 반대편 branch는 고려하지 않고 4번 과정을 반복적으로 수행.
5. root node까지 해당 과정들이 모두 끝나면 search가 종료됨.따라서 두 점군이 있을 때, KD-Tree를 이용해서 Nearest Neighbor Association을 효율적으로 수행할 수 있다.
