Summary form only given. The title exemplifies the topic as it is easily recognized as compressed from possible English original versions. It also exemplifies some difficulties. A small sampling of readers all thought "Losy" was a corruption of "Lossy," which is consistent with the apparent loss of letters in "Hstry" and "Losy". But while "Hstry" is compressed, it is not really lossy since it can almost certainly be decoded into "History" (as my spell checker does). Moreover, "Losy" need not be "Lossy" - an equally good candidate in terms of minimizing Levenshtein distance is "Lousy" - so this talk could be a history of lousy compression, lossless or lossy. There are also problems in the uncompressed words. "Partial" has neither compression nor evident losses, but it has ambiguous meaning: it could equally well mean "incomplete" or "biased." So the title is not uniquely decodable, which equally favors "lossy" (since you cannot guarantee an accurate reconstruction) or "lousy" (since lossy coding of English seems a bad idea). This talk will embrace the ambiguity of the title.

A vector extension of a necessary condition for asymptotically optimal stationary (sliding-block) source codes is presented. The condition implies the intuitive result that the reproduction process for an IID input must be approximately uncorrelated if the code is approximately optimal, a property previously demonstrated empirically for common examples. One-bit coding of a Gaussian IID process is used to illustrate the goodness of fit of the empirical distribution of the reproduction to the Shannon optimal distribution.

Necessary conditions for asymptotically optimal sliding-block or stationary codes for source coding and rate-constrained simulation of memoryless sources are presented and used to motivate a design technique for trellis-encoded source coding and rate-constrained simulation. The code structure has intuitive similarities to classic random coding arguments as well as to “fake process” methods and alphabet-constrained methods. Experimental evidence shows that the approach provides comparable or superior performance in comparison with previously published methods on common examples, sometimes by significant margins.

Necessary conditions for asymptotically optimal sliding-block or stationary codes for source coding and rate-constrained simulation are presented and applied to a design technique for trellis-encoded source coding and rate constrained simulation of memoryless sources.

A formal result is stated and proved showing that the bit stream produced by the encoder of a nearly optimal sliding-block source coding of a stationary and ergodic source is close to an equiprobable i.i.d. binary process.

Noise is ubiquitous in real life and changes image acquisition, communication, and processing characteristics in an uncontrolled manner. Gaussian noise and Salt and Pepper noise, in particular, are prevalent in noisy communication channels, camera and scanner sensors, and medical MRI images. It is not unusual for highly sophisticated image processing algorithms developed for clean images to malfunction when used on noisy images. For example, hidden Markov Gauss mixture models (HMGMM) have been shown to perform well in image segmentation applications, but they are quite sensitive to image noise. We propose a modified HMGMM procedure specifically designed to improve performance in the presence of noise. The key feature of the proposed procedure is the adjustment of covariance matrices in Gauss mixture vector quantizer codebooks to minimize an overall minimum discrimination information distortion (MDI). In adjusting covariance matrices, we expand or shrink their elements based on the noisy image. While most results reported in the literature assume a particular noise type, we propose a framework without assuming particular noise characteristics. Without denoising the corrupted source, we apply our method directly to the segmentation of noisy sources. We apply the proposed procedure to the segmentation of aerial images with Salt and Pepper noise and with independent Gaussian noise, and we compare our results with those of the median filter restoration method and the blind deconvolution-based method, respectively. We show that our procedure has better performance than image restoration-based techniques and closely matches to the performance of HMGMM for clean images in terms of both visual segmentation results and error rate.

The Shannon rate-distortion function R(D) of a random process provides a lower bound to the minimal average distortion given a constraint on the average rate. When a positive source coding theorem with a fidelity criterion applies, the lower bound is achievable in the limit of large block length and hence R(D) characterizes the optimal performance for source coding or lossy data compression. The source coding theorem for possibly nonstationary Gaussian autoregressive sources was established over three decades ago, but two apparently different formulas for R(D) have appeared in the literature, resulting in long standing confusion about which is correct. There has also been related confusion about the asymptotic eigenvalue distributions of the inverse covariance matrices of such processes. We here establish the equality of the two formulas under fairly general conditions and clarify the confusion regarding asymptotic eigenvalue distributions.

To reduce the semantic gap, image retrieval systems based on users' relevance feedback have been adopted. However, since this structure needs human intervention during the retrieval process, it cannot be applied to fully automated systems. To avoid this problem, we propose a feed-forward framework instead of the feed-back retrieval system, which adds a classifier to the traditional system for giving feed-forward information to maximize the average precision. That is, given a database, our proposed system improves the overall precision by selecting the best mode based on known statistics (average precision vs. recall for each category). Lloyd-clustered Gauss mixtures are used in the classifier to provide the feed-forward category information and in the quantization of color images for histogram generation.

Noise is ubiquitous in real life and changes image acquisition and processing characteristics in an uncontrolled manner. Highly sophisticated image processing algorithms developed for clean images often malfunction when they are used for noisy images. For example, hidden Markov Gauss mixture models (HMGMM) have been shown to perform well in image segmentation applications, but they have also proved to be quite sensitive to uncontrolled noise in test images. To resolve this difficulty, we propose a modified procedure to adjust covariance matrix estimates of test images. We shrink (or expand) the covariance matrix estimates of the noisy image to make them consistent with those in the codebooks. Note that the covariance matrices in the codebooks are those of the noiseless image. The novelty of this paper is that our method is equivalent to adjusting the covariance matrices of codebooks for noiseless images to be consistent wit those of noisy test images without retraining. The adjusted covariance matrices shrink (or expand) the covariance matrix estimates in the codebooks to minimize the overall minimum discrimination information distortion between test images and codebooks. To illustrate the proposed procedure, we apply it to segmenting aerial images with Salt and Pepper noise and with Gaussian noise. We compare our method with the median filter restoration method and the blind deconvolution method and show that our procedure has better performance than these image-restoration-based techniques in terms of both visual segmentation results and error rate. Further, we find that the suggested procedure performs almost as well as the HMGMM for clean images, which is the benchmark in comparison.

For two-class classification, it is common to classify by setting a threshold on class probability estimates, where the threshold is determined by ROC curve analysis. An analog for multi-class classification is learning a new class partitioning of the multiclass probability simplex to minimize empirical misclassification costs. We analyze the interplay between systematic errors in the class probability estimates and cost matrices for multiclass classification. We explore the effect on the class partitioning of five different transformations of the cost matrix. Experiments on benchmark datasets with naive Bayes and quadratic discriminant analysis show the effectiveness of learning a new partition matrix compared to previously proposed methods. 1.

Indexing and retrieving large quantities of image data is an extremely challenging and increasingly topical problem for both industry and academia. Massive volumes of image data are all around us-in personal and commercial collections and on public Websites accessible via the Internet. According to a recent study by the market researcher IDC, digital camera sales rose 15 percent in 2006 to 105.7 million units worldwide. A four-year old online photo sharing website, Flickr, has more than 40 million monthly visitors and 2 billion photos uploaded; in fact, in a single day, a few million photos are uploaded. These developments have spurred enormous interest in digital images and a corresponding demand, both from the public and from industry, for better ways of cataloging, annotating, and accessing these data. This in turn has motivated researchers in pattern analysis and machine intelligence to address these tasks. Indeed, in a recent survey of the field of image annotation and retrieval, Wang et al. noticed an exponential growth over the last 10 years in the number of publications arising from researchers in computer vision, database management, machine learning, mathematical statistics, and signal and image processing.

Source coding theorems and Shannon rate-distortion functions were studied for the discrete-time Wiener process by Berger and generalized to nonstationary Gaussian autoregressive processes by Gray and by Hashimoto and Arimoto. Hashimoto and Arimoto provided an example apparently contradicting the methods used in Gray, implied that Gray's rate-distortion evaluation was not correct in the nonstationary case, and derived a new formula that agreed with previous results for the stationary case and held in the nonstationary case. In this correspondence it is shown that the rate-distortion formulas of Gray and Hashimoto and Arimoto are in fact consistent and that the example of Hashimoto and Arimoto does not form a counterexample to the methods or results of the earlier paper. Their results do provide an alternative, but equivalent, formula for the rate-distortion function in the nonstationary case and they provide a concrete example that the classic Kolmogorov formula differs from the autoregressive formula when the autoregressive source is not stationary. Some observations are offered on the equality of the asymptotic distributions of the eigenvalues of the sequence of inverse autocorrelation matrices of possibly nonstationary autoregressive processes and of their Toeplitz approximations.

In this paper, the Lagrangian formulation of variable-rate vector quantization is extended to quantization with simultaneous constraints on entropy and codebook size, including variable- and fixed-rate quantization as special cases. The formulation leads to a Lloyd quantizer design algorithm and generalizations of Gersho's approximations characterizing optimal performance for asymptotically large rate. A variation of Gersho's approach is shown to yield rigorous results partially characterizing the asymptotically optimal performance.

A new Lagrangian formulation with entropy and codebook size was proposed to extend the Lagrangian formulation of variable-rate vector quantization. We use the new Lagrangian formulation to perform clustering and to find the number of clusters by fitting mixture models to data using vector quantization. Experimental results show that the entropy and memory constrained vector quantization outperforms the state-of-the-art model selection algorithms in the examples considered.

Quality criteria for image coding are often based on mean square error. However, this is not always a relevant measure of visual quality at low bit rates. Here, we investigate the properties of a distortion measure based on the conditional differential entropy of the input signal given its quantized value. The proposed measure appears to be a correct representation of the amount of information lost by quantization. An adaptive bit allocation algorithm is proposed in order to take advantage of this criterion. Experimental results illustrate the behavior of the proposed distortion measure and exhibit interesting visual properties for low bit-rate subband image coding.

Image segmentation is an important tool in image processing and can serve as an efficient front end to sophisticated algorithms and thereby simplify subsequent processing. We develop a multiclass image segmentation method using hidden Markov Gauss mixture models (HMGMMs) and provide examples of segmentation of aerial images and textures. HMGMMs incorporate supervised learning, fitting the observation probability distribution given each class by a Gauss mixture estimated using vector quantization with a minimum discrimination information (MDI) distortion. We formulate the image segmentation problem using a maximum a posteriori criteria and find the hidden states that maximize the posterior density given the observation. We estimate both the hidden Markov parameter and hidden states using a stochastic expectation-maximization algorithm. Our results demonstrate that HMGMM provides better classification in terms of Bayes risk and spatial homogeneity of the classified objects than do several popular methods, including classification and regression trees, learning vector quantization, causal hidden Markov models (HMMs), and multiresolution HMMs. The computational load of HMGMM is similar to that of the causal HMM.

Results are developed for optimal quantization with combined entropy and log codebook size constraints, including high rate characterizations of distortion, entropy, codebook size, and quantizer point density functions.

Gauss mixture models (GMMs) provide an approach to the image classification problems, utilizing the robustness and the analytical tractability of the Gaussian distribution. Previous work on the GMM-based image classification algorithms has focused on either the single sensor schemes or schemes with no noise or rate constraints. In our work, we consider a GMM-based image classification problem for a network of sensors with each sensor having a different noisy version of a common image. The goal of each sensor is to classify the image based on its own noisy version and the help it receives from the other sensors under rate constraints. We formulate the image sensor network classification problem as a vector quantization problem and design Lloyd optimal quantizers, minimizing the classification error for the given rate constraints. We then extend our algorithm to include context dependence. Our cross-validated simulations, using a set of aerial images, indicate an improvement in the classification performance (for the given rate constraints) when compared with the network extensions of previously published GMM-based algorithms.

SPIHT is an efficient image compression algorithm based on zerotrees. The significant wavelet coefficients are located by a series of set partitioning operations and then scalar quantized. Block-based algorithms inspired by SPIHT such as AGP and SWEET have good performance, but they are not embedded. Pearlman et al. proposed a block-based SPECK algorithmusing set partitioning of embedded blocks to exploit the energy clustering characteristics of the coefficients while the bit stream remains embedded. We here propose a variation on SPECK using vector quantization to code the significant coefficients. Different VQ techniques including TSVQ and ECVQ are also considered. Vector SPECK shows a performance improvement over JPEG 2000 at the cost of added complexity.

Quantization is the mapping of continuous quantities into discrete quantities, an operation far more general and flexible than the ubiquitous example of analog-to-digital conversion of scalar amplitude values. By appropriate choice of distortion measures and transmission constraints, quantization can incorporate signal processing such as statistical classification, estimation, and modeling. We here survey several approaches to incorporating such tasks into the quantization and possible extensions to distributed signal processing

Classical quality criteria for image coding are based on the mean square error. We investigate here the properties of a distortion measure based on differential entropy of the error signal. The proposed measure leads to an interesting alternative code design criterion. An adapted bit allocation algorithm is proposed in order to take advantage of this criterion. Experimental results illustrate the behavior of the proposed distortion measure and exhibit interesting psycho-visual properties.

An iterative model selection algorithm is proposed. The algorithm seeks relevant features and an optimal number of codewords (or codebook size) as part of the optimization. We use a well-known separability measure to perform feature selection, and we use a Lagrangian with entropy and codebook size constraints to find the optimal number of codewords. We add two model selection steps to the quantization process: one for feature selection and the other for choosing the number of clusters. Once relevant and irrelevant features are identified, we also estimate the probability density function of irrelevant features instead of discarding them. This can avoid the bias of problem of the separability measure favoring high dimensional spaces

Nonparametric neighborhood methods for learning entail estimation of class conditional probabilities based on relative frequencies of samples that are "near-neighbors" of a test point. We propose and explore the behavior of a learning algorithm that uses linear interpolation and the principle of maximum entropy (LIME). We consider some theoretical properties of the LIME algorithm: LIME weights have exponential form; the estimates are consistent; and the estimates are robust to additive noise. In relation to bias reduction, we show that near-neighbors contain a test point in their convex hull asymptotically. The common linear interpolation solution used for regression on grids or look-up-tables is shown to solve a related maximum entropy problem. LIME simulation results support use of the method, and performance on a pipeline integrity classification problem demonstrates that the proposed algorithm has practical value.

A Lagrangian formulation of fixed-rate vector quantization is presented. The formulation provides an alternative version of the classic high-rate quantization approximations for fixed-rate codes of Zador (1966), and Bucklew and Wise (1982) which parallels the Lagrangian results for variable-rate codes and it leads to a variation of the classic Lloyd (1982) algorithm for quantizer design. The approach also leads to a natural Lagrangian formulation combining both common rate constraints of alphabet size and entropy, effectively providing a Lagrangian formulation of memory and entropy constrained vector quantization.

