Identification of Tables in an Unstructured Document

• US 20100174975A1
• Filed: 06/07/2009
• Published: 07/08/2010
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Levy, Michael Robert, Mansfield, Philip Andrew
• Granted Patent: US 8,443,278 B2
• Time in Patent Office: Days
• 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 computer readable medium storing a computer program which when executed by at least one processor analyzes a document comprising a plurality of primitive elements, the computer program comprising sets of instructions for:

identifying boundaries between sets of primitive elements;

identifying that a plurality of the boundaries form a 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 computer readable medium of claim 1 further comprising a set of instructions for defining a structured document based on the tabular structural element.

3. The computer 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 unstructured document.

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

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

6. The computer readable medium of claim 1, wherein the set of instructions for identifying that a plurality of the boundaries form a table comprises sets of instructions for identifying (i) a set of boundaries that form a larger rectangular shape and (ii) a plurality of rectangular shapes contained within the larger rectangular shape.

7. The computer readable medium of claim 1, wherein the document comprises a plurality of graphic primitive elements, wherein the set of instructions for identifying boundaries between sets of primitive elements comprises identifying graphic primitive elements that are vertical or horizontal lines and graphic primitive elements that approximate vertical or horizontal lines.

8. The computer readable medium of claim 7, wherein the computer program further comprises a set of instructions for identifying a plurality of hierarchical regions based on said identified graphic primitive elements.

9. The computer readable medium of claim 8, wherein the set of instructions for identifying that a plurality of the boundaries form a table comprises a set of instructions for identifying a set of the hierarchical regions that satisfy a particular set of characteristics.

10. The computer readable medium of claim 9, wherein the set of instructions for identifying that a plurality of the boundaries form a table comprises a set of instructions for identifying (i) a first rectangular region that does not share any borders with a parent region and (ii) a set of at least two child regions of the first region, wherein the set of child regions entirely partitions the first region, wherein each child region in the set is rectangular.

11. The computer readable medium of claim 10, wherein the first region is an outer bound of the table and the child regions of the first region are cells of the table.

12. The computer readable medium of claim 1, wherein a plurality of the identified boundaries are inferred based on positions of the associated sets of glyphs that form the cells.

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

14. The computer readable medium of claim 12, wherein the set of instructions for identifying boundaries between sets of glyphs comprises a set of instructions for identifying at least two sets of glyphs that are vertically or horizontally aligned.

15. The computer readable medium of claim 1, wherein the set of instructions for defining a tabular structural element comprises a set of instructions for identifying sets of identified boundaries that form contiguous rectangles.

16. The computer readable medium of claim 15, wherein the contiguous rectangles are the cells of the tabular structural element.

17. The computer readable medium of claim 1, wherien the document is an unstructured document.

18. The computer readable medium of claim 1, wherein the document is a vector graphics document.

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

20. The computer readabl medium of claim 1, wherien the computer 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 boundaries between sets of primitive elements;

defining a module for identifying that a plurality of the boundaries form a 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. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document comprising a plurality of primitive elements, the computer program comprising sets of instructions for:

identifying a first set of primitive elements that comprise a table;

defining a tabular structural element for the first set of primitive elements;

identifying a second set of primitive elements that do not comprise a table;

defining a set of non-tabular structural elements for the second set of primitive elements;

defining a structured document comprising the tabular structural element and the set of non-tabular structural elements.

23. The computer readable medium of claim 22, wherein the set of instructions for defining a structured document comprises a set of instructions for defining a reading order through the structural elements, wherein the reading order flows from a first structural element from the set of structural elements to the tabular structural element to a second structural element from the set of structural elements.

24. The computer readable medium of claim 22, wherein the computer program further comprises sets of instructions for:

identifying different sets of primitive elements, wherein each of the different sets comprises a different table; and

defining different tabular structural elements for each of the different sets.

25. The computer readable medium of claim 24, wherein a first one of the different sets comprises both graphical primitive elements and glyphs while a second one of the different sets comprises only glyphs.