Identification of Compound Graphic Elements in an Unstructured Document

• US 20130185631A1
• Filed: 12/27/2012
• Published: 07/18/2013
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Levy, Michael Robert, Mansfield, Philip Andrew III
• Granted Patent: US 9,959,259 B2
• Time in Patent Office: Days
• 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 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-25. -25. (canceled)

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

receiving a document that comprises a plurality of primitive graphic elements defined separately within 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 a first value for a first primitive graphic element and a second primitive graphic element that is subsequent to the first in the drawing order; and

based on the comparison of the first value to other values calculated 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.

27. The non-transitory machine readable medium of claim 26, wherein the first value is a size value.

28. The non-transitory machine readable medium of claim 26, wherein the first value represents a size of a smallest bounding box that encompasses the first and second primitive graphic elements.

29. The non-transitory machine readable medium of claim 28, wherein the size of the smallest bounding box is calculated as a sum of a width and height of the bounding box divided by a sum of a width and height of a page containing the primitive graphic elements.

30. The non-transitory machine readable medium of claim 28, wherein the size of the smallest bounding box is calculated as an area of the bounding box divided by an area of a page containing the primitive graphic elements.

31. The non-transitory machine readable medium of claim 26, wherein the set of instructions for calculating comprises a set of instructions for calculating a different value for each pair of primitive graphic elements subsequent in the drawing order, wherein the set of instructions for defining the single structural graphic element comprises sets of instructions for:

using the calculated values for pairs of primitive graphic elements to identify clusters of primitive graphic elements as candidates for joining as compound graphic elements; and

identifying sequences of primitive graphic elements within a cluster whose bounding boxes intersect; and

joining the sequences as single graphic elements.

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

receiving a document that comprises a plurality of primitive graphic elements defined separately within the document;

based on values calculated for pairs of primitive graphic elements, defining a set of successive primitive graphic elements as a candidate compound graphic element;

using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements within the set; and

defining each particular subset having more than one primitive graphic element as a single structural graphic element within the document, the structure graphic element comprising the primitive graphic elements in the particular subset.

33. The non-transitory machine readable medium of claim 32, wherein the set of instructions for defining the set of successive primitive graphic elements comprises performing cluster analysis on the calculated values.

34. The non-transitory machine readable medium of claim 32, wherein the set of instructions for using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements comprises sets of instructions for:

selecting a first graphic element in the cluster and assigning the graphic element to a new sub-cluster;

assigning a second graphic element in the cluster to the sub-cluster when a bounding box of the second graphic element overlaps a bounding box of the sub-cluster.

35. The non-transitory machine readable medium of claim 34, wherein the set of instructions for using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements further comprises a set of instructions for assigning a third graphic element to a second sub-cluster when a bounding box of the third graphic element does not overlap the bounding box of the sub-cluster.

36. The non-transitory machine readable medium of claim 34, wherein the bounding box of the sub-cluster is an intersection of the bounding boxes of all primitive graphic elements already in the sub-cluster.

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

receiving a document that comprises a plurality of primitive graphic elements defined separately within 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 a first value for a first primitive graphic element and a second primitive graphic element that is subsequent to the first in the drawing order; and

based on the comparison of the first value to other values calculated 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.

38. The method of claim 37, wherein the first value represents a size of a smallest bounding box that encompasses the first and second primitive graphic elements.

39. The method of claim 38, wherein the size of the smallest bounding box is calculated as a sum of a width and height of the bounding box divided by a sum of a width and height of a page containing the primitive graphic elements.

40. The method of claim 38, wherein the size of the smallest bounding box is calculated as an area of the bounding box divided by an area of a page containing the primitive graphic elements.

41. The method of claim 37, wherein the calculating comprises calculating a different value for each pair of primitive graphic elements subsequent in the drawing order, wherein defining the single structural graphic element comprises:

using the calculated values for pairs of primitive graphic elements to identify clusters of primitive graphic elements as candidates for joining as compound graphic elements; and

identifying sequences of primitive graphic elements within a cluster whose bounding boxes intersect; and

joining the sequences as single graphic elements.

42. An apparatus comprising:

a set of processing units; and

a machine readable medium storing a program which when executed by at least one processing unit analyzes a document, the program comprising sets of instructions for;

receiving a document that comprises a plurality of primitive graphic elements defined separately within the document;

based on values calculated for pairs of primitive graphic elements, defining a set of successive primitive graphic elements as a candidate compound graphic element;

using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements within the set; and

defining each particular subset having more than one primitive graphic element as a single structural graphic element within the document, the structure graphic element comprising the primitive graphic elements in the particular subset.

43. The apparatus of claim 42, wherein the set of instructions for using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements comprises sets of instructions for:

selecting a first graphic element in the cluster and assigning the graphic element to a new sub-cluster;

assigning a second graphic element in the cluster to the sub-cluster when a bounding box of the second graphic element overlaps a bounding box of the sub-cluster.

44. The apparatus of claim 43, wherein the set of instructions for using bounds of the primitive graphic elements in the cluster to identify one or more subsets of primitive graphic elements further comprises a set of instructions for assigning a third graphic element to a second sub-cluster when a bounding box of the third graphic element does not overlap the bounding box of the sub-cluster.

45. The apparatus of claim 43, wherein the bounding box of the sub-cluster is an intersection of the bounding boxes of all primitive graphic elements already in the sub-cluster.

46. The apparatus of claim 42, wherein the document comprises an unstructured vector graphics document.