Two-channel conjugate vector quantizer for noisy channel speechcoding

A two-channel conjugate vector quantizer is proposed in an attempt to reduce quantization distortion for noisy channels. In this quantization, two different codebooks are used. The encoder selects the channel code pair that generates the smallest distortion between the input and the averaged output vectors. These two codebooks are alternately trained by an iterative algorithm which is based on the generalized Lloyd algorithm. Coding experiments show that the proposed scheme has almost the same SNR as a conventional vector quantizer for an error-free channel. On the other hand, it has a significantly higher SNR than the conventional one for a 1% error rate. This scheme also has merits in computational complexity and storage requirements. The scheme is confirmed to be effective for a medium bit-rate speech waveform coder     

Partial distortion sensitive competitive learning algorithm foroptimal codebook design

An effective competitive learning algorithm based on the partial distortion theorem is proposed for optimal codebook design. Compared with some representative learning algorithms for codebook design, the proposed algorithm has consistently shown the best performance for designing codebooks of different sizes, especially large size codebooks     

Residual vector quantization using a multilayer competitive neuralnetwork

This paper presents a new technique for designing a jointly optimized residual vector quantizer (RVQ). In conventional stage-by-stage design procedure, each stage codebook is optimized for that particular stage distortion and does not consider the distortion from the subsequent stages. However, the overall performance can be improved if each stage codebook is optimized by minimizing the distortion from the subsequent stage quantizers as well as the distortion from the previous stage quantizers. This can only be achieved when stage codebooks are jointly designed for each other. In this paper, the proposed codebook design procedure is based on a multilayer competitive neural network where each layer of this network represents one stage of the RVQ. The weight connecting these layers form the corresponding stage codebooks of the RVQ. The joint design problem of the RVQ's codebooks (weights of the multilayer competitive neural network) is formulated as a nonlinearly constrained optimization task which is based on a Lagrangian error function. This Lagrangian error function includes all the constraints that are imposed by the joint optimization of the codebooks. The proposed procedure seeks a locally optimal solution by iteratively solving the equations for this Lagrangian error function. Simulation results show an improvement in the performance of an RVQ when designed using the proposed joint optimization technique as compared to the stage-by-stage design, where both generalized Lloyd algorithm (GLA) and the Kohonen learning algorithm (KLA) were used to design each stage codebook independently, as well as the conventional joint-optimization technique     

A fast PNN design algorithm for entropy-constrained residual vectorquantization

A clustering algorithm based on the pairwise nearest-neighbor (PNN) algorithm developed by Equitz (1989), is introduced for the design of entropy-constrained residual vector quantizers. The algorithm designs residual vector quantization codebooks by merging the pair of stage clusters that minimizes the increase in overall distortion subject to a given decrease in entropy. Image coding experiments show that the clustering design algorithm typically results in more than a 200:1 reduction in design time relative to the standard iterative entropy-constrained residual vector quantization algorithm while introducing only small additional distortion. Multipath searching over the sequence of merges is also investigated and shown experimentally to slightly improve rate-distortion performance. The proposed algorithm can be used alone or can he followed by the iterative algorithm to improve the reproduction quality at the same bit rate.     

Vector quantization using tree-structured self-organizing featuremaps

In this paper, we propose a binary-tree structure neural network model suitable for structured clustering. During and after training, the centroids of the clusters in this model always form a binary tree in the input pattern space. This model is used to design tree search vector quantization codebooks for image coding. Simulation results show that the acquired codebook not only produces better-quality images but also achieves a higher compression ratio than conventional tree search vector quantization. When source coding is applied after VQ, the new model performs better than the generalized Lloyd algorithm in terms of distortion, bits per pixel, and encoding complexity for low-detail and medium-detail images     

Hierarchical structuring of video previews by Leading-Cluster-Analysis

