The prism machine: An alternative to the pyramid

The prism machine is a stack of n cellular arrays, each of size 2ⁿ × 2ⁿ. Cell (i, j) on level k is connected to cells (i, j), (i + 2^k, j), and (i, j + 2^k) on level k + 1, 1 ≤ k < n, where the sums are modulo 2ⁿ. Such a machine can perform various operations (e.g., “Gaussian” convolutions or least-squares polynomial fits) on image neighborhoods of power-of-2 sizes in every position in O(n) time, unlike a pyramid machine which can do this only in sampled positions. It can also compute the discrete Fourier transform in O(n) time. It consists of n · 4ⁿ cells, while a pyramid consists of fewer than 4ⁿ⁺¹/3 cells; but in practice n would be at most 10, so that a prism would be at most about seven times as large as a pyramid.