US5261012A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for thinning images
Assignee: F Poszat HU LLC
•
Filing: 1992-05-11
•
Granted: 1993-11-09
•
Expires: 2012-05-11
Abstract
Abstract Image data is subjected to a thinning process so as to derive a medial axis for each image. Boolean image data is reduced to lines and/or dots, each line generally being a centroid line of an image. The thinning process uses a change look-up table which is addressed using values from pixels in the neighborhood of a particular pixel which is the target for possible change. Pixels in the neighborhood which are to be evaluated are given a weight by use of a weight look-up table and the weight of the pixel is multiplied by the value of the pixel. Alternately, the weight of the pixel may be added to the pixel value. The pixels in the neighborhood of a target pixel (i.e., pixel which is being evaluated for possible removal) have their weights and values taken into account by a summation of the results of the multiplication (or addition) performed for each pixel so as to provide an address used to address a change look-up table which supplies an output indicative of change in the target pixel. The thinning is accomplished by a floating point processor using a pipelined procedure.
Inventors
- 👤 Robert M. Hardy
- 👤 James E. Wheeler
- 👤 John R. Meckley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 00:48
CPC Classifications
G; G06; G06T; G06T5/00; G06T5/20; G06T5/30; G06V; G06V10/00; G06V10/20; G06V10/34
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
422 words
A method of thinning images, in an image data processing system, comprising the steps of, for a line direction initially extending in a first direction: (a) scanning image data in an image memory in a scan pattern line by line, each line extending in said line direction, in order to determine whether pixels of image data in the lines should be changed in order to thin images in the image data; (b) selecting, by way of the scanning, a particular pixel A to be considered for possible change in its value, said A pixel having corresponding pixels B, C, D, E, F, G, H, and I around it to define a pixel neighborhood about that pixel A, a line from pixel B to pixel A extending in said line direction, pixels C, D, E, F, G, H, and I being disposed in clockwise order from pixel B and around and adjacent to pixel A, (c) generating an address which is associated with pixel A and which is dependent on values of at least a plurality of the pixels C, D, E, F, G, H, and I; (d) addressing a change look-up table stored in a memory of said image data processing system using said address so as to read out a change signal indicative of whether a change should be made in the value of pixel A; (e) changing the value of pixel A if said change signal indicates that it should be changed; (f) repeating steps (b) through (e) for different selected pixels A, one pixel A being selected at a time; and (g) repeating steps (a) through (f) for a line direction extending in a second direction, repeating steps (a) through (f) for a line direction extending in a third direction, and repeating steps (a) through (f) for a line direction extending in a fourth direction, each of said first, second, third, and fourth directions being perpendicular or anti-parallel to each of the other of said first, second, third and fourth directions, and wherein the changing of values of pixels causes the thinning of images in the image data and wherein the step of generating the address includes: addressing a weight look-up table to assign a unique weight to each of the pixels C, D, E, F, G, H, and I; performing a pixel arithmetic operation for each of the pixels C, D, E, F, G, H, and I using the weight and the value for the pixel; and combining results of said pixel arithmetic operations to provide the address.
Claim 2
Independent Claim
422 words
A method of thinning images, in an image data processing system, comprising the steps of, for a line direction initially extending in a first direction: (a) scanning image data in an image memory in a scan pattern line by line, each line extending in said line direction, in order to determine whether pixels of image data in the lines should be changed in order to thin images in the image data; (b) selecting, by way of the scanning, a particular pixel A to be considered for possible change in its value, said A pixel having corresponding pixels B, C, D, E, F, G, H, and I around it to define a pixel neighborhood about that pixel A, a line from pixel B to pixel A extending in said line direction, pixels C, D, E, F, G, H, and I being disposed in clockwise order from pixel B and around and adjacent to pixel A, (c) generating an address which is associated with pixel A and which is dependent on values of at least a plurality of the pixels C, D, E, F, G, H, and I; (d) addressing a change look-up table stored in a memory of said image data processing system using said address so as to read out a change signal indicative of whether a change should be made in the value of pixel A; (e) changing the value of pixel A if said change signal indicates that it should be changed; (f) repeating steps (b) through (e) for different selected pixels A, one pixel A being selected at a time; and (g) repeating steps (a) through (f) for a line direction extending in a second direction, repeating steps (a) through (f) for a line direction extending in a third direction, and repeating steps (a) through (f) for a line direction extending in a fourth direction, each of said first, second, third, and fourth directions being perpendicular or anti-parallel to each of the other of said first, second, third and fourth directions, and wherein the changing of values of pixels causes the thinning of images in the image data and wherein the step of generating the address includes: addressing a weight look-up table to assign a unique weight to each of the pixels C, D, E, F, G, H, and I; performing a pixel arithmetic operation for each of the pixels C, D, E, F, G, H, and I using the weight and the value for the pixel; and combining results of said pixel arithmetic operations to provide the address.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein steps (a) through (g) are repeated until the resulting image data is limited to images of lines and/or dots.
Claim 4
Dependent Claim
32 words
The method of claim 2 wherein the address generated for association with each pixel A is a function of values of the corresponding pixels C, D, E, F, G, H, and I.
Claim 5
Dependent Claim
36 words
The method of claim 3 wherein the address generated for association with a particular pixel A is independent of pixel values other than the values of corresponding pixels C, D, E, F, G, H, and I.
Claim 6
Dependent Claim
47 words
The method of claim 1 wherein the change look-up table outputs a change signal having only two values, a change to zero value if a particular pixel A is to be changed and a no change ever value if a particular pixel is not to be changed.
Claim 7
Dependent Claim
28 words
The method of claim 5 wherein the change signal is a pix out value which is written into the image memory to change the image data in place.
Claim 8
Dependent Claim
64 words
The method of claim 1 wherein a pixel number, which corresponds to the order of the pixel in a particular sequence of the pixels C, D, E, F, G, H, and I, is used to address the weight look-up table so as to output a weight for a pixel, and wherein said combining is performed by adding the results of said pixel arithmetic operations.
Claim 9
Dependent Claim
24 words
The method of claim 7 wherein the pixel arithmetic operations are the multiplication of the weight of a pixel by value of the pixel.
Claim 10
Dependent Claim
25 words
The method of claim 7 wherein the pixel arithmetic operations are the addition of the weight of a pixel to a value of the pixel.
Claim 11
Dependent Claim
14 words
The method of claim 7 wherein the pixel arithmetic operations are floating point operations.
Claim 12
Dependent Claim
54 words
The method of claim 7 wherein a pixel A is changed only if k is not 1 and n is less than 4, where k is the number of pixels C, D, E, F, G, H, and I having a value of 1 and n is the number of neighbor state changes about A.
Claim 13
Dependent Claim
54 words
The method of claim 1 wherein a pixel A is changed only if k is not 1 and n is less than 4, where k is the number of pixels C, D, E, F, G, H, and I having a value of 1 and n is the number of neighbor state changes about A.
Claim 14
Dependent Claim
27 words
The method of claim 1 wherein the image data processing system performs the generation of an address associated with a pixel A using a floating point processor.
Claim 15
Dependent Claim
31 words
The method of claim 1 wherein the image data processing system performs the generation of an address associated with a pixel A using a floating point processor for a pipeline procedure.
Claim 16
Dependent Claim
48 words
The method of claim 1 further comprising the steps of detecting energy in a form dependent on, and representative of, a zone under test, generating the image data from the energy which is detected, and displaying image data resulting from completion of the changing of values of pixels.
Claim 17
Dependent Claim
29 words
The method of claim 1 further comprising the steps of applying energy to the zone under test, and wherein the energy which is detected results from the applied energy.
Claim 18
Dependent Claim
34 words
The method of claim 1 wherein the unique weight assigned to each of the pixels C, D, E, F, G, H, and I by addressing the weight look-up table is independent of image data.
Claim 19
Dependent Claim
348 words
An image data processing system comprising: means to establish a line direction sequentially in first, second, third, and fourth directions, each of said first, second, third, and fourth directions being either perpendicular or anti-parallel to each of the other of said first, second, third, and fourth directions; scanning means to scan image data in a scan pattern line by line, each line extending in said line direction, in order to determine whether pixels of image data in the lines should be changed so as to thin images in the image data; selecting means to select, by way of the scanning, particular pixels to be considered for possible change, each particular pixel A having corresponding pixels B, C, D, E, F, G, H, and I around it to define a pixel neighborhood about that pixel A, a line from pixel B to pixel A extending in said line direction, pixels C, D, E, F, G, H, and I being disposed in clockwise order from pixel B and around and adjacent to pixel A; address generating means for generating an address which is associated with pixel A and which is dependent on values of at least a plurality of the corresponding pixels B, C, D, E, F, G, H, and I; a change look-up table stored in memory addressable by the address associated with pixel A to read out a change signal indicative of whether a change should be made in pixel A; and means for changing the value of pixel A if said change signal indicates that it should be changed; and wherein the changing of values of pixels causes the thinning of images in the image data and wherein said address generating means comprises: look-up table means for assigning a unique weight to each of the pixels C, D, E, F, G, H, and I; means for performing a pixel arithmetic operation for each of the pixels C, D, E, F, G, H, and I using the weight and the value for the pixel; and means for combining results of said pixel arithmetic operations to provide the address.
Claim 20
Dependent Claim
348 words
An image data processing system comprising: means to establish a line direction sequentially in first, second, third, and fourth directions, each of said first, second, third, and fourth directions being either perpendicular or anti-parallel to each of the other of said first, second, third, and fourth directions; scanning means to scan image data in a scan pattern line by line, each line extending in said line direction, in order to determine whether pixels of image data in the lines should be changed so as to thin images in the image data; selecting means to select, by way of the scanning, particular pixels to be considered for possible change, each particular pixel A having corresponding pixels B, C, D, E, F, G, H, and I around it to define a pixel neighborhood about that pixel A, a line from pixel B to pixel A extending in said line direction, pixels C, D, E, F, G, H, and I being disposed in clockwise order from pixel B and around and adjacent to pixel A; address generating means for generating an address which is associated with pixel A and which is dependent on values of at least a plurality of the corresponding pixels B, C, D, E, F, G, H, and I; a change look-up table stored in memory addressable by the address associated with pixel A to read out a change signal indicative of whether a change should be made in pixel A; and means for changing the value of pixel A if said change signal indicates that it should be changed; and wherein the changing of values of pixels causes the thinning of images in the image data and wherein said address generating means comprises: look-up table means for assigning a unique weight to each of the pixels C, D, E, F, G, H, and I; means for performing a pixel arithmetic operation for each of the pixels C, D, E, F, G, H, and I using the weight and the value for the pixel; and means for combining results of said pixel arithmetic operations to provide the address.
Claim 21
Dependent Claim
59 words
The image data processing system of claim 18 further comprising a detector for detecting energy in a form dependent on, and representative of, a zone under test, an image generator for generating the image data based upon the energy which is detected, and a display for displaying image data resulting from completion of the changing of values of pixels.
Claim 22
Dependent Claim
28 words
The system of claim 19 further comprising means for applying energy to the zone under test, and wherein the energy which is detected results from the applied energy.
Claim 23
Dependent Claim
30 words
The system of claim 18 wherein the means for changing the value of pixel A changes values so as to limit the image data to images of lines and/or dots.
Claim 24
Dependent Claim
43 words
The system of claim 18 wherein the address generating means uses a pipelined procedure to generate an address for association with a particular pixel A which is a function of values of the corresponding pixels C, D, E, F, G, H, and I.
Claim 25
Dependent Claim
27 words
The system of claim 18 wherein said means for performing a pixel arithmetic operation performs a floating point operation and is part of a floating point processor.
Claim 26
Dependent Claim
36 words
The system of claim 18 wherein said means for assigning a unique weight assigns a weight to each of the pixels C, D, E, F, G, H, and I which is independent of the image data.
References Cited (Backward Citations)
US3196398A
Cited
US3975709A
Cited
US4003024A
Cited
US4603430A
Cited
US4736439A
Cited
US4797806A
Cited
US4949390A
Cited
US4979221A
Cited
US5103484A
Cited
US5062142A
Cited
US5148500A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-08 | 1997-05-10 | 1997-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-08 | 2001-05-10 | 2001-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-08 | 2005-05-10 | 2005-11-09 | $7700.00 | Window Closed / Lapsed |