Clustering of shots is frequently used for accessing video data and enabling quick grasping of the associated content. In this work we first group video shots by a classic hierarchical algorithm, where shot content is described by a codebook of visual words and different codebooks are compared by a suitable measure of distortion. To deal with the high number of levels in a hierarchical tree, a novel procedure of Leading-Cluster-Analysis is then proposed to extract a reduced set of hierarchically arranged previews. The depth of the obtained structure is driven both from the nature of the visual content information, and by the user needs, who can navigate the obtained video previews at various levels of representation. The effectiveness of the proposed method is demonstrated by extensive tests and comparisons carried out on a large collection of video data.     

An optimal polygonal boundary encoding scheme in the ratedistortion sense

In this paper, we present fast and efficient methods for the lossy encoding of object boundaries that are given as eight-connect chain codes. We approximate the boundary by a polygon, and consider the problem of finding the polygon which leads to the smallest distortion for a given number of bits. We also address the dual problem of finding the polygon which leads to the smallest bit rate for a given distortion. We consider two different classes of distortion measures. The first class is based on the maximum operator and the second class is based on the summation operator. For the first class, we derive a fast and optimal scheme that is based on a shortest path algorithm for a weighted directed acyclic graph. For the second class we propose a solution approach that is based on the Lagrange multiplier method, which uses the above-mentioned shortest path algorithm. Since the Lagrange multiplier method can only find solutions on the convex hull of the operational rate distortion function, we also propose a tree-pruning-based algorithm that can find all the optimal solutions. Finally, we present results of the proposed schemes using objects from the Miss America sequence.     

A distributed algorithm of delay-bounded multicast routing formultimedia applications in wide area networks

Multicast routing is to find a tree which is rooted from a source node and contains all multicast destinations. There are two requirements of multicast routing in many multimedia applications: optimal network cost and bounded delay. The network cost of a tree is defined as the sum of the cost of all links in the tree. The bounded delay of a routing tree refers to the feature that the accumulated delay from the source to any destination along the tree shall not exceed a prespecified bound. This paper presents a distributed heuristic algorithm which generates routing trees having a suboptimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages and convergence time, and flexible in dynamic membership changes. A large amount of simulations have been done to show the network cost of the routing trees generated by our algorithm is similar to, or even better than, other existing algorithms     

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     

A successive approximation vector quantizer for wavelet transformimage coding

A coding method for wavelet coefficients of images using vector quantization, called successive approximation vector quantization (SA-W-VQ) is proposed. In this method, each vector is coded by a series of vectors of decreasing magnitudes until a certain distortion level is reached. The successive approximation using vectors is analyzed, and conditions for convergence are derived. It is shown that lattice codebooks are an efficient tool for meeting these conditions without the need for very large codebooks. Regular lattices offer the extra advantage of fast encoding algorithms. In SA-W-VQ, distortion equalization of the wavelet coefficients can be achieved together with high compression ratio and precise bit-rate control. The performance of SA-W-VQ for still image coding is compared against some of the most successful image coding systems reported in the literature. The comparison shows that SA-W-VQ performs remarkably well at several bit rates and in various test images.     

On testing trained vector quantizer codebooks

This paper discusses a criterion for testing a vector quantizer (VQ) codebook that is obtained by "training". When a VQ codebook is designed by a clustering algorithm using a training set, "time-average" distortion, which is called the training-set-distortion (TSD), is usually calculated in each iteration of the algorithm, since the input probability function is unknown in general and cumbersome to deal with. The algorithm stops when the TSD ceases to significantly decrease. In order to test the resultant codebook, validating-set-distortion (VSD) is calculated on a separate validating set (VS). Codebooks that yield small difference between the TSD and the VSD are regarded as good ones. However, the difference VSD-TSD is not necessarily a desirable criterion for testing a trained codebook unless certain conditions are satisfied. A condition that is previously assumed to be important is that the VS has to be quite large to well approximate the source distribution. This condition implies greater computational burden of testing a codebook. In this paper, we first discuss the condition under which the difference VSD-TSD is a meaningful codebook testing criterion. Then, convergence properties of the VSD, a time-average quantity, are investigated. Finally we show that for large codebooks, a VS size as small as the size of the codebook is sufficient to evaluate the VSD. This paper consequently presents a simple method to test trained codebooks for VQ's. Experimental results on synthetic data and real images supporting the analysis are also provided and discussed.     

