Method and apparatus for determining logical document structure

• US 7,392,473 B2
• Filed: 05/26/2005
• Issued: 06/24/2008
• Est. Priority Date: 05/26/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Meunier, Jean-Luc
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Stork, Kyle R
• Application Number:
  US11/137,566
• Publication Number:
  US 20060271847A1
• Time in Patent Office: 1,125 Days
• Field of Search: 715/513, 715/517, 715/523, 715/530
• US Class Current: 715/247
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

Methods are disclosed for recovering or determining logical structure of a document by assessing different combinations of vertical and horizontal cuts across a block of the document. The block is segmented using a scoring function that discards horizontal cuts in favor of vertical cuts shared among neighboring sub-blocks. The order in which the blocks and sub-blocks are segmented is then used to define the logical structure of the document, such as its reading order.

Claims

1. A method for determining a logical order of a document, comprising:

(a) assigning a page of the document to be a block having a width along a first direction and a length along a second direction perpendicular to the first direction;

the block having a plurality of layout objects arranged therein;

(b) identifying a first set of hypothetical cuts, substantially between layout object boundaries, that span the width of the block;

the first set of hypothetical cuts defining a set of sub-blocks with each sub-block having a width along the first direction and a length along the second direction;

(c) identifying a second set of hypothetical cuts, substantially between layout object boundaries, that span the length of sub-blocks in the set of sub-blocks;

(d) computing arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts;

(e) modifying cuts in the first and second sets of hypothetical cuts, using the computed arrangement criteria, to merge cuts that span two or more sub-blocks along the second direction by removing one cut in the first set of hypothetical cuts and combining two cuts in the second set of hypothetical cuts; and

(f) determining the logical order of the document using cuts between layout objects in the block remaining in the first and second sets of hypothetical cuts after performing (e).

2. The method according to claim 1, further comprising:

(g) segmenting the layout objects in the block using the cuts remaining in the first and second set of hypothetical cuts after performing (e) to define a set of blocks;

(h) repeating (b)-(e) for each block in the set of blocks defined at (g).

3. The method according to claim 2, wherein said identifying at (b) and (c) use thresholds for assessing whether potential cuts meet a first predefined minimum size.

4. The method according to claim 3, further comprising:

(i) reducing one of more of the thresholds used at (b) and (c) for assessing whether potential cuts meet a second predefined minimum size; and

(j) repeating (a)-(h).

5. The method according to claim 1, wherein each of the plurality of layout objects has one of a plurality of types of content.

6. The method according to claim 5, wherein the plurality of types includes textual content and image content.

7. The method according to claim 1, further comprising modifying cuts in the first or second sets of hypothetical cuts by:

(i) grouping cuts in the second set of hypothetical cuts that span two or more sub-blocks in the set of sub-blocks along the first direction, and (ii) eliminating cuts in the first set of hypothetical cuts that divide a span between two or more sub-blocks along the second direction.

8. The method according to claim 7, further comprising modifying cuts in the second set of hypothetical cuts by (iii) eliminating cuts in the second set of cuts that indicate logical groupings of layout objects along the first direction.

9. The method according to claim 1, wherein computing arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts further comprises computing inverse of distance between layout objects that form blocks from cuts along the second direction that may be merged.

10. The method according to claim 1, further comprising processing the document to tag the layout objects as being one of a plurality of types of content.

11. The method according to claim 10, wherein said processing tags the layout objects as being textual content or image content, or both.

12. The method according to claim 1, wherein the logical order is used for arranging textual content for audible playback.

13. The method according to claim 1, wherein the logical order is used for arranging scaled content for a display.

14. The method according to claim 1, wherein dynamic programming is used to compute the arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts.

15. The method according to claim 1, wherein computing arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts further comprises assessing one or a combination of:

cumulative height of a block created by merging vertical cuts;

vertical alignment of merged cuts;

width of columns created by cuts; and

