一种基于鲁棒非负矩阵分解的图像检索方法

摘要

本发明公开了一种基于鲁棒非负矩阵分解的图像检索方法。该方法针对非负矩阵分解算法模型在图像间关系表达和抗噪两方面的不足，首先依据图像数据的视觉特征集X构建表征数据分布关系的L1图约束，并加入稀疏噪声项，来构建鲁棒非负矩阵分解算法模型；接着在模型训练阶段，采用迭代优化求解方法，从X中得到图像特征基矩阵U和所有图像在U所展开的子空间中的特征表达V；最后在图像检索时，将检索参考的图像x转换到U的子空间，得到新特征表达v；依据v与图像数据集中图像的距离，对图像排序，返回距离最小的前K个图像给用户，实现对图像的检索功能。本方法具有较强的抗噪能力，对新图像的处理计算时间为线性时间，能够快速准确地进行图像检索。

说明书

技术领域

本发明涉及基于内容的图像检索和非负矩阵分解方法，尤其涉及一种基于鲁棒非负矩阵分解的图像检索方法。

背景技术

近年来，随着互联网络和智能手机、数码相机的普及，大量的图像资源被源源不断地产生出来。为了对这些图像资源进行有效的组织管理和检索，各种图像检索技术也随之被提出。目前，图像检索已经成为计算机视觉，尤其是多媒体检索领域里的一个研究热点。

除了最早的基于关键字的图像检索技术，目前绝大部分的图像检索技术都是基于内容的图像检索技术。基于内容的图像检索技术是通过从图像提取表征各种图像视觉特征的视觉特征，然后基于特定的算法计算用户提交的待检索图像与图像数据库中各个图片之间的相似性，即距离，从而依据特征距离的大小，对图像进行排序，返回给用户距离值较小的图像，实现对图像数据库中图像的检索。

在基于内容的图像检索算法中，数据降维算法是一种广泛被使用的技术。该技术的核心思想是认为原始图像特征空间存在一定的不足，无法有效地将不同类型的图像区分开来，因此希望寻找到一个合适的特征子空间，在该子空间上不同类型的图像彼此分开，而同类型的图像彼此聚拢。这类方法包括：主成分分析（Principal Component Analysis,PCA），线性鉴别分析（Linear Discriminant Analysis，LDA），非负矩阵分解（Nonnegative Matrix Factorization，NMF）和各种流形学习算法，如多维标度分析（Multidimensional Scaling，MDS），局部线性嵌套（Local Linear Embedded，LLE），局部保持投影（Local Preserving Projection，LPP）等。

在这些子空间方法中，NMF对降维后的数据添加了非负性约束，其目标函数是求解两个非负矩阵U和V，使得X≈UV。由于非负性约束的引入，使得NMF能够学习得到具有局部特征的基矩阵U，也获得了一种与人们认知中局部构成整体所一致的基于局部的数据表达方法。因此该方法的可解释性比较强，被广泛应用到图像检索，人脸识别，数字识别，文本分类等应用。

Liang等将NMF的初始化过程扩展为有监督的初始化，然后使用NMF在隐含语义索引中，用来寻找从底层视觉特征到高层语义特征之间的关系。BeAbdallah等人则采用NMF构建图像的隐含表达，用来提高图像的标注准确性。Caicedo等人基于NMF生成多模态图像表达，并在构建NMF目标函数的时候考虑图像语义信息。

然而，在传统的NMF对图像数据间的关系表达和抗噪声能方法比较弱。针对这个两方面问题，本方法借助L1图在视觉特征的自动选择特性，构建视觉L1图约束，同时引入稀疏噪声项约束，然后将这两种约束条件加入到传统的NMF算法框架中，得到鲁棒非负矩阵分解算法模型。基于所提出的模型，对新图像的处理计算时间为线性时间，能够快速准确地进行图像检索。

发明内容

