INVERTIBLE TEXT EMBEDDING FOR LEXICON-FREE OFFLINE HANDWRITING RECOGNITION

Abstract

A handwriting recognition method which uses an invertible label embedding (encoding) algorithm to embed character strings into an Euclidean vector space as attribute vectors, uses a CNN to learn and predict attribute vectors of handwriting images in this Euclidean vector space, and then directly decodes a predicted attribute vector into a character string using a decoding algorithm that is the inverse of the invertible encoding algorithm. No lexicon is required to decode the predicted attribute vector. Thus, this method can recognize images containing handwritten digital sequences commonly encountered in many practical applications, such as quantities, dollar, date, phone number, social security numbers, zip code, etc. which are outside of common lexicons.

Claims

1. A method implemented in one or mote computer systems for recognizing images of handwritten text, comprising: training an artificial neural network to perform a task of embedding images of handwritten character strings as attribute vectors into an Euclidean vector space, comprising: providing an untrained artificial neural network; providing training data, the training data comprising a plurality of training images each containing an image of a handwritten character string, and a plurality of training labels, each training label being associated with a training image and identifying a character string represented by the associated training image; and performing a plurality of training iterations on the artificial neural network, wherein each training iteration includes inputting a training image into the artificial neural network to calculate a first attribute vector in the Euclidean vector space, encoding the character string identified by the associated training label into a second attribute vector in the Euclidean vector space using an encoding algorithm, and updating weights of the artificial neural network to minimize a loss function which measures a distance between the first attribute vector and the second attribute vector in the Euclidean vector space, wherein the encoding algorithm uniquely encodes arbitrary character strings into attribute vectors of the Euclidean vector space where no two different character strings are encoded to a same attribute vector in the Euclidean vector space, whereby a trained artificial neural network is obtained after the plurality of training iterations; inputting a target image containing an image of a handwritten character string to the trained artificial neural network to calculate a third attribute vector in the Euclidean vector space; and decoding the third attribute vector using a decoding algorithm to obtain a decoded character string, without performing a nearest neighbor search in the Euclidean vector space.

2. The method of claim 1, wherein the encoding algorithm for encoding an input character string into an encoded attribute vector in the Euclidean vector space includes: recursively bisecting the input character string for a predetermined number of levels to form a binary tree, a root of the binary tree being the input character string, wherein a character string at each non-leaf node of the binary tree is bisected into a left child character string at its left child node and a right child character string at its right child node, the left child character string and the right child character string having equal lengths, a middle character of the character string being omitted in the bisecting, wherein the middle character is a non-empty character when the character string being bisected has an odd number of characters and is an empty character when the character string being bisected has an odd number of characters; for each node of the binary tree, computing a histogram of characters of the corresponding character string, the histogram of characters being a histogram having n values, where n is a size of a defined alphabet, each value being a number of times a corresponding character occurs in the character string; and concatenating all histogram of characters of all nodes of the binary tree according to a predefined order to form the encoded attribute vector, the predefined order being a predefined tree traversal order of traversing the binary tree.

3. The method of claim 2, wherein the decoding algorithm for decoding an attribute vector in the Euclidean vector space into a decoded character string includes: dividing the attribute vector according to the predefined order in which the histograms are concatenated in the encoding algorithm, to obtain individual histograms of characters which form a decoding binary tree, the decoding binary tree having an identical structure as the binary tree formed by the encoding algorithm, each histogram of characters being a node of the decoding binary tree; for each leaf node of the decoding binary tree, decoding the histogram of characters of the leaf node to obtain a corresponding decoded character for the leaf node, wherein the decoded character is a character corresponding to a maximum value of the histogram of characters when the maximum value is greater than a predetermined threshold of confidence value, and is an empty character when the maximum value of the histogram of characters is less than or equal to the predetermined threshold of confidence value; for each non-leaf node of the decoding binary tree, subtracting the histogram of characters of its left child node and the histogram of characters of its right child node from the histogram of characters of the non-leaf node to obtain a difference histogram, and decoding the difference histogram to obtain a corresponding decoded character for the non-leaf node, wherein the decoded character is a character corresponding to a maximum value of the difference histogram when the maximum value is greater than the predetermined threshold of confidence value, and is an empty character when the maximum value of the difference histogram less than or equal to the predetermined threshold of confidence value; and concatenating the decoded characters of all nodes of the decoding binary tree in an order that is a reverse order of the recursive bisecting in the encoding algorithm to form the decoded character string.

