一种基于多标签最小二乘哈希算法的大规模图像检索方法

摘要

本发明公开了一种基于多标签最小二乘哈希算法的大规模图像检索方法，包括：提取训练集中图像的视觉特征和监督信息，分别得到原始视觉特征数据矩阵和监督信息矩阵，训练集中每幅图像均包括多个标签信息；对原始视觉特征数据矩阵进行两次降维处理，分别得到第一次降维最优投影矩阵和第二次降维最优投影矩阵；求取最优旋转矩阵及两次降维后的视觉特征数据矩阵的哈希编码，得到标准哈希编码；根据训练集得到的第一次降维最优投影矩阵、第二次降维最优投影矩阵和最优旋转矩阵，检索图像库中的图像时，求取图像库中的每幅图像的哈希编码，并计算图像库中的每幅图像的哈希编码与标准哈希编码之间的海明距离，输出图像库中与标准哈希编码之间具有最小海明距离的图像。

说明书

技术领域

本发明涉及图像处理领域，具体涉及一种基于多标签最小二乘哈希算法的大规模图像检 索方法。

背景技术

最邻近搜索(NN)是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺 度空间M中给定一个点集S和一个目标点q∈M，在S中找到距离q最近的点。很多情况下， M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。随着互联网近几年不断 发展，互联网中产生了巨大规模的数据。在大规模数据中最近邻搜索往往需要很多时间，许 多情况下，我们选择近似最近邻搜索(ANN)算法，来近似NN的结果，使计算复杂度大大 下降。

在ANN方法发展的这几年中，提出了许多哈希方法用于高效的近似最近邻ANN搜索。 这些哈希方法把高维数据嵌入在一个能够保持相似性的低维海明空间中，比较类似的图像在 低维海明空间距离比较小。如果把现有的哈希方法按监督信息划分，大致分为3中类型：无 监督哈希、有监督哈希、半监督哈希。

当数据有监督信息的时候，有监督哈希方法性能总是表现的比无监督哈希方法要好。在 实际应用中，多标签数据会经常出现在监督搜索场景中(多标签指的是一个样本同时有多个标 签)，比如对一张描述“江南”的图像来讲，可能有水、山、竹子、白云、人等事物同时出现在 图像中；所以，研究多标签哈希方法在监督哈希领域有非常大有意义。然而，现有的哈希方 法主要是解决单标签的数据，很少有多标签哈希方法被提出。

发明内容

为应对并处理有监督数据的图像，该发明提出了一种基于多标签最小二乘哈希算法的大 规模图像检索方法。该方法提高了模型的泛化能力，而且对多标签数据的图像搜索结果有很 大提高。

为实现上述目的，本发明的具体方案如下：

一种基于多标签最小二乘哈希算法的大规模图像检索方法，包括以下步骤：

步骤(1)：提取训练集中图像的视觉特征和监督信息，分别得到原始视觉特征数据矩阵 和监督信息矩阵，所述训练集中每幅图像均包括多个标签信息；

步骤(2)：对原始视觉特征数据矩阵进行两次降维处理，分别得到第一次降维最优投影 矩阵和第二次降维最优投影矩阵；

步骤(3)：优化两次降维后的视觉特征数据矩阵，求取最优旋转矩阵R以及两次降维后 的视觉特征数据矩阵的哈希编码，得到标准哈希编码；

步骤(4)：检索图像库中的图像时，根据训练集得到的第一次降维最优投影矩阵、第二 次降维最优投影矩阵和最优旋转矩阵R，求取图像库中的每幅图像的哈希编码，并计算图像 库中的每幅图像的哈希编码与标准哈希编码之间的海明距离，输出图像库中与标准哈希编码 之间具有最小海明距离的图像。

所述步骤(1)的具体过程为：

步骤(1.1)：对训练集中每幅图像提取d维的视觉特征，得到一个d×n的原始视觉特征 数据矩阵X＝[x₁,...,x_n]∈R^d×n，其中，n表示训练集中训练样本的个数，所述训练样本是具有标 签的图像；

