改进的图正则化非负矩阵分解的图像识别方法①

杨彩凤，刘 涛，刘国庆，程 飞

(安徽工程大学计算机与信息学院，安徽 芜湖 241000)

0 引 言

图像识别是人工智能[1]重要研究领域之一，同时，图像识别也在机器视觉[2]和模式识别[3]中成为一个热点研究领域。面对大数据时，图像识别会面临“维数灾难”[4]的问题。然而，在识别过程中又需要快速精准地进行识别，找到两个或者两个以上的低维矩阵，使其乘积等于或者约等于原始矩阵，达到对原始矩阵降维的目的，是解决问题的一个主流方法，这就是矩阵分解技术。已有的心理和生理逻辑证明，在人脑中，对事物的认识是基于部分表示的[5]，而且在图像数据中，像素点的值是大于等于零的。对此，提出了NMF算法来学习图像的局部特征，NMF的目标是找到两个非负矩阵，它们的乘积能有效地逼近原始矩阵。NMF的这些特征既符合人脑对事物的认识，又满足图像数据的表示要求，是学习物体部分表示的最佳方法。原始的NMF算法虽然能有效地对图片进行压缩降维，但仍有不足之处，比如存在冗余数据、忽略某些重要特征、过度降维等等。针对NMF在图像识别中存在的问题，提出了改进的NMF算法，结合图谱理论，保留数据的内在几何结构关系，设置阈值，优化基矩阵，过滤冗余信息，提高图像识别的效果。在PIE-Pose05,YaleB和COIL20数据库上的实验表明，本文提出的改进算法取得理想效果。

1 NMF算法

首次提出NMF 算法的是Lee和Seung等人[5]，指出该算法可用于图像识别，并在同年发表的文章[6]中给出迭代公式的推导过程，基于两种目标函数，并且证明了收敛性。

有N张图像，将每张图像进行向量化表示，这里用字母M表示，那么图像数据库可以被表示为：一个M×N的矩阵X=[x1,x2,…,xN]∈RM×N，其中，X的每一列表示一个样本向量。进而，问题可以转化为：在实际中，需要找到两个非负数据矩阵U=[uik]∈RM×K和V=[vjk]∈RN×K，两者的乘积能很好地逼近原始矩阵X，即满足如下公式：

X≈U×VT

(1)

在一般的现实应用中K≪M，K≪N，所以，NMF对原始矩阵X进行了压缩。可以认为U包含一组基，该基对X中数据的线性逼近进行了优化，这里把U称基准图像矩阵，简称基矩阵，V称为编码矩阵，本文将对基矩阵U做相应处理，提高算法的效率。

2 改进的图正则化非负矩阵分解的图像识别算法设计

通过使用非负的约束，NMF可以学习基于部分的表示，然而，它没有发现数据空间固有的几何判别结构[7]，而这对实际应用是至关重要的，将图谱理论[8-9]与NMF相结合，有效揭示隐藏的语义，又尊重数据内在的几何结构。并且，为了更好地提取图像特征，对基矩阵进行处理，使得处理过后的向量包含更多实际所需要的信息。

2.1 图谱理论

给定一组数据，可以构造一个有N个顶点的邻近图，每个顶点代表一个相应的数据点，其中，图中的每个数据点xj，找到它的p个最近邻居，并在xj和它的邻居之间设置一条边，权矩阵W存储每条边的权值，本文为了简洁，选择0-1加权法，当且仅当点j和点l由一条边连接时，Wjl=1，Wjl用于表示点xj和点xl的接近度。利用权矩阵W，可以用下面的公式来度量低维表示的光滑性：

Tr(VTDV)-Tr(VTWV)=Tr(VTLV)

(2)

其中，D是由矩阵W的列或者行构成的一个对角矩阵，Tr则是计算矩阵的迹，Djj=∑lWjl，L=D-W，称为图拉普拉斯[10]。

2.2 改进的图正则化非负矩阵分解的图像识别算法

