基于最小生成树的多视图特征点快速匹配算法

Fast matching algorithm of multi-view feature points based on minimal spanning tree

针对图像特征点匹配中计算效率较低且误配率较高的问题,提出了一种在两视图匹配中引入最小生成树的新算法.该方法主要运用最小生成树构建匹配代价最小的图像对,首先通过对输入的多幅图像进行特征点提取,对生成的特征点采用基于欧式距离的两视图匹配,进一步构建最小生成树以生成最短特征点匹配轨迹,从而完成匹配.测试结果表明:最小生成树的引入使得大多数特征点匹配过程只在相关图像中运行,且能找出匹配代价最低的匹配路径,在保证匹配准确性的情况下,计算时间开销约为传统算法的20%,保证了图像匹配的实时性.

To solve the problem of low computation efficiency as well as the high rate of error matching in image feature points matching,an algorithm was proposed.The minimal spanning tree was mainly used to build image pairs with least matching costs based on two views.Firstly,the feature point was extracted from many images,and two views matching was used based on Euclidean distance.Then the minimal spanning tree was built to generate the shortest path of feature point matching to complete the matching.Experimental results show that the introduction of the minimal spanning tree makes most of the feature points matching process only run in the relevant images and matching of the lowest cost path can be found.On the premise of guarantee the matching accuracy,computation time costs of this algorithm is only about 20% of the traditional algorithm,which ensures the real-time image matching.