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

张小莉

摘 要： 针对海量图像匹配的速度瓶颈问题，提出一种结合图像SIFT特征和KD树搜索的图像匹配算法，并建立了适应有限内存环境的大型KD树混合存储模式。实验结果表明，该方法能显著提高图像搜索速度和图像库的可扩展性，查准率和查全率也明显高于其他搜索方法。

关键词： 图像匹配； 特征提取； KD树； 近似最近邻搜索

中图分类号：TP391.4 文献标志码：A 文章编号：1006-8228（2014）07-40-03

Abstract： To deal with the performance bottleneck problem in massive pairwise image matching， an image matching algorithm based on KD-tree is proposed， with a hybrid approach to KD-tree construction under a memory constraint. The experimental results indicate that the proposed method increases image searching speed and the extensibility of image library greatly. It has better performance than other search methods， in terms of precision and recall of image matching.

Key words： image matching； feature extraction； KD-Tree； approximate nearest neighbor searching

0 引言

图像匹配是图像处理和计算机视觉领域的重要内容，是图像查询、图像拼接、运动恢复结构等应用的核心步骤，也是最耗时的一个步骤。对于海量图像数据，匹配过程往往成为效率的最大瓶颈。本文提出一种结合图像SIFT特征[1]和KD树[2]搜索的图像匹配方法，并针对海量图像处理建立了一种大型KD树混合存储模式，基于该技术，图像搜索的时间复杂度大大降低，在同样的内存限制下，可索引更多的数据，有效提升了图像库的可扩展性，查准率和查全率也明显高于其他搜索方法。

1 图像特征提取

在基于特征的图像匹配技术中，首要任务是自动提取稳定可靠的图像特征。2004年Lowe提出了尺度不变特征变换（SIFT，Scale Invariant Feature Transform）算法，先建立图像的尺度空间表示，然后在尺度空间中搜索图像的极值点，由极值点建立特征点的描述向量。SIFT算法提取的图像特征是图像的局部特征，其对图像的旋转、缩放保持不变性，对光照改变和摄像机角度变化具有部分的不变性。以下给出算法实现的主要过程。

步骤2 关键点定位。检测到的极值点作为侯选点，对位置、尺度、弯曲度等做拟合，筛除所有低对比度和定位差边缘附近的点，同时对尺度空间函数D（x，y，σ）做泰勒展开得到关键点，计算二阶Hessian矩阵得出主曲率。

步骤3 设定主方向并建立描述向量。将以特征点为中心的16×16邻域分成4×4的像素块，建立梯度方向直方图，每个直方图包含8个特征，得到4×4×8=128维的特征描述向量。

实验表明，计算图像特征点的128维描述向量占用了SIFT算法80%以上的计算时间，为提高算法的实时性，采用PCA（主成分分析）降维技术加以改进，不使用梯度直方图而用主成分分析法将梯度面片归一化，将128维描述向量降低到36维，因而大大减少了计算量。

2 基于KD树的特征匹配

利用SIFT特征，将查询图像的特征描述向量与图像库的所有特征进行比较，特征匹配数目最多的几张图像即为查询结果。特征描述向量的匹配性采用欧氏距离度量，匹配过程相当于在两个特征集合中搜索距离最近的特征点的过程。常用的搜索过程有两种：一种是线性扫描，将一个特征描述向量与数据库中的所有向量逐一比较，这种方法实现简单但效率较低，时间复杂度为0（N），N为数据库中向量的数目；另一种是先建立数据索引，再对特征描述向量进行匹配。

2.1 KD树的构建

KD树是K维二叉索引树，是用于多维检索的树形数据结构。它的每一层将空间分成两个子空间，顶层结点按一维划分，下一层结点按另一维划分，以此类推，直至一个结点中的数据量少于设定的上限为止。KD树的搜索时间复杂度为0（log2N），其具有如下性质：

⑴ 若它的左子树不为空，则左子树上所有结点第d维的值均小于它的根结点第d维的值；

⑵ 若它的右子树不为空，则右子树上所有结点第d维的值均大于等于它的根结点第d维的值；

⑶ 它的左右子树也分别是KD树。

计算图像库中所有SIFT特征描述向量在每个维度上的数据方差，共得到36个方差，KD树的维度分区沿着数据项方差最大的方向，该方向上数据最分散，进行空间分割会有较好的分辨率，有利于提高发现最近邻的可能性。

2.2 KD树近似最近邻搜索

KD树对于给定的多维目标点，进行快速二分查找得到其近似最近邻点，搜索过程如下：

⑴ 根据输入的k维数据点建立KD树；

