A vector quantization approach to universal noiseless coding andquantization

A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that “quantizes” the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n ^-1 log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n^-1) when the universe of sources is countable, and as O(n^-1+ϵ) when the universe of sources is infinite-dimensional, under appropriate conditions     

On adaptive vector transform quantization for speech coding

Adaptive vector transform quantization (AVTQ) as a coding system is discussed. The optimal bit assignment is derived based on vector quantization asymptotic theory for different PDFs (probability density functions) of the transform coefficients. Strategies for shaping the quantization noise spectrum and for adapting the bit assignment to the changes in the speech statistics are discussed. A good estimate of the efficiency of any coding system is given by the system coding gain over scalar PCM (pulse code modulation). Based on the optimal bit allocation, the coding gain of the vector transform quantization (VTQ) system operating on a stationary input signal is derived. The VTQ coding gain demonstrates a significant advantage of vector quantization over scalar quantization within the framework of transform coding. System simulation results are presented for a first-order Gauss-Markov process and for typical speech waveforms. The results of fixed and adaptive systems are compared for speech input. Also, the AVTQ results are compared to known scalar speech coding systems     

Progressive coding and transmission of digital diagnostic pictures

In radiology, as a result of the increased utilization of digital imaging modalities, such as computed tomography (CT) and magnetic resonance imaging (MRI), over a third of the images produced in a typical radiology department are currently in digital form, and this percentage is steadily increasing. Image compression provides a means for the economical storage and efficient transmission of these diagnostic pictures. The level of coding distortion that can be accepted for clinical diagnosis purposes is not yet well-defined. In this paper we introduce some constraints on the design of existing transform codes in order to achieve progressive image transmission efficiently. The design constraints allow the image quality to be asymptotically improved such that the proper clinical diagnoses are always possible. The modified transform code outperforms simple spatial-domain codes by providing higher quality of the intermediately reconstructed images. The improvement is 10 dB for a compression factor of 256:1, and it is as high as 17.5 dB for a factor of 8:1. A novel progressive quantization scheme is developed for optimal progressive transmission of transformed diagnostic images. Combined with a discrete cosine transform, the new approach delivers intermediately reconstructed images of comparable quality twice as fast as the more usual zig-zag sampled approach. The quantization procedure is suitable for hardware implementation.     

Suboptimality of the Karhunen-Loeve transform for transform coding

We examine the performance of the Karhunen-Loeve transform (KLT) for transform coding applications. The KLT has long been viewed as the best available block transform for a system that orthogonally transforms a vector source, scalar quantizes the components of the transformed vector using optimal bit allocation, and then inverse transforms the vector. This paper treats fixed-rate and variable-rate transform codes of non-Gaussian sources. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code, and each quantized component is encoded separately. Earlier work shows that for the variable-rate case there exist sources on which the KLT is not unique and the optimal quantization and coding stage matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal quantization and coding stage matched to a "best" KLT. In this paper, we strengthen that result to show that in both the fixed-rate and the variable-rate coding frameworks there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further, we demonstrate in both frameworks that there exist sources for which even a best KLT gives suboptimal performance. Finally, we show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.     

Transform and Hybrid Transform/DPCM Coding of Images Using Pyramid Vector Quantization

The transform and hybrid transform/DPCM methods of image coding are generalized to allow pyramid vector quantization of the transform coefficients. An asymptotic mean-squared error performance expression is derived for the pyramid vector quantizer and used to determine the optimum rate assignment for encoding the various transform coefficients. Coding simulations for two images at average rates of 0.5-1 bit/pixel demonstrate a 1-3 dB improvement in signal-to-noise ratio for the vector quantization approach in the hybrid coding, with more modest improvements in signal-to-noise ratio in the transform coding. However, this improvement is quite noticeable in image quality, particularly in reducing "blockiness" in the low bit rate encoded images.     

Joint design of fixed-rate source codes and multiresolution channelcodes

