METHOD AND APPARATUS TO LOCATE FIELD LABELS ON FORMS

Method and apparatus to identify field labels from filled forms using image processing to compare two or a few copies of the same kind of form, possibly filled out differently. Filled forms are processed to provide text strings, one for each line of text on each filled form. The text strings are converted to vectors. Vectors from different filled forms are compared to identify common words which are indicative of field labels. In an embodiment, a histogram may be generated to show frequency of occurrence of characters and words, the histogram values also being indicative of field labels.

FIELD OF THE INVENTION

Aspects of the present invention relate to image processing of forms, and more particularly to image processing of filled forms to identify fields in the forms.

BACKGROUND OF THE INVENTION

Automatically finding field labels in images of forms is useful in document process automation. In order to understand how contents of a form match fields of the form, it is necessary to know the form's field labels. Often field labels can be identified in a blank form. However, a blank form is not always available. In that event, it is necessary to identify field labels from the image of a filled form.

There are challenges inherent in reading and comparing filled forms. For example, the same form can be filled out differently, with different contents in each field. As another example, filled form images can be magnified or shrunk to different extents, resulting in different filled forms having different vertical and horizontal dimensions.

Because of the foregoing differences, two of the same type of filled form images may differ significantly from each other, not only in appearance but also in scale, rotation, font style, and/or font size. As a result, it can be difficult to directly apply image processing techniques such as image feature descriptors and image transformations to find fields in filled forms.

In addition, attempting to apply artificial intelligence (AI) techniques to the above-described problems can be time consuming and difficult to accomplish, whether using supervised learning or unsupervised learning.

SUMMARY OF THE INVENTION

In view of the foregoing, it is one object of the present invention to identify field labels by comparing images of the same type of filled form. Among other things, embodiments of the present invention provide the following:A string encoding technique which is highly robust under the variations of scale and rotation, font size and font style, to solve the alignment of images of text lines between two different images of a filled form;A field label-identifying histogram hierarchical technique that tolerates errors in optical character recognition (OCR) error tolerant, but can discriminate between field labels and filled contents;A decreased need for a large number of images of a filled form in order to identify field labels.

Aspects of the invention enable identification of field labels in filled forms, and the generation of an unfilled form after the identification, in a relatively small number of iterations, without requiring the use of AI techniques or the compilation of substantial data sets to train an AI system.

DETAILED DESCRIPTION

FIG.1is a high level block diagram of a system to implement aspects of the method described herein according to one or more embodiments. InFIG.1, computing apparatus may provide pairs of synthetically generated forms (blank, partly filled, or filled) to computing system150. In an embodiment, a filled form110may be provided via scanner120, which may be connected to computing system150either directly or through computing apparatus130. In an embodiment, a camera may provide the input image.

In an embodiment, computing system150will process filled forms to identify field labels. Computing system150may include one or more processors, one or more storage devices, and one or more solid-state memory systems (which are different from the storage devices, and which may include both non-transitory and transitory memory).

As part of the discernment of field label and value location, computing system150may generate bounding boxes around text, using bounding box generation system160. In an embodiment, computing system150may include a text scaling and alignment system165to compensate for images of different scale in different filled forms. In an embodiment, storage175may store the input images that computing system150processes.

Computing system150may be in a single location, with network155enabling communication among the various elements in computing system150. Additionally or alternatively, one or more portions of computing system150may be remote from other portions, in which case network155may signify a cloud system for communication. In an embodiment, even where the various elements are co-located, network155may be a cloud-based system.

Additionally or alternatively, processing system190, which may contain one or more of the processors, storage systems, and memory systems referenced above, may implement one or more algorithms to resolve locations for field labels.

In order to have line-level detection, the images of lines are first extracted using line segmentation algorithms. Ordinarily skilled artisans will be aware of available line segmentation algorithms, and so for the sake of compactness of description line segmentation algorithm details are omitted here.

FIGS.2A and2Bshow two examples of the same form, each filled out differently, and each having a different degree of magnification. In these figures, bounding boxes are drawn around text in field labels in a form. Field205,205′ is the Name field, filled in with the name “Jonas Jackson”. Field210,210′ is the date of birth (DOB) field, filled in with two digits each for the month and day, and, for the year, either four digits (FIG.2A) or two digits (FIG.2B). Field215,215′ is the address field, filled in with a two-line address. Field220,220′ is the phone number field, filled in with a ten-digit number.

