Vision-Based Document Segmentation

• US 20060106798A1
• Filed: 01/09/2006
• Published: 05/18/2006
• Est. Priority Date: 07/28/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Yu, Shipeng, Wen, Ji-Rong, Cai, Deng
• Granted Patent: US 7,613,995 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• 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]

Abstract

Vision-based document segmentation identifies one or more portions of semantic content of a document. The one or more portions are identified by identifying a plurality of visual blocks in the document, and detecting one or more separators between the visual blocks of the plurality of visual blocks. A content structure for the document is constructed based at least in part on the plurality of visual blocks and the one or more separators, and the content structure identifies the one or more portions of semantic content of the document. The content structure obtained using the vision-based document segmentation can optionally be used during document retrieval.

Claims

1. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a device, causes the one or more processors to:

receive a query including one or more search terms;

rank a plurality of blocks based on how well the plurality of blocks matches the one or more search terms, wherein each of the plurality of blocks is part of one document of a plurality of documents, and wherein each of the plurality of blocks is obtained by visual segmentation of one of the plurality of documents;

for each of the plurality of documents, rank the document based at least in part on the rankings of the blocks that are part of the document; and

return, in response to the query, an indication of the rankings of one or more of the plurality of documents.

2. One or more computer readable media as recited in claim 1, wherein the instructions that cause the one or more processors to rank the document comprise instructions that cause the one or more processors to:

identify the ranking for each block that is part of the document;

select, as the ranking for the document, the highest ranking of the identified rankings.

3. One or more computer readable media as recited in claim 1, wherein the instructions that cause the one or more processors to rank the document comprise instructions that cause the one or more processors to:

identify the ranking for each block that is part of the document;

combine the rankings for each block to generate a ranking for the document.

4. One or more computer readable media as recited in claim 1, wherein the visual segmentation of a document comprises:

identifying a plurality of visual blocks in the document;

detecting one or more separators between the visual blocks of the plurality of visual blocks; and

constructing, based at least in part on the plurality of visual blocks and the one or more separators, a content structure for the document, wherein the content structure identifies the different visual blocks as different portions of semantic content of the document, and wherein the different visual blocks are the blocks of the plurality of blocks that are part of the document.

5. One or more computer readable media as recited in claim 4, wherein the document is described by a tree structure having a plurality of nodes, and wherein identifying the plurality of visual blocks in the document comprises:

identifying a group of candidate nodes of the plurality of nodes;

for each node in the group of candidate nodes;

determining whether the node can be divided, and

if the node cannot be divided, then identifying the node as representing a visual block.

6. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a device, causes the one or more processors to:

generate first rankings for a plurality of documents based on how well the plurality of documents match search criteria;

generate second rankings for the plurality of documents by visually segmenting each of the plurality of documents; and

generate final rankings for the plurality of documents based at least in part on the second rankings.

7. One or more computer readable media as recited in claim 6, wherein the instructions that cause the one or more processors to generate final rankings comprise instructions that cause the one or more processors to use, as the final rankings, the second rankings.

8. One or more computer readable media as recited in claim 6, wherein the instructions that cause the one or more processors to generate final rankings comprise instructions that cause the one or more processors to select, as a final ranking for a document of the plurality of documents, whichever ranking of the first ranking for the document and the second ranking of the document is higher.

9. One or more computer readable media as recited in claim 6, wherein the instructions that cause the one or more processors to generate final rankings comprise instructions that cause the one or more processors to generate a final ranking for a document of the plurality of documents by averaging the first ranking of the document and the second ranking of the document.

10. One or more computer readable media as recited in claim 6, wherein the instructions that cause the one or more processors to visually segment a document comprise instructions that cause the one or more processors to:

to identify a plurality of visual blocks in the document;

detect one or more separators between the visual blocks of the plurality of visual blocks; and

construct, based at least in part on the plurality of visual blocks and the one or more separators, a content structure for the document, wherein the content structure identifies the different visual blocks as different portions of semantic content of the document.

11. One or more computer readable media as recited in claim 10, wherein the document is described by a tree structure having a plurality of nodes, and wherein the instructions that cause the one or more processors to identify the plurality of visual blocks in the document comprise instructions that cause the one or more processors to:

identify a group of candidate nodes of the plurality of nodes;

for each node in the group of candidate nodes;

determine whether the node can be divided, and

if the node cannot be divided, then identify the node as representing a visual block.

12. A method of searching a plurality of documents, the method comprising:

receiving a request to search the plurality of documents, wherein the request includes query criteria;

identifying a subset of the plurality of documents based on the query criteria;

identifying, for each of the subset of documents, a plurality of blocks by visually segmenting the document;

expanding, based on the content of the plurality of blocks, the query criteria; and

identifying a second subset of the plurality of documents based on the expanded query criteria.

13. A method as recited in claim 12, returning, in response to the request identifiers of the second subset of documents.

14. A method as recited in claim 12, ranking each document of the second subset of the plurality of documents;

and

returning, in response to the request, identifiers of the second subset of documents and an indication of the ranking of each document of the second subset of documents.

15. A method as recited in claim 12, wherein the visually segmenting the document comprises:

identifying a plurality of visual blocks in the document;

detecting one or more separators between the visual blocks of the plurality of visual blocks; and

constructing, based at least in part on the plurality of visual blocks and the one or more separators, a content structure for the document, wherein the content structure identifies the different visual blocks as different portions of semantic content of the document, and wherein the different visual blocks are the plurality of blocks for the document.

16. A method as recited in claim 15, wherein the document is described by a tree structure having a plurality of nodes, and wherein identifying the plurality of visual blocks in the document comprises:

identifying a group of candidate nodes of the plurality of nodes;

for each node in the group of candidate nodes;

determining whether the node can be divided, and

if the node cannot be divided, then identifying the node as representing a visual block.