4. A method implemented in a computer system for training an artificial neural network to perform a task of embedding images of handwritten character strings as attribute vectors into an Euclidean vector space, comprising: providing an untrained artificial neural network; providing training data, the training data comprising a plurality of training images each containing an image of a handwritten character string, and a plurality of training labels, each training label being associated with a training image and identifying a character string represented by the associated training image; and performing a plurality of training iterations on the artificial neural network, wherein each training iteration includes inputting a training image into the artificial neural network to calculate a first attribute vector in the Euclidean vector space, encoding the character string identified by the associated training label into a second attribute vector in the Euclidean vector space using an encoding algorithm, and updating weights of the artificial neural network to minimize a loss function which measures a distance between the first attribute vector and the second attribute vector in the Euclidean vector space, wherein the encoding algorithm uniquely encodes arbitrary character strings into attribute vectors of the Euclidean vector space where no two different character strings are encoded to a same attribute vector in the Euclidean vector space, whereby a trained artificial neural network is obtained after the plurality of training iterations.

5. The method of claim 4, wherein the encoding algorithm for encoding an input character string into an encoded attribute vector in the Euclidean vector space includes: recursively bisecting the input character string for a predetermined number of levels to form a binary tree, a root of the binary tree being the input character string, wherein a character string at each non-leaf node of the binary tree is bisected into a left child character string at its left child node and a right child character string at its right child node, the left child character string and the right child character string having equal lengths, a middle character of the character string being omitted in the bisecting, wherein the middle character is a non-empty character when the character string being bisected has an odd number of characters and is an empty character when the character string being bisected has an odd number of characters; for each node of the binary tree, computing a histogram of characters of the corresponding character string, the histogram of characters being a histogram having n values, where n is a size of a defined alphabet, each value being a number of times a corresponding character occurs in the character string; and concatenating all histogram of characters of all nodes of the binary tree according to a predefined order to form the encoded attribute vector, the predefined order being a predefined tree traversal order of traversing the binary tree.

6. A method implemented in one or mote computer systems for recognizing images of handwritten text, comprising: providing a trained artificial neural network; inputting a target image containing an image of a handwritten character string to the trained artificial neural network to calculate an attribute vector in an Euclidean vector space; and decoding the attribute vector using a decoding algorithm to obtain a decoded character string, without performing a nearest neighbor search in the Euclidean vector space.

7. The method of claim 6, wherein the decoding algorithm includes: dividing the attribute vector according to a predefined order which is based on a binary tree traversal order, to obtain individual histograms of characters which form a decoding binary tree, each histogram of characters being a node of the decoding binary tree; for each leaf node of the decoding binary tree, decoding the histogram of characters of the leaf node to obtain a corresponding decoded character for the leaf node, wherein the decoded character is a character corresponding to a maximum value of the histogram of characters when the maximum value is greater than a predetermined threshold of confidence value, and is an empty character when the maximum value of the histogram of characters is less than or equal to the predetermined threshold of confidence value; for each non-leaf node of the decoding binary tree, subtracting the histogram of characters of its left child node and the histogram of characters of its right child node from the histogram of characters of the non-leaf node to obtain a difference histogram, and decoding the difference histogram to obtain a corresponding decoded character for the non-leaf node, wherein the decoded character is a character corresponding to a maximum value of the difference histogram when the maximum value is greater than the predetermined threshold of confidence value, and is an empty character when the maximum value of the difference histogram less than or equal to the predetermined threshold of confidence value; and concatenating the decoded characters of all nodes of the decoding binary tree in a predefined order to form the decoded character string.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0024] FIG. 1 schematically illustrates a known handwriting text recognition method that embeds word images and words in a lexicon into a common Euclidean attribute vector space and uses a nearest neighbor search to find the corresponding word for a word image.

[0025] FIGS. 2 and 3 schematically illustrate a handwriting text recognition method according to an embodiment of the present invention, which uses an invertible coding method to embed character strings (text labels) into an Euclidean attribute vector space and to directly decode predicted attribute vectors into character strings.

