工程科学与技术   2019, Vol. 51 Issue (2): 144-150

Image Retrieval Based on Random Rotation Locality Preserving Hashing
ZHAO Shan, LI Yongsi
School of Computer Sci. and Technol., Henan Polytechnic Univ., Jiaozuo 454003, China
Abstract: In order to solve the problem that locality preserving projection hashing can results in the poor expression of image feature and lower retrieval efficiency when it is applied in image retrieval, a novel image retrieval method based on hashing combining principal component analysis (PCA) with locality preserving projection (LPP) is proposed. Firstly, the sample is reduced dimension with PCA, a random matrix is introduced to make rotation of the PCA transformational matrix. The original sample is projected into the PCA transformational matrix and the reduced-dimension PCA sample is achieved. Meanwhile, the similarity structure between samples is taken into account. The reduced-sample is mapped with LPP. On these basis, the projection matrix is constructed with a random matrix. Finally, the original sample is projected into the projection matrix and the hash coding is achieved. The presented method can keep the local and overall similarity structure of the samples because of the application of PCA and LPP. Furthermore, the quantization error between codes is reduced by introducing of random rotation, thus improving the efficiency of image retrieval. Experiments show that the proposed method can achieve better performance compared with other traditional methods.
Key words: image retrieval    hashing    principal component analysis (PCA)    locality preserving projection (LPP)

1 特征提取

1.1 PCA降维

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

 ${{ W}^*} = {{WR}}$ (1)

 ${ Y} = {{ W}^{*{\rm T}}}{ X}$ (2)
1.2 LPP投影

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

 ${\sum\limits_{ij} {\left( {{{ y}_i} - {{ y}_j}} \right)} ^2}{{ M}_{ij}}$ (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)

 $\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)

 ${\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)

 ${ 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)

 \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)

 ${ V} = {{ W}^{{*}}}{{ V}^1}$ (10)

 ${ V} = { W}{ R}{{ V}^1}$ (11)

 ${ V} = { W}{ R}{{ V}^1} +{ b}$ (12)

1.3 哈希编码

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

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

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

3. 先计算原始样本的协方差矩阵A=XXT

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

5. 生成一个随机正交矩阵R $\in$ Rtxt，并利用随机正交矩阵RW进行旋转，则为旋转后的矩阵 ${{{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$ Rd×t对特征向量V进行上下偏移得到最终的编码投影矩阵 ${{V}} = {{WR}}{{{V}}^1} +{ b}$

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

2 实　验

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

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

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

 图1 在3个数据集下3种方法在不同编码长度的MAP曲线 Fig. 1 MAP curves of three methods with different code lengths in three databases

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 在3个数据集下7种哈希方法对比的MAP曲线 Fig. 2 MAP curves of the seven methods in three databases

 图3 在3种数据集下7种算法不同编码位的P–R曲线 Fig. 3 P–R curves of the seven methods with different code lengths in three databases

3 结　论

 [1] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive hashing scheme based on p-stable distribution[C]//Proceedings of the 20 th Annual Symposium on Computational Geometry.New York:ACM,2004:253–262. [2] Kulis B,Grauman K.Kernelized locality-sensitive hashing for scalable image search[C]//Proceedings of IEEE Conference on Computer Vision.Kyoto:IEEE,2009:2130–2137. [3] Raginsky M.Locality-sensitive binary codes from shift-invariant kernels[C]//Proceedings of Neural Information Processing Systems.Vancouver:Elsevier,2009:1509–1517. [4] Kim S,Choi S.Bilinear random projections for locality-sensitive binary codes[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Boston:IEEE,2015:1338–1346. [5] Moura P,Laber E,Lopes H,et al. LSHSIM:A locality sensitive hashing based method for multiple-point geostatistics[J]. Computers & Geosciences, 2017, 107: 49-60. [6] Zhang W,Ji J,Zhu J,et al. BitHash:An efficient bitwise locality sensitive hashing method with applications[J]. Knowledge-Based Systems, 2016, 97: 40-47. DOI:10.1016/j.knosys.2016.01.022 [7] Wang J,Kumar S,Chang S,et al.Semi-supervised hashing for scalable image retrieval[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE,2010:3424–3431. [8] Leng C,Cheng J,Yuan T,et al.Learning binary codes with bagging PCA[C]//Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases.Nancy:Springer,2014,177–192. [9] Li P,Ren P. R2PCAH:Hashing with two-fold randomness on principal projections[J]. Neurocomputing, 2017, 235: 236-244. DOI:10.1016/j.neucom.2017.01.019 [10] Abdi H,Williams L J. Principal component analysis[J]. Wiley Interdisciplinary Reviews Computational Statistics, 2010, 2(4): 433-459. DOI:10.1002/wics.101 [11] He X,Niyogi P.Locality preserving projections[C]//Proceedings of the International Conference on Neural Information Processing Systems.Vancouver:ACM,2003:153–160. [12] Heo J,Lee Y,He J,et al.Spherical hashing[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Rhode:IEEE,2012:2957- 2964. [13] Gong Y,Lazebnik S.Iterative quantization:A procrustean approach to learning binary codes[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs:IEEE,2011:817–824. [14] Zhu X,Zhang L,Huang Z. A sparse embedding and least variance encoding approach to hashing[J]. IEEE Transaction on Image Processing, 2014, 23(9): 373-3750.