Block prediction and reference frame generation play a central role in contemporary video codecs and hold significant potential for improving compression efficiency. For motion vectors of varying reliability, directly averaging the bi-directional reference blocks introduces noise in block prediction. In advanced video codecs such as AV2, the generation of co-located reference frames (CLRFs) within the temporal interpolated prediction (TIP) module is also performed at the block level. However, the imprecise vectors in the motion field cause the associated block pairs to exhibit weak correlation in their high-frequency components, which is not addressed by existing methods. This creates an opportunity for the transformdomain temporal prediction (TDTP) approach. This work proposes an adaptive TDTP framework for block prediction. Independent linear predictors (LPs) are trained for each AC coefficient to estimate the corresponding temporal correlation. A novel adaptive backward updating scheme for linear predictors is employed, in which reconstructed blocks are used to update the statistics and refine LP parameters without introducing additional bitrate overhead. Simulation results on the TIP module in AV2 demonstrate that the proposed approach effectively adapts to frame statistics and enhances the efficiency of compound inter-prediction.

The challenge of coding delay is becoming increasingly recognized as a barrier to the broader implementation of Higher Order Ambisonics (HOA), which is a highly flexible format for spatial audio encoding and reproduction. A low latency is essential for various applications, such as virtual reality, interactive gaming, and live online music sessions. Unfortunately, significant strides in the development of spatial audio codecs often compromise on latency to enhance compression efficiency. This work presents a low-delay codec designed for the compression of HOA signals. The codec uses a combination of singular value decomposition, short-term linear prediction, cascaded long-term prediction, and sub-band coding, as well as entropy coding, in order to maximally compress HOA signals while maintaining a low delay. A variety of configurations allow for algorithmic delays between 54 samples to 206 samples, at the cost of bitrate given a fixed quality level. The proposed codec outperforms the low-delay implementation of a standard codec for HOA lossy compression, both in terms of delay and bitrate at medium and higher quality levels.

This paper proposes an effective universal (on-the-Hy’’ mechanism for stochastic codebook generation in lossy coding of Markov sources. Earlier work has shown that the ratedistortion bound can be asymptotically achieved by a “natural type selection” (NTS) mechanism that iteratively considers asymptotically long source strings (from an unknown distribution P) and regenerates the codebook from a distribution obtained within a maximum likelihood distribution estimation framework, based on observation of a set of K codewords that “d-match’’ (i.e., satisfy the distortion constraint for) a respective set of K independently generated source words. This result was later generalized, in a straightforward manner, to account for source memory, by considering the source as a vector source, i.e., a sequence of super-symbols from a corresponding super-alphabet. While ensuring asymptotic optimality, this extension suffered from a significant practical flaw: it requires asymptotically long vectors or super-symbols, hence exponentially large super-alphabet, in order to approach the rate-distortion bound, even for finite memory sources, e.g., Markov sources. Such exponentially large super-alphabet implies that even a single NTS iteration is intractable, thus compromising the promise of NTS to approach the rate-distortion function, in practice, for sources with memory. This work describes a considerably more efficient and tractable mechanism to achieve asymptotically optimal performance given a prescribed memory constraint, within a practical framework tailored to Markov sources. Specifically, the algorithm finds, asymptotically, the optimal codebook reproduction distribution, within a constrained set of distributions satisfying a prescribed Markovian property, e.g., of the same order as the source, which achieves the minimum per letter coding rate while maintaining a specified distortion level.

Current video coders employ motion compensated pixel-to-pixel prediction, which largely ignores significant spatial correlations and the fact that true temporal correlations vary with spatial frequency. Earlier work from our lab proposed to first spatially decorrelate the block of pixels by performing temporal prediction in the transform domain, and to effectively account for both spatial and temporal correlations. To adapt to variations in video signal statistics, the encoder switches between a set of appropriately designed prediction modes.This setting critically depends on efficient offline learning of transform domain temporal prediction modes. Significant challenges include: i) issues of instability and mismatched statistics inherent to closed loop design; and ii) severe non-convexity of the cost function trapping the system in poor local minima. Statistics mismatch is tackled by an appropriate paradigm for system design in a stable open loop fashion, but which asymptotically mimics closed loop operation. The non-convexity is handled by deterministic annealing, a powerful non-convex optimization tool whose probabilistic formulation allows for direct optimization of the cost function with respect to the discrete set of prediction modes, and whose annealing schedule avoids poor local minima. Experimental results validate the method's efficacy.

