We present a systematic approach for training and testing structural texture similarity metrics (STSIMs) so that they can be used to exploit texture redundancy for structurally lossless image compression. The training and testing is based on a set of image distortions that reflect the characteristics of the perturbations present in natural texture images. We conduct empirical studies to determine the perceived similarity scale across all pairs of original and distorted textures. We then introduce a data-driven approach for training the Mahalanobis formulation of STSIM based on the resulting annotated texture pairs. Experimental results demonstrate that training results in significant improvements in metric performance. We also show that the performance of the trained STSIM metrics is competitive with state of the art metrics based on convolutional neural networks, at substantially lower computational cost.

We consider lossy compression of a broad class of bilevel images that satisfy the smoothness criterion, namely, images in which the black and white regions are separated by smooth or piecewise smooth boundaries, and especially lossy compression of complex bilevel images in this class. We propose a new hierarchical compression approach that extends the previously proposed fixed-grid lossy cutset coding (LCC) technique by adapting the grid size to local image detail. LCC was claimed to have the best rate-distortion performance of any lossy compression technique in the given image class, but cannot take advantage of detail variations across an image. The key advantages of the hierarchical LCC (HLCC) is that, by adapting to local detail, it provides constant quality controlled by a single parameter (distortion threshold), independent of image content, and better overall visual quality and rate-distortion performance, over a wider range of bitrates. We also introduce several other enhancements of LCC that improve reconstruction accuracy and perceptual quality. These include the use of multiple connection bits that provide structural information by specifying which black (or white) runs on the boundary of a block must be connected, a boundary presmoothing step, stricter connectivity constraints, and more elaborate probability estimation for arithmetic coding. We also propose a progressive variation that refines the image reconstruction as more bits are transmitted, with very small additional overhead. Experimental results with a wide variety of, and especially complex, bilevel images in the given class confirm that the proposed techniques provide substantially better visual quality and rate-distortion performance than existing lossy bilevel compression techniques, at bitrates lower than lossless compression with the JBIG or JBIG2 standards.

This paper provides results concerning the monotonicity of entropy within a family of Ising models defined by a positively correlated statistic on a tree. It uses a message passing approach to show that the marginal entropy at any set of sites is monotone decreasing in each of the exponential parameters indexing the model.

For generalized gamma probability densities, this paper studies the monotonicity of step sizes of optimal symmetric uniform scalar quantizers with respect to mean squared-error distortion. The principal results are that for the special cases of Gaussian, Laplacian, two-sided Rayleigh, and gamma densities, optimal step size monotonically decreases when the number of levels N increases by two, and that for any generalized gamma density and all sufficiently large N, optimal step size again decreases when N increases by two. Also, it is shown that for a Laplacian density and sufficiently large N, optimal step size decreases when N increases by just one.

This paper investigates the convexity of the mean squared-error distortion of symmetric uniform scalar quantization with respect to step size. The principal results include proofs for odd numbers of levels that distortion is not convex for any symmetric density and that it is convex for even numbers of levels for densities, such as Gaussian, Laplacian, and gamma, but is not, in general for two-sided Rayleigh. For the latter case, an interval is derived that includes the optimal step size and over which the distortion is convex. The proofs of convexity use the Euler-Maclaurin formula applied to the second derivative of distortion, with upper bounds on the remainder term. These results imply that a zero of the derivative of the distortion for these densities, which has been previously conjectured optimal, is indeed the optimal step size, because the distortion is convex either globally or locally over a sufficiently wide interval to ensure a global minimizer.

Motivated by the question of whether the recently introduced Reduced Cutset Coding (RCC) [1], [2] offers rate-complexity performance benefits over conventional context-based conditional lossless coding for sources with two-dimensional Markov structure, this paper compares several row-centric coding strategies that vary in the amount of conditioning as well as whether a model or an empirical table is used in the encoding of blocks of rows. The conclusion is that, at least for sources exhibiting low-order correlations, 1-sided model-based conditional coding is superior to the method of RCC for a given constraint on complexity, and conventional context-based conditional coding is nearly as good as the 1-sided model-based coding.

This paper analyzes the rate, redundancy and complexity of a generalized version of Reduced Cutset Coding (RCC) [4] in which cutset lines can consist of more than one image row. We show that increasing the thickness of the lines reduces coding rate for the cutset, increasing the spacing of the lines increases the coding rate of the non-cutset pixels, though the coding rate of the latter is always strictly less than that of the former. We show that the redundancy of RCC can be decomposed into two terms, a correlation redundancy due to coding the components of the cutset independently, and a distribution redundancy due to coding the cutset as a reduced Ising model [3]. We show that the correlation redundancy decreases with increasing spacing of the lines, and that the parameter of the reduced Ising model approaches the true parameter monotonically in the thickness of the lines. We present a learning phase in which the true parameter of the model is learned as well as the parameter of the reduced model. Numerical simulations show that only small improvements in rate-complexity performance are possible by increasing line widths, though rates within 3 to 4 percent of the entropy rate can be achieved with only 20 to 50 operations per pixel through combinations of line thickness and spacing.

This paper presents a study of bilevel image similarity, including new objective metrics intended to quantify similarity consistent with human perception, and a subjective experiment to obtain ground truth for judging the performance of the objective similarity metrics. The focus is on scenic bilevel images, which are complex, natural or hand-drawn images, such as landscapes or portraits. The ground truth was obtained from ratings by 77 subjects of 44 distorted versions of seven scenic images, using a modified version of the SDSCE testing methodology. Based on hypotheses about human perception of bilevel images, several new metrics are proposed that outperform existing ones in the sense of attaining significantly higher Pearson and Spearman-rank correlation coefficients with respect to the ground truth from the subjective experiment. The new metrics include adjusted percentage error, bilevel local direction, and connected components comparison. Combinations of these metrics are also proposed, which exploit their complementarity to attain even better performance. These metrics and the ground truth are then used to assess the relative severity of various kinds of distortion and the performance of several lossy bilevel compression methods.

This paper introduces Manhattan sampling in two and higher dimensions, and proves sampling theorems for them. In 2-D, Manhattan sampling, which takes samples densely along a Manhattan grid of lines, can be viewed as sampling on the union of two rectangular lattices, one dense horizontally and the other vertically, with the coarse spacing of each being a multiple of the fine spacing of the other. The sampling theorem shows that the images bandlimited to the union of the Nyquist regions of the two rectangular lattices can be recovered from their Manhattan samples, and an efficient procedure for doing so is given. Such recovery is possible even though there is an overlap among the spectral replicas induced by Manhattan sampling. In three and higher dimensions, there are many possible configurations for Manhattan sampling, each consisting of the union of special rectangular lattices called bi-step lattices. This paper identifies them, proves a sampling theorem showing that the images bandlimited to the union of the Nyquist regions of the bi-step rectangular lattices are recoverable from Manhattan samples, presents an efficient onion-peeling procedure for doing so, and shows that the union of Nyquist regions is as large as any bandlimited region, such that all images supported by such can be stably reconstructed from samples taken at the rate of the Manhattan sampling. It also develops a special representation for the bi-step lattices with a number of useful properties. While most of this paper deals with continuous-space images, Manhattan sampling of discrete-space images is also considered, for infinite, as well as finite, support images.

This paper presents a theoretical analysis of a newly proposed texture similarity feature, Local Radius Index (LRI). LRI is designed to enable texture similarity metrics consistent with human perception to be based on it, and has been successfully applied in several applications, including perceptual image compression, identical texture retrieval and texture classification. In this paper, a theoretical analysis of its different versions, LRI-A and LRI-D, is presented for textures modeled as periodic tessellations. General formulas are derived to predict LRI-A and LRI-D feature vectors, which are histograms. The analysis reveals the fundamental relationship between LRI-A and LRI-D. Numerical results demonstrate the accuracy of the analysis.

The ability to recognize different types of photographic paper can be useful when attributing photographs to specific photographers or eras. This paper uses the recently developed texture feature, Local Radius Index (LRI), and the similarity metrics based on it, to classify photographic papers, from raking light photos of such. The results show that LRI leads to better classification of photographic papers than previous methods. They also suggest the ability to distinguish photographic papers by brand/style and reflectance.

Matched-Texture Coding is a novel image coder that utilizes the self-similarity of natural images that include textures, in order to achieve structurally lossless compression. The key to a high compression ratio is replacing large image blocks with previously encoded blocks with similar structure. Adjusting the lighting of the replaced block is critical for eliminating illumination artifacts and increasing the number of matches. We propose a new adaptive lighting correction method that is based on the Poisson equation with incomplete boundary conditions. In order to fully exploit the benefits of the adaptive Poisson lighting correction, we also propose modifications of the side-matching (SM) algorithm and structural texture similarity metric. We show that the resulting matched-texture algorithm achieves better coding performance.

This work explores performance vs. communication energy tradeoffs in wireless sensor networks that use the recently proposed cutset deployment strategy in which sensors are placed densely along a grid of intersecting lines. For a given number of sensors, intersensor spacing is less for a cutset network than for a conventional lattice deployment, so that cutset networks require less communication energy, albeit with some potential loss in network performance. Previous work analyzed the energy-performance tradeoffs for square-grid cutset networks in the context of specific decentralized algorithms for source localization based on received signal strength (RSS). The current work also considers the RSS based source localization problem. However, it takes a more fundamental approach to analyzing the tradeoff by considering a centralized task, minimum energy communication paths, Maximum Likelihood estimation algorithms and Cramér-Rao bounds. Moreover, it analyzes triangular and honeycomb cutset deployments, in addition to square-grid ones. The results indicate that cutset networks offer sizable decreases in energy with only modest losses of performance.

This paper proposes new objective similarity metrics for scenic bilevel images, which are images containing natural scenes such as landscapes and portraits. Though percentage error is the most commonly used similarity metric for bilevel images, it is not always consistent with human perception. Based on hypotheses about human perception of bilevel images, this paper proposes new metrics that outperform percentage error in the sense of attaining significantly higher Pearson and Spearman-rank correlation coefficients with respect to subjective ratings. The new metrics include Adjusted Percentage Error, Bilevel Gradient Histogram and Connected Components Comparison. The subjective ratings come from similarity evaluations described in a companion paper. Combinations of these metrics are also proposed, which exploit their complementarity to attain even better performance.

