图像检索是近年的研究热点，有效的图像检索算法能够保证检索效率，同时不占用过多的内存空间。本文旨在利用SIFT描述子的位置信息提高VLAD在图像检索方面的准确率。

SIFT^[1-2]特征是图像检索领域广泛应用的特征之一，而BOW^[3-4]添加了SIFT描述子的数据分布信息^[5]。BOW方法首先利用训练集合的SIFT描述子进行k-means^[6]聚类求得聚类中心；其次，将待检索图像的SIFT描述子分配到对应的聚类中^[7]；再次，利用一个聚类内的描述子建立直方图，对该聚类内描述子的数据信息进行统计^{[5, 8]}；最终，以所有聚类的直方图作为该图像的特征。BOW的缺点在于这种方法忽略了图像的空间信息^[9-10]。VLAD^[11]在BOW的基础上进行改进。该方法同样进行BOW中描述子分配的工作^[12]。VLAD方法利用一个聚类内所有的SIFT描述子与该聚类中心求得残差，并将属于一个聚类的残差累加求得VLAD。VLAD在单独使用时，其图像检索的效果明显优于BOW^[13]，但是VLAD也忽略了图像的空间信息。VLAD特征是通过残差向量累加生成的，如果两幅非相关图像也有可能求得相同的VLAD特征，那么将无法区分这两幅图像。添加描述子的空间信息将能增强VLAD的区分能力，能够避免这一情况的发生。

现已提出了多种针对VLAD的改进方法。精细残差法^[12]对残差的表述能力进行更深入地挖掘。该方法训练残差码本并产生二次残差，通过两步聚合合并二次残差和原始残差求得一种VLAD，并记为FVLAD。HVLAD方法^[14]构造隐藏层，并建立隐藏层的码本，利用隐藏层码本生成VLAD。Adp方法^[15]利用聚类中的描述子求得平均值，即该聚类的集合中心。利用聚类的集合中心代替原本的聚类中心求得VLAD。残差归一化方法^[16](记为RN)使得所有描述子在进行累加时贡献均等。局部坐标系方法^[16](记为LCS)利用PCA方法^[16]为每个视觉单词训练与之计算的旋转矩阵，从而更好地处理视觉单词的突发性^[17]。Multivoc方法^[18]通过训练同样大小的多个码本求得VLAD并进行联合降维，从而提高VLAD降维之后的图像检索能力。

熵^[19]是信息论中的概念，用以描述系统中变量的混乱程度，常被应用于图像检索领域。文献[20]使用像素的坐标进行计算，求得一种熵用以描述图像中像素灰度的复杂程度。文献[21]利用熵描述SIFT描述子的数据分布情况，并将这种熵串联在VLAD之后，生成EEVLAD和CEVLAD两种改进后的描述子。

本文受文献[20-21]启发：在文献[20]中，使用熵统计像素坐标信息，说明熵可以对坐标信息进行良好地表示；在文献[21]中，使用熵统计VLAD的向量信息，并证明了熵与VLAD拼接在一起使用的有效性。但是文献[21]中的熵与VLAD向量大小相同，占据大量存储空间并降低了VLAD的检索效率。本文利用熵对一个聚类内的SIFT描述子坐标的混乱程度进行描述，并将这种熵称为位置信息熵。本文将位置信息熵与VLAD串联并进行图像检索。

1 利用位置信息熵改进的VLAD 1.1 信息熵理论

熵表示一个体系的混乱程度。本文将描述子的位置信息作为体系中的变量，利用熵对坐标的混乱程度进行统计。熵在信息论的应用中，使用概率分布度量变量的不定度。

假设x_i是某一体系中的变量，共计T个变量，i=1, 2, …, T，并将p(x_i)记为变量值为x_i时的概率。则这个体系的熵值H(x)为

$ H\left( x \right)=-\sum\limits_{i=1}^{T}{\text{log}\mathit{p}({{x}_{i}})} $

(1)

1.2 算法总流程

图 1是算法的总流程图，主要分为以下步骤：

