WO1994009448A1

WO1994009448A1 - Verifying the authenticity of an entity

Info

Publication number: WO1994009448A1
Application number: PCT/GB1993/002123
Authority: WO
Inventors: Michael Christopher Fairhurst; Paul St. John Brittan
Original assignee: British Technology Group Limited
Priority date: 1992-10-16
Filing date: 1993-10-14
Publication date: 1994-04-28
Also published as: EP0664913A1; GB2271657A; JPH08502376A; GB9221785D0

Abstract

Systems for the automatic verification of signatures already written on documents have produced results which lead to significant proportions of authentic signatures being rejected and false signatures being accepted. Signature verification according to the invention applies dynamic programming techniques to static features extracted from a previously recorded signature. The static features of an unauthenticated signature are compared with the corresponding static features of a set previously authenticated signatures. A characteristic distance of the unauthenticated signature from the set of authenticated signatures is then derived. The unauthenticated signature is verified by measuring the characteristic distance against a previoulsy set threshold.

Description

VERIFYING THE AUTHENTICITY OF AN ENTITY The present invention relates to methods and apparatus for verifying the authenticity of a representation of an entity and particularly to verification of handwritten signatures. Many proposals have been made to provide automatic verification of signals representing static features of signatures but, as far as is known, all have produced results which lead to a significant proportion of rejections of authentic signatures and acceptances of false signatures. In a paper, entitled "On-line Signature Verification Incorporating the Direction of Pen Movement" by M. Yoshimura, Y. Kato, S. Matsuda and I. Yashimura, IEICE Transactions, Vol. E 74, No. 7, July 1991, pages 43 to 49, a signature verification technique is described which includes dynamic programming (DP) applied to a dynamic feature of a signature, in that the DP algorithm employs the coordinates of points in a signature at sample times. Such information is only available when a signature is written and therefore cannot be applied to signatures already written on documents. A descriptive technique for signatures is the subject of a paper entitled "Structural Description and Classification of Signature Images" by M. Ammar, Y. Yoshida and T. Fukumura, Pattern Recognition, Vol. 23, No. 7, 1990, pages 697 to 709. In this technique horizontal and vertical projections of signatures are used to segment signatures vertically and horizontally as steps in constructing the description.

According to a first aspect of the invention there is provided a method of verifying the authenticity of a representation of an entity comprising the steps of selecting at least one static feature of members of a set of authentic representations of the entity, the feature consisting of a plurality of values, selecting a corresponding static feature of an unauthenticated representation of the entity, the corresponding feature consisting of a plurality of values, comparing the feature of the unauthenticated representation with the corresponding feature of each of the authentic representations by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, deriving from the minimum distances a characteristic distance between the unauthenticated representation and the set of authentic representations, and determining from the characteristic distance the authenticity of the unauthenticated representation of the entity. According to a second aspect of the invention there is provided a method of selecting a set of authentic representations of an entity comprising selecting at least one static feature of members of a set of genuine representations of an entity, the feature consisting of a plurality of values, comparing the feature of each representation with the corresponding feature of each other representation by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, deriving characteristic distances between each representation and the other representations, and rejecting a previously determined number of representations with the highest characteristic distances.

The entity may for example be a person's signature and the representations of the entity are then representations of signatures. The authenticity of a representation may be determined by comparing the characteristic distance derived with a previously set threshold. This threshold may be derived from the average of the characteristic distances for the selected set of authentic representations, as disclosed in the second aspect of the invention.

Further comparisons between a further feature and a corresponding further feature may also be made. In comparing one feature with a corresponding feature most of the values of the said first feature are preferably used to provide groups of comparisons which extend through most values of the first feature.

An important element of the invention 1s the realisation that dynamic programming can be applied to static features. In the past the DP technique has only been applied to dynamic situations because it has been assumed that the technique can only be used to correct mismatches in time.

