Identification of guides and gutters of a document

• US 8,719,701 B2
• Filed: 06/07/2009
• Issued: 05/06/2014
• 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): Hutton, Jr., Doug
• Assistant Examiner(s): MCINTOSH, ANDREW T
• Application Number:
  US12/479,847
• Publication Number:
  US 20100174978A1
• Time in Patent Office: 1,794 Days
• Field of Search: 715/249, 715/251, 715/252
• US Class Current: 715/249
• 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 words. Each word is an associated set of glyphs and each glyph has location coordinates. The method identifies clusters of words based on the location coordinates. Based on the identified clusters, the method defines a set of boundary elements for the glyphs that identify a set of borders for the glyphs. The method defines a structured document for the unstructured document based on the glyphs and the defined boundary elements. To identify clusters of words, the method orders the location coordinates and identifies several partitions of the location coordinates. Each partition specifies a particular grouping of the coordinates into subsets. For each partition, the method identifies a particular set of subsets of location values that satisfy a particular set of constraints and determines a set of subsets of location values that optimizes a particular measure.

Claims

1. A machine readable medium storing a program which when executed by at least one processing unit analyzes a document that comprises a plurality of words, each word comprising an associated set of glyphs, each glyph having location coordinates, the program comprising sets of instructions for:

identifying a group of words aligned in a first direction based on the location coordinates of a particular glyph in each of the words in the group of aligned words;

based on the identified group of aligned words, defining an alignment element for the particular glyphs at a particular location in the first direction, wherein the alignment element that indicates a particular alignment for a plurality of text lines containing the group of aligned words;

removing particular locations from the alignment element in a second direction based on an analysis of the group of aligned words, wherein each particular location of the alignment element corresponds to a particular text line; and

defining a structured document based on the glyphs and remaining locations of the defined alignment element.

2. The machine readable medium of claim 1, wherein the program further comprises a set of instructions for defining at least one region of empty space between a pair of alignment elements, wherein the structured document is further defined based on the region of empty space.

3. The machine readable medium of claim 1, wherein the set of instructions for identifying the group of aligned words comprises a set of instructions for performing cluster analysis on data derived from coordinates of the particular glyphs of the words along one axis.

4. The machine readable medium of claim 3, wherein the cluster analysis comprises density clustering in order to identify large groups of glyphs at the edges of words with similar location coordinate values in the first direction.

5. The machine readable medium of claim 1, wherein the alignment elements are right and left alignment guides for the text lines.

6. The machine readable medium of claim 1, wherein the set of instructions for defining a structured document comprises a set of instructions for identifying a column of text using the glyphs and the remaining locations of the defined alignment element.

7. The machine readable medium of claim 1, wherein the document is an unstructured document.

8. The machine readable medium of claim 1, wherein the document is a vector graphics document.

9. The machine readable medium of claim 1, wherein the document is a portable document format (PDF) document.

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

11. The machine readable medium of claim 1, wherein the set of instructions for removing particular locations from the alignment element in the second direction based on the analysis of the group of aligned words comprises a set of instructions for determining quantities of consecutive text lines with aligned words.

14. The machine readable medium of claim 1, wherein one word in the group of aligned words is in each of the plurality of text lines.

12. A method for (i) analyzing a document that comprises a plurality of words, each word comprising an associated set of glyphs, each glyph having location coordinates, and (ii) generating structural elements that define structure in said document based on said analysis, the method comprising:

defining an alignment guide for a set of words in different text lines based on the location coordinates of the glyphs at the edges of the words;

removing locations from the alignment guide based on an analysis of the words in different text lines, wherein each particular location of the alignment guide corresponds to a particular text line;

associating groups of text lines as aligned groups of text lines based on remaining locations of the alignment guide;

using the aligned groups of text lines to specify the structural elements; and

defining a structured document based on the glyphs, the aligned groups of text lines, and the structural elements.

13. The method of claim 12, wherein the analysis of the words in different text lines comprises identifying words that intersect the defined alignment guide.

15. The method of claim 12, wherein the glyphs at the edges of the words are the last glyphs in each of the words.

16. The method of claim 12, wherein the glyphs at the edges of the words are the first glyphs in each of the words.

17. A machine readable medium storing a program which when executed by at least one processing unit analyzes a document that comprises a plurality of glyphs, each glyph having location coordinates, the program comprising sets of instructions for:

identifying sets of glyphs to associate as words;

defining a potential alignment guide for a set of words in different text lines based on the location coordinates of the glyphs at the edges of the words;

identifying a plurality of alignment elements within the potential alignment guide by removing particular locations from the potential alignment guide based on an analysis of the group of vertically aligned words within each set of text lines, wherein each particular location of the potential alignment guide corresponds to a particular text line, each identified alignment element indicating a particular alignment for a set of text lines that contain a group of vertically aligned words;

using the identified alignment elements to specify additional structural elements within the document; and

defining a structured document based on the glyphs, the aligned groups of text lines, and the structural elements.

18. The machine readable medium of claim 17, wherein the program further comprises a set of instructions for defining at least one region of empty space between a pair of alignment elements.

19. The machine readable medium of claim 17, wherein the set of instructions for defining a potential alignment guide for a set of words comprises a set of instructions for performing cluster analysis on data derived from the location coordinates of the glyphs at the edges of the words along one axis.

20. The machine readable medium of claim 17, wherein the identified alignment elements are right and left alignment guides for the text lines.

21. The machine readable medium of claim 17, wherein the glyphs at the edges of the words are the last glyphs in each of the words.

22. The machine readable medium of claim 17, wherein the glyphs at the edges of the words are the first glyphs in each of the words.

23. The machine readable medium of claim 17, wherein the set of instructions for identifying alignment elements within the potential alignment guide based on the analysis of the words in the text lines comprises a set of instructions for determining whether words intersect the potential alignment guide.

24. The machine readable medium of claim 17, wherein the set of instructions for identifying alignment elements within the potential alignment guide based on the analysis of the words in the text lines comprises a set of instructions for determining quantities of consecutive text lines with words that begin in the potential alignment guide.