Marinai S., Fujisawa H. (eds.) Machine Learning in Document Analysis and Recognition

Подождите немного. Документ загружается.

398 S.N. Srihari et al.

Kullback-Leibler:D



b=1

log(

)(5)

= e

−ζD

(6)

Reverse KL:D

RKL

= KL(QP )=



b=1

log(

)(7)

RKL

= e

−ζD

RKL

(8)

Symmetric KL:D

HKL

KL(P Q)+

KL(QP )=

+ D

RKL

(9)

HKL

= e

−ζD

HKL

(10)

Jensen-Shannon KL:D





P + Q







P + Q



(11)

= e

−ζD

(12)

Combined KL and KS measure

A combination of the Kolmogorov-Smirnov and Kullback-Leibler measure, de-

noted KLKS, has been found to outperform the individual measures as will be

analyzed in the performance evaluation section following this. The method to

combine is very simple and is obtained by averaging the probabilities deﬁned

in equations (3) and (5).

KLKS

+ P

(13)

5 Performance Evaluation

5.1 Experiments

A database of oﬀ-line signatures was prepared as a test-bed [13]. Each of 55

individuals contributed 24 signatures thereby creating 1320 genuine signa-

tures. Some were asked to forge three other writers’ signatures, eight times

per subject, thus creating 1320 forgeries. Few samples from genuine signatures

are shown in Figure 7. Ten examples of genuines of one subject (subject no.

21) and ten forgeries of that subject are shown in Figure 8. Each signature

was scanned at 300 dpi gray-scale and binarized using a gray-scale histogram.

Salt pepper noise removal and slant normalization were two steps involved in

image preprocessing. The database had 24 genuines and 24 forgeries available

for each writer as in Figure 8. For each test case a writer was chosen and N

genuine samples of that writer’s signature were used for learning. The remain-

ing 24 − N genuine samples were used for testing. Also 24 forged signatures

of this writer were used for testing. Two diﬀerent error types can be deﬁned

Machine Learning for Signature Veriﬁcation 399

Fig. 7. Genuine signature samples

Fig. 8. Samples for one writer: (a) genuines and (b) forgeries

for any biometric person identiﬁcation problem. False reject rate (Type 1) is

the fraction of samples classiﬁed as not belonging to the person when truly

there were from that person. False acceptance rate (Type 2) is the fraction

of samples classiﬁed as belonging to the person when truly the samples were

not from that person. In the domain of signatures, Type 1 is the fraction of

samples classiﬁed as forgeries when truly they were genuine and Type 2 the

fraction of samples classiﬁed as genuine when truly they were forgeries.

5.2 Person-Independent(General) Method

The classiﬁcation decision boundary discussed in Section 4.1 is given by the

sign of the log likelihood-ratio, LLR, log P (D

|d) − log P (D

|d). A modi-

ﬁed decision boundary can be constructed using a threshold α, such that

log P (D

|d) − log P (D

|d) >α.Whenα is varied, we can plot ROC curves

as shown in Figure 9. The diﬀerent subplots in the ﬁgure correspond to the

ROC curves as the number of known samples is increased from 5 to 20. For

each plot, the total error rate deﬁned as (False acceptance+False reject)/2 is

400 S.N. Srihari et al.

minimum at a particular value of α. This is the best setting of α for the spec-

iﬁed number of known samples, denoted the operating point, and is indicated

with an asterix ‘*’. When 20 samples are used for learning the error rate is

approximately 79%.

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

5 Knowns. Error = 24.311 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

6 Knowns. Error = 22.951 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

7 Knowns. Error = 22.920 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

8 Knowns. Error = 23.552 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

9 Knowns. Error = 23.325 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

10 Knowns. Error = 22.515 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

11 Knowns. Error = 22.157 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

12 Knowns. Error = 22.729 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

13 Knowns. Error = 21.324 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

14 Knowns. Error = 21.254 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

15 Knowns. Error = 22.306 %

0 0.5 1

0.2

0.4

0.6

0.8

Hit Rate

16 Knowns. Error = 22.104 %

0 0.5 1

0.2

0.4

0.6

0.8

False Acceptance

Hit Rate

