SPIHT image compression without lists

Abstract

A variant of the SPIHT image compression algorithm called no list SPIHT (NLS) is presented. NLS operates without linked lists and is suitable for a fast, simple hardware implementation. NLS has a fixed predetermined memory requirement about 50% larger than that needed for the image alone. Instead of lists, a state table with four bits per coefficient keeps track of the set partitions and what information has been encoded. NLS sparsely marks selected descendant nodes of insignificant trees in the state table in such a way that large groups of predictably insignificant pixels are easily identified and skipped during coding passes. The image data is stored in a one dimensional recursive zig-zag array for computational efficiency and algorithmic simplicity. The performance of the algorithm on standard test images is nearly the same as SPIHT.