Compression of binary images on a hypercube machine

Peter Scheuermann, Anan Yaagoub, M. Aris Ouksel

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)49-59
Number of pages11
JournalJournal of Parallel and Distributed Computing
Issue number1
StatePublished - Oct 1994

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Compression of binary images on a hypercube machine'. Together they form a unique fingerprint.

Cite this