Method for determining boundaries of words in text

• US 5,321,770 A
• Filed: 11/19/1991
• Issued: 06/14/1994
• 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): Moore, David K.
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US07/794,392
• Time in Patent Office: 938 Days
• Field of Search: 382/22, 382/9, 382/10, 382/12, 382/16, 382/25, 382/28
• 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 at least one word object composed of multiple adjacent symbols within data defining a first image, 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) producing a second image, as a function of the first image, where adjacent symbols which form the work object are represented as having at least one point of contact between one another, thereby representing the word object as a group of connected symbols;

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

(d) identifying boundaries about each group of connected symbols within the second image, so as to segment the second image by word objects oriented with respect to the skew angle;

(e) applying the boundaries identified in step (d), 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;

(f) 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;

(g) 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, including the steps of;

(1) counting, along a branch line extending orthogonally from the first line, the number of pixels lying within the bounds of symbols which are intersected by the branch line;

(2) counting, along the branch line extending orthogonally from the first line, the number of pixels which lie at a vertical extend of a symbol and are intersected by the branch line;

(3) calculating a ratio between the number of intersected vertical extend pixels determined in step (g)(2) and the number intersected symbol pixels determined in step (g)(1);

(4) storing the ratio calculated in step (g)(3) in a unique memory position;

(5) repeating steps (g)(1) through (g)(4) for all discrete points lying along the first line, thereby determining ratios for the first image; and

(h) identifying the locations of local maxima within the projected data, wherein the maxima are representative of characteristic lines for the word objects and are oriented with respect to the skew angle.

2. The method of claim 1, wherein the step of identifying the locations of local maxima within the projected data, includes the steps of:

(a) specifying a first threshold based upon the maximum ratio value stored in the memory;

(b) determining the coarse characteristic line locations by applying the first threshold;

(c) calculating, using the coarse characteristic line locations, a separation between the coarse characteristic lines;

(d) defining, based upon the separation calculated in step (c), a mask having a width less than the separation;

(e) sequentially applying the mask to the ratio data stored in memory, and each time denoting the location of the largest ratio value within the domain defined by the mask;

(f) specifying a second threshold based upon the number of times the most often denoted location of step (e) was identified as the largest ratio; and

(g) using the second threshold, identifying those locations along the first line having a frequency of denotation greater than the second threshold, as characteristic lines for the word objects.

3. A method of isolating at least one word object within data defining a first image, comprising the steps of:

(a) producing a second image, where adjacent symbols which form the word object have at least one point of contact between one another in order to represent the word object as a group of connected symbols, by applying a median filter to the first image including the steps of;

(1) defining a mask window about a target data element;

(2) determining the number of data elements within the window which represent black symbol regions of the first image;

(3) comparing the number determined in step (2) to a predetermined threshold value;

(4) setting the target data element to a value representative of a black input level whenever the count exceeds the threshold;

(5) repeating steps (2) through (4) for all data elements within the first image, thereby creating a blurred representation of the first image;

(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.

4. The method of claim 3, wherein the step of locating the connected symbols within the second image comprises the steps of:

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

(b) storing the coordinate location of the element at the end of 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 levels;

(e) sorting the coordinate locations of adjoining data elements detected in step (d) at the end of 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 coordinate location stored in the queue in step (e); and

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

5. The method of claim 4, wherein the step of identifying boundaries about each group of connected components within the second image comprises the steps of:

(a) upon reaching the end of the queue containing coordinate locations of a series of adjoining data elements, retrieving the coordinate locations stored within the queue; and

(b) identifying, within the retrieved coordinate locations, those coordinate locations which represent local maxima and minima coordinate locations for those coordinate locations contained within the queue, thereby identifying the boundaries of the connected components.

6. A method of isolating at least one word object within data defining a first image, 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) producing a second image, as a function of the first image, where adjacent symbols which form the work object are represented as having at least one point of contact between one another, thereby representing the word object as a group of connected symbols;

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

(d) identifying boundaries about each group of connected symbols within the second image, so as to segment the second image by word objects oriented with respect to the skew angle;

(e) applying the boundaries identified in step (d), 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;

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

(g) identifying those connected symbols having boundaries spanning two or more sets of characteristic lines; and

(h) resetting the values of all the data elements in the first image, which are within the boundaries identified in step (g), to a value representative of a white input level, thereby effectively removing any extraneous mark.

7. A method of isolating at least one word object within data defining a first image, 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) producing a second image, as a function of the first image, where adjacent symbols which form the work object are represented as having at least one point of contact between one another, thereby representing the word object as a group of connected symbols;

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

