基于kd树的海量图像匹配技术

《基于kd树的海量图像匹配技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于KD树的海量图像匹配技术　　摘要：针对海量图像匹配的速度瓶颈问题，提出一种结合图像SIFT特征和KD树搜索的图像匹配算法，并建立了适应有限内存环境的大型KD树混合存储模式。实验结果表明，该方法能显著提高图像搜索速度和图像库的可扩展性，查准率和查全率也明显高于其他搜索方法。关键词：图像匹配；特征提取；KD树；近似最近邻搜索中图分类号：TP391.4文献标志码：A文章编号：1006-8228（2014）07-40-03Abstract：Todealwiththeperformancebottleneckprobleminmassivepairwiseimagematchin

2、g，animagematchingalgorithmbasedonKD-treeisproposed，withahybridapproachtoKD-treeconstructionunderamemoryconstraint.Theexperimentalresultsindicatethattheproposedmethodincreasesimagesearchingspeedandtheextensibilityofimagelibrarygreatly.Ithasbetterperformancethanothersearchmethods，intermsofpr

3、ecisionandrecallofimagematching.Keywords：imagematching；featureextraction；11KD-Tree；approximatenearestneighborsearching0引言图像匹配是图像处理和计算机视觉领域的重要内容，是图像查询、图像拼接、运动恢复结构等应用的核心步骤，也是最耗时的一个步骤。对于海量图像数据，匹配过程往往成为效率的最大瓶颈。本文提出一种结合图像SIFT特征[1]和KD树[2]搜索的图像匹配方法，并针对海量图像处理建立了一种大型KD树混合存储模式，基于该技术，图像搜索的时间复杂度大大降低，在

4、同样的内存限制下，可索引更多的数据，有效提升了图像库的可扩展性，查准率和查全率也明显高于其他搜索方法。1图像特征提取在基于特征的图像匹配技术中，首要任务是自动提取稳定可靠的图像特征。2004年Lowe提出了尺度不变特征变换（SIFT，ScaleInvariantFeatureTransform）算法，先建立图像的尺度空间表示，然后在尺度空间中搜索图像的极值点，由极值点建立特征点的描述向量。SIFT算法提取的图像特征是图像的局部特征，其对图像的旋转、缩放保持不变性，对光照改变和摄像机角度变化具有部分的不变性。以下给出算法实现的主要过程。步骤211关键点定位。检测到的极值点作为

5、侯选点，对位置、尺度、弯曲度等做拟合，筛除所有低对比度和定位差边缘附近的点，同时对尺度空间函数D（x，y，σ）做泰勒展开得到关键点，计算二阶Hessian矩阵得出主曲率。步骤3设定主方向并建立描述向量。将以特征点为中心的16×16邻域分成4×4的像素块，建立梯度方向直方图，每个直方图包含8个特征，得到4×4×8=128维的特征描述向量。实验表明，计算图像特征点的128维描述向量占用了SIFT算法80%以上的计算时间，为提高算法的实时性，采用PCA（主成分分析）降维技术加以改进，不使用梯度直方图而用主成分分析法将梯度面片归一化，将128维描述向量降低到36维，因而大大减少了计

6、算量。2基于KD树的特征匹配利用SIFT特征，将查询图像的特征描述向量与图像库的所有特征进行比较，特征匹配数目最多的几张图像即为查询结果。特征描述向量的匹配性采用欧氏距离度量，匹配过程相当于在两个特征集合中搜索距离最近的特征点的过程。常用的搜索过程有两种：一种是线性扫描，将一个特征描述向量与数据库中的所有向量逐一比较，这种方法实现简单但效率较低，时间复杂度为0（N），N为数据库中向量的数目；另一种是先建立数据索引，再对特征描述向量进行匹配。2.1KD树的构建11KD树是K维二叉索引树，是用于多维检索的树形数据结构。它的每一层将空间分成两个子空间，顶层结点按一维划分，下一层结

7、点按另一维划分，以此类推，直至一个结点中的数据量少于设定的上限为止。KD树的搜索时间复杂度为0（log2N），其具有如下性质：⑴若它的左子树不为空，则左子树上所有结点第d维的值均小于它的根结点第d维的值；⑵若它的右子树不为空，则右子树上所有结点第d维的值均大于等于它的根结点第d维的值；⑶它的左右子树也分别是KD树。计算图像库中所有SIFT特征描述向量在每个维度上的数据方差，共得到36个方差，KD树的维度分区沿着数据项方差最大的方向，该方向上数据最分散，进行空间分割会有较好的分辨率，有利于提高发现最近邻的可能性。2.