17 Knowns. Error = 20.723 %

0 0.5 1

0.2

0.4

0.6

0.8

False Acceptance

Hit Rate

18 Knowns. Error = 21.688 %

0 0.5 1

0.2

0.4

0.6

0.8

False Acceptance

Hit Rate

19 Knowns. Error = 20.379 %

0 0.5 1

0.2

0.4

0.6

0.8

False Acceptance

Hit Rate

20 Knowns. Error = 21.396 %

Fig. 9. ROC curves parameterized by α is varied. Each subplot is titled with the

number of knowns used for training and the optimum error rate that is possible.

The asterix ‘*’ denotes the optimal operating point α for that model.

Figure 10 shows the distribution of LLRs when the questioned samples

were genuine and when they were forgeries. A larger region of overlap indicates

a higher error rate.

5.3 Person-Dependent Method

The person-dependent classiﬁcation discussed in Section 4.1 mentioned six

diﬀerent statistics for comparing the two distributions to obtain a probability

of match between the questioned sample and the ensemble of knowns. In order

to measure error rates for this classiﬁcaton technique, once again a decision

needs to be made based on the probability of whether or not the questioned

sample belongs to the ensemble of knowns. If the probability of match >α,

then the decision is in favour of the questioned signature to be genuine, and

Machine Learning for Signature Veriﬁcation 401

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

5 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

6 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

7 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

8 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

9 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

10 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

11 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

12 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

13 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

14 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

15 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Probability of LLR in the bin

16 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Centers of bins of LLR values

Probability of LLR in the bin

17 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Centers of bins of LLR values

Probability of LLR in the bin

18 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Centers of bins of LLR values

Probability of LLR in the bin

19 Knowns. LLR distribution

−50 0 50

0.05

0.1

0.15

0.2

Centers of bins of LLR values

Probability of LLR in the bin

20 Knowns. LLR distribution

Fig. 10. LLR’s obtained from each test case plotted as histograms. The probability

(y-axis) that the LLR falls into a range of LLR values (x-axis) is shown for the

results of truly genuine (solid) and forgery cases (dotted). Each subplot corresponds

to training on a diﬀerent number of knowns.

if the probability of match <α, the decision is in favor of a forgery (this α

should not be confused with that used in the person-independent method).

By varying the parameter α, once again ROC curves (False Accept vs. False

Reject) can be plotted for each of the six measures. The best setting of α is

termed as the operating point. This setting of α corresponds to the least total

error rate possible. Note that the ROC curves are plotted for the test data

set and the operating point determined on them. This test data set can be

considered as a validation set that helps to determine the operating point. In

the curve, the operating point is the point closest to the origin. Table 1 shows

the least total error rate possible when diﬀerent number of known samples

were used for training for each of the 6 diﬀerent measures. Figure 12(a) shows

the same table as a graph comparing the diﬀerent measures and it can be seen

that the combined KL and KS measure performs the best. The reason for this

can be intutively explained by examining Figure 11(a), where it can be seen

that the KS statistic has low false accept rates whereas the KL statistic has

low false reject rates. The combination of these two in the KL and KS measure

works the best.

Figure 12(b) shows how the operating point (best setting of α) varies with

the number of known samples used. It can be seen that in order to obtain the

least total error rate, the value of α changes with the number of knowns for

402 S.N. Srihari et al.

5 10 15 20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

No of Knowns

Error Rates

False accept and False reject for KL and KS

KS False Accept

KS False Reject

KL False Accept

KS False Reject

(a) False acceptance and false reject

rates are plotted for the KL and the KS

statistic as the number of knowns used

for training is increased.

5 10 15 20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

No of Knowns

Error Rates

False accept and False reject for RKL,HKL and JS

RKL False Accept

RKL False Reject

HKL False Accept

HKL False Reject

JS False Accpet

JS False Reject

(b) False acceptance and false reject

rates are plotted as in (a), for the other

measures used: RKL, HKL, and JS. The

operating point is ﬁxed at 50%.

Fig. 11.

certain measures. The value of α explains a lot about what each statistic learns

from the known samples. For example, the high value of α for the KS statistic

when large numbers of known samples were used explains that the KS statistic

