Patent US5231676A successfully refreshed from Google Patents.
US5231676A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hierarchical operations on border attribute data for image regions
Assignee: Xerox Corp
•
Filing: 1990-06-08
•
Granted: 1993-07-27
•
Expires: 2010-06-08
Abstract
Abstract A hierarchy of border attribute data items is produced from a body of data such as the pixel values of an image. Each border attribute data item indicates an attribute of a border of an analysis region of the image. The starting border attribute data items, at the lowest level of the hierarchy, are produced by operation on the pixel values. Each border attribute data item at a higher level in the hierarchy is produced by operating on a respective set of data items from the next lower level. The border attribute data items can indicate, for example, the number of black pixels in each border or the number of edge pixels in each border. Or the border attribute data items could include boolean values indicating whether any of the pixels in a border is a black pixel with a neighboring black pixel outside the border. For rectangular regions in a binary hierarchy, values for two borders can be added or logically combined at a first level and one of the values for the same two borders can be selected at the next higher level; one of the values for the other two borders can be selected at the first level and the values for those two borders can be added or logically combined at the next higher level.
Inventors
- 👤 James V. Mahoney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 11:06
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/40; G06V10/44; G06V10/457
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
217 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; each pixel having four neighboring pixels; and operating the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; each pixel's starting border attribute data item including four values, each value indicating whether the image includes an edge between the pixel and one of its neighboring pixels; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level.
Claim 2
Independent Claim
217 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; each pixel having four neighboring pixels; and operating the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; each pixel's starting border attribute data item including four values, each value indicating whether the image includes an edge between the pixel and one of its neighboring pixels; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level.
Claim 3
Dependent Claim
51 words
The method of claim 1 in which the substep of operating on each of the pixel data items comprises a substep of operating on each pixel's pixel data item and on the pixel data item of each of the pixel's neighboring pixels to produce the pixel's starting border attribute data item.
Claim 4
Independent Claim
352 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; and operation the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the images; each border attribute data item including a set of values including first, second, third, and fourth numeric values; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level; the set of border attribute data items that are combined to produce a first one of the border attribute data items at a first one of the higher levels of the hierarchy including first and second lower level border attribute data items at the next lower level of the first higher level; the substep of producing each border attribute data item of the first higher level comprising a substep of producing the first and third numeric values of the first border attribute data items of the first higher level by adding the first and third numeric values, respectively, of the first and second lower level border attribute data items and producing the second and fourth numeric values of the first border attribute data item of the first higher level by selecting one of the second and fourth numeric values, respectively, of the first and second lower level border attribute data items.
Claim 5
Independent Claim
352 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; and operation the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the images; each border attribute data item including a set of values including first, second, third, and fourth numeric values; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level; the set of border attribute data items that are combined to produce a first one of the border attribute data items at a first one of the higher levels of the hierarchy including first and second lower level border attribute data items at the next lower level of the first higher level; the substep of producing each border attribute data item of the first higher level comprising a substep of producing the first and third numeric values of the first border attribute data items of the first higher level by adding the first and third numeric values, respectively, of the first and second lower level border attribute data items and producing the second and fourth numeric values of the first border attribute data item of the first higher level by selecting one of the second and fourth numeric values, respectively, of the first and second lower level border attribute data items.
Claim 6
Dependent Claim
183 words
The method of claim 3 in which the hierarchy includes a second higher level, the first higher level being the next lower level of the second higher level, the set of border attribute data items that are combined to produce a first one of the border attribute data items at the second higher level including the first border attribute data item at the first higher level and a second border attribute data item at the first higher level; the substep of producing each border attribute data item of the second higher level comprising a substep of producing the second and fourth numeric values of the first border attribute data item of the second higher level by adding the second and fourth numeric values, respectively, of the first and second border attribute data items of the first higher level and producing the first and third numeric values of the first border attribute data item of the second higher level by selecting one of the first and third numeric values, respectively, of the first and second border attribute data items of the first higher level.
Claim 7
Dependent Claim
69 words
The method of claim 3 in which the analysis region of each of the border attribute data items is rectangular with first, second, third, and fourth borders and with at least one border pixel in each border; the first, second, third, and fourth numeric values indicating a number of pixels that meet a border attribute criterion in the first, second, third, and fourth borders of the analysis region, respectively.
Claim 8
Dependent Claim
29 words
The method of claim 5 in which each indicated number of border pixels is a total number of border pixels that meet the border attribute criterion in the border.
Claim 9
Independent Claim
344 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; and operating the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the image; each border attribute data item at each level including a set of values including first and second boolean values; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level; the set of border attribute data items that are combined to produce a first one of the border attribute data items at a first one of the higher levels of the hierarchy including first and second lower level border attribute data items at the next lower level of the first higher level; the substep of producing each border attribute data item of the first higher level comprising a substep of producing the first boolean value of the first border attribute data item of the first higher level by logically combining the first boolean values of the first and second lower level border attribute data items and producing the second boolean value of the first border attribute data item of the first higher level by selecting one of the second boolean values of the first and second lower level border attribute data items.
Claim 10
Independent Claim
344 words
A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of: storing in the memory image data defining an image that includes a plurality of pixels, the image data including a pixel data item for each of the pixels; and operating the processor to produce a hierarchy of levels of border attribute data items by operating on the pixel data items, each border attribute data item indicating a border attribute of an analysis region of the image; each border attribute data item at each level including a set of values including first and second boolean values; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the pixel data items to produce a starting border attribute data item, the lowest level of the hierarchy including the starting border attribute data items; and for each of the higher levels, producing each border attribute data item of the level by combining a set of the border attribute data items of the next lower level; the set of border attribute data items that are combined to produce a first one of the border attribute data items at a first one of the higher levels of the hierarchy including first and second lower level border attribute data items at the next lower level of the first higher level; the substep of producing each border attribute data item of the first higher level comprising a substep of producing the first boolean value of the first border attribute data item of the first higher level by logically combining the first boolean values of the first and second lower level border attribute data items and producing the second boolean value of the first border attribute data item of the first higher level by selecting one of the second boolean values of the first and second lower level border attribute data items.
Claim 11
Dependent Claim
174 words
The method of claim 7 in which the hierarchy includes a second higher level, the first higher level being the next lower level of the second higher level, the set of border attribute data items that are combined to produce a first one of the border attribute data items at the second higher level including the first border attribute data item at the first higher level and a second border attribute data item at the first higher level; the substep of producing each border attribute data item of the second higher level comprising a substep of producing the second boolean value of the first border attribute data item of the second higher level by logically combining the second boolean values of the first and second border attribute data items of the first higher level and producing the first boolean values of the first border attribute data item of the second higher level by selecting one of the first boolean values of the first and second border attribute data items of the first higher level.
Claim 12
Dependent Claim
63 words
The method of claim 7 in which the analysis region of each of the border attribute data items is rectangular with first, second, third, and fourth borders and with at least one border pixel in each border; the first and second boolean values indicating whether any pixels meet a border attribute criterion in the first and second borders of the analysis region, respectively.
Claim 13
Dependent Claim
30 words
The method of claim 9 in which the border attribute criterion is met by one of the pixels that is black and has a neighboring black pixel outside the border.
Claim 14
Dependent Claim
26 words
The method of claim 10 in which each pixel's starting border attribute data item indicates whether the pixel and each of its neighboring pixels are connected.
Claim 15
Dependent Claim
26 words
The method of claim 11 in which each pixel's starting border attribute data item indicates that the pixel is connected only if the pixel is black.
References Cited (Backward Citations)
US4566124A
Cited
US4771474A
Cited
US4771469A
Cited
EP0257550A2
Cited
US5014331A
Cited
US5022091A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-26 | 1997-01-25 | 1997-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-26 | 2001-01-25 | 2001-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-26 | 2005-01-25 | 2005-07-27 | $7700.00 | Window Closed / Lapsed |