Thus an advantage of the invention is that a form of DP is applied to static features to enhance authentication. In its most simple form single feature values are compared with appropriate ranges of values of a corresponding feature but the full DP technique including deriving cumulative distances can also be used.

A cumulative distance may be determined for each comparison of one or more features of one representation with corresponding features of another representation using the minimum distances derived from comparing one or more pairs of corresponding features. The characteristic distance may then be derived by averaging the cumulative distances. A static feature of an entity is a feature which is apparent from a visual representation of the entity. The static feature used 1s a feature comprised of a number of values.

The overall shape of a signature 1s Important in verifying a signature by eye, and in order to make a similar appreciation some embodiments of the present invention use horizontal and vertical projection profiles in comparing corresponding profiles in unauthentic and authentic representations, and/or in selecting the set of authentic representations. A projection profile may be a summary of the representation projected onto an axis, where the representation is an image of the entity.

For signatures, horizontal and vertical projection profiles are preferably used and for each group of comparisons, one value of each profile from one representation is subtracted from each of a range of values of the corresponding profile from another representation. The range of values is usually centred on a value of the corresponding value which corresponds to the said one value. The differences so found are used in determining the minimum distances. The representation of the entity is created when the entity is created or later. The representation of the entity may be created from a digitised image of the entity, such as by scanning a signature.

According to a third aspect of the invention there is provided apparatus for verifying the authenticity of a representation of an entity comprising means for selecting at least one static feature of members of a set of authentic representations of an entity, the feature consisting of a plurality of values, means for selecting a corresponding static feature of an unauthenticated representation of the entity, the corresponding feature consisting of a plurality of values, means for comparing the feature of the unauthenticated representation with the corresponding feature of each of the authentic representations by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said first feature value, and determining from each group of comparisons a minimum distance, means for deriving from the minimum distances a characteristic distance between the unauthenticated representation and the set of authentic representations, and means for determining from the characteristic distance the authenticity of the unauthenticated representation of the entity.

According to a fourth aspect of the invention there is provided apparatus for selecting a set of authentic representations of an entity comprising means for selecting at least one static feature of members of a set of genuine representations of an entity, the feature consisting of a plurality of values, means for comparing the feature of each representation with the corresponding feature of each of the other representations by carrying out groups of comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, means for deriving from the minimum distances a characteristic distance between the one representation and the other representations, and means for rejecting a . previously determined number of representations with the highest characteristic distances in selecting the said set of authentic representations.

The means for obtaining a representation of the entity may comprise a scanner, for example a scanner for scanning cheques to verify representations in the form of signatures. As mentioned above projection profiles have been used for signature segmentation but not for comparison in signature recognition.

According to a fifth aspect of the present invention there is therefore provided a method of verifying the authenticity of a signature comprising the steps of obtaining a projection profile of the signature which is to be verified, and comparing the profile, or a characteristic thereof, with a corresponding profile, or characteristic, of an authentic signature, or a group of authentic signatures.

The present invention also includes apparatus corresponding to the method of the fifth aspect, and corresponding methods and apparatus for selecting a group of authentic signatures from a group of genuine signatures.

Certain embodiments of the invention will now be described by way of example with reference to the accompanying drawings in which:-

Figure 1 is a diagram of apparatus for verifying a signature, Figure 2 is a flow chart for verifying a person's signature,

Figure 3 is a flow chart for selecting the projection profiles from a signature,

Figure 4 shows a digitised representation of a signature and two projection profiles created from the signature, Figure 5 is a flow chart for selecting the best signatures for use during verification,

Figure 6 Is a flow chart for selecting a threshold for use during verification,

Figure 7 is a flow chart for finding the characteristic distance between a test signature and a set of reference signatures, and

Figure 8 is a flow chart for calculating the cumulative distance between one signature and another.

