In this paper, we compress convolutional neural network (CNN) weights post-training via transform quantization. Previous CNN quantization techniques tend to ignore the joint statistics of weights and activations, producing sub-optimal CNN performance at a given quantization bit-rate, or consider their joint statistics during training only and do not facilitate efficient compression of already trained CNN models. We optimally transform (decorrelate) and quantize the weights post-training using a rate-distortion framework to improve compression at any given quantization bit-rate. Transform quantization unifies quantization and dimensionality reduction (decorrelation) techniques in a single framework to facilitate low bit-rate compression of CNNs and efficient inference in the transform domain. We first introduce a theory of rate and distortion for CNN quantization, and pose optimum quantization as a rate-distortion optimization problem. We then show that this problem can be solved using optimal bit-depth allocation following decorrelation by the optimal End-to-end Learned Transform (ELT) we derive in this paper. Experiments demonstrate that transform quantization advances the state of the art in CNN compression in both retrained and non-retrained quantization scenarios. In particular, we find that transform quantization with retraining is able to compress CNN models such as AlexNet, ResNet and DenseNet to very low bit-rates (1-2 bits).

In this paper, we present a coding framework for deep convolutional neural network compression. Our approach utilizes the classical coding theories and formulates the compression of deep convolutional neural networks as a rate-distortion optimization problem. We incorporate three coding ingredients in the coding framework, including bit allocation, dead zone quantization, and Tunstall coding, to improve the rate-distortion frontier without noticeable system-level overhead introduced. Experimental results show that our approach achieves state-of-the-art results on various deep convolutional neural networks and obtains considerable speedup on two deep learning accelerators. Specifically, our approach achieves 20× compression ratio on ResNet-18, ResNet-34, and ResNet-50, and 10× compression ratio on the compact already model MobileNet-v2, without hurting the accuracy. We then examine the system level impact of our approach when deploying the compressed models to hardware platforms. Hardware simulation results show that our approach obtains up to 4.3× and 2.8× inference speedup on state-of-the-art deep learning accelerators TPU and Eyeriss, respectively.

We propose a joint albedo-normal approach to non-line-of-sight (NLOS) surface reconstruction using the directional light-cone transform (D-LCT). While current NLOS imaging methods reconstruct either the albedo or surface normals of the hidden scene, the two quantities provide complementary information of the scene, so an efficient method to estimate both simultaneously is desirable. We formulate the recovery of the two quantities as a vector deconvolution problem, and solve it via Cholesky-Wiener decomposition. We demonstrate that surfaces fitted non-parametrically using our recovered normals are more accurate than those produced with NLOS surface reconstruction methods recently proposed, and are 1,000 times faster to compute than using inverse rendering.

Recently, many fast implementations of the bilateral and the nonlocal filters were proposed based on lattice and vector quantization, e.g. clustering, in higher dimensions. However, these approaches can still be inefficient owing to the complexities in the resampling process or in filtering the high-dimensional resampled signal. In contrast, simply scalar resampling the high-dimensional signal after decorrelation presents the opportunity to filter signals using multi-rate signal processing techniques. Cis work proposes the Gaussian lifting framework for efficient and accurate bilateral and nonlocal means filtering, appealing to the similarities between separable wavelet transforms and Gaussian pyramids. Accurately implementing the filter is important not only for image processing applications, but also for a number of recently proposed bilateralregularized inverse problems, where the accuracy of the solutions depends ultimately on an accurate filter implementation. We show that our Gaussian lifting approach filters images more accurately and efficiently across many filter scales. Adaptive lifting schemes for bilateral and nonlocal means filtering are also explored.

We propose the fast optical flow extractor, a filtering method that recovers artifact-free optical flow fields from HEVCcompressed video. To extract accurate optical flow fields, we form a regularized optimization problem that considers the smoothness of the solution and the pixelwise confidence weights of an artifactridden HEVC motion field. Solving such an optimization problem is slow, so we first convert the problem into a confidence-weighted filtering task. By leveraging the already-available HEVC motion parameters, we achieve a 100-fold speed-up in the running times compared to similar methods, while producing subpixel-accurate flow estimates. Je fast optical flow extractor is useful when video frames are already available in coded formats. Our method is not specific to a coder, and works with motion fields from video coders such as H.264/AVC and HEVC.

We consider the task of indoor localization in large-scale environments using visual search on a database of geo-tagged panoramas. In this work we propose an efficient way to represent the database so as to maximize the search accuracy while minimizing the amount of computation required per query. The success of our method is due to a combination of (i) a hierarchical indexing method based on panorama image region information, and (ii) image descriptors aggregated from multiple views sampled finely over the panorama using generalized max pooling (GMP). Experiments on a large indoor dataset show that the complexity is reduced compared to common state-of-the-art retrieval methods such as FLANN (Fast Library for Approximate Nearest Neighbors): our scheme is more than twice as fast as an index based on FLANN while maintaining a similar retrieval performance.

Feature detectors and descriptors are key low-level vision tools that many higher-level tasks build on. Unfortunately these fail in the presence of challenging light transport effects including partial occlusion, low contrast, and reflective or refractive surfaces. Building on spatio-angular imaging modalities offered by emerging light field cameras, we introduce a new and computationally efficient 4D light field feature detector and descriptor: LiFF. LiFF is scale invariant and utilizes the full 4D light field to detect features that are robust to changes in perspective. This is particularly useful for structure from motion (SfM) and other tasks that match features across viewpoints of a scene. We demonstrate significantly improved 3D reconstructions via SfM when using LiFF instead of the leading 2D or 4D features, and show that LiFF runs an order of magnitude faster than the leading 4D approach. Finally, LiFF inherently estimates depth for each feature, opening a path for future research in light field-based SfM.

We propose a new, filtering approach for solving a large number of regularized inverse problems commonly found in computer vision. Traditionally, such problems are solved by finding the solution to the system of equations that expresses the first-order optimality conditions of the problem. This can be slow if the system of equations is dense due to the use of nonlocal regularization, necessitating iterative solvers such as successive over-relaxation or conjugate gradients. In this paper, we show that similar solutions can be obtained more easily via filtering, obviating the need to solve a potentially dense system of equations using slow iterative methods. Our filtered solutions are very similar to the true ones, but often up to 10 times faster to compute.

For most real-time implementations of deep artificial neural networks, both weights and intermediate layer activations have to be stored and loaded for processing. Compression of both is often advisable to mitigate the memory bottleneck. In this paper, we propose a bit allocation framework for compressing the weights and activations of deep neural networks. The differentiability of input-output relationships for all network layers allows us to relate the neural network output accuracy to the bit-rate of quantized weights and layer activations. We formulate a Lagrangian optimization framework that finds the optimum joint bit allocation among all intermediate activation layers and weights. Our method obtains excellent results on two deep neural networks, VGG-16 and ResNet-50. Without requiring re-training, it outperforms other state-of-the-art neural network compression methods.

The occurrence of missing regions in output images is a critical issue when rendering a scene from novel vantage points using depth-based view synthesis. These regions typically have to be filled using inpainting algorithms, which are slow and might yield unconvincing results. Understanding the likelihood of the occurrence of these missing regions can help us design better, application-specific data representations and camera systems by knowing which vantage points should be captured and stored to minimize disocclusion holes in the synthesized novel views. In this paper, we propose a statistical model that predicts the likelihood of missing data in synthesized images as a function of the viewpoint translation. Scene-dependent model parameters are efficiently estimated using simple shift and scaling transformations on the source depth images without needing view synthesis.

Retrieving videos from large repositories using image queries is important for many applications, such as brand monitoring or content linking. We introduce a new retrieval architecture, in which the image query can be compared directly with database videos - significantly improving retrieval scalability compared with a baseline system that searches the database on a video frame level. Matching an image to a video is an inherently asymmetric problem. We propose an asymmetric comparison technique for Fisher vectors and systematically explore query or database items with varying amounts of clutter, showing the benefits of the proposed technique. We then propose novel video descriptors that can be compared directly with image descriptors. We start by constructing Fisher vectors for video segments, by exploring different aggregation techniques. For a database of lecture videos, such methods obtain a two orders of magnitude compression gain with respect to a frame-based scheme, with no loss in retrieval accuracy. Then, we consider the design of video descriptors, which combine Fisher embedding with hashing techniques, in a flexible framework based on Bloom filters. Large-scale experiments using three datasets show that this technique enables faster and more memory-efficient retrieval, compared with a frame-based method, with similar accuracy. The proposed techniques are further compared against pre-trained convolutional neural network features, outperforming them on three datasets by a substantial margin.

We formulate the task of 3D object retrieval as a visual search problem where a database containing videos of objects captured manually from different viewpoints is queried using a single image. We propose to aggregate visual information of similar views and use the Fisher vector (FV) framework to compactly represent a database of objects. Large-scale experiments on an existing video dataset that we complemented with image queries, shows that our aggregation schemes significantly outperform standard retrieval techniques. When representing our database with only 4 FVs per object, our approach performs with a mean average precision (mAP) of 73.0% on our dataset while the baseline (no aggregation) only reaches a mAP of 43.8%. It can also reach a 72.0% mAP level with a 10× smaller database than the baseline.

Motion parallax is an important cue for depth perception. Rendering it accurately can lead to a more natural and immersive virtual reality (VR) experience. We introduce Stacked Omnistereo, a novel data representation that can render immersive video with six degrees of freedom (DoF). We compare the proposed representation against other depth-based and image-based motion parallax techniques using natural as well as synthetic scenes. We show that the proposed representation can synthesize plausible, view-dependent specular highlights, is compact compared to light fields, and outperforms state-of-the-art VR representations by up to 3 dB when evaluated with 6 DoF head motion.

This paper presents a mathematical analysis of the impact of key-point detection errors on the similarity of local image descriptors that are based on histogram of gradients. First, we derive a closed-form expression for the Lp distance between two descriptors, for general translation, scale and orientation detection errors. Second, we introduce a detailed analysis for the special case where translation errors dominate, using the L2 distance. We show that the individual components which form the squared L2 distance can be approximated using Gamma distributions whose parameters are computed in closed-form by our model. We obtain approximate closed-form expressions for the expected squared L2 distances when translation errors are fixed or uniformly distributed. Finally, these models are validated using image patches extracted from two standard image retrieval datasets, by comparing the predicted distributions to the ground-truth.

Cinematic virtual reality (VR) aims to provide immersive visual experiences of real-world scenes on head-mounted displays. Current cinematic VR systems support stereo cues, but not focus cues that are important for depth perception and comfortable viewing. We propose a new content representation, depth augmented stereo panorama (DASP), which permits generating light fields (LFs) across the observer's pupils, achieving an order of magnitude reduction in data requirements compared to the existing techniques. The LF generation and refocusing capabilities of DASP are evaluated for both, computer-generated and real scenes. Results indicate that DASP can successfully create stereo as well as support focus cues.

Cinematic virtual reality (VR) aims to provide immersive visual experiences of real-world scenes on head-mounted displays. Current cinematic VR systems employ omnidirectional stereo videos from a fixed position, and therefore do not address head-motion parallax, which is an important cue for depth perception. We propose a new 3D video representation, referred to as depth augmented stereo panorama (DASP), to address this issue. DASP is developed considering data capture, postproduction, streaming, and rendering stages of the VR pipeline. The capabilities of this representation are evaluated by comparing the generated viewports with those from known 3D models. Results indicate that DASP can successfully create stereo and induce head-motion parallax in a predefined operating range.

Compact descriptors for visual search (CDVS) is a recently completed standard from the ISO/IEC moving pictures experts group (MPEG). The primary goal of this standard is to provide a standardized bitstream syntax to enable interoperability in the context of image retrieval applications. Over the course of the standardization process, remarkable improvements were achieved in reducing the size of image feature data and in reducing the computation and memory footprint in the feature extraction process. This paper provides an overview of the technical features of the MPEG-CDVS standard and summarizes its evolution.

Visual text information is a descriptive part of many images that can be used to perform mobile visual search (MVS) with particularly small queries. In this paper, we propose a system that uses word patch descriptors for retrieving images containing visual text. A random sampling method is used to find duplicate word patches in the database and reduce the database size. The system achieves comparable retrieval performance to state-of-the-art image feature-based systems for images of book covers, and performs better than state-of-the-art text-based retrieval systems for images of book pages. Using visual text to provide distinctive features, our system achieves more than 10-to-1 query size reduction for images of book covers and more than 16-to-1 query size reduction for images of book pages.

We address the challenge of using image queries to retrieve video clips from a large database. Using binarized Fisher Vectors as global signatures, we present three novel contributions. First, an asymmetric comparison scheme for binarized Fisher Vectors is shown to boost retrieval performance by 0.27 mean Average Precision, exploiting the fact that query images contain much less clutter than database videos. Second, aggregation of frame-based local features over shots is shown to achieve retrieval performance comparable to aggregation of those local features over single frames, while reducing retrieval latency and memory requirements by more than 3X. Several shot aggregation strategies are compared and results indicate that most perform equally well. Third, aggregation over scenes, in combination with shot signatures, is shown to achieve one order of magnitude faster retrieval at comparable performance. Scene aggregation also outperforms the recently proposed aggregation in random groups.

Omnidirectional videos of real world environments viewed on head-mounted displays with real-time head motion tracking can offer immersive visual experiences. For live streaming applications, compression is critical to reduce the bitrate. Omnidirectional videos, which are spherical in nature, are mapped onto one or more planes before encoding to interface with modern video coding standards. In this paper, we consider the problem of evaluating the coding efficiency in the context of viewing with a head-mounted display. We extract viewport based head motion trajectories, and compare the original and coded videos on the viewport. With this approach, we compare different sphere-to-plane mappings. We show that the average viewport quality can be approximated by a weighted spherical PSNR.

Reproducible research in the area of visual search depends on the availability of large annotated datasets. In this paper, we address the problem of querying a video database by images that might share some contents with one or more video clips. We present a new large dataset, called Stanford I2V. We have collected more than 3; 800 hours of newscast videos and annotated more than 200 ground-truth queries. In the following, the dataset is described in detail, the collection methodology is outlined and retrieval performance for a benchmark algorithm is presented. These results may serve as a baseline for future research and provide an example of the intended use of the Stanford I2V dataset. The dataset can be downloaded at http://purl.stanford.edu/zx935qw7203.

Mobile visual search systems typically compare a query image against a database of annotated images for accurate object recognition. On-server database matching can search a large database hosted in the cloud, but the query latency could suffer with slow network transmissions or server congestion . On-device database matching can ensure fast recognition responses regardless of network or server conditions , but a small amount of memory on the mobile device can severely limit the number of images that can be stored in an on- device database. This paper presents a new hybrid system that combines the advantages of on-device and on-server database matching. At the core of this system, we first develop a compact and discriminative global signature to characterize each image. Our global signature uses an optimized local feature count that is derived from a statistical analysis of the retrieval performance . We additionally create two extensions that exploit color information within images and relationships between similar database images to improve retrieval accuracy. Then, we propose methods for efficient interframe coding of a sequence of global signatures which are extracted from the viewfinder frames on the mobile device. A low bitrate stream of global signatures can be sent to the server at an uplink bitrate of less than 2 kbps to broaden the search range of the current query and to update the on-device database to help future queries.

MPEG is currently developing a standard titled Compact Descriptors for Visual Search (CDVS) for descriptor extraction and compression. In this work, we report comprehensive patch-level experiments for a direct comparison of low bitrate descriptors for visual search. For evaluating different compression schemes, we propose a dataset of matching pairs of image patches from the MPEG-CDVS image-level data sets. We propose a greedy rate allocation scheme for distributing bits across different spatialbins of the SIFT descriptor. We study a scheme based on Entropy Constrained Vector Quantization and greedy rate allocation, which performs close to the performancebound for any compression scheme. Finally, we present extensive feature-level Receiver Operating Characteristic (ROC) comparisons for different compression schemes (VectorQuantization, Transform Coding, Lattice Coding) proposed during the MPEG-CDVS standardization process.

For mobile augmented reality, an image captured by a mobile device's camera is often compared against a database hosted on a remote server to recognize objects in the image. It is critically important that the amount of data transmitted over the network is as small as possible to reduce the system latency. A low bitrate global signature for still images has been previously shown to achieve high-accuracy image retrieval. In this paper, we develop new methods for interframe coding of a continuous stream of global signatures that can reduce the bitrate by nearly two orders of magnitude compared to independent coding of these global signatures, while achieving the same or better image retrieval accuracy. The global signatures are constructed in an embedded data structure that offers rate scalability. The usage of these new coding methods and the embedded data structure allows the streaming of high-quality global signatures at a bitrate that is less than 2 kbps. Furthermore, a statistical analysis of the retrieval and coding performance is performed to understand the trade off between bitrate and image retrieval accuracy and explain why interframe coding of global signatures substantially outperforms independent coding.

We study the challenges of image-based retrieval when the database consists of videos. This variation of visual search is important for a broad range of applications that require indexing video databases based on their visual contents. We present new solutions to reduce storage requirements, while at the same time improving video search quality. The video database is preprocessed to find different appearances of the same visual elements, and build robust descriptors. Compression algorithms are developed to reduce system's storage requirements. We introduce a dataset of CNN broadcasts and queries that include photos taken with mobile phones and images of objects. Our experiments include pairwise matching and retrieval scenarios. We demonstrate one order of magnitude storage reduction and search quality improvements of up to 12% in mean average precision, compared to a baseline system that does not make use of our techniques.

Despite being a highly distinctive feature, the potential of text in images for mobile visual search has been largely neglected. Our research reported in this paper strives to improve mobile visual search by incorporating algorithms and compact representations tailored to visual text. We develop a new word patch descriptor, called Word Histogram of Oriented Gradients (Word-HOGs). The descriptor is based on gradient orientation histograms and can be compressed to a very small size using context-based arithmetic coding with lattice quantization. Because of its special structure, we can build image features from the descriptor and use these features for large-scale word patch matching. We show that the Word-HOG descriptor has a word patch matching performance that is better or comparable to the state-of-the-art approaches while being more efficient in feature counts, and it can be highly compressed with negligible loss in retrieval performance.

We demonstrate a novel multimedia system that continuously indexes videos and enables real-time search using images, with a broad range of potential applications. Television shows are recorded and indexed continuously, and iconic images from recent events are discovered automatically. Users can query an uploaded image or an image in the web. When a result is served, the user can play the video clip from the beginning or from the point in time where the retrieved image was found.

We propose Multi-modal Language Models (MLMs), which adapt latent variable techniques for document analysis to exploring co-occurrence relationships in multi-modal data. In this paper, we focus on the application of MLMs to indexing text from slides and speech in lecture videos, and subsequently employ a multi-modal probabilistic ranking function for lecture video retrieval. The MLM achieves highly competitive results against well established retrieval methods such as the Vector Space Model and Probabilistic Latent Semantic Analysis. When noise is present in the data, retrieval performance with MLMs is shown to improve with the quality of the spoken text extracted from the video.

This special issue is concerned with the latest developments in state-of-the-art adaptive media streaming technologies and applications.

This paper introduces the new idea of describing people using first names. We show that describing people in terms of similarity to a vector of possible first names is a powerful representation of facial appearance that can be used for a number of important applications, such as naming never-seen faces and building facial attribute classifiers. We build models for 100 common first names used in the US and for each pair, construct a pairwise first-name classifier. These classifiers are built using training images downloaded from the internet, with no additional user interaction. This gives our approach important advantages in building practical systems that do not require additional human intervention for data labeling. The classification scores from each pairwise name classifier can be used as a set of facial attributes to describe facial appearance. We show several surprising results. Our name attributes predict the correct first names of test faces at rates far greater than chance. The name attributes are applied to gender recognition and to age classification, outperforming state-of-the-art methods with all training images automatically gathered from the internet. We also demonstrate the powerful use of our name attributes for associating faces in images with names from caption, and the important application of unconstrained face verification.

Streaming mobile augmented reality applications require both real-time recognition and tracking of objects of interest in a video sequence. Typically, local features are calculated from the gradients of a canonical patch around a keypoint in individual video frames. In this paper, we propose a temporally coherent keypoint detector and design efficient interframe predictive coding techniques for canonical patches, feature descriptors, and keypoint locations. In the proposed system, we strive to transmit each patch or its equivalent feature descriptor with as few bits as possible by modifying a previously transmitted patch or descriptor. Our solution enables server-based mobile augmented reality where a continuous stream of salient information, sufficient for image-based retrieval, and object localization, is sent at a bit-rate that is practical for today's wireless links and less than one-tenth of the bit-rate needed to stream the compressed video to the server.

This paper introduces a new idea in describing people using their first names, i.e., the name assigned at birth. We show that describing people in terms of similarity to a vector of possible first names is a powerful description of facial appearance that can be used for face naming and building facial attribute classifiers. We build models for 100 common first names used in the United States and for each pair, construct a pair wise first-name classifier. These classifiers are built using training images downloaded from the Internet, with no additional user interaction. This gives our approach important advantages in building practical systems that do not require additional human intervention for labeling. We use the scores from each pair wise name classifier as a set of facial attributes. We show several surprising results. Our name attributes predict the correct first names of test faces at rates far greater than chance. The name attributes are applied to gender recognition and to age classification, outperforming state-of-the-art methods with all training images automatically gathered from the Internet.

We demonstrate EigenNews, a personalized television news system. Upon visiting the EigenNews website, a user is shown a variety of news videos which have been automatically selected based on her individual preferences. These videos are extracted from 16 continually recorded television programs using a multimodal segmentation algorithm. Relevant metadata for each video are generated by linking videos to online news articles. Selected news videos can be watched in three different layouts and on various devices.

We present the radial gradient transform (RGT) and a fast approximation, the approximate RGT (ARGT). We analyze the effects of the approximation on gradient quantization and histogramming. The ARGT is incorporated into the rotation-invariant fast feature (RIFF) algorithm. We demonstrate that, using the ARGT, RIFF extracts features 16× faster than SURF while achieving a similar performance for image matching and retrieval.

Local features are widely used for content-based image retrieval and object recognition. Most feature descriptors are calculated from the gradients of a canonical patch around repeatable keypoints in the image. In this paper, we propose a technique for designing quantization matrices that reduce the mean squared error distortion of the gradient derived from DCT-encoded canonical patches. Experimental results demonstrate that our proposed patch encoder greatly outperforms a JPEG encoder at the same encoding complexity. Moreover, our quantization matrices achieve lower gradient distortion and larger number of feature matches at the same bit-rate.

Local features are widely used for content-based image retrieval and augmented reality applications. Typically, feature descriptors are calculated from the gradients of a canonical patch around a repeatable key point in the image. In previous work, we showed that one can alternatively transmit the compressed canonical patch and perform descriptor computation at the receiving end with comparable performance. In this paper, we propose a temporally coherent key point detector in order to allow efficient interframe coding of canonical patches. In inter-patch compression, one strives to transmit each patch with as few bits as possible by simply modifying a previously transmitted patch. This enables server-based mobile augmented reality where a continuous stream of salient information, sufficient for the image-based retrieval, can be sent over a wireless link at the smallest possible bit-rate. Experimental results show that our technique achieves a similar image matching performance at 1/10 of the bit-rate when compared to detecting key points independently frame-by-frame.

