Identification of compound graphic elements in an unstructured document

• US 8,365,072 B2
• Filed: 06/07/2009
• Issued: 01/29/2013
• 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,844
• Publication Number:
  US 20100174982A1
• Time in Patent Office: 1,332 Days
• Field of Search: 715/276, 715/243, 715/277
• US Class Current: 715/273
• 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 of analyzing an unstructured document. The method receiving the unstructured document that includes a number of primitive graphic elements, each of which is defined as a single object in the unstructured document. The unstructured document has a drawing order that indicates the order in which the primitive graphic elements are drawn when the unstructured document is displayed. The method identifies positional relationships between successive primitive graphic elements in the drawing order. Based on the positional relationships, the method defines a single structural graphic element from several of the primitive graphic elements.

Claims

1. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document, the computer program comprising sets of instructions for:

receiving a document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the document having a drawing order that indicates the order in which the primitive graphic elements are drawn when the document is displayed;

calculating, for a first primitive graphic element and a second primitive graphic element that is subsequent to the first in the drawing order, a size of a single element that comprises the first and second primitive graphic elements; and

based on the size of the single element compared to a plurality of different size calculations for additional primitive graphic elements that are subsequent in the drawing order, defining a single structural graphic element within the document from the first and second primitive graphic elements.

2. The computer readable medium of claim 1, wherein the document further comprises a plurality of glyphs, wherein the drawing order does not indicate the order in which the glyphs are drawn on the page.

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

4. The computer readable medium of claim 1, wherein the document is a vector graphics document, wherein the primitive graphic elements are vector graphics.

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

6. The computer readable medium of claim 1, wherein the size is proportional to the area of an upright bounding box that envelops the first and second primitive graphic elements.

7. The computer readable medium of claim 1, wherein the size is proportional to the sum of the length and height of an upright bounding box that envelops the first and second primitive graphic elements.

8. The computer readable medium of claim 1, wherein the single element is a first single element, wherein the set of instructions for calculating a size of the first single element that comprises the first and second primitive graphic elements is further for calculating, for the second primitive graphic element and a third primitive graphic element that is subsequent to the second in the drawing order, a size of a second single element that comprises the second and third primitive graphic elements, wherein the computer program further comprises a set of instructions for comparing the size of the first single element comprising the first and second primitive graphic elements to the size of the second single element comprising the second and third graphic elements.

9. The computer readable medium of claim 1, wherein the set of instructions for calculating a size of a single element that comprises the first and second primitive graphic elements comprises sets of instructions for calculating a spread value for the first and second primitive graphic elements.

10. The computer readable medium of claim 9, wherein the spread value describes the size and proximity of the two primitive graphic elements.

11. The computer readable medium of claim 9, wherein the set of instructions for defining a single structural graphic element within the document from the first and second primitive graphic elements comprises sets of instructions for:

identifying a cluster of primitive graphic elements that are near each other based on the calculated spread values, wherein within the cluster all of the primitive graphic elements are consecutive in the drawing order;

identifying sub-groups of consecutive primitive graphic elements in the cluster that satisfy a particular set of constraints; and

for each sub-group, defining a structural graphic element comprising all of the primitive graphic elements in the sub-group.

12. The computer readable medium of claim 11, wherein the set of instructions for identifying the cluster of primitive graphic elements comprises a set of instructions for performing difference clustering on the primitive graphic elements with the calculated spread values as first-order differences.

13. The computer readable medium of claim 11, wherein the particular set of constraints comprises a requirement that bounds for each particular primitive element in the sub-group intersect collective bounds for all primitive elements in the sub-group previous to the particular primitive element in the drawing order.

14. The computer readable medium of claim 13, wherein the bounds for each primitive element is a smallest upright bounding box that includes the primitive element.

15. The computer readable medium of claim 13, wherein the bounds for each primitive element is a smallest-area path that completely encloses the primitive element.

16. The computer readable medium of claim 1, wherein the set of instructions for defining the single structural graphic element within the document from the first and second primitive graphic elements comprises a set of instructions for creating at least one association between the first and second primitive graphic elements that are used to define the structural graphic element.

17. The computer readable medium of claim 1, wherein the computer program further comprises a set of instructions for defining a structured document based on the structural graphic element.

18. The computer readable medium of claim 17, wherein the structured document comprises a hierarchical model of the document comprising a plurality of nodes, wherein one of the nodes is populated by the structural graphic element.

28. The computer readable medium of claim 1, wherein the single structural graphic element is a first single structural graphic element, the set of instructions for defining the first single structural graphic element is further for defining a second single structural graphic element from a third and a fourth primitive graphic element, and the first and second single structural graphic elements are defined as separate objects within the document.

19. A method for analyzing a document and generating structural elements that define structure in the document based on the analysis, the method comprising:

calculating relative positional values for successive primitive graphic elements in a drawing order of a document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the drawing order indicating the order in which the primitive graphic elements are drawn when the document is displayed;