In order to provide ground truth for subjectively comparing compression methods for scenic bilevel images, as well as for judging objective similarity metrics, this paper describes the subjective similarity rating of a collection of distorted scenic bilevel images. Unlike text, line drawings, and silhouettes, scenic bilevel images contain natural scenes, e.g., landscapes and portraits. Seven scenic images were each distorted in forty-four ways, including random bit flipping, dilation, erosion and lossy compression. To produce subjective similarity ratings, the distorted images were each viewed by 77 subjects. These are then used to compare the performance of four compression algorithms and to assess how well percentage error and SmSIM work as bilevel image similarity metrics. These subjective ratings can also provide ground truth for future tests of objective bilevel image similarity metrics.

Cutset sampling is a new approach to image sampling where 2D data is recorded densely along intersecting lines. A special case of cutset sampling is Manhattan sampling, where data is sampled densely along evenly-spaced rows and columns. This paper presents a new method for interpolating pixels from their Manhattan samples called the orthogonal gradient (OG) algorithm, which exploits the fact that pixels tend to be correlated along the direction orthogonal to the image gradient. Such an approach is enhanced by Manhattan sampling, where dense sampling along straight lines allows for better reconstruction of both sharp and soft image edges. In particular, the OG algorithm alternates between solving a constrained optimization problem, and changing the weights of the optimization problem according to the direction of the gradient of each new image estimate. The proposed method improves upon previous Manhattan interpolation algorithms, both qualitatively as well as in mean-squared error. Furthermore, unlike the previous algorithms, the OG algorithm can easily be extended to any sampling scheme.

This paper proposes a new rotation-invariant texture similarity feature, called Rotation-Invariant Local Radius Index (RI-LRI). Whereas the original LRI was designed for applications that are sensitive to rotation and aimed to penalize rotation monotonically, the new rotation-invariant LRI is well suited to texture classification. When combined with frequency domain contrast information and the well known Local Binary Patterns (LBP) feature, the proposed metric has comparable texture classification accuracy to state-of-the-art metrics, when tested on the Outex and CUReT databases. Moreover, it has an approximately ten times lower dimensional feature vector and requires substantially less computation than other state-of-the-art texture features, such as those based on LBP.

An effective, low complexity method for lossy compression of scenic bilevel images, called lossy cutset coding, is proposed based on a Markov random field model. It operates by losslessly encoding pixels in a square grid of lines, which is a cutset with respect to a Markov random field model, and preserves key structural information, such as borders between black and white regions. Relying on the Markov random field model, the decoder takes a MAP approach to reconstructing the interior of each grid block from the pixels on its boundary, thereby creating a piecewise smooth image that is consistent with the encoded grid pixels. The MAP rule, which reduces to finding the block interiors with fewest black-white transitions, is directly implementable for the most commonly occurring block boundaries, thereby avoiding the need for brute force or iterative solutions. Experimental results demonstrate that the new method is computationally simple, outperforms the current lossy compression technique most suited to scenic bilevel images, and provides substantially lower rates than lossless techniques, e.g., JBIG, with little loss in perceived image quality.

For wireless sensor networks, many decentralized algorithms have been developed to address the problem of locating a source that emits acoustic or electromagnetic waves based on received signal strength. Among the motivations for decentralized algorithms is that they reduce the number of transmissions between sensors, thereby increasing sensor battery life. Whereas most such algorithms are designed for arbitrary sensor placements, such as random placements, this paper focuses on applications that permit a choice of sensor placement. In particular, to make communications costs small, it is proposed to place sensors uniformly along evenly spaced rows and columns, i.e., a Manhattan grid. For such a placement, the Midpoint Algorithm is proposed, which is a simple noniterative decentralized algorithm. The results of this paper show that Manhattan grid networks offer improved accuracy vs. energy tradeoff over randomly distributed networks. Results also show the proposed Midpoint Algorithm offers further energy savings over the recent POCS algorithm.

We develop a new type of statistical texture image feature, called a Local Radius Index (LRI), which can be used to quantify texture similarity based on human perception. Image similarity metrics based on LRI can be applied to image compression, identical texture retrieval and other related applications. LRI extracts texture features by using simple pixel value comparisons in space domain. Better performance can be achieved when LRI is combined with complementary texture features, e.g., Local Binary Patterns (LBP) and the proposed Subband Contrast Distribution. Compared with Structural Texture Similarity Metrics (STSIM), the LRI-based metrics achieve better retrieval performance with much less computation. Applied to the recently developed structurally lossless image coder, Matched Texture Coding, LRI enables similar performance while significantly accelerating the encoding.

Texture is an important visual attribute both for human perception and image analysis systems. We review recently proposed texture similarity metrics and applications that critically depend on such metrics, with emphasis on image and video compression and content-based retrieval. Our focus is on natural textures and structural texture similarity metrics (STSIMs). We examine the relation of STSIMs to existing models of texture perception, texture analysis/synthesis, and texture segmentation. We emphasize the importance of signal characteristics and models of human perception, both for algorithm development and testing/validation.

We develop new metrics for texture similarity that accounts for human visual perception and the stochastic nature of textures. The metrics rely entirely on local image statistics and allow substantial point-by-point deviations between textures that according to human judgment are essentially identical. The proposed metrics extend the ideas of structural similarity and are guided by research in texture analysis-synthesis. They are implemented using a steerable filter decomposition and incorporate a concise set of subband statistics, computed globally or in sliding windows. We conduct systematic tests to investigate metric performance in the context of "known-item search," the retrieval of textures that are "identical" to the query texture. This eliminates the need for cumbersome subjective tests, thus enabling comparisons with human performance on a large database. Our experimental results indicate that the proposed metrics outperform peak signal-to-noise ratio (PSNR), structural similarity metric (SSIM) and its variations, as well as state-of-the-art texture classification metrics, using standard statistical measures.

This paper establishes rates attainable by several lossy schemes for coding a continuous parameter source to a specified mean-squared-error distortion based on sampling at asymptotically large rates. First, a densely sampled, spatiotemporal, stationary Gaussian source is distributively encoded. The Berger–Tung bound to the distributed rate-distortion function and three convergence theorems are used to obtain an upper bound, expressed in terms of the source spectral density, to the smallest attainable rate at asymptotically large sampling rates. The bound is tighter than that recently obtained by KashyapBoth indicate that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marcofor encoders based on scalar quantization and Slepian–Wolf distributed lossless coding. The second scheme is transform coding with scalar coefficient quantization. A new generalized transform coding analysis, as well as the aforementioned convergence theorems, is used to find the smallest attainable rate at asymptotically large sampling rates in terms of the source spectral density and the operational rate-distortion function of the family of quantizers, which in contrast to previous analyses need not be convex. The result shows that when a transform is used, scalar quantization need not cause the poor performance found by MarcoAs a corollary, the final result pursues an approach, originally proposed by Berger, to show that the inverse water-pouring formula for the rate-distortion function can be attained at high sampling rates by transform coding with ideal vector quantization to encode the coefficients. Also established in the paper are relations between operational rate-distortion and distortion-rate functions for a continuous parameter source and those for the discrete parameter source that results from sampling.

This paper presents a sampling theorem for Manhattan-grid sampling, which is a sampling scheme in which data is taken along evenly spaced rows and columns. Given the spacing between the rows, the columns, and the samples along the rows and columns, the theorem shows that an image can be perfectly reconstructed from Manhattan-grid sampling if its spectrum is bandlimited to a cross-shaped region whose arm lengths and widths are determined by the aforementioned sample spacings. The nature of such cross-bandlimited images is demonstrated by filtering an image with a cross-bandlimiting filter for several choices of sampling parameters.

We focus on the evaluation of texture similarity metrics for structurally lossless or nearly structurally lossless image compression. By structurally lossless we mean that the original and compressed images, while they may have visible differences in a side-by-side comparison, they have similar quality so that one cannot tell which is the original. This is particularly important for textured regions, which can have significant point-by-point differences, even though to the human eye they appear to be the same. As in traditional metrics, texture similarity metrics are expected to provide a monotonic relationship between measured and perceived distortion. To evaluate metric performance according to this criterion, we introduce a systematic approach for generating synthetic texture distortions that model variations that occur in natural textures. Based on such distortions, we conducted subjective experiments with a variety of original texture images and different types and degrees of distortions. Our results indicate that recently proposed structural texture similarity metrics provide the best performance.

We propose a new texture-based compression approach that relies on new texture similarity metrics and is able to exploit texture redundancies for significant compression gains without loss of visual quality, even though there may visible differences with the original image (structurally lossless). Existing techniques rely on point-by-point metrics that cannot account for the stochastic and repetitive nature of textures. The main idea is to encode selected blocks of textures - as well as smooth blocks and blocks containing boundaries between smooth and/or textured regions - by pointing to previously occurring (already encoded) blocks of similar textures, blocks that are not encoded in this way, are encoded by a baseline method, such as JPEG. Experimental results with natural images demonstrate the advantages of the proposed approach.

This paper builds upon previous work for image reconstruction problems in which samples are taken on evenly spaced rows and columns, i.e., a Manhattan grid. A new reconstruction method is proposed that uses three steps to interpolate the interior of each block under the model that an image can be decomposed into piecewise planar regions plus noise. First, the K-planes algorithm is developed in order to fit several planes to the observed pixel values on the border. Second, one of theK planes is assigned to each pixel of the block interior, by a process of partitioning the block with polygons, thereby creating a piecewise planar approximation. Third, the interior pixels are interpolated by modeling them as a Gauss Markov random field whose mean is the piecewise planar approximation just obtained. The new method is shown to improve significantly upon previous methods, especially in the preservation of “soft” image edges.