本发明的目的是克服现有基于非负矩阵分解在图像间关系表达和抗噪声两方面上的不足，提出一种基于鲁棒非负矩阵分解的图像检索方法。

基于鲁棒非负矩阵分解的图像检索方法包括如下步骤：

1)从公共图像数据集Corel5K中选择50类共5000张图像，提取PHOG视觉特征[1]集X＝[x₁,...,x_n]，其中n＝5000，x_i为第i张图像所对应的PHOG视觉特征向量；将PHOG视觉特征集X作为所要构建的L1图的顶点，L1图的边权重矩阵W＝[w₁,...,w_n]，，其中w_i计算如下：

$>\left(\begin{array}{c}\min {\left|\right|w_i\left|\right|}_1\\ s.t.\left|\right|x_i-X{w}_i\left|\right|\le ϵ,w_{\mathrm{ii}}=0\forall i\end{array}\right)---1$>

其中，x_i为第i幅图像的视觉特征，w_i为矩阵W的第i列，ε为误差系数，w_ii为向量w_i的第i个分量；

构建表征图像数据分布结构关系的L1图约束如下：

$>\left(\begin{array}{c}\min R_g={\Sigma }_{i=1}^n{\left|\right|v_i-V{w}_i\left|\right|}^2={\left|\right|V-\mathrm{VW}\left|\right|}_F^2\\ =\mathrm{tr}\left(V(I-W){(I-W)}^T{V}^T\right)=\mathrm{tr}\left({\mathrm{VGV}}^T\right)\end{array}\right)---2$>

其中，G＝(I-W)(I-W)^T，V＝[v₁,...,v_n]为图像集在子空间上的特征表达，I为单位矩阵；

2)将L1图约束和稀疏噪声约束项E加入到传统的非负矩阵分解算法框架中，构建鲁棒非负矩阵矩阵分解算法模型：

$>\underset{U,V\ge 0,E}{\min }{\left|\right|X-\mathrm{UV}-E\left|\right|}_F^2+{\lambda }_1·\left|\right|E\left|\right|+{\lambda }_2·{\left|\right|U\left|\right|}_F^2+{\lambda }_3·\mathrm{tr}\left({\mathrm{VGV}}^T\right)---3$>

其中，λ₁，λ₂和λ₃为正则化参数，在实验中分别设置为0.01，0.001和0.1，U∈R^d×r为保持视觉和语义相似性的图像基矩阵，V∈R^r×n为图像基矩阵U所展开的子空间中的特征表达，E∈R^d×n是稀疏噪声约束项，d为图像特征的维度，r为低维特征空间的维度；

3)利用图像数据集对公式3算法模型进行训练，采用迭代优化求解，计算得到保持视觉和语义相似性的图像基矩阵U和所有图像在图像基矩阵U所展开的子空间中的特征表达V，计算步骤如下：

i)随机初始化U，V和E矩阵，令中间变量X_e＝X-E；

ii)固定E，迭代计算U和V，计算公式如下：

$>U_{\mathrm{ij}}\leftarrow U_{\mathrm{ij}}\frac{{\left({\tilde{X}}_e{\tilde{V}}^T\right)}_{\mathrm{ij}}}{{\left(U\tilde{V}{\tilde{V}}^T\right)}_{\mathrm{ij}}}---4$>

$>V_{\mathrm{ij}}\leftarrow V_{\mathrm{ij}}\sqrt{\frac{{(U^T{X}_e+{\lambda }_3{\mathrm{VG}}^{-})}_{\mathrm{ij}}}{{(U^T\mathrm{UV}+{\lambda }_3{\mathrm{VG}}^{+})}_{\mathrm{ij}}}}---5$>

其中$>{\tilde{X}}_e=(X_e,0_{d\times r}),\tilde{V}=(V,\sqrt{{\lambda }_2}{I}_r),$>$>G^{+}=\frac{1}{2}(G+|G\left|\right),$>$>G^{-}=\frac{1}{2}(G-|G\left|\right),$>|G|为矩阵G中所有元素取对应绝对值所构成的矩阵；