步骤(1.2)：标注训练集中每张图中的标签，然后对所标注的结果进行筛选和统一；假 设标注后图像库中的所有图像一共有k个标签，每幅图像的标签信息表示为k×1的向量；

当图像包含某个标签，标签向量中对应位置为1，否则为0，那么对于训练样本个数为n 的训练集得到一个k×n的监督信息矩阵Y＝[y₁,...,y_n]∈R^k×n。

所述步骤(2)的具体过程为：

步骤(2.1)：使用与典型相关分析等价的最小二乘法，把训练集的原始视觉特征数据矩 阵均投影到与训练集的监督信息矩阵维度一致的低维空间中，得到训练集的第一次降维后的 视觉特征数据矩阵；

步骤(2.2)：使用主成分析方法，把经过步骤(2.1)降维后的视觉特征数据矩阵再投影 预设的哈希码长度的维度空间中，得到第二次降维后的视觉特征数据矩阵。

所述步骤(2.1)的具体过程为：

步骤(2.1.1)：确定投影矩阵W^d×k的求解模型该模型采用典型相关分 析的等价形式的最小二乘法加上二范数约束的方法获得：

      $\tilde{T}={\left(Y^{T}Y\right)}^{-\frac{1}{2}}{Y}^T$      

      $\left(\begin{array}{c}\underset{W,\alpha }{\min }{f}_{\mathrm{LS}-\mathrm{CCA}2}\left(W^{d\times k}\right)=\underset{j=1}{\overset{k}{\Sigma }}(\underset{i=1}{\overset{n}{\Sigma }}{(w_j^T{x}_i-{\tilde{T}}_{\mathrm{ij}})}^2+\alpha {\left|\right|w_j\left|\right|}_2^2)\\ ={\left|\right|{\left(W^{d\times k}\right)}^{T}X-\tilde{T}\left|\right|}_F^2+\alpha {\left|\right|W^{d\times k}\left|\right|}_F^2\end{array}\right)---\left(1\right)$      

其中，为类指示矩阵；Y为监督信息；X为原始视觉特征数据矩阵，(W^d×k)^T是W^d×k的 转值矩阵；w_j是W^d×k矩阵的第j列，是w_j的转置；k指的是训练集中样本具有标签的总个 数，n是训练样本的个数；α表示系数；

步骤(2.1.2)：采用最小二乘QR分解方法来求解公式(1)，得到W^d×k的最优投影矩阵， 记为

步骤(2.1.3)：将投影矩阵代入降维方程中，得到第一次降维后的视觉特征数据矩阵X₁， 所述降维方程的表达式为：

      $X_1={\left(W_{\mathrm{LS}-\mathrm{CCA}2}^{d\times k}\right)}^{T}X---\left(2\right)$      

其中，X为原始视觉特征数据矩阵；是的转置矩阵。

所述步骤(2.2)中获取第二次降维后的视觉特征数据矩阵再投影预设的哈希码长度的维 度空间中的线性映射投影矩阵的具体过程为：

步骤(2.2.1)：假设把第二次降维后的视觉特征数据矩阵再投影预设的哈希码长度的维度 空间中的线性映射投影矩阵为W^k×c，确定其优化函数：

      $\underset{W}{\max }{f}_{\mathrm{PCA}}\left(W^{k\times c}\right)=\underset{i=1}{\overset{c}{\Sigma }}\mathrm{var}\left(h_i\left(x\right)\right)=\underset{i=1}{\overset{c}{\Sigma }}\mathrm{var}\left(\mathrm{sgn}\left(w_i^{T}x\right)\right)---\left(3\right)$      

其中，h_i(x)表示假定的哈希函数；c表示要将数据降到的维数；w_i表示W^k×c的第i列；表示w_i的转置；n表示样本的个数；X为原始视觉特征数据矩阵；x为原始视觉特征数据矩阵 的元素；

