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

鄒杰 孫寶林 於俊

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

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

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

在線筆跡認(rèn)證,筆跡匹配,筆畫差異值度量,動(dòng)態(tài)規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

建立筆畫間對應(yīng)關(guān)系問題可描述為:對于模板和測試筆跡筆畫序列,在時(shí)序性約束條件下,在所有可能的筆畫對應(yīng)關(guān)系序列中,尋找一個(gè)使筆畫間累計(jì)差異值之和最小的筆畫對應(yīng)關(guān)系序列.

考慮到求解過程的復(fù)雜度,一種基于迭代的動(dòng)態(tài)規(guī)劃方法被引入進(jìn)來[35].其中,采用何種規(guī)則來計(jì)算累計(jì)差異值矩陣D成為匹配算法是否準(zhǔn)確和魯棒的關(guān)鍵.

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

1.1 筆跡匹配步驟

筆跡匹配步驟如下:

步驟1.按Brault等提出的視覺關(guān)鍵點(diǎn)將筆跡按筆畫進(jìn)行分割[18],得到筆畫序列.兩個(gè)按視覺關(guān)鍵點(diǎn)分割后的筆跡如圖1所示.

圖1 按視覺關(guān)鍵點(diǎn)得到的筆跡分割結(jié)果示例Fig.1 Examples of handwriting segmented by perceptually important points

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

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

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

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

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

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

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

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

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

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

顯然,引入越多的合并規(guī)則,算法應(yīng)對各種復(fù)雜不一致的能力越強(qiáng).但是合并規(guī)則越多,算法復(fù)雜度越高,產(chǎn)生過匹配[24]的可能性越大.

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

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

步驟4.從DNM開始,依據(jù)被選取的合并規(guī)則和跳躍規(guī)則,回溯得到筆畫對應(yīng)關(guān)系.

1.2 筆畫差異度量

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

1)大小差異度量

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

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

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

3)方位角差異度量

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

4)形狀差異

形狀差異是指除去筆畫間的大小、方位、位置差異后,單純從形態(tài)上所體現(xiàn)的差異.本文采用關(guān)鍵點(diǎn)的對應(yīng)關(guān)系來度量形狀差異.

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

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

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

步驟3.采用經(jīng)典DTW算法計(jì)算筆畫S1與S2的點(diǎn)點(diǎn)對應(yīng)關(guān)系[35].結(jié)果如圖9所示.

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

圖9 采用經(jīng)典DTW得到的點(diǎn)點(diǎn)對應(yīng)關(guān)系Fig.9 Point-to-point corresponding calculated by the classical DTW

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

規(guī)則1.設(shè)q是S2中與S1中分段點(diǎn)d2對應(yīng)的點(diǎn),D2是S2中與q點(diǎn)距離最近的分段點(diǎn),若點(diǎn)q到D2的距離小于距離閾值T,則判定S2分段點(diǎn)D2與S1分段點(diǎn)d2相匹配.

規(guī)則2.設(shè)d3是S1中與S2中分段點(diǎn)D3對應(yīng)的點(diǎn),若S1中不存在與點(diǎn)d3的距離小于距離閾值T的分段點(diǎn),則判定分段點(diǎn)D3與采樣點(diǎn)d3相匹配.

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

利用上述規(guī)則,糾偏后的分段點(diǎn)對應(yīng)關(guān)系如圖10所示.

圖10 糾偏后的分割點(diǎn)對應(yīng)關(guān)系Fig.10 Revised segmentation point corresponding

依據(jù)得到的分段點(diǎn)對應(yīng)關(guān)系,采用式(7)計(jì)算筆畫間形狀差異.

圖11 以相鄰分割點(diǎn)構(gòu)成的向量近似表示筆畫Fig.11 Stroke approximated by vectors consisting of adjacent segmentation points

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

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

2 實(shí)驗(yàn)

本節(jié)在公共簽名數(shù)據(jù)庫SVC2004任務(wù)2數(shù)據(jù)集上驗(yàn)證本文方法4個(gè)預(yù)設(shè)參數(shù)對匹配結(jié)果的影響.然后,將所獲得的最優(yōu)閾值應(yīng)用到SUSIG有視覺反饋數(shù)據(jù)集上,在SVC2004和SUSIG上,將本文方法的匹配結(jié)果與文獻(xiàn)[12,20?25,30]進(jìn)行比較,以此檢驗(yàn)本文方法的有效性.

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

