Region adjacent subgraph isomorphism for layout clustering in document images

Abstract

A computer system and computerized method that groups documents with similar image layout together. A document similarity metric based on locally connected subgraphs is employed. Region adjacency graphs are generated from word segments extracted from document images. Fuzzy attributed graph isomorphism is performed on subgraphs checking node and edge attribute similarity. Document similarity is then calculated on a normalized score between matching subgraphs of different documents. Unsupervised clustering of document layouts is performed to generate clusters of documents with similar structure.

What is claimed is: 
     
       1. A computerized method for generating groupings of documents that are in image format, where the image format has a visually perceptible geometric structure, the method comprising:
 processing each of the documents, by optical character recognition, to generate, for each of the documents, a set of word segments in a text format; 
 generating for each of the documents, a region adjacency graph, comprising one or more subgraphs, from the word segments generated for the corresponding document, wherein, each of the subgraphs comprises one or more nodes, each node corresponding to a word segment, each node connected to at least one other node by an edge, each edge characterized by a distance attribute and an angle attribute; 
 determining node attribute similarity between each document by performing fuzzy attributed graph isomorphism between each subgraph in each document; 
 calculating document similarity, between any two of the documents, on a normalized score between matching subgraphs of the two documents, where determining whether subgraphs from any two documents match is a function of node attribute similarity; and 
 performing unsupervised clustering of document layouts using the calculated document similarity, 
 wherein the processing each of the documents to generate, for each of the documents, a set of word segments comprises:
 processing each document to generate a textual representation of a plurality of keyword segments represented in the document; 
 comparing each of the keyword segments represented in the document against an alias list, the alias list comprising text strings of interest for processing of one or more particular document types; and 
 adding, to the set of word segments that are to be considered when generating the corresponding region adjacency graph for the corresponding document, only those of the keyword segments that match an entry in the alias list, and 
 wherein, documents with similar layout may be grouped together, such that a template designed on one document in a group permits an extraction engine to extract all relevant fields on all documents within the group. 
 
 
     
     
       2. The computerized method of  claim 1  wherein generating for each of the documents, a region adjacency graph, comprising one or more subgraphs, from the word segments generated for the corresponding document, wherein, each of the subgraphs comprises one or more nodes, each node corresponding to a word segment, each node in a subgraph connected to at least one other node by an edge, each edge characterized by a distance attribute and an angle attribute, comprises:
 assigning each keyword segment in the set of word segments to a node, wherein each of the nodes has associated therewith a position corresponding to a two-dimensional position of a corresponding keyword segment in the corresponding document; 
 comparing position of each node in the region adjacency graph with a position of each other node in the region adjacency graph; and 
 connecting a first node to a second node if the second node has a position within a parameterized radius of the first node or if the first node and the second node have y-coordinates that differ within a parameterized range, wherein a set of connected nodes in a region adjacency graph for a document comprises a subgraph within the region adjacency graph. 
 
     
     
       3. The computerized method of  claim 2  wherein each node has associated therewith a segmentation rectangle that encompasses a word segment corresponding to the node, and wherein a connection between the first node and the second node is represented as distance in pixels between top left corners of segmentation rectangles corresponding to the first node and the second node, and angle in degrees between the top left corners of the segmentation rectangles corresponding to the first node and the second node. 
     
     
       4. The computerized method of  claim 1  wherein determining node attribute similarity between each document by performing fuzzy attributed graph isomorphism between each subgraph in each document comprises:
 comparing each subgraph in each document with each subgraph in each of the other documents. 
 
     
     
       5. The computerized method of  claim 4  wherein comparing each subgraph in each document with each subgraph in each of the other documents comprises:
 employing a node matching function to match each node in each subgraph in each document with each node in each subgraph of each of the other documents; and 
 employing an edge matching function to match each edge in each subgraph in each document with each edge in each subgraph in each of the other documents. 
 
     
     
       6. The computerized method of  claim 5  wherein employing a node matching function to match each node in each subgraph in each document with each node in each subgraph of each of the other documents comprises:
 determining similarity of text between a selected first node and a selected second node by determining how many characters in the selected first node and the selected second node nodes are different and normalizing by the mean length of the text strings represented by the selected first node and the selected second node. 
 
     
     
       7. The computerized method of  claim 6  wherein determining similarity of text between a selected first node and a selected second node is performed after converting text in the first node and the second node to lower case characters. 
     
     
       8. The computerized method of  claim 5  wherein employing an edge matching function to match each edge in each subgraph in each document with each edge in each subgraph of each of the other documents comprises:
 determining similarity of a first edge in a first subgraph with a second edge in a second subgraph by determining whether angle attributes of the first edge and the second edge are within a parameterized edge tolerance, and whether distance attributes of the first edge and the second edge are within a parameterized distance tolerance. 
 
     
     
       9. The computerized method of  claim 4  further comprising storing results of the fuzzy attributed graph isomorphism in an n×m matrix where n is the number of subgraphs in any first selected region adjacency graph image graph and m is the number of subgraphs in any region adjacency graph selected for comparison with the first selected region adjacency graph. 
     
     
       10. The computerized method of  claim 1  wherein calculating document similarity, between any two of the documents, on a normalized score between matching subgraphs of the two documents, where determining whether subgraphs from any two documents match is a function of node attribute similarity, comprises:
 matching each subgraph in each region adjacency graph with at most one other subgraph in another region adjacency graph. 
 
     
     
       11. The computerized method of  claim 1  wherein performing unsupervised clustering of document layouts using the calculated document similarity is performed employing density based spatial clustering of applications with noise employing a plurality of parameters employed in generating the region adjacency graphs and in matching subgraphs. 
     
     
       12. The computerized method of  claim 11  wherein the plurality of parameters employed in generating the region adjacency graphs and in matching subgraphs comprises: parameterized radius distance for connecting nodes, parameterized y-coordinate distance for connecting nodes, string edit distance employed in determining if a node exists in a dictionary, edge matching distance tolerance between nodes, edge matching angle tolerance between nodes, string edit distance between nodes, maximum similarity distance between nodes, and number of samples in a neighborhood for a node to be considered as a core node. 
     
     
       13. A document processing system comprising:
 data storage for storing documents that are in image format, where the image format has a visually perceptible geometric structure; and 
 a processor operatively coupled to the data storage and configured to execute instructions that when executed cause the processor to generate groupings of the documents based on similarities in visually perceptible geometric structure by:
 processing each of the documents to generate, by optical character recognition, for each of the documents, a set of word segments; 
 generating for each of the documents, a region adjacency graph, comprising one or more subgraphs, from the word segments generated for the corresponding document, wherein, each of the subgraphs comprises one or more nodes, each node corresponding to a word segment, each node connected to at least one other node by an edge, each edge characterized by a distance attribute and an angle attribute; 
 determining node attribute similarity between each document by performing fuzzy attributed graph isomorphism between each subgraph in each document; 
 calculating document similarity, between any two of the documents, on a normalized score between matching subgraphs of the two documents, where determining whether subgraphs from any two documents match is a function of node attribute similarity; and 
 performing unsupervised clustering of document layouts using the calculated document similarity, 
 
 wherein the processing each of the documents to generate, for each of the documents, a set of word segments comprises:
 processing each document to generate a textual representation of a plurality of keyword segments represented in the document; 
 comparing each of the keyword segments represented in the document against an alias list, the alias list comprising text strings of interest for processing of one or more particular document types; and 
 adding, to the set of word segments that are to be considered when generating the corresponding region adjacency graph for the corresponding document, only those of the keyword segments that match an entry in the alias list. 
 
 
     
     
       14. A document processing system of  claim 13  wherein generating for each of the documents, a region adjacency graph, comprising one or more subgraphs, from the word segments generated for the corresponding document, wherein, each of the subgraphs comprises one or more nodes, each node corresponding to a word segment, each node in a subgraph connected to at least one other node by an edge, each edge characterized by a distance attribute and an angle attribute, comprises:
 assigning each keyword segment in the set of word segments to a node, wherein each of the nodes has associated therewith a position corresponding to a two-dimensional position of a corresponding keyword segment in the corresponding document; 
 comparing position of each node in the region adjacency graph with a position of each other node in the region adjacency graph; and 
 connecting a first node to a second node if the second node has a position within a parameterized radius of the first node or if the first node and the second node have y-coordinates that differ within a parameterized range, wherein a set of connected nodes in a region adjacency graph for a document comprises a subgraph within the region adjacency graph. 
 
     
     
       15. A document processing system of  claim 14  wherein each node has associated therewith a segmentation rectangle that encompasses a word segment corresponding to the node, and wherein a connection between the first node and the second node is represented as distance in pixels between top left corners of segmentation rectangles corresponding to the first node and the second node, and angle in degrees between the top left corners of the segmentation rectangles corresponding to the first node and the second node. 
     
     
       16. A document processing system of  claim 13  wherein determining node attribute similarity between each document by performing fuzzy attributed graph isomorphism between each subgraph in each document comprises:
 comparing each subgraph in each document with each subgraph in each of the other documents. 
 
     
     
       17. A document processing system of  claim 16  wherein comparing each subgraph in each document with each subgraph in each of the other documents comprises:
 employing a node matching function to match each node in each subgraph in each document with each node in each subgraph of each of the other documents; and 
 employing an edge matching function to match each edge in each subgraph in each document with each edge in each subgraph in each of the other documents. 
 
     
     
       18. A document processing system of  claim 17  wherein employing a node matching function to match each node in each subgraph in each document with each node in each subgraph of each of the other documents comprises:
 determining similarity of text between a selected first node and a selected second node by determining how many characters in the selected first node and the selected second node nodes are different and normalizing by the mean length of the text strings represented by the selected first node and the selected second node.