METHOD FOR FINDING TEXT READING ORDER IN A DOCUMENT

• US 20100198827A1
• Filed: 07/27/2005
• Published: 08/05/2010
• Est. Priority Date: 07/27/2005
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ortega, Daniel, Peiro, Jose Abad, Faraboschi, Paolo, Yacoub, Sherif
• Granted Patent: US 9,098,581 B2
• Time in Patent Office: Days
• US Class Current: 707/739
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G06F 40/30 Semantic analysis
• 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

A method for finding text reading order in a document such as a scanned newspaper or magazine includes the steps of pruning unnecessary text zones using semantic analysis (40), using text correlation measures to cluster zones (41), and then finding a reading order within each of the clusters (42).

Claims

1. A method of finding text reading order in a document, the method comprising:

(1). determining a plurality of text zones within the document;

(2). for each zone, generating a semantic measure of the text within the zone; and

(3). calculating a plurality of correlations between respective zone pairs;

the method being characterised by;

(4). clustering the zones into a plurality of clusters in dependence upon the said pairwise correlations; and

(5). determining a separate reading order for the zones within each of the respective clusters.

2. A method as claimed in claim 1 in which the semantic measure is multi-valued, and in which the correlation is determined in dependence upon the combined similarity of the respective values between a first zone of each pair and a second.

3. A method as claimed in claim 1 in which the clusters are determined by the steps of:

(a) selecting an initial zone as the start of a cluster;

(b) adding to the cluster any zone which has a pairwise correlation of greater than a cut-off value with a zone already in the cluster;

(c) repeating step (b) until no further zones are added to the cluster; and

(d) repeating steps (a) to (c) until there are no more clusters to create.

4. A method as claimed in claim 3 in which the cut-off value is user selectable.

5. A method as claimed in claim 1 including, after step (4), assigning to an existing cluster any zone which has not already been assigned to a cluster by the said clustering.

7. A method as claimed in claim 1 including the step of determining whether any two clusters have interleaving zones, and if so merging the said two clusters.

8. A method as claimed in claim 1 including the step of determining whether the zones of a given cluster, considered in order of layout flow, are interrupted by one or more zones of another cluster, and if so splitting the given cluster at the point of interruption.

9. A method as claimed in claim 1 including, after step (2), excluding unwanted zones from consideration in dependence upon their respective semantic measures.

10. A computer program comprising a series of computer-operable steps which, when run on a computer, execute a method as claimed in claim 1.

11. A computer-readable medium carrying a computer program as claimed in claim 10.

12. A sequence of electrical signals representative of a computer program as claimed in claim 10.

6. A method as claimed in 5 in which a non-clustered zone is assigned to an existing cluster based on layout proximity.