We propose three new design algorithms for jointly optimizing source and channel codes. Our optimality criterion is to minimize the average end-to-end distortion. For a given channel SNR and transmission rate, our joint source and channel code designs achieve an optimal allocation of bits between the source and channel coders. Our three techniques include a source-optimized channel code, a channel-optimized source code, and an iterative descent technique combining the design strategies of the other two codes. The joint designs use channel-optimized vector quantization (COVQ) for the source code and rate compatible punctured convolutional (RCPC) coding for the channel code. The optimal bit allocation reduces distortion by up to 6 dB over suboptimal allocations and by up to 4 dB relative to standard COVQ for the source data set considered. We find that all three code designs have roughly the same performance when their bit allocations are optimized. This result follows from the fact that at the optimal bit allocation the channel code removes most of the channel errors, in which case the three design techniques are roughly equivalent. We also compare the robustness of the three techniques to channel mismatch. We conclude the paper by relaxing the fixed transmission rate constraint and jointly optimizing the transmission rate, source code, and channel code     

Fourier Transform Vector Quantization for Speech Coding

Design algorithms and simulation results are presented for vector quantizers for Fourier transformed data. Transforming the data prior to quantization has two potential advantages. First, each sample in the transform domain depends on many samples in the original domain. Thus, even scalar quantization in the transform domain is a form of vector quantization or block source coding in the original waveform domain and the basic coding theorems of information theory show that such block codes can provide better performance than scalar codes, even for memoryless sources. Second, vector quantization of Fourier transformed speech waveforms provides distinctly better subjective quality than ordinary vector quantization of the waveform using codes of comparable complexity. While the system is, of course, more complicated due to the need to take Fourier transforms, its envisioned application is as a coder for the output of FFT chips currently available or under development. The proposed implementation of a Fourier transform vector quantizer (FTVQ) uses a product code structure, providing different codes for different coefficient vectors corresponding to different frequency bands. This is a form of subband coding and yields a simple means of optimizing bit allocations among the subcodes. Two coding structures with corresponding distortion measures are considered: those that quantize vectors of pairs of real and imaginary coefficients and those that quantize separate vectors of magnitude and phase coefficients. Both structures yield good performance for the given complexity in comparison to waveform vector quantizers. For speech coding, a magnitude-phase FTVQ yields better subjective quality than a real-imaginary FTVQ when the rate allocation is properly chosen.     

基于矢量量化的层次分形编码方法

文中提出了一种新的分形图像压缩方法,该方法将矢量量化的概念应用于分形块编码中,对图像的平缓区进行矢量量化的线性组合编码,对图像的丰富细节区用分形编码,并且在分形编码时,采取了层次处理。实验表明,与基本的分形块编码方法相比,本文提出的矢量量化层次分形编码方法在保证一定的重建图像质量下,使图像的压缩比有了明显的提高,并且大大提高了编码和解码速度。     

基于BWT和FVQ的极低比特率图像编码算法

该文提出了一种基于双正交小波变换(BWT)和模糊矢量量化(FVQ)的极低比特率图像编码算法。该算法通过构造符合图像小波变换系数特征的跨频带矢量,充分利用了不同频带小波系数之间的相关性,有效地提高了图像的编码效率和重构质量。该算法采用非线性插补矢量量化(NLIVQ)的思想,从大维数矢量中提取小维数的特征矢量,并提出了一种新的模糊矢量量化方法一渐进构造模糊聚类(PCFC)算法用于特征矢量的量化,从而大大提高了矢量量化的速度和码书质量。实验结果证明,该算法在比特率为0．172bpp的条件下仍能获得PSNR＞30dB的高质量重构图像。     

基于自适应小波变换的嵌入图像压缩算法

针对遥感、指纹、地震资料等图像纹理复杂丰富、局部相关性较弱等特点,文章通过实施自适应小波变换、合理确定系数扫描次序、分类量化小波系数等措施,提出了一种高效的图像压缩编码算法.仿真结果表明,相同压缩比下,本文算法的图像复原质量明显优于SPIHT算法(特别是对于纹理图像,如标准图像Barbara).     

On color transforms and bit allocation for optimal subband image compression