Modified VQ-BTC algorithm for image compression

VQ-BTC is a recent technique used in the coding of image data to combat edge degradation produced by vector quantisation (VQ) or block truncation coding (BTC). However, it has high encoding complexity and needs a large amount of memory to store 31 codebooks at both the encoder and decoder. A modified VQ-BTC (MVQ-BTC) algorithm is presented which achieves a performance close to that of VQ-BTC, but needs only three codebooks, and requires less computation time than VQ-BTC     

A Near-Optimal Multiuser Joint Speech Source-Channel Resource-Allocation Scheme Over Downlink CDMA Networks

In downlink of code-division multiple-access (CDMA) networks, the maximal number of real-time calls can be increased by smoothly increasing the end-to-end distortions. In this paper, a cross-layer optimization system is developed to control each user's distortion by adapting source coding rates, channel coding rates, and transmit powers. In addition, the channel-induced distortion is controlled to be only a small proportion of the total end-to-end distortion, such that the subjective quality of the received signal is high. The formulated problem is to reduce the overall end-to-end distortion in downlink single-cell systems, under the constraints of users' maximal acceptable distortions and maximal total transmit power from the base station. To solve this problem, a near-optimal algorithm is constructed to allocate resources. A performance upper bound is developed and compared with the performance of the proposed algorithm. A dynamic system considering speech activities and different offered loads is also analyzed. From the simulation results, the proposed algorithm significantly reduces distortion and the necessary maximal transmit power when the number of users is large, compared with the traditional voice over CDMA schemes.     

Tree encoding for symmetric sources with a distortion measure

A simple algorithm is developed for mapping the outputs of a source into the set of code sequences generated by a tree code. The algorithm is analyzed for a special case in which the source produces discrete independent equiprobable letters, and the distortion measure satisfies a symmetry condition. LettingRbe the code rate andD^{ast}be the minimum average distortion for that rate as given by Shannon's rate-distortion theorem, we show that the algorithm is capable of achieving average distortion as close toD^{ast}as desired. Furthermore an upper bound is developed on the average amount of computation for the algorithm. Asymptotically as the average distortionapproaches the theoretical limitD^{ast}, the bound on average computation has the formexp [a/ sqrt{ - D^{ast} }]for some constanta.     

A transform tree code for stationary Gaussian sources

A new tree code is introduced for discrete-time stationary Gaussian sources with hounded, integrable power spectra and the squared-error distortion measure. The codewords in the tree are reconstructions of Karhunen-Loève transforms of the source words. The branching factor and the number of code letters per branch may vary with level in the tree. A theorem that guarantees the existence of an optimal code for any code rate using such a tree is proved. The proof uses the random coding argument in conjunction with a theorem on survival of a branching process with random environment. A suboptimal but computationally affordable realization of the theorem's coding technique was used for encoding simulations for six autoregressive sources at rates of1.0, 0.50, 0.25, and0.10bits per source symbol. The average distortion results were generally within1dB of the distortion-rate bound but varied widely depending on the source and rate. The results were compared with those for transform quantization simulations for the same sources and rates. The tree code always performed better but only by an average of0.44dB all sources and rates. Longer source blocks and more intensive search would certainly improve the performance of the tree codes, but at the expense of extra computation and storage.     

Voice Coding and Tree Encoding Speech Compression Systems Based Upon Inverse Filter Matching

Two speech compression systems based on codebooks of inverse filters produced by off-line linear predictive coding (LPC) and vector quantization (VQ) techniques are considered. The first system is a pitch excited vocoder that is a variation on a speech coding system based upon vector quantization. The encoder selects an LPC reverse filter from a finite codebook that best "matches" an observed frame of sampled speech. This filter is in turn used to determine the voicing and digitized pitch information. Unlike LPC systems, the digitization is performed in a single step on the data rather than separate modeling and digitization steps. The second system is a tree encoding system that uses the filter selected by an inverse filter matching vocoder to "color" a tree that is then searched for a minimum distortion path for the original sampled speech waveform. This system can be viewed as a hybrid between an adaptive predictive coder and a universal tree encoder. The two systems are described, simulated, and compared with other similar systems.     