This paper proposes a multi-layer multi-reference prediction framework for effective video compression. Current AOM/AV1 baseline uses three reference frames for the inter prediction of each video frame. This paper first presents a new coding tool that extends the total number of reference frames in both forward and backward prediction directions. A multi-layer framework is then described, which suggests the encoder design and places different reference frames within one Golden Frame (GF) group to different layers. The multi-layer framework leverages the existing coding tools in the AV1 baseline, including the tool of "show_existing_frame" and the reference frame buffer update module of a wide flexibility. The use of extended ALTREF_FRAMEs is proposed, and multiple ALTREF_FRAME candidates are selected and widely spaced within one GF group. ALTREF_FRAME is a constructed, no-show reference obtained through temporal filtering of a look-ahead frame. In the multi-layer structure, one reference frame may serve different roles for the encoding of different frames through the virtual index manipulation. The experimental results have been collected over several video test sets of various resolutions and characteristics both texture- and motion-wise, which demonstrate that the proposed approach achieves a consistent coding gain compared to the AV1 baseline. For instance, using PSNR as the distortion metric, an average bitrate saving of 5.57+% in BDRate is obtained for the CIF-level resolution set, some of which has a gain of up to 13+%, and 4.47% on average for the VGA-level resolution set, some of which up to 18+%.

Conventional video coders rely heavily on pixel-domain block matching to remove temporal redundancies. This prediction structure constrains pixels within a block to use the same motion vector, which is ineffective for blocks with complex motion. To mitigate this shortcoming we recently proposed a new paradigm of adaptive interpolated motion compensation (AIMC), wherein neighboring motion vectors are considered as pointers to multiple estimation sources, which are linearly combined to form the final prediction, with weights chosen from pre-trained K-sets to capture variations in statistics. While promising initial results were obtained for fixed block sizes, this paper extends the approach to the important setting of variable block size partitioning, which has become standard in state-of-the-art video coding. Specifically, we propose a non-trivial generalization of AIMC to account for arbitrary block partitioning by “virtually” breaking a block to match its non-causal neighbors, and creating an interpolation tree structure, whose nodes extend from the original partitioning. This provides multiple estimates at the leaf nodes of the tree and enables an effective AIMC implementation. Experimental results validate the proposed paradigm with significant bit rate savings over conventional motion compensated prediction.