Although subband transform coding is a useful approach to image compression and communication, the performance of this method has not been analyzed so far for color images, especially when the selection of color components is considered. Obviously, the RGB components are not suitable for such a compression method due to their high inter-color correlation. On the other hand, the common selection of YUV or YIQ is rather arbitrary and in most cases not optimal. In this work we introduce a rate–distortion model for color image compression and employ it to find the optimal color components and optimal bit allocation (optimal rates) for the compression. We show that the DCT (discrete cosine transform) can be used to transform the RGB components into an efficient set of color components suitable for subband coding. The optimal rates can be also used to design adaptive quantization tables in the coding stage with results superior to fixed quantization tables. Based on the presented results, our conclusion is that the new approach can improve presently available methods for color image compression and communication.     

Error-resilient pyramid vector quantization for image compression

Pyramid vector quantization (PVQ) uses the lattice points of a pyramidal shape in multidimensional space as the quantizer codebook. It is a fixed-rate quantization technique that can be used for the compression of Laplacian-like sources arising from transform and subband image coding, where its performance approaches the optimal entropy-coded scalar quantizer without the necessity of variable length codes. In this paper, we investigate the use of PVQ for compressed image transmission over noisy channels, where the fixed-rate quantization reduces the susceptibility to bit-error corruption. We propose a new method of deriving the indices of the lattice points of the multidimensional pyramid and describe how these techniques can also improve the channel noise immunity of general symmetric lattice quantizers. Our new indexing scheme improves channel robustness by up to 3 dB over previous indexing methods, and can be performed with similar computational cost. The final fixed-rate coding algorithm surpasses the performance of typical Joint Photographic Experts Group (JPEG) implementations and exhibits much greater error resilience.     

Adaptive block transform coding of speech based on LPC vectorquantization

The authors describe several adaptive block transform speech coding systems based on vector quantization of linear predictive coding (LPC) parameters. Specifically, the authors vector quantize the LPC parameters (LPCVQ) associated with each speech block and transmit the index of the code vector as overhead information. This code vector will determine the short-term spectrum of the block and, in turn, can be used for optimal bit allocation among the transform coefficients. In order to get a better estimate of the speech spectrum, the authors also consider the possibility of incorporating pitch information in the coder. In addition, entropy-coded zero-memory quantization of the transform coefficients is considered as an alternative to Lloyd-Max quantization. An adaptive BTC scheme based on LPCVQ and using entropy-coded quantizers is developed. Extensive simulations are used to evaluate the performance of this scheme     

VQ Based on a Main Feature Classification in Images

A number of algorithms have been developed for lossy image compression. Among the existing techniques, a block-based scheme is widely used because of its tractability even for complex coding schemes. Fixed block-size coding, which is the simplest implementation of block-based schemes, suffers from the nonstationary nature of images. The formidable blocking artifacts always appear at low bit rates. To suppress this degradation, variable block-size coding is utilized. However, the allowable range of sizes is still limited because of complexity issues. By adaptively representing each region by its feature, input to the coder is transformed to fixed-size (8×8) blocks. This capability allows lower cross-correlation among the regions. Input feature is also classified into the proper group so that vector quantization can maximize its strength compatible with human visual sensitivity. Bit rate based on this algorithm is minimized with the new bit allocation algorithm. Simulation results show a similar performance in terms of PSNR over conventional discrete cosine transform in conjunction with classified vector quantization.     

Embedded image coding using zerotrees of wavelet coefficients

The embedded zerotree wavelet algorithm (EZW) is a simple, yet remarkably effective, image compression algorithm, having the property that the bits in the bit stream are generated in order of importance, yielding a fully embedded code. The embedded code represents a sequence of binary decisions that distinguish an image from the “null” image. Using an embedded coding algorithm, an encoder can terminate the encoding at any point thereby allowing a target rate or target distortion metric to be met exactly. Also, given a bit stream, the decoder can cease decoding at any point in the bit stream and still produce exactly the same image that would have been encoded at the bit rate corresponding to the truncated bit stream. In addition to producing a fully embedded bit stream, the EZW consistently produces compression results that are competitive with virtually all known compression algorithms on standard test images. Yet this performance is achieved with a technique that requires absolutely no training, no pre-stored tables or codebooks, and requires no prior knowledge of the image source. The EZW algorithm is based on four key concepts: (1) a discrete wavelet transform or hierarchical subband decomposition, (2) prediction of the absence of significant information across scales by exploiting the self-similarity inherent in images, (3) entropy-coded successive-approximation quantization, and (4) universal lossless data compression which is achieved via adaptive arithmetic coding     

