Automated signature extraction and verification

A system for extraction and verification of handwritten signatures from arbitrary documents. The system comprises one or more computing devices configured to: receive a digital image of a document; remove a subset of words from the digital image identified via OCR; determine a plurality of regions of connected markings that remain in the digital image; based at least in part on a pixel density or proximity to an anchor substring of each region, determine that a region contains a handwritten signature; extract first image data of the region containing a handwritten signature from the digital image; retrieve second image data of a confirmed example signature for a purported signer of the handwritten signature; and based on a comparison of the first image data with the second image data, forward a determination of whether the first image data and second image data are similar.

FIELD OF INVENTION

This application relates to software systems for user authentication, and more specifically, an automated system for extracting a signature from a signed document and verifying that the signature was actually made by a person identified by the document.

BACKGROUND

Many businesses and government agencies use a variety of paper forms that require a signature by a person filling out the form in order to be valid. In some circumstances, documents sent to the business or agency by a customer or other stakeholder may even be in a format defined by the customer or stakeholder, rather than one under the business or agency's control. For example, a seller of property may generate a deed of sale on their own computing device, print it out, sign it, and expect the deed to be recorded by a county register, or a contractor may generate invoices to be signed and submitted to a business for payment.

When a signature must be verified to ensure that the stakeholder who purportedly signed a document actually signed the document, a human service representative may be tasked with pulling up a signature card recording a master copy of the stakeholder's signature, or with retrieving multiple examples of documents known to have been signed by the stakeholder in the past. The human representative will then visually compare the signatures, a process prone to error if done hastily, and costing valuable time otherwise.

Due to the sheer number of forms a business or agency may presently use or have used variation of in the past, and the unpredictability of forms that may be received in the future, it may be impossible to know a priori where the signature will be on an arbitrary document, and therefore impossible for a naïve algorithm to extract a region containing a signature to pass on to verification software without analyzing the document itself. Even with a human reviewer, it can take unnecessary extra seconds for each document to glance through multiple pages and identify every instance of a signature.

Even if a region of a document that exclusively contains the signature can be extracted, current verification algorithms are insufficiently flexible and are error-prone, as signatures have variance every time and no two instances of a person's signature will have identical lengths and angles of every pen stroke, and there will be significant differences when two images are compared on a pixel-by-pixel basis.

As a result of all of the above issues, businesses or agencies dealing with a variety of forms signed by numerous stakeholders are unable to easily shift signature verification tasks currently assigned to human employees to automated systems.

SUMMARY OF THE INVENTION

A computer-implemented method for handwritten signature extraction is disclosed. The method comprises receiving a digital image of a document comprising a handwritten signature; removing a subset of words from the digital image identified via optical character recognition; determining a plurality of regions of connected markings that remain in the digital image; based at least in part on a pixel density or a proximity to an anchor substring of each of the plurality of regions, determining that one or more regions of the plurality of regions each contain a handwritten signature; and extracting image data of the one or more regions, each containing a handwritten signature, from the digital image.

Another computer-implemented method for handwritten signature verification is also disclosed, comprising receiving first image data comprising a purported signature of an individual; retrieving second image data comprising a known signature of an individual; creating a feature vector that incorporates a plurality of similarity metrics between the first and second image data; and passing the feature vector to a linear regression model to estimate a likelihood that that the first image data and second image data represent similarity between the image pair.

A system for performing both of the methods above sequentially is also disclosed, comprising one or more processors executing instructions that cause the one or more processors to extract a signature from an arbitrary document according to the first method and verify the signature according to the second method.

DETAILED DESCRIPTION

In order to address the issues described above, a fully or partially automated system may obtain a digital image of a document containing a signature, perform a series of transformations and analyses of the image data, isolate a region of the document that contains only the signature, pass the extracted region of the image containing the signature to a verification module, and determine its similarity to the other signature.

FIG. 1depicts a system of computing devices for capturing, transmitting, extracting, and verifying a handwritten signature on a document against another signature extracted from a similar document referred in the system as a signature card.

A physical document100comprising a handwritten signature in ink (or another pigment or marking device) on paper (or another substrate) may be placed before scanner or other device105to be scanned, photographed, or otherwise digitized. In some alternate embodiments, document100may be a digital document, such as a PDF (portable document format) or bitmap that has been “signed” via a user physically manipulating a mouse, stylus, touchscreen, or other input device to translate movements of the user's hand into an additional graphical element added to the digital document, approximating what the user's handwritten physical signature would be.

