基于筆畫特征的在線筆跡匹配算法

鄒杰 孫寶林 於俊

基于筆畫特征的在線筆跡匹配算法

鄒杰1,2孫寶林2於俊1

針對現有在線筆跡匹配算法魯棒性不強的問題,本文提出將合并規則和跳躍規則引入到動態規劃的迭代過程,以跳躍規則應對書寫中的多、漏筆現象,以合并規則應對因多種書寫不一致造成的分割點多提取、漏提取現象.在累計差異矩陣計算中,提出以筆畫特征,特別是筆畫形狀信息來度量筆畫間的差異.在SVC2004和SUSIG簽名數據庫上與現有主要在線筆跡匹配算法進行比較.實驗結果表明,本文方法能較好應對多種局部書寫和分割的不一致,從而獲得更準確、魯棒的筆畫對應關系.

在線筆跡認證,筆跡匹配,筆畫差異值度量,動態規劃

現代社會,計算機網絡已走進人們生產生活的方方面面.網絡環境下,方便快捷、安全可靠地對用戶身份進行認證成為亟待解決的問題.手寫筆跡作為一種行為特征,相對于其他生理特征,例如指紋、虹膜、DNA等,具有主動的特征提取過程、模板內容可更換等特點,更適合于網絡環境下的應用,受到人們廣泛關注[1?2].

按獲取信息的方式,筆跡認證分為離線和在線兩種.前者依據書寫后留下的靜態筆跡圖像數據進行認證[3?4],后者依靠專門的設備實時獲取書寫過程中產生的各種信息進行認證.本文主要討論在線筆跡認證.

在線筆跡認證的特征提取通常分為參數法和函數法[5].參數法是指用一組參數表示筆跡,通過參數的比較來判斷測試筆跡的真實性.常用的參數特征包括筆跡書寫時間、落筆書寫長度、長寬比、各種極值點個數、各種域變換系數等[5?6].由于書寫活動的復雜性以及這些特征對筆跡書寫細節描述能力的不足,通常認證系統還會采用函數法提取特征.

函數法是指將手寫筆跡的各種信號看作時間的函數,通過直接比較模板和測試筆跡時間函數來判別真實性.常用的函數特征提取方法包括動態時間規整(Dynamic time warping,DTW)[7?8]、隱馬爾科夫模型(Hidden Markov model,HMM)[8?9]等.在小樣本約束條件下,通過函數法挖掘筆畫特征具有重要意義.這是因為:1)穩定性.盡管在微觀細節上筆跡特征差異可能較大,但從宏觀上看,例如筆順、筆畫的形狀、長短、筆畫間的相對位置關系、前后筆畫間的轉折承接方式、筆跡整體結構布局等,具有較高的穩定性.2)個性化.筆跡學研究發現,受自身成長環境、感知能力等因素影響,人們在筆畫的運筆方式、起落筆方式、筆畫間相對位置關系、前后筆畫間的轉折書寫用力、書寫節奏上有著多種多樣的表現形式,從根本上反映出書寫者自身的書寫習慣,具有較高的鑒別價值[10].然而,提取上述筆畫特征卻并非易事,需要以魯棒地建立筆畫對應關系為前提.

典型的匹配算法包括筆跡分割和筆畫匹配兩個步驟.國內外學者對此進行了廣泛深入的研究.簡單的筆跡分割方法有等長分割法[11]和起落筆點選取法[12].由于筆跡書寫長度和提落筆的不一致,簡單分割法的匹配結果往往難以令人滿意.其他分割方法還包括:1)遺傳算法[13].該方法選用模板筆跡集合中兩兩分割點序列的DTW差異值的均值作為適配函數,使適配函數最小的點被選為分割點.2)直線近似法[13].以筆跡中任意兩點構成的直線代替對應的曲線運筆,若曲線運筆與直線圍成的面積大于某一閾值,則在曲線中尋找一個點將運筆分為前后兩段.重復上述步驟直到所有直線與曲線的面積都小于預設的閾值.3)小波變換法[14].其思路是小波變換的過零點往往對應書寫中的視覺關鍵點. 4)極值點法.包括速度極小值、角度、曲率極大值等[15?16].5)模糊綜合法.考慮到書寫的任意性,單一的極值并不完全與筆畫的起止點對應,而應綜合考慮多方面的信息[17],由此定義分割點的隸屬度函數,函數值由角度、速度共同決定,其值越大,越可能是關鍵點.6)視覺拐點法[18].計算前后某一長度運筆中采樣點在彎曲程度上對中間點的貢獻值,其值越大,越可能是視覺拐點.

按建立分割點對應關系的方式,文獻中的匹配方法大致分為三類:1)事先無需提取分割點[19].該方法采用HMM模型尋找分割點對應關系.具體地,模型選用左右狀態轉移結構,狀態發生變化的采樣點被定義為分割點.該方法依據狀態轉移路徑中狀態發生變化的位置得到分割點對應關系.2)僅提取模板筆跡的分割點,分割點對應關系依DTW全局匹配路徑計算得到[19].首先,提取模板筆跡中的分割點;然后采用DTW算法建立模板與測試筆跡之間的全局匹配路徑;最后根據全局匹配路徑,找出與模板筆跡分割點對應的測試筆跡采樣點,以此得到分割點對應關系.3)提取模板和測試筆跡的分割點,利用優化方法建立分割點對應關系.首先,對模板和測試筆跡按筆畫進行分割;其次,計算分割點的各種屬性值,例如分割點類型[20?24]、開口方向[12,23]、相鄰分割點之間的距離[23?24]、角度[22,25]等;再次,以這些采樣點特征構造目標函數;最后,采用優化算法求目標函數極值,與極值對應的即為所求的分割點對應關系.文獻中常見的優化算法包括:遺傳算法[13]、最小化二次適應判定方程方法(Quadratic fitting criterion equation)[26]、動態規劃方法[27]、最小化薄板樣條函數(Thin-plate spline)扭曲能量(Warping energy)[28]的退火算法.

