劉 莉,詹恩奇,鄭建彬,汪 陽

(1.武漢理工大學 信息工程學院,武漢 430070; 2.光纖傳感技術與信息處理教育部重點實驗室(武漢理工大學),武漢 430070)(*通信作者電子郵箱powerflow@whut.edu.cn)

0 引言

手寫簽名是生物特征的一種,它是一種復雜的物理行為。在社會活動中,手寫簽名的認證在金融交易、銀行提款、合同簽署、國家安全以及法律執(zhí)行等方面廣泛使用。手寫簽名的動態(tài)信息處理和分析不同人的簽名信息之間的差異性仍然是現(xiàn)在研究的熱門問題。

傳統(tǒng)的手寫簽名認證方法主要包括特征提取、匹配和認證三個部分。手寫簽名的特征提取可以分為函數(shù)特征提取和參數(shù)特征提取。其中函數(shù)特征包括位置、速度、加速度、壓力、移動方向以及筆的傾斜角度等信息,參數(shù)特征包括總的簽名時間特征、下筆時間比特征、提筆次數(shù)特征、方向統(tǒng)計特征、曲率特征等。

匹配和認證的技術包括動態(tài)時間規(guī)劃(Dynamic Time Wraping, DTW)[1-4]、支持向量機(Support Vector Machine, SVM)[5]、隱馬爾可夫模型(Hidden Markov Model, HMM)[6-7]和神經(jīng)網(wǎng)絡[8]等。此外離散小波變換(Discrete Wavelet Transform, DWT)[9]和離散余弦變換(Discrete Cosine Transform, DCT)[10]的特征匹配也應用到了認證中。還有一些融合的方法,比如文獻[11]中使用了SVM和最長公共子序列(Longest Common SubSequence, LCSS)相結合的方法。如圖1所示,在傳統(tǒng)的曲線比較方法中,主要是對簽名離散的點集進行DTW,當遇到曲線的旋轉、縮放或者采樣不均勻的問題時,此方法得到的曲線相似距離不符合實際情況。由于同一個人的簽名曲線的走勢總是相似的,本文基于這一點,提出了一種曲線相似度的度量方法。它將離散的點集以曲線的形式描述,然后對其相似變換和曲線采樣,并計算其相似距離。通過這種方式可以得到較準確的匹配距離。

圖1 曲線相似度比較方法對比

此外,本文改進了一種計算窗口累計差異的動態(tài)規(guī)劃匹配算法,在本文算法中加入了合并規(guī)則,并在匹配的優(yōu)化過程中加入跳躍規(guī)則。這種方法不僅可以達到匹配的全局最優(yōu),刪除多余的段,還能夠避免文獻[12]中出現(xiàn)的閾值選取困難的問題。從實驗結果可以看出,本文算法可以達到較好的匹配效果。

1 基于曲線擬合的曲線相似度判定

為了解決相似曲線由于平移、縮放以及旋轉所產(chǎn)生的匹配距離過大問題,本文方法在對曲線進行比較之前,需要對其進行相似變換以減少誤差。實際應用中,簽名曲線存在很多突變的拐點,所以要先對其進行分段,然后再進行曲線相似度的比較。實驗選取高階貝塞爾曲線[13]對離散點集進行了擬合,利用貝塞爾曲線的性質(zhì)對曲線進行相似變換。本文首先給出了曲線相似度度量的一種方法。

1.1 曲線的相似變換理論研究

在幾何數(shù)學中,對多邊形的相似有明確的定義,曲線相似和多邊形相似不同,沒有明確的定義,目前廣泛認為一條曲線經(jīng)過平移、旋轉、位似變換得到的曲線與原曲線成相似關系,比如所有的圓、所有的拋物線、離心率相等的橢圓以及離心率相等的雙曲線構成的曲線滿足曲線相似的關系。本文給出了一種曲線相似的定義,它在本文的曲線相似度比較實驗中,起到了關鍵的作用。

1.2 基于曲線擬合的曲線相似度判定

