蔣青云

(湖南省婦幼保健院信息中心，湖南 長沙 410008)

0 引 言

離線簽名識別作為一種身份識別技術(shù)，廣泛運用于金融、安全等領(lǐng)域。相對于在線簽名識別方法，進行離線簽名識別時無法獲得書寫簽名時的書寫速度、壓力等各種動態(tài)信息，只能依賴于簽名圖像反映的靜態(tài)信息，簽名識別的難度相對更大，通常也存在識別率偏低等問題[1]。

近年來，國內(nèi)外學(xué)者在手寫簽名鑒定及識別領(lǐng)域的研究逐步深入，涌現(xiàn)出了許多特征提取、分類識別方法。Vargas、Ferrer等人[2-3]通過提取灰度共生矩陣、局部二值模式等特征，采用支持向量機進行分類識別。Jaiswal等人[4]通過提取簽名圖像的全局、局部特征，使用神經(jīng)網(wǎng)絡(luò)進行識別，得到較高的識別率。Shekar等人[5]結(jié)合離散余弦變換與支持向量機，獲得了較高的簽名識別率。Pham等人[6]基于直方圖、幾何特征，在荷蘭簽名數(shù)據(jù)庫上取得了較好的識別率，但在中文簽名上的識別率欠佳。Hatkar等人[7]通過提取圖像的幾何特征，基于神經(jīng)網(wǎng)絡(luò)進行分類識別。Serdouk等人[8]基于局部二值模式、拓撲特征等，使用人工免疫系統(tǒng)進行分類匹配，在英文、中文簽名中取得了較好的效果。Das等人[9]基于Gabor濾波技術(shù)提取簽名圖像的拓撲及統(tǒng)計特征，采用粗糙集理論構(gòu)建分類識別系統(tǒng)。

中文簽名具有復(fù)雜、多樣化等特點，給簽名圖像特征提取、分類識別帶來難度。本文對中文簽名識別方法進行研究，為了融合多種有效簽名圖像特征并進行合理的特征提取，引入一種基于改進的保局投影(Locality Preserving Projections, LPP)方法進行線性降維，以得到有利的特征向量和特征維度。針對中文簽名識別率問題，本文提出一種基于改進的糾錯輸出碼支持向量機(ECOC-SVMS)的簽名識別方法，以有效提升識別成功率。實驗結(jié)果表明本文的方法取得了較好的特征提取效果，同時也顯著提升了多類分類性能。

1 基于LPP的特征提取

LPP方法具有流形學(xué)習(xí)和線性降維的共同優(yōu)點，在模式識別特征提取領(lǐng)域得到了廣泛應(yīng)用。LPP方法本質(zhì)上使得高維空間中接近的樣本，映射到低維空間后所有樣本的局部K-近鄰重建誤差達到最小。然而，傳統(tǒng)LPP方法具有如下不足[10-11]：1)屬于無監(jiān)督方法，降維過程中未使用樣本類別信息；2)創(chuàng)建鄰接圖時近鄰參數(shù)K非常關(guān)鍵，但原始方法中并未給定通用的有效方法；3)通過歐氏距離確定K近鄰域，僅考慮了樣本空間的距離特性而未考慮其幾何結(jié)構(gòu)特性。

1.1 保局投影方法

對于高維空間RD×N中的數(shù)據(jù)集合X=x1,x2,…，xN(N為樣本個數(shù))，LPP算法的目標是尋找一個投影矩陣A=a1,a2,…,ad，將高維空間中的數(shù)據(jù)集合映射到低維空間Rd×N中的數(shù)據(jù)集合Y=y1,y2,…，yN，其中Y=ATX。矩陣A為最小化以下目標函數(shù)的解：

(1)

式(1)中，W為衡量節(jié)點之間權(quán)值的關(guān)系矩陣。

LPP的一般步驟：

1)創(chuàng)建鄰接圖。建立一個包含m個頂點的權(quán)圖G，若權(quán)圖G中的節(jié)點xi是xj的K-近鄰，或節(jié)點xj是xi的K-近鄰，則在節(jié)點xi、xj之間用一條邊連接。

2)確定權(quán)重。若權(quán)圖中節(jié)點xi、xj有邊相連接，則Wij=e-‖xi-xj‖2/t(t為大于0的常數(shù))；簡化地，若節(jié)點xi、xj有邊相連接，則Wij=1，否則Wij=0。

XLXTa=λXDXTa

(2)