Multimedia content is required at different quality levels due to heterogeneous network conditions and diverse consumption devices. A conventional scalable coder generates a layered bitstream, wherein a base layer produces a coarse reconstruction, and successive layers refine the quality, incrementally. However most multimedia sources are not successively refinable under their relevant distortion metrics. When a source is not successively refinable, conventional scalable coding introduces a performance penalty, while at the other extreme, independent coding is clearly wasteful in resources. As an alternative, we recently proposed a framework with a relaxed hierarchical structure to separate and transmit information common to different quality levels, along with individual bitstreams for each quality level. This framework offers the exibility to operate at various tradeoff points between conventional scalable coding and independent coding.In this paper we propose a technique to jointly design scalar quantizers acrosslayers of this framework, while focusing on the setting of two quality levels. We need three layers for two quality levels, one common layer sent to both receivers and two individual layers, which refine the common layer to two different required quality levels. We propose an iterative approach for designing the three scalar quantizers, wherein at each iteration one quantizer's intervals are updated to minimize the overall cost function while the others are fixed, and the iterations are repeated until convergence. Given the common layer quantizer intervals, for each of the individual layer, refining quantizers for all the intervals of the common layer are jointly designed to minimize the overall cost function. We also develop (\Lloyd algorithm style") optimal interval update rules for the common layer quantizer that minimizes the overall cost while accounting for the current individual layer quantizers.We provide experimental results for Laplacian sources, as many practical applications, model multimedia sources by the Laplacian distribution. The results clearly demonstrate that, by exploiting the concept of common information, the proposed approach can achieve all intermediate operating points at considerably better performance compared to the convex hull between non-scalable and scalable coding. Also we obtain interesting operating points, with distortions very close to non-scalable coding, but with a 14% reduction in total transmit rate compared to non-scalable coding.In this paper we propose a technique to jointly design scalar quantizers across layers of this framework, while focusing on the setting of two quality levels. We need three layers for two quality levels, one common layer sent to both receivers and two individual layers, which refine the common layer to two different required quality levels. We propose an iterative approach for designing the three scalar quantizers, wherein at each iteration one quantizer's intervals are updated to minimize the overall cost function while the others are fixed, and the iterations are repeated until convergence. Given the common layer quantizer intervals, for each of the individual layer, refining quantizers for all the intervals of the common layer are jointly designed to minimize the overall cost function. We also develop (“Lloyd algorithm style”) optimal interval update rules for the common layer quantizer that minimizes the overall cost while accounting for the current individual layer quantizers. We provide experimental results for Laplacian sources, as many practical applications, model multimedia sources by the Laplacian distribution. The results clearly demonstrate that, by exploiting the concept of common information, the proposed approach can achieve all intermediate operating points at considerably better performance compared to the convex hull between non-scalable and scalable coding. Also we obtain interesting operating points, with distortions very close to non-scalable coding, but with a 14% reduction in total transmit rate compared to non-scalable coding.

The hidden Markov model (HMM) is widely used to model processes in several real world applications, including speech processing and recognition, image understanding and sensor networks. A problem of concern is that of quantization of the sequence of observations generated by an HMM, which is referred as a hidden Markov source (HMS). Despite the importance of the problem, and the well-defined structure of the process, there has been very limited work addressing the optimal quantization of HMS, and conventional approaches focus on optimization of parameters of known quantization schemes. This paper proposes a method that directly tracks the state probability distribution of the underlying source and optimizes the encoder structure according to the estimated HMS status. Unlike existing approaches, no stationarity assumption is needed, and code parameters are updated on they: with each observation, both the encoder and the decoder refine the estimated probability distribution over the states. The main approach is then specialized to a practical variant involving switched quantizers, and an algorithm that iteratively optimizes the quantize codebooks is derived. Numerical results show superiority of the proposed approach over prior methods.

Randomized (dithered) quantization is a method capable of achieving white reconstruction error independent of the source. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization. In this paper we extend conventional dithered quantization to nonuniform quantization, via a subterfage: dithering is performed in the companded domain. Closed form necessary conditions for optimality of the compressor and expander mappings are derived for both fixed and variable rate randomized quantization. Numerically, mappings are optimized by iteratively imposing these necessary conditions. The resulting quantizer renders the reconstruction error white with negligible performance loss compared to the optimal quantizer. The framework is extended to include an explicit constraint that deterministic or randomized quantizers yield reconstruction error that is uncorrelated with the source. Surprising theoretical results show direct and simple connection between the optimal constrained quantizers and their unconstrained counterparts. Numerical results for the Gaussian source provide strong evidence that the proposed constrained randomized quantizer outperforms the conventional dithered quantizer, as well as the constrained deterministic quantizer.