We present a new class of visual text features that are based on text in camera phone images. A robust text detection algorithm locates individual text lines and feeds them to a recognition engine. From the recognized characters, we generate the visual text features in a way that resembles image features. We calculate their location, scale, orientation, and a descriptor that describes the character and word information. We apply visual text features to image matching. To disambiguate false matches, we developed a word-distance matching method. Our experiments with image that contain text show that the new visual text feature based image matching pipeline performs on par or better than a conventional image feature based pipeline while requiring less than 10 bits per feature. This is 4.5× smaller than state-of-the-art visual feature descriptors.

Internet protocol television (IPTV) systems employ IP multicast to deliver television programs to end-users. To provide reliable IPTV services over the error-prone digital subscriber line (DSL) access networks, a combination of multicast forward error correction and unicast retransmissions is employed to mitigate the impulse noise in DSL links. In current systems, the error control function is provided by special retransmission servers. In this paper, we propose an alternative distributed solution where the burden of packet loss repair is partially shifted to end-user set-top boxes. Using a peer-assisted repair (PAR) protocol, we demonstrate how packet repairs can be delivered in a timely, reliable, and decentralized manner using the combination of server-peer coordination and redundant repairs. We also show that this distributed protocol can be seamlessly integrated with an application-layer source-aware error protection mechanism called forward and retransmitted systematic lossy error protection (SLEP/SLEPr). Analysis and simulations show that this joint PAR-SLEP/SLEPr framework not only efficiently improves the resistance to the impulse noise but also effectively mitigates the bottleneck experienced by the retransmission servers, thus greatly enhancing system scalability.

We present a novel approach using distributed source coding for image authentication. The key idea is to provide a Slepian-Wolf encoded quantized image projection as authentication data. This version can be correctly decoded with the help of an authentic image as side information. Distributed source coding provides the desired robustness against legitimate variations while detecting illegitimate modification. The decoder incorporating expectation maximization algorithms can authenticate images which have undergone contrast, brightness, and affine warping adjustments. Our authentication system also offers tampering localization by using the sum-product algorithm.

We consider distributed source coding in the presence of hidden variables that parameterize the statistical dependence among sources. We derive the Slepian-Wolf bound and devise coding algorithms for a block-candidate model of this problem. The encoder sends, in addition to syndrome bits, a portion of the source to the decoder uncoded as doping bits. The decoder uses the sum-product algorithm to simultaneously recover the source symbols and the hidden statistical dependence variables. We also develop novel techniques based on density evolution (DE) to analyze the coding algorithms. We experimentally confirm that our DE analysis closely approximates practical performance. This result allows us to efficiently optimize parameters of the algorithms. In particular, we show that the system performs close to the Slepian-Wolf bound when an appropriate doping rate is selected. We then apply our coding and analysis techniques to a reduced-reference video quality monitoring system and show a bit rate saving of about 75% compared with fixed-length coding.

With recent advances in mobile computing, the demand for visual localization or landmark identification on mobile devices is gaining interest. We advance the state of the art in this area by fusing two popular representations of street-level image data - facade-aligned and viewpoint-aligned - and show that they contain complementary information that can be exploited to significantly improve the recall rates on the city scale. We also improve feature detection in low contrast parts of the street-level data, and discuss how to incorporate priors on a user's position (e.g. given by noisy GPS readings or network cells), which previous approaches often ignore. Finally, and maybe most importantly, we present our results according to a carefully designed, repeatable evaluation scheme and make publicly available a set of 1.7 million images with ground truth labels, geotags, and calibration data, as well as a difficult set of cell phone query images. We provide these resources as a benchmark to facilitate further research in the area.

Detecting text in natural images is an important prerequisite. In this paper, we propose a novel text detection algorithm, which employs edge-enhanced Maximally Stable Extremal Regions as basic letter candidates. These candidates are then filtered using geometric and stroke width information to exclude non-text objects. Letters are paired to identify text lines, which are subsequently separated into words. We evaluate our system using the ICDAR competition dataset and our mobile document database. The experimental results demonstrate the excellent performance of the proposed method.

Multiview video coding systems are characterized by their high encoding complexity. In this paper, we propose to reduce the encoding complexity by omitting frames at the encoder in a pattern that keeps the ability to reconstruct an interpolated version of each omitted frame, by motion-compensated and inter-view interpolation. Since our goal is maintaining good visual quality, we propose a method to estimate the quality of the interpolated frames at the decoder by transmitting a small amount of error control information in lieu of an omitted frame. This information is obtained from a projection of the frame on a suitable low-dimensional basis. The projection coefficients can be compressed by conventional techniques or, more efficiently, by Slepian-Wolf coding. Based on the quality estimate, the decoder can adaptively detect the interpolation technique that results in better visual quality. Moreover, it can suppress occasional frames for which interpolation yields noticeable artifacts. Experimental results demonstrate that our approach eliminates most interpolation artifacts and achieves much better visual quality at a very small increase in bit-rate.

The temporal synchronization of presentation slides and lecture videos enables us to enhance the user experience of online lecture viewing systems. In this work, we present a novel approach to robustly and reliably detect and recognize slide changes, which is based on bit rate sequences. By exploiting readily available information, the computational complexity of the approach is very low. In contrast to prior work, no requirements on the amount or type of texture, motion of foreground objects, or text size on the slide are imposed. Experimental results show the ability to detect even minor slide changes and demonstrate the robustness against occlusions, foreground motion, and camera motion.

We present a novel mobile printed document retrieval system that utilizes both text and low bit-rate features. On the client phone, text are detected using an algorithm based on edge-enhanced Maximally Stable Extremal Regions. The title text image patch is rectified using a gradient based algorithm and recognized using Optical Character Recognition. Low bit-rate image features are extracted from the query image. Both text and compressed features are sent to a server. On the server, the title text is used for on-line search and the features are used for image-based comparison. The proposed system is capable of web-scale document retrieval using title text without the need of constructing a document image database. Using features for image-based comparison, we can reliably match retrieved documents to the query document. Last, by using text and low bit-rate features, we can reduce the transmitted query size significantly.

Retrieving information about books on a bookshelf by snapping a photo of book spines with a mobile device is very useful for bookstores, libraries, offices, and homes. In this paper, we develop a new mobile augmented reality system for book spine recognition. Our system achieves very low recognition delays, around 1 second, to support real-time augmentation on a mobile device's viewfinder. We infer user interest by analyzing the motion of objects seen in the viewfinder. Our system initiates a query during each low-motion interval. This selection mechanism eliminates the need to press a but ton and avoids using degraded motion-blurred query frames during high-motion intervals. The viewfinder is augmented with a book's identity, prices from different vendors, average user rating, location within the enclosing bookshelf, and a digital compass marker. We present a new tiled search strategy for finding the location in the bookshelf with improved accuracy in half the time as in a previous state-of-the-art system. Our AR system has been implemented on an Android smartphone.

The ClassX open source project is a free experimental interactive video streaming platform designed for educators, researchers and software developers. With minimal infra-structure set-up, ClassX offers educational communities a cost-effective solution for online lecture delivery. Our goal is to encourage contributions from other researchers, developers and educators in building an open, cost-effective and state-of-the-art online education video viewing system for the general public.

Small screen sizes, limited bandwidth, and low computational power often prohibit streaming of high-resolution videos to mobile devices over a wireless network. Recent advances in interactive region-of-interest (IRoI) video streaming technology enable users to interactively control pan/tilt/ zoom, while provide bit-rate and complexity savings. One recent application of IRoI video streaming is ClassX developed at Stanford University. It offers an open-source experimental platform for interactive online lecture streaming. In this technical demonstration, we present ClassX Mobile, which extends the current ClassX system and delivers high-quality interactive video to smartphones and tablets with multi-touch screens.

Despite the successful use of local image features for large-scale object recognition, they are not effective in recognizing book spines on bookshelves. This is because some book spines contain only text components that do not yield distinguishing image features. To overcome this issue, we develop a new approach that combines a text-based spine recognition pipeline with an image feature-based spine recognition pipeline. The text within the book spine image is recognized and used as keywords to search a book spine text database. The image features of the book spine image are searched through a book spine image database. The search results of the two approaches are then carefully combined to form the final result. We implement the proposed hybrid book recognition pipeline used in a book inventory management system, and conduct extensive experiments to evaluate its performance. The experimental results show that while text-based or image feature-based systems only achieve a recall of 72%, the proposed hybrid system achieves a recall of ~91%.

Reduced reference video quality assessment techniques provide a practical and convenient way of evaluating the quality of a processed video. In this paper, we propose a method to efficiently compress standardized VQM (Video Quality Model) [1] features to bit-rates that are small relative to the transmitted video. This is achieved through two stages of compression. In the first stage, we remove the redundancy in the features by only transmitting the necessary original video features at the lowest acceptable resolution for the calculation of the final VQM value. The second stage involves using the features of the processed video at the receiver as side-information for efficient entropy coding and reconstruction of the original video features. Experimental results demonstrate that our approach achieves high compression ratios of more than 30× with small error in the final VQM values.

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.

High-spatial-resolution videos offer the possibility of viewing an arbitrary region-of-interest (RoI) interactively. Zoom functionality enables watching high-resolution content even on displays of lower spatial resolution. If arbitrary regions corresponding to arbitrary zoom factors can be served to the user, the transmission and/or decoding of the entire high-spatial-resolution video can be avoided. Moreover, if the video content can be encoded such that arbitrary RoIs corresponding to different zoom factors can be simply extracted from the compressed bitstream, we can avoid dedicated video encoding for each user. We propose such a video coding scheme that is vital in allowing the system to scale to large numbers of remote users as well as to encode and store the content for subsequent repeated playback. Apart from generating a multi-resolution representation, our coding scheme uses P slices from H.264/AVC. We study the tradeoff in the choice of slice size. A larger slice size enables higher coding efficiency for representing the entire scene but increases the number of pixels that have to be transmitted. The optimal slice size achieves the best tradeoff and minimizes the expected transmission bitrate. Experimental results confirm the optimality of our predicted slice size for various test cases. Furthermore, we propose an improvement based on background extraction and long-term memory motion-compensated prediction. Experiments indicate up to 85% bitrate reduction while retaining efficient random access capability.

A unified optimization framework for rate allocation among multiple video multicast sessions sharing a wireless network is presented. Our framework applies to delivery of both scalable and non-scalable video streams. In both cases, the optimization objective is to minimize the total video distortion of all peers without incurring excessive network utilization. Our system model explicitly accounts for heterogeneity in wireless link capacities, traffic contention among neighboring links, as well as different video rate-distortion (RD) characteristics. The proposed distributed rate allocation scheme leverages cross-layer information exchange between the media access control and application layers to achieve fast convergence at the optimal, media-aware allocation. Performance of the proposed media-aware rate allocation protocol is compared against a heuristic scheme based on TCP-friendly rate control (TFRC). In network simulations of standard-definition video streaming over single or multiple multicast trees, the proposed scheme consistently achieves higher overall video quality than the TFRC-based heuristics. When delivering scalable streams, the flexibility of per-peer rate adaptation inside each multicast tree yields a further slight improvement in overall video quality over multicast of non-scalable streams.

We present a method that unifies tracking and video content recognition with applications to Mobile Augmented Reality (MAR). We introduce the Radial Gradient Transform (RGT) and an approximate RGT, yielding the Rotation-Invariant, Fast Feature (RIFF) descriptor. We demonstrate that RIFF is fast enough for real-time tracking, while robust enough for large scale retrieval tasks. At 26× the speed, our tracking-scheme obtains a more accurate global affine motion-model than the Kanade Lucas Tomasi (KLT) tracker. The same descriptors can achieve 94% retrieval accuracy from a database of 104images.

In this paper, they address a key challenge for scaling image search up to larger databases: the amount of memory consumed by the inverted index. In a VT-based image retrieval system, the most memory-intensive structure is the inverted index. For example, in a database of one million images where each image contains hundreds of features, the inverted index consumes 2.5 GB of RAM. Such large memory usage limits the ability to run other concurrent processes on the same server, such as recognition systems for other databases. A memory-congested server can exhibit swapping between main and virtual memory, which significantly slows down all processes.

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.

In this paper, we focus on a new application of mobile visual search: snapping a photo with a mobile device of a video playing on a TV screen to automatically retrieve and stream the remainder of the video to the mobile device. When the user takes a photo of the video, the captured query frame may contain too few useful features for good retrieval performance. We design and implement a new algorithm for mobile video retrieval to accurately select a feature-rich frame from a sequence of viewfinder frames in a very short temporal window determined by the user-initiated query event. Fast and accurate selection using efficiently computed Hessian scores is developed for real-time operation on mobile devices. Viewfinder frames captured before the query starts are pre-processed, while the number of viewfinder frames captured afterwards is minimized by a probabilistic optimization process. Evaluated on a large video database of 10 million frames, dynamic query frame selection provides a substantial increase in retrieval accuracy with very low search latency.

High-spatial-resolution videos offer the possibility of viewing an arbitrary region-of-interest (RoI) interactively. In this paper, we focus on a real-time video streaming system with interactive RoI functionality. Real-time video encoding poses a bottleneck for developing such a system. We present some solutions for speeding up the encoding process at the server so it can be performed in real-time. First, we encode only those video slices that intersect the users' RoIs during a given frame-interval. The server load can be further reduced by skipping the downsampling of the static background in the scene. We also make use of the modes and motion vectors information available in the original high-definition bitstream. Experimental results show that the encoding time at the server can be reduced significantly (more than 90% in some cases) without affecting the video quality or increasing the transmission bit-rate.

We present a fast and efficient geometric re-ranking method that can be incorporated in a feature based image-based retrieval system that utilizes a Vocabulary Tree (VT). We form feature pairs by comparing descriptor classification paths in the VT and calculate geometric similarity score of these pairs. We propose a location geometric similarity scoring method that is invariant to rotation, scale, and translation, and can be easily incorporated in mobile visual search and augmented reality systems. We compare the performance of the location geometric scoring scheme to orientation and scale geometric scoring schemes. We show in our experiments that re-ranking schemes can substantially improve recognition accuracy. We can also reduce the worst case server latency up to 1 sec and still improve the recognition performance.

Consider distributed source coding in which each block of the source at the encoder is associated with multiple candidates for side information at the decoder, just one of which is statistically dependent on the source block. Our encoder codes the source as syndrome bits and also sends a portion of it uncoded as doping bits. The decoder adaptively discovers the best side information candidates for each block of the source. The main contribution is a method based on density evolution to analyze and design the coding performance. Experimental results show that the density evolution technique is accurate in modeling the codec and optimizing its doping rate.

Manual generation of a book inventory is time-consuming and tedious, while deployment of barcode and radio-frequency identification (RFID) management systems is costly and affordable only to large institutions. In this paper, we design and implement a mobile book recognition system for conveniently generating an inventory of books by snapping photos of a bookshelf with a smartphone. Since smartphones are becoming ubiquitous and affordable, our inventory management solution is cost-effective and very easy to deploy. Automatic and robust book recognition is achieved in our system using a combination of spine segmentation and bag-of-features image matching. At the same time, the location of each book is inferred from the smartphone's sensor readings, including accelerometer traces, digital compass measurements, and WiFi signatures. This location information is combined with the image recognition results to construct a location-aware book inventory. We demonstrate the effectiveness of our book spine recognition and location estimation techniques in recognition experiments and in an actual mobile book recognition system.

Restoring the fine detail in the slide area of a defocused lecture video is a challenging task. In this work, we propose to use clean images of slides available along with the defocused lecture video to help the restoration. Our proposed method uses local feature descriptors and multiple defocused slide decks to automatically identify the slide that is displayed in the defocused frame. We then use the matching slide as side information to estimate the parameters for deconvolution and bilateral filtering. Experimental results show that the proposed algorithm compares favorably to a computationally-intensive iterative deconvolution algorithm that does not employ any side information. In particular, it can recover small drawings and text that are severely blurred in a poorly focused lecture video

We study video transcoding for accelerated channel changes in IPTV systems. Video transcoding at the Retransmission Server not only reduces the channel change latency, but also reduces the duration and data size of the unicast burst stream used for rapid acquisition. We develop an analytical model to capture the fundamental trade-offs in this system. This model is then used to characterize the potential savings from transcoding the unicast stream. Analysis and simulation results show that the stream compression factor affects linearly the saving in the channel change latency, and superlinearly the saving in unicast burst duration (or data size).

We present a mobile product recognition system for the camera-phone. By snapping a picture of a product with a camera-phone, the user can retrieve online information of the product. The product is recognized by an image-based retrieval system located on a remote server. Our database currently comprises more than one million entries, primarily products packaged in rigid boxes with printed labels, such as CDs, DVDs, and books. We extract low bit-rate descriptors from the query image and compress the location of the descriptors using location histogram coding on the camera-phone. We transmit the compressed query features, instead of a query image, to reduce the transmission delay. We use inverted index compression and fast geometric re-ranking on our database to provide a low delay image recognition response for large scale databases. Experimental timing results on different parts of the mobile product recognition system is reported in this work.

Interactive media streaming is the communication paradigm where an observer periodically requests new desired subsets from the streaming sender in real-time, upon which the sender sends the appropriate media data, corresponding to the received requests, for immediate decoding and display. This is in contrast to non-interactive media streaming, e.g., TV broadcast, where the entire media set is compressed and delivered to the observer before the observer interacts with the data (such as switching TV channels). Examples of interactive streaming abound in different media modalities: interactive browsing of JPEG2000 images, interactive light field or multiview video streaming, etc. Interactive media streaming has the obvious advantage of bandwidth efficiency: only the media subsets corresponding to observer's requests are transmitted. This is important when an observer only views a small subset out of a very large media data set during a typical streaming session. The technical challenge is how to structure media data such that good compression efficiency can be achieved by exploiting correlation among media subsets (thus inducing a particular decoding order if correlation is exploited during encoding), while providing sufficient flexibility for the observer to freely navigate the media data set in his/her desired unique order. In this overview paper, we survey different proposals in the literature that simultaneously achieve the conflicting objectives of compression efficiency and decoding flexibility.

Emerging IPTV technology uses source-specific IP multicast to deliver television programs to end-users. To provide reliable IPTV services over the error-prone DSL access networks, a combination of multicast forward error correction (FEC) and unicast retransmissions is employed to mitigate the impulse noises in DSL links. In existing systems, the retransmission function is provided by the Retransmission Servers sitting at the edge of the core network. In this work, we propose an alternative distributed solution where the burden of packet loss repair is partially shifted to the peer IP set-top boxes. Through Peer-Assisted Repair (PAR) protocol, we demonstrate how the packet repairs can be delivered in a timely, reliable and decentralized manner using the combination of server-peer coordination and redundancy of repairs. We also show that this distributed protocol can be seamlessly integrated with an application-layer source-aware error protection mechanism called forward and retransmitted Systematic Lossy Error Protection (SLEP/SLEPr). Simulations show that this joint PARSLEP/ SLEPr framework not only effectively mitigates the bottleneck experienced by the Retransmission Servers, thus greatly enhancing the scalability of the system, but also efficiently improves the resistance to the impulse noise.

When multiple video streams share a wireless network, careful rate allocation is needed to prevent congestion, as well as to balance the video qualities among the competing streams. In this paper, we present a distributed media-aware rate allocation protocol, and evaluate its performance for streaming of high-definition video over 802.11-based wireless home networks. Our optimization framework accommodates heterogeneity in wireless link speeds and video rate-distortion characteristics, as well as traffic contention among neighboring links. The goal of the protocol is to minimize the total video distortion of all participating streams while limiting network utilization. It relies on cross-layer information exchange between video rate controllers at the end hosts and link state monitors at the relaying wireless nodes. Results from various network simulations confirm that the media-aware allocation outperforms transmission control protocol-friendly rate control in terms of average video quality and fairness among the streams.

The direction-adaptive partitioned block transform (DA-PBT) is proposed to exploit the directional features in color images to improve coding performance. Depending on the directionality in an image block, the transform either selects one of the eight directional modes or falls back to the nondirectional mode equivalent to the conventional 2-D DCT. The selection of a directional mode determines the transform direction that provides directional basis functions, the block partitioning that spatially confines the high-frequency energy, the scanning order that arranges the transform coefficients into a 1-D sequence for efficient entropy coding, and the quantization matrix optimized for visual quality. The DA-PBT can be incorporated into image coding using a rate-distortion optimized framework for direction selection, and can therefore be viewed as a generalization of variable blocksize transforms with the inclusion of directional transforms and nonrectangular partitions. As a block transform, it can naturally be combined with block-based intra or inter prediction to exploit the directionality remaining in the residual. Experimental results show that the proposed DA-PBT outperforms the 2-D DCT by more than 2 dB for test images with directional features. It also greatly reduces the ringing and checkerboard artifacts typically observed around directional features in images. The DA-PBT also consistently outperforms a previously proposed directional DCT. When combined with directional prediction, gains are less than additive, as similar signal properties are exploited by the prediction and the transform. For hybrid video coding, significant gains are shown for intra coding, but not for encoding the residual after accurate motion-compensated prediction.

Establishing visual correspondences is an essential component of many computer vision problems, and is often done with robust, local feature-descriptors. Transmission and storage of these descriptors are of critical importance in the context of mobile distributed camera networks and large indexing problems. We propose a framework for computing low bit-rate feature descriptors with a 20× reduction in bit rate. The framework is low complexity and has significant speed-up in the matching stage. We represent gradient histograms as tree structures which can be efficiently compressed. We show how to efficiently compute distances between descriptors in their compressed representation eliminating the need for decoding. We perform a comprehensive performance comparison with SIFT, SURF, and other low bit-rate descriptors and show that our proposed CHoG descriptor outperforms existing schemes.

For mobile image matching applications, a mobile device captures a query image, extracts descriptive features, and transmits these features wirelessly to a server. The server recognizes the query image by comparing the extracted features to its database and returns information associated with the recognition result. For slow links, query feature compression is crucial for low-latency retrieval. Previous image retrieval systems transmit compressed feature descriptors, which is well suited for pairwise image matching. For fast retrieval from large databases, however, scalable vocabulary trees are commonly employed. In this paper, we propose a rate-efficient codec designed for tree-based retrieval. By encoding a tree histogram, our codec can achieve a more than 5times rate reduction compared to sending compressed feature descriptors. By discarding the order amongst a list of features, histogram coding requires 1.5times lower rate than sending a tree node index for every feature. A statistical analysis is performed to study how the entropy of encoded symbols varies with tree depth and the number of features.

Media authentication is important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of a media file might exist. Our previous work applied distributed source coding not only to distinguish the legitimate diversity of encoded images from tampering but also to localize tampered regions in an image already deemed to be in authentic. In both cases, authentication requires a Slepian-Wolf encoded image projection that is supplied to the decoder. We extend our scheme to authenticate images that have undergone affine warping. Our approach incorporates an expectation maximization algorithm into the Slepian-Wolf decoder. Experimental results demonstrate that the proposed algorithm can distinguish legitimate encodings of authentic images from illegitimately modified versions, despite an arbitrary affine warping, using authentication data of less than 250 bytes per image.