[0026] FIG. 4 schematically illustrates the neural network training process according to the embodiment.

[0027] FIG. 5 schematically illustrates the word recognition process according to the embodiment.

[0028] FIGS. 6A-6D are examples that illustrate an invertible text embedding (encoding) and decoding method according to an embodiment of the present invention.

[0029] FIG. 7 illustrates an encoding method for encoding a character string into an attribute vector according to an embodiment of the present invention.

[0030] FIG. 8 illustrates a decoding method for decoding an attribute vector into a character string according to an embodiment of the present invention.

[0031] FIG. 9 illustrates an exemplary algorithm for decoding an attribute vector according to an embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0032] Embodiments of the present invention provide a handwriting recognition method which uses an invertible label embedding (encoding) algorithm to embed character strings into an Euclidean vector space as attribute vectors, uses a CNN to learn and predict attribute vectors of handwriting images in this Euclidean vector space, and then directly decodes a predicted attribute vector into a character string using a decoding algorithm that is the inverse of the invertible encoding algorithm, without requiring a lexicon. As used in the relevant art, a lexicon is a collection of all possible words that can be recognized by a recognition method.

[0033] The overall process of the handwriting recognition method according to an embodiment of the present invention is described below with reference to FIGS. 2 and 3, including neural network training (FIG. 2) and prediction and decoding (FIG. 3).

[0034] As shown in FIG. 2, an artificial neural network, such as a convolutional neural network (CNN), is trained to perform image embedding to embed images of handwritten words into an Euclidean vector space V. To train a neural network, a large amount of training data is inputted into an untrained network, and an iterative training process is conducted to obtain the weights of the network. Here, the training data are formed of training images of handwritten words along with the associated labels, which are the words the images represent. The words are not limited to any lexicon and can be any finite-length string of characters drawn from a fixed alphabet. During training, in each iteration, a training image is inputted into the neural network to calculate a first attribute vector v1 in the Euclidean vector space V (image embedding), and the training label (the word) is embedded into the same Euclidean vector space V using the invertible encoding algorithm (described in detail later) as a second attribute vector v0 (label embedding (encoding)). The weights of the neural network are updated to minimize a loss function which measures the distance between the attribute vectors v1 and v0 in the Euclidean vector space. Thus, during training, the label embedding step is used to construct the ground truth of training samples: the ground truth word label is encoded into its corresponding attribute vector as ground truth. The trained neural network is able to predict an attribute vector from an input word image. This neural network training process is summarized in FIG. 4.

[0035] In one particular embodiment, an L_2 loss function and stochastic gradient descent are used to train a VGG-based CNN. The VGG model is described in K. Simonyan et al., Very Deep Convolutional Networks For Large-Scale Image Recognition, ICLR 2015. In this embodiment, the CNN also includes a horizontal Spatial Pyramid Pooling before the fully-connected layers to enable arbitrary input image size in the horizontal direction. This is helpful because a CNN would otherwise require input images to have the same size, while the length of the word image may vary greatly as compared to its height.

[0036] To recognize a target handwriting image (FIG. 3), the target image is inputted into the trained neural network to predict an attribute vector v2 in the Euclidean vector space V (image embedding). A decoding process is then applied to the predicted attribute vector v2, using a decoding algorithm which is the inverse of the encoding (label embedding) algorithm used in the training process. The result of the decoding process is the recognition result, i.e. the character string that is recognized. This image recognition process is summarized in FIG. 5.

[0037] The invertible encoding (label embedding) and decoding algorithms used in the above embodiment, referred to as invertible Pyramidal Histogram of Characters (iPHOC), are described below with reference to FIGS. 7 and 8 and using the examples shown in FIGS. 6A-6D.

[0038] It is assumed that all characters of the string being encoded belong to a known and fixed alphabet . The encoding of a character string into an iPHOC attribute vector uses a recursive bisection and histogram computation process. A predetermined parameter k represents the maximum number of levels of bisection, which also defines the maximum length of the character string that can be encoded. More specifically, given an arbitrary character string, its iPHOC attribute vector is constructed by computing the histogram of characters of the string itself (step S71), then recursively bisecting the string into two equal length child strings (step S72) and computing the histogram of characters of each child string (step S73), until the child strings become empty (and thereafter, the child strings of the remining ones of the k levels are all empty strings). In each bisecting step, if the string being bisected has an odd number of characters, its middle character is omitted in the next level child strings. Thus, the child strings at each level always have the same number of characters. If the string being bisected has an even number of characters, it is deemed to have an omitted middle character that is an empty character.

