[영상처리] 이미지매칭(3) - Nearest Neighbor Search (with kd-tree)

 

Nearest Neighbor Search - Naive Algorithm

영상을 매칭할 때, 매칭 쌍으로 지정하기 위해 최근접 이웃(Nearest Neighbor)을 구하면서 생각할 수 있는 가장 기본적인 알고리즘을 생각해봅시다.

첫 번째 영상의 특징벡터 ai(1<=i<=m), 두 번째 특징벡터 bj(1<=j<=n)라고 할 때

첫 번째 영상의 특징 벡터를 하나씩 두 번째 영상의 특징벡터에 하나씩 모두 매칭하는 경우, 즉 모든 쌍을 일일이 검사하는 경우 매칭시도횟수는 mn번이 됩니다.

따라서 해당 알고리즘은 특징벡터의 크기(m,n)가 크고 실시간 처리가 필요한 응용에는 적절하지 않습니다.

---

kd트리의 직관

오늘 다룰 주제는 어떻게하면 Nearest Neighbor Search를 빨리 할지가 주된 관심사로,

적절한 자료구조를 설계해서 특정 벡터 집합을 미리 인덱싱 하면 훨씬 빠른 시간 안에 최근접 점을 찾을 수 있습니다.

오늘은 이 적절한 자료구조의 예시로 "kd트리"에 대해서 알아봅시다.

 

kd트리 자료구조

먼저 kd트리의 정의를 살펴봅시다.

The k-d tree is a binary tree in which every leaf node is a k-dimensional point.

kd트리는 이진트리의 일종입니다. 이진검색트리에 대해서 잠깐 알아봅시다!

이진검색트리(Binary Search Tree)

루트 노드를 기준으로, 왼쪽 서브트리에 있는 모든 노드는 루트값보다 작고, 오른쪽 서브트리에 있는 모든 노드는 루트값보다 큽니다.

재귀 과정을 통해 검색 키를 빠른 속도로 찾아 낼 수 있습니다.

이진검색트리가 평형을 이룬다면(왼쪽과 오른쪽 트리의 크기가 대략 같다면), O(log(n))시간에 검색을 마칠 수 있습니다.(n은 노드의 개수)

 

하지만 이런 이진검색트리를 매칭문제에 바로 적용하기에는 다음과 같은 문제가 있습니다.

• 검색키 v가 하나의 값이 아니라 여러개의 실수로 구성된 벡터이다.
• v와 같은 값을 갖는 노드를 찾는 것이 아니라 v와 가장 가까운 최근접 이웃 노드를 찾아야 한다.

따라서 이진검색트리를 그대로 적용하는 것은 불가능합니다. 이제, kd트리로 가봅시다.

---

kd트리

kd트리는 위의 두 문제를 해결할 수 있도록 BST를 확장한 기법입니다. kd트리로 검색을 하기 앞서 kd트리를 만들어 봅시다.

 

kd트리 만들기

n개의 특징벡터 X={x1,x2...xn}을 가지고 kd 트리를 만든다고 합시다. (하나의 특징벡터는 x=(x1,x2,...xd)와 같이 표현되는 d차원 벡터)

kd트리

다음은 2차원 벡터 (d=2)와 10개의 특징벡터 X={x1:(3,1), x2:(2,3), x3:(6,2), x4:(4,4), x5:(3,6), x6:(8,5), x7:(7, 6.5), x8:(5,8), x9:(6,10), x10:(6,11)}를 가지고 kd트리를 만든 예시입니다.

(kd트리는 하나의 벡터가 하나의 노드가 됩니다.)

---

kd트리의 분할기준

루트노드는 X를 두개의 부분집합 xleft와 xright로 분할합니다. 이때 분할의 기준을 선택하는 일이 중요합니다.

 

두 가지 기준을 선택해야 하는데,

1. 첫 번째로 d개의 차원(축) 중에 어느 것을 쓸 것인지 선택해야 합니다.

(이때 분할효과를 극대화 하기 위해 각 차원의 분산을 계산한 후 최대 분산을 갖는 축 k를 선택)

위 예시에서 두개의 차원은 각각 1: (3, 2, 6, 4, 3, 8, 7, 5, 6, 6), 2: (1, 3, 2, 4, 6, 5, 6.5, 8, 10, 11)의 값을 갖고 있고,

각 분산을 구해보면 3.4, 9.9로 2번째 차원의 분산이 더 큰 것을 볼 수 있습니다. 따라서 예제의 k값은 2가 됩니다.

 

2. 축을 선택한 이후 n개의 샘플 중 어느 것을 기준으로 x를 분할할 것인지 결정합니다.

이때 Xleft와 Xright의 크기를 같게 하여 균형잡힌 트리를 만들기 위해 X를 차원 k로 정렬하고 그 결과의 중앙값을 기준으로 삼게됩니다.

 

2번째 차원을 기준으로 X를 정렬해서 이를 X'라고 하면,

