Graphical syntax analysis of tables through tree rewriting

• US 7,752,538 B2
• Filed: 07/26/2006
• Issued: 07/06/2010
• Est. Priority Date: 07/26/2006
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Vion-Dury, Jean-Yves
• Primary Examiner(s): Campbell; Joshua D
• Assistant Examiner(s): BRYANT, CHRISTOPHER D
• Application Number:
  US11/493,203
• Publication Number:
  US 20080028291A1
• Time in Patent Office: 1,441 Days
• Field of Search: 715/228, 715/212, 715/217, 715/240, 358/3.2
• 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 storage medium storing software that is executable on a computer or digital device to perform 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, wherein the grammatical expression is a table structure comprising a tree in which the cells are represented by leaf nodes of the tree and the structural relationships are represented by non-leaf nodes of the tree, and the parsing includes;

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 added as a leaf node and at least one element indicative of a structural relationship between the next cell and the minimum rectangular bounding box added as a non-leaf node, and

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

2. The storage medium 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 storage medium as set forth in claim 2, wherein the rewriting is configured to remove any cell crossings or containments using one or more rewrites.

4. 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;

wherein each cell of the derived spatially ordered sequence of rectangular cells is represented by two points corresponding to opposing corners of the cell, and the ordered sequence of rectangular cells employs a spatial ordering based on coordinates of the points 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, p₁, p₂, p₃, p₄ 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.

5. The method as set forth in claim 4, wherein the method is performed by a processor executing software.

6. 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;

wherein the structural relationship operators of the grammar include at least AboveLeft, AboveRight, AboveEq, LeftUpper, LeftBottom, and LeftEq, two-dimensional structural relationship operators.

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

8. The method as set forth in claim 7, wherein the method is performed by a processor executing software.

9. The method as set forth in claim 6, wherein the method is performed by a processor executing software.

10. A storage medium storing software that is executable on a computer or digital device to perform 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 table structure comprising a grammatical expression with the cells represented by terminal elements and structural relationships represented by non-terminal elements, 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.

11. The storage medium as set forth in claim 10, wherein the parsing further comprises:

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

12. The storage medium as set forth in claim 10, wherein the method further comprises:

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.

13. The storage medium as set forth in claim 10, 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.