Smooth wavelets, transform coding, and Markov-1 processes

This paper compares the energy compacting properties of unitary transforms from transform coders and two-band paraunitary filter banks from subband coders using a cost criterion that is proposed. Stationary processes for which paraunitary filters have better energy compaction than unitary filters are denoted as subband optimal, and all subband optimal processes are analytically characterized for the case of length-4 filters. It is shown analytically for length-4 filters and empirically for longer-length filters that Markov-1 processes are subband optimal and that the Daubechies (1988) maximally smooth wavelet sequences achieve better energy compaction than the best unitary filters for Markov-1 inputs     

Spherical Coding Algorithm for Wavelet Image Compression

In recent literature, there exist many high-performance wavelet coders that use different spatially adaptive coding techniques in order to exploit the spatial energy compaction property of the wavelet transform. Two crucial issues in adaptive methods are the level of flexibility and the coding efficiency achieved while modeling different image regions and allocating bitrate within the wavelet subbands. In this paper, we introduce the ldquospherical coder,rdquo which provides a new adaptive framework for handling these issues in a simple and effective manner. The coder uses local energy as a direct measure to differentiate between parts of the wavelet subband and to decide how to allocate the available bitrate. As local energy becomes available at finer resolutions, i.e., in smaller size windows, the coder automatically updates its decisions about how to spend the bitrate. We use a hierarchical set of variables to specify and code the local energy up to the highest resolution, i.e., the energy of individual wavelet coefficients. The overall scheme is nonredundant, meaning that the subband information is conveyed using this equivalent set of variables without the need for any side parameters. Despite its simplicity, the algorithm produces PSNR results that are competitive with the state-of-art coders in literature.     

A jointly optimized subband coder

The mainstream approach to subband coding has been to partition the input signal into subband signals and to code those signals separately with optimal or near-optimal quantizers and entropy coders. A more effective approach, however, is one where the subband coders are optimized jointly so that the average distortion introduced by the subband quantizers is minimized subject to a constraint on the output rate of the subband encoder. A subband coder with jointly optimized multistage residual quantizers and entropy coders is introduced and applied to image coding. The high performance of the coder is attributed to its ability to exploit statistical dependencies within and across the subbands. The efficiency of the multistage residual quantization structure and the effectiveness of the statistical modeling algorithm result in an attractive balance among the reproduction quality, rate, and complexity.     

Coding gain in paraunitary analysis/synthesis systems

A formal proof that bit allocation results hold for the entire class of paraunitary subband coders is presented. The problem of finding an optimal paraunitary subband coder, so as to maximize the coding gain of the system, is discussed. The bit allocation problem is analyzed for the case of the paraunitary tree-structured filter banks, such as those used for generating orthonormal wavelets. The even more general case of nonuniform filter banks is also considered. In all cases it is shown that under optimal bit allocation, the variances of the errors introduced by each of the quantizers have to be equal. Expressions for coding gains for these systems are derived     

Image coding by block prediction of multiresolution subimages

The redundancy of the multiresolution representation has been clearly demonstrated in the case of fractal images, but it has not been fully recognized and exploited for general images. Fractal block coders have exploited the self-similarity among blocks in images. We devise an image coder in which the causal similarity among blocks of different subbands in a multiresolution decomposition of the image is exploited. In a pyramid subband decomposition, the image is decomposed into a set of subbands that are localized in scale, orientation, and space. The proposed coding scheme consists of predicting blocks in one subimage from blocks in lower resolution subbands with the same orientation. Although our prediction maps are of the same kind of those used in fractal block coders, which are based on an iterative mapping scheme, our coding technique does not impose any contractivity constraint on the block maps. This makes the decoding procedure very simple and allows a direct evaluation of the mean squared error (MSE) between the original and the reconstructed image at coding time. More importantly, we show that the subband pyramid acts as an automatic block classifier, thus making the block search simpler and the block matching more effective. These advantages are confirmed by the experimental results, which show that the performance of our scheme is superior for both visual quality and MSE to that obtainable with standard fractal block coders and also to that of other popular image coders such as JPEG.     

Construction of optimal subband coders using optimized and optimalquantizers