X' = {x1:(3,1), x3:(6,2), x2:(2,3), x4:(4,4), x6:(8,5), x5:(3,6), x7:(7, 6.5), x8:(5,8), x9:(6,10), x10:(6,11)}이 됩니다.

 

X'의 중앙값 x5를 기준으로 좌우를 분할하면

X_left  =  {x1:(3,1), x3:(6,2), x2:(2,3), x4:(4,4), x6:(8,5)},      X_right  =  {x7:(7, 6.5), x8:(5,8), x9:(6,10), x10:(6,11)}가 됩니다.

 

각각에 같은 과정을 재귀적으로 반복하면 kd트리가 완성됩니다.

---

kd트리의 표현

kd트리가 나눈 공간은 어떻게 생겼을 까요? kd트리가 나눈 공간을 시각적으로 살펴봅시다.

 

kd트리는 맨 처음 분할된 차원을 기준으로 한 깊이 내려갈 때 마다 선택되는 차원 축을 순서대로 바꿔줍니다.

 

예제를 위의 설명을 바탕으로 공간적으로 표현해보면 다음과 같습니다.

처음 선택된 두번째 차원을 기준으로 공간을 크게 한 번 나누고, 한 깊이 내려갈때마다 기준을 바꾸어 나눈 결과입니다.

---

kd트리로 Nearest Neighbor 탐색

이제 kd트리를 만드는 방법을 알아보았으니 이 트리를 통해 빠르게 Nearest Neighbor를 탐색하는 방법을 알아봅시다.

 

최근접 이웃 탐색

새로 들어온 노드 x의 최근접 노드를 알아보기 위해서,

분할 기준에 따라서 노드를 따라가 마지막 리프노드의 분할공간을 찾습니다.

해당 공간 안에 있는 특징벡터들은 검색하려는 x의 최근접일 가능성이 큽니다. (반드시 최근접 아닐 수 있음)

왜냐하면 분할 평면 너머에 더 가까운 점이 있을 수 있기 때문입니다.

현재 분할 평면에서 가장 가까운 점까지의 거리 보다 주변 분할 평면까지의 거리가 더 가까우면, 해당 분할평면을 탐색하게 됩니다.

 

최근접 이웃을 찾는 것은 일반적으로 분석이 까다롭지 만 무작위로 분포 된 점의 경우 평균 O(logn) 연산입니다.

하지만 kd트리에서는 단말노드에 도달한 이후 백트래킹으로 추가적인 탐색을 수행합니다. (주변 분할 평면 추가 탐색)

이에 따라 고차원 공간에서 차원의 저주로 인해 알고리즘이 저차원 공간보다 훨씬 더 많은 분기를 방문해야합니다. 

10차원 이상이 되면 모든 특징벡터와 비교를 수행하는 첫 Naive Algorithm과 비슷해져 낮은 효율을 보입니다.

 

근사 최근접 이웃 탐색

위 문제에 대한 대책으로 최근접 이웃 대신, "근사" 최근접 이웃을 찾게 됩니다.

백트래킹할 때 거리가 가까운 노드부터 시도할 수 있도록 스택을 사용하는 대신 우선순위 큐를 사용하여 거리가 가까운 노드부터 시도할 수 있도록 합니다.

우선순위 기준은 새로들어온 노드x로부터의 거리를 사용합니다.

거리가 가까우면 최근접 이웃이 놓여있을 가능성이 크기 때문에 해당 전략은 효과적이라고 합니다.

해당 알고리즘을 best-bin-first search(최적 칸 우선 탐색)라고 부릅니다.

또한 매개변수를 사용해 조사횟수를 제한해 해당 횟수까지 찾은 것을 답으로 하여 빠른 매칭을 성공시킬 수 있습니다.

 

그러나 반드시 최근접 이웃을 찾아야 하는경우,

근사 최근접 이웃 알고리즘대신 최근접 이웃 알고리즘을 GPU를 사용하여 병렬처리하는 등의 방식으로 속도를 높이는 방식으로 사용해야 합니다.

---

kd트리 Code Implementation - python

해당 코드는 kd트리 wiki에서 가져온 코드입니다.

point_list 부분을 변경하여서 여러 실험을 해보며 kd트리에 대한 직관을 얻어보면 좋을것 같습니다 :D

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple("Node", "location left_child right_child")):
    def __repr__(self):
        return pformat(tuple(self))

def kdtree(point_list, depth: int = 0):
    if not point_list:
        return None

    k = len(point_list[0])  # assumes all points have the same dimension
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k

    # Sort point list by axis and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    # Create node and construct subtrees
    return Node(
        location=point_list[median],
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1 :], depth + 1),
    )

def main():
    """Example usage"""
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    print(tree)

if __name__ == "__main__":
    main()

 

kd트리 구현이 존재하는 오픈소스 라이브러리들입니다.

• ALGLIB
• SciPy
• scikit-learn

 

Reference

오일석(2014), 컴퓨터 비전 Computer Vision, 한빛아카데미

kd트리-wiki

kd트리-youtube