This paper investigates the cost-optimal design of a hybrid video distribution system that includes broadcast and unicast delivery networks. Broadcast costs are modeled based on the total bandwidth of all broadcasted channels, while unicast costs are based on the total edge traffic generated by users accessing unicast-delivered content. Using these models, we derive an expression for the system's overall operating cost and formulate an optimization problem to minimize it. Subsequently, we derive an analytical solution that reveals the lowest achievable cost, enables comparisons between hybrid and purely broadcast or unicast architectures, and explains the effects of key system parameters on the attainable operating cost. To validate our approach, we perform a numerical study using real-world TV channel audience statistics and realistic cost metrics for both delivery modes. The results confirm our theoretical findings.

This paper studies the problem of minimizing delivery costs in multi-CDN streaming systems. As inputs, this problem receives information about minimum edge traffic volume commitments and edge traffic rates defined in CDN contracts. As input, the problem also receives historical data about CDN traffic volume statistics and predicted volume trends for the remainder of a billing period. As output, it computes load allocation for all CDNs for the remainder of the billing period, minimizing total CDN delivery costs. We show how this problem can be formalized and analytically reduced to a superposition of linear programming and combinatorial search problems. As such, this problem is tractable and practically solvable by existing methods. The paper also discusses the implementation of the proposed methods by multi-CDN systems using the HLS/DASH content steering mechanism.

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.

Over the years, many subjective and objective quality assessment datasets have been created and made available to the research community. However, there is no standard process for documenting the various aspects of the dataset, such as details about the source sequences, number of test subjects, test methodology, encoding settings, etc. Such information is often of great importance to the users of the dataset as it can help them get a quick understanding of the motivation and scope of the dataset. Without such a template, it is left to each reader to collate the information from the relevant publication or website, which is a tedious and time-consuming process. In some cases, the absence of a template to guide the documentation process can result in an unintentional omission of some important information. This paper addresses this simple but significant gap by proposing a datasheet template for documenting various aspects of sub-jective and objective quality assessment datasets for multimedia data. The contributions presented in this work aim to simplify the documentation process for existing and new datasets and improve their reproducibility. The proposed datasheet template is available on GitHub1, along with a few sample datasheets of a few open-source audiovisual subjective and objective datasets.

In modern-era video streaming systems, videos are streamed and displayed on a wide range of devices. Such devices vary from large-screen UHD and HDTVs to medium-screen Desktop PCs and Laptops to smaller-screen devices such as mobile phones and tablets. It is well known that a video is perceived differently when displayed on different devices. The viewing experience for a particular video on smaller screen devices such as smartphones and tablets, which have high pixel density, will be different with respect to the case where the same video is played on a large screen device such as a TV or PC monitor. Being able to model such relative differences in perception effectively can help in the design of better quality metrics and in the design of more efficient and optimized encoding profiles, leading to lower storage, encoding, and transmission costs. However, to the best of our knowledge, open-source datasets providing subjective scores for the same content when viewed on multiple devices with different screen sizes do not exist, thus limiting a proper evaluation of the existing quality metrics for such multi-screen video streaming applications. This paper addresses this research gap by presenting a new, open-source dataset consisting of subjective ratings for various encoded video sequences of different resolutions and bitrates (quality) when viewed on three devices of varying screen sizes: TV, Tablet, and Mobile. Along with the subjective scores, an evaluation of some of the most famous and commonly used open-source objective quality metrics is also presented. It is observed that the performance of the metrics varies a lot across different device types, with the recently standardized ITU-T P.1204.3 Model, on average, outperforming their full-reference counterparts. The dataset consisting of the videos, along with their subjective and objective scores, is available freely on Github1.