We consider image retrieval based on minimum distortion selection of features of color images modelled by Gauss mixtures. The proposed algorithm retrieves the image in a database having minimum distortion when the query image is encoded by a separate Gauss mixture codebook representing each image in the database. We use Gauss mixture vector quantization (GMVQ) for clustering Gauss mixtures, instead of the conventional expectation-maximization (EM) algorithm. Experimental comparison shows that the simpler GMVQ and the EM algorithms have close Gauss mixture parameters with similar convergence speeds. We also provide a new color-interleaving method, reducing the dimension of feature vectors and the size of covariance matrices, thereby reducing computation. This method shows a slightly better retrieval performance than the usual color-interleaving method in HSV color space. Our proposed minimum distortion image retrieval performs better than probabilistic image retrieval.

We consider the problem of finding the optimal one-bit quantizer for symmetric source distributions, with the Euclidean norm as the measure of distortion. For fixed rate quantizers, we prove that for (symmetric) monotonically decreasing source distributions with ellipsoidal level curves, the centroids of the optimal 1-bit quantizer must be on the major axis of the ellipsoids. Under the same assumptions on the source distribution, the centroids of the optimal one-bit variable-rate quantizer lie on one of the axes of the ellipsoid. If further, the source distribution f(x) is log-concave in x, the optimal 1-bit fixed-rate quantizer is unique and symmetric about the origin. (The Gaussian is an example of a distribution that satisfies all these conditions.) Under a further set of conditions on the source distributions, we show that there is a threshold below which the optimal fixed rate and variable rate quantizer are the same.

The Wasserstein distortion has proved useful in a variety of mathematical, signal processing and coding problems as a measure of how different two distributions are. In this paper we provide an expression for the performance of the optimal entropy constrained quantizer in terms of the Wasserstein distortion. The proof presented is significantly different from that previously shown by Linder (2002) and also provides an algorithm to achieve the optimal performance as the block size increases.

Summary form only given. We design a generalized Gauss mixture vector quantizer (GMVQ) with an encoder at each sensor and a decoder at the common receiver, minimizing the expected quadratic discriminant analysis (QDA) distortion between the original data and the Gauss mixture component, to which it is assigned by the decoder. Each encoder first predicts the index assignment of the other encoder based on its own noisy version of the data. We denote the predicted index of the other encoder by j/sup p/. Then, the encoder assigns its own noisy version to the index i such that the Gauss mixture component associated with the index pair (i, j/sup p/) at the decoder is the one minimizing the expected QDA distortion. The decoder, upon receiving an index from each encoder, maps the received index pair to the mixture component, minimizing the expected distortion. The quantizer is trained using the Lloyd algorithm, by iteratively updating the encoders and the decoder. Each encoder is updated by predicting the index assignments of the other encoder followed by assigning each noisy input vector to the index, minimizing the expected QDA distortion. The decoder is updated by mapping each index pair to the optimum Gauss mixture component followed by the update of the parameters of each Gauss mixture component. We have implemented our algorithm on three different data sets: a mixture of Gaussians, a mixture of Laplacians and a a set of aerial images. For each data set, we observed that the classification performance achieved by our algorithm is very close to the theoretically optimal (Bayes) performance.

Expectation-maximization (EM) is the dominant algorithm for estimating the parameters of a Gauss mixture (GM). Recently, Gauss mixture vector quantization (GMVQ) based on the Lloyd algorithm has been applied successfully as an alternative for both compression and classification. We investigate the performance of the two algorithms for GMs in image retrieval. The asymptotic likelihood approximation is used as a similarity criterion to compare GMs directly. The two algorithms result in very close retrieval performance. We demonstrate that the closeness comes from the close mutual approximation of the GM estimated parameter values and that the two algorithms have similar convergence speed. Our analysis shows that GMVQ has roughly half the computational complexity of EM.

Gauss mixture models are commonly used in image classification due to their analytical tractability and robustness. When the feature vectors are formed as the coefficients of a linear image transform, the underlying mixture components are not necessarily Gaussian, in which case there is no guarantee that the Gauss mixture model (GMM)-based clustering algorithms can capture the mixture components. In this work, we train an unbalanced tree-structured GMM-based classifier to reduce this problem. We derive and apply a parameter-independent test to determine the number of mixture components in any given tree node. The classifier tree is grown only in the regions with multiple mixture components.

Previous work has shown Gaussian mixture vector quantization (GMVQ) based classifiers to be effective in classifying image blocks, image regions and whole images. A significant attraction of GMVQ for whole image classification is that simple local features can be used, thereby avoiding time-consuming feature design and selection. Unfortunately, however, this approach does not work so well when the artifact of interest occupies a small area relative to the size of the image. We propose a simple weighting approach to focus the classifier's attention on the artifact blocks. This extends the usefulness of whole image GMVQ classification without compromising the simplicity of feature selection. The algorithm is motivated by difficulties in classifying pipeline images. Results on this dataset show the weighted GMVQ approach to be effective for classifying images with small artifacts of interest.