We propose a hierarchical lossy bilevel image compression method that relies on adaptive cutset sampling (along lines of a rectangular grid with variable block size) and Markov Random Field based reconstruction. It is an efficient encoding scheme that preserves image structure by using a coarser grid in smooth areas of the image and a finer grid in areas with more detail. Experimental results demonstrate that the proposed method performs as well as or better than the fixed-grid approach, and outperforms other lossy bilevel compression methods in its rate-distortion performance.

It is well known that for discrete-time, stationary sources, most lossy source coding techniques have operational rate-distortion functions that approach the Shannon ratedistortion function with respect to squared error to within an additive constant as distortion approaches zero. With the goal of investigating similar phenomena for continuous-time sources, this paper investigates the low-distortion performance of distributed coding of continuous-time, stationary, Gaussian sources based on high-rate sampling. It is found that for bandlimited sources and nonbandlimited sources whose spectra have sufficiently light, e.g., exponentially decreasing, tails, distributed source coding is asymptotically as good as centralized coding in the small distortion regime. On the other hand, for spectra with tails that decay as a power (greater than one) of frequency, it is found that for small distortions the distributed rate-distortion function is a constant times larger than the Shannon rate-distortion, where the constant decreases as the power increases. For example, it is approximately 1.2 when the power is 2. The conclusion is that for a stationary Gaussian source and asymptotically small distortion, the ratio of the distributed to centralized rate-distortion function is a function of the weight of the tail of the source spectrum. In the process of finding the ratio, the low distortion form of the centralized rate-distortion function is found for sources whose spectra have exponential and power law tails.

Asymptotic formulas are derived for the mean-squared error (MSE) distortion ofN-level uniform scalar quantizers designed to be MSE optimal for one density function, but applied to another, asN→ ∞. These formulas, which are based on the Euler-Maclaurin formula, are then applied with generalized gamma, Bucklew-Gallagher, and Hui-Neuhoff density functions as the designed-for and applied-to densities. It is found that the mismatch between the designed-for and applied-to densities can disturb the delicate balance between granular and overload distortions in optimal quantization, with the result that, generally speaking, the granular or overload distortion dominates, respectively, depending on whether the applied-to density function has a lighter or heavier tail than the designed-for density. Specifically, in the case of generalized gamma densities, a variance mismatch makes overload distortion dominate for an applied-to source with a slightly larger variance, whereas a shape mismatch can tolerate a wider variance difference while retaining the dominance of the granular distortion. In addition, for the studied density functions, the Euler-Maclaurin approach is used to derive asymptotic formulas for the optimal quantizer step size in a simpler, more direct, way than previous approaches.

This paper presents a new approach to sampling images in which samples are taken on a cutset with respect to a graphical image model. The cutsets considered are Manhattan grids, for example every Nth row and column of the image. Cutset sampling is motivated mainly by applications with physical constraints, e.g. a ship taking water samples along its path, but also by the fact that dense sampling along lines might permit better reconstruction of edges than conventional sampling at the same density. The main challenge in cutset sampling lies in the reconstruction of the unsampled blocks. As a first investigation, this paper uses segmentation followed by linear estimation. First, the ACA method [1] is modified to segment the cutset, followed by a binary Markov random field (MRF) inspired segmentation of the unsampled blocks. Finally, block interiors are estimated from the pixels on their boundaries, as well as their segmentation, with methods that include a generalization of bilinear interpolation and linear MMSE methods based on Gaussian MRF models or separable autocorrelation models. The resulting reconstructions are comparable to those obtained with conventional sampling at higher sampling densities, but not generally as good as conventional sampling at lower rates.

With mean-squared error D as a goal, it is well known that one may approach the rate-distortion function R(D) of a nonbandlimited, continuous-time Gaussian source by sampling at a sufficiently high rate, applying the Karhunen-Loeve transform to sufficiently long blocks, and then independently coding the transform coefficients of each type. Motivated by the question of the efficiency of dense sensor networks for sampling, encoding and reconstructing spatial random fields, this paper studies the following three cases. In the first, we consider a centralized encoding setup with a sample-transform-quantize scheme where the quantization is assumed to be optimal. In the second, we consider a distributed setup, where a spatio-temporal source is sampled and distributively encoded to be reconstructed at a receiver. We show that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marco et al. for encoders based on time- and space-invariant scalar quantization and ideal Slepian-Wolf distributed lossless coding. In the third, we consider a centralized setup, with a sample-and-transform coding scheme in which ideal coding of coefficients is replaced by coding with some specified family of quantizers. It is shown that when the sampling rate is large, the operational rate-distortion function of such a scheme comes within a finite constant of that of the first case.

This paper presents Reduced Cutset Coding, a new Arithmetic Coding (AC) based approach to lossless compression of Markov random fields. In recent work, the authors presented an efficient AC based approach to encoding acyclic MRFs and described a Local Conditioning (LC) based approach to encoding cyclic MRFs. In the present work, we introduce an algorithm for AC encoding of a cyclic MRF for which the complexity of the LC method of, or the acyclic MRF algorithm of combined with the Junction Tree (JT) algorithm, is too large. For encoding an MRF based on a cyclic graph G = (V,E), a cutset U ¿ V is selected such that the subgraph GUinduced by U, and each of the components of G\U, are tractable to either LC or JT. Then, the cutset variables XUare AC encoded with coding distributions based on a reduced MRF defined on GU, and the remaining components XV\Uof XVare optimally AC encoded conditioned on XU. The increase in rate over optimal encoding of XVis the normalized divergence between the marginal distribution of XUand the reduced MRF on GUused for the AC encoding. We show this follows a Pythagorean decomposition and, additionally, that the optimal exponential parameter for the reduced MRF on GUis the one that preserves the moments from the marginal distribution. We also show that the rate of encoding XUwith this moment-matching exponential parameter is equal to the entropy of the reduced MRF with this moment-matching parameter. We illustrate the concepts of our approach by encoding a typical image from an Ising model with a cutset consisting of evenly spaced rows. The performance on this image is similar to that of JBIG.

This paper considers the entropy of highly correlated quantized samples. Two results are shown. The first concerns sampling and identically scalar quantizing a stationary continuous-time random process over a finite interval. It is shown that if the process crosses a quantization threshold with positive probability, then the joint entropy of the quantized samples tends to infinity as the sampling rate goes to infinity. The second result provides an upper bound to the rate at which the joint entropy tends to infinity, in the case of an infinite-level uniform threshold scalar quantizer and a stationary Gaussian random process. Specifically, an asymptotic formula for the conditional entropy of one quantized sample conditioned on the previous quantized sample is derived. At high sampling rates, these results indicate a sharp contrast between the large encoding rate (in bits/sec) required by a lossy source code consisting of a fixed scalar quantizer and an ideal, sampling-rate-adapted lossless code, and the bounded encoding rate required by an ideal lossy source code operating at the same distortion.

The development of objective texture similarity metrics for image analysis applications differs from that of traditional image quality metrics because substantial point-by-point deviations are possible for textures that according to human judgment are essentially identical. Thus, structural similarity metrics (SSIM) attempt to incorporate ¿structural¿ information in image comparisons. The recently proposed structural texture similarity metric (STSIM) relies entirely on local image statistics. We extend this idea further by including a broader set of local image statistics, basing the selection on metric performance as compared to subjective evaluations. We utilize both intra- and inter-subband correlations, and also incorporate information about the color composition of the textures into the similarity metrics. The performance of the proposed metrics is compared to PSNR, SSIM, and STSIM on the basis of subjective evaluations using a carefully selected set of 50 texture pairs.

Given a Markov random field (MRF) X defined by potentials on a graph G = (V,E), and given a subset U ¿ V of the sites on which X is defined, we prove, under a positive correlation constraint on the MRF, that the entropy of the subfield XUis upper bounded by the entropy of an MRF defined on the subgraph induced by U with potentials taken directly from those assigned to U in G. To prove this we use exponential family representations of MRFs. We first show that the entropy of an MRF is monotone decreasing in the exponential parameters. We then use the Maximum Entropy principle and a well-known result from information geometry to show that the marginal entropy of XUis upper bounded by the MRF on the induced subgraph with moments matching the marginal distribution. We then use the convexity of the log-partition function to show that to match the marginal moments on the induced subgraph, the exponential coordinates on the induced subgraph are component-wise greater than the corresponding parameter of the original exponential characterization. Our result follows from monotonicity.

This paper introduces methods for losslessly encoding a Markov random field (MRF) with arithmetic coding. The issues are how to choose the pixel scan order and how to produce coding distributions to accompany the pixels. For an MRF based on an acyclic graph, we choose a scan consistent with the graph and use belief propagation (BP) to efficiently compute the optimal coding distributions. For an MRF based on a cyclic graph, we use local conditioning (LC) to losslessly encode an appropriately chosen scan of a loop cutset, whose removal leaves an acyclic graph whose pixels can be encoded by the previous method. The results include BP-like formulas for LC in an undirected graph and a formula for the complexity of LC in a cyclic graph. As a first application of the methods, preliminary results of applying the method to an Ising model are given.

We investigate perceptual similarity metrics for the content-based retrieval of natural textures. The goal is to find perceptually similar textures that may have significant differences on a point-by-point basis. The evaluation of such metrics typically requires extensive and cumbersome subjective tests. The focus of this paper is on the recovery of textures that are "identical" to the query texture, in the sense that they are pieces of the same texture. This is important in content-based image retrieval (CBIR), where one may want to find images that contain a particular texture, as well as in some near-threshold coding applications. The advantage of evaluating metric performance in the context of retrieving identical textures is that the ground truth is known, and therefore no subjective tests are required. We can thus compare the performance of different metrics on large sets of textures, and derive meaningful statistical results.We evaluate the performance of a recently proposed structural texture similarity metric on grayscale textures, and compare it to that of PSNR, as well as space domain and complex wavelet structural similarity metrics. Experimental results with a database of 748 distinct texture images, indicate that the new metric outperforms the other metrics in the retrieval of identical textures, according to a number of standard statistical measures.