假設(shè)列向量a1,a2,…,ad為式(2)的解，且其對應(yīng)特征值滿足λ1<…<λd,則矩陣AD×d=(a1,a2,…,ad)為保局投影方法中的投影矩陣。

1.2 改進的LPP方法應(yīng)用于特征提取

針對傳統(tǒng)LPP方法的不足之處，本文從如下幾個方面對傳統(tǒng)LPP方法進行改進[11-12]：

1)通過樣本之間的相關(guān)性自適應(yīng)確定鄰域K。確定節(jié)點xi的鄰域時，首先通過式(3)計算節(jié)點xi與其他節(jié)點之間的平均相關(guān)性度量：

(3)

(4)

2)采用有監(jiān)督方式構(gòu)建鄰接圖，引入樣本標簽類別信息，鄰域內(nèi)同類別之間的節(jié)點有邊相連；否則，無相連邊，其對應(yīng)權(quán)值也為0。

3)結(jié)合距離特性和幾何特性，引入歐氏距離、測地距離進行鄰接點權(quán)值計算，如式(5)：

(5)

式(5)中，de(xi,xj)表示歐氏距離，dg(xi,xj)表示測地距離，dg,m表示鄰域內(nèi)測地距離中值。由式(5)可知，鄰域內(nèi)鄰接點與樣本點的測地距離越大，則計算出的權(quán)值越??；鄰域內(nèi)鄰接點與樣本點之間的歐氏距離與測地距離比值可反映鄰域的幾何結(jié)構(gòu)特性。

基于改進LPP的特征提取方法步驟如下：

輸入：高維空間RD×N中的數(shù)據(jù)集合X={x1,x2,…,xN}(N為樣本個數(shù))及其類別屬性{c1,c2,…,ci,…,cN}(其中ci∈{1,2,…,P}，P表示最大類別數(shù))

輸出：投影矩陣A=[a1,a2,…,ad]；低維空間Rd×N中的數(shù)據(jù)集合Y={y1,y2,…,yN}

Step2計算權(quán)值矩陣。根據(jù)式(5)計算每個節(jié)點與其鄰接節(jié)點之間的權(quán)值。

Step3計算投影矩陣A。根據(jù)式(2)按傳統(tǒng)LPP方法求取其特征值對應(yīng)的非0特征向量，該向量構(gòu)成投影矩陣A=[a1,a2,…,ad]。

Step4計算降維后的特征向量Y。根據(jù)求得的投影矩陣、高維數(shù)據(jù)集合，求得降維后的特征向量數(shù)據(jù)集合Y={y1,y2,…，yN}。

2 基于ECOC-SVMS的離線簽名識別

多分類器設(shè)計是離線簽名識別系統(tǒng)的關(guān)鍵。糾錯輸出編碼(Error Correcting Output Code，ECOC)[13]框架借助通信系統(tǒng)中的編、解碼模型，將多類分類問題分解為多個二類分類問題，利用編碼冗余特性提供糾錯能力，根據(jù)某種解碼規(guī)則得到多類分類結(jié)果。ECOC支持向量機在多類識別問題中得到了廣泛的應(yīng)用。ECOC的主要問題在于：1)尋求合適的編碼方法將多類分類問題分解為多個二類分類問題，并對二類分類器進行訓(xùn)練；2)設(shè)計合理的解碼策略，使得融合決策后的輸出能夠達到優(yōu)異的分類性能。

2.1 Hadamard糾錯輸出碼

本文引入Hadamard糾錯碼來設(shè)計ECOC編碼方法[14]。Hadamard糾錯編碼矩陣最大的特點在于其任意兩行或兩列均相互正交。對N階的Hadamard矩陣，其行、列間的漢明距離均為N/2，具有良好的區(qū)分性能，滿足ECOC對編碼的要求。實際使用時，由于其矩陣第一列全為“-1”且其階數(shù)固定為2的冪次方，需要對Hadamard矩陣進行改造。Hadamard糾錯碼生成算法如下：

1)根據(jù)類別數(shù)P確定Hadamard矩陣的階數(shù)：若2i-1

2)按照Hadamard矩陣遞推公式生成階數(shù)為2i的Hadamard矩陣H2i；

3)去除矩陣的第一列，并根據(jù)類別數(shù)P取矩陣的前P行，得到所需的糾錯編碼矩陣MP×2i-1。

2.2 改進的Hadamard ECOC-SVMS應(yīng)用于離線簽名識別

