US 7474770 B2
The fields of biometrics and commerce can benefit from the aggressive compression techniques presented here. A novel approach to compressing the on-line handwriting signal without losing the dynamic information (i.e., velocity and order) is presented which provides the means to fit almost any signature sample within the 57-byte limit of one of the free magnetic strips on the back of conventional transaction cards such as credit or debit cards or other identity cards. The apparatus requires an on-line signature capture tablet capable of sampling the handwritten signature in a series of sampled X and Y coordinates. The compression method starts with segmenting the on-line handwriting signal into portions which may be approximated with a set of features from which the velocity and position may be reconstructed. These features are then compressed further using standard compression techniques. A Huffman coding technique is used to demonstrate this step. The size of the average signature including its dynamic information is stored in a space less than 57 bytes which is the magic limit imposed by conventional, magnetic transaction (credit or debit) card strips. This is by far less than about 1000 bytes required if only loss-less techniques were used. A loss-less compression technique is also briefly presented. Normally, out of the three strips which are provided on the back of a card, two strips are available and may be used for storing the template of the owner's signature for future verification.
1. In a system that captures handwriting on a digitizer tablet, a method performed by a processor for generating and storing data representing the handwriting comprising:
said processor processing the captured handwriting to identify strokes of the handwriting;
said processor partitioning each stroke into a plurality of segments;
said processor generating a plurality of parameters for each segment;
said processor generating a compressed representation for each given segment by transforming the parameters for the given segment;
said processor generating data representing the handwriting based upon the compressed representation for each given segment; and
said processor storing the data representing the handwriting.
2. The method of
the partitioning involves identifying points with zero velocity along a predetermined direction.
3. The method of
the predetermined direction is selected from the group including an x direction and a y direction.
4. The method of
the plurality of parameters for a given segment are dynamic features derived from a second order mechanical model of a hand and stylus movement on the digitizer tablet.
5. The method of
the parameters for a given segment represent velocity along two orthogonal directions.
6. The method of
the parameters for a given segment include
i) first components representing amplitude for each one of the two orthogonal directions;
ii) second components representing frequency for each one of the two orthogonal directions;
iii) third components representing phase for each one of the two orthogonal directions;
iv) fourth components representing mean velocity for each one of the two orthogonal directions; and
v) a fifth component representing initial position of the given segment.
7. The method of
the transforming of the parameters of a given segment comprises reducing the number of parameters for the given segment.
8. The method of
reducing the number of parameters for the given segment is accomplished by using one of the second components associated with a corresponding one of the two orthogonal directions to represent frequency for the segment along both of the two orthogonal directions.
9. The method of
reducing the number of parameters for the given segment is accomplished by using the phase difference between the third components for the two orthogonal directions to represent phase for the segment.
10. The method of
the transforming of the parameters of a given segment comprises reducing bit length quantization of at least one component of the parameters of the segment.
11. The method of
reducing bit length quantization of at least one component of the parameters of the segment is accomplished by using 4 bits to represent each one of the first components for the two orthogonal directions.
12. The method of
reducing bit length quantization of at least one component of the parameters of the segment is accomplished by using 5 bits to represent each one of the second components for the two orthogonal directions.
13. The method of
the transforming of the parameters of a given segment comprises reducing bit length quantization of data derived from the parameters of the segment.
14. The method of
comprises reducing bit length quantization of data derived from the parameters of the segment is accomplished by using 4 bits to represent a phase difference along two orthogonal directions for the segment.
15. The method of
generating a non-linear table associated with a given parameter to provide increased resolution.
16. The method of
applying a coding scheme to the data representing the handwriting.
17. The method of
the coding scheme employs Huffman Coding.
18. The method of
the handwriting is a signature.
19. The method of
the data representing the handwriting is stored on the memory of a transaction card.
20. The method of
the data representing the handwriting is stored on media in accordance with ISO-7811/2 standards.
21. In a system that captures a handwriting sample on a digitizer tablet, a method embodied by a processor for verification of the handwriting sample comprising:
said processor storing data representing a handwriting signal in accordance with the method of
said processor accessing the stored data representing the handwriting signal and converting such data to parameters for the segments of the handwriting signal;
said processor processing the captured handwriting sample to generate parameters for segments of the handwriting sample; and
said processor comparing the parameters of the segments of the handwriting signal to the parameters of the segments of the handwriting sample to make a verification decision.
22. A method according to
the comparing involves calculating a distortion measure between the parameters of the segments of the handwriting signal and the parameters of the segments of the handwriting sample.
23. A method according to
said processor processing the parameters for the segments of the handwriting signal to reconstruct the handwriting signal for display.
1. Field of the Invention
This invention relates to the field of biometrics as well as storage and retrieval of the dynamics of handwriting on limited space media and it specifically relates to the storage, retrieval and verification of signatures preserving the dynamic information on small memory devices such as the back of a transaction card (credit, debit or ID card).
2. Description of the Related Art
In 1995, Kodak scientists presented an aggressive image compression technique for coding the photo of a credit card holder in one of the three 57-byte magnetic strips available on the back of conventional credit cards. A more important or perhaps complementary piece of information which should be stored on one of these strips is the signature of the individual. Currently, the signature is written on the back of the credit card and is available to any forger to see at the moment of making purchases. In addition, this is only a static image of the individual's signature and lacks the dynamic information such as velocity, order and pressure at different portions of the signature. This dynamic information can substantially increase automatic signature verification results.
In their patent (U.S. Pat. No. 5,466,918), Ray, et al. provide a method for storing a human image (a biometric on the back of a transaction card which allows less than 57 bytes of storage). Here, I provide a method and apparatus for storing the full dynamic information of an on-line signature on the same medium. This data may be used to render the image of the signature or to act as a biometric template verifying the full dynamics of the signer's motion while signing and not just the image. The image is easy to forge by practicing, but the dynamics such as changes in velocity at different locations in the signature are much harder to forge even for professional forgers. In a dynamic template the order of the points in the image is preserved as well as the speed at different points in each stroke of the signature.
Low quality tablets have recently been installed at many department store cash registers to obtain electronic signature samples from customers. These samples are, however, still being treated as images and their dynamic information is not being used. For on-line verification, part of the problem is the storage of the signature templates which would have to be done at a central location accessible to stores through a network. This would be an expensive system which although is quite warranted, will not be easily attainable in practice since many stores do not have network connectivity. A self-contained signature verification system would be made possible if the credit card of the individual included his or her signature sample electronically. The electronic information may also be used to render the signature on a screen for the store manager to review and compare against the individual's signature at the time of purchase.
Van Leer in his patent number U.S. Pat. No. 4,005,878 uses a moving surface while the signature is being created to change the shape of the signature to make forgeries hard. It uses the image of the signature and forfeits the usage of any dynamic information.
Nair, et al. in their patent number U.S. Pat. No. 5,428,210 discuss a scenario which requires that the signature (although compressed) be sent to a server to authenticate the card-holder. This is due to the inability of the compression scheme discussed the invention to produce small enough templates. Also, they again do not use the dynamic information of the signature. Price, et al. in their patent number U.S. Pat. No. 5,448,044 use the image of a signature. They talk about comparing the facsimile of the captured signature to the image signature signed on the back of the credit card. This does not use dynamic information. The dynamic information is quite important in reducing the possibility of a forgery. It also defeats the purpose of capturing the electronic signal since the forger will be able to see the signature on the back of the card and to practice forging it. Since only the image is used by an operator to match the two signatures, forgeries may be easily accomplished.
Beatson et al. in their patent number U.S. Pat. No. 5,892,824 are forced to use an IC card to be able to store the image of a signature as stated in their invention's description (stated toward the beginning of column 19). In this description they state that the image of the signature is different from the biometric template and state earlier in the patent that the image takes up about 500 bytes requiring an IC card. My invention provides a biometric template which not only includes the full dynamic information such as the velocity at different points in the signature (much harder to forge than just shape), it also provides an image of the signature to be displayed on the monitor of the merchant which may also be used by the merchant to verify the signature of the customer. This eliminates the need for having a handwritten signature in ink on the back of the credit card and makes the job of a forger much harder.
In this patent, as a matter of comparison, I will present a loss-less compression scheme which will produce coded signatures of requiring over 1000 bytes for coding an average on-line signature. This is not nearly enough for our objective of an upper limit of 57 bytes, but it certainly has its own applications.
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional systems and techniques, the present invention has been devised, and it is object of the present invention to provide a structure and method for storing the dynamic information of the handwriting (signature) on limited space media such as the magnetic strip on the back of a transaction (credit, debit or identity) card with the capability to reconstruct the image of the signature as well as the full dynamic information to be used for verification purposes.
To attain the objects above, according to one aspect of the invention, a computer-implemented method for modeling and encoding the dynamics of the handwritten signature, includes the feature extraction of the signature based on an input from a stylus pen capable of producing a sequence of coordinates sampled through time and presented to a CPU to process and produce a set of parameters representing the dynamics of the signature as well as its shape and which fit on average in less than 57 bytes which is the limit imposed by the space available on the magnetic strip on the back of conventional transaction cards. This information is then stored on the back of the transaction card at the time of registering the transaction card at the issuing institution or affiliates as the template of the signature of the holder of the card. At the time of usage, the information is retrieved from the back of the transaction card and may be used to reconstruct the signature in its entirety including the image of the signature and all its dynamic information. The dynamic information is generally much harder to forge than the image of the signature since any forger, by practicing, can learn to forge the shape of a signature in time. However, the forger will not be readily able to forge the speeds at the different locations of the trace of the signature. This information without the presented compression would amount in average to over 1000 bytes of information which is not storable on conventional transaction cards and hence has generated ideas by other inventors in using devices with more memory such as smart-cards. This invention eliminates the need for such media (smart cards and extra memory) and allows conventional credit cards with conventional systems to be used to attain this goal with great efficiency.
A methodology is presented her for compressing all the dynamic information within an average signature to less than 57 bytes so that it may be included on the back of a credit card. In addition, it requires less storage than storing the actual x and y coordinates and it maintains all the dynamic information as well. In addition to biometric applications, since the order and velocity information are conserved, stored on-line handwriting data may be used by on-line recognizers without much degradation in accuracy results. The promised lossy compression technique is formulated by first segmenting the signature into smaller pieces. Each piece is subsequently modeled by only six or less parameters. These parameters may be further compressed using quantization and tabulation. Finally, Huffman coding scheme is used to further reduce the size of the signature code.
The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:
Referring now to the drawing, and more particularly to
In order to be able to code the dynamics of the signature, one should understand the process of writing as it happens inside the human system.
Having understood the process of signature generation, the coding of the signature is presented.
Block 54 in
I have presented the grounds for these approximations in, Homayoon S. M. beigi, “Pre-Processing the Dynamics of On-Line Handwriting Data, Feature Extraction and Recognition,” Progress in Handwriting Recognition, A. C. Downtown and S. Impedovo (eds.), World Scientific Publishers, New Jersey, 1997, pp. 191-198. Considering these arguments, let us assume that the differential equations for the handwriting generation process may be tkapproximated by a two dimensional second order differential equation with linear time-invariant coefficients along a piece of writing between any two consecutive extreme positions in each coordinate (x and y), given by
Therefore, the velocity in each coordinate will also have the same form. For the sake of modeling the handwriting it is better to consider the velocity rather than the position for the apparent reasons of robustness to noise and pre-emphasis. Thus, the velocities in x and y directions under these very crude assumptions would be of the form given in the following equation,
Therefore, the first level of compression is achieved by estimating these six parameters which may be used to reconstruct the segment through an integration process starting from the beginning of the stroke at recorded initial values of x and y. The estimation is formulated as a quadratic optimization problem in Beigi 1997 and solved by minimizing the an error function.
Parameter Reduction 56 in
Parameter Quantization and Tabulation is part of the compression of the stroke parameters as stated by 58 in
Another part of 58 may be a coding scheme such as Huffman Coding. We have many features which portray substantial repetition—a great candidate for Huffman Coding, see David A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, September 1952, pp. 1098-1101. A 254-element table was generated from all 450 signatures. In practice, this means that a Huffman Table should be computed from a large corpus of signatures and kept for coding and decoding purposes. Finally, after doing the Huffman coding, the average signature came out to about 52 bytes with the maximum at 84 bytes. Huffman coding is loss-less, so the reconstruction results do not differ from those in the previous section.
I devised a loss-less compression technique as well as a very aggressive lossy technique. The loss-less method results in signature sized in the order of 1000 bytes. The lossy method codes keeps most signatures in less than 57 bytes which is the limit on a magnetic strip on the back of conventional credit cards. As opposed to the image compression, the signature compression may still be used if it overflows the 57-byte limit. We may chose to save as much of the signature as we can possibly fit on the magnetic strip. This would be enough for doing a verification since apparently most signatures are not that long. Future work on signature compression will include the pressure information which is readily available by many tablets today. This code, up to the limit imposed by the magnetic strip may now be written by 14 on 10. Note that for each stroke, the starting point of the stroke as well as the length of the stroke in time should also be stroke to be able to reconstruct the signature fully.
The loss-less compression technique for applications which require exact reconstruction of the handwriting signal from the coded signal. Consider the writing as a sequence of strokes, themselves defined as sequences of x(t) and y(t) coordinates beginning with a pen-down and ending with a pen-up signal. Almost all commercial tablet provide the x(t) and y(t) coordinates at a fixed sampling rate in the order of 100 Hz. In lieu of recording the x(t) and y(t) coordinates directly, one may compute a difference approximation to the local speeds vx(t) and vy(t). Since the speed of writing has an upper limit, the number of bits needed to represent vx(t) and vy(t) are quite small. Also, by keeping the coordinates of the initial position of each stroke, the stroke may be re-integrated with almost no loss. In fact to avoid any loss, only the Δx and Δy for each time step are recorded and the computation of the real velocity is not even attempted. A Huffman coding scenario is discussed which may be used to code these differences in a table with variable number of bits representing the data. Less frequent differences are coded with longer number of bits and more frequent ones are coded with less bits. This compression proves to be very practical and provides considerable compression of the on-line data without loss of the sequence and velocity information. This method creates signature codes of about 1000 bytes which is not even close to the space available to us (57 bytes) on the back of a transaction card.