在實際的工程應用中,使用曲線的模糊相似度[15]。計算兩曲線的相似距離的原則是保證在相同的條件下比較,不受平移、旋轉、縮放等因素的影響,因此給出以下定義。

定義2 對兩二維離散曲線S1={(x1,y1),(x2,y2),…,(xn,yn)}和S2={(x1′,y1′),(x2′,y2′),…,(xm′,ym′)}分別進行高階貝塞爾曲線的擬合,然后對曲線S1進行類曲率不變型相似變換Tα、θ、 β得到新的曲線，對其進行重采樣，并計算它和曲線S2的相似距離。相似距離計算方法如式(1)所示:

dsim=dmean=

其中：α、θ、β分別為平移、旋轉、縮放因子；N0表示重采樣的點數(shù),可采用對點數(shù)較少的曲線進行參數(shù)插值后再計算匹配距離。給定閾值μthresh,若dmean<μthresh則判定兩曲線相似,否則為不相似。曲線相似度的比較不僅對原簽名圖像適用,同樣也用于x軌跡和y軌跡的曲線相似度比較,可以依據(jù)實際情況,選取更加穩(wěn)定的曲線信息進行分析,這樣更有利于認證。

2 簽名曲線分段相似匹配算法

2.1 算法流程

基于簽名曲線分段擬合相似匹配算法,主要包括曲線分段、粗匹配、段內(nèi)曲線相似度計算三個部分。具體過程如下:

步驟1 曲線分段。根據(jù)視覺關鍵點對簽名曲線進行分段[16]。首先選取點數(shù)密集區(qū)域作為候選區(qū)域,然后對區(qū)域內(nèi)的所有點計算頂點域,并計算其對應的曲率,最后取曲率的局部極大值作為分段點,同時刪除孤立的采樣點。

步驟2 粗匹配。粗匹配的目的是找到匹配段對應關系,過程中會出現(xiàn)一段對多段和多段對多段的情況,本文引入一種合并和跳躍規(guī)則。為了確保粗匹配的全局最優(yōu),本文改進了一種計算累計差異矩陣的動態(tài)規(guī)劃算法,算法內(nèi)容見2.2節(jié)和2.3節(jié)。

步驟3 曲線相似度計算。計算曲線的相似度是對粗匹配距離優(yōu)化的過程,它的目的是為了減小曲線相似度比較過程中由于曲線的旋轉、縮放、位移以及采樣不均勻等造成的誤差。在一定的范圍內(nèi),對曲線相似距離進行優(yōu)化,對簽名認證是有利的。

2.2 分段粗匹配

首先根據(jù)視覺關鍵點對簽名曲線進行分段,圖2展示了分段后的效果。

圖2 分段效果

粗匹配的主要思想是通過動態(tài)規(guī)劃的思想尋找最優(yōu)匹配路徑。在這個過程中,累計差異矩陣D的構建非常關鍵。由于簽名曲線的分段情況有所差異,模板簽名和測試簽名曲線可能會出現(xiàn)多段對一段、一段對多段或者多段對多段的情況,所以在進行匹配策略的選擇的原則是盡可能考慮到所有的情況。通過對數(shù)據(jù)庫中分段簽名曲線比對發(fā)現(xiàn),計算當前的累計差異值Di, j時存在8種段與段的匹配規(guī)則,可通過計算和比較這8種匹配規(guī)則下各自的累計差異值,再選取最小差異值保留下來并作為當前段的匹配結果,如式(2)所示:

Di, j=min(Di-1, j-1+di, j,Di-2, j-1+dmer(i-1,i), j,

Di-1, j-2+di,mer(j-1, j),Di-3, j-1+dmer(i-2,i), j,

Di-1, j-3+di,mer(j-2, j),Di-2, j-2+dmer(i-1,i),mer(j-1, j),

Di-3, j-2+dmer(i-2,i),mer(j-1, j),

Di-2, j-3+dmer(i-1,i),mer(j-2, j));

|i-j|

(2)

