A DSmT Based System for Writer-Independent Handwritten Signature Verification Nassim ABBAS1 , Youcef CHIBANI1 , Bilal HADJADJI1 , Zayen AZZOUZ OMAR1 [email protected] [email protected] [email protected] [email protected] & Florentin SMARANDACHE2 [email protected] Communicating and Intelligent System Engineering Laboratory Faculty of Electronic and Computer Science University of Sciences and Technology Houari Boumediene Algiers, Algeria 1 Department of Mathematics University of New Mexico Gallup, NM 87301, U.S.A. 2 ICIF Outline Introduction One Class Support Vector Machines Classifier Belief Function Theories Proposed Combination Scheme for Handwritten Signature Verification Conclusion and future works

ICIF 2016 F. SMARANDACHE 2 1. Introduction (1) Statement of the problem Input pattern Data Acquisition Feature Generation Preprocessing Decision Classification Figure 1. Structure of the recognition system Solution Parallel combination scheme 1 Feature Generation 1 Classifier-1 n

Output-1 Parallel Input pattern Combination Preprocessing Final decision Module Feature Generation p Classifier-p Output-p Figure 2. Parallel combination of classifiers ICIF 2016 F. SMARANDACHE 3 1. Introduction (2) Combination levels Class level combination Rank level combination Measure level combination Distance Credibility

Posterior probability Possibility Confidence value Fuzzy measure Match score Belief function Belief functions take into considerations two notions: Uncertainty: is an unrealistic measure induced by the outputs of classifier, which leads to interpret the response of the classifier as the result of a random phenomenon Imprecision: is measure representing the uncertainty linked to incomplete knowledge ICIF 2016 F. SMARANDACHE 4 1. Introduction (3) Three theories dealing with uncertainty and imprecise information have been introduced Probability theory (PT): uncertainty Evidence theory (Dempster-Shafer Theory): uncertainty + imprecision Plausible and paradoxical reasoning theory (Dezert-Smarandache Theory): uncertainty + imprecision Output (Classifier-c1) Estimation of Masses

Output (Classifier-c2) Estimation of Masses 1 Combination Rule Decision Measure Decision Rule 2 n Output (Classifier-cp) Estimation of Masses Estimation Combination Decision Figure 3. Belief Function Theories-Based Parallel Combination of Classifiers ICIF 2016 F. SMARANDACHE 5

2. One Class Support Vector Machines Classifier One Class Support Vector Machines (OC-SVM) Support vector Outliers Training data f ( x) 0 Support vector K ( x, xi ) Projection Hyper sphere w f ( x) 0 Original space Decision function: Sv f ( x ) j K ( x, x j ) j 1 f ( x) 0 Feature space Sv : Number of Support Vectors

j : Lagrangian multipliers : Distance of the hyperplane from the origin Pattern x is accepted when f ( x) 0 Otherwise it is rejected ICIF 2016 F. SMARANDACHE 6 3. Belief Function Theories: Probability Theory (1) Mathematical Formalism Discernment space: is defined as a finite set of exhaustive and mutually exclusive hypotheses G 1 , 2 .., n Basic probability assignment (bpa): m 0 m i 1, m i 0 m P : 0, 1 i m i Bayesian rule: P i x i P x i .P i n P x .P i

i i 1 ICIF 2016 F. SMARANDACHE 7 3. Belief Function Theories: Probability Theory (2) Basic Sum combination rule 1 p mi j i mc A msum A p 1 0 if A j , A otherwise. p : Simple class belonging to discernment space : Number of information sources mi . : bpa issued from the i-th source Advantage: Simple Limitation: No managing conflict between two sources ICIF 2016 F. SMARANDACHE

8 3. Belief Function Theories: Dempster-Shafer Theory (1) Evidence Theory Dempster-Shafer theory (DST) allows to model both ignorance and imprecision, and to consider compound hypotheses such as the union of classes. It is generally recognized as a convenient and flexible alternative to the bayesian theory. Mathematical Formalism Discernment space: Power-set: 1 , 2 .., n G 2 ,1 , 2 , , n ,1 2 ,1 3 , ,1 2 n 1 , Basic belief assignment (bba): m : 2 0, 1 Ai m Ai ICIF 2016 m 0 m Ai 1, m Ai 0 Ai 2 F. SMARANDACHE

9 3. Belief Function Theories: Dempster-Shafer Theory (2) Estimation of belief mass functions It's specific to each application area according the nature of the data. Handwriting recognition. 1 2 n ICIF 2016 P x 1 P x 2 P x n F. SMARANDACHE Transfer Model It's not directly explicit in term of modelling of the problem under consideration. Bayesian Model

m x A1 m x A2 m x 10 3. Belief Function Theories: Dempster-Shafer Theory (3) Dissonant model of Appriou Axiom (1): Consistency with the Bayesian approach Axiom (2): Separability of the evaluation of the hypotheses Axiom (3): Consistency with the probabilistic association of sources .R .P x i m j i i j , 1 R j .P x i i m j i , 1 R j .P x i m j 1 i , R j 0, max sup P x i i 1, n P x i : Conditional probability of an object x given the class i . Rj : Normalization factor i ICIF 2016