傳統(tǒng)SVM的分類結(jié)果并不存在概率輸出。通?？烧J為，樣本被分類到某一類的概率可以看作它屬于這一類的可能性。一般情況下，SVM中樣本xi到分類面的距離是gxi/‖w‖，經(jīng)訓(xùn)練后樣本到分類面的距離僅與判別函數(shù)值g(xi)有關(guān)。SVM的輸出經(jīng)轉(zhuǎn)換后可以生成近似的后驗概率[15]為：

(6)

式(6)中，A、B可通過最大似然方法求解。通過上述方法將SVM輸出轉(zhuǎn)換成后驗概率，可以對ECOC-SVMS中每個基分類器輸出賦予一個概率。分類測試時，將訓(xùn)練樣本x送入各個訓(xùn)練好的基分類器，各分類器均會輸出類別標簽及其對應(yīng)的近似后驗概率輸出。各個類別對應(yīng)序列的概率計算如式(7)[15]：

(7)

式(7)中，k表示類別索引，bj表示一個碼字，b1…bn表示編碼序列。假定碼字的后驗概率相互獨立，并對式(7)兩邊取對數(shù)，并求取概率最大時對應(yīng)的類別即為最終的判決類別，即：

(8)

離線簽名問題中，通常會采集簽名者的多個簽名構(gòu)成簽名數(shù)據(jù)庫。簽名識別系統(tǒng)中，通過采集的簽名樣本作為訓(xùn)練樣本對分類器進行訓(xùn)練，構(gòu)建分類器參數(shù)。測試時，將測試樣本輸入至已訓(xùn)練好的多類分類器，分類器的最終輸出即為最終的簽名識別結(jié)果?；贖adamard ECOC-SVMS的離線簽名識別方法步驟如下：

輸入：訓(xùn)練樣本集Y0={{y1,c1},{y2,c2},…，{yN,cN}}(其中yi表示特征向量，ci表示對應(yīng)的類別屬性)；測試樣本集Y1={{y1,c1},{y2,c2},…，{yN,cN}}；類別數(shù)P。

輸出：分類輸出結(jié)果ci。

Step1根據(jù)樣本類別數(shù)，由2.1節(jié)所述方法生成Hadamard糾錯編碼輸出矩陣MP×2i-1；

Step2根據(jù)糾錯編碼輸出矩陣，使用訓(xùn)練樣本集對各個基分類器進行訓(xùn)練，得到各基SVM分類器參數(shù)、判別函數(shù)；

Step3輸入測試樣本至已訓(xùn)練好的Hadamard ECOC-SVMS分類器中，按式(6)根據(jù)分類判別函數(shù)計算輸出近似概率結(jié)果；

Step4按式(7)、式(8)計算測試樣本屬于各類別的序列的概率，取概率值最大時對應(yīng)的類別即為最終的分類輸出結(jié)果ci。

3 實驗與分析

3.1 簽名圖像特征選取

簽名圖像特征一般包括圖像的全局形狀或幾何結(jié)構(gòu)特征、統(tǒng)計特征等。針對簽名灰度、二值圖像的特點，本文選取的典型原始特征有：

1)簽名圖像有效高度寬度比。對簽名圖像區(qū)域四個方向進行掃描，取簽名區(qū)域的寬、高比值作為一維全局形狀特征向量。

2)黑點面積與總面積比。對二值化后的圖像，計算簽名圖像區(qū)域黑點像素與總像素比值，作為一維衡量簽名筆劃的特征向量。

3)重心坐標。根據(jù)簽名圖像水平、垂直方向的黑點投影密度進行計算并歸一化，得到水平、垂直方向的坐標作為二維特征向量。

4)筆劃寬度分布。通過以簽名圖像骨架為中心從水平、垂直兩個方向向外搜索，取筆劃像素點統(tǒng)計結(jié)果作為筆劃寬度。再對筆劃寬度值進行直方圖統(tǒng)計，獲得筆劃寬度的分布。根據(jù)簽名筆畫的通常寬度，取1～18之間的直方圖分布共18維特征向量。

5)灰度分布直方圖。

對簽名圖像的簽名區(qū)域，取灰度級分布的概率直方圖作為特征，實際計算時，可通過灰度分布累積值進行歸一化。簽名圖像的灰度級別一般不豐富，可取256級灰度分布中的主要灰度級別即可，本文取64級構(gòu)成64維特征向量。

6)中心投影。

7)基于Gabor變換的紋理特征。