iii)固定U和V，计算最佳的E，计算公式如下：

$>E=f_{\frac{{\lambda }_1}{2}}(X-\mathrm{UV})---6$>

其中函数f定义为：

4)在进行图像检索时，将作为检索参考的图像x转换到图像基矩阵U所展开的子空间中，得到新的特征表达v，计算如下：

v＝(U^TU)^-1U^Tx＝Mx，   8

其中，M＝(U^TU)^-1U^T，U^T为矩阵U转置，(U^TU)^-1为U^TU的逆矩阵；

5)依据步骤4）得到的v，计算v与图像数据集中任一图像x_i的子空间特征表达v_i之间的距离s_i，计算公式如下：

s_i＝exp(-||v-v_i||²)   9

最后根据距离s_i对图像数据集中所有图像进行排序，返回距离值最小的前K个图像给用户，从而实现图像检索。

本方法能够表征图像之间的空间结构关系，具有较强的抗噪声能力，在得到图像基矩阵U后，对新图像的低维子空间特征表达的计算时间为线性时间，与现有方法相比能够比较快速准确地进行图像检索。

附图说明

图1是Corel5K图像数据集上的部分样例图像；

图2(a)是羚羊图像作为检索例子时，算法检索样例图；

图2(b)是羚羊图像作为检索例子时，算法前10个检索结果图；

图3(a)是热气球图像作为检索例子时，算法检索样例图；

图3(b)是热气球图像作为检索例子时，算法前10个检索结果图；

图4(a)是柜子图像作为检索例子时，算法检索样例图；

图4(b)是柜子图像作为检索例子时，算法前10个检索结果图；

图5(a)是公交车图像作为检索例子时，算法检索样例图；

图5(b)是公交车图像作为检索例子时，算法前10个检索结果图。

具体实施方式

基于鲁棒非负矩阵分解的图像检索方法包括如下步骤：

1)从公共图像数据集Corel5K中选择50类共5000张图像，提取PHOG视觉特征[1]集X＝[x₁,...,x_n]，其中n＝5000，x_i为第i张图像所对应的PHOG视觉特征向量；将PHOG视觉特征集X作为所要构建的L1图的顶点，L1图的边权重矩阵W＝[w₁,...,w_n]，，其中w_i计算如下：

$>\left(\begin{array}{c}\min {\left|\right|w_i\left|\right|}_1\\ s.t.\left|\right|x_i-X{w}_i\left|\right|\le ϵ,w_{\mathrm{ii}}=0\forall i\end{array}\right)---1$>

其中，x_i为第i幅图像的视觉特征，w_i为矩阵W的第i列，ε为误差系数，w_ii为向量w_i的第i个分量；

构建表征图像数据分布结构关系的L1图约束如下：

$>\left(\begin{array}{c}\min R_g={\Sigma }_{i=1}^n{\left|\right|v_i-V{w}_i\left|\right|}^2={\left|\right|V-\mathrm{VW}\left|\right|}_F^2\\ =\mathrm{tr}\left(V(I-W){(I-W)}^T{V}^T\right)=\mathrm{tr}\left({\mathrm{VGV}}^T\right)\end{array}\right)---2$>

其中，G＝(I-W)(I-W)^T，V＝[v₁,...,v_n]为图像集在子空间上的特征表达，I为单位矩阵；

2)将L1图约束和稀疏噪声约束项E加入到传统的非负矩阵分解算法框架中，构建鲁棒非负矩阵矩阵分解算法模型：

$>\underset{U,V\ge 0,E}{\min }{\left|\right|X-\mathrm{UV}-E\left|\right|}_F^2+{\lambda }_1·\left|\right|E\left|\right|+{\lambda }_2·{\left|\right|U\left|\right|}_F^2+{\lambda }_3·\mathrm{tr}\left({\mathrm{VGV}}^T\right)---3$>

