If we quantize a block of n samples and then transmit information about quantization step size in the same bitstream, we may naturally expect such a code to be at least O(1/n) redundant. However, as we will show in this paper, this may not necessarily be true. Moreover, we prove that asymptotically, such codes can be as efficient as block codes without embedded step-size information. The proof relies on results from the Diophantine approximations theory. We discuss the significance of this finding for practical applications, such as the design of audio and video coding algorithms.

This paper analyzes the average behavior of video streaming systems with adaptation to network bandwidth and player sizes. The main results are formulae for average system performance parameters such as average system bandwidth consumption, average delivered quality, etc. Derived expressions are used to study performance limits achievable by adaptive streaming, and to pose several related optimization problems. Numerical simulations, illustrating the usefulness of the proposed formulae and techniques are also provided.

In this paper, we provide an overview of the DCT/DST transform scheme for intra coding in the HEVC standard. A unique feature of this scheme is the use of DST-VII transforms in addition to DCT-II. We further derive factorizations for fast joint computation of DCT-II and DST-VII transforms of several sizes. Simulation results for the DCT/DST scheme in the HM reference software for HEVC are also provided together with a discussion on computational complexity.

We describe the design of a perceptual preprocessing filter for improving the effectiveness of video coding. This filter uses known parameters of the reproduction setup, such as viewing distance, pixel density, and contrast ratio of the screen, as well as a contrast sensitivity model of human vision to identify spatial oscillations that are invisible. By removing such oscillations the filter simplifies the video content, therefore leading to more efficient encoding without causing any visible alterations of the content. Through experiments, we demonstrate the use of our filter can yield significant bit rate savings compared to conventional encoding methods that are not tailored to specific viewing conditions.

We study the problem of coding of unordered sets of words, appearing in natural language processing, retrieval, machine learning, computer vision, and other fields. We note that this problem is different from the problem of coding of a particular sequence of same words, and show that up to log(m!) bits (where m is the number of words in the set) can be saved by specialized codes for sets. We propose one possible design of such codes, and prove its asymptotic optimality in the memoryless model.

We study the problem of quantization of discrete probability distributions, arising in universal coding, as well as other applications. We show, that in many situations this problem can be reduced to the covering problem for the unit simplex, yielding precise characterization in the high-rate regime. Our main contribution is a simple and asymptotically optimal algorithm for solving this problem. Performance of this algorithm is studied and compared with several known solutions.

This paper presents fast 15times15 transform for image and video coding applications. We note, that our proposed transform is significantly less complex than DCT-II of nearest dyadic size N=16, for which best known factorization [2] requires 31 multiplications and 81 additions. In comparison with H.264-type cascade of 4-point transforms, our proposed algorithm is slightly higher in complexity, but offers better coding gain.

Consider an m-ary memoryless source, producing symbols alpha1,..., alphamwith probabilities p1, ..., pm. We assume that instead of true probabilities, we have to use their approximate values pcirc1, ..., pcircmwith maximum absolute error: delta* = maxi|pi- pcirci| . By Pmin= mini{pi} we denote the smallest source's probability. We assume that pmin> 0, and that it is relatively large w.r.t approximation error delta*/pmin< 1.

This paper presents variable length code and its corresponding Moffatt-Turpin decoding structure. The code of a modified algorithm using such data structure.

We design a low-complexity algorithm for adaptive encoding/decoding of binary sequences produced by memoryless sources. Our algorithm processes input data in blocks of n = 8..16 bits, and uses numbers of nonzero bits in previously encoded blocks as contexts

Summary form only given. Given a sample produced by an unknown memoryless source, we show how to estimate its entropy with much higher precision by adding a simple correction term to a commonly used expression. We also derive asymptotic expansions for sample-based entropy of mixtures and sample-based mutual information. These results are obtained using technique discussed by P. Flajolet (see Theoretical Computer Science, vol.215, p.371-81, 1999).

Summary form only given. Complex data sources, like images and audio, require sophisticated coding contexts and source modeling. Fortunately, in many cases the high cost for estimating a very large number of conditional probabilities and then computing optimal codes, can be avoided by storing sets of codewords, and selecting the best choice based on local source estimates. Golomb-Rice prefix codes are commonly used for such purposes because of their convenient features. We consider the fact that, even when the source distribution is geometric, the Golomb-Rice codes are truly optimal only when the source parameter, /spl rho/, is known with certainty, which in practice is never the case. We investigate how these codes perform - on sources with geometric distribution - depending on how /spl rho/ is estimated from previous samples. We analyze possible changes in the code to increase robustness, but keeping the useful structural properties. The intention is not to propose a "new" type of code for particular applications, but to observe how the optimal codes change with different models of source uncertainty and estimation methods. Numerical results show that the optimal codes are, as expected, always better than Golomb-Rice codes.

This paper provides a brief overview of an emerging ISO/IEC standard for lossless audio coding, MPEG-4 ALS and explains the choice of algorithms used in its design, and compare it to current state-of-the-art algorithms for lossless audio compression.

Summary form only given. The average redundancy rate of Krichevsky's sample-based universal block codes was analyzed, in a situation wherein the samples and block codes for compression were produced from two different memoryless sources. It was proven that the average redundancy rate of adaptive block codes O/sub /spl lscr/,T/, constructed using samples of length /spl lscr/ from a source T, were used to encode block codes of length n from a source S. The adaptive block codes, constructed using samples from a source T and applied to a source S, have achieved lower average redundancy than universal codes.

In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memoryless sources. This technique (which we call a symmetrization of the source) bijectively maps the sequences of symbols from the original (asymmetric) source into symbols of an output alphabet resulting in a more uniform distribution. We introduce a criterion of efficiency for such a mapping, and demonstrate that a problem of finding an optimal construction for a given source (or universal) symmetrization transform is equivalent to a problem of constructing a minimum redundancy variable-length-to-block code for this source (or class of sources). Based on this result, we propose search algorithms that incorporate known (optimal for a given source and universal) variable-length-to-block codes and study their asymptotic behaviour. We complement our analysis with a description of an efficient algorithm for universal symmetrization of binary memoryless sources, and compare the performance of the resulting search structure with the standard tries.

In this paper we examine the average redundancy rate of a Lempel-Ziv 78 code with the k-error protocol. Storer and Reif (1997) have studied this modification of the Lempel-Ziv scheme and shown that it provides an efficient protection against error propagation while preserving the asymptotic optimality of the code. We refine this result by providing an asymptotic expression for the average redundancy rate of this code for memoryless sources. We have established our result by exploiting a relationship between a parsing scheme of the Lempel-Ziv encoder with the k-error protocol and a generalization of the digital search tree structure, and by using analytical techniques of the analysis of algorithms. We accompany our analysis with a number of experiments that test the validity of our theoretical result and demonstrate the effects of various additional modifications of the Lempel-Ziv algorithm.

Summary form only given. A very fast longest-match string search algorithm for Ziv-Lempel compression has been proposed. The new algorithm uses a variable-radix search tree of limited maximum size with an appropriate node-replacement strategy. The efficiency of the new algorithm has been practically evaluated using the LZRW1 implementation as a test model. The results of the evaluation are presented in a table.