基于优化GDTW-SVM算法的联机手写识别

摘要：基于高斯动态时间规整核函数(Gaussian Dynamic Time Warping kernel)的支持向量机(GDTW-SVM)在联机手写识别中有较高的识别率，但是存在计算复杂度高的问题。结合联机手写识别中特征向量的特点，提出了通过引入控制参数来约束GDTW最优对齐路径计算空间的方法，优化了GDTW核函数。然后，使用联机手写识别数据库UJIpenchar2进行实验。实验结果表明，该优化方法不仅可以减少支持向量的数目，而且提高了GDTW-SVM算法运行的效率。
关键词：手写识别；动态时间规整；支持向量机；核方法

0 前言
    随着智能手机和平板电脑等无输入键盘电子设备的流行，联机手写识别的研究吸引了越来越多的关注。而手写签名验证和基于3D加速度传感器的姿态识别、手写识别等新应用形式的出现，也为联机手写识别的研究注入了新的活力。
    支持向量机(Support Vector Machine，SVM)是在统计学习理论的基础上发展起来的新一代分类识别算法，使用核函数方法将非线性可分的特征向量映射到高维空间，计算最大化分类间隔的最优分类超平面。在文本分类、语音识别、手写识别、曲线拟合等领域，SVM已经有比较成熟的应用。但是，一般的核函数要求不同样本的特征向量的维数相同，限制了SVM在语音识别和联机手写识别领域的进一步发展。为此，Bahlmann等人使用弹性距离计算算法--DTW算法--构造了GDTW核函数，进而提出GDTW-SVM算法。GDTW-SVM的联机手写识别实验结果表明，GDT W-SVM取得了可媲美隐马尔科夫模型、神经网络等分类算法的识别率，并且与使用后来提出的基于其它弹性距离计算构造的核函数的SVM相比，性能不相伯仲。
    本文结合GDTW核函数和联机手写识别样本的特征向量的特点，引入新的控制参数优化GDTW核函数的计算。实验结果表明，本文提出的优化方法不仅减少了支持向量的数目，而且提高了GDTW-SVM运行效率。

1 联机手写识别过程
1．1 联机手写识别流程介绍
    联机手写识别的过程与通用模式识别的过程基本相同，由数据采集和预处理、特征提取、分类识别、后处理四个步骤组成。
    在数据采集和预处理阶段，首先使用传感器采集原始物理信息，比较常见的是加速度、速度、位移、起笔和落笔；然后，对原始信息进行传感器矫正、去噪等预处理。
    特征提取是手写识别的重要步骤之一，对分类器的设计和分类结果有着重要的影响，选择合适的特征不仅可以提高识别率，也可以节省计算存储空间、运算时间、特征提取费用。联机手写识别中比较常见特征提取方法有加速度、位移、DCT变换等。
    分类识别是手写识别的核心阶段，大多数分类器在实际分类应用之前，需要使用训练样本对分类器进行训练，不断地修正特征提取方法和方案、分类器的判决规则和参数。目前，分类识别的训练阶段需要人工干预以达到最佳的识别率。
    一些识别系统在分类识别之后使用后处理进一步提高识别率。例如，数字“1”和小写字母“1”在很多情况下难以分辨，但是在后处理阶段结合上下文信息，决定当前字符是数字“1”还是小写字母“1”。
1．2 联机手写识别实验
    本文联机手写识别实验采用了Bahlmann等人和Bothe等人使用的方法。所使用的样本数据库是免费的联机手写数据库UJIpenchars2。它采用Toshiba M400 Tablet PC收集，包含60个书写者的共11640个手写样本。这些样本包含ASCII字符、拉丁字符和西班牙字符，而每个字符包含80个训练样本和140个测试样本。每个样本由一划或多划组成，数据库提供每个笔划的坐标序列。
    坐标序列由等时间间隔采集的笔尖的水平坐标xi和垂直坐标yi组成。而在本文实验中，样本的坐标序列不经过任何去噪等预处理，直接对每个坐标点，使用字符的重心(μx，μy)和垂直坐标的方差σy计算列向量
   
    式(1)中，ang是求虚数相角的函数。每个字符样本的特征向量是T=(t1，…，tNT)，其中，NT是采集的坐标点数目，即特征向量的维数，每个字符样本的NT可以不相同。
    本文的联机手写识别实验假设每个字符不需要分析其上下文即可完成识别，所以，特征提取之后使用本文所述的分类算法进行分类识别，并且将其输出结果作为最终识别结果，不经过任何后处理。