其中，λ₁，λ₂和λ₃为正则化参数，在实验中分别设置为0.01，0.001和0.1，U∈R^d×r为保持视觉和语义相似性的图像基矩阵，V∈R^r×n为图像基矩阵U所展开的子空间中的特征表达，E∈R^d×n是稀疏噪声约束项，d为图像特征的维度，r为低维特征空间的维度；

3)利用图像数据集对公式3算法模型进行训练，采用迭代优化求解，计算得到保持视觉和语义相似性的图像基矩阵U和所有图像在图像基矩阵U所展开的子空间中的特征表达V，计算步骤如下：

i)随机初始化U，V和E矩阵，令中间变量X_e＝X-E；

ii)固定E，迭代计算U和V，计算公式如下：

$>U_{\mathrm{ij}}\leftarrow U_{\mathrm{ij}}\frac{{\left({\tilde{X}}_e{\tilde{V}}^T\right)}_{\mathrm{ij}}}{{\left(U\tilde{V}{\tilde{V}}^T\right)}_{\mathrm{ij}}}---4$>

$>V_{\mathrm{ij}}\leftarrow V_{\mathrm{ij}}\sqrt{\frac{{(U^T{X}_e+{\lambda }_3{\mathrm{VG}}^{-})}_{\mathrm{ij}}}{{(U^T\mathrm{UV}+{\lambda }_3{\mathrm{VG}}^{+})}_{\mathrm{ij}}}}---5$>

其中$>{\tilde{X}}_e=(X_e,0_{d\times r}),\tilde{V}=(V,\sqrt{{\lambda }_2}{I}_r),$>$>G^{+}=\frac{1}{2}(G+|G\left|\right),$>$>G^{-}=\frac{1}{2}(G-|G\left|\right),$>|G|为矩阵G中所有元素取对应绝对值所构成的矩阵；

iii)固定U和V，计算最佳的E，计算公式如下：

$>E=f_{\frac{{\lambda }_1}{2}}(X-\mathrm{UV})---6$>

其中函数f定义为：

4)在进行图像检索时，将作为检索参考的图像x转换到图像基矩阵U所展开的子空间中，得到新的特征表达v，计算如下：

v＝(U^TU)^-1U^Tx＝Mx，   8

其中，M＝(U^TU)^-1U^T，U^T为矩阵U转置，(U^TU)^-1为U^TU的逆矩阵；

5)依据步骤4）得到的v，计算v与图像数据集中任一图像x_i的子空间特征表达v_i之间的距离s_i，计算公式如下：

s_i＝exp(-||v-v_i||²)   9

最后根据距离s_i对图像数据集中所有图像进行排序，返回距离值最小的前K个图像给用户，从而实现图像检索。

参考文献

[1]PHOG特征代码实现：http://www.robots.ox.ac.uk/～vgg/research/caltech/phog.html。

实施例1

采用Corel5K图像数据集（如图1所示）进行试验，图2、图3，图4，图5分别展示四个检索结果。下面结合前面所述的方法步骤，具体说明该实施实例如下：

1）对Corel5K中的图像分别提取图像的680维的PHOG原始图像视觉特征，将其作为图像特征表达，得到图像视觉特征矩阵X＝[x₁,...,x_n]，n＝5000。

2）根据图像视觉特征矩阵X，对视觉相似性建模，以图像集原始视觉特征X＝[x₁,...,x_n]作为L1图的顶点，图的边权重矩阵W＝[w₁,...,w_n]中w_i计算如下：

$>\left(\begin{array}{c}\min {\left|\right|w_i\left|\right|}_1\\ s.t.\left|\right|x_i-X{w}_i\left|\right|\le ϵ,w_{\mathrm{ii}}=0\forall i\end{array}\right)---1$>

设置ε＝0.001，采用L1_LS求解工具包对上面目标函数1进行优化求解，计算得到W矩阵，从而得到如下一个视觉L1图约束：

