基于非负矩阵分解方法的笔迹鉴别
发布时间：2015-07-11 10:02
摘 要 笔迹鉴别在模式识别的发展和应用中都有着重要的意义。运用非负矩阵分解算法(NMF)对中文单字提取笔迹特征，并利用训练样本和测试样本之间角度的相关性和K近邻算法对笔迹进行分类。结果表明，NMF算法其分类正确率明显高于主分量分析(PCA)方法。这说明了NMF算法在手写笔迹鉴别分析中的潜力。
关键字 笔迹鉴别；非负矩阵分解；K近邻
1 引言
随着信息数字化的飞速发展，手写体笔迹鉴别[4，5]成为计算机视觉和模式识别领域中活跃的研究课题。笔迹是一种相当稳定的行为特征，不同的人有不同的笔迹，且手写笔迹易于获取。基于其种种优点，笔迹鉴别[6，8]广泛的应用于政府部门，金融，法律等领域。文献专家可以鉴别出笔迹的真伪，但计算机自动提取笔迹特征，并鉴别其真伪，特别是对少量的笔迹仍然有一定的难度。
1999年Lee和Seung在Nature上发表了非负矩阵分解算法[1，2]。非负矩阵分解(Non-negative Matrix Factorization)是目前国际上提出的一种新的矩阵分解方法，即NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。非负矩阵分解方法提供了一种新的矩阵分解思路：其分解算法实现简便，分解的结果中没有负值，矩阵具有可解释性和明确的物理意义，而且占用的存储空间较少。
本文对每个人书写的少量（如个人签名）笔迹进行鉴别。为了更好的提取笔迹特征，首次引入非负矩阵分解算法，并应用欧氏距离、Cos距离以及K近邻对测试样本进行分类。将分类结果与主成分分析算法得到的结果进行比较，得出结论。
2 非负矩阵分解理论
非负矩阵分解问题可描述为：已知一个非负矩阵V，要找出非负的n＊r矩阵 W和非负的n＊m矩阵H，使 V=WH。由上述可知，非负矩阵分解是用非负性约束来获取数据表示的一种方法。非负性是对矩阵分解非常有效的条件限制，它导致了对于原始数据的基于部分的表示形式，即样本数据只允许加性和非负的组合。算法所得到的非负基向量组 具有一定的线性无关性和稀疏性，从而使得其对原始数据的特征及结构具有相当的表达能力。这使得该算法具有很强的应用背景。
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)
(3)根据公式(2-2)计算V 和WH 之间的散度，如果大于预定订值，返回(2)继续运算；否则停止，运算结束。
3 K近邻和Cos距离
3.1 k近邻
取未知样本x 的k个近邻，看这k个近邻中多数属于哪一类，就把x 归为哪一类。具体说就是在N个已知样本中，找出 x的k个近邻。设这N个样本中，来自w1 类的样本有N1个，来自 w2类的有N2个，…，来自 wc类的有Nc个，若k1，k2，...，kc分别是k个近邻中属于几类的样本，则我们可以定义判别函数为：
(3-1)
决策规则为：若则决策。
3.2 Cos距离
Cos距离是指向量之间角度的相关相，用公式表示为：
(3-2)
4 过程及其结果
4.1 实验过程
作者用20个人的中文笔迹进行测试，包含每人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次迭代得到图像特征空间。
笔迹鉴别：将测试样本映射特征空间，求出训练样本的特征向量，与已知的特征向量之间欧氏距离、Cos距离和K近邻(k=3)。然后对样本进行鉴别，得出鉴别结果。由于初始化矩阵的随机性，对每一个r值进行10次运算，分别求出其识别率。
图1 “试”字的笔迹样本
4.2 实验结果
对“试”字的笔迹图像分别运用主成分分析变换和非负矩阵分解算法提取图像特征，如图2、 3所示。图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=50得到的结果。
图4 算法的识别率
将测试样本图像映射到特征空间求得特征向量。通过求测试样本和训练样本特征向量之间的欧氏距离、Cos距离和三近邻，得出识别率。表1为PCA和NMF得到的识别率(由于NMF的随机性，识别率为重复10次实验得到识别率的均值)。也可参见直方图图4。结果表明，对于每种分类方法，非负矩阵分解算法的识别率都明显高于主成分分析算法。
5 结论
本文首次引入非负矩阵分解算法对中文单字进行笔迹鉴别，对20人的600份样本进行实验，得到良好的结果，识别率达到96%。
相对于传统的降维算法PCA，NMF算法识别率平均提高了10%。并且NMF能有效节约存储空间和计算资源，非负矩阵本身具有明确的物理含义易于理解。
虽然非负矩阵分解在其应用中取得了一定的成功，但是还存在着一定的问题有待进一步的研究。在其优化过程中优化的目标函数和约束条件的选择，分解算法初始化函数过程随机性，导致了得到的分解矩阵结果也不稳定，有待提出一种更为稳定地初始化方法。
表1 算法的识别率
算法
图像维数
20
25
30
35
40
45
50
100
欧氏距离
0.86
0.76
0.78
0.74
0.82
0.82
0.74
0.76
PCA
K近邻(k=3)
0.82
0.78
0.74
0.78
0.80
0.76
0.68
0.78
Cos距离
0.80
0.80
0.70
0.70
0.64
0.68
0.68
0.70
欧氏距离
0.84
0.88
0.88
0.88
0.90
0.90
0.92
0.90
NMF
K近邻(k=3)
0.88
0.90
0.86
0.88
0.88
0.86
0.90
0.92
Cos距离
0.84
0.86
0.92
0.92
0.94
0.96
0.96
0.96
参考文献
[1]Daniel ，H. Sebastian Seung. Learing the parts of objects by non-negativematrix factorization[J]. Nature，1999，401：788-791
Daniel ，ian Seung. Algorithms for non-negative matrix factorization [J]. Advances in Neural Information Processing Systems，2001，13：556-562.
met，. Evaluation of distance metrics for recognition based on non-negative matrix factorization. Pattern Recognition Letters，2003，24：1599-1605
Ameur Bensefia，Thierry Paquet，Laurent Heutte．A writer identification and verification system．Pattern Recognition Letters，2005，26：2080～2092
H．E．S．Said，T．n．Tan，K．D．Baker．Personal identification based on handwriting．Pattern Recognition，2000，33(1)：149～160
边肇祺，张学工．模式识别．北京：清华大学出版社，2000
汪鹏.非负矩阵分解：数学的奇妙力量.计算机教育，2004，10：38-40
刘宏，李锦涛，崔国勤．基于SVM和纹理的笔迹鉴别方法．计算机辅助设计与图形学学报，2003，15(12)：1479～1484