•Sumerians used intricat e seals appli ed to clay cuneif orm tabl etsto aut hentic ate their writings. •Documents were authenticated in the Ro man… [613829]

Signature Verification

History
•Sumerians used intricat e seals appli ed to clay cuneif orm tabl etsto aut hentic ate
their writings.
•Documents were authenticated in the Ro man Empire (AD 439) by af fixing
handwritten signatures to the documents.
•In 1677 England passed a an act to prev ent frauds and perj uries by requiring
documents to be signed by the participating parties.
•In 1977, the first studies of both off- line and on-line signature verification
algorithms were published
–Nagel and Rosenfeld “off-li ne system” IEEE T. Comp.
–Liu and Herbst “on-li ne system” IBM J. Res. Dev .
•Much research has foll owed, attempting various methods for both feature
extraction and matching
–Yang et. al. “Appli cation of Hidden Markov Models for Si gnature Verifi cation” (HMM)
–Lam et. al. “Sig nature Re cognition through Spectral Analysis” (FFT)
–Hangaiet. al. “Writer Verifi catio n using Altitude and D irection of Pen Movement”
(DTW)
–Lejman et. al. “On-li ne Handw ritten Signatur e Verification usi ng Wavelets and Back-
propagation N eural Netw orks” (Neural Network)
–Crane et. al. “Automatic Sign ature Verificati on using a Thre e-axis Force-sensiti ve Pen”
(Parametric)

Current State of the Art
•No common agreement on benchmark databases and protocols in
the research community.
•1st International Signature Veri fication Competition in 2004 (100
users; 20 genuine and 20 forgeries):
–Web: http://www.cs.ust.hk/svc2004/
–On-line signature: 2 Tasks.
–No companies participated (or participated but remained anonymous).
–Difficult task (pen tablet without vis ual feedback, synthetic signatures,
forgers were given the dynamics of the signatures to imitate, English
and Chinese signatures, etc.).
–Best system (3% EER Skilled Forgeries, 1.5% EER Random Impostors)
•Human performance:
–Expert (0.5%FAR @ 7%FRR), Layperson (6.5%FAR @ 26%FRR)

Signature Verification vs.
Handwriting Recognition
Paola Garcia
Handwriting
RecognitionSignature Recognition
(Verification)

•On-Line:
•Off-LineAltitude (0°-90°)
90°270°0°Azimuth (0°-359°)
180°
X Y P Az
0 100 200 300Al
SCANNER

ApplicationsApplications
•On-line:
–SOFTPRO
(http://ww w.signplus.com/)
–CYBERSIGN
(http://ww w.cybersign.com/)
–CIC
(http://www.cic.com/)
•Off-line:
–APP-DAVOS (http ://www.app-
davos.ch/)
–NUMEDIA
(http://ww w.sapura.com.my/N
uMedia/check.htm)

•Advantages of signature verification:
–User-friendly.
–Well accepted socially and legally.
–Non invasive.
–Already acquired in a number of applic ations.
–Acquis ition hardware:
•Off-line: ubiquitous (pen and paper).
•On-line: inexpensive and already in tegrated in some devices (Tablet
PC).
–If compromis ed, can be changed.
–Long experience in forensic environments.

•Disadvantages:
–High intra-class variability
–Forgeries
–Higher error rates than other traits
–Affected by the physical and emotional state of the
user
–Large temporal variation

Pattern Recognition System
(On-line Signature Verification)

Pattern Recognition System

•Acquisition devices:
X Y P Az Al
0 100 200 300

Pattern Recognition Process

Preprocessing
•For online signatures no segmentation needs to be
performed
–All parts of the signatur e are known after sensing
•Attempt to eliminate noise from the capturing device,
speed of writing, and the writing itself
•Minimize the potential of eliminating writer
dependencies
•Solutions
1)Size Normalization
2)Position Normalization
3)Smoothing
4)Re-sampling
5)Ligature

-1500 -1000 -500 0 500 1000 1500 2000 2500-1500-1000-50005001000
-500 0 500 1000 1500 2000 2500 3000 3500 4000-800-600-400-2000200400600800
-2000 -1500 -1000 -500 0 500 1000 1500 2000-1000-500050010001500
-2000-1500-1000 -500 0 500 1000 1500 2000 2500-800-600-400-2000200400600800•Position Normalization:
Initial Sample
Center of Mass

Resample
•In order to compare two signatures with respect to their
shape, they must be re-sampled to eliminate the
dependencies on speed
–Sample rate: 100 samples/second
•Temporal features must be extracted beforehand since
all local speed information is lost during this process

Resampling
•Ensures that the signature is uniformly
smoothed
–Segments of high writing velocity will be
smoothed more than segments that are
written slow

Smoothing
∑
−=+ =σσ2
2*
iorig
it ifiltered
t xf x•A one dimensional
Gaussian filter is used in
both the x and y
directions
–Small changes in the signal
are smoothed out while the
overall structure is kept
•Each segment between
critical points is smoothed
separately in order to
retain their absolute
positionswhere
∑
−=−−
=σσσ
σ
2
222
2222
jji
i
eef

Stroke Concatenation
•A stroke is the points input between a pen down
and pen up sequence
•All strokes are connected into one long string
–This is done in order to facilitate the use of the string
matching procedure

Critical Points
•Def: points that carry more information than others
–Endpoints of strokes
–Points of trajectory change

Critical Points
•Re-sampling or smoothing of these points
will discard important information about
the structure and speed of the signature
–Accordingly, these points are never changed
throughout preprocessing
–The speed information is stored at each of
these points