[0039] For example, in FIG. 6A, success (level 0) is bisected into two child strings suc and ess (omitting the middle character c) (level 1), which are further bisected into smaller child strings s and c, and e and s (again omitting the respective middle characters) (level 2). The next level bisections (level 3) are all empty, as indicated by the quotation marks. FIG. 6B shows the bisection of a string that is not a common word.

[0040] This bisecting process can be represented as a binary tree, where the root of the tree is the original string and the other nodes are the child strings. This binary tree can also be seen as a coarse-to-fine pyramid where each level focuses on smaller and smaller child strings.

[0041] For each node of the binary tree, a histogram of characters is calculated from the character string of that node (step S73), which is a histogram with n values (n being the size of the alphabet ), each value being the number of times the corresponding character occurs in the string. FIG. 6C shows the histograms of levels 0 to 2 for the example of FIG. 6A (in this example, all child strings at level 3 are empty, so all level 3 histograms have zero values and are not shown in FIG. 6C).

[0042] Note that the omission of the middle character when bisecting odd-length strings does not cause any lost of information. During decoding, the omitted middle characters can always be recovered by finding the difference between a histogram of a node and the sum of the two histograms of its left and right child node (and if there is no difference, then the omitted middle character is empty). For example, the central c in success can be found by subtracting the sum of two level 1 histograms (for suc and ess) from the level 0 histogram (for success) (see FIG. 6C).

[0043] After the bisection is completed, all histograms for all nodes of the tree (including the zero histograms) are concatenated in an order defined by a predetermined tree traversal of the binary tree, to form a vector as the attribute vector (step S74). A tree traversal is an order of visiting each node of a tree exactly once (described in more detail later).

[0044] For an iPHOC encoding of k levels, there will be (2.sup.k1) histograms; and with an alphabet of size n, the attribute vector's dimension will be (2.sup.k1)*n. Since the middle characters are omitted when bisecting odd-length strings, the maximum length of strings that the iPHOC coding with k levels can represent is 2.sup.k1. For most application of transcribing word images, k=4 (levels 0 to 3) is sufficient, which gives a maximum transcription length of 15 characters. Note here that the k levels include level 0 (root level) which corresponds to the original string.

[0045] To decode a CNN-predicted iPHOC attribute vector of dimension (2.sup.k1)*n, the vector is divided to obtain (2.sup.k1) individual histograms each of size n, using the same order in which the histograms are concatenated in the encoding algorithm, i.e., the same predetermined tree traversal order (step S81). These individual histograms can be placed on a binary tree (referred to as the decoding binary tree for convenience) having the same structure as the binary tree used in the encoding algorithm (referred to as the encoding binary tree for convenience).

[0046] For each leaf node of the decoding binary tree, the histogram is decoded to obtain a decoded character in the follow way (step S82): If the maximum histogram value is greater than a predetermined threshold of confidence (0<<1), the decoded character is the character having the maximum histogram value; if the maximum histogram value is less than or equal to the threshold of confidence , the decoded character is an empty or null character. Here, the real values of the histogram are used directly to perform decoding. The decoded character for each leaf node, which contains either a single character or no character, corresponds to the character represented by the leaf node of the encoding binary tree.

[0047] For each non-leaf node of the decoding binary tree, the histograms of its left and right child nodes are subtracted from the histogram of the current node to obtain a difference histogram (step S83). The difference histogram is decoded to obtain a decoded character in the same way as for a leaf node histogram (step S83), i.e.: If the maximum histogram value is greater than the threshold of confidence , the decoded character is the character having the maximum histogram value; if the maximum histogram value is less than or equal to the threshold of confidence , the decoded character is an empty or null character. The decoded character for each non-leaf node, which contains either a single character or no character, corresponds to the omitted middle character when bisecting that node in the encoding algorithm. As noted earlier, the omitted middle character is either a non-empty character (when the string being bisected has an odd number of characters) or an empty character (when the string being bisected has an even number of characters).

[0048] Note that the processing steps for the leaf nodes and the non-leaf nodes may be done in any order because the steps are not dependent on each other.

