基于改进LPP和ECOC-SVMS的离线签名识别方法

蒋青云

(湖南省妇幼保健院信息中心，湖南 长沙 410008)

0 引 言

离线签名识别作为一种身份识别技术，广泛运用于金融、安全等领域。相对于在线签名识别方法，进行离线签名识别时无法获得书写签名时的书写速度、压力等各种动态信息，只能依赖于签名图像反映的静态信息，签名识别的难度相对更大，通常也存在识别率偏低等问题[1]。

近年来，国内外学者在手写签名鉴定及识别领域的研究逐步深入，涌现出了许多特征提取、分类识别方法。Vargas、Ferrer等人[2-3]通过提取灰度共生矩阵、局部二值模式等特征，采用支持向量机进行分类识别。Jaiswal等人[4]通过提取签名图像的全局、局部特征，使用神经网络进行识别，得到较高的识别率。Shekar等人[5]结合离散余弦变换与支持向量机，获得了较高的签名识别率。Pham等人[6]基于直方图、几何特征，在荷兰签名数据库上取得了较好的识别率，但在中文签名上的识别率欠佳。Hatkar等人[7]通过提取图像的几何特征，基于神经网络进行分类识别。Serdouk等人[8]基于局部二值模式、拓扑特征等，使用人工免疫系统进行分类匹配，在英文、中文签名中取得了较好的效果。Das等人[9]基于Gabor滤波技术提取签名图像的拓扑及统计特征，采用粗糙集理论构建分类识别系统。

中文签名具有复杂、多样化等特点，给签名图像特征提取、分类识别带来难度。本文对中文签名识别方法进行研究，为了融合多种有效签名图像特征并进行合理的特征提取，引入一种基于改进的保局投影(Locality Preserving Projections, LPP)方法进行线性降维，以得到有利的特征向量和特征维度。针对中文签名识别率问题，本文提出一种基于改进的纠错输出码支持向量机(ECOC-SVMS)的签名识别方法，以有效提升识别成功率。实验结果表明本文的方法取得了较好的特征提取效果，同时也显著提升了多类分类性能。

1 基于LPP的特征提取

LPP方法具有流形学习和线性降维的共同优点，在模式识别特征提取领域得到了广泛应用。LPP方法本质上使得高维空间中接近的样本，映射到低维空间后所有样本的局部K-近邻重建误差达到最小。然而，传统LPP方法具有如下不足[10-11]：1)属于无监督方法，降维过程中未使用样本类别信息；2)创建邻接图时近邻参数K非常关键，但原始方法中并未给定通用的有效方法；3)通过欧氏距离确定K近邻域，仅考虑了样本空间的距离特性而未考虑其几何结构特性。

1.1 保局投影方法

对于高维空间RD×N中的数据集合X=x1,x2,…，xN(N为样本个数)，LPP算法的目标是寻找一个投影矩阵A=a1,a2,…,ad，将高维空间中的数据集合映射到低维空间Rd×N中的数据集合Y=y1,y2,…，yN，其中Y=ATX。矩阵A为最小化以下目标函数的解：

(1)

式(1)中，W为衡量节点之间权值的关系矩阵。

LPP的一般步骤：

1)创建邻接图。建立一个包含m个顶点的权图G，若权图G中的节点xi是xj的K-近邻，或节点xj是xi的K-近邻，则在节点xi、xj之间用一条边连接。

2)确定权重。若权图中节点xi、xj有边相连接，则Wij=e-‖xi-xj‖2/t(t为大于0的常数)；简化地，若节点xi、xj有边相连接，则Wij=1，否则Wij=0。

XLXTa=λXDXTa

(2)

假设列向量a1,a2,…,ad为式(2)的解，且其对应特征值满足λ1<…<λd,则矩阵AD×d=(a1,a2,…,ad)为保局投影方法中的投影矩阵。

1.2 改进的LPP方法应用于特征提取

针对传统LPP方法的不足之处，本文从如下几个方面对传统LPP方法进行改进[11-12]：

1)通过样本之间的相关性自适应确定邻域K。确定节点xi的邻域时，首先通过式(3)计算节点xi与其他节点之间的平均相关性度量：

(3)

(4)

2)采用有监督方式构建邻接图，引入样本标签类别信息，邻域内同类别之间的节点有边相连；否则，无相连边，其对应权值也为0。

3)结合距离特性和几何特性，引入欧氏距离、测地距离进行邻接点权值计算，如式(5)：

(5)

式(5)中，de(xi,xj)表示欧氏距离，dg(xi,xj)表示测地距离，dg,m表示邻域内测地距离中值。由式(5)可知，邻域内邻接点与样本点的测地距离越大，则计算出的权值越小；邻域内邻接点与样本点之间的欧氏距离与测地距离比值可反映邻域的几何结构特性。

