基于離散F距的在線手寫簽名認(rèn)證算法

1、基于離散F距的在線手寫簽名認(rèn)證算法    摘  要  提出了一種新的在線手寫簽名認(rèn)證算法。該算法將參考簽名和測試簽名曲線中特殊點(diǎn)的位置坐標(biāo)分別提取出來，求出其離散F距，再進(jìn)行判決。在算法中引入了簽名曲線中特殊點(diǎn)的平移和刪除等技術(shù)，使得匹配效果增強(qiáng)。     關(guān)鍵詞  簽名認(rèn)證；離散F距；判決  1  引言    隨著網(wǎng)絡(luò)的普及，安全問題越來越突出。如何準(zhǔn)確地鑒定一個人的身份，保護(hù)信息安全是當(dāng)今信息化時(shí)代必須解決的一個關(guān)鍵問題。目前，指紋識別、語音

2、識別和簽名識別在信息安全領(lǐng)域應(yīng)用的較為廣泛。而手寫簽名認(rèn)證技術(shù)與其它身份認(rèn)證技術(shù)相比具有明顯的優(yōu)點(diǎn)：與指紋、語音等其它生物學(xué)特征識別相比成本較低，并且不需要專門而且復(fù)雜的采樣設(shè)備。與傳統(tǒng)的密碼、口令識別技術(shù)相比較，又不會丟失遺忘。因此，簽名認(rèn)證技術(shù)將會在信息安全領(lǐng)域有著廣闊的前景。     從20世紀(jì)80年代起，有很多學(xué)者都致力于研究簽名認(rèn)證的算法。隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，簽名認(rèn)證的算法主要有特征值法和函數(shù)法兩大類。比較有代表性的有：Mohankrishnan和Paulik提出了一個基于自回歸(Autoregressive)模型的簽名認(rèn)證方法2。而Yang和Wi

3、djaja提出了隱馬爾可夫模型(Hidden Markov Model)法3。20世紀(jì)90年代后期，一些研究者以簽名波形跳變點(diǎn)的能量5為特征，將動態(tài)時(shí)間規(guī)整方法應(yīng)用于簽名的匹配。最近武漢理工大學(xué)的鄭建彬教授提出了一種基于演化計(jì)算的簽名認(rèn)證算法4，該算法將參考簽名分割成曲線段，以一定長度的搜索窗在測試簽名曲線上進(jìn)行動態(tài)搜索，實(shí)現(xiàn)與參考簽名曲線段自適應(yīng)的動態(tài)分割與匹配。     由于簽名的特征的多樣性，在簽名中取何種特征，至今還沒有定論。而對于函數(shù)法，由于每個人的簽名都有很大的隨意性，且將簽名用函數(shù)表示十分復(fù)雜。因此，目前很難提出一個較好地評判簽名相似度的準(zhǔn)則，從而給

4、比較測試簽名和參考簽名相似度帶來很大困難。本文給出了一種新的關(guān)于曲線相似性的定義，并且利用了離散F距1(Discrete Fr´echet Distance)作為距離的測度，提出了一種新的在線手寫簽名認(rèn)證算法。該算法以簽名曲線的離散F距作為評判準(zhǔn)則來比較測試簽名和參考簽名的相似程度，建立數(shù)學(xué)模型，利用了簽名曲線中特殊點(diǎn)的平移和刪除等技術(shù)，提高了算法的效率，收到了較好的效果。 2  基于離散F距的簽名認(rèn)證算法     離散F距的數(shù)學(xué)定義如下：     定義1：給定兩參數(shù)曲線f:0,1R2和g:0,1R2，它們之間的F

5、rechet距離的定義如下： 其中，涉及到所有連續(xù)非減的實(shí)函數(shù)且(0)=(0)=0 ，(1)=(1)=1  。     定義2：給定一個有n個至高點(diǎn)的多邊形鏈p<p1,p2,.pn>，一個沿著p的k步，分割p的至高點(diǎn)成為k個不相交的非空子集，使得和。     給定兩個多邊形鏈，一個沿著A和B的組合步是一個沿著A的k步和一個沿著B的k步組成，使得對于，要么，要么 (就是說Ai，Bi中有一個恰好包含一個至高點(diǎn))。     一個沿著鏈A和B的組合步W=(Ai,Bi)的花費(fèi)(cost)就是