盡管國內外學者在匹配問題上做了大量工作,但目前仍未取得令人滿意的匹配結果.造成現有算法魯棒性不強的原因可歸納為:1)在筆跡分割方面,以采樣點特征為依據的筆跡分割方法,難以克服書寫的各種不一致(停筆、頓筆、抖筆、多筆、少筆、繞筆、異化筆、虛提筆、簡化筆等),從而得到一致的筆跡分割結果;2)在筆畫匹配方面,由于存在不一致的筆跡分割結果,且后繼優化方法未采取相應的應對措施;更糟的是,在錯誤分割基礎上采用易受干擾且可分性不強的采樣點特征來計算目標函數,造成現有方法難以克服多種書寫不一致,進而得到正確的筆畫對應關系.

由此可見,當存在上述各種書寫不一致且僅有采樣點特征可用的條件下,筆跡分割的不一致幾乎是不可避免的.分析運筆特點可發現,造成不一致分割的書寫不一致大體分為兩類:1)整體一致條件下局部出現的多筆、少筆;2)整體一致條件下局部因簡化筆、抖筆、頓筆、異化筆等造成的分割點多提取或漏提取.對此,本文采取的應對方法為:1)如果模板筆跡中出現多筆或漏筆,在測試筆跡相應位置處將沒有或多出筆畫與之匹配.由此,在尋優過程中引入跳躍規則.2)如果模板筆跡中出現分割點多提取或漏提取,那么,正確的筆畫對應關系應該是模板筆跡中的多個或一個筆畫與測試筆跡的一個或多個筆畫相對應.因此,引入合并規則.

現有工作大多基于分割點特征構造目標函數.由于抗干擾能力不強、包含信息量有限,分割點特征并不足以區分前后相鄰的筆畫.筆跡學研究指出,筆畫有著豐富表現形式.以橫畫為例,有平直橫、上弧橫、下弧橫(弧的彎曲程度有大有小),以及蠶頭燕尾橫(以向下點筆開始、接著向上運筆、最后以向下頓筆結束)等.在筆畫差異度量方面,常見的方法僅利用了采樣點位置[29?30]、速度[31]、曲率[32]等信息.匹配結果表明,這些信息未能充分體現筆畫中的差異,使得算法魯棒.對此,本文提出從筆畫長短、重心位置、方位角、筆畫形狀四個方面對筆畫差異進行度量.

最后,在SVC2004[33]和SUSIG[34]公共簽名數據庫上,將本文方法的匹配結果與現有主要匹配算法的進行比較[12,20?25,30],以此驗證本文方法的有效性.

1 基于筆畫特征的筆跡匹配

建立筆畫間對應關系問題可描述為:對于模板和測試筆跡筆畫序列,在時序性約束條件下,在所有可能的筆畫對應關系序列中,尋找一個使筆畫間累計差異值之和最小的筆畫對應關系序列.

考慮到求解過程的復雜度,一種基于迭代的動態規劃方法被引入進來[35].其中,采用何種規則來計算累計差異值矩陣D成為匹配算法是否準確和魯棒的關鍵.

針對前文分析的造成算法不夠魯棒的原因,本文采用抗干擾能力更強、信息量更豐富的筆畫特征.利用筆畫特征的直觀性,在迭代過程中引入多種物理含義明確的合并和跳躍規則來計算累計差異值矩陣D.

1.1 筆跡匹配步驟

筆跡匹配步驟如下:

步驟1.按Brault等提出的視覺關鍵點將筆跡按筆畫進行分割[18],得到筆畫序列.兩個按視覺關鍵點分割后的筆跡如圖1所示.

圖1 按視覺關鍵點得到的筆跡分割結果示例Fig.1 Examples of handwriting segmented by perceptually important points

步驟2.將合并規則和跳躍規則引入迭代過程,計算累計差異值矩陣D.

圖2給出了因關鍵點多(漏)提取造成的筆跡分割不一致示例,右圖中“的”字橫豎彎鉤運筆部分因彎曲程度不夠明顯造成分割點的漏提取.為應對此類不一致,在累計差異矩陣計算中引入合并規則.具體為:如式(1)中[a]～[j]項所示(分別為1:1,1: 2,2:1,···,1:4,4:1合并規則),如果存在某一合并規則,使按該規則得到的對應筆畫間差異值小于閾值P,則本輪累計差異矩陣的取值由那個使對應筆畫差異值與上輪累計差異矩陣取值之和最小的合并規則而定.式(1)中dmer(i?1,i),j表示合并模板筆跡中的(i?1)～i段筆畫后與測試筆跡中的第j段筆畫間的差異值,下標mer(x,y)表示合并筆畫序列中的x～y段筆畫,該符號出現的位置與筆跡對應,左(右)側表示合并模板(測試)筆跡.dij表示第i段模板筆畫與第j段測試筆畫的差異值.

圖2 因彎曲程度不夠造成的筆跡分割不一致Fig.2 Inconsistent segmentation caused by over and less curving strokes

圖3給出了因多(漏)筆造成的分割不一致示例,左圖中“孟”字的第1筆被漏寫了.對此類不一致,引入跳躍規則,如式(1)中[k]～[l]項所示,其中,Dij表示累計差異值矩陣中第i行第j列元素, 1≤i≤N,1≤j≤M,其中N和M 分別表示模板和測試筆跡的筆畫數.

圖3 因多筆造成的筆跡分割不一致Fig.3 Inconsistent segmentation caused by superfluous and loss strokes

一般來講,如果出現多筆,該多出的筆畫與前后筆畫的差異可能很大.基于這一觀察,定義跳躍規則為:如果筆畫間的差異大于閾值P,則模板或測試筆跡中的當前筆畫被跳過.式(1)中閾值P需要預先設定.在本文實驗部分將對閾值P的設定方法和不同取值對匹配結果的影響進行討論.

