一種基于DTW的動(dòng)態(tài)筆跡識(shí)別算法

雷海武 劉任任 劉新

摘要：隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，智能手機(jī)、平板電腦等移動(dòng)設(shè)備也得到了廣泛使用。移動(dòng)設(shè)備在網(wǎng)上購(gòu)物、在線支付、轉(zhuǎn)賬等方面具有方便、快捷的特性，網(wǎng)上電子商務(wù)交易量越來(lái)越大，導(dǎo)致移動(dòng)平臺(tái)上電子商務(wù)信息的安全隱患越發(fā)突出，信息安全技術(shù)在移動(dòng)平臺(tái)上的應(yīng)用越來(lái)越重要。基于生物特征的身份鑒別由于克服了傳統(tǒng)身份鑒別方式的很多缺陷而得到了廣泛的應(yīng)用。手寫筆跡是生物特征識(shí)別的重要領(lǐng)域之一，因具有采集設(shè)備簡(jiǎn)單、易采集、安全等優(yōu)點(diǎn)，被廣大用戶所接受。針對(duì)在移動(dòng)平臺(tái)上識(shí)別手寫筆跡的問(wèn)題，提出一種基于DTW的動(dòng)態(tài)筆跡識(shí)別算法。算法結(jié)合了FastDTW算法中限定路徑彎折斜率，保證了識(shí)別效率;并通過(guò)放松時(shí)間彎曲時(shí)對(duì)起始端點(diǎn)的對(duì)齊，提高了識(shí)別的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明，算法的錯(cuò)誤拒絕率（FRR）和錯(cuò)誤接納率（FAR）分別為4.5%和1.5%，識(shí)別效率和識(shí)別準(zhǔn)確率較于經(jīng)典DTW算法和FastDTW算法有所提高。

關(guān)鍵字：動(dòng)態(tài)筆跡;DTW;身份識(shí)別;信息安全

中圖分類號(hào)：TP391.43

文獻(xiàn)標(biāo)志碼：A

1 引 言

基于生物特征的身份識(shí)別技術(shù)是當(dāng)前信息安全技術(shù)領(lǐng)域的熱點(diǎn)。而生物特征的普遍性、唯一性、穩(wěn)定性和容易采集，使得生物特征應(yīng)用在人的身份識(shí)別上更加安全可靠。隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展以及智能手機(jī)等移動(dòng)設(shè)備廣泛普及，移動(dòng)平臺(tái)的安全性也成為了一個(gè)備受矚目的信息安全技術(shù)問(wèn)題。隨著移動(dòng)平臺(tái)上的網(wǎng)上支付手段、交易方式被廣大的用戶所接納，傳統(tǒng)的以用戶名密碼方式的身份識(shí)別方式存在著極大的風(fēng)險(xiǎn)，因此在移動(dòng)平臺(tái)設(shè)備上采用以生物特征識(shí)別身份的方式對(duì)于個(gè)人信息和財(cái)產(chǎn)的安全性具有重大的意義。

動(dòng)態(tài)筆跡識(shí)別是通過(guò)采集手寫者的筆跡，然后檢驗(yàn)筆跡的真?zhèn)涡裕瑥亩鴮?shí)現(xiàn)身份識(shí)別的一種技術(shù)。動(dòng)態(tài)筆跡可以采集手寫者手寫時(shí)筆劃、筆順與時(shí)間的關(guān)系以及書寫速度和壓力等信息，比靜態(tài)筆跡的身份識(shí)別更加精確。