$>\left(\begin{array}{c}\min R_g={\Sigma }_{i=1}^n{\left|\right|v_i-V{w}_i\left|\right|}^2={\left|\right|V-\mathrm{VW}\left|\right|}_F^2\\ =\mathrm{tr}\left(V(I-W){(I-W)}^T{V}^T\right)=\mathrm{tr}\left({\mathrm{VGV}}^T\right)\end{array}\right)---2$>

其中，G＝(I-W)(I-W)^T，V＝[v₁,...,v_n]为图像集在子空间上的特征表达，I为单位矩阵。

3)将L1图约束和稀疏噪声约束项E加入到传统的非负矩阵分解算法框架中，构建鲁棒非负矩阵矩阵分解算法模型：

$>\underset{U,V\ge 0,E}{\min }{\left|\right|X-\mathrm{UV}-E\left|\right|}_F^2+{\lambda }_1·\left|\right|E\left|\right|+{\lambda }_2·{\left|\right|U\left|\right|}_F^2+{\lambda }_3·\mathrm{tr}\left({\mathrm{VGV}}^T\right)---3$>

其中，λ₁，λ₂和λ₃为正则化参数，分别设置为1.6，0.1和0.01，U∈R^d×r为保持视觉和语义相似性的图像基矩阵，V∈R^r×n为图像基矩阵U所展开的子空间中的特征表达，E∈R^d×n是稀疏噪声约束项，d为图像特征的维度，即680维，r为低维特征空间的维度，设置为150维；

4)利用图像数据集对公式3算法模型进行训练，采用迭代优化求解，计算得到保持视觉和语义相似性的图像基矩阵U和所有图像在图像基矩阵U所展开的子空间中的特征表达V，计算步骤如下：

i)随机初始化U，V和E矩阵，令中间变量X_e＝X-E；

ii)固定E，迭代计算U和V，计算公式如下：

$>U_{\mathrm{ij}}\leftarrow U_{\mathrm{ij}}\frac{{\left({\tilde{X}}_e{\tilde{V}}^T\right)}_{\mathrm{ij}}}{{\left(U\tilde{V}{\tilde{V}}^T\right)}_{\mathrm{ij}}}---4$>

$>V_{\mathrm{ij}}\leftarrow V_{\mathrm{ij}}\sqrt{\frac{{(U^T{X}_e+{\lambda }_3{\mathrm{VG}}^{-})}_{\mathrm{ij}}}{{(U^T\mathrm{UV}+{\lambda }_3{\mathrm{VG}}^{+})}_{\mathrm{ij}}}}---5$>

其中$>{\tilde{X}}_e=(X_e,0_{d\times r}),\tilde{V}=(V,\sqrt{{\lambda }_2}{I}_r),$>$>G^{+}=\frac{1}{2}(G+|G\left|\right),$>$>G^{-}=\frac{1}{2}(G-|G\left|\right),$>|G|为矩阵G中所有元素取对应绝对值所构成的矩阵；

iii)固定U和V，计算最佳的E，计算公式如下：

$>E=f_{\frac{{\lambda }_1}{2}}(X-\mathrm{UV})---6$>

其中函数f定义为：

5)在进行图像检索时，将作为检索参考的图像x转换到图像基矩阵U所展开的子空间中，得到新的特征表达v，计算如下：

v＝(U^TU)^-1U^Tx＝Mx，   8

其中，M＝(U^TU)^-1U^T，U^T为矩阵U转置，(U^TU)^-1为U^TU的逆矩阵；

6)依据步骤5）得到的v，计算v与图像数据集中任一图像x_i的子空间特征表达v_i之间的距离s_i，计算公式如下：

s_i＝exp(-||v-v_i||²)   9

最后根据距离s_i对Corel5K图像数据集中所有图像进行排序，返回距离值最小的前10个图像给用户，从而实现图像检索。