Preprocessing Steps
•Original
•Critical points

Preprocessing Steps
•Fine re-sampling
•Gaussian filter

Preprocessing Steps
•Coarse re-sampling
•Stoke concatenation

Pattern Recognition Process

Functional vs. Parametric
•Functional Approac hes (local)
–Complete signals (e.g. x(t), y(t), p(t), v(t), a(t), etc.) are considered as
mathematical time functions whose values are directly correlated with
the feature set.
–Difficulties are encountered in the matching step (temporal differences
and non-linear distortions)
–Feature extracting is relatively simple
–More computationally intensive (slower), higher accuracy
•Parametric Approac hes
–m parameters are computed as features from the measured signals
–Feature extraction is very difficult (selection of meaningful features)
–Simple matching techniques for comparing 2 sets of parameters can be
used
–Very fast matching, lower accuracy

Feature Extraction
•Local features
–Spatial: static features extracted from the shape of the
signature
•Change of the distance betwe en two consecutive points (δx,
δy)
•Absolute y coordinate ( y)
•Sine and cosine of the angle with the x axis ( sin αand cosα)
•Curvature (β)
•Grey values in a 9×9 pixel neighborhood
–Temporal: features using th e ordering (timing) of the
signature
•Absolute and relativ e speed at each re-sampled point
•Absolute and relativ e speed between two critical points
–Pressure value

Local Features
•δxand δyfor poi nt piare the
changes with respect to the
subsequent point pi+1
•yis the y-coordinate of each
re-sampled point after
preprocessing
•αis the angle between the x-
axis and the line through
points pi and pi+1
–αis not used (ex. 1 and 359)
–sinand cosare both used for
directional information
•βis the angle between the
straight lines pi -pi-2and pi –
pi+2

Local Features
•The 9×9 pixel neighborhood
is divided into nine 3×3
squares
–Grey values are computed by
summing pixel values in each
3×3 square
–Most costly operation
•No features are extracted
for the last point of a stroke
•Total number of features
–15

Temporal Features
•Absolute and relative speeds are defined as
distance per unit time
–Tablet PC captures the position of the pen 100 times
per second
–Distance is measured in pixels
–Only distance between points is necessary to define
the speed
•Speed is normalized by dividing the local speed
at each sample point by the average writing
speed of the signature
–Overall speed may vary but the relative speeds
should be more stable

Global Features

Pattern Recognition System

String Matching
•To compute this alignment, dynamic time warping (DTW) is
used
–D(i,j) is the optimal alignment up to point i of the first string and point
j of the second string
–de(i,j) is the Euc lidian distance between points i and j
•The overall dissimilarity for a signature⎪⎩⎪⎨⎧
++−+−−
=
Penalty Spurious1Penalty Missing),1(),( )1,1(
),(
) D(i,j-j iDjid j iD
MinjiDE
),( _),(),(2
J INN Factor NormJIDJI Dist =

DTW Example
•Match strings ‘abcacac’ and ‘bcab’
Difference Score Matrix Reverse Path
Result

String Matching
•Each point is represented by an n-ary feature vector
–Feature reduction is performed
•Euclidean distance is used as the metric to compare two feature
vectors
•Each feature is normalized using the z-score
–σµ−=′ff
•A set of pairings between the
template and input string is found
where the sum of the differences
between each pair of aligned points
in minimal

User Dependent Normalization
•Training set:
–Pair-wise distances between all training samples is calc ulated
(DTW)
–The sample with the smallest average distance is selected as
the template
–Normalization Statistics:
•Average distance from template
•Average maximum distance
•Average minimum distance
•Test sample:
–Compute DTW against all training samples
•Record: distance from template, maximum distance and minimum
distance
–Normalize the 3 distances by di viding them by the set’s average
statistics

Dimension Reduction
•PCA
–Transform a 3D vector of highly correlated data to 1D
–Find a linear transformation W that maps the original
vector (X) to projection coefficient vector (Y)
–Compute Average:
–Covariance Matrix:
–Eigen-decomposition:XWYT=
∑
==N
iixN 11
µ
∑
=−−=N
iT
i i T x x S
1) )( (µ
µ
e eSTλ=

PCA
•Project the distance vector (max, min,
template) to 1 dimension

Validation Set
•PCA needs samples to calculate the projection
coefficients
–Using data fr om the training or testing sets will bias the results
•Divide data into training, validation, and testing
•SVC 2004
–40 users: 20 genuine signatures , 20 skilled forgeries per user.
–Testing procedures :
•Train on 5 genuine signatures
•Test on 10 genuine signatures
•Test on 20 skilled forgeries
•Test on 10 random forgeries
•2-Fold Cross Validation
–Select data from the second half of 20 users (genuine, skilled)
for validation set to train PCA
–Test on the first half of 20 user s with the calculated coefficients
–Repeat this process, switching the 2 groups

SVC Examples
Genuine
Imposter

Mahalanobis Distance
•Introduced by P. C. Mahalanobis in 1936
•A distance measure which utilizes the
correlations between the features
•
•M is the squared Mahalanobis distance
•s represents the within-group covariance matrix
•y is the vector of the means of the scores for a
group
•x is the vector containing the individual scores of a
sample
•In our work, a diagonal covariance matrix is
assumed) ( ) (),(1y x Sy x yx dM −′−=−

Pattern Recognition System

Score Fusion

Score Fusion
Global FeaturesLocal Features

Weighted Sum Rule
•Assign a test sample to wiif
–
And to waotherwise)|( )|( )|( )|(g a g l a l g i g l i l xwPW xwPW xwPW xwPW + > +

Biometric Comparison