基于競爭聚類的離線簽名驗證算法

摘要：提出一種新的基于競爭聚類的離線簽名驗證算法。在注冊階段，通過樣本特征的相關(guān)系數(shù)檢查樣本的一致性；在驗證階段，利用樣本與待驗簽名的競爭聚類結(jié)果判斷待驗簽名的真?zhèn)?。實驗結(jié)果表明，該算法不需用閾值來進(jìn)行控制，能有效地降低誤納率。

關(guān)鍵詞：一致性檢查；競爭聚類；生物模式識別；簽名驗證

中圖法分類號：TP393．08文獻(xiàn)標(biāo)識碼：A

文章編號：1001－3695(2007)01-0191－03

生物模式識別（Biometrics）技術(shù)是通過計算機(jī)利用人體所固有的生理特征或行為特征來進(jìn)行個人身份鑒定。生理特征與生俱來，多為先天性的；行為特征則與后天有關(guān)。將生理特征和行為特征統(tǒng)稱為生物特征。常用的生物特征包括指紋、掌紋、虹膜、臉形、聲音、筆跡等，某些生理特征具有極高的穩(wěn)定性，其識別技術(shù)也較成熟，如指紋和虹膜識別。手寫簽名方便有效，從筆跡中抽取個人信息，不侵犯隱私而被廣泛接受[1]，如商業(yè)交易中的簽名確認(rèn)及驗證；但計算機(jī)簽名驗證的問題尚未完全解決，尤其是對離線簽名驗證難度更大，原因如下：

(1)簽名的可變性。同一人的簽名相似但不完全等同，必定存在整體或局部的差異，如位置、大小、方向等；簽名還隨著人的心理、生理狀態(tài)的變化而波動，如疾病、疲勞、飲酒等；另外，隨著時間的推移，人們的簽名有不斷進(jìn)化的趨勢，因此完全可靠的簽名不存在。

(2)可用樣本少。從實用的角度來講，不可能用大量的樣本進(jìn)行訓(xùn)練，這樣會造成閾值選取的困難。另一方面，偽造簽名樣本不易獲得。

(3)動態(tài)特征的丟失。離線簽名驗證失去了所有的動態(tài)特征，如位置（坐標(biāo)）、筆順、筆壓力、簽名時間、速度變化等。

目前國內(nèi)外對于離線簽名的研究主要集中在特征的提取和分類器的設(shè)計上，提取的特征主要有全局特征、統(tǒng)計特征、幾何特征和偽動態(tài)特征；分類算法主要有統(tǒng)計模式分類、模糊集識別和神經(jīng)網(wǎng)絡(luò)。

Yoshiki Mizukami等人[2]在只有兩個真簽名樣本的情況下，利用歐氏距離定義位移函數(shù)，以此獲得待驗簽名與真實簽名的差異，實現(xiàn)簽名識別。C. Sansone等人[3]將整個驗證過程分為三個階段：①過濾隨機(jī)和簡單的偽造簽名；②過濾熟練的偽造簽名；③結(jié)合前兩階段的閾值對沒有過濾掉的簽名作最終判決。A. N. AbuRezq等人[4]提取了四組特征向量：不變矩、投影、水平垂直投影的線性相關(guān)系數(shù)和統(tǒng)計特征，對四組特征各自采用聚類分析法分類，以四個結(jié)果的民主投票最終判決待驗簽名的真?zhèn)巍adasu Hanmandlu等人[5]采用模糊模式識別法，特征提取方法是先從銀行支票分割出簽名圖像，歸一化、二值化、細(xì)線化，然后按水平方向?qū)D像分割成黑像素相等的八份，再按垂直方向分割成三份，以每份的左下角為原點，計算所有黑像素相對原點的角度之和。實驗分為變系數(shù)和固定系數(shù)、單規(guī)則和多規(guī)則等多種情況，識別各種類型的偽簽名。胡馳峰等人[6]研究了中文簽名中的角度矯正和漢字切分問題，提取的特征為Hausdorff距離，采用最小距離分類法，對簽名進(jìn)行識別。這些方法的誤納率較高，為了降低誤納率，本文針對中文簽名提出了一種新的競爭聚類算法，實驗結(jié)果表明，該方法能有效地降低誤納率。

