A brief survey of Approaches to Signature Verification

David Feil-Seifer and Benjamin B. Kimia

Introduction:

Signature verification is an extremely active research area. Although systems exist on the market, there are few that can promise sufficiently high accuracy rates at a reasonable level of efficiency. Few have reached correct recognition rates above 95% and those that are are extrememly time consuming. What will be explored below is what several of the leading groups in signature verification are doing to solve this problem.

Requirements of a signature verification system;

When considering a signature verifiaction system, there are many factors which go into making that system effective. First, data collection has to be sufficently accurate. Next, identification of the signature as the correct signature, to make sure that the signed name is the correct name. Following that, there must to be some determination as to whether or not the given signature is accurate or a forgery. Currently data collection is largely a solved problem, data tablets exist at a sufficient resolution, both spatially and temporally, to acquire accurate data. The other two problems have been attempted with moderate to reasonable success, but there is still room for improvement. Accuracy and/or proccessing time for the given systems must be improved in order to make any signature verification system a distributable and marketable technology.

Groups and their activities:

On-line recognition system. Basic unit of measurement is pen-tip velocity. The system runs on the assumption that movements of pen are more characteristic than ink trace. Look for regularities and lawfulness in writing process. This approach is not suited for children or handwriting with tremor because it is sensitive to speed and regularity.

System works as follows:

• Tablet decodes x and y points with a timestamp.
• Using timestamp, velocity is derived.
• Points are grouped into strokes (Character classification)
• Character Hypotheses are made and tested (Word search)
• Word Hypotheses are made and tested (Word List)
• Work list is outputted

Velocity Based Stroke is the is the trajectory between two consecutive minima in the pen-tip velocity.

VBS has 14 properties:

• Vertical starting point with reference to baseline
• Vertical end point
• 5 Angles of spatially equidistant sub-vectors
• 2 Angles from the end of the previous stroke
• 2 Angles from the beginning of the next stroke
• loop area, zero if there is no loop
• percentage pen-up time, zero if all ink
• length of the stroke trajectory

Example Word:

The system groups strokes together on a self-associating graph. Graph's weights are the probabilities that one stroke can transition to another stroke. When the system is in the recognition phase, it looks at predecessor and successor strokes. This is a system to deal with handwriting recognition, but it has applications in both signature verification and handwriting recognition. In particular, the metrics for the velocity-based strokes are extremely applicable to a user-specific comparison. There are several things to note about this group. First, this is a system that spawned the UNIPEN format. It's worth it to become familiar with that format since they hold a large database of handwriting that is velocity based. Second, NICI maintained a large listserv e-mail list on handwriting recognition. A lot of novel ideas are posted there. (Date Unknown)

Created on the basis of making a point-of-sale product. Collects 49 features of a signature. None of them are related to the shape of the signature.

15 are static off-line features:

• maximum distance between the highest and lowest points
• signature length
• standard deviation of x / change in x, y/change in y
• ((x|y)(min|max)-(x|y)(0|end))/change in (x|y)
• initial direction

34 are dynamic features such as:

• maximum forward velocity
• where and when in the signature max velocity occurs
• first time instance of v = 0
• average velocity over x and over y
• average writing speed
• number of pen ups and downs
• time of second pen down
• direction at first pen down, first pen up
• total dots recorded
• duration of negative x and y velocities
• duration of positive x and y velocities

The system also relies on two assumptions:

1. Temporal Assumption: an instance of an event will occur at rougly the same place of the writing duration regardless of the overall signing speed.
2. Spatial Assumption: linear scaling of the horizontal and vertical displacements will restore signatures to their genuine shape.

While it is unproven whether these assumptions are necessarily absolute, they would restrict the signature verification problem quite a bit, especially in the normalization stage.

With 1% false rejection, there is a 20% false acceptance error. This error is when using the best 15 features out of the 49 feature set. For timed forgeries done by a skilled forger, there is 50% error. This timed forgery requires the forger to watch signing, and imitate timing as well as shape. Especially important here is that no shape comparasion is used. This system is very focused on the dynamics of the signature, however there are some interesting focuses to the dynamics. Chief among them is the points at which direction and velocity are measured. Measuring the velocity and direction at pen up and down points would certainly show characteristic references specific to a signer and not related to shape. These dynamic features should certainly be examined much more closely. Computationally not intensive, can be run on a 486. The news article said that this group was applying for a patent. (1996)