Optimal encoding of discrete-time continuous-amplitude memoryless sources with finite output alphabets

A rate-distortion theory is introduced for the optimal encoding of stationary memoryless continuous-amplitude sources with a single-letter distortion measure and reproduction alphabets of a given finite size. The theory arises from a judicious approximation of the original continuous-input discrete-output problem by one with discrete input and output. A size-constrained output alphabet rate-distortion function is defined, its coding significance is established by coding theorems, and a convergent algorithm is presented for its evaluation. The theory is applied to Gaussian sources with squared-error distortion measure. Using the algorithm for the calculation of the new rate-distortion function in this case establishes the existence of codes which attain almost any desired rate between the rate-distortion bound and the optimum entropy-coded quantizer. Furthermore, one can closely approach the rate-distortion limit with a surprisingly small number of output levels. The calculation furnishes optimal output levels, output level probabilities, and other parameters necessary for a trellis coding simulation. The search algorithm represents the first use for asymmetric sources and distortion measures of a variation of a single stack algorithm proposed by Gallager. Carrying out the simulation at a rate of 1 bit per source symbol, codes are found with 4 and 64 output levels which attain distortions smaller than that of an optimum quantizer and close to the rate-distortion bound. Furthermore, these codes attain comparable or better performance with far less search effort than previous attempts with a continuous output alphabet.     

Uniform distribution of points on a hyper-sphere with applicationsto vector bit-plane encoding

In vector bit-plane encoding schemes, codebooks must be uniformly distributed on a hyper-sphere. Shells of regular lattices are often used, but they provide only a limited choice of number of vectors K and dimension N. The authors propose a method to generate codebooks in dimension N with arbitrary number K of vectors, almost uniformly distributed on a hyper-sphere. The uniform distribution of an arbitrary number of points on the surface of a hyper-sphere is still an open problem. Some mathematicians indeed consider it one of the mathematical challenges of the 21st century. The proposed method uses a combination of geometric and stochastic approaches to generate approximate solutions. The generated codebooks are tested in vector bit-plane encoding schemes. The results show that the proposed method is effective in generating codebooks almost uniformly distributed on a hyper-sphere     

Minimax partial distortion competitive learning for optimalcodebook design

The design of the optimal codebook for a given codebook size and input source is a challenging puzzle that remains to be solved. The key problem in optimal codebook design is how to construct a set of codevectors efficiently to minimize the average distortion. A minimax criterion of minimizing the maximum partial distortion is introduced in this paper. Based on the partial distortion theorem, it is shown that minimizing the maximum partial distortion and minimizing the average distortion will asymptotically have the same optimal solution corresponding to equal and minimal partial distortion. Motivated by the result, we incorporate the alternative minimax criterion into the on-line learning mechanism, and develop a new algorithm called minimax partial distortion competitive learning (MMPDCL) for optimal codebook design. A computation acceleration scheme for the MMPDCL algorithm is implemented using the partial distance search technique, thus significantly increasing its computational efficiency. Extensive experiments have demonstrated that compared with some well-known codebook design algorithms, the MMPDCL algorithm consistently produces the best codebooks with the smallest average distortions. As the codebook size increases, the performance gain becomes more significant using the MMPDCL algorithm. The robustness and computational efficiency of this new algorithm further highlight its advantages.     

可变尺寸块运动估计的R—D优化

本文应用率失真理论在固定码率的前提下对可变尺寸块运动估计过程进行R－D优化,获得了最佳预测块划分和最小运动补偿误差,并提出了基于树形结构的运动矢量编码方案。R－D优化问题的求解通过引入失真度－码率梯度,将R－D优化与分层运动估计结合在一起,克服了GP－BFOS算法需要对各个分块层次进行运动估计及所得局部最优解严格位于R－D曲线凸包络线上的弊病。软件模拟结果显示本算法大大降低了G－BFOS优化算法的计算量,且运动补偿RSNR值高于G－BFOS算法结果。