6、則鏈A和B間的離散F距就是 這個組合步W=(Ai,Bi)稱為鏈A和B的Frechet排列。 3  算法的設(shè)計(jì)與實(shí)現(xiàn)    在線簽名認(rèn)證系統(tǒng)分為硬件采集數(shù)據(jù)和軟件驗(yàn)證兩個部分。硬件部分是通過手寫板實(shí)時(shí)采集書寫人的簽名信息，簽名的采樣時(shí)間為每隔10ms采樣一次。除了可以采集簽名位置信息，還可以記錄書寫時(shí)的速度、運(yùn)筆壓力等動態(tài)信息。通常情況下我們使用的比較多的是手寫板上采集到的X坐標(biāo)、Y坐標(biāo)、壓力值等信息。圖1是某人的簽名和其對應(yīng)的X坐標(biāo)曲線。 圖1 參考簽名和測試簽名X軸坐標(biāo)對應(yīng)曲線     假設(shè)參考簽名提取出的特殊點(diǎn)(這里以波

7、峰點(diǎn)為例)有 個，記 ；測試簽名提取出的波峰點(diǎn)有 個，記為 ；且 。以峰值點(diǎn)少的集合 為基準(zhǔn)，利用Frechet排列的定義將峰值點(diǎn)多的集合 分成 部分，而這種劃分假設(shè)有 種( )，則集合 和 的 種Frechet排列 。由于對于 ，要么 ，要么 (也就是說 ， 中有一個恰好包含一個峰值點(diǎn))，且若 ， ，則 ， 。即是上一步的劃分會直接影響到下一步的劃分。 3.1  搜索空間的確定    在判斷相似性的時(shí)候，如果兩條曲線是相似的話，那么其中參考簽名曲線的第 個峰值點(diǎn)只可能與測試簽名的對應(yīng)的第 個峰值點(diǎn)或其相鄰的峰值點(diǎn)相關(guān)，故在簽名認(rèn)證算法中設(shè)定的搜索空間是

8、參考簽名曲線的第 個峰值點(diǎn)只可能與測試簽名曲線的對應(yīng)的第0個峰值點(diǎn)(參考簽名的第 個峰值點(diǎn)可能為多余的峰值點(diǎn))、第 個峰值點(diǎn)、第 個峰值點(diǎn)、第 個峰值點(diǎn)對應(yīng)匹配。這種方法實(shí)際上是利用了特殊點(diǎn)的平移和刪除技術(shù)，壓縮后的搜索空間如下：     在A和B的k種Frechet排列中對于任意一種 3.2  基于離散F距的判別簽名曲線相似性的算法：    離散F距用于簽名認(rèn)證的算法如下：     (1)假設(shè)參考簽名提取出的特殊點(diǎn)(這里以波峰點(diǎn)為例)有 個，記 ；測試簽名提取出的波峰點(diǎn)有m個，記為，且mn。若

9、n-m>5，則認(rèn)為參考簽名和測試簽名不相似，算法結(jié)束；否則執(zhí)行下一步。     (2)以參考簽名提取的峰值點(diǎn)序列A 為基準(zhǔn)，其共有 m個波峰點(diǎn)；然后將集合B 的n 個峰值點(diǎn)分為m 部分，根據(jù)搜索空間的范圍，然后找出所有滿足條件的劃分，假設(shè)有k 種劃分情況( kR)，在每一種劃分(或Frechet排列) 中， 集合B的每一部分均與集合A的每一個峰值點(diǎn)對應(yīng)求距離。這里的峰值點(diǎn)之間的距離定義為 ，兩個簽名的每一部分的特殊點(diǎn)將各自對應(yīng)進(jìn)行匹配，選擇出每一部分內(nèi)部的所有對應(yīng)點(diǎn)之間的最大距離。根據(jù)組合步的數(shù)學(xué)定義，求出每一種劃分方法中的 部分距離的最大值，即  

10、;   (3)找出所有劃分方法中的距離的最小值，選擇出一種最佳的劃分方法(即是求出最小的距離)。     (4)用此種劃分對波峰和波谷分別進(jìn)行研究，得出兩個波峰間的最小距離和兩個波谷間的最小距離；對于給定的閾值，則判定兩條曲線相似，否則判定兩條曲線不相似。如果越小，表示參與匹配的參考簽名與測試簽名的距離越小，即它們的相似度越高。     基于離散F距算法的流程圖如圖2所示。 圖2  基于離散F距算法的流程圖     同時(shí)根據(jù)以上算法求出參考簽名和測試簽名的波谷點(diǎn)的離散F距和判

11、決門限比較，若，則可以判定測試簽名和參考簽名匹配。 4  實(shí)驗(yàn)結(jié)果分析    為了初步判別出不同人的簽名，需要對參考簽名和測試簽名進(jìn)行特殊點(diǎn)的歸一化。在初步匹配階段，需要將提取出的特殊點(diǎn)的集合以第一個特殊點(diǎn)為基準(zhǔn)進(jìn)行位置歸一化，使兩條簽名曲線的第一個特殊點(diǎn)的位置坐標(biāo)重合。在匹配過程中設(shè)置當(dāng)波峰點(diǎn)的最優(yōu)值和波谷點(diǎn)的最優(yōu)值均大于門限E時(shí)，則判定兩個簽名不匹配。 圖3  某人的兩次簽名歸一化前和歸一化后的峰值點(diǎn)的曲線 (兩個簽名均有17個峰值點(diǎn))     通過對同一個人的真實(shí)簽名、不同人的簽名、隨機(jī)偽造簽名和熟練偽造簽名