⑵ 利用优先队列，用目标点搜索比较整个KD树，找到m个最近邻的点，从其根结点扫描到叶结点，错过的结点放入优先队列，再从队列中取出当前维度上距离最小的点，重复扫描到叶子结点，直到队列为空或扫描次数达到设定上限；

⑶ 分别计算最近邻点和次近邻点到目标点的欧氏距离，若最近距离除以次近距离的比值小于设定的比例阈值，则选择该最近邻点作为搜索结果，若没有找到，则返回空。

3 大型KD树混合存储模式

传统的KD树要求将所有的数据项都加载到内存，这将限制海量图像数据匹配的应用规模，为此，本文提出了一种大型KD树混合结构，来解决有限内存环境下的图像匹配问题。我们将所有图像的SIFT特征描述向量及对应的图像ID信息保存为一个外部文件F，后续过程将针对文件F来实施基于硬盘的KD树构造和最近邻搜索。

3.1 基于硬盘的KD树构造

外部文件F中存有N个36维数据项，需构造一棵KD树来索引这些数据项，构造过程中数据项被加载到内存执行，目的是根据数据项计算并选择分区方向轴，且计算这些数据项在分区轴上投影的中值点。假设有限内存环境下最多只有m个数据项可被加载到内存，则改进后的大型KD树混合结构如图1所示。

图1假设m=N/4，即在构造KD树时，任何时候最多只有N/4的数据项可被加载到内存。在树的最上面两层（黑色结点），每个结点分支下索引的数据项数量超过了m，因此这些结点在硬盘上构造；第三层以下（白色结点），每个结点分支下的索引数据项数量不到m，可在内存中构造。由于KD树是一种平衡二叉树，可以推知第0层（根结点）到第log2（N/M）-1层中每个结点索引的数据项都超过m，所以对这些结点使用基于硬盘的方法来构造。具体来讲，构造第0到第log2（N/M）-1层时，随机抽样硬盘上的m个数据项即一个数据子集，加载到内存后进行近似分区轴操作，分区轴选择采样数据项具有最大差异的坐标轴。计算数据项投影并选择中间值时，为保持KD树的平衡，当前结点下所有数据项应被平分，外部文件F中所有相关数据项都要被计算，但内存中只存放计算出的数据项投影，因此不会超出容量限制。当递归构造到达log2（N/M）层时，KD树转入内存构造过程，所有相关数据项都可被加载到内存中构造当前结点的整个子树。递归过程采用深度优先的方式，一个结点的整个子树构造后，分配给这些数据项的内存被立即释放。KD树叶结点的内容不是特征向量数据，而是指向硬盘上数据项的一个指针。

上述KD树的混合构造方式会导致顶层分区轴的选择可能不是最优的，但经过试验证明，这种近似的影响很小。在区间{N，0.9N，…，0.1N}变换m的值，由此产生的大型KD树结构相同，直到m减少到0.01N时，构造结果才出现不同。这是因为：首先，基于硬盘的过程只用于构建KD树的上层，即使m小到N/16，近似也只发生在最上面4层的15个结点；其次36维特征向量是分布在一个低维特征空间上的，维度之间的差异性本来就比较大，因此特征向量在KD树的上层空间差异足够明显，足以抵消近似分区的影响。

3.2 大型KD树的实现

KD树是平衡二叉树，因此可用数组来表示：树中的结点以深度优先的方式存储在一个有2N个元素的数组中，其中N是被KD树索引的数据项的数量；结点i的两个子结点位于数组中2i和2i+1的位置。树的每个内结点上保存分区轴编号（1个字节，存储整数1到36）和截断值（4字节浮点数）。每个叶结点上保存指向特征描述向量的索引（每个索引4字节）。内结点的数量和叶结点的数量都小于等于N，KD树总共用约（1+4）N个字节存储内结点和4N个字节存储叶结点，共占用约9N字节的内存。被KD树索引指向的特征描述向量大小为144N个字节（每个SIFT特征描述向量有36个浮点数）。通过将特征描述向量驻留在硬盘上，KD树的内存消耗从（144+9）N减少到9N。

在1GB内存环境中，一个传统KD树要求所有的描述向量驻留在内存中，只能索引约700万描述向量（不到5000张常规尺寸的图像），而本文的大型KD树可以索引超过1亿个描述向量（约8万张图像），系统的可扩展性显著提高。

3.3 基于硬盘的近似最近邻搜索

传统的最近邻搜索将数据库所有特征描述向量驻留于内存，以便快速地随机存取（每次耗时10-4ms）并计算距离。大型KD树索引的特征向量存放于硬盘，如果仍按随机访问的方式来存取数据（每次耗时10ms），最近邻搜索的效率会很低。假设每个查询特征向量最近邻搜索s个数据库特征后停止，当s=200时，处理该查询队列会在I/O上花费2秒，当处理1张有1500个特征点的图像时，查询队列的存取时间将达到50分钟，这甚至比依次精确比对图像库的速度还要慢。

