邓清文，林志贤，郭太良

福州大学 物理与信息工程学院，福州 350002

1 引言

2010年，著名网站Flickr统计的图片总量超过50亿[1]，2014年平均每天在Facebook、Snapchat、Whats App等平台上上传分享的图片数量超过18亿张。面对如此庞大的数据，传统的线性枚举查找方法也会变得十分耗时[2]。因此，如何快速准确地进行内容查找对大规模数据管理意义重大。

例如，给定一幅待查的图片，如何在大规模的数据库中快速、准确地检索到与给其具有语义相似的图像，基本的思想是对数据集中所有图像提取特征，然后定义特征相似性度量，对数据库进行线性扫描并根据相似度排序，从而获取检索的结果。然而，这样必能存在两个重要的问题：（1）图像特征往往是一种高维化的数据，高维数据的存储要求高，计算效率和类与类之间的区分性较低；（2）对大规模数据进行线性搜索很难满足效率要求。因此，如何对图像高维特征进行有效索引成为一个亟需解决的问题。研究人员在这方面最早提出了以树形结构索引算法，主要以树形结构索引算法。基于树的查找方法如：kd-tree[3]、M-tree[4]、cover-tree[5]、metric-tree[6]等方法，然而，树形索引结构提高了检索速度，但所需的存储空间大，难以适应大规模数据检索的要求。

与此同时，基于哈希的相似度查询方法倍受关注。基于哈希的相似度查找方法是将数据映射到低维度的汉明空间，也就是二进制编码。通过查找哈希表的方式，在计算查询样本点和数据库中的样本点的相似度时只需要简单的位操作运算，并且拥有良好的存储效率。

Chum等人[7]将局部敏感的哈希算法（Locality-Sensitive Hashing，LSH）引入到图像哈希索引技术当中，其利用随机投影的方式对样本点特征进行哈希，通过构建一组哈希函数，将n维的原始特征索引成d维(d≪n)，其形式定义：对于集合S，集合内元素间相似度计算公式为sim( )a,b。如果存在一个哈希函数h(*)满足以下条件：存在一个相似度S到概率P的单调递增映射关系，使得S中的任意两个元素满足，如果sim(a ,b)≤R，则 有P{h (a)=h(b)}≥P1；如果 sim(a ,b)≥(1 +ξ) R，则 有 P{h (a)≠h(b)} ≤P2，其 中 ξ＞0,P1＞P2。2006年，Andoni等人[8]又提出了Min哈希，其对LSH哈希函数族进行了扩展，构造了ls范数距离下的LSH哈希函数，将空间随机分割为固定宽度的单元，每个单元代表一个桶，通过ls和Jaccard系数作为近似最近邻检索的度量标准。对于高维核数据，当核函数未知情况下，LSH类方法的检索效果并不好。为了解决这个问题，Kulis等人[9]将LSH扩展为核位置敏感哈希（Kernelized Locality-Sensitive Hashing，KLSH）。然而这类LSH算法采用与特征无关随机投影的方式构建哈希函数，因此为了增加哈希码的碰撞概率，需要较多的超平面对数据进行分割投影才能达到令人满意的准确率。近年来，研究者为了克服LSH方法的缺点，提出了一系列的基于机器学习的哈希函数算法，利用数据局部性的特性，通过哈希函数将高维特征映射为紧凑的二进制编码，降低了检索时间的复杂度。这些算法中最具有代表性的是利用主成分分析（Principle Component Analysis Hashing，PCAH）[10]进行降维，从而对特征实现索引，相对于随机的投影方式产生哈希函数的算法而言，该算法构建哈希函数依赖数据本身，提高了检索的准确率。这类算法还包括Weiss等人[11]提出的谱哈希算法（Spectral Hashing，SpH）。通过谱分析，利用服从分布的n个离散数据点求拉普拉斯的特征方程求解。为了使算法的性能随着哈希编码长度的增加而得到提升，Jin等人[12]采用了和局部敏感的哈希算法类似的框架，利用了数据的几何结构特征产生投影向量，提出了一种密度敏感的哈希算法（Density Sensitive Hashing，DSH），即使在较短的哈希编码时，密度敏感的算法在检索性能上也得到了相应的提升。此外，Gong等人[13]提出了迭代量化哈希算法（Iterative Quantization Hashing，ITQ）通过对相互正交的投影进行旋转，最小化哈希函数的实数值输出和当前哈希编码之间的差值的平方和来构建哈希函数，使得二值哈希编码的均衡性大大增加，性能也随之得到显著的改善。然而，现有的方法存在一个问题，通过学习哈希函数获得的二进制编码，这些投影矩阵不仅需要很强的判别性，而且能够同时区分多类特征，否则难以保证检索的准确性。而实际的图像数据往往很难学习到这样的投影，如果增加编码的长度，那么需要更多的存储空间，因此，如何在编码位数相同的情况下，使学习到的哈希函数得到更高的检索性能，是一个有待解决的问题。

