0.10 Wavelet-based signal processing and applications  (Page 11/13)

Signal and image compression

Fundamentals of data compression

From basic information theory, we know the minimum average number of bits needed to represent realizations of a independent and identically distributeddiscrete random variable $X$ is its entropy $H\left(X\right)$ [link] . If the distribution $p\left(X\right)$ is known, we can design Huffman codes or use the arithmetic coding method to achieve this minimum [link] . Otherwise we need to use adaptive method [link] .

Continuous random variables require an infinite number of bits to represent, so quantization is always necessary for practical finiterepresentation. However, quantization introduces error. Thus the goal is to achieve the best rate-distortion tradeoff [link] , [link] , [link] . Text compression [link] , waveform coding [link] and subband coding [link] have been studied extensively over the years. Here we concentrate on waveletcompression, or more general, transform coding. Also we concentrate on low bitrate.

Prototype transform coder

The simple three-step structure of a prototype transform coder is shown in [link] . The first step is the transform of the signal. For a length- $N$ discrete signal $f\left(n\right)$ , we expand it using a set of orthonormal basis functions as

where

We then use the uniform scalar quantizer $Q$ as in [link] , which is widely used for wavelet based image compression [link] , [link] ,

Denote the quantization step size as $T$ . Notice in the figure that the quantizer has a dead zone, so if $|c_i|<T$ , then $Q\left(c_i\right)=0$ . We define an index setfor those insignificant coefficients

$\mathcal{I}=\{i:|c_i|<T\}$ . Let $M$ be the number of coefficients with magnitudes greater than $T$ (significant coefficients). Thus the size of $\mathcal{I}$ is $N-M$ . The squared error caused by the quantization is

Since the transform is orthonormal, it is the same as the reconstruction error. Assume $T$ is small enough, so that the significant coefficients are uniformly distributed within each quantization bins. Then the secondterm in the error expression is

For the first term, we need the following standard approximation theorem [link] that relates it to the $l_p$ norm of the coefficients,

Theorem 56 Let $\lambda =\frac{1}{p}>\frac{1}{2}$ then

This theorem can be generalized to infinite dimensional space if ${\parallel f\parallel }_p^2<+\infty$ . It has been shown that for functions in a Besov space, ${\parallel f\parallel }_p^2<+\infty$ does not depend on the particular choice of the wavelet as long as each wavelet in the basis has $q>\lambda -\frac{1}{2}$ vanishing moments and is $q$ times continuously differentiable [link] . The Besov space includes piece-wise regular functions that may include discontinuities. This theoremindicates that the first term of the error expression decreases very fast when the number of significant coefficient increases.

The bit rate of the prototype compression algorithm can also be separated in two parts. For the first part, we need to indicate whether thecoefficient is significant, also known as the significant map. For example, we could use 1 for significant, and 0 for insignificant. We need atotal of $N$ these indicators. For the second part, we need to represent the values of the significantcoefficients. We only need $M$ values. Because the distribution of the values and the indicators arenot known in general, adaptive entropy coding is often used [link] .