為了驗(yàn)證匹配算法的準(zhǔn)確性,將匹配結(jié)果與人工得到的理想匹配結(jié)果相比較.具體步驟為:對數(shù)據(jù)庫中每位用戶的20個(gè)真實(shí)簽名,任選其中1個(gè)作為模板樣本,剩下19個(gè)作為測試樣本.計(jì)算模板與每個(gè)測試樣本之間的關(guān)鍵點(diǎn)對應(yīng)關(guān)系.然后,將其與人工得到的匹配結(jié)果進(jìn)行比較.設(shè)

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

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

設(shè)匹配錯(cuò)誤率

其中,c表示Patha中正確匹配個(gè)數(shù).

圖12列出了4組由人工給出分割點(diǎn)的理想對應(yīng)關(guān)系示例,圖中用星號表示分割點(diǎn),星號旁邊的數(shù)字表示該分割點(diǎn)在關(guān)鍵點(diǎn)序列中的序號.兩個(gè)序號相同的分割點(diǎn)相對應(yīng).

圖12 由人工給出的四組筆跡分割點(diǎn)的理想對應(yīng)關(guān)系Fig.12 Four group of ideal segmentation point corresponding

2.1 窗口寬度閾值選取實(shí)驗(yàn)

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

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

從表1可以看出,過小和過大的β取值,匹配錯(cuò)誤率較高.因?yàn)檫^小的窗口寬度使本應(yīng)正確的匹配筆畫被排除在窗口以外;而過大的窗口則引入了過多的錯(cuò)誤匹配筆畫.當(dāng)0.15≤β≤0.20時(shí),β的取值對匹配結(jié)果影響不大,因?yàn)楸M管多筆少筆普遍存在,但從以筆畫作為筆跡構(gòu)成單位來看,多數(shù)人筆跡具有較好的書寫一致性,沒有出現(xiàn)嚴(yán)重的少筆多筆問題.因此相對較松的窗口閾值即可將正確的筆畫包含進(jìn)來.

2.2 距離閾值選取實(shí)驗(yàn)

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

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

從表2可以看出,在一個(gè)相對較小的閾值上,得到最小的匹配錯(cuò)誤率.因?yàn)楸疚姆椒ㄖ蠨TW僅被應(yīng)用于局部筆畫間的采樣點(diǎn)匹配.相對于全局筆跡匹配中普遍存在的嚴(yán)重錯(cuò)誤累積問題,由于受限于筆畫長度,該問題并不明顯,因此給定較小的距離閾值即可將匹配錯(cuò)誤糾正過來.實(shí)驗(yàn)結(jié)果表明,當(dāng)η=0.10時(shí),算法得到最低的匹配錯(cuò)誤率.

2.3 差異閾值選取實(shí)驗(yàn)

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

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

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

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

2.4 合并規(guī)則選取實(shí)驗(yàn)

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

依據(jù)前述實(shí)驗(yàn)得到的3個(gè)最優(yōu)閾值,在相同實(shí)驗(yàn)條件下,依次增加合并規(guī)則,觀察到不同合并規(guī)則組合方案在SVC2004庫40組簽名上得到的平均匹配錯(cuò)誤率如表4所示.

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

從表4可以看出,起初隨著一步迭代方程中引入更多的合并規(guī)則,本文方法的平均匹配錯(cuò)誤率逐步降低.說明本文引入的合并規(guī)則能較好地應(yīng)對書寫中的不一致,從而得到正確的匹配結(jié)果.但是,當(dāng)?shù)竭_(dá)一定程度后,平均匹配錯(cuò)誤率開始上升.因?yàn)槿绻緫?yīng)匹配筆畫由于書寫的不一致,造成差異值過大,以至于大過錯(cuò)誤匹配筆畫的差異值時(shí),將發(fā)生匹配錯(cuò)誤.特別是引入合并規(guī)則的個(gè)數(shù)越多,發(fā)生上述錯(cuò)誤的可能性越大.此外,引入過多的合并規(guī)則還將增加計(jì)算量.

