Abstract

The S et Partitioning in Hierarchical Trees (S PIHT) image compression algorithm is very efficient, has low computational complexity, and generates an embedded compressed bit-stream that can be efficiently decoded at several data rates (qualities). Unfortunately it needs a huge amount of computer memory due to using three linked lists to store the coordinates of the image pixels. In addition the S PIHT has complex memory management due to the random access to these lists. This paper proposes a new algorithm termed S ingle List-S PIHT (S LS). The proposed S LS algorithm has very low memory requirements as it needs about six times less memory than the original S PIHT. This is achieved by using a single list and two state mark bitmaps instead of the three lists that are used by the original S PIHT. In addition, the proposed S LS has simpler memory management because once a pixel is added to the list, it will never be removed. This will permit to impleme nt the list as a simple ordered array that is accessed sequentially. Moreover, the size of the list can be predefined which avoids the dynamic memory allocation problem. This memory reduction and management simplification make the S LS algorithm very suitable for hardware implementation. Furthermore, S LS has better compression performance as compared to the original S PIHT. The price paid for these features is very slight increment in the algorithm's complexity as compared to the original S PIHT