This paper is concerned with transform coding of correlated sources in conjunction with variable rate quantization at high resolution. The approach builds on our prior work on optimality conditions for transform coding in the point-to-point setting. The first contribution involves transform coding with decoder side information. In this setting, side information is only available to the decoder, whereas the encoder knows the joint statistics. The necessary and sufficient condition for optimality of a unitary transform in the side information setting is derived, namely, such transform minimizes a conditional divergence-based measure of inter-dependence of the transform coefficients, given the side information. This optimality result subsumes prior, known results that were restricted to the Gaussian case, where the conditional Karhunen-Loeve transform is optimal. The second contribution involves distributed transform coding, where two correlated sources are to be transform coded separately, but decoded jointly. The necessary and sufficient condition for optimality of unitary transforms in the distributed coding setting is derived. It is then specialized to produce closed form optimal transforms for specific source densities, including the case of jointly Gaussian sources.

We consider approaches for similarity search in correlated, high-dimensional data sets, which are derived within a clustering framework. We note that indexing by “vector approximation” (VA-File), which was proposed as a technique to combat the “Curse of Dimensionality,” employs scalar quantization, and hence necessarily ignores dependencies across dimensions, which represents a source of suboptimality. Clustering, on the other hand, exploits interdimensional correlations and is thus a more compact representation of the data set. However, existing methods to prune irrelevant clusters are based on bounding hyperspheres and/or bounding rectangles, whose lack of tightness compromises their efficiency in exact nearest neighbor search. We propose a new cluster-adaptive distance bound based on separating hyperplane boundaries of Voronoi clusters to complement our cluster based index. This bound enables efficient spatial filtering, with a relatively small preprocessing storage overhead and is applicable to euclidean and Mahalanobis similarity measures. Experiments in exact nearest-neighbor set retrieval, conducted on real data sets, show that our indexing method is scalable with data set size and data dimensionality and outperforms several recently proposed indexes. Relative to the VA-File, over a wide range of quantization resolutions, it is able to reduce random IO accesses, given (roughly) the same amount of sequential IO operations, by factors reaching 100X and more.

This paper focuses on optimal analog mappings for zero-delay, distributed source-channel coding. The objective is to obtain the optimal vector transformations that map between m-dimensional source spaces and k-dimensional channel spaces, subject to a prescribed power constraint and assuming the mean square error distortion measure. Closed-form necessary conditions for optimality of encoding and decoding mappings are derived. An iterative de- sign algorithm is proposed, which updates encoder and decoder mappings by sequentially enforcing the complementary optimality conditions at each iteration. The obtained encoding functions are shown to be a continuous relative of, and in fact subsume as a special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems, by mapping multiple source intervals to the same channel interval. Example mappings and performance results are presented for Gaussian sources and channels.

Current video coding schemes employ motion compensation to exploit the fact that the signal forms an auto-regressive process along the motion trajectory, and remove temporal redundancies with prior reconstructed samples via prediction. However, the decoder may, in principle, also exploit correlations with received encoding information of future frames. In contrast to current decoders that reconstruct every block immediately as the corresponding quantization indices are available, we propose an estimation-theoretic delayed decoding scheme which leverages quantization and motion information of one or more future frames to refine the reconstruction of the current block. The scheme, implemented in the transform domain, efficiently combines all available (including future) information in an appropriately derived conditional pdf, to obtain the optimal delayed reconstruction of each transform coefficient in the frame. Experiments demonstrate substantial gains over the standard H.264 decoder. The scheme learns the autoregressive model from information available to the decoder, and compatibility with the standard syntax and existing encoders is retained.

This paper is concerned with optimal transform coding in conjunction with dithered quantization. While the optimal deterministic quantizer's error is uncorrelated with the reconstructed value, the dithered quantizer yields quantization errors that are correlated with the reconstruction but are white and independent of the source. These properties offer potential benefits, but also have implications on the optimization of the rest of the coder. We derive the optimal transform for consequent dithered quantization. For fixed rate coding, we show that the transform derived for dithered quantization is universally optimal (for all sources), unlike the conventional quantization case where optimality of the Karhunen-Loeve transform is guaranteed for Gaussian sources. Moreover, we establish variable rate coding optimality for Gaussian sources.