本文针对上述问题，提出了一种基于主成分的多表图像哈希检索方法，即在编码位数相同的情况下，通过增加查询哈希表的索引个数提高检索的性能。

2 主成分的多表索引哈希函数构建

如果哈希函数判别能力不够，即使使用了紧凑的编码方式，仍然需要增加编码位数来达到令人满意的检索性能。换言之，在构造哈希之前提高样本特征的区分性就更容易学习到区分度高的哈希编码。因此，为了获取图像区分性强的特征，本文首先利用主元分析在原有的特征维度中，抽取具有区分性的特征作为原始数据的主成分，这样可以减少高维空间中所包含的冗余信息或噪声，得到数据内部的本质结构特征，同时解决了数据稀疏性问题，加快了后续的计算速度。此外，为了保证不同语义样本哈希编码具有很强的判别性，运用了不同语义样本的聚类中心进行特征聚类。在编码位数相同的情况下，通过每类聚类中心获取多个相似类，构建多组哈希函数并生成多个哈希索引表，提高相似样本的召回率。最后，为了进一步提高算法检索的准确度，避免投影在某个方向方差大，引起对应编码位的权重较大而其他位的权重小，导致检索性能下降，采用正交矩阵对投影向量进行旋转，均衡每位哈希编码的权值，确保相似的样本通过哈希映射后得到相似编码。

2.1 区分性特征提取

图像哈希检索的目的是把原始高维度的数据映射到低维的汉明空间，且在这个低维空间编码后的数据能够保持原来高维空间的语义关系，即在原始空间是近邻的特征，在编码空间还是近邻。因此，在降低图像特征维度的同时尽量减少高维空间中所包含的冗余信息或噪声。本文首先通过主元分析提取原始高维特征中具有区分性强的特征维度，得到训练集内部的本质结构特征，也就是原始特征经过投影后保留那些方差较大的特征维度。

如图1所示，假设不同颜色的点代表不同样本的特征，如果将这些区分性不大的特征按照X、Y轴投影，那么投影后的数据在X、Y轴上的方差相差不大，即这些投影后的特征区分性较小。为了增强不同样本之间特征的区分性，如何寻找一个最佳投影u降低数据集样本特征的维度，且保留具有区分性特征维度。下面给出推导过程。

图1 数据集样本特征示意图

如图2所示，绿色和浅蓝色表示样本点X′(x)，X″(x)分别在U(x)和Û(x)上的投影，其中U(x)和Û(x)都为单位向量。显然红色和棕红色的样本点在U(x)方向上的投影之间的方差最大，而在Û(x)方向上投影之间的方差几乎为零，不适合样本点特征之间的区分。对于给定的数据图像特征库，如何找到这个投影矩阵u(x)={u1,u2,…,un}，使得投影后样本点特征方差最大。

图2 样本点特征投影

定义u(x)={u1,u2,…,ud}为投影矩阵，X(x)={x1(x),x2(x),…,xn(x)}为由n个样本xi(x)组成的数据集，其中xi(x)∈Rk。假设这些样本点的每一维特征均值都为0，因此x(i)在u上的投影均值也为0。根据最大化方差理论，数据集在u(x)上投影后的方差为：上述表达式为即可知，λ是的特征值，u(x)是其对应的特征向量，最佳的投影向量为特征值λ最大时对应的特征向量u1(x)，以此类推，第i个特征值对应的特征向量为ui(x)，本文选取前k个最大特征值对应的特征向量作为最佳投影矩阵u(x)={u1(x),u2(x),…,uk(x)}，其中k值与样本点哈希编码的位数有关，则X(x)在u(x)投影后的数据X(x)∗u(x)为该数据集样本特征方差最大的主成分，在降低维度的同时过滤了那些方差小的特征。

2.2 特征聚类量化预处理

哈希函数往往需要很强的判别性，即能够同时区分多类样本点特征，否则很难确保检索的准确率。Jegou等人[14]研究表明数据量化的预处理将显著提高最近邻检索的性能，基于这个研究成果，在学习哈希投影之前，对数据集的主成分进行量化处理，即利用不同语义样本的聚类中心进行特征聚类，将不同特征的多类样本n分到k个不同的组里面，并作为哈希投影的训练集，以此得到具有更强判别性的哈希函数。

