Method and apparatus for detecting running text in an image

• US 5,889,886 A
• Filed: 11/28/1995
• Issued: 03/30/1999
• Est. Priority Date: 11/28/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mahoney, James V.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/563,479
• Time in Patent Office: 1,218 Days
• Field of Search: 382/173, 382/176, 382/180, 382/229, 358/462, 358/464, 358/467
• US Class Current: 382/176
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

The present invention is a method and apparatus for analyzing image data, and more particularly for analyzing image data representing images containing text to partition the image into running and non-running text regions therein. The present invention utilizes characteristics of running text regions to identify such regions and to subsequently group all non-running text regions into related groups.

Claims

1. A method comprising:

retrieving an input image, the image comprising an array of image signals and associated data defining a set of boundaries of a plurality of text-blocks represented therein, and storing the array of image signals in a bitmap array and the data defining the set of boundaries in a second array;

partitioning the text-blocks defined by the set of boundaries stored in the second array into text groups, wherein the partitioning step further comprises the steps of,

applying a similarity grouping criterion to the text-blocks to identify a stable number of text groups in the input image, wherein the similarity grouping criterion is a sufficient stability criterion that is based upon the width of the text blocks along a raste,r and

dividing the input image into the stable number of text groups; and

classifying the text-groups to determine those text-groups which represent running text regions of the image and those which represent non-running text regions of the image.

2. The method of claim 1, wherein the partitioning step further comprises the step of enforcing spatial contiguity between the text-blocks assigned to each one of the stable number of text groups.

3. The method of claim 1, wherein the stable number of text groups is determined in accordance with a method comprising the steps of:

obtaining data defining a third array, the array comprising values wherein each value in the third array represents a text-block width;

using the third array of values to obtain difference data, the difference data representing any difference in the values represented in the third array, and storing the difference data in the fourth array as values;

using the difference data stored in the fourth array, determining a similarity threshold τ

, where τ

is equal to the first value for which a predefined in incremental change does not affect the number of groups; and

applying the similarity threshold to the difference data of the fourth array to group the text blocks according to a similarity in the width of the text blocks.

4. The method of claim 1, wherein the partitioning step comprises the steps of:

applying a unique label to each text group;

evaluating an adjacency criterion for each pixel in the image;

based upon the determined adjacency criterion, determining new boundaries between different regions in the image; and

regrouping a text block in at least one group in accordance with the new boundaries.

5. A method comprising:

retrieving an input image, the image comprising an array of image signals and associated data defining a set of boundaries of a plurality of text-blocks represented therein, and storing the array of image signals in a bitmap array and the data defining the set of boundaries in a second array;

partitioning the text-blocks defined by the set of boundaries stored in the second array into text groups; and

classifying the text-groups to determine those text-groups which represent running text regions of the image and those which represent non-running text regions of the image, wherein the step of classifying the text groups further comprises the steps of,

(a) classifying those text groups having a group-width to page-width ratio greater than a first threshold as running text and all other groups as non-running text,

(b) identifying the text groups according to the classification in step (a),

(c) classifying the remaining running text groups having a gap-area to block-area ratio greater than a second threshold as running text and all other remaining running text groups as non-running text, and

(d) identifying the groups according to the classifications of step (a) and step (c).

6. The method of claim 5, wherein the step of classifying the text groups further comprises the steps of:

defining non-running text groups based upon an adjacency criterion;

splitting a first text group by extending the horizontal extent of an adjacent running text group so as to form at least two non-running text groups from the first text group; and

merging running text groups that are at least partially nested into non-running text groups adjacent thereto.

7. A method operating on a programmable computer for partitioning a an image containing text into regions of running text and non-running text, the image consisting essentially of an array of image signals and associated data defining a set of boundaries of a plurality of text-blocks represented therein, said method comprising the steps of:

retrieving an input image and storing image signals thereof in a first bitmap array memory location and the data defining the set of boundaries in a second memory location;

