Patent EP0460970A2 successfully refreshed from Google Patents.
EP0460970A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Dense aggregative hierarchical techniques for data analysis
Assignee: Xerox Corp
•
Filing: 1991-06-07
•
Granted: —
•
Expires: 2011-06-07
Abstract
Abstract A body of data (60) is operated upon hierarchically in such a way that, at one or more levels (62, 64) of the hierarchy, the number of aggregative data items produced is not substantially less than the number produced at the preceding level. The body of data can be an image, so that each aggregative data item indicates an attribute of a distinct image region. Such attributes include presence of a single connected component or properties of a component such as width, orientation and curvature. A class of abstract computation structures, called exhaustive hierarchical structures, is introduced in which such dense or exhaustive hierarchical aggregative data analysis processes can be embedded. The embedding of exhaustive hierarchical analysis in a computation structure of this class is analogous, and in some implementations similar in processing efficiency, to the embedding of conventional hierarchical aggregative data analysis processes in tree structures. The exhaustive hierarchical embedding introduced analyzes extensively overlapping regions in a manner that places minimum demands on the number of communication links, memory resources, and computing power of the individual processing units. Specifically, the embedding scheme is a general scheme for mapping locations in an array into nodes at two adjacent levels of a binary exhaustive hierarchical structure. The scheme establishes positional relations in the array that correspond to parent-child relations at a given level in the exhaustive hierarchical computing structure; these positional relations are uniform power-of-two offsets in each array dimension at a given hierarchical level. Consequently, this exhaustive hierarchical analysis can be implemented efficiently using conventional communication techniques, including hypercube and grid techniques, on a massively parallel processor. To minimize memory requirements, hierarchical results at each location can be encoded across all levels.
Inventors
- 👤 James V. Mahoney
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 09:35
CPC Classifications
G; G06; G06T; G06T7/00; G06V; G06V10/00; G06V10/40; G06V10/42; G06V10/422; G06V10/44; G06V10/457
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
208 words
A method of analyzing a body of data that includes a plurality of data items; the method being performed by operating a system that includes memory and a processor connected for accessing the memory; the method comprising steps of: storing in the memory the data items of the body of data; and operating the processor to produce a hierarchy of data items, the hierarchy including the data items of the body of data as a lowest level and at least one higher level of aggregative data items, each higher level having a respective next lower level, each level of the hierarchy having a respective number of data items; the step of operating the processor to produce the hierarchy comprising, for each of the higher levels, a respective substep of producing each aggregative data item of the level by operating on a respective group of the data items of the respective next lower level, each aggregative data item of the level being for indicating an attribute of a respective group of the data items of the lowest level; the respective number of aggregative data items of a first one of the higher levels being not substantially less than the respective number of data items of the next lower level.
Claim 2
Dependent Claim
56 words
The method of claim 1 in which the body of data defines an image, each data item indicating an attribute of a respective region of the image, the respective region of each aggregative data item including the respective regions of each data item in the respective group of the data items of the next lower level.
Claim 3
Dependent Claim
37 words
The method of claim 1 or claim 2 in which the respective number of aggregative data items of the first higher level is equal to the respective number of data items of the respective next lower level.
Claim 4
Independent Claim
190 words
A system for analyzing a body of data that includes a plurality of data items; the system comprising: memory for storing the data items of the body of data; and a processor connected for accessing the data items stored in the memory, the processor further being for producing a hierarchy of data items, the hierarchy including the data items of the body of data as a lowest level and a series of higher levels of aggregative data items, each of the higher levels having a respective next lower level, each level of the hierarchy having a respective number of data items; the processor producing each of the higher levels of the hierarchy by producing each aggregative data item of the level by operating on a respective group of the data items of the respective next lower level, each aggregative data item of the level indicating an attribute of a respective group of the data items of the lowest level; the respective number of aggregative data items of a first one of the higher levels being not substantially less than the respective number of data items of the next lower level.
Claim 5
Dependent Claim
52 words
The system of claim 4 in which the body of data defines an image, each data item indicating an attribute of a respective region of the image, the respective region of each aggregative data item including the respective regions of the respective group of the data items of the next lower level.
Claim 6
Dependent Claim
44 words
The system of claim 5 in which the image has a plurality of pixels, the data items of the body of data including, for each of the pixels of the image, a respective data item, the respective data item including a respective pixel value.
Claim 7
Dependent Claim
122 words
The system of claim 6 in which the respective next lower level of the first higher level of the hierarchy is the lowest level with the respective data items that include the respective pixel values for the pixels, the first higher level including a respective first level aggregative data item for a first one of the pixels; the processor comprising a plurality of processing units including a first respective processing unit for the first pixel; the first respective processing unit of the first pixel producing the first pixel's respective first level aggregative data item by operating on a respective group of pixel values from the respective data items of the lowest level, the respective group including the first pixel's respective pixel value.
Claim 8
Dependent Claim
25 words
The system of claim 7 in which the respective group includes only the first pixel's respective pixel value and a second pixel's respective pixel value.
Claim 9
Dependent Claim
92 words
The system of claim 7 in which the hierarchy of levels includes a second one of the higher levels, the respective next lower level of the second higher level being the first higher level, the second higher level including a respective second level aggregative data item for the first pixel; the processor further being for producing the first pixel's respective second level aggregative data item by operating on a respective group of data items from the first higher level, the respective group including the first pixel's respective first level aggregative data item.
Claim 10
Dependent Claim
52 words
The system of claim 9 in which the plurality of processing units further includes, for the first pixel, a second respective processing unit; the first pixel's second respective processing unit producing the first pixel's respective second level aggregative data item by operating on the first pixel's respective first level aggregative data item.
Claim 11
Dependent Claim
79 words
The system of claim 6 in which each of the higher levels of the hierarchy includes a respective aggregative data item for each of the pixels, the processor comprising a plurality of processing units including a respective processing unit for each of the pixels; the respective processing unit producing each pixel's respective aggregative data item at each of the higher levels of the hierarchy by operating on a respective group of data items from the respective next lower level.
Claim 12
Dependent Claim
47 words
The system of claim 11 in which, for each pixel, the respective group of data items from the respective next lower level includes the pixel's respective data item at the respective next lower level and at most one additional data item from the respective next lower level.
Claim 13
Dependent Claim
46 words
The system of claim 12 in which, for each pixel whose respective group includes one additional data item, the additional data item is a respective data item of a paired pixel, the paired pixel being separated from the pixel by a power-of-two offset in the image.
Claim 14
Independent Claim
53 words
The system of any one of claims 4 to 13, further comprising an image output device for providing an output image and a user input device for receiving signals from a user requesting modifications in the output image to produce a modified image, the body of data being data defining the modified image.
Claim 15
Independent Claim
308 words
A method of operating a system that includes a plurality of processing units and, for each processing unit, respective local memory, each processing unit being connected for accessing its respective local memory, the processing units being connected for communication; the method comprising steps of: storing in the respective local memory of each of the processing units a respective lowest level data item, the respective lowest level data items together forming a body of data; and producing a hierarchy of data items, the hierarchy including the data items of the body of data as a lowest level and at least one higher level of aggregative data items, each higher level having a respective next lower level, each level of the hierarchy having a respective number of data items; the step of producing the hierarchy comprising, for each higher level, substeps of: operating each of the processing units to produce a respective aggregative data item of the higher level by operating on a respective group of the data items of the respective next lower level, each aggregative data item of the respective higher level indicating an attribute of the respective group of the data items of the respective next lower level; and operating each of the processing units to store the respective aggregative data item produced by each processing unit in its local memory; the substep of operating each of the processing units to produce a respective aggregative data item comprising a substep of communicating with a connected processing unit to obtain a first one of the respective group of the data items, the first one of the respective group of data items being stored in the local memory of the connected processing unit; the respective number of aggregative data items of each of the higher levels being equal to the respective number of data items of the lowest level.
Claim 16
Independent Claim
248 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 a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and operating the processor to produce a dense hierarchy of levels of attribute data items by operating on the data items in the body of data, each attribute data item indicating an attribute of a respective region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the hierarchy; each level of the hierarchy having a respective number of attribute data items; the step of operating the processor comprising substeps of: operating on each of the data items in the body of data to produce a respective starting attribute data item for each pixel, the lowest level of the hierarchy including the respective starting attribute data items; and for each of the higher levels, producing each attribute data item of the level by combining a respective set of the attribute data items of the respective next lower level; the respective number of attribute data items of each of the higher levels being not substantially less than the respective number of attribute data items of the respective next lower level.
Claim 17
Independent Claim
315 words
A method of operating a system that includes a plurality of processing units and, for each processing unit, respective local memory, each processing unit being connected for accessing its respective local memory; the method comprising steps of: storing in the respective local memory of each of the processing units a respective lowest level data item, the respective lowest level data items together forming a body of data; and producing a hierarchy of data items, the hierarchy including the data items of the body of data as a lowest level and a plurality of higher levels of data items, each higher level having a respective next lower level; the lowest level being the respective next lower level of one of the higher levels; the step of producing the hierarchy comprising, for each of the higher levels, a substep of operating each of the processing units to produce a respective data item of the higher level by operating on a respective set of the data items of the respective next lower level; each data item of the respective higher level indicating an attribute of the respective set of the data items of the respective next lower level; the attribute being a binary attribute having a first value and a second value; each processing unit producing a respective sequence of data items, the respective sequence including one data item for each of the higher levels; each respective sequence including at most one transition from the first value to the second value; the respective sequence of a first one of the processing units including a transition from the first value to the second value between first and second ones of the levels; the step of producing the hierarchy further comprising a substep of operating the first processing unit to store level data indicating the transition from the first value to the second value between the first and second levels.
Claim 18
Independent Claim
275 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 a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; operating the processor to produce a hierarchy of levels of upward attribute data items by operating on the data items in the body of data, each upward attribute data item indicating an upward attribute of a respective region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the hierarchy; each level of the hierarchy having a respective number of upward attribute data items; the respective number of upward attribute data items of each of the higher levels being not substantially less than the respective number of upward attribute data items of the respective next lower level; and for a first one of the higher levels in the hierarchy, operating the processor to produce a number of downward attribute data items at a second level in the hierarchy by operating on a respective set of the upward attribute data items of the first higher level, the second level being the respective next lower level of the first higher level, each downward attribute data item indicating a downward attribute of a respective region of the image; each of the upward attribute data items of the second level having a respective one of the downward attribute data items.
Claim 19
Independent Claim
264 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 a body of data that includes a plurality of data items, each including one of a set of respective values; and operating the processor to produce a first hierarchy of levels of prominent value data items by operating on the data items in the body of data, each prominent value data item including one of the respective values and a count; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the first hierarchy; the step of operating the processor comprising substeps of: operating on each of the data items in the body of data to obtain a respective starting prominent value data item for each data item in the body of data, each data item's respective starting prominent value data item including the data item's respective value; the lowest level of the first hierarchy including the respective starting prominent value data items; and for each of the higher levels, producing each prominent value data item of the higher level by combining a respective set of the prominent value data items of the respective next lower level, each prominent value data item including one of the respective values from the prominent value data items in the respective set, the count in each prominent value data item being produced by operating on the counts in the prominent value data items in the respective set.
Claim 20
Independent Claim
291 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 a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and operating the processor to produce a hierarchy of levels of first attribute data items by operating on the data items in the body of data, each first attribute data item indicating a first attribute of a respective region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the hierarchy; the step of operating the processor comprising substeps of: operating on each of the data items in the body of data to produce a respective starting first attribute data item for each pixel, the lowest level of the hierarchy including the respective starting first attribute data items; the substep of operating on each of the data items in the body of data comprising, for each of the data items, a substep of operating on a set of data items that includes the data item and the respective data items of a number of neighborhood pixels to determine a respective neighborhood configuration; the data item's respective pixel and the neighborhood pixels together forming a respective neighborhood; the respective neighborhood configuration being a configuration of pixels of the respective neighborhood; and for each of the higher levels, producing each first attribute data item of the level by combining a respective set of the first attribute data items of the respective next lower level.
Claim 21
Independent Claim
362 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 a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each for a respective one of the pixels; each pixel's data item including current selection data indicating whether the pixel is in a set of currently selected pixels; each pixel's data item further including first attribute data indicating a first attribute of the pixel; operating the processor to produce a hierarchy of levels of upward attribute data items by operating on the data items in the body of data, each upward attribute data item indicating an upward attribute of a respective region of the image; the levels further including a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the hierarchy, one of the higher levels being a highest level, each of the levels other than the highest level having a respective next higher level; each level of the hierarchy having a respective number of upward attribute data items, the respective number of upward attribute data items of each of the higher levels being not substantially less than the respective number of upward attribute data items of the respective next lower level; operating the processor to produce a hierarchy of levels of downward attribute data items by operating on the upward attribute data items at the highest level, each downward attribute data item indicating a downward attribute of a respective region of the image; the levels of the hierarchy of downward attribute data items being the same as the levels of the hierarchy of upward attribute data items; each downward attribute data item at the lowest level of the downward attribute data items indicating the downward attribute of a respective pixel of the image; and operating the processor to use the downward attribute data items at the lowest level in determining whether to set each pixel's current selection data to indicate that the pixel is in the set of currently selected pixels.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.