A method is presented for the optimization of arbitrary quantizers by use of a compensating postfilter. It is shown that the resulting optimized quantizers fit the model of a linear time-invariant filter followed by additive noise uncorrelated with the input which also characterizes the optimal (Lloyd-Max) quantizers. On the basis of this model, an expression for the variance of the error of a subband coder using optimized quantizers is explicitly determined. Given analysis filters which statistically separate the subbands, it is shown that this variance is minimized if these synthesis filters are chosen, which would achieve perfect reconstruction in lossless coding. The globally optimum filter bank, minimizing the coder error variance, is further obtained by proper choice of its analysis filters. A novel method for the determination of optimal bit allocation to subbands of the filter banks with optimized quantizers is also developed. The results are evaluated experimentally by comparison of the optimum uniformly split subband image coding scheme to classical logarithmically-split filter bank (wavelet) coding methods.     

Rate-distortion-optimal subband coding withoutperfect-reconstruction constraints

We investigate the design of subband coders without the traditional perfect-reconstruction constraint on the filters. The coder uses scalar quantizers, and its filters and bit allocation are designed to optimize a rate-distortion criterion. Using convexity analysis, we show that optimality can be achieved using filterbanks that are the cascade of a (paraunitary) principal component filterbank for the input spectral process and a set of pre and postfilters surrounding each quantizer. Analytical expressions for the pre and postfilters are then derived. An algorithm for computing the globally optimal filters and bit allocation is given. We also develop closed-form solutions for the special case of two-channel coders under an exponential rate-distortion model. Finally, we investigate a constrained-length version of the filter design problem, which is applicable to practical coding scenarios. While the optimal filterbanks are nearly perfect-reconstruction at high rates, we demonstrate an apparently surprising advantage of optimal FIR filterbanks; they significantly outperform optimal perfect-reconstruction FIR filterbanks at all bit rates     

Results on principal component filter banks: colored noisesuppression and existence issues

We have made explicit the precise connection between the optimization of orthonormal filter banks (FBs) and the principal component property: the principal component filter bank (PCFB) is optimal whenever the minimization objective is a concave function of the subband variances of the FB. This explains PCFB optimality for compression, progressive transmission, and various hitherto unnoticed white-noise, suppression applications such as subband Wiener filtering. The present work examines the nature of the FB optimization problems for such schemes when PCFBs do not exist. Using the geometry of the optimization search spaces, we explain exactly why these problems are usually analytically intractable. We show the relation between compaction filter design (i.e., variance maximization) and optimum FBs. A sequential maximization of subband variances produces a PCFB if one exists, but is otherwise suboptimal for several concave objectives. We then study PCFB optimality for colored noise suppression. Unlike the case when the noise is white, here the minimization objective is a function of both the signal and the noise subband variances. We show that for the transform coder class, if a common signal and noise PCFB (KLT) exists, it is, optimal for a large class of concave objectives. Common PCFBs for general FB classes have a considerably more restricted optimality, as we show using the class of unconstrained orthonormal FBs. For this class, we also show how to find an optimum FB when the signal and noise spectra are both piecewise constant with all discontinuities at rational multiples of π     

Optimal construction of subband coders using Lloyd-Max quantizers

A new method is presented for the analysis of the effects of Lloyd-Max quantization in subband filterbanks and for the optimal design of such filterbanks. A rigorous statistical model of a vector Lloyd-Max quantizer is established first, consisting of a linear time-invariant filter followed by additive noise uncorrelated/with the input. On the basis of this model, an expression for this variance of the error of a subband coder using Lloyd-Max quantizers is explicitly determined. Given analysis filters that statistically separate the subbands, it is shown that this variance is minimized if the synthesis filters are chosen, which mould achieve perfect reconstruction in lossless coding. The globally optimum of such a filterbank, minimizing the coder error variance, is further obtained by proper choice of its analysis filters. An alternative design method is also evaluated and optimized. In this, the errors correlated with the signal are set to zero, leaving a random error residue uncorrelated with the signal. This design method is optimized by choosing the analysis filters so as to minimize the random error variance. The results are evaluated experimentally in the realistic setting of a logarithmically split subband image coding scheme.     

Performance improvement of the SPIHT coder

The set partitioning in hierarchical trees (SPIHT) coder is one of the state-of-the-art coders among the wavelet-based image compression coders. For improving the performance of the SPIHT coder, in this paper, we propose a pre-processing method that applies the discrete sine transform or the discrete cosine transform to the wavelet coefficients in the highest frequency subbands and in the next highest frequency subbands before the SPIHT encoding. Experimental results show that the proposed method increases the peak signal to noise ratio by up to 0.4 (dB) in textured images over the original SPIHT coder.     

Design of efficient M-band coders with linear-phase andperfect-reconstruction properties