Local features are widely used for content-based image retrieval and object recognition. We present an efficient method for encoding digital images suitable for local feature extraction. First, we find the patches in the image corresponding to the detected features. Then, we extract these patches at their characteristic scale and orientation and encode them for efficient transmission. A Discrete Cosine Transform (DCT) with adaptive block size is used for patch compression. We compare this method to directly compressing feature descriptors using transform coding. Experimental results show the superior performance of our technique. Image patches can be compressed to rates around 55 bits/patch (18times compression relative to uncompressed SIFT feature descriptors) and still achieve good image matching performance.

We consider a video streaming system in which the user can interactively watch an arbitrary region of a high-spatial-resolution scene. Region-of-interest (RoI) prediction helps pre-fetch select slices of encoded video. The more accurate the RoI prediction the lower is the percentage of missing pixels. We compare different techniques for RoI prediction for streaming soccer sequences. Two techniques proposed in our earlier work are not domain-specific and can be applied to any type of content. Here we propose two techniques geared for soccer sequences that perform semantic video analysis. The goal of the paper is to find out whether domain-specific techniques can predict the client's RoI more accurately. Experiments indicate that for short prediction look-ahead there is little gain whereas for a long prediction look-ahead of 2 seconds the percentage of missing pixels can be reduced from 24% for the best general technique to 18% for the best domain-specific technique. This translates to a PSNR gain of around 1 dB for long prediction look-ahead. The percentage of missing pixels can be reduced further by spending additional bitrate for pre-fetching a margin around the predicted RoI.

Continuous recognition and tracking of objects in live video captured on a mobile device enables real-time user interaction. We demonstrate a streaming mobile augmented reality system with 1 second latency. User interest is automatically inferred from camera movements, so the user never has to press a button. Our system is used to identify and track book and CD covers in real time on a phone's viewfinder. Efficient motion estimation is performed at 30 frames per second on a phone, while fast search through a database of 20,000 images is performed on a server.

Emerging IPTV technology uses source-specific IP multicast to deliver TV programs to the end-users. To provide timely and reliable services over the error-prone DSL access networks, a combination of multicast forward error correction and unicast retransmissions is employed to mitigate the impact of impulse noise. In current systems, the retransmission function is provided by the Retransmission Servers.

Media authentication is important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of a media file might exist. Our previous work applied distributed source coding not only to distinguish the legitimate diversity of encoded images from tampering but also to localize tampered regions in an image already deemed to be inauthentic. In both cases, authentication requires a Slepian-Wolf encoded image projection that is supplied to the decoder. We extend our scheme to authenticate images that have undergone contrast, brightness, and affine warping adjustment. Our approach incorporates an expectation maximization algorithm into the Slepian-Wolf decoder. Experimental results demonstrate that the proposed algorithm can distinguish legitimate encodings of authentic images from illegitimately modified versions, despite arbitrary contrast, brightness, and affine warping adjustment, using authentication data of less than 250 bytes per image.

Video streaming with virtual pan/tilt/zoom functionality allows the viewer to watch arbitrary regions of a high-spatial-resolution scene. A video coding scheme with random access to arbitrary regions of arbitrary zoom factors helps avoid transmission and/or decoding of the entire high-spatial-resolution video signal. The video coding scheme, proposed in our earlier work, creates a multi-resolution representation and uses P slices of H.264/AVC. The base layer, which provides a thumbnail overview of the entire scene, is encoded using motion-compensated prediction (MCP) among temporally successive frames. To provide efficient random access, we avoid MCP among temporally successive frames of the higher resolution layers. Instead, upward prediction from the reconstructed thumbnail frames is used for coding high-resolution P slices. In this paper, we show that background extraction and long-term memory motion-compensated prediction can reduce the bitrate by up to 85% while retaining efficient random access capability.

We review the Stanford peer-to-peer multicast (SPPM) protocol for live video streaming and report recent extensions. SPPM has been designed for low latency and robust transmission of live media by organizing peers within multiple complementary trees. The recent extensions to live streaming are time-shifted streaming, interactive region-of-interest (IRoI) streaming, and streaming to mobile devices. With time-shifting, users can choose an arbitrary beginning point for watching a stream, whereas IRoI streaming allows users to select an arbitrary region to watch within a high-spatial-resolution scene. We extend the live streaming to mobile devices by addressing challenges due to heterogeneous displays, connection speeds, and decoding capabilities.

This paper addresses the rate allocation problem for wireless video streaming. Results from a simple subjective viewing test indicate that perceptually preferred allocation can be closely approximated by minimizing the total mean-squared-error (MSE) distortion of all participating streams. This finding motivates the design of a distributed media-aware rate allocation protocol, which achieves the optimal solution by allowing cross-layer information exchange between the video end hosts and relaying wireless nodes. Various network simulation results confirm the effectiveness of the proposed scheme, which consistently outperforms conventional media-unaware TCP-friendly Rate Control (TFRC).

In the above titled paper (ibid., vol. 18, no. 10, pp. 1347-1360, Oct 08), Fig. 4 was printed incorrectly. The correct figure is presented here.

We consider the problem of rate allocation among multiple simultaneous video streams sharing multiple heterogeneous access networks. We develop and evaluate an analytical framework for optimal rate allocation based on observed available bit rate (ABR) and round-trip time (RTT) over each access network and video distortion-rate (DR) characteristics. The rate allocation is formulated as a convex optimization problem that minimizes the total expected distortion of all video streams. We present a distributed approximation of its solution and compare its performance against Hinfin-optimal control and two heuristic schemes based on TCP-style additive-increase-multiplicative-decrease (AIMD) principles. The various rate allocation schemes are evaluated in simulations of multiple high-definition (HD) video streams sharing multiple access networks. Our results demonstrate that, in comparison with heuristic AIMD-based schemes, both media-aware allocation and Hinfin-optimal control benefit from proactive congestion avoidance and reduce the average packet loss rate from 45% to below 2%. Improvement in average received video quality ranges between 1.5 to 10.7 dB in PSNR for various background traffic loads and video playout deadlines. Media-aware allocation further exploits its knowledge of the video DR characteristics to achieve a more balanced video quality among all streams.

We propose peer swapping as a means to improve the throughput of structured-overlay-based peer-to-peer (P2P) streaming systems. In many P2P streaming systems, an overlay is incrementally constructed as peers join the system. When the system is dominated by peers with low uplink bandwidth (so-called leeches), the overlay can get clogged, which hampers its growth. A P2P system that suffers from clogging cannot scale any longer because even peers with high bandwidth are rejected. We first provide a theoretical analysis of clogging, which reveals that clogging is inevitable in a structured-overlay-based streaming system with heterogeneous peer uplink bandwidths. To overcome clogging, we propose distributed peer swapping, a method to reconfigure the overlay without centralized control. Experimental results demonstrate that peer swapping enables the system to accept more peers by mitigating clogging.

Distributed coding of correlated grayscale stereo images is effectively addressed by a recently proposed codec that learns block-wise disparity at the decoder. Based on the Slepian-Wolf theorem, one image can be transmitted at a rate approaching the conditional entropy if the other image is referenced as side information at the decoder. This paper improves the methods in the decoder design by refining disparity estimates to pixel resolution, generating more accurate initial disparity estimates, and modeling noise as a nonstationary random field. The new decoder enables up to an additional 9 percent bit rate savings for lossless coding. When the rate is insufficient for lossless reconstruction, the new decoder improves PSNR and significantly reduces visually unpleasant blocking artifacts.

Audio authentication is important in content delivery via untrusted intermediaries, for example peer-to-peer (P2P) file sharing. Many differently encoded versions of the original audio might exist. Distinguishing the legitimate diversity of encodings from malicious tampering is the challenge addressed in this paper. We develop an approach based on distributed source coding for the problem of backward-compatible audio authentication. The key idea is to provide a Slepian-Wolf encoded quantized perceptually significant audio projection as authentication data. This version can be correctly decoded only with the help of authentic audio as side information. Distributed source coding provides the desired robustness against legitimate encoding variations, while detecting illegitimate modification. We demonstrate reliable authentication at a Slepian-Wolf bitrate of less than 100 bit/s.

We propose a direction-adaptive block transform that exploits the directionality in images to improve the compression performance. It can be viewed as a generalization of variable block-size transforms with the inclusion of non-rectangular partitions and directional transforms. As a block transform, it can be directly combined with block-wise intra and inter prediction in video coding standards. Experimental results show that the proposed transform outperforms the variable block-size 2-D DCT by up to 3 dB. It also outperforms a previously proposed direction-adaptive DCT by up to 2 dB. When combined with intra prediction, the proposed transform further provides a gain of 0.5 to 2 dB upon intra prediction with the 2-D DCT.

Wyner-Ziv coding of multiview images avoids communications between source cameras. To achieve good compression performance, the decoder must relate the source and side information images. Since correlation between the two images is exploited at the bit level, it is desirable to map small Euclidean distances between coefficients into small Hamming distances between bitwise codewords. This important mapping property is not achieved with the binary code but can be achieved with the Gray code. Comparing the two mappings, it is observed that the Gray code offers a substantial benefit for unsupervised learning of unknown disparity but provides limited advantage if disparity is known. Experimental results with multiview images demonstrate the Gray code achieves PSNR gains of 2 dB over the binary code for unsupervised learning of disparity.

Media authentication and tampering localization are important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of a media file might exist. Our previous work applied distributed source coding to authenticate the legitimate diversity of encoded images and also localize the tampered regions in an inauthentic image. The authentication/localization decoder was supplied with a Slepian-Wolf encoded image projection as authentication data. We extend our scheme to localize tampering in contrast and brightness adjusted images using an expectation maximization algorithm at the decoder. Experimental results demonstrate that tampered image blocks can be identified with high probability using data of only a few hundred bytes for a 512 times 512 image.

Video streaming with virtual pan/tilt/zoom functionality allows the viewer to watch arbitrary regions of a high-spatial-resolution scene. In our proposed system, the user controls his region-of-interest (ROI) interactively during the streaming session. The relevant portion of the scene is rendered on his screen immediately. An additional thumbnail overview aids his navigation. We design a peer-to-peer (P2P) multicast live video streaming system to provide the control of interactive region-of-interest (IROI) to large populations of viewers while exploiting the overlap of ROIs for efficient and scalable delivery. Our P2P overlay is altered on-the-fly in a distributed manner with the changing ROIs of the peers. The main challenges for such a system are posed by the stringent latency constraint, the churn in the ROIs of peers and the limited bandwidth at the server hosting the IROI video session. Experimental results with a network simulator indicate that the delivered quality is close to that of an alternative traditional unicast client-server delivery mechanism yet requiring less uplink capacity at the server.

Multi-user rate allocation is essential for preventing multiple simultaneous video streaming sessions from congesting a time- shared wireless network. Although the problem fits naturally within an optimization framework, it remains unclear which objective function to optimize, especially for video streams with heterogeneous resolutions, frame rates and content complexity. To address this issue, we have conducted subjective tests and have collected viewers' opinion scores for various quality combinations of high-definition (HD) and standard-definition (SD) video snapshots. The test results yield a simple subjective quality model, useful for comparing performance of several rate allocation schemes. It is shown that the subjectively preferred allocation can be closely approximated by minimizing weighted or equal-weight sum of mean-squared-error (MSE) distortion of all streams. Significant performance gains can be achieved over media-unaware TCP-friendly allocation, up to 1.5 in MOS, when network resources are limited.

Wyner-Ziv coding of multiview images is an attractive solution because it avoids communications between individual cameras. To achieve good rate-distortion performance, the Wyner-Ziv decoder must reliably estimate the disparities between the multiview images. For the scenario where two reference images exist at the decoder, we propose a codec that effectively performs unsupervised learning of the two disparities between an image being Wyner-Ziv coded and the two reference images. The proposed two-disparity decoder disparity-compensates the two references images and generates side information more accurately than an existing one-disparity decoder. Experimental results with real multiview images demonstrate that the proposed codec achieves PSNR gains of 1-5 dB over the one-disparity codec.

This paper presents a reduced-reference image quality assessment scheme using distributed source coding for remotely monitoring image quality. In our scheme, an image server extracts a feature vector from the original image and transmits its Slepian-Wolf syndrome using an LDPC encoder. With the rate of the Slepian-Wolf bitstream chosen according to a predetermined admissible image quality, the receiver can reconstruct the feature vector using its received image, as side information, as long as the quality is higher than the admissible quality. Thus the receiver can determine the received image quality using the reconstructed feature vector. Simulation results show that distributed source coding can reduce the bit-rate of the feature vector by 50% and achieve better compression performance than conventional source coding.

Media authentication is important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of a media file might exist. Our previous work applied distributed source coding not only to distinguish the legitimate diversity of encoded images from tampering but also localize the tampered regions in an image already deemed to be inauthentic. An authentication decoder was supplied with a Slepian-Wolf encoded image projection as authentication data. We extend our scheme to authenticate contrast and brightness adjusted images using an Expectation Maximization algorithm. Experimental results demonstrate that the proposed algorithm can distinguish legitimate encodings of authentic contrast and brightness adjusted images from illegitimately modified versions using authentication data of about 100 bytes.

We design a test methodology to analyze in detail the video quality received at each peer in a peer-to-peer (P2P) video streaming system. The metrics that we employ at each peer include video PSNR, statistical analysis of frame-freeze events, the amount of time to wait before video playback starts, nature of the data-paths established to serve the peer, protocol overhead and duplicate data received. These metrics are estimated by analyzing the packet reception times at each peer and utilizing information about the original uncompressed video as well as the encoded video. We use this framework to compare the performance of three P2P video streaming systems by deploying them on our controlled traffic-shaped network test-bed. We can emulate the same network conditions and peer behavior for testing different systems and ensure that the experiments are repeatable. These measurements highlight the differences between systems based upon their underlying implementation, overlay architecture, and choice of protocols. This measurement study helps to gauge the performance of currently available P2P video streaming systems and points out desirable performance improvements.

We propose an overlay consisting of multiple trees with moderate outdegree to reduce end-to-end transmission delays in P2P media streaming systems. In real-time media streaming, lower end-to-end delays lead to less waiting time before playback and hence improve interactivity. A theoretical analysis of degree-bounded trees reveals that an optimal number of multiple trees can be chosen by considering the trade-off between the total propagation delay and the queueing delay experienced at intermediate peers. A distributed protocol is presented that allows peers to build multiple degree-bounded trees. From extensive packet-level simulations, we observe that the worst end-to-end transmission delay is minimized when the peerpsilas outdegree, or fan-out, is between 4 and 6 for realistic simulation parameters. This matches well with the predictions from our analysis.

We evaluate the performance of a large-scale live P2P video multicast session comprising more than 120, 000 peers on the Internet. Our analysis highlights P2P video multicast characteristics such as high bandwidth requirements, high peer churn, low peer persistence in the P2P multicast system, significant variance in the media stream quality delivered to peers, relatively large channel start times, and flash crowd effects of popular video content. Our analysis also indicates that peers are widely spread across the IP address space, spanning dozens of countries and hundreds of ISPs and Internet ASes. As part of the P2P multicast evaluation several QoS measures such as fraction of stream blocks correctly received, number of consecutive stream blocks lost, and channel startup time across peers. We correlate the observed quality with the underlying network and with peer behavior, suggesting several avenues for optimization and research in P2P video multicast systems.

Automatic CD cover recognition has interesting applications for comparison shopping and music sampling. We demonstrate a real-time CD cover recognition using a cameraphone. By snapping a picture of a CD cover with her cameraphone, a user can conveniently retrieve information related to the CD. Robust image feature extraction is applied to overcome the image distortions in the query photo. To limit the amount of data transmitted over a wireless network, we compress the query image or features extracted from the query image. On the database side, fast and reliable image matching against a database of 10,000 CD covers is accomplished using a scalable vocabulary tree.

Illumination distortion due to uncontrolled lighting can severely degrade the color appearance of a photo. Frequently, the desired colors for objects in a newly taken query image are found in a previously stored database image. Then, the goal is to change the colors in the query image to match the colors in the database image. This paper presents a color restoration system that automatically retrieves a database image which matches the query image, even if the two images are taken from different viewpoints and under different illuminations. Robust features enable both accurate retrieval from the database and efficient sampling of the color differences between the query and database images. A spatially varying color mismatch model is generated, and the colors of the query image are effectively restored.

We investigate retransmission-based robust video streaming over lossy packet networks in this paper. We propose to send a thumbnail video along with the video packets. The thumbnail video is Wyner-Ziv-coded to exploit its correlation with the primary video. The receiver decodes the primary video with the help of error concealment to mitigate packet losses. Upon receiving and successfully decoding the thumbnail, the receiver can estimate the local distortion due to packet losses and make intelligent decisions on which packets are needed for retransmission. Additional gain in video quality can be achieved by using the thumbnail to aid error concealment. Our experimental results demonstrate gains over previously proposed distortion-unaware heuristic methods.

We consider the general scenario where content hosted by the server comprises streams and each peer can subscribe one or more streams. Multiple multicast trees are built to deliver the streams to respective peers while exploiting the overlap of their interests for efficient and scalable delivery. We propose an optimization framework for allocating server bandwidth to minimize distortion across the peer population. We apply the framework to a novel application, peer-to-peer (P2P) multicast live video streaming with virtual pan/tilt/zoom functionality. In this application, each user can watch arbitrary regions of a high-spatial-resolution scene yet the system exploits overlapping interests by building multicast trees. Experimental results indicate that optimal server bandwidth allocation enhances the delivered quality across the peer population.

We consider a new problem in network image coding for multicast. In a multihop mesh network, structured as a directed graph, all nodes decode and display reconstructions of the image (at possibly different qualities). Each node may also perform transcoding before transmitting data downstream in the network. The problem is the design of the coding and transcoding schemes to deliver the best image quality over the network. For a network with diamond topology, we show that multiple description coding combined with Wyner-Ziv transcoding is often superior to other methods. We argue further that the benefits are magnified for larger networks containing one or more diamond subnets. Our image coding experiments demonstrate that multiple description coding with Wyner-Ziv transcoding outperforms single description coding or multiple description coding with conventional transcoding, for both a diamond network and a two-hop mesh network with four branches.

Peer-to-peer multicast is promising for large-scale streaming video distribution over the Internet. Viewers contribute their resources to a peer-to-peer overlay network to act as relays for the media streams, and no dedicated infrastructure is required. As packets are transmitted over long, unreliable multipeer transmission paths, it is particularly challenging to achieve consistently high video quality and low end-to-end delay. In this paper, we focus on error-resilient transport for peer-to-peer video streaming. The algorithms we describe are representative of three broad categories of robust video streaming schemes: forward error correction, multiple descriptions, and prioritized automatic repeat request. We analyze how these techniques can be employed for live peer-to-peer multicast and discuss their relative merits. Our results show that significant gains can be obtained when systems are designed to adapt to the encoding structure of the video streams they are transmitting. They also reveal the importance of avoiding congestion at every peer participating in the multicast to obtain a low-latency system. Finally, we provide insights as to which are the important metrics to compare different peer-to-peer streaming systems.

Video communication is often afflicted by various forms of losses, such as packet loss over the Internet. This paper examines the question of whether the packet loss pattern, and in particular, the burst length, is important for accurately estimating the expected mean-squared error distortion resulting from packet loss of compressed video. We focus on the challenging case of low-bit-rate video where each P-frame typically fits within a single packet. Specifically, we: 1) verify that the loss pattern does have a significant effect on the resulting distortion; 2) explain why a loss pattern, for example a burst loss, generally produces a larger distortion than an equal number of isolated losses; and 3) propose a model that accurately estimates the expected distortion by explicitly accounting for the loss pattern, inter-frame error propagation, and the correlation between error frames. The accuracy of the proposed model is validated with H.264/AVC coded video and previous frame concealment, where for most sequences the total distortion is predicted to within plusmn0.3 dB for burst loss of length two packets, as compared to prior models which underestimate the distortion by about 1.5 dB. Furthermore, as the burst length increases, our prediction is within plusmn0.7 dB, while prior models degrade and underestimate the distortion by over 3 dB. The proposed model works well for video-telephony-type of sequences with low to medium motion. We also present a simple illustrative example, of how knowledge of the effect of burst loss can be used to adapt the schedule of video streaming to provide improved performance for a burst loss channel, without requiring an increase in bit rate.

This paper proposes a scheme called Systematic Lossy Error Protection (SLEP) for robust transmission of video signals over packet erasure channels. The systematic portion of the transmission consists of a conventionally encoded video bit stream which is transmitted without channel coding. An additional bit stream generated by Wyner–Ziv encoding of the video signal is transmitted for error resilience. In the event of packet loss, this supplementary bit stream is decoded and allows the recovery of a coarsely quantized video signal, which is displayed in lieu of the lost portions of the primary video signal. The quantization mismatch results in a small, controlled loss in picture quality, but a drastic reduction in picture quality is avoided. An implementation of the SLEP system using the state-of-the-art H.264/AVC standard codec is described. Specifically, H.264/AVC redundant slices are used in conjunction with Reed–Solomon coding to generate the Wyner–Ziv bit stream. The received video quality is modeled as a function of the bit rates of the primary and redundant descriptions and the error resilience bit rate. The model is used to optimize the video quality delivered by SLEP. Via theoretical analysis and experimental simulation, it is shown that SLEP provides a flexible tradeoff between error resilience and decoded picture quality. By allowing the quality to degrade gracefully over a wider range of packet loss rates, SLEP mitigates the precipitous drop in picture quality suffered by traditional FEC-based systems.

Motion-compensated lifted wavelets have received much interest for video compression. While they are biorthogonal, they may substantially deviate from orthonormality due to motion compensation, even if based on an orthogonal or near-orthogonal wavelet. A temporal transform for video sequences that maintains orthonormality while permitting flexible motion compensation would be very desirable. We have recently introduced such a transform for integer-pel accurate motion compensation from one previous frame. In this paper, we extend this idea to half-pel accurate motion compensation. Orthonormality is maintained for arbitrary half-pel motion compensation by cascading a sequence of incremental orthogonal transforms. The half-pel intensity values are obtained by averaging neighboring integer-pel positions. Depending on the number of averaged integer-pel values, we use different types of incremental transforms. The cascade of incremental transforms allows us to choose in each step the optimal type of incremental transform and, hence, the optimal half-pel position. Half-pel motion-compensated blocks of arbitrary shape and size can be used as the granularity of the cascade can be as small as one pixel. The new half-pel accurate motion-compensated orthogonal video transform compares favorably with the integer-pel accurate orthogonal transform