在動(dòng)態(tài)筆跡識(shí)別方面，已有許多種成熟的算法，包括隱馬爾可夫（ Hidden Markov Models，HMM）[1]、動(dòng)態(tài)時(shí)間規(guī)整（Dynamic TimeWarping，DTW ）c2]、人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeural Network，ANN）[3]、支持向量機(jī)（SupportVector Machine，SVM）c4]等。其中HMM算法和DTW算法的應(yīng)用最為廣泛，但是由于DTW算法所需樣本少且簡(jiǎn)單有效，更適用于資源受限的移動(dòng)平臺(tái)上，因此DTW算法在這方面的應(yīng)用更為廣泛。20世紀(jì)60年代，日本學(xué)者Itakura將DTW算法運(yùn)用到語(yǔ)音識(shí)別后，DTW算法很快地被引入到了筆跡識(shí)別當(dāng)中。Wirtz[5]、Martens和Claesen[6]等人先后研究了DTW算法在筆跡識(shí)別中的應(yīng)用。隨著更深入的研究，很多研究者對(duì)DTW算法提出了各種改進(jìn)算法，并得到了更好的認(rèn)證效果。Hao Feng等提出采用規(guī)整特殊點(diǎn)的序列來(lái)代替DTW算法中對(duì)整個(gè)數(shù)據(jù)序列的規(guī)整，以提高規(guī)整的效率[7]。KarB提出了一種基于DTW的以筆段劃分的多階段匹配的方法[8]。胡金平等[9]通過(guò)限定彎折的斜率來(lái)減少計(jì)算量，從而提高效率。由于移動(dòng)設(shè)備的傳感器獲取數(shù)據(jù)時(shí)可能會(huì)出現(xiàn)時(shí)間延遲的原因，目前已有的各種方法應(yīng)用到移動(dòng)平臺(tái)上時(shí)，識(shí)別精度都會(huì)有所下降。因此，本文在結(jié)合了FastDTW算法中限定匹配路徑彎折斜率的原理，并在路徑搜索時(shí)自定義了一個(gè)路徑搜索方式，同時(shí)放松起始端點(diǎn)的對(duì)齊，減少了路徑匹配時(shí)的計(jì)算量以及占用的系統(tǒng)的空間，保證了識(shí)別效率和準(zhǔn)確率。

2 算法原理

2.1 DTW基本原理

如圖1中，定義一組時(shí)間序列相似性關(guān)系的連續(xù)元素集合，我們稱之為規(guī)整路徑W，這條路徑需滿足以下約束條件[10]：

1）邊界條件：由于一個(gè)人的手寫筆跡各部分的先后次序是不會(huì)改變的，因此所選的匹配路徑必定是從左下角出發(fā)，在右上角結(jié)束。

2）連續(xù)性：匹配路徑上某點(diǎn)只能和其相鄰的點(diǎn)進(jìn)行連接。這樣可以保證參考模板R和待匹配模板T中的每個(gè)坐標(biāo)都可能在時(shí)間規(guī)整函數(shù)上中出現(xiàn)。

3）單調(diào)性：彎曲路徑起始點(diǎn)（m，n）的下一個(gè)起始點(diǎn)必定是（ m+l，n）、（m，n+l）或（m+l，n+l）3個(gè)點(diǎn)中的一個(gè)，因此路徑是單調(diào)的。

設(shè)（m，n）為匹配路徑中的一點(diǎn)，則根據(jù)DTW匹配路徑規(guī)則，其下一個(gè)點(diǎn)為（ m+l，n）、（m，n+1）或（ m+l，n+l）中的一點(diǎn)，取點(diǎn)（m，n）到這3個(gè)點(diǎn)的距離最小的一點(diǎn)為下一個(gè)出發(fā)點(diǎn)，距離遞推公式如下，

本文的DTW算法是在DTW經(jīng)典算法基礎(chǔ)上自定義了路徑搜索方式，放松了算法匹配路徑中起始端點(diǎn)對(duì)齊的限制，由于移動(dòng)平臺(tái)系統(tǒng)中繪制事件會(huì)阻塞觸屏事件的采樣，在采集手寫筆跡信息的過(guò)程中會(huì)產(chǎn)生時(shí)間延遲，因此適當(dāng)?shù)姆潘善鹗级它c(diǎn)的對(duì)齊可以提高筆跡識(shí)別的準(zhǔn)確率。此外，本文算法為了保證識(shí)別效率，還結(jié)合了FastDTW算法中的限定搜索路徑彎曲斜率。

2.2本文算法實(shí)現(xiàn)原理

2.2.1 算法路徑搜索方式

本文針對(duì)DTW算法中的原始路徑搜索方式、傾向橫軸的搜索方式、傾向豎軸的搜索方式，提出了一種如圖2的路徑搜索方式。

