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.