Online system employing a Hidden Markov Model. Equal error rate of 2.5%, at 1% false rejection, error rate is 5%. System creates a universal prototype of signatures from a preconceived database. Each new signature type is assigned a distance from the prototype along a few measurements.

21 Global features considered: (Global features = pen-down segments or whole signature)

• total signature time
• time of pen down
• rms speed
• average horizontal speed
• integrated absolute centripetal acceleration
• length-to width ratio
• horizontal span ratio
• 8 directional histograms
• 4 directional change histograms
• x,y speed correlation
• first moment

Local features considered: (Local features = equally spaced sub-segments or every signature sample point)

• slope of the tangent at each point

Model parameters are estimated from a list of valid signatures. For signature modeling, the system uses the handwriting tangent and its derivative as a vector. Signature normalization is considered an important step of the process. Worries about rotation and other locational transformation. Uses global features that do not related directly to the shape of the signature. Hidden Markov Model is used to test local features of the signature. This model is trained using segmentation done by the Viterbi algorithm as well as parameter re-estimation along the optimal path. (1997)

This paper compared online and offline models of signature verification. It emphasized that signature verification must account for length and height variations, which occur, even when the same person signs their name twice. The use of HMM's has been more and more popular in speech recognition and for handwriting recognition. HMM's are a powerful tool for modeling time-varying dynamic patterns. Train HMMs to recognize individuals' signature cues. Also uses a feature-extraction system which looks at:

• absolute angle
• difference angle
• a local pixel window (30x30)
• velocity acceleration
• frequency vector
• pressure

Picture of the local pixel window:

Off-line system is much simpler as it only looks at the pixel image. That pixel image is subdivided and analyzed as a gray-level comparison. Results of the off-line and on-line systems show preference for on-line verification system. The on-line system had 99% accuracy with the following features targeted, local pixel window, velocity, Fourier, and pressure. The off-line system had an accuracy of 98.1%. Where this system falls short is that it appears to be computationally intensive. Between a direct pixel comparison and a Fourier transform, this system does not appear to be very efficient. While it would be very hard to improve upon the accuracy shown here, it would be extremely plausible to improve on their running time. For testing the system used a database of 14 people, each training the system with 16 signatures. The system was tested using 40 skilled forgeries (by people making an effort to copy the structure of the signature, unknown how skilled the forgers were) and 20 random forgeries. This is a smaller sample than other systems that were tested. (>1997)

Employs a 3 expert system that evaluates the signature three different ways and judges it as genuine or forgery or rejection by a majority vote of the three. Again makes an attempt to gauge more than just the ink trace on the paper. The three experts work as follows:

1. Shape-based features and holistic analysis.
2. Speed-based features
3. Regional Analysis

Graphic tablets or integrated graphic-tablet displays perform data acquisition. This requires a certain amount of pre-processing to eliminate noise and prepare data for future processing (correct format). The segmentation of the signature into important segments is performed here. Then relevant features are extracted from the pre-processed signature. Then the verification experts take over. For the reference database, two approaches are used. First, a prototype could be used with additional data on writer variability, or actual signature samples could be used and the test signature could be compared directly against that. The experts perform in the following ways:

1. The first expert performs a holistic analysis based on the segmentation results:
   • segments the test signature according to the characteristics of the reference signature(s)
   • detects local minima and maxima (Candidate Splitting Points (CSP))
   • determines the warping function between the CSPs which minimizes quantity
   • matches the CSPs between the reference and test signatures

     

   • result is: number of splinted strokes of the test signature/number of candidate splitting points of the test signature
   • result is evaluated in terms of user-specific thresholds
2. The second expert adopts a regional verification strategy using elastic matching procedure segment by segment:
   • matches the stroke against corresponding strokes of the reference signature(s)
   • speed-based dissimilarity is used to construct a threshold
   • this threshold is used to evaluate the test segment
   • result is: length of genuine strokes of the test signature/length of the test signature
   • result is evaluated in terms of user-specific thresholds
3. The number of valid strokes the metric for the third expert:
   • using the stroke data generated by the previous expert
   • result is: number of genuine strokes of the test signature/number of strokes of the test signature

Three possibilities can come out of this system, genuine, false, or rejected. The system has the following error: 3.2% false rejection, .55% false acceptance with 3.2% undecided rejection rate. The multi-expert system presented is conducive to adding more experts and possibly adjusting the weight of how much each expert votes. It's also possible to give one expert "veto-power" over the others. This system is the best one shown which combines the global and local verification data. The accuracy could be improved greatly by changing the way that local data is evaluated by incorporating curve matching into this system. (>1999)

