Cviˇcen´ı z pˇredmˇetu Biometrie ´ Uloha: Verifikace osoby pomoc´ı dynamick´eho podpisu Jiˇr´ı Wild, Jakub Schneider kontaktn´ı email:
[email protected] 5. ˇr´ıjna 2015
1
´ Uvod
´ Uloha m´a za c´ıl sezn´amit v´as s metodami verifikace identity ˇclovˇeka pomoc´ı jeho dynamick´eho podpisu. J´adro verifikaˇcn´ıch metod leˇz´ı ve srovn´av´an´ı verifikovan´eho podpisu s ovˇeˇren´ ymi pˇredlohami pouˇzit´ım r˚ uzn´ ych algoritm˚ u. Dva takov´e algoritmy budou tvoˇrit j´adro cviˇcen´ı — algoritmus zaloˇzen´ y na statistick´em modelov´an´ı Gaussian Mixture Model (GMM) a algoritmus urˇcuj´ıc´ı m´ıru podobnosti dvou sekvenc´ı Dynamic Time Warping (DTW). K u ´loze byl vytvoˇren Signature Toolbox pro Matlab, kter´ y obsahuje z´akladn´ı funkce s naimplementovan´ ym algoritmem GMM a pˇripravenou funkc´ı pro DTW, kterou, pro hlubˇs´ı pochopen´ı, bude u ´kolem implementovat. Oba algoritmy budou porovn´any chybovost´ı nad datab´az´ı podpis˚ u SVC2004 (popis v [3]). Posledn´ım u ´kolem bude falsifikovat vybran´ y podpis a urˇcit u ´spˇeˇsnost.
2
Teorie
Kaˇzd´ y zn´a klasick´ y podpis jako bˇeˇznˇe uˇz´ıvanou biometrickou veliˇcinu pro stvrzen´ı a ovˇeˇren´ı pravosti dokument˚ u. Dynamick´ y podpis je rozˇs´ıˇren´ım klasick´eho podpisu sn´ıman´ y elektronicky, ˇc´ımˇz pˇrid´av´a ˇcasovou informaci o z´apisu a informace o pˇr´ıtlaku nebo n´aklonu a natoˇcen´ı pera. Ze dvou z´akladn´ıch pouˇzit´ı biometrick´ ych veliˇcin pro identifikaci nebo verifikaci se podpis uplatˇ nuje v´ yhradnˇe pro verifikaci. Verifikac´ı je myˇslena procedura ovˇeˇren´ı totoˇznost ˇclovˇeka podle jeho podpisu. Vstupem verifikaˇcn´ı procedury je tedy podpis a identifikace osoby hl´as´ıc´ı se k podpisu. Pot´e je potˇreba m´ıt z tr´enovac´ı mnoˇziny (vˇetˇsinou ˇc´ıtaj´ıc´ı okolo deseti podpis˚ u u nichˇz m´ame ovˇeˇren´ y p˚ uvod) vytvoˇren´ y model podpisu. Vˇetˇs´ı mnoˇzstv´ı podpis˚ u potlaˇcuje intervariabilitu v podpisech jedn´e osoby. Model pˇr´ısluˇs´ıc´ı k ovˇeˇrovan´e identitˇe je pot´e srovn´av´an se vstupn´ım podpisem, v naˇsem pˇr´ıpadˇe pomoc´ı algoritm˚ u GMM a DTW, a z v´ ysledn´e m´ıry podobnosti je rozhodnuto o pravosti podpisu. Pr´ah pro zam´ıtnut´ı podpisu je urˇcen pˇri tvorbˇe modelu tak, aby pomˇery faleˇsnˇe zam´ıtnut´ ych prav´ ych podpis˚ u (FRR) a faleˇsnˇe pˇrijat´ ych plagi´at˚ u (FAR) vyhovoval poˇzadavk˚ um syst´emu. 1
2.1
Vstupn´ı podpisy, pˇ redzpracov´ an´ı sign´ alu
Jak bylo uvedeno, dynamick´ y podpis sn´ıman´ y speci´aln´ım tabletem d´av´a k dispozici prostorovou informaci o kontuˇre a jej´ım vzniku v ˇcase. Kromˇe toho tak´e informaci o pˇr´ıtlaku, n´aklonu a natoˇcen´ı pera. Sn´ıman´e veliˇciny se naz´ yvaj´ı pˇr´ıznaky, sn´ıman´e v ˇcasech t = 1..T . Jednotliv´e pˇr´ıznaky si oznaˇc´ıme xt , yt pro polohu a pt , φt , θt pro pˇr´ıtlak, n´aklon a natoˇcen´ı. D´ale je moˇzn´e pˇrid´avat dalˇs´ı pˇr´ıznaky odvozen´e z uveden´ ych. Tradiˇcn´ı odvozen´e pˇr´ıznaky 2 2 dy , ]k pro rychlost a at = k[ ddt2x , ddt2y ]k. jsou hodnoty rychlosti a zrychlen´ı, tedy: vt = k[ dx dt dt Z mnoˇzinu pˇr´ıznak˚ u je dobr´e zvolit jenom ty, kter´e pˇrin´aˇsej´ı nejv´ıce informace pro odliˇsen´ı prav´eho podpisu od falsifik´atu. Klasicky pouˇz´ıvan´e pˇr´ıznaky jsou poloha, rychlost, zrychlen´ı. Pˇr´ıpadnˇe jeˇstˇe pˇr´ıtlak. Vyzkouˇset r˚ uzn´e kombinace pˇr´ıznak˚ u bude jedn´ım z vaˇsich u ´kol˚ u. Dalˇs´ı vliv na v´ ysledek modelov´an´ı m´a poˇca´teˇcn´ı pˇredzpracov´an´ı — um´ıstit podpisy do podobn´eho stˇredu (napˇr. tˇeˇziˇstˇe) a normalizovat jejich velikost na definovan´ y rozsah. Posledn´ım v´ yznamn´ ym bodem je poˇcet podpis˚ u pouˇzit´ ych pro tvorbu modelu. Vˇsechny tyto parametry budete zkouˇset nastavovat a sledovat jejich vliv na chybovost syst´emu.
2.2
Signature Toolbox
Pˇripraven´ y syst´em Signature Toolbox pro Matlab slouˇz´ı k naˇc´ıt´an´ı podpis˚ u i jejich zpracov´an´ı. Jsou pˇripraveny funkce pro naˇc´ıt´an´ı podpis˚ u a extrakci jednotliv´ ych pˇr´ıznak˚ u a tak´e v´ ypoˇcet pˇr´ıznak˚ u pˇridan´ ych. Pˇripraveny jsou tak´e funkce na modelov´an´ı podpisu pomoc´ı GMM a ohodnocen´ı kvality podpisu pomoc´ı score. K algoritmu DTW je k dispozici pr´azdn´a funkce, kterou je potˇreba implementovat. Popis pouˇzit´ı toolboxu je v Pˇr´ıloze A.
2.3
M´ıra podobnosti vyuˇ z´ıvaj´ıc´ı Gaussian mixture model
Princip syst´emu zaloˇzen´em na GMM se d´a shrnout v n´asleduj´ıc´ıch bodech: Z podpisu je extrahov´ano n pˇr´ıznak˚ u x1,t . . . xn,t , kaˇzd´ y sn´ıman´ y v ˇcasech t = 1 . . . T . Pˇri uˇcen´ı modelu podpisu je pomoc´ı GMM odhadnuto pravdˇepodobnostn´ı rozdˇelen´ı zvl´aˇst’ pro kaˇzd´ y pˇr´ıznak x1 . . . xn ve vˇsech jeho instanc´ıch (ˇcasov´ ych okamˇzic´ıch). Pokud je v tr´enovac´ı mnoˇzinˇe v´ıce podpis˚ u, jsou do odhadu p. rozdˇelen´ı postupnˇe ˇrazeny vzorky dan´eho pˇr´ıznaku od vˇsech podpis˚ u. T´ımto z´ısk´ame n pravdˇepodobnostn´ıch rozdˇelen´ı P1 . . . Pn . Pokud pot´e rozpozn´ av´ame nezn´am´ y podpis, ohodnot´ıme jej hodnot´ıc´ı funkc´ı pomoc´ı Pn PT log-likelihood: score = i=1 j=1 ln[Pi (X = xi,j )]
2.4
M´ıra podobnosti vyuˇ z´ıvaj´ıc´ı Dynamic time warping
Pˇri pouˇzit´ı m´ıry podobnosti podpis˚ u DTW nedoch´az´ı k uˇcen´ı modelu, ale pouze uloˇzen´ı zvolen´eho mnoˇzstv´ı podpis˚ u (tr´enovac´ı podpisy) do registru. Pˇri rozpozn´av´an´ı podpisu je pot´e nezn´am´ y podpis porovn´av´an s tr´enovac´ımi podpisy pomoc´ı m´ıry DTW (viz pˇredn´aˇsky nebo [2]). Algoritmus v´ ypoˇctu podobnosti dvou (obecnˇe n-rozmˇern´ ych) vektor˚ u pomoc´ı DTW je n´asleduj´ıc´ı: 2
M´ ame dva podpisy s1 , s2 tvoˇren´e n pˇr´ıznaky, jejichˇz d´elky jsou t a s. Notace je stejn´a, jako v pˇredchoz´ım pˇr´ıpadˇ e. x1,1 , x2,1 , . . . , xn,1 x1,1 , x2,1 , . . . , xn,1 x ,x ,...,x x ,x ,...,x 1,2 2,2 n,2 n,2 . , s2 = s1 = 1,2 2,2 ... ... x1,s , x2,s , . . . , xn,s x1,t , x2,t , . . . , xn,t Porovn´ an´ı pomoc´ı DTW je moˇzn´e spoˇc´ıtat n´asleduj´ıc´ım algoritmem: i) Je vytvoˇrena matice D o rozmˇerech (t + 1, s + 1), kter´a je iniciov´ana D(1, 1) = 0, D(i, 1) = inf, D(1, j) = inf, i = 2 . . . n, j = 2 . . . m. ii) Dalˇs´ı pole v matici D jsou poˇc´ıt´ana n´asledovnˇe: D(i, j − 1) D(i − 1, j) , D(i, j) = ||s1 (i − 1, :) − s2 (j − 1, :)|| + min D(i − 1, j − 1) ||s1 (i − 1, :) − s2 (j − 1, :)|| oznaˇcuje eukleidovskou vzd´alenost mezi (i-1)-t´ ym ˇra´dkem qP n 2 (vzorkem) podpisu s1 a (j-1)-t´ ym ˇra´dkem v podpisu s2 , tedy d=1 [s1 (i − 1, d) − s2 (j − 1, d)] . Vz´ ajemn´a vzd´alenost obou vektor˚ u je na konci v´ ypoˇctu naakumulov´ana v dist = D(t + 1, s + 1).
Po porovn´an´ı testovan´eho podpisu se vˇsemi tr´enovac´ımi podpisy spoˇc´ıt´ame pr˚ umˇernou vzd´alenost a z´apornou hodnotu t´eto vzd´alenosti pouˇzijeme jako m´ıru hodnocen´ı kvality podpisu (z´aporn´a hodnota proto, ˇze ˇc´ım jsou podpisy podobnˇejˇs´ı, t´ım je hodnota menˇs´ı, u je m´ıry podobnosti je tˇreba tuto z´avislost pˇrevr´atit).
3
Vypracov´ an´ı u ´ lohy 1. Kaˇzd´ y student dostane zad´any podpisy od 15 r˚ uzn´ ych osob vˇcetnˇe jejich identifikace. Jako prvn´ı vytvoˇrte model podpisu pro kaˇzd´eho zadan´eho ˇclovˇeka metodou GMM. (pouˇzijte pˇrednastaven´e parametry) D´ale zvolte pr´ah m´ıry podobnosti (score), pˇri kter´em urˇc´ıme podpis jako prav´ y (pro cel´ y set a pro pˇet ze zadan´ ych osob - porov’ nejte). Statisticky vyhodnot te kolik pomˇernˇe podpis˚ u je nespr´avnˇe zam´ıtnuto (FRR) a kolik falsifik´at˚ u je faleˇsnˇe oznaˇceno za prav´e podpisy (FAR) na cel´e datab´azi pro V´ami zvolenou hodnotu prahu score. [3 b] 2. Dalˇs´ım krokem bude implementace metody DTW do Sign Toolboxu. Metodu tak, jak je pops´ana v Sekci 2.4 implementujte do pˇr´ısluˇsn´e funkce v toolboxu. Pot´e stejnˇe jako v pˇredchoz´ım kroku vytvoˇrte model pro zadan´e podpisy a stejnˇe statisticky zpracujte. [7 b] 3. Posledn´ım krokem bude optimalizace syst´em˚ u. Pro oba implementovan´e syst´emy vyzkouˇsejte, jak´ y vliv na z´ıskan´e chybov´e statistiky m´a nejprve normalizace vstupn´ıch podpis˚ u (nulov´a stˇredn´ı hodnota pˇr´ıznak˚ u a jednotkov´ y rozptyl). D´ale vyzkouˇsejte pˇridat dalˇs´ı pˇr´ıznaky, kromˇe klasick´ ych — poloha, rychlost, zrychlen´ı — pˇridejte postupnˇe pˇr´ıtlak a ˇcasovou derivaci polohy x a polohy y. [4 b] 3
4. Po nalezen´ı nejlepˇs´ıch v´ ysledk˚ u zmˇenou pouˇz´ıvan´ ych pˇr´ıznak˚ u vyzkouˇsejte jak se zmˇen´ı situace pˇrid´an´ım vˇetˇs´ıho poˇctu tr´enovac´ıch podpis˚ u pˇri tvorbˇe modelu. [1 b] 5. Nakonec zkuste vlastn´ım falsifik´atem podpisu spoluˇz´aka prolomit rozpozn´avac´ı syst´em. (Po p´arech jeden se pokouˇs´ı falsifikovat podpis druh´eho a obr´acenˇe) [5 b] O postupu zpracov´an´ı u ´lohy sepiˇste struˇcn´ y protokol, kde ilustrujte postup ˇreˇsen´ı jednotliv´ ych bod˚ u zad´an´ı. Pˇredpokl´ad´a se samostatn´a pr´ace na u ´loze.
3.1
Bonusy:
1. Implementujte jinou metodu rozpozn´av´an´ı podpisu napˇr. z literatury (velik´ y pˇrehled metod je v [1]). [5 b]
A
Pˇ r´ıloha: Struktura Sigature Toolboxu.
Ke cviˇcen´ı je pˇriloˇzen ˇca´steˇcnˇe vytvoˇren´ y syst´em s jiˇz implementovan´ ym porovn´av´an´ım podpisu v Matlabu pomoc´ı GMM a sadou testovac´ıch podpis˚ u. Cel´ y syst´em je moˇzn´e pouˇz´ıvat pomoc´ı n´asleduj´ıc´ıch funkc´ı: an´ı podpis˚ u tak, jak byly uloˇzeny od poˇc´ıtaˇce. V´ ystupem load data — funkce k naˇc´ıt´ je cell-array s naˇcten´ ymi podpisy, napˇr. S = {s1 , s2 , . . .}, kdy si odpov´ıd´a podpisu tak, jak je definov´an v pˇredchoz´ı kapitole o DTW. K jednotliv´ ym podpis˚ um se v Matlabu pˇristupuje n´asledovnˇe: si = S{i}. preprocess — funkce k pˇredzpracov´ an´ı vstupn´ıch dat.
u ze vstupn´ıch dat. extract features — funkce k z´ısk´an´ı pˇr´ıznak˚ make model — funkce k nauˇcen´ı modelu. score — funkce pro v´ ypoˇcet ohodnocen´ı rozpozn´avan´eho podpisu. ukazka — funkce s uk´ azkov´ ym k´odem pouˇzit´ı.
Vˇsechny funkce i jejich pouˇzit´ı jsou dokumentov´any v n´apovˇedˇe funkc´ı.
Reference [1] Donato Impedovo. Automatic signature verification: The state of the art. Ke stazeni: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4603099 (dostupne pres dialog.cvut.cz). [2] J M Pascual-Gaspar. Practical on-line signature verification. Ke stazeni: http://www. springerlink.com/content/n0x73333061702u4/ (dostupne pres dialog.cvut.cz).
4
[3] SVC2004. Svc 2004: First international signature verification competition, detailed instructions for participants. Ke stazeni: http://www.cse.ust.hk/svc2004/ instructions.pdf.
5