This paper presents a new design technique for obtaining M-band orthogonal coders where M=2ⁱ. The structures obtained using the proposed technique have the perfect reconstruction property. Furthermore, all filters that constitute the subband coder are linear-phase FIR-type filters. In contrast with conventional design techniques that attempt to find a unitary alias-component matrix in the frequency domain, we carry out the design in the time domain, based on time-domain orthonormality constraints that the filters must satisfy. The M-band design problem is reduced to the problem of finding a suitable lowpass filter h₀(n). Once a suitable lowpass filter is found, the remaining (M-1) filters of the coder are obtained through the use of shuffling operators on the lowpass filter. This approach leads to a set of filters that use the same numerical coefficient values in different shift positions, allowing very efficient numerical implementation of the subband coder. In addition, by imposing further constraints on the lowpass branch impulse response h₀(n), we are able to construct continuous bases of M-channel wavelets with good regularity properties. Design examples are presented for four-, eight-, and 16-band coders, along with examples of continuous wavelet bases that they generate     

Efficient design of oversampled NPR GDFT filterbanks

We propose a flexible, efficient design technique for the prototype filter of an oversampled near perfect reconstruction (NPR) generalized discrete Fourier transform (GDFT) filterbank. Such filterbanks have several desirable properties for subband processing systems that are sensitive to aliasing, such as subband adaptive filters. The design criteria for the prototype filter are explicit bounds (derived herein) on the aliased components in the subbands and the output, the distortion induced by the filterbank, and the imaged subband errors in the output. It is shown that the design of an optimal prototype filter can be transformed into a convex optimization problem, which can be efficiently solved. The proposed design technique provides an efficient and effective tool for exploring many of the inherent tradeoffs in the design of the prototype filter, including the tradeoff between aliasing in the subbands and the distortion induced by the filterbank. We calculate several examples of these tradeoffs and demonstrate that the proposed method can generate filters with significantly better performance than filters obtained using current design methods.     

Digital Speech Interpolation for Variable Rate Coders with Application to Subband Coding

A theoretical method of evaluating degradations of variable rate coders in a multichannel digital speech interpolation (DSI) system is developed. Each of the coder outputs has a variable rate based on the algorithm. The DSI system multiplexes the outputs of these variable rate coders into a fixed bit rate channel. During periods of high activity all active users are served, but at a reduced rate depending on the demand. The degradation due to high activity is shared by all active users. This system avoids speech clipping and "freeze-out" distortion. Theoretical expressions of the system overload probability and the probability of degradation to a particular user in the DSI system are derived. Two types of variable rate coders, namely, a constant quality subband coder and a constant noise subband coder, are chosen and used as examples. Comparisons of the degradations are made between the theoretical results and computer simulated results for the two types of variable rate coders, and close agreement is observed. The theory is applicable to other variable rate coding algorithms as well. In this study, all of the simulations are made at 40 percent speech activity and the average rate of the variable rate coders is close to 16 kbits/s. Objective quality measures indicate that in a system with a trunk size larger than 40, the variable rate coder DSI system can achieve a 2:1 compression with a degradation of less than 1 dB compared to non-DSI variable rate coders. This corresponds to a total gain of 8:1 when compared to 64 kbit/s PCM.     

Orthonormal and biorthonormal filter banks as convolvers, andconvolutional coding gain

Convolution theorems for filter bank transformers are introduced. Both uniform and nonuniform decimation ratios are considered, and orthonormal as well as biorthonormal cases are addressed. All the theorems are such that the original convolution reduces to a sum of shorter, decoupled convolutions in the subbands. That is, there is no need to have cross convolution between subbands. For the orthonormal case, expressions for optimal bit allocation and the optimized coding gain are derived. The contribution to coding gain comes partly from the nonuniformity of the signal spectrum and partly from nonuniformity of the filter spectrum. With one of the convolved sequences taken to be the unit pulse function,,e coding gain expressions reduce to those for traditional subband and transform coding. The filter-bank convolver has about the same computational complexity as a traditional convolver, if the analysis bank has small complexity compared to the convolution itself     

New directions in subband coding

Two very different subband coders are described. The first is a modified dynamic bit-allocation-subband coder (D-SBC) designed for variable rate coding situations and easily adaptable to noisy channel environments. It can operate at rates as low as 12 kb/s and still give good quality speech. The second coder is a 16-kb/s waveform coder, based on a combination of subband coding and vector quantization (VQ-SBC). The key feature of this coder is its short coding delay, which makes it suitable for real-time communication networks. The speech quality of both coders has been enhanced by adaptive postfiltering. The coders have been implemented on a single AT&T DSP32 signal processor     

Invertible temporal subband/wavelet filter banks with half-pixel-accurate motion compensation

