Identification of layout and content flow of an unstructured document

• US 9,063,911 B2
• Filed: 06/07/2009
• Issued: 06/23/2015
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Levy, Michael Robert, Mansfield, Philip Andrew
• Primary Examiner(s): Padmanabhan, Kavita
• Assistant Examiner(s): MCINTOSH, ANDREW T
• Application Number:
  US12/455,866
• Publication Number:
  US 20100174985A1
• Time in Patent Office: 2,207 Days
• Field of Search: 715/249, 715/251, 715/252
• US Class Current: 1/1
• 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, each of which has a position in the unstructured document. Based on positions of the glyphs in the unstructured document, the method creates associations between different sets of glyphs in order to identify different sets of glyphs as different words. The method creates associations between different sets of words in order to identify different sets of words as different paragraphs. The method defines associations between paragraphs that are not contiguous in order to define a reading order for the paragraphs.

Claims

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

receiving a document comprising a plurality of glyphs, each glyph having a position in the document, wherein the glyphs are arranged in paragraphs and columns that are not defined in the received document;

based on positions of the glyphs in the document, creating associations between glyphs to identify different sets of glyphs as different words;

creating associations between words to identify different sets of words as different paragraphs of the received document;

generating, for a page of the document, a graph of the paragraphs on the page comprising (i) a node for each paragraph and (ii) connections between a plurality of the nodes that account for relative positions of the different paragraphs to each other according to the positions of the glyphs that are associated with the different paragraphs of the received document;

based on the connections between nodes, modifying the graph by merging sets of at least two connected nodes into single nodes, wherein each merged node represents a column of the received document; and

using the modified graph with the merged nodes to identify layouts of the received document and assign the columns to different layouts on the page.

2. The non-transitory machine readable medium of claim 1, wherein the set of instructions for creating an association between words comprises a set of instructions for identifying a set of words to associate based on (i) vertical spacing properties of the glyphs that form the words and (ii) horizontal alignment properties of the glyphs that form the words.

3. The non-transitory machine readable medium of claim 1, wherein the set of instructions for creating associations between words in order to identify different sets of words as different paragraphs comprises sets of instructions for:

creating an association between words to identify a set of words as a text line; and

creating an association between text lines to identify a set of text lines as a paragraph.

4. The non-transitory machine readable medium of claim 3, wherein the set of instructions for creating an association between words to identify a set of words as a text line comprises sets of instructions for:

identifying a set of horizontally aligned words, wherein all the words in the set have baselines within a particular threshold of each other;

splitting the set of horizontally aligned words based on the presence of at least one horizontal gap; and

creating associations between the words in each remaining set.

5. The non-transitory machine readable medium of claim 4, wherein the set of instructions for splitting the set of horizontally aligned words comprises sets of instructions for:

identifying horizontal gaps as gaps of at least a threshold width between horizontally aligned words;

identifying sets of horizontal gaps that are vertically aligned;

removing sets of horizontal gaps that do not meet a particular set of criteria; and

splitting the set of horizontally aligned words at the unremoved gaps.

6. The non-transitory machine readable medium of claim 3, wherein the set of instructions for creating an association between text lines to identify a set of text lines as a paragraph comprises sets of instructions for comparing vertical spacing properties of adjacent text lines.

7. The non-transitory machine readable medium of claim 3, wherein the set of instructions for creating an association between text lines to identify a set of text lines as a paragraph comprises sets of instructions for comparing horizontal alignment properties of adjacent text lines.

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

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

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

11. 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 glyphs, each glyph having a position in the document, the program comprising sets of instructions for:

based on the positions of the glyphs, identifying different sets of glyphs as different words;

identifying different sets of words as different paragraphs;

generating, for a plurality of paragraphs of the document, a graph of the paragraphs comprising (i) a node for each paragraph and ii) connections between the nodes that account for relative positions of the paragraphs to each other;

based on the relative positions of the paragraphs in the plurality of paragraphs, partitioning the generated graph into at least two independent graphs that are each isolated from each other, each independent graph representing a different layout on the page, wherein nodes of each independent graph are only connected to other nodes that are within the independent graph; and

assigning paragraphs of each independent graph to the different layouts based on the independent graphs.

12. The non-transitory machine readable medium of claim 11, wherein the program further comprises a set of instructions for defining a reading order through the paragraphs based on the graph, said reading order specifying a flow through at least two paragraphs that are not contiguous in the document.

13. The non-transitory machine readable medium of claim 12, wherein the program further comprises a set of instructions for using the reading order to assign the paragraphs to different layouts prior to partitioning the generated graph.

14. The non-transitory machine readable medium of claim 12, wherein the two paragraphs that are not contiguous comprise a first paragraph at the bottom of a first column and a second paragraph at the top of a second column, wherein the reading order specifies a flow from the first paragraph directly to the second paragraph.

15. The non-transitory machine readable medium of claim 12, wherein the two paragraphs that are not contiguous comprise a first paragraph at the end of a first page and a second paragraph at the start of a second page, wherein the reading order specifies a flow from the first paragraph directly to the second paragraph.

16. The non-transitory machine readable medium of claim 15, wherein the first page and the second page are not contiguous in the document.

17. The non-transitory machine readable medium of claim 11, wherein the set of instructions for identifying a particular set of glyphs as a word comprises a set of instructions for associating the glyphs.

18. A method for analyzing a document, the method comprising:

receiving a document comprising a plurality of glyphs, each glyph having a position in the document, wherein the glyphs are arranged in paragraphs and columns that are not defined in the received document;

based on positions of the glyphs in the document, creating associations between glyphs to identify different sets of glyphs as different words;

creating associations between words to identify different sets of words as different paragraphs of the received document;

generating, for a page of the document, a graph of the paragraphs on the page comprising (i) a node for each paragraph and (ii) connections between a plurality of the nodes that account for relative positions of the glyphs that are associated with the different paragraphs of the received document;

based on the connections between nodes, modifying the graph by merging sets of at least two connected nodes into single nodes, wherein each merged node represents a column of the received document; and

using the modified graph with the merged nodes to identify layouts of the received document and assign the columns to different layouts on the page.

19. The method of claim 18, further comprising, prior to using the modified graph to assign the columns to different layouts on the page, (i) identifying call-outs in the graph, wherein call-outs are text elements on a page that are meant to be read in an order independent from the rest of the text on the page, and (ii) removing the identified callouts from the graph.

20. The method of claim 18 further comprising partitioning the graph with the merged nodes.

21. The method of claim 20, wherein partitioning the graph into different layouts partitions each column into a particular layout on the page.

22. The method of claim 18 further comprising calculating a set of adjacency values for each particular paragraph that defines the particular paragraph'"'"'s relative position to a plurality of the other paragraphs, wherein calculating the set of adjacency values for a particular paragraph comprises calculating at least one of an in-order, an out-order, a left-order, and a right-order for the particular paragraph.

23. The method of claim 18, wherein the connections between the plurality of nodes indicate a flow through the paragraphs.

24. The method of claim 23, wherein merging sets of at least two connected nodes merges pairs of connected nodes when (i) a first node'"'"'s only subsequent node in the flow is a second node and (ii) the second node'"'"'s only previous node in the flow is the first node.