Clustering of forms from large-scale scanned-document collection

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.

TECHNICAL FIELD

The invention generally relates to the field of image processing, in particular to identifying common underlying structures.

BACKGROUND

Document archives often include instances of the same underlying forms. Examples of such instances include standard governmental documents of a certain country used during a specific time range in the past (e.g., 1930's German birth certificates). Because the underlying form is the same across different instances, knowledge of the form can be exploited when extracting information from the document archive via processing of the forms contained therein. However, there is no known approach that can effectively identify instances of the same forms in a large document collection. Accordingly, there is a need for a way to automatically recognize instances of the same forms in a large document collection.

SUMMARY OF THE INVENTION

In accordance with one aspect of the invention, a computer-implemented method of identifying documents sharing at least one common underlying structure, includes: detecting occurrences of a plurality of predetermined image features in a plurality of document images, in which 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, in which nodes representing instances of a predefined document type are connected by lines (also called “edges”) in the graph; and identifying the documents sharing common underlying structures using the graph. The above-described computer-implemented method may advantageously be used to identify instances of the same forms in a large document collection.

In accordance with another aspect of the invention, a computer system for identifying documents sharing at least one common underlying structure, includes: a computer-readable storage medium that includes executable computer program code for: detecting occurrences of a plurality of predetermined image features in a plurality of document images, in which 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, in which nodes representing instances of a predefined document type are connected by edges in the graph; and identifying the documents sharing common underlying structures using the graph. The above-described computer system may advantageously be used to identify instances of the same forms in a large document collection.

In accordance with still another aspect of the invention, a non-transitory computer-readable storage medium storing executable computer program instructions for identifying documents sharing at least one common underlying structure, the computer program instructions include instructions for: detecting occurrences of a plurality of predetermined image features in a plurality of document images, in which 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, in which nodes representing instances of a predefined document type are connected by edges in the graph; and identifying the documents sharing common underlying structures using the graph. The above-described storage medium may advantageously be used to identify instances of the same forms in a large document collection.

DETAILED DESCRIPTION

System Environment

FIG. 1is a high-level block diagram that illustrates a computing environment100for identifying documents sharing common underlying structures in a large collection of documents and processing the documents using the identified structures. The common underlying structures include graphical components such as lines, boxes, and logos, and text components such as boilerplate. Example documents sharing common underlying structures include filled (or populated) instances of a same form (e.g., 1930's German birth certificates). For simplicity, documents sharing common underlying structures are also referred to as “common form instances” in the following description. As used herein, the term “common underlying structures” refers to structures which are shared by at least two documents in which the shared structures are determined to be sufficiently similar using a predetermined criterion or predetermined criteria, which include but are not limited to the presence of matching image features. As further described herein, an image feature is an attribute or attributes of a structure in a document image. One skilled in the art would understand that the embodiments described herein may be applied to documents of a variety of predefined document types such as forms. As shown, the computing environment100includes a scanner110connected with a form identification and processing system120. Only one instance of the scanner110and the system120are shown inFIG. 1for clarity, but those of skill in the art will recognize that multiple scanners110and/or systems120can be present.

The scanner110is a hardware device configured to optically scan a large corpus of printed documents (e.g., books, newspapers) and convert the printed documents to a set of digital images (also called “document images”). The set of document images from the printed document corpus is fed into the form identification and processing system120.

The form identification and processing system120identifies common form instances in the set of document images and processes the document images using the underlying structures of the forms. The system120analyzes the document images to detect the presence of a predetermined set of image features that are common or similar among forms, and builds a weighted graph of nodes connected through lines (also called “edges”) that describes similarity among the document images. Each node represents a document image and has weighted edges connecting it to other nodes representing similar document images based on matched image features detected therein. The edge weights represent the level of similarity between the document images. The system120analyzes the weighted graph to identify clusters of nodes representing common form instances, and optionally uses information present in the clusters to process the document images. The processing can be used to output, for example, a representative image describing the form, an image of the underlying form, and/or text extracted from the form instances. An example architecture and an example methodology of the system120are described in detail below.

Computer Architecture

The entities shown inFIG. 1are implemented using one or more computers.FIG. 2is a high-level block diagram illustrating an example computer200. The computer200includes at least one processor202coupled to a chipset204. The chipset204includes a memory controller hub220and an input/output (I/O) controller hub222. A memory206and a graphics adapter212are coupled to the memory controller hub220, and a display218is coupled to the graphics adapter212. A storage device208, keyboard210, pointing device214, and network adapter216are coupled to the I/O controller hub222. Other embodiments of the computer200have different architectures.

The storage device208is a non-transitory computer-readable storage medium such as a hard drive, compact disk read-only memory (CD-ROM), DVD, or a solid-state memory device. The memory206holds instructions and data used by the processor202. The pointing device214is a mouse, track ball, or other type of pointing device, and is used in combination with the keyboard210to input data into the computer system200. The graphics adapter212displays images and other information on the display218. The network adapter216couples the computer system200to one or more computer networks.

The types of computers200used by the entities ofFIG. 1can vary depending upon the embodiment and the processing power required by the entity. For example, the form identification and processing system120might comprise multiple blade servers working together to provide the functionality described herein. The computers200can lack some of the components described above, such as keyboards210, graphics adapters212, and displays218.

Example Architectural Overview of the Form Identification and Processing System

FIG. 3is a high-level block diagram illustrating a detailed view of modules within the form identification and processing system120. Some embodiments of the system120have different and/or other modules than those described herein. Similarly, the functions can be distributed among the modules in accordance with other embodiments in a different manner than is described herein. As shown, the system120includes a feature detection module310, an image index module320, a graphing module330, a clustering engine340, a form processing module350, and a data store360.

The feature detection module310detects occurrences of image features in document images and generates descriptions of the detected image features (e.g., orientation, relative position). An image feature is an attribute or a set of attributes relevant for describing content such as a structure in an image. An underlying structure (e.g., a graphical component such as a signature line, a text component such as boilerplate language in a form) may include one or more image features describing various characteristics of the underlying structure. In one embodiment, the module310is configured to detect a predetermined set of families of image features that are relevant to distinguishing between forms and other types of documents.

One example family of image features includes stable features that are invariant (or partially invariant) to image parameters such as scale, orientation, illumination, contrast, and image quality. Examples of the stable features include features describing using the Scale-Invariant Feature Transform (SIFT).

Another example family of image features includes features describing line segments found in an image. Forms often contain line segments such as text bounding boxes, signature locations, and checkboxes. In one embodiment, the feature detection module310is configured to detect and generate features describing line segments in images satisfying certain criteria, such as having particular orientations (e.g., almost vertical/horizontal) and particular lengths.

Yet another example family of image features includes features describing text phrases recognized in an image along with measurements of bounding boxes (e.g., relative position and size) containing the text phrases. Many form instances will contain text in the same locations. For example, the text can be identical boilerplate text that always appears in the same location in the form instances. The text can also be different text that always appears in approximately the same location, such as text answering questions posed by the form.

In one embodiment, to detect image features, the feature detection module310first pre-processes the images to identify text orientation in the images. The module310then rotates the images (e.g., by 90°, 180° or 270°) into a standard orientation, such that the text orientation is consistent across the set of images. In one embodiment, the image is rotated to bring the text into the standard reading orientation. The module310then detects image features such as those described above in the resulting images using the appropriate techniques (e.g., SIFT algorithm, Optical Character Recognition (OCR) procedures).

The image index module320indexes the document images in an image index based on the image features (or combinations of image features) detected therein, such that one can search for document images in the image index based on image features. The image index module320supports image lookup for images similar to a given image as measured by the image features. The image index module320detects the features of the given image, and then identifies images in the image index that have similar features. In one embodiment, the image index module320supports k-nearest-neighbors (kNN) searches (e.g., the image index module320returns k images that are more similar to the given image than the other images (also called the “top k images”)). To support the kNN searches, the image index module320includes a similarity measure module325for measuring degrees of similarity among document images by matching image features detected therein, and returning the top k images as search results. The degree of similarity between two images can be measured based on the number or portion of matching image features between the two images. Because the detected image features are relevant for describing structures in document images, matching image features indicate that two images likely have common structures.

In one embodiment, the similarity measure module325measures similarity between two images using a similarity distance score representing the similarity of the images based on consideration of one or more image features from the various feature families. In one embodiment, the smaller a similarity distance score, the greater the similarity between the two images. Other embodiments use a similarity distance score where a greater score indicates greater similarity.

For example, the similarity measure module325can use a similarity distance score derived from a combination of component scores measuring constituent image features. One component score can be calculated based on the total number (or portion) of matching stable features in the two images, taking into account optimum transformation factors (e.g., allowing scale, shift, and small rotation). Another component score can be based on the total number (or portion) of matching line-segment features. A third component score can be based on the overlap of text phrase collections of the two images. The module325can give different image features or feature families different weights that influence the overall affect that the features or families have on the similarity distance score. In one embodiment, the module325determines the component scores to use, and the weights for the scores, through direct observation and/or machine learning. For example, a machine-learning engine can be trained using labeled similar/unsimilar image pairs to calculate similarity distance scores for image pairs based on their component scores.

The graphing module330builds a weighted graph describing the document images and the similarities among them. One embodiment of the graph includes nodes connected through weighted edges. Each node represents a document image in the image index and has edges connected to nodes representing similar document images. Each edge carries as its weight the similarity distance score between the two document images represented by the connected nodes. In one embodiment, the graphing module330builds the weighted graph by first creating nodes representing the indexed document images, and then connecting each node with nodes representing the top k most similar images (e.g., k=100).

The clustering engine340analyzes the weighted graph to identify clusters of nodes representing common form instances. A cluster (also called a near-clique) is a set of strongly inter-connected nodes (e.g., nodes having more links among each other than they have with the other nodes). Because only nodes representing similar images are connected and the similarity is based on similarities of predetermined image features common among forms, document images represented by nodes within a cluster are more likely to be images of common form instances as compared to document images represented by nodes of different clusters.

In one embodiment, the clustering engine340identifies clusters by building a second unweighted graph, called a “cluster graph.” The cluster graph shares the same nodes as the original weighted graph (i.e., the weighted graph built by the graphing module330) but not the edges in the weighted graph. Any two nodes in the cluster graph are connected if they are connected through a short path (i.e., one or a series of edges) in the weighted graph. Example conditions for a path to qualify as a short path include the total number of hops in the path not exceeding a threshold value, and the total of weights assigned to the edges along the path satisfying another threshold value.

FIG. 5Aillustrates a weighted graph of 6 nodes N1through N6connected through edges Ei,jwith various weights Wi,jandFIG. 5Billustrates a corresponding exemplary cluster graph according to a set of example conditions. The example conditions applied to build the exemplary cluster graph include, for a path to qualify as a short path, the total number of hops must be no more than 3 and the total of weights along the path must be smaller than a value that is smaller than the weight assigned to the edge between N4and N5).

Once the cluster graph is built, the clustering engine340applies graph-based clustering algorithms to gather nodes in the cluster graph into clusters. The clustering engine340may optionally verify the resulting clusters by measuring the distance (e.g., the similarity distance score) between any two nodes within a same cluster. The clustering engine340may also measure the distance of images from different clusters to find nearby clusters and optionally merge them. The clustering engine340may also provide the resulting clusters to human operators for quality control and/or labeling. The clustering engine340may be configured to identify multiple hierarchies of clusters. For example, a higher level cluster may include instances of a particular U.S. government immigration form (e.g., the Arrival-Departure Records), and multiple lower level sub-clusters within the higher level cluster may include instances of that form in different languages (e.g., the Arrival-Departure Records in English, Spanish, Chinese, etc.).

In an alternative embodiment, instead of (or in addition to) the weighted graph and the cluster graph, the graphing module330is configured to represents the images as points in a k-dimensional space based on the image features detected therein. The clustering engine340is configured to apply corresponding known clustering techniques to gather these points in the k-dimensional space.

The form processing module350processes the document images using the image features and identified clusters. As illustrated through various non-limiting examples discussed below, the module350can process the document images using a variety of different techniques and for a variety of different purposes. In general, each type of processing exploits the identified clusters and/or image features to produce results that are not possible or not as efficiently derived in the absence of such cluster or feature information.

In one embodiment, the form processing module350processes the document images to identify a set of representative images for forms contained in the document corpus. To perform this type of processing for a form, an embodiment of the module350analyzes a cluster in the cluster graph containing nodes representing document images of instances of the form to identify one or more nodes in the cluster as representative of the cluster. The module350can identify a representative node by, for example, identifying a node with the highest number of edges in the cluster. The document image of this node is representative of the document images represented in the cluster.

The form processing module350can use the set of representative images for further processing (e.g., associating, labeling) of document images. For example, when new document images are received, the module350can classify the new document images as given form instances by comparing the new images with the set of representative images and classifying the new images as being the same type of form as the closest-matching representative image. Further, the module350can recognize new document images that do not closely-match representative images in the set as representing possible new forms.

In another embodiment, the form processing module350uses the document images within a cluster to reproduce the form from which the form instances are derived. For example, the module350can process the document images in the cluster to identify the aspects of the images that are common to all, or a majority, of the form instances, and establish these aspects as being part of the base form. The module350can additionally use the reproduced form to perform further processing of the document images within the cluster to extract variable text from the form instances, recognize boilerplate text in the form, etc. The text in the form and form instances can then be further processed for purposes such as allowing textual searching within the form instances. Additionally or alternatively, the module350can remove the common aspects (e.g., common image features) from the document images in the cluster, such that the resulting images only contain image features that are not shared by other images in the cluster. The module350can then process the resulting images to detect information unique to the document images (e.g., recognizing text unique to an instance of the underlying form).

The form processing module350can also process the form instances by using the reproduced form to improve the quality of the form instances. The module350can use the reproduced form to identify components in the form instances that are of highest quality, and then augment the other form instances using these high-quality components. For example, the module350can identify a form instance that has a high-quality version of a boilerplate section (e.g., a version free from scanning artifacts that are present in other form instances) and overlay this boilerplate section on other instances of the form that are displayed to a viewer. The module350can also insert text or other components extracted from the high-quality version into other form instances, thereby providing improved searching capacity for the form instances having the components.

The data store360stores data used by the form identification and processing system120. Examples of such data include but are not limited to the document images, the detected image features, the image index, the weighted graph, the cluster graph, and the reproduced underlying forms. The data store350may be a relational database or any other type of database. Portions of the data store360may be stored temporarily or permanently in main memory (RAM) across one or more computers in the computing environment100.

Overview of Methodology for the Form Identification and Processing System

FIG. 4is a flow diagram illustrating a process400for identifying documents sharing common underlying structures in a large collection of documents and processing the documents using the shared structures. Other embodiments can perform the steps of the process400in different orders. Moreover, other embodiments can include different and/or additional steps than those described herein.

In step410, the system120detects the presence of a plurality of predetermined image features that are common among forms in the document images. Examples of the image features include SIFT features, line segments, and recognized text phrases. In step420, the system120indexes the document images in an image index based on the image features detected therein, and in step430builds a weighted graph of nodes representing the indexed images and connected to nodes representing the top k most similar images measured based on matching image features.

In step440, the system120identifies common form instances by building a cluster graph based on the weighted graph, classifying nodes in the cluster graph into clusters, and identifying document images represented in a same cluster as instances of a common form. In step450, the system120processes the common form instances based on the identified clusters. For example, the system120identifies a set of representative images for the identified form instances and/or improves the quality of the form instances using high quality components identified among the form instances.

Upon reading this disclosure, those of skill in the art will appreciate still additional alternative structural and functional designs for a system and a process for identifying documents sharing common underlying structures in a large collection of documents and processing the documents using the identified structures. Thus, while particular embodiments and applications have been illustrated and described, it is to be understood that the present disclosure is not limited to the precise construction and components disclosed herein and that various modifications, changes and variations which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method, system, and storage medium disclosed herein without departing from the spirit and scope as defined in the appended claims.