Method for graph-based table recognition

Claim 2

A graph-based method for recognizing tables present in a document represented as digital image data, including the steps of: segmenting the digital image data to identify textual and image entities within the document; building a layout graph of the document using the entities; automatically tagging each of the text entities with a label from a document node alphabet to produce a labeled graph; automatically rewriting the labeled graph, by manipulating the text entities therein, using at least one rewriting rule, to identify the logical structure of the document, wherein the logical structure includes an identified table and the labeled graph is a host graph and where the step of automatically rewriting the labeled graph by manipulating the text entities comprises the steps of identifying at least two entities in the layout graph that are isomorphic instances of subgraphs, and replacing, in the host graph, the at least two entities that are isomorphic instances of the subgraphs with a nonterminal entity.

Claim 3

The method of claim 1, wherein the segmentation operation identifies as text entities contiguous, non-overlapping regions of text.

Claim 4

The method of claim 2, wherein the contiguous, non-overlapping regions of text each have a bounding box identifying the boundaries thereof.

Claim 5

The method of claim 3, wherein the step of building a layout graph is based upon a set of geometric relations between entity bounding boxes.

Claim 6

The method of claim 4, wherein the geometric relations between entity bounding boxes are stored in a memory as an ordered list.

Claim 7

The method of claim 4, wherein the geometric relations between entity bounding boxes results in the construction of an edge whenever a relation therebetween is detected from the group consisting of: left of; right of; top of; and bottom of.

Claim 8

The method of claim 2, wherein the text entities are selected from at least one of: a character; a word; a line; and a text region.

Claim 9

The method of claim 7, wherein the text entity group obeys a hierarchical structure, where a character is subordinate to a word; a word is subordinate to a line; and a line is subordinate to a text region.

Claim 10

The method of claim 7, further comprising the step of re-classifying text regions according to their logical identity as one of a plurality of classifications selected from at least one of: a paragraph; a column; a table; an indexed list; a jagged text region; and an unformatted text region.

Claim 11

The method of claim 1, wherein the step of manipulating the text entities of the labeled graph includes a context-free rewrite rule.

Claim 12

The method of claim 1, wherein the step of manipulating the text entities of the labeled graph includes a context-sensitive rewrite rule.

Claim 13

The method of claim 1, wherein the nonterminal entity is connected to the remainder of the host graph based upon a set of embedding relations.

Claim 14

The method of claim 12, wherein the embedding relations are geometric.

Claim 15

The method of claim 12, wherein the embedding relations are logical.

Claim 16

The method of claim 12, wherein each rewrite rule has at least one application condition associated therewith.

Claim 17

The method of claim 15, further comprising the step of testing the application condition prior to the application of a rewrite rule.

Claim 18

The method of claim 16 wherein the application condition requires that a bounding box about the nonterminal entity does not overlap with a bounding box of any of the other entities in the host graph.

Claim 19

The method of claim 1 wherein each rewrite rule has an attribute transfer function associated therewith.

Claim 20

The method of claim 1 wherein each rewrite rule has a production rule associated therewith.

Claim 21

The method of claim 1, further comprising the step of recursively applying the step of manipulating the text entities until no more rewrite rules are applicable.

Claim 22

A graph-based method for recognizing tables present in a document represented as digital image data, including the steps of: segmenting the digital image data to identify textual and image entities within the document; building a layout graph of the document using the entities; automatically tagging each of the text entities with a label from a document node alphabet to produce a labeled graph; automatically rewriting the labeled graph, by manipulating the text entities therein, using at least one rewriting rule, to identify the logical structure of the document, wherein the logical structure includes an identified table and where the rewriting rule comprises a production rule, an embedding function, an attribute transfer functions, and an application condition.

Claim 23

A graph-based method for recognizing tables present in a document represented as digital image data, including the steps of: segmenting the digital image data to identify textual and image entities within the document; building a layout graph of the document using the entities; automatically tagging each of the text entities with a label from a document node alphabet to produce a labeled graph; automatically rewriting the labeled graph, by manipulating the text entities therein, using at least one rewriting rule, to identify the logical structure of the document, wherein the logical structure includes an identified table and where the rewriting rule comprises a production rule, an embedding function, an attribute transfer functions, and an application condition.

Claim 24

An automated document structure recognition system for performing a graph-based method for recognizing tables present in a document represented as digital image data, including: a segmentation subsystem for segmenting the digital image data to identify textual and image entities within the document; a graph construction module for building a layout graph of the document using the entities; an entity recognition subsystem for automatically tagging each of the text entities within the layout graph with a label from a document node alphabet to produce a labeled graph; and a graph rewriting system for automatically rewriting the labeled graph, by manipulating the text entities therein, using at least one rewriting rule, to identify the logical structure of the document, wherein the logical structure includes an identified table, wherein the labeled graph is a host graph and where the rewriting system identifies at least two entities in the layout graph that are isomorphic instances of subgraphs, and replaces, in the host graph, the at least two entities that are isomorphic instances of the subgraphs with a nonterminal entity.

Claim 25

An automated document structure recognition system for performing a graph-based method for recognizing tables present in a document represented as digital image data, including: a segmentation subsystem for segmenting the digital image data to identify textual and image entities within the document; a graph construction module for building a layout graph of the document using the entities; an entity recognition subsystem for automatically tagging each of the text entities within the layout graph with a label from a document node alphabet to produce a labeled graph; and a graph rewriting system for automatically rewriting the labeled graph, by manipulating the text entities therein, using at least one rewriting rule, to identify the logical structure of the document, wherein the logical structure includes an identified table, wherein the labeled graph is a host graph and where the rewriting system identifies at least two entities in the layout graph that are isomorphic instances of subgraphs, and replaces, in the host graph, the at least two entities that are isomorphic instances of the subgraphs with a nonterminal entity.