focuses on learning the variation amongst the known samples. Presence of

large known samples accounts for greater variation amongst them. Hence if

KS focuses on learning the variation, then almost every questioned sample

ends up receiving a high probability of match as the majority of questioned

samples (genuines and forgeries) invariably fall within the variation. Thus by

setting a high value of α the decision that a sample is truly genuine is made

only if probability is really high. In simple terms this means that when more

samples are used for training the KS statistic will declare a sample as genuine

only if the probability of match is really high. In contrast to this measure

the KL measure captures the similarities amongst the known samples a lot.

This is evident by the low value of α when large number of known signatures

are used. Presence of large number of samples accounts for observing more

similarities. The KL measure focuses on learning the similarities amongst

the samples and it returns a high probability of match very rarely and only

when every similarity that is learnt amongst the known samples is present

in the questioned sample. Hence the majority of questioned sample receive

a low probability of match by the KL measure. To counter this, a low value

of α, ensures that the KL measure will declare a sample as forgery only if

the probability of match is really low. Similar comments can be made about

other measures and it is important to note that those measures for which the

operating point does not vary with the number of knowns and those which

are around the 50% mark can be a useful property. This basically shows

that irrespective of the number of knowns used for training, one can make

a decision using the same operating point, and also if the operating point is

Machine Learning for Signature Veriﬁcation 403

around the 50% mark there is an equal range of probabilties across which the

two diﬀerent decisions fall. And it is also intuitive that the combined KL KS

measure has this ﬁne property. It can be seen that the operating point for

the combined KL and KS measure is closest to the 50% mark amongst other

measures and is also independent of the number of known samples to some

extent. Proceeding with the conclusion that the combined KL KS measure

has the above mentioned properties and also outperforms other measures in

terms total error rate, we can now consider allowing rejections to reduce the

error rates even further. Consider probabilities between .5 − β and .5+β

for some β>0 as the region for reject probabilities. No decision is made if

.5−β < P robability < .5+β. This can signiﬁcantly reduce the total error rate.

Figure 13 shows the total error rate as the rejection percentage is changed by

changing the value of β. This analysis enables the operator to select a value

of β that will induce a certain rejection rate and in turn result in a certain

desired error rate. For example, in order to obtain a error rate of 10% with

20 knowns in this data set one should set β to .15 and that accounts for 35%

reject rate. Similarly for an error rate of 5% for 20 knowns, β needs be set to

.30 which accounts for 62% reject rate.

No. of Knowns KS KL RKL HKL JS KL and KS

5 25.88 24.70 25.61 24.96 25.26 23.87

6 23.54 25.10 25.40 24.57 24.60 22.52

7 22.71 23.35 23.83 23.57 23.31 21.54

8 21.67 23.76 24.60 23.58 23.39 21.20

9 22.17 23.31 24.01 23.03 23.03 20.94

10 21.36 21.93 22.79 21.94 21.63 20.58

11 19.27 20.74 20.96 20.28 20.18 19.02

12 21.13 20.96 21.71 20.42 20.10 19.58

13 20.14 21.73 20.81 21.25 20.78 19.72

14 19.06 20.03 20.84 19.46 19.33 18.41

15 18.28 18.88 19.15 18.10 17.76 17.32

16 19.27 19.08 20.08 18.50 18.38 17.56

17 17.37 17.28 17.36 16.68 16.43 16.07

18 17.79 17.88 18.31 17.58 17.52 17.17

19 17.39 18.09 18.42 17.75 17.37 16.97

20 17.31 17.15 18.58 16.90 17.23 16.40

Table 1. Error rates for signature veriﬁcation. Measures are Kolmogorov-Smirnov

(KS), Kullback-Leibler (KL), reverse KL (RKL), symmetrized KL (HKL), Jensen-

Shannon (JS), and combined KL and KS (KL and KS). These are graphed in

Figure 12(a)

5.4 Results with Deformed Template

With the construction of a more sophisticated grid, the GSC featuers can be

extracted from using these cells in the grid and distances can be computed as

before. The reﬁnement method based on ﬂexible template was compared with

the original GSC features for performance comparison. In this experiment

404 S.N. Srihari et al.

