Compression of binary images on a hypercube machine

The S-tree linear representation is an efficient structure for representing binary images which requires three bits for each disjoint binary region. We present parallel algorithms for encoding and decoding the S-tree representation from/onto a binary pixel array in a hypercube connected machine. Both the encoding and the decoding algorithms make use of a condensation procedure in order to produce the final result cooperatively. The encoding algorithm conceptually uses a pyramid configuration, where in each iteration half of the processors in the grid below it remain active. The decoding algorithm is based on the observation that each processor can independently decode a given binary region if it contains in its memory an S-tree segment augmented with a linear prefix. We analyze the algorithms in terms of processing and communication time and present results of experiments performed with real and randomly generated images that verify our theoretical results.