This paper extends the theory of data synchronization with timing for fixed-rate codes, previously developed by the authors, to the variable-rate case. Given a source code, a class of sync-timing codes called variable-rate cascaded (VRC) codes is considered that ldquowrap aroundrdquo the source code in such a way as to enable the decoder to not only resynchronize rapidly when the encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indices of the data symbols encoded by the source code. The estimates of the time indices are modulo-Treductions of the actual time indices, for some integerTcalled the timing span of the code. These sync-timing codes are analyzed on the basis of the maximum timing span achievable for a given coding rateRand permissible resynchronization delayD. It is shown that the timing span of VRC codes is upper-bounded by 2D(1-R)+o(D), and that this upper bound is achievable asymptotically in D. This exponential rate of growth of timing span with delay is the same as that found previously for certain fixed-rate sync-timing codes, e.g., (fixed-rate) cascaded codes.

Traditional image similarity metrics compare two images on a point-by-point basis. On the other hand, structural similarity metrics (SSIM) attempt to base image similarity on "structural" information. We evaluate the performance of SSIM metrics in the context of texture similarity, and propose new metrics that incorporate the best features of SSIM and eliminate the most serious drawbacks. We show that the proposed new texture similarity metrics outperform SSIM and its variations, as well as PSNR and other traditional metrics. We demonstrate the advantages of the new metrics on a carefully selected set of 39 texture pairs and comparisons with informal subjective test results.

In 1965, Nitadori (1965) derived an infinite sequence such that for any N, the ith term of the sequence is the size of the ith half cell (counting from the right) of the N-level minimum mean-squared error quantizer for a unit variance exponential source. This was done by exploiting a key property that the source's probability density function and its tail function are equal, a fact resulting from its memoryless property. In this paper, an asymptotic version of this key fact is found to hold for a general exponential (GE) source parameterized by an exponential power p, and it is used to show that for such a source, the size of the ith half cell of an optimal N-level quantizer multiplied by the (p-l)st power of the ith threshold approaches the ith term of the Nitadori sequence as N grows to infinity. Thus, the Nitadori sequence asymptotically characterizes the cells of MMSE quantizers for GE sources, as well as exponential.

Typical vector quantizer (VQ) design algorithms, such as generalized Lloyd methods, are susceptible to local minima. In addition, for entropy-constrained VQ, it is not obvious what the "right" number of codevectors is for any given source and target rate. One method that has shown promising results for solving both problems is deterministic annealing, where randomness is added to the encoding process, the uncertainty of which is gradually reduced until a deterministic coder is found. This method has been used for fixed-rate and entropy-constrained unstructured VQ, as well as for a variety of structurally constrained VQs. For the unstructured entropy-constrained case, we generalize the existing methods to include new cost functions, and we argue that, depending on the chosen cost function, some splitting criteria are more suitable than others. We give analytical advantages and disadvantages to several cost functions and several splitting criteria, then give performance evaluations by testing on synthetic and natural sources.

A new method for lossy compression of bilevel images based on Markov random fields (MRFs) is proposed. It preserves key structural information about the image, and then reconstructs the smoothest image that is consistent with this information. The smoother the original image, the lower the required bit rate, and conversely, the lower the bit rate, the smoother the approximation provided by the decoded image. The main idea is that as long as the key structural information is preserved, then any smooth contours consistent with this information will provide an acceptable reconstructed image. The use of MRFs in the decoding stage is the key to efficient compression. Experimental results demonstrate that the new technique outperforms existing lossy compression techniques, and provides substantially lower rates than lossless techniques (JBIG) with little loss in perceived image quality.

This paper considers the source-channel coding problem of optimally assigning the codewords of an [n, k] binary linear code to the ^-dimensional vectors produced by an IID, uniformly distributed, integer-valued source with alphabet {0,1,..., 2k/n-1} when overall distortion is measured by mean squared error (MSE). It finds explicit formulas for the optimal encoding rule, minimum MSE decoding rule, and resulting distortion. This extends to the vector case the 1974 analysis by Wolf and Redinbo [2] of the optimal assignment of binary linear codes to integers. As in [1], [2], the main tool is abstract Fourier analysis for functions defined on groups. The optimal linear assignment found for vectors can be interpreted as applying the optimal assignment found in [2] to the integer in {0,1,..., 2k-1} formed by multiplexing the binary representations of the nmiddot integers in the vector being encoded in such a way that more significants bits of each integer come before less significant bits of all integers.

This paper finds the best binary linear block codes to use when an IID uniform source is uniform scalar quantized for transmission over a binary symmetric channel, with performance measured by mean squared error (MSE). The best code is found by optimizing the source-channel rate allocation, the linear code, and the assignment of its codewords to quantization indices. A table shows the maximum attained SNR, together with a code that achieves it, for a range of channel transition probabilities and transmission rates. When optimized, the performance of such systems comes within 1 ~ 2 dB of that of the best nonlinear codes found by an iterative algorithm.

With mean-squared error D as a goal, it is well known that one may approach the rate-distortion function R(D) of a nonbandlimited, continuous-time Gaussian source by sampling at a sufficiently high rate, applying the Karhunen-Loeve transform to sufficiently long blocks, and then independently coding the transform coefficients of each type. In particular, the coefficients of a given type are ideally encoded with performance attaining a suitably chosen point on the first-order rate-distortion function of that type of coefficient. This paper considers a similar sample-and-transform coding scheme in which ideal coding of coefficients is replaced by coding with some specified family of quantizers, whose operational rate-distortion function is convex. A prime example is scalar quantization with entropy-coding and, if needed for convexity, time sharing. It is shown that when the sampling rate is large, the operational rate-distortion function of such a scheme comes within a finite constant of R(D). Applied to the scalar quantization family, the finiteness of this bound contrasts with a recent result showing that direct scalar quantization of samples (without a transform) has unbounded rate when distortion is held constant and sampling rate becomes large, even when the quantized samples are compressed to their entropy-rate. Thus, at high sampling rates, the transform reduces the loss due to scalar quantization from something infinite to something finite.

This correspondence considers low-resolution scalar quantization for a memoryless Gaussian source with respect to absolute error distortion. It shows that slope of the operational rate-distortion function of scalar quantization is infinite at the point Dmaxwhere the rate becomes zero. Thus, unlike the situation for squared error distortion, or for Laplacian and exponential sources with squared or absolute error distortion, for a Gaussian source and absolute error, scalar quantization at low rates is far from the Shannon rate-distortion function, i.e., far from the performance of the best lossy coding technique

Motivated by the question of the efficiency of dense sensor networks for sampling, encoding and reconstructing spatial random fields, this paper uses the Berger-Tung upper bound to the discrete-time distributed rate-distortion function and Grenander-Szego asymptotic eigenvalue theory to obtain an upper bound to the smallest possible rate when using distributed lossy encoding of densely spaced samples that is tighter than the bound recently obtained by Kashyap et al. Both bounds indicate that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marco et al. for encoders based on time- and space-invariant scalar quantization and ideal Slepian-Wolf distributed lossless coding

This paper derives a lower bound of the form ngamma-1to the per-node throughput achievable by a wireless network when n source-destination pairs are randomly distributed throughout a disk of radius ngamma, 0alpha, alpha > 2

This paper considers low resolution scalar quantization for a memoryless Gaussian source with respect to absolute error distortion. It shows that slope of the operational rate-distortion function of scalar quantization is infinite at the point Dmaxwhere the rate becomes zero. Thus, unlike the situation for squared error distortion, or for Laplacian and exponential sources with squared or absolute error distortion, for a Gaussian source and absolute error, scalar quantization at low rates is far from the Shannon rate-distortion function, i.e. far from the performance of the best lossy coding technique

A generating function method is developed in order to select synchronization markers that maximize the timing span of period-2 periodic prefix-synchronized (PPS) sync-timing coding with small delay. Sync-timing codes are used in situations where conventional data synchronization is required, and data time stamps or time indices are also needed. A PPS code is a sync-timing code in which each encoded block of data is preceded by a synchronization marker, with the markers preceding successive blocks forming a periodic sequence with some period p. Since only PPS codes with small periods can have good rates at small delays, and since codes with p=1 are simply Gilbert's prefix-synchronized codes which have been studied previously in the literature, this paper focuses on p=2 codes. The generating function method, which extends that used by Guibas and Odlyzko to analyze p=1 codes, enables one to find PPS codes with the largest possible timing span among codes with a given delay and rate. It is found that at low delays such optimized PPS codes offer significant advantages over cascaded and natural marker PPS codes. They also compare favorably with embedded-index codes. Finally, for asymptotically large delays, it is shown that the best p=2 PPS codes operate at approximately the same rate and delay, but twice the timing span, of the best p=1 codes.

This correspondence analyzes the low-resolution performance of entropy-constrained scalar quantization. It focuses mostly on Gaussian sources, for which it is shown that for both binary quantizers and infinite-level uniform threshold quantizers, as D approaches the source variance /spl sigma//sup 2/, the least entropy of such quantizers with mean-squared error D or less approaches zero with slope -log/sub 2/e/2/spl sigma//sup 2/. As the Shannon rate-distortion function approaches zero with the same slope, this shows that in the low-resolution region, scalar quantization with entropy coding is asymptotically as good as any coding technique.

This paper considers the entropy of the highly correlated quantized samples resulting from sampling at high rate. Two results are shown. The first concerns sampling and identically scalar quantizing a stationary random process over a finite interval. It is shown that if the process crosses a quantization threshold with positive probability, then the joint entropy of the quantized samples tends to infinity as the sampling interval goes to zero. The second result provides an upper bound to the rate at which the joint entropy tends to infinity, in the case of infinite-level uniform threshold scalar quantizers and a stationary Gaussian random process whose mean lies at a midpoint of some quantization cell. Specifically, an asymptotic formula for the conditional entropy of one quantized sample conditioned on another quantized sample is derived

This paper presents a new method for designing noisy channel scalar quantizers, which is fast, more robust to initial conditions, and more amenable to a variety of distortion criteria

