摘要：基于高斯動(dòng)態(tài)時(shí)間規(guī)整核函數(shù)(Gaussian Dynamic Time Warping kernel)的支持向量機(jī)(GDTW-SVM)在聯(lián)機(jī)手寫(xiě)識(shí)別中有較高的識(shí)別率，但是存在計(jì)算復(fù)雜度高的問(wèn)題。結(jié)合聯(lián)機(jī)手寫(xiě)識(shí)別中特征向量的特點(diǎn)，提出了通過(guò)引入控制參數(shù)來(lái)約束GDTW最優(yōu)對(duì)齊路徑計(jì)算空間的方法，優(yōu)化了GDTW核函數(shù)。然后，使用聯(lián)機(jī)手寫(xiě)識(shí)別數(shù)據(jù)庫(kù)UJIpenchar2進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該優(yōu)化方法不僅可以減少支持向量的數(shù)目，而且提高了GDTW-SVM算法運(yùn)行的效率。
關(guān)鍵詞：手寫(xiě)識(shí)別；動(dòng)態(tài)時(shí)間規(guī)整；支持向量機(jī)；核方法

0 前言
    隨著智能手機(jī)和平板電腦等無(wú)輸入鍵盤(pán)電子設(shè)備的流行，聯(lián)機(jī)手寫(xiě)識(shí)別的研究吸引了越來(lái)越多的關(guān)注。而手寫(xiě)簽名驗(yàn)證和基于3D加速度傳感器的姿態(tài)識(shí)別、手寫(xiě)識(shí)別等新應(yīng)用形式的出現(xiàn)，也為聯(lián)機(jī)手寫(xiě)識(shí)別的研究注入了新的活力。
    支持向量機(jī)(Support Vector Machine，SVM)是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展起來(lái)的新一代分類識(shí)別算法，使用核函數(shù)方法將非線性可分的特征向量映射到高維空間，計(jì)算最大化分類間隔的最優(yōu)分類超平面。在文本分類、語(yǔ)音識(shí)別、手寫(xiě)識(shí)別、曲線擬合等領(lǐng)域，SVM已經(jīng)有比較成熟的應(yīng)用。但是，一般的核函數(shù)要求不同樣本的特征向量的維數(shù)相同，限制了SVM在語(yǔ)音識(shí)別和聯(lián)機(jī)手寫(xiě)識(shí)別領(lǐng)域的進(jìn)一步發(fā)展。為此，Bahlmann等人使用彈性距離計(jì)算算法--DTW算法--構(gòu)造了GDTW核函數(shù)，進(jìn)而提出GDTW-SVM算法。GDTW-SVM的聯(lián)機(jī)手寫(xiě)識(shí)別實(shí)驗(yàn)結(jié)果表明，GDT W-SVM取得了可媲美隱馬爾科夫模型、神經(jīng)網(wǎng)絡(luò)等分類算法的識(shí)別率，并且與使用后來(lái)提出的基于其它彈性距離計(jì)算構(gòu)造的核函數(shù)的SVM相比，性能不相伯仲。
    本文結(jié)合GDTW核函數(shù)和聯(lián)機(jī)手寫(xiě)識(shí)別樣本的特征向量的特點(diǎn)，引入新的控制參數(shù)優(yōu)化GDTW核函數(shù)的計(jì)算。實(shí)驗(yàn)結(jié)果表明，本文提出的優(yōu)化方法不僅減少了支持向量的數(shù)目，而且提高了GDTW-SVM運(yùn)行效率。

1 聯(lián)機(jī)手寫(xiě)識(shí)別過(guò)程
1．1 聯(lián)機(jī)手寫(xiě)識(shí)別流程介紹
    聯(lián)機(jī)手寫(xiě)識(shí)別的過(guò)程與通用模式識(shí)別的過(guò)程基本相同，由數(shù)據(jù)采集和預(yù)處理、特征提取、分類識(shí)別、后處理四個(gè)步驟組成。
    在數(shù)據(jù)采集和預(yù)處理階段，首先使用傳感器采集原始物理信息，比較常見(jiàn)的是加速度、速度、位移、起筆和落筆；然后，對(duì)原始信息進(jìn)行傳感器矯正、去噪等預(yù)處理。
    特征提取是手寫(xiě)識(shí)別的重要步驟之一，對(duì)分類器的設(shè)計(jì)和分類結(jié)果有著重要的影響，選擇合適的特征不僅可以提高識(shí)別率，也可以節(jié)省計(jì)算存儲(chǔ)空間、運(yùn)算時(shí)間、特征提取費(fèi)用。聯(lián)機(jī)手寫(xiě)識(shí)別中比較常見(jiàn)特征提取方法有加速度、位移、DCT變換等。
    分類識(shí)別是手寫(xiě)識(shí)別的核心階段，大多數(shù)分類器在實(shí)際分類應(yīng)用之前，需要使用訓(xùn)練樣本對(duì)分類器進(jìn)行訓(xùn)練，不斷地修正特征提取方法和方案、分類器的判決規(guī)則和參數(shù)。目前，分類識(shí)別的訓(xùn)練階段需要人工干預(yù)以達(dá)到最佳的識(shí)別率。
    一些識(shí)別系統(tǒng)在分類識(shí)別之后使用后處理進(jìn)一步提高識(shí)別率。例如，數(shù)字“1”和小寫(xiě)字母“1”在很多情況下難以分辨，但是在后處理階段結(jié)合上下文信息，決定當(dāng)前字符是數(shù)字“1”還是小寫(xiě)字母“1”。