Gauss mixture vector quantizers (GMVQ's), designed using the Lloyd algorithm, provide an approach to the image classification problems, utilizing the robustness and the analytical tractability of the Gaussian distribution. We generalize the Lloyd-based GMVQ training algorithm to design a Lloyd-optimal GMVQ when only a noisy version of the original data is available at the classifier and the classifier is allowed to cooperate with sensors, having different noisy versions of the original data, under rate constraints. Our simulations, using a set of aerial images, indicate that our algorithm leads to a better classification performance than the non-optimized schemes.

We propose a feature selection algorithm suitable for classification problems. Our algorithm tries to find a subset of features, which maximizes separability between Gaussian clusters. To reduce the complexity of exhaustive searching the best feature set, we follow a backward elimination method. Our feature selection algorithm can be applied to a full search classifier to obtain a single global subspace. However, one global subspace may not alone capture local behavior well. We realize multiple subspace clustering by applying our dimension reduction algorithm to a tree structured classifier. Experimental results show that the resulting classifier not only removes irrelevant features but also improves classification performance.

Recent results and conjectures are presented regarding the behavior of asymptotically optimal vector quantizers. The principal new results are four lemmas and a corollary relating the distortion and entropy of quantizers and asymptotically optimal quantizers. Several related conjectures (some of which are based on simulations) are made regarding the behavior of asymptotically optimal quantizers.

Gauss mixture (GM) models are frequently used for their ability to well approximate many densities and for their tractability to analysis. We propose new classification methods built on GM clustering algorithms more often studied and used for vector quantization (VQ). One of our methods is an extension of the 'codebook matching' idea to the specific case of classifying whole images. We apply these methods to a realistic supervised classification problem and empirically evaluate their performances compared with other classification methods.

According to the principle of minimum description length, the best statistical classifier is the one that minimizes the sum of the complexity of the model and the description length of the training data. This paper focuses on improving the classification rate through correctly classifying the vectors that are misclassified by classifiers. For this purpose, a new tree-structured version of the algorithm, namely tree-structured discriminant vector quantisation, based on the BFOS algorithm. The major problem of the conventional algorithm is overcome by modifying the pdf of the training vectors using the adaptive-boosting algorithm. This new algorithm is implemented on a set of seven textures from the Brodatz data set.

The Gauss mixture model (GMM)-based vector quantizer with the quadratic discriminant analysis (QDA) distortion measure provides an approach to statistical image classification problems. Recent work has concentrated on designing tree-structured vector quantizers for image classification problems using the QDA distortion measure and the BFOS algorithm for pruning. It has been shown that the tree-structured design often increases the correct classification rate for the same design complexity, avoids over-fitting by pruning and makes it possible to include other classification algorithms such as adaptive boosting. Both the full-search design and the tree-structured design are based on clustering using the Lloyd algorithm. Even when the true underlying distribution of the feature vectors follows (approximately) a Gauss mixture distribution, the variances of the Gaussian components estimated by the clustering algorithm tend to be less than those of the true distribution. Hence, clustering introduces a variance bias. The work reported here intends to reduce the effects of the variance bias using the independent central limit theorem when the feature vectors are formed as (weighted) sums of the image block pixels. This is done through a joint quantization of the means and covariances of the image blocks and the feature vectors derived from the image blocks. Our simulations indicate that, both for the full-search design and the tree-structured design, our algorithm leads to an improvement in the classification accuracy. Finally, for the tree-structured classifier, we introduce a fast algorithm, which uses only the median eigenvalue of the covariance matrix (instead of the full covariance matrix) of each Gaussian component in the classification stage.

We present a new wavelet video coding algorithm and an optimization framework that allocates bits efficiently among consecutive frames at the pixel level. The video residual coder is based on set partitioning in hierarchical trees and wavelet blocks, allowing flexible bit allocation among active and inactive regions in a video frame. To optimize the encoder for efficient bit allocation, we use Lagrangian methods. First, the rate-distortion cost for each wavelet block is minimized, effectively enforcing the equal-slope rule at the pixel level. The Lagrangian method is then extended to successive frames, and an iterative algorithm is presented to solve the dependent coding problem. Finally, motion search is jointly optimized by including motion vectors in the cost function, completing an optimization framework that enforces the equal-slope rule for all bits at the macroblock level and pixels across consecutive frames. The result is a video compression algorithm that requires no training, no explicit quantization, no floating-point operation for INTER frames, no entropy coding, and allows precise rate control. Compared with the discrete cosine transform code in H.263, the new video coding algorithm has faster decoding procedures and achieves an improvement up to 1.12 dB in a PSNR or 20.6% in bit rate savings for typical sequences used in the video compression community.

It is shown that if an asymptotically optimal sequence of variable rate codes is designed for a k-dimensional probability density function (pdf) g and then applied to another pdf f for which f/g is bounded, then the resulting mismatch or loss of performance from the optimal possible is given by the relative entropy or Kullback-Leibler divergence I(f/spl par/g). It is also shown that under the same assumptions an asymptotically optimal code sequence for g can be converted to an asymptotically optimal code sequence for a mismatched source f by modifying only the lossless component of the code. The development does not require Gersho's conjecture.

Summary form only given. Taking the average of feature vectors from the center and neighboring blocks to a block being coded is proposed as a method of considering context information in block classification. The algorithm has the advantage of low complexity. Gauss mixture models (GMM) are adopted to extract features from image blocks, including an algorithm to handle singular covariance matrices. Two different distortion measures are used; namely log-likelihood quadratic discrimination analysis (QDA) and a dimension-compensated distortion measure defined by dividing the QDA distortion by the corresponding cell's dimension. Aerial images were used to train and test. Experimental results show that the proposed algorithm not only improves the classification performance, but also provides a solution to the singular covariance problem.

Histogram-based image retrieval requires some form of quantization since the raw color images result in large dimensionality in the histogram representation. Simple uniform quantization disregards the spatial information among pixels in making histograms. Since traditional vector quantization (VQ) with squared-error distortion employs only the first moment, it neglects the relationship among vectors. We propose Gauss mixture vector quantization (GMVQ) as the quantization method for a histogram-based image retrieval to capture the spatial information in the image via the Gaussian covariance structure. Two common histogram distance measures are used to evaluate the similarity of histograms resulting from GMVQ. Our results show that GMVQ, with a quadratic discriminant analysis (QDA) distortion, outperforms the two typical quantization methods in histogram-based image retrieval.

Recently developed optical inspection tools provide images from the inside of natural gas pipelines to monitor pipeline integrity. The vast amount of data generated prohibits human inspection of the resulting images. We designed an image processing and classification method to identify ab- normal events. Non-overlapping image blocks are classified into twelve categories: normal, black line, grinder marks, magnetic flux leakage inspector marks, single dots, small black corrosion dots, osmosis blisters, corrosion dots, longitudinal weld, field joint, cavity at a weld and longitudinal weld too close to field joints. Results compare different types of statistical classifiers. Features extracted from the pipeline image are designed to mimic the features humans use to identify the different classes. Difficulties include the large number of classes, the uneven costs associated with different errors, and training on a limited amount of expert classified data. Classification results show this to be a useful tool for pipeline monitoring.

Histogram-based image retrieval requires some form of quantization since the raw color images result in large dimensionality in the histogram representation. Simple uniform quantization disregards the spatial information among pixels in making histograms. Since traditional vector quantization (VQ) with squared-error distortion employs only the first moment, it neglects the relationship among vectors. We propose Gauss mixture vector quantization (GMVQ) as the quantization method for a histogram-based image retrieval to capture the spatial information in the image via the Gaussian covariance structure. Two common histogram distance measures are used to evaluate the similarity of histograms resulting from GMVQ. Our result shows that GMVQ with a quadratic discriminant analysis (QDA) distortion outperforms the two typical quantization methods in the histogram- based image retrieval.

A light field is a collection of multiview images which represent a three-dimensional scene. Rendering from a light field provides a simple and efficient way to generate arbitrary new views of the scene, bypassing the difficult problem of acquiring accurate geometric and photometric models. The enormous amount of data required in a light field poses a key challenge in rendering. Tree-structured vector quantization (TSVQ) provides a moderate compression ratio of around 24:1, which alleviates, but does not solve, the problem. Compression schemes based on video coding techniques exploit the data redundancy very effectively, but do not provide adequate random access for rendering. The paper presents an analysis of the data-access pattern during the rendering process and describes a compression scheme that supports interactive rendering directly from compressed light field data. The proposed algorithm provides a high compression ratio of as much as ten times that of TSVQ, while slowing down the rendering speed by only a factor smaller than 2.

Bucklew's (1984) high-rate vector quantizer mismatch result is extended from fixed-rate coding to variable-rate coding using a Lagrangian formulation. It is shown that if an asymptotically (high-rate) optimal sequence of variable rate codes is designed for a k-dimensional probability density function (PDF) g and then applied to another PDF f for which f/g is bounded, then the resulting mismatch or loss of performance from the optimal possible is given by the relative entropy or Kullback-Leibler (1968) divergence I(f/spl par/g). It is also shown that under the same assumptions, an asymptotically optimal code sequence for g can be converted to an asymptotically optimal code sequence for a mismatched source f by modifying only the lossless component of the code. Applications to quantizer design using uniform and Gaussian densities are described, including a high-rate analog to the Shannon rate-distortion result of Sakrison (1975) and Lapidoth (1997) showing that the Gaussian is the "worst case" for lossy compression of a source with known covariance. By coupling the mismatch result with composite quantizers, the worst case properties of uniform and Gaussian densities are extended to conditionally uniform and Gaussian densities, which provides a Lloyd clustering algorithm for fitting mixtures to general densities.

We propose a novel image classification method using a non-causal hidden Markov Gauss mixture model (HMGMM) We apply supervised learning assuming that the observation probability distribution given each class can be estimated using Gauss mixture vector quantization (GMVQ) designed using the generalized Lloyd algorithm with a minimum discrimination information (MDI) distortion. The maximum a posteriori (MAP) hidden states in an Ising model are estimated by a stochastic EM algorithm. We demonstrate that HMGMM obtains better classification than several popular methods, including CART, LVQ, causal HMM, and multiresolution HMM, in terms of Bayes risk and the spatial homogeneity of the classified objects. A heuristic solution for the number of clusters achieves a robust image classification.

The paper describes an automatic object segmentation algorithm for images with low depth of field (DOF). The low DOF images are segmented into two regions, namely, focused objects and defocused background. A local variance image field (LVIF) can represent the pixel-wise spatial distribution of the high-frequency components in the image. However, applying a thresholding method to the LVIF for segmentation often yields blob-like errors in both focused and defocused regions. To eliminate these errors, a block-wise MRF (Markov random field) image model is employed for maximum a posteriori (MAP) segmentation. After the block-wise MAP segmentation, the image blocks in the object boundary are divided into smaller blocks. Then, they are reassigned to one of the neighboring objects through the watershed algorithm, which eventually yields a pixel-level segmentation. Experimental results show that the proposed method yields more accurate segmentation than the multiresolution wavelet-based segmentation method.

We propose a texture classification method using multiple Gauss mixture vector quantizers (GMVQ). We designed a separate model codebook or Gauss mixture for each texture using the generalized Lloyd algorithm with a minimum discrimination information (MDI) distortion based on a training data set. The multi-codebook structure of the GMVQ classifier is an extension to images of the isolated utterance speech recognizer of J.E. Shore and D. Burton (see Proc. Int. Conf. Acoust., Speech, and Sig. Processing, IEEE82Ch.1746-7, p.907-10, 1982). We applied the algorithm to the Brodatz texture database and showed it to be competitive in performance in comparison to other texture classifiers. Its low complexity implementation and real-time operation make the approach suitable for content-based image retrieval.

We propose a multiresolution algorithm to jointly optimize a source coder and channel coder. The variable-rate source coder combines an optimal bit-allocation strategy and efficient stack-run coding. This compression scheme, concatenated with appropriate rate-compatible punctured convolutional codes, provides a competitive approach to state-of-the-art extensions of zerotree methods to noisy channels. Results show that under the assumption of almost zero probability of decoding error, the proposed scheme provides good performance for a lower complexity.

Zador's (1963, 1966) classic result for the asymptotic high-rate behavior of entropy-constrained vector quantization is recast in a Lagrangian form which better matches the Lloyd algorithm used to optimize such quantizers. The equivalence of the two formulations is shown and the result is proved for source distributions that are absolutely continuous with respect to the Lebesgue measure which satisfy an entropy condition, thereby generalizing the conditions stated by Zador under which the result holds.

Zador's classic result for the asymptotic high-rate behavior of entropy-constrained vector quantization is recast in a Lagrangian form which better matches the Lloyd algorithm used to optimize such quantizers. A proof that the result holds for a general class of distributions is sketched.

We introduce a video residual coding technique based on wavelet transforms and set partitioning in hierarchical trees (SPIHT). In this scheme, wavelet coefficients that correspond to the same spatial location in the image domain are grouped together to form wavelet blocks. Each wavelet block is then converted to a SPIHT-compatible bit stream by an optimized SPIHT encoder minimizing the Lagrangian cost J=D+/spl lambda/R. We also extend the rate-distortion method to include future dependency and propose an iterative algorithm to solve the dependent coding problem. The result is a coding system which achieves better rate-distortion performance than baseline H.263 with a very fast integer-only decoding procedure.

We study the rate-distortion performance of the set partitioning in hierarchical trees (SPIHT) image compression algorithm and present an optimization method that produces the bit stream with minimum Lagrangian cost J=D+/spl lambda/R for a given stopping criterion. Although there are only three applicable stop points at each bit plane, experiments show that substantial improvements can be obtained over a wide range of bit rates.

Gauss mixtures are a popular class of models in statistics and statistical signal processing because they can provide good fits to smooth densities, because they have a rich theory, and because they can be well estimated by existing algorithms such as the EM (expectation maximization) algorithm. We here extend an information theoretic extremal property for source coding from Gaussian sources to Gauss mixtures using high rate quantization theory and extend a method originally used for LPC (linear predictive coding) speech vector quantization to provide a Lloyd clustering approach to the design of Gauss mixture models. The theory provides formulas relating minimum discrimination information (MDI) for model selection and the mean squared error resulting when the MDI criterion is used in an optimized robust classified vector quantizer. It also provides motivation for the use of Gauss mixture models for robust compression systems for general random vectors.

The asymptotic optimal performance of variable-rate vector quantizers of fixed dimension and large rate was first developed in a rigorous fashion by Paul Zador (1966). Subsequent design algorithms for such compression codes used a Lagrangian formulation in order to generalize Lloyd's classic quantizer optimization algorithm to variable rate codes. This formulation has been subsequently adopted in a variety of practical systems including rate-optimized streaming video. We describe a Lagrangian formulation of Zador's variable-rate quantization results and apply it to estimate Zador's constant using the generalized Lloyd algorithm.

Gauss mixtures have gained popularity in statistics and statistical signal processing applications for a variety of reasons, including their ability to approximate well a large class of interesting densities and the availability of algorithms such as EM for constructing the models based on observed data. We here consider a different motivation and framework based on the information theoretic view of Gaussian sources as a "worst case" for compression developed by D.J. Sakrison (see IEEE Trans. Inform. Theory, vol.21, p.301-9, 1975) and A. Lapidoth (see IEEE Trans. Inform. Theory, vol.43, p.38-47, 1997). This provides an approach for clustering Gauss mixture models using a minimum discrimination distortion measure and provides the intuitive support that good modeling is equivalent to good compression. A simple example of a clustered Gauss mixture model applied to image archiving and querying is presented and and compared with the common color histogram method. Signatures for both query and target images were formed by encoding an image using the minimum distortion encoder to obtain a histogram for the components. A simple decision tree was designed to decide whether or not a "match" occurred between the query image (representing its type) and the target image based on the component histogram of each.

We propose a new estimation method using the maximum entropy principle and show that it is successfully used for the three-dimensional interpolation step involved in many color conversions. Color conversions are a key part of color management systems, and many device characterizations, especially for printers, rely on multidimensional interpolation to perform the conversion. Our method is a linear interpolation that is not limited in the number of sample points used to estimate new color values. We find a unique solution to the underdetermined inverse matrix problem by invoking the maximum entropy principle. We compare our approach to the standard technique of tetrahedral interpolation and demonstrate that more accurate and more robust approximations may result.

A light field is a collection of multi-view images which represent a 3D scene. Rendering from a light field provides a simple and efficient way to generate arbitrary new views of the scene as the viewing position and angle change, thus offering the experience of immersive viewing. The enormous amount of data required in a light field poses a key challenge in rendering. Tree-structured vector quantization (TSVQ) provides moderate compression ratio of around 24:1, which alleviates but does not solve the problem. Compression schemes based on video coding techniques exploit the data redundancy very effectively, but do not provide adequate random access for rendering. This paper describes a new compression scheme that supports interactive rendering directly from compressed light field data. The proposed algorithm provides a high compression ratio of as much as 10 times that of TSVQ, while only slowing down the rendering speed by a factor smaller than 2.

Unsupervised segmentation of images with low depth of field (DOF) is highly useful in various applications. This paper describes a novel multiresolution image segmentation algorithm for low DOF images. The algorithm is designed to separate a sharply focused object-of-interest from other foreground or background objects. The algorithm is fully automatic in that all parameters are image independent. A multi-scale approach based on high frequency wavelet coefficients and their statistics is used to perform context-dependent classification of individual blocks of the image. Unlike other edge-based approaches, our algorithm does not rely on the process of connecting object boundaries. The algorithm has achieved high accuracy when tested on more than 100 low DOF images, many with inhomogeneous foreground or background distractions. Compared with he state of the art algorithms, this new algorithm provides better accuracy at higher speed.

A light field is a collection of multi-view images which represent a 3-D scene. Rendering from a light field provides a simple and efficient way to generate arbitrary new views of the scene as the viewing position and angle change, thus offering the experience of immersive viewing. The enormous amount of data required in a light field (typically on the order of tens or hundreds of megabytes and in some cases even gigabytes) poses a key challenge in rendering. Tree-structured vector quantization (TSVQ) provides moderate compression ratio, which alleviates but does not solve the problem. Compression schemes based on video coding techniques exploit the data redundancy very effectively but do not provide adequate random access for rendering. This paper describes a hierarchical compression scheme based on disparity compensated prediction, which provides a high compression ratio while offering fast random access. More information is available at http://www-ise.stanford.edu//spl sim/xin/lf.

We present a fast classification technique for document images such as Web pages and for information retrieval. The technique involves performing all computations off-line and building the results into tables, so that during actual classification the only operations performed are simple table-lookups. We also introduce a distortion measure that is suitable for classification. Results show that the probability of misclassification for table-lookup gives good performance and the implementation is fast.

In this paper, an algorithm is developed for segmenting document images into four classes: background, photograph, text, and graph. Features used for classification are based on the distribution patterns of wavelet coefficients in high frequency bands. Two important attributes of the algorithm are its multiscale nature-it classifies an image at different resolutions adaptively, enabling accurate classification at class boundaries as well as fast classification overall-and its use of accumulated context information for improving classification accuracy.

This paper treats a multiresolution hidden Markov model for classifying images. Each image is represented by feature vectors at several resolutions, which are statistically dependent as modeled by the underlying state process, a multiscale Markov mesh. Unknowns in the model are estimated by maximum likelihood, in particular by employing the expectation-maximization algorithm. An image is classified by finding the optimal set of states with maximum a posteriori probability. States are then mapped into classes. The multiresolution model enables multiscale information about context to be incorporated into classification. Suboptimal algorithms based on the model provide progressive classification that is much faster than the algorithm based on single-resolution hidden Markov models.

We present an algorithm to achieve good compression and classification for images using vector quantization and a two dimensional hidden Markov model. The feature vectors of image blocks are assumed to be generated by a two dimensional hidden Markov model. We first estimate the parameters of the model, then design a vector quantizer to minimize a weighted sum of compression distortion and classification risk, the latter being defined as the negative of the maximum log likelihood of states and feature vectors. The algorithm is tested on both synthetic data and real image data. The extension to joint progressive compression and classification is discussed.

In this paper, we present a VQ-based two-codebook design which uses separate codebooks for predicted residuals and full pixel values. We show that our approach captures abrupt scene changes while exploiting inter-frame dependencies. We use a simple universal code consisting of two codebooks, an intra-codebook containing codewords that are used as reproduction of image blocks together with a residual-codebook. Codebooks are selected to minimize distortion for the block being coded. If there is relatively little motion in a frame, most blocks use the residual-codebook. On the other hand, if a frame is very different from the previous one, most blocks will be coded using the intra-codebook. When compared to other VQ schemes mentioned above, the resulting quantizer not only follows scene changes closely with satisfactory fidelity but also is robust against mismatch between the training and test sequence. We compare the PSNR of three coding schemes, intra-coding-only, inter-coding only, and the proposed method.

Traditional block-based image classification algorithms, such as CART and VQ based classification, ignore the statistical dependency among image blocks. Consequently, these algorithms often suffer from over-localization. In order to benefit from the inter-block dependency, an image classification algorithm based on a hidden Markov model (HMM) is developed. An HMM for image classification, a two dimensional extension from the one dimensional HMM used for speech recognition, has transition probabilities conditioned on the states of neighboring blocks from both directions. Thus, the dependency in two dimensions can be reflected simultaneously. The HMM parameters are estimated by the EM algorithm. A two dimensional version of the Viterbi algorithm is also developed to classify optimally an image based on the trained HMM. An application of the HMM algorithm to document image and aerial image segmentation shows that the algorithm performs better than CART.

We present a technique to speed up classification of document images such as web pages. The technique involves performing all computation off-line and building the results into tables, so that during actual classification the only operations performed are simple table-lookups. Results show that the probability of misclassification for table-look up gives good performance and the implementation is much faster.

This paper presents an image classification algorithm based upon a two dimensional multiresolution hidden Markov model (MHMM). This model represents an image by feature vectors in several resolutions and considers the feature vectors statistically dependent through an underlying state process assumed to be a multiscale Markov mesh. To estimate the model by the maximum likelihood criterion, approximations are made successively based on the EM algorithm to reach feasible computation. To classify an image, the algorithm attempts to find the optimal set of states with the maximum a posteriori probability. The states are then mapped into classes. The multiresolution model enables multiscale context information to be incorporated into classification. Suboptimal algorithms based on the model provide progressive classification which greatly speeds up classification based on single resolution HMMs.

We describe a general coding strategy leading to a family of universal image compression systems designed to give good performance in applications where the statistics of the source to be compressed are not available at design time or vary over time or space. The basic approach considered uses a two-stage structure in which the single source code of traditional image compression systems is replaced with a family of codes designed to cover a large class of possible sources. To illustrate this approach, we consider the optimal design and use of two-stage codes containing collections of vector quantizers (weighted universal vector quantization), bit allocations for JPEG-style coding (weighted universal bit allocation), and transform codes (weighted universal transform coding). Further, we demonstrate the benefits to be gained from the inclusion of perceptual distortion measures and optimal parsing. The strategy yields two-stage codes that significantly outperform their single-stage predecessors. On a sequence of medical images, weighted universal vector quantization outperforms entropy coded vector quantization by over 9 dB. On the same data sequence, weighted universal bit allocation outperforms a JPEG-style code by over 2.5 dB. On a collection of mixed test and image data, weighted universal transform coding outperforms a single, data-optimized transform code (which gives performance almost identical to that of JPEG) by over 6 dB.

We describe a procedure by which Joint Photographic Experts Group (JPEG) compression may be customized for gray-scale images that are to be compressed before they are scaled, halftoned, and printed. Our technique maintains 100% compatibility with the JPEG standard, and is applicable with all scaling and halftoning methods. The JPEG quantization table is designed using frequency-domain characteristics of the scaling and halftoning operations, as well as the frequency sensitivity of the human visual system. In addition, the Huffman tables are optimized for low-rate coding. Compression artifacts are significantly reduced because they are masked by the halftoning patterns, and pushed into frequency bands where the eye is less sensitive. We describe how the frequency-domain effects of scaling and halftoning may be measured, and how to account for those effects in an iterative design procedure for the JPEG quantization table. We also present experimental results suggesting that the customized JPEG encoder typically maintains "near visually lossless" image quality at rates below 0.5 b/pixel (with reference to the number of pixels in the original image) when it is used with bilinear interpolation and either error diffusion or ordered dithering. Based on these results, we believe that in terms of the achieved bit rate, the performance of our encoder is typically at least 20% better than that of a JPEG encoder using the suggested baseline tables.

Gersho's (1979) bounds on the asymptotic performance of vector quantizers are valid for vector distortions which are powers of the Euclidean norm. Yamada, Tazaki, and Gray (1980) generalized the results to distortion measures that are increasing functions of the norm of their argument. In both cases, the distortion is uniquely determined by the vector quantization error, i.e., the Euclidean difference between the original vector and the codeword into which it is quantized. We generalize these asymptotic bounds to input-weighted quadratic distortion measures and measures that are approximately output-weighted-quadratic when the distortion is small, a class of distortion measures often claimed to be perceptually meaningful. An approximation of the asymptotic distortion based on Gersho's conjecture is derived as well. We also consider the problem of source mismatch, where the quantizer is designed using a probability density different from the true source density. The resulting asymptotic performance in terms of distortion increase in decibels is shown to be linear in the relative entropy between the true and estimated probability densities.

We consider the problem of joint quantization and classification for the example of a simple Gaussian mixture used by Kohonen (1988) to demonstrate the performance of his "learning vector quantization" (LVQ). Implicit in the problem is the issue of estimating the underlying densities, which is accomplished by CART/sup TM/ and by an inverse halftoning method.

The history of the theory and practice of quantization dates to 1948, although similar ideas had appeared in the literature as long ago as 1898. The fundamental role of quantization in modulation and analog-to-digital conversion was first recognized during the early development of pulse-code modulation systems, especially in the 1948 paper of Oliver, Pierce, and Shannon. Also in 1948, Bennett published the first high-resolution analysis of quantization and an exact analysis of quantization noise for Gaussian processes, and Shannon published the beginnings of rate distortion theory, which would provide a theory for quantization as analog-to-digital conversion and as data compression. Beginning with these three papers of fifty years ago, we trace the history of quantization from its origins through this decade, and we survey the fundamentals of the theory and many of the popular and promising techniques for quantization.

The substitution of digital representations for analog images provides access to methods for digital storage and transmission and enables the use of a variety of digital image processing techniques, including enhancement and computer assisted screening and diagnosis. Lossy compression can further improve the efficiency of transmission and storage and can facilitate subsequent image processing. Both digitization (or digital acquisition) and lossy compression alter an image from its traditional form, and hence it becomes important that any such alteration be shown to improve or at least not damage the utility of the image in a screening or diagnostic application. One approach to demonstrating in a quantifiable manner that a specific image mode is at least equal to another is by clinical experiment simulating ordinary practice and suitable statistical analysis. In this paper we describe a general protocol for performing such a verification and present preliminary results of a specific experiment designed to show that 12 bpp digital mammograms compressed in a lossy fashion to 0.015 bpp using an embedded wavelet coding scheme result in no significant differences from the analog or digital originals. Die Ersetzung analoger Bilder durch digitale Darstellungen erlaubt eine digitale Speicherung und Übertragung sowie den Einsatz einer Vielzahl von Methoden der digitalen Bildverarbeitung, z.B. zur Verbesserung der Bildqualität und zum computerunterstützten Screening bzw. zur computerunterstützten Diagnose. Eine verlustbehaftete Kompression kann die Effizienz der Übertragung oder Speicherung weiter steigern und eine nachfolgende Bildverarbeitung erleichtern. Sowohl die Digitalisierung (oder digitale Aufnahme) als auch die verlustbehaftete Kompression ändern ein Bild bezüglich seiner ursprünglichen Form. Deswegen ist es wichtig, zu zeigen daβ eine solche Veränderung die Nützlichkeit des Bildes bei Screening- oder diagnostischen Anwendungen steigert oder wenigstens nicht beeinträchtigt. Eine Möglichkeit, auf quantifizierbare Weise zu zeigen, daβ eine bestimmte Bilddarstellung einer anderen zumindest äquivalent ist, ist ein die gewöhnliche Praxis simulierendes klinisches Experiment und eine geeignete statistische Analyse. In diesem Artikel beschreiben wir ein allgemeines Protokoll für die Durchführung einer solchen Verifikation. Wir präsentieren weiters vorläufige Resultate eines spezifischen Experiments, welches zeigt, daβ die verlustbehaftete Kompression digitaler Mammogramme von 12 bpp auf 0.15 bpp mittels einer eingebetteten Wavelet-Codierung zu keinen signifikanten Unterschieden von den analogen oder digitalen Originalen führt. La substitution d'images analogiques par des représentations numériques donne accès à des méthodes de stockage et de transmission numériques, et permet l'utilisation d'une grande variété de techniques de traitement d'images, incluant le rehaussement, les tests de dépistage assisté ordinateur et le diagnostic. La compression avec pertes peut encore améliorer l'efficacité de la transmission et du stockage, et peut faciliter le traitement ultérieur des images. La numérisation et la compression avec pertes altérant toutes deux une image par rapport à sa forme traditionnelle, il devient important de montrer qu'une telle altération améliore, ou du moins ne réduit pas, l'utilité de l'image dans un screening ou une application de diagnostic. Une approche pour démontrer d'une manière quantifiable qu'un mode d'image spécifique est au moins égal à un autre est l'expérimentation clinique simulant la pratique ordinaire jointe à une analyse statistique adaptée. Dans cet article, nous décrivons un protocole général pour effectuer une telle vérification et présentons les résultats préliminaires d'une expérience faite pour montrer que des mamogrammes numérisés à 12 bpp et comprimés avec pertes à 0.15 bpp à l'aide d'une technique de codage par ondelettes incluses ne présentent pas de différences significatives par rapport aux versions originales analogique ou numérique.

Transmission of digital subband-coded images over lossy packet networks presents a reconstruction problem at the decoder. This paper presents two techniques for reconstruction of lost subband coefficients, one for low-frequency coefficients and one for high-frequency coefficients. The low-frequency reconstruction algorithm is based on inherent properties of the hierarchical subband decomposition. To maintain smoothness and exploit the high intraband correlation, a cubic interpolative surface is fit to known coefficients to interpolate lost coefficients. Accurate edge placement, crucial for visual quality, is achieved by adapting the interpolation grid in both the horizontal and vertical directions as determined by the edges present. An edge model is used to characterize the adaptation, and a quantitative analysis of this model demonstrates that edges can be identified by simply examining the high-frequency bands, without requiring any additional processing of the low-frequency band. High-frequency reconstruction is performed using linear interpolation, which provides good visual performance as well as maintains properties required for edge placement in the low-frequency reconstruction algorithm. The complete algorithm performs well on loss of single coefficients, vectors, and small blocks, and is therefore applicable to a variety of source coding techniques.

This paper presents techniques for the design of generic constrained and recursive vector quantizer encoders implemented by table-lookups. These vector quantizers include entropy-constrained VQ, tree structured VQ, classified VQ, product VQ, mean-removed VQ, multi-stage VQ, hierarchical VQ, nonlinear interpolative VQ, predictive VQ and weighted universal VQ. Our algorithms combine these different VQ structures with hierarchical table-lookup vector quantization. Thus the full-search encoder in the different VQ structures is replaced by a table-lookup encoder, which approximates the search, but the codebook structure and decoder are the same. In these table-lookup encoders, input vectors to the encoders are used directly as addresses in code tables to choose the codewords. In order to preserve manageable table sizes for large dimension VQs, we use hierarchical structures to quantize the vector successively in stages. Since both the encoder and decoder are implemented by table-lookups, there are no arithmetic computations required in the final system implementation. To further improve the subjective quality of the compressed images we use block transform based table-lookup vector quantizers with subjective distortion measures. There is no need to perform the forward or reverse transforms as they are implemented in the tables.

Classification and compression play important roles today in communicating digital information and their combination is useful in many applications. The aim is to produce image classification without any further signal processing on the compressed image. This paper presents techniques for the design of block based joint classifier and quantizer classifiers/encoders implemented by table lookups. In the table lookup classifiers/encoders, input vectors to the encoders are used directly as addresses in code tables to choose the codewords with the appropriate classification information. In order to preserve manageable table sizes for large dimension VQs, hierarchical structures that quantize the vector successively in stages are used. Since both the classifier/encoder and decoder are implemented by table lookups, there are no arithmetic computations required in the final system implementation. They are unique in that both the classifier/encoder and the decoder are implemented with only table lookups and are amenable to efficient software and hardware solutions.

Prediction can play an important role in image compression. Better rate-distortion tradeoffs can be achieved by coding the residuals from predictive schemes rather than the direct pixel values. The price is only a modest increase in complexity. A variety of linear and nonlinear predictors have been used successfully in applications of predictive vector quantization. It makes sense that the better the prediction, the better the resulting compression. One method by which to improve predictive accuracy is to reduce the variability of the predictions. We here apply ridge regression in order to obtain prediction coefficients for use in a predictive vector quantizer as an alternative to standard Wiener-Hopf techniques.

This paper presents an algorithm for image compression using finite state hierarchical table-lookup vector quantization. Finite state vector quantizers are vector quantizers with memory. Finite state vector quantization (FSVQ) takes advantage of the correlation between adjacent blocks of pixels in an image and also helps in overcoming the complexity problem of block memoryless VQ for large block sizes by using smaller block sizes for similar performance. FSVQ algorithms typically try to preserve edge and gray scale gradient continuity across block boundaries in images in order to reduce blockiness. Our algorithm combines FSVQ with hierarchical table-lookup vector quantization. Thus the full-search encoder in an FSVQ is replaced by a table-lookup encoder. In these table lookup encoders, input vectors to the encoder are used directly as addresses in code tables to choose the code-words. In order to preserve manageable table sizes for large dimension VQs, we use hierarchical structures to quantize the vector successively in stages. Since both the encoder and decoder are implemented by table lookups, there are no arithmetic computations required in the final system implementation. To further improve the subjective quality of compressed images we use block transform based finite-state table-lookup vector quantizers with subjective distortion measures. There is no need to perform the forward or reverse transforms as they are implemented in the tables.

Multimedia applications such as educational videos and color facsimile contain images that are rich in both textual and continuous tone data. Because these two types of data have different properties, segmentation of the images into text and continuous tone data can improve compression by allowing different compression parameters or even algorithms to be employed on the different types. We propose and compare algorithms that use classification trees (CLTR) or tree-structured vector quantization (TSVQ) for block-based classification in mixed-mode images. We also examine different types of features that can be used in these classifiers. The results show that using linear transform features with either the CLTR or TSVQ can be effective for accurate text classification. In addition, the results indicate that combining these classifiers with another TSVQ that is designed simultaneously to minimize both compression and classification error can provide better classification than does either system alone.

We present an algorithm for image compression which involves adaptively segmenting a block of residuals resulting from prediction, while encoding them using hierarchical table lookup vector quantization. An optimum decomposition of the block allows an image to be adaptively quantized depending on the statistics of the residual block being encoded. This is useful since most images are nonstationary and have some regions with high detail and some with little. With an optimum decomposition, we can adaptively allocate bits by varying the block size to be quantized. Predictive vector quantization (PVQ) allows us to take advantage of the correlation between adjacent blocks of pixels being encoded by providing memory. The quadtree structure is used to represent the segmentation information and is sent as side information. To reduce the encoding complexity, we use hierarchical table lookups so no arithmetic computations have to be performed to find the minimum distortion codeword. To further improve the performance, we use a variable rate code to decrease the rate. Also, to improve the subjective quality of the image, we use subjective distortion measures.

Subband and wavelet decompositions are powerful tools in image coding because of their decorrelating effects on image pixels, the concentration of energy in a few coefficients, their multirate/multiresolution framework, and their frequency splitting, which allows for efficient coding matched to the statistics of each frequency band and to the characteristics of the human visual system. Vector quantization (VQ) provides a means of converting the decomposed signal into bits in a manner that takes advantage of remaining inter and intraband correlation as well as of the more flexible partitions of higher dimensional vector spaces. Since 1988, a growing body of research has examined the use of VQ for subband/wavelet transform coefficients. We present a survey of these methods.

Classification and compression play important roles in communicating digital information. Their combination is useful in many applications, including the detection of abnormalities in compressed medical images. In view of the similarities of compression and low-level classification, it is not surprising that there are many similar methods for their design. Because some of these methods are useful for designing vector quantizers, it seems natural that vector quantization (VQ) is explored for the combined goal. We investigate several VQ-based algorithms that seek to minimize both the distortion of compressed images and errors in classifying their pixel blocks. These algorithms are investigated with both full search and tree-structured codes. We emphasize a nonparametric technique that minimizes both error measures simultaneously by incorporating a Bayes risk component into the distortion measure used for the design and encoding. We introduce a tree-structured posterior estimator to produce the class posterior probabilities required for the Bayes risk computation in this design. For two different image sources, we demonstrate that this system provides superior classification while maintaining compression close or superior to that of several other VQ-based designs, including Kohonen's (1992) "learning vector quantizer" and a sequential quantizer/classifier design.

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/sup -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/sup -1/) when the universe of sources is countable, and as O(n/sup -1+/spl epsiv//) when the universe of sources is infinite-dimensional, under appropriate conditions.

We propose a predictive coding algorithm for lossy compression of digital halftones produced by clustered-dot dithering. In our scheme, the predictor estimates the size and shape of each halftone dot (cluster) based on the characteristics of neighboring clusters. The prediction template depends on which portion, or sub-cell, of the dithering matrix produced the dot. Information loss is permitted through imperfect representation of the prediction residuals. For some clusters, no residual is transmitted at all, and for others, information about the spatial locations of bit errors is omitted. Specifying only the number of bit errors in the residual is enough to allow the decoder to form an excellent approximation to the original dot structure. We also propose a simple alternative to the ordinary Hamming distance for computing distortion in bi-level images. Experiments with 1024/spl times/1024 images, 8/spl times/8 dithering cells, and 600 dpi printing have shown that the coding algorithm maintains good image quality while achieving rates below 0.1 bits per pixel.

Packet-based transmission of subband coded images over lossy networks presents a reconstruction problem at the decoder. Accurate reconstruction of the high-energy low frequency subband coefficients is imperative in providing consumer-grade image quality. This paper introduces a family of one-dimensional quadrature mirror filters (QMFs) designed to minimize the mean-squared error of reconstructed low frequency coefficients for a given reconstruction algorithm to be implemented at the decoder. Mean-reconstruction, in which a missing coefficient is replaced with the average of its neighbors either horizontally or vertically, is selected for its simplicity and implementation ease. The resulting filters perform well as QMFs and provide the desired reconstruction properties in the event of loss. While the filters are developed using mean-reconstruction the filter design algorithm can be used with more sophisticated reconstruction techniques, providing that the mean-squared error can be expressed in the appropriate quadratic form.

A Bayes risk weighted vector quantizer (Bayes VQ) combines compression and low-level classification of images by incorporating a Bayes risk component into the distortion measure used to design the code. The class posterior probabilities required for the Bayes risk computation can be estimated based on a labeled training sequence. We introduce two new methods for estimating these posteriors. In particular, two types of tree-structured estimators are constructed by applying the classification and regression tree algorithm CART to eight features of the training sequence. We apply the resulting Bayes VQ systems to aerial photographs where the goal is to compress the images and classify man-made and natural regions. These systems provide classification superior to that of previous work with Bayes VQ while maintaining similar compression performance. The systems also provide moderate to substantial improvement in classification with only a small loss in compression to performance obtained with a modified version of Kohonen's (1988) "learning vector quantizer" and with an independent design of quantizer and classifier.

Image quality and utility become crucial issues for engineers, scientists, patients, regulators, administrators, insurance companies, and lawyers whenever there are changes in the technology by which medical images are produced. Examples of such changes include analog-to-digital conversion, lossy compression for efficient transmission and storage, image enhancement, and computer-aided methodology for diagnosis that affects the appearances of images. This paper is a summary of some principles for designing protocols for clinical experiments to quantify the relative qualities and utilities of different images, here analog, digital, and lossy compressed digital mammograms. A talk supplemented this paper with a status report on the specific experiment described which is scheduled to be conducted during summer 1995.

Discusses the convergence properties of an iterative design algorithm for JPEG quantization tables. The algorithm is useful for generating tables that control, to a specified amount, the proportion of quantization error produced (on average) by the JPEG encoder in each of the 64 DCT frequency bins. An initial table is iteratively improved in such a way that the achieved quantization error profile more closely approximates the desired profile, which might be based on a human vision model or various other criteria. The convergence of the design algorithm is relatively easy to ensure if the desired error profile is modified at each iteration to account for changes in the achieved error values. Adjustments to the quantization table entries may be made according to several different schemes. We propose a successive approximation method that is guaranteed to converge after no more than eight iterations, and also discuss some alternative strategies.

We describe a method of combining classification and compression into a single vector quantizer by incorporating a Bayes risk term into the distortion measure used in the quantizer design algorithm. Once trained, the quantizer can operate to minimize the Bayes risk weighted distortion measure if there is a model providing the required posterior probabilities, or it can operate in a suboptimal fashion by minimizing the squared error only. Comparisons are made with other vector quantizer based classifiers, including the independent design of quantization and minimum Bayes risk classification and Kohonen's LVQ. A variety of examples demonstrate that the proposed method can provide classification ability close to or superior to learning VQ while simultaneously providing superior compression performance.>

A new algorithm for variable dimension weighted universal coding is introduced. Combining the multi-codebook system of weighted universal vector quantization (WUVQ), the partitioning technique of variable dimension vector quantization, and the optimal design strategy common to both, variable dimension WUVQ allows mixture sources to be effectively carved into their component subsources, each of which can then be encoded with the codebook best matched to that source. Application of variable dimension WUVQ to a sequence of medical images provides up to 4.8 dB improvement in signal to quantization noise ratio over WUVQ and up to 11 dB improvement over a standard full-search vector quantizer followed by an entropy code. The optimal partitioning technique can likewise be applied with a collection of noiseless codes, as found in weighted universal noiseless coding (WUNC). The resulting algorithm for variable dimension WUNC is also described.>

The authors investigate a method that combines compression and low-level classification of images by designing codes that contain implicit information regarding classification. The design consists of a tree-structured vector quantizer (TSVQ) that incorporates a Bayes risk term into the distortion measure used in the quantizer design algorithm in order to permit a tradeoff of mean squared error and classification error. Once designed, the quantizer can operate to minimize the Bayes risk weighted distortion measure by incorporating the posterior probabilities into the encoding process. A completely nonparametric design algorithm is constructed by estimating these posterior distributions using a TSVQ that incorporates the classification error into the splitting criterion. This approach is used to analyze simulated data and to identify tumors in CT lung images. Comparisons are made with other vector quantizer based classifiers, including Kohonen's "learning vector quantizer." For the examples considered, their method provided a classification that was superior to the other methods while simultaneously providing close to or superior compression performance.>

This paper examines two vector quantization algorithms which can combine the tasks of compression and classification: Bayes risk weighted vector quantization (BRVQ) proposed by Oehler et al. (1991), and optimized learning vector quantization 1 (OLVQ1) proposed by Kohonen et al. (1988). BRVQ uses a parameter /spl lambda/ to control the tradeoff between compression and classification. BRVQ performance is studied for a range of /spl lambda/ values for four classification problems. Increasing the /spl lambda/ parameter in BRVQ is intended to improve classification performance. However, for two of the problems studied, increasing /spl lambda/ degraded classification performance. A majority rule reclassification of the final codebook (using only the training set) greatly improves high-/spl lambda/ BRVQ performance for these cases. Finally, we compare the classification performance and mean square error (MSE) performance of BRVQ to that of OLVQ1 for four classification problems. BRVQ with codebook reclassification is found to have a lower MSE than OLVQ1 while maintaining comparable, but slightly inferior, classification performance.>

The authors introduce a one-pass adaptive universal quantization technique for real, bounded alphabet, stationary sources. The algorithm is set on line without any prior knowledge of the statistics of the sources which it might encounter and asymptotically achieves ideal performance on all sources that it sees. The system consists of an encoder and a decoder. At increasing intervals, the encoder refines its codebook using knowledge about incoming data symbols. This codebook is then described to the decoder in the form of updates on the previous codebook. The accuracy to which the codebook is described increases as the number of symbols seen, and thus the accuracy to which the codebook is known, grows.>

A reconstruction technique for block-based transform-coded images transmitted over lossy packet networks is proposed and demonstrated. Lost blocks of transform coefficients are reconstructed via linear interpolation using the same coefficients from adjacent blocks, thus preserving high frequency details and local image characteristics. Determination of the interpolation coefficients, or weights, is combined with vector quantization in a single step at the encoder, and the resulting quantized weights are transmitted as overhead information. The required transmission overhead is less than 10% for typical JPEG-coded images, and the computation for reconstruction of a block is less than that required for simply decoding a block using an inverse discrete cosine transform. This technique is applicable to both luminance and chrominance components, and the reconstructed images maintain good visual quality at loss rates as high as 30%.>

We propose a coding algorithm for lossy compression of digital halftones produced by clustered-dot dithering. Our scheme is based on pixel ordering and run-length coding, and has small memory and computation requirements. Data reduction techniques give an efficient, but imperfect, representation of the run lengths, allowing low-rate coding along with a good approximation to the original dot structure. Experiments with 1024/spl times/1024 images, 8/spl times/8 dithering cells, and 600 dpi printing have shown that the algorithm maintains good image quality while achieving rates of about 0.1 bits per pixel.>

A novel algorithm is described for constructing a progressive, multiresolution compression code. The codec consists of nested levels of tree-structured vector quantizers (TSVQs) where the codebook for each level of the nested TSVQs is constructed from the terminal leaves of the TSVQ from the previous level. In order to generate a multiresolution output in a progressive manner, the codeword dimension at each level's TSVQ is greater than or equal to those of the previous levels. Pruning is performed on the nested TSVQs to achieve the bit allocation across the levels. The resulting pruned TSVQ provides a multiresolution output with low computational complexity at the decoder while simultaneously providing superior performance to ordinary pruned TSVQ at low bit rates.>

We compare the compression and classification performance of various vector-quantizer based classifiers on real images. These quantizers include a Bayes risk weighted vector quantizer, Kohonen's "learning vector quantizer" (LVQ), and an independent design of quantizer and classifier. Both full search and tree-structured codes are considered. The quantizers are applied to aerial photographs and medical images where the goal is to both compress the images and classify particular features within the images. We demonstrate that for the examples considered, Bayes risk weighted vector quantization with posterior estimation obtains similar or superior classification and compression performance to that obtained with the other systems.>

We investigated the effects of lossy image compression on measurement accuracy in magnetic resonance images. Thirty chest scans were compressed to five different levels using predictive pruned tree-structured vector quantization (predictive PTSVQ). Three radiologists measured the diameters of the four principal blood vessels on each image. Errors were analyzed relative to both an independent standard and personal performance on uncompressed images. Data were compared with both t and Wilcoxon tests. We conclude that for the purpose of measuring blood vessels in the chest, there is no significant difference in measurement accuracy when images are compressed up to 16:1 with predictive PTSVQ.>

Compressing a digital image can facilitate its transmission, storage, and processing. As radiology departments become increasingly digital, the quantities of their imaging data are forcing consideration of compression in picture archiving and communication systems (PACS) and evolving teleradiology systems. Significant compression is achievable only by lossy algorithms, which do not permit the exact recovery of the original image. This loss of information renders compression and other image processing algorithms controversial because of the potential loss of quality and consequent problems regarding liability, but the technology must be considered because the alternative is delay, damage, and loss in the communication and recall of the images. How does one decide if an image is good enough for a specific application, such as diagnosis, recall, archival, or educational use? The authors describe three approaches to the measurement of medical image quality: signal-to-noise ratio (SNR), subjective rating, and diagnostic accuracy. They compare and contrast these measures in a particular application, consider in some depth recently developed methods for determining diagnostic accuracy of lossy compressed medical images and examine how good the easily obtainable distortion measures like SNR are at predicting the more expensive subjective and diagnostic ratings. The examples are of medical images compressed using predictive pruned tree-structured vector quantization, but the methods can be used for any digital image processing that produces images different from the original for evaluation.>

For a stationary ergodic source, the source coding theorem and its converse imply that the optimal performance theoretically achievable by a fixed-rate or variable-rate block quantizer is equal to the distortion-rate function, which is defined as the infimum of an expected distortion subject to a mutual information constraint. For a stationary nonergodic source, however, the. Distortion-rate function cannot in general be achieved arbitrarily closely by a fixed-rate block code. We show, though, that for any stationary nonergodic source with a Polish alphabet, the distortion-rate function can be achieved arbitrarily closely by a variable-rate block code. We also show that the distortion-rate function of a stationary nonergodic source has a decomposition as the average of the distortion-rate functions of the source's stationary ergodic components, where the average is taken over points on the component distortion-rate functions having the same slope. These results extend previously known results for finite alphabets.>

The authors combine pruned tree-structured vector quantization (pruned TSVQ) with Itoh's (1987) universal noiseless coder. By combining pruned TSVQ with universal noiseless coding, they benefit from the "successive approximation" capabilities of TSVQ, thereby allowing progressive transmission of images, while retaining the ability to noiselessly encode images of unknown statistics in a provably asymptotically optimal fashion. Noiseless compression results are comparable to Ziv-Lempel and arithmetic coding for both images and finely quantized Gaussian sources.>

Weighted universal vector quantization uses traditional codeword design techniques to design locally optimal multi-codebook systems. Application of this technique to a sequence of medical images produces a 10.3 dB improvement over standard full search vector quantization followed by entropy coding at the cost of increased complexity. In this proposed variation each codebook in the system is given a mean or 'prediction' value which is subtracted from all supervectors that map to the given codebook. The chosen codebook's codewords are then used to encode the resulting residuals. Application of the mean-removed system to the medical data set achieves up to 0.5 dB improvement at no rate expense.>

The goal is to produce codes where the compressed image incorporates classification information without further signal processing. This technique can provide direct low level classification or an efficient front end to more sophisticated full-frame recognition algorithms. Vector quantization is a natural choice because two of its design components, clustering and tree-structured classification methods, have obvious applications to the pure classification problem as well as to the compression problem. The authors explicitly incorporate a Bayes risk component into the distortion measure used for code design in order to permit a tradeoff of mean squared error with classification error. This method is used to analyze simulated data, identify tumors in computerized tomography lung images, and identify man-made regions in aerial images.>

A review is presented of vector quantization, the mapping of pixel intensity vectors into binary vectors indexing a limited number of possible reproductions, which is a popular image compression algorithm. Compression has traditionally been done with little regard for image processing operations that may precede or follow the compression step. Recent work has used vector quantization both to simplify image processing tasks, such as enhancement classification, halftoning, and edge detection, and to reduce the computational complexity by performing the tasks simultaneously with the compression. The fundamental ideas of vector quantization are explained, and vector quantization algorithms that perform image processing are surveyed.>

The performance of a vector quantizer can be improved by using a variable-rate code. Three variable-rate vector quantization systems are applied to speech, image, and video sources and compared to standard vector quantization and noiseless variable-rate coding approaches. The systems range from a simple and flexible tree-based vector quantizer to a high-performance, but complex, jointly optimized vector quantizer and noiseless code. The systems provide significant performance improvements for subband speech coding, predictive image coding, and motion-compensated video, but provide only marginal improvements for vector quantization of linear predictive coefficients in speech and direct vector quantization of images. Criteria are suggested for determining when variable-rate vector quantization may provide significant performance improvement over standard approaches.>

A theory of overall quantization noise for nonsubtractive dither was originally developed in unpublished work by J.N. Wright and by T.J. Stockham and subsequently expanded by L.K. Brinton, S.P. Lipshitz, J. Vanderkooy, and R.A. Wannamaker. It is suggested that since these latter results are not as well known as the original results, misunderstanding persists in the literature. New proofs of the properties of quantizer dither, both subtractive and nonsubtractive, are provided. The new proofs are based on elementary Fourier series and Rice's characteristic function method and do not require the use of generalized functions (impulse trains of Dirac delta functions) and sampling theorem arguments. The goal is to provide a unified derivation and presentation of the two forms of dithered quantizer noise based on elementary Fourier techniques.>

The authors apply a lossy compression algorithm to medical images, and quantify the quality of the images by the diagnostic performance of radiologists, as well as by traditional signal-to-noise ratios and subjective ratings. The authors' study is unlike previous studies of the effects of lossy compression in that they consider nonbinary detection tasks, simulate actual diagnostic practice instead of using paired tests or confidence rankings, use statistical methods that are more appropriate for nonbinary clinical data than are the popular receiver operating characteristic curves, and use low-complexity predictive tree-structured vector quantization for compression rather than DCT-based transform codes combined with entropy coding. The authors' diagnostic tasks are the identification of nodules (tumors) in the lungs and lymphadenopathy in the mediastinum from computerized tomography (CT) chest scans. Radiologists read both uncompressed and lossy compressed versions of images. For the image modality, compression algorithm, and diagnostic tasks the authors consider, the original 12 bit per pixel (bpp) CT image can be compressed to between 1 bpp and 2 bpp with no significant changes in diagnostic accuracy. The techniques presented here for evaluating image quality do not depend on the specific compression algorithm and are useful new methods for evaluating the benefits of any lossy image processing technique.

A design procedure for a vector quantizer which simultaneously performs halftoning and compression of sampled monochrome images is presented. The design method is based on the generalized Lloyd algorithm which results in a quantizer that is locally optimal under a given weighted-squared-error distortion measure. The optimal system is approximated by means of a computationally efficient vector halftoning algorithm. A test image encoded by this method at 0.094 b/pixel is compared with images of the same rate produced by independent compression and halftoning steps.>

Combined vector quantization and adaptive histogram equalization Pamela C. Cosman Eve A. Riskin Robert M. Gray tDurand Building, Department of Electrical Engineering Stanford University, Stanford, CA, 94305-4055 Department of Electrical Engineering, FT- 10 University of Washington, Seattle, WA 98195 ABSTRACT Adaptive histogram equalization is a contrast enhancement technique in which each pixel is remapped to an intensity proportional to its rank among surrounding pixels in a selected neighborhood. We present work in which adaptive histogram equalization is performed on the codebook of a tree-structured vector quantizer so that encoding with the resulting codebook performs both compression and contrast enhancement. The algorithm was tested on magnetic resonance brain scans from different subjects and the resulting images were significantly contrast enhanced. 1. INTRODUCTION Histogram equalization refers to a set of contrast enhancement techniques which attempt to spread out the intensity levels occurring in an image over the full available range.1 Histogram equalization is a competitor of interactive intensity windowing, which is the established contrast enhancement technique for medical images. In global histogram equalization, one calculates the intensity histogram for the entire image and then remaps each pixel's intensity proportional to its rank among all the pixel intensities. In adaptive histogram equalization (AHE), the histogram is calculated only for pixels in a context region, usually a square, and the remapping is done for the center pixel of the square. This can be called pointwise histogram equalization because, for each point in the image, one calculates the histogram for the square context region centered on that point. Because this is very computationally intensive, the bilinear interpolative version is an alternative that lowers the computational complexity.2 It calculates the histogram for only a set of non-overlapping context regions that cover the image and the reniapping of pixel intensity values is then exact for only the small number of pixels that are at the centers of these context regions. For all other pixels, a bilinear interpolation from the nearest context region centers determines the appropriate remapping function. With the bilinear interpolative version of AHE, the remapping function for a given pixel of intensity i at location (, y) is determined from the nearest 4 context regions as shown in figure 1. Ifm+_ denotes the mapping at the grid pixel (x+, y.) to the upper right of (x, y), and similar subscripts are used for the other surrounding context regions, then the interpolated AHE result is given by2: in(i) = a[bm(i) + (1 — b)m_(i)J + [1 — u]{bm_(i) + (1 — b)m__(i)], b= here y+—y- O-8194-0805-O/92/$4.QO SPIE Vol. 1653 Image Capture, Formatting, and Display (1992) / 213 Downloaded From: http://proceedings.spiedigitallibrary.org/ on 05/20/2014 Terms of Use: http://spiedl.org/terms

A modulo sigma-delta modulator is introduced, and the behavior of the quantization error is derived. The system consists of a modulo limiter followed by a sigma-delta modulator. The limiter confines the input to the no-overload region of the sigma-delta modulator, and the modulo arithmetic performed by the limiter is amenable to recently developed techniques for the exact analysis of quantizer error behavior in sigma-modulators with bounded inputs. The quantization error behavior is derived for a modulator driven by a quasi-stationary random process. The limit distribution and the power of the quantization error are found. Except for some singular cases, the normalized quantization error is uniformly distributed in (-1/2, 1/2). The power spectrum and the autocorrelation function of the quantization error with a causal ARMA (p, q) process input are also derived. It is shown that the quantization noise is white when the input is a random process with stationary independent increments. Simulation results support the theoretical analysis.>

Exact descriptions of the behavior of quantization noise for single-loop, multistage (cascade), and multiloop sigma-delta modulators for a variety of input signals have been found during recent years under the assumption of ideal integration. The techniques used to solve the ideal integrator case do not easily extend to the more realistic model of a leaky integrator sigma-delta. In this paper a dynamical system representation for the leaky integrator sigma-delta with a constant input is developed. Several properties of the resulting piecewise monotone and piecewise linear transformation T on the interval

Histogram equalization is performed on the codebook of a tree-structured vector quantizer. Encoding with the resulting codebook performs both compression and contrast enhancement. It is also possible to perform intensity windowing on the codebook, or a combination of intensity windowing and histogram equalization so that these need not be separate post-processing steps.>

A vector quantization compression system is presented which is suitable for use in commercial applications, i.e., efficient enough to encode a wide variety of images and simple enough to decode the images in real time using software (for machine compatibility). A fixed-rate code with unbalanced tree structure is used, and a method of unbalanced tree growing is extended. Simple prediction techniques are applied to improve coded image quality.>

An exact analysis of the quantization error of the single-loop single-stage sigma-delta modulator with a multilevel quantizer and single-bit feedback is given. It is shown that the output sequence of this system is identical to that of a coder using a multilevel digital-to-analog converter (DAC) in the feedback loop provided that an extra bit is available in the forward quantizer.>

A technique is presented for directly designing an unbalanced variable rate tree-structured vector quantizer. The algorithm is an extension of an algorithm for decision tree design which grows the tree one node at a time rather than one layer at a time. The node that is split is the one that yields the greatest slope of decrease in distortion to increase in rate. This is performing a lookahead step of depth one. The authors then modify the growing technique to allow for lookahead of depths two and three. It is found that two- and three-step lookahead provide only slight improvement in the signal to noise ratio of the overall tree (on the order of 0.6 dB).>

The spectrum of the quantization error in a dithered sigma-delta modulator is derived under the constraint that the dithering signal does not cause overload. The results apply to DC, sinusoidal, and more general quasi-stationary signals. It is shown in the case of a simple sigma-delta modulation that no-overload dithering can smooth the error spectrum and can make the quantization error asymptotically uncorrelated with the input. It does not, however, make the quantization error white. In the case of multistage sigma-delta modulation with the appropriate dithering, the quantization error becomes white, even for a system with only two stages. The signal-to-quantization-noise ratio (SQNR) is derived for sigma-delta and multistage sigma-delta oversampled analog-to-digital conversion with additive dithering. Simulation results, are presented to support the theoretical analysis.>

A time-domain analysis of sigma-delta modulation with linear filter decoding has been provided. The decoding operation of the 1-b output from a sigma-delta modulator can always be decomposed, and the final output of the decoding filter is the sum of signal term s/sub H/ and noise term n/sub H/. The exact form of s/sub H/ and n/sub H/ has been derived. Two typical sinc and since/sup 2/ digital decoding filters are studied. The only condition imposed on the input x/sub n/ is that x/sub n/ belongs to (-b,b), to avoid overloading the sigma-delta modulator. The results apply even to the case when the signal is not oversampled.>

Several results describing the behavior of quantization noise in a unified and simplified manner are discussed. Exact formulas for quantizer noise spectra are developed. They are applied to a variety of systems and inputs, including scalar quantization (PCM), dithered PCM, sigma-delta modulation, dithered sigma-delta modulation, two-stage sigma-delta modulation, and second-order sigma-delta modulation.>

In a decentralized hypothesis testing network, several peripheral nodes observe an environment and communicate their observations to a central node for the final decision. The presence of capacity constraints introduces theoretical and practical problems. The following problem is addressed: given that the peripheral encoders that satisfy these constraints are scalar quantizers, how should they be designed in order that the central test to be performed on their output indices is most powerful? The scheme is called cooperative design-separate encoding since the quantizers process separate observations but have a common goal; they seek to maximize a system-wide performance measure. The Bhattacharyya distance of the joint index space as such a criterion is suggested, and a design algorithm to optimize arbitrarily many quantizers cyclically is proposed. A simplified version of the algorithm, namely an independent design-separate encoding scheme, where the correlation is either absent or neglected for the sake of simplicity, is outlined. Performances are compared through worked examples.>

The response of a single-loop sigma-delta modulator to an independent identically distributed (i.i.d.) Gaussian input signal is analyzed. A continuous-time stochastic model is developed and the connection of the model to the system is described. A condition is given so that the difference between the behavior of the model and that of the true system can be made arbitrarily small. Theories from renewal and Wiener processes are applied to show the convergence and mixing properties of the output sequence. Also derived is the power spectrum of the quantization noise. Compared to the spectrum when the input is DC, the i.i.d. Gaussian random process smears the discrete spectrum into band structures.>

A recently developed technique for variable-rate vector quantizer (VQ) design by P.A. Chou et al. (see IEEE Trans. Inf. Theory, vol.35, no.2, p.299-315, 1989) has been applied to both memoryless and predictive VQ of images. This technique, called pruned tree-structured vector quantization (PTSVQ), uses variable-depth encoders that are tree-structured and thus have very low design and search complexity. PTSVQ is applied to a series of medical images, and gains over full-search VQ of up to 3.78 dB in the signal-to-noise-ratio (SNR) are measured. On still images from the USC database, gains of up to 1.63 dB in the peak SNR are realized for predictive PTSVQ over predictive full search VQ, resulting in high image quality at 0.51 bits per pixel.>

The authors introduce a novel approach to narrow- and medium-band speech coding that can dynamically balance the transmission rate between the excitation and the spectral parameters. The coding algorithm, called multimode coding, operates several coding blocks, each of which has a different bit assignment in parallel, and selects the optimum coding block frame by frame based on an evaluation of the reproduced speech quality. This coding algorithm is applied to 4.8 and 8.0 kb/s CELP coders, and 2.0-2.4 dB of SNRseg improvement is achieved over conventional CELP coders. The spectral distortion measure is added as an evaluation function, improving the subjective speech quality.>

An exact discrete-time analysis of the moments and spectra of the quantization noise of a discrete-time single-loop sigma-delta modulator with a DC input is presented. An exact difference equation for the discrete-time nonlinear system is used to evaluate the first- and second-order moments and power spectrum of the binary quantizer noise and the binary quantizer output for a single-loop sigma-delta encoder with a DC input. It is shown that the sample mean and power of the binary quantization noise are consistent with the common uniform distribution assumption, but that the autocorrelation and power spectrum are not consistent with the white noise assumption. The results are used to evaluate the overall sample average mean squared quantization error as a function of the decimation filter used.>

An exact nonlinear difference equation is derived and solved for a simple sigma-delta modulator consisting of a discrete-time integrator and a binary quantizer inside a single feedback loop and an arbitrary input signal. It is shown that the system can be represented as an affine operation (discrete-time integration of a biased input) followed by a memoryless nonlinearity. An extension of the transform method for the analysis of nonlinear systems is applied to obtain formulas for first- and second-order time-average moments of the binary quantization noise, including the sample mean, energy, and autocorrelation. The results are applied to the special case of a sinusoidal input signal to evaluate these time averages and the power spectrum. In the limit of large oversampling ratios, the marginal moments behave as if the quantization noise had a uniform distribution. The spectrum is neither white nor continuous, however, even in the limit of large oversampling ratios.>

An algorithm introduced by L. Breiman et al. (1984) in the context of classification and regression trees is reinterpreted and extended to cover a variety of applications in source coding and modeling in which trees are involved. These include variable-rate and minimum-entropy tree-structured vector quantization, minimum expected cost decision trees, variable-order Markov modeling, optimum bit allocation, and computer graphics and image processing using quadtrees. A concentration on the first of these and a detailed analysis of variable-rate tree-structured vector quantization are provided. It is found that variable-rate tree-structured vector quantization outperforms not only the fixed-rate variety but also full-search vector quantization. The successive approximation character of variable-rate tree-structured vector quantization permits it to degrade gracefully if the rate is reduced at the encoder. This has applications to the problem of buffer overflow.>

A theoretical basis is provided for multistage sigma-delta modulation (MSM), which is a cascade realization of several single-loop sigma-delta modulators with a linear combinatorial network. Equations are derived describing the output and the quantization noise of MSM for an arbitrary input signal, and the noise-shaping characteristic of MSM is investigated. The spectral characteristics of an m-stage sigma-delta modulator with both DC and sinusoidal inputs are developed. For both types of inputs the binary quantizer noise of the mth (m>or=3) quantizer, which appears at the output as an mth order difference, is asymptotically white, uniformly distributed, and uncorrelated with the input level. It is also found that for an m-stage sigma-delta quantizer with either an ideal low-pass filter or a sinc/sup m+1/ filter decoder, the average quantization noise of the system is inversely proportional to the (2m+1)th power of the oversampling ratio. This implies that the high-order systems are favourable in terms of the trade-off between the quantization noise and oversampling ratio. Simulation results are presented to support the theoretical analysis.>

The authors consider how much performance advantage a fixed-dimensional vector quantizer can gain over a scalar quantizer. They collect several results from high-resolution or asymptotic (in rate) quantization theory and use them to identify source and system characteristics that contribute to the vector quantizer advantage. One well-known advantage is due to improvement in the space-filling properties of polytopes as the dimension increases. Others depend on the source's memory and marginal density shape. The advantages are used to gain insight into product, transform, lattice, predictive, pyramid, and universal quantizers. Although numerical prediction consistently overestimated gains in low rate (1 bit/sample) experiments, the theoretical insights may be useful even at these rates.>

Data compression by vector quantization is considered for sources which have been degraded by noise. It is shown that, by appropriately modifying the given distortion measure, the problem becomes a standard quantization problem for the noisy source and the modified distortion measure. For the special case of sources corrupted by statistically independent additive noise, the authors provide sufficient conditions on the original distortion measure and probability distributions of the source and the noise for convergence of the generalized Lloyd algorithm in designing the quantizers. The results are specialized to waveform and autoregressive model vector quantization using the weighted quadratic and the Itakura-Saito distortion measures, respectively.>

An explicit expression is derived for the minimum discrimination information (MDI) measure with respect to Gaussian priors for sources characterized by their mean and by any principal leading block of their covariance matrix. An explicit expression is provided for the MDI extension of the given partial covariance of the source with respect to a Gaussian prior. For zero-mean sources and zero-mean Gaussian priors that are asymptotically weakly stationary (AWS) processes, it is shown that the asymptotic MDI measure equals half the Itakura-Saito distortion measure between the asymptotic power spectral densities of the source and prior. Asymptotic MDI modelling of a given AWS source by autoregressive and autoregressive moving average models, which are AWS models, is considered, and conditions are given for convergence of the sample covariance estimator of the source to the stationary covariance used in the modelling.>

In speech recognition, vector quantizers have traditionally been used as a pre-processor for sophisticated algorithms such as hidden Markov modelling (HMM) or dynamic time warping (DTW). Recently, simpler systems based more directly on vector quantization (VQ) have been proposed for recognizing isolated words with small vocabularies. The major problem with these simple algorithms is the lack of temporal information. This paper describes a conditional histogram technique which incorporates temporal information by considering the relative likelihoods that certain codewords follow others. Simulation results show that this approach produces better decoding results than the simple VQ algorithm with similar complexity.

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.

Oversampled sigma-delta modulation has been proposed as a practical implementation for high rate analog-to-digital conversion because of its simplicity and its robustness against circuit imperfections. To date, mathematical developments of the basic properties of such systems have been based either on simplified continuous-time approximate models or on linearized discrete-time models where the quantizer is replaced by an additive white uniform noise source. In this paper, we rigorously derive several basic properties of a simple discrete-time single integrator loop sigma-delta modulator with an accumulate-and-dump demodulator. The derivation does not require any assumptions on the correlation or distribution of the quantizer error, and hence involves no linearization of the nonlinear system, but it does show that when the input is constant, the state sequence of the integrator in the encoder loop can be modeled exactly as a linear system in an appropriate space. Two basic properties are developed: 1) the behavior of the sigma-delta quantizer when driven by a constant input and its relation to uniform quantization, and 2) the rate-distortion tradeoffs between the oversampling ratio and the average mean-squared quantization error.