We consider a first-order Markov source, which is predictively encoded using a DPCM-style encoder. The quantized compressed prediction residual is transmitted over an erasure channel. Additionally, a Wyner-Ziv encoded version of the prediction residual is transmitted in order to provide error resilience. When the symbols from the first transmission are erased by the channel, this second description is decoded, and limits the maximum distortion that can occur. Since the quantization step size used in the second description is, in general, larger than that used in the main transmission, error protection is lossy. Using high-rate quantization theory, we derive expressions for the rate and the end-to-end distortion incurred by this system. We show that, compared to conventional lossless forward error correction, this lossy error protection scheme is robust in the sense that it allows the received signal quality to degrade gracefully when the erasure probability increases

Distributed compression is particularly attractive for stereo images since it avoids communication between cameras. Since compression performance depends on exploiting the redundancy between images, knowing the disparity is important at the decoder. Unfortunately, distributed encoders cannot calculate this disparity and communicate it. We consider the compression of grayscale stereo images, and develop an expectation maximization algorithm to perform unsupervised learning of disparity during the decoding procedure. Towards this, we devise a novel method for joint bitplane distributed source coding of grayscale images. Our experiments with both natural and synthetic 8-bit images show that the unsupervised disparity learning algorithm outperforms a system which does no disparity compensation by between 1 and more than 3 bits/pixel and performs nearly as well as a system which knows the disparity through an oracle

Motion-compensated lifted wavelets have received much interest for video compression. While they are biorthogonal, they may substantially deviate from orthonormality due to motion compensation, even if based on an orthogonal or near-orthogonal wavelet. A temporal transform for video sequences that maintains orthonormality while permitting flexible motion compensation would be very desirable. We have recently introduced such a transform for unidirectional motion compensation from one previous frame. In this paper, we extend this idea to bidirectional motion compensation. Orthonormality is maintained for arbitrary integer-pixel motion compensation by cascading a sequence of incremental orthogonal 3×3 transforms. The energy of three input pictures is accumulated in two temporal low-bands while the temporal high-band is zero if the input pictures are identical after motion compensation. Further, the motion-compensated orthogonal transforms can be cascaded to build a dyadic wavelet decomposition. The new bidirectionally motion-compensated orthogonal transform compares favorably with the lifted 5/3 wavelet in video coding experiments with integer-pixel motion compensation.

Simultaneous support of multiple delay-critical application sessions such as multiuser video streaming require a paradigm shift in the design of ad-hoc wireless networks. Instead of the conventional layered approach, cross-layer optimization is needed for more efficient resource allocation, across the protocol stack and among multiple users. In this work, we extend our previous effort in joint capacity and flow assignment at the MAC and network layers, to include rate allocation at the application layer of each user. The proposed optimization aims to minimize the tradeoff between encoded video quality of all users versus overall network congestion. Compared to a scheme with oblivious layers, where capacity, flow and video rates are assigned individually, simulation results show significant performance gain of our proposed cross-layer approach, in terms of maximum sustainable rate and quality of the video streams.

This paper proposes a scheme for low-delay robust transmission of video signals over packet erasure channels. In applications such as video conferencing, the permissible delay between encoding and playback may be too low to allow retransmission or channel coding approaches which require buffering several video packets. For such a scenario, we present a scheme that provides error robustness using redundant video descriptions applied to pertinent portions of the video signal. In the H.264/AVC specification, this can be efficiently implemented using redundant slices and flexible macroblock ordering (FMO). We describe a model that determines the bit rate of the redundant descriptions such that the expected distortion at the decoder is minimized. Across all the video test sequences used, the average video quality delivered by the proposed scheme is 3.7 dB higher than decoder-based error concealment, and 1.2 dB higher than encoder-based loss-aware rate-distortion optimization.

Image authentication is important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of the original image might exist. On the other hand, intermediaries might tamper with the contents. Distinguishing the legitimate diversity of encodings from malicious manipulation is the challenge addressed in this paper. We develop a novel approach based on distributed source coding for the problem of backward-compatible image authentication. The key idea is to provide a Slepian-Wolf encoded quantized image projection as authentication data. This version can be correctly decoded only with the help of an authentic image as side information. Distributed source coding provides the desired robustness against legitimate encoding variations, while detecting illegitimate modification. We demonstrate false acceptance rates close to zero for authentication data sizes that are only a few percent of the compressed image size.

Simultaneous support of multiple video streaming sessions over a shared wireless network requires careful resource allocation to achieve high utilization while dynamically adapting to network and video fluctuations. We propose a distributed algorithm for channel time allocation among multiple video streams, and investigate several heuristic packet pruning schemes for rate adaptation of high-definition (HD) video streams. Simulation results are presented for streaming multiple HD video sequences over an 802.11a network. In comparison with TCP-Friendly Rate Control (TFRC) and a basic scheme without rate adaptation, it is shown that the proposed scheme can sustain higher video quality with lower packet delivery delay.

This paper describes the Stanford P2P multicast (SPPM) streaming system that employs an overlay architecture specifically designed for low delay video applications. In order to provide interactivity to the user, this system has to keep the end-to-end delay as small as possible while guaranteeing a high video quality. A set of complimentary multicast trees is maintained to efficiently relay video traffic and a congestion-distortion optimized (CoDiO) scheduler prioritizes more important video packets. Local retransmission is employed to mitigate packet loss. Real-time experiments performed on the Planet-Lab show the effectiveness of the system and the benefits of a content-aware scheduler in case of congestion or node failures.

We propose a novel, low-complexity, tracking scheme that uses motion vectors directly from a video coder. We compare our tracking algorithm against ground truth data, and show that we can achieve a high level of accuracy, even though the motion vectors are rate-distortion optimized and do not represent true motion. We develop a framework for tracking in video sequences with various GOP structures. Such a scheme would find applications in the context of Mobile Augmented Reality. The proposed feature tracking algorithm can significantly reduce the required rate of feature extraction and matching.

When multiple video streaming sessions are simultaneously transported over a shared wireless network, careful rate allocation is needed for efficient utilization of the network resources, while avoiding network congestion. The problem becomes more challenging when the network comprises links with heterogeneous transmission speeds, and when eachvideo stream has a different utility of its allocated rate. We propose a distributed scheme for congestion-distortion optimized rate allocation among multiple video streams sharing a network. Simulation results are presented for streaming multiple high-definition (HD) video sequences over both single-hop and multi-hop 802.11a networks with heterogeneous link speeds. In comparison with TCP-Friendly Rate Control (TFRC), the proposed cross-layer allocation scheme benefits from being both media-aware and network-aware, and achieves higher average video quality among all streams without incurring excessive network congestion.

Contemporary wireless devices integrate multiple networking technologies, such as cellular, WiMax and IEEE 802.11a/b/g, as alternative means of accessing the Internet. Efficient utilization of available bandwidth over heterogeneous access networks is important, especially for media streaming applications with high data rates and stringent delay requirements. In this work we consider the problem of rate allocation among multiple video streaming sessions sharing multiple access networks. We develop and evaluate an analytical framework for optimal video rate allocation, based on observed available bit rate (ABR) and round trip time (RTT) over each access network, as well as the video distortion-rate (DR) characteristics. The rate allocation is formulated as a convex optimization problem that minimizes the sum of expected distortion of all video streams. We then present a distributed approximation of the optimization, which enables autonomous rate allocation at each device in a media- and network-aware fashion. Performance of the proposed allocation scheme is compared against robust rate control based on H∞ optimal control and two heuristic schemes employing TCP style additive-increase-multiplicative-decrease (AIMD) principles. Wesimulate in NS-2 [1] simultaneous streaming of multiple high-definition(HD) video streams over multiple access networks, using ABR and RTT traces collected on Ethernet, IEEE 802.11g, and IEEE 802.11b networks deployed in a corporate environment. In comparison with heuristic AIMD-based schemes, rate allocation from both the media-aware convex optimization scheme and H∞ optimal control benefit from proactive avoidance of network congestion, and can reduce the average packet loss ratio from 27% to below 2%, while improving the average received video quality by 3.3 - 4.5 dB in PSNR.

Media authentication is important in content delivery via untrusted intermediaries, such as peer-to-peer (P2P) file sharing. Many differently encoded versions of a media file might exist. Our previous work applied distributed source coding to distinguish the legitimate diversity of encoded images from tampering. An authentication decoder was supplied with a Slepian-Wolf encoded lossy version of the image as authentication data. Distributed source coding provided the desired robustness against legitimate encoding variations, while detecting illegitimate modification. We augment the decoder to localize tampering in an image already deemed to be unauthentic. The localization decoder requires only incremental localization data beyond the authentication data since we use rate-adaptive distributed source codes. Both decoders perform joint bitplane decoding, rather than conditional bitplane decoding. Our results demonstrate that tampered image blocks can be identified with high probability using authentication plus localization data of only a few hundred bytes for a 512times512 image.

This paper discusses a transform for successive pictures of an image sequence which strictly maintains orthogonality while permitting 2-hypothesis motion compensation between pairs of pictures. We extend previous work on an orthogonal transform for image sequences which uses only 1-hypothesis motion compensation between pairs of pictures. This work is motivated by the well known fact that the motion-compensated lifted Haar wavelet maintains orthogonality only approximately. In the case of zero motion fields, the motion-compensated lifted Haar wavelet is known to be orthogonal. But for complex motion fields with many multi-connected and unconnected pixels, the motion-compensated lifted Haar wavelet cannot accurately maintain its transform property and, hence, suffers a performance degradation. The presented double motion-compensated orthogonal transform strictly maintains orthogonality for any motion field. For the transform, each pixel in the high-band is compensated by a linear combination of two motion-compensated pixels chosen from the corresponding low-band. That is, each pixel in the high-band is associated with two motion vectors. This is in contrast to the previously presented single motion-compensated orthogonal transform where each pixel in the high-band is compensated by only one motion-compensated pixel chosen from the corresponding low-band. In terms of energy concentration, the double motion-compensated orthogonal transform outperforms the single motion-compensated orthogonal transform and compares favorably with the double motion-compensated lifted Haar wavelet.

Motion-compensated temporal filtering is an open-loop coding technique, which generally employs a motion-compensated update step. Although the update step is essential at the encoder for good rate-distortion efficiency, it might be skipped at the decoder for benefits like lower complexity and lower playout delay. Previous investigations showed that skipping the update step at the decoder results in some quality degradation at high rates. In this paper we analyze how this degradation arises and also propose a simple method to reduce this degradation. The proposed solution can also be implemented as a post-processing procedure after conventional decoding without the update step. Experimental results show that the degradation in quality is reduced by half. For our t+2D wavelet coder, this gives a gain of approximately 1.0 - 1.5 dB at high bit-rates.

The direction-adaptive discrete wavelet transform (DA-DWT) locally adapts the filtering direction to the geometric flow in the image. DA-DWT image coders have been shown to achieve a rate-distortion performance superior to non-adaptive wavelet coders. However, since the direction information must always be signalled regardless of total bit-rate, performance at very low bit-rates might be worse. In this paper, we propose two scalable direction representations: the layered scheme which is similar to the scalable motion vector representation in scalable video coding and the level-unit scheme which provides finer granularity upon the layered scheme. Experimental results indicate that we can achieve the desirable performance at both low and high bit rates with our proposed level-unit scheme. Significant improvement in image quality (about 3-5 dB) is observed at very low bit rate, relative to non-scalable coding of the direction information.

We investigate the rate-distortion efficiency of motion and disparity compensated coding for multiview video. Disparity compensation exploits the correlation among the view sequences and motion compensation makes use of the temporal correlation within each view sequence. We define a matrix of pictures withNview sequences, each with K temporally successive pictures. For experimental coding purposes, a scheme based on H.264/AVC is devised. We assess the overall rate-distortion efficiency for matrices of pictures of various dimensions (N,K). Moreover, we discuss the impact of inaccurate disparity compensation within a matrix of pictures. Finally, we propose and discuss a theoretical model for multiview video coding that explains our experimental observations. Performance bounds are presented for high rates.

We propose a direction-adaptive DWT (DA-DWT) that locally adapts the filtering directions to image content based on directional lifting. With the adaptive transform, energy compaction is improved for sharp image features. A mathematical analysis based on an anisotropic statistical image model is presented to quantify the theoretical gain achieved by adapting the filtering directions. The analysis indicates that the proposed DA-DWT is more effective than other lifting-based approaches. Experimental results report a gain of up to 2.5 dB in PSNR over the conventional DWT for typical test images. Subjectively, the reconstruction from the DA-DWT better represents the structure in the image and is visually more pleasing.

High-quality, photorealistic image-based rendering datasets are typically too large to download entirely before viewing, even when compressed. It is more suitable to instead stream the required image data to a remote user who can start interacting with the dataset immediately. This paper presents an interactive light field streaming system and proposes packet scheduling for transmitting the encoded image data in a rate-distortion optimized manner. An interactive light field streaming system must have low user latency. The system presented in this paper predicts the future user viewing trajectory to mitigate the effects of the low-latency constraints. Experimental results show that view prediction can improve performance, and that this improvement is limited by the prediction accuracy. The proposed packet scheduling algorithm considers network conditions and rate-distortion cost, knowledge of sent and received images, and the distortion for a set of images, to optimize the rendered image quality for the remote user. Rate-distortion optimized scheduling can be implemented either at the receiver or the sender. It is shown that this rate-distortion optimized packet scheduling can significantly improve performance over a heuristic scheduling approach. Experimental results also show that the encoding prediction dependency structure affects streaming performance both through the compression efficiency of the encoding and also through any decoding dependencies that may be introduced

We propose an adaptive lifted discrete wavelet transform to locally adapt the filtering direction to the geometric flow in the image. The proposed approach refines previous directional lifting approaches to achieve superior compression performance with less demand for computation. Additionally, a bandeletization procedure is combined with directional lifting in a unified framework to further remove the correlation in the wavelet coefficients. Up to 2.8 dB improvement in PSNR over the conventional 2-D CDF 9/7 wavelet transform for natural images is reported. Significant improvement in subjective quality is also observed.

We investigate coding of multiple image sequences with video sensors. The video sensors are arranged in an array to monitor the same scene from different view points. Furthermore, the sensors are connected to a central decoder via a network. Note that the video sensors process highly view-correlated images. This correlation can be exploited if the video sensors operate in a collaborative fashion. On the contrary, temporal correlation among the images of each sequence can be exploited locally at each sensor. Collaborative coding of the multi-view videos can be achieved by distributed processing of the multi-view imagery. If the video sensor network utilizes a central decoder, the view-correlation can be exploited by centralized disparity compensation at the decoder. But before the decoder is able to apply disparity compensation efficiently, accurate disparity values have to be estimated at the central decoder. This paper discusses the impact of disparity fields at the central decoder and uses these estimates for centralized disparity compensation at the decoder to improve the efficiency of the video sensor network.

In live peer-to-peer streaming, a video stream is transmitted to a large population of viewers, through the use of the uplink bandwidth of participating peers. This approach overcomes the cost of large-scale deployment of such services. An essential problem of this type of system is to limit the incurred congestion. In particular, overwhelming the uplink of some peers would create a large increase in the latency of the system and make this application less compelling. In this work we focus on limiting the congestion in a peer-to-peer network where multiple multicast trees are used to distribute video to a large set of receivers. We present the idea of congestiondistortion optimized streaming which aims at maximizing decoded video quality while limiting network congestion. We describe how this type of media scheduling maintains high video quality even for low latencies, and extend its usage to the peer-to-peer scenario. Experiments over a simulated network of 300 peers illustrate the benefits of the suggested approach. 1.

We study peer-to-peer multicast streaming, where a source distributes real-time video to a large population of hosts by making use of their forwarding capacity rather than relying on dedicated media servers. We present a distributed streaming protocol which builds and maintains multiple multicast trees. The protocol is combined with an adaptive scheduling algorithm which ensures packets destined to a large number of peers, or particularly important to decode the video, are sent in priority. Experiments carried out over a simulated network of up to 3000 peers illustrate the performance of the protocol. For low latency video streaming, the prioritization algorithm offers performance gains, especially for large audiences and low latencies

When multiple video sources are live-encoded and transmitted over a common wireless network, each stream needs to adapt its encoding parameters to wireless channel fluctuations, so as to avoid congesting the network. We present a stochastic system model for analyzing multi-user congestion control for live video coding and streaming over a wireless network. Variations in video content complexities and wireless channel conditions are modeled as independent Markov processes, which jointly determine the bottleneck queue size of each stream. Interaction among multiple users are captured by a simple model of random traffic contention. Using the model, we investigate two distributed congestion control policies: an approach based on stochastic dynamic programming (SDP) and a greedy heuristic. Compared to fixed-quality coding with no congestion control, performance gains in the range of 0.5-1.3 dB in average video quality are reported for the optimized schemes from simulation results

This paper discusses a transform for successive pictures of an image sequence which strictly maintains orthogonality while permitting motion compensation between pairs of pictures. The well known motion-compensated lifted Haar wavelet maintains orthogonality only approximately. In the case of zero motion fields, the motion-compensated lifted Haar wavelet is known to be orthogonal. But for complex motion fields with many multi-connected and unconnected pixels, the motion-compensated lifted Haar wavelet cannot accurately maintain its transform property and, hence, suffers a performance degradation. The presented motion-compensated orthogonal transform strictly maintains orthogonality for any motion field. Further, the transform is designed with an energy-concentration constraint. The energy of the input pictures is accumulated in the temporal low-band while the temporal high-band is zero if the input pictures are identical up to a known single-connecting motion field. This constraint makes the transform suitable for coding applications

Distributed compression is particularly attractive for stereoscopic images since it avoids communication between cameras. Since compression performance depends on exploiting the redundancy between images, knowing the disparity is important at the decoder. Unfortunately, distributed encoders cannot calculate this disparity and communicate it. We consider a toy problem, the compression of random dot stereograms, and propose an expectation maximization algorithm to perform unsupervised learning of disparity during the decoding procedure. Our experiments show that this can achieve twice as efficient compression compared to a system with no disparity compensation and perform nearly as well as a system which knows the disparity through an oracle

The quality of service limitation of today's best-effort networks poses major challenge for low-latency video communication. To combat network losses for real-time and on-demand video communication, which exhibits stronger dependency across packets, a network-adaptive coding scheme is employed to dynamically manage the packet dependency using optimal reference picture selection. The selection of the reference is achieved within a rate-distortion optimization framework and is adapted to the varying network conditions. For network-adaptive streaming of prestored video, based on an accurate loss-distortion model, a prescient scheme that optimizes the dependency of a group of packets is proposed to achieve global optimality as well as improved rate-distortion performance. With the improved trade-off between compression efficiency and error resilience, the proposed system does not require retransmission of lost packets, which makes less than one-second low-latency communication possible.

The new SP and SI picture types, introduced in the latest video coding standard H.264, allow drift-free bitstream switching and can also be used for error-resilience and random access. In this paper, we propose a model for the rate-distortion performance of SP and SI pictures and compare it to experimental results, obtained with our implementation of an SP/SI encoder, made publicly available and recently adopted by the Joint Video Team. The model predicts how the relative sizes of SP and SI slices can be traded off. We analyze, both theoretically and experimentally, how this can be used to minimize the transmitted bit rate when SP frames are used for video streaming with packet losses and derive optimal settings for our encoder. We investigate the benefits of SI and SP frames for error resilience as compared with periodic I frame insertion. Empirical rate-distortion curves predict rate-distortion gains may be obtained. Experiments carried out over a simulated throughput-limited network confirm this to be the case when the end-to-end delay is limited. We analyze the influence of loss rate and delay on the congestion-rate-distortion performance of streaming with SI and SP frames. Our results identify scenarios for which SI and SP frames provide an attractive alternative to streaming with I frames.

We propose disparity-compensated lifting for wavelet compression of light fields. With this approach, we obtain the benefits of wavelet coding, such as scalability in all dimensions, as well as superior compression performance. Additionally, the proposed approach solves the irreversibility limitations of previous light field wavelet coding approaches, using the lifting structure. Our scheme incorporates disparity compensation into the lifting structure for the transform across the views in the light field data set. Another transform is performed to exploit the coherence among neighboring pixels, followed by a modified SPIHT coder and rate-distortion optimized bitstream assembly. A view-sequencing algorithm is developed to organize the views for encoding. For light fields of an object, we propose to use shape adaptation to improve the compression efficiency and visual quality of the images. The necessary shape information is efficiently coded based on prediction from the existing geometry model. Experimental results show that the proposed scheme exhibits superior compression performance over existing light field compression techniques.

We extend the rate-distortion function for Wyner-Ziv coding of noisy sources with quadratic distortion, in the jointly Gaussian case, to more general statistics. It suffices that the noisy observation Z be the sum of a function of the side information Y and independent Gaussian noise, while the source data X must be the sum of a function of Y, a linear function of Z, and a random variable N such that the conditional expectation of N given Y and Z is zero, almost surely. Furthermore, the side information Y may be arbitrarily distributed in any alphabet, discrete or continuous. Under these general conditions, we prove that no rate loss is incurred due to the unavailability of the side information at the encoder. In the noiseless Wyner-Ziv case, i.e., when the source data is directly observed, the assumptions are still less restrictive than those recently established in the literature. We confirm, theoretically and experimentally, the consistency of this analysis with some of the main results on high-rate Wyner-Ziv quantization of noisy sources.

We investigate the design of optimal quantizers for individual encoding of several noisy observations of an unseen source, which is jointly decoded with the help of side information available at the decoder only. The joint statistics of the source data, the noisy observations and the side information are known, and exploited in the design. A variety of lossless coders for the quantization indices, including ideal Slepian-Wolf coders, are allowed. We present the optimality conditions such quantizers must satisfy, together with an extension of the Lloyd algorithm for a locally optimal design. Experimental results for Wyner-Ziv quantization of noisy Gaussian sources confirm the high-rate quantization theory established in our previous work.

In this paper, we study the performance of rate-distortion optimized video streaming over traces of packet delays and packet losses collected in the Internet. The study provides us with an understanding how important rate-distortion optimization may be for Internet streaming today and when it actually pays off to perform it. We propose a simple technique for channel estimation that can be incorporated within rate-distortion optimized streaming to remove the assumption of known channel statistics. In the experiments, performance of rate-distortion optimized streaming is compared to that of simpler transmission techniques such as ARQ.

We consider the transmission of multiple video streams from one server to multiple clients over a shared channel. Transcoders are used to dynamically adapt encoded source rates as link capacities vary. We present a closed-form solution for determining optimal values for the transcoded source rates in this case where multiple video streams with independently varying link capacities share time on a channel. We also present a real-time algorithm for optimized packet transmission scheduling and source pruning. Experimental results show gains of 2.5 dB in PSNR when our optimized pruning and scheduling technique is added to a system that uses transcoding, in the case when there is time lag in the control of transcoders. We also show results in which our pruning scheme performs within 1 dB of off-line, R-D optimal pruning.

Previous work on rate-distortion optimized streaming of light fields assumes that the scheduling task is performed by a central server. To scale to large numbers of simultaneous users, however, it is necessary to shift the computational burden of image scheduling to the clients. In this paper, we present a receiver-driven streaming framework where the packet scheduling is performed at the client. One key challenge of receiver-based streaming is in efficiently transmitting the rate-distortion preamble necessary for the scheduling algorithm. We present a method to efficiently represent and estimate the view-dependent distortions, and show that the performance is nearly as good as if the actual distortion values were used. We also show that the sender-driven and receiver-driven systems have very similar rate-distortion streaming performance.