實(shí)驗(yàn)結(jié)果表明,當(dāng)采用方案4時(shí),本文方法的平均匹配錯(cuò)誤率達(dá)到最低.

2.5 筆畫差異量度比較實(shí)驗(yàn)

基于前述實(shí)驗(yàn)得到各個(gè)最優(yōu)閾值和最優(yōu)合并規(guī)則,將第1.2節(jié)所描述的筆畫差異度量方法與現(xiàn)有的方法[29?32]進(jìn)行比較,在SVC2004庫40組簽名上的平均匹配錯(cuò)誤率如表5所示.

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

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

圖13 本文方法和已有筆畫差異度量方法在匹配結(jié)果上的比較(第1欄和第2欄給出了本文方法的匹配結(jié)果示例,第3欄和第4欄給出了相同筆跡在已有方法上的匹配結(jié)果示例)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 匹配結(jié)果比較實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)與展望

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

基于匹配結(jié)果,除了采用DTW簡單地計(jì)算對應(yīng)筆畫間各種信號的差異值特征,還可以進(jìn)一步挖掘其他的筆畫特征,例如起落筆方式、筆畫運(yùn)筆方式、筆畫間轉(zhuǎn)折承接方式、筆跡整體結(jié)構(gòu)布局、筆畫間相對位置關(guān)系等重要特征,從而提升系統(tǒng)認(rèn)證性能.

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 (李昕,丁曉青,彭良瑞.一種基于微結(jié)構(gòu)特征的多文種文本無關(guān)筆跡鑒別方法.自動(dòng)化學(xué)報(bào),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的離線中文簽名驗(yàn)證方法.自動(dòng)化學(xué)報(bào),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 (焦慧敏,王黨校,張玉茹,方磊.基于書寫摩擦力的簽名識(shí)別方法.自動(dòng)化學(xué)報(bào),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. (王梓合.練習(xí)摹仿筆跡鑒定研究[碩士學(xué)位論文],西南政法大學(xué),中國,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 (蔡洪濱,施澤生,范曉峰,黃浩,尹社廣.一種基于小波變換提取拐點(diǎn)的手寫簽名認(rèn)證方法.中國圖象圖形學(xué)報(bào),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 (郭宏,金先級.一種基于簽名動(dòng)態(tài)特征的特殊點(diǎn)提取算法.武漢科技大學(xué)學(xué)報(bào)(自然科學(xué)版),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. (全中華.基于動(dòng)態(tài)手寫簽名的身份認(rèn)證研究[博士學(xué)位論文],中國科學(xué)技術(shù)大學(xué),中國,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. (李彬.聯(lián)機(jī)手寫簽名鑒別技術(shù)的研究[博士學(xué)位論文],哈爾濱工業(yè)大學(xué),中國,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

鄒 杰 博士,武漢工商學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系講師.主要研究方向?yàn)槟Ｊ阶R(shí)別,在線筆跡身份認(rèn)證和圖像處理.

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.)

孫寶林 博士,武漢工商學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系教授.主要研究方向?yàn)楝F(xiàn)場總線和實(shí)時(shí)以太網(wǎng).

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.)

於 俊 博士,中國科學(xué)技術(shù)大學(xué)自動(dòng)化系副研究員.主要研究方向?yàn)橹悄苋藱C(jī)交互和智能機(jī)器人.本文通信作者.

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

鄒杰,孫寶林,於俊.基于筆畫特征的在線筆跡匹配算法.自動(dòng)化學(xué)報(bào),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

國家自然科學(xué)基金(61572012,61303150),中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金重要方向培育基金項(xiàng)目(WK2350000002),湖北省自然科學(xué)基金重點(diǎn)項(xiàng)目(2014CFA055),湖北省高等學(xué)校優(yōu)秀中青年科技創(chuàng)新團(tuán)隊(duì)計(jì)劃項(xiàng)目(T201631),浙江大學(xué)計(jì)算機(jī)輔助與圖形學(xué)國家重點(diǎn)實(shí)驗(yàn)室開放課題(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)

本文責(zé)任編委桑農(nóng)

Recommended by Associate Editor SANG Nong

1.中國科學(xué)技術(shù)大學(xué)自動(dòng)化系合肥 230027 2.武漢工商學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系武漢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