图像检索是指在大规模的图像数据库中快速并且准确地搜索到与给定图像相似的图像，而图像特征的提取是其中关键技术。由于哈希技术能够将原特征编码成紧致的二值哈希码，大幅降低内存消耗，同时在计算汉明距离时可以使用计算机内部运算器具有的异或运算，使计算可以在微秒量级内完成，缩减单次查询响应的所需时间，因此，基于哈希的图像检索技术近年来备受关注。基于哈希的图像检索方法是将图像的高维内容特征通过满足某些特性要求的哈希函数映射到汉明空间（二值空间）中，生成一个低维的哈希序列表示一幅图像，降低了图像检索系统对计算机内存空间的要求，提高检索速度，能够更好地适应大数据时代海量图像数据检索的要求。最经典的哈希方法是局部敏感哈希（locality sensitive hashing，LSH）^[1]，被认为是高维空间近似最近邻搜索的重要突破。但由于在构造哈希函数的过程中并没有利用数据本身，在长编码位数下会降低相似样本在哈希离散过程中的碰撞概率，导致检索的效率下降。为了克服LSH的局限，衍生出了很多改良和拓展的方法^[2–6]，并提出了数据依赖的图像哈希^[7]，利用数据自身所包含的特性构造哈希，在进行检索时具有更高的检索精度。主成分分析哈希（PCA hashing，PCAH）^[7]及其改进算法^[8–9]是一种基于数据依赖的哈希，主要利用主成分分析（principal component analysis，PCA）^[10]方法，通过线性变换寻找一组最优的单位正交基，并将原始数据投影到这组正交基上进行降维，通过保留最大方差构造哈希函数，在巨量数据中实现快速的相似性检索。而基于流形的局部保持投影（locality preserving projection，LPP）^[11]本质上也是一种线性降维方法并同时兼有流形学习的能力，主要是通过保留数据的局部相似性结构构造哈希，在数据投影中其不但能够很好地保持高维数据的局部结构，而且很容易获得内嵌低维坐标表示和提取新样本特征。但是，LPP本身容易受小样本问题的影响，并且在投影过程中无法保持数据的全局结构，因此，将LPP直接构造哈希运用于图像检索中，会存在低效、耗时等缺点。

为了解决LPP直接用于哈希图像检索存在的问题，作者提出了一种随机旋转局部保持哈希的图像检索算法RLPH （random rotation locality preserving hashing）。融合PCA和LPP技术，通过考虑原始数据的结构分布构造哈希，增加哈希函数与真实数据的关联性，确保检索效果。利用PCA技术对原始样本降维，引入随机旋转矩阵构造PCA变换矩阵，把高维空间向量映射到低维空间，得到PCA降维样本，在此基础上，对PCA降维样本进行LPP映射，并引入随机矩阵对特征向量进行偏移构造最终编码投影矩阵，将原始样本重新投影到编码投影矩阵中，并利用哈希编码将原始空间的特征向量映射为二进制编码，通过计算编码的汉明距离进行相似性检索。本研究的主要思想是针对LPP哈希的不足，结合PCA和LPP构造哈希，并利用随机旋转减少编码引起的量化误差，既可以增强判别性，还能在一定程度上保留相同图像特征的局部结构和全局信息，提高了算法的检索效率。大量实验证明了本文方法的可行性和高效性。

1 特征提取

图像检索技术主要根据有效的全局或局部图像特征进行相似性搜索，图像特征对其内容的表征能力至关重要。算法中，特征提取主要包括PCA降维，LPP投影和哈希编码3部分。

1.1 PCA降维