基于改进LPP的特征提取方法步骤如下：

输入：高维空间RD×N中的数据集合X={x1,x2,…,xN}(N为样本个数)及其类别属性{c1,c2,…,ci,…,cN}(其中ci∈{1,2,…,P}，P表示最大类别数)

输出：投影矩阵A=[a1,a2,…,ad]；低维空间Rd×N中的数据集合Y={y1,y2,…,yN}

Step2计算权值矩阵。根据式(5)计算每个节点与其邻接节点之间的权值。

Step3计算投影矩阵A。根据式(2)按传统LPP方法求取其特征值对应的非0特征向量，该向量构成投影矩阵A=[a1,a2,…,ad]。

Step4计算降维后的特征向量Y。根据求得的投影矩阵、高维数据集合，求得降维后的特征向量数据集合Y={y1,y2,…，yN}。

2 基于ECOC-SVMS的离线签名识别

多分类器设计是离线签名识别系统的关键。纠错输出编码(Error Correcting Output Code，ECOC)[13]框架借助通信系统中的编、解码模型，将多类分类问题分解为多个二类分类问题，利用编码冗余特性提供纠错能力，根据某种解码规则得到多类分类结果。ECOC支持向量机在多类识别问题中得到了广泛的应用。ECOC的主要问题在于：1)寻求合适的编码方法将多类分类问题分解为多个二类分类问题，并对二类分类器进行训练；2)设计合理的解码策略，使得融合决策后的输出能够达到优异的分类性能。

2.1 Hadamard纠错输出码

本文引入Hadamard纠错码来设计ECOC编码方法[14]。Hadamard纠错编码矩阵最大的特点在于其任意两行或两列均相互正交。对N阶的Hadamard矩阵，其行、列间的汉明距离均为N/2，具有良好的区分性能，满足ECOC对编码的要求。实际使用时，由于其矩阵第一列全为“-1”且其阶数固定为2的幂次方，需要对Hadamard矩阵进行改造。Hadamard纠错码生成算法如下：

1)根据类别数P确定Hadamard矩阵的阶数：若2i-1

2)按照Hadamard矩阵递推公式生成阶数为2i的Hadamard矩阵H2i；

3)去除矩阵的第一列，并根据类别数P取矩阵的前P行，得到所需的纠错编码矩阵MP×2i-1。

2.2 改进的Hadamard ECOC-SVMS应用于离线签名识别

传统SVM的分类结果并不存在概率输出。通常可认为，样本被分类到某一类的概率可以看作它属于这一类的可能性。一般情况下，SVM中样本xi到分类面的距离是gxi/‖w‖，经训练后样本到分类面的距离仅与判别函数值g(xi)有关。SVM的输出经转换后可以生成近似的后验概率[15]为：

(6)

式(6)中，A、B可通过最大似然方法求解。通过上述方法将SVM输出转换成后验概率，可以对ECOC-SVMS中每个基分类器输出赋予一个概率。分类测试时，将训练样本x送入各个训练好的基分类器，各分类器均会输出类别标签及其对应的近似后验概率输出。各个类别对应序列的概率计算如式(7)[15]：

(7)

式(7)中，k表示类别索引，bj表示一个码字，b1…bn表示编码序列。假定码字的后验概率相互独立，并对式(7)两边取对数，并求取概率最大时对应的类别即为最终的判决类别，即：

(8)

离线签名问题中，通常会采集签名者的多个签名构成签名数据库。签名识别系统中，通过采集的签名样本作为训练样本对分类器进行训练，构建分类器参数。测试时，将测试样本输入至已训练好的多类分类器，分类器的最终输出即为最终的签名识别结果。基于Hadamard ECOC-SVMS的离线签名识别方法步骤如下：

输入：训练样本集Y0={{y1,c1},{y2,c2},…，{yN,cN}}(其中yi表示特征向量，ci表示对应的类别属性)；测试样本集Y1={{y1,c1},{y2,c2},…，{yN,cN}}；类别数P。

输出：分类输出结果ci。

Step1根据样本类别数，由2.1节所述方法生成Hadamard纠错编码输出矩阵MP×2i-1；

Step2根据纠错编码输出矩阵，使用训练样本集对各个基分类器进行训练，得到各基SVM分类器参数、判别函数；

Step3输入测试样本至已训练好的Hadamard ECOC-SVMS分类器中，按式(6)根据分类判别函数计算输出近似概率结果；

Step4按式(7)、式(8)计算测试样本属于各类别的序列的概率，取概率值最大时对应的类别即为最终的分类输出结果ci。

3 实验与分析

3.1 签名图像特征选取

签名图像特征一般包括图像的全局形状或几何结构特征、统计特征等。针对签名灰度、二值图像的特点，本文选取的典型原始特征有：