2 GDTW-SVM算法
2．1 支持向量机
    假设线性分类器对输入的特征向量x={x1，x2，…xn}(n是样本数目)，输出Y={y1，y2，…，yn}其中，xi，I RN，N是特征向量的维数：yi∈{-1，1}， yi=-1表示样本(xi，yi)属于第一类，yi=1表示样本(xi，yi)属于另一类。该线性分类器的分类决策为
    y(<w·x>+b)≥1         (2)
    式(2)中(w,b)确定分类超平面<w·x>+b=0。
    SVM以最小化结构风险为目标，计算使得训练样本集到分类超平面的距离最大化的最优分类超平面。其等价于对式(2)求解凸二次规划问题。

    式(4)中ai是拉格朗日乘子，靠近超平面的点对应的ai非零，其它所有点对应的ai为零。因此，最优分类决策的对偶表示
   
    只包含ai非零的点。这些点称为支持向量(Support Vector，SV)，支持向量决定了最优分类超平面，且其数目越多，分类判决的计算时间越长。
    对于非线性可分样本，SVM使用满足Mercer定理的核函数K(x，z)，代替式(5)中的内积计算，将输入的特征向量映射到高维线性可分的特征空间。Merce定理保证了核函数的正定对称性和式(4)最优化问题求解过程的收敛性。一个比较常用的核函数是高斯核函数(GRBF)
    KGRBF(X，Z)=exp(-y·‖X-Z‖p)，p=1，2，…      (6)
2．2 GDTW核函数
    假设T=(t1，…，tNT)和R=(r1，…，rNR)是长度分别为NT和NR的特征向量序列。对齐路径f=(f(1)，…，f(L))是对齐序列T和R的索引序列，其中，L是路径长度，
   
    即寻找使平均距离最小的最优对齐路径。DTW距离越小，T和R所代表的样本越相似。可以使用动态规划(Dynamic Programming)算法计算最优对齐路径和DTW距离。
    图1给出了最优对齐路径和DTW距离的示例，其中，上半部分是字符样本的绘图，顺次是“oocae”；下半部分是各个字符样本与第一个字符样本的最优对齐路径和DTW距离。

    Bahlmann等人使用DTW距离代替高斯核函数(6)中的欧几里德距离‖X-Z‖p的计算(取p=2)，构造了GDTW核函数
    KGRBF(X，Z)=exp(-y·DTW(X，Z))      (8)
    他们的联机手写识别实验的结果和Bothe等人的实验结果表明，GDTW-SVM取得了比GDTW-SVM和k近邻算法(k-Nearest Neighbor，kNN)更高的识别率，而且在不同联机手写识别数据库子集的识别实验中，与基于其它弹性距离计算的核函数的SVM相比，各有优劣且识别率的差值在0．3％以内。

