Rob Hess의 SIFT
1. kd-tree 란..
http://snisni.net/98
http://zupet.tistory.com/272 - Kd-Tree 구현 참고 사항
http://zupet.tistory.com/395 kd-tree <- 꼭 참고 ~~
에 있는 자료를 기반으로 하여서 정리하였습니다.
개인적으로 이해를 위해서 정리한 자료이니, 이해가 가지 않으시는 분들은 위의 사이트에서
참고하여주시기 바랍니다.
제목인 kd-tree에서 k란 다차원 인 k차원의 공간을 의미합니다.
즉 다차원 트리를 만들고 정리하는 것을 말합니다.
실제로는 binary-tree의 확장 버전으로 이해하시면 됩니다.
공간을 다루는 dB로서 문자 기반의 dB와는 다르게 됩니다.
key 값을 matching 시키는 문제이고, 공간 기반에서 검색합니다.
공간 기반의 검색이란 range 로 표현되는 질의어를 기반으로 검색한다는 뜻입니다.
spatial data는 (공간 데이터는) 점과 선, 다각형 등을 포함하고 있습니다. 이러한 공간상의 데이터를 뒤져서 원하는 값을 찾아내어야 하는데
공간 데이터를 효율적으로 처리하기 위해서는 다음과 같은 특징적 어려움을 알아야 합니다.
① First, spatial data are latge in quantity, complex in structures and relationships
첫번쨰, 공간 데이터는 크고, 복잡한 구조와 관계를 가지고 있습니다.
② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment
둘째로, 탐색 과정은 복잡한 공간 연산을 기반으로 구현됩니다. 예를들어서
교차점 탐색, 인접 물 탐색, 묶어 탐색 등등..
③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations
→ spatial indices 필요!
3번째는, 공간상에 순서를 정하는 것이 어렵다는 점이다. 그래서 일반적인 방식으로는 공간상에서 dB를 구성하는 것이 쉽지 않다.
- 공간 인덱스가 필요해진다.
1.1 kd-tree : Binary-tree based indexing
kd-tree는 multi-attribute data index를 binary search하는 tree로,
k는 표현될 데이터 공간의 차원을 가리킵니다.
각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute가 사용이 됩니다.
예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면,
홀수 depth에서는 y 좌표가 branch 방향의 기준이 됩니다..
마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없습니다.
위의 그림을 보면 제일 먼저 X값을 기준으로 중앙에 있는 A를 선택합니다.
따라서 최초 분리자는 ROOT이며 이것이 A가 됩니다.
이제 다시 A를 가지고 Y축으로 값을 분리합니다. 그럼 B와 E가 선택이 됩니다.
{
NOTE :
의문 사항 : A다음에 B와 E를 택하는 이유는 무엇일까 ?
F와 C가 되지 않고 말이지...
답 : B 가 선택이 되는 이유는 A를 중심으로 좌우를 분리하면
좌측에 B/C/D가 존재한다. 이 점에서 Y값을 기준으로 정렬해보면
B가 가운데 온다. 따라서 B가 선택이 되는 것이다.
우측은 그냥 E와 F가 있다 2개의 값이므로 아무값이나 하나 선택
한것이다.
의문사항 : 정말 아무값이나 선택해서 E일까 ??
}
B와 E에서 다시 X 축 기반으로 각각 C/D 및 F를 분리합니다.
위의 사항을 그림으로 표현하면 다음과 같습니다.
1.2 Principle
각각의 Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 됩니다.
(left, right 두 개의 child가 있습니다.→ 현재 노드 값 보다 작은가? 큰가?)
한 Node는 5개의 field로 구성되어 있습니다.
LEFT Node를 가리키는 포인터 : LOSON(작은 값을 가진 left 자식),
Right Node를 가리키는 포인터 : HISON(큰 값을 가진 right 자식),
좌표 값 (x,y,...), : 차원에 따라서 그 차원의 개수만큼 늘어납니다.
NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.),
DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).
1.3 삽입 Insertion
Tree Build에 해당합니다.
Binary search tree에서의 insertion 방법과 유사합니다.
다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것입니다.
tree의 bottom에 도달하면, 거기에 새 node를 삽입(Insertion)합니다.
2개의 함수를 먼저 정의합니다.
1) 비교 주어진 노드의 값을 비교하여 값을 반환합니다.
2) 삽입
2개의 노드 포인터가 주어집니다.
하나는 삽입해야할 즉 추가 해야 할 노드 이며,
다른 하나는 그때 참조하는 값에 해당하는 노드입니다.
Procedure KD_COMPARE(P,Q)
/* 주어진 노드 Q를 기준으로 P가 붙어야할 위치가 어딘지 판단한다.*/
value pointer node P,Q
direction D
기준값을 X축 값을 가지고 해야 한다면
{
P의 X 좌표가 Q의 X 좌표 보다 작다면
노드의 왼쪽에 붙어야 하고
아니면 오른쪽에 붙어야 한다.
}
아니면
{
P의 Y 좌표가 Q의 Y 좌표 보다 작다면
노드의 왼쪽에 붙어야 하고
아니면 오른쪽에 부터야 한다.
}
붙어야 할 방향 정보를 반환한다.
삽입 ( Insertion)
KD_INSERT(P,R)
value pointer note P : 삽입해야할 노드 이다.
reference pointer note R : 기준 노드를 의미한다.
pointer note F,T
direction Q
만약 R이 NULL 이면, 즉 기준 노드가 없다면
{
R <- P // 기준 노드는 P가 되고
DISC(P) <- 'X'; // P의 기준 값은 X축 값으로 한다고 표시한다.
}
아니면 즉 기준 노드가 있다면,
{
T <- R /*
기준 노드인 R을 임시 값으로 복사한다. 이것은
아래 트리 탐색을 위한 반복문에서 반복시 사용되는 인자를
세팅하기 위함이다.
*/
임시 노드 T가 NULL이 아니고, EQUAL_COORD(P,T) 가 아닌 동안 계속 해서
{
F <- T ; /* 직전 노드값을 기억하여 두고 */
Q <- KD_COMPARE(P,T); /* 삽입할 값과 비교하여 방향을
찾아낸다.*/
T <- SON(T,Q); /* 찾아낸 방향의 노드를 다시 꺼낸다. */
....
/* 꺼낸 노드가 NULL이 아닐때 까지 반복...*/
}
만약 T가 NULL 이면, /* 즉 트리최종 말단까지 도착하면 */
{
SON(F,Q) <- P; /* 직전노드의 찾아낸 방향에 P를 삽입한다.
DISC(P) <- NEXT_DISC(F); /* P의 참조 기준 값은 직전 노드의 다음 값이 된다.
즉 F의 참조 기준 값이 X였다면, Y가 되고 Y였다면, X (혹은 3차원일 경우 Z) 가 된다.
*/
}
}
차근 차근 따라가면서 읽어보면 이해 할수 있는 내용입니다.
1.4 탐색 Search
Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다.
여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐.
참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데,
예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다.
Region Search는 Euclidean distance를 이용하여 구할 수있다.
node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면,
우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다.
그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라,
한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게
맞는지 확인이 필요하다.
우선 다음과 같이 트리가 준비되어 있다고 가정하고요
(88,6)을 기준으로 3개의 점 범위 내에 있는 모든 도시를 찾아라 라고 한다면
(85~91 , 3~9)까지가 된다.
따라서 좌측 상단은 ( 85,3 ) 이 되고 우측 하단은 (91,9)가 된다.
우선 처음에 찾는 값은 85,3으로 찾는다. 기준값과 비교해서 오른쪽에 해당함을 확인할 수 있다.
91,9를 가지고 MOBILE을 참조값으로 하여 찾으면 왼쪽 값이 나온다.
이때 사용되는 참조 변수는 Y축 값인 9이다.
마지막 노드의 값이 NULL이고,
좌우 범위 내에 들어간다면, OK이다.
최종 그림은 아래와 같이 된다.
붉은색 점선 원이 탐색 범위이고, 마이애미가 범위내에 들어감을 확인할 수 있다.
1.5 삭제 : Deletion
앞에 insert나 search는 BST와 비슷하기 때문에 쉽지만 , deletion은 복잡합니다.
각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에,
모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다.
kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고,
아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨킵니다.
이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까?
오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다.
그러면 다음의 예를 보자.
그림과 같이 A가 최상위 노드로 되어 있는 상태이다.
여기서 하나의 노드를 삭제한다. 하필이면 A를 삭제하기로 한다.
그럼 A가 삭제된 상태에서 노드를 구성하는 동작을 하게 된다.
우선 A가 삭제되었으므로, A의 X축 값에서 가장 가까운 노드의 값을 선택한다.
예제의 경우 C가 되고 우연히도 C가 A의 바로 밑에 있으므로 개념상 C를 올린다.
{
의문 사항 :
최소값이라고 하였는데 이것을 가장 가까운 값으로 해석해야 하는것인지 궁굼하다.
}
그럼 오른쪽 개념처럼 기준선이 움직인 셈이 된다.
그럼 C를 기준으로 최소 Y값은 우연히도 D이므로 D를 한단계 끌어올린다.
그럼 개념상 오른쪽 그림처럼 된다.
D에서 X 값으로 최소값은 H이므로 이것을 선택한다. 이때 H는 한단계 더 하위 계층이므로 이것을 끌러 올린다.
이때 I가 G보다 X축 값이 작으므로 왼쪽으로 붙는다.
1.6 장단점
kd-tree는 partial matching search에 유용하지만, empty space가 없고,
point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다.
kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다
1.7 응용처
응용하는데 중에서 쉽게 찾을 수 있는 것은 폴리곤의 분류이다.
3차원 그래픽도 당연히 다차원이므로, 공간세어 객체를 뿌려놓고 찾아서, 렌더링을 해야 하는데 이럴때
kd-tree를 사용한다.
당연히 속도 문제가 이슈가 되기 때문에 여러가지 방법과 논문이 제안되고 있다.
삭은이 님의 블로그에서 보면
논문을 하나 추천하고 있다.
http://www.cgg.cvut.cz/members/havran/ARTICLES/ingo06rtKdtree.pdf