Summary form only given: Dithered quantization has useful properties such as producing quantization noise independent of the source and continous reconstruction at the decoder side. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization framework. A uniformly distributed (with step size matched to the quantization interval) dither signal is added before quantization and the same dither signal is subtracted from the quantized value at the decoder side (only subtractive dithering is considered in this paper). The quantized values are entropy coded conditioned on the dither signal. This work proposes and analyzes optimal (non-uniform) dithered quantization. One immediate problem with nonuniform dithered quantization is how to apply dithering for unequal quantization intervals. This problem is circumvented by performing dithering in the companded domain. After appropriate companding, uniform dither can be applied. The quantization problem is defined as finding the optimal compander mapping that minimizes the mean square error. To solve the problem, some approximations of rate and distortion expressions and to the compander mapping are used. First, we only consider the piecewise linear compander which is also used in deterministic quantizers. Also, we assume the error in each half quantization interval (the interval between the decision boundary and the reconstruction) is constant and only a function of the intervals length, i.e., identical to the case where for each interval a uniform dithered quantizer is applied. We also assume that rate can be approximated by the rate of the deterministic quantizer which uses the same compander. We derive the necessary conditions for optimality and design the compander by iterating between the necessary conditions.

Motivated by the paradigm of event-based monitoring, which can potentially alleviate the inherent bandwidth and energy constraints associated with wireless sensor networks, we consider the problem of joint coding of correlated sources under a cost criterion that is appropriately conditioned on event occurrences. The underlying premise is that individual sensors only have access to partial information and, in general, cannot reliably detect events. Hence, sensors optimally compress and transmit the data to a fusion center, so as to minimize the expected distortion in segments containing events. In this work, we derive and demonstrate the approach in the setting of entropy constrained distributed vector quantizer design,using a modified distortion criterion that appropriately accounts for the joint statistics of the events and the observation data. Simulation results show significant gains over conventional design as well as existing heuristic based methods, and provide experimental evidence to support the promise of our approach.

Motivated by sensor networks, we consider the fusion storage of correlated sources in a database, such that any subset of them may be efficiently retrieved in the future. Only statistical information about future queries is available during encoding and storage. Fusion coding of correlated sources poses new challenges due to the conflicting objectives of exploiting inter-source correlations and enabling efficient selective retrieval. Practical signal compression imposes additional constraints on system complexity. We propose a shared-descriptions approach for the design of lossy fusion coding systems, to manage the precise tradeoffs between storage rate, retrieval rate, distortion and system complexity, within one unified framework. An iterative descent algorithm is derived for the design of such fusion coders. The optimized system provides significant gains over traditional quantization techniques that are not directly optimized for fusion coding.

This paper considers the problem of distributed scalable coding of correlated sources that are communicated to a central unit. The general setting is typically encountered in sensor networks. The conditions of communication channels between the sensor sources and fusion center may be time-varying and it is often desirable to guarantee a base layer of coarse information during channel fades. Specifically, we consider a multi-stage coding system to perform such distributed scalable coding of correlated sources. This problem poses new challenges. We show that mere extensions of distributed coding ideas to include multi-stage coding yield poor rate-distortion performance, due to underlying conflicts between the objectives of scalable and distributed coding. An appropriate system paradigm is developed which allows such tradeoffs to be explicitly controlled within joint optimization of all the system components. We propose an iterative joint design technique and derive the necessary conditions for optimality which yield its update rules. Simulation results show substantial gains over single source (separate) multi-stage coding as well as naive extensions to incorporate scalability in distributed scalable coding schemes.