其中:Di, j表示到當前段的累計差異值;w是搜索窗口,它對匹配的范圍進行了限制,可根據(jù)實際需要選取;M和N表示分別表示兩簽名的分段數(shù);di, j表示模板簽名第i段和測試簽名第j段的差異距離;dmer(i-1,i), j表示第i-1段到第i段合并段與第j段的差異距離。

這些匹配規(guī)則的主要是通過加入不同的合并規(guī)則來實現(xiàn)的。

為了實現(xiàn)段間匹配的效率和準確度,首先選取描述筆段走勢信息的幾個采樣點來參與匹配,從而確定筆段的對應關系,如式(3)所示:

(3)

(4)

圖3以2∶1的合并規(guī)則和1∶2的合并規(guī)則為例進行說明。圖3(a)中,計算當前累計差異值Di, j時,通過計算比較發(fā)現(xiàn)將模板簽名的第i-1段和第i段合并后與測試簽名的第j段匹配時的Di, j可達到最小,則保留這個最小值并記下段的對應關系。同理,可以得到如圖3(b)所示的匹配結果。

圖3 段合并示意圖

2.3 粗匹配優(yōu)化

同一個人的簽名仍存在一些多余曲線段,這些筆段參與到了粗匹配的過程中,為了去除這些多余曲線段,需要制定優(yōu)化策略對已有的匹配段進行優(yōu)化。針對前面8種匹配規(guī)則,本文主要制定了以下策略用于剔除多余段,如式(5)所示:

dmer(i-k1,i),mer(j-k2, j)=min(dmer(i-k1,i),mer(j-k2, j),

dmer(i-k1,i)skip(i-0),mer(j-k2, j),dmer(i-k1,i)skip(i-1),mer(j-k2, j),…,dmer(i-k1,i)skip(i-k1),mer(j-k2, j),dmer(i-k1,i),mer(j-k2, j)skip(j-0),dmer(i-k1,i),mer(j-k2, j)skip(j-1),…,dmer(i-k1,i),mer(j-k2, j)skip(j-k2));

0≤k1<3,0≤k2<3

(5)

其中:dmer(i-k1,i)skip(i-x),mer(j-k2, j)表示將模板簽名曲線段i-x剔除后剩余曲線段的匹配差異距離;skip(i-x)表示曲線段i-x作為多余的曲線筆畫段進行剔除。同理,dmer(i-k1,i),mer(j-k2, j)skip(j-y)表示將測試簽名曲線段j-y剔除后剩余曲線段的匹配差異距離。這些優(yōu)化策略是通過加入不同的跳躍規(guī)則實現(xiàn)的。

圖4對優(yōu)化中的跳躍規(guī)則的進行了說明。通過粗匹配得到累計差異矩陣D之后,尋找匹配路徑,得到匹配對合并段mer(i-1,i)和曲線段j,通過比較發(fā)現(xiàn)di, j

圖4 段跳躍示意圖

粗匹配的過程總結如下:

1)從起始段開始,在搜索窗口內(nèi)使用2.2節(jié)的方法計算累計差異值Di, j,構造累計差異矩陣。

2)從累計差異矩陣元素DM,N開始回溯,記錄匹配路徑和匹配對的差異距離。

3)對得到匹配對進行遍歷,如果為一對一的匹配對關系則保留,如果是多對一、一對多或者多對多的關系,則執(zhí)行粗匹配的優(yōu)化方法,保留差異距離最小的匹配關系,并更新差異距離。

圖5分別展示了二維圖像的匹配結果示例和x軌跡曲線的匹配結果示例。從圖5可以看出,該方法可以實現(xiàn)多對多的匹配,可以將多余的段去掉,能夠得到較準確的匹配結果。

圖5 粗匹配效果

2.4 曲線相似度計算

在2.2節(jié)和2.3節(jié)中已經(jīng)得到的曲線段間的對應關系,為了更加精確地計算這些對應曲線段的相似度,在一定范圍內(nèi)對曲線段進行相似變換,使得計算曲線相似度時可以不受縮放、旋轉、平移等的影響,然后將變換后的曲線進行重采樣并計算其相似度。主要步驟如下:

