A Block-Based Pass-Parallel SPIHT Algorithm

Set-partitioning in hierarchical trees (SPIHT) is a widely used compression algorithm for wavelet-transformed images. One of its main drawbacks is a slow processing speed due to its dynamic processing order that depends on the image contents. To overcome this drawback, this paper presents a modified SPIHT algorithm called block-based pass-parallel SPIHT (BPS). BPS decomposes a wavelet-transformed image into 4 x 4 blocks and simultaneously encodes all the bits in a bit-plane of a 4 x 4 block. To exploit parallelism, BPS reorganizes the three passes of the original SPIHT algorithm and then BPS encodes/decodes the reorganized three passes in a parallel and pipelined manner. The precalculation of the stream length of each pass enables the parallel and pipelined execution of these three passes by not only an encoder but also a decoder. The modification of the processing order slightly degrades the compression efficiency. Experimental results show that the peak signal-to-noise ratio loss by BPS is between approximately 0.23 and 0.59 dB when compared to the original SPIHT algorithm. Both an encoder and a decoder are implemented in the hardware that can process 120 million samples per second at an operating clock frequency of 100 MHz. This processing speed allows a video of size of 1920 x 1080 in the 4: 2: 2 format to be processed at the rate of 30 frames/s. The gate count of the hardware is about 43.9K.