US5239596A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Labeling pixels of an image based on near neighbor attributes
Assignee: Xerox Corp
•
Filing: 1990-06-08
•
Granted: 1993-08-24
•
Expires: 2010-06-08
Abstract
Abstract Pixels within an image are labeled based on near neighbor attributes. The attributes may be attributes for a near neighbor link or for a near neighbor pixel to which the link leads. The near neighbor attribute data for a pixel may indicate attributes for plural near neighbor links, and a link relationship criterion may be applied to determine whether the links are related in a manner that meets the criterion. For example, a pixel may be labeled only if its near neighbor links include a pair with relative orientation difference of approximately 180°, both of which have been previously labeled or are links to a boundary; this criterion is useful in labeling a partially bounded region. A distance independent connected component labeling criterion may be applied during parallel labeling of pixels for rapid connected component labeling. Labeling based on a near neighbor labeling criterion may be iterated until a component or region is completely labeled.
Inventors
- 👤 James V. Mahoney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 17:06
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/11; G06T7/187; G06V; G06V10/00; G06V10/40; G06V10/44; G06V10/457; G06T2207/00; G06T2207/20; G06T2207/20016
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
196 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data; the near neighbor attribute data indicating a first attribute for a first near neighbor link of the first pixel and indicating a second attribute for a second near neighbor link of a second one of the pixels; and operating the processor to use the near neighbor attribute data of the first pixel to determine whether the first near neighbor link of the first pixel is a link to the second pixel and the second near neighbor link of the second pixel is a link to the first pixel and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels.
Claim 2
Independent Claim
196 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data; the near neighbor attribute data indicating a first attribute for a first near neighbor link of the first pixel and indicating a second attribute for a second near neighbor link of a second one of the pixels; and operating the processor to use the near neighbor attribute data of the first pixel to determine whether the first near neighbor link of the first pixel is a link to the second pixel and the second near neighbor link of the second pixel is a link to the first pixel and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels.
Claim 3
Dependent Claim
85 words
The method of claim 1 in which the near neighbor attribute data indicate a first quadrant and a first offset for the first near neighbor link and a second quadrant and a second offset for the second near neighbor link; the step of operating the processor to use the near neighbor attribute data comprising substeps of: determining whether the first and second quadrants are opposite; and if the first and second quadrants are opposite, determining whether the first and second offsets are equal in magnitude.
Claim 4
Dependent Claim
142 words
The method of claim 1 in which the near neighbor attribute data indicate a link orientation and a distance for the first near neighbor link, the method further comprising a step of operating the processor to use the near neighbor attribute data of the first pixel to determine whether the first pixel and the second pixel are in a group, comprising substeps of: obtaining a minimum of a maximum distance and the distance for the first near neighbor link; using the minimum to obtain a proportion of a maximum orientation difference; obtaining a difference between the link orientation for the first near neighbor link and an independent orientation for the first pixel; and comparing the proportion of the maximum orientation difference with the difference between the link orientation for the first near neighbor link and the independent orientation for the first pixel.
Claim 5
Dependent Claim
45 words
The method of claim 1 in which the first attribute is a first length and the second attribute is a second length; the step of operating the processor to use the near neighbor attribute data including a substep of comparing the first and second lengths.
Claim 6
Dependent Claim
48 words
The method of claim 1 in which the first attribute is a first link orientation and the second attribute is a second link orientation; the step of operating the processor to use the near neighbor attribute data including a substep of comparing the first and second link orientations.
Claim 7
Dependent Claim
94 words
The method of claim 1 in which the near neighbor attribute data further indicate a third attribute for the first near neighbor link and indicate a fourth attribute for the second near neighbor link; the first attribute being a first length; the second attribute being a second length; the third attribute being a first link orientation; the fourth attribute being a second link orientation; the step of operating the processor to use the near neighbor attribute data including substeps of: comparing the first and second link orientations; and comparing the first and second lengths.
Claim 8
Independent Claim
174 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data; the near neighbor attribute data indicating a first relative orientation from the first pixel to a first near neighbor pixel and indicating a second relative orientation from the first pixel to a second near neighbor pixel; and operating the processor to use the near neighbor attribute data of the first pixel to determine whether the difference between the first and second relative orientations is approximately 180° and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels.
Claim 9
Independent Claim
174 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data; the near neighbor attribute data indicating a first relative orientation from the first pixel to a first near neighbor pixel and indicating a second relative orientation from the first pixel to a second near neighbor pixel; and operating the processor to use the near neighbor attribute data of the first pixel to determine whether the difference between the first and second relative orientations is approximately 180° and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels.
Claim 10
Dependent Claim
69 words
The method of claim 7 in which, if the difference between the first and second relative orientations is approximately 180°, the step of operating the processor to use the near neighbor attribute data further includes a substep of determining whether the respective pixel set data of each of the first and second near neighbor pixels indicate that the first and second near neighbor pixels are in the indicated set.
Claim 11
Dependent Claim
98 words
The method of claim 7 in which the near neighbor attribute data indicate whether the first near neighbor pixel is a boundary pixel; the step of operating the processor to use the near neighbor attribute data including, if the difference between the first and second relative orientations is approximately 180°, a substep of determining whether the near neighbor attribute data indicate that the first near neighbor pixel is a boundary pixel and, if so, determining whether the pixel set data of the second near neighbor pixel indicate that the second near neighbor pixel is in the indicated set.
Claim 12
Independent Claim
244 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including pixel set data indicating whether the pixel is in an indicated set of pixels; a first one of the pixel's pixel set data indicating that the pixel is in the indicated set of pixels; and for each of a series of steps, operating the processor to set the pixel set data of a number of additional ones of the pixels until a final step in which the number of additional pixels is not sufficient to justify another step; each of the steps of operating the processor to set the pixel set data of additional pixels comprising substeps of: producing, for each pixel, near neighbor attribute data indicating an attribute of a near neighbor pixel of the pixel, the attribute being whether the near neighbor pixel's pixel set data indicates that the pixel is in the indicated set of pixels; and for each pixel whose near neighbor attribute data indicates that the near neighbor pixel is in the indicated set of pixels, applying a labeling criterion to determine whether to set the pixel's pixel set data to indicate that the pixel is in the set of pixels and, if so, setting the pixel's pixel set data accordingly.
Claim 13
Independent Claim
244 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including pixel set data indicating whether the pixel is in an indicated set of pixels; a first one of the pixel's pixel set data indicating that the pixel is in the indicated set of pixels; and for each of a series of steps, operating the processor to set the pixel set data of a number of additional ones of the pixels until a final step in which the number of additional pixels is not sufficient to justify another step; each of the steps of operating the processor to set the pixel set data of additional pixels comprising substeps of: producing, for each pixel, near neighbor attribute data indicating an attribute of a near neighbor pixel of the pixel, the attribute being whether the near neighbor pixel's pixel set data indicates that the pixel is in the indicated set of pixels; and for each pixel whose near neighbor attribute data indicates that the near neighbor pixel is in the indicated set of pixels, applying a labeling criterion to determine whether to set the pixel's pixel set data to indicate that the pixel is in the set of pixels and, if so, setting the pixel's pixel set data accordingly.
Claim 14
Dependent Claim
27 words
The method of claim 10 in which the number of additional pixels is not sufficient to justify another step when the number of additional pixels is zero.
Claim 15
Dependent Claim
31 words
The method of claim 10 in which the labeling criterion is whether the pixel's near neighbor attribute data indicates that the near neighbor pixel is in the indicated set of pixels.
Claim 16
Dependent Claim
22 words
The method of claim 10 in which, after the final step, the indicated set of pixels defines a region of the image.
Claim 17
Independent Claim
203 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data indicating an attribute for a plurality of near neighbor links; and operating the processor to apply a link relationship criterion to the near neighbor attribute data of the first pixel to determine whether the plurality of near neighbor links are related in a manner that meets the link relationship criterion and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels; the near neighbor attribute data indicating a distance between the first pixel and a second pixel; the step of operating the processor to apply the link relationship criterion comprising a substep of varying the criterion with the distance indicated by the near neighbor attribute data.
Claim 18
Independent Claim
203 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for a first one of the pixels, near neighbor attribute data indicating an attribute for a plurality of near neighbor links; and operating the processor to apply a link relationship criterion to the near neighbor attribute data of the first pixel to determine whether the plurality of near neighbor links are related in a manner that meets the link relationship criterion and, if so, setting the first pixel's pixel set data to indicate that the first pixel is in the indicated set of pixels; the near neighbor attribute data indicating a distance between the first pixel and a second pixel; the step of operating the processor to apply the link relationship criterion comprising a substep of varying the criterion with the distance indicated by the near neighbor attribute data.
Claim 19
Independent Claim
187 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for each of a plurality of the pixels, near neighbor attribute data that indicate a first attribute for a first near neighbor link of the pixel and that indicate a second attribute for a second near neighbor link of the pixel; and operating the processor to apply a link relationship criterion to the near neighbor attribute data of each of the plurality of the pixels to determine whether the first and second near neighbor links of each pixel are related to each other in a manner that meets the link relationship criterion and, if so, setting the pixel's pixel set data to indicate that the pixel is in the indicated set of pixels.
Claim 20
Independent Claim
187 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel's respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels; operating the processor to produce, for each of a plurality of the pixels, near neighbor attribute data that indicate a first attribute for a first near neighbor link of the pixel and that indicate a second attribute for a second near neighbor link of the pixel; and operating the processor to apply a link relationship criterion to the near neighbor attribute data of each of the plurality of the pixels to determine whether the first and second near neighbor links of each pixel are related to each other in a manner that meets the link relationship criterion and, if so, setting the pixel's pixel set data to indicate that the pixel is in the indicated set of pixels.
Claim 21
Dependent Claim
34 words
The method of claim 15 in which the first attribute is a first length and the second attribute is a second length, the link relationship criterion comparing the first length and the second length.
Claim 22
Dependent Claim
34 words
The method of claim 15 in which the first attribute is a first orientation and the second attribute is a second orientation, the link relationship criterion comparing the first orientation and the second orientation.
Claim 23
Dependent Claim
48 words
The method of claim 15 in which the near neighbor attribute data indicate a first length for the first near neighbor link and a second length for the second near neighbor link, the link relationship criterion determining whether the first length is much longer than the second length.
Claim 24
Dependent Claim
56 words
The method of claim 18 in which the step of operating the processor to apply the link relationship criterion comprises substeps of: obtaining a square of a difference between the first and second lengths; obtaining a sum of the first and second lengths; and obtaining a ratio of the square of the difference to the sum.
Claim 25
Dependent Claim
46 words
The method of claim 15 in which the near neighbor attribute data indicate a first orientation for the first near neighbor link and a second orientation for the second near neighbor link, the link relationship criterion determining whether the first and second orientations are sufficiently aligned.
Claim 26
Dependent Claim
88 words
The method of claim 20 in which the near neighbor attribute data further indicate a first distance for the first near neighbor link and a second distance for the second near neighbor link, the step of operating the processor to apply the link relationship criterion comprising substeps of: obtaining a greater one of the first and second distances; obtaining a minimum of a maximum distance and the greater one of the first and second distances; and using the minimum to obtain a proportion of a maximum orientation difference.
References Cited (Backward Citations)
US4513438A
Cited
EP0216158A2
Cited
US5014331A
Cited
EP0380721A1
Cited
US5048109A
Cited
US5065437A
Cited
US5129014A
Cited
US5131049A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-23 | 1997-02-22 | 1997-08-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-23 | 2001-02-22 | 2001-08-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-23 | 2005-02-22 | 2005-08-24 | $7700.00 | Window Closed / Lapsed |