在迭代過程中,跳躍規則被執行時可能的筆畫對應關系狀態如圖4所示.圖中以圓或三角形表示筆畫,其中,實心圓表示到上一輪為止已確立對應關系的筆畫,空心圓表示在計算當前Dij時若干候選的待跳過筆畫,三角形表示未確定對應關系的筆畫,黑色直線表示已確立的筆畫對應關系.如式(1)中[k]～[l]項所示,被跳過的筆畫依上輪迭代得到的累計差異陣取值而定.

圖4 跳過測試筆跡的第j段筆畫(左)和跳過模板筆跡的第i段筆畫(右)Fig.4 Jumping the jth stroke of testing handwriting (left)and jumping the ith stroke of template(right) handwriting

圖5給出了合并規則被執行時可能的筆畫對應關系狀態.為簡便起見,僅以2:1和1:2兩種情況為例,圖5中空心圓表示計算當前Dij時若干候選筆畫,灰色直線表示候選的筆畫對應關系,圖中其他符號的含義與圖4中相同.

圖5 2:1(左)和1:2(右)合并規則Fig.5 2:1(left)and 1:2(right)merging rule

顯然,引入越多的合并規則,算法應對各種復雜不一致的能力越強.但是合并規則越多,算法復雜度越高,產生過匹配[24]的可能性越大.

式(1)中w表示尋優搜索的窗口寬度,w=β ×N,其中N表示模板筆跡的筆畫數.

步驟3.采用式(1)給出的合并規則和跳躍規則,從i=1,j=1開始,迭代地計算累計差異值矩陣D,設初值D00=0.

步驟4.從DNM開始,依據被選取的合并規則和跳躍規則,回溯得到筆畫對應關系.

1.2 筆畫差異度量

手寫活動是非常細膩的,由此產生的筆畫具有豐富的表現形態.準確度量筆畫間差異對提高算法準確性具有重要意義.文獻中對筆畫差異度量主要采用了采樣點各種差異特征的累計加權求和,包括位置[29?30]、速度[31]、曲率[31]等信息.分析發現:1)筆畫間至少包含大小、位置、方位角以及筆畫形態等方面的差異,僅用其中一種特征對差異的描述顯然不夠全面.2)基于采樣點特征的求和使得少數決定筆畫形態的轉折處差異淹沒在其他多數平緩的運筆中,使本應有的差異體現不出來.3)采樣點特征易受噪聲、抖動的干擾.為克服這些問題,本文依據由分段點分得的筆畫特征計算差異.下面以圖6中“九”字“橫豎彎”筆畫為例,介紹本文筆畫差異度量方法.

1)大小差異度量

其中,AMaxX,AMaxY,AMinX,AMinY,BMinY, BMinX,BMaxX,BMaxY分別表示模板和測試筆畫在X和Y軸上的最大、最小值.

2)位置差異度量其中,GA和GB分別表示兩段筆畫的重心位置坐標.

圖6 兩個漢字筆跡“九”Fig.6 Two handwriting examples of Chinese character“nine”

3)方位角差異度量

其中,0°≤αA≤180°,0°≤αB≤180°分別表示與兩段筆畫最大特征值對應的特征向量與X軸的夾角[29].

4)形狀差異

形狀差異是指除去筆畫間的大小、方位、位置差異后,單純從形態上所體現的差異.本文采用關鍵點的對應關系來度量形狀差異.

步驟 1.對筆畫進行縮放[36]、旋轉[29]和平移變換[29],去除掉筆畫間的大小、方位、位置差異.為了防止縮放失真,對筆畫的長寬按等比例進行縮放[36].為便于比較,統一將max(width,height)設置為100,其中width、height分別表示縮放后筆畫的寬度和高度.對圖6中筆畫除去大小、位置和方位差異后的結果如圖7所示.其中,S1,S2分別表示模板和測試筆畫.

圖7 兩段歸一化后“九”字的橫豎彎筆畫Fig.7 Two normalized compound strokes in Chinese character“nine”

步驟2.利用角度極大值點對筆畫進行分割.分割后的結果如圖8所示.圖8中D2、D3、d2表示角度極大值分割點.由于彎曲不夠明顯,S1第二個轉折處分段點d3被漏提取.

步驟3.采用經典DTW算法計算筆畫S1與S2的點點對應關系[35].結果如圖9所示.

圖8 筆畫分割結果,D2、D3、d2為角度極大值點Fig.8 Two compound strokes segmented by angle maximum points D2,D3,and d2

圖9 采用經典DTW得到的點點對應關系Fig.9 Point-to-point corresponding calculated by the classical DTW

步驟4.對匹配偏差加以糾正,得到分段點對應關系.從圖9可以看出,由于書寫的不一致,S1中的分段點d2并未與S2中的分段點D2匹配上.但是,由于DTW在這里僅限于局部的筆畫匹配,累積的錯誤并未產生過大偏差.該特性將被用來消除匹配錯誤.

規則1.設q是S2中與S1中分段點d2對應的點,D2是S2中與q點距離最近的分段點,若點q到D2的距離小于距離閾值T,則判定S2分段點D2與S1分段點d2相匹配.

規則2.設d3是S1中與S2中分段點D3對應的點,若S1中不存在與點d3的距離小于距離閾值T的分段點,則判定分段點D3與采樣點d3相匹配.

規則1和規則2中的距離閾值T=η×L,其中,L表示模板筆畫S1的長度,η為比例因子.

利用上述規則,糾偏后的分段點對應關系如圖10所示.

圖10 糾偏后的分割點對應關系Fig.10 Revised segmentation point corresponding

依據得到的分段點對應關系,采用式(7)計算筆畫間形狀差異.

圖11 以相鄰分割點構成的向量近似表示筆畫Fig.11 Stroke approximated by vectors consisting of adjacent segmentation points

按式(8)對所求四種差異值進行融合

其中,μ,σ分別表示在自建簽名筆跡數據庫上計算得到的所有對應筆畫間關于大小、位置、方位角和筆畫形狀差異的均值和方差.

2 實驗