5 10 15 20

0.16

0.17

0.18

0.19

0.2

0.21

0.22

0.23

0.24

0.25

0.26

No of Knowns

Total Error Rate %

Comparison of measures

RKL

HKL

KL AND KS

(a) Comparison of measures. The total

error rate is plotted for the diﬀerent

measures as the number of knowns used

for training is increased. The combined

KL and KS measure (lowest trace) out-

performs other measures (see text).

5 10 15 20

100

No of Knowns

Operating point

Variation of operating point with number of knowns

RKL

HKL

KL AND KS

(b) Variation of operating point of the

diﬀerent measures, as a function of the

number of knowns used for training.

Operating point correponds to the best

setting of the decision boundary (proba-

bility) for classifying samples as genuine

or forgery.

Fig. 12.

0 10 20 30 40 50

Total error rate

5 Knowns

0 10 20 30 40 50

Total error rate

6 Knowns

0 10 20 30 40 50

Total error rate

7 Knowns

0 10 20 30 40 50

Total error rate

8 Knowns

0 10 20 30 40 50

Total error rate

9 Knowns

0 10 20 30 40 50

Total error rate

10 Knowns

0 10 20 30 40 50

Total error rate

11 Knowns

0 10 20 30 40 50

Total error rate

12 Knowns

0 10 20 30 40 50

Total error rate

13 Knowns

0 10 20 30 40 50

Total error rate

12 Knowns

0 10 20 30 40 50

Total error rate

15 Knowns

0 10 20 30 40 50

Total error rate

16 Knowns

0 10 20 30 40 50

Reject %

Total error rate

17 Knowns

0 10 20 30 40 50

Reject %

Total error rate

18 Knowns

0 10 20 30 40 50

Reject %

Total error rate

19 Knowns

0 10 20 30 40 50

Reject %

Total error rate

20 Knowns

Fig. 13. Error rates as the percentage of allowed rejected (no decision) cases in-

creases. The rejection rate is indirectly controlled by varying the β which assigns the

probability region 50 − β and 50 + β where no decisions are made and considered as

rejects. The diﬀerent subplots show the plots for diﬀerent number of knowns used

for learning. We have plotted only the trend for the combined KL and KS measure

Machine Learning for Signature Veriﬁcation 405

for each writer we randomly chose 16 signatures from genuine set as known

signatures. The testing signature is matched with all the 16 known signatures

resulting in 16 distances. Here again, the previously discussed approaches of

person-independent and person-dependent can be applied. But for simplicity,

a simple averaging of all the 16 distance can be done. The resulting average

distance can be compared to a threshold (learnt from a training set), to make a

decision of Genuine/Forgery. This resulted in an improvement of performance

from 16.07% to as low as 7.9%. It suﬃces to say that the more sophisticated

person-dependent approach using these distances computed from these reﬁned

features, will yield even lower error rates for signature veriﬁcation.

6 Interactive Implementation

Document examination is still a process that must use the expertise of a

human examiner since signatures can change with time and there are non-

image issues such as speed and pressure of writing, etc. Thus an image-based

method described earlier is only one part of the solution. The process of using

the algorithms also needs to be interactive so that the user can prepare the

inputs and obtain an opinion from the system.

This section describes an interactive software implementation of signature

veriﬁcation where machine learning is a part of the process. CEDAR-FOX [28]

is a forensic document examination system. It has graphical interfaces for

performing various writer and signature veriﬁcation/identiﬁcation tasks.

The learning method chosen for CEDAR-FOX is person-dependent or spe-

cial learning. This reﬂects the fact that the questioned document examiner

insists on having a set of genuines (size greater than one) in order to perform

the task. The combination of KL and KS methods is used.

The learning phase involves the user selecting ﬁles corresponding to images

of genuine signatures and specifying a name for the compiled learning set. A

screen shot of the user interface, where ﬁve genuine signatures are used in

learning, is shown in Fig 14. CEDAR-FOX allows the user to choose either

the standard GSC feature set or the deformed GSC set in feature extraction.

The testing phase involves the user selecting: (i) the ﬁle corresponding to

the questioned signature, (ii) the name of the compiled learning set and (iii)