The generalized Lloyd algorithm is applied to the design of joint source and channel trellis waveform coders to encode discrete-time continuous-amplitude stationary and ergodic sources operating over discrete memoryless noisy channels. Experimental results are provided for independent and autoregressive Gaussian sources, binary symmetric channels, and absolute error and squared error distortion measures. Performance of the joint codes is compared with the tandem combination of a trellis source code and a trellis channel code on the independent Gaussian source using the squared error distortion measure operating over an additive white Gaussian noise channel. It is observed that the jointly optimized codes achieve performance close to or better than that of separately optimized tandem codes of the same constraint length. Performance improvement via a predictive joint source and channel trellis code is demonstrated for the autoregressive Gaussian source using the squared error distortion measure.

An important class of engineering problems involves sensing an environment and making estimates based on the phenomena sensed. In the traditional model of this problem, the sensors' observations are available to the estimator without alteration. There is .growing interest in {\em distributed} sensing systems in which several observations are communicated to the estimator over channels of limited capacity. The observations must be separately encoded so that the target can be estimated with minimum distortion. Two questions are addressed for a special case of this problem wherein there are two sensors which observe noisy data and communicate with a single estimator: 1) if the encoder is unlimited in complexity, what communication rates and distortions can be achieved, 2) if the encoder must be a quantizer (a mapping of a single observation sample into a digital output), how can it be designed for good performance? The first question is treated by the techniques of information theory. It is proved that a given combination of rates and distortion is achievable if there exist degraded versions of the observations that satisfy certain formulas. The second question is treated by two approaches. In the first, the outputs of the quantizers undergo a second stage of encoding which exploits their correlation to reduce the output rate. Algorithms which design the second stage are presented and tested. The second approach is based on the {\em distributional distance}, a measure of dissimilarity between two probability distributions. An algorithm to modify a quantizer for increased distributional distance is derived and tested.