本節在公共簽名數據庫SVC2004任務2數據集上驗證本文方法4個預設參數對匹配結果的影響.然后,將所獲得的最優閾值應用到SUSIG有視覺反饋數據集上,在SVC2004和SUSIG上,將本文方法的匹配結果與文獻[12,20?25,30]進行比較,以此檢驗本文方法的有效性.

SVC2004和SUSIG分別收集了40和100位用戶的真實簽名筆跡.為了體現簽名隨時間的波動性,兩個庫的組織者分兩次對每位用戶的簽名進行采集,采集間隔至少一周,每次各采集10個樣本.這樣,共獲得2800個樣本.

為了驗證匹配算法的準確性,將匹配結果與人工得到的理想匹配結果相比較.具體步驟為:對數據庫中每位用戶的20個真實簽名,任選其中1個作為模板樣本,剩下19個作為測試樣本.計算模板與每個測試樣本之間的關鍵點對應關系.然后,將其與人工得到的匹配結果進行比較.設

表示Patha中與距離之和最近的一對關鍵點對應關系,1≤j′≤n,Len(·,·)表示筆跡序列中兩個采樣點間的運筆長度.

式(11)或式(12)成立.

設匹配錯誤率

其中,c表示Patha中正確匹配個數.

圖12列出了4組由人工給出分割點的理想對應關系示例,圖中用星號表示分割點,星號旁邊的數字表示該分割點在關鍵點序列中的序號.兩個序號相同的分割點相對應.

圖12 由人工給出的四組筆跡分割點的理想對應關系Fig.12 Four group of ideal segmentation point corresponding

2.1 窗口寬度閾值選取實驗

本節討論式(1)中窗口寬度閾值w的選取對匹配結果的影響.設w=β×N,其中,N表示模板筆跡被分割的筆畫數.其他閾值預設為:采用式(1)列出的所有10種合并規則;T=0.1×L;P=u+3 ×σ;其中,L表示模板筆畫的長度,u,σ含義如第2.3節所述.不同β取值在SVC2004庫40組簽名上得到的平均匹配錯誤率如表1所示.

表1 β取值對平均匹配錯誤率(%)的影響Table 1 Average matching error rate(%)for various values of β

從表1可以看出,過小和過大的β取值,匹配錯誤率較高.因為過小的窗口寬度使本應正確的匹配筆畫被排除在窗口以外;而過大的窗口則引入了過多的錯誤匹配筆畫.當0.15≤β≤0.20時,β的取值對匹配結果影響不大,因為盡管多筆少筆普遍存在,但從以筆畫作為筆跡構成單位來看,多數人筆跡具有較好的書寫一致性,沒有出現嚴重的少筆多筆問題.因此相對較松的窗口閾值即可將正確的筆畫包含進來.

2.2 距離閾值選取實驗

本節討論距離閾值T=η×L選取對匹配結果的影響.基于第2.1節的實驗結果,設β=0.175,其他閾值的預設值與第2.1節所述相同.不同η取值在SVC2004庫40組簽名上得到的平均匹配錯誤率如表2所示.

表2 η取值對平均匹配錯誤率(%)的影響Table 2 Average matching error rate(%)for various values of η

從表2可以看出,在一個相對較小的閾值上,得到最小的匹配錯誤率.因為本文方法中DTW僅被應用于局部筆畫間的采樣點匹配.相對于全局筆跡匹配中普遍存在的嚴重錯誤累積問題,由于受限于筆畫長度,該問題并不明顯,因此給定較小的距離閾值即可將匹配錯誤糾正過來.實驗結果表明,當η=0.10時,算法得到最低的匹配錯誤率.

2.3 差異閾值選取實驗

本節討論式(1)中差異閾值P的選取對匹配結果的影響.設差異閾值P=u+ασ,其中,u,σ分別表示在自建簽名筆跡數據庫上計算得到的所有對應筆畫間差異值的均值和方差,α是比例因子.其中,自建簽名筆跡數據庫包含利用手寫板采集的34位書寫者的簽名筆跡,每位書寫者提供了30個真實簽名,共1020個真實簽名,以及針對每位書寫者10個專業偽造簽名和10個隨機偽造簽名,共680個偽造簽名.

基于前述實驗得到的最優窗口和距離閾值,調整比例因子α,采用式(1)列出的10種合并規則,在SVC2004庫40組簽名上得到的平均匹配錯誤率如表3所示.

表3 α取值對平均匹配錯誤率(%)的影響Table 3 Average matching error rate(%)for various values of α

從表3可以看出,隨著比例因子α的逐步增加,本文方法平均匹配錯誤率迅速降低.因為過小差異閾值使很多本應匹配的筆畫被排除在迭代候選項之外,從而造成匹配錯誤.隨著α的加大,錯誤率隨之降低.但隨著α的進一步加大,匹配錯誤率反而隨之增加.因為雖然過大的差異閾值能將書寫一致性較差的正確匹配包含進來,但是,由于式(1)中引入了過多合并規則,一些錯誤筆畫也被包含進來.若正確筆畫間的差異值在所有候選項中不是最小時,則產生匹配錯誤.

2.4 合并規則選取實驗

本節將對式(1)中列出的10個合并規則進行討論.關于少筆或多筆現象,由于多個少筆或多筆可用多個跳躍規則的疊加來處理,因此迭代過程采用式(1)中的[k]、[l]兩個跳躍規則即可.

依據前述實驗得到的3個最優閾值,在相同實驗條件下,依次增加合并規則,觀察到不同合并規則組合方案在SVC2004庫40組簽名上得到的平均匹配錯誤率如表4所示.

表4 不同合并規則對匹配錯誤率(%)的影響Table 4 Average matching error rate(%)for different merging rule combination schemes

從表4可以看出,起初隨著一步迭代方程中引入更多的合并規則,本文方法的平均匹配錯誤率逐步降低.說明本文引入的合并規則能較好地應對書寫中的不一致,從而得到正確的匹配結果.但是,當到達一定程度后,平均匹配錯誤率開始上升.因為如果本應匹配筆畫由于書寫的不一致,造成差異值過大,以至于大過錯誤匹配筆畫的差異值時,將發生匹配錯誤.特別是引入合并規則的個數越多,發生上述錯誤的可能性越大.此外,引入過多的合并規則還將增加計算量.

