US6470095B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic extraction of text regions and region borders for an electronic work surface
Assignee: Xerox Corp
•
Filing: 1998-10-13
•
Granted: 2002-10-22
•
Expires: 2018-10-13
Abstract
Abstract The spatial separations between clusters of objects on the electronic work surface are analyzed to automatically generate borders, which may be used in at least two manners. The borders may become explicit editable borders within an output image. Alternatively, the borders created may be implicit ephemeral borders. According to an aspect, a method uses the sufficient stability grouping technique to determine grouping of elements in the input image array into the text lines in the output text lines array. According to another aspect, a method uses the sufficient stability grouping technique to determine the amount of vertical expansion to apply to each text line so as to create text regions in the output array which correspond to the text lines in the input text lines array. According to yet another aspect, a method takes the text regions array as input and extracts enclosure borders from the text regions. The method according to this aspect applies distance thresholding and edge labeling based upon the contents of the text lines array. According to still another aspect, a method extracts structured borders from the text regions array. The method according to this aspect applies two-dimensional projection operations based upon the contents of the text lines array. According to yet still another aspect, a method extracts freeform linear borders from the text regions array. The freeform linear borders result from a Voronoi tesselation performed upon the contents of text regions array.
Inventors
- 👤 James V. Mahoney
- 👤 Patrick Chiu
- 👤 Thomas P. Moran
- 👤 William J. van Melle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:00
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/40; G06V30/41; G06V30/414
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
72 words
A method for generating a text lines array from an input image array, the method comprising the steps of: computing a sufficient stability threshold; and for each white pixel in the input image array, setting a corresponding pixel in the text lines array to black if a horizontal distance value from the white pixel to a nearest black pixel in a same image pixel row is less than the sufficient stability threshold.
Claim 2
Independent Claim
72 words
A method for generating a text lines array from an input image array, the method comprising the steps of: computing a sufficient stability threshold; and for each white pixel in the input image array, setting a corresponding pixel in the text lines array to black if a horizontal distance value from the white pixel to a nearest black pixel in a same image pixel row is less than the sufficient stability threshold.
Claim 3
Dependent Claim
27 words
A method as in claim 1 , further comprising the steps of: filling in top and bottom concavities in the text lines array by horizontal projection operations.
Claim 4
Dependent Claim
50 words
A method as in claim 2 , wherein the filling step includes the steps of setting every white pixel in the text lines array for which its nearest neighboring black pixels to the left and right in a same text lines array pixel row belong to a same connected component.
Claim 5
Dependent Claim
30 words
A method as in claim 3 , further comprising the steps of: eliminating all connected components in the text lines array having an area less than a minimum area threshold.
Claim 6
Dependent Claim
15 words
A method as in claim 4 , wherein the minimum area threshold is ten pixels.
Claim 7
Independent Claim
65 words
A method for generating a text regions array from a text lines array, the method comprising the steps of: computing a maximum frequency stability threshold from a Voronoi tessellation point; and for each white pixel in the text lines array, setting a corresponding pixel in the text regions array to black if a vertical distance value is not greater than the maximum frequency stability threshold.
Claim 8
Independent Claim
65 words
A method for generating a text regions array from a text lines array, the method comprising the steps of: computing a maximum frequency stability threshold from a Voronoi tessellation point; and for each white pixel in the text lines array, setting a corresponding pixel in the text regions array to black if a vertical distance value is not greater than the maximum frequency stability threshold.
Claim 9
Dependent Claim
100 words
A computer readable storage medium comprising: computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for generating a text lines array from an input image array, the method comprising the steps of computing a sufficient stability threshold; and for each white pixel in the input image array, setting a corresponding pixel in the text lines array to black if a horizontal distance value from the white pixel to a nearest black pixel in a same image pixel row is less than the sufficient stability threshold.
Claim 10
Dependent Claim
100 words
A computer readable storage medium comprising: computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for generating a text lines array from an input image array, the method comprising the steps of computing a sufficient stability threshold; and for each white pixel in the input image array, setting a corresponding pixel in the text lines array to black if a horizontal distance value from the white pixel to a nearest black pixel in a same image pixel row is less than the sufficient stability threshold.
Claim 11
Dependent Claim
32 words
A computer readable storage medium as in claim 7 , the method further comprising the steps of: filling in top and bottom concavities in the text lines array by horizontal projection operations.
Claim 12
Dependent Claim
53 words
A computer readable storage medium as in claim 8 , wherein the filling step includes the steps of: setting every white pixel in the text lines array for which its nearest neighboring black pixels to the left and right in a same text lines array pixel row belong to a same connected component.
Claim 13
Dependent Claim
35 words
A computer readable storage medium as in claim 9 , the method further comprising the steps of: eliminating all connected components in the text lines array having an area less than a minimum area threshold.
Claim 14
Dependent Claim
18 words
A computer readable storage medium as in claim 10 , wherein the minimum area threshold is ten pixels.
Claim 15
Dependent Claim
93 words
A computer readable storage medium comprising: computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for generating a text regions array from a text lines array, the method comprising the steps of: computing a maximum frequency stability threshold from a Voronoi tessellation point; and for each white pixel in the text lines array, setting a corresponding pixel in the text regions array to black if a vertical distance value is not greater than the maximum frequency stability threshold.
Claim 16
Dependent Claim
93 words
A computer readable storage medium comprising: computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for generating a text regions array from a text lines array, the method comprising the steps of: computing a maximum frequency stability threshold from a Voronoi tessellation point; and for each white pixel in the text lines array, setting a corresponding pixel in the text regions array to black if a vertical distance value is not greater than the maximum frequency stability threshold.
Claim 17
Dependent Claim
41 words
The method of claim 1 , wherein the step of computing a sufficient stability threshold includes the steps of: determining a distance value from a fist pixel included in said input array to a second pixel in said input image array.
Claim 18
Dependent Claim
43 words
The method of claim 13 , wherein the first pixel at which a distance to a nearest black pixel to the left of the first pixel is equal to a distance to a nearest black pixel to the right of the first pixel.
Claim 19
Independent Claim
124 words
A method for generating an image border from an input image array having a plurality of pixels comprising the steps of: generating a text lines array having a plurality of pixels from the input image array, wherein the step of generating a text lines array includes the steps of: computing a sufficient stability threshold; and, setting, for each pixel in the input image array, a respective pixel in the text lines array to a first value, if a distance from a first pixel in the input image array to a second pixel in the input image array is less than the sufficient stability threshold; generating a text regions array from the text lines array; and, generating said image border from said text regions array.
Claim 20
Independent Claim
124 words
A method for generating an image border from an input image array having a plurality of pixels comprising the steps of: generating a text lines array having a plurality of pixels from the input image array, wherein the step of generating a text lines array includes the steps of: computing a sufficient stability threshold; and, setting, for each pixel in the input image array, a respective pixel in the text lines array to a first value, if a distance from a first pixel in the input image array to a second pixel in the input image array is less than the sufficient stability threshold; generating a text regions array from the text lines array; and, generating said image border from said text regions array.
Claim 21
Independent Claim
125 words
A method for generating an image border from an input image array having a plurality of pixels comprising the steps of: generating a text lines array having a plurality of pixels from the input image array; generating a text regions array from the text lines array, wherein the step of generating a text regions array includes the steps of: computing a maximum frequency stability threshold; and, setting, for each pixel in the text lines array, a respective pixel in the text regions array to a first value, if a distance from a first pixel in the text lines array to a second pixel in the text lines array is less that the maximum frequency stability threshold; generating said image border from said text regions array.
Claim 22
Independent Claim
125 words
A method for generating an image border from an input image array having a plurality of pixels comprising the steps of: generating a text lines array having a plurality of pixels from the input image array; generating a text regions array from the text lines array, wherein the step of generating a text regions array includes the steps of: computing a maximum frequency stability threshold; and, setting, for each pixel in the text lines array, a respective pixel in the text regions array to a first value, if a distance from a first pixel in the text lines array to a second pixel in the text lines array is less that the maximum frequency stability threshold; generating said image border from said text regions array.
References Cited (Backward Citations)
US5583949A
Cited
US5537491A
Cited
US5844991A
Cited
US5889886A
Cited
US5914718A
Cited
US5956468A
Cited
US5915039A
Cited
US6035058A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-21 | 2006-04-22 | 2006-10-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-21 | 2010-04-22 | 2010-10-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-21 | 2014-04-22 | 2014-10-22 | $7700.00 | Window Closed / Lapsed |