雷海武 劉任任 劉新

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

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

中圖分類號：TP391.43

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

1 引 言

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

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

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

2 算法原理

2.1 DTW基本原理

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

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

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

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

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

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

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

2.2.1 算法路徑搜索方式

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

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

2.2.2 放寬起始端點的對齊限制

DTW算法的端點對齊如圖4所示。

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

2.2.3 匹配路徑約束范圍

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

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

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

2.2.4 算法描述

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

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

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

3 實驗設(shè)計

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

動態(tài)筆跡識別訓(xùn)練階段：

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

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

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

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

5）模板匹配，將待測筆跡的特征與真實手寫筆跡特征進行匹配，通過本文算法計算累積失真度。

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

4 實驗結(jié)果與分析

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

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

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

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

5 結(jié)束語

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

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

參考文獻(xiàn)

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

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

[3]許楠，基于神經(jīng)網(wǎng)絡(luò)的在線手寫簽名驗證方法研究[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]胡金平，陳若珠，李站明，語音識別中DTW改進算法的研究[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].山東理工大學(xué)學(xué)報：自然科學(xué)版.2013. 27（01）：63-66.

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

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

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

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

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

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

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

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