This paper proposes systematic lossy error protection of video waveforms using multiple embedded Wyner-Ziv video descriptions. A video signal transmitted over an error-prone channel, without channel coding, constitutes the systematic portion of the transmission. Error protection is achieved by additionally transmitting two or more bitstreams generated by Wyner-Ziv coding of the video signal. The Wyner-Ziv bitstreams contain multiple embedded coarsely quantized descriptions of the original video signal. In the event of channel errors, the Wyner-Ziv descriptions are decoded, thereby limiting the maximum distortion that can occur. The available Wyner-Ziv bit-rate is allocated among the multiple embedded descriptions, using the observation that the visibility of slice losses and quantization artifacts depends on the employed coding structure. Experimental results show that the trade-off between error-resilience and residual quantization distortion can be better exploited using multiple embedded Wyner-Ziv descriptions, compared to earlier results with a single Wyner-Ziv bitstream. The system delivers gracefully deteriorating video quality without requiring a layered video compression scheme in the systematic portion of the transmission.

When multiple video streams are present in an ad hoc network, they share and compete for the common network resources. A rate allocation algorithm must balance the available resources among the video streams in a fair and efficient manner. In addition, it is desirable to have a distributed solution so that nodes do not need to collect global information of the network and that the computational burden can be shared. We propose a distributed rate allocation algorithm which minimizes the total distortion of all video streams. Based on the subgradient method, the proposed scheme only requires link price updates at each relay node based on local observations and rate adaptations at each source node derived from rate-distortion (RD) models of the video. Simulation results show that the proposed scheme can achieve the same optimal rate allocation as that obtained from exhaustive search.

We present a new algorithm for deadline-aware scheduling of video streams over a wireless shared channel, which only requires the computation of a single metric per user and transmission slot. By incorporating side information about the video stream structure and the future channel behavior in the scheduling algorithm, our approach outperforms existing solutions by slowing down the transmission of streams to users with favorite channel conditions until their deadline is approaching. Hence, in overload situations, the quality of the bad users is significantly increased, while good users are almost unaffected. As a consequence, this leads to a fairer distribution of the achievable video quality among all users.

When an ad hoc network with limited link capacities is used to transport high-rate, latency-constrained multimedia streams, it is important that routing algorithms not only yield high aggregated bandwidth, but also minimize network congestion to avoid excessive delay. We propose a distributed algorithm to achieve congestion-minimized multi-path routing. The optimal solution can be approximated by decomposing the total target rate into a sequence of rate increments, and using the classical Bellman-Ford algorithm to find a corresponding minimum-cost route for each increment. Simulation results for video streaming over an ad hoc network show that compared to a centralized scheme, the approximations introduced by the distributed algorithm lead to performance loss of less than 0.5 dB in PSNR of received video quality.

We propose a novel adaptive wavelet transform that exploits local image properties for image compression. It combines wavelet filters adaptive to edge orientations with quincunx subsampling to form a 2-D nonseparable transform through lifting. Filter selections are efficiently represented. Significant improvement on both subjective and objective quality over the conventional separable transform is observed. In addition, unlike previous adaptive transforms, the symmetry in quincunx subsampling enables even quality for image features along different directions and the compression performance is insensitive to image orientation

In wavelet video coding, the quantization error in the temporal sub-bands propagates through temporal wavelet synthesis to the reconstructed frames. We analyze this propagation by considering the impact of the spatial interpolation in motion compensation on the statistics of the quantization error. Based on the analysis, a distortion model that can be derived from the motion fields is introduced and incorporated into a rate allocation method aiming at reducing the quality fluctuation over frames. Comparing to the conventional allocation method that ignores the effect of motion compensation, significant reduction in quality fluctuation is observed while incurring minimal loss in the average quality

When multiple video streams are delivered from a single server to multiple clients over a time-shared channel that may support differing transmission speeds depending on the client, the problem arises of how to optimally divide channel time among the streams so that the overall quality of the decoded videos is maximized. This paper presents solutions to this allocation problem for three optimization objectives: minimizing the MSE of the decoded video over all the streams, maximizing the PSNR over all the streams, and minimizing the maximum MSE (equivalent to maximizing the minimum PSNR). Each is shown to be a convex problem which can be solved quickly using standard techniques. This paper then investigates the question of which objective should be used. Subjective tests were conducted to determine how well allocations made according to the various objectives correspond to the preferences of human test subjects. Results indicate, surprisingly, that the minimum MSE objective corresponds best to subjective preferences

In wavelet video coding, due to motion-compensation entwined in the temporal wavelet transform, the distortion in the temporal subbands propagates in an uneven manner into the reconstructed frames of a group of pictures. This leads to fluctuation of reconstruction quality in time, which can be visually displeasing. We propose a new update step which is derived by taking into account a Lagrangian term for even distribution of distortion among reconstructed frames in addition to minimizing total distortion. Additionally some heuristics for the implementation of this new update step are proposed. Experimental results show reduction of quality fluctuation compared to the conventional update step

One of the challenges in supporting multiple video streams over a small wireless network is appropriate rate control at each video source. Two rate adaptation approaches are proposed in this paper, to meet both quality and latency requirements while achieving overall efficiency. Encoding frame rate is adapted according to the importance of the video contents; quantization parameter for each frame is dynamically adjusted based on complexity of the current frame and past observations of end-to-end delay. Simulation results for a multi-camera surveillance application show the effectiveness of the proposed network-adaptive rate control in a live coding and streaming scenario. Compared to conventional methods combining TCP-friend rate control (TFRC) at the transport layer and video encoder rate control at the application layer, the proposed scheme improves the average PSNR of received video by 0.3-3.5 dB while also achieving less fluctuation in the video quality

Distributed coding is a new paradigm for video compression, based on Slepian and Wolf's and Wyner and Ziv's information-theoretic results from the 1970s. This paper reviews the recent development of practical distributed video coding schemes. Wyner-Ziv coding, i.e., lossy compression with receiver side information, enables low-complexity video encoding where the bulk of the computation is shifted to the decoder. Since the interframe dependence of the video sequence is exploited only at the decoder, an intraframe encoder can be combined with an interframe decoder. The rate-distortion performance is superior to conventional intraframe coding, but there is still a gap relative to conventional motion-compensated interframe coding. Wyner-Ziv coding is naturally robust against transmission errors and can be used for joint source-channel coding. A Wyner-Ziv MPEG encoder that protects the video waveform rather than the compressed bit stream achieves graceful degradation under deteriorating channel conditions without a layered signal representation.

In wavelet video coding with motion-compensated lifting, the update step typically reverses the motion vectors from the prediction step. Where motion compensation is not invertible, heuristic rules are used for the update step. This paper derives a closed-form expression for the optimal update step for a given general linear prediction step and applies the result to motion-compensated wavelet coding. The analysis justifies using reversed motion vectors, where possible, and yields new results on proper inversion of subpixel motion compensation and optimal treatment of motion discontinuities. A new sparse matrix technique is presented that allows the practical implementation of the optimal update step for motion-compensated wavelet video coding. Experimental results confirm that optimizing the update step improves the rate-distortion performance for a motion-compensated wavelet video coder and provide justification for heuristics used in conventional techniques.

We present a technique for low-complexity rate-distortion (R-D) optimized adaptive video streaming based on the concept of rate-distortion hint track (RDHT). RDHTs store the precomputed characteristics of a compressed media source that are crucial for high performance online streaming but difficult to compute in real time. This enables low-complexity adaptation to variations in transport conditions such as available data rate or packet loss. An RDHT-based streaming system has three components: 1) information that summarizes the R-D attributes of the media; 2) an algorithm for using the RDHT to predict the distortion for a feasible packet schedule; and 3) a method for determining the best packet schedule to adapt the streaming to the communication channel. A family of distortion models, denoted distortion chains, are presented which accurately predict the distortion produced by arbitrary packet loss patterns. Two distortion chain models are examined which lead to two RDHT-based techniques. We evaluate the proposed techniques for two canonical problems in streaming media, adaptation to available data rate and to packet loss. Experimental results demonstrate that for the difficult case of nonscalably coded H.264 video, the proposed systems provide significant performance gains over conventional low-complexity streaming systems, and achieve this gain with a comparable level of complexity making them suitable for online R-D optimized streaming.

Affine motion compensation is combined with long-term memory motion-compensated prediction. The idea is to determine several affine motion parameter sets on subareas of the image. Then, for each affine motion parameter set, a complete reference picture is warped and inserted into the multipicture buffer. Given the multipicture buffer of decoded pictures and affine warped versions thereof, block-based translational motion-compensated prediction and Lagrangian coder control are utilized. The affine motion parameters are transmitted as side information requiring additional bit rate. Hence, the utility of each reference picture and, with that, each affine motion parameter set is tested for its rate-distortion efficiency. The combination of affine and long-term memory motion-compensated prediction provides a highly efficient video compression scheme in terms of rate-distortion performance. The two incorporated multipicture concepts complement each other well providing almost additive rate-distortion gains. When warping the prior decoded picture, average bit-rate savings of 15% against TMN-10, the test model of ITU-T Recommendation H.263, are reported for the case that 20 warped reference pictures are used. When employing 20 warped reference pictures and 10 decoded reference pictures, average bit-rate savings of 24% can be obtained for a set of eight test sequences. These bit-rate savings correspond to gains in PSNR between 0.8-3 dB. For some cases, the combination of affine and long-term memory motion-compensated prediction provides more than additive gains.

We consider the problem of rate-distortion optimized streaming of packetized media over the Internet from a server to a client using rich acknowledgments. Instead of separately acknowledging each media packet as it arrives, the client periodically sends to the server a single acknowledgment packet, denoted rich acknowledgment, that contains information about all media packets that have arrived at the client by the time the rich acknowledgment is sent. Computing the optimal transmission policy for the server involves estimation of the probability that a single packet will be communicated in error as a function of the expected redundancy (or cost) used to communicate the packet. In this paper, we show how to compute this error-cost function, and thereby optimize the server's transmission policy, in this scenario.

When designing a system for video communication over a lossy packet network, it is highly beneficial to have a mechanism for accurately predicting the mean-squared error (MSE) distortion that results from different packet loss patterns. The paper proposes a distortion chains model for accurately predicting the end-to-end distortion for different general packet loss patterns. The performance is examined using JVT/H.264 encoded video sequences and previous frame error concealment. It is shown that, for all tested sequences, the proposed model predicts the total distortion due to a packet loss pattern within a 10% error bound 80% of the time, as compared to the conventional additive approach which achieves the same accuracy less then 40% of the time.

In the current interframe video compression systems, the encoder performs predictive coding to exploit the similarities of successive frames. The Wyner-Ziv theorem on source coding with side information available only at the decoder suggests that an asymmetric video codec, where individual frames are encoded separately, but decoded conditionally (given temporally adjacent frames) could achieve similar efficiency. In the previous work we propose a Wyner-Ziv coding scheme for motion video that uses intraframe encoding instead of interframe decoding. In this paper we improve on our Wyner-Ziv video codec by sending hash codewords of the current frame to aid the decoder in accurately estimating the motion. This allows us to implement a low-delay system where only the previous reconstructed frame is used to generate the side information of a current frame. Simulation results show significant gains above conventional DCT-based intraframe coding. The Wyner-Ziv video codec with hash-based motion compensation at the receiver enables low-complexity encoding while achieving high compression efficiency.

We propose a rate-distortion optimized framework to stream scalable bitstreams of 3-D wavelet video stored at the sender to a remote receiver. Based on the source rate-distortion profiles, the desired playout deadline, transmission rate, and the network characteristics, the receiver issues customized requests throughout the video playout session in order to retrieve the data that minimize the distortion in the reconstructed frames. Rate-distortion optimized data request is formulated as a convex optimization problem. Experimental results show that the proposed scheme improves the video quality by up to 3.1 dB over the heuristic scheme at the same rate, or correspondingly reduces the required the transmission rate by up to 60% for the same quality.

Wc extend recent work on rate-distortion optimized streaming of video to include the case when multiple, independently encoded and packetized versions of the video are available for transmission. While there has been much recent work on the rate-distortion optimized streaming of packetized video, previous work has focussed on layered video encodings and encodings that are comprised of a single set of interdependent packets. In this paper we extend the rate-distortion optimizing packet transmission algorithms, a major benefit of which is that they select the optimal source rate from a rate-scalable encoding on a per-transmission basis, to handle the case of multiple independent encodings, the most ubiquitous form of rate-scalable video in use. In our experimental results, we show up to a 3 dB performance improvement for our multiple-encoding optimizing scheduler over a non-optimizing scheduler.

Image-based rendering data sets, such as light fields, require efficient compression due to their large data size, but also easy random access when rendering from the data set. Efficient compression usually depends upon prediction between images, which creates dependencies between them, conflicting with the requirement of having easy random access. Existing light field coders concentrate either on compression efficiency, or use ad hoc methods to design prediction that balances random access and compression efficiency requirements. In this paper, we study this joint problem of compression efficiency and random access. We propose a model for light field image generation, light field image coding and rendering novel views from these light field images. We present a view-dependent rate-distortion measure that allows us to consider random access and compression efficiency simultaneously. We compare the theoretical results from the model with the experimental results from our DCT-based coder and show that they qualitatively give similar results. Finally, we suggest how. with this model, we can better optimize the prediction dependency structure in our coder for random access and compression efficiency performance.

We present a practical scheme for error-resilient digital video broadcasting, using the Wyner-Ziv coding paradigm. We apply the general framework of systematic lossy source-channel coding to generate a supplementary bitstream that can correct transmission errors in the decoded video waveform up to a certain residual distortion. The systematic portion consists of a conventional MPEG-2 bitstream, which is transmitted over the error-prone channel without forward error correction. The supplementary bitstream is a low rate representation of the transmitted video sequence generated using Wyner-Ziv encoding. We use the received error-prone MPEG-2 prediction error signal as side information to decode the Wyner-Ziv bits. The decoder combines the error-prone side information and the Wyner-Ziv description to yield an improved decoded video signal. Wc describe a system that uses an embedded Wyner-Ziv codec to achieve graceful quality degradation without the need for a layered representation of the video waveform.

For multipath video streaming over ad hoc wireless networks, received video quality is influenced by both the encoder performance and the delayed packet arrivals due to limited bandwidth. We propose a rate allocation scheme to optimize the expected received video quality based on simple models of encoder rate-distortion performance and network rate-congestion tradeoffs. Given the embedded bit-streams of a group of video frames and the cross traffic condition on a given set of paths, a gradient descent method is used to determine the amount of bits to be transmitted over the multiple paths for each frame. Two rate allocation strategies, layered representation and partial repetition are also investigated. Simulation results of video streaming over a 15-node wireless ad hoc network demonstrates the benefit of performing rate allocation optimization over a simple heuristic scheme. It is also shown that while layered representation is more efficient for mild delay constraints, partial repetition is more robust against packet losses.

This work presents the concept of rate-distortion hint track (RDHT), and evaluates two specific implementations of streaming systems that employ RDHT. Using RDHT, low-complexity streaming can be realized for systems that adapt to variations in transport conditions such as bandwidth or packet loss. An RDHT-based streaming system has three components: (1) an R-D hint track; (2) an algorithm for using the RDHT to predict the distortion for different packet schedules; and (3) a method for determining the best packet schedule. Two RDHT-based systems are presented which perform R-D optimized scheduling with dramatically reduced complexity as compared to conventional on-line R-D optimized streaming algorithms. Experimental results demonstrate that for the difficult case of R-D optimized scheduling of non-scalably coded video the proposed systems provide 7-12 dB gain when adapting to a bandwidth constraint and 2-4 dB gain when adapting to random packet loss, both relative to a conventional streaming system that does not take into account the different importance of individual packets.

The paper proposes a receiver-based rate-distortion optimized framework to stream interactively scalable bitstreams of light fields. Based on the desired viewpoints, the predicted future buffer state, the network characteristics, and the target transmission rate, the receiver customizes the data request in order to minimize the distortion in the frames to be rendered. Experimental results show that the proposed framework improves the rendering quality by 1.0-2.8 dB over a heuristic scheme at the same rate. Correspondingly, to achieve the same rendering quality the proposed framework reduces 25-35% of the rate over the heuristic scheme.

We introduce an Internet packet delay and loss model for use in rate-distortion optimized media streaming. Our scheme uses feedback to learn the delay over the channel in the recent past and then finds probability mass functions for delays at later times by using chains of approximated conditional delay distributions. With an Internet delay trace we have collected and a performance metric that we introduce, we show that our scheme is far more accurate than the commonly-used model, which assumes packet delays to be i.i.d. /spl Gamma/-distributed, at predicting arrival outcomes for groups of successively-transmitted Internet packets. In addition, we outline our Linux-based one-way delay trace collection techniques and we show the suitability of the shifted /spl Gamma/ distribution for modeling conditional packet delays over Internet links that include a cable modem last hop.

Streaming prestored video with low latency requires an architecture which does not rely on buffering and retransmissions. We propose a scheme based on multiple description encoding which attempts to maintain a constant video quality despite packet loss, and test its performance on a real-time streaming test-bed. The scheme relies on a low complexity restart mechanism which enhances the inherent robustness of multiple descriptions by efficiently stopping inter-frame error propagation. Our multiple-description-with-restart scheme uses a second version of the video, generated by a different predictive pattern, to break faulty prediction chains. When a loss is detected, a frame from this second bitstream is transmitted and corrects errors on the fly. At the network layer, source routing is performed to take advantage of different network paths. Experiments performed on our prototype streaming system show performance improvements compared to less adaptive schemes.

We analyze the benefits of optimal multi-path routing on video streaming, in a band-limited ad hoc network. In such environments, the actions of each node can potentially impact the overall network conditions. Thus optimal routing solutions which seek to minimize congestion are attractive as they make use of the resources efficiently. For low-latency video streaming, we propose to limit the number of routes to overcome the limitations of such solutions. To predict the performance in terms of rate and distortion, we develop a model which captures the impact of quantization and packet loss on the overall video quality. Simulations are performed to illustrate the advantages of the multi-path congestion-based partitioning scheme and confirm the validity of the model.

Image-based rendering data sets, such as light fields, require efficient compression due to their large data size, but also easy random access when rendering from the data set. Efficient compression usually depends upon prediction between images, which creates dependencies between them, conflicting with the requirement of having easy random access. In this paper we propose to eliminate prediction at the encoder by using Wyner-Ziv coding for compressing the light field images. The images are independently encoded by a Wyner-Ziv encoder. At the receiver, previously reconstructed images are used by the Wyner-Ziv decoder as side information to exploit similarities among images. Simulation results show significant compression performance gains compared to conventional independent image coding while maintaining random access capabilities.

We propose a sender-based rate-distortion optimized framework to stream scalable bitstreams of 3-D wavelet video stored at the sender to a remote receiver. Based on the requests and feedback from the receiver, the source rate-distortion profiles, the desired playout latency and transmission rate, and the network characteristics, the sender optimizes the responses sent to the receiver throughout the video playout session in order to minimize the distortion in the reconstructed frames. Rate-distortion optimized response is formulated as a convex optimization problem, and an offline-computation approach is proposed to further reduce the complexity at the sender. Experimental results show that the proposed sender-based approach outperform the receiver-based approach, and the offline-computation approach very closely approximates the fully-optimized approach.

We introduce a formulation for the rate-distortion optimized transmission scheduling of packetized video that incorporates a new, more accurate model for Internet packet delay and loss. The model assumes that delays at successive transmission times form a 1st order Markov random process. The model uses feedback to learn about delays in the recent past, and finds delay distributions for later transmissions by chaining together approximated conditional delay distributions. In prior work, this model has proved to be more accurate than the iid /spl Gamma/ delay model commonly used for rate-distortion optimized streaming. In this work, we show how to use the new delay and loss model to perform rate-distortion optimized packet transmission scheduling. Our results show a more than 1 dB gain in scheduling performance for our new delay model over the iid /spl Gamma/ model, for streaming simulations conducted with measured Internet delay and loss traces.

Image-based rendering data sets, such as light fields, require efficient compression due to their large data size, but also easy random access when rendering from or streaming the data set. Efficient compression usually depends upon prediction between images, which creates dependencies between them, making random access more difficult. Independent encoding of the images is less efficient but provides random access, and in many cases is superior to predictive coding when considering the rate-distortion performance for certain viewing trajectories of the light field. In this paper, we describe a method which can obtain the best of both worlds: random access to any image; and compression efficiency, through predictive coding. We store multiple representations of each light field image, and decode using the appropriate representation depending on the available images that are already decoded. To eliminate prediction mismatch between the representations, we employ the idea of "SP-frames" from video coding. This allows us to generate identical reconstruction images from all representations. Our experimental results show a significant improvement in terms of view-trajectory-dependent rate-distortion performance over independent coding of the images.

Recent research on multimedia scheduling has focused on minimizing the rate-distortion cost of transmission policies. This tradeoff only partially reflects the network congestion a media stream may generate on bandwidth-limited channels. We introduce the concept of congestion-distortion optimized streaming and propose a scheduler which attempts to minimize the Lagrangian cost of end-to-end delay and media distortion. Experiments for video on a simulated network illustrate the performance of the scheduler. Compared to a state-of-the-art scheduler, the proposed algorithm reduces end-to-end delay by approximately 50% while improving the video quality by up to 3 dB.

We propose a cross-layer design framework for supporting delay-critical traffic over ad hoc wireless networks and analyze its benefits for video streaming. In this framework, link capacities and traffic flows are jointly allocated to minimize the congestion experienced by video packets. The optimal solution, calculated via time sharing among different transmission schemes, concentrates resources only on active links. Experimental results on a simulated network illustrate the advantages of cross-layer design over another method based on oblivious layers. With one path, the cross-layer approach yields a 10-fold gain in supported data rate or equivalently 8.5 dB improvement in PSNR of achievable received video quality. Using 3 paths, the gain is 3-fold in rate or 5 dB in video quality. While multipath routing is essential to high data rate in oblivious-layered design, cross-layer design achieves efficient resource utilization regardless of the number of routes.

In current interframe video compression systems, the encoder performs predictive coding to exploit the similarities of successive frames. The Wyner-Ziv Theorem on source coding with side information available only at the decoder suggests that an asymmetric video codec, where individual frames are encoded separately, but decoded conditionally (given temporally adjacent frames) could achieve similar efficiency. We propose a transformdomain Wyner-Ziv coding scheme for motion video that uses intraframe encoding, but interframe decoding. In this system, the transform coefficients of a Wyner-Ziv frame are encoded independently using a scalar quantizer and turbo coder. The decoder uses previously reconstructed frames to generate side information to conditionally decode the Wyner-Ziv frames. Simulation results show significant gains above DCT-based intraframe coding and improvements over the pixel-domain Wyner-Ziv video coder.

