Listless SPIHT Image Compression Algorithm

Compression of images saves storage capacity, channel bandwidth, and transmission time. Its use is ubiquitous, as almost every digital still or moving image has been compressed before it reaches the user. Efficient and computationally simple techniques of transform-based image coding have been realized using set partitioning and significance testing on hierarchical structure of discrete wavelet transformed (DWT) image. Said and Pearlman introduced such a technique in their SPIHT (Set Partitioning In Hierarchical Trees) algorithm, in their successful effort to extend and improve Shapiro's EZW (Embedded Zerotree Wavelet) algorithm. The SPIHT algorithm demonstrates a very simple and efficient way to code a DWT image. It has since become a standard benchmark in image compression. SPIHT uses list structure to keep track of which sets must be tested. During coding, it needs to maintain three lists to store temporarily the image's zerotree structure and significance information. However, the use of lists in SPIHT causes a variable, data dependent memory requirement, and the need for memory management as list nodes are added, removed and moved. At high rate, there can be as many list nodes as coefficients. This may be undesirable in hardware implementation. Most of all, these three lists represent a major drawback for hardware implementation because a large amount of memory is needed to maintain them. This high memory requirement makes SPIHT not a cost effective compression algorithm for VLSI implementation. Lin et al. developed listless zerotree codec for images and video that makes use of fixed size state tables instead of lists. The amount of memory required by the LZC codec is only a fraction of the amount needed by a SPIHT codec. Consequently the implementation complexity and hardware cost can be reduced significantly. EZW explicitly performs a breath first search of the hierarchical trees, moving form the coarse to fine bands. Though it is not explicit, SPIHT does a rough breadth first search as well. After partitioning a grand-descendant set, SPIHT places the four new descendent sets at the end of the LIS, or list of insignificant sets. It is the appending to the LIS that results in the approximate breadth first traversal. Breadth first, as opposed to depth first, scanning improves performance because coefficients more likely to be significant are tested first. However, LZC adopts a depth first search, which slightly lowers its compression performance compared with SPIHT. In this thesis, an improved listless zerotree image coder has been presented that produces a fully embedded bit stream. Furthermore, the compression performance of this algorithm is competitive with the well known SPIHT algorithm and it is much simpler, faster and very memory efficient. The remarkable performance can be attributed to the use of the following four features: (1) A modified zerotree structure, which is more effective in presenting similarities between wavelet coefficients not only across subbands of different levels, but also similarities between coefficients in the coarsest level. (2) State maps, which are used to encode the positions of significant pixels or keep track of which set must be tested. The advantage of the new algorithm over SPIHT is that no lists are needed during coding and decoding. Instead, a coefficient only needs a 1-bit flag if the coefficient is in the first wavelet transform level and a 3-bit flag is it is in any other transform level. Consequently, the amount of memory that required by the new codec is only a fraction of the amount needed by a SPIHT codec. In common with SPIHT, the new algorithm is a progressive coding algorithm (3) The lifting scheme, which is performed to realize fast wavelet transform of the image data. Besides the increased flexibility, lifting allows: (a) fast implementation, by making optimal use of similarities between high and low pass filters, the necessary number of flops can be reduced to half, (b) fully in-place calculation, by gradually replacing the original image with its transform, the need for an auxiliary memory can be avoided and the hardware implementation can be simplified, (c) simple inverse transform, of the same computational complexity as the forward one, the inverse transform being composed of the inverse elementary operations of the forward one, taken in reversed order. (4) A new coding procedure, which results in better compression performance, especially at very low bit rate. The coding procedure of SPIHT is divides into sorting pass and refinement pass. The control flow of switching between these two passes can be easily done by software, but not so easy for hardware implementation. Furthermore, it results in more bits being used to represent location information, which may lower the quality of reconstructed image, especially at very low bit rate. Therefore, in the improved algorithm the sorting pass and refinement pass were...