1)签名图像有效高度宽度比。对签名图像区域四个方向进行扫描，取签名区域的宽、高比值作为一维全局形状特征向量。

2)黑点面积与总面积比。对二值化后的图像，计算签名图像区域黑点像素与总像素比值，作为一维衡量签名笔划的特征向量。

3)重心坐标。根据签名图像水平、垂直方向的黑点投影密度进行计算并归一化，得到水平、垂直方向的坐标作为二维特征向量。

4)笔划宽度分布。通过以签名图像骨架为中心从水平、垂直两个方向向外搜索，取笔划像素点统计结果作为笔划宽度。再对笔划宽度值进行直方图统计，获得笔划宽度的分布。根据签名笔画的通常宽度，取1～18之间的直方图分布共18维特征向量。

5)灰度分布直方图。

对签名图像的签名区域，取灰度级分布的概率直方图作为特征，实际计算时，可通过灰度分布累积值进行归一化。签名图像的灰度级别一般不丰富，可取256级灰度分布中的主要灰度级别即可，本文取64级构成64维特征向量。

6)中心投影。

7)基于Gabor变换的纹理特征。

根据Gabor变换的实现，取5尺度、8方向的Gabor核进行纹理特征提取，共80维统计纹理特征。

8)CS-LBP纹理特征。

签名灰度图像中，对于其中任意像素灰度值gc，在其像素位置为中心、半径为R(R=1或2)的环形邻域上，P(P=8或16)个像素点均匀分布(若均匀分布位置上无对应像素点时，可通过插值法得到)。以该中心像素为基准的纹理可用邻域中P+1个像素定义为：

T=tsg0-gc,sg1-gc,…,sgP-1-gc

(9)

其中，gc，g0，g1,…,gP-1代表中心像素及其邻域上P个点的灰度值，s为权重系数，邻域中像素大于中心像素灰度值时，s为1，否则为0。LBP值定义为：

(10)

中心对称局部二值模式(Center Symmetric LBP,CS-LBP)以LBP为基础[16]，不再依次比较邻域周边P个像素与中心像素的灰度值，而是比较基于中心像素对称的2个周边像素点的灰度值，CS-LBP定义为：

(11)

CS-LBP相比LBP统计直方图的维数更低，维数为2P/2(LBP则为2P)，计算复杂度更低，且抗噪能力更强。取典型的八邻域，CS-LBP特征共16维。

以上各类原始特征通过融合方式可构成206维特征向量。对每幅签名图像，均按本节所述方法进行提取并构成样本的原始特征向量。

3.2 实验结果及分析

为了验证本文方法的可行性和有效性，取自行构建的中文签名数据库作为实验数据来源。签名数据库总共采集了包括不同性别、年龄、书写风格的签名者共计32人的签名，每个签名者在不同时间段、以不同书写速度各签名40个，该数据库共计1280个签名。图像预处理阶段，采用统一的方法对图像进行去噪等预处理。本文实验设计主要考察特征提取中的降维效果以及ECOC-SVMS分类识别性能，如邻域参数K、降维后的维数d、识别率等。

实验1考察特征提取中的降维效果以及对签名识别率的影响，本实验将传统PCA方法、原始LPP方法与本文改进的LPP方法进行比较。从表1可以看出，改进的LPP方法相较于其他2种方法，在获得良好降维特性的同时还保持了较高的分类识别效果。

此外，对于改进LPP中的自适应邻域参数选取情况，邻域K值一般在8～11。从分类识别实验结果来看，自适应邻域值的选择取得了较好的实验效果。

表1 多种特征提取方法的实验结果比较

实验2考察使用本文改进LPP特征提取方法应用于不同ECOC-SVMS分类识别方法时对签名识别效果的影响，本实验将BCH编码ECOC-SVMS方法、原始Hadamard ECOC-SVMS方法与本文改进的Hadamard ECOC-SVMS方法进行比较。从表2可以看出，改进的Hadamard ECOC-SVMS方法相较于其他2种方法，在分类识别率方面具有显著的提升。

表2 本文特征提取方法与其他ECOC-SVMS分类方法的实验结果比较

4 结束语

针对离线签名识别领域，本文提出了一种结合LPP和Hadamard ECOC-SVMS的离线签名识别方法。对于经预处理后的签名图像，选择多种有效特征构建原始的高维特征向量，引入一种改进的保局投影方法进行特征提取并同时实现高效降维；签名识别方面，使用基于Hadamard纠错编码方法的ECOC支持向量机多类分类方法，并引入近似概率方法对ECOC解码进行改进，以提升多类分类器的性能。实验结果表明了此方法的可行性和有效性。下一步应考虑更大规模、种类、不同图像质量的签名数据库，并针对高效特征提取、高性能分类器、算法复杂度优化等方面进行继续深入研究。