A Markov channel is a discrete information channel that includes as special cases the finite state channels and finite state codes of information theory. Kieffer and Rahe proved that one-sided and two-sided Markov channels have the following property: If the input source to a Markov channel is asymptotically mean stationary (AMS), then so is the resulting input-output process and hence the ergodic theorem and the Shannon-McMillan-Breiman theorem hold for the input-output process. Kieffer and Rahe also provided a sufficient condition for any AMS ergodic source to yield an AMS ergodic input-output process. New conditions for a Markov channel to have this ergodicity property are presented and discussed here. Several relations are developed among various classes of channels, including weakly ergodic, indecomposable, and strongly mixing channels. Some connections between Markov channels and the theory of nonhomogeneous Markov chains are also discussed.

Trellis source codes consist of a finite-state machine decoder and a trellis search algorithm, such as the Viterbi algorithm, as the encoder. The encoder experiments with a local copy of the decoder and determines the best channel path map in the sense that it will yield the smallest average distortion between the source sequence and the reproduction sequence given the codebook. In this paper we present a coding system and a design algorithm for predictive trellis coding. Results obtained via simulation are compared for trellis and predictive trellis codes designed for first-order autoregressive sources with Gaussian and Laplacian innovations and for sampled speech. On a random source which models speech, simulation results of the predictive and nonpredictive trellis codes designed by the generalized Lloyd algorithm and those obtained by other researchers are compared. Issues related to computational complexity, the effects of initial codebook selection, training sequence segmentation, search length, channel errors, and algorithm convergence are addressed.

