Abstract

The purpose of this two-part monograph is to present a tutorial on set partition coding, with emphasis and examples on image wavelet transform coding systems, and describe their use in modern image coding systems. Set partition coding is a procedure that recursively splits groups of integer data or transform elements guided by a sequence of threshold tests, producing groups of elements whose magnitudes are between two known thresholds, therefore, setting the maximum number of bits required for their binary representation. It produces groups of elements whose magnitudes are less than a certain known threshold. Therefore, the number of bits for representing an element in a particular group is no more than the base-2 logarithm of its threshold rounded up to the nearest integer. SPIHT (Set Partitioning in Hierarchical Trees) and SPECK (Set Partitioning Embedded blocK) are popular state-of-the-art image coders that use set partition coding as the primary entropy coding method. JPEG2000 and EZW (Embedded Zerotree Wavelet) use it in an auxiliary manner. Part I elucidates the fundamentals of set partition coding and explains the setting of thresholds and the block and tree modes of partitioning. Algorithms are presented for the techniques of AGP (Amplitude and Group Partitioning), SPIHT, SPECK, and EZW. Numerical examples are worked out in detail for the latter three techniques. Part II describes various wavelet image coding systems that use set partitioning primarily, such as SBHP (Subband Block Hierarchical Partitioning), SPIHT, and EZBC (Embedded Zero-Block Coder). The basic JPEG2000 coder is also described. The coding procedures and the specific methods are presented both logically and in algorithmic form, where possible. Besides the obvious objective of obtaining small file sizes, much emphasis is placed on achieving low computational complexity and desirable output bitstream attributes, such as embeddedness, scalability in resolution, and random access decodability.

This monograph is extracted and adapted from the forthcoming textbook entitled Digital Signal Compression: Principles and Practice by William A. Pearlman and Amir Said, Cambridge University Press, 2009.

Set Partition Coding

Set partition coding is a simple, popular, and effective method that has produced some of the best results in image and signal coding. Nevertheless, the literature has not adequately explained the principles of this method that make it so effective. This article, in tandem with Part II, which is available separately, remedies this situation and describes various image wavelet coding systems, most of which use set partition coding in some form. In Part I, the principles and various methods of set partition coding are thoroughly explained. These methods include the well-known SPIHT (Set Partitioning In Hierarchical Trees) and SPECK (Set Partitioning Embedded bloCK) algorithms and the lesser known AGP (Alphabet and Group Partitioning) algorithm. Furthermore, because it inspired SPIHT, the EZW (Embedded Zerotree Wavelet) algorithm is described. The coding actions of SPIHT, SPECK, and EZW are completely delineated and compared in a numerical example. Appendix A explains transforms of signal sources. This material is not necessary for understanding the coding methods, most of which can be applied either to the source or its transform. However, since most modern coding systems employ transforms and examples are presented that use transforms, a reader might feel more comfortable with this material having read this appendix. Therein are explained the Karhunen-Loeve transform (KLT), discrete cosine transform (DCT), and subband transforms, including the wavelet transform. Parts I and II together build to a tutorial that is written on a level suitable for students and practitioners of image and signal compression. A unique aspect is the setting apart in boxes of the detailed steps of the algorithms in addition to explanation of these steps and their underlying principles. Many figures and examples are sprinkled throughout to aid understanding.