Three-dimensional (3-D) subband/wavelet coding with motion compensation has been demonstrated to be an efficient technique for video coding applications in some recent research works. When motion compensation is performed with half-pixel accuracy, images need to be interpolated in both temporal subband analysis and synthesis stages. The resulting subband filter banks developed in these former algorithms were not invertible due to image interpolation. In this paper, an invertible temporal analysis/synthesis system with half-pixel-accurate motion compensation is presented. We look at temporal decomposition of image sequences as a kind of down-conversion of the sampling lattices. The earlier motion-compensated (MC) interlaced/progressive scan conversion scheme is extended for temporal subband analysis/synthesis. The proposed subband/wavelet filter banks allow perfect reconstruction of the decomposed video signal while retaining high energy compaction of subband transforms. The invertible filter banks are then utilized in our 3-D subband video coder. This video coding system does not contain the temporal DPCM loop employed in the conventional hybrid coder and the earlier MC 3-D subband coders. The experimental results show a significant PSNR improvement by the proposed method. The generalization of our algorithm for MC temporal filtering at arbitrary subpixel accuracy is also discussed.     

Optimal pyramidal and subband decompositions for hierarchicalcoding of noisy and quantized images

Optimal hierarchical coding is sought, for progressive or scalable image transmission, by minimizing the variance of the error difference between the original image and its lower resolution renditions. The optimal, according to the above criterion, pyramidal and subband image coders are determined for images subject to corruption by quantization or transmission noise. Given arbitrary analysis filters and assuming adequate knowledge of the noise statistics, optimal synthesis filters are found. The optimal analysis filters are subsequently determined, leading to formulas for globally optimal structures for pyramidal and subband image decompositions. Experimental results illustrate the implementation and performance of the optimal coders.     

A generalized Lloyd-type algorithm for adaptive transform coder design

In this paper, we establish a probabilistic framework for adaptive transform coding that leads to a generalized Lloyd type algorithm for transform coder design. Transform coders are often constructed by concatenating an ad hoc choice of transform with suboptimal bit allocation and quantizer design. Instead, we start from a probabilistic latent variable model in the form of a mixture of constrained Gaussian mixtures. From this model, we derive an transform coder design algorithm, which integrates optimization of all transform coder parameters. An essential part this algorithm is our introduction of a new transform basis-the coding optimal transform-which, unlike commonly used transforms, minimizes compression distortion. Adaptive transform coders can be effective for compressing databases of related imagery since the high overhead associated with these coders can be amortized over the entire database. For this work, we performed compression experiments on a database of synthetic aperture radar images. Our results show that adaptive coders improve compressed signal-to-noise ratio (SNR) by approximately 0.5 dB compared with global coders. Coders that incorporated the coding optimal transform had the best SNRs on the images used to develop the coder. However, coders that incorporated the discrete cosine transform generalized better to new images.     

小波图像的膨胀-游程编码算法

提出了一种基于形态膨胀运算和游程编码的新型小波编码器膨胀-游程(Dilation-Run)算法。编码器根据图像小波变换后重要系数的带内聚类特性和重要系数分布的带间相似性,利用数学形态学中的膨胀运算搜索并编码各聚类中的重要系数;同时使用一种高效的游程编码技术对各聚类的种子系数,即膨胀运算起始点的位置进行编码,从而避免了小波图像中非重要系数的逐个编码。编码器算法简单,并且基于位平面实现,因此输出码流具有渐进性。实验结果表明,膨胀-游程算法的性能优于零树小波编码器SPIHT,并能与两种形态学小波编码器MRWD 和SLCCA的性能媲美。对于聚类特性显著的图像,算法的性能则优于上述形态学小波编码器。     

Unequal error protection for MPEG-2 video transmission over wireless channels

This paper proposes an unequal error protection (UEP) method for MPEG-2 video transmission. Since the source and channel coders are normally concatenated, if the channel is noisy, more bits are allocated to channel coding and fewer to source coding. The situation is reversed when the channel conditions are more benign. Most of the joint source channel coding (JSCC) methods assume that the video source is subband coded, the bit error sensitivity of the source code can be modeled, and the bit allocations for different subband channels will be calculated. The UEP applied to different subbands is the rate compatible punctured convolution channel coder. However, the MPEG-2 coding is not a subband coding, the bit error sensitivity function for the coded video can no longer be applied. Here, we develop a different method to find the rate-distortion functions for JSCC of the MPEG-2 video. In the experiments, we show that the end-to-end distortion of our UEP method is smaller than the equal error protection method for the same total bit-rate.