基于競(jìng)爭(zhēng)聚類的離線簽名驗(yàn)證算法

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

關(guān)鍵詞：一致性檢查；競(jìng)爭(zhēng)聚類；生物模式識(shí)別；簽名驗(yàn)證

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

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

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

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

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

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

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

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

1特征提取

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

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

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

1．3特征集

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

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

(2)峰度(Kurtosis)

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

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

2一致性檢查

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

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

3競(jìng)爭(zhēng)聚類

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

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

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

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

（3）若i

（4）判斷余下的一個(gè)頂點(diǎn)是否是待驗(yàn)證簽名的特征向量，若是，則判決該簽名為偽造；否則判決為真實(shí)簽名。

4實(shí)驗(yàn)結(jié)果

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

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

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

圖5簽名驗(yàn)證

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

表2實(shí)驗(yàn)結(jié)果

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

5總結(jié)

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

參考文獻(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］胡馳峰， 張長(zhǎng)水， 李衍達(dá). 基于Hausdorff距離的簽字驗(yàn)證問(wèn)題[J]. 計(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.

作者簡(jiǎn)介：

張顯全（1964），男，重慶人，副教授，主要研究方向?yàn)閳D形圖像處理；劉忠平（1972），男，湖南邵陽(yáng)人，碩士研究生，主要研究方向?yàn)閳D形圖像處理。

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