12、做實(shí)驗(yàn)對比，可以初步設(shè)置判決門限 =150，E=900。     如果，表示參考簽名和測試簽名匹配。     表1選取的是簽名樣本庫中的同一個人的若干次簽名，在全局范圍內(nèi)求出他們的的最優(yōu)值dmin，并與匹配門限比較，判斷是否匹配。表1  某人10個真實(shí)簽名的X坐標(biāo)曲線的匹配情況   zeq01.h zeq02.h zeq03.h zeq04.h zeq05.h zeq01.h 0         zeq02.h 2 0       zeq03.h

13、 265 29 0     zeq04.h 71 88 168 0   zeq05.h 174 114 356 103 0 zeq06.h 6 8 95 89 121 zeq07.h 28 18 33 215 65 zeq08.h 30 70 83 71 71 zeq09.h 50 74 74 96 100 zeq10.h 120 67 64 88 60     從表1中可以看到，某人的真實(shí)簽名的認(rèn)證率達(dá)到了85.71%。在真實(shí)簽名樣本庫中，對真實(shí)簽名的認(rèn)證率達(dá)到了88%。在熟練偽造簽名樣本庫中，對于熟練偽造簽名的驗(yàn)證率達(dá)到了80%。

14、在隨機(jī)偽造簽名樣本庫中，對于某人的隨機(jī)偽造簽名的驗(yàn)證率達(dá)到了88%。比較離散F距和演化計(jì)算這兩種方法，它們對偽造簽名都有著較高的驗(yàn)證率。相比之下，基于離散F距的算法在計(jì)算機(jī)中運(yùn)行的效率比演化計(jì)算要高，而且其時(shí)間復(fù)雜度比演化計(jì)算要低。     在以前的研究中，有些研究者將演化計(jì)算的思想用于在線手寫簽名認(rèn)證中，通過實(shí)驗(yàn)得到了比較理想的結(jié)果，誤拒率和誤納率均可以控制在10%以下，但是其時(shí)間復(fù)雜度比較高。同時(shí)在保證有著較高的驗(yàn)證率的前提下，離散F距相對于演化計(jì)算和連續(xù)F距有著較低的時(shí)間復(fù)雜度，并且提高了整個簽名認(rèn)證系統(tǒng)的運(yùn)行效率，有效地減少了系統(tǒng)運(yùn)行的時(shí)間。 5 

15、0;結(jié)語    本文將離散F距應(yīng)用到在線手寫簽名認(rèn)證中，提出了一種新的判別簽名相似度的準(zhǔn)則，并對整個算法進(jìn)行了初步的研究。由實(shí)驗(yàn)分析，離散F距算法應(yīng)用到簽名認(rèn)證中，加快了簽名的驗(yàn)證速度，使簽名認(rèn)證算法的運(yùn)算結(jié)果有了較大提高，實(shí)驗(yàn)結(jié)果證明了該方法的可行性。利用離散F距的思想，只考慮簽名曲線中特殊點(diǎn)的坐標(biāo)特征，因此這種方法相對于神經(jīng)網(wǎng)絡(luò)和演化計(jì)算等方法，它的時(shí)間復(fù)雜度要低的多。     但是該方法還有一些問題需要解決。例如目前的算法在特殊點(diǎn)序列的匹配過程中，對于中間的部分冗余的特殊點(diǎn)沒有刪除，導(dǎo)致在某些情況下搜索到的全局范圍內(nèi)的最優(yōu)值與實(shí)

16、際情況下的最優(yōu)值產(chǎn)生了一定的誤差，因此還需要對算法進(jìn)一步改進(jìn)和完善；同時(shí)對于簽名曲線中特殊點(diǎn)的其它特征如壓力、握筆傾斜度、局部加速度等并未深入考慮。 參考文獻(xiàn)1Minghui Jiang，Ying Xu，Binhai ZhuProtein Structure-Structure Alignment with Discrete Fr´echet DistanceJuly 9，2007：p 1-12 2Mohankrishnan N， Paulik M J， and Khalil M. On-line signature verification using a nonstationar

17、y autoregresssive model representation. IEEE Int. Sym. On Circuits and Systems，1993，2：p 2303-2306. 3L. Yang，B.R. Widjaja，R. PrasadApplication of Hidden Markov Model for Signature VerificationPattern Recognition，1996，28(2)：p 180-188 4Zheng Jianbin，Zhu GuangxiNew algorithm for on-line handwriting sign

18、ature verification based on evolutionary computationWuhan University Journal of Natural Sciences，v 11，n 3， May， 2006：p 596-600 5Zheng Jianbin，Zhu GuangxiOn-line handwriting signature recognition based on wavelet energy feature matchingProceedings of the World Congress on Intelligent Control and Automa