: Coarsening factor. F. SMARANDACHE 11 3. Belief Function Theories: Dempster-Shafer Theory (4) Dempsters orthogonal sum rule m A p mk Bk , A 2 B1 , B 2 , , B p 2 k 1 B1 B 2 B p A p 2 : Focal element of the power-set . m A : Combined mass of Dempsters m A mc A mDS A , A 2 1 Kc K c m

A mk Bk B1 , B 2 , , B p 2 k 1 B1 B 2 B p conjunctive rule. Kc : Conflict measure between the different masses mk . issued from information sources S k , respectively. Advantage: Taking into account the imprecise and uncertain information Limitation: No managing high conflict between two sources of information ICIF 2016 F. SMARANDACHE 12 3. Belief Function Theories: Dempster-Shafer Theory (5) Decision rules Combined mass function : uncertainty [Belief function, Plausibility function] : imprecision Selecting the more realistic hypothesis. Rules used for decision-making: Maximum of belief function. Maximum of plausibility function. Maximum of Pignistic Probability. Minimization of mass function with an acceptance threshold.

ICIF 2016 F. SMARANDACHE 13 3. Belief Function Theories: Dempster-Shafer Theory (6) Limitations of DST Foundation of the DST Does not take into account the paradoxical information Significant conflict DST based measure possible combination is not Solution: Dezert-Smarandache Theory (DSmT) ICIF 2016 F. SMARANDACHE

14 3. Belief Function Theories: Dezert-Smarandache Theory (1) Plausible and Paradoxical Reasoning Theory It has been originally developed since 2003 by Jean Dezert and Florentin Smarandache. It has the advantage of being able to represent explicitly the uncertainty from imprecise knowledge. It was elaborated for dealing with paradoxical sources of information (i.e. classes, descriptors, classifiers, sensors,etc). It is based on a particular framework where the finite discrete frame of discernment is exhaustive but not necessarily exclusive. ICIF 2016 F. SMARANDACHE 15 3. Belief Function Theories: Dezert-Smarandache Theory (2) Mathematical Formalism Discernment space: 1 , 2 .., n 1. ,1 , , n D . Hyperpower-set: G D

2. If A, B D , then A B D and A B D . 3. No other elements belong to D , except those obtained by using rules 1 or 2. Generalized belief assignment (gbba): m : D 0, 1 Ai m Ai m 0 m Ai 1, m Ai 0 Ai D Estimation techniques of masses in DST framework ICIF 2016 F. SMARANDACHE Valid in DSmT framework 16 3. Belief Function Theories: Dezert-Smarandache Theory (3) Combination rules Classical DSm combination rule (DSmC) DSm Hybrid combination rule (DSmH) Proportional Conflict Redistribution rules (PCR1, , PCR5, PCR6)

Decision rules Minimum of mass function with an acceptance threshold Accepted Decision Rejected if min mtest 1 , mtest 2 t opt otherwise Note: t opt : Denotes the optimal value of the acceptance decision threshold mtest . : Defines the combined mass of the simple class i ICIF 2016 F. SMARANDACHE 17 Parallel Combination of Classifiers for Handwritten Signature Verification Handwritten Signature Verification (HSV) Application Writer-Independent HSV ICIF 2016 F. SMARANDACHE 18 4. Proposed Combination Scheme for Handwritten Signature Verification (1)

Motivation Physiological Biological Behavioral Fingerprint Face DNA Writing Keyboarding Iris Hand geometry Smell Gait Signature ICIF 2016 F. SMARANDACHE 19 4. Proposed Combination Scheme for Handwritten Signature Verification (2) Motivation

Sign a document to identify himself is a natural gesture. Handwritten signature is the biometric modality the most accepted by many peoples. It is used in many countries as legal or administrative element. Design of a signature verification system is cheaper and more simple comparatively to other biometric systems (for instance iris or face). ICIF 2016 F. SMARANDACHE 20 4. Proposed Combination Scheme for Handwritten Signature Verification (3) Motivation Dynamic features (Velocity, Pressure, .) e Onlin Acquisition of the handwritten signature

Electronic tablet Offl ine Static features (Image) Scanner Difficulties of the offline handwritten signature verification: High variability intra-writer Easy to imitate Quality of the signature (Paper, Pen, Scanner) ICIF 2016 F. SMARANDACHE 21 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Why use a writer-independent HSV approach ? Writer-dependent approach Off-line HSV problem Writer-independent approach Off-line HSV writer-dependent approach: Advantage: Providing a high performance verification Limitation: Need of learning the model each time when a new writer should be included in the system Solution: (1) Off-line HSV writer-independent approach, (2) Using only genuine signatures, (3) through combination scheme of two individual verification systems ICIF 2016 F. SMARANDACHE 22

