Creation of semantic objects for providing logical structure to markup language representations of documents

• US 20070136660A1
• Filed: 12/14/2005
• Published: 06/14/2007
• Est. Priority Date: 12/14/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lopez, Rodrigo, Liu, Ming, Sedky, Khaled, Gurcan, Ahmet, McGatha, Jesse, Leese, Eric, Foehr, Oliver, Dunietz, Jerry
• Granted Patent: US 7,853,869 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• 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/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/174 Form filling; Merging

Abstract

Semantic objects are created that provide a structure for markup language representations of documents. The semantic objects include text runs that are produced from the markup language representation and that are placed into semantic blocks that group text runs according to how text is logically structured in the document being represented. The text runs of each semantic block are ordered to correspond to the logical order of the document being represented. The semantic blocks corresponding to each page of the document being represented are ordered to correspond to the logical order of the document being represented. The ordered semantic blocks including the ordered text runs are saved as a semantic object which can they be utilized to make use of the logical structure of the document being represented by the markup language.

Claims

1. A computer-implemented method of constructing an object model reflective of structure of a document, comprising:

scanning a markup language representation of the document to construct a plurality of text runs;

determining which text runs correspond to a same semantic block to thereby create at least one semantic block container;

determining the order of the text lines within each of the at least one semantic blocks;

determining the order of the at least one semantic blocks on a current page; and

saving the semantic blocks including the order of the text lines and the order of the semantic blocks on the page as the object model.

2. The computer-implemented method of claim 1, wherein determining which text runs correspond to the same semantic block comprises considering whether blank horizontal or vertical blank lines are present as specified by the markup language representation.

3. The computer-implemented method of claim 1, wherein determining which text runs correspond to the same semantic block comprises determining whether the font height of a current text run is within an allowed variation of a font height of other text runs that are within a current semantic block as specified by the markup language representation.

4. The computer-implemented method of claim 1, wherein determining which text runs correspond to the same semantic block comprises determining whether a bounding rectangle of a current text run intersects a bounding rectangle of a current semantic block as specified by the markup language representation.

5. The computer-implemented method of claim 1, further comprising post processing a collection of semantic blocks to determine whether any semantic blocks may be merged to form a single semantic block and whether any semantic blocks may be divided to form multiple semantic blocks.

6. The computer-implemented method of claim 1, wherein determining which text runs correspond to the same semantic block comprises determining whether there are any transformation matrices for a current text run and a current semantic block are the same as specified by the markup language representation.

7. The computer-implemented method of claim 1, further comprising creating a new semantic block container for a current text run when the current text turn does not correspond to any existing semantic blocks.

8. The computer-implemented method of claim 1, wherein determining the order of text lines within a semantic block comprises determining a bidi level and sorting text runs within the semantic block based on the bidi level.

9. The computer-implemented method of claim 8, wherein determining the order of the text lines within the semantic block further comprises sorting from top down as specified by the markup language representation.

10. The computer-implemented method of claim 1, wherein determining the order of the semantic blocks on a page comprises:

determining whether a current semantic block is above another semantic block and overlaps horizontally with the other semantic block as specified by the markup language representation;

if the current semantic block is above the other semantic block and overlaps horizontally with the other semantic block, then placing the current semantic block before the other semantic block;

if the current semantic block is either not above the other semantic block or does not overlap horizontally with the other semantic block, then determining whether the current block is on the left side of the other semantic block and overlaps vertically with the other semantic block; and

if the current semantic block is on the left side of the other semantic block and overlaps vertically with the other semantic block, then placing the current semantic block before the other semantic block where the current semantic block and the other semantic block are left-to-right languages and placing the current semantic block after the other semantic block where both the current semantic block and the other semantic block are right-to-left languages.

11. The computer-implemented method of claim 10, wherein determining the order of the semantic blocks on a page further comprises:

if the current semantic block is not on the left side of the other semantic block or does not overlap vertically with the other semantic block, then determining whether the first text run of the current semantic block is consecutive with the last text run of the other semantic block;

if the first text run of the current semantic block is consecutive with the last text run of the other semantic block, then ordering the current semantic block relative to the other semantic block based on the order of the markup language representation;

if the first text run of the current semantic block is not consecutive with the last text run of the other semantic block, then determining whether the vertical position of the current block is the same as that of the other block;

if the vertical position of the current semantic block is the same as that of the other block, then placing the current semantic block before the other semantic block where the current semantic block and the other semantic block are left-to-right languages and placing the current semantic block after the other semantic block where the current semantic block and the other semantic block are right-to-left languages; and