步骤(2.2.2)：对sgn()函数进行松弛，然后得到下列优化函数：

      $\left(\begin{array}{c}\underset{W}{\max }{f}_{\mathrm{PCA}}\left(W^{k\times c}\right)=\frac{1}{n}\underset{i=1}{\overset{c}{\Sigma }}{w}_i^T{X}_1^T{X}_1{w}_i\\ =\frac{1}{n}\mathrm{tr}\left({\left(W^{k\times c}\right)}^T{X}_1^T{X}_1{W}^{k\times c}\right)\end{array}\right)$      

s.t.  (W^k×c)^TW^k×c＝I  (4)

其中，X₁为第一次降维后的视觉特征数据矩阵；表示求取矩阵 的主对角线上的元素之和；n表示训练集的样本个数；

步骤(2.2.3)：通过分解特征值，来求得各个特征值对应的特征向量，从而得到投影矩阵 W^k×c的最优矩阵

所述步骤(2.2)中的第二次降维后的视觉特征数据矩阵X₂为：

      $X_2={\left(W_{\mathrm{PCA}}^{k\times c}\right)}^T{X}_1---\left(5\right)$      

其中，为的转置矩阵；X₁为第一次降维后的视觉特征数据矩阵。

所述步骤(3)中使用迭代量化方法优化经过步骤(2)降维后的视觉特征数据矩阵。

所述步骤(3)中获取标准哈希编码的具体过程为：

步骤(3.1)：随机生成出一个旋转矩阵R；

步骤(3.2)：采用旋转矩阵R来旋转经过步骤(2)降维后的视觉特征数据矩阵；

步骤(3.3)：采用符号函数sgn()，把使用步骤(3.2)旋转过后的视觉特征数据矩阵进行 二值化，得到二值化矩阵B；

步骤(3.4)：将旋转矩阵R和二值化矩阵B代入公式(6)中，重复步骤(3.2)～步骤(3.3)， 得到公式(6)的局部最优解，也就是最优旋转矩阵R；

      $\underset{B,R}{\min }{f(B,R)}_{\mathrm{ITO}}={\left|\right|B-R^T{X}_2\left|\right|}_F^2$      

B＝sgn(X₃)

X₃＝R^TX₂  (6)

其中，X₂为第二次降维后的视觉特征数据矩阵；R^T为R的转置矩阵；

步骤(3.5)：再重复步骤(3.2)～步骤(3.3)，得到标准哈希编码。

本发明的有益效果为：

(1)该发明可以直接对多标签数据进行二进制编码；

(2)在对数据进行二进制转化的时候可以充分考虑数据在标签空间中的相似性；

(3)使用该方法对数据进行二进制转化后，可以大大提高数据的检索速度，并且降低数 据的存储空间。

附图说明

图1为本发明的基于多标签最小二乘哈希算法的大规模图像检索方法流程图。

具体实施方式

下面结合附图与实施例对本发明做进一步说明：

如图1所示，一种基于多标签最小二乘哈希算法的大规模图像检索方法，包括以下步骤：

步骤(1)：提取训练集中图像的视觉特征和监督信息，分别得到原始视觉特征数据矩阵 和监督信息矩阵，所述训练集中每幅图像均包括多个标签信息；

步骤(2)：对原始视觉特征数据矩阵进行两次降维处理，分别得到第一次降维最优投影 矩阵和第二次降维最优投影矩阵；

步骤(3)：优化两次降维后的视觉特征数据矩阵，求取最优旋转矩阵R以及两次降维后 的视觉特征数据矩阵的哈希编码，得到标准哈希编码；

步骤(4)：检索图像库中的图像时，根据训练集得到的第一次降维最优投影矩阵、第二 次降维最优投影矩阵和最优旋转矩阵R，求取图像库中的每幅图像的哈希编码，并计算图像 库中的每幅图像的哈希编码与标准哈希编码之间的海明距离，输出图像库中与标准哈希编码 之间具有最小海明距离的图像。

步骤(1)：对做训练集的图像，提取监督信息和视觉特征；

所述步骤(1)中，假设训练集中的训练样本一共有n个，提取提取视觉特征的方法为：