這種路徑搜索方式始終保證路徑從左下角出發(fā)，右上角終止。由于避免了路徑向橫軸和豎軸傾斜，可以減少路徑匹配的計(jì)算量，從而提高了筆跡識(shí)別的效率。

2.2.2 放寬起始端點(diǎn)的對(duì)齊限制

DTW算法的端點(diǎn)對(duì)齊如圖4所示。

從圖3中可以看出模板T中端點(diǎn)a的最佳對(duì)齊點(diǎn)是模板R中的a。但由于移動(dòng)平臺(tái)系統(tǒng)采樣具有延遲性而且數(shù)據(jù)庫(kù)模板長(zhǎng)度和待匹配模板長(zhǎng)度大都不同，使得模板T中的端點(diǎn)a極大可能的匹配對(duì)齊到模板R中的端點(diǎn)b'。因此，適當(dāng)?shù)姆潘啥它c(diǎn)對(duì)齊限制，可以提高端點(diǎn)對(duì)齊的準(zhǔn)確率，從而提高識(shí)別精度。對(duì)起始端點(diǎn)的對(duì)齊放松了k個(gè)點(diǎn)，設(shè)定k的范圍為（2，5）。路徑匹配的起始端點(diǎn)范圍可以在橫軸或者豎軸（1，k）上。

2.2.3 匹配路徑約束范圍

本文算法結(jié)合了FastDTW算法中模板匹配限定匹配路徑的斜率（如圖4）的方式，并適當(dāng)放松了起始端點(diǎn)的對(duì)齊。參考FastDTW算法原理，本文匹配路徑斜率區(qū)間限定為[l/k，k]，k為起始端點(diǎn)放松的額度。如圖5所示。

匹配路徑的約束范圍為圖6中虛線所包含的區(qū)域。根據(jù)FastDTW算法中匹配路徑約束條件可知，虛線之外的格點(diǎn)的值是不需要計(jì)算的，這樣

通過(guò)給定的起始端點(diǎn)放寬額度，從而可以得到限定的匹配路徑斜率，進(jìn)而能夠獲取路徑匹配時(shí)的搜索范圍。在搜索邊界范圍內(nèi)找到最短路徑，得到兩個(gè)模板之間的失真度和閾值比較，從而判斷動(dòng)態(tài)筆跡的真實(shí)性。

2.2.4 算法描述

根據(jù)采樣獲得的筆跡信息包含了筆跡的坐標(biāo)（x，y）和時(shí)間（t）。本文選取樣本的全部采樣點(diǎn)進(jìn)行動(dòng)態(tài)時(shí)間規(guī)整。兩個(gè)筆跡采樣點(diǎn)間的距離公式定義如下：

Step 6根據(jù)式（3）計(jì)算模板的累積失真度。

Step 7 將計(jì)算出來(lái)的總體失真度與閾值S比較，如果小于閾值，則判定為真實(shí)筆跡;否則，判定為虛假筆跡。

3 實(shí)驗(yàn)設(shè)計(jì)

動(dòng)態(tài)筆跡識(shí)別過(guò)程包括訓(xùn)練階段和匹配階段，訓(xùn)練階段包括手寫筆跡數(shù)據(jù)采集、筆跡信息預(yù)處理、筆跡特征提取和建立模板特征數(shù)據(jù)庫(kù);匹配階段包括手寫筆跡數(shù)據(jù)采集、筆跡信息預(yù)處理、筆跡特征提取、模板匹配和結(jié)果判決。動(dòng)態(tài)筆跡識(shí)別流程圖如下所示。

動(dòng)態(tài)筆跡識(shí)別訓(xùn)練階段：

1）動(dòng)態(tài)筆跡數(shù)據(jù)采集，利用移動(dòng)設(shè)備上自帶的傳感器獲取手寫筆跡數(shù)據(jù)，建立動(dòng)態(tài)筆跡數(shù)據(jù)庫(kù)。由于條件限制，本文借用SVC 2004國(guó)際手寫筆跡識(shí)別競(jìng)賽的測(cè)試數(shù)據(jù)庫(kù)。由于該手寫筆跡數(shù)據(jù)庫(kù)包含中文和英文兩種手寫筆跡，并且此數(shù)據(jù)庫(kù)是在相同的標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)和規(guī)則下建立的，該數(shù)據(jù)庫(kù)對(duì)不同的筆跡識(shí)別算法的性能比較更具有說(shuō)服力，因此本文算法的實(shí)驗(yàn)驗(yàn)證將采用此數(shù)據(jù)庫(kù)。