A uniform scalar quantizer with small step size, large support, and midpoint reconstruction levels is frequently modeled as adding orthogonal noise to the quantizer input. This paper rigorously demonstrates the asymptotic validity of this model when the input probability density function (pdf) is continuous and satisfies several other mild conditions. Specifically, as step size decreases, the correlation between input and quantization error becomes negligible relative to the mean-squared error (MSE). The model is even valid when the input density is discontinuous at the origin, but discontinuities elsewhere can prevent the correlation from being negligible. Though this invalidates the additive model, an asymptotic formula for the correlation is found in terms of the step size and the heights and positions of the discontinuities. For a finite support input density, such as uniform, it is shown that the support of the uniform quantizer can be matched to that of the density in ways that make the correlation approach a variety of limits. The derivations in this paper are based on an analysis of the asymptotic convergence of cell centroids to cell midpoints. This convergence is fast enough that the centroids and midpoints induce the same asymptotic MSE, but not fast enough to induce the same correlations.

The tradeoff between reliability and efficiency in distributed source coding for field-gathering sensor networks is examined. In the considered networks, sensors measure some underlying random field, quantize their measurements, encode the quantized values into bits and transmit these directly, or via relays, to a collector that reconstructs the field. The bits from one sensor's encoder are regarded as a packet. The minimum achievable coding rate can be attained if the sensors are ordered and each applies Slepian-Wolf distributed coding to its data assuming the decoder knows the data from all prior sensors. However, with such a coding scheme, losing even one sensor's packet would cause decoding failure for all subsequent sensors' values. Therefore, one might consider other ways of applying Slepian-Wolf coding, where in trade for increased coding rate, fewer sensor values are lost when a packet is lost. In this paper, the tradeoff between efficiency, i.e. coding rate, and reliability, characterized by a loss factor, is considered for several different Slepian-Wolf based coding schemes as a function of the packet error probability and the size of the network.

The operational rate-distortion function of entropy-constrained scalar quantizers in the asymptotic low resolution regime, for memoryless Gaussian sources, is investigated. It is shown that asymptotically, as distortion tends to variance, or equivalently as rate tends to zero, the operational rate-distortion function matches the Shannon rate-distortion function. This implies that scalar quantization is asymptotically optimal, a fact not previously known.

The performance of frog-in-the box (FIB) code index assignments is numerically investigated when maximum likelihood (ML) decoding is used in place of optimal MMSE decoding. Specifically, the reproduction levels are chosen to be those that would be used for a noiseless channel, and the decoder simply maps the channel output to a level whose index codeword is closest to the channel output.

For a Laplacian source, we estimate the support threshold for a minimum mean-squared error (MSE), fixed-rate scalar quantizer. We provide upper and lower bounds to the support threshold as a function of the number of quantization levels N and observe that the optimal support threshold grows as 3//spl radic/2 log (N/2)+O/sub N/ (1). An upper bound is given by the support threshold for a nonuniform scalar quantizer designed around the asymptotically optimal companding function c(x). A lower bound is constructed by examining the decay rate of the smallest lower half step as a function of N. Using these bounds, we derive an upper bound to the convergence rate of N/sup 2/D*/sub N/ to the Panter-Dite constant, where D*/sub N/ is the least MSE of any even, N-level scalar quantizer.

A new image coder is presented in which an image is divided into blocks, each block is quadtree segmented, and each segment is coded using a form of predictive coding. We provide nearly-optimal segmentation and quantization rules for this framework, as well as an iterative codebook design algorithm. In simulations, our new system comes within 1 dB of JPEG 2000 and outperforms JPEG by about 1.5 dB at moderate rates and up to 4.5 dB at low rates. Additionally, our method captures edges better and has potentially lower complexity than transform-based methods.

Two common source-channel coding strategies, joint and tandem, are compared on the basis of distortion versus complexity and distortion versus delay by analyzing specific representatives of each when transmitting analog data samples across a binary symmetric channel. Channel-optimized transform coding is the joint source-channel strategy; transform coding plus Reed-Solomon coding is the tandem strategy. For each strategy, formulas for the mean-squared error, computational complexity, and delay are found and used to minimize distortion subject to constraints on complexity and delay, for source data modeled as Gauss-Markov. The results of such optimizations suggest there is a complexity threshold such that when the number of operations per data sample available for encoding and decoding is greater than this threshold, tandem coding is better, and when less, channel-optimized transform coding is better. Similarly, the results suggest there is also a delay threshold such that tandem coding is better than joint coding when the permissible encoding and decoding delay is greater than this threshold.

Typically, predictive vector quantization is performed by making a prediction of upcoming data based on previously coded samples, then, using a residual quantizer to code the prediction errors. We take in alternative approach, and introduce coding by selective prediction (CSP). In CSP, there is no residual quantizer - the codebook consists only of a collection of predictors. The encoder selects the predictor that best describes a source block, then transmits the index of that predictor. We give a framework for CSP, then propose a training method for codebook design, similar to the generalized Lloyd algorithm. Using fixed-rate coding, performance results for CSP as an image coder indicate a 0.5 dB improvement over conventional predictive vector quantization at equal rates.

In this paper, we ignore transmission issues and focus on the total number of bits to transmit to the collector to form a reconstruction of the field with a given MSE. We assume that all sensors can transmit bits to the collector without error. With this assumption, with total number of bits as the cost measure, and with the style of coding, it can be argued that sensor-to-sensor relaying offers no advantages. This problem is similar to image coding and transmission, except that the quantization, encoding and transmission are constrained to take place separately at each sensor (pixel location), in contrast to traditional image coding and transmission, wherein the entire image is available for quantization, encoding, and transmission. Due to the need to separately encode values from separate sensors, we pursue a Slepian-Wolf style coding approach.

Two common source-channel coding strategies, joint and tandem, are compared on the basis of distortion vs. delay by analyzing specific representatives of each when transmitting analog data samples across a binary symmetric channel. Channel-optimized transform coding is the joint source-channel coding strategy; transform coding with Reed-Solomon coding is the tandem strategy. For each strategy, formulas for the mean-squared error and delay are found and used to minimize distortion subject to a delay constraint, for data modeled as Gauss-Markov. The results of such optimizations suggest there is a threshold such that when the permissible delay is above this threshold, tandem coding is better, and when below the threshold, channel-optimized transform coding is better.

All motion-vectors are encoded with the same tired accuracy, typically 1/2-pixel accuracy, but the best motion-vector accuracies are not known. We present a theoretical framework to find the motion-vector accuracies that minimize the total encoding rate with this type of coder, for the classical case where all motion-vectors are encoded with the same accuracy, and for new cases where the accuracy is adapted on a frame-by-frame or block-by-block basis. To do this, we analytically model the effect of motion-vector accuracy and show that the energy in a block of the difference frame is approximately quadratic in the accuracy of the block's motion-vector. This energy-accuracy model is then used to obtain expressions for the total bit rate (motion rate plus difference frame rate) in terms of the blocks' motion accuracies and other key parameters. Minimizing these expressions leads to simple formulas that indicate how to choose the best motion-vector accuracies for this type of coder. These formulas also show that the motion accuracy must increase where more texture is present and decrease when there is much scene noise or when the level of compression is high. We implement several entropy and MPEG-like video coders based on our analysis and present experimental results on synthetic and real video sequences. These results suggest that our formulas are accurate and that significant bit rate savings can be achieved when our optimization procedures are used.

Studies the asymptotic characteristics of uniform scalar quantizers that are optimal with respect to mean-squared error (MSE). When a symmetric source density with infinite support is sufficiently well behaved, the optimal step size /spl Delta//sub N/ for symmetric uniform scalar quantization decreases as 2/spl sigma/N/sup -1/V~/sup -1/(1/6N/sup 2/), where N is the number of quantization levels, /spl sigma//sup 2/ is the source variance and V~/sup -1/(/spl middot/) is the inverse of V~(y)=y/sup -1/ /spl int//sub y//sup /spl infin// P(/spl sigma//sup -1/X>x) dx. Equivalently, the optimal support length N/spl Delta//sub N/ increases as 2/spl sigma/V~/sup -1/(1/6N/sup 2/). Granular distortion is asymptotically well approximated by /spl Delta//sub N//sup 2//12, and the ratio of overload to granular distortion converges to a function of the limit /spl tau//spl equiv/lim/sub y/spl rarr//spl infin//y/sup -1/E[X|X>y], provided, as usually happens, that /spl tau/ exists. When it does, its value is related to the number of finite moments of the source density, an asymptotic formula for the overall distortion D/sub N/ is obtained, and /spl tau/=1 is both necessary and sufficient for the overall distortion to be asymptotically well approximated by /spl Delta//sub N//sup 2//12. Applying these results to the class of two-sided densities of the form b|x|/sup /spl beta//e(-/spl alpha/|x|/sup /spl alpha//), which includes Gaussian, Laplacian, Gamma, and generalized Gaussian, it is found that /spl tau/=1, that /spl Delta//sub N/ decreases as (ln N)/sup 1//spl alpha///N, that D/sub N/ is asymptotically well approximated by /spl Delta//sub N//sup 2//12 and decreases as (ln N)/sup 2//spl alpha///N/sup 2/, and that more accurate approximations to /spl Delta//sub N/ are possible. The results also apply to densities with one-sided infinite support, such as Rayleigh and Weibull, and to densities whose tails are asymptotically similar to those previously mentioned.

This paper proposes and analyzes data synchronization techniques that not only resynchronize after encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indexes of the decoded data symbols, in order to determine their positions in the original source sequence. The techniques are based on block codes, and the estimates are of the time indexes modulo some integer T, called the timing span, which is desired to be large. Several types of block codes that encode binary data are analyzed on the basis of the maximum attainable timing span for a given coding rate R (or, equivalently, redundancy /spl rho/=1-R) and permissible resynchronization delay D. It is found that relatively simple codes can asymptotically attain the maximum timing span among such block codes, which grows exponentially with delay, with exponent D(1-R)+o(D). Thus, large timing span can be attained with little redundancy and only moderate values of delay.

