Identification of Regions of a Document

• US 20100174980A1
• 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,832,549 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 for analyzing a document that includes a number of primitive elements. The method identifies boundaries between sets of primitive elements and identifies regions bounded by the boundaries. The method uses the identified regions to define structural elements for the document. The method defines a structured document based on the primitive elements and the structural elements.

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 primitive elements, the computer program comprising sets of instructions for:

identifying boundaries between sets of primitive elements;

identifying regions bounded by the boundaries; and

defining a structured document based on the regions and the primitive elements.

2. 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 hierarchical relationship between at least two identified regions.

3. The computer readable medium of claim 2, wherein a first region that is wholly within a second region is a child of the second region.

4. The computer readable medium of claim 2, wherein the set of instructions for identifying a hierarchical relationship between two identified regions includes a set of instructions for defining a hierarchical document object model in which each identified region is a node of the document object model.

5. The computer readable medium of claim 4, wherein the set of instructions for defining the structured document further comprises a set of instructions for populating the document object model with at least one structural element defined from the primitive elements.

6. The computer readable medium of claim 1, wherein boundaries are identified based on locations of particular primitive elements in the document.

7. The computer readable medium of claim 6, wherein the particular primitive elements are straight lines or shapes that approximate straight lines.

8. The computer readable medium of claim 1, wherein the set of instructions for identifying the regions comprises sets of instructions for:

selecting a set of boundaries that actually border a regions based on whether the boundaries intersect other boundaries; and

traversing a subset of the boundaries to identify a region.

9. The computer readable medium of claim 1, wherein the set of instructions for identifying boundaries between sets of primitive elements comprises sets of instructions for:

identifying, as potential boundaries, primitive elements and groups of primitive elements that are straight lines or shapes that approximate straight lines;

identifying intersections between said potential boundaries; and

removing potential boundaries that do not intersect at least two other potential boundaries.

10. The computer readable medium of claim 1, wherein the set of instructions for identifying regions bounded by the boundaries comprises sets of instructions for traversing the identified boundaries to identify closed loops of boundaries, wherein each closed loop is a region.

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

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

13. The computer readable medium of claim 12, wherein the document is a Portable Document Format (PDF) file.

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

15. The computer readable medium of claim 1, wherein the computer program is a portion of an operating system.

16. The computer readable medium of claim 1, wherein the computer program is an application that runs on top of an operating system.

17. The computer readable medium of claim 1, wherein the computer program further comprises a set of instructions for using the identified regions to define structural elements for the document, wherein the structured document is further based on the structural elements.

18. The computer readable medium of claim 17, wherein the set of instructions for using the identified regions to define structural elements comprises a set of instructions for analyzing each particular region separately to create associations between sets of primitive elements in the particular region.

19. A method for defining a program for (i) analyzing a document that comprises 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 regions bounded by the boundaries;

defining a module for using the identified boundaries and regions to specify the structural elements.

20. The method of claim 21 further comprising defining a module for defining a structured document based on the regions, the primitive elements, and the structural elements.

21. The method of claim 19, wherein the document is an unstructured document.

22. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document that comprises a plurality of primitive elements, the primitive elements comprising a plurality of glyphs and a plurality of graphical elements the computer program comprising sets of instructions for:

identifying a plurality of the graphical elements as potential boundaries;

identifying a portion of the potential boundaries as actual boundaries;

traversing the actual boundaries to identify one or more zones; and

defining a hierarchical document model with the identified zones.

23. The computer readable medium of claim 22, wherein identifying a plurality of the graphical elements as potential boundaries comprises sets of instructions for:

identifying graphical elements that are vertical and horizontal straight lines of at most a particular thickness;

identifying graphical elements that approximate vertical and horizontal straight lines of at most a particular thickness; and

identifying outer edges of upright rectangular graphical elements.

24. The computer readable medium of claim 22, wherein the set of instructions for identifying a portion of the potential boundaries as actual boundaries comprises sets of instructions for:

identifying intersections between the potential boundaries; and

iteratively removing potential boundaries that do not intersect at least two other potential boundaries until all remaining potential boundaries intersect at least two other potential boundaries; and

identifying the remaining potential boundaries as actual boundaries.

25. The computer readable medium of claim 22, wherein the set of instructions for traversing the actual boundaries to identify one or more zones comprises sets of instructions for:

defining a set of directionally-aligned intervals comprising two intervals aligned in opposite directions for each of the actual boundaries;

selecting an intersection and a direction away from the intersection;

traversing the intervals in the set of intervals beginning from the selected intersection in the selected direction until returning to the selected intersection;

defining the area enclosed by the traversed intervals as a zone; and

removing the traversed intervals from the set of intervals.

26. The computer readable medium of claim 25, wherein the directionally-aligned intervals are vectors.

27. The computer readable medium of claim 25, wherein the set of instructions for traversing the actual boundaries to identify one or more zones further comprises sets of instructions for:

repeatedly, until the set of directionally-aligned intervals is empty;

selecting an intersection and a direction from the intersection;

traversing the intervals in the set of intervals beginning from the selected intersection in the selected direction until returning to the selected intersection;

defining the area enclosed by the traversed intervals as a zone; and

removing the traversed intervals from the set of intervals.

28. The computer readable medium of claim 22, further comprising defining a particular zone as an island when the particular zone is traversed in a particular direction.

29. The computer readable medium of claim 22, wherein a first zone is a parent of a second zone when the second zone is fully enclosed by the first zone.

30. The computer readable medium of claim 29, wherein the second zone is an island when the first zone and second zone do not share a boundary.

31. The computer readable medium of claim 22, wherein the computer program further comprises a set of instructions for defining structural elements based on the glyphs and the graphical elements that are not actual boundaries.

32. The computer readable medium of claim 31, wherein the computer program further comprises a set of instructions for populating a zone of the hierarchical document model with at least one structural element.

33. The computer readable medium of claim 31, wherein the computer program further comprises a set of instructions for identifying a rotation zone.

34. The computer readable medium of claim 33, wherein a rotation zone is a zone that is not aligned with a page that includes the rotation zone.

35. The computer readable medium of claim 34, wherein a zone is not aligned with a page when the zone is offset from edges of the page by at least a particular angle.