将图谱理论技术与原始的NMF相结合，利用流形假设，开发图正则化非负矩阵分解(GNMF)；在GNMF得到的基矩阵上添加阈值，过滤冗余信息，进而得到新的GNMF。

GNMF的欧式距离目标最小化函数如下：

O=‖X-UVT‖+λTr(VTLV)

(3)

其中，λ≥0，是正则化参数，控制新表示的平滑度。在GNMF的目标函数O在U和V中不是同时凸的，所以找到全局最小值是不现实的，但可以找到局部最小值。以下给出O的步骤，并且推导出最后的迭代公式。

O=‖X-UVT‖+λTr(VTLV)=

Tr((X-UVT)(X-UVT)T)+λTr(VTLV)=

Tr(XXT)-2Tr(XVUT)+Tr(UVTVUT)+

λTr(VTLV)

(4)

利用拉格朗日乘子ψik和φjk分别约束uik≥0和vjk≥0，并且Ψ=[ψik]，Φ=[φjk]，拉格朗日Γ是：

Γ=Tr(XXT)-2Tr(XVUT)+Tr(UVTVUT)+

λTr(VTLV)+Tr(ΨUT)+Tr(ΦVT)

(5)

Γ对U和V求偏导得：

(6)

(7)

运用KKT条件ψikuik=0和φjkvjk=0，得到uik和vjk的方程：

-(XV)ikuik+(UVTV)ikuik=0

(8)

-(XTU)jkvjk+(VUTU)jkvjk+λ(LV)jkvjk=0

(9)

解得方程的跟新规则为：

(10)

(11)

对基矩阵U进行优化，过滤数据之间存在的冗余信息。选择一个阈值S，对矩阵U进行阈值判断处理，具体过程为，对于基矩阵U的每一列，将其与阈值S进行比较，小于阈值S的置为s，s一般为一个很小的数，并且s大于0，得到新的基矩阵Unew，X在新的基矩阵Unew投影得到新的Vnew，从而得到优化的迭代跟新规则，对于公式(10)和(11)有：

(12)

(13)

经过优化的GNMF算法，降低冗余数据的干扰，使分解后的结果中含有更多在图像识别过程中所需的有用信息，能够有效提高算法的效率。

3 实验分析

3.1 实验数据库

为了验证本文提出的将NMF结合图谱理论和对基矩阵优化的有效性，利用MATLAB平台进行实验验证，同时选用公开的两种人脸图像数据库和一种物体图像数据库：PIE-Pose05,YaleB和COIL20图像数据库。表1展示了三种图像数据库的详细信息。

表1 三种图像数据库详情

3.2 不同算法比较

用不同算法的对比实验，验证本文提出算法在图像识别中的有效性，这里选用了Kmeans,PCA,NMF,GNMF，同时为了表明本文提出的对基矩阵优化的有效性，给出两种优化处理的实验：第一种，针对NMF，在原始NMF之上运用本文提出的优化方法，简称New-NMF。第二种，针对GNMF，在GNMF之上运用本文提出的优化方法，简称New-GNMF。

不同参数设置为：GNMF中，p设置为5，正则化参数λ设置为100；New-NMF中，在PIE-Pose05,YaleB两种人脸图像数据库上，基矩阵阈值S设置为0.7，s设置为0.00001；在COIL20物体图像数据库上，基矩阵阈值S设置为0.03，s设置为0.00001；New-GNMF中，p设置为5，正则化参数λ设置为100，PIE、YaleB上基矩阵阈值S设置为0.7，s设置为0.00001；COIL20上基矩阵阈值S设置为0.03，s设置为0.00001。

3.3 实验结果

为了直观地表示出本文提出的算法在实际应用中的有效性，使用两种常用的标准度量方法：正确率(AC)和归一化互信息(NMI)。表2～7展示了实验结果，为了随机化实验，对每个给定的集群号K分别测试运行10次，表中报告了不同方法的每个集群号的性能结果(取平均值，并且保留两位小数)。