Until recently, the solution to the Kelvin problem of finding a partition of R/sup 3/ into equal-volume cells with the least surface area was believed to be tessellation by the truncated octahedron. In 1994, D. Weaire and R. Phelan described a partition that outperformed the truncated octahedron partition in this respect. This raises the question of whether the Weaire-Phelan (WP) partition can outperform the truncated octahedron partition in terms of normalized moment of inertia (NMI), thus providing a counterexample to Gersho's conjecture that the truncated octahedron partition has the least NMI among all partitions of R/sup 3/. In this correspondence, we show that the effective NMI of the WP partition is larger than that of the truncated octahedron partition. We also show that if the WP partition is used as the partition of a three-dimensional (3-D) vector quantizer (VQ), with the corresponding codebook consisting of the centroids of the cells, then the resulting quantization error is white. We then show that the effective NMI of the WP partition cannot he reduced by passing it through an invertible linear transformation. Another contribution of this correspondence is a proof of the fact that the quantization error corresponding to an optimal periodic partition is white, which generalizes a result of Zamir and Feder (1996).

This paper determines how the support regions of optimal and asymptotically optimal fixed-rate scalar quantizers (with respect to mean-squared error) depend on the number of quantization points N and the probability density of the variable being quantized. It shows that for asymptotic optimality it is necessary and sufficient that the support region grow fast enough that the outer (or overload) distortion decreases as o(1/N/sup 2/). Formulas are derived for the minimal support of asymptotically optimal quantizers for generalized gamma densities, including Gaussian and Laplacian. Interestingly, these turn out to be essentially the same as for the support of optimal fixed-rate uniform scalar quantizers. Heuristic arguments are then used to find closed-form estimates for the support of truly optimal quantizers for generalized gamma densities. These are found to be more accurate than the best prior estimates, as computed by numerical algorithms. They demonstrate that the support of an optimal quantizer is larger than the minimal asymptotically optimal support by a factor depending on the density but not N, and that the outer distortion of optimal quantizers decreases as 1/N/sup 3/.

Though most lossless image coding techniques use a raster scan to order the pixels for context-based predictive coding, other scans, such as the Hilbert or Peano scan, have been proposed as alternatives with potentially better performance. However, a general understanding of the merits of different scans has been lacking. In previous work, the authors had presented a framework in which the effect of pixel scan order on lossless compression can be quantitatively analyzed, so that comparisons of different scans can be made. Assuming a quantized-Gaussian and isotropic image model with contexts consisting of previously scanned adjacent pixels in a distance constrained neighborhood, it was found that the raster scan is better than the Hilbert scan. In this paper we further develop our arguments and show that for a large class of scans, which we call axial symmetric scans, the raster scan is indeed optimal. We would like to note that many common scans including the Hilbert scan fall under the class of axial symmetric scans.

This paper proposes lossless image compressors that are simpler than existing ones and yet still work well. The compressors process images in raster-scan order, and to code a pixel first estimate that pixel's value by using a linear function of already-coded pixels. Next the compressors estimate the uncertainty in the first estimate by using a nonlinear function of already-coded pixels. Finally, based on these estimates, they select a discretized Laplacian with which an arithmetic coder represents the pixel. Alternatively, the compressors may select Golomb codewords based on the estimates, and thus directly represent the pixels. These compressors' rates come within 6 to 8% of CALIC, a highly-effective image compressor. Another benefit is that a simple theoretical motivation exists for the chosen uncertainty estimators.

Though most image coding techniques use a raster scan to order pixels prior to coding, Hilbert and other scans have been proposed as having better performance due to their superior locality preserving properties. However, a general understanding of the merits of various scans has been lacking. This paper develops an approach for quantitatively analyzing the effect of pixel scan order for context-based, predictive lossless image compression and uses it to compare raster, Hilbert, random and hierarchical scans. Specifically, for a quantized-Gaussian image model and a given scan order, it shows how the encoding rate can be estimated from the frequencies with which various pixel configurations are available as previously scanned contexts, and from the corresponding conditional differential entropies. Formulas are derived for such context frequencies and entropies. Assuming an isotropic image model and contexts consisting of previously scanned adjacent pixels, it is found that the raster scan is better than the Hilbert scan which is often used in compression applications due to its locality preserving properties. The hierarchical scan is better still, though it is based on nonadjacent contexts. The random scan is the worst of the four considered. Extensions and implications of the results to lossy coding are also discussed.

This paper investigates the design and analysis of data synchronization codes whose decoders have the property that, in addition to reestablishing correct decoding after encoded data is lost or afflicted with errors, they produce the original time index of each decoded data symbol modulo some integer T. The motivation for such data synchronization with timing is that in many situations where data must be encoded, it is not sufficient for the decoder to present a sequence of correct data symbols. Instead, the user also needs to know the position in the original source sequence of the symbols being presented. With this goal in mind, periodic prefix-synchronized (PPS) codes are introduced and analyzed on the basis of their synchronization delay D, rate R, and timing span T. Introduced are two specific PPS designs called natural marker and cascaded codes. A principal result is that when coding binary data with rate R, the largest possible timing span attainable with PPS codes grows exponentially with delay D, with exponent D(1-R). Thus, a large timing span can be attained with little redundancy and moderate values of delay.

A least-squares model-based (LSMB) approach to digital halftoning is proposed. It exploits both a printer model and a model for visual perception. It attempts to produce an optimal halftoned reproduction, by minimizing the squared error between the response of the cascade of the printer and visual models to the binary image and the response of the visual model to the original gray-scale image. It has been shown that the one-dimensional (1-D) least-squares problem, in which each row or column of the image is halftoned independently, can be implemented using the Viterbi algorithm to obtain the globally optimal solution. Unfortunately, the Viterbi algorithm cannot be used in two dimensions. In this paper, the two-dimensional (2-D) least-squares solution is obtained by iterative techniques, which are only guaranteed to produce a total optimum. Experiments show that LSMB halftoning produces better textures and higher spatial and gray-scale resolution than conventional techniques. We also show that the least-squares approach eliminates most of the problems associated with error diffusion. We investigate the performance of the LSMB algorithms over a range of viewing distances, or equivalently, printer resolutions. We also show that the LSMB approach gives us precise control of image sharpness.

The authors have previously analyzed the performance of context-based lossless image coding techniques in conjunction with the Hilbert and raster scans. The analysis revealed that, under certain reasonable assumptions, the raster scan is indeed better than the Hilbert scan, thereby dispelling the popular notion that using a Hilbert scan would always lead to improved performance. In this paper they apply similar techniques to analyze a random scan as well as a progressive scan (closely based on the commonly used HINT scan). They demonstrate that the progressive scan outperforms the raster scan, but that the expected performance of a random scan is inferior to the other three systematic scans considered so far.

This paper introduces methods for reducing the table storage required for encoding and decoding with unstructured vector quantization (UVQ) or tree-structured vector quantization (TSVQ). Specifically, a low-storage secondary quantizer is used to compress the code vectors (and test vectors) of the primary quantizer. The relative advantages of uniform and nonuniform secondary quantization are investigated. A Linde-Buzo-Gray (LBG) like algorithm that optimizes the primary UVQ codebook for a given secondary codebook and another that jointly optimizes both primary and secondary codebooks are presented. In comparison to conventional methods, it is found that significant storage reduction is possible (typically a factor of two to three) with little loss of signal-to-noise ratio (SNR). Moreover, when reducing dimension is considered as another method of reducing storage, it is found that the best strategy is a combination of both. The method of secondary quantization is also applied to TSVQ to reduce the table storage required for both encoding and decoding. It is shown that by exploiting the correlation among the test vectors in the tree, both encoder and decoder storage can be significantly reduced with little loss of SNR--by a factor of about four (or two) relative to the conventional method of storing test vectors (or test hyperplanes).

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.

A conceptually simple coding method may be described as follows. The source sequence is parsed into fixed-length blocks and a list of these blocks is placed in a dictionary. In the lossless case, the dictionary is transmitted and each successive block is encoded by giving its dictionary location. In the lossy case, the smallest collection of blocks such that every member of the dictionary is within distortion /spl delta/ of the collection is determined, this codebook is transmitted, and each successive block is encoded by giving the location of a member of the code within /spl delta/ of it. We show that by optimizing on the block length, this method is universal, that is, for any ergodic process it achieves entropy in the limit in the lossless case and the rate-distortion function R(/spl delta/) in the lossy case.

We introduce an image coding algorithm based on the cortex transform, matching pursuit and perceptual pruning that selects and codes only the most perceptually relevant image components, as determined by a new image indistinguishability criterion that derives from a maximum likelihood paradigm. We demonstrate that this method selects image components that produce images with higher subjective quality than matching pursuit with the same number of components. We also show that our perceptual quantization rule makes a substantial gain over uniform scalar quantization. Finally, we present image coding results of high quality at low encoding rates.

This paper presents a probabilistic model for use in lossless image compressors. For each pixel the model provides a conditional distribution, which in the most simple case is a discretized Gaussian. The mean and variance of this Gaussian are determined by using that pixel's neighbors to search a tree to find an autoregressive model, which is then applied to those same neighbors. Finally, arithmetic coding transmits the pixel. This paper also shows how to design this tree and find the distribution parameters associated with each leaf.

A hybrid of wavelet and quadtree image coding is introduced. It uses a quadtree predictive coding technique, having good rate/fidelity performance and very low complexity, to encode the baseband wavelet coefficients. The resulting quadtree decomposition of the baseband is then used to guide the encoding of higher frequency subbands, by indicating which of their coefficients require encoding and which do not. The result is a coding method with performance comparable to those of the best known wavelet coders, but with less complexity.

We address the problem of finite-state code construction for the costly channel. This channel model is a generalization of the hard-constrained channel, also known as a subshift. Adler et al. (1986) developed the powerful state-splitting algorithm for use in the construction of finite-state codes for hard-constrained channels. We extend the state-splitting algorithm to the costly channel. We construct synchronous (fixed-length to fixed-length) and asynchronous (variable-length to fixed-length) codes. We present several examples of costly channels related to magnetic recording, the telegraph channel, and shaping gain in modulation. We design a number of codes, some of which come very close to achieving capacity.