proximity of sub-blocks to be merged with each other.

16. An apparatus for determining a logical order of a document, comprising:

a memory for storing processing instructions of the apparatus; and

a processor coupled to the memory for executing the processing instructions of the apparatus;

the processor in executing the processing instructions;

(a) assigning a page of the document to be a block having a width along a first direction and a length along a second direction perpendicular to the first direction;

the block having a plurality of layout objects arranged therein;

(b) identifying a first set of hypothetical cuts, substantially between layout object boundaries, that only span the entire width of the block, wherein any hypothetical cut in the first direction that is less than the entire width of the block is excluded;

the first set of hypothetical cuts defining a set of sub-blocks with each sub-block having a width along the first direction and a length along the second direction;

(c) identifying a second set of hypothetical cuts, substantially between layout object boundaries, that span the length of sub-blocks in the set of sub-blocks;

(d) computing arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts;

(e) modifying cuts in the first and second sets of hypothetical cuts, using the computed arrangement criteria, to merge cuts that span two or more sub-blocks along the second direction;

(f) determining the logical order of the document using cuts between layout objects in the block remaining in the first and second sets of hypothetical cuts after performing (e).

17. The apparatus according to claim 16, wherein the processor in executing said processing instructions further comprises:

(g) segmenting the layout objects in the block using the cuts remaining in the first and second set of hypothetical cuts after performing (e) to define a set of blocks;

(h) repeating (b)-(e) for each block in the set of blocks defined at (g).

18. The apparatus according to claim 17, wherein said identifying at (b) and (c) use thresholds for assessing whether potential cuts meet a first predefined minimum size.

19. The apparatus according to claim 18, further comprising:

(i) reducing one or more of the thresholds used at (b) and (c) for assessing whether potential cuts meet a second predefined minimum size; and

(j) repeating (a)-(h).

20. The apparatus according to claim 16, wherein the processor in executing said processing instructions further comprises modifying cuts in the first or second sets of hypothetical cuts by:

(i) grouping cuts in the second set of hypothetical cuts that span two or more sub-blocks in the set of sub-blocks along the first direction, and (ii) eliminating cuts in the first set of hypothetical cuts that divide a span between two or more sub-blocks along the second direction.

21. The apparatus according to claim 20, wherein the processor in executing said processing instructions further comprises modifying cuts in the second set of hypothetical cuts by (iii) eliminating cuts in the second set of cuts that indicate logical groupings of layout objects along the first direction.

22. The apparatus according to claim 16, wherein the processor in executing said processing instructions to compute arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts further comprises assessing one or a combination of:

cumulative height of a block created by merging vertical cuts;

vertical alignment of merged cuts;

width of columns created by cuts; and

proximity of sub-blocks to be merged with each other.

23. An article of manufacture for determining a logical order of a document, the article of manufacture comprising computer usable media including computer readable instructions embedded therein that causes a computer to perform a method wherein the method comprises:

(a) assigning a page of the document to be a block having a width along a first direction and a length along a second direction perpendicular to the first direction;

the block having a plurality of layout objects arranged therein;

(b) identifying a first set of hypothetical cuts, substantially between layout object boundaries, that span the width of the block;

the first set of hypothetical cuts defining a set of sub-blocks with each sub-block having a width along the first direction and a length along the second direction;

(c) identifying a second set of hypothetical cuts, substantially between layout object boundaries, that span the length of sub-blocks in the set of sub-blocks;

(d) computing arrangement criteria of layout objects ordered according to the first and the second sets of hypothetical cuts;

(e) modifying cuts in the first and second sets of hypothetical cuts, using the computed arrangement criteria, to merge cuts that span two or more sub-blocks along the second direction by removing one cut in the first set of hypothetical cuts and combining two cuts in the second set of hypothetical cuts; and

(f) determining the logical order of the document using cuts between layout objects in the block remaining in the first and second sets of hypothetical cuts after performing (e).