假设区分性特征样本集为：X′(x)={x1(x),x2(x),…,xk(x)}，其中xi(x)∈Rk，特征聚类将样本聚类成k个簇，算法描述如下：

1.随机选取k个样本点作为聚类质心，μ1,μ2,…,μk∈Rk。

2.对于每一个样本点i，计算其归属的类。

3.对于每个类j，重新计算该类的质心。

4.重复步骤2、3直到收敛。

然而，大规模图像特征聚类的收敛过程非常耗时，在实际的应用中，一般不知道算法迭代的次数p和最佳的聚类组数k，经过大量实验发现，特征降维后的迭代次数p通常比较小，其性能就能够达到理想值。此外，算法性能往往还取决于聚类的组数k，一般来说k值越大，算法的性能会有所提升，但是，这将必导致量化的计算量增大，系统检索的时间会更慢。在该算法中，聚类的组数k与哈希编码的位数L有关，下一节会详细介绍。

2.3 多表哈希函数构建

基于上述两节，得到低维度且区分性强的图像特征，并通过不同语义样本的聚类中心进行特征聚类，将不同特征的多类样本n分到k个不同的聚类组，从而增强了多样本间的区分度。本节选取每类样本的聚类中心作为哈希函数的训练集，获取多组哈希投影矩阵，每组哈希矩阵包含L个投影向量，其中L为哈希编码的位数。定义一个哈希函数的形式如下：

其中，x⊂Rn×d是从原始特征提取的具有区分性的特征向量，ϖTi(x)⊂Rd×L是投影矩阵，sign(⋅)是符号函数，t是偏移参数，在学习哈希函数之前，对数据进行了零均值处理，函数可简化为h(x)≈sign(xϖTi(x))。通过哈希函数每个样本的图像特征将被映射为长度为L的哈希值。

训练哈希函数时，充分利用了数据内部本质特征，并将这些区分性特征进行了聚类，作为哈希函数的指引，因此得到区分度高的投影矩阵ϖTi(x)。下面是推导过程，假设低维空间中样本特征x⊂Rn×d经过特征聚类后得到图3。

图3 低维空间中样本点的特征聚类

令s={s1,s2,…,sk}为区分性特征聚类后的结果，引用误差平方和（Sum of Square Error，SSE）评判聚类后的性能：

其中μn为第n组sn的代表点，则：

然而特征聚类后相似类之间的离散度相差较大，或者是相似样本点属性分布区间较大，即原本是相似的样本类，而被分到两个不同的聚类组。这样势必导致相似的样本点，在哈希检索时被遗漏。因此，采用学习多组哈希投影矩阵的方式，生成多张哈希索引表，这样在编码位数相同的情况下，便可以提高相似样本的召回率。

定义1相似簇ζ

如图4所示，黄色梅花型是查询图像，其他不同颜色不同形状的点是与查询图像相似的图像。如果仅在黄色梅花聚类哈希表里查询，势必导致其他相似图像被遗漏。如果利用图4所示四个相似类分别构建一组哈希函数，各自生成一张哈希表，那么查询时结合这些表可检索到更多的相似样本，以此提高检索召回率。下面为其中一组哈希函数的构建过程，在特征聚类后再次进行二次聚类，并将相似类归为到一组相似簇里面，再利用相似簇中心与其中相似类聚类中心之间的中垂面作为超几何平面分离相似簇中相邻类的样本点集。并将这些中垂面构建一组投影矩阵ϖTi(x)。

定义2超几何中垂面

图4 相似簇中相似类

其中μi，μj表示相似簇和其中一个子集聚类中心，推导相应的哈希函数如下：

由上式可知，假设哈希编码的长度为L，特征聚类最终得到L个相似簇，并且每个相似簇ζ包含λ个相似类，每一位哈希码对应一个相似簇ζ，从而可以得到λ组哈希函数，每组哈希函数对应一个投影矩阵其中包含L个投影向量。

2.4 哈希编码优化

本文为了进一步提高算法检索的准确度，避免投影后数据xϖTi(x)在某个方向方差大，引起对应编码位的权重较大而其他位的权重小，导致检索性能下降。本节借鉴文献[12]，引入正交矩阵R对投影向量ϖTi(x)进行旋转，均衡每位哈希编码的权值，以减小量化误差。定义损失函数为投影后数据xϖTi(x)与对应的哈希编码之间的误差。利用矩阵运算性质和弗罗贝尼乌斯范数的定义，损失函数可简化为：

