GB2259391A - Signature matching - Google Patents

Abstract

A method for matching one signature against another includes creating a mapping between points in two signatures to be compared measured at corresponding times after the commencement of writing the signatures which maximises the correlation between the local spatial neighbourhoods of the measured points and simultaneously minimises the curvature of the distortions in the mapping, and providing quantitative measures of both the maximum of the correlation and the minimum of the curvature of the distortions in the mapping thereby to provide a measure of the similarity between the signatures. <IMAGE>

Description

Signature Matching The present invention relates to a method for matching one signature with another and more specifically to a method for verifying signatures written as part of a transaction.

Existing debit or credit cards have on them a signature provided by a person to whom the credit card has been issued. During a debit or credit card transaction the person making the transaction signs a voucher and the other party to the transaction compares the two signatures before completing the transaction. A similar operation is carried out for cheque verification.

As the card which is used for the transaction carries the signature of the holder of the card, it is possible for someone who acquires the card illegally to practice the signature and so obtain money or goods by false pretences. The problem is a major one, it is estimated that some 5 x 108 are lost in this way annually.

A signature represents a two-dimensional pattern, but by the nature of its creation from human writing, it can be classified according to a one-dimensional variable-time and methods using variations in this parameter have been proposed. For example, Herbet and Lui published a method based on the use of accelerationtime functions which reduced the level of acceptance of forgeries by some 98%.

The present invention also makes use of time variations to compare signatures and has some similarities to the method of spectrum matching published in GB Patent Application 2,225,149A. The essential difference, however, is that a signature represents a continuous pair of spatial variables recorded as a function of time, rather than sets of variables defined at the discrete times corresponding to peaks in the spectra to be matched. The nature of the crrelation therefore, is quite different.

According to the present invention there is provided a method for matching a prototype signature designated (B) with a test signature designated (A) to determine whether the signatures are written by a specified person, comprising the operations of creating a mapping between points in the two signatures to be compared measured at corresponding times after the commencement of the writing of each of the signatures which maximises the correlation between the spatial neighbourhoods of the measured points in the signatures and simultaneously minimises the curvature of the distortions in the mapping, providing quantitative measures of both the maximum of the correlations between the spatial neighbourhoods of the measured points in the signatures and the minimum of the curvature of the distortions thereby to provide a measure of the similarity between the two signatures, comparing the measure of similarity between the signatures with an accepted criterion of similarity indicative of an acceptable probability that both signatures were written by the specified person and providing an indication of the acceptance or rejection thereof.

The invention will now be described and explained, by way of example, with reference to the accompanying drawings, in which Figure 1 illustrates how a signature may be considered a discontinuous line in three dimensional space-time, Figure 2 shows an initial phase defining one parameter of a pair of signatures, Figure 3 shows a later phase defining a second parameter of a pair of signatures, Figure 4 shows a mapping from one signature to another.

Referring to the drawings, a signature written on a touch sensitive pad is digitised in both position and time to give a sequence of spatial positions x(t), y(t) which add the further dimensions of time (t) to the definition of the signature. The signature can now be represented by a discontinuous line in three dimensions as shown in Figure 1, the spatial and time characteristics of which can be held in a data base.

Verification of a test signature involves a comparison of corresponding parameters of that signature with those of the prototype signature in the database.

The principle of the invention is as follows: At the start of the prototype (B) and test (A) signatures, the difference in (x, y) space between the two signatures is given by dx(t=O) = xB(t=0) dy(t=0) = y,(t=O) - YA(t=O). The running average of this vector, when averaged over a specified distortion radius in (x, y) space, becomes the spatial distortion vector dx(x, y), Q(x, y) mapping the test signature on to the prototype signature.At a subsequent time tl = to + st in the prototype signature, a matching is made between a circular area centred on XB (t) YB (t) in the prototype signature and an area centred on x^(t2) y^(t2) in the test signature. The radius of this area is defined as the correlation radius. The correlation can be defined in various ways, for example, by the Hamming distance of matching pixels. The initial value for time t2 would be equal to tl. However, an adjustment of the value of t2, for example by a Monte Carlo code, would be made to optimise the correlation between the two areas.The best matching time difference averaged over a specified distortion time defines a third component of the distortion vector, Q(t) = t2 - tl.

The method of the invention seeks to find the best match between each point, (iB) on the prototype signature and the corresponding point iA = link(i3) on the test signature. All signatures are assumed to be written in such a way that corresponding features always are written in the same time order. For example, i's are dotted and t's are crossed in the same order. If this is so, then the connections link(iB) will increase monotonically with time. The different timings of the B and A signatures will mean that the connections are distorted with time so that some linkages from the B signature will go to the same point on the A signature and some points on the A signature will have no linkage with the B signature.

The optimal connection j = link(i) is assumed to be that which simultaneously has the following attributes:1) The best spatial correlation between a subset of points j3 and jA neighbouring the linked points in either space or time.