實驗結果表明,當采用方案4時,本文方法的平均匹配錯誤率達到最低.

2.5 筆畫差異量度比較實驗

基于前述實驗得到各個最優閾值和最優合并規則,將第1.2節所描述的筆畫差異度量方法與現有的方法[29?32]進行比較,在SVC2004庫40組簽名上的平均匹配錯誤率如表5所示.

從表5可以看出,本文方法能有效降低匹配錯誤率.對此的解釋是:本文方法更全面考慮了筆畫間各種差異,使得筆畫間的可區分性更強.圖13給出了在相同三組簽名上分別采用新差異度量方法和已有方法得到的匹配結果,其中,第1欄和第2欄是本文方法的匹配結果,第3欄和第4欄是已有方法的.第1欄和第3欄是模板筆跡,第2欄和第4欄是測試筆跡.圖13中以直線表示對應的筆畫,直線起點處的數字表示相應的筆畫序號,序號相同的直線相匹配.若直線起點處沒有數字則表示該筆畫沒有對應的匹配.如圖13中箭頭所示,已有方法在多處產生了匹配錯誤,而本文方法能克服多種書寫不一致,得到合理的匹配結果.例如箭頭A所示的第一組“王丹”筆跡的起始“橫豎”運筆處.顯然,模板筆跡中的“橫豎”運筆與測試筆跡中的“豎”畫運筆是存在明顯差異的,然而已有方法得到的筆畫“橫豎”與“豎”間的差異卻比“豎”與“豎”間的小,致使隨后的迭代過程選取了錯誤匹配路徑.同樣的錯誤還出現在箭頭B到F處.本文方法由于更全面反映了筆畫間差異,避免了上述錯誤,得到正確的筆畫對應關系.

表5 本文筆畫差異度量方法與已有方法比較Table 5 Comparison of the proposed stroke difference measurement method and the existing method

圖13 本文方法和已有筆畫差異度量方法在匹配結果上的比較(第1欄和第2欄給出了本文方法的匹配結果示例,第3欄和第4欄給出了相同筆跡在已有方法上的匹配結果示例)Fig.13 Comparison of matching results based on stroke difference measurement between the proposed (the 1 and 2 columns)and existing methods(the 3 and 4 columns)

2.6 匹配結果比較實驗

將本文方法在SVC2004和SUSIG兩個公共簽名數據庫上,與已有筆跡匹配方法進行比較,以此驗證本文方法的準確性和魯棒性,以及多個先驗閾值設定的有效性.將SVC2004和SUSIG數據庫每個用戶的簽名按字形一致性,從高到低人為地分為4組.分組數據如表6和表7所示.為了方便比較,在同一實驗平臺上(Windows7.0,Matlab2007b,4GB內存,4核2.4GHz CPU)編程分別實現了本文及公開文獻中給出的幾種主要筆跡匹配算法[12,20?25,30].在每一組簽名上,將本文方法與已有方法的匹配結果進行比較,平均匹配錯誤率如表8所示.

從表8可以看出,在兩個數據庫的每一組簽名上,本文方法均獲得最小的匹配錯誤率.說明本文方法的匹配準確性和魯棒性是最好的.圖14和圖15分別給出了本文方法與已有方法在兩個公共簽名數據庫上的匹配結果示例.圖中,第1欄和第2欄為本文方法的匹配結果,第3欄和第4欄為相同筆跡在已有方法上的匹配結果.圖14和圖15中各種符號含義與圖12和圖13相同.圖14和圖15中用箭頭標出了造成現有方法出現匹配錯誤的兩類原因:1)不一致的筆跡分割,主要表現為落筆時的抖動(A,T)、轉折處的頓筆造成的關鍵點多提取(E,D,J,R,U, W)、連筆處的虛提筆(I)、圓滑轉筆造成的關鍵點漏提取(G,P)、偽關鍵點提取(K);2)各種不一致的運筆,主要有不一致的筆順(B)、多筆、少筆(C, F,L,Q,S)、一致性較差的小碎筆(H,M,N)、簡化筆(O,V).通常情況下,上述現象是混合出現的,這進一步增加了解決匹配問題的困難程度.

表6 SVC2004的簽名分組表Table 6 SVC2004 signature group table

表7 SUSIG的簽名分組表Table 7 SUSIG signature group table

表8 在SVC2004和SUSIG上,本文方法與已有方法在4組筆跡上平均匹配錯誤率(%)比較Table 8 Average matching error rate(%)comparison on four group signatures between our method and existing methods on SVC2004 and SUSIG