由式（7）可知，最小化损失函数等价于最大化J(B)=tr(BTxϖTi(x)R)。当固定参数R时，最小化损失函数对应的参数B的最优解为对于固定参数B时，最小化目标函数等价于最大化J(R)=tr(BTxϖTi(x)R)。将矩阵BTxϖTi(x)进行奇异值分解（SVD）得：J(R)=tr(SΩTR)=tr(TRSΩ)由奇异值分解SVD定义：T=I，STS=I可知，当 R=ST时，损失函数达到最小值。

3 实验结果分析

本文实验所选的测试集为Caltech-256和CIFAR-10，并选取了具有代表性的方法如：LSH[7]、PCAH[10]、SPH[11]、DSH[12]、ITQ[13]、SH[15]与本文提出的方法进行比较。对本文提出的方法进行验证和分析，为了比较方便，本文提出了一种基于主成分的多表图像哈希检索方法（A Multi Table Image Hash Retrieval Method Based on Principal Component），简称为PMTH。对于每个图像库，随机选择1 000个样本点作为查询图像，剩下的样本作为训练集，用于学习哈希函数。对于每个查询样本点，计算其哈希编码与召回来的图像哈希编码的汉明距离，并按照距离大小来排序，距离越小的排得越前。

3.1 检索性能评判标准

实验选取了召回率，准确率作为算法性能的评价标准。具体来说，假设特征A在原始空间有相同语义的特征集合为Sem(A)，其元素个数为T，在经过哈希函数索引后，以汉明距离dist为阈值进行检索，将汉明距离小于dist的特征集合Sem(H(A))作为检索结果，其元素个数为G，S=Sem(A)∩Sem(H(A))表示检索结果中与特征A语义相同的元素集合，其元素个数为H。召回率可表示为Recall=H/T，准确率可表示为Precision=H/G。

3.2 PMTH算法参数设置

2.1节通过主元分析提取图像的区分性特征维度d与当前哈希编码的位数L相等；在2.2节特征聚类量化预处理部分有两个设置参数，特征聚类迭代次数P和最佳的聚类组数k，经过大量的重复性实验，当P∈(20,50)时，算法性能达到最佳，聚类组数k和相似簇ζ的值有关，即：k=λζ，其中，λ为相似簇中相似类的个数，也就是构建哈希函数的组数，对图像进行了10次以上的量化检索实验，在兼顾准确率的同时，当λ=3时，图像召回率达到最佳。最后在2.4节哈希编码的优化阶段，采用和ITQ算法一样的迭代次数N=50。

3.3 测试结果

数据集Caltech-256、CIFAR-10的图像特征分别为1 024维的CNN特征和512维的GIST特征。哈希编码的位数一般不超过特征维数，分别采用32 bit、64 bit、128 bit对图像特征进行汉明编码。随着汉明距离依次增加，得到图5 P-R曲线，图6 P-S曲线，图7 R-S曲线和图8 M-CL曲线。

如图5（a），（b）所示，在相同的召回率下，PMTH算法取得的准确率更高。因为在训练哈希编码前，首先获取了图像的区分性特征，并利用这些特征进行聚类作为哈希投影矩阵的训练集，得到了判别性强的哈希函数，提高了检索的准确率。另外，可以看出在CIFAR-10数据集下所有的方法实验结果有明显的下降，这是因为CIFAR-10数据集下的图像本身比较复杂，但在相同的测试环境下，该方法均优于其他的方法。

如图6（a），（b）所示，在Recall-Sample曲线这种评价标准下，PMTH算法优于其他六种算法，随着检索样本数量的增加PMTH算法召回的相似样本数有了明显的提升。这是因为在编码位数相同的情况下，构造了多组哈希码索引表，在查询过程中通过查询多表的方式降低了相似样本遗漏率。另外，在Caltech-256数据集下，当检索样本数量相同时，召回率较ITQ算法提升不太明显，这是因为当前哈希编码位数比较低，不能充分获取原始高维图像的区分性特征信息。

如图7（a），（b）所示，PMTH算法在Precision-Sample曲线上，其32 bit、64 bit和128 bit编码性能都比其他六种算法要高。尤其在CIFAR-10数据集下，当检索样本数一定时，其准确率有了显著提高，这是因为其原始图像特征维度是Caltech-256数据集下，图像特征维度的，即在相同位数编码的情况下，能获取到 CIFAR-10数据集图像特征信息要比Caltech-256的要多。