Figure 1 is a block diagram of apparatus for enrolling new users and verifying the signatures of previously enrolled users. A representation of a signature 1s created by the input device 1. This may be either a tablet and pen, with which the signature is created, or a camera or scanner which reads in a previously written signature. The signatures are then represented as a stored matrix of picture elements (pixels). The user enters an identification (a User I.D.) into the identification unit 2 which may be, for example, a keypad or a smartcard and card reader. A processor 3 processes the signatures and a display 4 is used to prompt the user for information and to display results.

A flow chart of a method both for enrolling new users and verifying the signatures of previously enrolled users is shown in Figure 2. In the operation 11 the processor 3 and the display 4 prompts for the mode of operation and ask for the user's identification. If the enrolment procedure (test 12) is to be followed an enrolment count is set to zero (operation 13 ). In an operation 14 the input device creates a representation of a signature made by the user. In operation 15, described more fully by Figure 3, projection profiles of the signature are extracted. Test 16 determines whether the enrolment (A) or verification (B) procedure is followed.

If enrolment is to take place the captured signature is stored, operation 17, and the enrolment count is incremented in operation 18. Test 19 determines whether the enrolment is complete by comparing the enrolment count with a previously determined number of signatures. The number of signatures depends on the accuracy required weighed against the time taken to process the signatures. If the enrolment is not complete the stages 14 to 19 are repeated until test 19 is satisfied. Operation 20 selects the best signatures from the set of captured signatures and is described more fully in Figure 5. Operation 21, described in detail in Figure 6, generates a threshold value for use in the verification process. If the threshold is lower than a previously set minimum, as determined by test 22, operation 23 raises the threshold artificially and moves to operation 25. If the threshold is higher than a previously set maximum (test 24) operation 26 suggest that the user re-enrols by returning to operation 14. The levels of the maximum and minimum, and therefore the resultant threshold, depend on the application and the level of security demanded. Operation 25 stores the selected set of authenticated reference signatures under the user's identification number and the enrolment procedure ends. If the verification procedure is to be followed then at test 16 the system moves to point B. Operation 27 retrieves the previously authenticated reference signatures stored under that user identifier during operation 25. Operation 28, described more fully in Figure 7, finds the characteristic distance between the test signature to be verified (the unauthenticated captured signature) and the set of reference signatures retrieved in operation 27. In this embodiment a cumulative distance between a test (the unauthenticated) signature and a reference (an authentic) signature is derived and the characteristic distance is and average of the cumulative distances between the test signature and a set of authentic reference signatures. Operation 29 selects the level of security, for example low, medium or high. It is the level of security which determines the number of false acceptances or rejections; with a high level of security there will be more false rejections and fewer false acceptances. The level of security may be determined by the application or may be set at a permanent level. Test 30 compares the characteristic distance with the threshold set during enrolment, with an offset for the level of security made if required. If the characteristic distance is greater than the adjusted threshold the signature is rejected as a forgery (operation 31); if it is lower than the adjusted threshold then the signature is accepted as authentic (operation 32).

Figure 3 is a more detailed description of operation 15, in which projection profiles of the signatures are extracted. A projection profile is a feature which is a function of the representation of the signature and is comprised of a plurality of values. Operation 35 pre-processes the representation of the signature, which is usually a pixel matrix. This pre-processing may centre or scale the representation as necessary, and may also include other image analysis necessary to reduce the noise in the image. Operation 36 produces a horizontal projection profile and operation 37 produces a vertical projection profile for the pixel matrix representing the signature. The horizontal projection profile H at a point y on the vertical axis is given by

max(x) H(y) = Σ Kx.y) ⁽1⁾ x=l where I represents the pixel matrix containing elements of either

1 or 0. Similarly the vertical projection profile V at a point x on the horizontal axis is given by