2）預(yù)處理，對(duì)筆跡進(jìn)行旋轉(zhuǎn)、平滑處理、去噪以及大小和位置歸一化等，由于移動(dòng)平臺(tái)系統(tǒng)對(duì)觸屏事件的采樣率過(guò)低，因此還需對(duì)筆跡進(jìn)行重采樣。

3）特征提取，提取手寫筆跡中能體現(xiàn)出手寫者的書寫風(fēng)格，同時(shí)又相對(duì)穩(wěn)定的特征。本文提取的特征是動(dòng)態(tài)筆跡的坐標(biāo)值（x，y）和時(shí)間t。

4）模板特征數(shù)據(jù)庫(kù)建立，SVC 2004國(guó)際手寫筆跡識(shí)別競(jìng)賽的測(cè)試數(shù)據(jù)庫(kù)中包含100個(gè)人手寫筆跡數(shù)據(jù)，其中每個(gè)人的包含20個(gè)真實(shí)手寫筆跡和20個(gè)熟練偽造筆跡。每個(gè)手寫筆跡的文本數(shù)據(jù)首行表示筆跡序列的長(zhǎng)度，然后采集并記錄各個(gè)采樣點(diǎn)的信息，包括橫坐標(biāo)、縱坐標(biāo)和采樣點(diǎn)對(duì)應(yīng)的時(shí)間t等。

5）模板匹配，將待測(cè)筆跡的特征與真實(shí)手寫筆跡特征進(jìn)行匹配，通過(guò)本文算法計(jì)算累積失真度。

6）結(jié)果判決，將計(jì)算出的總失真度與閾值計(jì)較來(lái)判斷筆跡的真實(shí)性。閾值通過(guò)實(shí)驗(yàn)數(shù)據(jù)來(lái)確定。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)選擇FRR（錯(cuò)誤拒絕率）和FAR（錯(cuò)誤接受率）作為評(píng)判算法性能的標(biāo)準(zhǔn)。

在實(shí)驗(yàn)中，由于起始端點(diǎn)放松額度k是可變的，因此實(shí)驗(yàn)應(yīng)先確定k的取值。圖7所示為k取不同值時(shí)，F(xiàn)RR和FAR的變化曲線。從圖7中可以看出，當(dāng)k>5時(shí)，曲線處于穩(wěn)定狀態(tài)，算法的識(shí)別精度趨于穩(wěn)定。而從放寬起始端點(diǎn)對(duì)齊限制的原理可知，放松額度k的值越大，則表示算法路徑搜索的范圍越大，從而使得算法的計(jì)算量越大。因此，本文算法中k的值選取為因此，本文算法中k的值選取為（2，5）。

本文實(shí)驗(yàn)主要將本文算法與經(jīng)典DTW算法和FastDTW算法進(jìn)行測(cè)試比較，三種算法的識(shí)別效果比較如表1所示。

通過(guò)實(shí)驗(yàn)數(shù)據(jù)可知，本文算法的FRR和FAR分別為6.33%和4.13%，比經(jīng)典DTW算法要高，但是在效率上經(jīng)典DTW算法;而比FastDTW算法的實(shí)驗(yàn)結(jié)果要低，且效率上相差不大，證明了本文算法的合理性和可行性。

5 結(jié)束語(yǔ)

針對(duì)在移動(dòng)平臺(tái)上識(shí)別手寫筆跡的問(wèn)題，提出一種基于DTW的動(dòng)態(tài)筆跡識(shí)別算法。算法通過(guò)放松筆跡模板匹配時(shí)的起始端點(diǎn)對(duì)齊限制，提高了識(shí)別準(zhǔn)確率;并通過(guò)約束路徑搜索方式和限定匹配路徑斜率提高了識(shí)別效率。

