Method for classifying non-running text in an image

• US 6,009,196 A
• Filed: 11/28/1995
• Issued: 12/28/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): CHANG, JON CARLTON
• Application Number:
  US08/565,181
• Time in Patent Office: 1,491 Days
• Field of Search: 382/176, 382/180, 382/224, 382/174, 382/173, 382/175, 358/462, 358/464, 707/509, 707/510, 707/517, 707/520, 707/523
• 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 for analyzing image data, and more particularly for analyzing of image data representing images containing text to partition the image into running and non-running text regions and to further classify the 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 prior to the classification of the non-running text regions. Classification of the non-running text regions is accomplished by analyzing whether the non-running text regions exhibit pronounced horizontal and/or vertical alignment of the text blocks therein. Once the analysis is complete, alignment information is used to determine the number of "rows" and "columns" so as to classify the non-running text region as text, a horizontal sequence, a vertical sequence, or a table.

Claims

1. A method comprising the steps of:

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;

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

automatically 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;

automatically regrouping at least one non-running text region of the image based upon locations of the text blocks within the non-running text region, said step of regrouping at least one non-running text reunion further comprising the sub-steps of;

determining the locations of the text blocks within the non-running text region;

grouping the text blocks within the non-running text region into horizontally and vertically aligned groups of text blocks based upon at least one common coordinate;

assigning a common identifier to all text blocks in each horizontally and vertically aligned group;

counting the number of terms in the horizontally and vertically aligned groups, where an item of a horizontally aligned group is a set of text blocks in the horizontally aligned group belonging to a single vertically aligned group, and an item of a vertically aligned group is a set of text blocks in the vertically aligned group belonging to a single horizontally aligned group; and

storing the number of items in each group in memory;

further automatically classifying a non-running text region as to the extent to which such a text region is tabularized.

2. The method of claim 1, wherein the extent to which such a text region is tabularized with respect to an initial text block is limited to classification as one of a group of classifications consisting of:

non-tabularized text;

a horizontal sequence of text;

a vertical sequence of text; and

a table having text entries therein.

3. The method of claim 1, wherein a rectangular coordinate system is employed and where vertical alignment is determined based upon a common reference x-coordinate on each of the text blocks.

4. The method of claim 3, wherein the common reference coordinate is selected from the group of locations consisting of:

a left-x position of each text block;

a center-x position of each text block; and

a right-x position of each text block.

5. The method of claim 1, wherein a rectangular coordinate system is employed and where horizontal alignment is determined based upon a common reference y-coordinate on each of the text blocks.

6. The method of claim 5, wherein the common reference ycoordinate is selected from the group of locations consisting of:

an upper-y position of each text block,

a center-y position of each text block; and

a lower-y position of each text block.

7. The method of claim 1, wherein the step of grouping the text blocks within the non-running text region comprises the steps of:

grouping the text blocks into a set of vertical groups based upon a horizontal coordinate of each text block; and

grouping the text blocks into El set of horizontal groups based upon a vertical coordinate of each text block.

8. The method of claim 7, further comprising the step of applying a filter to eliminate from the sets of vertical and horizontal groups any group that consists of a single text block.

9. The method of claim 8, wherein the step of counting the number of items in the horizontally and vertically aligned groups comprises the steps of:

counting the number of items in a horizontally aligned group having a unique vertical identifier to determine the number of items in the horizontally aligned group;

counting the number of items in a vertically aligned group having a unique horizontal identifier to determine the number of items in the vertically aligned group; and

repeating the above steps for each horizontally and vertically aligned group.

10. The method of claim 9, further comprising the steps of:

defining the number of rows in the non-running text region as a maximum number of items in any vertically aligned group within the non-running text region; and

defining the number of columns in the non-running text region as a maximum number of items in any horizontally aligned group within the non-running text region.

11. The method of claim 10, wherein the step of further classifying a non-running text region comprises the steps of:

classifying the text group as a vertical sequence if the number of columns is equal to 1;

classifying the text group as a horizontal sequence if the number of rows is equal to 1; and

otherwise classifying the text group as a table.

12. A method comprising the steps of:

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;

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;

regrouping at least one non-running text region of the image based upon locations of the text blocks within the non-running text region, where the step of regrouping the non-running text region includes the steps of

grouping the text blocks of the non-running text region using independent horizontal and vertical projection operations to produce horizontal and vertical subgroups of text blocks,

labeling pixels within the text blocks of the horizontal subgroup to reflect the number of items in the horizontal subgroup, wherein an item is a set of text blocks where each member of the set of text blocks has a common identifier associated therewith ,

labeling pixels within the text blocks of the vertical subgroup to reflect the number of items in the vertical subgroup,

determining the apparent number of rows within the non-running text region as a function of the number of items in the vertical subgroup,

determining the apparent number of columns within the non-running text region as a function of the number of items in the horizontal subgroup, and

storing the apparent number of rows and the apparent number of columns in memory;

and

further classifying a non-running text region as to the extent to which such a text region is tabularized.

13. The method of claim 12, wherein the step of grouping the text blocks of the non-running text region using independent horizontal and vertical projection operations, comprises:

allocating a first binary array for the horizontal projection operation;

setting the value of a pixel position within the first array to "1" if the pixel position corresponds to pixel within a text block;

setting the value of a pixel position within the first array to "1" if there are text block pixels both to the left and right in the same horizontal row;

identifying connected components within the first array;

characterizing the connected components as a horizontal band;

determining the horizontal subgroup to be the set of text blocks contained within the area defined by the horizontal band;

allocating a second binary array for the vertical projection operation;

setting the value of a pixel position within the second array to "1" if the pixel position corresponds to pixel within a text block;

setting the value of a pixel position within the second array to "1" if there are text block pixels both to the top and bottom in the same vertical column;

identifying connected components within the second array;

characterizing the connected components as a vertical band; and

determining the vertical subgroup to be the set of text blocks contained within the area defined by the vertical band.

14. The method of claim 13, wherein the step of labeling pixels within the text blocks of the horizontal subgroup to reflect the number of items in the horizontal subgroup comprises the steps of:

enumerating left edge pixels of the connected components within a horizontal band to produce an enumerated array of pixel labels(i);

copying the values in array(i) horizontally over the region defined by the horizontal band;

determining the mode of the values in array(i);

assigning to every pixel position in the first array associated with a text block, the mode (j) of the values in array(i) for a region defined by the text block pixel positions.

15. The method of claim 14, wherein the step of determining the apparent number of rows within the non-running text region comprises the steps of:

calculating the mode (k) for a plurality of modes (j), each mode (j) representing a vertical band within the non-running text region; and

setting the apparent number of rows equal to the mode (k).

16. The method of claim 13, wherein the step of labeling pixels within the text blocks of the vertical subgroup to reflect the number of items in the vertical subgroup comprises the steps of:

enumerating upper edge pixels of the connected components within a vertical band to produce an enumerated array of pixel labels(i);

copying the values in array(i) vertically over the region defined by the vertical band;

determining the mode of the values in array(i);

assigning to every pixel position in the first array associated with a text block, the mode of the values in array(i) for a region defined by the text block pixel positions.

17. The method of claim 16, wherein the step of determining the apparent number of columns within the non-running text region comprises the steps of:

calculating the mode (k) for a plurality of modes (j), each mode (j) representing a horizontal band within the non-running text region; and

setting the apparent number of columns equal to the mode (k).

18. 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;

automatically partitioning the text blocks, using data defining the boundaries stored in the second memory location, into text groups;

automatically 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;

automatically regrouping at least one non-running text region of the image based upon locations of the text blocks within said non-running text region; and

automatically classifying at least one text group representing a non-running text region as to the extent to which the text group is tabularized; and

wherein an item is a set of text blocks each having a common identifier associated therewith and where the step of automatically regrouping at least one non-running text region of the image based upon locations of the text blocks within said non-running text region further comprises the sub-steps of;

determining the number of items in the text region; and

classifying the text group as non-tabularized text if the number of items in the text region is equal to one.

19. The method of claim 18, wherein the text group comprises a plurality of text blocks, and where the method further comprises the steps of:

grouping the plurality of text blocks as columns;

identifying distinct columnar entries as column items and counting the number of column items;

storing the number of column items in a first memory location;

classifying the text group as a vertical sequence if the number of column items stored in the first memory location is equal to 1.

20. The method of claim 19, further comprising the steps of:

grouping the plurality of text blocks as rows;

identifying distinct row entries as row items and counting the number of row items;

storing the number of row items in a second memory location;

classifying the text group as a horizontal sequence if the number of row items stored in the second memory location is equal to 1; and

otherwise classifying the text group as a table.

21. The method of claim 20, wherein the steps of grouping the text blocks comprise the steps of:

projecting an aspect of the text blocks along an axis of the image;

identifying contiguous regions of the projection;

counting the total number of contiguous regions of the projection;

assigning to each text block or identifier associated with the contiguous region to which it was projected; and

grouping those text blocks having a common identifier.

22. The method of claim 20, wherein the steps of grouping the text blocks comprise the steps of:

identifying a first boundary location for the text blocks;

retrieving, from memory, coordinate data for the first boundary location of each text block; and

associating those text blocks having coordinate data for the first boundary location that meets a sufficient stability criterion as a group.

23. 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 executing the instructions of;

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;

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

automatically 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; and

automatically regrouping at least one non-running text region of the image based upon locations of the text blocks within said non-running text region

said step of regrouping at least one non-running text region further comprising the sub-steps of;

determining the locations of the text blocks within the non-running text region;

grouping the text blocks within the non-running text region into horizontally and vertically aligned groups of text blocks based upon at least one common coordinate;

assigning a common identifier to all text blocks in each horizontally and vertically aligned group;

counting the number of items in the horizontally and vertically aligned groups, where an item of a horizontally aligned group is a set of text blocks in the horizontally aligned group belonging to a single vertically aligned group, and an item of a vertically aligned group is a set of text blocks in the vertically aligned group belonging to a single horizontally aligned group; and

storing the number of items in each group in memory;

further classifying, automatically in response to instructions stored in said instruction memory, at least one text group representing a non-running text region as to the extent to which the non-running text group is tabularized.