| 摘要 |
<p>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. <IMAGE></p> |