max(y) V(x) = Σ Kx.y) (2⁾ y=0 Operation 38 applies a three point averaging function (three point smoothing filter) to both the horizontal and vertical profiles. Thus the projection profile is a digital summary of the two dimensional image projected onto a given axis.

Figure 4 shows a digitised representation of a signature 41, and the horizontal projection profile 42 and the vertical projection profile 43 derived therefrom.

Figure 5, which shows in detail operation 20, selects the best signatures from the previously captured signatures. Operation 50 sets the reference signature pointer to the first signature captured. Operation 51 sets the test signature pointer also to the first signature captured. Operation 52 sets the running average distance for the reference signature to zero. Test 53 compares the reference signature pointer with the test signature pointer and if the two are equal, which at this stage will be the case, increments the test signature pointer by one (operation 56). Test 57 determines whether all of the captured signatures have been used. If this is not the case the system moves back to test 53. Since the reference signature pointer and the test signature pointer are no longer equal, the system moves on to operation 54. Operation 54 calculates the cumulative distance between the reference signature and the test signature and is described more fully in Figure 8. The running average distance is calculated from the cumulative distance in operation 55. The test pointer is advanced by one in operation 56 and stages 53 to 57 are repeated until the last signature captured has been used (test 57). The final running average distance becomes the characteristic distance and operation 58 assigns the new characteristic distance to the reference signature. Operation 59 advances the reference pointer by one and stages 51 to 60 are repeated until every captured signatures has been compared with every other signature. Operation 61 rejects those reference signatures with the highest characteristic distance, as these will be those signatures which differ most from the remaining signatures. The number of signatures rejected depends on the number of signatures captured. If five signatures are captured and the two signatures with the highest cumulative distance will be rejected, the remaining three reference signatures will form the basis of the verification procedure.

Figure 6, which describes in detail operation 21, generates a threshold value for use in the verification process, based on the reference signatures remaining after operation 61. Operation 62 sets the maximum cumulative distance between the reference signature and the test signature to zero. Operation 63 sets the reference signature pointer to the first remaining signature. Operation 64 sets the test signature pointer to the first remaining signature. Test 65 compares the reference signature pointer with the test signature pointer and if the two are equal, which at this stage will be the case, increments the test signature pointer by one (operation 69). Test 70 determines whether the test signature pointer is pointing to the last remaining signature. If this is not the case the system moves back to test 65. Since the reference signature pointer and the test signature pointer are no longer equal, the system moves on to operation 66. Operation 66 calculates the cumulative distance between the reference signature and the test signature and is described more fully in Figure 7. Test 67 compares the distance returned by operation 66 with the maximum value. If the cumulative distance is greater than the maximum cumulative distance operation 68 sets the new maximum to that distance returned by operation 66. Operation 69 advances the test pointer by one and stages 65 to 70 are repeated until all of the signatures have been used. Operation 71 advances the reference signature pointer by one and stages 65 to 72 are repeated until every signature has been compared with every other signature. The threshold value is then set to the maximum cumulative distance recorded by operation 68.

Figure 7 shows in detail operation 28, which finds the characteristic distance between a test signature and a set of reference signatures, and in particular an unauthenticated signature and a set of authenticated signatures. Operation 74 sets the reference signature pointer the first of a set of references signatures retrieved during operation 27 and sets the running average distance to zero. Operation 75 calculates the cumulative distance between the test signature and the first reference signature and operation 76 calculates the running average distance from the cumulative distance. Operation 77 advances the reference signature pointer by one and stages 75 to 78 are repeated until test 78 determines that all the reference signatures have been used. The running average distance then indicates the characteristic distance between the test signature and the set of reference signatures (operation 79).

Figure 8 describes in detail a method of calculating the cumulative distance between a test signature and a reference signature, (operations 54, 66 & 75). In this example the method uses the projection profiles which were derived in operation 15. In this method a cost g(i,j) at a point (i,j) is defined as the difference d between the amplitudes of the respective projection profiles and the cost of moving to that point from adjacent points, and is given by,

g(i,j-l) + d(i,j) g(i,j) = min g(1-l , -1 ) + 2d(i ,j) (3) g(i-l,j) + d(i,j) The function d is given by d(i,j) = |H_r(i) - H_t(j)| + |V_r(i) - V_t(j)| (4) where H_r(1), H_t(j , V_r(1) and V_t(j) are values of the horizontal and vertical projection profiles at points i and j, and d(i,j) is the difference between the amplitudes of the respective projection profiles. The cost g is a measure of similarity between the two signatures; the path of maximum similarity is given by the line i=j. Operation 80 sets the reference pointer i to the start of the horizontal and vertical projection profiles of the reference signature and test pointer j to the start of the horizontal and vertical projection profiles of the test signature. Operation 81 sets the distance g(0,0) to twice d(0,0) and operation 82 advances the reference pointer by one. Operation 83 sets the test pointer j to the base of a window, which is defined as an area centred around the point indicated by the references pointer. The size of this window may be varied from 5% to 25% of the size of the profiles and typically may be ±5% around i=j. If each projection profile is a discrete function comprising 100 points then a window of ±5% will contain 10 points. Operation 84 calculates d(i,j) according to equation 4 and operation 85 determines the minimum distance from the minimum of g(i,j) according to equation 3. Equation 3 is a recursive equation and if a value for a point g(i+m,j+n) has not been previously determined, either by the operation 81 or from a previous calculation, then g(i+m,j+n) is set to infinity. This means that any point which falls outside of the window and which is used in determining g(i,j) according to equation 3 is given a value of infinity in operation 85. An alternative method is to set all g(i,j) to infinity except for the seed point (g(0,0)) during operation 81 and redetermine those g(i,j) necessary during operation 85. Operation 86 advances the test pointer by one and stages 84 to 87 are repeated until the test pointer is outside the window (test 87). If a 10 point window is used then stages 84 to 86 will be repeated 10 times. Stages 82 to 88 are repeated until test 88 indicates that the reference signature has been scanned through completely. Finally, operation 89 searches back through the last window for the lowest minimum distance g(i,j), which is then assigned as the cumulative distance between the two signatures. While the invention has been specifically described above it will be apparent that the invention can be put into practice in many other ways and in particular may be used for verifying any other entity apart from a signature. The static feature selected may be any feature which is made up from a plurality of values, such as a projection profile projected onto the x=y axis or a perimeter profile. The number of values of a representation of an entity which are compared with one value of a representation of a corresponding entity, and from which the minimum distance is derived may be varied. Other dynamic programming techniques may be used on the projection profiles and in particular the methods of determining minimum distances may be altered.

Claims

1. A method of verifying the authenticity of a representation of an entity comprising the steps of selecting at least one static feature of members of a set of authentic representations of the entity, the feature consisting of a plurality of values, selecting a corresponding static feature of an unauthenticated representation of the entity, the corresponding feature consisting of a plurality of values, comparing the feature of the unauthenticated representation with the corresponding feature of each of the authentic representations by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, deriving from the minimum distances a characteristic distance between the unauthenticated representation and the set of authentic representations, and determining from the characteristic distance the authenticity of the unauthenticated representation of the entity.

2. A method of selecting a set of authentic representations of an entity comprising selecting at least one static feature of members of a set of genuine representations of an entity, the feature consisting of a plurality of values, comparing the feature of each representation with the corresponding feature of each other representation by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, deriving characteristic distances between each representation and the other representations, and rejecting a previously determined number of representations with the highest characteristic distances in selecting the said set of authentic representations.

3. A method according to Claim 1 or 2 wherein each feature is a dependent variable which is a function of an independent variable, the values are values of the dependent variable, and corresponding values are values of the dependent variable at the same independent variable value.

4. A method according to Claim 3 wherein in comparing features, a number of different features of one representation are compared with corresponding features of another representation by carrying out the said groups of comparisons, and each minimum distance is determined from a set of the comparisons of each group for corresponding ranges of independent variable values of at least two different features, and the method includes deriving a number of cumulative distances, one for each comparison of a number of features of one representation with corresponding features of another representation from at least the minimum distances derived from the groups of comparisons used in comparing the said number of features with the said corresponding features, and deriving the characteristic distances from the cumulative distances.

5. A method according to Claim 4 wherein each cumulative distance is found by summing set costs, one for each said set of comparisons. each set cost being determined by adding the minimum distance for a set of comparisons to the minium of a number of sums, each sum being formed by adding the set cost of a previous set of comparisons to a cost dependent on the difference in the independent variable values corresponding to the said one value of the previous set and the set, the cost of which is being determined.

6. A method according to Claim 1, or Claim 3, 4 or 5 insofar as dependent on Claim 1, wherein the cumulative distances obtained by comparing features of the unauthenticated representations with corresponding features of each of the authentic representations are averaged to derive the characteristic distance.

7. A method according to Claim 2, or Claims 2, 4 or 5 insofar as dependent on Claim 2, wherein the cumulative distances obtained by comparing features of each genuine representation with corresponding features of each of the other genuine representations are averaged to derive the characteristic distance.

8. A method according to Claim 1 or any of Claims 3 to 6 insofar as dependent on Claim 1, wherein determining the authenticity of the unauthenticated representation is by comparing the characteristic distance with a threshold.

9. A method according to Claim 8 including selecting a set of authentic representations according to Claim 2 or 7, or any of Claims 4 to 6 insofar as dependent on Claim 2, and setting the threshold of the average of the characteristic distances of the said set of selected authentic representations.

10. A method according to any preceding claim wherein the entity is a signature and the static feature selected is the horizontal or vertical projection profile of a representation of the entity.

11. A method according to Claim 4 or 5, or Claims 6 to 9 insofar as dependent on Claim 4, wherein the entity is a signature and in comparing features, two features are compared, these features being the horizontal and vertical profiles.

12. A method according to any of Claims 1 to 9 where the entity is a person's signature and the representations of the entity are representations of signatures.

13. A method according to any preceding claim wherein the representation of the entity is created when the entity is created.

14. A method according to any of Claims 1 to 13 wherein the representation of the entity is created at a time after the entity is created.

15. A method according to any preceding claim wherein the representation of the entity is created from a digitised image of said entity.

16. Apparatus for verifying the authenticity of a representation of an entity comprising means for selecting at least one static feature of members of a set of authentic representations of an entity, the feature consisting of a plurality of values, means for selecting a corresponding static feature of an unauthenticated representation of the entity, the corresponding feature consisting of a plurality of values, means for comparing the feature of the unauthenticated representation with the corresponding feature of each of the authentic representations by carrying out groups of value comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said first feature value, and determining from each group of comparisons a minimum distance, means for deriving from the minimum distances a characteristic distance between the unauthenticated representation and the set of authentic representations, and means for determining from the characteristic distance the authenticity of the unauthenticated representation of the entity.

17. Apparatus for selecting a set of authentic representations of an entity comprising means for selecting at least one static feature of members of a set of genuine representations of an entity, the feature consisting of a plurality of values, means for comparing the feature of each representation with the corresponding feature of each of the other representations by carrying out groups of comparisons in which at least one value of a first of the features is compared with a range of values of a second of the features, said range extending over values which include a second feature value which corresponds to the said one first feature value, and determining from each group of comparisons a minimum distance, means for deriving from the minimum distances a characteristic distance between the one representation and the other representations, and means for rejecting a previously determined number of representations with the highest characteristic distances in selecting the said set of authentic representations.

18. Apparatus according to Claim 16 or 17 for authenticating signatures wherein the entity is a signature, including graphical input means or scanning means for forming representations of signatures.

19. Apparatus according to Claim 18 wherein the apparatus comprises computer means and the set of authentic representations are, in operation, stored by the computer means.