PCA是一种降低数据维度的有效方法，对于图像检索技术来说，其目的就是保留那些有区分能力的特征，即方差大的维度，去除掉那些方差小的维，降低整个数据矩阵的维数，减少计算量。设X= $\left[{{{ x}_1},{{ x}_2}, \cdots ,} \right.$ $\left. {{{ x}_n}} \right] \in {{{R}}^{d \times n}}$ ，为样本矩阵，n和d分别表示样本点的数目和样本点的维数。首先，对样本X进行PCA降维，并得到PCA变换矩阵W，其中，W= $\left[ {{ w}_1},{{ w}_2}, \cdots ,{{ w}_t}\right] \!\in\! {{{R}}^{d \times t}} $ ，即特征向量W所包含的特征向量个数t。为了减少编码时的量化误差，引入一个随机正交矩阵R^t×t对变换矩阵W进行旋转，使得哈希编码间的量化误差最小，把旋转后的W记为 ${ W}^*$ ，记作：

${{ W}^*} = {{WR}}$

(1)

式中， ${ W}^*$ = $[{ w}_1^*, { w}_2^*, \cdots, { w}_t^*]$ ， ${ W}^*$ $ \in $ R^d×t。最后，再将原始样本投影到变换矩阵 ${ W}^*$ 上得到PCA降维后的样本Y，即

${ Y} = {{ W}^{*{\rm T}}}{ X}$

(2)

1.2 LPP投影

LPP的基本思想就是寻找一个投影矩阵V，将高维空间R^d中的样本集X= $\left[ {{{ x}_1},{{ x}_2}, \cdots ,{{ x}_n}} \right]$ 映射为低维空间R^t（t<d）中的样本集Y= $\left[ {{{ y}_1},{{ y}_2}, \cdots ,{{ y}_n}} \right]$ ，即：y_i=V^Tx_i， $\left( {i = 1,2, \cdots ,n} \right)$ ，而且在R^d空间内互为近邻的两点经V映射后在R^d空间中仍互为近邻。其目标函数为：

${\sum\limits_{ij} {\left( {{{ y}_i} - {{ y}_j}} \right)} ^2}{{ M}_{ij}}$

(3)

通过简单的代数运算，目标函数（3）可以简化为：

$ \begin{aligned}[b] \frac{1}{2}{\sum\limits_{ij} {\left( {{{ y}_i} - {{ y}_j}} \right)} ^2}{{ M}_{ij}} = \frac{1}{2}{\sum\limits_{ij} {\left( {{{ V}^{\rm T}}{{ x}_i} - {{ V}^{\rm T}}{{ x}_j}} \right)} ^2}{{ M}_{ij}}= \hfill \\ {{ V}^{\rm T}}{ X}\left( {{ D} - { M}} \right){{ X}^{\rm T}} = {{ V}^{\rm T}}{ X}{ L}{{ X}^{\rm T}}{ V} \end{aligned} $

(4)

其中：M_ij是近邻图的权值矩阵，通常采用高斯核方法来设置，如果 ${ x}_i$ 与 ${ x}_j$ 之间有一条边相连， ${{ M}_{ij}} = {\rm{exp}}\left( { - {{\left| {\left| {{{ x}_i} - {{ x}_j}} \right|} \right|}^2}/2{\delta ^2}} \right)$ ，否则 ${{ M}_{ij}} = 0$ ；矩阵D是一个对角矩阵，其值为权值矩阵M的每一行或每一列的数据元素之和，即 ${{ D}_{ii}} = {\displaystyle\sum _j}{{ M}_{ij}}$ ， ${ L} ={ D} -{ M}$ ，为近邻图的拉普拉斯矩阵。在约束条件 ${{ V}^{\rm T}}{ X}{ D}{{ X}^{\rm T}}{ V} = 1$ 的情况下，最小化目标函数（4），得到最终目标函数如下：

$ \mathop {\arg \min}\limits_{ V} \;{{ V}^{\rm T}}{ X}{ L}{{ X}^{\rm T}}{ V}\;{\rm{ s}}{\rm{. t}}{{. }}\;{{ V}^{\rm T}}{ X}{ D}{{ X}^{\rm T}}{ V} = 1$

(5)