Resolution is a fundamental property of encoded video. Understanding the impact of resolution on quality as an independent parameter can help design better, more efficient systems, such as selecting optimum rendition in adaptive video streaming applications. One known quality model that considers resolution for predicting the perceived picture quality is the Westerink and Roufs (WR) model, which establishes the relationship between subjective quality and two parameters of viewing setup: angular resolution and viewing angle. This paper first validates the WR model on recent datasets and shows that it is reasonably accurate. We then propose a generalization of this model, allowing operation in a broader range of parameters and with more graceful saturation in extended regions. We then validate the performance of the proposed Generalized WR model on the new datasets and show that the proposed model achieves even a better fit to the recent datasets. We also demonstrate that the proposed Generalized model can account for the differences in scaling algorithms, including more advanced ML-based methods such as super-resolution. We conclude with a discussion of several possible applications of this model, including its use to guide the rendition selection decisions in streaming players and adapt that decision logic based on the upsampling algorithms used at the player.

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.

We propose dataset capturing statistics of several large-scale real-world streaming events, delivering videos to different devices (TVs, desktops, mobiles, tablets, etc.), and over different networks (from 2.5G, 3G, and other early generation mobile networks to 5G and broadband). The data we capture include network-related statistics, playback statistics (session- and player-event-level), and characteristics of the encoded streams. Such data should enable a broad level of possible applications and uses in the research community: from analysis of the effectiveness of algorithms in streaming players to studies of QoE metrics, and end-to-end system optimizations. Examples of such possible studies based on the proposed datasets are also provided.

Reducing end-to-end streaming latency is critical to HTTP-based live video streaming. There are currently two technologies in this domain: Low-Latency HTTP Live Streaming (LL-HLS) and Low-Latency Dynamic Adaptive Streaming over HTTP (LL-DASH). Many players support LL-HLS and/or LL-DASH protocols, including Apple's AVPlayer, Shaka player, HLS.js Dash.js, and others. This paper is dedicated to the analysis of the performance of low-latency players and streaming protocols. The evaluation is based on a series of live streaming experiments, repeated using identical video content, encoders, encoding profiles, and network conditions, emulated by using traces of real-world networks. Several performance metrics, such as average stream bitrate, the amounts of downloaded media data, streaming latency, as well as buffering and stream switching statistics are captured and reported in our experiments. These results are subsequently used to describe the observed differences in the performance of LL-HLS and LL-DASH-based players.

We study the behavior of a modern-era adaptive streaming system delivering videos embedded in web-pages. In such an application, the size of videos rendered on the screen may depend on user preferences, such as the position and size of a browser window. Moreover, the stream selection logic in such a system appears to be influenced not only by the available network bandwidth but also by the output video size, which, in many cases, limits the selection of higher quality streams. To explain this behavior, in this paper we introduce a simple analytical model of a client adapting to both bandwidth and player size. Using this model, we then compute stream selection probabilities and show that they are sufficiently close to respective statistics observed in practical experiments. Possible uses of this proposed client model are also suggested. Specifically, we show how it can be used to derive formulae for the average performance parameters of the system and also for posing related optimization problems.

In this paper, we present a frame rate up-conversion (FRUC) scheme that uses optical flows in forward and backward directions and with two different regularization parameters to derive alternative motion vector fields. The motion vectors are then assessed for their relevance, resulting in prediction weights assigned to each candidate motion vector. Multiple hypothesis reconstruction is then performed, where overlapping patches of pixels associated with multiple motion vectors are fused using their corresponding weights to yield pixels of an interpolated frame. Four flavors of our approach are proposed having different tradeoffs between quality and computational complexity. Experiments conducted using standard test set show that all our schemes yield significantly higher quality compared to existing FRUC algorithms.

The human visual system (HVS) cannot perceive spatial frequency components in an image that are above a certain limit, the value of which is affected by factors such as the viewing distance. This has been exploited to improve the video coding efficiency by first filtering out redundant frequency components and then doing conventional video encoding. To facilitate the deployment of this scheme, we propose to implement it in a network entity such as a Multipoint Control Unit (MCU). Specifically, by analyzing the video sent from a client, the MCU infers that client's viewing conditions, which are then used to adapt the encoding of the video destined to that client. The scheme is implemented in a real-world video teleconferencing system. Experimental results show that our approach can result in significant savings in bandwidth without affecting subjective video quality.