如表8與圖14和圖15中第1欄和第2欄所示,在SVC2004和SUSIG兩個公共簽名數據庫上,與現有方法相比較,本文方法在匹配準確性和魯棒性上均有明顯提升.這是由于:1)本文提出了“采用視覺關鍵點分割+基于多特征融合的筆畫相似性度量”的技術方案,在度量筆畫相似性方面,提出了一種單純形狀差異的度量方法.雖然現有方法也主張進行分段,但大多利用X和Y分量的極大極小值對一維時序信息進行分割[12,20?25,30],在分別建立上述兩種序列的波形極值點對應關系后,再通過一組規則來推導得到二維筆畫的對應關系[22].波形對應規則看似簡單直觀(波峰對波峰、波谷對波谷),但是由于波形包含的信息量有限(峰谷大小、位置),從而在匹配峰谷大小相似但個數不同的兩組時序信號時,極易產生錯誤匹配(這種情況在英文簽名中尤為常見,例如圖15中箭頭P、U所示).接下來在推導二維筆畫對應關系時,由于每組規則均引入了先驗的閾值參數,因而在處理各種復雜的書寫不一致情況時,很難設定統一的閾值以使得算法魯棒.基于上述問題,直接利用二維筆畫特征來構造目標函數的方法被提出來.例如利用分段點的開口類型特征[12,23],利用筆畫的(X,Y)[12,21,30]、速度[21,30]、角度[25]、曲率[12]的差異值特征.如前文所述,由于書寫活動的細膩性,僅依靠上述信息很難有效地反映筆畫間所包含的細微差異.第2.5節筆畫差異值度量實驗結果表明,簡單利用筆畫的某一特征很難將其中的差異真實反映出來.這樣的直接結果就是算法將兩段看起來差異明顯的筆畫而不是更為相似的筆畫匹配起來(例如圖13中箭頭A,B,C,D,E,F所示).相對于現有方法,本文技術方案的優點有:a)省去了兩次計算一維極值點匹配再求二維關鍵點匹配的步驟;b)相較于波形,平面中筆畫所包含的豐富信息有利于描述它們間的差異;c)筆畫特征的直觀性使得本文方法將多種物理意義明確的合并和跳躍規則引入到優化過程中來.2)基于融合多特征的筆畫差異度量方法構造的目標函數,本文提出了將跳躍和合并規則引入到尋優過程,以應對各種復雜的書寫不一致.雖然也用到了合并規則(2對1、1對2規則)[22?24],但受限于X,Y分量對筆畫差異反映的間接性,文獻中的合并規則只是被用來應對因書寫中的頓筆、抖動而產生的X,Y分量偽波峰問題[22?24].更復雜的多筆、漏筆、簡化筆、異化筆等書寫不一致則無力應對(例如圖14和圖15中箭頭C,F,H,N,O,V所示).與此相反,本文直接提取筆畫特征,得益于筆畫特征的直觀性,更加豐富(1對1、2對1等10種規則)且物理含義明確的合并規則被引入到尋優過程中.受益于不同類型的筆畫在差異值特征上表現出來的可區分性,例如撇畫和捺畫的方位角特征,使得跳躍規則被引入尋優過程中以應對多筆、漏筆問題.由于新筆畫特征度量更真實地體現了筆畫本身所具有的差異,使得算法在面對如式(1)所示的多個候選匹配項時,選取的差異值最小項最有可能為正確的匹配結果(例如圖14和圖15中左邊兩列所示).

圖14 本文方法與現有方法在SVC2004上匹配結果示例Fig.14 Examples of matching result obtained by the proposed and the existing methods on SVC2004

如圖14中第1行第2列“劉”字中的第一筆是因虛落筆而多出來的“提筆畫”.該提筆與前后筆畫均存在較大差異,以至于在如式(1)所示的所有合并規則中,基于新筆畫度量方法得到的該筆畫與前后對應筆畫的差異值均大于閾值P,這樣跳躍規則被執行.最終本文方法成功地將該多出的筆畫分辯出來.由于未引入跳躍規則,現有方法需強行找一個與該多筆對應的筆畫,因此導致匹配錯誤.進一步,該錯誤被傳導到后繼匹配而導致連鎖反應,例如圖14中箭頭A、B所示.

相似的因多筆引起的匹配錯誤如圖14中箭頭C所示,本來應該合并模板筆跡(圖14第2行第3列)中的第16～17、17～18、18～20段與測試筆跡(圖14第2行第4列)中的第19～20段相匹配(這里的數字表示圖中關鍵點的序號),然而由于現有算法沒有引入合并規則,從而致使匹配錯誤;與之相反,在本文方法中,由于引入了多種合并規則并且新的筆畫差異度量方法計算的差異值在所有合并規則中最小,從而使得期望的合理匹配被尋優方法選中,最終輸出正確的匹配結果.

因快速運筆導致的分割點漏提取例子如圖15第3行第1列和第2列所示.圖中第1列第10段筆畫由于快速書寫,本應提取的兩個關鍵點被漏提取.但是由于本文方法引入了合并規則并且根據正確合并規則(第3行第1列中的第10段筆畫與第2列中的由3個子段組成的第10段筆畫相匹配)得到的差異值在所有合并規則中最小,因而輸出正確的匹配結果.與此相反,從圖15第3行第3列和第4列給出的已有方法的匹配結果可以看出,由于同樣的原因,已有方法未能輸出正確匹配結果.

由于本文引入的合并規則、跳躍規則和有效的筆畫差異度量方法,在面對因小碎筆(圖14和圖15中箭頭H,M,N所示)和簡化筆(圖15中箭頭O, V所示)導致的分割不一致問題時,本文方法均輸出了正確的匹配結果(本文方法的匹配結果如圖14和圖15中相同行的第1行和第2行所示).本文方法得到正確匹配的原因與前述多筆、分割點漏提取的相同.

圖15 本文方法與現有方法在SUSIG上匹配結果示例Fig.15 Examples of matching result obtained by the proposed and the existing methods on SUSIG

2.7 本文方法存在的問題及不足

本文方法存在以下不足及有待解決的問題:1)如圖16第1行所示,若筆跡中包含如“ABAB”這樣特征相似的筆畫組,如筆跡“軍”字中的“橫折橫折”運筆,且“橫”筆畫出現在兩個筆跡中的次數不一致時,可能出現匹配錯誤.圖16第1行中兩個簽名匹配錯誤的原因在于測試筆跡中第1個橫折畫與其他位置處的橫折畫在長度和形狀上更一致.2)本文算法的匹配結果受閾值P的影響較大.不合理的設定可能產生這樣的錯誤:本應跳過的筆畫未被跳過,或者相反.如圖16第2行所示,兩個“王”字筆跡在起筆處均有抖動,由于抖筆長度、形態相差過大,使得本應匹配的筆畫被跳過.在下個迭代步驟中,測試筆跡中本應跳過的抖筆,由于模板筆跡中的“橫”與測試筆跡中的“抖橫”間差異過小,從而產生錯誤匹配.

圖16 本文方法存在的問題和不足示例Fig.16 Examples of remaining shortcomings of our method

3 總結與展望