式中，LPP投影变换的矩阵就是式（5）求解后最小的t个特征值对应的特征向量构成的V= $\left[{{{ v}_1},{{ v}_2}, \cdots ,{{ v}_t}} \right]$ 。

将式（2）中的投影矩阵Y $ \in $ R^r×n进行LPP映射，构造最终的变换矩阵，其中Y是经过PCA投影之后得到的降维样本。在进行LPP映射之前先进行PCA处理能够有效地解决LPP计算过程中遇到的特征值问题，从而进一步提高算法的识别能力。把Y代入式（5）中得出新的目标函数如下：

${\mathop {\arg \min}\limits_{ V^1}}\;{{ V}^{1{\rm T}}}{ Y}{ L}{{ Y}^{\rm T}}{{ V}^1}\;{\rm{ s}}{\rm{. t}}{{. }}\;{{ V}^{1{\rm T}}}{ Y}{ D}{{ Y}^{\rm T}}{{ V}^1} = 1$

(6)

对式（6）求解后，V¹表示最小的r个特征值对应的特征向量V¹= $\left[ {{{ v}_1^1},{{ v}_2^1}, \cdots ,{{ v}_r^1}} \right]$ 。利用拉格朗日乘子法可将式（6）转化为：

$ { L}\left( {{ v}, \lambda } \right) = {{ V}^{1{\rm T}}}{ Y}{ L}{{ Y}^{\rm T}}{{ V}^1} - \lambda \left( {{{ V}^{1{\rm T}}}{ Y}{ D}{{ Y}^{\rm T}}{{ V}^1} - 1} \right) $

(7)

接着，对L( $ { v}$ ， $\lambda$ )中的 ${ v}$ 和 $\lambda $ 进行求导