We describe the use of perceptual pre-processing to reduce the bitrate needed for delivery of Video on Demand (VOD) content. The proposed system exploits estimated viewing conditions to remove image oscillations which are not visible to the user under the specific viewing conditions. The pre-processing uses parameters such as: viewing distance, pixel density, ambient illumination, etc. A model of human visual system contrast sensitivity is used to remove oscillations in the image data which cannot be seen and need not be encoded. Experiments demonstrate significant bitrate savings compared to conventional encoding methods which do not exploit viewing conditions.

The MPEG committee has completed development of a new audio coding standard called “MPEG-4 advanced audio coding-enhanced low delay” (AAC-ELD). AAC-ELD uses low delay spectral band replication (LD-SBR) technology together with a low delay time domain alias cancellation (LD TDAC) filterbank in the encoder to achieve both high coding efficiency and low algorithmic delay. In this paper, we present fast algorithms for implementing LD-TDAC filterbanks in AAC-ELD. Two types of fast algorithms are presented. In the first, we map LD-TDAC analysis and synthesis filterbanks to modified discrete cosine transform (MDCT) and inverse modified discrete cosine transform (IMDCT), respectively. Since MDCT/IMDCT are already extensively used in AAC and they have many fast algorithms, this mapping not only provides a fast implementation but also allows a common implementation of the filterbanks in AAC Low Complexity (AAC-LC), AAC Low Delay (AAC-LD) and AAC-ELD codecs. In the second algorithm, we provide a mapping to discrete Cosine transform of type II. The mapping to DCT-II allows the merger of the matrix operations with the windowing stage that precedes or follows them. This further reduces the number of multiplications and leads to an algorithm with the lowest known arithmetic complexity. For filterbanks of lengths 1024 and 960, we also present a new fast factorization of 15-point DCT-II that requires only 14 irrational multiplications, 3 dyadic rational multiplications and 67 additions.

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.

Discrete Sine Transforms of type VII (DST-VII) have recently received considerable interest in video coding. In this paper, we show that there exists a direct connection between DST-VII and DCT-II transforms, allowing their joint computation for certain transform sizes. This connection also yields fast algorithms for constructing DCT-VI and DCT-VII.

We describe design of an adaptive video delivery system employing a perceptual preprocessing filter. Such filter receives parameters of the reproduction setup, such as viewing distance, pixel density, ambient illuminance, etc. It subsequently applies a contrast sensitivity model of human vision to remove spatial oscillations that are invisible under such conditions. 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 that the use of our filter can yield significant bit rate savings compared to conventional encoding methods that are not tailored to specific viewing conditions.

In this paper, we analyze the effect of time-varying channels to video codec buffer specially for low-delay applications. We derive the sufficient conditions under which an encoder can design a bitstream for any time-varying channel without decoder buffer overflow and underflow. We then apply those conditions to design a bandwidth adaptive rate control in x264 and test it under LTE simulator. Our test results show significant improvement of delay and delay jitter over traditional leaky bucket models.

Summary form only given. We describe the design of a mobile streaming system, which optimizes video delivery based on dynamic analysis of user behavior and viewing conditions, including user proximity, viewing angle, and ambient illuminance.

In systems employing feedback-based error resilience, error propagation can significantly degrade visual quality when feedback delay is in the order of a few seconds. We propose a coding structure based on multiple description coding that mitigates error propagation during feedback delay, and uses feedback to adapt its coding structure to effectively limit error propagation. We demonstrate the effectiveness of our approach at different error rates when compared to conventional coding schemes that use feedback.