[0049] As a result, a decoded character (which may be an empty character) is generated for each node of the decoding binary tree. FIG. 6D illustrates the decoded characters organized in the decoding binary tree, corresponding to the example of FIG. 6A.

[0050] The decoded characters for all the nodes of the decoding binary tree are concatenated together, based on an order that is the reverse of the recursive bisection used in the encoding algorithm, to obtain a character string that is the final decoding result (step S84).

[0051] For example, starting from the leaf nodes and working progressively toward the root node, the character strings for a pair of left and right child nodes and their parent node are concatenated in the order of left child node, parent node, right child node to form the concatenated character string of the parent node. The concatenation progresses toward the root node, each time using already concatenated character strings for the left and right child nodes and the decoded character of the parent node. The concatenated character string for the root node is the final decoding result. For example, for the example of FIG. 6D, the concatenated character string for the left most node at level 2 is s , i.e. s; the concatenated character string for the left most node at level 1 is s u c, i.e. suc; etc.

[0052] The concatenation of the decoded characters may also be done by traversing the binary tree using an in-order tree traversal and concatenating the decoded characters of the nodes in that order. In-order tree traversal gives the original string in this case because of the way the string is recursively bisected in the encoding algorithm.

[0053] The actual implementation of the decoding algorithm may perform the step of dividing the attribute vector into individual histograms (step S81), the steps of decoding each histogram to obtain the corresponding decoded character (steps S82 and S83), and the steps of concatenating the decoded characters (step S84) in any suitable order. For example, a recursive algorithm may be used which may go in either a root to leaf direction or a leaf to root direction, performing the dividing, decoding and concatenating steps concurrently. As a particular example, in the program code for a decoding algorithm set forth in FIG. 9, decoding progresses from root to leaf, and one histogram (ht) is extracted from the attribute vector (v) at a time and decoded into a decoded character (char), and the steps are performed recursively while concatenating the decoded character with the next level decoding result.

[0054] As mentioned above, the encoding and decoding processes use the same binary tree traversal order when concatenating the multiple histograms of the tree into the attribute vector and when dividing the attribute vector into the multiple histograms of the tree. A tree traversal (also referred to as tree search) is an order of visiting each node of a tree exactly once. Many tree traversal methods are known, including, for example, depth-first search and breath-first search. Depth-first search includes pre-order, in-order, and post-order search. These tree traversal methods are well known in the computer art (see, for example, the Wikipedia article entitled Tree traversal), and are not described in detail here. In a preferred embodiment, a pre-order traversal is used to traverse the tree in the encoding and decoding processes. For example, in the example of FIG. 6B, using pre-order traversal, the order of the nodes will be: F3NP20X!--F3NP--F3--F--3--NP--N--P--20X!--20--2--0--X!--X--!. The decoding program code set forth in FIG. 9 uses a pre-order tree traversal. Other tree traversal orders may be used as well.

[0055] As can be seen, the invertible label encoding and decoding method is a one-to-one mapping between character strings and a set of grid points of the Euclidean vector space. Grid points are points (i.e. vectors) in the Euclidean vector space for which the values of the coordinates (i.e. values of the elements of the vector) are natural numbers. Each character string (arbitrary string, not required to belong to a lexicon) can be uniquely encoded by the encoding method to a grid point of the Euclidean vector space. Each valid grid point can be uniquely decoded by the decoding method to a character string, without requiring the string to belong to a lexicon. Note here that only a subset of grid points in the vector space are valid grid points that represent valid attribute vectors. For example, for an alphabet of size 2 (n=2) and 2 bisection levels (k=2), the dimension of the vector space is 6. Let v=[v1, v2, v3, v4, v5, v6] be a grid point in this space, v must satisfy v1+v2>=v3+v4+v5+v6 to be a valid grid point, since the number of characters in higher level child strings is less than those of lower levels. Any vector predicted by the CNN is effectively rounded to its nearest grid point and decoded to the corresponding character string, regardless of whether the character string belongs to a lexicon. In actual implementation, because real-valued vectors cannot be directly converted to text, and direct rounding can affect accuracy, a deterministic algorithm as that described above is used to decode these vectors to character strings, using a preset threshold , which can be interpreted as a confidence threshold to transcribe a particular character. This way, a fixed lexicon is not required for decoding. This method is simple and fast, as it does not require an optimization (nearest neighbor search) process for decoding.

