Identification of Guides and Gutters of a Document

• US 20100174978A1
• 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,719,701 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• 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 computer readable medium storing a computer program which when executed by at least one processor analyzes a document that comprises a plurality of words, each word comprising an associated set of glyphs, each glyph having location coordinates, the computer program comprising sets of instructions for:

identifying a group of words based on the location coordinates of the glyphs;

based on the identified cluster of words, defining a set of boundary elements for the glyphs;

defining a structured document based on the glyphs and the defined set of boundary elements.

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

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

4. The computer readable medium of claim 3, wherein the cluster analysis comprises density clustering in order to identify large groups of data with similar values.

5. The computer readable medium of claim 1, wherein the boundary elements are right and left alignment guides for glyphs.

6. The computer readable medium of claim 1, wherein the set of instructions for defining the set of boundary elements comprises sets of instructions for:

for each cluster, defining a strip along a first axis with a width based on the words in the cluster; and

eliminating the strip at coordinates along the first axis where a word crosses into the strip from a particular direction along a second axis.

7. The computer 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 defined boundary elements.

8. The computer readable medium of claim 1, wherein the document is an unstructured document.

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

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

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

12. A method for defining a program 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 a module for identifying groups of words based on the location coordinates of the glyphs;

defining a module for defining a set of boundary elements for the glyphs based on the identified clusters of words, the boundary elements identifying a set of borders for the glyphs; and

defining a module for using the identified boundary elements to specify the structural elements

13. The method of claim 12 further comprising defining a module for defining a structured document based on the glyphs the defined boundary elements, and the structural elements.

14. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document comprising a plurality of words, each word comprising a plurality of glyphs, each word having a particular location value, the computer program comprising sets of instructions for:

ordering the location values of the words;

identifying a plurality of different groupings of the location values into subsets.

for each different grouping, identifying a set of the subsets of location values that satisfy a particular set of constraints; and

determining a particular one of the sets of the subsets of location values that optimizes a particular measure; and

defining boundary elements for the glyphs based on the particular set of subsets that optimizes the particular measure.

15. The computer readable medium of claim 14, wherein the set of constraints includes a requirement that the subsets of location values have at least a particular number of values.

16. The computer readable medium of claim 14, wherein the set of constraints includes a requirement that the difference between the largest and smallest value in the subset be no more than a particular threshold.

17. The computer readable medium of claim 14, wherein the particular location values represent right edges of words, wherein the set of subsets that optimizes the particular measure is used to identify right alignment guides.

18. The computer readable medium of claim 14, wherein the particular location values represent left edges of words, wherein the set of subsets that optimizes the particular measure is used to identify left alignment guides.

19. A computer readable medium storing a computer program which when executed by at least one processor identifies clusters of data, the computer program comprising sets of instructions for:

receiving a set of data values to be clustered;

identifying a plurality of partitions of the data values, each different partition specifying a particular grouping of the data values into subsets;

for each group of subsets of data values, identifying a set of the subsets that satisfy a particular set of constraints; and

determining a set of subsets that optimizes a particular measure.

20. The computer readable medium of claim 19, wherein the data values are positions of glyphs in a document, wherein the set of subsets that optimizes a particular measure identifies alignment guides for the document.

21. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document that comprises a plurality of words, each word an associated set of glyphs, the computer program comprising sets of instructions for:

identifying a set of left alignment points and a set of right alignment points in the document;

identifying an empty space in the document between a left alignment point and a right alignment point that satisfies particular criteria; and

defining a structured document using the identified white space.

22. The computer readable medium of claim 21, wherein the set of left alignment points and the set of right alignment points comprise alignment guides determined by density clustering of words.

23. The computer readable medium of claim 21, wherein the set of instructions for identifying a white space in the document comprises sets of instructions for:

selecting a right alignment point from the set of right alignment points;

identifying a left alignment point in the set of left alignment points that is the closest left alignment point to the selected right alignment point that is right of the selected right alignment point;

defining a vertical strip between the selected right alignment point and the identified left alignment point; and

eliminating the vertical strip at coordinates where a word crosses into the strip.

24. The computer readable medium of claim 21, wherein the set of instructions for defining a structured document using the identified white space comprises sets of instructions for splitting lines of words.