The MPEG committee has recently completed development of a new audio coding standard “MPEG-4 Advanced Audio Coding-Enhanced Low Delay” (AAC-ELD). AAC-ELD is targeted towards high-quality, full-duplex communication applications such as audio and video conferencing. AAC-ELD uses low delay spectral band replication (LD-SBR) technology together with a low delay AAC core encoder to achieve high coding efficiency and low algorithmic delays. In this paper, we present fast algorithms for computing LD-SBR filterbanks in AAC-ELD. The proposed algorithms map complex exponential modulation portion of the filterbanks to discrete cosine transforms of types IV and II. Our proposed mapping also allows to merge some multiplications with the windowing stage that precedes or succeeds the modulation step. This further reduces computational complexity. Our presentation includes detailed explanation and flow-graphs of the algorithms, complexity analysis, and comparisons with alternative implementations.

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.

We study the problem of coding of unordered sets of words, appearing in language processing, retrieval, machine learning, computer vision, and other fields. We review known results about this problem, and offer a code construction technique suitable for solving it. We show that in a memoryless model the expected length of our codes approaches Ht - log m! + O(m) where m is the number of words in the set, t is the combined length of all words, and H is the entropy of the source. We also offer design of a universal code for sets of words and perform its redundancy analysis.

We survey popular data sets used in computer vision literature and point out their limitations for mobile visual search applications. To overcome many of the limitations, we propose the Stanford Mobile Visual Search data set. The data set contains camera-phone images of products, CDs, books, outdoor landmarks, business cards, text documents, museum paintings and video clips. The data set has several key characteristics lacking in existing data sets: rigid objects, widely varying lighting conditions, perspective distortion, foreground and background clutter, realistic ground-truth reference data, and query data collected from heterogeneous low and high-end camera phones. We hope that the data set will help push research forward in the field of mobile visual search.

We evaluate the performance of MPEG-7 image signatures, Compressed Histogram of Gradients descriptor (CHoG) and Scale Invariant Feature Transform (SIFT) descriptors for mobile visual search applications. We observe that SIFT and CHoG outperform MPEG-7 image signatures greatly in terms of feature-level Receiver Operating Characteristic (ROC) performance and image-level matching. Moreover, CHoG descriptors demonstrate such gains while being comparable with MPEG-7 image signatures in bit-rate.

This paper describes a video coding technology proposal submitted by Qualcomm in response to a joint call for proposals (CfP) issued by ITU-T SG16 Q.6 (VCEG) and ISO/IEC JTC1/SC29/WG11 (MPEG) in January 2010. The proposed video codec follows a hybrid coding approach based on temporal prediction, followed by transform, quantization, and entropy coding of the residual. Some of its key features are extended block sizes (up to 64$\,\times\,$64), single pass switched interpolation filters with offsets, mode-dependent directional transforms for intra-coding, luma and chroma high precision filtering, geometric motion partitions, adaptive motion vector resolution and efficient 16-point transforms. It also incorporates internal bit-depth increase and modified quadtree-based adaptive loop filtering. Simulation results are presented to demonstrate the high compression efficiency achieved by the proposed video codec at the expense of moderate increase in encoding and decoding complexity compared to the advanced video coding standard (AVC/H.264). For the random access and low delay configurations, it achieved average bit rate reductions of 30.9% and 33.0% for equivalent peak signal-to-noise ratio, respectively, compared to the corresponding AVC anchors. The proposed codec scored highly in both subjective evaluations and objective metrics and was among the best-performing CfP proposals.

A variable-to-fixed length encoder partitions the source string into variable-length phrases that belong to a given and fixed dictionary. Tunstall, and independently Khodak, designed variable-to-fixed length codes for memoryless sources that are optimal under certain constraints. In this paper, we study the Tunstall and Khodak codes using variety of techniques ranging from stopping times for sums of independent random variables to Tauberian theorems and Mellin transform. After proposing an algebraic characterization of the Tunstall and Khodak codes, we present new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates.

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.

