This paper describes three hierarchical organizations of small processors for bottom-up image analysis:pyramids, interleaved pyramids, and pyramid trees. Progressively lower levels in the hierarchies process image windows of decreasing size. Bottom-up analysis is made feasible by transmitting up the levels quadrant borders and border-related information that captures quadrant interaction of interest for a given computation. The operation of the pyramid is illustrated by examples of standard algorithms for interior-based computations (e.g., area) and border-based computations of local properties (e.g., perimeter). A connected component counting algorithm is outlined that illustrates the role of border-related information in representing quadrant interaction. Interleaved pyramids are obtained by sharing processors among several pyramids. They increase processor utilization and throughput rate at the cost of increased hardware. Trees of shallow interleaved pyramids, calld pyramid trees, are introduced to reduce the hardware requirements of large interleaved pyramids at the expense of increased processing time, without sacrificing processor utilization. The three organizations are compared with respect to several performance measures.

A linear recursive procedure is one in which a procedural call can activate at most one other procedural call. When linear recursion cannot be replaced by iteration, it is usually implemented with a stack of size proportional to the depth of recursion. In this paper we analyze implementations of linear recursion which permit large reductions in storage space at the expense of a small increase in computation time. For example, if the depth of recursion is n, storage space can be reduced to √n at the cost of a constant factor increase in running time. The problem is treated by abstracting linear recursion into the pebbling of a simple graph and for this abstraction we exhibit the optimal space-time tradeoffs.

The performance of the fast Fourier transfmm algorithm is examined under limitations on computational space and time. It is shown that if the algorithm withninputs,nas a power of two, is implemented withStemporary locations whereS=o(n/ \log n), then the computation timeTgrows faster thann \log n. Furthermore,Tcan grow as fast asn^{2}ifS=S_{min} + O(1)whereS_{min}=l+\log_{2}n, the minimum necessary. These results are obtained by deriving tight bounds onTversusSandn.

The generalized Reed-Muller expansions of a switching function are generated using a single Boolean matrix and step-by-step shifting of the principal column.