$\left\{ \begin{aligned} & \frac{{\partial { L}}}{{\partial { V}}} = { Y}{ L}{{ Y}^{\rm T}}{{ V}^1} - \lambda { Y}{ D}{{ Y}^{\rm T}}{{ V}^1} = 0,\\ & \frac{{\partial { L}}}{{\partial \lambda }} = {{ V}^{1{\rm T}}}{ Y}{ L}{{ Y}^{\rm T}}{{ V}^1} - 1 = 0 \end{aligned} \right.$

(8)

结果为：

$ { Y}{ L}{{ Y}^{\rm T}}{{ V}^1} = \lambda { Y}{ D}{{ Y}^{\rm T}}{{ V}^1} $

(9)

在式（9）中的YLY^T和YDY^T都是R^t×t的非奇异矩阵，只需要求解一个广义特征值问题。式（2）和（9）联立便可以求得一个新的投影矩阵V $ \in $ R^d×t：

$ { V} = {{ W}^{{*}}}{{ V}^1} $

(10)

又因为式（1）中利用随机正交矩阵对W进行旋转，因此用W代替式（10）中的 ${ W}^*$ 。此时式（10）便化为：

$ { V} = { W}{ R}{{ V}^1} $

(11)

式中，V= $\left[ {{{ v}_1},{{ v}_2}, \cdots ,{{ v}_t}} \right]$ 是由求解后最小的t个特征值对应的特征向量构成。

在此基础上，构造一个随机矩阵 ${ b} \in $ R^d×t，对特征向量V进行偏移得到最终的编码投影矩阵：

$ { V} = { W}{ R}{{ V}^1} +{ b} $

(12)

最后，将原始样本X投影到矩阵V上，得到低维的样本数据。

1.3 哈希编码

相似的样本具有相似的哈希编码，也就是说，欧氏空间中相近的点在汉明空间中也应该是相邻点，因此，哈希函数必须能够在汉明空间中保持数据在欧氏空间中的位置结构。利用式（13）的哈希函数对得到的低维样本进行0或1的二值编码，就可以得到最终的二进制哈希码。

$ { H}={\rm sign}\left( {{{ V}^{\rm T}}{ X}} \right) $

(13)

这样，通过哈希函数把原始样本进行最后的压缩。

具体算法描述如下：

1. 输入：X= $\left[{{{ x}_1},{{ x}_2}, \cdots ,{{ x}_n}} \right]$ $ \in $ R^d×n，编码长度为t。

2. 输出：哈希编码矩阵H。

3. 先计算原始样本的协方差矩阵A=XX^T。

4. 进行PCA降维得到变换矩阵W= $\left[{{{ w}_1},{{ w}_2}, \cdots ,} \right.$ w_t] $ \in $ R^d×t。

5. 生成一个随机正交矩阵R $ \in $ R^txt，并利用随机正交矩阵R对W进行旋转，则为旋转后的矩阵 ${{{W}}^*} ={{WR}}$ 。

6. 输入样本X经过 $ { W}^*$ 投影之后得到降维样本Y= $ { W}^{*{\rm T}}$ =(WR)^TX。

7. 再把Y=(WR)^TX代入 ${{YL}}{{{Y}}^{\rm T}}{{{V}}^1} = $ $\lambda {{YD}}{{{Y}}^{\rm T}}{{{V}}^1}$ 中，得到 ${{V}} = {{WR}}{{{V}}^1}$ 。

8. 采用随机矩阵 ${{b}}\!\in $ R^d×t对特征向量V进行上下偏移得到最终的编码投影矩阵 ${{V}} = {{WR}}{{{V}}^1} +{ b}$ 。

9. 将原始样本X投影到矩阵V上，然后利用哈希函数进行哈希编码得到最后的二进制码矩阵H=[h₁， $\left. {{h_2}, \cdots ,{h_n}} \right]$ $ \in $ {–1，1}^t×n。

2 实　验

为验证本文所提算法的性能，在Windows 8系统MATLAB R2016a环境下，在使用3个公开的人脸图像数据库AR、PIE和UMIST组建测试数据集进行检索测试，并与相应的方法进行了比较。表1给出了测试数据库的大小和维数。

AR：由120位志愿者的彩色图像组成，每位志愿者都有1 680张图像，每张图像均由2 000维特征向量表示，其中每个人由14张不同人脸图像组成。

PIE：由68位志愿者的41 368张图像组成，其中，包括每个人的13种姿态、43种光照条件和4种表情下的照片。

UMIST：由20位志愿者的564张图像组成，每位志愿者都包含从侧面到正面的不同角度、不同姿态的多幅图像。

为了保证实验公平性，对于以上每一个数据库，分别随机选择30个数据作为实验的测试样本，剩下的全部作为训练样本。采用汉明排序准则进行定量评价，即对于查询图像集中的任意一张图像，在检索时根据汉明距离进行排序。检索性能通过平均检索精度（mean average precision，MAP）和查准率–召回率曲线（precision–recall curve，P–R）两个指标衡量。

将本文算法（RLPH）、仅在PCA降维后的子空间中进行LPP映射的算法（LPPH）以及仅基于PCA随机旋转算法（LPP–RR）3种方法在不同的编码长度下的性能进行对比实验，图1给出了3个不同的数据集下3种方法的MAP曲线。从图1可以看出，RLPH由于把PCA和LPP两种方法有效地进行结合，充分保留了原始样本的局部和全局有效信息，而且在PCA降维处理时采用随机旋转构造降维矩阵，并结合随机偏移，有效减少了编码时的量化误差，因此，RLPH算法比LPP–RR和LPPH要占优势。

实验中，为进一步验证本文算法的性能，将本文方法（RLPH）与6种经典哈希方法进行了对比。为了保证实验的可靠性，6种哈希算法都是在原始数据未做任何处理的基础上运行，并且其参数设置与原文献保持一致。

LSH^[1]：局部敏感哈希（locality sensitive hashing）。一种经典的无监督哈希方法，主要采用随机投影作为哈希函数集。

PCAH^[2]：主成分分析哈希（principle component analysis hashing）。最简单的数据依赖哈希方法，直接对数据的协方差矩阵进行特征分解，并选取一部分特征向量为投影向量，数据经过投影后直接进行二值化获得哈希编码。

SpH^[12]：球哈希（spherical hashing）。是一种基于超球面的哈希方法，哈希函数由超球面函数定义，在计算汉明距离时采用球汉明距离进行相似度排序。

ITQ^[13]：迭代量化哈希（iterative quantization）。这是一个既简单又高效的哈希方法。该方法分两部分，第1部分是PCA降维，第2部分是旋转迭代。

PCA–RR^[13]：PCA随机旋转哈希（PCA-random rotation）。主要利用随机正交矩阵对PCA投影后的特征向量进行随机旋转。

SELVE^[14]：稀疏嵌入与最小方差哈希（sparse embedding and least variance encoding）。将稀疏样本嵌入到训练样本空间，学习出一个字典以对稀疏嵌入特征进行编码，通过二值化编码系统构造哈希码。

表2给出了7种方法在3个数据集下分别进行32、64和96bit编码的MAP值。从表2中同样可以看出：RLPH的MAP值最高。对PCAH而言，由于在进行PCA降维时的噪音信息使得其随着编码长度的增加性能变差，3个数据集中随着编码长度的增加，其MAP值逐渐降低。PCA–RR采用随机正交矩阵对PCA进行旋转使得编码间的量化误差最小，其检索性能较好。ITQ先采用PCA对原始数据进行降维，然后把原始数据分别映射到超立方体的顶点，将该超立方体在空间中旋转，通过求解初旋转矩阵得到最佳的映射方式，检索性能也较好。而RLPH引入随机正交矩阵对PCA变换矩阵进行随机旋转，减少了编码间的量化误差，而且PCA和 LPP的有效结合使很多有用的信息都被整合在RLPH中，因此检索性能优于其他几种算法。

同时，将RLPH与6种算法的复杂度在PIE数据集上进行了对比实验，结果如表3所示。由表3可以看出，由于RLPH采用将PCA和LPP两种技术结合的方法保留原始样本的全局和局部信息，从而提升特征对图像内容的表征能力，而且为降低量化误差，引入了随机旋转矩阵构造PCA降维矩阵，因此，与简单哈希算法相比，本文算法复杂度较高，但由于图像特征是先提前提取并进行存储再基于汉明距离进行最终的检索，因此，本文算法的复杂度并不影响最终的检索效率。

图2给出了以上7种方法在3个数据集上的MAP值对比曲线。从图2可以看出，在3种数据集上RLPH都具有较好的性能。而且，PCAH方法随着编码长度的增加其MAP曲线迅速地下降，其重要的原因是在PCA进行特征值分解时引入了一些噪音，编码长度越大，其引入的噪音越多，性能越差。RLPH充分地利用随机旋转获得具有辨识度高的特征向量，有效地解决了在传统LPP在基于哈希的图像检索中出现的低效、耗时等缺点。

为更全面评价所提算法的性能，采用查准率–召回率曲线指标（P–R）分别在3个数据集下将7种算法进行对比实验。实验结果如图3所示。

由图3可以看出，随着编码长度的增加，各哈希算法的P–R曲线与横纵轴围成的曲线面积逐渐增大，该面积反映了平均检索精度的大小，因此，当编码长度增加时，其平均检索精度也是逐渐增加。同时，在不同编码长度下本文方法的性能同样优于其他哈希算法，表明PCA和LPP结合构造哈希方法的有效性。

3 结　论

作者提出了一种基于哈希的图像检索方法，首先对样本进行PCA变换，引入随机矩阵对变换矩阵进行旋转构造PCA降维矩阵，降低编码时的量化误差，然后在此基础上对降维后样本进行LPP投影，重构编码投影矩阵，最后对投影后的样本进行哈希编码，将得到的有效、紧凑的二进制码用于图像检索。该方法能够在投影过程中保持数据的全局结构和局部信息，有效解决了LPP直接用于哈希图像检索存在的问题。实验结果证明，该算法取得了较好的效果。