相似最近邻搜索算法是指在一个尺度空间中查找最优点的一类图像处理算法，在目前许多大规模的计算机视觉应用中占有很重要的地位，如用于图像修复[1]、图像分类[2]、图像检索[3]、图像识别[4]等方面，其性能会对图像搜索的精度和效率产生很大影响。
最近邻搜索的算法主要有基于向量空间的K-dimensional (KD)树算法[5]和基于度量空间的vantage point (VP)树算法[6\]，目前应用较多的算法是在KD树的基础上进行的优化与改进。其中best bin first(BBF)算法[7]非常经典，但数据点增多或者在高维度中搜索时，其查找效率大大降低。随后提出的随机KD森林(RKF)算法[8]是目前最流行的相似最近邻搜索算法之一，其搜索精度、搜索效率都要优于BBF算法，而且更适合于高维度数据搜索，但是对于精度要求很高的搜索，其效果并不理想[9]。
由于VP树使用了多个维度的信息，比依靠单一维度值进行判断的KD树有更好的搜索精度和搜索效率[10]，因此本文在对VP树构建及搜索过程进行优化的基础上提出一种优化的VP森林(OVF)算法，以弥补KD树的不足，最后通过实验对比分析改进前后的算法性能。
1 主要算法 1.1 随机KD森林算法传统KD树的构建过程为统计数据集中所有数据点在每一维度上的方差，选取其中具有最大方差值的维度并对其数据进行排序，以位于中间的数据点作为分裂点，将所有数据点一分为二分别作为左右子树，依次递归构建KD树。
随机KD森林(RKF)算法的构建过程是从数据维度中挑选方差最大的前D维，然后从中随机选出一维将数据集一分为二，如此构建出多棵不同的KD树，使不同的KD树之间尽可能保持相对独立。
搜索过程是选用一个贯穿所有树的优先队列，对所有树进行并行搜索，通过优先队列将得到的最近邻候选点进行排序，选取与查询点距离小的最近邻候选点作为相似最近邻。
1.2 距离函数 1.2.1 欧氏距离两个N维向量a (x11, x12, …, x1N)和b (x21, x22, …, x2N)，a、b之间的欧式距离d1计算公式为
| $ {d_1} = \sqrt {\sum\limits_{k = 1}^N {{{\left( {{x_{1k}} - {x_{2k}}} \right)}^2}} } $ | (1) |
其中x1k表示向量a的第k个分量，k=1, …, N。
1.2.2 卡方检验检验数据相关性。设d2及χ2为卡方值，Dac为实际距离，Dth为理论距离，卡方值由式(2) 计算
| $ {d_2} = {\chi ^2} = \sum {\frac{{{{\left( {{D_{{\rm{ac}}}} - {D_{{\rm{th}}}}} \right)}^2}}}{{{D_{{\rm{th}}}}}}} $ | (2) |
由卡方的计算公式可知，χ2的值为0时，Dac与Dth相等；χ2值越小，Dac与Dth越接近，两者差异越小；反之亦然。
1.2.3 曼哈顿距离两个N维向量a (x11, x12, …, x1N)和b (x21, x22, …, x2N)，a、b之间的曼哈顿距离d3计算公式为
| $ {d_3} = \sum\limits_{k = 1}^N {\left| {{x_{1k}} - {x_{2k}}} \right|} $ | (3) |
欧氏距离的平方函数为计算两个向量距离的平方，以简化计算。两个N维向量a (x11, x12, …, x1N)和b (x21, x22, …, x2N)之间的欧式距离的平方d4计算公式为
| $ {d_4} = \sum\limits_{k = 1}^N {{{\left( {{x_{1k}} - {x_{2k}}} \right)}^2}} $ | (4) |
VP树是一种基于距离度量空间的高维索引结构，它是一棵基于距离函数的二叉平衡树，其构建和搜索均较简单。构建过程为首先从数据集(Da)中随机选取一点作为优势点(Pv)，然后将其他点到Pv距离的中位数(M)作为半径(r)对特征空间进行划分，即r < M的点作为Pv的左子树，r > M的点作为Pv的右子树。递归该过程，生成的VP树会覆盖整个数据集。
VP树的每个非叶结点由特征点P、距离中值M和分别指向左右子树的指针3部分组成。
2.2 优化的VP森林(OVF)算法OVF由并行构建的多棵优化的VP树构成，通过并行查找每棵树中查询点的相似最近邻，并依每个最近邻到查询点的距离远近进行排序，最终从森林中返回最近的邻居。
2.2.1 优势点的选取OVF采用中心选择算法代替传统VP树的随机选择的方法来选取优势点，即从数据集Da中随机采样两组数据P1和P2，将P1作为优势点Pv的候选集，P2作为选取Pv的测试集，然后对P1中每一个候选点进行评估，计算其到P2中所有点的距离的方差，将每一个数据点的方差值作为该点对于测试集中点的区分度，从中选择区分度最大的点作为Pv。这样选取的Pv构成的左右子树分布更均匀，精度更高。具体过程如算法1。
算法1 中心选择优势点算法
输入 数据集Da；
输出 优势点Pv；
function Select (Da)
P1←从Da中随机选择p1个元素;
Dbest←0; //初始最优距离Dbest为0
for i∈P1
P2←从Da中随机选择p2个元素;
Dmd←i到P1中剩余元素距离的平均值;
Dmd’←sum |(D(i, j)-Dmd)|;
//其中j为P2中的所有元素
if Dmd’ > Dbest
Dbest←Dmd’;
Pv←i;
end if
end for
return Pv;
2.2.2 森林的构建由于VP树是根据距离的远近划分左右子树的，因此近侧的节点通常会比远侧的节点更具有自相似性。随着数据集增大，近侧的子树会递归成更加相似的子树，而远侧的子树往往并没有那么紧凑，容易导致远侧的邻居难以匹配，降低了算法精度。因此通过建立VP森林，从每棵树返回的邻居中选择最近的邻居，可以提高匹配精度。
为了减小计算量，分区数据时并没有计算全部数据点到优势点的平均距离，而是随机选取部分点进行计算，所以对精度影响不大。
优化的VP森林构建算法如算法2。
算法2 构建优化的度量森林算法
输入 数据集Da，建树的数量N，距离函数D
输出 优化的度量森林结构
function BuildOptimizedVpForest (Da, N, D)
trees←{ };
for i←{1…N} do
//其中S为叶子结点大小
trees←BuildOptimizedVpTree(Da, S, D);
end for
return trees;
function BuildOptimizedVpTree (Da, S, D)
if |Da| < S then
createleafNode(Da); //创建叶子结点
else
Pv←Select(Da); //选取优势点Pv
S’←从数据集Da中随机选取S个元素;
Dist←{D(x, Pv), ∀x∈s′};
M←median(Dist); //计算平均距离
//将数据集分为左右子树
Dal←{x∈Da|D(x, Pv) ≤ M};
Dar←{x∈Da|D(x, Pv) > M};
LeftChildTree←BuildOptimizedVpTree(Dal, S, D);
RightChildTree←BuildOptimizedVpTree(Dar, S, D);
end if
2.2.3 森林的搜索OVF与传统的搜索算法类似，只是在搜索每棵树时添加了一个优先队列来选取K个最近邻；从每棵树选取的邻居中进行距离排序后，选择距离最小的前K个点作为最终的相似最近邻。
搜索时，需要首先为查询点设置一个距离阈值，使所选邻居都在该阈值范围内。假设Dm为优势点处计算的平均距离，Dtau为查询点的距离阈值。Pq为查询点，Pv为优势点，D为距离函数。
查询左子树或右子树分为以下几种情况：
1) 若Pq的边界范围与Pv的左右分界不相交，并且Pq在Pv的平均距离区域外，即D(Pq, Pv)≥Dm+Dtau，此时可以直接搜索右子树，修剪掉左子树；
2) 若Pq的边界均在Pv的平均距离范围内，即D(Pq, Pv)≥Dm-Dtau，此时可以直接搜索左子树，修剪掉右子树；
3) 若Pq的边界与Pv的左右分界相交，则左右子树都需要搜索；当Pq在Pv边界之外，即Dm < D(Pq, Pv) < Dm+ Dtau；当Pq在Pv边界之内，即Dm-Dtau < D(Pq, Pv) < Dm时，左右子树都需要搜索。
3 实验部分为了验证本文算法的可靠性及准确性，通过实验对传统VP树算法(VT)、优化的VP森林算法(OVF)和随机KD森林算法(RKF)在不同维数、不同数据集大小、不同K值及不同距离函数D下的匹配正确率进行比较，同时比较了树的个数对OVF和RKF匹配正确率的影响。
3.1 实验环境电脑配置为Windows7 64位操作系统，Intel i3 CPU，6 GB内存。开发环境为Visual Studio 2010。实验中使用的RKF直接调用快速相似匹配库FLANN中实现的算法。
实验使用的数据集为从大量的CD封面数据集中随机选取的多组不同大小的128维sift特征数据集，以及从Winder和Brown[10]中随机取样的不同维度的10 k大小的数据集。
对VP树进行搜索时，需要首先确定距离阈值Dtau，本文通过一组实验来确定最合适的Dtau值，实验中使用10 k的sift特征点构建15棵树，K取为3。实验得出Dtau为20左右时对应的匹配正确率最高，故取Dtau=20。
3.2 结果表征设Er为匹配正确率即搜索精度，Dme为查找到的相似最近邻距查询点的平均距离，Dex为准确的最近邻距离，用线性搜索算法中求得的距离表示。Er由式(5) 计算得出
| $ {E_{\rm{r}}} = {D_{{\rm{me}}}}/{D_{{\rm{ex}}}} $ | (5) |
为了获取准确数据，每次实验结果均采取3次实验结果的平均值。
3.3 结果与讨论 3.3.1 不同数据维度对匹配正确率的影响实验分别测试维度为3、12、64、128的10 k的数据集，K值为3，建树个数(T)为20，距离函数使用欧氏距离，从数据集中选取1 k的数据作为测试集。得到不同维度下的匹配正确率如图 1所示。
|
图 1 不同数据维度的匹配正确率 Fig.1 Matching accuracy of different data dimensions |
由图 1看出，低维数据中算法匹配正确率更高，且OVF与RKF相差不大；在高维数据中匹配正确率都有所下降，但OVF的匹配正确率明显更高。
3.3.2 不同数据集大小对匹配正确率的影响实验分别测试了数据集大小为10 k、100 k、1 M的128维sift数据集，其余设置与3.3.1节相同。得到不同数据集大小的匹配正确率如图 2所示。
|
图 2 不同大小数据集的匹配正确率 Fig.2 Matching accuracy of different size data sets |
由图 2看出，两种算法的匹配正确率均随数据集的增大而降低，但OVF的匹配正确率相对较高。
3.3.3 不同K值对匹配正确率的影响在进行图像匹配时，最终确定匹配点时所需要返回的邻居个数K可能不同，对匹配正确率的影响也不同。实验分别测试K值为1、2、3、4、5的128维10 k的sift数据集，其余设置与3.3.1节相同。得到不同K值的匹配正确率如图 3所示。
|
图 3 不同K值的匹配正确率 Fig.3 Matching accuracy of different K values |
由图 3看出，3种算法的匹配正确率均随K值的增大而降低，但OVF的精度相对较高。
3.3.4 不同距离函数对匹配正确率的影响通过实验测试欧氏距离(ED)、卡方检验(CT)、曼哈顿距离(MD)及欧氏距离的平方函数(SED)4种不同距离函数下的匹配正确率，其余参数设置同3.3.1节。得到不同距离函数的匹配正确率如图 4所示。
|
图 4 不同的距离函数下的匹配正确率 Fig.4 Matching accuracy for different distance functions |
由图 4看出，不同距离函数对几种算法的影响不大，但OVF的匹配正确率明显高于VT算法和RKF算法。
3.3.5 不同T值对匹配正确率的影响本次实验分别测试T值为1、3、5、7、9、11、13、15、17、19、21、23、25的128维10 k的sift数据集，其余设置与3.3.1节相同。得到不同T值的匹配正确率如图 5所示。
|
图 5 不同T值的匹配正确率 Fig.5 Matching accuracy of different T values |
由图 5看出，随着树的数量增加，RKF的匹配正确率一直处于稳定状态，而OVF的匹配精度越来越高，并在9棵树时超过RKF，20棵左右时趋于稳定，说明OVF的性能更好。
4 结束语本文提出优化的VP森林算法，首先改进选择优势点的方法并选取区分度最大的点作为优势点；然后提出构建VP森林的方法，从每棵树返回的邻居中选择最近的邻居，以提高匹配精度；最后使用优先队列与剪枝结合的搜索方法来优化查找最近邻的效率。实验结果证明，当构建树达到一定数量时，在不同的数据维度、数据集大小、返回邻居个数、建树个数及不同距离函数等条件下，本文算法的匹配正确率均比传统的VP树和随机KD森林算法明显提高，其中在高维数据中匹配率提高更为显著。
| [1] |
Liu S G, Wei Y W. Fast nearest neighbor searching based on improved VP-tree[J]. Pattern Recognition Letters, 2015, 60/61(C): 8-15. |
| [2] |
Li J, Huang X, Gamba P, et al. Multiple feature learning for hyperspectral image classification[J]. IEEE Transactions on Geoscience and Remote Sensing, 2015, 53(3): 1592-1606. DOI:10.1109/TGRS.2014.2345739 |
| [3] |
Cai J J, Zha Z J, Wang M, et al. An attribute-assisted reranking model for web image search[J]. IEEE Transactions on Image Processing, 2015, 24(1): 261-272. DOI:10.1109/TIP.2014.2372616 |
| [4] |
Liu H Y, Gu J, Meng Q H, et al. Fast weighted total variation regularization algorithm for blur identification and image restoration[J]. IEEE Access, 2016, 4: 6792-6801. DOI:10.1109/ACCESS.2016.2516949 |
| [5] |
Friedman J H, Bentley J L, Finkel R A. An algorithm for finding best matches in logarithmic expected time[J]. ACM Transactions on Mathematical Software, 1977, 3(3): 209-226. DOI:10.1145/355744.355745 |
| [6] |
Yianilos P N. Data structures and algorithms for nearest neighbor search in general metric spaces[C]//SODA'93 Proceedings of the Fourth Annual ACM-siam Symposium on Discrete Algorithms. Austin, USA, 1993:311-321.
|
| [7] |
Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. DOI:10.1023/B:VISI.0000029664.99615.94 |
| [8] |
Slipa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching[C]//IEEE Conference on Computer Vision & Pattern Recognition. Anchorage, USA, 2008:1-8.
|
| [9] |
Muja M, Lowe D G. Scalable nearest neighbor algorithms for high dimensional data[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(11): 2227-2240. DOI:10.1109/TPAMI.2014.2321376 |
| [10] |
邹水中, 江贵平, 张煜, 等. 基于平衡VP树的快速空间配准算法[J]. 计算机工程与应用, 2010, 46(8): 159-162. Zou S Z, Jiang G P, Zhang Y, et al. Fast space registration algorithm based on the balance of the VP tree[J]. Computer Engineering and Applications, 2010, 46(8): 159-162. (in Chinese) |