3 优化GDTW-SVM算法
    尽管GDTW-SVM获得了较高的识别率，但是其计算复杂度高。DTW算法的计算复杂度是O(NT,NR)，而SVM算法在训练和识别过程中需要反复使用GDTW核函数，对于嵌入式设备的计算能力要求较高。因此，需要对GDTW核函数进行优化。
    分析图1中的最优对齐路径，当两个样本完全相同时，最优对齐路径和对角线重合；当两个样本有所差别时，最优对齐路径偏离对角线，且差别(DTW距离)越大最优路径越偏离对角线。下面以字母m和n为例，进一步分析以上结论。
    (1)依次从字母n的所有训练样本中选择一个样本，计算其到字母n的所有训练样本最优对齐路径，并规整到80’80矩阵；
    (2)将所有计算结果叠加后得到n-n最优对齐路径叠加图；
    (3)绘制叠加图，即图2的第一幅图，图中像素点灰度越高，代表越多最优对齐路径经过此点。同理，绘制n-m最优对齐路径叠加图和m-m最优对齐路径叠加图，分别为图2的第二和第三幅图所示。

    从图2可以看到，两个相同或相似字符的最优对齐路径集中在对角区域：由于n的不同样本、m的不同样本的起笔写法比收笔写法随意，第一和第三幅图的对角区域的左下角比较宽；n和m的最优对齐路径在对角区域中分布较均匀，且第二幅图显示对角区域的中部有明显的低灰度区域。
    假设训练样本可以代表联机手写字符的特征，则可以通过仅计算对角区域中的最优对齐路径来优化GDTW核函数。计算两个样本T=(t1，…，tNT)和R=(r1，…，rNR)的GDTW核函数时，假定二者属于相同的字符类，那么二者的差别不大，因此，在GDTW核函数计算中引入参数k和τ
   
    式(9)中lbottom，ltop，lleft，lright如图3所示。引入参数k和τ之后，不在NT×NR的矩阵中求解式(8)，而是在k和τ约束的区域(即图3中两条虚线所夹的对角区域)中求解，计算最优对齐路径。

    从直观的角度看，参数k和τ减少了最优对齐路径的计算空间，因此，修改后的GDTW核函数的计算时间减少。而另外一方面，如果参数τ保持不变(如τ=0．6)，参数k越小，最优对齐路径的前端的计算被约束在越小的空间，迫使其“最优”对齐路径的计算选择非最优对齐路径，即参数k是两个字符样本头部的相识程度的权重；类似地，参数τ是两个字符样本尾部的相识程度的权重。参数k和τ的权重作用对于如数字“0”和“6”等相似字符的分类有重要意义。

4 实验结果与分析
    本文主要针对阿拉伯数字样本集和英文字母样本集进行识别实验，阿拉伯数字样本集、英文小写字母样本集和英文大写字母样本集分开识别。实验环境是Matlab R2010a，所使用的SVM工具包是Matlab SVM Toolbox。
    分类实验采用Leave-One-Out的交叉验证策略：依次从样本集中取出一个字符的训练样本标记为第一类，将剩余字符的训练样本标记为第二类，用标记后的训练样本训练GDTW-SVM；使用样本集中的所有测试样本测试GDTW-SVM的识别率。
    使用未优化GDTW-SVM重复分类识别10次，取10次实验结果的平均值作为未优化GDTW-SVM的识别结果；其次，优化GDTW-SVM的参数(K，τ)分别取(0．2，0．5)、(0．2，0．2)和(0．5，0．5)，分别重复分类识别10次且取10次识别结果的平均值作为使用该组参数的优化GDTW-SVM的识别结果，最终取三组识别结果中的最优识别结果作为优化GDTW-SVM的识别结果；以上实验中，γ=1．9。

    表1是阿拉伯数字和英文字母的识别结果对比。其中，英文字母数目较多，因此，仅给出平均识别结果。优化后的GDTW-SVM和未优化的GDTW-SVM的实验结果对比显示：参数k和τ的引入不仅使字符识别的错误率基本保持不变，同时，训练时间减少13～25％、测试时间减少29～39％、支持向量的数目也减少3．0～7．6％。

5 结论
    本文提出了在GDTW核函数中引入参数k和τ，约束GDTW最优对齐路径的计算空间，然后构造GDTW-SVM分类器。实验结果表明，优化后的GDTW-SVM分类器的识别率与未优化的分类器的识别率基本相同；同时，支持向量数目减少，计算时间有13％～39％的减少，有利于GDTW-SVM分类器的联机手写识别的应用和推广。