0 前言
隨著智能手機(jī)和平板電腦等無輸入鍵盤電子設(shè)備的流行,聯(lián)機(jī)手寫識(shí)別的研究吸引了越來越多的關(guān)注。而手寫簽名驗(yàn)證和基于3D加速度傳感器的姿態(tài)識(shí)別、手寫識(shí)別等新應(yīng)用形式的出現(xiàn),也為聯(lián)機(jī)手寫識(shí)別的研究注入了新的活力。
支持向量機(jī)(Support Vector Machine,SVM)是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展起來的新一代分類識(shí)別算法,使用核函數(shù)方法將非線性可分的特征向量映射到高維空間,計(jì)算最大化分類間隔的最優(yōu)分類超平面。在文本分類、語音識(shí)別、手寫識(shí)別、曲線擬合等領(lǐng)域,SVM已經(jīng)有比較成熟的應(yīng)用。但是,一般的核函數(shù)要求不同樣本的特征向量的維數(shù)相同,限制了SVM在語音識(shí)別和聯(lián)機(jī)手寫識(shí)別領(lǐng)域的進(jìn)一步發(fā)展。為此,Bahlmann等人使用彈性距離計(jì)算算法--DTW算法--構(gòu)造了GDTW核函數(shù),進(jìn)而提出GDTW-SVM算法。GDTW-SVM的聯(lián)機(jī)手寫識(shí)別實(shí)驗(yàn)結(jié)果表明,GDT W-SVM取得了可媲美隱馬爾科夫模型、神經(jīng)網(wǎng)絡(luò)等分類算法的識(shí)別率,并且與使用后來提出的基于其它彈性距離計(jì)算構(gòu)造的核函數(shù)的SVM相比,性能不相伯仲。
本文結(jié)合GDTW核函數(shù)和聯(lián)機(jī)手寫識(shí)別樣本的特征向量的特點(diǎn),引入新的控制參數(shù)優(yōu)化GDTW核函數(shù)的計(jì)算。實(shí)驗(yàn)結(jié)果表明,本文提出的優(yōu)化方法不僅減少了支持向量的數(shù)目,而且提高了GDTW-SVM運(yùn)行效率。
1 聯(lián)機(jī)手寫識(shí)別過程
1.1 聯(lián)機(jī)手寫識(shí)別流程介紹
聯(lián)機(jī)手寫識(shí)別的過程與通用模式識(shí)別的過程基本相同,由數(shù)據(jù)采集和預(yù)處理、特征提取、分類識(shí)別、后處理四個(gè)步驟組成。
在數(shù)據(jù)采集和預(yù)處理階段,首先使用傳感器采集原始物理信息,比較常見的是加速度、速度、位移、起筆和落筆;然后,對(duì)原始信息進(jìn)行傳感器矯正、去噪等預(yù)處理。
特征提取是手寫識(shí)別的重要步驟之一,對(duì)分類器的設(shè)計(jì)和分類結(jié)果有著重要的影響,選擇合適的特征不僅可以提高識(shí)別率,也可以節(jié)省計(jì)算存儲(chǔ)空間、運(yùn)算時(shí)間、特征提取費(fèi)用。聯(lián)機(jī)手寫識(shí)別中比較常見特征提取方法有加速度、位移、DCT變換等。
分類識(shí)別是手寫識(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”和小寫字母“1”在很多情況下難以分辨,但是在后處理階段結(jié)合上下文信息,決定當(dāng)前字符是數(shù)字“1”還是小寫字母“1”。
1.2 聯(lián)機(jī)手寫識(shí)別實(shí)驗(yàn)
本文聯(lián)機(jī)手寫識(shí)別實(shí)驗(yàn)采用了Bahlmann等人和Bothe等人使用的方法。所使用的樣本數(shù)據(jù)庫(kù)是免費(fèi)的聯(lián)機(jī)手寫數(shù)據(jù)庫(kù)UJIpenchars2。它采用Toshiba M400 Tablet PC收集,包含60個(gè)書寫者的共11640個(gè)手寫樣本。這些樣本包含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)過任何去噪等預(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ī)手寫識(shí)別實(shí)驗(yàn)假設(shè)每個(gè)字符不需要分析其上下文即可完成識(shí)別,所以,特征提取之后使用本文所述的分類算法進(jìn)行分類識(shí)別,并且將其輸出結(jié)果作為最終識(shí)別結(jié)果,不經(jīng)過任何后處理。
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(
式(2)中(w,b)確定分類超平面
SVM以最小化結(jié)構(gòu)風(fēng)險(xiǎn)為目標(biāo),計(jì)算使得訓(xùn)練樣本集到分類超平面的距離最大化的最優(yōu)分類超平面。其等價(jià)于對(duì)式(2)求解凸二次規(guī)劃問題。
即尋找使平均距離最小的最優(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ī)手寫識(shí)別實(shí)驗(yàn)的結(jié)果和Bothe等人的實(shí)驗(yàn)結(jié)果表明,GDTW-SVM取得了比GDTW-SVM和k近鄰算法(k-Nearest Neighbor,kNN)更高的識(shí)別率,而且在不同聯(lián)機(jī)手寫識(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í)別過程中需要反復(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)過此點(diǎn)。同理,繪制n-m最優(yōu)對(duì)齊路徑疊加圖和m-m最優(yōu)對(duì)齊路徑疊加圖,分別為圖2的第二和第三幅圖所示。
從圖2可以看到,兩個(gè)相同或相似字符的最優(yōu)對(duì)齊路徑集中在對(duì)角區(qū)域:由于n的不同樣本、m的不同樣本的起筆寫法比收筆寫法隨意,第一和第三幅圖的對(duì)角區(qū)域的左下角比較寬;n和m的最優(yōu)對(duì)齊路徑在對(duì)角區(qū)域中分布較均勻,且第二幅圖顯示對(duì)角區(qū)域的中部有明顯的低灰度區(qū)域。
假設(shè)訓(xùn)練樣本可以代表聯(lián)機(jī)手寫字符的特征,則可以通過僅計(jì)算對(duì)角區(qū)域中的最優(yōu)對(duì)齊路徑來優(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ù)字樣本集、英文小寫字母樣本集和英文大寫字母樣本集分開識(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ī)手寫識(shí)別的應(yīng)用和推廣。