Time-invariant and time-varying multirate filter banks : application to image coding

This paper reviews various concepts and solutions of time-invariant and time-varying multirate filter banks. It discusses their performance for image and video coding at low bit rates, and their applicability in the mpeg-4 framework. Time-invariant multirate filter banks, and methods of design with different criteria appropriate for signal compression are first presented. Several procedures of quantization, namely scalar and lattice vector quantization, with bit allocation optimized in the rate-distortion sense, are used for the encoding of the subband signals. A technique of rate-constrained lattice vector quantization (rc-lvq), combined with a three components entropy coding, allow, together with distortion psychovi-sual weighting mechanisms to obtain significant visual improvements versus scalar quantization or the zerotree technique. However, time-invariant multirate filter banks, although efficient in terms of compression, are not well suited for content-based functionalities. Content-based features may require the ability to manipulate and thus encode a given region in the scene independently of the neighbouring regions, hence the use of transformations that can be adapted to arbitrary size bounded supports. Also, to increase the compression efficiency, one may want to adapt the transformation to the region characteristics, and thus use transform switching mechanisms, with soft or hard transitions. Three main classes of transformations can address these problems: shape-adaptive block transforms, transforms relying on signal extensions and transforms relying on time-varying multirate filter banks. These various solutions, with their methods of design, are reviewed. Emphasis is put on an extension of the SDF (symmetric delay factorization) technique which opens new perspectives in the design of time-bounded and time-varying filter banks. A region-adapted rate-distortion quantization algorithm has been used in the evaluation of the transformations compression efficiency. The coding results illustrate the interest of these techniques for compression but also for features such as quality scalability applied to selected regions of the image.     

Source-channel optimized trellis codes for bitonal imagetransmission over AWGN channels

We consider the design of trellis codes for transmission of binary images over additive white Gaussian noise (AWGN) channels. We first model the image as a binary asymmetric Markov source (BAMS) and then design source-channel optimized (SCO) trellis codes for the BAMS and AWGN channel. The SCO codes are shown to be superior to Ungerboeck's codes by approximately 1.1 dB (64-state code, 10^-5 bit error probability), We also show that a simple “mapping conversion” method can be used to improve the performance of Ungerboeck's codes by approximately 0.4 dB (also 64-state code and 10 ^-5 bit error probability). We compare the proposed SCO system with a traditional tandem system consisting of a Huffman code, a convolutional code, an interleaver, and an Ungerboeck trellis code. The SCO system significantly outperforms the tandem system. Finally, using a facsimile image, we compare the image quality of an SCO code, an Ungerboeck code, and the tandem code, The SCO code yields the best reconstructed image quality at 4-5 dB channel SNR     

On the modeling of DCT and subband image data for compression

Image subband and discrete cosine transform coefficients are modeled for efficient quantization and noiseless coding. Quantizers and codes are selected based on Laplacian, fixed generalized Gaussian, and adaptive generalized Gaussian models. The quantizers and codes based on the adaptive generalized Gaussian models are always superior in mean-squared error distortion performance but, generally, by no more than 0.08 bit/pixel, compared with the much simpler Laplacian model-based quantizers and noiseless codes. This provides strong motivation for the selection of pyramid codes for transform and subband image coding.     

Theoretical foundations of transform coding

Discusses various aspects of transform coding, including: source coding, constrained source coding, the standard theoretical model for transform coding, entropy codes, Huffman codes, quantizers, uniform quantization, bit allocation, optimal transforms, transforms visualization, partition cell shapes, autoregressive sources, transform optimization, synthesis transform optimization, orthogonality and independence, and departures form the standard model