面對因分割不一致造成的筆跡匹配算法魯棒性不強的問題,本文提出一種引入合并規則和跳躍規則的動態規劃方法,并采用筆畫特征,特別是筆畫間單純意義上的形態差異特征來計算累計差異值矩陣.匹配結果表明,本文方法能有效克服多種書寫不一致,例如多筆、漏筆、簡化筆、異化筆等,進而得到魯棒的筆畫對應關系.在SVC2004和SUSIG簽名數據庫上,與同類匹配算法的實驗結果驗證了本文方法的有效性.

基于匹配結果,除了采用DTW簡單地計算對應筆畫間各種信號的差異值特征,還可以進一步挖掘其他的筆畫特征,例如起落筆方式、筆畫運筆方式、筆畫間轉折承接方式、筆跡整體結構布局、筆畫間相對位置關系等重要特征,從而提升系統認證性能.

1 Mohammed R A,Nabi R M,Mahmood S M R,Nabi R M. State-of-the-art in handwritten signature verification system.In:Proceedings of the 2015 International Conference on Computational Science and Computational Intelligence. Las Vegas,NV:IEEE,2015.519?525

2 Yu J,Wang Z F.A video,text,and speech-driven realistic 3-D virtual head for human-machine interface.IEEE Transactions on Cybernetics,2015,45(5):991?1002

3 Li Xin,Ding Xiao-Qing,Peng Liang-Rui.A microstructure feature based text-independent method of writer identification for multilingual handwritings.Acta Automatica Sinica, 2009,35(9):1199?1208 (李昕,丁曉青,彭良瑞.一種基于微結構特征的多文種文本無關筆跡鑒別方法.自動化學報,2009,35(9):1199?1208)

4 Chen Xiao-Su,Wu Zhen-Hua,Xiao Dao-Ju.Off-line Chinese signature verification based on segmentation and HMM. Acta Automatica Sinica,2007,32(2):205?210 (陳曉蘇,吳振華,肖道舉.一種基于簽名分段和HMM的離線中文簽名驗證方法.自動化學報,2007,32(2):205?210)

5 Liu Y S,Yang Z H,Yang L H.Online signature verification based on DCT and sparse representation.IEEE Transactions on Cybernetics,2015,45(11):2498?2511

7 Nautsch A,Rathgeb C,Busch C.Bridging gaps:an application of feature warping to online signature verification.In: Proceedings of the 2014 International Carnahan Conference on Security Technology(ICCST).Rome,Italy:IEEE,2014. 1?6

8 Jiao Hui-Min,Wang Dang-Xiao,Zhang Yu-Ru,Fang Lei. Signature verification using handwriting friction force.Acta Automatica Sinica,2011,37(7):883?890 (焦慧敏,王黨校,張玉茹,方磊.基于書寫摩擦力的簽名識別方法.自動化學報,2011,37(7):883?890)

9 Pirlo G,Cuccovillo V,Impedovo D,Mignone P.On-line signature verification by multi-domain classification.In:Proceedings of the 14th International Conference on Frontiers in Handwriting Recognition(ICFHR).Heraklion,Greece: IEEE,2014.67?72

10 Wang Zi-He.Identification of Practicing Imitating Handwriting[Master dissertation],Southwest University of Political Science and Law,China,2010. (王梓合.練習摹仿筆跡鑒定研究[碩士學位論文],西南政法大學,中國,2010.)

11 Ansari A Q,Kour J.Uniform segmentation in online signature verification.In:Proceedings of the 2015 Annual IEEE India Conference.New Delhi,India:IEEE,2015.1?6

12 Wang K Y,Wang Y H,Zhang Z X.On-line signature verification using segment-to-segment graph matching.In:Proceedings of the 2011 International Conference on Document Analysis and Recognition.Beijing,China:IEEE,2011.804?808

13 Wirotius M,Ramel J Y,Vincent N.Selection of points for on-line signature comparison.In:Proceedings of the 9th International Workshop on Frontiers in Handwriting Recognition(IWFHR).Tokyo,Japan:IEEE,2004.503?508

14 CaiHong-Bin,ShiZe-Sheng,FanXiao-Feng,Huang Hao,Yin She-Guang.A handwritten signature verification method based on wavelet transform to pick up inflection points.Journal of Image and Graphics,2003,8(3):261?265 (蔡洪濱,施澤生,范曉峰,黃浩,尹社廣.一種基于小波變換提取拐點的手寫簽名認證方法.中國圖象圖形學報,2003,8(3):261?265)

17 Guo Hong,Jin Xian-Ji.The extract algorithm of special points in signature based on dynamic information.Journal of Wuhan University of Science and Technology(Natural Science Edition),2001,24(2):186?188 (郭宏,金先級.一種基于簽名動態特征的特殊點提取算法.武漢科技大學學報(自然科學版),2001,24(2):186?188)

18 Brault J J,Plamondon R.Segmenting handwritten signatures at their perceptually important points.IEEE Transactions on Pattern Analysis and Machine Intelligence,1993, 15(9):953?957

19 Quan Zhong-Hua.A Study of the Authentication Based on Online Signatures[Ph.D.dissertation],University of Science and Technology of China,China,2007. (全中華.基于動態手寫簽名的身份認證研究[博士學位論文],中國科學技術大學,中國,2007.)

20 Quan Z H,Ji H W.Aligning and segmenting signatures at their crucial points through DTW.In:Proceedings of the 2005 International Conference on Intelligent Computing.Hefei,China:Springer,2005.49?58

21 Mohammadi M H,Faez K.Matching between important points using dynamic time warping for online signature verification[Online],available:http://www.cyberjournals.com/ Papers/Jan2012/01.pdf,June 24,2016

22 Li B,Zhang D,Wang K Q.Improved critical point correspondence for on-line signature verification.International Journal of Information Technology,2006,12(7):45?56

23 Lee J,Yoon H S,Soh J,Chun B T,Chung Y K.Using geometric extrema for segment-to-segment characteristics comparison in online signature verification.Pattern Recognition, 2004,37(1):93?103

24 Hao F,Chan C W.Online signature verification using a new extreme points warping technique.Pattern Recognition Letter,2003,24(16):2943?2951