partitioning the text-blocks defined by the boundaries stored in the second memory location into text groups wherein the partitioning step further comprises the steps of

applying a similarity grouping criterion to the text-blocks to identify a stable number of text groups, wherein the similarity grouping criterion is a sufficient stability criterion that is based upon a dimension of the text blocks, and

dividing the input image into the stable number of text groups; and

classifying the text groups to determine those text groups which represent running text regions of the image and those which represent non-running text regions of the image.

8. The method of claim 7, wherein the partitioning step further comprises the step of enforcing spatial contiguity between the text-blocks assigned to each one of the stable number of text groups.

9. The method of claim 7, wherein the stable number of groups is determined in accordance with a method comprising the steps of:

obtaining data defining an initial array of values, each value representing a text-block width;

using the initial array of values to obtain difference data for a second array, said second array having values stored therein representing the difference in the values represented in the initial array;

using the difference data stored in the second array, determining a similarity threshold τ

, where τ

is equal to the first value for which a predefined incremental change does not affect the number of groups; and

applying the similarity threshold to the difference data of the second array to group the text blocks according to similarity in the width of the text blocks.

10. The method of claim 7, wherein the partitioning step comprises the steps of:

applying a unique label to each text group;

evaluating an adjacency criterion for each pixel in the image;

based upon the determined adjacency criterion, determining new boundaries between different regions in the image; and

regrouping a text block in at least one group in accordance with the new boundaries.

11. A method operating on a programmable computer for partitioning an image containing text into regions of running text and non-running text, the image consisting essentially of an array of image signals and associated data defining a set of boundaries of a plurality of text-blocks represented therein, said method comprising the steps of:

retrieving an input image and storing image signals thereof in a first bitmap array memory location and the data defining the set of boundaries in a second memory location;

partitioning the text-blocks defined by the boundaries stored in the second memory location into text groups; and

classifying the text groups to determine those text groups which represent running text regions of the image and those which represent non-running text regions of the image wherein the step of classifying the text groups further comprises the substeps of

(a) classifying those text groups having a group-width to page-width ratio greater than a first threshold as running text and all other groups as non-running text,

(b) identifying the text groups according to the classification in step (a),

(c) classifying the remaining running text groups having a gap-area to block-area ratio greater than a second threshold as running text and all other groups as non-running text, and

(d) identifying the groups according to the classifications of substep (a) and substep (c).

12. The method of claim 11, wherein the step of classifying the text groups further comprises the steps of:

defining non-running text groups based upon an adjacency criterion;

splitting a first text group by extending the horizontal extent of an adjacent running text group so as to form at least two non-running text groups from the first text group; and

merging running text groups that are at least partially nested into non-running text groups adjacent thereto.

13. An apparatus, comprising:

a first memory for storing image data;

a second memory for storing data representing characteristics of an image, the bitmap data for said image being stored in said first memory array;

instruction memory;

a text processor, connected to said first and second memory and said instruction memory for accessing the data stored in the first and second memory in accordance with instructions stored in said instruction memory, the processor in executing the instructions;

accessing the image data stored in the first memory location to produce text block boundaries representing text blocks in the image, the data defining the text block boundaries being stored in the second memory as image characteristic data;

partitioning the text-blocks defined by the boundaries stored in the second memory location into text groups; and

classifying the text-groups to determine those text-groups which represent running text regions of the image and those which represent non-running text regions of the image, wherein

the text processor, operating in accordance with a partitioning instruction,

applies a similarity grouping criterion to the text blocks to identify a stable number of text groups in the input image stored in said first memory, wherein the similarity grouping criterion is a sufficient stability criterion that is based upon a dimension of the text blocks, and

divides the input image into the stable number of text groups, wherein data characterizing boundaries of the text groups is stored in said second memory.

14. The apparatus of claim 13, wherein the similarity grouping criterion is stored in said instruction memory as code representing a sufficient stability criterion that is based upon a width of the text blocks along a raster direction.