The scan of physical document100(or the file of digital document100) is at least temporarily stored on user computing device110before transmission to user interface server115. User computing device110may comprise scanner105(for example, a camera in a mobile phone), be communicatively coupled to the scanner105(for example, connected to a dedicated scanner/photocopier via a wireless connection or USB [universal serial bus] cable), or simply receive a file that has been previously scanned by scanner105at a previous time or remote location.

User interface server115may, in some embodiments, have prompted a user of user computing device110to send the scanned document (such as, for example, a web page interface prompting a user to upload a document for processing). In other embodiments, user interface server115may receive the file passively, such as via an email communication from the user or by operating FTP (file transfer protocol) server software to receive arbitrary files at any time. A user interface generated by user interface server115may be used not only by the user to upload the scanned document but also by a customer service representative, using customer service computing device120, to act upon instructions or information in the document once it is verified as genuinely signed.

User interface server115may forward the scanned document to an extraction server125, containing software to identify a region of the scanned document containing the handwritten signature, according to a method described below in the paragraphs accompanyingFIG. 2. The identified image part130may be sent, in some embodiments, to a verification server135for automatic verification of the signature, while in other embodiments, the identified image part may be sent, directly or via user interface server115, to customer service computing device120for a human user to perform the verification by sight and personal judgment call.

In some embodiments, the extracted image part130may be accompanied by the full document or by some subset of information gleaned from the document, such as an identification of the purported signer, so that the verification server135or customer service representative using device120may know whose signature is to be compared to the extracted signature in the image125.

When verification server performs the verification, a method described further below (in paragraphs accompanyingFIG. 4) is used to automatically compare the extracted signature130to one or more signatures retrieved from a database140. If a customer service representative is performing the verification, one or more example signatures may be forwarded to an interface on customer service computing device120, or the customer service representative may consult a physical signature card.

Although a system is described here in which five computing devices110,115,120,125,135, and140are treated as separate computing devices, other configurations are possible in which additional devices are added (dividing between them the functionality ascribed to a single device) or devices are removed (and in which a single general purpose computer performs multiple functionalities described throughout the paragraphs above and below).

For example, a single computer operated by a customer service representative may have all the functionality to receive, extract, and verify a signature, so that it acts as devices115,120,125,135, and140with no transmission of information between devices, only passing of information between different software modules in the same device.

FIG. 2depicts a method of extracting a signature from a document according to methods disclosed herein.

Initially, the system receives the image data of a document100that has been captured by the scanner/camera105(Step200). Although the following steps assume that raw optical data is received without the scanner/camera having done any processing to clean up the image file, it is not necessary that the raw image be provided rather than an image that has undergone some cleanup performed automatically by devices105or110.

Next, the image is converted to grayscale and then undergoes Otsu thresholding and image inversion (Step205), resulting in an image where every pixel is either pure white or pure black, based on its comparative lightness or darkness to the rest of the image prior to processing. In other embodiments, a thresholding algorithm other than Otsu's method that results in image binarization may be used. The image is inverted in order to treat foreground (printed) characters as ones in any array rather than zeroes for mathematical purposes, but the methods described below could theoretically be modified to work whether the image is inverted or not.

Optionally, the image is automatically cropped at the edges to produce the smallest image that still contains all foreground pixels or the substantial totality of them (Step210).

The image may also undergo deskewing (Step212) to rotate the entire image or portions thereof, compensating for a document that was entered into a scanner askew, printed at an angle to the underlying paper or substrate, or otherwise caused to have its contents non-horizontal within the captured image.

Next, the image is de-speckled using fast non-local image denoising (Step215) to remove any foreground pixels that were spuriously picked up during the optical capture by the scanner and that survived the thresholding process, but were not actually printed or written matter on the page.

Next, horizontal and vertical lines may be removed via a convolution matrix kernel (Step220) selected such that foreground pixels with a number of foreground pixels directly above, below, or to the left or right are replaced with background pixels, but pixels that are not a part of a horizontal or vertical line are retained.

As a final preprocessing step to maximize the suitability of the image for optical character recognition (OCR), the image contrast may be increased (Step222) if the image is not already binarized to maximize the contrast.

Next, the image undergoes OCR (Step225) to identify as many regions of printed text as possible, storing coordinates of a minimal bounding box around the text and confidence level of word identification for each region.

The set of identified words and characters is searched for any that are “anchor words” or substrings of anchor words (Step230). Anchor words indicate the likely presence of a nearby signature and may include, for example, “signature”, “signed”, “affixed”, etc., and their equivalents in other languages. Identification of substrings is preferred in case a signature passes through a nearby anchor word and interferes with the ability of the OCR process to capture the full word.

For all words or substrings that are confidently identified and are not anchor words or substrings of anchor words, the regions containing those identified are replaced fully with background pixels (Step235). At the same time, any printed handwritten characters that are sufficiently neat and identifiable as to be picked up by OCR are also whited out and replaced with background pixels, as they are unlikely to be part of a signature if printed.