25 Barkoula K,Economou G,Fotopoulos S.Online signature verification based on signatures turning angle representation using longest common subsequence matching.International Journal on Document Analysis and Recognition, 2013,16(3):261?272

26 Zhang K,Pratikakis I,Cornelis J,Nyssen E.Using landmarks to establish a point-to-point correspondence between signatures.Pattern Analysis and Applications,2000,3(1): 69?75

27 Ansari A Q,Hanmandlu M,Kour J,Singh A K.Online signature verification using segment-level fuzzy modelling.IET Biometrics,2014,3(3):113?127

28 Li Bin.Research on the Technology of Online Handwritten Signature Verification.[Ph.D.dissertation],Harbin Institute of Technology,China,2006. (李彬.聯機手寫簽名鑒別技術的研究[博士學位論文],哈爾濱工業大學,中國,2006.)

29 Ibrahim M T,Khan M A,Alimgeer K S,Khan M K,Taj I A, Guan L.Velocity and pressure-based partitions of horizontal and vertical trajectories for on-line signature verification. Pattern Recognition,2010,43(8):2817?2832

31 Kholmatov A,Yanikoglu B.Identity authentication using improved online signature verification method.Pattern Recognition Letters,2005,26(15):2400?2408

32 Kar B,Dutta P K,Basu T K,VielHauer C,Dittmann J. DTW based verification scheme of biometric signatures.In: Proceedings of the 2006 IEEE International Conference on Industrial Technology.Mumbai,India:IEEE,2006.381?386

33 Yeung D Y,George S,Kashi R,Matsumoto T,Rigoll G. SVC 2004:first international signature verification competition[Online],available:http://www.cse.ust.hk/svc2004, June 24,2016

34 Kholmatov A,Yanikoglu B.SUSIG:an on-line signature database,associated protocols and benchmark results.Pattern Analysis and Applications,2009,12(3):227?236

35 Sakoe H,Chiba S.Dynamic programming algorithm optimization for spoken word recognition.IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1): 43?49

36 Fischer A,Diaz M,Plamondon R,Ferrer M A.Robust score normalization for DTW-based on-line signature verification. In:Proceedings of the 13th International Conference on Document Analysis and Recognition(ICDAR).Tunis,Italy: IEEE,2015.241?245

37 Fang P,Wu Z C,Meng M,Ge Y J,Yu Y.A novel tablet for on-line handwriting signal capture.In:Proceedings of the 5th World Congress on Intelligent Control and Automation. Hangzhou,China:IEEE,2004.3714?3717

鄒 杰 博士,武漢工商學院計算機科學與技術系講師.主要研究方向為模式識別,在線筆跡身份認證和圖像處理.

E-mail:qvbso@mail.ustc.edu.cn

(ZOU Jie Ph.D.,lecturer in the Department of Computer Science and Technology,Wuhan Technology and Business University.His research interest covers pattern recognition,online handwriting verification,and image processing.)

孫寶林 博士,武漢工商學院計算機科學與技術系教授.主要研究方向為現場總線和實時以太網.

E-mail:blsun@163.com

(SUN Bao-Lin Ph.D.,professor in the Department of Computer Science and Technology,Wuhan Technology and Business University.His research interest covers field bus and real-time Etherent.)

於 俊 博士,中國科學技術大學自動化系副研究員.主要研究方向為智能人機交互和智能機器人.本文通信作者.

E-mail:harryjun@ustc.edu.cn

(YU Jun Ph.D.,associate professor in the Department of Automation,University of Science and Technology of China.His research interest covers human computer interaction and intelligent robot.Corresponding author of this paper.)

Online Handwriting Matching Algorithm Based on Stroke Features

ZOU Jie1,2SUN Bao-Lin2YU Jun1

To solve the robustness problem of online handwriting matching,a novel method is proposed in which the jumping and merging rules are introduced to the iterative step of dynamic programming.Specifically,jumping rules are used to deal with the superfluous and loss strokes while merging rules are used to deal with inconsistent handwriting segmentation caused by jerk,hesitating,compound-strokes,etc.In calculation of the cumulative difference matrix,a new measurement is proposed in which stroke shape information is applied to measuring stroke differences.The matching results calculated by the proposed method are compared to those of the existing main methods on SVC2004 and SUSIG public signatures databases.It is shown that the new method can obtain better accuracy and more robust stroke correspondence with respect to various local writings and segmentation inconsistency.

Online handwriting verification,handwriting matching,stroke difference measurement,dynamic programming

鄒杰,孫寶林,於俊.基于筆畫特征的在線筆跡匹配算法.自動化學報,2016,42(11):1744?1757

Zou Jie,Sun Bao-Lin,Yu Jun.Online handwriting matching algorithm based on stroke features.Acta Automatica Sinica,2016,42(11):1744?1757

2015-09-06 錄用日期2016-06-22

Manuscript received September 6,2015;accepted June 22,2016

國家自然科學基金(61572012,61303150),中央高校基本科研業務費專項資金重要方向培育基金項目(WK2350000002),湖北省自然科學基金重點項目(2014CFA055),湖北省高等學校優秀中青年科技創新團隊計劃項目(T201631),浙江大學計算機輔助與圖形學國家重點實驗室開放課題(A1501)資助

Supported by National Natural Science Foundation of China (61572012,61303150),the Fundamental Research Funds for the Central Universities(WK2350000002),the Key Project Natural Science Foundation of Hubei Province(2014CFA055),Hubei Province High School Outstanding Young Science and Technology Innovation Team Project(T201631),and the Open Project Program of the State Key Laboratory of CAD and CG of Zhejiang University(A1501)

本文責任編委桑農

Recommended by Associate Editor SANG Nong

1.中國科學技術大學自動化系合肥 230027 2.武漢工商學院計算機科學與技術系武漢430065

1.Department of Automation,University of Science and Technology of China,Hefei 230027 2.Department of Computer Science and Technology,Wuhan Technology and Business University,Wuhan 430065

DOI 10.16383/j.aas.2016.c150563