Most tree or trellis encoding data compression systems use decoders which form scalar outputs as a (possibly nonlinear) function of the contents of a shift register containing received channel symbols. We here develop design algorithms for trellis encoding systems having decoders not constrained to have such a scalar sliding-block code structure. In particular, we consider using the decoder of a finite-state vector quantizer together with a vector trellis search. Simulation results are presented for vector trellis encoding systems for Gauss-Markov sources, sampled speech data, and LPC speech data.

The generalized Lloyd algorithm for vector quantizer design is analyzed as a descent algorithm for nonlinear programming. A broad class of convex distortion functions is considered and any input distribution that has no singular-continuous part is allowed. A well-known convergence theorem is applied to show that iterative applications of the algorithm produce a sequence of quantizers that approaches the set of fixed-point quantizers. The methods of the theorem are extended to sequences of algorithms, yielding results on the behavior of the algorithm when an unknown distribution is approximated by a training sequence of observations. It is shown that as the length of the training sequence grows large that 1) fixed-point quantizers for the training sequence approach the set of fixed-point quantizers for the true distribution, and 2) limiting quantizers produced by the algorithm with the training sequence distribution perform no worse than limiting quantizers produced by the algorithm with the true distribution.

In this note we present a very simple method for improving the efficiency of minimum distortion encoding for vector quantization. Simulations indicates a reduction of up to 70 percent in the number of multiplications for a full search vector quantizer with a large number of codewords, and about 25-40 percent for a tree search vector quantizer. Similar improvement can be achieved in other vector quantization systems.

