1 Introduction

Recent work in wavelet image coding has resulted in quite a number of advanced coding algorithms that give extremely good performance. Building on the signal processing foundations laid by researchers including Vetterli ^[[VH92]] and in some instances on the idea of zerotree coding introduced by Shapiro ^{[[Shapiro93]]}, algorithms described by Said and Pearlman ^[[SP96]], Xiong et al. [XRO97], Joshi et al. ^{[[JJKFFMB95]]}, and LoPresto et al. ^[[LRC97]] appear to be converging on performance limits of wavelet image coding. These algorithms have been developed with performance as the primary goal, with complexity viewed as an important, but usually secondary consideration to be addressed after the basic algorithmic framework has been established. This does not imply that that algorithms listed above are overly complex; for example, the algorithm of Said and Pearlman involves low arithmetic complexity. However, the question still arises as to how small the sacrifice in coding performance can be made while reducing the complexity even further.

There is a very interesting and less well explored approach to wavelet image coding in which the problem can be set up as follows: Impose constraints on the arithmetic and addressing complexity, and then work to find an algorithm which optimizes the coding performance within those constraints. While the importance of low arithmetic complexity is universally appreciated, there has been less consideration given to addressing complexity. Despite the increasing capabilities of workstations and PCs which have ample resources for handling...