This paper considers the design of efficient quantizers for a distributed source coding system. The information is encoded at independent terminals and transmitted across separate channels, any of which may fail. The scenario subsumes a wide range of vector quantization problems. Greedy descent methods rely heavily on initialization, and the presence of numerous 'poor' local optima on the distortion cost surface strongly motivates the use of a global design algorithm. We propose a deterministic annealing approach for the design of all components of a generic distributed source coding system. Our approach avoids many poor local optima, is independent of initialization, and does not assume any prior information on the underlying source distribution. Simulation results show significant gains over an iterative greedy algorithm.

This paper presents an algorithm to optimize the tradeoff between rate and expected end-to-end distortion of a video sequence transmitted over a packet network. The approach optimizes the source coding parameters, slicing, network QoS class selection and/or error control coding parameters, and accounts for the effects of compression, packetization, error propagation, and concealment at the decoder. It builds on, and substantially extends the applicability of, the recursive optimal per-pixel estimate (ROPE) technique for end-to-end distortion estimation. A trellis-based algorithm is introduced in order to overcome macroblock interdependencies in the estimation procedure, and allow adaptive slicing. Moreover, we propose a complementary packetization scheme to efficiently arrange the slices into packets for FEC protection while minimizing rate loss due to padding. Simulations demonstrate consistent gains over currently used techniques.

Let finite source and reproduction alphabets X and Y and a distortion measure d: X/spl times/Y/spl rarr/[0,/spl infin/) be given. We study the minimum asymptotic rate required to describe a source distributed over X within a (given) distortion threshold D at every sample. The problem is hence a min-max problem, and the distortion measure is extended to vectors as follows: for x/sup n//spl isin/X/sup n/, y/sup n//spl isin/Y/sup n/, d(x/sup n/, y/sup n/)=max/sub i/d(x/sub i/, y/sub i/). In the graph-theoretic formulation we introduce, a code for the problem is a dominating set of an equivalent distortion graph. We introduce a linear programming lower bound for the minimum dominating set size of an arbitrary graph, and show that this bound is also the minimum asymptotic rate required for the corresponding source. Turning then to the optimality of scalar coding, we show that scalar codes are asymptotically optimal if the underlying graph is either an interval graph or a tree.

We derive an asymptotically optimal multi-layer coding scheme for entropy-coded scalar quantizers (SQ) that minimizes the weighted mean-squared error (WMSE). The optimal entropy-coded SQ is non-uniform in the case of WMSE. The conventional multi-layer coder quantizes the base-layer reconstruction error at the enhancement-layer, and is sub-optimal for the WMSE criterion. We consider the compander representation of the quantizer, and propose to implement scalability in the compressed domain. We show that such a multi-layer coding system achieves the operational rate-distortion bound given by the non-scalable entropy-coded SQ, at the limit of high resolution. Simulation results for a synthetic memoryless Laplace source with /spl mu/-law companding are presented for various values of layer rates. Substantial gains are also achieved on the "real-world" sources of audio signals, when the optimal multi-layer approach is applied to a two-layer scalable MPEG-4 Advanced Audio Coder.

The design of predictive quantizers generally suffers from difficulties due to the prediction loop, which have an impact on the convergence and the stability of the design procedure. We previously proposed an asymptotically closed-loop approach to quantizer design for predictive coding applications, which benefits from the stability of open-loop design while asymptotically optimizing the actual closed-loop system. In this paper, we present an enhancement to the approach where joint optimization of both predictor and quantizer is performed within the asymptotically closed-loop framework. The proposed design method is tested on synthetic sources (first-order Gauss and Laplacian-Markov sequences), and on natural sources, in particular, line spectral frequency parameters of speech signals.

Robustness to packet loss is a critical requirement for video communication over packet switched networks. Intra-coding is an important tool to mitigate the effects of packet loss by limiting error propagation. This work proposes an algorithm for intra/inter coding mode selection, while utilizing the feedback channel that carries acknowledgement information about received packets. The overall distortion in frame reconstruction at the decoder due to quantization, error concealment (after packet loss) and error propagation is estimated at pixel-level precision, and is dynamically refined based on the feedback information. The estimate is then integrated into a rate-distortion (RD) framework for optimal selection of coding mode for each macroblock. Simulation results demonstrate that precise distortion estimation enables the coder to achieve substantial and consistent gain in PSNR over known state-of-the-art feedback-based mode selection modes.