对每幅图像提取d维的视觉特征，比如GIST特征，具体实施过程中可以提取其他的视 觉特征或者多种特征进行组合，得到一个d×n的原始视觉特征数据矩阵X＝[x₁,...,x_n]∈R^d×n， 其中，所述训练样本是具有标签的图像。

提取提监督信息的方法为：

对于训练数据的标签采取人工的方式来对其进行标注，即多人对数据集中的数据进行标 注，然后对所标注的结果进行筛选和统一；假设标注后数据集的所有图像一共有k个标签， 每幅图像的标签信息可以表示为k×1的向量。其中，如果该图像包含某个标签，标签向量中 对应位置为1，否则为0。在该表示条件下，对于训练样本个数为n的训练集得到一个k×n的 监督信息矩阵Y＝[y₁,...,y_n]∈R^k×n。

所述步骤(2)的具体过程为：

步骤(2.1)：使用与典型相关分析等价的最小二乘法，把待检索图像和训练集的每一幅 图像的原始视觉特征数据矩阵均投影到与训练集的监督信息矩阵维度一致的低维空间中，得 到待检索图像和训练集中每一幅图像的第一次降维后的视觉特征数据矩阵；

步骤(2.2)：使用主成分析方法，把经过步骤(2.1)降维后的视觉特征数据矩阵再投影 预设的哈希码长度的维度空间中，得到第二次降维后的视觉特征数据矩阵。

所述步骤(2.1)中，使用CCA的等价形式的最小二乘法，把原始数据特征数据投影到 符合监督信息的低维空间，具体过程如下：

在这个步骤中，目的是寻找一个投影矩阵W^d×k把原始数据特征数据X投影到符合监督 信息Y的低维空间，使用的目标函数是典型相关分析(CCA)的等价形式的最小二乘法，并 且在此形式之上加上二范数约束项，来提高目标函数的效果。

具体做法如下，先定义一个特别类指示矩阵，从而可以得到CCA和最小二乘法的等价 形式，在此称其为LS-CCA；然后，在LS-CCA模型上添加一个二范数约束项，来控制模型 的复杂性，提高了模型的泛化能力。

假定加入二范数约束项的目标函数为LS-CCA2，则它的形式如下：

      $\tilde{T}={\left(Y^{T}Y\right)}^{-\frac{1}{2}}{Y}^T$      

      $\left(\begin{array}{c}\underset{W,\alpha }{\min }{f}_{\mathrm{LS}-\mathrm{CCA}2}\left(W^{d\times k}\right)=\underset{j=1}{\overset{k}{\Sigma }}(\underset{i=1}{\overset{n}{\Sigma }}{(w_j^T{x}_i-{\tilde{T}}_{\mathrm{ij}})}^2+\alpha {\left|\right|w_j\left|\right|}_2^2)\\ ={\left|\right|{\left(W^{d\times k}\right)}^{T}X-\tilde{T}\left|\right|}_F^2+\alpha {\left|\right|W^{d\times k}\left|\right|}_F^2\end{array}\right)---\left(1\right)$             

其中，为类指示矩阵；Y为监督信息；X为原始视觉特征数据矩阵，(W^d×k)^T是W^d×k的 转值矩阵；w_j是W^d×k矩阵的第j列，是w_j的转置；k指的是训练集中样本具有标签的总个 数，n是训练样本的个数；在对该函数进行优化求解时，α表示系数，通过交叉验证的方法 得到的，在实际运用中也采用默认值1。然后，采用最小二乘QR分解方法(LSQR)来求最 优解，也就是映射矩阵W。假定求得的最优解为然后可以用此降维矩阵对数据特 征原始矩阵X进行降维，把数据投影到符合标签信息的低维空间中，即使用公式(2)对数 据X进行降维。