if the vertical position of the current semantic block is not the same as that of the other block, then placing the current semantic block before the other semantic block where the current semantic block is above the other semantic block as specified by the markup language representation.

12. A computer readable medium having instructions encoded there for performing acts comprising:

obtaining text runs from a markup language representation of a document;

constructing semantic block containers by determining which text runs correspond to the same semantic blocks and placing those text runs corresponding to the same semantic block into the same semantic block container;

ordering the text runs within each semantic block to match a logical order present in the document; and

ordering the semantic blocks within a page to match a logical order present in the document.

13. The computer readable medium of claim 12, wherein constructing the semantic block containers comprise determining whether a current text block corresponds to an existing semantic block and if not, then creating a new semantic block to include the current text run.

14. The computer readable medium of claim 13, wherein determining whether a current text block corresponds to an existing semantic block comprises

determining whether the current text run is separated by a horizontal or vertical line from a current semantic block;

if not, then determining whether the current text run has a font height within an allowed variation from a font height of the current semantic block;

if so, then determining whether a bounding rectangle of the current text run intersects a bounding rectangle of the current semantic block;

if so, then determining whether the current text run starts on the same horizontal location of the current semantic block and is of a width smaller than a gap on the last line of the current semantic block;

if not, then determining whether any transformation matrices applicable to the current text run are also applicable to the current semantic block; and

if so, then placing the current text run in the semantic block container corresponding to the current semantic block.

15. A computer system, comprising:

storage containing instructions for generating a semantic object and containing a markup language representation of a document;

a processor that implements the instructions to generate the semantic object, wherein implementing the instructions comprises accessing the markup language representation to produce text turns, placing the text runs in corresponding semantic blocks in accordance with a logical structure of the document, ordering the text runs within the semantic blocks in accordance with the logical structure of the document, ordering the semantic blocks to form one or more pages in accordance with the logical structure of the document, and storing the ordered semantic blocks containing the order text runs as the semantic object.

16. The computer system of claim 15, wherein the processor implements the instructions to place a text run into a semantic block by performing the following:

determining whether any transformation matrices applicable to the current text run are also applicable to the current semantic block;

if so, then determining whether the current text run is separated by a horizontal or vertical line from a current semantic block;

if not, then determining whether the current text run has a font height within an allowed variation from a font height of the current semantic block;

if so, then determining whether a bounding rectangle of the current text run intersects a bounding rectangle of the current semantic block;

if so, then placing the current text run in the semantic block container corresponding to the current semantic block.

17. The computer system of claim 16, wherein the processor implements the instructions to order the text runs within the semantic blocks by performing the following:

determining a bidi level and sorting text runs within the semantic block based on the bidi level; and

sorting from top down as specified by the markup language representation.

18. The computer system of claim 17, wherein the processor implements the instructions further to generate new semantic blocks when text runs cannot be placed in existing semantic blocks.

19. The computer system of claim 18, wherein the processor implements the instructions to order the semantic blocks by performing the following:

determining whether a current semantic block is above another semantic block and overlaps horizontally with the other semantic block as specified by the markup language representation;

if the current semantic block is above the other semantic block and overlaps horizontally with the other semantic block, then placing the current semantic block before the other semantic block;

if the current semantic block is either not above the other semantic block or does not overlap horizontally with the other semantic block, then determining whether the current block is on the left side of the other semantic block and overlaps vertically with the other semantic block; and

if the current semantic block is on the left side of the other semantic block and overlaps vertically with the other semantic block, then placing the current semantic block before the other semantic block where the current semantic block and the other semantic block are left-to-right languages and placing the current semantic block after the other semantic block where both the current semantic block and the other semantic block are right-to-left languages.

20. The computer system of claim 19, wherein the processor implements the instructions to order the semantic blocks by performing the following:

if the current semantic block is not on the left side of the other semantic block or does not overlap vertically with the other semantic block, then determining whether the first text run of the current semantic block is consecutive with the last text run of the other semantic block;

if the first text run of the current semantic block is consecutive with the last text run of the other semantic block, then ordering the current semantic block relative to the other semantic block based on the order of the markup language representation;

if the first text run of the current semantic block is not consecutive with the last text run of the other semantic block, then determining whether the vertical position of the current block is the same as that of the other block;

if the vertical position of the current semantic block is the same as that of the other block, then placing the current semantic block before the other semantic block where the current semantic block and the other semantic block are left-to-right languages and placing the current semantic block after the other semantic block where the current semantic block and the other semantic block are right-to-left languages; and

if the vertical position of the current semantic block is not the same as that of the other block, then placing the current semantic block before the other semantic block where the current semantic block is above the other semantic block as specified by the markup language representation.