2) The minimum distortion between the actual connection link(iB) and a mean distortion vector dx(i#)dy(i#), defined by the average of the connections between a different subset of points kB and kA neighbouring the connected points in either space or time.

As an example, the spatial correlation C may be defined as the least squares residual between the currently linked points 3A' jB' CjA,jB=[XB(jB)-XA{link(iB)}] + [YB(jB) -yA{link(iB)}] where the points j, are, for example, from 1B - ncorr to 1B + ncorr, and the corresponding points j, are for example from link(iB) - ncorr to link(iB) + ncorr. Where ncorr is a parameter of the model defining the distances along the signatures over which the correlations are evaluated.

The distortion vector may be defined similarly as the mean vector between linked points over a range. For example:

where the summation covers the time from iB-ndiSt to iB+ndist and nudist is a characteristic number of points in the signatures over which the distortion is evaluated.

The method leads iteratively from a starting set of connections, the precise definition of which is unimportant. For example the connections may be made at equal time index. The changes to the connections are made using a Monte Carlo procedure depending on an "energy" term E which is to be minimised. The energy is assumed to have up to four positive terms.

i) An energy proportional to the spatial correlation.

ii) An energy proportional to the squared difference between the actual spatial displacement between the connected time points, and the averaged distortion vector at that point.

iii) An energy depending on the numbers of connections ending on any one point on the A signature. This energy is set to zero for the desired one to one connection, and is set to a positive value if any point is either not connected or is multiply connected.

iv) An energy depending on the squared difference in the actual times of the connected points. The energy term will favour signatures that are written at closely similar speeds.

Quantitatively these four terms may be written E=Ecorr+Edi5t+Ebond+Etime where Ecorr=#Fcorr{ (XE (jB) -XA{link (jb)}] 2 (YB (JE) -yA{link(jA ) ]

Ebond=#Fbond[nlink(iB) -1 ] 2, Etime=#Ftime [link(iB) ) -iB], Fcorr, Foist Fbond and Ftime are coefficients and the summations are carried out over the whole signatures.

The values of these four energies are then entered into a classification algorithm with coefficients Fcorr, Foist , Fbond and Ftime which decides if the signature is genuine or otherwise. The classification algorithm will have been trained by operating on a database of genuine and forged signatures the authenticity of which is known in advance.

Claims (10)

1. Claims

   Signature Matching 1. A method for matching a prototype signature designated (B) with a test signature designated (A) to determine whether the signatures are written by a specified person, comprising the operations of creating a mapping between points in the two signatures to be compared measured at corresponding times after the commencement of the writing of each of the signatures which maximises the correlation between the spatial neighbourhoods of the measured points in~the signatures and simultaneously minimises the curvature of the distortions in the mapping, providing quantitative measures of both the maximum of the correlations between the spatial neighbourhoods of the measured points in the signatures and the minimum of the curvature of the distortions thereby to provide a measure of the similarity between the two signatures, comparing the measure of similarity between the signatures with an accepted criterion of similarity indicative of an acceptable probability that both signatures were written by the specified person and providing an indication of the acceptance or rejection thereof.
2. 2. A method according to Claim 1 including the operations of digitising in space and time the prototype signature to give a series of time related spatial data signals representative of the prototype signature, storing in a database parameters relating to the time related spatial data signals representative of the prototype signature, similarly digitising in space and time the test signature and comparing corresponding parameters of the two signatures to create the mapping between the points in the two signatures measured at corresponding times after the commencement of the writing of each of the two signatures.
3. 3. A method according to Claim 1 or Claim 2 wherein the corresponding points on the prototype and test signatures are connected by the relation iA=link(iB) and the optimal connection between linked points on the two signatures simultaneously has the best spatial correlation between a subset of points j3 and jA neighbouring the linked points in either space or time and the minimum distortion between the actual connection link(iB) and a mean distortion vector dx(i#)dy(i#), defined by the average of the connections between a different subset of points kB and kA neighbouring the points in each signature which are connected points in space or time.
4. 4. A method according to Claim 3 wherein the correlation C between linked points j, and jA in the prototype and test signatures is given by the relation CiA#ia= [XB (iB) -XA{link(jB)}] 2+ [ YE(JB) -YA(link(iB)}] 2
5. 5. A method according to Claim 4 wherein the points j, are from iB-ncorr to i, to ncorr and the corresponding points jA are from i-link iB-ncorr to link iB+ncorr where ncorr is a parameter of the model defining the distances along the signatures over which the correlations are evaluated.
6. 6. A method according to Claim 3 wherein the distortion vector is defined by the relation

   where the summation covers the time from iB-ndiSt to iB+ndist and nudist is a characteristic number of points on the signatures over which the distortion is evaluated.
7. 7. A method according to any preceding claim wherein an initial comparison between the signatures is refined iteratively by means of a Monte Carlo procedure.
8. 8. A method according to Claim 7 wherein the Monte Carlo procedure operates to minimise an expression having four terms which are > zero, comprising, i) A term proportional to the spatial correlation between corresponding points in the signatures.

   ii) A term proportional to the squared difference between the actual spatial displacement between connected time points in the signatures and the averaged distortion vector at that point.

   iii) A term dependent upon the numbers of connections ending at any one point on the test signature, the term being zero if a one to one connection exists and a positive value otherwise.

   iv) A term dependent upon the squared difference in the actual times after the start of the writing of the signatures of the connected points.
9. 9. A method according to Claim 8 wherein the numerical values of the terms are entered into a classification algorithm which is adapted to provide an acceptance or rejection of the signatures as having been written by the specified person.
10. 10. A method for matching a test signature against a prototype signature substantially as hereinbefore described.

    14794 WdH