Vector quantization of image subbands: a survey <s> Introduction <s> A simple, nonrigorous, synthetic view of wavelet theory is presented for both review and tutorial purposes. The discussion includes nonstationary signal analysis, scale versus frequency, wavelet analysis and synthesis, scalograms, wavelet frames and orthonormal bases, the discrete-time case, and applications of wavelets in signal processing. The main definitions and properties of wavelet transforms are covered, and connections among the various fields where results have been developed are shown. > <s> BIB001 </s> Vector quantization of image subbands: a survey <s> Introduction <s> A review is presented of vector quantization, the mapping of pixel intensity vectors into binary vectors indexing a limited number of possible reproductions, which is a popular image compression algorithm. Compression has traditionally been done with little regard for image processing operations that may precede or follow the compression step. Recent work has used vector quantization both to simplify image processing tasks, such as enhancement classification, halftoning, and edge detection, and to reduce the computational complexity by performing the tasks simultaneously with the compression. The fundamental ideas of vector quantization are explained, and vector quantization algorithms that perform image processing are surveyed. > <s> BIB002 </s> Vector quantization of image subbands: a survey <s> Introduction <s> This note is a very basic introduction to wavelets. It starts with an orthogonal basis of piecewise constant functions, constructed by dilation and translation. The ``wavelet transform'' maps each $f(x)$ to its coefficients with respect to this basis. The mathematics is simple and the transform is fast (faster than the Fast Fourier Transform, which we briefly explain), but approximation by piecewise constants is poor. To improve this first wavelet, we are led to dilation equations and their unusual solutions. Higher-order wavelets are constructed, and it is surprisingly quick to compute with them --- always indirectly and recursively. We comment informally on the contest between these transforms in signal processing, especially for video and image compression (including high-definition television). So far the Fourier Transform --- or its 8 by 8 windowed version, the Discrete Cosine Transform --- is often chosen. But wavelets are already competitive, and they are ahead for fingerprints. We present a sample of this developing theory. <s> BIB003 </s> Vector quantization of image subbands: a survey <s> Introduction <s> Preface.- Suggestions to the Reader.- Symbols, Conventions, and Transforms.- Part I: Basic Wavelet Analysis. Preliminaries: Background and Notation.- Windowed Fourier Transforms.- Continuous Wavelet Transforms.- Generalized Frames: Key to Analysis and Synthesis.- Discrete Time-Frequency Analysis and Sampling.- Discrete Time-Scale Analysis.- Multiresolution Analysis.- Daubechies' Orthonormal Wavelet Bases.- Part II: Physical Wavelets.- Introduction to Wavelet Electromagnetics.- Applications to Radar and Scattering.- Wavelet Acoustics.- References.- Index. <s> BIB004
Image compression maps an original image into a bit stream suitable for communication over or storage in a digital medium. The number of bits required to represent the coded image should be smaller than that required for the original image so that one can use less storage space or communication time. There are two basic types of compression. Lossless compression, also called noiseless coding, data compaction, entropy coding, or invertible coding, refers to algorithms which allow the original pixel intensities to be perfectly recovered from the compressed representation. Lossy compression algorithms do not allow that. This paper is concerned with digital compression techniques, and if an image is analog in space and amplitude to begin with, one must rst render it discrete in both space and amplitude. Discretization in space is generally called sampling{ this consists of examining the intensity of the analog image on a regular grid of points called picture elements or pixels. Discretization in amplitude is often called quantization{ this consists of mapping a number from a continuous range of possible values into a nite set of approximating values. The term analog-to-digital (A/D) conversion is often used to mean both sampling and quantization{ that is, the conversion of a signal that is analog in both space and amplitude to a signal that is discrete in both space and amplitude. Such a conversion is by itself an example of lossy compression. A general system for digital image compression is shown in Figure 1 (a). It consists of one or more of the following operations, which may be combined with each other or with additional signal processing: Signal decomposition: The image is decomposed into several images for separate processing, typically by linear transformation by a Fourier or discrete cosine transform or by ltering with a subband or wavelet lter bank. The goal is to concentrate energy in a few coe cients, to reduce correlation, or to provide a useful data structure. Quantization: High rate digital pixel intensities are mapped into a relatively small number of symbols. This operation is nonlinear and noninvertible; it is \lossy." The conversion can operate on individual pixels (scalar quantization) or groups of pixels (vector quantization). Quantization can include throwing away some of the components of the signal decomposition step. Lossless compression: Further compression is achieved by an invertible (lossless, entropy) code such as Hu man, Lempel-Ziv, or arithmetic code. The idea here is to assign codewords with a few bits to likely symbols and codewords with more bits to unlikely symbols so that the average number of bits is minimized. Original Image A bewildering variety of image compression systems have been proposed, which involve various choices for each of the three basic components. The JPEG still-image compression standard, for example, uses a discrete cosine transform for the rst step, scalar quantization with di erent quantizer step sizes for the di erent transform coe cients in the second step, and run-length coding combined with Hu man coding for the third step, as shown in Figure 1 (b). This paper is concerned with those image compression systems that use a subband or wavelet decomposition for the rst step, some form of vector quantization for the second step, and any lossless coding (or none at all) for the third step, as shown in Figure 1 (c). We also brie y consider systems based on scalar quantization (SQ) because of its simplicity and historical importance. It also provides comparisons with the systems using vector quantization (VQ). Although SQ can be viewed as a special case of VQ with 1-D vectors, many systems using SQ are uniquely suited to 1-D vectors and do not immediately generalize to larger dimensions. This paper treats only subband/VQ systems used for image compression. Vector quantization can be used for many other types of image processing besides compression BIB002 , and subband/VQ systems can similarly be used for non-compressive purposes as well. For example, wavelet/VQ systems have been used for signature veri cation 121], for automatic target recognition from high range resolution radar returns 12], and other clustering and classi cation uses. This survey paper will not include these other uses of subband/VQ. The organization of the paper is as follows. In Section 2 we present a brief introduction to subband and wavelet image coding systems. We begin with a description of the subband decomposition. The reader is expected to be already somewhat familiar with this material, and we include it primarily to establish the notation which we will use for the remainder of the paper. For thorough introductions to subband and wavelet coding, the reader is referred to a plethora of books, tutorials, and survey articles   BIB001 BIB003  BIB004 . Section 2 also discusses some issues of entropy coding, scalar quantization, and bit allocation as they apply to subband image coding systems. Section 3 presents a brief overview of several VQ techniques that have been studied in the context of subband coding. Section 4 presents a survey of a wide variety of subband/VQ systems. Lastly, Section 5 discusses di erences between VQ applied to subband coe cients and VQ applied directly to image pixels, and o ers some conclusions. were the rst to solve the critical problem of aliasing cancellation after decimation and reconstruction in subbands, using \Quadrature mirror lters" (QMFs). The theoretical extension of subband ltering from 1-D to 2-D was made by Vetterli 147] . 2-D subband ltering was rst applied to image coding by Woods and O' Neil 156] . A subband decomposition is produced by an analysis lter bank followed by downsampling. Any or all of the resulting subbands can be further input to an analysis lter bank and downsampling operation, for as many stages as desired. Figure 2 shows one stage of such a system using 2-D separable lters. In the gure, # 2 denotes downsampling by a factor of two, H 0 denotes a low-pass lter, and H 1 denotes a high-pass lter. The initial high and low pass lters and downsampling are applied to the rows of an image. The subsequent lters and downsampling are then applied to the resulting columns. Because there are only two lters, this is called a two-channel system. Multi-channel systems have been much less explored than two-channel systems. The image is split into four bands, denoted LL, LH, HL, and HH, according to whether the rows and columns received the low-frequency or high-frequency ltering. The reconstruction operation consists of an upsampling operator followed by a synthesis lter bank, as shown in Figure 3 . One stage of reconstructing is used for each stage of decomposing. In this paper, we use the term \decomposition" to refer to the ltering and downsampling operations, for as many stages as desired. Ideally, decomposition followed by reconstruction will provide a perfect replica of the original signal. This perfect reconstruction requirement is usually built into the decomposition as a requirement if real inputs and analog arithmetic are assumed, but it is only an approximation when dealing with digital signals because of round-o error in the arithmetic. Furthermore, we are here interested in image compression, in which case the decomposed signal is compressed in a lossy fashion, typically by scalar or vector quantization. The term \encoding" refers to the combination of decomposing and quantizing, with or without subsequent entropy coding. The term \decoding" refers to the inverse operation to encoding, and so it consists of the combination of inverse quantization followed by reconstruction.