We attack the problem of robust and efficient image compression for transmission over noisy channels. To achieve the dual goals of high compression efficiency and low sensitivity to channel noise we introduce a multimode coding framework. Multimode coders are quasi-fixed length in nature, and allow optimization of the tradeoff between the compression capability of variable-length coding and the robustness to channel errors of fixed length coding. We apply our framework to develop multimode image coding (MIC) schemes for noisy channels, based on the adaptive DCT. The robustness of the proposed MIC is further enhanced by the incorporation of a channel protection scheme suitable for the constraints on complexity and delay. To demonstrate the power of the technique we develop two specific image coding algorithms optimized for the binary symmetric channel. The first, MIC1, incorporates channel optimized quantizers and the second, MIC2, uses rate compatible punctured convolutional codes within the multimode framework. Simulations demonstrate that the multimode coders obtain significant performance gains of up to 6 dB over conventional fixed length coding techniques.

Many compression applications consist of compressing multiple sources with significantly different distributions. In the context of vector quantization (VQ) these sources are typically quantized using separate codebooks. Since memory is limited in most applications, a convenient way to gracefully trade between performance and storage is needed. Earlier work addressed this problem by clustering the multiple sources into a small number of source groups, where each group shares a codebook. As a natural generalization, we propose the design of a size-limited universal codebook consisting of the union of overlapping source codebooks. This framework allows each source codebook to consist of any desired subset of the universal codevectors and provides greater design flexibility which improves the storage-constrained performance. Further advantages of the proposed approach include the fact that no two sources need be encoded at the same rate, and the close relation to universal, adaptive, and classified quantization. Necessary conditions for optimality of the universal codebook and the extracted source codebooks are derived. An iterative descent algorithm is introduced to impose these conditions on the resulting quantizer. Possible applications of the proposed technique are enumerated and its effectiveness is illustrated for coding of images using finite-state vector quantization.

The authors address the variable rate tree-structured vector quantizer design problem, wherein the rate is measured by the quantizer's entropy. For this problem, tree pruning via the generalized Breiman-Friedman-Olshen-Stone (1980) algorithm obtains solutions which are optimal over the restricted solution space consisting of all pruned trees derivable from an initial tree. However, the restrictions imposed on such solutions have several implications. In addition to depending on the tree initialization, growing and pruning solutions result in tree-structured vector quantizers which use a sub-optimal encoding rule. To remedy the latter problem, they consider a "tree-constrained" version of entropy-constrained vector quantizer design. This leads to an optimal tree-structured encoding rule for the leaves. In practice, though, improvements obtained in this fashion are limited by the tree initialization, as well as by the sub-optimal encoding performed at non-leaf nodes. To address these problems, they develop a joint optimization method which is inspired by the deterministic annealing algorithm for data clustering, and which extends their previous work on tree-structured vector quantization. The method is based on the principle of minimum cross entropy, using informative priors to approximate the unstructured solution while imposing the structural constraint. As in the original deterministic annealing method, the number of distinct codevectors (and hence the tree) grows by a sequence of bifurcations in the process, which occur as solutions of a free energy minimization. Their method obtains performance gains over growing and pruning methods for variable rate quantization of Gauss-Markov and Gaussian mixture sources.>

A new structure permits improved solutions which approximate the exhaustive-search multistage solution. A deterministic annealing design method capitalizing on this structure is formulated within the framework of information theory. The sequential search constraint is included as a prior, and the principal of minimum cross entropy is invoked. The method obtains improvement over both the standard sequential design and joint optimization approaches.>