步驟1 假設模板曲線的初始化采樣點數(shù)為δ,先對兩條曲線進行擬合,可以使用最小二乘法,如式(6)所示：

dfit=min(‖TC-P‖)

(6)

其中：T表示通過時間的歸一化后采樣點的時間信息所構成的矩陣；C表示擬合曲線的控制點坐標構成的矩陣,可參考文獻[13]；P表示采樣點的坐標矩陣。擬合后的模板曲線為Ctemplate(a1,a2,a3,a4),測試曲線為Ctest(b1,b2,b3,b4),ai和bi表示擬合曲線的控制點坐標矢量。

步驟2 計算兩曲線的旋轉系數(shù)θ=angle(b4-b1,a4-a1),以及縮放系數(shù)β=‖b4-b1‖/‖a4-a1‖,如果滿足約束條件θ∈[θT1,θT2],且β∈[βT1,βT2],則執(zhí)行步驟3;如果不滿足約束條件,則將測試曲線Ctest(b1,b2,b3,b4)進行重采樣,計算相似距離并返回。約束條件由實驗的數(shù)據(jù)決定,取決于真實簽名曲線的穩(wěn)定性以及簽名是否存在旋轉、縮放等因素。

步驟3 對測試簽名進行相似變換,相似變換的公式如式(7)所示：

(7)

其中:

β=‖b4-b1‖/‖a4-a1‖

θ=angle(b4-b1,a4-a1)

在實驗過程中,可以通過對控制點構成的多邊形進行相似變換來實現(xiàn)曲線的相似變換,如圖6所示。在得到相似變換的測試曲線C"test(c1,c2,c3,c4)后,對測試簽名曲線段進行重采樣,計算兩對應的曲線段的相似距離并返回,計算公式如式(1)所示。實驗中可以使用方差來計算曲線的相似距離,這樣可以忽略平移因素的影響。

圖6 曲線相似度比較過程示意圖

在已經(jīng)得到的匹配路徑上,依據(jù)上述的方法,計算所有的曲線段間相似度,然后通過累計求和的方法計算模板簽名和測試簽名的相似距離dsum,如式(8)所示：

(8)

其中：l1i和l2i表示分別表示模板簽名和測試簽名在第i個匹配段的采樣點數(shù);l1總和l2總分別表示模板簽名和測試簽名總的采樣點數(shù);Ns表示匹配對的總數(shù)。

3 實驗與分析

實驗主要運用本地數(shù)據(jù)庫和公開數(shù)據(jù)庫SUSIG Visual和SUSIG Blind數(shù)據(jù)集[17]進行評估。本地數(shù)據(jù)庫為中文簽名,總共有20位簽名者,每位簽名者有20個真實樣本和10個偽造樣本,訓練時,選隨機選取真實樣本中的5個真實樣本進行訓練,剩余的樣本作為測試樣本。SUSIG 數(shù)據(jù)集是外文簽名,Visual總共有94位簽名者,Blind共有90位簽名者,每位簽名者共有10個真實樣本和10個熟練偽造樣本,訓練時,隨機選取真實樣本中的3個真實樣本進行訓練,剩余的樣本作為測試樣本。根據(jù)訓練結果和測試結果對每個人選取個性化的閾值,通過誤拒率(False Rejection Rate, FFR)和誤納率(False Acceptance Rate,FAR)進行結果統(tǒng)計,并分析等誤率(Equal Error Rate,EER)。

以SUSIG數(shù)據(jù)庫為例,認證結果分析過程如下:

步驟1 隨機選取3個真實樣本作為模板,兩兩之間計算相似距離,然后得到3個距離,并記錄計算結果。閾值選取的規(guī)則如式(9)所示,δ的取值可根據(jù)實驗的結果進行調(diào)整。

(9)