根據(jù)Gabor變換的實現(xiàn)，取5尺度、8方向的Gabor核進行紋理特征提取，共80維統(tǒng)計紋理特征。

8)CS-LBP紋理特征。

簽名灰度圖像中，對于其中任意像素灰度值gc，在其像素位置為中心、半徑為R(R=1或2)的環(huán)形鄰域上，P(P=8或16)個像素點均勻分布(若均勻分布位置上無對應(yīng)像素點時，可通過插值法得到)。以該中心像素為基準的紋理可用鄰域中P+1個像素定義為：

T=tsg0-gc,sg1-gc,…,sgP-1-gc

(9)

其中，gc，g0，g1,…,gP-1代表中心像素及其鄰域上P個點的灰度值，s為權(quán)重系數(shù)，鄰域中像素大于中心像素灰度值時，s為1，否則為0。LBP值定義為：

(10)

中心對稱局部二值模式(Center Symmetric LBP,CS-LBP)以LBP為基礎(chǔ)[16]，不再依次比較鄰域周邊P個像素與中心像素的灰度值，而是比較基于中心像素對稱的2個周邊像素點的灰度值，CS-LBP定義為：

(11)

CS-LBP相比LBP統(tǒng)計直方圖的維數(shù)更低，維數(shù)為2P/2(LBP則為2P)，計算復(fù)雜度更低，且抗噪能力更強。取典型的八鄰域，CS-LBP特征共16維。

以上各類原始特征通過融合方式可構(gòu)成206維特征向量。對每幅簽名圖像，均按本節(jié)所述方法進行提取并構(gòu)成樣本的原始特征向量。

3.2 實驗結(jié)果及分析

為了驗證本文方法的可行性和有效性，取自行構(gòu)建的中文簽名數(shù)據(jù)庫作為實驗數(shù)據(jù)來源。簽名數(shù)據(jù)庫總共采集了包括不同性別、年齡、書寫風(fēng)格的簽名者共計32人的簽名，每個簽名者在不同時間段、以不同書寫速度各簽名40個，該數(shù)據(jù)庫共計1280個簽名。圖像預(yù)處理階段，采用統(tǒng)一的方法對圖像進行去噪等預(yù)處理。本文實驗設(shè)計主要考察特征提取中的降維效果以及ECOC-SVMS分類識別性能，如鄰域參數(shù)K、降維后的維數(shù)d、識別率等。

實驗1考察特征提取中的降維效果以及對簽名識別率的影響，本實驗將傳統(tǒng)PCA方法、原始LPP方法與本文改進的LPP方法進行比較。從表1可以看出，改進的LPP方法相較于其他2種方法，在獲得良好降維特性的同時還保持了較高的分類識別效果。

此外，對于改進LPP中的自適應(yīng)鄰域參數(shù)選取情況，鄰域K值一般在8～11。從分類識別實驗結(jié)果來看，自適應(yīng)鄰域值的選擇取得了較好的實驗效果。

表1 多種特征提取方法的實驗結(jié)果比較

實驗2考察使用本文改進LPP特征提取方法應(yīng)用于不同ECOC-SVMS分類識別方法時對簽名識別效果的影響，本實驗將BCH編碼ECOC-SVMS方法、原始Hadamard ECOC-SVMS方法與本文改進的Hadamard ECOC-SVMS方法進行比較。從表2可以看出，改進的Hadamard ECOC-SVMS方法相較于其他2種方法，在分類識別率方面具有顯著的提升。

表2 本文特征提取方法與其他ECOC-SVMS分類方法的實驗結(jié)果比較

4 結(jié)束語

針對離線簽名識別領(lǐng)域，本文提出了一種結(jié)合LPP和Hadamard ECOC-SVMS的離線簽名識別方法。對于經(jīng)預(yù)處理后的簽名圖像，選擇多種有效特征構(gòu)建原始的高維特征向量，引入一種改進的保局投影方法進行特征提取并同時實現(xiàn)高效降維；簽名識別方面，使用基于Hadamard糾錯編碼方法的ECOC支持向量機多類分類方法，并引入近似概率方法對ECOC解碼進行改進，以提升多類分類器的性能。實驗結(jié)果表明了此方法的可行性和有效性。下一步應(yīng)考慮更大規(guī)模、種類、不同圖像質(zhì)量的簽名數(shù)據(jù)庫，并針對高效特征提取、高性能分類器、算法復(fù)雜度優(yōu)化等方面進行繼續(xù)深入研究。