Graphical syntax analysis of tables through tree rewriting

• US 20080028291A1
• Filed: 07/26/2006
• Published: 01/31/2008
• Est. Priority Date: 07/26/2006
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Vion-Dury, Jean-Yves
• Granted Patent: US 7,752,538 B2
• Time in Patent Office: Days
• US Class Current: 715/228
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

To determine a table structure, a spatially ordered sequence of rectangular cells (42) disposed in a two dimensional region is derived. The ordered sequence of rectangular cells is parsed in accordance with a two-dimensional structural grammar (54) having terminal elements corresponding to cells and non-terminal elements corresponding to structural relationship operators. The parsing produces a grammatical expression (52) with the cells represented by terminal elements and structural relationships represented by non-terminal elements.

Claims

1. a method for determining a table structure, the method comprising:

determining a table structure respective to a first two cells of a spatially ordered sequence of rectangular cells, the table structure including elements indicative of the first two cells and at least one element indicative of a structural relationship between the first two cells;

defining a minimum rectangular bounding box containing the cells of the table structure;

updating the table structure with additional structure including an element indicative of a next cell of the spatially ordered sequence of rectangular cells and at least one element indicative of a structural relationship between the next cell and the minimum rectangular bounding box; and

repeating the defining and updating until the cells of the ordered sequence of rectangular cells are exhausted.

2. The method as set forth in claim 1, wherein the updating further comprises:

conditional upon a selected portion of the table structure satisfying a rewrite criterion, rewriting the selected portion of the table structure in accordance with a rewrite rule corresponding to the rewrite criterion.

3. The method as set forth in claim 2, wherein the rewriting is configured to remove any cell crossings or containments using one or more rewrites.

4. The method as set forth in claim 1, wherein the table structure is a tree structure in which the elements indicative of cells are leaf nodes and the elements indicative of structural relationships are non-leaf nodes, the updating comprising:

adding a leaf indicative of the next cell to the table structure; and

adding a non-leaf node indicative of a structural relationship between the next cell and the minimum rectangular bounding box.

5. The method as set forth in claim 4, wherein the updating further comprises:

conditional upon a selected portion of the tree structure satisfying a rewrite criterion, rewriting the selected portion of the tree structure in accordance with a rewrite rule corresponding to the rewrite criterion.

6. The method as set forth in claim 5, wherein the rewrite rules include the Standard Structural Rewriting Rule Set.

7. The method as set forth in claim 4, further comprising:

conditional upon failure of one of the determining and the updating, terminating the method with an indication that the ordered sequence of rectangular cells does not correspond to a recognizable table.

8. An apparatus operating on a spatially ordered sequence of rectangular cells representing a table, the apparatus comprising:

a two-dimensional structural grammar having terminal elements corresponding to rectangular cells and non-terminal elements corresponding to structural relationship operators; and

a structural parser configured to parse the spatially ordered sequence of rectangular cells representing the table in accordance with the two-dimensional structural grammar, the parsing producing a grammatical expression indicative of spatial positions of the rectangular cells relative to one another.

9. The apparatus as set forth in claim 8, further comprising:

a set of grammar rewrite rules, the structural parser accessing selected grammar rewrite rules to simplify the grammatical expression during parsing.

10. The apparatus as set forth in claim 8, wherein the structural parser outputs the grammatical expression with the cells represented by terminal elements of the grammar and structural relationships represented by non-terminal elements of the grammar.

11. The apparatus as set forth in claim 8, further comprising:

a pre-processor configured to process a document to identify the spatially ordered sequence of rectangular cells representing the table.

12. The apparatus as set forth in claim 11, wherein the pre-processor comprises:

a canonical transformation processor configured to generate a spatially ordered sequence of vectors from the document; and

a cells segmenter configured to identify the spatially ordered sequence of rectangular cells representing the table from the spatially ordered sequence of vectors.

13. The apparatus as set forth in claim 11, wherein the pre-processor outputs the spatially ordered sequence of rectangular cells representing the table in a format in which each rectangular cell is represented by coordinates of opposing corners of the rectangular cell and the spatially ordered sequence of rectangular cells is spatially ordered respective to the coordinates of opposing corners of the rectangular cells.

14. The apparatus as set forth in claim 8, further comprising:

a logical analyzer configured to process contents of the table based at least in part on the grammatical expression indicative of spatial positions of the rectangular cells relative to one another.

15. A method for determining a table structure, the method comprising:

deriving a spatially ordered sequence of rectangular cells disposed in a two-dimensional region; and

parsing the spatially ordered sequence of rectangular cells in accordance with a two-dimensional structural grammar having terminal elements corresponding to cells and non-terminal elements corresponding to structural relationship operators, the parsing producing a grammatical expression with the cells represented by terminal elements and structural relationships represented by non-terminal elements.

16. The method as set forth in claim 15, wherein each cell of the derived spatially ordered sequence is represented by two points corresponding to opposing corners of the cell, and the ordered sequence employs a spatial ordering based on coordinates of the points.

17. The method as set forth in claim 16, wherein each point is represented by two rectilinear coordinates, and the spatial ordering is in accordance with:

<

p₁,p₂>

<

p₃,p₄>

(p₁p₃)(p₁p₃̂

(p₂p₄))

where <

p₁,p₂> and

<

p₃,p₄>

denote two cells, p1, p2, p3, p4 denote points representing said cells, and the spatial ordering of points is in accordance with;

p₁p₂(p₁.α

<

p₂.α

)(p₁.α

=p₂.α

p₁.β

<

p₂.β

)

where the notation “

p.α

”

denotes an α

-coordinate of a point denoted by “

p”

, and the notation “

p.β

”

denotes a β

-coordinate of the point denoted by “

p”

, the α and

β

coordinates being mutually orthogonal.

18. The method as set forth in claim 15, wherein the structural relationship operators of the grammar include at least AboveLeft, AboveRight, AboveEq, LeftUpper, LeftBottom, and LeftEq, two-dimensional structural relationship operators

19. The method as set forth in claim 18, wherein the structural relationship operators of the grammar further include Contains and Overlaps two-dimensional structural relationship operators

20. The method as set forth in claim 15, wherein the parsing comprises:

generating an existing grammatical expression including an initial two terminal elements representing a first two cells of the spatially ordered sequence of rectangular cells and a non-terminal element representing a relationship between the initial two terminal elements;

extending the existing grammatical expression by adding a next terminal element indicative of a next cell of the spatially ordered sequence of rectangular cells and a non-terminal element indicative of a relationship between the next cell and the table structure represented by the existing grammatical expression; and

repeating the extending until the existing grammatical expression includes terminal elements representing all cells of the spatially ordered sequence of rectangular cells.

21. The method as set forth in claim 20, wherein the parsing further comprises:

selectively applying grammatical rewrite rules to rewrite at least a portion of the existing grammatical expression.

22. The method as set forth in claim 15, further comprising:

conditional upon completion of the parsing, identifying the spatially ordered sequence of rectangular cells as corresponding to a table; and

conditional upon a failure of the parsing, identifying the spatially ordered sequence of rectangular cells as not corresponding to a table.