1) 训练单词码本。对训练集描述子进行聚类，假设通过训练共产生k个聚类中心，则将聚类中心记为c_i，i=1, 2, …, k。

2) 提取待检索图像的SIFT特征。具体包括SIFT描述子及SIFT描述子的x坐标和y坐标。假设一幅图像中共提取出了m个SIFT描述子，则将描述子记为s_i，i=1, 2, …, m。

3) 分配描述子。将待检索图像的SIFT特征分配到所属的聚类，一般采用最近邻方法。

4) 求得VLAD。首先，利用描述子与聚类中心做差求得残差向量，将每个描述子产生的残差记为r_i，i=1, 2, …, m；其次，将一个聚类内的所有残差相加，求得对应于一个聚类的VLAD值；最后，一幅图像的VLAD由所有聚类的VLAD表示。

将一个聚类中的描述子个数假设为n，那么c_i所在的聚类中则有n_i个描述子，c_i的聚类中第j个描述子表示为s_{i, j}。所以，在一个聚类内求得一个残差的方法为

$ {{r}_{i, j}}={{s}_{i, j}}-{{c}_{i}} $

(2)

求得一个聚类的VLAD的方法为

$ {{v}_{i}}=\sum\limits_{j=1}^{{{n}_{i}}}{{{r}_{i, j}}} $

(3)

本文提取的SIFT描述子是128维的向量，所以一个聚类的VLAD向量的大小为1×128。所有聚类的VLAD形成一个k×128的向量，该向量即为一幅图像的VLAD。

5) 求得位置信息熵。利用该幅图像SIFT描述子的x坐标建立直方图，并进行熵的计算，求得x方向的位置信息熵H(x)，对于y坐标也进行如上计算，求得y方向的位置信息熵H(y)。

6) 改进VLAD特征。对VLAD向量，x方向位置信息熵和y方向位置信息熵进行归一化处理，并将三者串联。本文将最终得到的向量称为LIVLAD(location information boosting VLAD)，简记为LIv。

步骤1)~4)为VLAD的计算步骤，下文将详细介绍生成和使用位置信息熵的步骤。

1.3 算法详细流程 1.3.1 建立坐标直方图

因为SIFT描述子与SIFT描述子的位置信息存在联系，又因为VLAD是SIFT描述子与单词码本计算求得，所以本文利用位置信息、SIFT描述子和单词码本三者之间的关系，建立图像的位置信息与单词码本之间的联系——本文为每个聚类建立对应的集合，用以存储该聚类中描述子的坐标信息。

在建立直方图时，首先，本文利用最近邻方法^[7]将图像中m个描述子分配到其所属的聚类，并将描述子与对应聚类的索引记为idx(i)，i=1, 2，…, m；其次，利用索引将x坐标和y坐标分配到聚类对应的集合；最后，为坐标信息建立直方图。

以x坐标为例，图 1中共有5个聚类，所以建立5个集合，对属于一个集合的x坐标进行直方图统计，产生5个直方图。将直方图bin的个数设为T，记一个集合中描述子的x坐标信息产生的直方图为h_i，i=1，2，…, T。由经验得到，T值应设定为350。

1.3.2 计算位置信息熵

以x坐标为例，将一个集合中的x坐标值视为一个系统。在完成直方图统计后，每一个集合都有对应的直方图h_i，i =1, 2，…, T。因为一个集合中所有的x坐标组成一个一维向量，并且直方图统计是基于分段的频数统计，所以可以将h_i理解为：某集合的x坐标值划分为T段后，在第i段出现的x坐标的个数。利用h_i除以该集合坐标的个数，求得x坐标出现在第i段的概率值p_i，i=1, 2, …, T。如果将一个集合中的x坐标值作为一个系统，那么x坐标即为坐标值系统中的变量，p_i即为该变量的不定度。将p_i代入式(1)中进行计算，即可得到直方图每段的熵值，再将每段的熵值进行累加，形成一个大小为k×1的向量，即为该集合对应聚类在x方向上的位置信息熵。对y坐标也进行如上的计算，同样可以求得一个大小为k×1的位置信息熵向量。如果该集合坐标的个数为0，则该聚类的熵为0，因为在该聚类中没有描述子出现，也就意味着没有混乱程度可言。

