Clustering of forms from large-scale scanned-document collection

• US 8,509,525 B1
• Filed: 04/06/2011
• Issued: 08/13/2013
• Est. Priority Date: 04/06/2011
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Urbach, Shlomo, Netzer, Yuval, Fink, Eyal, Yadid, Tal
• Primary Examiner(s): Rahmjoo, Mike
• Application Number:
  US13/080,877
• Time in Patent Office: 860 Days
• Field of Search: 382/159, 382/186, 382/185, 382/181, 382/173, 382/189, 382/226, 345/435, 345/436, 345/440
• US Class Current: 382/159
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

Techniques for identifying documents sharing common underlying structures in a large collection of documents and processing the documents using the identified structures are disclosed. Images of the document collection are processed to detect occurrences of a predetermined set of image features that are common or similar among forms. The images are then indexed in an image index based on the detected image features. A graph of nodes is built. Nodes in the graph represent images and are connected to nodes representing similar document images by edges. Documents sharing common underlying structures are identified by gathering strongly inter-connected nodes in the graph. The identified documents are processed based at least in part on the resulting clusters.

Claims

1. A computer-implemented method of identifying documents sharing a common underlying structure, comprising:

detecting occurrences of a plurality of predetermined image features in a plurality of document images, wherein at least one of the plurality of predetermined image features is common among instances of a form;

indexing the plurality of document images in an image index based on the detected image features;

building a graph of connected nodes for the plurality of document images by searching the image index;

identifying the documents sharing the common underlying structure using the graph;

reproducing the common underlying structure shared by the identified documents; and

generating improved images of the identified documents by overlaying the reproduced common underlying structure on document images of the identified documents.

2. The method of claim 1, wherein the graph comprises a weighted graph and edges in the weighted graph are assigned weights measuring similarities between document images represented by nodes connected by the edges.

3. The method of claim 2, wherein a weight assigned to an edge in the weighted graph comprises a combination of component scores measuring similarities between image features detected in images represented by nodes connected by the edge, and the method further comprises:

training a machine-learning engine using labeled image pairs; and

generating the combination of component scores by the machine-learning engine based on the component scores.

4. The method of claim 1, wherein the plurality of predetermined image features comprises one or more of the following:

stable features that are at least partially invariant to one or more of the following;

scale, orientation, illumination, contrast, and image quality;

line segments detected in the document images; and

text phrases recognized in the document images.

5. The method of claim 1, wherein the identifying comprises:

gathering nodes in the weighted graph into one or more clusters of strongly inter-connected nodes; and

identifying document images represented by nodes in a same cluster as documents sharing the common underlying structure.

6. The method of claim 5, wherein nodes having more links among each other than they have with other nodes are gathered into a same cluster.

7. The method of claim 5, further comprising:

building a cluster graph sharing the same nodes as the weighted graph;

connecting two nodes in the cluster graph based on (1) whether the two nodes are connected in the weighted graph through a path, (2) a comparison of a total number of hops in the path and a first threshold value, and (3) a comparison of a sum of weights assigned to edges along the path and a second threshold value; and

gathering the nodes in the cluster graph into one or more clusters based at least on connectivity among the nodes in the cluster graph.

8. The method of claim 5, further comprising:

identifying a representative document image for the one or more clusters;

indexing the representative document images in a classification index; and

labeling documents sharing the common underlying structure in a second plurality of document images by searching the second plurality of document images in the classification index for similar document images.

9. The method of claim 1, further comprising:

recognizing text in the reproduced common underlying structure shared by the identified documents; and

augmenting the identified documents using the text recognized in the reproduced common underlying structure.

10. The method of claim 1, further comprising:

removing the common underlying structure from an identified document to generate a resulting image; and

processing the resulting image to detect information unique to the identified document.

11. A computer system for identifying documents sharing a common underlying structure, comprising:

a non-transitory computer-readable storage medium comprising executable computer program code for;

detecting occurrences of a plurality of predetermined image features in a plurality of document images, wherein at least one of the plurality of predetermined image features is common among instances of a form;

indexing the plurality of document images in an image index based on the detected image features;

building a graph of connected nodes for the plurality of document images by searching the image index;

identifying the documents sharing the common underlying structure using the graph;

reproducing the common underlying structure shared by the identified documents; and

generating improved images of the identified documents by overlaying the reproduced common underlying structure on document images of the identified documents; and

a processor for executing the computer program code.

12. The system of claim 11, wherein the graph comprises a weighted graph and edges in the weighted graph are assigned weights measuring similarities between document images represented by nodes connected by the edges.

13. The system of claim 12, wherein a weight assigned to an edge in the weighted graph comprises a combination of component scores measuring similarities between image features detected in images represented by nodes connected by the edge, and the computer-readable storage medium further comprises executable computer program code for:

training a machine-learning engine using labeled image pairs; and

generating the combination of component scores by the machine-learning engine based on the component scores.

14. The system of claim 11, wherein the plurality of predetermined image features comprises one or more of the following:

stable features that are at least partially invariant to one or more of the following;

scale, orientation, illumination, contrast, and image quality;

line segments detected in the document images; and

text phrases recognized in the document images.

15. The system of claim 11, wherein the identifying comprises:

gathering nodes in the weighted graph into one or more clusters of strongly inter-connected nodes; and

identifying document images represented by nodes in a same cluster as documents sharing the common underlying structure.

16. A non-transitory computer-readable storage medium storing executable computer program instructions for identifying documents sharing at least one a common underlying structure, the computer program instructions comprising instructions for:

detecting occurrences of a plurality of predetermined image features in a plurality of document images, wherein at least one of the plurality of predetermined image features is common among instances of a form;

indexing the plurality of document images in an image index based on the detected image features;

building a graph of connected nodes for the plurality of document images by searching the image index, wherein nodes representing instances of a predefined document type are connected by edges in the graph;

identifying the documents sharing the common underlying structure using the graph;

reproducing the common underlying structure shared by the identified documents; and

generating improved images of the identified documents by overlaying the reproduced common underlying structure on document images of the identified documents.

17. The storage medium of claim 16, wherein the graph comprises a weighted graph and edges in the weighted graph are assigned weights measuring similarities between document images represented by nodes connected by the edges.

18. The storage medium of claim 17, wherein a weight assigned to an edge in the weighted graph comprises a combination of component scores measuring similarities between image features detected in images represented by nodes connected by the edge, and the computer program instructions further comprise instructions for:

training a machine-learning engine using labeled image pairs; and

generating the combination of component scores by the machine-learning engine based on the component scores.

19. The storage medium of claim 16, wherein the plurality of predetermined image features comprises one or more of the following:

stable features that are at least partially invariant to one or more of the following;

scale, orientation, illumination, contrast, and image quality;

line segments detected in the document images; and

text phrases recognized in the document images.