步驟2 將測試樣本簽名和模板樣本簽名進行匹配,得到相似距離后,去掉匹配距離過大的值,然后取剩余剩下的距離的平均值作為最終的認證距離;最后將最終的認證距離與閾值比較。若認證距離大于閾值則為偽造簽名,小于閾值則為真實簽名。

步驟3 調(diào)整δ值,計算數(shù)據(jù)集整體的FAR、FRR和EER。對每個簽名者單獨分析,得到每個簽名者的個性化閾值,計算每個簽名用戶的EER。

圖7展示了各數(shù)據(jù)庫在不同閾值分析方法下的簽名認證結果。

從圖7(a)、(b)可看出：在本地數(shù)據(jù)庫中，δ取值為2.61時，整體閾值方法的EER為3.78%；使用個性化閾值時，平均EER為2.63%，認證效果較好。

從圖7(c)、(d)可看出：在SUSIG Visual數(shù)據(jù)集中，δ取值為1.58時，整體閾值方法的EER達到6.80%；使用個性化閾值時，有8個簽名組的等誤率在20%以上，錯誤主要集中在對高度偽造簽名的認證中。

從圖7(e)、(f)可看出：在SUSIG Blind數(shù)據(jù)集中，δ取值為1.42時，整體閾值方法的EER為6.25%；使用個性化閾值時，平均EER達到了2.44%，只有4個簽名組的等誤率在20%以上，認證效果較好。

表1 在SUSIG數(shù)據(jù)集和已有的方法對比

表1列出了本文方法與對比方法在數(shù)據(jù)集SUSIG上的實驗結果對比。從實驗結果可以看出,在Blind數(shù)據(jù)集上,本文算法具有一定的優(yōu)勢,相對于傳統(tǒng)的DTW方法，EER降低了約14.4%。文獻[15]方法利用遺傳算法找到相似度最高的曲線,要求兩曲線的采樣點數(shù)相同的方式具有局限性,而且過程中未考慮抬筆的情況。文獻[17]方法利用DTW找到匹配的最小距離,匹配中沒有考慮出現(xiàn)多余段的情況,而且對于采樣點較多的情況,DTW算法時間復雜度較高。在Visual數(shù)據(jù)集中,對于高度熟練偽造簽名的認證,多維動態(tài)特征提取和信息融合的方法具有更高的優(yōu)勢。

圖7 閾值分析

4 結語

本文研究了曲線相似變換的性質(zhì),將離散的點以曲線的形式表示出來,并對曲線進行相似變換和重采樣。通過這種方式來減少因為曲線平移、旋轉、縮放以及采樣點不均勻而導致的匹配距離過大的問題。在實際應用中,本文對簽名曲線進行了研究,對簽名進行分段,然后用高階貝塞爾曲線進行擬合,并在一定范圍內(nèi)對擬合后的貝塞爾曲線的進行相似變換和重采樣,最后進行曲線差異性的度量用于認證。同時本文還研究了曲線分段段匹配的算法,對傳統(tǒng)的基于動態(tài)規(guī)劃的算法作了改進,使其能夠能夠剔除多余段和合并有效段,達到了比較好的匹配效果。在SUSIG Visual和SUSIG Blind數(shù)據(jù)集上對本文方法進行測試,達到了等誤率為3.56%和2.44%的認證效果。在匹配的過程中,出現(xiàn)了一些簽名者的簽名不夠穩(wěn)定的情況,在后續(xù)的研究中考慮使用動態(tài)匹配的方法來減少不穩(wěn)定因素,同時通過提取更多的動態(tài)信息進行信息融合的方式來共同完成認證,從而降低認證的錯誤率。

參考文獻(References)

[1] MARTENS R, CLAESEN L. Dynamic programming optimisation for on-line signature verification[C]// Proceedings of the Fourth International Conference on Document Analysis and Recognition. Washington, DC: IEEE Computer Society, 1997: 653-656.

[2] FANG P, WU Z C, SHEN F, et al. Improved DTW algorithm for online signature verification based on writing forces[C]// ICIC 2005: Proceedings of the 2005 International Conference on Intelligent Computing. Berlin: Springer, 2005: 631-640.

