Fast Nearest Neighbor Search Algorithm using Cached k-d Tree and Connected-Bin Search Techniques

Abstract

This thesis presents a fast Nearest Neighbor Search (NNS) algorithm for geometric data sets using a modified k-d tree. A NNS algorithm based on k-d tree structure mainly consists of two steps

forward tracking and backward tracking. We improved the computation time in both steps by using the cache and the connected-bin techniques, respectively.The first step (forward tracking) is to find the leaf node containing a query data with pre-constructed tree structure. We improved the computation time by using a cache technique. The search process of the standard k-d tree tracks from the root node to the leaf node, and employs a tentative depth-first search. In contrast, the proposed method begins to search at the appropriate leaf node (cached node) and applies a non-tentative depth-first search. If the cached node is close to the leaf node containing a query data, the tree traversal distance of the proposed algorithm is shorter than the standard algorithm’s. We also developed several techniques of what and how information is cached and reused. In most cases, data are stored in consecutive order and adjacent data points can be usually clustered. So the data point p(i) can be similar to i) the previous indexing data point p(i-1), ii) the same indexing data point q(i-1) in another data set, and iii) the NNS result of the previous iteration in the Iterative Closest Point (ICP) algorithm. Supported by these properties (Point-to-Point closeness, Set-to-Set closeness, and ICP closeness), cache technique can improve the search speed. Furthermore, we introduce a forced-sorting technique to apply the proposed search algorithm to even randomly sequenced data.The second step (backward tracking) is to unwind the recursion of the tree, to check whether nodes could contain any data that are closer to the query point than the current best, and to search and update the nearest data. We introduce a Connected-Bin search technique that searches leaf nodes only which are bounded by the node containing the query point. This can reduce the search space and improve the search time. In addition, using the concept of the Best-Bin-First algorithm, we propose two kinds of priority search algorithms i) that the connected-bin close to the query data has search priority, and ii) that the boundary close to the query data among all boundaries of the node containing the query point has search priority. We evaluated the algorithm with 3 kinds of data set (LIDAR, Kinect, and randomly generated data). The result shows that this algorithm is more efficient than other variants of the k-d tree algorithm.

이 논문에서는 3D 기하학 데이터에 적합하고 k-d tree 기반의 최근접 이웃 검색 기술의 속도를 향상시키는 방법을 제안한다. k-d tree 구조를 기반으로 하는 최근접 이웃 검색 기술은 크게 전방향 트래킹과 역방향 트래킹으로 이루어진다. 본 논문에서는 caching 기술을 이용해 전방향 크래킹의 속도를 향상 하였고, Connected-Bin 검색 기술을 이용해 역방향 트래킹의 속도를 향상 하였다.전방향 트래킹은 tree 형태의 data 구조에서 쿼리 data point를 포함하고 있는 최하단 노드를 찾는 것이다. 여기서 Cached k-d tree 기술을 이용하여 검색 속도를 향상 하였다. 일반적인 방법은 최상단 노드에서 검색을 시작하여 depth-first 방식으로 최하단 노드를 찾고, 검색하지 않은 분기 노드는 추후 역방향 트래킹을 위해 따로 저장하여 둔다. 하지만, 본 논문에서 제안한 방식은, 미리 저장된 최하단 노드에서 검색을 시작하며, depth-first 방식으로 목표 node를 찾아간다. 이때 분기 노드에 대한 저장을 할 필요는 없다. 제안된 알고리즘의 검색 경로의 길이가 일반적인 방법보다는 짧기 때문에, 전체적으로 검색속도의 향상을 가져온다.Cache 기술을 올바로 적용하기 위해서, 본 논문에서는 어떤 정보를 어떻게 저장하고, 어떻게 다시 사용할지에 대한 몇가지 방법도 제안한다. 대부분의 경우 data point들은 순차적으로 저장되게 되고, 실제 센서로부터 오는 data 들에서는 인접한 data point의 값들은 비슷한 경향이 있다. 예를 들어, data point (pi)는 이전에 색인했던 data point (pi-1)의 값과 비슷할 수 있고, 다른 data set의 같은 색인지점의 point (qi) 와도 비슷할 수 있고, 또는 Iterative Closest Point 알고리즘에서 이전에 iteration 에서의 NNS 결과와도 비슷할 수 있다. 이 세가지 특성을 이용하면, Cache 기술을 이용해 검색속도를 향상 시킬수 있다. 게다가 data point 가 순차적으로 저장되어 있지 않은 경우라도 forced-sorting 기술을 이용하면 제안된 Cache 기술을 적용할 수 있다. 역방향 검색은 전방향 검색 결과를 통해 얻은 결과보다 정확한 결과를 얻기 위해 우선 순위를 가지고 tree 구조 상에서 전체 영역을 검색 하는 것이다. 저장된 분기된 노드 리스트를 가지고, Stack 방식 (Last-in-First-Out) 으로 노드를 검색하게 된다. 본 논문에서는 소개하는 Connected-Bin 검색 기술은 해당 노드와 경계를 접하는 최하단 노드만 검색하는 방법이다. 이 방법을 위해서는 tree construction 단계에서 모든 최하단 노드는 자신과 접하고 있는 최하단 노드들의 명단을 가지고 있었다. 이 같은 방법은 검색 영역을 줄임으로써 속도를 향상할 수 있다.Best-Bin-First 검색 방법은 가장 널리 쓰이는 우선순위선택 방법이여, 본 논문에서는 이 것을 두가지 방법으로 Connected-Bin 검색 기술에 적용 해 보았다. 첫째, 모든 Connected-Bin을 query data point와의 거리를 기준으로 정렬 하여 가까운 Connected-Bin이 검색 우선순위를 가지는 방법이다. 둘째, 해당 노드의 경계면 중에서 query data point와의 거리를 기준으로 정렬하여, 가장 가까운 경계면에 접하는 Connected-Bin들이 검색 우선순위를 가지는 방법이다.제안된 알고리즘은 임의로 생성한 data를 이용해 simulation 하였으며, 실제 LIDAR (Velodyne)와 RGB-D sensor (Kinect)의 data 를 이용해 성능을 검증하였고, 기존의 다양한 k-d tree 기반 알고리즘 보다 우수한 성능을 보였다.