基于支持向量機的聯(lián)機手寫(xiě)識別

0 前言

隨著(zhù)智能手機和平板電腦等無(wú)輸入鍵盤(pán)電子設備的流行，聯(lián)機手寫(xiě)識別的研究吸引了越來(lái)越多的關(guān)注。而手寫(xiě)簽名驗證和基于3D加速度傳感器的姿態(tài)識別、手寫(xiě)識別等新應用形式的出現，也為聯(lián)機手寫(xiě)識別的研究注入了新的活力。

支持向量機(Support Vector Machine，SVM)是在統計學(xué)習理論的基礎上發(fā)展起來(lái)的新一代分類(lèi)識別算法，使用核函數方法將非線(xiàn)性可分的特征向量映射到高維空間，計算最大化分類(lèi)間隔的最優(yōu)分類(lèi)超平面。在文本分類(lèi)、語(yǔ)音識別、手寫(xiě)識別、曲線(xiàn)擬合等領(lǐng)域，SVM已經(jīng)有比較成熟的應用。但是，一般的核函數要求不同樣本的特征向量的維數相同，限制了SVM在語(yǔ)音識別和聯(lián)機手寫(xiě)識別領(lǐng)域的進(jìn)一步發(fā)展。為此，Bahlmann等人使用彈性距離計算算法--DTW算法--構造了GDTW核函數，進(jìn)而提出GDTW-SVM算法。GDTW-SVM的聯(lián)機手寫(xiě)識別實(shí)驗結果表明，GDT W-SVM取得了可媲美隱馬爾科夫模型、神經(jīng)網(wǎng)絡(luò )等分類(lèi)算法的識別率，并且與使用后來(lái)提出的基于其它彈性距離計算構造的核函數的SVM相比，性能不相伯仲。

本文結合GDTW核函數和聯(lián)機手寫(xiě)識別樣本的特征向量的特點(diǎn)，引入新的控制參數優(yōu)化GDTW核函數的計算。實(shí)驗結果表明，本文提出的優(yōu)化方法不僅減少了支持向量的數目，而且提高了GDTW-SVM運行效率。

1 聯(lián)機手寫(xiě)識別過(guò)程

1．1 聯(lián)機手寫(xiě)識別流程介紹

聯(lián)機手寫(xiě)識別的過(guò)程與通用模式識別的過(guò)程基本相同，由數據采集和預處理、特征提取、分類(lèi)識別、后處理四個(gè)步驟組成。

在數據采集和預處理階段，首先使用傳感器采集原始物理信息，比較常見(jiàn)的是加速度、速度、位移、起筆和落筆；然后，對原始信息進(jìn)行傳感器矯正、去噪等預處理。

特征提取是手寫(xiě)識別的重要步驟之一，對分類(lèi)器的設計和分類(lèi)結果有著(zhù)重要的影響，選擇合適的特征不僅可以提高識別率，也可以節省計算存儲空間、運算時(shí)間、特征提取費用。聯(lián)機手寫(xiě)識別中比較常見(jiàn)特征提取方法有加速度、位移、DCT變換等。

分類(lèi)識別是手寫(xiě)識別的核心階段，大多數分類(lèi)器在實(shí)際分類(lèi)應用之前，需要使用訓練樣本對分類(lèi)器進(jìn)行訓練，不斷地修正特征提取方法和方案、分類(lèi)器的判決規則和參數。目前，分類(lèi)識別的訓練階段需要人工干預以達到最佳的識別率。

一些識別系統在分類(lèi)識別之后使用后處理進(jìn)一步提高識別率。例如，數字“1”和小寫(xiě)字母“1”在很多情況下難以分辨，但是在后處理階段結合上下文信息，決定當前字符是數字“1”還是小寫(xiě)字母“1”。

1．2 聯(lián)機手寫(xiě)識別實(shí)驗

本文聯(lián)機手寫(xiě)識別實(shí)驗采用了Bahlmann等人和Bothe等人使用的方法。所使用的樣本數據庫是免費的聯(lián)機手寫(xiě)數據庫UJIpenchars2。它采用Toshiba M400 Tablet PC收集，包含60個(gè)書(shū)寫(xiě)者的共11640個(gè)手寫(xiě)樣本。這些樣本包含ASCII字符、拉丁字符和西班牙字符，而每個(gè)字符包含80個(gè)訓練樣本和140個(gè)測試樣本。每個(gè)樣本由一劃或多劃組成，數據庫提供每個(gè)筆劃的坐標序列。

坐標序列由等時(shí)間間隔采集的筆尖的水平坐標xi和垂直坐標yi組成。而在本文實(shí)驗中，樣本的坐標序列不經(jīng)過(guò)任何去噪等預處理，直接對每個(gè)坐標點(diǎn)，使用字符的重心(μx，μy)和垂直坐標的方差σy計算列向量

式(1)中，ang是求虛數相角的函數。每個(gè)字符樣本的特征向量是T=(t1，…，tNT)，其中，NT是采集的坐標點(diǎn)數目，即特征向量的維數，每個(gè)字符樣本的NT可以不相同。

本文的聯(lián)機手寫(xiě)識別實(shí)驗假設每個(gè)字符不需要分析其上下文即可完成識別，所以，特征提取之后使用本文所述的分類(lèi)算法進(jìn)行分類(lèi)識別，并且將其輸出結果作為最終識別結果，不經(jīng)過(guò)任何后處理。