1．2 聯(lián)機(jī)手寫(xiě)識(shí)別實(shí)驗(yàn)
    本文聯(lián)機(jī)手寫(xiě)識(shí)別實(shí)驗(yàn)采用了Bahlmann等人和Bothe等人使用的方法。所使用的樣本數(shù)據(jù)庫(kù)是免費(fèi)的聯(lián)機(jī)手寫(xiě)數(shù)據(jù)庫(kù)UJIpenchars2。它采用Toshiba M400 Tablet PC收集，包含60個(gè)書(shū)寫(xiě)者的共11640個(gè)手寫(xiě)樣本。這些樣本包含ASCII字符、拉丁字符和西班牙字符，而每個(gè)字符包含80個(gè)訓(xùn)練樣本和140個(gè)測(cè)試樣本。每個(gè)樣本由一劃或多劃組成，數(shù)據(jù)庫(kù)提供每個(gè)筆劃的坐標(biāo)序列。
    坐標(biāo)序列由等時(shí)間間隔采集的筆尖的水平坐標(biāo)xi和垂直坐標(biāo)yi組成。而在本文實(shí)驗(yàn)中，樣本的坐標(biāo)序列不經(jīng)過(guò)任何去噪等預(yù)處理，直接對(duì)每個(gè)坐標(biāo)點(diǎn)，使用字符的重心(μx，μy)和垂直坐標(biāo)的方差σy計(jì)算列向量
   
    式(1)中，ang是求虛數(shù)相角的函數(shù)。每個(gè)字符樣本的特征向量是T=(t1，…，tNT)，其中，NT是采集的坐標(biāo)點(diǎn)數(shù)目，即特征向量的維數(shù)，每個(gè)字符樣本的NT可以不相同。
    本文的聯(lián)機(jī)手寫(xiě)識(shí)別實(shí)驗(yàn)假設(shè)每個(gè)字符不需要分析其上下文即可完成識(shí)別，所以，特征提取之后使用本文所述的分類算法進(jìn)行分類識(shí)別，并且將其輸出結(jié)果作為最終識(shí)別結(jié)果，不經(jīng)過(guò)任何后處理。

2 GDTW-SVM算法
2．1 支持向量機(jī)
    假設(shè)線性分類器對(duì)輸入的特征向量x={x1，x2，…xn}(n是樣本數(shù)目)，輸出Y={y1，y2，…，yn}其中，xi，I RN，N是特征向量的維數(shù)：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以最小化結(jié)構(gòu)風(fēng)險(xiǎn)為目標(biāo)，計(jì)算使得訓(xùn)練樣本集到分類超平面的距離最大化的最優(yōu)分類超平面。其等價(jià)于對(duì)式(2)求解凸二次規(guī)劃問(wèn)題。

    式(4)中ai是拉格朗日乘子，靠近超平面的點(diǎn)對(duì)應(yīng)的ai非零，其它所有點(diǎn)對(duì)應(yīng)的ai為零。因此，最優(yōu)分類決策的對(duì)偶表示
   
    只包含ai非零的點(diǎn)。這些點(diǎn)稱為支持向量(Support Vector，SV)，支持向量決定了最優(yōu)分類超平面，且其數(shù)目越多，分類判決的計(jì)算時(shí)間越長(zhǎng)。
    對(duì)于非線性可分樣本，SVM使用滿足Mercer定理的核函數(shù)K(x，z)，代替式(5)中的內(nèi)積計(jì)算，將輸入的特征向量映射到高維線性可分的特征空間。Merce定理保證了核函數(shù)的正定對(duì)稱性和式(4)最優(yōu)化問(wèn)題求解過(guò)程的收斂性。一個(gè)比較常用的核函數(shù)是高斯核函數(shù)(GRBF)
    KGRBF(X，Z)=exp(-y·‖X-Z‖p)，p=1，2，…      (6)