[0056] To the contrary, the SPOC and PHOC coding methods in Rodriguez-Serrano et al. 2013 and Almazn et al. 2014 do not provide an invertible decoding method. In these coding methods, each words of the lexicon is mapped to a grid point, but not uniquely. For SPOC, strings containing the same characters are map to the same attribute vectors even though they have different length. For example, let the alphabet be {a, b, c} and k=2, level 1 of SPOC(aaa) are the same as level 1 of SPOC(aa), and level 2 of that of two string are the same also: [1, 0, 0, 1, 0, 0] (refer to the second to last paragraph in section 2.3 of their paper). So given a vector of [1, 0, 0, 1, 0, 0, 1, 0, 0], one would not be able to tell whether it represents aaa or aa. For PHOC, histogram only record occurrence. Unlike iPHOC and SPOC, PHOC divide texts into {1, 2, 3, . . . } regions instead of bisection only. If the number of levels are {1, 2, 3}, level 1 of PHOC(abc) and PHOC(abbc) are both [1, 1, 1], and level 2 of that of two strings are both [1, 1, 0, 0, 1, 1] and level 3 are both [1, 0, 0, 0, 1, 0, 0, 0, 1] (refer to the last paragraph in section 3.1 of their paper), again indistinguishable between abbc and abc. These characteristics of SPOC and PHOC are not likely to cause problems in actual application because the coding methods are only intended to be used for recognizing character strings that belong to a practical lexicon, where the lexicon is unlikely to contain strings or substrings like those examples discussed above. However, in applications where the character string to be recognized can be any arbitrary strings, these characteristics of SPOC and PHOC will present a problem.

[0057] Another difference between the encoding algorithm of the present embodiments and SPOC and PHOC is that SPOC and PHOC do not drop any characters during their division process and each designed their particular letter assignment scheme when calculating the histogram for each resulting region.

[0058] Moreover, in SPOC and PHOC, not all grid points correspond to words in the lexicon. Thus, during recognition, given a predicted attribute vector, a nearest neighbor searching step is required to find the nearest point that corresponds to a word in the lexicon.

[0059] To summarize, the handwriting recognition process according to embodiments of the present invention differs from the SPOC and PHOC coding methods described in the Rodriguez-Serrano et al. 2013 and Almazn et al. 2014 (see also FIG. 1) in that, here, after the target image is embedded into the Euclidean vector space, no nearest neighbor search is done; rather, the predicted attribute vector v2 of the target image is directly subject to the decoding algorithm to obtain the recognition result. This is possible because the label embedding uses an invertible coding scheme which is a one-to-one mapping between valid grid points of the Euclidean vector space and character strings.

[0060] Thus, embodiments of the present invention provide a handwriting recognition method enables unconstrained transcription of handwritten word images. Unconstrained refers to the fact that the method does not require the use of a predefined lexicon during transcription. The method resolve the technical difficulty of transcribing a textual image that may contain arbitrary text. The method provides a defined procedure to encode and decode text embedding without using optimization or machine learning based methods for encoding and decoding (machine learning is only used to embed the handwriting image into the attribute vector space). This method enables the recognition of textual images that are not contained in a lexicon, such as financial numbers in accounting forms, or any character sequences that is not pre-defined.

[0061] Is should be noted that when the image to be processed is a scanned image with textual information, it first needs to be preprocessed to remove noise, correct skewness, and analyze its layout so that textual region can be located. Those textual regions are then segmented into line images and further into word images. In the network training process and image recognition process described above, all input images are word images that have been subject to the above pre-processing.

[0062] The handwriting recognition method described above can be implemented on one or more computer systems which include memories storing computer executable programs and processors executing such programs. The one or more computer systems that implement the artificial neural network may include one or more GPU cluster machines. Different parts of the process (e.g., network training, prediction using trained network, etc.) may be implemented on different computers or computer systems.

[0063] It will be apparent to those skilled in the art that various modification and variations can be made in the handwriting recognition method of the present invention without departing from the spirit or scope of the invention. Thus, it is intended that the present invention cover modifications and variations that come within the scope of the appended claims and their equivalents.