所述步骤(2.2)中，使用主成分析方法(PCA)，解决一个特征值分解的问题，把第二 次降维后的数据再投影我们需要的符合哈希码长度的空间。PCA主要用于数据降维，PCA的 问题其实是一个把原始数据矩阵变换和投影问题，使得变换后的数据有着最大的方差。所 以，目标还是求出一个最优的线性映射投影矩阵，即

      $\underset{W}{\max }{f}_{\mathrm{PCA}}\left(W^{k\times c}\right)=\underset{i=1}{\overset{c}{\Sigma }}\mathrm{var}\left(h_i\left(x\right)\right)=\underset{i=1}{\overset{c}{\Sigma }}\mathrm{var}\left(\mathrm{sgn}\left(w_i^{T}x\right)\right)---\left(3\right)$      

其中，h_i(x)表示假定的哈希函数；c表示要将数据降到的维数；w_i表示W^k×c的第i列；表示w_i的转置；n表示样本的个数；X为原始视觉特征数据矩阵；x为原始视觉特征数据矩阵 的元素；公式(3)的约束函数为：

      $\left(\begin{array}{cc}s.t.& \frac{1}{n}{\left(B^{\prime }\right)}^T\left(B^{\prime }\right)=I\end{array}\right)$      

            

在这里我们可以对sgn()函数进行松弛，即去掉对数据的二值化，从而可以得到下列目标 函数：

      $\left(\begin{array}{c}\underset{W}{\max }{f}_{\mathrm{PCA}}\left(W^{k\times c}\right)=\underset{i=1}{\overset{c}{\Sigma }}E\left({\left|\right|w_i^{T}x\left|\right|}_2^2\right)=\frac{1}{n}\underset{i=1}{\overset{c}{\Sigma }}{w}_i^T{X}_1^T{X}_1{w}_i\\ =\frac{1}{n}\mathrm{tr}\left({\left(W^{k\times c}\right)}^T{X}_1^T{X}_1{W}^{k\times c}\right)\end{array}\right)$      

s.t.  (W^k×c)^TW^k×c＝I  (4)

其中，约束项(W^k×c)^TW^k×c＝I可以使投影的哈希超平面彼此正交；X₁为第一次降维后的 视觉特征数据矩阵；表示求取矩阵的主对角线上的元素 之和；n表示训练集的样本个数；

优化这个目标函数的具体做法通过解决一个特征值分解问题。即求出协方差矩阵前 c个特征值对应的特征向量，这c个特征向量作成一个投影矩阵得到该矩阵后，可以 用此降维矩阵的转置对数据经过第二次降维后的数据进行降维，从而把数据投影到我们需要 的符合哈希码长度的维度空间中，即

      $X_2={\left(W_{\mathrm{PCA}}^{k\times c}\right)}^T{X}_1---\left(5\right)$      

其中，为的转置矩阵；X₁为第一次降维后的视觉特征数据矩阵。

所述步骤(3)中，使用迭代量化的方法优化经过步骤(2)降维后的数据。

训练出一个旋转矩阵来旋转经过步骤(2)降维后的数据矩阵，来减少量化误差。为此， 先定义一个量化误差的公式||sgn(v)-v||，其中，v∈R^c是投影后的数据向量，最后得到的数据量 化误差越小，说明最后得到的哈希编码越好保护了数据原来的局部结构。

其中，定义的迭代误差损失函数如下：

      $\underset{B,R}{\min }{f(B,R)}_{\mathrm{ITO}}={\left|\right|B-R^T{X}_2\left|\right|}_F^2$      

B＝sgn(X₃)

X₃＝R^TX₂  (6)

其中，X₂为第二次降维后的视觉特征数据矩阵；在这个损失函数中，R^T为旋转矩阵R 的转置矩阵；在对以上函数进行优化时，先初始化一个随机矩阵R，然后用类似k-means的 迭代量化过程来找量化误差的局部最小值。

在每一次迭代中，先固定R矩阵，然后更新B矩阵，然后再固定B矩阵，然后再更新 R矩阵。重复这一过程，我们就可以找到局部最优解R。

一旦通过以上方法得到旋转矩阵R，就可以用这个旋转矩阵来投影经过步骤(2)处理的 数据X₂，来最小化这个量化误差；使用sgn函数把使用步骤(2)旋转过后的数据转化为二 进制的哈希编码B，即B＝sgn(X₃)。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限 制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付 出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。