A finite-state vector quantizer (FSVQ) is a switched vector quantizer where the sequence of quantizers selected by the encoder can be tracked by the decoder. It can be viewed as an adaptive vector quantizer with backward estimation, a vector generalization of an AQB system. Recently a family of algorithms for the design of FSVQ's for waveform coding application has been introduced. These algorithms first design an initial set of vector quantizers together with a next-state function giving the rule by which the next quantizer is selected. The codebooks of this initial FSVQ are then iteratively improved by a natural extension of the usual memoryless vector quantizer design algorithm. The next-state function, however, is not modified from its initial form. In this paper we present two extensions of the FSVQ design algorithms. First, the algorithm for FSVQ design for waveform coders is extended to FSVQ design of linear predictive coded (LPC) speech parameter vectors using an Itakura-Saito distortion measure. Second, we introduce a new technique for the iterative improvement of the next-state function based on an algorithm from adaptive stochastic automata theory. The design algorithms are simulated for an LPC FSVQ and the results are compared with each other and to ordinary memoryless vector quantization. Several open problems suggested by the simulation results are presented.

A finite-state vector quantizer is a finite-state machine used for data compression: Each successive source vector is encoded into a codeword using a minimum distortion rule, and into a code book, depending on the encoder state. The current state and the selected codeword then determine the next encoder state. A finite-state vector quantizer is capable of making better use of the memory in a source than is an ordinary memoryless vector quantizer of the same dimension or blocklength. Design techniques are introduced for finite-state vector quantizers that combine ad hoc algorithms with an algorithm for the design of memoryless vector quantizers. Finite-state vector quantizers are designed and simulated for Gauss-Markov sources and sampled speech data, and the resulting performance and storage requirements are compared with ordinary memoryless vector quantization.

An end-point detector for LPC speech using squared prediction error look-ahead and automatic/manual threshold determination is described. The detector is algorithmically simple, computationally efficient,and uses only one decision parameter. Preliminary tests indicate that it is relatively immune to transient pulses and various low-level noises, yet preserves low-level speech sounds such as weak fricatives to a significant extent under moderate noise conditions. Tests indicate that 93.8% of automatically determined endpoints agree to within two frames of manually determined endpoints. The detector is especially suitable for use in vector-quantization based LPC systems, where the squared prediction error is easily available.

A real-time full search vector quantization system for speech waveform coding is implemented using LSTTL and CMOS devices. The system consists of low-pass filters, A/D and D/A converters, an algorithm for discriminating voiced and unvoiced speed, a full search vector quantizer encoder and decoder, and a microprocessor-based controller. The system is designed to operate at two possible rates: one bit/sample using a dimension 8 vector quantizer (6500 bits/s) or 2 bits/sample using a dimension 4 vector quantizer (13 000 bits/s). In both cases the codebooks have rate 8 bits/vector. Separate codebooks were designed for voiced and unvoiced speech based on a training sequence of 640 000 samples containing five different speakers. The subjective and quantitative results are compared to both simulations and with a real-time array processor based implementation.

Several properties of operational and information theoretic distortion rate functions and of mutual information rate are developed for asymptotically mean stationary (ams) processes with standard alphabets and used to prove a block source coding theorem for ergodic ams sources. In the development we prove an ergodic decomposition of the mutual information rate of ams sources, we show that the operational distortion rate function of an ams source equals that of its stationary mean, and we provide a new and direct proof of the equality of the ergodic and stationary process distortion rate functions. The latter result yields a proof of the block source coding theorem not requiring the Nedoma decomposition and complicated code construction used by Gallager and Berger.

Vector quantizers of one and two bits per sample are designed for a training sequence of 640000 speech samples and tested on a speaker not in the training sequence. Both full search vector quantizers and tree search vector quantizers are considered. The tree searched codes are suboptimal in an information theory sense, but they have a greatly reduced search effort and provide a vector successive approximation quantizer.

This paper considers the problem of classifying an input vector of measurements by a nearest neighbor rule applied to a fixed set of vectors. The fixed vectors are sometimes called characteristic feature vectors, codewords, cluster centers, models, reproductions, etc. The nearest neighbor rule considered uses a non-Euclidean information-theoretic distortion measure that is not a metric, but that nevertheless leads to a classification method that is optimal in a well-defined sense and is also computationally attractive. Furthermore, the distortion measure results in a simple method of computing cluster centroids. Our approach is based on the minimization of cross-entropy (also called discrimination information, directed divergence, K-L number), and can be viewed as a refinement of a general classification method due to Kullback. The refinement exploits special properties of cross-entropy that hold when the probability densities involved happen to be minimum cross-entropy densities. The approach is a generalization of a recently developed speech coding technique called speech coding by vector quantization.

Low-rate vector quantizers are designed and simulated for highly correlated Gauss-Markov sources and the resulting performance is compared with Arnstein's optimized predictive quantizer and with Huang and Schultheiss' optimized transform coder. Two implementations of vector quantizers are considered: full search vector quantizers-which are optimal but require large codebook searches-and tree searched vector quantizers-which are suboptimal but require far less searching. The various systems are compared on the basis of performance, complexity, and generality of design techniques.

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.

The importance of integrating voice and data over digital networks has increased during the last few years primarily because of the growing popularity of such networks. Of particular interest are efficient voice digitizing terminals, capable of operating at various data rates in both circuit-switched and packet-switched data networks. Several such terminals, including two or more speech compression algorithms, have been proposed and implemented. Typically the terminal switches between a low-rate (500 - 4000 bits/s) vocoding scheme and a medium-rate (7000 - 16000 bits/s) waveform coding algorithm, depending on, among other things, the network congestion and on the desired voice quality and robustness. We here describe the design and simulation of a multirate voice digitizer (MRVD) that switches between two speech compression systems, each based on a recently developed vector quantization (VQ) coding technique. This technique consists of the off-line interactive design of a codebook minimizing an average distortion measure, followed by the use of the codebook in an on-line nearest neighbor encoding scheme. One of the two systems is a rate-distortion speech coder that resembles a linear predictive coding (LPC) speech compression system but has a much lower rate (800 bits/s and below). We call this the LPC-VQ system, and it is similar to other previously reported systems [15],[19],[21]. The only difference is that the LPC parameters are extracted using the Burg method instead of the autocorrelation method. We here show that this provides both qualitative and quantitative improvements. The other system of our MRVD is a residual-excited linear predictive (RELP) speech compression system using VQ in both model selection and residual digitization. The residual waveform is digitized at 1 or 2 bits/sample, resulting in rates of 7300 and 13800 bits/s, respectively. We call this the RELP-VQ system. When compared to other RELP systems [6]-[8], it is shown to have a simpler architecture and to provide comparable speech quality. In a direct comparison with an APC scheme, our RELP-VQ system was determined to provide a more natural speech sound. Another interesting result presented is the quantitative comparison of the application of the VQ algorithm to the original speech waveform and its residuals.

New algorithms for the design of trellis encoding data compression systems are described. The mare algorithm uses a training sequence of actual data from a source to improve an initial trellis decoder. An additional algorithm extends the constraint length of a given decoder. Combined, these algorithms allow the automatic design of a trellis encoding system for a particular source. The algorithms' effectiveness for random sources is demonstrated through performance comparisons with other source coding systems and with theoretical bounds. The algorithms are applied to the practical problem of the design of trellis and hybrid codes for medium-to-lowrate speech compression.

Two results are presented on vector quantizers meeting necessary conditions for optimality. First a simple generalization of well-known centroid and moment properties of the squared-error distortion measure to a weighted quadratic distortion measure with an input dependent weighting is presented. The second result is an application of the squared-error special case of the first result to a simulation study of the design of1bit per sample two- and three-dimensional quantizers for a memoryless Gaussian source using the generalized Lloyd technique. The existence of multiple distinct local optima is demonstrated, thereby showing that sufficient conditions for unique local optima do not exist for this simple common case. It is also shown that at least three dimensions are required for a vector quantizer to outperform a scalar quantizer for this source.

An algorithm for the design of locally optimum vector quantizers relative to a distortion measure is used to design and simulate vector quantizers for both real sampled speech and for speech-like waveforms produced by a tenth order autoregressive random process with matching autocorrelation. Both squared-error and a weighted squared error were considered. The experimental results were compared with performance bounds from rate distortion theory based on the autoregressive model.

In a trellis encoding communication system the decoder is a time-invariant nonlinear filter with finite memory (sliding-block code), and the encoder is a trellis search algorithm matched to the decoder. A coding theorem is established for a trellis encoding of a stationary and ergodic source over a discrete memoryless noisy channel which shows that such communication systems can perform arbitrarily close to the source distortion-rate function evaluated at the channel capacity.