改进后的硬盘最近邻搜索将单个的硬盘随机访问优化为批量顺序访问硬盘[3]（如图2所示）。每次批量处理Q个查询图像，每个查询图像的每个特征点从大型KD树获取200个候选匹配特征。在此过程中不执行候选特征匹配的距离测试，而是先放入内存中缓冲，因而没有触发随机硬盘访问。当搜索完所有Q个查询图像的候选匹配特征后，对指向硬盘上特征向量的索引进行统一排序，并按硬盘顺序扫描来对其访问。

试验中，笔者根据经验设置Q=100，共有100×1500×200=3000万个候选匹配特征，顺序扫描外部文件F大约需要50秒。一个特征描述向量的平均硬盘访问时间从单个随机访问时的10 ms，下降为50秒/3000万≈2×10-3ms。相应地，查询一张图像的I/O处理时间从50分钟显著下降为0.5秒。增大Q的值将进一步减少特征描述向量的平均访问时间，但也同时增加了用于KD树遍历和数值计算的内存消耗，查询处理的瓶颈从硬盘转移到内存，因此Q的值不宜无限增加。

对所有候选匹配特征进行距离测试后，可获得查询图像队列Q和数据库图像的一组鲁棒特征匹配，最终通过匹配特征的数量来确定两幅图像的相似性。

4 实验结果与分析

为评估大型KD树的图像匹配性能，本文比较了大型KD树与广泛采用的词汇树方法[4]在图像匹配时的查准率和查全率，证明了大型KD树的优越性能。

4.1 实验环境

本文的实验对象为一个有1万张图像的图像库，每个图像包含约1500个SIFT特征，每个特征是一个36维的向量，图像库共有1500万个特征，存储该图像库特征描述向量的外部文件占用了1500万×144≈2GB硬盘空间。

⑴ 大型KD树的近似图像匹配。近似图像匹配过程参照第3节的方法，构造大型KD树时，假设内存限制m=0.1N，其中N是图像库特征描述向量的数量。在最近邻居搜索中，设置s=200（每次查询访问的数据库特征数量）和Q=100（一批处理的查询图像数量）。匹配结果由两个图像间匹配的特征数量决定。

⑵ 基于词汇树的近似图像匹配。作为对比，本文同时使用广泛应用的词汇树方法进行近似图像匹配。把所有图像的SIFT特征描述向量进行分层聚类后构造成一个分支系数为10、深度为6的词汇树，从而获得一个有106=100万个视觉单词的字典。查询特征描述向量通过遍历词汇树量化成视觉单词，每个图像被转换为一组视觉单词，生成一个100万维的稀疏特征向量。最后，以两幅图像词汇特征向量之间的曼哈顿距离来判断图像相似度，距离越远，相似度越小。在计算距离时，特征向量里的每一维特征描述子都用对应视觉单词的熵加以权重。

4.2 实验结果

对实验图像库分别使用精确匹配和近似匹配，统计数据如表1所示。可以看到近似匹配获得的匹配特征比精确匹配少了约90%，但近似匹配的速度快了约400倍，因为它只检索了精确匹配特征对的一小部分，约0.02%。在实际应用中，近似匹配时相对稀少的匹配特征数量并不影响匹配效果，因为两幅真正相似的图像往往有几百个匹配的特征，而两个不相似的图像间最多只有几个匹配的特征，所以即使失去了很多匹配特征，这种方法仍然能够把相似和不相似的图像配对区分开。

5 结束语

针对海量图像匹配的效率瓶颈，本文提出大型KD树混合存储模式及其近似最近邻搜索方法，有效地减少了图像特征匹配的计算量，提高了图像匹配的速度和图像库的可扩展性。除SIFT特征外，该技术同样适用于其他图像特征的匹配，甚至适用于其他类型的海量多维信息匹配应用。这一技术方法具有广泛的应用价值。

参考文献：

[1] 李宏荣，李晓明.基于SIFT，PCA-SIFT和SURF特征检测方法的研究[J].太原师范学院学报（自然科学版），2012.

[2] 杜振鹏，李德华.基于KD-Tree搜索和SURF特征的图像匹配算法研究[J].计算机与数字工程，2012.

[3] Ke Yan， Sukthankar R， Huston L. An efficient parts-basednear-duplicate and sub-image retrieval system[C].New York：MULTIMEDIA '04 Proceedings of the 12th annual ACM international conference on Multimedia，2004.

[4] Nister D， Stewenius H. Scalable recognition with a vocabulary tree[C].New York：IEEE Conference on Computer Vision and Pattern Recognition，2006.