Multistage storage- and entropy-constrained tree-structured vectorquantization

This paper proposes a new algorithm for the design of a tree-structured vector quantizer that operates under storage and entropy constraints; hence, it is called the storage- and entropy-constrained tree-structured vector quantizer (SECTSVQ). The algorithm uses the tree-growing approach and designs the tree one stage/layer at a time. The constraints on the rate and storage size, i.e., the number of nodes or codewords, at each stage are specified prior to the design procedure. While growing the tree, at each stage the algorithm optimally allocates the rate and the number of nodes available for the current stage to the nodes of the previous stage using the dynamic programming technique. The nodes of the current stage are then determined based on the allocations. In addition to being useful as a tree-structured VQ, SECTSVQ is particularly suited for application in progressive transmission. Moreover, the optimal allocation technique used in the design can be effectively applied to other optimal resource allocation problems. The SECTSVQ algorithm is implemented for various sources and is shown to compare favorably with other VQs     

Fast tree-structured nearest neighbor encoding for vectorquantization

This work examines the nearest neighbor encoding problem with an unstructured codebook of arbitrary size and vector dimension. We propose a new tree-structured nearest neighbor encoding method that significantly reduces the complexity of the full-search method without any performance degradation in terms of distortion. Our method consists of efficient algorithms for constructing a binary tree for the codebook and nearest neighbor encoding by using this tree. Numerical experiments are given to demonstrate the performance of the proposed method.     

A differential index assignment scheme for tree-structured vectorquantization

A differential index (DI) assignment scheme is proposed for the image encoding system in which a variable-length tree-structured vector quantizer (VLTSVQ) is adopted. Each source vector is quantized into a terminal node of VLTSVQ and each terminal node is represented as a unique binary vector. The proposed index assignment scheme utilizes the correlation between interblocks of the image to increase the compression ratio with the image quality maintained. Simulation results show that the proposed scheme achieves a much higher compression ratio than the conventional one does and that the amount of the bit rate reduction of the proposed scheme becomes large as the correlation of the image becomes large. The proposed encoding scheme can be effectively used to encode MR images whose pixel values are, in general, highly correlated with those of the neighbor pixels.     

Adaptive entropy-coded pruned tree-structured predictive vectorquantization of images

Simpler versions of a previously introduced adaptive entropy-coded predictive vector quantization (PVQ) scheme where the embedded entropy constrained vector quantizer (ECVQ) is replaced by a pruned tree-structured VQ (PTSVQ) are described. The resulting encoding scheme is shown to result in drastically reduced complexity at only a small cost in performance. Coding results for selected real-world images are given     

A unified approach to tree-structured and multistage vectorquantization for noisy channels

The large encoding complexity and sensitivity to channel errors of vector quantization (VQ) are discussed. The performance of two low-complexity VQs-the tree-structured VQ (TSVQ) and the multistage VQ (MSVQ)-when used over noisy channels are analyzed. An algorithm is developed for the design of channel-matched TSVQ (CM-TSVQ) and channel-matched MSVQ (CM-MSVQ) under the squared-error criterion. Extensive numerical results are given for the correlation coefficient 0.9. Comparisons with the ordinary TSVQ and MSVQ designed for the noiseless channel show substantial improvements when the channel is very noisy. The CM-MSVQ, which can be regarded as a block-structured combined source-channel coding scheme, is compared with a block-structured tandem source-channel coding scheme (with the same block length as the CM-MSVQ). For the Gauss-Markov source, the CM-MSVQ outperforms the tandem scheme in all cases that the authors have considered. It is demonstrated that the CM-MSVQ is fairly robust to channel mismatch     

Generalized-cost-measure-based address-predictive vectorquantization

Address-predictive vector quantization (APVQ) exploits the interblock dependency by jointly encoding the addresses of the codewords associated with spatially close blocks. It profiles the same image quality as memoryless VQ for a much lesser bit rate (BR) and the same computational complexity. In the generalized-cost-measure-based APVQ, the two steps of the encoding process, namely, VQ and predictive address encoding, are carried out jointly by minimizing a generalized cost measure, which takes into account both the BR and the distortion. Computer simulations show that a significant improvement can be obtained with respect to APVQ in terms of both BR and distortion. Compared with memoryless VQ, a bit-rate reduction of almost 60% is obtained for the same image quality.     