(d) identifying boundaries about each group of connected symbols within the second image, so as to segment the second image by word objects oriented with respect to the skew angle;

(e) applying the boundaries identified in step (d), 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;

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

(g) identifying those connected symbols having boundaries which enclose an area which is less than a calculated size, said calculated size being a function of the separation distance between said characteristic lines; and

(h) resetting the values of all the data elements in the first image, which are within the boundaries identified in step (g), to a value representative of a white input level, thereby effectively removing any extraneous mark.

8. A method of isolating at least one word object within data defining a first image, 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) producing a second image, as a function of the first image, where adjacent symbols which form the work object are represented as having at least one point of contact between one another, thereby representing the word object as a group of connected symbols;

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

(d) identifying boundaries, oriented with respect to the skew angle, about each group of connected symbols within the second image, so as to segment the second image by word objects;

(e) applying the boundaries identified in step (d), 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;

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

(g) identifying connected components having boundaries which extend beyond the borders of the data which defines the first image; and

(h) resetting the values of all the data elements in the first image, which are within the boundaries identified in step (g), to a value representative of a white input level, thereby effectively removing any extraneous mark.

9. 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 corresponding to the orientation of the word object within the data defining the first image;

(b) defining a mask window centered about a target data element, said mask window being oriented with respect to the skew angle;

(c) counting the number of data elements within the window which are representative of black input regions on an original document;

(d) comparing the count determined in step (c) to a predetermined threshold value;

(e) setting the target data element to a value representative of a black input level whenever the count exceeds the threshold;

(f) repeating steps (c) through (e) for all data elements within the first image, thereby blurring the data defining the first image to produce a second image where adjacent components which make up the word object are caused to become connected to one another;

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

(h) 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

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

10. In a digital representation of a document, said document originally containing one or more lines of textual information composed of a plurality of strings of adjacent symbols and extraneous marks thereon, the method of removing the extraneous marks from the digital representation of the document, comprising the steps of:

(a) determining a skew angle representative of the orientation of the text lines within the digital representation;

(b) identifying the locations of baselines and toplines for the text lines, said baselines and toplines being oriented at the skew angle;

(c) altering the digital representation to produce a blurred image, whereby the adjacent symbols within a string are caused to contact one another, thereby becoming connected components;

(d) using the locations of baselines and toplines identified in step (b) to assure the inter-line separation of the connected components present in the adjacent lines of textual information within the blurred image;

(e) locating the connected components of the blurred image;

(f) identifying bounding reference lines about each group of connected components within the blurred image, so as to segment the blurred image into word objects;

(g) superimposing the bounding reference lines identified in step (f), on the digital representation of the document to produce bounding reference lines for the word objects within the digital representation;

(h) identifying the connected components which represent the extraneous marks which were present on an original document from which the first image was produced; and

(i) resetting the values of all the data elements in the first image, which are within the boundaries of the connected components identified in step (h), to a value representative of a white input level, thereby effectively removing the extraneous marks.

11. The method of claim 10, wherein the step of identifying the connected components which represent the extraneous marks further comprises the step of reviewing each group of connected components to determine those connected components having bounding reference lines spanning at least two text lines.

12. The method of claim 10, wherein the step of identifying the connected components which represent the extraneous marks further comprises the step of locating connected components having boundaries which enclose an are which is less than a predetermined size.

13. 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 by applying a median filter, which includes the steps of;

(1) defining a mask window about a target data element within the image;

(2) determining the number of data elements within the mask window which represent symbol regions within the image;

(3) comparing the number determined in step (b)(2) to a predetermined threshold;

(4) setting the target data element to a level representative of a symbol region whenever the number exceeds the predetermined threshold;

(5) repeating steps (b)(1) through (b)(4) for all data elements within the image, thereby creating a blurred representation of the image, wherein the intercharacter gap between adjacent symbols is generally indistinguishable from the symbol regions, thus causing the adjacent symbols to become grouped as a set of connected symbols; 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.

14. The method of claim 13, wherein the step of locating the boundaries of symbols identified to the word object, includes the steps of:

(a) imposing an orthogonal coordinate system, oriented at an angle equivalent to the skew angle, upon the image; and

(b) determining, with respect to the orthogonal coordinate system, the upper, lower, left and right boundaries for the group of connected symbols.

15. The method of claim 14, further including the step of superimposing, on the image, a rectangular border about the group of connected symbols, said border being at a level distinguishable from the symbol regions, and said border passing through the previously determined upper, lower, left and right boundaries of the connected symbols.