4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Verification scheme using an OC-SVM classifier ICIF 2016 Learning phase Verification phase Learning data Testing data Vectors of (dis) similarity measures Vectors of (dis) similarity measures Learning algorithm OC-SVM classifier Generation of the model Selection of the optimal threshold Decision

F. SMARANDACHE 23 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Classification based on DSmT Space of discernment: 1 descriptor1 , 2 descriptor 2 Mass function: mi ( A j ) [0,1] Such that: i 1,2 (Source 1 or 2) Combination space: Source 1 Source 2 (OC SVM 1) (OC SVM 2) PT: G 1 , 2 DST: G 2 ,1 , 2 ,1 2 DSmT: G D ,1 , 2 ,1 2 ,1 2 Combination (Conflict management) Combined masses: mc ( A) m1 ( X ) m2 (Y ) Card (G ) Combined sources ICIF 2016 A, X , Y G G G

mc ( A j ) 1 j 1 F. SMARANDACHE 24 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Decision making in both DST and DSmT frameworks Select outputs of both classifiers (validation phase) tmass min mc 1 , mc 2 1 Combinaison of masses (validation phase) Combinaison of masses (learning and validation) Compute the optimal decision threshold Decision making ICIF 2016 tmass min min mlearn 1 , min mlearn 2 2 tmass opt

tmass tmass 1 2 2 Accepted if min mtest 1 , mtest 2 tmass Decision otherwise Rejected F. SMARANDACHE 25 opt 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Case study: Combining two Off-Line HSV Systems (1) Partitioning of the CEDAR database: 25 Writers 55 Writers 30 Writers 1 Writer 1 Writer 24 genuine signatures 5 Signatures for learning

ICIF 2016 24 genuine signatures 5 Reference signatures 14 Signatures for validation F. SMARANDACHE 5 Reference signatures 24 impostor signatures 43 Signatures for testing 26 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Case study: Combining two Off-Line HSV Systems (2) Feature generation: Simple features are generated from each off-line signature image, which are: Discrete cosine transform (DCT) based features Curvelet transform (CT) based features Advantage of both transforms : DCT: Two important properties: Decorrelation and energy compaction CT: Analyzing local line or curve singularities Sources of information: Two sources are considered Source 1: DCT based descriptor Source 2: CT based descriptor Performance criteria: Three popular errors are considered

False Rejection Rate (FRR) False Acceptance Rate (FAR) Average Error Rate (AER) ICIF 2016 F. SMARANDACHE 27 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Case study: Combining two Off-Line HSV Systems (3) Comparative analysis: Algorithm Optimal Threshold Verification Error Rates (%) FRR FAR AER OC-SVM classifier 1 (DCT) -0.060712 28.7719 44.0278 37.2868 OC-SVM classifier 2 (CT)

-0.419880 9.6491 0.0000 4.2636 Max combination rule -0.060710 17.5439 44.0278 32.3256 Sum combination rule -0.480590 6.8421 44.0278 27.5969 Min combination rule -0.419880 9.6491 0.0000

4.2636 Table 3. Experimental results of proposed individual systems and classical combination algorithms ICIF 2016 F. SMARANDACHE 28 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Case study: Combining two Off-Line HSV Systems (4) Conflict managing in DSmT framework: Kc Conflict measure Signature index Figure 1. Conflict between both OC-SVM classifiers using DCT and CT-based descriptors for testing signatures ICIF 2016 F. SMARANDACHE 29 4. Proposed Combination Scheme for Handwritten Signature Verification: Writer-Independent Handwritten Signature Verification Case study: Combining two Off-Line HSV Systems (5) Comparative analysis: Algorithm

Optimal Threshold Verification Error Rates (%) FRR FAR AER OC-SVM classifier 1 (DCT) -0.060712 28.7719 44.0278 37.2868 OC-SVM classifier 2 (CT) -0.419880 9.6491 0.0000 4.2636 Max combination rule -0.060710 17.5439 44.0278

32.3256 Sum combination rule -0.480590 6.8421 44.0278 27.5969 Min combination rule -0.419880 9.6491 0.0000 4.2636 DS combination rule 0.334200 0.0000 6.3158 2.7907 PCR6 combination rule 0.267100

0.0000 6.1404 2.7132 Table 4. Experimental results of proposed algorithms ICIF 2016 F. SMARANDACHE 30 6. Conclusion and futur work Conclusion Proposed combination scheme with PCR6 rule yields the best verification accuracy compared to the statistical match score combination algorithms and DS theory-based combination algorithm even when the individual writer-independent off-line HSV systems provide conflicting outputs. Futur works Adapt the use of the evidence supporting measure of similarity (ESMS) criteria to select complementary sources of information using the same proposed combination scheme in order to attempt to improve the FRR. Replace the OC-SVM classifier by the Histogram Symbolic Representation (SHR) based one class classifier. ICIF 2016 F. SMARANDACHE 31 Many thanks for your attention Questions

Florentin SMARANDACHE [email protected] Department of Mathematics University of New Mexico Gallup, NM 87301, U.S.A. 2 ICIF 2016 F. SMARANDACHE 32