This system works by capturing velocities at each point. Author stresses, however, that one cannot exclusively depend on them because pen dynamics are not reliably consistent even from one signing to another. Velocities are hard to copy however, so they make good forgery detectors. It is still necessary that the shapes of the signatures correspond for the signature to be genuine. Look at both local and global models. Weighted and biased harmonic mean as a way of combining errors from multiple models.

Key Concepts:

• Harmonic Mean - ORs the errors by hyperbolical isocontours instead of ANDing the errors by root weighted mean squared method of reducing error.
• Jitter - results from a forgery. Greater than sampling error jitter.
• Aspect Normalization
• Parameterization over Normalized Length - spatial rather than temporal metric?
• Sliding Computational Window
• Torque
• Moments of inertia
• Moving Coordinate Frame and Saturation - get a complete list of functions normalized along length of the signature
• Weighted cross-coordination and warping - see algorithm.

A process of Normalization, Description, and Comparison verifies signature. The comparison is distinctive because of the harmonic mean process of judging discrepancy between test and reference cases. Error - equal error of 3%, 2%, and 5% depending on the database, based on the skill of the forgeries. (1997)

This system focuses not on signature verification, but instead on signature identification. The system codes certain aspects of the signature into a string, then enters the signature into a database based on a hash-code of that string. The following is what is coded into the string:

• Loops End Point
• Branch Point
• Crossing Point
• Convex Point
• Concave Point

The system then has a fast and efficient way of comparing and indexing the strings. This system would not be very useful in signature verification because it is not very user-specific. But does have a nice method of cataloging the features of handwriting. With more features included, the recognition rate could climb a bit higher (1995).

This system works with both static and dynamic features. Also, in contrast to a lot of other systems, the system compares features based on polar coordinates. It's unknown how much this helps recognition because they are using Chinese character exclusively. The algorithm works by splitting the signature into two parts at different points and evaluating each part separately. Further segmenting the signature does this. Comparison is done by comparing the differences in distance and velocity of the signature for each segment. Not much attention is given to the details of comparison, mainly to the split and merge algorithm. The system has a correct acceptance of 86.5% and a correct rejection rate of 97.2%. (1997)

While this group was focusing on signature identification instead of signature verification, this paper is important because of their focus on an active vision system. They go into extensive detail as to their approaches to threshold and also to normalization. For normalization, they attempt only an orientation normalization because of the deformable structure system that they use.

Deformable structure:

They do no size normalization. As to thresholding, they have to have rigorous thresholding to establish a binary image of the signature (signature acquisition is done off-line). An optimal threshold is selected in order to maximize the serparability of the resultant classes into gray levels. The results for this group on the identification task are not as good as the others, but they are tackling a somewhat harder problem due to their use of deformable models. The deformable models attempt to create a vague outline of the signature in order to make it easier to classify. This technique would be hard to implement in the case of signature verification. They have a 78.9% accurate system, with 18.3% inconclusive data and 2.8% false recognition. (1998)

This group used a neural network in their model, which is not what is interesting about this paper. What's important about this paper is that it illustrates the difference in error in deliberate forgeries versus the error that random forgeries such as signing someone else's name can cause. The system of signature verification for non-related forgeries or random signatures had an equal error rate of .25%. However, when they entered deliberate forgeries into the mix, the error rate climbed quite a bit 2.29% false acceptance and 7.1% false rejection. This stresses the importance of using reasonable forgeries in test data to truly test forgeries.

This paper outlines the curve-matching algorithm which will be used in this new signature verification system. The system was applied to handwritten character recogntion on an off-line basis, but only of one-stroke characters. The system performed with an accuracy rate of 98%. The curve matching algorithm works by comparing the curves using an alignment curve. The curves are then judged in reference to each other by an edit distance by how much length and curvature have to be adjusted in order to align the curves. There are issues with using this method which are outlined below. The notion of an alignment curve can be used when creating a prototype of each segment of the signature.

These segments can be joined together to form the entire signature for a prototype. Examples of average curves to aid in alignment were shown with examples of different bone and brain structures which were then averaged for a prototype of that structure. The ultimate strength of this method of curve matching is that it works on the basis of comparing the intrinsic properties of a curve. Intrinsic recognition is an especially important part of the shape-comparasion part of signature recognition.

