Weak-to-strong annotation alignment for tabular data

Abstract

Systems and processes for aligning weakly-annotated tabular data to recognized characters in a document are provided. Data table annotations are grouped by column and value to produce a plurality of annotation groups. Character recognition tokens are received, and a search algorithm is performed to align the annotation groups to the tokens in a stepwise manner. A base column is designated, after which the search algorithm is performed on the base column annotation groups and the results are used to determine a vertical range of the data table. The search algorithm is then run for the other columns of the data table with the results being limited based on the vertical range. At each step, the annotations in an annotation groups are each aligned to one or more of the tokens. A bounding box is generated for each annotation in the data table and output to a target application.

We claim: 
     
         1 . One or more computer-readable media storing instructions which, when executed by one or more hardware processors, cause the hardware processors to perform actions comprising:
 receiving, from a character recognition engine, tokens identifying recognized words in a document and bounding box coordinates for each token;   receiving, from an annotation source, a data table comprising a plurality of columns and one or more rows, each row comprising a plurality of annotations to be aligned with the tokens;   grouping the annotations in the data table by column and value to produce a plurality of annotation groups;   in a stepwise process for each of the annotation groups:
 performing a search algorithm to identify a plurality of candidate alignments and associated heuristic scores for the annotation group, each candidate alignment comprising one or more of the tokens; 
 selecting, from among the plurality of candidate alignments, n candidate alignments with highest heuristic scores for the annotation group, where n is a number of annotations in the annotation group; and 
 matching each annotation in the annotation group with one of the selected candidate alignments based on an order in which the annotations are arranged in the data table and the bounding box coordinates of token(s) of the selected candidate alignments; 
   generating, for each of the matches identified via the stepwise process, an annotation bounding box having coordinates associated with a location of the corresponding token(s) in the document; and   outputting an indication of the coordinates of the annotation bounding boxes in the document.   
     
     
         2 . The one or more computer-readable media of  claim 1 , wherein the actions further comprise:
 for each column of the data table, determining a mean character count of the annotations arranged therein; and   designating, among the plurality of columns of the data table, the column whose annotations have a highest mean character count as a base column.   
     
     
         3 . The one or more computer-readable media of  claim 2 , wherein the actions further comprise:
 determining a vertical range of the base column based on the bounding box coordinates of the token(s) of the selected candidate alignments matched with the annotations in the base column.   
     
     
         4 . The one or more computer-readable media of  claim 3 , wherein for the annotation groups in the columns of the data table other than the base column, the n candidate alignments with the highest heuristic scores are selected from among a subset of the plurality of candidate alignments whose token(s) have bounding box coordinates within the vertical range of the base column, wherein the subset includes one or more of the plurality of candidate alignments. 
     
     
         5 . The one or more computer-readable media of  claim 1 , wherein the actions further comprise, in the stepwise process for each of the annotation groups:
 determining that the plurality of candidate alignments comprises a subset of candidate alignments with a same heuristic score and a same y-coordinate of bounding box(es) of the token(s); and   selecting, from among the subset of candidate alignments, the candidate alignment whose token(s) have a smallest bounding box height as one of the n candidate alignments.   
     
     
         6 . The one or more computer-readable media of  claim 1 , further comprising:
 receiving, from the annotation source, an ordered annotation list in which the annotations are arranged in the order they appear in the data table,   wherein the matching further comprises, for each annotation group:
 generating an ordered candidate list of the selected candidate alignments by sorting the selected candidate alignments in descending order based on their bounding box coordinates; and 
 matching the annotations one-by-one in the order they appear in the ordered annotation list to the selected candidate alignments in the order they appear in the ordered candidate list. 
   
     
     
         7 . The one or more computer-readable media of  claim 1 , further comprising:
 identifying, in the data table, annotations representing header fields; and   in a stepwise process for each of the annotations representing the header fields:
 performing a search algorithm to identify a plurality of candidate alignments and associated heuristic scores for the annotation, each candidate alignment comprising one or more of the tokens; 
 determining that the plurality of candidate alignments comprises a subset of candidate alignments with a same heuristic score; and 
 selecting, from among the subset of candidate alignments, the candidate alignment whose token(s) have bounding box(es) with higher y-coordinate values. 
   
     
     
         8 . The one or more computer-readable media of  claim 1 , wherein the search algorithm includes a best-first beam search algorithm. 
     
     
         9 . The one or more computer-readable media of  claim 1 , wherein the indication of the coordinates of the annotation bounding boxes in the document is output to a target application comprising a machine learning model configured to accept strong annotations for documents to train the model. 
     
     
         10 . A method performed by a computer, the method comprising:
 receiving, from a character recognition engine, tokens identifying recognized words in a document and bounding box coordinates for each token;   receiving, from an annotation source, a data table comprising a plurality of columns and one or more rows, each row comprising a plurality of annotations to be aligned with the tokens;   for each column of the data table, determining a mean character count of the annotations arranged therein;   designating, among the plurality of columns of the data table, the column whose annotations have a highest mean character count as a base column;   grouping the annotations in the data table by column and value to produce a plurality of annotation groups;   in a first stepwise process for each of the annotation groups in the base column:
 performing a search algorithm to identify a plurality of candidate alignments and associated heuristic scores for the annotation group, each candidate alignment comprising one or more of the tokens; 
 selecting, from among the plurality of candidate alignments, n candidate alignments with highest heuristic scores for the annotation group, where n is a number of annotations in the annotation group; and 
 matching each annotation in the annotation group with one of the selected candidate alignments based on an order in which the annotations are arranged in the data table and the bounding box coordinates of token(s) of the selected candidate alignments; 
   determining a vertical range of the base column based on the bounding box coordinates of the token(s) of the selected candidate alignments matched with the annotations in the base column;   in a second stepwise process for each of the annotation groups in the columns of the data table other than the base column:
 performing a search algorithm to identify a plurality of candidate alignments and associated heuristic scores for the annotation group, each candidate alignment comprising one or more of the tokens; 
 selecting, from among the plurality of candidate alignments, n candidate alignments with highest heuristic scores for the annotation group whose token(s) have bounding box coordinates within the vertical range of the base column, where n is a number of annotations in the annotation group; and 
 matching each annotation in the annotation group with one of the selected candidate alignments based on the order in which the annotations are arranged in the data table and the bounding box coordinates of the token(s) of the selected candidate alignments; and 
   for each of the matches identified via the first and second stepwise processes, generating an annotation bounding box having coordinates associated with a location of the corresponding token(s) in the document.   
     
     
         11 . The method of  claim 10 , further comprising, in each of the first and second stepwise processes:
 determining that the plurality of candidate alignments comprises a subset of candidate alignments with a same heuristic score and a same y-coordinate of bounding box(es) of the token(s); and   selecting, from among the subset of candidate alignments, the candidate alignment whose token(s) have a smallest bounding box height as one of the n candidate alignments,   
     
     
         12 . The method of  claim 10 , further comprising:
 receiving, from the annotation source, an ordered annotation list in which the annotations are arranged in the order they appear in the data table,   wherein, in each of the first and second stepwise processes, the matching further comprises, for each annotation group:
 generating an ordered candidate list of the selected candidate alignments by sorting the selected candidate alignments in descending order based on their bounding box coordinates; and 
 matching the annotations one-by-one in the order they appear in the ordered annotation list to the selected candidate alignments in the order they appear in the ordered candidate list. 
   
     
     
         13 . The method of  claim 10 , further comprising:
 identifying, in the data table, annotations representing header fields; and   in a third stepwise process for each of the annotations representing the header fields:
 performing a search algorithm to identify a plurality of candidate alignments and associated heuristic scores for the annotation, each candidate alignment comprising one or more of the tokens; 
 determining that the plurality of candidate alignments comprises a subset of candidate alignments with a same heuristic score; and 
 selecting, from among the subset of candidate alignments, the candidate alignment whose token(s) have bounding box(es) with higher y-coordinate values. 
   
     
     
         14 . The method of  claim 10 , further comprising:
 outputting an indication of the coordinates of the annotation bounding boxes in the document to a target application.   
     
     
         15 . The method of  claim 14 , wherein the target application comprises a machine learning model configured to accept strong annotations for documents to train the model. 
     
     
         16 . The method of  claim 10 , wherein the search algorithm comprises a best-first beam search algorithm. 
     
     
         17 . A system, comprising:
 one or more hardware processors with memory coupled thereto;   computer-readable media storing instructions executable by the one or more hardware processors, the instructions comprising:
 instructions to receive, from a character recognition engine, tokens identifying recognized words in a document and bounding box coordinates for each token; 
 instructions to receive, from an annotation source, a data table comprising a plurality of columns and one or more rows, the plurality of columns comprising a base column and one or more other columns, and each row comprising a plurality of annotations to be aligned with the tokens; 
 instructions to group the annotations in the data table by column and value to produce a plurality of annotation groups; 
 instructions to perform, in a first stepwise process for each of the annotation groups in the base column, a search algorithm to match each annotation in the annotation group with one or more of the tokens; 
 instructions to generate, for each of the matches identified via the first stepwise process, an annotation bounding box having coordinates associated with a location of corresponding token(s) in the document; 
 instructions to determine a vertical range of the base column based on the bounding box coordinates of the token(s) matched with the annotations in the base column; 
 instructions to perform, in a second stepwise process for the annotation groups in the one or more other columns, the search algorithm to match each annotation in the annotation group with one or more of the tokens, wherein the search algorithm only considers tokens for matching whose bounding box coordinates are within the vertical range of the base column; and 
 instructions to generate, for each of the matches identified via the first and second stepwise processes, an annotation bounding box having coordinates associated with a location of the corresponding token(s) in the document. 
   
     
     
         18 . The system of  claim 17 , wherein the annotations in the base column have a higher mean character count than the annotations in each of the one or more other columns. 
     
     
         19 . The system of  claim 18 , wherein the search algorithm includes a best-first beam search algorithm. 
     
     
         20 . The system of  claim 17 , wherein the instructions further comprise:
 instructions to output an indication of the coordinates of the annotations in the document to a machine learning model configured to accept strong annotations for documents to train the model.