Variable-length Gunn oscillator

By optically controlling the position of extinction of a domain in a Gunn-effect oscillator, it has been possible to measure the domain transit time and the threshold electric field as a function of active sample length. The device resistivity profile can be obtained simultaneously.     

Variable-branch tree-structured vector quantization

Tree-structured vector quantizers (TSVQ) and their variants have recently been proposed. All trees used are fixed M-ary tree structured, such that the training samples in each node must be artificially divided into a fixed number of clusters. This paper proposes a variable-branch tree-structured vector quantizer (VBTSVQ) based on a genetic algorithm, which searches for the number of child nodes of each splitting node for optimal coding in VBTSVQ. Moreover, one disadvantage of TSVQ is that the searched codeword usually differs from the full searched codeword. Briefly, the searched codeword in TSVQ sometimes is not the closest codeword to the input vector. This paper proposes the multiclassification encoding method to select many classified components to represent each cluster, and the codeword encoded in the VBTSVQ is usually the same as that of the full search. VBTSVQ outperforms other TSVQs in the experiments presented here.     

采用通用码书实现存储受限矢量量化

针对图像源矢量量化（VQ）过程中码书储需很大空间面空间又有限的矛盾,提出了一种采用通用码书实现存储受限矢量量化（CSVQ）的解决方案。各种图像源（矢量源）所用的子码书都可从这个通用码书中提取出来,而这些子码书之间存在交集,大大节约了所需存储空间,并且,各种矢量源可以以不同的速率编码。     

Extension of two-stage vector quantization-lattice vectorquantization

This paper is the extension of two-stage vector quantization-(spherical) lattice vector quantization (VQ-(S)LVQ) recently introduced by Pan and Fischer (see IEEE Trans. Inform. Theory, vol.41, p.155, 1995). First, according to high resolution quantization theory, generalized vector quantization-lattice vector quantization (G-VQ-LVQ) is formulated in order to release the constraint of the spherical boundary for the second-stage lattice vector quantization (LVQ), which would provide possibilities of improving this kind of two-stage unstructured/structured quantizer by using more efficient LVQ. Second, among G-VQ-LVQ, vector quantization-pyramidal lattice vector quantization (VQ-PLVQ) is developed which is slightly superior or comparable to VQ-(S)LVQ in performance but has a much lower complexity. Simulation results show that for memoryless sources, VQ-PLVQ achieves a rate-distortion performance that is among the best of the fixed-rate quantization that we found in the literature. Therefore, VQ-PLVQ is an attractive alternative to VQ-(S)LVQ in practice. Third, transform VQ-PLVQ (TVQ-PLVQ) is proposed for sources with memory. For encoding 16-D vectors of the Gauss-Markov source, T-VQ-PLVQ has an advantage of close to 1.0 dB over VQ-PLVQ and is about 0.5 dB better than VQ-(S)LVQ     

Cryptanalysis of tree-structured ciphers

Tree structures have been proposed for both the construction of block ciphers by Kam and Davida (1979), and self-synchronous stream ciphers by Kuhn (1988). Attacks on these ciphers have been given by Anderson (1991), and Heys and Tavares (1993). Here the authors demonstrate that a more efficient attack can be conducted when the underlying Boolean functions for the cells are known. It is shown that this attack requires less than one third of the chosen ciphertext of Anderson's original attack on the Kuhn cipher     

Fast nearest neighbor search of entropy-constrained vectorquantization

Entropy-constrained vector quantization (ECVQ) offers substantially improved image quality over vector quantization (VQ) at the cost of additional encoding complexity. We extend results in the literature for fast nearest neighbor search of VQ to ECVQ. We use a new, easily computed distance that successfully eliminates most codewords from consideration.     

Variable-rate tree-structured vector quantizers