We consider an unconventional procedure for communicating to the server the receipt of media packets for Internet video streaming. Instead of separately acknowledging each media packet as it arrives, we periodically send to the server a single acknowledgment packet, denoted rich acknowledgment, that contains information about all media packets that have arrived at the client by the time the rich acknowledgment is sent. We investigate rate-distortion optimized sender-driven streaming that employs rich acknowledgments. Performance gains of up to 1.3 dB for streaming packetized video content are observed over rate-distortion optimized sender-driven systems that employ conventional acknowledgments.

A rate-distortion optimized scheme for interactive light field streaming is proposed. The light field data set is transformed into blocks of wavelet coefficients; each block is coded as a scalable bitstream and stored at the sender. To render a frame, the receiver issues a request for relevant data. Based on the request, the estimated state of the data already at the receiver, the network characteristics, and the desired transmission rate, the sender customizes the outgoing packets in order to minimize the distortion experienced at receiver. Experimental results show that the proposed rate-distortion optimized scheme improves the rendering quality by 0.5~2.1 dB in PSNR over a heuristic scheme at the same rate. Alternatively, it reduces the required bit-rate by 10%~25% over the heuristic scheme at the same rendering quality.

This paper investigates video coding with wavelet transforms applied in the temporal direction of a video sequence. The wavelets are implemented with the lifting scheme in order to permit motion compensation between successive pictures. We improve motion compensation in the lifting steps and utilize complementary motion-compensated signals. Similar to superimposed predictive coding with complementary signals, this approach improves compression efficiency. We investigate experimentally and theoretically complementary motion-compensated signals for lifted wavelet transforms. Experimental results with the complementary motion-compensated Haar wavelet and frame-adaptive motion compensation show improvements in coding efficiency of up to 3 dB. The theoretical results demonstrate that the lifted Haar wavelet scheme with complementary motion-compensated signals is able to approach the bound for bit-rate savings of 2 bits per sample and motion-accuracy step when compared to optimum intra-frame coding of the input pictures.

We present a novel scheme for error-resilient digital video broadcasting,using the Wyner-Ziv coding paradigm. We apply the general framework of systematic lossy source-channel coding to generate a supplementary bitstream that can correct transmission errors in the decoded video waveform up to a certain residual distortion. The systematic portion consists of a conventional MPEG-coded bitstream, which is transmitted over the error-prone channel without forward error correction.The supplementary bitstream is a low rate representation of the transmitted video sequence generated using Wyner-Ziv encoding. We use the conventionally decoded error-concealed MPEG video sequence as side information to decode the Wyner-Ziv bits. The decoder combines the error-prone side information and the Wyner-Ziv description to yield an improved decoded video signal. Our results indicate that, over a large range of channel error probabilities, this scheme yields superior video quality when compared with traditional forward error correction techniques employed in digital video broadcasting.

When media is streamed over best-effort networks, media data is buffered at the client to protect against playout interruptions due to packet losses and random delays. While the likelihood of an interruption decreases as more data is buffered, the latency that is introduced increases. In this paper we show how adaptive media playout (AMP), the variation of the playout speed of media frames depending on channel conditions, allows the client to buffer less data, thus introducing less delay, for a given buffer underflow probability. We proceed by defining models for the streaming media system and the random, lossy, packet delivery channel. Our streaming system model buffers media at the client, and combats packet losses with deadline-constrained automatic repeat request (ARQ). For the channel, we define a two-state Markov model that features state-dependent packet loss probability. Using the models, we develop a Markov chain analysis to examine the tradeoff between buffer underflow probability and latency for AMP-augmented video streaming. The results of the analysis, verified with simulation experiments, indicate that AMP can greatly improve the tradeoff, allowing reduced latencies for a given buffer underflow probability.

Two separate applications of Wyner-Ziv coding of motion video coding are considered. The Wyner-Ziv theorem on source coding with side information available only at the decoder suggests that an asymmetric video codec, where individual frames are encoded separately, but decoded conditionally could achieve efficiency comparable to current interframe video compression systems. First results on the Wyner-Ziv coding scheme for motion video are reported that use interframe encoding, but interframe decoding. Secondly, Wyner-Ziv coding for the transmission of compressed video over an error-prone channel is applied. This coding scheme is used to generate a supplementary bit stream, which contains a coarsely quantized representation of the transmitted video signal. Using the conventionally decoded, error-concealed video signal as side information to decode the Wyner-Ziv bits, the transmission errors in the decoded video waveform are corrected up to a certain residual distortion, significantly improving the visual quality of the decoded video.

The diversity for media streaming in a rate-distortion optimization framework was considered. A sender-driven transmission scenario was also investigated. Diversity was achieved by using multiple transmission paths over the network. The proposed framework enables the sender to decide at every instant which packets, if any, to transmit and over which transmission paths in order to meet a rate constraint while minimizing the end-to-end distortion. Experimental results demonstrate the benefit of exploiting packet diversity in rate-distortion optimized sender-driven streaming of packetized media.

The problem of designing optimal quantizers for distributed source coding is addressed. The generality of this formulation includes both the symmetric and asymmetric scenarios, together with a number of coding schemes, such as ideal coding achieving a rate equal to the joint conditional entropy of the quantized sources given the side information. The paper shows the optimality conditions that quantizers must satisfy, and generalizes the Lloyd algorithm for their design. Experimental results are shown for the Gaussian scalar asymmetric case.

We propose a novel approach for light field compression that incorporates disparity compensation into 4D wavelet coding using disparity-compensated lifting. With this approach, we obtain the benefits of wavelet coding, including compression efficiency and scalability in all dimensions. Additionally, our proposed approach solves the irreversibility limitations of previous wavelet coding approaches. Experimental results show that the compression efficiency of the proposed technique outperforms current state-of-the-art wavelet coding techniques by a wide margin.

Video communication is often afflicted by various forms of losses, such as packet loss over the Internet. The paper examines the question of whether the packet loss pattern, and in particular the burst length, is important for accurately estimating the expected mean-squared error distortion. Specifically, we (1) verify that the loss pattern does have a significant effect on the resulting distortion, (2) explain why a loss pattern, for example a burst loss, generally produces a larger distortion than an equal number of isolated losses, and (3) propose a model that accurately estimates the expected distortion by explicitly accounting for the loss pattern, inter-frame error propagation, and the correlation between error frames. The accuracy of the proposed model is validated with JVT/H.26L coded video and previous frame concealment, where for most sequences the total distortion is predicted to within /spl plusmn/0.3 dB for burst loss of length two packets, as compared to prior models which underestimate the distortion by about 1.5 dB. Furthermore, as the burst length increases, our prediction is within /spl plusmn/0.7 dB, while prior models degrade and underestimate the distortion by over 3 dB.

A novel scheme for error-resilient digital video broadcasting, using Wyner-Ziv coding, is presented in this paper. We apply the general framework of systematic lossy source-channel coding to generate a supplementary bitstream that can correct transmission errors in the decoded video waveform up to a certain residual distortion. The systematic portion consists of a conventional MPEG-coded bitstream, which is transmitted over the error-prone channel without any forward error correction. The supplementary bitstream is a low rate representation of the transmitted video sequence generated using Wyner-Ziv encoding. We use the conventionally decoded error-concealed MPEG video sequence as side information to decode the Wyner-Ziv bits. The decoder combines the error-prone side information and the Wyner-Ziv description to yield an improved decoded video signal. We show how this scheme can be used to build a system which achieves graceful degradation without the need of a layered representation of the video waveform.

In current interframe video compression systems, the encoder performs predictive coding to exploit the similarities of successive frames. The Wyner-Ziv theorem on source coding with side information available only at the decoder suggests that an asymmetric video codec, where individual frames are encoded separately, but decoded conditionally (given temporally adjacent frames) achieves similar efficiency. We report results on a Wyner-Ziv coding scheme for motion video that uses intraframe encoding, but interframe decoding. In the proposed system, key frames are compressed by a conventional intraframe codec and in-between frames are encoded using a Wyner-Ziv intraframe coder. The decoder uses previously reconstructed frames to generate side information for interframe decoding of the Wyner-Ziv frames.

We consider diversity for media streaming in a receiver-driven rate-distortion optimization framework. Diversity is achieved by requesting media packets from multiple servers. A framework is proposed that enables the receiver to decide at every instant which packets, if any, to request for transmission and from which servers in order to meet a rate constraint while minimizing the end-to-end distortion. Experimental results demonstrate the benefit of exploiting server diversity in rate-distortion optimized receiver-driven streaming of packetized media.

We propose a method of using shape adaptation for compression of light fields of 3D objects. Shape adaptation is incorporated into two light field coders, both applying disparity compensation with an explicit geometry model, to improve the compression efficiency. The shape information can be derived at the decoder from an accurate geometry model. If the available geometry is inaccurate, we propose to code the exact 2D shapes with the aid of the approximate geometry. Experiments show that shape adaptation greatly improves the compression performance of both coders.

We extend a recently-proposed framework for the rate-distortion optimized transmission of packetized media. The original framework assumed that each packet has a single arrival deadline and that a packet is useless if it arrives after its deadline. In practice, however, packets may be associated with multiple deadlines. Examples include the case of compressed video that uses bi-directional prediction and the case of decoders that can recover from late packet arrivals through the accelerated retroactive decoding of the dependency chain. We extend the original framework to consider multiple deadlines. In our experimental results for the case of the accelerated retroactive decoding of late packets, the multiple-deadline formulation yields up to a 3.15 dB improvement in rate-distortion performance compared to the original, single-deadline formulation. The results indicate, furthermore, that accelerated retroactive decoding offers significant benefit only when coupled with a scheduler that considers multiple deadlines.

An improved, prescient, scheme to deliver preencoded video streams at very low latency is presented. We dynamically manage the prediction dependency for a group of packets using a rate-distortion (R-D) optimization framework that adapts to the channel, so that the expected end-to-end distortion is minimized under a given rate constraint. In our system, the R-D characteristics of each prediction mode are precomputed at compression time and stored in an R-D preamble along with the multiple compressed versions of the stream. The distortion in the preamble is estimated using an accurate loss-distortion model, and the optimal prediction modes are computed with an iterative descent algorithm. Complexity is reduced at streaming time by using the preamble to compute the optimal modes instead of actually compressing the video. Experiments demonstrate that the proposed prescient scheme provides significant performance gains over simple intra-insertion, and consistent bitrate savings compared to the greedy scheme.

We propose a framework for the streaming of light fields over a lossy error-prone packet network. This system is optimized for the end-user according to a rate-distortion criterion. We build upon recent rate-distortion optimized streaming work for audio and video data. We extend this work to light field image data by introducing view-dependent distortion, multiple playout deadlines, and state-based distortion. In our experimental results, the rate-distortion optimized framework has a bit-rate reduction of up to 75% over a heuristic rule-based system.

Packet path diversity is one of the recent advances in network-adaptive video streaming. In this paper we first examine two specific techniques for video streaming that exploit diversity to achieve improved performance. The first technique uses a framework for rate-distortion optimized scheduling of the packet transmissions over the available network paths. The second technique exploits feedback and channel probing to determine which network path should be used for transmission and to adapt the source encoding of the video to mitigate error propagation effects. In the final section, we compare the performance of these two techniques by analyzing experimental results and discuss their respective advantages and drawbacks.

We propose a novel approach for light field compression that incorporates disparity compensation into 4-D wavelet coding using disparity-compensated lifting. With this approach, we obtain the benefits of wavelet coding, including compression efficiency and scalability in all dimensions. Additionally, our proposed approach solves the irreversibility limitations of previous wavelet coding approaches. Experimental results show that the compression efficiency of the proposed technique outperforms current state-of-the-art wavelet coding techniques by a wide margin.

Low latency video applications need to incorporate a high level of error resiliency and of error concealment to provide acceptable quality. We investigate how to combine the benefits of multiple stream coding and multiple path transmission for this purpose. We present a transmission strategy for multiple description coded video which maintains the inherent error resiliency of the encoding in the case of transmission over bursty channels. Through the analysis of feedback and through rate-distortion optimized channel probing, this strategy determines which channels should be used to take advantage of path diversity. At the encoder, a restart scheme stops error propagation by selecting references in error-free streams. Experiments demonstrate significant gains over other schemes such as video redundancy coding.

In this paper, we examine the performance of specific implementations of multiple description coding and of layered coding for video streaming over error-prone packet switched networks. We compare their performance using different transmission schemes with and without network path diversity. It is shown that given the specific implementations there is a large variation in relative performance between multiple description coding and layered coding depending on the employed transmission scheme. For scenarios where the packet transmission schedules can be optimized in a rate-distortion sense, layered coding provides a better performance. The converse is true for scenarios where the packet schedules are not rate-distortion optimized.

This paper reviews recent advances in using B pictures in the context of the draft H.264/AVC video-compression standard. We focus on reference picture selection and linearly combined motion-compensated prediction signals. We show that bidirectional prediction exploits partially the efficiency of combined prediction signals whereas multihypothesis prediction allows a more general form of B pictures. The general concept of linearly combined prediction signals chosen from an arbitrary set of reference pictures improves the H.264/AVC test model TML-9 which is used in the following. We outline H.264/AVC macroblock prediction modes for B pictures, classify them into four groups and compare their efficiency in terms of rate-distortion performance. When investigating multihypothesis prediction, we show that bidirectional prediction is a special case of this concept. Multihypothesis prediction allows also two combined forward prediction signals. Experimental results show that this case is also advantageous in terms of compression efficiency. The draft H.264/AVC video-compression standard offers improved entropy coding by context-based adaptive binary arithmetic coding. Simulations show that the gains by multihypothesis prediction and arithmetic coding are additive. B pictures establish an enhancement layer and are predicted from reference pictures that are provided by the base layer. The quality of the base layer influences the rate-distortion trade-off for B pictures. We demonstrate how the quality of the B pictures should be reduced to improve the overall rate-distortion performance of the scalable representation.

To store and transmit the large amount of image data necessary for Image-based Rendering (IBR), efficient coding schemes are required. This paper presents two different approaches which exploit three-dimensional scene geometry for multi-view compression. In texture-based coding, images are converted to view-dependent texture maps for compression. In model-aided predictive coding, scene geometry is used for disparity compensation and occlusion detection between images. While both coding strategies are able to attain compression ratios exceeding 2000:1, individual coding performance is found to depend on the accuracy of the available geometry model. Experiments with real-world as well as synthetic image sets show that texture-based coding is more sensitive to geometry inaccuracies than predictive coding. A rate-distortion theoretical analysis of both schemes supports these findings. For reconstructed approximate geometry models, model-aided predictive coding performs best, while texture-based coding yields superior coding results if scene geometry is exactly known.

The quality of service limitation of today's Internet is a major challenge for real-time voice communications. Excessive delay, packet loss, and high delay jitter all impair the communication quality. A new receiver-based playout scheduling scheme is proposed to improve the tradeoff between buffering delay and late loss for real-time voice communication over IP networks. In this scheme the network delay is estimated from past statistics and the playout time of the voice packets is adaptively adjusted. In contrast to previous work, the adjustment is not only performed between talkspurts, but also within talkspurts in a highly dynamic way. Proper reconstruction of continuous playout speech is achieved by scaling individual voice packets using a time-scale modification technique based on the Waveform Similarity Overlap-Add (WSOLA) algorithm. Results of subjective listening tests show that this operation does not impair audio quality, since the adaptation process requires infrequent scaling of the voice packets and low playout jitter is perceptually tolerable. The same time-scale modification technique is also used to conceal packet loss at very low delay, i.e., one packet time. Simulation results based on Internet measurements show that the tradeoff between buffering delay and late loss can be improved significantly. The overall audio quality is investigated based on subjective listening tests, showing typical gains of 1 on a 5-point scale of the Mean Opinion Score.

We show that turbo codes can come close to the Slepian-Wolf bound in lossless distributed source coding. In the asymmetric scenario considered, X and Y are statistically dependent signals and X is encoded with no knowledge of Y. However, Y is known as side information at the decoder. We use a system based on turbo codes to send X at a rate close to H(X|Y). We apply our system to binary sequences and simulations show performance close to the information-theoretic limit. For distributed source coding of Gaussian sequences, our results show significant improvement over previous work. The scheme also performs well for joint source-channel coding.

In geometry-aided light field compression, a geometry model is used for disparity-compensated prediction of light field images from already encoded light field images. This geometry model, however, may have limited accuracy. We present an algorithm that refines a geometry model to improve the overall light field compression efficiency. This algorithm uses an optical-flow technique to explicitly minimize the disparity-compensated prediction error. Results from experiments performed on both real and synthetic data sets show bit-rate reductions of approximately 10% using the improved geometry model over a silhouette-reconstructed geometry model.

This paper discusses the efficiency of a compression scheme for video sequences that jointly encodes groups of pictures. Our approach, motion-compensated transform coding, applies a KLT to decorrelate a set of motion-compensated pictures for efficient encoding. The theoretical investigation utilizes a signal model for inaccurate motion compensation and provides a performance comparison to motion-compensated prediction. We discuss the influence of motion accuracy, residual noise, and the correlation of displacement errors dependent on the number of coded pictures.

Motion-compensated prediction based on multiple previous or future frames can enhance the compression efficiency of video coding. Multi-frame prediction can be applied as an extension to P-pictures, but also to B-pictures in the form of multi-hypothesis prediction. We review recent advances, several of which have been embraced by the ITU-T Rec. H.263 and the emerging JVT/H.26L standard, jointly developed by ITU-T and ISO/IEC MPEG. Already, JVT/H.26L video outperforms MPEG-2 by a factor greater than 2/spl times/. These recent developments could play a significant role in future digital set-top boxes.

We review recent advances in channel-adaptive video streaming. Adaptive media playout at the client can be used to reduce receiver buffering and therefore average latency, and provide a limited rate scalability. Rate-distortion optimized packet scheduling determines the best packet to send given the distortion reduction associated with sending that packet, interpacket dependencies, and the success of past transmissions. Channel-adaptive packet dependency control can greatly improve the error-robustness of streaming video and reduce or eliminate the need for packet retransmissions. Finally we consider three architectures for wireless video streaming and discuss the utility of the discussed techniques for each architecture.

This paper presents a robust scalable video coding scheme with leaky prediction, suitable for time-varying error-prone channels, such as the Internet or wireless channels. The proposed scheme shows how leaky prediction can be utilized for efficient motion-compensated video coding, as well as for robust video transmission over packet erasure networks. We show that leaky prediction with a temporal prediction coefficient of less than one increases the robustness in the presence of errors significantly, while introducing only a small loss in coding efficiency in the error-free case. The proposed scalable video coding scheme is combined with a prioritized ARQ scheme in which higher priority is assigned to more important layers. Our simulation results demonstrate graceful degradation with an increasing error rate over wireless links.

We propose a new scheme for streaming media systems that combines adaptive media playout (AMP) with rate-distortion (R-D)optimized packet transmission. AMP, the client-controlled, adaptive modification of the media playout rate, allows us to flexibly adjust the playout deadlines of individual packets, and can therefore reduce reconstruction distortion. This added flexibility incurs a subjective cost, however. We introduce functions that assess the subjective cost of a schedule of playout rate modifications, and we show how to optimize the schedule with respect to these costs and distortion. Because the optimal playout rate schedule and the R-D optimal transmission schedule are interdependent, we solve the two problems jointly. In simulations that model a receiver-driven scenario, results for a short media clip show a more than 2 dB improvement in mean PSNR for R-D optimized transmission scheduling combined with a moderate amount of AMP, over R-D optimized transmission scheduling alone.

Today's Internet video streaming systems employ buffering and multiple retransmissions to guarantee the correct reception of each packet, which leads to high latency in media delivery. In this work, a novel scheme of dynamic management of the dependency across packets is proposed using optimal reference picture selection at the frame level that adapts to the channel. The optimal selection of the reference picture is achieved with a rate-distortion framework, which minimizes the expected end-to-end distortion given a rate constraint. The expected distortion is calculated based on an accurate binary tree modeling with the effects of channel loss and error concealment taken into account. Experiments demonstrate that the proposed :scheme provides significant performance gains over a simple INTRA-insertion scheme. The increased error-resilience eliminates the need of retransmission, which makes it possible to reduce the latency from 10-15 seconds to a few hundred milliseconds, with similar video quality maintained.

In current light field compression algorithms, geometry information is critical for efficient compression of light field image data. Inaccuracies in the geometry can greatly affect the compression efficiency. In this paper, we present a theoretical framework with which we can analyze and understand the effects of geometry inaccuracy on the compression efficiency of a light field coder. This framework combines ideas from statistical signal processing and rate-distortion theory. We demonstrate using simulations that the theory qualitatively matches the actual results of light field coding algorithms.

Streaming media systems buffer media data at the client to improve reconstruction quality at the cost of latency. Reconstruction quality may be further improved with rate-distortion optimized packet transmission. In this paper we show how the tradeoff between buffering latency and reconstruction quality can be improved with adaptive media playout (AMP) - the client-controlled manipulation of the playout speeds of media frames. We then show how to incorporate AMP into an existing framework for rate-distortion optimized packet transmission. The resulting receiver-driven scheme jointly optimizes packet transmissions and playout speeds with respect to rate, distortion and the subjective cost of playout speed variations. Results for a short media clip show a more than 2 dB improvement in mean PSNR for R-D optimized transmission combined with a moderate amount of AMP, over R-D optimized transmission alone.

We describe a real-time LAN-based testbed that allows us to investigate the behavior of streaming media applications under various network conditions. For commercially available streaming media applications, we are interested to see how they perform over next-generation wireline and wireless networks. For future streaming media applications, the testbed is an invaluable tool for the development and verification of new algorithms. Our testbed implementation is based on Linux Divert Sockets and supports a straightforward integration of various packet erasure and delay models. Individual IP-packets are diverted to a user process where they are delayed or deleted according to the desired channel model. The testbed has been used to investigate the flow-control behavior of existing streaming media systems over wireless networks. Our experiments confirm that flow-control algorithms that consider lost packets to be the result of network congestion, as employed today in wireline streaming, are not suited for wireless networks, where loss is mainly due to link impairments.

Today's Internet video streaming systems employ buffering and retransmission to guarantee the correct reception of each packet. This leads to high latency in media delivery. In this paper, we present an efficient low-latency Internet video streaming system that does not require retransmission of lost packets. We pre-store multiple representations of certain frames on the server such that a representation using a more reliable reference frame will be selected and sent during transmission. The potential mismatch error during bitstream assembly at transmission is avoided by using a novel layered coding structure with coding restrictions. The optimal picture type is determined within a rate-distortion framework during pre-encoding and transmission, adapting to the channel, so that the expected end-to-end distortion is minimized under the given rate constraint. The expected distortion is calculated based on an accurate binary tree modeling with the effects of channel loss and error concealment taken into account. Experiments demonstrate that the proposed scheme provides significant performance gains over a simple INTRA-insertion scheme. The increased error-resilience eliminates the need for retransmission, which allows to reduce the latency of streaming from 10-15 seconds to a few hundred milliseconds, with good video quality maintained.

