Identification of regions of a document

• US 8,832,549 B2
• Filed: 06/07/2009
• Issued: 09/09/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): Hong, Stephen
• Assistant Examiner(s): TSUI, WILSON W
• Application Number:
  US12/479,850
• Publication Number:
  US 20100174980A1
• Time in Patent Office: 1,920 Days
• Field of Search: 715234-236, 715243-247, 715/251, 382173-180
• US Class Current: 715/243
• 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 non-transitory machine readable medium storing a program which when executed by at least one processing unit analyzes a document that comprises a plurality of primitive elements, the primitive elements are present in the document prior to analysis by the program, the program comprising sets of instructions for:

identifying a set of potential boundaries as rectilinearly aligned graphical primitive elements that satisfy a set of size constraints;

identifying a subset of the potential boundaries as actual boundaries by eliminating from the set (i) potential boundaries identified from the graphical primitive elements that intersect with primitive elements that are not in the set of potential boundaries and (ii) potential boundaries identified from the graphical primitive elements that do not intersect at least two additional potential boundaries;

identifying regions bounded by the actual boundaries; and

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

2. The non-transitory machine 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 non-transitory machine 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 non-transitory machine 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 hierarchical document object model.

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

6. The non-transitory machine readable medium of claim 1, wherein the set of potential boundaries are identified based on locations of the graphical primitive elements in the document.

7. The non-transitory machine readable medium of claim 6, wherein the set of potential boundaries comprises straight lines or shapes that approximate straight lines.

8. The non-transitory machine readable medium of claim 1, wherein the set of instructions for identifying the regions comprises sets of instructions for traversing a subset of the actual boundaries to identify a region.

9. The non-transitory machine readable medium of claim 1, wherein the set of instructions for identifying regions bounded by the actual boundaries comprises sets of instructions for traversing the identified actual boundaries to identify closed loops of boundaries, wherein each closed loop is a region.

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

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

12. The non-transitory machine readable medium of claim 11, wherein the document is a Portable Document Format (PDF) file.

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

14. The non-transitory machine readable medium of claim 1, wherein the program is a portion of an operating system.

15. The non-transitory machine readable medium of claim 1, wherein the program is an application that runs on top of an operating system.

16. The non-transitory machine readable medium of claim 1, wherein the 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 defined based on the structural elements.

17. The non-transitory machine readable medium of claim 16, 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.

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

identifying a set of potential boundaries as (i) rectilinearly aligned graphical elements that have less than a threshold thickness in one rectilinear direction and (ii) edges of rectilinearly aligned graphical elements that satisfy size constraints, wherein graphical elements that satisfy the size constraints have at least a threshold height and width;

identifying as actual boundaries a portion of the potential boundaries identified from the rectilinearly aligned graphical elements, by eliminating from the set (i) potential boundaries that intersect with primitive elements that are not in the set of potential boundaries and (ii) the potential boundaries that do not intersect with at least two additional potential boundaries;

identifying regions bounded by the actual boundaries; and

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

19. The non-transitory machine readable medium of claim 18, wherein the threshold thickness requires that a largest dimension of an upright bounding box of a potential boundary be at least eight times a size of a smaller dimension of the upright bounding box.

20. The non-transitory machine readable medium of claim 18, wherein graphical elements that satisfy the size constraints have at least a threshold area.

21. The non-transitory machine readable medium of claim 18, wherein the set of instructions for identifying a set of potential boundaries further comprises a set of instructions for identifying as potential boundaries as rectilinearly aligned page borders of the document.

22. A method for analyzing a document that comprises a plurality of primitive elements, the method comprising:

identifying a set of potential boundaries as (i) rectilinearly aligned graphical elements that have less than a threshold thickness in one rectilinear direction and (ii) edges of rectilinearly aligned graphical elements that satisfy size constraints, wherein graphical elements that satisfy the size constraints have at least a threshold height and width;

identifying as actual boundaries a portion of the potential boundaries identified from the rectilinearly aligned graphical elements, by eliminating from the set (i) potential boundaries that intersect with primitive elements that are not in the set of potential boundaries and (ii) the potential boundaries that do not intersect with at least two additional potential boundaries;

identifying regions bounded by the actual boundaries; and

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

23. The method of claim 22, wherein the threshold thickness requires that a largest dimension of an upright bounding box of a potential boundary be at least eight times a size of a smaller dimension of the upright bounding box.

24. The method of claim 22, wherein graphical elements that satisfy the size constraints have at least a threshold area.

25. The method of claim 22, wherein identifying a set of potential boundaries further comprises identifying as potential boundaries as rectilinearly aligned page borders of the document.

26. A method for analyzing a document that comprises a plurality of primitive elements, the primitive elements are present in the document prior to analysis, the method comprising:

identifying a set of potential boundaries as rectilinearly aligned graphical primitive elements that satisfy a set of size constraints;

identifying a subset of the potential boundaries as actual boundaries by eliminating from the set (i) potential boundaries identified from the graphical primitive elements that intersect with primitive elements that are not in the set of potential boundaries and (ii) potential boundaries identified from the graphical primitive elements that do not intersect at least two additional potential boundaries;

identifying regions bounded by the actual boundaries; and

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

27. The method of claim 26, wherein defining a structured document comprises identifying a hierarchical relationship between at least two identified regions.

28. The method of claim 27, wherein a first region that is wholly within a second region is a child of the second region.

29. The method of claim 27, wherein identifying a hierarchical relationship between two identified regions comprises defining a hierarchical document object model in which each identified region is a node of the hierarchical document object model.

30. The method of claim 29, wherein defining the structured document further comprises populating the hierarchical document object model with at least one structural element defined from the primitive elements.

31. The method of claim 26, wherein the set of potential boundaries are identified based on locations of the graphical primitive elements in the document.

32. The method of claim 31, wherein the set of potential boundaries comprises straight lines or shapes that approximate straight lines.

33. The method of claim 26, wherein identifying the regions comprises traversing a subset of the actual boundaries to identify a region.

34. The method of claim 26, wherein identifying regions bounded by the actual boundaries comprises traversing the identified actual boundaries to identify closed loops of boundaries, wherein each closed loop is a region.

35. The method of claim 26, wherein the document is an unstructured document.

36. The method of claim 26 further comprising using the identified regions to define structural elements for the document, wherein the structured document is further defined based on the structural elements.

37. The method of claim 36, wherein using the identified regions to define structural elements comprises analyzing each particular region separately to create associations between sets of primitive elements in the particular region.