We investigate central issues such as invertibility, stability, synchronization, and frequency characteristics for nonlinear wavelet transforms built using the lifting framework. The nonlinearity comes from adaptively choosing between a class of linear predictors within the lifting framework. We also describe how earlier families of nonlinear filter banks can be extended through the use of prediction functions operating on a causal neighborhood of pixels. Preliminary compression results for model and real-world images demonstrate the promise of our techniques.

Summary form only given. Image compression relies on efficient representations of images, and within smooth image regions, the wavelet transform provides such a representation. However, near edges, wavelet coefficients decay slowly and are expensive to code. We focus on improving the transform by incorporating adaptivity. Construction of nonlinear filter banks has been discussed, but the question of how to utilize the nonlinearities remained. We answer this question by describing our transform via lifting. Lifting provides a spatial domain framework for the wavelet transform. In the lifting formalism, wavelet coefficients are seen as prediction residuals from a linear prediction operation. Wavelet coefficients are large near edges because the linear predictors are built to interpolate low order polynomials. Our goal is to avoid this problem by adapting the predictor based on local image properties. In smooth regions of the image, we use high order polynomial predictors. We adaptively reduce the prediction order to avoid attempting to predict values across discontinuities.

Why does fractal image compression work? What is the implicit image model underlying fractal block coding? How can we characterize the types of images for which fractal block coders will work well? These are the central issues we address. We introduce a new wavelet-based framework for analyzing block-based fractal compression schemes. Within this framework we are able to draw upon insights from the well-established transform coder paradigm in order to address the issue of why fractal block coders work. We show that fractal block coders of the form introduced by Jacquin (1992) are Haar wavelet subtree quantization schemes. We examine a generalization of the schemes to smooth wavelets with additional vanishing moments. The performance of our generalized coder is comparable to the best results in the literature for a Jacquin-style coding scheme. Our wavelet framework gives new insight into the convergence properties of fractal block coders, and it leads us to develop an unconditionally convergent scheme with a fast decoding algorithm. Our experiments with this new algorithm indicate that fractal coders derive much of their effectiveness from their ability to efficiently represent wavelet zero trees. Finally, our framework reveals some of the fundamental limitations of current fractal compression schemes.

A number of recent embedded transform coders, including Shapiro's (1993) EZW scheme, Said and Pearlman's (see IEEE Trans. Circuits and Systems for Video Technology, vol.6, no.3, p.243-250, 1996) SPIHT scheme, and Xiong et al. (see IEEE Signal Processing Letters, no.11, 1996) EZDCT scheme employ a common algorithm called significance tree quantization (STQ). Each of these coders have been selected from a large family of significance tree quantizers based on empirical work and a priori knowledge of the transform coefficient behavior. We describe an algorithm for selecting a particular form of STQ that is optimized for a given class of images. We apply our optimization procedure to the task of quantizing 8/spl times/8 DCT blocks. Our algorithm yields a fully embedded, low-complexity coder with performance from 0.7 to 2.5 dB better than baseline JPEG for standard test images.

A number of embedded transform coders, including Shapiro's (1993) EZW scheme, Said and Pearlman's (see IEEE Trans. Circuits and Systems for Video Technology, vol.6, no.3, p.243-50, 1996) SPIHT scheme, and Xiong et al.'s (see IEEE Signal Processing Letters, November 1996) EZDCT scheme employ a common algorithm called significance tree quantization (STQ). Each of these coders have been selected from a large family of significance tree quantizers based on empirical work and a priori knowledge about transform coefficient behavior. We describe an algorithm for selecting a particular form of STQ that is optimized for a given class of images. We apply our optimization procedure to the task of quantizing 8/spl times/8 DCT blocks. Our algorithm yields a fully embedded, low-complexity coder with PSNRs from 0.7 to 1.7 dB better than baseline JPEG for standard test images.

Fractal compression schemes do not fit into the standard transform coder paradigm and have proven difficult to analyze. The theory of iterated function systems motivates a broad class of fractal schemes but does not give much guidance for their implementation. We introduce a wavelet-based framework for analyzing fractal block coders which simplifies these schemes considerably. We show that fractal block coders are Haar wavelet subtree quantization schemes, and we thereby place fractal schemes in the context of conventional transform coders. We derive a wavelet-based analog of fractal compression, the self-quantization of subtrees (SQS) scheme. SQS compression outperforms the best fractal schemes in the literature by roughly 1 dB in PSNR across a broad range of compression ratios and has performance comparable to some of the best conventional wavelet schemes. We describe a fast SQS decoding scheme which suffers from none of the convergence problems of fractal decoders.

Images are usually transmitted across the Internet using a lossless protocol such as TCP/IP. Lossless protocols require retransmission of lost packets, which substantially increases transmission time. We introduce a fast lossy Internet image transmission scheme (FLIIT) for compressed images which uses forward error correction to eliminate retransmission delays. FLIIT couples an embedded quantization scheme with optimized shielding of important portions of the image. We describe a joint source and channel coding algorithm for images that minimizes the expected distortion resulting both from network packet losses and from inexact quantization of transform coefficients. The algorithm adaptively allocates quantizer resolution bits and redundancy bits to image subbands to control quantization errors and expected packet transmission losses. Our packet loss model incorporates the effects of burst losses using a Markov packet loss model with empirically derived parameters. Our preliminary results show a dramatic reduction in the amount of forward error correction needed to achieve a given expected fidelity as compared to a fixed-rate channel coding scheme.

No abstract available.

Images are usually transmitted across the Internet using a lossless protocol such as TCP/IP. Lossless protocols require retransmission of lost packets, which substantially increases transmission time. We introduce a fast lossy Internet image transmission scheme (FLIIT) for compressed images which eliminates retransmission delays by strategically shielding important portions of the image with redundancy bits. We describe a joint source and channel coding algorithm for images which minimizes the expected distortion of transmitted images. The algorithm efficiently allocates quantizer resolution bits and redundancy bits to control quantization errors and expected packet transmission losses. We describe an implementation of this algorithm and compare its performance on the Internet to lossless TCP/IP transmission of the same images. In our experiments, the FLIIT scheme transmitted images five times faster than TCP/IP during the day, with resulting images of equivalent quality. KEYWORDS fo...