Field225,225′ is the diagnosis field, filled in with a description of the diagnosis. Field230,230′ is the procedure/treatment field, filled in with an identification of procedures and/or treatments to be followed. Field235,235′ is a begin date field, filled in with a date on which the procedure and/or treatment is to begin. Field240,240′ is an end date field, filled in with a date on which the procedure and/or treatment is to end. Similarly to fields210,210′, inFIG.2Athe begin date field235,235′ and end date field240,240′ are filled in with two digits each for the month and day, and for the year, either four digits (FIG.2A) or two digits (FIG.2B). Field245,245′ is a field that is filled in with the reason for the particular procedure and/or treatment in field230,230′. Field250,250′ is a field that is filled in with instructions for carrying out the procedure and/or treatment.

FIG.2Aalso contains an extraneous handwritten notation255whichFIG.2Bdoes not have.

One aspect of filled forms such asFIGS.2A and2Bis that their fields are filled in differently, depending on what is to be put in those fields. Descriptions of different diagnoses, procedures/treatments, and/or procedures/treatment instructions can take different amounts of space. Consequences of these differently filled-in forms will be discussed below.

FIG.3shows an example of images of the first line in each of the documents inFIGS.2A and2B. The first line310contains fields205,210(FIG.2A) and the second line320contains fields205′,210′ (FIG.2B).

In an embodiment, after the line images inFIG.3are extracted from the filled forms inFIGS.2A and2B, each line image is digitized into a text string. The text string then is segmented into a set of words with an order based on a position of a word in the string. Repeating words in the text string may be identified by putting an extra character, or extra characters after the word. For example, if a word in the text string appears twice, the second occurrence may have a _1 appended to it. If the word appears three times, the second occurrence may have a _1 appended to it and the third occurrence may have a _2 appended to it. In an embodiment, punctuation marks may not be counted as characters in the text string.

For example, after the line image310inFIG.3is digitized, the text string can be segmented as follows: “BEGIN\DATE\02\03\2023\END\DATE_1\04\03\2023”. After the line image320inFIG.3is digitized, the resulting text string can be segmented as follows: “BEGIN\DATE\07\08\23\END\DATE_1\11\08\23”.

In view of the foregoing, in an embodiment it is possible to encode a set of words in a text string as follows.1) The words in the text string may be numbered with successively increasing numbers from left to right, to form a numerical vector representation of the text string. For example, the text string from the line image310may be encoded as a vector S1={1, 2, 3, 4, 5, 6, 2, 7, 8, 9}. That is, the word “DATE” appears twice in the vector, and so is assigned the same number2) A vector S2may be encoded for the text string320inFIG.3in the same way as vector S1. Vector S2may be generated as follows. If a word in vector S2is the same as a word in S1, the position of the word is the same as the position of the corresponding word in vector S1, and will be assigned the same number. In the present situation, then, vector S2={1, 2, 10, 11, 12, 2, 7, 13, 14, 15}. That is, the first, second, sixth, and seventh words in text string320are the same as in text string310, and so they are assigned the same numbers as in the vector for text string310. The third through fifth words and eighth through tenth words in text string320are different from those in text string310.

In an embodiment, if there are words in vector S2that are not in vector S1, those words may be encoded to follow the number of the last position in vector S1. In an embodiment, if the second text string is shorter than the first text string, padding zeros may be added to vector S2to make vector S2the same length as vector S1. Vector S2may be encoded in this way so that a length of a longest increasing subsequence of vector S2may be a measure of similarity between vector S1and vector S2, where the longest increasing subsequence is a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

With the foregoing comparison of two vectors for the same line of text in two different filled forms, it is useful to consider the performance of this comparison for all lines of text in the two different filled forms. For purposes of this comparison, it is appropriate to select, by hand, two copies of the same form, filled out differently. In this way, the text in the two copies may be compared, and the field labels identified.