本文将使用x坐标和y坐标求得的所有聚类的位置信息熵称为该图的位置信息熵，其大小为k×2。并将位置信息熵向量拼接在VLAD向量之后，求得一个k×130大小的向量，作为新的描述子进行图像检索。

1.3.3 归一化处理

在对VLAD进行归一化处理时，L2归一化^[21]和power归一化^[21]是最为常见和有效的两种方法。本文采用L2归一化与power归一化结合的方式对VLAD进行归一化处理，并将求得的向量记为v^*。如果将power归一化的参数值设置为0.5，即SSR方法^[21]，可以使得power归一化在处理VLAD时达到最佳效果。

本文对位置信息熵同样采用L2归一化和power归一化结合的方法进行处理。power归一化的参数由实验得到，应设置为0.4。

2 实验结果分析

利用本文提出的算法，在公认的数据集上进行实验。INRIA Holidays图像集^[22]提供1 491幅图像，记录了500个不同的场景或物体。利用Flickr60k^[22]训练在Holidays上实验时所需的单词码本。使用的另一个测试集为Oxford5k^[22]，该图像集提供5 062幅图像，共分为550个场景，利用Paris6k数据集^[22]来进行单词码本的训练。以上两个数据集均使用mAP值作为图像检索准确性的衡量标准。

2.1 全尺寸向量实验

使用k=64时求得的VLAD，在Holidays和Oxford5k数据集上进行位置信息熵及其他方法与其组合的实验。实验采用三种描述子：SIFT描述子；利用Root方法^[2]优化SIFT求得的RSIFT；将128维的SIFT描述子进行PCA降维求得的64维SIFT描述子，记为PSIFT。对SIFT降维时，利用Flickr60k训练Holidays数据集的PCA降维矩阵，利用Paris6k训练Oxford5k的PCA降维矩阵。

对实验方法进行编号：编号1对应只添加位置信息熵的方法；编号2对应在方法1上结合残差归一化的方法；编号3对应在方法2上添加LCS的方法；编号4对应方法3结合Adp的方法。

表 1用以记录在Holidays数据集上，利用SIFT、RSIFT和PSIFT产生的VLAD采用方法1~4求得的mAP值。

使用原始的SIFT描述子进行实验时，原始VLAD求得的mAP值为0.521，归一化之后提高至0.556，添加位置信息熵后的值为0.585。利用编号2方法可以使得v^*，LIv的mAP值获得进一步地提高，最高值提高至0.597.2和方法3中都含有残差归一化方法，而此方法在Holidays数据集上使用时，需要结合power归一化方法才可以起到作用^[16]。因为方法2和3中的v表示原始的VLAD，并未进行power归一化处理，所以v对应的mAP值有略微下降。编号2和3两种方法使得v^*和LIv的mAP均有所提高，但是方法3的提高效果比方法2的效果更为明显。因为方法4中采用的Adp方法使得v本身有所提高，抵消了没有结合power归一化的残差归一化方法产生的略微下降的效果，所以v对应的mAP提升至0.530。最高值由方法4的LIv产生，mAP值为0.644。

结合Root方法进行实验时，利用VLAD求得的mAP值为0.562。在方法2和3中v处的值同样出现下降的情况。从横向看方法1~4，归一化处理后的VLAD向量的检索能力都要优于原始VLAD向量，而在归一化处理基础上添加位置信息熵的方法检索结果最佳。从纵向看，随着方法的不断改进，求得的mAP呈平稳提升趋势，并在方法4中求得最佳值0.664。因为采用Root方法后的SIFT的性能要优于原始的SIFT^[2]，所以RSIFT的实验结果与使用相同方法的SIFT相比均有所提高。