identifying groups of the calculated relative positional values by ordering the relative positional values and calculating differences between the ordered values; and

based on the identified groups of relative positional values, defining clusters of primitive graphic elements to associate as structural graphic elements, wherein the relative positional values for pairs of elements within the same cluster of primitive graphic elements are relatively smaller than the relative positional values between pairs of primitive graphic elements in different clusters.

20. The method of claim 19 further comprising defining a structured document that includes the structural graphic elements.

21. The method of claim 20, wherein the structured document comprises a hierarchical model of the document comprising a plurality of nodes, wherein one of the nodes is populated by a particular structural graphic element.

39. The machine readable medium of claim 20, wherein the structured document comprises a hierarchical model of the document comprising a plurality of nodes, wherein one of the nodes is populated by a particular structural graphic element.

22. A computer readable medium storing a computer program which when executed by at least one processor analyzes a document, the computer program comprising sets of instructions for:

receiving the document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the document having a drawing order that indicates the order in which the primitive graphic elements are drawn when the unstructured document is displayed;

calculating relative positional values for each pair of successive primitive graphic elements in the drawing order, wherein the calculated relative positional values relate to a size of the primitive graphic elements in the pair;

based on the calculated relative positional values, defining a cluster of successive primitive graphic elements;

identifying a set of sub-clusters of primitive graphic elements in the cluster that satisfy particular constraints; and

defining each particular sub-cluster as a single structural graphic element within the document comprising the primitive graphic elements in the particular sub-cluster.

23. The computer readable medium of claim 22, wherein the calculated relative positional values further relate to the proximity to each other of the primitive graphic elements in the pair.

24. The computer readable medium of claim 22, wherein the document is an unstructured document.

25. The computer readable medium of claim 22, wherein the particular constraints require that the primitive graphic elements of the identified sub-clusters intersect.

26. The computer readable medium of claim 25, wherein two primitive graphic elements intersect when smallest upright bounding boxes of the two primitive graphic elements overlap.

27. The computer readable medium of claim 22, wherein the particular constraints require that the primitive graphic elements of an identified sub-cluster meet density constraints.

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

receiving a document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the document having a drawing order that indicates the order in which the primitive graphic elements are drawn when the document is displayed;

calculating, for a first primitive graphic element and a second primitive graphic element that is subsequent to the first in the drawing order, a size of a single element that comprises the first and second primitive graphic elements; and

based on the size of the single element compared to a plurality of different size calculations for additional primitive graphic elements that are subsequent in the drawing order, defining a single structural graphic element within the document from the first and second primitive graphic elements.

30. The method of claim 29, wherein the size is proportional to the area of an upright bounding box that envelops the first and second primitive graphic elements.

31. The method of claim 29, wherein calculating a size of a single element that comprises the first and second primitive graphic elements comprises calculating a spread value for the first and second primitive graphic elements.

32. The method of claim 29, wherein defining the single structural graphic element within the document from the first and second primitive graphic elements comprises creating at least one association between the first and second primitive graphic elements that are used to define the structural graphic element.

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

receiving the document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the document having a drawing order that indicates the order in which the primitive graphic elements are drawn when the unstructured document is displayed;

calculating relative positional values for each pair of successive primitive graphic elements in the drawing order, wherein the calculated relative positional values relate to a size of the primitive graphic elements in the pair;

based on the calculated relative positional values, defining a cluster of successive primitive graphic elements;

identifying a set of sub-clusters of primitive graphic elements in the cluster that satisfy particular constraints; and

defining each particular sub-cluster as a single structural graphic element within the document comprising the primitive graphic elements in the particular sub-cluster.

34. The method of claim 33, wherein the calculated relative positional values further relate to the proximity to each other of the primitive graphic elements in the pair.

35. The method of claim 33, wherein the particular constraints require that the primitive graphic elements of the identified sub-clusters intersect.

36. The method of claim 33, wherein the particular constraints require that the primitive graphic elements of an identified sub-cluster meet density constraints.

37. A machine readable medium storing a program which when executed by at least one processing unit analyzes a document and generates structural elements that define structure in the document based on the analysis, the program comprising sets of instructions for:

calculating relative positional values for successive primitive graphic elements in a drawing order of a document that comprises a plurality of primitive graphic elements, each primitive graphic element defined as a single object in the document, the drawing order indicating the order in which the primitive graphic elements are drawn when the document is displayed;

identifying groups of the calculated relative positional values by ordering the relative positional values and calculating differences between the ordered values; and

based on the identified groups of relative positional values, defining clusters of primitive graphic elements to associate as structural graphic elements, wherein the relative positional values for pairs of elements within the same cluster of primitive graphic elements are relatively smaller than the relative positional values between pairs of primitive graphic elements in different clusters.

38. The machine readable medium of claim 37, wherein the program further comprises a set of instructions for defining a structured document that includes the structural graphic elements.