算法在實(shí)際應(yīng)用過(guò)程中還存在一些局限性。本文動(dòng)態(tài)筆跡識(shí)別時(shí)閾值對(duì)FRR和FAR有一定的影響;算法對(duì)于跨設(shè)備采集的信息識(shí)別還不能達(dá)到要求。未來(lái)將繼續(xù)針對(duì)這幾個(gè)方面進(jìn)行研究。

參考文獻(xiàn)

[1]欒方軍，程海，宋曉宇，基于HMM的在線手寫簽名認(rèn)證系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2008，06：78-80.

[2] 王珂敏，基于DTW改進(jìn)算法的在線簽名鑒別方法[J].科技導(dǎo)報(bào)，2010，28（13）：101-104.

[3]許楠，基于神經(jīng)網(wǎng)絡(luò)的在線手寫簽名驗(yàn)證方法研究[D].武漢理工大學(xué)，2006.

[4] 王容霞，基于SVM的在線手寫簽名認(rèn)證研究[D].武漢理工大學(xué)，2013.

[5] WIRTZ B.Stroke-based time warping for signature verifica-tion[C]// International Conference on Document Analysisand Recognition. IEEE，1995：179 -182.

[6]MARTENS R，CLAESEN L.Incorporating local consistencyinformation into the online signature verification process[J].Journal of Bacteriology，2007，189（ 24）：9076 - 81.

[7]HAO F，CHAN C W. Online signature verification using anew extreme points warping technique[J]. Physics LettersB，1995，355（s1-2）：27-31..

[8] KAR B，DUTTA P K，BASU T K，et al.DTW Based Verifi-cation Scheme of Biometric Signatures[C]// IEEE Interna-tional Conference on Industrial Technology. 2007：381- 386.

[9]胡金平，陳若珠，李站明，語(yǔ)音識(shí)別中DTW改進(jìn)算法的研究[J].微型機(jī)與應(yīng)用，2011，30（3）：30-32.

[10]KEOGH E J，PAZZANI M J.Derivative Dynamic TimeWarping[C]，'/ SIAM International Conference ，2002.

[11]SHIN J. OKUYAMA T. Detection of alcohol intoxicationvia online handwritten signature verification[J]. PatternRecognition Letters，2014 ，35（ 35）：101 -104.

[12]BHATTACHARYA I，GHOSH P，BISWAS S. Offline Sig-nature Verification Using Pixel Matching Technique[J].Procedia Technology，2013 ，10（1）：970 - 977.

[13]劉靜，王儒.曲金玉.等，基于DTW改進(jìn)算法的孤立詞語(yǔ)音識(shí)別仿真[J].山東理工大學(xué)學(xué)報(bào)：自然科學(xué)版.2013. 27（01）：63-66.

[14]徐貴力.趙妍，姜斌.等，基于局部尺度特征描述和改進(jìn)DTW技術(shù)的局部輪廓匹配算法[J].電子學(xué)報(bào).2016. 44（01）：135-142.

[15]李成華.龔良慧.江小平.等，基于EMD和SVD的在線手寫簽名特征提取方法[J].中南民族大學(xué)學(xué)報(bào)：自然科學(xué)版.2016，35（01）：103-107+113.

[16] 申麗敏，語(yǔ)音翻譯信號(hào)數(shù)字模型的構(gòu)建及DTW算法的改進(jìn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用.2015，18（02）：70-72.

[17]王劍.馬書月，基于幾何中心靜態(tài)手寫簽名的識(shí)別算法研究[J].計(jì)算機(jī)應(yīng)用研究.2012，29（03）：1149 1151.

[18] 艾茜，基于速度和壓力分區(qū)的在線手寫簽名驗(yàn)證[D].武漢：武漢理工大學(xué).2012.

[19] 羅勇軍，基于優(yōu)化DTW算法的在線手寫簽名認(rèn)證系統(tǒng)研究與設(shè)計(jì)[D].廣州：廣東工業(yè)大學(xué).2014.

[20]黃申文，在線手寫簽名認(rèn)證技術(shù)的研究與應(yīng)用[D].南京：南京航空航天大學(xué).2010.

[21] 羅瓊，智能手機(jī)在線手寫簽名認(rèn)證系統(tǒng)設(shè)計(jì)[D].武漢：武漢理工大學(xué).2014.