[3] QIAO Y, WANG X, XU C. Learning Mahalanobis distance for DTW based online signature verification[C]// Proceedings of the 2011 IEEE International Conference on Information and Automation. Piscataway, NJ: IEEE, 2011: 333-338.

[4] SAE-BAE N, MEMON N. Online signature verification on mobile devices[J]. IEEE Transactions on Information Forensics and Security, 2014, 9(6): 933-947.

[5] GRUBER C, GRUBER T, SICK B. Online signature verification with new time series kernels for support vector machines[C]// Proceedings of the 2006 International Conference on Biometrics. Berlin: Springer, 2006: 500-508.

[6] YANG L, WIDJAJA B K, PRASAD R. Application of hidden Markov models for signature verification[J]. Pattern Recognition, 1995, 28(2): 161-170.

[7] VAN B L, GARCIA-SALICETTI S, DORIZZI B. On using the Viterbi path along with HMM likelihood information for online signature verification[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(5): 1237-1247.

[8] FALLAH A, JAMAATI M, SOLEAMANI A. A new online signature verification system based on combining Mellin transform, MFCC and neural network[J]. Digital Signal Processing, 2011, 21(2): 404-416.

[9] EMERICH S, LUPU E, RUSU C. On-line signature recognition approach based on wavelets and support vector machines[C]// Proceedings of the 2010 IEEE International Conference on Automation Quality and Testing Robotics. Piscataway, NJ: IEEE, 2010, 3: 1-4.

[10] LIU Y, YANG Z, YANG L. Online signature verification based on DCT and sparse representation[J]. IEEE Transactions on Cybernetics, 2015, 45(11): 2498-2511.

[11] GRUBER C, GRUBER T, KRINNINGER S, et al. Online signature verification with support vector machines based on LCSS kernel functions[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2010, 40(4): 1088-1100.

[12] 鄒杰, 孫寶林, 於俊. 基于筆畫特征的在線筆跡匹配算法[J]. 自動化學報, 2016, 42(11): 1744-1757.(ZOU J, SUN B L, YU J. Online handwriting matching algorithm based on stroke feature[J]. Acta Automatica Sinica, 2016, 42(11): 1744-1757.)

[13] PRAUTZSCH H, BOEHM W, PALUSZNY M. Bézier and B-spline Techniques[M]. Berlin: Springer, 2013: 9-56.

[14] 于昊, 趙乃良, 陳小雕. 類曲率在曲線相似度判定中的應用[J]. 中國圖象圖形學報, 2012, 17(5): 707-714.(YU H, ZHAO N L, CHEN X D, Quasi-curvature and its application in similarity measurement of curves[J]. Journal of Image and Graphics, 2012, 17(5): 707-714.)

[15] 邱益鳴, 胡華成, 鄭建彬, 等. 基于曲線相似的在線簽名認證方法[J]. 系統(tǒng)工程與電子技術, 2014, 36(5): 1016-1020.(QIU Y M, HU H C, ZHENG J B, et al. On-line handwriting signature verification based on curve similarity[J]. Systems Engineering and Electronics, 2014, 36(5): 1016-1020.)

[16] YUE K W, WIJESOMA W S. Improved segmentation and segment association for on-line signature verification[C]// Proceedings of the 2000 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ: IEEE, 2000, 4: 2752-2756.

[17] ALISHER K, BERRIN Y. SUSIG: an on-line signature database, associated protocols and benchmark results[J]. Pattern Analysis & Applications, 2009, 12(3): 227-236.

[18] YANIKOGLU B, KHOLMATOV A. Online signature verification using Fourier descriptors[J]. Eurasip Journal on Advances in Signal Processing, 2009, 2009(1): 1-13.

[19] KHALIL M I, MOUSTAFA M, ABBAS H M. Enhanced DTW based on-line signature verification[C]// Proceedings of the 2009 16th IEEE International Conference on Image Processing. Piscataway, NJ: IEEE, 2009: 2713-2716.