US5245674A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image processing using distance as a function of direction
Assignee: Xerox Corp
•
Filing: 1991-07-30
•
Granted: 1993-09-14
•
Expires: 2011-07-30
Abstract
Abstract Characteristics of images such as skew of lines of text or dominant typeface of characters are detected by producing distance data. Distance data is produced for each of a number of starting pixels within an image. Each starting pixel meets a criterion, such as an edge pixel or a pixel inside a connected component. Each starting pixel's distance data indicates the distance in each of a number of directions from the starting pixel to another pixel at which the image meets another criterion. For example, to detect skew of lines of text, the distance data can indicate distance from a starting pixel at an edge across white pixels to another edge. To detect dominant typeface, the distance data can indicate distance from a starting pixel at an edge or inside a connected component across black pixels to another edge. The separating angle between adjacent directions can be small enough to detect features of an appropriate size at an appropriate distance, such as features of character size at the average intercharacter spacing. The distances at each direction from all the starting pixels can be averaged to obtain a combined distance at each direction. A sufficient number of starting pixels can be used so that the combined distance is approximately the same as if every pixel in the image were a starting pixel. The combined distances at all the directions form a profile.
Inventors
- 👤 Todd A. Cass
- 👤 Daniel P. Huttenlocher
- 👤 Peter C. Wayner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:26
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/14; G06V30/146
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
205 words
A method of performing image processing on an image that includes a plurality of locations; the method comprising a plurality of choosing acts, each choosing act choosing a starting location; the plurality of choosing acts together choosing a set of starting locations that includes more than one of the locations in the plurality of locations; the method comprising, for each of the starting locations in the set, a plurality of distance obtaining acts, each distance obtaining act for a respective one of a plurality of directions; each direction's respective distance obtaining act obtaining respective distance data with respect to the starting location in the set; the direction's distance data indicating a distance in the direction from the starting location in the set to a respective other location at which the image meets a criterion; the method further comprising an act of combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction; the plurality of choosing acts together choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.
Claim 2
Independent Claim
205 words
A method of performing image processing on an image that includes a plurality of locations; the method comprising a plurality of choosing acts, each choosing act choosing a starting location; the plurality of choosing acts together choosing a set of starting locations that includes more than one of the locations in the plurality of locations; the method comprising, for each of the starting locations in the set, a plurality of distance obtaining acts, each distance obtaining act for a respective one of a plurality of directions; each direction's respective distance obtaining act obtaining respective distance data with respect to the starting location in the set; the direction's distance data indicating a distance in the direction from the starting location in the set to a respective other location at which the image meets a criterion; the method further comprising an act of combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction; the plurality of choosing acts together choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.
Claim 3
Dependent Claim
16 words
The method of claim 1 in which each of the plurality of locations is a pixel.
Claim 4
Dependent Claim
93 words
The method of claim 1 in which each distance obtaining act for each starting location in the set comprises: starting at the starting location in the image; and for each of a sequence of locations along a line extending from the starting location in the direction through the image, obtaining respective length data indicating length from the starting location to the location along the line; the sequence including the respective other location at which the image meets the criterion; the respective length data of the respective other location being the direction's distance data.
Claim 5
Dependent Claim
22 words
The method of claim 3 in which each of the plurality of locations is a pixel and the criterion is an edge.
Claim 6
Dependent Claim
55 words
The method of claim 4 in which the respective other location at which the image meets the criterion is a black pixel separated from the starting location by white pixels; the distance data indicating length across the white pixels between the starting location and the respective other location at which the image meets the criterion.
Claim 7
Dependent Claim
55 words
The method of claim 4 in which the respective other location at which the image meets the criterion is a white pixel separated from the starting location by black pixels; the distance data indicating length across the black pixels between the starting location and the respective other location at which the image meets the criterion.
Claim 8
Dependent Claim
67 words
The method of claim 1 in which the plurality of directions includes adjacent first and second directions separated by a separating angle, the separating angle being small enough that the first direction's distance data and the second direction's distance data for each of the starting locations indicate whether the image contains a blob subtending the first and second directions within a limiting distance from the starting location.
Claim 9
Dependent Claim
23 words
The method of claim 7 in which the image has an outer dimensions and the limiting distance is equal to the outer dimension.
Claim 10
Dependent Claim
28 words
The method of claim 7 in which each of the plurality of directions is separated from each adjacent direction by an angle approximately equal to the separating angle.
Claim 11
Dependent Claim
80 words
The method of claim 7 in which the image includes blobs that form text that includes characters, adjacent ones of the characters being separated by intercharacter distances; the limiting distance being approximately equal to an average of the intercharacter distances so that the first direction's distance data and the second direction's distance data for each of the starting locations indicate whether the image contains a character subtending the first and second directions within the limiting distance from the starting location.
Claim 12
Dependent Claim
36 words
The method of claim 1 in which the act of combining comprises obtaining an average of the distances indicated by the respective distance data for each direction for all of the starting locations in the set.
Claim 13
Dependent Claim
32 words
The method of claim 1 in which the plurality of choosing acts together choose the set of starting locations so that the set includes a smaller number of locations than the image.
Claim 14
Dependent Claim
33 words
The method of claim 1, further comprising an act of storing each direction's combined distance data in memory so that the direction's combined distance data is accessible using direction data indicating the direction.
Claim 15
Dependent Claim
39 words
The method of claim 1 in which the image includes lines of characters at a skew; the method further comprising an act of using the combined distance data of all the directions to obtain skew data indicating the skew.
Claim 16
Dependent Claim
39 words
The method of claim 1 in which the image includes characters having a dominant typeface; the method further comprising an act of using the combined distance data of all the directions to obtain typeface data indicating the dominant typeface.
Claim 17
Dependent Claim
54 words
The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction; the method further comprising an act of comparing the profile formed by the combined distance data with a set of model profiles of distance as a function of direction.
Claim 18
Dependent Claim
45 words
The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction; the method further comprising an act of providing the profile formed by the combined distance data to a storage medium.
Claim 19
Dependent Claim
45 words
The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction; the method further comprising an act of providing the profile formed by the combined distance data to a transmission medium.
Claim 20
Dependent Claim
194 words
An image processing machine comprising: memory; the memory storing image data defining an image that includes a plurality of locations; and a processor connected for accessing the memory; the memory further storing instruction data indicating instructions the processor can execute; the processor, in executing the instructions, choosing a set of starting locations that includes more than one of the plurality of locations in the image; the processor, in executing the instructions, using the image data to obtain, for each of a plurality of directions, respective distance data with respect to each of the starting locations in the set; each direction's distance data for each starting location indicating a distance in the direction from the starting location to a respective other location at which the image meets a criterion; the processor, in executing the instructions, combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction; the processor choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.
Claim 21
Dependent Claim
194 words
An image processing machine comprising: memory; the memory storing image data defining an image that includes a plurality of locations; and a processor connected for accessing the memory; the memory further storing instruction data indicating instructions the processor can execute; the processor, in executing the instructions, choosing a set of starting locations that includes more than one of the plurality of locations in the image; the processor, in executing the instructions, using the image data to obtain, for each of a plurality of directions, respective distance data with respect to each of the starting locations in the set; each direction's distance data for each starting location indicating a distance in the direction from the starting location to a respective other location at which the image meets a criterion; the processor, in executing the instructions, combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction; the processor choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.
Claim 22
Dependent Claim
102 words
The machine of claim 19, in which the image data include, for each location in the image, a respective data item indicating a respective value; the processor, in obtaining each direction's respective distance data for each starting location, obtaining length data indicating a length along a line from the starting location in the direction; the processor, in obtaining each direction's respective distance data for each starting location, using the length data to access the respective data item of a second location at the indicated length in the direction from the starting location to determine whether the second location's value meets the criterion.
Claim 23
Dependent Claim
43 words
The machine of claim 20 in which the processor, in obtaining each direction's respective distance data for each starting location, stores the length data when the second location's value meets the criterion; the stored length data being the distance data for the direction.
Claim 24
Dependent Claim
25 words
The machine of claim 21 in which the processor stores the length data so that it can be accessed using direction data indicating the direction.
Claim 25
Dependent Claim
36 words
The machine of claim 19 in which the processor combines the respective distance data by obtaining an average of the distances indicated by the respective distance data for each direction for all of the starting locations.
Claim 26
Dependent Claim
71 words
The machine of claim 19 in which the processor comprises a plurality of processing units, the memory comprising respective local memory for each processing unit; the image data including, for each location in the image, a respective data item indicating a respective value, each processing unit's respective local memory being for storing the respective data item of a respective location in the image; the processing units executing the instructions in parallel.
Claim 27
Dependent Claim
34 words
The machine of claim 19 in which the image includes lines of characters at a skew; the processor, in executing the instructions, using the combined distance data to obtain skew data indicating the skew.
Claim 28
Dependent Claim
34 words
The machine of claim 19 in which the image includes characters having a dominant typeface; the processor, in executing the instructions, using the combined distance data to obtain typeface data indicating the dominant typeface.
Claim 29
Dependent Claim
59 words
The machine of claim 19 in which the combined distance data for all the directions form a profile of distance as a function of direction; the memory storing a set of model profiles of distance as a function of direction, the processor, in executing the instructions, comparing the profile formed by the combined distance data with the model profiles.
Claim 30
Dependent Claim
49 words
The machine of claim 27, further comprising input means for receiving data from sources outside the machine, the processor being connected for receiving data from the input means, the processor, in executing the instructions, receiving the set of model profiles and storing the set of model profiles in memory.
Claim 31
Dependent Claim
18 words
The machine of claim 28 in which the input means is for receiving data from a storage medium.
Claim 32
Dependent Claim
18 words
The machine of claim 28 in which the input means is for receiving data from a transmission medium.
Claim 33
Dependent Claim
69 words
The machine of claim 19 in which the combined distance data for all the directions form a profile of distance as a function of direction; the machine further comprising output means for providing data to destinations outside the machine; the processor being connected for providing data to the output means, the processor, in executing the instructions, providing the profile formed by the combined distance data to the output means.
Claim 34
Dependent Claim
18 words
The machine of claim 31 in which the output means is for providing data to a storage medium.
Claim 35
Dependent Claim
18 words
The machine of claim 31 in which the output means is for providing data to a transmission medium.
References Cited (Backward Citations)
US2838602A
Cited
US2983822A
Cited
US3297989A
Cited
US4847912A
Cited
US4802230A
Cited
US4989258A
Cited
US5054094A
Cited
US5131054A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-13 | 1997-03-15 | 1997-09-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-13 | 2001-03-15 | 2001-09-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-13 | 2005-03-15 | 2005-09-14 | $7700.00 | Window Closed / Lapsed |