在利用PSIFT进行实验时，原始mAP值为0.315。只使用残差归一化不结合power归一化，对方法2和3的原始VLAD仍然有所影响。整体mAP的变化趋势都与SIFT和RSIFT相同。因为PSIFT是SIFT降维后的描述子，会损失部分有效信息，所以PSIFT的实验结果要普遍低于使用原始SIFT的结果^[21]。

表 2中记录了利用SIFT、RSIFT和PSIFT产生的VLAD，并采用方法1~4在Oxford5k数据集上实验求得的mAP值。

在利用SIFT描述子进行实验时，从方法1中可知，利用原始的VLAD求得的mAP值为0.385，进行归一化求得的值为0.392，LIv的值为0.398。方法2的值与方法1相比较，求得的mAP值均进一步提高。方法3添加的Adp方法对v没有优化，只使得v^*和LIv的值有所提升。方法4求得使用SIFT描述子进行实验时的最佳结果0.422。

将所有方法的v、v^*及LIv进行纵向比较，v^*处的值都要优于v，而LIv处的值都要优于v^*。在利用RSIFT和PSIFT描述子进行实验时，mAP值的大体趋势与SIFT实验得到的趋势基本一致，而不同之处在于，方法4对v没有提升效果。

2.2 128-D向量实验

将由SIFT和RSIFT产生的LIVLAD投影至128维的压缩向量^[23](缩写为：128-D)，并在Holidays和Oxford5k数据集上进行实验。

表 3列出了多种128-D的VLAD向量的实验结果。当原始VLAD压缩为128-D时，如表 3第1行所示，在Holidays上的mAP为0.510；由SSR归一化的VLAD也被压缩为128-D，如第2行所示，在Holidays上的mAP为0.557，在Oxford5k上为0.287；第3行为使用Multivoc方法的的结果，值为0.614，该方法可以大大改善原始VLAD降维之后的结果；使用内部归一化^[15]和Adp结合方法的128-D结果在第4行，HVLAD、FVLAD、EEVLAD和CEVLAD的mAP值在第5~9行。除本文方法外，在Holidays数据集上的最佳值是0.681，在Oxford5k数据集上的最佳值是0.552，而产生这些最佳值的方法中均含有Multivoc和Root方法。

表 3的方法多采用k=256的码本，所以本文此部分实验也采用该大小的码本。因为最佳值的方法中均含有Multivoc和Root方法，所以本文方法也结合这两种方法。Multivoc中考虑多个码本的联合，因此本文使用4个码本进行联合，并将联合降维的VLAD应用到LIVLAD中。

表 3中也列出了采用本文方法的实验结果。在Holidays数据集上，当只采用位置信息熵对VLAD进行改进时，mAP值为0.683，该值已经高于已有的最高值；使用本文方法结合Multivoc，使得mAP提升至0.727；采用Root方法并结合位置信息熵方法使得mAP值提高至0.702；使用本文方法结合Multivoc和Root方法可求得最高值0.733。

在Oxford5k数据集上，LIVLAD的mAP值为0.530，与原始的VLAD相比该值明显提高。使用Multivoc改进LIVLAD的mAP值为0.547，与不使用Root方法的最高值0.536相比，本文方法的结果更佳。使用Root方法对LIVLAD进行改进时，得到的mAP值为0.549，如果结合Multivoc方法，可以求得在该数据集上的最佳检索效果，值为0.559。

表 3中的实验结果表明，与其他方法相比，本文提出的位置信息熵可以有效提高VLAD的检索能力，并且可以求得最佳的检索结果。

3 结论

1) LIVLAD的实验结果表明：描述子的位置信息对改进VLAD的检索能力具有重要意义。

2) LIVLAD易于和已有方法结合，LIVLAD与多种方法结合能进一步提升VLAD的检索能力。

3) LIVLAD具备较低的时间复杂性和空间复杂性，在进行图像检索时具备较高优势。

神经网络能有效提高VLAD的检索能力，在未来的工作中，本文方法将与神经网络进行结合。