Looking back atFIGS.2A and2B, it can be seen that some of the fields contain more lines than others. For example, field215inFIG.2Ahas two lines, while field215′ inFIG.2Bhas three lines. Field225inFIG.2Ahas one line, while field225′ inFIG.2Bhas two lines. Field250inFIG.2Ahas three lines, while field250′ inFIG.2Bhas one line. The differing number of lines in the two forms represented inFIGS.2A and2B, respectively, motivate the approach that will be described for comparing line images of the two forms.

Looking now at the two different copies of the same form, after digitizing and word segmentation, there may be M text strings (corresponding to M line images) from the first image and N text strings (corresponding to N line images) from the second image. M and N may be different for a variety of reasons. For example, there may be additional text lines in one or the other of the images, asFIGS.2A and2Bshow. Sometimes there may be artifacts, as seen at the top ofFIG.2A, which has a handwritten notation255, as noted previously. As a result, the following two word matrices A and B, with M rows and N rows, respectively, can be provided to represent the above two document images:

where ai1. . . aiK, a set of words for the first image, is a row in matrix A and bi1. . . biK, a set of words for the second image, is a row in matrix B, respectively. To determine correspondence between a row in matrix A and a row in matrix B, in an embodiment, the following sequence may be performed:1) Take a row, ai1. . . aiK, from matrix A;2) Find any repeated words in ai1. . . aiKand append a repeated word with “_n” at the end;3) Encode ai1. . . aiKas a vector as described above;4) Take a set of rows, bj1. . . bjKfrom matrix B, where, in an embodiment, j=i−3 to i+3. Depending on the embodiment, a larger or smaller number of rows either before or after the row of focus may be selected. A reason for looking at at least three lines (that is, at least one line before and one line after the line of focus) is to account for possible situations in which the filled-in text associated with a particular field label may occupy different numbers of lines in the respective filled form, as in the examples discussed above with respect toFIGS.2A and2B;5) Encode each row of bj1. . . bjKwith respect to ai1. . . aiKas described above;6) Find the best match between ai1. . . aiKand bj1. . . bjKby finding the longest increasing subsequence for each rows of bj1. . . bjK, where j=i−3 to i+3;7) Go to the next row by incrementing i=i+1.

After the ith iteration of the just-described process, resulting in associating two text lines, l1and l2, respectively, from the two images, the next step is to align l1and l2before going on to the next row. Alignment of l1and l2may be necessary because of considerations such as differing image scale or font size between the two text lines. To determine the correct alignment, in an embodiment each word in l1and l2may be segmented into characters or words. Because the text lines have been matched based on a vector match, it is likely that there will be characters or words in common between the two text lines, so that scaling can be carried out. If no common characters or words are found, the lack of common characters implies that there are no common keywords existing in these two lines. In this case, the process may go on to handle other pairs of text lines, as described previously.

In an embodiment, after a certain number of failures of the process in terms of ability to align text lines, it may be presumed that alignment has failed. Such failure may occur because of image quality of one or both of the filled forms being compared, or because of artifacts on one or both of the filled forms, or for other technical reasons which ordinarily skilled artisans will appreciate. In that event, another filled form may be substituted for one of the just-compared filled forms, or another pair of filled forms may be selected, and the process repeated.

If there are common characters or words between the two text lines l1and l2, it will be possible to identify a group of characters or words that are common to both l1and l2, as seeds for calculating the scale Sxand Syfor the two text lines. For example, looking toward the bottom ofFIG.5, bounding boxes may be drawn around each of the words in the respective text lines.

Using the above calculated scales Sxand Sy, all of the bounding boxes of words in l1can be made to the same scale as in l2. Then, each word in l2can be aligned to the corresponding word in l1based on a position of its bounding box asFIG.5shows. In an embodiment, further alignment can be conducted on the characters of each corresponding word between l1and l2by minimizing an edit distance via a deletion and insertion operation. After alignment, a character histogram can be constructed, as shown in the middle ofFIG.5. In the character histogram, the x-axis represents the characters of the words in text lines, and the y-axis represents the number count of that character appearing in the word. More frequently occurring characters will be represented by taller lines.

Still further, a word histogram can be constructed on top of the character histogram, where the x-axis represents the words in text lines and the y-axis represents the density of the underlying distribution of the characters in the word, where the range of the density is [0, 1], using the following equation:

