Simulating Essential Pyramids

Pyramid computers. and more generallv pyramid algorithms, have long been proposed for image processing. They have the advantage of being a regular structure with a base naturally identified with an input image, and a logarithmic height which enables rapid reduction of information. Unfortunately, when the image contains multiple objects of interest, it is often difficult to use the pyramid efficiently since the most straightforward algorithms try to simultaneously use the apex for each object, creating a severe bottleneck. Furthermore, algorithms which are efficient in such settings tend to be significantly more complicated than is desirable, limiting the appeal of pyramids for more complicated analyses and images. However, this paper shows that one can systematically simulate the effect of having a separate “essential” pyramid over each object, greatly simplifying algorithm development since algorithms can be written assuming that there is only a single object. This approach can yield optimal or nearly optimal algorithms for the pyramid computer, and can also be used on nonpyramid architectures such as the hypercube, mesh-of-trees, mesh, mesh with row and column buses, mesh with reconfigurable buses, and PRAM. For several of these architectures, the simulated essential pyramids can all simultaneously perform an algorithm nearly as fast as a pyramid computer over a single object.