Next, the image is again processed using a convolution matrix to “dilate” the image (Step240), smudging each pixel slightly in the vertical and horizontal directions (a cross-shape of positive values in the kernel for processing).

After dilation, regions of connected pixels are identified and grouped (Step245) by recursively starting at any given foreground pixel and adding any of its eight neighbors that is also a foreground pixel to the group, and then their neighbors, and so on.

In some embodiments, regions of connected pixels may be filtered out from consideration based on a high pixel density (Step247) in the area of the connected pixels, as extremely unlikely to contain a signature (see further discussion below, regarding Step255).

For each connected group, a minimal bounding box is drawn around the group and stored in memory (Step250). Multiple bounding boxes may be consolidated into a single bounding box if, for example, they overlap, or share Y-coordinates (and are likely to be on a same line of text) while being closer in the X-direction than a predetermined threshold.

Within each of these bounding boxes, one or more methods of determining whether the contents are a signature may be applied (Step255), as described below.

First, the overall density of foreground pixels within the bounding box may be measured and compared to other bounding boxes. Printed text tends to delineate more neatly into horizontal lines of completely white space above and below lines of dense printing, where neither capital letters nor descenders tend to encroach much into that white space, signatures tend to be made of thin pen strokes that have much greater vertical range, causing a bounding box that contains the entire signature to contain much more white space than a bounding box containing a typeface.

Second, the relative or absolute dimensions of the bounding box may be taken into account. A typewritten or even a printed handwritten word will in many cases fit into a bounding box that is much longer than it is tall, and if it is short enough to have a small aspect ratio, is unlikely to be a signature, which tends to have a minimum length. A bounding box for a signature is also likely to be taller than those of printed text in a smaller font, and longer than the average typewritten word in the document.

Third, the proximity of each bounding box to the previously identified anchor words or substring is factored into the determination. A signature is much more likely to be immediately next to, above, or below an anchor that is prompting the signer where to sign the document, or at least on a same level (if, for example, a person signs in the middle or at the right edge of a long signature line having the “Signature” anchor at the far left).

Fourth, a machine learning algorithm may be trained to take in binarized images as vectors and return a likelihood that they represent a signature. In a preferred embodiment, the machine learning technique may be a convolutional neural net into which is fed a series of subsections of the image as bit vectors. In a preferred embodiment a multi-class classifier can be trained to differentiate between different classes, such as typewritten words, numbers, handwritten printed text, and/or handwritten signatures, to determine a relative confidence in classification as a signature compared to classification as another kind of information.

Based on these factors, an overall confidence level or likelihood that a bounding box contains a signature may be determined, and in a signed document, a particular box (or multiple boxes, if a document has multiple signatories) should have a much higher confidence than the remaining regions that survived the OCR and other image processing steps. The identified regions of the image within the identified bounding boxes are extracted (Step260) for subsequent use in verification.

In some instances, a document may be determined to lack any signature at all after processing has been performed and failed to identify any portion of the document that has a sufficiently high likelihood of being a handwritten signature. In such a case, extraction server125may generate a message to user interface server115, indicating this fact, which may also be forwarded in substantial part to either user computing device110(indicating to the user that there is an error and the document has not yet been signed) or to customer service computing device120(indicating that the customer service representative needs to contact a user, inform the user of the situation, and obtain a signed version).

FIGS. 3A-3Fdepict a sample document at different stages of a signature recognition process.

FIG. 3Adepicts an original scanned document with a number of features, including signature300, various typed words305, handwritten printed characters310, and dust or other speckling315picked up by a scanner. For example, the document might read: “Whereas Mr. Smith wishes to sell a piece of land to Mr. Jones on this 9thday of June, 2019, he acknowledges that sufficient financial consideration has been provided and grants the land to Mr. Jones and his successors” and be signed on a line beneath the printed text.

FIG. 3Bdepicts the same document asFIG. 3A, after the image has been grayscaled, thresholded, binarized, despeckled, and had lines removed via convolution matrix. Speckling315is no longer present, nor is the line on which the signature300was made, and any text that was not fully black (or picked up as lighter by the scanner) has been made black via the binarization/thresholding.

FIG. 3Cdepicts the bounding boxes320around words noted by OCR, including one around anchor word325and one around a handwritten character310.

FIG. 3Ddepicts the document after non-anchor boxes noted by OCR have been removed.

FIG. 3Edepicts the connected regions of text330that result after the image inFIG. 3Dhas been dilated and the connected pixel group identification process is complete.