A necessary and sufficient condition for a source to satisfy the ergodic theorem and the Shannon-McMillan theorem--the two basic mathematical tools of the Shannon theory--is that it be asymptotically mean stationary (AMS). A channel is defined here to be AMS if whenever an AMS input source is connected to the channel, the resulting input/output process is AMS. We develop several characterizations and properties of AMS channels that resemble those of AMS sources. As an application we show that these ideas are useful in characterizing composite sources, and in particular that there exist sources that exhibit distinct short term and long term stationarity properties. Thus "locally stationary" or "quasi-stationary" processes such as those used to model speech waveforms may also be stationary. In addition, some preliminary results on coding for AMS channels are presented.

An information theory approach to the theory and practice of linear predictive coded (LPC) speech compression systems is developed. It is shown that a traditional LPC system can be viewed as a minimum distortion or nearest-neighbor system where the distortion measure is a minimum discrimination information between a speech process model and an observed frame of actual speech. This distortion measure is used in an algorithm for computer-aided design of block source codes subject to a fidelity criterion to obtain a 750-bits/s speech compression system that resembles an LPC system but has a much lower rate, a larger memory requirement, and requires no on-line LPC analysis. Quantitative and informal subjective comparisons are made among our system and LPC systems.

A low-rate (about one bit per sample) waveform coder for speech compression is designed using techniques from universal source coding, fake process tree encoding, and linear predictive coding (LPC). The system does not require on-line adaptation or LPC analysis, yet it yields a fidelity that compares well with the best existing adaptive-waveform coder of the same rate.

With rare exception, all presently available narrowband speech coding systems implement scalar quantization (independent quantization) of the transmission parameters (such as reflection coefficients or transformed reflection coefficients in LPC systems). In this paper a new approach called Vector Quantizatlon is presented. For very low data rates, realistic experiments have shown that vector quantization can achieve a given level of average distortion with fifteen to twenty fewer bits per frame than that required for optimized scalar quantizing approachs presently in use.

An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data. The basic properties of the algorithm are discussed and demonstrated by examples. Quite general distortion measures and long blocklengths are allowed, as exemplified by the design of parameter vector quantizers of ten-dimensional vectors arising in Linear Predictive Coded (LPC) speech compression with a complicated distortion measure arising in LPC analysis that does not depend only on the error vector.

Several new properties as well as simplified proofs of known properties are developed for the mutual information rate between discrete-time random processes whose alphabets are Borel subsets of complete separable metric spaces. In particular, the asymptotic properties of quantizers for such spaces provide a fink with finite-alphabet processes and yield the ergodic decomposition of mutual information rate. This result is used to prove the equality of stationary and ergodic process distortion-rate functions with the usual distortion-rate function. An unusual definition of mutual information rate for continuous-alphabet processes is used, but it is shown to be operationally appropriate and more useful mathematically; it provides an intuitive link between continuous-alphabet and finite-alphabet processes, and it allows generalizations of some fundamental results of ergodic theory that are useful for information theory.

Gersho's bounds on the asymptotic (large rate or small distortion) performance of block quantizers are valid for vector distortion measures that are powers of the Euclidean orl_{2}norm. These results are generalized to difference distortion measures that are increasing functions of the seminorm of their argument, where any seminorm is allowed. This provides ak-dimensional generalization of Gish and Pierce's results for single-symbol quantizers. When the distortion measore is a power of a seminorm the bounds are shown to be strictly better than the corresponding bounds provided by thekth-order rate-distortion functions.

A training sequence of speech data is used to design a two-step speech compression system, based upon either single speakers or multiple speakers. The system is designed to minimize an average spectral distortion over the training sequence, leading to an identification step using linear prediction techniques followed by a vector quantizer. The system is then used to compress test sequences of speech data, leading to much lower bit rates than obtained using scalar quantization for equivalent distortions. For the same numerical distortion, 20-bits/frame were required using optimal scalar bit allocation and quantization, whereas 8-bits/frame were required using vector quantization. Results are presented in the form of numerical distortion measures and analog tapes of synthesized speech.

A new class of discrete stationary noisy channels with memory and anticipation termed d-continuous channels is introduced and is shown to include all stationary discrete channels for which coding theorems exist. Roughly speaking, in a\bar{d}-continuous channel the effect of the "past" and "future" inputs on n successive outputs dies out asymptotically withnas measured in a\bar{d}or average Hamming distance sense. This is weaker than the corresponding uotious of Pfaffeihuber, Kadota, and Wyner, who require that probabilities of alln-tuples be close; that is, closeness in a variational or distribution sense. General block channel coding and block joint source and channel coding theorems are proved for stationary\bar{d}-continuous channels, and various definitions of channel capacity are compared.

The problem of designing a good decoder for a timeinvariant tree-coding data compression system is equivalent to that of finding a good low rate "fake process" for the original source, where the fake is produced by a time-invariant nonlinear filtering of an independent, identically distributed sequence of uniformly distributed discrete random variables and "goodness" is measured by the\bar{\rho}-distance between the fake and the original source. Several simple ad hoc techniques for obtaining such fake processes are introduced and shown by simulation to provide an improvement of typically 1-2 dB over optimum quantization, delta modulation, and predictive quantization for one-bit per symbol compression of Gaussian memoryless, autoregressive, and moving average sources. In addition, the fake process viewpoint provides a new intuitive explanation of why delta modulation and predictive quantization work as well as they do on Gaussian autoregressive sources.

Distortion-rate theory is used to derive absolute performance bounds and encoding guidelines for direct fixed-rate minimum mean-square error data compression of the discrete Fourier transform (DFT) of a stationary real or circularly complex sequence. Both real-part-imaginary-part and magnitude-phase-angle encoding are treated. General source coding theorems are proved in order to justify using the optimal test channel transition probability distribution for allocating the information rate among the DFT coefficients and for calculating arbitrary performance measures on actual optimal codes. This technique has yielded a theoretical measure of the relative importance of phase angle over the magnitude in magnitude-phase-angle data compression. The result is that the phase angle must be encoded with 0.954 nats, or 1.37 bits, more rate than the magnitude for rates exceeding 3.0 nats per complex element. This result and the optimal error bounds are compared to empirical results for efficient quantization schemes.

The theory of sliding-block codes (nonlinear, time-invariant, discrete-time filters) is employed to obtain general source coding theorems for ergodic sources using time-invariant trellis coding (time-invariant decoding filter and replicating trellis). The results are coupled with the theory of universal block source codes to obtain universal trellis source coding theorems for classes of sources. It is shown for a certain class of sources that the problem of designing good trellis codes is equivalent to that of simulating general random processes by filtering digital memoryless sources.

Asymptotically accurate approximations for quantizer performance were developed by Gish and Pierce. Variational techniques were used to obtain asymptotically optimal performance. In this correspondence, optimal performance is demonstrated simply without variational techniques using Holder's and Jensen's inequalities.

Sliding-block codes are nonblock coding structures consisting of discrete-time time-invariant possibly nonlinear filters. They are equivalent to time-invariant trellis codes. The coupling of Forney's rigorization of Shannon's random-coding/typical-sequence approach to block coding theorems with the strong Rohlin-Kakutani Theorem of ergodic theory is used to obtain a sliding-block coding theorem for ergodic sources and discrete memoryless noisy channels. Combining this result with a theorem on sliding-block source coding with a fidelity criterion yields a sliding-block information transmission theorem. Thus, the basic existence theorems of information theory hold for stationary nonblock structures, as well as for block codes.

A simple upper bound is derived to the difference in performance obtained from applying a given quanfizer to two different sources. This provides a bound on the performance loss or mismatch resulting when applying a quantizer designed for one source to another. The bound is in terms of a generalization of the Vasershtein distance between the source random variables and does not depend on the particular quantizer chosen. In particular, if two sources are sufficiently close in this sense, then any quantizer results in nearly identical performance on either source. Implications for optimal performance bounds are discussed and examples are given.

Both noiseless source coding and source coding with a fidelity criterion are traditionally accomplished via the mapping of consecutive nonoverlapping source blocks into code blocks of fixed or variable length. Here we use an easy application and interpretation of the Kolmogorov-Ornstein isomorphism theorem of ergodic theory to prove the existence of a new class of noiseless source coding techniques consisting of nonlinear time-invariant discrete-time filters. The output codes are physically stationary, are not of variable length, require no buffers except for the filter memory, are not catastrophically affected by occasional channel errors, and provide a new interpretation of noiseless source coding. An information-theoretic interpretation of an early special case of the isomorphism theorem provides an example. The noiseless sliding-block theorem is then coupled with the sliding-block source coding subject to a fidelity criterion theorem to obtain a general sliding-block source coding theorem for noiseless and almost noiseless Channels. The approach, assumptions, and results are compared and contrasted with the special cases of quantization, delta modulation, and block stationary convolutional, trellis, tree, Viterbi, and sequential source coding techniques.

The standard definition of the distortion-rate function involves a limit of information-tbeoretic minimizations over distributions of random vectors. Several alternative definitions, each involving a single minimization over random processes, are presented here and verified. These definitions parallel Khinchine's process definition of channel capacity, provide a new interpretation of block and nonblock source coding (with a fidelity criterion) theorems in terms of optimal stochastic codes, and provide a comparison between the optimal performance theoretically attainable (OPTA) using block and nonblock source codes. Coupling the process definitions with recently developed bounding techniques provides a new and simple proof of the block source coding theorem for ergodic sources.

A unified theory is developed for fixed rate block source encoding subject to a fidelity criterion in incompletely or inaccurately specified stationary statistical environments. Several definitions of universal encoding are given and compared, and the appropriate theorems are stated and proved for each. The new results and approaches are compared and contrasted with earlier related results of Ziv.

Source coding theorems are proved for discrete-time stationary processes subject to a fidelity criterion. The alphabet of the process is assumed to be a separable metric space, but the process is not assumed to be ergodic. When the process is not ergodic, the minimum average distortion for a fixed-rate code is not given by the distortion-rate function of the source as usually defined. It is given instead by a weighted average of the distortion-rate functions of ergodic subsources comprising the ergodic decomposition of the source. Potential applications to universal source coding with a fidelity criterion are discussed.

The ergodic decomposition is discussed, and a version focusing on the structure of individual sample functions of stationary processes is proved for the special case of discrete-time random processes with discrete alphabets. The result is stronger in this case than the usual theorem, and the proof is both intuitive and simple. Estimation-theoretic and information-theoretic interpretations are developed and applied to prove existence theorems for universal source codes, both noiseless and with a fidelity criterion.

The definition of the rate-distortion function is extended to the case of a stationary-ergodic source with side information, and the appropriate coding theorem is proved. Inequalities between the joint, marginal, and conditional rate-distortion functions for ergodic processes are given, and their implications in terms of universal coding are discussed.

Recent extensions of information and communication theoretic concepts to simple systems involving a single transmitter and several receivers are described and compared in an intuitive and tutorial manner.

A new class of lower bounds to rate-distortion functions of stationary processes with memory and single-letter vector-valued distortion measures is derived. This class is shown to include or imply all other well-known lower bounds to rates of such sources and distortion measures. The derivation is based on the definition and properties of the conditional rate-distortion function. In addition to providing a unified and intuitive approach to lower bounds, this approach yields several interesting relations among conditional, joint, and marginal rates that are similar to and sometimes identical with the analogous relations among the corresponding entropies.

A class of lower bounds to rate-distortion functions of stationary sources with context-dependent fidelity criteria is derived by mapping the source and distortion measure into an equivalent restricted-transition stationary source with a single-letter fidelity criterion, and then applying the composite bound. This approach is seen to yield bounds which, although sometimes quite loose, apply to general stationary sources and context-dependent fidelity criteria. Two examples are presented.

Since covariance matrices of weakly stationary random processes are Toeplitz, much of the theory involving asymptotic results for such processes is simply the theory of the asymptotic behavior of Toeplitz forms. The fundamental theorem of this type is the Szegö theorem on the asymptotic eigenvalue distribution of Toeplitz matrices. This theorem is often quoted but relatively little understood in the engineering literature. In this tutorial paper we prove the Szegiö theorem for the special case of finite-order Toeplitz matrices. In this setting the mathematical sophistication of the classical proofs is not required and the proof is both simple and intuitive--yet it contains the important concepts involved in the most general case.

A lower bound to the rate-distortion functionR(D)of finite-alphabet sources with memory is derived for the class of balanced distortion measures. For finite-state finite-alphabet Markov sources, sufficient conditions are given for the existence of a strictly positive average distortionD_csuch thatR(D)equals its lower bound for0 \leqq D \leqq D_c. The bound is evaluated for the Hamming and Lee distortion measures and is identical to the corresponding bound for memoryless sources having the same entropy and alphabet. These results are applied to yield a simple proof of the converse of the noisy-channel coding theorem for sources satisfying the sufficient conditions for equality with the lower bound and channels with memory.D_cis evaluated explicitly for the special case of the binary asymmetric Markov source.

The generalized Shannon lower bound to the rate-distortion functionR(D)for stationary sources with memory is extended to a wide class of distortion measures involving no symmetry conditions. The lower boundR_{L} (D)is a reasonably simple function of the entropy and marginal probabilities of the source and the per-letter distortion measure. Sufficient conditions only slightly less general than necessary conditions are given for the existence of a strictly positive cutoff distortionD_csuch thatR(D) = R_{L} (D)forD \leq D_c. The sufficient conditions are the most general to date and include all previously known examples. This provides a nearly complete resolution of the question of when the Shannon-type lower bound to the rate-distortion function of a source with memory is tight. The results are applied to generalize earlier results for balanced distortion measures and Markov sources to nonbalanced distortion measures and wide-sense Markov sources. As a special case, it is shown thatD_c > 0for all finite-alphabet autoregressive sources. As an example,R_{L} (D)is evaluated for the first-order ternary autoregressive source for a balanced (Hamming) and a nonbalanced (modular distance) distortion measure. A simple lower bound toD_cis derived for this example.

The rate distortion functionR(D)is calculated for two time-discrete autoregressive sources--the time-discrete Gaussian autoregressive source with a mean-square-error fidelity criterion and the binary-symmetric first-order Markov source with an average probability-of-error per bit fidelity criterion. In both cases it is shown thatR(D)is bounded below by the rate distortion function of the independent-letter identically distributed sequence that generates the autoregressive source. This lower bound is shown to hold with equality for a nonzero region of small average distortion. The positive coding theorem is proved for the possibly nonstationary Gaussian autoregressive source with a constraint on the parameters. Finally, it is shown that the rate distortion function of any time-discrete autoregressive source with a difference distortion measure can be bounded below by the rate distortion function of the independent-letter identically distributed generating sequence with the same distortion measure.