非负矩阵分解方法及其在选票图像识别中的应用

摘要

图像识别是随着计算机技术发展而兴起的。它利用计算机对图像进行处理，以识别各种不同模式的目标和对象，是图像融合、立体视觉、运动分析等实用技术的基础。
　　 近年来，随着图像识别技术在自然资源分析、生理病变、天气预报、导航、地图与地形配准、环境监测等领域的广泛应用，各种理论和方法也被大量应用到图像识别中，非负矩阵分解(Non-negativeMatrixFactorization，NMF)理论就是其中之一，是当今的研究热点。NMF是从“对整体的感知由对组成整体的部分感知构成”观点出发而构建的。它将一个非负矩阵分解为两个非负矩阵的乘积，原矩阵中的一列可以解释为基矩阵巾所有列向量的加权和，而权重系数为权重矩阵中对应列向量中的元素。这样基于向量组合的分解具有可解释性和明确的物理意义，而且占用存储空间更少，是一个处理非负数据的强大工具。从模式识别角度来看，NMF实质上是一种子空间分析方法，其本质是一种特征提取和选择的方法。NMF的主要思想是在样本空间中寻找合适的子空间（特征子空间），通过将高维样本投影到低维子空间上，从而在子空间上获得样本的本质特征，利用这些特征实现分类。作为一项数据处理技术，NMF揭示了描述数据的本质，已经被广泛应用到人脸检测与识别、图像融合、图像检索、图像分类、图像复原、图像压缩、灰度图像的数字水印、文本分析与聚类、语音识别、生物医学工程、网络安全的入侵检测等诸多方面的研究中。
　　 本文在非负矩阵分解理论方面进行深入研究。首先，基于Frobenius范数和Kullback-Leibler散度的两个目标函数，利用Taylor展开式、稳定点求解和Newton求根公式，提出了一种非负矩阵分解的理论分析方法;然后，利用该方法，严格导出了三种非负矩阵分解方法，解决了相关问题。最后，将结构模式识别方法和本文的非负矩阵分解方法应用到选票图像中的特殊手写符号识别，详细给出了选票图像识别方法。本文的主要贡献有以下几个方而:
　　 1.提出了非负矩阵分解新方法
　　 根据Frobenius范数‖X-WH‖2F和Kullback-Leibler散度D(X‖WH)，提出了一种新的非负矩阵分解(NovelNon-negativeMatrixFactorization，NNMF)方法。从理论上严格推导了非负矩阵分解中基矩阵和权重矩阵的迭代公式，算法推导方法是新颖的。证明了算法的收敛性。给出了算法步骤。与标准NMF方法比较，本文的方法更容易找到辅助函数，从而更容易确定迭代公式。当使用Frobenius范数作为目标函数时，可以得到与标准NMF完全相同的迭代公式。当使用Kullback-Leibler散度作为口标函数时，获得了一组新的迭代公式;在人脸识别实验中，当收敛精度不是很高时，基矩阵的列基取不同值的大部分情况下，相对于相应的标准NMF算法，该算法具有较高的识别率。
　　 2.提出了近似正交非负矩阵分解方法
　　 将Frobenius范数和近似正交约束作为目标函数，提出了近似正交非负矩阵分解（ApproximateOrthogonalNon-negativeMatrixFactorization，AONMF）方法。利用Taylor展开式和稳定点求解方法，严格导出了非负矩阵分解的基矩阵和权重矩阵的迭代更新算法，并证明了算法的收敛性、阐述了基矩阵近似正交的理由。人脸识别结果表明:只要基矩阵的秩选择恰当，识别率是较高的。
　　 3.提出了收敛投影非负矩阵分解方法
　　 为了解决投影非负矩阵分解(ProjectiveNon-negativeMatrixFactorization，P-NMF)算法的收敛性问题，提出了收敛投影非负矩阵分解(ConvergentProjectiveNon-negativeMatrixFactorization，CP-NMF)方法。分别利用Frobenius范数和Kullback-Leibler散度作为目标函数，利用Taylor展开式和Newton迭代求根公式，严格导出了投影非负矩阵分解的基矩阵迭代算法，并证明了算法的收敛性。实验结果表明:该算法具有较快的收敛速度，而基矩阵的初值会影响收敛速度;相对于标准NMF，该方法的基矩阵具有更好的正交性和稀疏性，但数据重建结果说明基矩阵仍然是近似正交的;人脸识别结果表明该方法具有较高的识别率。
　　 4.提出了线性投影非负矩阵分解方法
　　 针对基于线性投影结构的非负矩阵分解(LinearProjection-BasedNon-negativeMatrixFactorization，LPBNMF)迭代方法比较复杂的问题，提出了线性投影非负矩阵分解(LinearProjectiveNon-negativeMatrixFactorization，LP-NMF)方法。从投影和线性变换角度出发，将Frobenius范数作为目标函数，利用Taylor展开式和稳定点求解方法，严格导出了基矩阵和线性变换矩阵的迭代算法，并证明了算法的收敛性。实验结果表明:该算法是收敛的;相对于一些非负矩阵分解方法，该方法的基矩阵具有更好的正交性和稀疏性;人脸识别结果说明该方法具有较高的识别率。
　　 5.提出了选票图像识别方法
　　 选票图像中的特殊手写符号通常是:勾“√”、罔“○”、叉“×”、杠“＼、—、/（三种写法）”。为了解决基于光学字符识别(OpticalCharacterRecognition，OCR)技术的选举投票系统巾手写符号图像的快速定位与识别问题，提出了选票图像识别方法。该方法在充分考虑选举信息的基础上，实现了选票的可视化设计。该选票设计记录了选举信息巾相关对象的位置数据。利用这些数据，将选票图像预处理后，找到一个确定的参考点，再提取选票设计中的位置数据，将它转化为相对于这个参考点的图像位置，利用该位置搜索表格线，从而确定要识别图像的准确位置;基于该位置，可截取手写符号图像，对该图像进行一系列处理后，提取其结构特征，采用结构模式识别方法识别。如果结构特征无法判别，就采用本文的NMF方法进行新的特征提取后再识别。实验结果表明，这种方法的定位速度快、识别率高。结合选票设计的识别方法使得识别软件定位速度更快、选票版面可以更复杂，采用结构模式识别和NMF相结合的方法识别准确率更高，有效提高了系统效率，选举投票系统更加完善。