FIG. 3Fdepicts the two connected regions identified inFIG. 3Econnected into a single region335due to their proximity with one another. Based on one or more of proximity to the known location of anchor word325, the length and relatively low aspect ratio of the bounding box, the low density of pixels within the bounding box, and/or input from a machine learning analysis of the contents, the bounding box335around signature300is clearly the best candidate for the signature, and is extracted.

FIG. 4depicts a method of verifying that an extracted signature purported to be by a particular signer was actually made by that signer.

In a preferred embodiment, the verification algorithm receives a binarized signature that is contained in a minimal bounding box, as returned by the method for extraction described above. In some embodiments, a signature may be provided which was the result of a different extraction process, and must undergo preprocessing (Step400), or may undergo additional preprocessing not performed by the extraction algorithm. Preprocessing may include, as necessary, conversion of received image data to grayscale, despeckling the image data, removing horizontal and vertical lines from the data via convolution matrix, cropping the image to remove whitespace, rotating the image if the signature is aligned at an angle rather than horizontal, via a deskewing algorithm, and binarization.

One or more known examples copies of the signature (such as one made on a bank card, or an initial sign-up form) may be retrieved from a database (Step405) or otherwise loaded or inserted into the system for analysis.

Next, both the purported signature and the known signature may undergo global feature extraction (Step410). In a preferred embodiment, each image is divided into a series of smaller tiles (for example, 3 pixel by 3 pixel tiles) and these sets of tiles undergo wave extraction via the SIFT and SURF algorithm. A Pearson correlation coefficient is determined from the extracted wave features to allow determination of a p-value that the two signatures are similar.

Next, both the purported signature and the known signature may also undergo local feature extraction (Step415).

Local feature analyses may include any of histogram of oriented gradients, a structural similarity analysis, a cosine similarity metric, and/or an energy-entropy comparison between the two images.

A histogram of oriented gradients (HoG) analysis involves generating two HoG vectors for each image, determining the dot product of the two vectors, determining the Frobenius norm of the two vectors, and determining a ratio between the dot product and Frobenius norm.

A cosine similarity metric may involve dividing the image into a fixed number of tiles, calculating the X- and Y-axis centroids of each tile of the two tilesets, and generating two vectors, each with the X- and Y-coordinates of each of the centroids of each image. A similarity can be determined based on the ratio of the dot product to the Frobenius norm of these two centroid vectors.

An energy-entropy metric may compare the total entropy of equivalent tiles from each image (equal to −p log p, where p is the pixel density within the tile) and the total energy of equivalent tiles (equal to the sum of squares of all pixel intensities, divided by the area of the tile).

The values returned by various aspects of the global and local feature extraction may be combined into a single feature vector (Step420) in order to allow processing of that vector by one or more machine learning techniques to return a final likelihood of similarity of the signatures.

In a preferred embodiment, the determination is made based on a trained linear regression (Step425) of the feature vector.

The software-implemented methods described above do not generally rely on the use of any particular specialized computing devices, as opposed to standard desktop computers and/or web servers. For the purpose of illustrating possible such computing devices,FIG. 5is a high-level block diagram of a representative computing device that may be utilized to implement various features and processes described herein, including, for example, those of computing devices110,115,120,125,135, and/or140. The computing device may be described in the general context of computer system-executable instructions, such as program modules, being executed by a computer system. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types.

As shown inFIG. 5, the computing device is illustrated in the form of a special purpose computer system. The components of the computing device may include (but are not limited to) one or more processors or processing units900, a system memory910, and a bus915that couples various system components including memory910to processor900.

Processing unit(s)900may execute computer programs stored in memory910. Any suitable programming language can be used to implement the routines of particular embodiments including C, C++, Java, assembly language, etc. Different programming techniques can be employed such as procedural or object oriented. The routines can execute on a single computing device or multiple computing devices. Further, multiple processors900may be used.

The computing device typically includes a variety of computer system readable media. Such media may be any available media that is accessible by the computing device, and it includes both volatile and non-volatile media, removable and non-removable media.

Program/utility950, having a set (at least one) of program modules955, may be stored in memory910by way of example, and not limitation, as well as an operating system, one or more application software, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment.

The computing device may also communicate with one or more external devices970such as a keyboard, a pointing device, a display, etc.; one or more devices that enable a user to interact with the computing device; and/or any devices (e.g., network card, modem, etc.) that enable the computing device to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interface(s)960.

In addition, as described above, the computing device can communicate with one or more networks, such as a local area network (LAN), a general wide area network (WAN) and/or a public network (e.g., the Internet) via network adaptor980. As depicted, network adaptor980communicates with other components of the computing device via bus915. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with the computing device. Examples include (but are not limited to) microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.