Abstract: In order to solve the SIFT algorithm, and the algorithm efficiency is not high, POKD-tree algorithm （partition optimization KD tree search algorithm） is proposed. Firstly, image feature points are extracted using SIFT algorithm, the largest span direction in the image feature point set in X and Y direction is the partition line direction, and calculate the centroid of image features point set, through the partition to partition the image centroid line; using Euclidean distance between feature points in image matching, the first corresponding match, at the same time in order to solve the partition error, then cross search after the corresponding search. Finally, the experimental results show that POKD-tree algorithm is superior to BBF algorithm and RKD-tree algorithm in matching efficiency.

Key words: POKD-tree algorithm, partition line, corresponding match, cross search, matching efficiency

摘要： 为解决SIFT算法计算复杂，且算法效率不高的问题，提出了POKD-tree算法（分区优化kd树搜索算法）。首先，利用SIFT算法提取图像的特征点，以图像特征点集在X和Y方向中跨度最大的方向为分区直线的方向，计算图像特征点集的质心，用通过质心的分区直线来进行图像分区；采用欧式距离对图像进行特征点匹配，首先进行对应搜索匹配，同时为了解决分区误差，在进行对应搜索之后再进行交叉搜索。通过实验证明，POKD-tree算法在匹配的效率上要优于BBF算法和RKD-tree算法。

关键词: POKD-tree算法, 分区直线, 对应搜索, 交叉搜索, 匹配效率