2 GDTW-SVM算法

2．1 支持向量機

假設線(xiàn)性分類(lèi)器對輸入的特征向量x={x1，x2，…xn}(n是樣本數目)，輸出Y={y1，y2，…，yn}其中，xi，I RN，N是特征向量的維數：yi∈{-1，1}， yi=-1表示樣本(xi，yi)屬于第一類(lèi)，yi=1表示樣本(xi，yi)屬于另一類(lèi)。該線(xiàn)性分類(lèi)器的分類(lèi)決策為

y(+b)≥1 (2)

式(2)中(w,b)確定分類(lèi)超平面+b=0。

SVM以最小化結構風(fēng)險為目標，計算使得訓練樣本集到分類(lèi)超平面的距離最大化的最優(yōu)分類(lèi)超平面。其等價(jià)于對式(2)求解凸二次規劃問(wèn)題。

即尋找使平均距離最小的最優(yōu)對齊路徑。DTW距離越小，T和R所代表的樣本越相似?？梢允褂脛?dòng)態(tài)規劃(Dynamic Programming)算法計算最優(yōu)對齊路徑和DTW距離。

圖1給出了最優(yōu)對齊路徑和DTW距離的示例，其中，上半部分是字符樣本的繪圖，順次是“oocae”；下半部分是各個(gè)字符樣本與第一個(gè)字符樣本的最優(yōu)對齊路徑和DTW距離。

Bahlmann等人使用DTW距離代替高斯核函數(6)中的歐幾里德距離‖X-Z‖p的計算(取p=2)，構造了GDTW核函數

KGRBF(X，Z)=exp(-y·DTW(X，Z)) (8)

他們的聯(lián)機手寫(xiě)識別實(shí)驗的結果和Bothe等人的實(shí)驗結果表明，GDTW-SVM取得了比GDTW-SVM和k近鄰算法(k-Nearest Neighbor，kNN)更高的識別率，而且在不同聯(lián)機手寫(xiě)識別數據庫子集的識別實(shí)驗中，與基于其它彈性距離計算的核函數的SVM相比，各有優(yōu)劣且識別率的差值在0．3％以?xún)取?br type="_moz" />
到字母n的所有訓練樣本最優(yōu)對齊路徑，并規整到80’80矩陣；

(2)將所有計算結果疊加后得到n-n最優(yōu)對齊路徑疊加圖；

(3)繪制疊加圖，即圖2的第一幅圖，圖中像素點(diǎn)灰度越高，代表越多最優(yōu)對齊路徑經(jīng)過(guò)此點(diǎn)。同理，繪制n-m最優(yōu)對齊路徑疊加圖和m-m最優(yōu)對齊路徑疊加圖，分別為圖2的第二和第三幅圖所示。

從圖2可以看到，兩個(gè)相同或相似字符的最優(yōu)對齊路徑集中在對角區域：由于n的不同樣本、m的不同樣本的起筆寫(xiě)法比收筆寫(xiě)法隨意，第一和第三幅圖的對角區域的左下角比較寬；n和m的最優(yōu)對齊路徑在對角區域中分布較均勻，且第二幅圖顯示對角區域的中部有明顯的低灰度區域。

假設訓練樣本可以代表聯(lián)機手寫(xiě)字符的特征，則可以通過(guò)僅計算對角區域中的最優(yōu)對齊路徑來(lái)優(yōu)化GDTW核函數。計算兩個(gè)樣本T=(t1，…，tNT)和R=(r1，…，rNR)的GDTW核函數時(shí)，假定二者屬于相同的字符類(lèi)，那么二者的差別不大，因此，在GDTW核函數計算中引入參數k和τ

式(9)中lbottom，ltop，lleft，lright如圖3所示。引入參數k和τ之后，不在NT×NR的矩陣中求解式(8)，而是在k和τ約束的區域(即圖3中兩條虛線(xiàn)所夾的對角區域)中求解，計算最優(yōu)對齊路徑。

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

4 實(shí)驗結果與分析

本文主要針對阿拉伯數字樣本集和英文字母樣本集進(jìn)行識別實(shí)驗，阿拉伯數字樣本集、英文小寫(xiě)字母樣本集和英文大寫(xiě)字母樣本集分開(kāi)識別。實(shí)驗環(huán)境是Matlab R2010a，所使用的SVM工具包是Matlab SVM Toolbox。

分類(lèi)實(shí)驗采用Leave-One-Out的交叉驗證策略：依次從樣本集中取出一個(gè)字符的訓練樣本標記為第一類(lèi)，將剩余字符的訓練樣本標記為第二類(lèi)，用標記后的訓練樣本訓練GDTW-SVM；使用樣本集中的所有測試樣本測試GDTW-SVM的識別率。

使用未優(yōu)化GDTW-SVM重復分類(lèi)識別10次，取10次實(shí)驗結果的平均值作為未優(yōu)化GDTW-SVM的識別結果；其次，優(yōu)化GDTW-SVM的參數(K，τ)分別取(0．2，0．5)、(0．2，0．2)和(0．5，0．5)，分別重復分類(lèi)識別10次且取10次識別結果的平均值作為使用該組參數的優(yōu)化GDTW-SVM的識別結果，最終取三組識別結果中的最優(yōu)識別結果作為優(yōu)化GDTW-SVM的識別結果；以上實(shí)驗中，γ=1．9。

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

5 結論

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