2．2 GDTW核函數(shù)
    假設(shè)T=(t1，…，tNT)和R=(r1，…，rNR)是長(zhǎng)度分別為NT和NR的特征向量序列。對(duì)齊路徑f=(f(1)，…，f(L))是對(duì)齊序列T和R的索引序列，其中，L是路徑長(zhǎng)度，
   
    即尋找使平均距離最小的最優(yōu)對(duì)齊路徑。DTW距離越小，T和R所代表的樣本越相似。可以使用動(dòng)態(tài)規(guī)劃(Dynamic Programming)算法計(jì)算最優(yōu)對(duì)齊路徑和DTW距離。
    圖1給出了最優(yōu)對(duì)齊路徑和DTW距離的示例，其中，上半部分是字符樣本的繪圖，順次是“oocae”；下半部分是各個(gè)字符樣本與第一個(gè)字符樣本的最優(yōu)對(duì)齊路徑和DTW距離。

    Bahlmann等人使用DTW距離代替高斯核函數(shù)(6)中的歐幾里德距離‖X-Z‖p的計(jì)算(取p=2)，構(gòu)造了GDTW核函數(shù)
    KGRBF(X，Z)=exp(-y·DTW(X，Z))      (8)
    他們的聯(lián)機(jī)手寫(xiě)識(shí)別實(shí)驗(yàn)的結(jié)果和Bothe等人的實(shí)驗(yàn)結(jié)果表明，GDTW-SVM取得了比GDTW-SVM和k近鄰算法(k-Nearest Neighbor，kNN)更高的識(shí)別率，而且在不同聯(lián)機(jī)手寫(xiě)識(shí)別數(shù)據(jù)庫(kù)子集的識(shí)別實(shí)驗(yàn)中，與基于其它彈性距離計(jì)算的核函數(shù)的SVM相比，各有優(yōu)劣且識(shí)別率的差值在0．3％以內(nèi)。

3 優(yōu)化GDTW-SVM算法
    盡管GDTW-SVM獲得了較高的識(shí)別率，但是其計(jì)算復(fù)雜度高。DTW算法的計(jì)算復(fù)雜度是O(NT,NR)，而SVM算法在訓(xùn)練和識(shí)別過(guò)程中需要反復(fù)使用GDTW核函數(shù)，對(duì)于嵌入式設(shè)備的計(jì)算能力要求較高。因此，需要對(duì)GDTW核函數(shù)進(jìn)行優(yōu)化。
    分析圖1中的最優(yōu)對(duì)齊路徑，當(dāng)兩個(gè)樣本完全相同時(shí)，最優(yōu)對(duì)齊路徑和對(duì)角線重合；當(dāng)兩個(gè)樣本有所差別時(shí)，最優(yōu)對(duì)齊路徑偏離對(duì)角線，且差別(DTW距離)越大最優(yōu)路徑越偏離對(duì)角線。下面以字母m和n為例，進(jìn)一步分析以上結(jié)論。
    (1)依次從字母n的所有訓(xùn)練樣本中選擇一個(gè)樣本，計(jì)算其到字母n的所有訓(xùn)練樣本最優(yōu)對(duì)齊路徑，并規(guī)整到80’80矩陣；
    (2)將所有計(jì)算結(jié)果疊加后得到n-n最優(yōu)對(duì)齊路徑疊加圖；
    (3)繪制疊加圖，即圖2的第一幅圖，圖中像素點(diǎn)灰度越高，代表越多最優(yōu)對(duì)齊路徑經(jīng)過(guò)此點(diǎn)。同理，繪制n-m最優(yōu)對(duì)齊路徑疊加圖和m-m最優(yōu)對(duì)齊路徑疊加圖，分別為圖2的第二和第三幅圖所示。

    從圖2可以看到，兩個(gè)相同或相似字符的最優(yōu)對(duì)齊路徑集中在對(duì)角區(qū)域：由于n的不同樣本、m的不同樣本的起筆寫(xiě)法比收筆寫(xiě)法隨意，第一和第三幅圖的對(duì)角區(qū)域的左下角比較寬；n和m的最優(yōu)對(duì)齊路徑在對(duì)角區(qū)域中分布較均勻，且第二幅圖顯示對(duì)角區(qū)域的中部有明顯的低灰度區(qū)域。
    假設(shè)訓(xùn)練樣本可以代表聯(lián)機(jī)手寫(xiě)字符的特征，則可以通過(guò)僅計(jì)算對(duì)角區(qū)域中的最優(yōu)對(duì)齊路徑來(lái)優(yōu)化GDTW核函數(shù)。計(jì)算兩個(gè)樣本T=(t1，…，tNT)和R=(r1，…，rNR)的GDTW核函數(shù)時(shí)，假定二者屬于相同的字符類，那么二者的差別不大，因此，在GDTW核函數(shù)計(jì)算中引入?yún)?shù)k和τ
   
    式(9)中l(wèi)bottom，ltop，lleft，lright如圖3所示。引入?yún)?shù)k和τ之后，不在NT×NR的矩陣中求解式(8)，而是在k和τ約束的區(qū)域(即圖3中兩條虛線所夾的對(duì)角區(qū)域)中求解，計(jì)算最優(yōu)對(duì)齊路徑。

    從直觀的角度看，參數(shù)k和τ減少了最優(yōu)對(duì)齊路徑的計(jì)算空間，因此，修改后的GDTW核函數(shù)的計(jì)算時(shí)間減少。而另外一方面，如果參數(shù)τ保持不變(如τ=0．6)，參數(shù)k越小，最優(yōu)對(duì)齊路徑的前端的計(jì)算被約束在越小的空間，迫使其“最優(yōu)”對(duì)齊路徑的計(jì)算選擇非最優(yōu)對(duì)齊路徑，即參數(shù)k是兩個(gè)字符樣本頭部的相識(shí)程度的權(quán)重；類似地，參數(shù)τ是兩個(gè)字符樣本尾部的相識(shí)程度的權(quán)重。參數(shù)k和τ的權(quán)重作用對(duì)于如數(shù)字“0”和“6”等相似字符的分類有重要意義。