图5（a） Caltech数据集下Precision-Recall测试

图5（b） CIFAR数据集下Precision-Recall测试

图6（a） Caltech数据集下Recall-Sample测试

图6（b） CIFAR数据集下Recall-Sample测试

图7（a） Caltech数据集下Precision-Sample测试

图7（b） CIFAR数据集下Precision-Sample测试

图8 Caltech和CIFAR数据集下平均准确率测试

如图8所示，PMTH算法分别在32 bit、64 bit、128 bit和256 bit哈希编码检索的平均准确率要高于比较的六种算法。这是因为充分利用了数据内部的本质结构特征，抽取具有区分性的特征，并通过特征聚类后的数据训练哈希函数，提高了样本间的判别性。表1、表2分别为不同算法在Caltech-256和CIFAR-10数据集下的训练时间，每个算法分别在32 bit、64 bit和128 bit上进行量化训练测试。最终，取10次量化结果的平均训练时间作为当前编码位的训练时间。测试平台配置为Intel 2核2.53 GHz的CPU，4 GB的内存，Matlab 2014。

为了更为直观地比较PMTH算法的性能，图9为CIFAR-10下的64 bit哈希编码可视化检索结果比算法性能更好，验证了算法的有效性。

表1 Caltech-256数据集下，不同哈希编码的训练时间

表2 CIFAR10数据集下，不同哈希编码的训练时间

图9 CIFAR数据集下可视化检索测试

4 结束语

本文提出了一种基于主成分的多表图像哈希检索方法。利用主元分析提取了具有区分性强的主成分特征，并通过特征聚类训练学习多个哈希索引表，以此提高相似样本的召回率，最后采用正交旋转矩阵对哈希函数进行优化，提高了相同语义的样本检索的准确率，实验表明该方法是有效的。

[1]Kullin H.Two Swedish eyes on media and public relations[EB/OL].（2010-09）[2010-11-16].http：//www.kullin.net/2010/09/flickr-5-billion-photos/.Media Culpa.

[2]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.

[3]Silpa-Anan C，Hartley R.Optimised KD-trees for fast image descriptor matching[C]//IEEE Conference on Computer Vision and Pattern Recognition，2008：1-8.

[4]Ciaccia P，Patella M，Zezula P.M-tree：An efficient access method for similarity search in metric spaces[C]//International Conference on Very Large Data Bases，1997：426-435.

[5]Beygelzimer A，Kakade S，Langford J.Cover trees for nearestneighbor[C]//Proceedings of the 23rd International Conference on Machine Learning，2006：97-104.

[6]Uhlmann J K.Satisfying general proximity/similarity queries with metric trees[J].Information Processing Letters，1991，40（4）：175-179.

[7]Chum O，Philbin J，Isard M，et al.Scalable near identical image and shot detection[C]//Proceedings of the 6th ACM International Conference on Image and Video Retrieval，2007：549-556.

[8]Andoni A，Indyk P.Efficient algorithms for substring near neighbor problem[C]//Proceedings of the Seventeenth AnnualACM-SIAM Symposium onDiscreteAlgorithm，Society for Industrial and Applied Mathematics，2006：1203-1212.

[9]Kulis B，Grauman K.Kernelized locality-sensitive hashing for scalable image search[C]//IEEE 12th International Conference on Computer Vision，2010，30（2）：2130-2137.

[10]Price A L，Patterson N J，Plenge R M，et al.Principal components analysis corrects for stratification in genomewide association studies[J].Nature Genetics，2006，38（8）：904-909.

[11]Weiss Y，Torralba A，Fergus R.Spectral hashing[C]//Advances in Neural Information Processing Systems，2009：1753-1760.

[12]Jin Z，Li C，Lin Y，et al.Density sensitive hashing[J].IEEE Transactions on Cybernetics，2014，44（8）：1362-1371.

[13]Gong Y，Lazebnik S，Gordo A，et al.Iterative quantization：A procrustean approach to learning binary codes for large-scale image retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（12）：2916-2929.

[14]Jégou H，Amsaleg L，Schmid C，et al.Query adaptative locality sensitive hashing[C]//IEEE International Conference on Acoustics，Speech and Signal Processing，2008：825-828.

[15]Heo J P，Lee Y，He J，et al.Spherical hashing[C]//IEEE Conference on Computer Vision and Pattern Recognition，2012：2957-2964.