一種基于DTW的動態筆跡識別算法

雷海武 劉任任 劉新

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

關鍵字：動態筆跡;DTW;身份識別;信息安全

中圖分類號：TP391.43

文獻標志碼：A

1 引 言

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

動態筆跡識別是通過采集手寫者的筆跡，然后檢驗筆跡的真偽性，從而實現身份識別的一種技術。動態筆跡可以采集手寫者手寫時筆劃、筆順與時間的關系以及書寫速度和壓力等信息，比靜態筆跡的身份識別更加精確。

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

2 算法原理

2.1 DTW基本原理

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

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

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

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

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

本文的DTW算法是在DTW經典算法基礎上自定義了路徑搜索方式，放松了算法匹配路徑中起始端點對齊的限制，由于移動平臺系統中繪制事件會阻塞觸屏事件的采樣，在采集手寫筆跡信息的過程中會產生時間延遲，因此適當的放松起始端點的對齊可以提高筆跡識別的準確率。此外，本文算法為了保證識別效率，還結合了FastDTW算法中的限定搜索路徑彎曲斜率。

2.2本文算法實現原理

2.2.1 算法路徑搜索方式

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

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

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

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

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

2.2.3 匹配路徑約束范圍

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

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

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

2.2.4 算法描述

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

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

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

3 實驗設計

動態筆跡識別過程包括訓練階段和匹配階段，訓練階段包括手寫筆跡數據采集、筆跡信息預處理、筆跡特征提取和建立模板特征數據庫;匹配階段包括手寫筆跡數據采集、筆跡信息預處理、筆跡特征提取、模板匹配和結果判決。動態筆跡識別流程圖如下所示。

動態筆跡識別訓練階段：

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

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

3）特征提取，提取手寫筆跡中能體現出手寫者的書寫風格，同時又相對穩定的特征。本文提取的特征是動態筆跡的坐標值（x，y）和時間t。

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

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

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

4 實驗結果與分析

實驗選擇FRR（錯誤拒絕率）和FAR（錯誤接受率）作為評判算法性能的標準。

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

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

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

5 結束語

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

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

參考文獻

[1]欒方軍，程海，宋曉宇，基于HMM的在線手寫簽名認證系統設計與實現[J].計算機應用與軟件，2008，06：78-80.

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

[3]許楠，基于神經網絡的在線手寫簽名驗證方法研究[D].武漢理工大學，2006.

[4] 王容霞，基于SVM的在線手寫簽名認證研究[D].武漢理工大學，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].微型機與應用，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].山東理工大學學報：自然科學版.2013. 27（01）：63-66.

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

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

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

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

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

[19] 羅勇軍，基于優化DTW算法的在線手寫簽名認證系統研究與設計[D].廣州：廣東工業大學.2014.

[20]黃申文，在線手寫簽名認證技術的研究與應用[D].南京：南京航空航天大學.2010.

[21] 羅瓊，智能手機在線手寫簽名認證系統設計[D].武漢：武漢理工大學.2014.