Identification of tables in an unstructured document

• US 8,443,278 B2
• Filed: 06/07/2009
• Issued: 05/14/2013
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mansfield, Philip Andrew, Levy, Michael Robert
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US12/479,848
• Publication Number:
  US 20100174975A1
• Time in Patent Office: 1,437 Days
• Field of Search: 715/234, 715/243, 715/254, 715/255, 715/227
• US Class Current: 715/227
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/10 Text processing natural language analysis G06F40/20; semantic analysis G06F40/30; processing or translation of natural language G06F40/40
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/126 Character encoding
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/163 Handling of whitespace
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Some embodiments provide a method for analyzing an unstructured document that includes a number of glyphs. The method identifies boundaries between sets of glyphs. The method identifies that several of the boundaries form a table. The method defines a tabular structural element based on the table. The tabular structural element includes several cells arranged in a plurality of rows and columns, each of which includes an associated set of glyphs.

Claims

1. A non-transitory machine readable medium storing a program which when executed by at least one processing unit analyzes a document comprising a plurality of primitive elements, the program comprising sets of instructions for:

identifying regions that comprise sets of primitive elements, the regions arranged in a hierarchy such that a first region at a first level of the hierarchy comprising a first set of primitive elements encompasses a second region at a second lower level of the hierarchy comprising a second set of primitive elements, the second set of primitive elements a subset of the first set of primitive elements, the first and second regions linked in the hierarchy;

determining that a particular region at a particular level in the hierarchy does not share a border with any linked region at a higher level than the particular level and encompasses at least two additional linked regions at a lower level in the hierarchy than the particular level;

identifying the particular region as a table and the encompassed regions as cells of the table; and

defining a tabular structural element for the table, the tabular structural element comprising a plurality of cells arranged in a plurality of rows and columns, each cell comprising an associated set of primitive elements.

2. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for defining a structured document comprising a plurality of structural elements, the plurality of structural elements including the tabular structural element.

3. The non-transitory machine readable medium of claim 2, wherein the set of instructions for defining the structured document comprises a set of instructions for defining a hierarchical model of the document with the plurality of structural elements comprising nodes in the hierarchical model.

4. The non-transitory machine readable medium of claim 3, wherein the cells of the tabular structural element comprise nodes in the hierarchical model.

5. The non-transitory machine readable medium of claim 3, wherein the tabular structural element comprises a node in the hierarchical model.

6. The non-transitory machine readable medium of claim 1, wherein the particular region is a larger rectangular shape and the additional regions are a plurality of rectangular shapes contained within the larger rectangular shape.

7. The non-transitory machine readable medium of claim 1, wherein the document comprises a plurality of graphic primitive elements, wherein the set of instructions for identifying the regions comprises a set of instructions for identifying sets of borders encompassing the sets of primitive elements.

8. The non-transitory machine readable medium of claim 7, wherein the set of instructions for identifying the sets of borders comprises a set of instructions for identifying graphic primitive elements that are vertical or horizontal lines and graphic primitive elements that approximate vertical or horizontal lines.

9. The non-transitory machine readable medium of claim 1, wherein the particular region and the encompassed additional regions satisfy a particular set of characteristics indicative of a table.

10. The non-transitory machine readable medium of claim 1, wherein the particular region does not share any borders with any parent region.

11. The non-transitory machine readable medium of claim 1, wherein the particular region is an outer bound of the table.

12. The non-transitory machine readable medium of claim 1, wherein the primitive elements comprise glyphs, wherein a plurality of the identified regions are inferred based on positions of associated sets of glyphs that form the cells.

13. The non-transitory machine readable medium of claim 12, wherein the program further comprises a set of instructions for associating sets of glyphs as paragraphs, wherein the regions are inferred based on positions of the paragraphs.

14. The non-transitory machine readable medium of claim 12, wherein the set of instructions for identifying regions comprises a set of instructions for identifying at least two sets of associated glyphs that are vertically or horizontally aligned.

15. The non-transitory machine readable medium of claim 1, wherein the set of instructions for identifying the particular region as a table comprises a set of instructions for identifying sets of borders that form contiguous rectangles within the particular region.

16. The non-transitory machine readable medium of claim 15, wherein the contiguous rectangles are the cells of the tabular structural element.

17. The non-transitory machine readable medium of claim 1, wherein the document is an unstructured document.

18. The non-transitory machine readable medium of claim 1, wherein the document is a vector graphics document.

19. The non-transitory machine readable medium of claim 1, wherein the document is a portable document format (PDF) file.

20. The non-transitory machine readable medium of claim 1, wherein the program is an application for a handheld device.

21. A method for defining a program for (i) analyzing a document comprising a plurality of primitive elements and (ii) generating structural elements that define structure in said document based on said analysis, the method comprising:

defining a module for identifying regions that comprise sets of primitive elements, the regions arranged in a hierarchy such that a first parent region comprising a first set of primitive elements encompasses a second child region comprising a second set of primitive elements, the second set of primitive elements a subset of the first set of primitive elements;

defining a module for determining that a particular region (i) is rectangular, (ii) encompasses at least two additional rectangular child regions, and (iii) only shares borders with the additional rectangular child regions;

defining a module for identifying the particular region as a table and the encompassed child regions as cells of the table; and

defining a module for defining a tabular structural element based on the table, the tabular structural element comprising a plurality of cells arranged in a plurality of rows and columns, each cell comprising an associated set of primitive elements.

22. The method of claim 21, wherein the primitive elements comprise glyphs, wherein defining a module for identifying regions that comprise sets of primitive elements comprises defining a module for inferring regions based on positions of associated sets of glyphs that form the cells.

23. The method of claim 21, wherein the identified particular region shares at least one border with at least two of the additional encompassed regions.

24. A non-transitory machine readable medium storing a program which when executed by at least one processing unit analyzes a document comprising a plurality of primitive elements and generates structural elements that define structure in the document based on the analysis, the program comprising sets of instructions for:

identifying regions that comprise sets of primitive elements, the regions arranged in a hierarchy such that a first parent region comprising a first set of primitive elements encompasses a second child region comprising a second set of primitive elements, the second set of primitive elements a subset of the first set of primitive elements;

determining that a particular region (i) is rectangular, (ii) encompasses at least two additional rectangular child regions, and (iii) only shares borders with the additional rectangular child regions;

identifying the particular region as a table and the encompassed child regions as cells of the table; and

defining a tabular structural element based on the table, the tabular structural element comprising a plurality of cells arranged in a plurality of rows and columns, each cell comprising an associated set of primitive elements.

25. The non-transitory machine readable medium of claim 24, wherein the primitive elements comprise glyphs, and wherein the set of instructions for identifying regions that comprise sets of primitive elements comprises a set of instructions for inferring regions based on positions of associated sets of glyphs that form the cells.

26. The non-transitory machine readable medium of claim 24, wherein the identified particular region shares at least one border with at least two of the additional encompassed regions.