컴퓨터 비전 - 24. kd 트리를 이용한 매칭

순수 매칭 알고리즘

- 첫 영상 특징 벡터들에 대한 둘째 영상의 최근접 이웃 구함

=> 매칭쌍들을 mlist에 모음

- 아래의 그림은 이진 검색

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

 

kd트리

- 이진 검색트리의 예시

- 왼쪽 자식 노드는 기준 노드보다 작고 오른쪽 자식 노드는 기준 노드보다 큼

- 검색 키 : kd 트리에서 찾아야될 노드의 값

 

 

kd 트리 생성

- 특징

 1. 검색키는 스칼라가 아니라 벡터

 2. 검색 키에 가장 가까운 최근접 이웃 노드를 찾아야 함 

- n개의 특징벡터 X로 kd 트리를 만드는 경우, 하나의 특징 벡터 x는 d차원 벡터

- 루드 노드가 X를 두 부분 집합 X_left와 X_right로 분할

 -> 자식 노드에서도 계속 분할을 수행 => kd 노드 생성

https://www.snisni.net/98

 

 

kd 트리에서의 최근접 이웃 탐색

- 목표 : 특징 벡터 x입력이 주어질때 최근접 이웃을 찾기

- 입력 : x = (20,20)

- 과정 : 루트노드에서부터 분할해 나가며 입력에 가까운 노드를 찾아나감 -> 입력 벡터 x는 노드C에 최근접이웃

https://www.snisni.net/98