Method for determining boundaries of words in text

• US 6,249,604 B1
• Filed: 02/14/1994
• Issued: 06/19/2001
• Est. Priority Date: 11/19/1991
• Status: Expired due to Term

• Current Assignee: Technology Licensing Corporation
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hopcroft, Michael J., Huttenlocher, Daniel P., Wayner, Peter C.
• Primary Examiner(s): Chang, Jon
• Application Number:
  US08/196,028
• Time in Patent Office: 2,682 Days
• Field of Search: 382/9, 382/10, 382/11, 382/12, 382/16, 382/27, 382/25, 382/28, 382/46, 382/31, 382/172, 382/174, 382/177, 382/181, 382/193, 382/190, 382/199, 382/203, 382/206, 382/210, 382/296, 382/229, 382/289
• US Class Current: 382/174
• 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 determining the boundaries of a symbol or word string within an image, including the steps of determining page orientation, isolating symbol strings from adjacent symbol strings, establishing a set of boundaries or references with respect to which measurements about, or further processing of, the symbol string may be made.

Claims

1. A method of isolating a word object composed of multiple adjacent symbols within data defining a first image, comprising the steps of:

(a) producing a second image, as a function of the first image, where the adjacent symbols which form the word object are represented in the second image as having at least one point of contact between one another, thereby representing the word object as a group of connected symbols;

(b) locating the connected symbols within the second image;

(c) identifying boundaries about each group of connected symbols within the second image, so as to segment the second image by word objects; and

(d) applying the boundaries identified in step (c), to the first image to group the data associated with each word object, thereby isolating the word object within the data defining the first image.

2. The method of claim 1, further comprising the step of determining a skew angle corresponding to the orientation of the word object within the data defining the first image, wherein the step of identifying boundaries about each group of connected symbols orients the boundaries with respect to the skew angle.

3. The method of claim 2, wherein the boundaries about each group of connected symbols are rectangular in shape and have two principal dimensions, further comprising the steps of:

(a) locating characteristic lines of the word object, said characteristic lines being oriented with respect to the skew angle; and

(b) removing, from the data defining the first image, extraneous marks, said extraneous marks being identified as such based upon an analysis of the principal dimensions of boundaries surrounding the extraneous marks with respect to said characteristic lines.

4. The method of claim 1, further comprising the steps of:

(a) determining a skew angle corresponding to the orientation of the word object within the data defining the first image;

(b) locating characteristic lines of the word object, said characteristic lines being oriented with respect to the skew angle; and

(c) altering the second image, by superimposing interline boundaries, based upon the locations of said characteristic lines, between respective upper and lower word objects present within the second image, thereby imposing a separation between word objects lying on adjacent text lines.

5. The method of claim 3, wherein the step of identifying the locations of characteristic lines for the word objects comprises the steps of:

(a) constructing a first line through the image, said first line being composed of a plurality of discrete points and oriented in a direction perpendicular to the orientation of the word object, as defined by the skew angle;

(b) projecting the data defining the first image onto said first line, to produce an indication of the frequency of occurrence of symbol extents within the projected data as a function of the displacement along the line; and

(c) identifying the locations of local maxima within the projected data, wherein the maxima are representative of the characteristic lines for the word objects lying along symbol lines.

6. The method of claim 3, wherein the step of identifying the locations of characteristic lines for the word objects comprises the steps of:

(a) constructing a line through the image, said line being composed of a plurality of discrete points and oriented in a direction perpendicular to the orientation of the word object, as defined by the skew angle;

(b) projecting the data defining the first image onto said line, to produce a signal representative of the frequency of the projected data as a function of the displacement along the line;

(c) identifying local maxima and minima of the signal;

(d) applying a threshold to said signal, in order to enable the classification of the local maxima and minima; and

(e) identifying text characteristic lines as those lines which exhibit local maxima above the threshold.

7. The method of claim 6, further comprising the step of identifying text toplines as those local maxima which are the first rising maxima after a falling minima.

8. The method of claim 6, further comprising the step of identifying text baselines as those local maxima which are the second rising maxima after a falling minima.

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

separating the text characteristic lines into pairs of lines, each pair representing a topline and baseline for a line of text; and

verifying the validity of the text characteristic line pairs by calculating the average separation of the text characteristic line pairs, and discarding any line pairs having a separation less than the average separation.

10. The method of claim 1, wherein the step of producing a second image, as a function of the first image, comprises the step of applying a median filter to the first image, thereby producing a second image having a blurred representation of the first image.

11. A method of determining bounding reference lines for at least one word object within data defining a first image, comprising the steps of:

(a) determining a skew angle representative of the orientation of the word object within the data defining the first image;

(b) blurring the data defining the first image, thereby producing a second image where adjacent components which make up the word object are caused to become connected to one another, the connected components consisting of a plurality of like-valued data elements having positions within the second image that adjoin one another;

(c) locating the connected components of the second image;

(d) identifying bounding reference lines about each group of connected components within the second image, so as to segment the second image by word objects, said bounding reference lines being oriented with respect to the skew angle; and

(e) applying the bounding reference lines identified in step (d), to the first image to produce bounding reference lines for the word object within the data defining the first image.

12. The method of claim 11, wherein the step of locating the connected components of the second image comprises the steps of:

(a) finding a data element, within the second image, representative of a black input regions;

(b) storing the coordinate location of the element in a queue;

(c) setting the value of the data element to a value representative of a white input region;

(d) detecting adjoining data elements, within the second image, which are also representative of black input regions;

(e) storing the coordinate locations of adjoining data elements detected in step (d) in the queue;

(f) setting the value of the data elements detected in step (d) to a value representative of a white input region;

(g) continuing the process at step (d) for each data element in the queue; and

(h) continuing the process at step (a) until all data elements within the second image have been processed.

13. The method of claim 12, wherein the step of identifying bounding reference lines about each group of connected components further comprises the steps of:

(a) retrieving the coordinate locations stored within the queue;

(b) identifying relative maxima and minima coordinate locations, thereby identifying the boundaries of the connected components; and

(c) constructing bounding reference lines through the relative maxima and minima to enclose the connected components.

14. A method of isolating at least one word object, formed from one or more adjacent symbols within data defining an image, comprising the steps of:

(a) determining a skew angle corresponding to the orientation of the word object within the data defining the image;

(b) grouping adjacent symbols to form the word object, said adjacent symbols being distinguished from other symbols represented within the image by an intercharacter spacing which is less than a predefined distance; and

(c) locating the boundaries of symbols grouped to the word object in step (b), in a coordinate system oriented with respect to the skew angle, thereby isolating the word object within the data defining the image.

15. The method of claim 14, wherein the step of grouping adjacent symbols to form the word object, includes the step of applying a median filter to the image, thereby causing all symbols separated from a neighboring symbol by a spacing smaller than the dimensions of the median filter mask to be recognized as adjacent symbols.