High-rate (or asymptotic) quantization theory has found formulas for the average squared length (more generally, the qth moment of the length) of the error produced by various scalar and vector quantizers with many quantization points. In contrast, this paper finds an asymptotic formula for the probability density of the length of the error and, in certain special cases, for the probability density of the multidimensional error vector, itself. The latter can be used to analyze the distortion of two-stage vector quantization. The former permits one to learn about the point density and cell shapes of a quantizer from a histogram of quantization error lengths. Histograms of the error lengths in simulations agree well with the derived formulas. Also presented are a number of properties of the error density, including the relationship between the error density, the point density, and the cell shapes, the fact that its qth moment equals Bennett's integral (a formula for the average distortion of a scalar or vector quantizer), and the fact that for stationary sources, the marginals of the multidimensional error density of an optimal vector quantizer with large dimension are approximately i.i.d. Gaussian.

In a recent paper, Lee and Neuhoff (see ibid., vol.42, no.2, p446-60, 1996) found an asymptotic formula for the distribution of the length of the errors produced by a vector quantizer with many quantization points. This distribution depends on the source probability density, the quantizer point density, and the quantizer shape profile. (The latter characterizes the shapes of the quantization cells as a function of position.) The purpose of this paper is to give a rigorous derivation of this formula by identifying precise conditions under which it is shown that if a sequence of vector quantizers with a given dimension and an increasing number of points has "specific" point densities and "specific" shape profiles converging to a "model" point density and a "model" shape profile, respectively, then the distribution of the length of the quantization error, suitably normalized, converges to the aforementioned formula, with the model point density and the model shape profile substituted.

Several improvements to the Bugajski-Russo N-gram algorithm are proposed. When applied to English text these result in an algorithm with comparable complexity and approximately 10 to 30% less rate than the commonly used COMPRESS algorithm.

This paper studies the characteristic properties of a specific class of near-lossless image compression schemes which consists of a lossless coder followed by a uniform scalar quantizer. Three specific instances of such schemes are investigated; namely, differential pulse code modulation, hierarchical interpolation, and two-dimensional space-varying multiplicative autoregressive coders. The compression gains attainable with such schemes are studied and results of experiments conducted on several medical images are presented.

We present a novel vector quantizer (VQ) image coding algorithm, called synthetic texture VQ (STVQ), that employs shape-gain techniques to adaptively modify a synthetically-generated codebook to changing image statistics. We recursively apply STVQ to encode high-pass bands of a wavelet transform using the low-pass band as side information. An advantage of our approach is that no training is required to construct codebooks. We demonstrate STVQ on synthetic aperture radar (SAR) imagery and show that it provides efficient coding of the characteristic SAR image texture while preserving perceptual quality. Preliminary comparisons indicate that STVQ's perceptual performance exceeds JPEG at comparable rates, even though the mean-squared error performance of JPEG is better than STVQ.

We present a simple frame-adaptative procedure for minimizing the total rate in classical block based, motion-compensated lossless video coders. Our method can be applied to compress digital video for applications where no distortion is tolerated in the original video data. In motion-compensated video coding, motion vectors are used to improve the prediction of the current frame to be coded and must themselves be encoded with bits. We find an expression for the total rate of the current frame as a function of the number of bits allocated to the motion vectors. Then, we analytically derive the optimal motion bit allocations that minimize the total rate. We implement the video coder and present results on real video sequences, and discuss the potential applications of this work to the more interesting case of lossy video coding.

A new quadtree-based lossy image compression algorithm is introduced. One new feature is that one pixel in each quadtree block is predictively encoded while the remaining pixels are linearly predicted from this one and from pixels of previous blocks. Another is that the criteria for subdividing a block involves the reproduction error in each pixel, as opposed to the error energy for the entire block. Though the algorithm has very low complexity, its predictive nature gives it good rate/distortion performance and suppresses blocking artifacts. This paper describes the algorithm, shows the results of coding at .5 and .25 bits per pixel, and compares its peak signal-to-noise ratio with other methods.

A new model-based approach to digital halftoning is proposed. It is intended primarily for laser printers, which generate "distortions" such as "dot overlap". Conventional methods, such as clustered-dot ordered dither, resist distortions at the expense of spatial and gray-scale resolution. The proposed approach relies on printer models that predict distortions, and rather than merely resisting them, it exploits them to increase, rather than decrease, both spatial and gray-scale resolution. We propose a general framework for printer models and find a specific model for laser printers. As an example of model-based halftoning, we propose a modification of error diffusion, which is often considered the best halftoning method for CRT displays with no significant distortions. The new version exploits the printer model to extend the benefits of error diffusion to printers. Experiments show that it provides high-quality reproductions with reasonable complexity. The proposed modified error diffusion technique is compared with Stucki's (1981) MECCA, which is a similar but not widely known technique that accounts for dot overlap. Model-based halftoning can be especially useful in transmission of high-quality documents using high-fidelity gray-scale image encoders.

The problem of scalar and vector quantization in conjunction with a noisy binary symmetric channel is considered. The issue is the assignment of the shortest possible distinct binary sequences to quantization levels or vectors so as to minimize the mean-squared error caused by channel errors. By formulating the assignment as a matrix (or vector in the scalar case) and showing that the mean-squared error due to channel errors is determined by the projections of its columns onto the eigenspaces of the multidimensional channel transition matrix, a class of source/quantizer pairs is identified for which the optimal index assignment has a simple and natural form. Among other things, this provides a simpler and more accessible proof of the result of Crimmins et al. (1969) that the natural binary code is an optimal index assignment for the uniform scalar quantizer and uniform source. It also provides a potentially useful approach to further developments in source-channel coding.

This paper extends Bennett's (1948) integral from scalar to vector quantizers, giving a simple formula that expresses the rth-power distortion of a many-point vector quantizer in terms of the number of points, point density function, inertial profile, and the distribution of the source. The inertial profile specifies the normalized moment of inertia of quantization cells as a function of location. The extension is formulated in terms of a sequence of quantizers whose point density and inertial profile approach known functions as the number of points increase. Precise conditions are given for the convergence of distortion (suitably normalized) to Bennett's integral. Previous extensions did not include the inertial profile and, consequently, provided only bounds or applied only to quantizers with congruent cells, such as lattice and optimal quantizers. The new version of Bennett's integral provides a framework for the analysis of suboptimal structured vector quantizers. It is shown how the loss in performance of such quantizers, relative to optimal unstructured ones, can be decomposed into point density and cell shape losses. As examples, these losses are computed for product quantizers and used to gain further understanding of the performance of scalar quantizers applied to stationary, memoryless sources and of transform codes applied to Gaussian sources with memory. It is shown that the short-coming of such quantizers is that they must compromise between point density and cell shapes.>

A new lossless predictive image coder is introduced and tested. The predictions are made with a nonlinear, vector quantizer based, adaptive predictor. The prediction errors are losslessly compressed with an arithmetic coder that presumes they are Laplacian distributed with variances that are estimated during the prediction process, as in the approach of Howard and Vitter (1992).>

The paper presents several algorithms for designing fixed- and variable-depth decision trees for searching vector quantizer (VQ) codebooks. Two applications of such are explored. First, given a source vector, a tree can be used to find the closest codevector in the VQ codebook with many fewer arithmetic operations than the usual "full search." This decrease in complexity comes at the expense of an increase in auxiliary table storage. Second, the tree can be used as the first stage of fine-coarse vector quantization, which yields further savings in complexity at the cost of somewhat more storage and a small increase in distortion. The design methods involve incrementally growing trees with a variety of node splitting criteria and, subsequently, optimally pruning trees on the basis of performance functionals such as distortion, storage, and computational complexity. The pruning is done with the BFOS algorithm, which optimally trades one performance functional with another, and with an extension of the BFOS algorithm wherein one performance measure is traded with a combination of two others. The results of applying these methods to i.i.d. Gaussian, Gauss-Markov, and sampled speech sources at encoding rates of one and two bits per source sample demonstrate the tradeoffs achievable amongst time (complexity), memory (storage), and distortion.>

The authors present a new technique for coding gray-scale images for facsimile transmission and printing on a laser printer. They use a gray-scale image encoder so that it is only at the receiver that the image is converted to a binary pattern and printed. The conventional approach is to transmit the image in halftoned form, using entropy coding (e.g., CCITT Group 3 or JBIG). The main advantages of the new approach are that one can get higher compression rates and that the receiver can tune the halftoning process to the particular printer. They use a perceptually based subband coding approach. It uses a perceptual masking model that was empirically derived for printed images using a specific printer and halftoning technique. In particular, they used a 300 dots/inch write-black laser printer and a standard halftoning scheme ("classical") for that resolution. For nearly transparent coding of gray-scale images, the proposed technique requires lower rates than the standard facsimile techniques.

We present a new technique for coding gray-scale images for facsimile transmission and printing on a laser printer. We use a gray-scale image encoder so that it is only at the receiver that the image is converted to a binary pattern and printed. The conventional approach is to transmit the image in halftoned form, using entropy coding (e.g. CCITT Group 3 or JBIG). The main advantages of the new approach are that we can get higher compression rates and that the receiver can tune the halftoning process to the particular printer. We use a perceptually based subband coding approach. It uses a perceptual masking model that was empirically derived for printed images using a specific printer and halftoning technique. In particular, we used a 300 dots/inch write-black laser printer and a standard halftoning scheme ("classical") for that resolution. For nearly transparent coding of gray-scale images, the proposed technique requires lower rates than the standard facsimile techniques.

A least-squares model-based approach to digital halftoning is proposed. It exploits both a printer model and a model for visual perception. It obtains an optimal halftoned reproduction by minimizing the squared error between the response of the cascade of the printer and visual models to the binary image and the response of the visual model to the original gray-scale image. Least-squares model-based halftoning uses explicit eye models and relies on printer models that predict distortions and exploit them to increase, rather than decrease, both spatial and gray-scale resolution. The authors examine the one-dimensional case, in which each row or column of the image is halftoned independently. One-dimensional least-squares halftoning is implemented, in closed form, with the Viterbi algorithm. Experiments show that it produces better spatial and gray-scale resolution than conventional one-dimensional techniques and eliminates the problems associated with the modified (to account for printer distortions) error diffusion algorithm.>