Summary of groups' activities:

Signature verification is currently feasible. Many different methods have been tried with varying results. About the best results so far have been about 99% at the best. While that does not seem to leave room for improvement, there is a great deal of speed improvement to be done. Thesystem explained in the Rigoli paper used in the comparison uses several time-intensive methods in order to make the comparison. A relatively speedy system with comparable accuracy has yet to be developed. Thomas Sebastian's curve-matching technique could replace the Hidden Markov Model approach to signature recognition which most of the competing systems have used. There are several ideas from previous projects that should be preserved in order to construct a new system:

1. The new system should be an on-line system. Although a paper comparing the two systems found that they performed within a single percentage point of accuracy, the method for verification was extremely intensive, and that percentage point is extremely important at the high a level of recognition.
2. While shape is an integral part of signature verification, it is a metric that is most easily imitated by a forger. Dynamic factors such as signature velocity characteristics are especially important for catching experienced forgers.
3. Global factors of the signature should be considered as shown in that Kashi paper and in the Lee paper. There were many global features that were charted over the span of the signature. These factors if expanded upon and thought out further could be a powerful tool in signature verification.
4. Signature segmentation into individual strokes is a priority to facilitate more accurate curve matching. This segmentation has been approached in many ways, but one of the best is to look for local minima of pen-tip velocity.
5. A multi-expert system should be considered to integrate the different methods of verification. The benefits of this system include a convenient way to handle inconclusive results, and a good way to handle user-specific variations at each level of verification such as global and local variation.
6. Local factors should not merely include curve matching, but also should include provisions for such factors as pen-down time and percentage of local curve length with respect to the entire signature length. These factors expand the system beyond a mere structural comparison system, thus making forgery detection more likely.
7. One of the strongest approaches to signature verification is the proper setting of thresholds. Training the system for each user with a certain amount of signatures should not only yield a prototype signature, but also several thresholds that are specific to the user and to all of the metrics we are using.

Description of new approach:

The following is an outline of what I feel would be the best approach to signature verification:

1. Signature data is captured on-line. Data captured would include position coordinates with a time stamp so that velocity can be derived as well. Possibly pressure data could be captured as well, allowing for that to be used as a metric.
2. A certain amount of pre-processing could occur to filter out noise. More research would have to be involved to figure out what noise is irrelevant to signature verification and which is actually helpful, i.e. jitter effect could actually prove that a forgery occurred.
3. Segmentation of the signature into parts. Segmentation occurs naturally at pen up and pen down points. Also used for segmentation would be local minima for velocity. If there is enough of a precedent to, pressure data could also be used for segmentation. Segments should not be individual strokes, however, since individual stroke data might not be as accurate as segment data. This could be controlled by some velocity threshold.
4. Local features such as a segment comparison would be computed by using the curve matching system. Segments would be accepted or rejected based on user-specific thresholds set during training.
5. Global features such as velocity histograms and pressure data would be computed based on training data. This allows the system to detect features of a signature characteristic to the signer.
6. All comparison data would be combined into a single value using some sort of voting system based on the different metrics.
7. Genuine, rejection, or forgery would be returned by the system.

The strengths of this approach are that it combines the best qualities and the proven best and/or most efficient metrics from each study into one system. The Wacom tablet available will be sufficient for data collection. Something that will have to be given special attention when further designing this system is to look at qualities which a forger cannot duplicate easily, but is easily verified in the natural signer. These metrics are going to be the most useful in a practical and accurate signature verification system.

Trouble Spots:

• The curve matching algorithm might have issues with characters. Length and curvature are the two factors used in the curve matching algorithm. As shown below, there no length difference and only a curvature difference at one point in the curves below. This would make the edit distance of the two curves relatively small, thus making each pair of curves relatively equal when they are not.

• Ways to minimize error, improve both forgery detection and signature recognition. With an equal error rate of 3%, one has created a robust system. But in order to get the false rejection rate down to 1%, one might have to take steps to increase the false acceptance rate to as much as 8 or 10%. This is very detrimental. To remedy this, the system should be tweaked in order to promote better strategies for both correct rejection and correct acceptance, not just reducing the error in one metric or the other. One way to do this is to focus both on what make a correct signature and what makes a forgery and deciding a way to detect both.

• There is some doubt as to what makes a feature a good feature. Several of the the features used so for have no justification as to why they were used in the system. Some research will have to be done to establish this area more.