the choice of the feature extraction algorithm. This is shown in the screen-shot

of Fig. 15. The interface allows the user to ﬁlter out noise in the signature

image, e.g., by automatically erasing extraneous printed text that might ac-

company the signature image. The result of signature veriﬁcation is displayed

as a probability. In this case the questioned matched the knowns with proba-

bility 0.9895.

406 S.N. Srihari et al.

Fig. 14. Signature learning in CEDAR-FOX. The user has interactively slected ﬁve

genuine image ﬁles

Fig. 15. Signature testing in CEDAR-FOX. The display shows ﬁve known signa-

tures, the questioned signature and the probability of the questioned matching the

genuines

7 Summary and Discussion

Automatic signature veriﬁcation is a task where machine learning can be used

as a natural part of the process. Two diﬀerent machine learning approaches,

one involving genuines and forgeries in a general set and another involving only

genuines for a particular case were described. The ﬁrst approach is analogous

to using counter-examples with near misses in the learning process. Both ap-

Machine Learning for Signature Veriﬁcation 407

proaches involve using a similarity measure to compute a distance between

features of two signatures. Special learning outperforms general learning par-

ticularly as the number of genuines increases. General learning is useful when

the number of genuines is very small (less than four). A reﬁned method of ex-

tracting features for signatures was also discussed which can further increase

veriﬁcation accuracy. An interactive software implementation of signature ver-

iﬁcation was described. Future work should consider combining the two types

of learning to improve performance.

Acknowledgments: This work was supported in part by the National Insti-

tute of Justice grant 2004-IJ-CX-K030

References

1. Osborn, A.: Questioned Documents. Nelson Hall Pub (1929)

2. Robertson, E.W.: Fundamentals of Document Examination. Nelson-Hall (1991)

3. Bradford, R.R., Bradford, R.: Introduction to Handwriting Examination and

Identiﬁcation. Nelson-Hall (1992)

4. Hilton, O.: Scientiﬁc Examination of Questioned Documents. CRC Press (1993)

5. Huber, R., Headrick, A.: Handwriting Identiﬁcation: Facts and Fundamentals.

CRC Press (1999)

6. Slyter, S.A.: Forensic Signature Examination. Charles C. Thomas Pub (1995)

7. Mitchell, T.M.: Machine Learning. McGraw-Hill (1997)

8. Srihari, S.N., Xu, A., Kalera, M.K.: Learning strategies and classiﬁcation meth-

ods for oﬀ-line signature veriﬁcation, Proceedings of the Seventh International

Workshop on Frontiers in Handwriting Recognition (IWHR), IEEE Computer

Society Press (2004) 161–166

9. Winston, P.: Learning structural descriptions from examples. In Winston, P.,

ed.: The Psychology of Computer Vision. McGraw-Hill (1975) 157–210

10. Leclerc, F., Plamondon, R.: Automatic signature veriﬁcation: the state of the

art, 1989-1993. International Journal of Pattern Recognition and Artiﬁcial In-

telligence 8(3) (1994) 643–660

11. Guo, J.K., Doermann, D., Rosenﬁeld, A.: Local correspondences for detecting

random forgeries, Proceedings of the International Conference on Document

Analysis and Pattern Recognition (1997) 319–323

12. Plamondon, R., Srihari, S.N.: On-line and oﬀ-line handwriting recognition: A

comprehensive survey. IEEE Transactions on Pattern Analysis and Machine

Intelligence 22(1) (2000) 63–84

13. Kalera, M.K., Zhang, B., Srihari, S.N.: Oﬀ-line signature veriﬁcation and iden-

tiﬁcation using distance statistics. International Journal of Pattern Recognition

and Artiﬁcial Intelligence 18(7) (2004) 1339–1360

14. Fang, B., Leung, C.H., Tang, Y.Y., Tse, K.W., Kwok, P.C.K., Wong, Y.K.:

Oﬀ-line signature veriﬁcation by the tracking of feature and stroke positions.

Pattern Recognition 36 (2003) 91–101

15. Srihari, S.N., Cha, S., Arora, H., Lee, S.: Individuality of handwriting. Journal

of Forensic Sciences (2002) 856–872