where ρ is the density of the underlying distribution of the characters in a word; m is a number of text lines; n is a number of characters in the word; and fiis the number count for the ith character in the word. The character histogram and the word histogram form a histogram hierarchy which can be used to identify field labels given several form images. A group of adjacent words with higher density values are determined to be the field labels to be extracted. With this extraction, a blank form such as the one shown inFIG.6may be produced, where the field labels605-650correspond to field labels205-250inFIG.2A.

The foregoing description has been based on the assumption that the two filled forms that are received at the beginning of the process can be matched, aligned, and scaled, and character and word histograms produced to determine field labels from just those two forms. Sometimes, an additional filled form will need to be added to the comparison. In that event, looking at three images with constructed word matrices A, B and C being built, and identified row correspondence between matrices A and B and between matrices A and C, the following process may be provided.1. Take a row of words from matrix A and from the corresponding row in matrices B and C;2. Align the row of words from matrices B and C to the row of words from matrix A;3. Build histograms by using the three aligned rows;4. Localize keywords based on hierarchy histogram for this row;5. Repeat 1 to 4 until all rows are processed.

FIGS.4A and4Bdescribe a flow for the foregoing process according to an embodiment. At401, a number of versions of the same filled form are received. In specifically described embodiments, two or three versions may be received at this point, but in any event the number is not large. At403, image processing is performed to identify line images in each of the filled forms. At405, text strings are created from the line images. At407, for each filled form, a matrix of text strings is created. At409, the first iteration of the comparison of lines of the respective matrices begin, with a variable m being set to 1.

At411, for a first matrix, within a text string, words appearing multiple times are identified. At413, a vector is created for each text string, using the identified words. At415, where the same words are identified in the text string, the same number at that position in the vector is assigned.

At417, a determination is made to see whether the process is far enough along to be working on a line image that is far enough down the matrix to be able to look a predetermined number of rows (x, an integer) before and after the row being worked on. If not (“no” at417), then at419, the vector for the mth row is used, and flow proceeds to429, which will be described. If the process is far enough along (“yes” at417), then at421, for another matrix, a number of text strings from m−x to m+x is selected, and at423, a vector is created for each of those text strings, using identified words in each text string. As before, the same number is assigned to vector positions in each text string that contain the same word for that position.

At427, then, a best vector match between row m of the first matrix and rows m−x to m+x of another matrix may be found. (Similarly to the description for matrices A, B, and C,427may be a comparison between two matrices, or among three, or in any event, among a very small number compared to a number required to obtain a training set to train an AI-based system.) At429, text lines are aligned corresponding to the matched vectors.

Having matched the vectors, at433a determination is made as to whether scaling is possible to give the text lines the same scale. If not (“no” at433), then at435a check is made to see whether all of the lines of the first matrix have been processed. If not (“no” at435), then at437, m is incremented, and flow returns to411. If all of the lines of the first matrix have been processed (“yes” at435), then at439, a further version or versions of the same filled form are received, and flow returns to403.

If scaling is possible (“yes” at433), then at441, seeds are identified from among characters and/or words for each text line, and a scale is calculated. At443, the calculated scales are used to give the text lines under comparison the same scale. Here, again, the number of text lines under comparison may be two or three, depending on the number of matrices being compared in the embodiment, or possibly a few more, but in any event, a much smaller number compared to a number required to obtain a training set to train an AI-based system.

At445, after scaling has been accomplished, a character histogram may be constructed for characters in the text lines. Then, at447, a word histogram may be constructed for words in the text lines. After this, at449, field labels may be identified from the histograms, with the higher numbers as represented along the y axis of the histograms signifying characters in words in the field labels (445), and words in the field labels (447).

At451, if all field labels for the form have been identified, (“yes” at451), then at453a blank form with the field labels may be generated. If not all of the field labels have been generated (“no” at451), then at455a check is made to see whether all of the lines of the first matrix have been processed. If not (“no” at455), then at437, m is incremented, and flow returns to411. If all of the lines of the first matrix have been processed (“yes” at455), then at439, a further version or versions of the same filled form are received, and flow returns to403.

While aspects of the present invention have been described in detail with reference to various drawings, ordinarily skilled artisans will appreciate that there may be numerous variations within the scope and spirit of the invention. Accordingly, the invention is limited only by the following claims.