It is proved that for finite-alphabet, finite-state unifilar sources, variable-to-fixed length codes provide better large deviations performance of the empirical compression ratio, than fixed-to-variable length codes. It is shown how to construct a universal variable-to-fixed length code that achieves the optimal performance.>

Two-stage vector quantization (2VQ) reduces the complexity of single-stage VQ at the cost of reduced performance. Cell-conditioned (CC) 2VQ is proposed to improve the performance of 2VQ, while retaining the advantage of reduced complexity. In CC2VQ, the error vector from the first stage is transformed prior to its quantization by second stage. The effect of transformation is to cause the size and orientation of different first-stage cells to be as similar as possible. It is shown theoretically that CC2VQ performs as well as single-stage VQ under asymptotic conditions. Some experimental results for the vector quantization of speech waveforms are presented to support these theoretical results.>

Tree-structured vector quantization (TSVQ) is a commonly used structured vector quantization (VQ) technique that permits much faster quantization and incurs a little more distortion than full search of an optimal unstructured VQ. By exploiting two recently developed asymptotic quantization formulas it is shown that the mean-squared error of TSVQ and, moreover, the probability density of the magnitude of its errors support the hypothesis that TSVQ has an optimal point density and that its cells consist of various rectangular-like polyhedra.>

A new technique is presented for coding gray-scale images for facsimile transmission and printing on a laser printer. The authors use a gray-scale image encoder so that it is only at the receiver that the image is converted to a binary pattern and printed. The conventional approach is to transmit the image in halftoned form, using entropy coding (e.g. CCITT Group 3, or JBIG). The main advantages of the new approach are that it is possible to get higher compression rates and that the receiver can tune the halftoning process to the particular printer. A perceptually based subband coding approach is used.>

The performance of a lattice-based fast vector quantization (VQ) method, which yields rate-distortion performance to that of an optimal VQ, is analyzed. The method, which is a special case of fine-coarse vector quantization (FCVQ), uses the cascade of a fine lattice quantizer and a coarse optimal VQ to encode a given source vector. The second stage is implemented in the form of a lookup table, which needs to be stored at the encoder. The arithmetic complexity of this method is essentially that of lattice VQ. Its distortion can be made arbitrarily close to that of an optimal VQ, provided sufficient storage for the table is available. It is shown that the distortion of lattice-based FCVQ is larger than that of full search quantization by an amount that decreases as the square of the diameter of the lattice cells, and it provides exact formulas for the asymptotic constant of proportionality in terms of the properties of the lattice, coarse codebook, and source density. It is shown that the excess distortion asymptotically equals that of the fine quantizer. Simulation results indicate how small the lattice cells must be in order for the asymptotic formulas to be applicable.>

A method for computing the mean squared error distortion of differential pulse code modulation (DPCM) applied to Gaussian autoregressive sources is developed. This extends previous work wherein the code predictor was matched to the source. A two-dimensional version of the projection method for the computation of the stationary distribution of the joint source-state process is developed from which distortion can be readily evaluated. An iterative algorithm is used to optimize the quantizer for a given source and predictor. The results show that the matched predictor is very nearly optimal but not exactly so, and that DPCM is fairly robust to mismatch of the prediction coefficient to the correlation coefficient of a first-order autoregressive source.>

Continuity and singularity properties of the stationary state distribution of differential pulse code modulation (DPCM) are explored. Two-level DPCM (i.e. delta modulation) operating on a first-order autoregressive source is considered, and it is shown that, when the magnitude of the DPCM prediction coefficient is between zero and one-half, the stationary state distribution is singularly continuous; i.e. it is not discrete but concentrates on an uncountable set with a Lebesgue measure of zero. Consequently, it cannot be represented with a probability density function. For prediction coefficients with magnitude greater than or equal to one-half, the distribution is pure, i.e. either absolutely continuous and representable with a density function, or singular. This problem is compared to the well-known and still substantially unsolved problem of symmetric Bernoulli convolutions.>

The key step in the analysis of differential pulse code modulation (DPCM) is to find the steady-state probability distribution of a random process in terms of which the code distortion can be evaluated. For the case of an autoregressive source and a matched DPCM code, a well-known approximation technique has been used for the evaluation of the steady-state distribution of the prediction error process. However, the validity of this approximation method has not been justified before. A framework in which this approximation technique can be viewed as the projection method for the solution of integral equations is established. Sufficient conditions under which the approximation method can be rigorously justified are obtained.>

Several incremental algorithms are presented for designing fixed length decision trees for searching the codebook of a vector quantizer (VQ). These trees are then used as the basis for a two-stage VQ, wherein the first stage is a high-rate, structured VQ with a fast quantization algorithm and the second stage is a low-rate optimal VQ. The mean square error and complexity of the resulting two-stage VQs are presented for i.i.d. Gaussian and speech sources, and are compared with both TSVQ and previous tree based two-stage VQ designs.>

A new class of chain codes for line drawings, named delta codes is introduced. Two specific types of fixed angle delta codes and ring delta codes are described. The area-of-error distortion and rate are calculated for two types of delta codes applied to straight and slowly curving lines, and it is shown that the delta outperforms other chain codes with the same set of link types. For rapidly curving lines, however, the delta codes introduce curvature overload distortion analogous to the slope overload distortion of traditional delta modulation for waveforms.>

A fixed-rate block code is said to be strongly robust for a class of sources\Lambdaif its maximum distortion over\Lambdah is no larger than the maximum of the distortion-rate functions of the sources in the class at the rate of the code. It is shown that such codes exist at all positive rates whenever the class is compact with resect to the topology of weak convergence and satisfies certain additional, but not very strong, constraints on the alphabet and distortion measure. Examples of classes that satisfy these conditions are given. In addition, classes are exhibited for which there are no strongly robust codes. These help to demarcate the boundary between classes for which strongly robust codes do and do not exist. More specifically, they show that strongly robust codes exist more widely than strongly universal codes but !ess widely than weakly universal codes.

The performance of chain codes for line drawings in the framework of source coding with a fidelity criterion is investigated. A formal characterization is given for a broad class of chain codes that includes the generalized chain codes of Freeman and the convex quantizers of Koplowitz. Measures of distortion (fidelity) and rate (efficiency) are introduced. The distortion and rate are calculated for several types of chain codes applied to straight and slowly curving lines. Several statistical models for straight lines are introduced and the average performance of chain codes for these models is investigated.

The following problem in universal source coding is explored. Some members of a class of sources have various constraints on the maximum rate at which they may be encoded, and thc remainder have various constraints on the maximum distortion that may result from encoding. It is desired to find a universal code that will adapt its performance so that whatever source in the class is encoded, the resulting performance meets the constraint and is optimal in the rate-distortion function sense for that particular source. It is shown that such codes exist when the class is totally bounded and the constraints are uniformly continuous in an appropriate sense. A key result shows that the value of any uniformly continuous function on a totally bounded class can be uniformly well estimated from observations of the output of any source in

Causal source codes are defined. These include quantizers, delta modulators, differential pulse code modulators, and adaptive versions of these. Several types of causal codes are identified. For memoryless sources it is shown that the optimum performance attainable by causal codes can be achieved by memoryless codes or by time-sharing memoryless codes. This optimal performance can be evaluated straightforwardly.

The class of discrete stationary channels with memory that can be arbitrarily well approximated by indecomposable finite state channels is investigated. The\bar{d}concept of channel distance is used to quantify the notion of one channel approximating another, and it is shown that the class of interest equals the class of channels approximable by nonanticipating primitive channels. The latter class includes all nonanticipating finite memory channels and all nonanticipating\bar{d}-continuous, conditional almost block independent (CABI) channels. In addition, it is shown that for a large class of finite state channels,\bar{d}continuity and CABI imply indecomposability.

Two results on the coding of stationary nonergodic sources are presented. The first is a source coding theorem stating that there exist variable-rate codes with performance arbitrarily close to the rate-distortion function of the stationary nonergodic source. The second is a converse information transmission theorem. It is shown that the distortion which results when the source is transmitted across a channel with capacityCis no less than the least distortion achievable by fixed-rate codes with rateC.

A stationary channel can have two kinds of memory--input memory and output memory. Recently, Gray and Ornstein introduced a condition on the decay of input memory called\bar{d}-continuity and established coding theorems for d-continuous channels. In this paper a condition for the decay of output memory is introduced which is called conditional almost block independence (CABI). It is believed that these two properties describe the character of many channels of interest. The principal result states that the\bar{d}-continuous CABI channels are precisely those which can be approximated in a very strong sense by a simple kind of finite memory channel, called a primitive channel, in which the source of randomness is memoryless and completely separated from the memory.

The existence of a fixed-rate block source code whose performance for each source in a class of Markov sources is uniformly close to the distortion-rate function of that source is investigated. Such a code is called strong universal. It is found that strong universal codes of all rates exist for the class of all binary first-order Markov sources. But for a larger alphabet or for the class of allnth-order Markov sources withn > 2, there is a critical rateR\astsuch that strong universal codes exist for rates greater than or equal toR\ast, but not for rates less thanR\ast.

A new form of source coding subject to a fidelity criterion, called sliding-block coding, has recently been introduced by Gray, Neuhoff, and Ornstein. A method of conversion from block coding to sliding-block coding, or vice versa, with an arbitrarily small increase in rate is shown for ergodic sources. The ergodic theorem is used to convert from sliding-block codes to block codes. A theorem similar to one of Rohlin is used to convert from block codes to sliding-block codes. A proof of this theorem and some discussion of the nonergodic case appear in the appendices.

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.

The results of an experiment are described in which contextual information is used to improve the performance of an optical character reader when reading English text. Specifically, English is modeled as a Markov source and the Viterbi algorithm is used to do maximuma posteriorisequence estimation on the output of an optical character reader (OCR).

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.