目录

声明

摘要

第一章 绪论

1．1 研究目的和意义

1．2 国内外研究现状

1．3 主要研究内容与创新

1．4 本文的组织结构

第二章 非负矩阵分解方法简介

2．1 非负矩阵分解的起源

2．2 非负矩阵分解理论

2．2．1 问题描述

2．2．2 目标函数

2．2．3 迭代公式

2．2．4 解的性质

2．3 非负矩阵分解的直观解释

2．4 非负矩阵分解的应用

第三章 非负矩阵分解新方法

3．1 基于Frobenius范数的新非负矩阵分解(NNMF-FRO)

3．1．1 基矩阵W的迭代更新规则

3．1．2 权重矩阵H的迭代更新规则

3．2 基于Kullback-Leibler散度的新非负矩阵分解(NNMF-DIV)

3．2．1 基矩阵W的迭代更新规则

3．2．2 权重矩阵H的迭代更新规则

3．3 算法步骤

3．4 ORL人脸库简介

3．5 实验与分析

3．5．1 算法收敛性

3．5．2 算法收敛速度

3．5．3 基矩阵分析

3．6 人脸识别结果及分析

3．7 本章小结

第四章 近似正交非负矩阵分解方法

4．1 基矩阵W的迭代更新规则

4．2 权重矩阵H的迭代更新规则

4．3 算法步骤

4．4 实验与分析

4．4．1 算法收敛性

4．4．2 基矩阵分析

4．5 人脸识别结果及分析

4．6 本章小结

第五章 收敛投影非负矩阵分解方法

5．1 基于Frobenius范数的收敛投影非负矩阵分解(CP-NMF-FRO)

5．1．1 基矩阵W的迭代更新规则

5．1．2 算法步骤

5．2 基于Kullback-Leibler散度的收敛投影非负矩阵分解(CP-NMF-DIV)

5．2．1 基矩阵W的迭代更新规则

5．2．2 算法步骤

5．3 实验与分析

5．3．1 算法收敛性

5．3．2 基矩阵分析

5．4 人脸识别结果及分析

5．5 本章小结

第六章 线性投影非负矩阵分解方法

6．1 基矩阵W的迭代更新规则

6．2 线性变换矩阵Q的迭代更新规则

6．3 算法步骤

6．4 实验与分析

6．4．1 算法收敛性

6．4．2 基矩阵分析

6．5 人脸识别结果及分析

6．6 本章小结

第七章 选票图像识别方法

7．1 选票图像识别的背景

7．2 选票图像识别存在的问题

7．3 选票设计

7．3．1 选举信息

7．3．2 选票

7．4 图像识别

7．4．1 图像采集

7．4．2 定位

7．4．3 图像预处理

7．4．4 手写符号识别

7．5 本章小结

第八章 总结与展望

8．1 总结

8．2 展望

参考文献

致谢

附录

图索引

表索引

Appendix

Figure index

Table index

攻读博士学位期间发表的论文目录

攻读博士学位期间参加的研究项目