表2 PIE-Pose05上的AC结果(%)

表3 PIE-Pose05上的NMI结果(%)

表4 YaleB上的AC结果(%)

表5 YaleB上的NMI结果(%)

表6 COIL20上的AC结果(%)

表7 COIL20上的NMI结果(%)

从以上实验结果可以看出，本文提出的改进算法对于图像识别是有效的，可以总结为以下几点：

1)经过对基矩阵进行阈值限制优化处理后，滤除图像识别中数据之间的冗余信息，降低冗余信息的干扰，达到了有效特征提取目的，在不同的图像数据库中，本文算法比Kmeans,PCA,NMF,原始GNMF的效果好，AC和NMI两个指标都有所提高；

2)在NMF的基础上引入图谱理论有效地描述了图像的几何判别结构，提高识别效果，在三个数据库中，不管是AC还是NMI，GNMF比NMF效果好，New-GNMF比New-NMF效果好；

3)在矩阵分解技术的基础上，通过本文提出的对分解后的基矩阵设置阈值限制，进行优化处理，不管是对NMF还是GNMF，都能提高算法的有效性，并且在PIE-Pose05,YaleB人脸图像数据库上，NMF效果更加明显，在COIL20物体图像数据库上，GNMF效果更加明显。可见，对在NMF和GNMF的基础上对基矩阵进行优化处理能达到理想的效果；

4)由于不同数据库中的图片的拍摄条件、图片数量等有所不同，在三个数据库上的效果有所不同，表现为，YaleB和COIL20数据库上的提高结果比PIE-Pose05数据库上的提高结果更加出色；

5)对于每个给定的集群号K(1，3，5，10，20，23)，实验结果也存在差异，但差异不是很大，算法整体表现稳定。

3.4 参数选择

本文提出的优化算法关键是对基矩阵添加阈值S，在图像识别过程中过滤冗余信息，S具有控制优化程度的功能。本小节以曲线图的形式展示出在三个数据库上AC和NMI随阈值的变化而变化的结果，这里在集群号23上分别对NMF和GNMF两个方法进行实验，并将s设置为0.00001。横坐标表示阈值S的取值范围，纵坐标表示三个数据库上AC和NMI随S的变化而变化的结果，如下各图所示：

图1 AC和NMI在PIE-Pose05上随参数S变化而变化

图2 AC和NMI在YaleB上随参数S变化而变化

图3 AC和NMI在COIL20上随参数S变化而变化

从图1,2和图3可以得到以下结论：

1)对于NMF，在数据库PIE-Pose05上，当S在0.7和1.1之间，AC和NMI都有比较好的效果；

2)对于NMF，在数据库YaleB上，当S在0.5到1.1之间，AC和NMI都有比较好的效果；

3)对于NMF，在数据库COIL20上，当S在0.01到0.06之间，AC和NMI都有比较好的效果；

4)对于GNMF，在数据库PIE-Pose05和YaleB上，当S在0.3到0.9之间，AC和NMI都有比较好的效果；

5)对于GNMF，在数据库COIL20上，当S在0.01到0.04之间，AC和NMI都有比较好的效果。

4 结 语

提出了一种新的图正则化非负矩阵分解算法，将图谱理论与传统的NMF相结合，利用流形假设，构建邻近图，搭建模型，保留数据的内在几何结构；对分解后的基矩阵设置阈值S，进行优化处理，过滤了数据中的冗余信息，并且将这种方法运用到图像识别中。实验结果表明，不管是NMF还是GNMF，本文提出的改进方法，在图像数据库中都具有更强的识别能力。

但此方法也存在不足，第一，阈值处理对不同数据达不到针对性优化，在PIE-Pose05数据库上的表现不是很出色；第二，因为增加了阈值处理，使得整个识别过程所需时间增加。在未来的工作中，将对这两点不足进行改进：对于阈值S如何针对性自动取值以及如何降低识别速度做进一步地研究。