4 實(shí)驗(yàn)結(jié)果與分析
    本文主要針對(duì)阿拉伯?dāng)?shù)字樣本集和英文字母樣本集進(jìn)行識(shí)別實(shí)驗(yàn)，阿拉伯?dāng)?shù)字樣本集、英文小寫(xiě)字母樣本集和英文大寫(xiě)字母樣本集分開(kāi)識(shí)別。實(shí)驗(yàn)環(huán)境是Matlab R2010a，所使用的SVM工具包是Matlab SVM Toolbox。
    分類實(shí)驗(yàn)采用Leave-One-Out的交叉驗(yàn)證策略：依次從樣本集中取出一個(gè)字符的訓(xùn)練樣本標(biāo)記為第一類，將剩余字符的訓(xùn)練樣本標(biāo)記為第二類，用標(biāo)記后的訓(xùn)練樣本訓(xùn)練GDTW-SVM；使用樣本集中的所有測(cè)試樣本測(cè)試GDTW-SVM的識(shí)別率。
    使用未優(yōu)化GDTW-SVM重復(fù)分類識(shí)別10次，取10次實(shí)驗(yàn)結(jié)果的平均值作為未優(yōu)化GDTW-SVM的識(shí)別結(jié)果；其次，優(yōu)化GDTW-SVM的參數(shù)(K，τ)分別取(0．2，0．5)、(0．2，0．2)和(0．5，0．5)，分別重復(fù)分類識(shí)別10次且取10次識(shí)別結(jié)果的平均值作為使用該組參數(shù)的優(yōu)化GDTW-SVM的識(shí)別結(jié)果，最終取三組識(shí)別結(jié)果中的最優(yōu)識(shí)別結(jié)果作為優(yōu)化GDTW-SVM的識(shí)別結(jié)果；以上實(shí)驗(yàn)中，γ=1．9。

    表1是阿拉伯?dāng)?shù)字和英文字母的識(shí)別結(jié)果對(duì)比。其中，英文字母數(shù)目較多，因此，僅給出平均識(shí)別結(jié)果。優(yōu)化后的GDTW-SVM和未優(yōu)化的GDTW-SVM的實(shí)驗(yàn)結(jié)果對(duì)比顯示：參數(shù)k和τ的引入不僅使字符識(shí)別的錯(cuò)誤率基本保持不變，同時(shí)，訓(xùn)練時(shí)間減少13～25％、測(cè)試時(shí)間減少29～39％、支持向量的數(shù)目也減少3．0～7．6％。

5 結(jié)論
    本文提出了在GDTW核函數(shù)中引入?yún)?shù)k和τ，約束GDTW最優(yōu)對(duì)齊路徑的計(jì)算空間，然后構(gòu)造GDTW-SVM分類器。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的GDTW-SVM分類器的識(shí)別率與未優(yōu)化的分類器的識(shí)別率基本相同；同時(shí)，支持向量數(shù)目減少，計(jì)算時(shí)間有13％～39％的減少，有利于GDTW-SVM分類器的聯(lián)機(jī)手寫(xiě)識(shí)別的應(yīng)用和推廣。