In this paper, an efficient algorithm for implementing MDCT/IMDCT of lengths N = 5 ldr 2m(m ges 2) is presented. Transforms for such lengths are of interest for speech and audio coding applications, such as recently issued and/or emerging standards G.729.1, G.EV-VBR, and EVRC-WB. In our design we utilize a mapping of MDCT of size N into JV/2-point DCT-IV and DCT-II with isolated pre- multiplications, which are subsequently moved in the windowing stage. We show that such a modified window is piece-wise symmetric, and can be stored using N/2 words. In our algorithm we also use an efficient factorization of 5- point DCT-II which requires only 4 multiplications by irrational factors. We compare our proposed algorithm with several alternative implementations and show that our design offers practically appreciable reduction in complexity and memory usage.

We describe a general technique for improving the precision of fixed-point implementations of signal processing algorithms (such as filters, transforms, etc.) relying on the use of "common factors". Such factors are applied to groups of real constants in the algorithms (e.g. filter coefficients), turning them into quantities that can be more accurately approximated by dyadic rational numbers. We show that the problem of optimal design of such approximations is related to the classic Diophantine approximation problem, and explain how it can be solved and used for improving practical designs.

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

This paper presents an efficient algorithm for computing the Inverse discrete cosine transform (IDCT) for image and video coding applications. This algorithm was submitted in response to MPEG's call for proposals for ISO/IEC 23002-2 (fixed-point 8times8 IDCT and DCT) standard, and was subsequently adopted in the Working Draft 1 of this standard. Our proposed algorithm is a multiplication-free implementation. It is based on a modification of Arai, Agui, and Nakajima's (AAN) factorization, and requires only 42 addition and 16 shift operations per scaled ID transform. Each register in our scaled ID transform requires at most 22 bits. This implementation complies with the MPEG IDCT precision specification ISO/IEC 23002-1.

We describe an efficient algorithm for computing the inverse discrete cosine transform (IDCT) for image and video coding applications. This algorithm was derived by converting an 8-point IDCT factorization of C. Loeffler, A. Ligtenberg, and G. Moschytz into a scaled form, leaving 8 multiplications by irrational factors inside the transform. The key advantage of such a modification is that these factors can be sufficiently accurately represented by 8-bit integer values, resulting in a very small dynamic range of variables inside the transform. Our scaled ID transform can be implemented either by using 8 multiplications, 26 additions and 6 shifts or (in a multiplier-less fashion) by using only 44 additions and 18 shifts. This implementation fully complies with the new MPEG IDCT precision standard (ISO/IEC 23002-1, replacement of former IEEE 1180 specification), and shows remarkably low drift in decoding of H.263, MPEG-2, and MPEG-4 bitstreams produced by reference software encoders (employing 64-bit floating-point DCT and IDCT implementations).

We study the Tunstall code using the machinery from the analysis of algorithms literature. In particular, we propose an algebraic characterization of the Tunstall code which, together with tools like the Mellin transform and the Tauberian theorems, leads to new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates

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.

We describe two alternative schemes for encoding of the prediction residual adopted in the MPEG-4 ALS (audio lossless coding) standard for lossless audio coding. We explain choices of algorithms used in their design and provide both analytical and experimental analysis of their performance.

This paper presents the second-order properties of minimum redundancy block codes. A block Huffman code constructed for a binary memoryless source with probabilities is considered. The result proves that the variance of its redundancy distribution of block Shannon and Huffman code is distributed very uniformly between its codewords.

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.

We provide an overview of an architecture of today's Internet streaming media delivery networks and describe various problems that such systems pose with regard to video coding. We demonstrate that based on the distribution model (live or on-demand), the type of the network delivery mechanism (unicast versus multicast), and optimization criteria associated with particular segments of the network (e.g., minimization of distortion for a given connection rate, minimization of traffic in the dedicated delivery network, etc.), it is possible to identify several models of communication that may require different treatment from both source and channel coding perspectives. We explain how some of these problems can be addressed using a conventional framework of temporal motion-compensated, transform-based video compression algorithm, supported by appropriate channel-adaptation mechanisms in client and server components of a streaming media system. Most of these techniques have already been implemented in RealNetworks(R) RealSystem(R) 8 and its RealVideo(R) 8 codec, which we use throughout the paper to illustrate our results.

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.