1特征提取

在簽名識別中，首先需要對簽名圖像進(jìn)行特征提取，良好的特征應(yīng)具有以下四個特點：可區(qū)別性、可靠性、獨立性、數(shù)量少。目前，從簽名圖像中提取的特征數(shù)目多達(dá)200多個[7]，本文通過實驗選取其中的六個特征：水平垂直投影的歪斜度、峰度以及不變矩中的M1，M2，M3和歐拉數(shù)。

1．1圖像預(yù)處理

先將灰度圖像二值化，再用中值濾波消除噪聲。為了消除筆和紙的不同給特征向量帶來的差異，本文對簽名圖像進(jìn)行了細(xì)化。預(yù)處理結(jié)果如圖1所示。

1．3特征集

本文通過實驗篩選，在實際的系統(tǒng)中提取了以下特征：

歪斜度反映了投影分布的對稱性。當(dāng)sk>0時，稱為正偏，此時數(shù)據(jù)位于均值右邊的比位于左邊的多，反之稱為負(fù)偏；當(dāng)sk=0時，可認(rèn)為分布是對稱的。

(2)峰度(Kurtosis)

因正態(tài)分布的峰度為3，所以為了與正態(tài)分布比較，將峰度減去3。若ku>0，表示分布有較厚的尾部，說明樣本中含有較多遠(yuǎn)離均值的數(shù)據(jù)。

以上兩個特征是針對細(xì)線圖的水平垂直投影，在計算前，為消除漢字間空格不均的影響，對投影進(jìn)行了去除空格處理，即刪除所有零值，然后將水平垂直投影拼接成一維向量再計算。

2一致性檢查

在放松的狀態(tài)下，大部分人能提供十分穩(wěn)定的簽名，但這種穩(wěn)定性極易受到自身及外部的干擾。為了使用戶注冊時能提供可靠的簽名樣本，除了在簽名時排除外部干擾和放松自身外，本文提出了在注冊階段對樣本進(jìn)行一致性檢查，這樣能保證被接納的樣本都是強(qiáng)相關(guān)的。設(shè)r，s為兩個樣本的特征向量，定義兩樣本間的相關(guān)系數(shù)為

實驗結(jié)果表明，8組樣本中的7組其相關(guān)系數(shù)在0.93以上，為此將閾值定為0.9。在注冊階段，根據(jù)g(sample(n，p)的符號決定是否接納注冊樣本。若g(sample(n，p))≥0，則接納注冊樣本；否則，拒絕接納，要求用戶重新提供新的注冊樣本。

3競爭聚類

設(shè)數(shù)據(jù)庫中個體的簽名樣本數(shù)為n，待驗證的簽名數(shù)為1，從這n+1個簽名中選取n個強(qiáng)相關(guān)的樣本，然后判斷剩下的一個弱相關(guān)的樣本是否是待驗證簽名，若是，則說明該簽名與真簽名有明顯差距，可判為偽簽名；否則，為真簽名。

競爭聚類算法可借助圖論中最小生成樹算法來實現(xiàn)（其不同之處是競爭聚類算法允許有環(huán)存在）。將n個樣本的p維特征向量和待驗證簽名的p維特征向量視為p維空間的n+1個頂點，歐氏距離視為邊，共有C2n+1，這樣便構(gòu)成了一個完全圖G=(V，E)。用一個頂點數(shù)組vertex[n]來收集強(qiáng)相關(guān)的n個頂點，算法如下：

（1）將E中每條邊的距離按非降排序。

（2）從小到大取E中的每條邊，判斷該邊的每一個頂點是否在vertex數(shù)組中，不在則將其加入數(shù)組，并將計數(shù)器i加1。

（3）若i

（4）判斷余下的一個頂點是否是待驗證簽名的特征向量，若是，則判決該簽名為偽造；否則判決為真實簽名。

4實驗結(jié)果

簽名驗證分為用戶注冊和簽名驗證兩個部分，首先通過用戶注冊，對用戶簽名進(jìn)行處理獲取樣本數(shù)據(jù)。其過程如圖3所示。

圖4樣本數(shù)據(jù)獲取

在對簽名進(jìn)行驗證時，將待驗證簽名數(shù)據(jù)經(jīng)過同樣的預(yù)處理，然后與樣本文件中的樣本一起進(jìn)行競爭聚類，根據(jù)最后聚類的結(jié)果判決待驗簽名的真?zhèn)?。其過程如圖4所示。