In this paper we argue that biological vision and electronic image acquisition share common principles despite their vastly different implementations. These shared principles are based on the need to acquire a common set of input stimuli as well as the need to generalize from the acquired images. Two related principles are discussed in detail, namely, multiple parallel image representations and the use of dedicated local memory in various stages of acquisition and processing. We review relevant literature in visual neuroscience and image systems engineering to support our argument. Particularly, the paper discusses multiple capture image acquisition, with applications such as dynamic range, field-of-view, or depth-of-field extension. Finally, as an example, a novel multiple-capture-single-image complementary metal-oxide-semiconductor sensor is presented. This sensor illustrates the principles that are shared among biological vision and image acquisition.

This paper investigates linearly combined motion-compensated signals for video compression. In particular, we discuss multiple motion-compensated signals that are jointly estimated for efficient prediction and video coding. First, we extend the wide-sense stationary theory of motion-compensated prediction (MCP) for the case of jointly estimated prediction signals. Our theory suggests that the gain by multihypothesis MCP is limited and that two jointly estimated hypotheses provide a major portion of this achievable gain. In addition, the analysis reveals a property of the displacement error of jointly estimated hypotheses. Second, we present a complete multihypothesis codec which is based on the ITU-T Recommendation H.263 with multiframe capability. Multiframe motion compensation chooses one prediction signal from a set of reference frames, whereas multihypothesis prediction chooses more than one for the linear combination. With our scheme, the time delay associated with B-frames is avoided by choosing more than one prediction signal from previously decoded pictures. Experimental results show that, multihypothesis prediction improves significantly coding efficiency by utilizing variable block size and multiframe motion compensation. We show that variable block size and multihypothesis prediction provide gains for different scenarios and that multiframe motion compensation enhances the multihypothesis gain. For example, the presented multihypothesis codec with ten reference frames improves coding efficiency by up to 2.7 dB when compared to the reference codec with one reference frame for the set of investigated test sequences.

The paper presents a model for watermarking and some attacks on watermarks. Given the watermarked signal, the so-called Wiener attack performs minimum mean-squared error (MMSE) estimation of the watermark and subtracts the weighted MMSE estimate from the watermarked signal. Under the assumption of a fixed correlation detector, the attack is shown to minimize the expected correlation statistic for the same attack distortion among linear, shift-invariant filtering attacks. It also leads to the idea of energy-efficient watermarking: watermarking that resists MMSE estimation as much as possible, and provides a meaningful way to evaluate robustness. The paper shows that energy-efficient watermarks must satisfy a power-spectrum condition (PSC), which states that the watermark's power spectrum should be directly proportional to the original signal's. PSC-compliant watermarks are proven to be most robust. Experiments with signal models and natural images demonstrate that watermarks that do not closely fulfill the PSC are vulnerable to the Wiener attack, while PSC-compliant watermarks are highly resistant to it. These theoretical and experimental results justify prior heuristic arguments that, for maximum robustness, a watermark should be closely matched to the spectral content of the original signal. The results also discourage the use of watermarks that do not approximately satisfy the PSC.

Abstract Despite the well‐known challenges of variations in throughput, delay, and packet loss over the Internet, video streaming has experienced phenomenal growth, owing to the extensive research in video coding and transmission. In this paper, we review several recent advances for channel‐adaptive video streaming that, we believe, will benefit the design of video streaming systems in the future. Employed in different components of the system, these techniques have the common objective of providing efficient, robust, scalable, and low‐latency streaming video. Firstly, by allowing the client to control the rate at which it consumes data, adaptive media playout can be used to reduce receiver buffering and therefore average latency, and provide limited rate scalability. Secondly, rate‐distortion optimized packet scheduling, a transport technique, provides a flexible framework to determine the best packet to send, given the channel behaviors, the packets' deadlines, their transmission histories, the distortion reduction associated with sending each packet, and the interpacket dependencies. Thirdly, at the source encoder, channel‐adaptive packet‐dependency control can greatly improve the error resilience of streaming video and reduce latency. Finally, we address the specific additional challenges for wireless video streaming. We consider three architectures for wireless video and discuss the utility of the reviewed techniques for each architecture. Copyright © 2002 John Wiley & Sons, Ltd.

Multihypothesis motion-compensating predictors combine several motion-compensated signals to predict the current frame of a video signal. This paper applies the wide-sense stationary theory of multihypothesis motion compensation for hybrid video codecs to multihypothesis motion estimation. This allows us to study the influence of the displacement error correlation on the efficiency of multihypothesis motion compensation. Reducing the displacement error correlation between the hypotheses decreases the variance of the multihypothesis prediction error. We derive a property for the displacement error correlation coefficient for an optimal multihypothesis motion estimator in the mean squared error sense. We observe for the wide-sense stationary model that jointly optimal motion estimation improves the prediction performance and reduces the prediction error variance up to 12 dB per accuracy refinement step compared to 6 dB per accuracy refinement step for uncorrelated displacement errors. Consequently, the gain of multihypothesis motion-compensated prediction with jointly optimal motion estimation over motion-compensated prediction increases by improving the accuracy of each hypothesis. We also discuss the combination of hypotheses with additive noise and extend the predictor by the optimum Wiener filter.

To prevent image manipulations and fraudulent use of modified images, the embedding of semi-fragile digital watermarks into image data has been proposed. The watermark should survive modifications introduced by random noise or compression, but should not be detectable from non-authentic regions of the image The original image cannot be used by the watermark detector to verify the authenticity of the image. In this paper, we investigate the application of a recently developed quantization based watermarking scheme to image authentication. The watermarking technology, called Scalar Costa Scheme (SCS), allows reliable blind watermark detection from a small number of pixels, and thus enables the detection of local modifications to the image content.

A new receiver-based playout scheduling scheme is proposed, which estimates the network delay from past statistics and adaptively adjusts the playout time of the voice packets. In contrast to previous work, the adjustment is not only performed in between talkspurts, but also within the talkspurts in a highly dynamic way. Proper reconstruction of continuous output speech is achieved by scaling individual voice packets using a time-scale modification technique which modifies the rate of playout while preserving voice pitch. Subjective listening tests show that this operation does not impair the audio quality. Simulation results based on Internet measurement indicate that buffering delay and loss rate can be significantly reduced by adaptive scheduling.

Summary form only given, as follows. Mobile video systems face particularly challenging problems due to the hostile nature of the mobile radio channel and the very low bit-rate available. For the fading channel, the Shannon separation principle does not hold, and hence source and channel coding should be considered jointly. This talk reviews some advances in our work on joint optimization of video coding and error control schemes for the mobile radio channel. As a new formal framework for end-to-end optimization, the so-called distortion-distortion-function (DDF) is introduced that shows the distortions introduced by source coding vs. the distortions resulting from channel errors for varying bit allocation between source and channel coding. We show the impact of various error-resiliency techniques on the DDF, such as motion-compensated concealment, increasing the frequency of synchronization words in the bit-stream, or increasing the percentage of intra-coded blocks. We show that for increasing burstiness of channel errors, the importance of an error-resilient decoder increases, while the effectiveness of FEC decreases. Channel-adaptive source coding is shown to be a powerful technique, if channel feedback can be incorporated into the source coder. Finally we address techniques that take advantage of layered scalable representations of the video signal. In order to achieve unequal error protection of the layers, we discuss FEC across IP packets and receiver-driven adaptive pre-etching techniques. Such techniques can be advantageously combined with proxy servers for mobile multimedia access.

Network variations in video streaming require sufficient data to be prebuffered at the client prior to playout. This receiver buffer prevents the display process from starvation in case of network congestion. Prebuffering, however, is also responsible for the major part of the delay between requesting a media stream and playing it at the receiver. We show how adaptive media playout can be employed to reduce the delay introduced by the receiver buffer while preserving the same resilience against buffer underflow as in non-adaptive media playout. For adaptive media playout we adjust the playout speed of the media packets depending on the condition of the channel and the current client buffer fullness. We employ a two-state Markov channel model to analyze the buffer underflow-delay trade-off for our adaptive playout strategy and show that for typical parameters the average end-to-end delay can be reduced by 1 to 2 seconds.

Applications like distance learning and teleconferencing often require compression of images that contain both text and graphics. Because text and graphics have different properties, a compression scheme can benefit by treating the textual and graphical portions of such compound images separately. In this paper, we propose new methods, called transform coefficient likelihood (TCL) schemes, for separating the textual and graphical portions of a compound image. TCL schemes examine the DCT coefficient values of an 8/spl times/8 block. For each coefficient, they refer to stored histograms that give the likelihood that a certain value occurs in a text block, or in a graphics block. They then examine the differences in these two likelihoods over all the coefficients in the block to decide whether it contains text or graphics. Experimental results show that the best TCL methods significantly outperform previously proposed techniques.

Multi-view image coding benefits from knowledge of the depicted scene's 3D geometry. To exploit geometry information for compression, two different approaches can be distinguished. In texture-based coding, images are converted to texture maps prior to compression. In image-based predictive coding, geometry is used for disparity compensation and occlusion detection between images. Coding performance of both approaches depends on the accuracy of the available geometry model. Texture-based and image-based coding are compared with regard to the influence of geometry accuracy on coding efficiency. The results are theoretically explained. Experiments with natural as well as synthetic image sets show that texture-based coding is more sensitive to small geometry inaccuracies than image-based coding. For approximate geometry models, image-based coding performs best, while texture-based coding yields superior coding results if scene geometry is exactly known.

In this paper, we describe a multi-hypothesis prediction technique for disparity-compensated light field compression. Multi-hypothesis prediction has been used extensively in video compression. In this work, we apply multi-hypothesis prediction to the problem of light field compression. Most current techniques for light field compression utilize some form of disparity compensation with one hypothesis. We demonstrate that a multi-hypothesis approach, where two hypotheses are used, improves the overall efficiency of a light field coder. Our experimental results show an image quality gain of up to 1 dB in PSNR on our test data sets.

Lagrangian coder control with parameter choice is presented that lead to the creation of the new hybrid video coder specifications TMN-10 for H.263 and TML for H.26L. An efficient approach for the determination of the encoding parameters is developed. It is shown by means of experimental results that the Lagrange multiplier for the macroblock mode decision corresponds to the negative slope of the distortion-rate curve of the prediction error coding. This distortion-rate curve is parameterized by the quantization parameter of the DCT coefficients motivating the established dependency with the Lagrange multiplier.

The quality of real-time voice communication over best-effort networks is mainly determined by the delay and loss characteristics observed along the network path. Excessive playout buffering at the receiver is prohibitive and significantly delayed packets have to be discarded and considered as late loss. We propose to improve the tradeoff among delay, late loss rate, and speech quality using multi-stream transmission of real-time voice over the Internet, where multiple redundant descriptions of the voice stream are sent over independent network paths. Scheduling the playout of the received voice packets is based on a novel multi-stream adaptive playout scheduling technique that uses a Lagrangian cost function to trade delay versus loss. Experiments over the Internet suggest largely uncorrelated packet erasure and delay jitter characteristics for different network paths which leads to a noticeable path diversity gain. We observe significant reductions in mean end-to-end latency and loss rates as well as improved speech quality when compared to FEC protected single-path transmission at the same data rate. In addition to our Internet measurements, we analyze the performance of the proposed multi-path voice communication scheme using the ns network simulator for different network topologies, including shared network links.

We propose multi-stream transmission of real-time voice over best-effort packet networks such as today's Internet, where multiple redundant descriptions of the voice stream are sent over independent network paths. At the receiver, multi-stream adaptive playout scheduling is employed to improve the tradeoff among delay, late loss rate, and speech quality. Experiments over the Internet suggest largely uncorrelated statistical characteristics, such as erasure probability and delay jitter, for different network paths, which leads to a noticeable path diversity gain. We have obtained significant reductions in mean end-to-end latency and loss rates compared to FEC protected single-path transmission at the same data rate. The speech quality perceived by the receiver is evaluated using the recently standardized objective quality measure PESQ. In our experiments, we observe gains of more than 0.4 PESQ score for voice transmission with packet path diversity.

It was shown previously that, in some situations, blind watermarking can perform as well as watermarking schemes with the host signal available to the decoder. In this paper, blind watermarking of colored Gaussian host signals in the presence of filtering and additive Gaussian noise attacks is discussed. Three suboptimal but practical schemes are compared with a scheme where the host signal is available at the decoder. The performance is analyzed theoretically and experimentally for image watermarking.

We show that traditional waveform coding and 3-D model-based coding are not competing alternatives but should be combined to support and complement each other. Both approaches are combined such that the generality of waveform coding and the efficiency of 3-D model-based coding are available where needed. The combination is achieved by providing the block-based video coder with a second reference frame for prediction which is synthesized by the model-based coder. Since the coding gain of this approach is directly related to the quality of the synthetic frame, we have extended the model-aided coder to cope with illumination changes and multiple objects. Remaining model failures and objects that are not known at the decoder are handled by standard block-based motion-compensated prediction. Experimental results show that bit-rate savings of up to 45% are achieved at equal average PSNR when comparing the model-aided codec to TMN-10, the test model of the H.263 standard.

Multi-hypothesis prediction extends motion compensation with one prediction signal to the linear superposition of several motion-compensated prediction signals with the result of increased coding efficiency. The multiple hypotheses in this paper are blocks in past decoded frames. These blocks are referenced by individual motion vectors and picture reference parameters incorporating long-term memory motion-compensated prediction. In this work, we at most employ two hypotheses similar to B-frames. However, they are obtained from the past. Due to the increased rate for the motion vectors, rate-constrained coder control is utilized. For this scheme, we demonstrate the coding efficiency of multi-hypothesis prediction in combination with variable block size and long-term memory and present bit-rate savings up to 32% when compared to standard variable block size prediction without long-term memory motion compensation.

Two compression schemes for coding multiple images of a static scene are compared. Both codecs apply approximate 3-D scene geometry: in model-aided coding, images are predicted by model-driven disparity compensation, while the model-based coder uses the geometry to convert images into texture maps for compression. Images of real-world objects are used to evaluate both codecs. The coding performance is examined subject to varying geometry accuracy. Compression factors of up to 1000:1 at an acceptable reconstruction quality verify the usefulness of the 3-D geometry for coding multi-viewpoint imagery.

S.919-922

In this paper we present a voxel-based 3-D reconstruction technique that computes a set of non-transparent object surface voxels from a given set of calibrated camera views. We show that the quality of the reconstruction strongly depends on the accuracy of the computed voxel projection in the image plane and discuss different approximations of the exact projection. The most simple and computationally least demanding approximation is obtained when projecting point voxels, i.e., voxels without spatial extent. However, correct occlusion handling is not possible for point voxel volumes leading to reconstruction artifacts. The most accurate projection is obtained by computing the exact outline of the projected voxels. This projection is computationally most demanding but allows correct occlusion handling during reconstruction. Experimental results that compare the reconstruction quality for point and exact voxel projection show that it is worthwhile computing the tract image plane footprint of the projected voxels.

An analytical model of a video transmission system is used to study the impact of its parameters. The optimal trade-off between error resilience using INTRA coding and the channel code rate is determined for given channel parameters by minimizing the expected mean square error at the decoder. It is shown that the results strongly depend on the burstiness of the channel.

Long-term memory prediction extends the spatial displacement vector utilized in hybrid video coding by a variable time delay permitting the use of more than one reference frame for motion compensation. This extension provides improved rate-distortion performance. However, motion compensation in combination with transmission errors leads to temporal error propagation that occurs when the reference frames at encoder and decoder differ. In this paper, we present a framework that incorporates an error estimate into rate-constrained motion estimation and mode decision. Experimental results with a Rayleigh fading channel show that long-term memory motion compensation significantly outperforms single-frame prediction.

We derive an image-domain cost function for calibrated 3-D rigid body motion estimation from two views. The cost function is based on the accumulation of minimum mean squared error values along the epipolar lines for a large number of small measurement windows. In comparison to other non-linear, but feature-based formulations, the minimization of this cost function does not require pre-computed point correspondences. Several speedups are derived that keep the computational complexity similar to other non-linear formulations of the 3-D rigid body motion estimation problem. The main advantage of the proposed technique is that no effort has to be devoted to the reliable determination of point correspondences.

We describe a voxel-based 3-D reconstruction technique from multiple calibrated camera views that makes explicit use of the finite size footprint of a voxel when projected into the image plane. We derive a class of computationally efficient axis-aligned volume traversal orders that ensure that a processed voxel cannot occlude previously processed voxels. For each view, one out of 79 different cases of volume traversal is identified depending on the relative position between camera and voxel volume. Views belonging to the same visibility class can be processed simultaneously. Our voxel coloring strategy is based on a color hypothesis test that ensures the consistency of the projected reconstruction with the original images. A surface voxel list is constantly updated during reconstruction ensuring that only a minimum number of voxels has to be processed. Experimental results that compare the reconstruction quality for voxels with and without spatial extent underscore the conclusion that it is worthwhile taking into account the exact footprint of the projected voxels.

A theoretical analysis of the overall mean squared error (MSE) in hybrid video coding is presented for the case of error prone transmission. Our model covers the complete transmission system including the rate-distortion performance of the video encoder, forward error correction, interleaving, and the effect of error concealment and interframe error propagation at the video decoder. The channel model used is a 2-state Markov model describing burst errors on the symbol level. Reed-Solomon codes are used for forward error correction. Extensive simulation results using an H.263 video codec are provided for verification. Using the model, the optimal tradeoff between INTRA and INTER coding as well as the optimal channel code rate can be determined for given channel parameters by minimizing the expected MSE at the decoder. The main focus of this paper is to show the accuracy of the derived analytical model and its applicability to the analysis and optimization of an entire video transmission system.

Long-term memory prediction extends the spatial displacement vector utilized in hybrid video coding by a variable time delay, permitting the use of more than one reference frame for motion compensation. This extension leads to improved rate-distortion performance. However, motion compensation in combination with transmission errors leads to temporal error propagation that occurs when the reference frames at the coder and decoder differ. In this paper, we present a framework that incorporates an estimated error into rate-constrained motion estimation and mode decision. Experimental results with a Rayleigh fading channel show that long-term memory prediction significantly outperforms the single-frame prediction H.263-based anchor. When a feedback channel is available, the decoder can inform the encoder about successful or unsuccessful transmission events by sending positive (ACK) or negative (NACK) acknowledgments. This information is utilized for updating the error estimates at the encoder. Similar concepts, such as the ACK and NACK mode known from the H.263 standard, are unified into a general framework providing superior transmission performance.

We show that traditional waveform coding and 3-D model-based coding are not competing alternatives, but should be combined to support and complement each other. Both approaches are combined such that the generality of waveform coding and the efficiency of 3-D model-based coding are available where needed. The combination is achieved by providing the block-based video coder with a second reference frame for prediction, which is synthesized by the model-based coder. The model-based coder uses a parameterized 3-D head model, specifying the shape and color of a person. We therefore restrict our investigations to typical videotelephony scenarios that show head-and-shoulder scenes. Motion and deformation of the 3-D head model constitute facial expressions which are represented by facial animation parameters (FAPs) based on the MPEG-4 standard. An intensity gradient-based approach that exploits the 3-D model information is used to estimate the FAPs, as well as illumination parameters, that describe changes of the brightness in the scene. Model failures and objects that are not known at the decoder are handled by standard block-based motion-compensated prediction, which is not restricted to a special scene content, but results in lower coding efficiency. A Lagrangian approach is employed to determine the most efficient prediction for each block from either the synthesized model frame or the previous decoded frame. Experiments on five video sequences show that bit rate savings of about 35% are achieved at equal average peak signal-to-noise ratio (PSNR) when comparing the model-aided codec to TMN-10, the state-of-the-art test model of the M.263 standard. This corresponds to a gain of 2-3 dB in PSNR when encoding at the same average bit rate.

A system for the automatic reconstruction of real-world objects from multiple uncalibrated camera views is presented. The camera position and orientation for all views, the 3-D shape of the rigid object, as well as the associated color information, are recovered from the image sequence. The system proceeds in four steps. First, the internal camera parameters describing the imaging geometry are calibrated using a reference object. Second, an initial 3-D description of the object is computed from two views. This model information is then used in a third step to estimate the camera positions for all available views using a novel linear 3-D motion and shape estimation algorithm. The main feature of this third step is the simultaneous estimation of 3-D camera-motion parameters and object shape refinement with respect to the initial 3-D model. The initial 3-D shape model exhibits only a few degrees of freedom and the object shape refinement is defined as flexible deformation of the initial shape model. Our formulation of the shape deformation allows the object texture to slide on the surface, which differs from traditional flexible body modeling. This novel combined shape and motion estimation using sliding texture considerably improves the calibration data of the individual views in comparison to fixed-shape model based camera-motion estimation. Since the shape model used for model based camera-motion estimation is only approximate, a volumetric 3-D reconstruction process is initiated in the fourth step that combines the information from ail views simultaneously. The recovered object consists of a set of voxels with associated color information that describes even fine structures and details of the object. New views of the object can be rendered from the recovered 3-D model, which has potential applications in virtual reality or multimedia systems and the emerging field of video coding using 3-D scene models.

Two light-field compression schemes are presented. The codecs are compared with regard to compression efficiency and rendering performance. The first proposed coder is based on video-compression techniques that have been modified to code the four-dimensional light-field data structure efficiently. The second coder relies entirely on disparity-compensated image prediction, establishing a hierarchical structure among the light-field images. The coding performance of both schemes is evaluated using publicly available light fields of synthetic, as well as real-world, scenes. Compression ratios vary between 100:1 and 2000:1, depending on the reconstruction quality and light-field scene characteristics.

Overlapped block motion compensation or B-frames are examples of multihypothesis motion compensation where several motion-compensated signals are superimposed to reduce the bit-rate of a video codec. This paper extends the wide-sense stationary theory of motion-compensated prediction (MCP) for hybrid video codecs to multihypothesis motion compensation. The power spectrum of the prediction error is related to the displacement error probability density functions (pdfs) of an arbitrary number of hypotheses in a closed-form expression. We then study the influence of motion compensation accuracy on the efficiency of multihypothesis motion compensation as well as the influence of the residual noise level and the gain from optimal combination of N hypotheses. For the noise-free limiting case, doubling the number of (equally good) hypotheses can yield a gain of up to 1/2 bits/sample, while doubling the accuracy of motion compensation can additionally reduce the bit-rate by up to 1 bit/sample independent of N. For realistic noise levels, it is shown that the introduction of B-frames or overlapped block motion compensation can provide larger gains than doubling motion compensation accuracy. Spatial filtering of the motion-compensated candidate signals becomes less important if more hypotheses are combined. The critical accuracy beyond which the gain due to more accurate motion compensation is small moves to larger displacement error variances with increasing noise and increasing number of hypotheses N. Hence, sub-pel accurate motion compensation becomes less important with multihypothesis MCP. The theoretical insights are confirmed by experimental results for overlapped block motion compensation, B-frames, and multiframe motion-compensated prediction with up to eight hypotheses from ten previous frames.