In general, growth algorithms for optimal tree-structured vector quantizers do not exist. In this paper we show that if the source satisfies certain conditions; namely, that of diminishing marginal returns; optimal growth algorithms do exist. We present such an algorithm and compare its performance with that of other tree growth algorithms. Even for sources that do not meet the necessary conditions for the growth algorithm to be optimal, such as for speech with unknown statistics, it is seen by simulation that the algorithm outperforms other known growth algorithms, For sources that do not satisfy the required conditions, the algorithm presented here can also be used to grow the initial tree for the pruning process. The performance of such pruned trees is superior to that of trees pruned from full trees of the same rate     

Variable-length codes and the Fano metric

It is shown that the metric proposed originally by Fano for sequential decoding is precisely the required statistic for minimum-error-probability decoding of variable-length codes. The analysis shows further that the "natural" choice of bias in the metric is the code rate and gives insight into why the Fano metric has proved to be the best practical choice in sequential decoding. The recently devised Jelinek-Zigangirov "stack algorithm" is shown to be a natural consequence of this interpretation of the Fano metric. Finally, it is shown that the elimination of the bias in the "truncated" portion of the code tree gives a slight reduction in average computation at the sacrifice of increased error probability.     

Image coding using variable-rate side-match finite-state vectorquantization

Future B-ISDN (broadband integrated services digital network) users will be able to send various kinds of information, such as voice, data, and image, over the same network and send information only when necessary. It has been recognized that variable-rate encoding techniques are more suitable than fixed-rate techniques for encoding images in a B-ISDN environment. A new variable-rate side-match finite-state vector quantization with a block classifier (CSMVQ) algorithm is described. In an ordinary fixed-rate SMVQ, the size of the state codebook is fixed. In the CSMVQ algorithm presented, the size of the state codebook is changed according to the characteristics of the current vector which can be predicted by a block classifier. In experiments, the improvement over SMVQ was up to 1.761 dB at a lower bit rate. Moreover, the improvement over VQ can be up to 3 dB at nearly the same bit rate.     

Tandem transcoding without distortion accumulation for vectorquantization

Transcoding algorithms that eliminate distortion accumulation due to tandem transcodings between memoryless, finite-state, and predictive vector quantization and pulse code modulation (PCM) are presented. The algorithms can be implemented using table lookups for memoryless and finite-state vector quantization, whereas predictive vector quantization requires online calculations. Computer simulations indicate a 6 dB improvement in the case of 16 kb/s predictive vector quantizers, 48 kb/s PCM, and four tandems for speech     

Combined compression and classification with learning vectorquantization

Combined compression and classification problems are becoming increasingly important in many applications with large amounts of sensory data and large sets of classes. These applications range from automatic target recognition (ATR) to medical diagnosis, speech recognition, and fault detection and identification in manufacturing systems. In this paper, we develop and analyze a learning vector quantization (LVQ) based algorithm for combined compression and classification. We show convergence of the algorithm using the ODE method from stochastic approximation. We illustrate the performance of the algorithm with some examples     

Wavelet-based image coding using nonlinear interpolative vectorquantization

We propose a reduced complexity wavelet-based image coding technique. Here, 64-D (for three stages of decomposition) vectors are formed by combining appropriate coefficients from the wavelet subimages, 16-D feature vectors are then extracted from the 64-D vectors on which vector quantization (VQ) is performed. At the decoder, 64-D vectors are reconstructed using a nonlinear interpolative technique. The proposed technique has a reduced complexity and has the potential to provide a superior coding performance when the codebook is generated using the training vectors drawn from similar images.     

Entropy-constrained tree-structured vector quantizer design

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.     

Unified variable-length transform coding and image-adaptive vectorquantization

The authors introduce an image coding method which unifies two image coding techniques: variable-length transform coding (VLTC) and image-adaptive vector quantization (IAVQ). In both VLTC and IAVQ, the image is first decomposed into a set of blocks. VLTC encodes each block in the transform domain very efficiently: however, it ignores the interblock correlation completely. IAVQ addresses the interblock correlation by using a codebook generated from a subset of the blocks to vector-quantize all blocks. Although the resulting codebook represents the input image better than a universal codebook generated from a large number of training images, it has to be transmitted separately as an overhead, therefore degrading the coding performance at high bit rates