圖5簽名驗證

本文共收集10人的900個簽名樣本，其中10個真簽名用于注冊，真、假簽名各40個用于驗證。由于隨機(jī)偽造簽名很容易識別，而熟練偽造又很難獲得，所以本文收集的偽簽名都是經(jīng)過適當(dāng)訓(xùn)練的簡單偽造簽名。從10人中隨機(jī)抽取4人的注冊樣本，分別對其真、假各40個的待驗樣本進(jìn)行驗證。實驗結(jié)果用兩類錯誤率來度量：誤拒率(False Rejection Rate， FRR)，即真簽名被拒絕的比率；誤納率(False Acceptance Rate， FAR)，即假簽名被接收的比率。所得結(jié)果如表2所示。

表2實驗結(jié)果

從實驗結(jié)果可知，該方法有效地降低了誤納率，平均誤納率為1.25%，第四組的誤拒率和誤納率均較高。通過對這些樣本的分析，發(fā)現(xiàn)該組簽名的穩(wěn)定性較差，相關(guān)系數(shù)為0．9026。

5總結(jié)

大多數(shù)簽名識別算法都是通過閾值來平衡誤拒率和誤納率，但事實上這兩類問題的性質(zhì)是不同的，誤拒會帶來較大的麻煩，而誤納將會帶來損失。本文采用了競爭聚類的驗證算法，盡最大可能地降低了誤納率。本文的另一個特點是在注冊階段通過一致性檢查進(jìn)行樣本篩選，由于奇異樣本會對競爭聚類算法產(chǎn)生很大影響，所以為確保樣本的穩(wěn)定性，對樣本進(jìn)行相關(guān)性檢查，不符合要求的注冊，將被要求重新提供樣本，以保證較低的誤納率。

參考文獻(xiàn)：

［1］M C Fairhust. New Perspectives in Automatic Signature Verification[J]. Information Security Technical Report， 1998，3(1):5259.

［2］Yoshiki Mizukami， Mitsu Yoshimura， Hidetoshi Miike， et al. An Offline Signature Verification System Using an Extracted Displacement Function[J]. Pattern Recognition Letters，2002，23(4):15691577.

［3］C Sansone， M Vento. Signature Verification: Increasing Performance by a MultiStage System[J]. Pattern Analysis Applications， 2000，3(1):169181.

［4］A N AbuRezq， A S Tolba. Cooperative SelfOrganizing Maps for Consistency Checking and Signature Verification[J]. Digital Signal Processing， 1999， 9(2):107119.

［5］Madasu Hanmandlu， Mohd Hafizuddin， Mohd Yusof， et al. Offline Signature Verification and Forgery Detection Using Fuzzy Modeling[J]. Pattern Recognition， 2005，38(3):341356.

［6］胡馳峰， 張長水， 李衍達(dá). 基于Hausdorff距離的簽字驗證問題[J]. 計算機(jī)應(yīng)用， 2003，23(9):4546.

［7］Darwish A， Auda G. A New Composite Feature Vector for Arabic Handwritten Signature Recognition[C]. Australia: International Conference on Acoustics， Speech and Signal Processing (ICASSP)， 1994.613616.

作者簡介：

張顯全（1964），男，重慶人，副教授，主要研究方向為圖形圖像處理；劉忠平（1972），男，湖南邵陽人，碩士研究生，主要研究方向為圖形圖像處理。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文