《基于非负矩阵分解方法的笔迹鉴别(1)》由会员分享，可在线阅读，更多相关《基于非负矩阵分解方法的笔迹鉴别(1)（6页珍藏版）》请在金锄头文库上搜索。
1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于非负矩阵分解方法的笔迹鉴别(1)摘 要 笔迹鉴别在模式识别的发展和应用中都有着重要的意义。运用非负矩阵分解算法(NMF)对中文单字提取笔迹特征，并利用训练样本和测试样本之间角度的相关性和K近邻算法对笔迹进行分类。结果表明，NMF算法其分类正确率明显高于主分量分析(PCA)方法。这说明了NMF算法在手写笔迹鉴别分析中的潜力。 关键字 笔迹鉴别；非负矩阵分解；K近邻1 引言 随着信息数字化的飞速发展，手写体笔迹鉴别4，5成为计算机视觉和模式识别领域中活跃的研究课
2、题。笔迹是一种相当稳定的行为特征，不同的人有不同的笔迹，且手写笔迹易于获取。基于其种种优点，笔迹鉴别6，8广泛的应用于政府部门，金融，法律等领域。文献专家可以鉴别出笔迹的真伪，但计算机自动提取笔迹特征，并鉴别其真伪，特别是对少量的笔迹仍然有一定的难度。 1999年Lee和Seung在Nature上发表了非负矩阵分解算法1，2。非负矩阵分解(Non-negative Matrix Factorization)是目前国际上提出的一种新的矩阵分解方法，即NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。非负矩阵分解方法提供了一种新的矩阵分解思路：其分解算法实现简便，分解的结果中没有负值，
3、矩阵具有可解释性和明确的物理意义，而且占用的存储空间较少。 本文对每个人书写的少量笔迹进行鉴别。为了更好的提取笔迹特征，首次引入非负矩阵分解算法，并应用欧氏距离、Cos距离以及K近邻对测试样本进行分类。将分类结果与主成分分析算法得到的结果进行比较，得出结论。非负矩阵分解理论 非负矩阵分解3问题可描述为：已知一个非负矩阵V，要找出非负的nr矩阵 W和非负的nm矩阵H，使 V=WH。由上述可知，非负矩阵分解是用非负性约束来获取数据表示的一种方法。非负性是对矩阵分解非常有效的条件限制，它导致了对于原始数据的基于部分的表示形式，即样本数据只允许加性和非负的组合。算法所得到的非负基向量组 具有一定的线性
4、无关性和稀疏性，从而使得其对原始数据的特征及结构具有相当的表达能力。这使得该算法具有很强的应用背景。 NMF的求解是一个最优化问题，可以用迭代方法求解W和H。NMF 问题的目标函数有很多种，最常用的两种目标函数为KL散度和欧几里德距离。KL散度计算公式如下： (2-1) 其中，当且仅当A=B 时才等于0。欧几里德距离计算公式如下： (2-2) 其中， ，当且仅当 A=B时才等于0，该问题的求解过程如下： (1)初始化 W、H 矩阵为非负随即矩阵； (2)按公式(2-3)对 W、H 进行迭代运算，其中W 和 H是同步迭代，也就是说，完成 W中的一行更新之后，立即更新 H中相应的列； (2-3)
5、(3)根据公式(2-2)计算V 和WH 之间的散度，如果大于预定订值，返回(2)继续运算；否则停止，运算结束。3 K近邻和Cos距离 k近邻6 取未知样本x 的k个近邻，看这k个近邻中多数属于哪一类，就把x 归为哪一类。具体说就是在N个已知样本中，找出 x的k个近邻。设这N个样本中，来自w1 类的样本有N1个，来自 w2类的有N2个，来自 wc类的有Nc个，若k1，k2，.，kc分别是k个近邻中属于几类的样本，则我们可以定义判别函数为： (3-1) 决策规则为：若则决策。3.Cos距离3 Cos距离是指向量之间角度的相关相，用公式表示为： (3-2)4 过程及其结果 实验过程 作者用20个人的
6、中文笔迹进行测试，包含每人30共600份手写汉字的笔迹图像，按彩色模式被扫描入计算机。其中15份/人作为训练样本，其余的15份/人作为测试样本。即600份笔迹图像中，300份为训练样本，300份测试样本，其中部分样本见图1。 通过随机变换训练样本和测试样本，重复10次这样的实验。实验步骤如下： 图像预处理：首先去除所有的笔迹图像外边缘的空白，并将其归一化为20*20的256色灰度jpg图像。 特征提取：用NMF 100算法提取笔迹图像的特征，将 W、H 初始化为非负的正态分布矩阵，分别取r=20，25，30，35，40，45，50，100进行50次迭代得到图像特征空间。 笔迹鉴别：将测试样本映
7、射特征空间，求出训练样本的特征向量，与已知的特征向量之间欧氏距离、Cos距离和K近邻(k=3)。然后对样本进行鉴别，得出鉴别结果。由于初始化矩阵的随机性，对每一个r值进行10次运算，分别求出其识别率。图1 “试”字的笔迹样本 实验结果 对“试”字的笔迹图像分别运用主成分分析变换和非负矩阵分解算法提取图像特征，如图2、所示。图2为经过PCA变换得到的分别降至20维和50维的特征空间，图3为经NMF变换得到的特征空间。 (a)(b)图2 PCA运算得到的特征空间。(a)r=20得到的结果；(b)r=50得到的结果。(a)(b) 图3 NMF运算得到的特征空间。(a)r=20得到的结果；(b)r=5
8、0得到的结果。图4算法的识别率 将测试样本图像映射到特征空间求得特征向量。通过求测试样本和训练样本特征向量之间的欧氏距离、Cos距离和三近邻，得出识别率。表1为PCA和NMF得到的识别率(由于NMF的随机性，识别率为重复10次实验得到识别率的均值)。也可参见直方图图4。结果表明，对于每种分类方法，非负矩阵分解算法的识别率都明显高于主成分分析算法。结论 本文首次引入非负矩阵分解算法对中文单字进行笔迹鉴别，对20人的600份样本进行实验，得到良好的结果，识别率达到96%。 相对于传统的降维算法PCA，NMF算法识别率平均提高了10%。并且NMF能有效节约存储空间和计算资源，非负矩阵本身具有明确的物
9、理含义易于理解。 虽然非负矩阵分解在其应用中取得了一定的成功，但是还存在着一定的问题有待进一步的研究。在其优化过程中优化的目标函数和约束条件的选择，分解算法初始化函数过程随机性，导致了得到的分解矩阵结果也不稳定，有待提出一种更为稳定地初始化方法。表1 算法的识别率算法图像维数欧氏距离PCAK近邻(k=3)Cos距离欧氏距离NMFK近邻(k=3)Cos距离参考文献1Daniel ，H. Sebastian Seung. Learing the parts of objects by non-negativematrix factorizationJ. Nature，1999，401：788-79
10、12Daniel ， Seung. Algorithms for non-negative matrix factorization J. Advances in Neural Information Processing Systems，XX，13：556-562.3， Evaluation of distance metrics for recognition based on non-negative matrix factorization. Pattern Recognition Letters，XX，24：1599-16054Ameur Bensefia，Thierry Paque
11、t，Laurent HeutteA writer identification and verification systemPattern Recognition Letters，XX，26：208020925HESSaid，TnTan，KDBakerPersonal identification based on handwritingPattern Recognition，XX，33(1)：1491606边肇祺，张学工模式识别北京：清华大学出版社，XX7汪鹏.非负矩阵分解：数学的奇妙力量.计算机教育，XX，10：38-408刘宏，李锦涛，崔国勤基于SVM和纹理的笔迹鉴别方法计算机辅助设计与图形学学报，XX，15(12)：14791484 课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。