In this paper we present a volumetric method for the 3-D reconstruction of real world objects from multiple calibrated camera views. The representation of the objects is fully volume-based and no explicit surface description is needed. The approach is based on multi-hypothesis tests of the voxel model back-projected into the image planes. All camera views are incorporated in the reconstruction process simultaneously and no explicit data fusion is needed. In a first step each voxel of the viewing volume is filled with several color hypotheses originating from different camera views. This leads to an overcomplete representation of the 3-D object and each voxel typically contains multiple hypotheses. In a second step only those hypotheses remain in the voxels which are consistent with all camera views where the voxel is visible. Voxels without a valid hypothesis are considered to be transparent. The methodology of our approach combines the advantages of silhouette-based and image feature-based methods. Experimental results on real and synthetic image data show the excellent visual quality of the voxel-based 3-D reconstruction.

In this paper we combine model-based video synthesis with block-based motion-compensated prediction (MCP). Two frames utilized for prediction where one frame is the previous decoded one and the other frame is provided by a model-based coder. The approach is integrated into an H.263-based video codec. Rate-distortion optimization is employed for the coding control. Hence, the coding efficiency does not decrease below H.263 even if the model based coder cannot describe the current scene. On the other hand, if the objects in the scene correspond to the model-based coder, significant gains in coding efficiency can be obtained compared to TMN-10, the test model of the H.263 standard. This is verified by experiments with natural head-and-shoulder sequences. Bit-rate savings of about 35% are achieved at equal average PSNR. When encoding at equal bit-rate, significant improvements in terms of subjective quality are visible.

A theoretical analysis of the overall mean squared error (MSE) in hybrid video coding is presented for the case of error prone transmission. The derived model for interframe error propagation includes the effects of INTRA coding and spatial loop filtering and corresponds to simulation results very accurately. For a given target bit rate, only four parameters are necessary to describe the overall distortion behavior of the decoder. Using the model, the optimal trade-off between INTRA and INTER coding can be determined for a given packet loss probability by minimizing the expected MSE at the decoder.

This paper highlights recent advances in image compression aided by 3-D geometry information. As two examples, we present a model-aided video coder for efficient compression of head-and-shoulder scenes and a geometry-aided coder for 4-D light fields for image-based rendering. Both examples illustrate that an explicit representation of 3-D geometry is advantageous if many views of the same 3-D object or scene have to be encoded. Waveform-coding and 3-D model-based coding can be combined in a rate-distortion framework, such that the generality of waveform coding and the efficiency of 3-D models are available where needed.

All current video compression standards employ motion compensated prediction and blockwise encoding of the prediction error using the discrete cosine transform (DCT). The DCT coefficients of each block are quantized, re-ordered into a vector, and each zero-run/coefficient pair is encoded as a single symbol, using a variable length code (VLC) table. In this paper, we show that the use of multiple instead of one VLC table yields significant bit-rate savings of the coded sequences, compared to H.263. The bit-rate-savings are typically up to 20% for medium bit-rates and still around 5% for very low bit-rates. No extra information has to be transmitted. The complexity at both coder and decoder is practically not increased. The only disadvantage of the method is the need to store larger VLC tables.

A coder for light fields is presented. Due to the large amount of data needed to represent a complete light field, a hierarchical decomposition is employed. The full light field is built up by recursively predicting intermediate images from a small subset of light-field images. Intermediate images are predicted by disparity-compensating multiple surrounding images. The predicted images are refined using DCT coding. Rate-distortion measurements for two standard light fields verify the efficiency of the proposed scheme. Compression ratios of 1000:1 are achieved at acceptable quality of the rendered views.

A novel motion representation and estimation scheme is presented that leads to improved coding efficiency of block-based video coders like, e.g., H.263. The proposed scheme is based on motion-compensated prediction from more than one reference frame. The reference pictures are warped or globally motion-compensated versions of the previous frame. Affine motion models are used as warping parameters approximating the motion vector field. Motion compensation is performed using standard block matching in the multiple reference frames buffer. The frame reference and the affine motion parameters are transmitted as side information. The approach is incorporated into an H.263-based video codec at minor syntax changes and embedded into a rate-constrained motion estimation and macroblock mode decision frame work. In contrast to conventional global motion compensation, where one motion model is transmitted, we show that multiple global motion models are of benefit in terms of coding efficiency. Significant coding gains in comparison to TMN-10, the test model of H.263+, are achieved that provide bit-rate savings between 20% and 35% for the various sequences tested.

A simple but powerful theoretical model for watermarking and attacks is presented. The attack consists of Wiener estimation of the watermark, followed by weighted feedback of the estimate to reduce the detector's correlation value. The Wiener attack is provably optimal, and it leads to the notion of energy-efficient watermarking, the generation of watermarks that resist Wiener estimation. It also leads to a meaningful way to measure watermark robustness. Designing watermarks to resist the attack produces a power-spectrum condition (PSC): the watermark's power spectrum should be a scaled version of the original document's. Experiments with signal models demonstrate the importance of the PSC and show that watermarks that fail to meet the PSC may be vulnerable to attack. These analytic predictions are confirmed with experiments on natural images. The paper provides a theoretical basis for the popular heuristic argument that a watermark should be embedded in the "perceptually significant frequency components" of the original document and discourages the use of watermarks whose power spectra are not closely matched to the original document's power spectrum.

Long-term memory prediction extends motion compensation from the previous frame to several past frames with the result of increased coding efficiency. We demonstrate that combining long-term memory prediction with affine motion compensation leads to further coding gains. For that, various affine motion parameter sets are estimated between frames in the long-term memory buffer and the current frame. Motion compensation is conducted using standard block matching in the multiple reference frame buffer. The picture reference and the affine motion parameters are transmitted as side information. The technique is embedded into a hybrid video coder mainly following the H.263 standard. The coder control employs Lagrangian optimization for the motion estimation and macroblock mode decision. Significant bit-rate savings between 20 and 50% are achieved for the sequences tested over TMN-10 the test model of H.263+. These bit-rate savings correspond to gains in PSNR between 0.8 and 3 dB.

We review feedback-based low bit-rate video coding techniques for robust transmission in mobile multimedia networks. For error control on the source coding level, each decoder has to make provisions for error detection, resynchronization, and error concealment, and we review techniques suitable for that purpose. Further, techniques are discussed for intelligent processing of acknowledgment information by the coding control to adapt the source coder to the channel. We review and compare error tracking, error confinement, and reference picture selection techniques for channel-adaptive source coding. For comparison of these techniques, a system for transmitting low bit-rate video over a wireless channel is presented and the performance is evaluated for a range of transmission conditions. We also show how feedback-based source coding can be employed in conjunction with precompressed video stored on a media server. The techniques discussed are applicable to a wide variety of interframe video schemes, including various video coding standards. Several of the techniques have been incorporated into the H.263 video compression standard, and this standard is used as an example throughout.

Long-term memory motion-compensated prediction extends the spatial displacement vector utilized in block-based hybrid video coding by a variable time delay permitting the use of more frames than the previously decoded one for motion compensated prediction. The long-term memory covers several seconds of decoded frames at the encoder and decoder. The use of multiple frames for motion compensation in most cases provides significantly improved prediction gain. The variable time delay has to be transmitted as side information requiring an additional bit rate which may be prohibitive when the size of the long-term memory becomes too large. Therefore, me control the bit rate of the motion information by employing rate constrained motion estimation. Simulation results are obtained by integrating long-term memory prediction into an H.263 codec. Reconstruction PSNR improvements up to 2 dB for the Foreman sequence and 1.5 dB for the Mother-Daughter sequence are demonstrated in comparison to the TMN-2.0 H.263 coder. The PSNR improvements correspond to bit-rate savings up to 34 and 30%, respectively. Mathematical inequalities are used to speed up motion estimation while achieving full prediction gain.

Multi-hypothesis motion-compensated prediction extends traditional motion-compensated prediction used in video coding schemes. Known algorithms for block-based multi-hypothesis motion-compensated prediction are, for example, overlapped block motion compensation (OBMC) and bidirectionally predicted frames (B-frames). This paper presents a generalization of these algorithms in a rate-distortion framework. All blocks which are available for prediction are called hypotheses. Further, we explicitly distinguish between the search space and the superposition of hypotheses. Hypotheses are selected from a search space and their spatio-temporal positions are transmitted by means of spatio-temporal displacement codewords. Constant predictor coefficients are used to combine linearly hypotheses of a multi-hypothesis. The presented design algorithm provides an estimation criterion for optimal multi-hypotheses, a rule for optimal displacement codes, and a condition for optimal predictor coefficients. Statistically dependent hypotheses of a multi-hypothesis are determined by an iterative algorithm. Experimental results show that Increasing the number of hypotheses from 1 to 8 provides prediction gains up to 3 dB in prediction error.

This paper presents a theoretical analysis of multi-hypothesis motion-compensated prediction for hybrid video coders. The power spectrum of the prediction error is related to the displacement error PDFs of an arbitrary number of hypotheses in a closed form expression. It is shown that, if the residual noise level is low, doubling the number of (equally good) hypotheses can yield a gain of up to 0.5 bits/sample and that doubling the accuracy of motion compensation (such as going from integer-pel to 1/2-pel accuracy) can additionally reduce the bit-rate by up to 0.5 bits/sample independent of N. With realistic residual noise levels, the introduction of B-frames or overlapped block motion compensation typically provides larger gains than doubling the motion compensation accuracy.

Embedding information into multimedia data, also called watermarking, is a topic that has gained increased attention. For video broadcast applications, watermarking schemes operating on compressed video are desirable. We present a scheme for robust watermarking of MPEG-2 encoded video. The watermark is embedded into the MPEG-2 bitstream without increasing the bit-rate, and can be retrieved even from the decoded video and without knowledge of the original, unwatermarked video. The scheme is robust and of much lower complexity than a complete decoding process followed by watermarking in the pixel domain and re-encoding. Although an existing MPEG-2 bitstream is partly altered, the scheme avoids visible artifacts by adding a drift compensation signal. The scheme has been implemented and the results confirm that a robust watermark can be embedded into MPEG encoded video which can be used to securely transmit arbitrary binary information at a data rate of several bytes/second. The scheme is also applicable to other hybrid coding schemes like MPEG-1, H.261, and H.263.

Given two frames of a dynamic scene with several rigid body objects undergoing different motions in the three-dimensional space, we robustly estimate the motion and structure of each object. The least median of squares (LMedS) estimator is integrated into a robust 3D motion parameter estimation and scene structure recovery framework to deal with the multi-motion problem. Experimental results underline the capability of the approach to deal successfully with multi-component motion. We apply the approach presented in this paper to the problem of automatic insertion of artificial objects in real image sequences.

We present a model-based algorithm for the estimation of 3D motion and the analysis of facial expressions of a speaking person. A set of facial animation parameters based on the MPEG-4 standard is determined from two successive video frames using a hierarchical optical flow based method. The motion in the image plane is constrained by a 3D triangular B-spline model that defines shape, texture and facial expressions of an individual person. The computational requirement for this solution is low due to the linear structure of the algorithm.

For interactive video storage applications that retrieve video data over low bit-rate networks, precoded bit-streams have to be transmitted to the receiver with low latency. Besides random access, fast forward and reverse, the scalability of the bit-stream is an important requirement for the above application. In this paper, we investigate a standard compatible approach that avoids the overhead involved in the transmission of periodic I-frames. We propose to store multiple bit-streams of different rates at the video server, which can be selected for transmission. Especially encoded P-frames are used to switch between the stored bit-streams. During normal-speed playback only P-frames are transmitted, providing increased efficiency. The approach is evaluated in the framework of the H.263 video compression standard. Based on the Salesman test sequence encoded at 12.5 fps in QCIF format, the resulting frame jitter is investigated when an error control protocol is used to transmit the bit-streams over a wireless DECT channel. Compared to periodic I-frames at an interval of 800 ms, a gain of 2 dB PSNR can be observed at the same frame jitter.

Most watermarking techniques for images and video techniques involve a private key, for example a pseudo-noise signal, which is required for retrieval of the watermark information. This key is typically not public, because publication of the key would give rise to attacks on the watermark. In practical systems, however, watermarking techniques are required that enable public decoding of the watermark. In this paper, an extension of spread-spectrum watermarking is presented which enables public decoding and verification of the watermark, without at the same time giving the possibility of removing the watermark. The underlying idea, is to make only parts of the pseudo-noise key public. The scheme can be combined with a fast compressed-domain embedding technique to facilitate on-the-fly compressed-domain public-key watermarking.

Oversampled pyramid decompositions have been successfully applied to scalable video coding. Quantization noise feedback at the encoder ("closed-loop coding") has several advantages compared to "open-loop coding" where noise feedback is not included. Finding optimal bit allocations for closed-loop coders is a complex task since the rate-distortion (R-D) performance of one quantizer depends on the selected operational points of all previous ones. We present simplified models for closed-loop and open-loop coding. From those, analytical solutions to the optimal bit allocation problem can be derived. In the optimal case, closed-loop coding outperforms open-loop coding although distortion in lower resolution layers of the closed-loop coder may become rather high which is undesirable in scalable coding applications. In this case it turns out to be a good solution to use an optimal open-loop bit allocation for closed-loop coding. Theoretical results are verified by coding experiments.

We investigate how the temporal evolution of image point correspondences over multiple frames can be exploits for 3D motion and structure estimation. In comparison to other multi-frame approaches we do not separate the establishment of feature point correspondences and the 3D motion parameter computation. As a result our approach does not suffer from the limitations of the traditional two step approaches where even small errors in point correspondence can lead to large errors in 3D motion parameters. Experimental results on synthetic and real video sequences show that the estimation error is reduced when processing more than two frames simultaneously.

In this paper a contour prediction scheme is presented. Its application in a region-based motion compensation algorithm is shown. To achieve optimal performance in a rate-distortion sense the predicted regions are optimized by using a Lagrangian cost function. By using contour prediction the bit rate for motion compensation can be decreased.

In this paper a model-based multi-view image generation system for video conferencing is presented. The system assumes that a 3-D model of the person in front of the camera is available. It extracts texture from speaking person sequence images and maps it to the static 3-D model during the videoconference session. Since only the incrementally updated texture information is transmitted during the whole session, the bandwidth requirement is very small. Based on the experimental results one can conclude that the proposed system is very promising for practical applications.

Motion-compensating long-term memory prediction extends the spatial displacement utilized in block-based hybrid video coding by a variable time delay permitting the use of more frames than the previously decoded one for motion compensation. The long-term memory covers the decoded frames of some seconds at encoder and decoder. We investigate the influence of memory size in our motion compensation scheme and analyze the trade-off between the bit-rates spent for motion compensated prediction and residual coding. Simulation results are obtained by integrating long-term memory prediction into an H.263 codec. PSNR improvements up to 2 dB for the Foreman sequence and 1.5 dB for the Mother-Daughter sequence are demonstrated in comparison to the TMN-2.0 H.263 coder.

In this paper we address the problem of robust video transmission in error prone environments. The approach is compatible with the ITU-T video coding standard H.263. Fading situations in mobile networks are tolerated and the image quality degradation due to spatio-temporal error propagation is minimized utilizing a feedback channel between transmitter and receiver carrying acknowledgment information. In a first step, corrupted group of blocks (GOB's) are concealed to avoid annoying artifacts caused by decoding of an erroneous bit stream. The GOB and the corresponding frame number are reported to the transmitter via the back channel. The encoder evaluates the negative acknowledgments and reconstructs the spatial and temporal error propagation. A low complexity algorithm for real-time reconstruction of spatio-temporal error propagation is described in detail. Rapid error recovery is achieved by INTRA refreshing image regions (macroblocks) bearing visible distortion. The feedback channel method does not introduce additional delay and is particularly relevant for real-time conversational services in mobile networks. Experimental results with bursty bit error sequences simulating a Digital European Cordless Telephony (DECT) channel are presented with different combinations of forward error correction (FEC), automatic repeat on request (ARQ), and the proposed error compensation technique, Compared to the case where FEC and ARQ are used for error correction, a gain of up to 3 dB peak signal-to-noise ratio (PSNR) is observed if error compensation is employed additionally.

Quantization is the core part of all lossy source coding schemes. We present a design scheme for statistical optimization of a set of one-bit (i.e., two-level) quantizers, given the signal statistics of an arbitrary signal, for example a prediction error signal. The set of quantizers can then be used for block-adaptive quantization of the signal. The quantizer design criterion combines ideas from block truncation coding (BTC) and vector quantization (VQ). As an example application of our design scheme we apply a set of two-level quantizers to adaptive differential pulse code modulation of color video where the quantizers are switched adaptively on a block-by-block basis. Coding results show that this scheme has a better performance than other low-complexity video coding schemes. At 2 bit/pel, it performs more than 2 dB better in peak signal-to-noise ratio than DPCM (differential pulse code modulation) and up to 3.5 dB better than BTC.

Model-based video communication systems attempt to extract information about the three-dimensional structure of the scene to be transmitted. The relative motion between camera and objects can be a powerful depth cue, if the objects are rigid or almost rigid. We present a new algorithm for estimation of rigid body motion parameters and scene structure from monocular image sequences. A novel epipolar image transform is utilized to preserve the relevant information from mean squared displaced frame difference (DFD) surfaces and thus overcomes the inherent limitations of feature correspondence methods. Our algorithm conducts a coarse-to-fine search in 5-dimensional parameter space. Relative depth values are computed for each measurement window. Experimental results are presented to demonstrate the performance of the new algorithm.

Spatio-temporal resolution pyramids are well suited for scalable video codecs. An oversampled pyramid decomposition can be incorporated efficiently into either open-loop or closed-loop pyramid encoders. We discuss two different motion compensation (MC) techniques suitable for open-loop as well as for closed-loop pyramid coders. We compare the performance of each technique for both pyramid coders for the case of equal quantization noise in all resolution layers. Simulation results show that for this case all schemes have similar performance. By allowing higher quantization noise in the predicted frame it can be seen that bandpass MC performs up to 1 dB better.

We present a two stage technique for estimation of rigid body motion and scene structure from monocular image sequences. The robustness of motion recovery is considerably increased by motion dependent distortion of rectangular measurement windows. In the first stage, we estimate a set of candidate motion parameter sets from which the optimum is determined in a second step evaluating motion based image content deformation together with corresponding depth values. Experimental results show that the motion parameter estimation error can be reduced significantly.

Anatomy-based facial tissue modeling for surgical simulation is a field whose time has come. Real-time facial animation has been created in the last few years using models based on the anatomical structure of the human skin. Anatomy-based models are also under development in the field of medical visualization, with which facial surgery can be realistically simulated. In this article, we present an anatomy-based 3D finite element tissue model. Integrated into a computer-aided surgical planning system, this model allows the precise prediction of soft tissue changes resulting from the realignment of the underlying bone structure. The model has already been used in our Department of Oral and Maxillofacial Surgery and has improved craniofacial surgical planning procedures. The model is described in detail, and surgical simulation results are shown and discussed.

The design of a low complexity joint source channel codec for images using trellis coded quantization and convolutional codes is studied. It is shown that a low complexity joint source channel codec offering high robustness is enabled by using the same Ungerboeck trellis code to do both quantization and convolutional coding. Simulation results are presented for joint source channel coding of Gaussian sources over the additive white Gaussian noise channel (AWGN) under the restriction of BPSK modulation; coding of image subband coefficients is also performed. The results compare favorably with those previously reported for systems employing unified trellis source coding and convolutional channel coding, and for pseudo-Gray coded systems. The simulation results also show that there is an optimal allocation of transmission bandwidth between the source and channel codes.

The effect of fractional-pel accuracy on the efficiency of motion-compensating predictors is studied using various spatial prediction/interpolation filters. In model calculations, the power spectral density of the prediction error is related to the probability density function of the displacement error. Prediction can be improved both by higher accuracy of motion-compensation and by spatial Wiener filtering in the predictor. Beyond a critical accuracy, the possibility of further improving prediction by more accurate motion-compensation is small. Experiments with videophone signals and with broadcast TV signals confirm these model calculations. Sinc-interpolation, bilinear interpolation, and Wiener filtering are compared at integer-pel, 1/2-pel, 1/4-pel, and 1/8-pel accuracies. A three-state technique for reliable displacement estimation with fractional-pel accuracy is introduced. It is based on phase correlation. For motion-compensation with block size of 16 pels*16 pels, 1/4-pel accuracy appears to be sufficient for broadcast TV signals, whereas for videophone signals, 1/2-pel accuracy is desirable.>

Vector quantization for entropy coding of image subbands is investigated. Rate distortion curves are computed with mean square error as a distortion criterion. The authors show that full-search entropy-constrained vector quantization of image subbands results in the best performance, but is computationally expensive. Lattice quantizers yield a coding efficiency almost indistinguishable from optimum full-search entropy-constrained vector quantization. Orthogonal lattice quantizers were found to perform almost as well as lattice quantizers derived from dense sphere packings. An optimum bit allocation rule based on a Lagrange multiplier formulation is applied to subband coding. Coding results are shown for a still image.

Nonuniform quantizers for just-not-visible reconstruction errors in an adaptive intra-/interframe DPCM (digital pulse-code modulation) scheme for component-coded color television signals are presented, both for conventional and for noise-shaping DPCM. Noise feedback filters that minimize the visibility of reconstruction errors by spectral shaping are designed for Y, R-Y, and B-Y. A closed-form description of the masking function is derived which leads to a one-parameter b-quantizer characteristic. Subjective tests that were carried out to determine visibility thresholds for reconstruction errors for conventional DPCM and for noise shaping DPCM show significant gains by noise shaping. For a transmission rate of around 30 Mb/s, reconstruction errors are almost always below the visibility threshold if variable length encoding of the prediction error is combined with noise shaping within a 3:1:1 system.>

Performance bounds for generalized hybrid coding of video sequences with motion-compensating prediction are derived based on rate-distortion theory. It is shown that the spatial power spectrum of the motion-compensated prediction error can be calculated from the signal power spectrum and the displacement estimation error p.d.f.. A spatial Wiener filter can improve the efficiency of motion-compensating prediction. Memoryless encoding of the motion-compensated prediction error and intraframe encoding of the motion-compensated prediction error are compared. An evaluation of the rate-distortion functions for a typical videoconference sampling format shows that for integer pel accuracy of the displacement estimate the additional gain by motion-compensating prediction over pure intraframe coding is limited to ∼ 0.8 bits/sample in moving areas. Required accuracies of the displacement estimate for a gain of motion-compensating interframe coding over intraframe coding are given.

An analytical quality measure is essential for the successful design of digital transmission systems. For images the processes involved in human quality perception are too complicated to be modelled in a mathematically tractable way. In order to obtain useful results we have given up generality and investigated only quality measures for achromatic still images which have been coded by Pulse-Code-Modulation (PCM), Pseudo-Random Noise PCM, or Differential PCM. For this class of distortions we have found an objective quality measure based on the mean squared error, that performs better than commonly assumed. Another powerful measure has the same form as the mutual information between original and distorted image under the assumption of jointly Gaussian signals. In this paper these measures are compared with subjective results for the same distortions. The correlation is sufficiently good to justify the use of such measures in coding and evaluation of digital image coders.