We study the problem of lossy attribute compression, given encoded 3D point cloud geometry available at the decoder, in a multi-resolution B-spline projection framework. A target continuous 3D attribute function is first projected onto a sequence of nested subspaces ${\mathcal {F}}^{(p)}_{l_{0}} \subseteq \cdots \subseteq {\mathcal {F}} ^{(p)}_{L}$ , where ${\mathcal {F}}^{(p)}_{l}$ is a family of functions spanned by a B-spline basis function of order $p$ at a chosen scale and its integer shifts. The projected low-pass coefficients $F_{l}^{*}$ are computed via variable-complexity unrolling of a rate-distortion (RD) optimization algorithm into a feed-forward network, where the rate term is the sparsity-promoting $\ell _{1}$ -norm. Thus, the projection operation is end-to-end differentiable. For a chosen coarse-to-fine predictor, the coefficients are then adjusted to account for the prediction from a lower-resolution to a higher-resolution, which is also optimized in a data-driven manner.

We extend a previous study on 3D point cloud attribute compression scheme that uses a volumetric approach: given a target volumetric attribute function f : ℝ3↦ ℝ, we quantize and encode parameters θ that characterize f at the encoder, for reconstruction ${f_{\hat \theta }}({\mathbf{x}})$ at known 3D points x at the decoder. Specifically, parameters $\hat \theta $ are quantized coefficients of B-spline basis vectors Φl(for order p ≥ 2) that span the function space $\mathcal{F}_l^{(p)}$ at a particular resolution l, which are coded from coarse to fine resolutions for scalability. In this work, we focus on the prediction of finer-grained coefficients given coarser-grained ones by learning parameters of a polynomial bilateral filter (PBF) from data. PBF is a pseudo-linear filter that is signal-dependent with a graph spectral interpretation common in the graph signal processing (GSP) field. We demonstrate PBF’s predictive performance over a linear predictor inspired by MPEG standardization over a wide range of point cloud datasets.

We study 3D point cloud attribute compression via a volumetric approach: assuming point cloud geometry is known at both encoder and decoder, parameters $\theta$ of a continuous attribute function $f: \mathbb{R}^{3} \mapsto \mathbb{R}$ are quantized to $\hat{\theta}$ and encoded, so that discrete samples $f_{\hat{\theta}}\left(\mathbf{x}_{i}\right)$ can be recovered at known 3D points $\mathbf{x}_{i} \in \mathbb{R}^{3}$ at the decoder. Specifically, we consider a nested sequences of function subspaces ${\mathcal{F}}_{l_{0}}^{(p)} \subseteq \cdots \subseteq {\mathcal{F}}_{L}^{(p)}$, where ${\mathcal{F}}_{l}^{(p)}$ is a family of functions spanned by B-spline basis functions of order $p, f_{l}^{*}$ is the projection of f on ${\mathcal{F}}_{l}^{(p)}$ represented as low-pass coefficients $F_{l}^{*}$, and $g_{l}^{*}$ is the residual function in an orthogonal subspace ${\mathcal{G}}_{l}^{(p)}$ (where ${\mathcal{G}}_{l}^{(p)} \oplus {\mathcal{F}}_{l}^{(p)}=$ $\left.{\mathcal{F}}_{l+1}^{(p)}\right)$ represented as high-pass coefficients $G_{l}^{*}$. In this paper, to improve coding performance over [1], we study predicting $f_{l+1}^{*}$ at level $l+1$ given $f_{l}^{*}$ at level l and encoding of $G_{l}^{*}$ for the $p=1$ case (RAHT (1)). For the prediction, we formalize RAHT (1) linear prediction in MPEG-PCC in a theoretical framework, and propose a new nonlinear predictor using a polynomial of bilateral filter. We derive equations to efficiently compute the critically sampled high-pass coefficients $G_{l}^{*}$ amenable to encoding. We optimize parameters in our resulting feed-forward network on a large training set of point clouds by minimizing a rate-distortion Lagrangian. Experimental results show that our improved framework outperforms the MPEG G-PCC predictor by $11 \%-12 \%$ in bit rate.

Neural networks are now widely used in image compression. Network architecture and hyperparameter choices impact both compression performance and complexity, but (as we show) there are many examples where higher complexity does not entail better compression. Thus, it is desirable to perform rate-complexity optimization over the space of hyperparameters. In the context of neural-based lossless image compression, we propose an algorithm that traces hyperparameter choices of points on or near the lower convex hull of the cloud of rate-complexity points produced by all combinations of hyperparameters, without having to know in advance the rate-complexity performance of each combination. This reduces the training/evaluation load of the rate-complexity optimization by over 50% in our experiments, for each of three measures of complexity: multiply/add operations per pixel, Joules per pixel, and encoded network size.

We build interpretable and lightweight transformer-like neural networks by unrolling iterative optimization algorithms that minimize graph smoothness priors---the quadratic graph Laplacian regularizer (GLR) and the $\ell_1$-norm graph total variation (GTV)---subject to an interpolation constraint. The crucial insight is that a normalized signal-dependent graph learning module amounts to a variant of the basic self-attention mechanism in conventional transformers. Unlike "black-box" transformers that require learning of large key, query and value matrices to compute scaled dot products as affinities and subsequent output embeddings, resulting in huge parameter sets, our unrolled networks employ shallow CNNs to learn low-dimensional features per node to establish pairwise Mahalanobis distances and construct sparse similarity graphs. At each layer, given a learned graph, the target interpolated signal is simply a low-pass filtered output derived from the minimization of an assumed graph smoothness prior, leading to a dramatic reduction in parameter count. Experiments for two image interpolation applications verify the restoration performance, parameter efficiency and robustness to covariate shift of our graph-based unrolled networks compared to conventional transformers.

Point cloud compression (PCC) has been rapidly evolving in the context of international standards. Despite the inherent scalability of octree-based geometry descriptions, current attribute compression techniques prevent full scalability of compressed point clouds. We propose an improvement on an embedded attribute encoding method for point clouds based on set partitioning in hierarchical trees (SPIHT). We propose to use a multi-layer perceptron (MLP) to model contexts in order to further compress the final bit-stream. The encoder is used along with the region-adaptive hierarchical transform, which has been a popular transform for point cloud coding and is included in the standard geometry-based point cloud coder (G-PCC). The result is an encoder that is efficient, scalable, and, best of all, embedded. That is, higher compression is achieved by further trimming the single bit-stream. Experimental results show approximately 13% BD-Rate reduction using MLP-based context modeling.

We study 3D point cloud attribute compression using a volumetric approach: given a target volumetric attribute function f : ℝ3→ ℝ, we quantize and encode parameter vector θ that characterizes f at the encoder, for reconstruction ${f_{\hat \theta }}\left( {\mathbf{x}} \right)$ at known 3D points x’s at the decoder. Extending a previous work Region Adaptive Hierarchical Transform (RAHT) that employs piecewise constant functions to span a nested sequence of function spaces, we propose a feedforward linear network that implements higher-order B-spline bases spanning function spaces without eigen-decomposition. Feedforward network architecture means that the system is amenable to end-to-end neural learning. The key to our network is space-varying convolution, similar to a graph operator, whose weights are computed from the known 3D geometry for normalization. We show that the number of layers in the normalization at the encoder is equivalent to the number of terms in a matrix inverse Taylor series. Experimental results on real-world 3D point clouds show up to 2-3 dB gain over RAHT in energy compaction and 20-30% bitrate reduction.

We propose sandwiched video compression – a video compression system that wraps neural networks around a standard video codec. The sandwich framework consists of a neural pre- and post-processor with a standard video codec between them. The networks are trained jointly to optimize a rate-distortion loss function with the goal of significantly improving over the standard codec in various compression scenarios. End-to-end training in this setting requires a differentiable proxy for the standard video codec, which incorporates temporal processing with motion compensation, inter/intra mode decisions, and in-loop filtering. We propose differentiable approximations to key video codec components and demonstrate that, in addition to providing meaningful compression improvements over the standard codec, the neural codes of the sandwich lead to significantly better rate-distortion performance in two important scenarios. When transporting high-resolution video via low-resolution HEVC, the sandwich system obtains 6.5 dB improvements over standard HEVC. More importantly, using the well-known perceptual similarity metric, LPIPS, we observe 30% improvements in rate at the same quality over HEVC. Last but not least, we show that pre- and post-processors formed by very modestly-parameterized, light-weight networks can closely approximate these results.

In this paper, we introduce a novel 6-D representation of plenoptic point clouds, enabling joint, non-separable transform coding of plenoptic signals defined along both spatial and angular (viewpoint) dimensions. This 6-D representation, which is built in a global coordinate system, can be used in both multi-camera studio capture and video fly-by capture scenarios, with various viewpoint (camera) arrangements and densities. We show that both the Region-Adaptive Hierarchical Transform (RAHT) and the Graph Fourier Transform (GFT) can be extended to the proposed 6-D representation to enable the non-separable transform coding. Our method is applicable to plenoptic data with either dense or sparse sets of viewpoints, and tocompleteorincompleteplenoptic data, while the state-of-the-art RAHT-KLT method, which is separable in spatial and angular dimensions, is applicable only tocompleteplenoptic data. The “complete” plenoptic data refers to data that has, for each spatial point, one colour for every viewpoint (ignoring any occlusions), while “incomplete” data has colours only for thevisiblesurface points at each viewpoint. We demonstrate that the proposed 6-D RAHT and 6-D GFT compression methods are able to outperform the state-of-the-art RAHT-KLT method on 3-D objects with various levels of surface specularity, and captured with different camera arrangements and different degrees of viewpoint sparsity.

Given a standard image codec, we compress images that may have higher resolution and/or higher bit depth than allowed in the codec's specifications, by sandwiching the standard codec between a neural pre-processor (before the standard encoder) and a neural post-processor (after the standard decoder). Using a differentiable proxy for the the standard codec, we design the neural pre-and post-processors to transport the high resolution (super-resolution, SR) or high bit depth (high dynamic range, HDR) images as lower resolution and lower bit depth images. The neural processors accomplish this with spatially coded modulation, which acts as watermarks to preserve the important image detail during compression. Experiments show that compared to conventional methods of transmitting high resolution or high bit depth through lower resolution or lower bit depth codecs, our sandwich architecture gains ~9dB for SR images and $\sim$3dB for HDR images at the same rate over large test sets. We also observe significant gains in visual quality.

Arithmetic coding is used in most media compression methods. Context modeling is usually done through frequency counting and look-up tables (LUTs). For long-memory signals, probability modeling with large context sizes is often infeasible. Recently, neural networks have been used to model probabilities of large contexts in order to drive arithmetic coders. These neural networks have been trained offline. We introduce anonlinemethod for training a perceptron-based context-adaptive arithmetic coder on-the-fly, calledadaptive perceptron coding, which continuously learns the context probabilities and quickly converges to the signal statistics. We test adaptive perceptron coding over a binary image database, with results always exceeding the performance of LUT-based methods for large context sizes and of recurrent neural networks. We also compare the method to a version requiring offline training, which leads to equally satisfactory results.

In the past decade, several multi-resolution representation theories for graph signals have been proposed. Bipartite filter-banks stand out as the most natural extension of time domain filter-banks, in part because perfect reconstruction, orthogonality and bi-orthogonality conditions in the graph spectral domain resemble those for traditional filter-banks. Therefore, many of the well known orthogonal and bi-orthogonal designs can be easily adapted for graph signals. A major limitation is that this framework can only be applied to the normalized Laplacian of bipartite graphs. In this paper we extend this theory to arbitrary graphs and positive semi-definite variation operators. Our approach is based on a different definition of the graph Fourier transform (GFT), where orthogonality is defined with respect to the Q inner product. We construct GFTs satisfying a spectral folding property, which allows us to easily construct orthogonal and bi-orthogonal perfect reconstruction filter-banks. We illustrate signal representation and computational efficiency of our filter-banks on 3D point clouds with hundreds of thousands of points.

We sandwich a standard image codec between two neural networks: a preprocessor that outputs neural codes, and a postprocessor that reconstructs the image. The neural codes are compressed as ordinary images by the standard codec. Using differentiable proxies for both rate and distortion, we develop a rate-distortion optimization framework that trains the networks to generate neural codes that are efficiently compressible as images. This architecture not only improves rate-distortion performance for ordinary RGB images, but also enables efficient compression of alternative image types (such as normal maps of computer graphics) using standard image codecs. Results demonstrate the effectiveness and flexibility of neural processing in mapping a variety of input data modalities to the rigid structure of standard codecs. A surprising result is that the rate-distortion-optimized neural processing seamlessly learns to transport color images using a single-channel (grayscale) codec.

Some forms of novel visual media enable the viewer to explore a 3D scene from essentially arbitrary viewpoints, by interpolating between a discrete set of original views. Compared to 2D imagery, these types of applications require much larger amounts of storage space, which we seek to reduce. Existing approaches for compressing 3D scenes are often based on a separation of compression and rendering: each of the original views is compressed using traditional 2D image formats; the receiver decompresses the views and then performs the rendering. We unify these steps by directly compressing an implicit representation of the scene, a function that maps spatial coordinates to a radiance vector field, which can then be queried to render arbitrary viewpoints. The function is implemented as a neural network and jointly trained for reconstruction as well as compressibility, in an end-to-end manner, with the use of an entropy penalty on the parameters. Our method significantly outperforms a state-of-the-art conventional approach for scene compression, achieving simultaneously higher quality reconstructions and lower bitrates. Furthermore, we show that the performance at lower bitrates can be improved by jointly representing multiple scenes using a soft form of parameter sharing.

We propose an embedded attribute encoding method for point clouds based on set partitioning in hierarchical trees (SPIHT). The encoder is used with the region-adaptive hierarchical transform which has been a popular transform for point cloud coding, even included in the standard geometry-based point cloud coder (G-PCC). The result is an encoder that is efficient, scalable, and embedded. That is, higher compression is achieved by trimming the full bit-stream. G-PCCs RAHT coefficient prediction prevents the straightforward incorporation of SPIHT into G-PCC. However, our results over other RAHT-based coders are promising, improving over the original, nonpredictive RAHT encoder, while providing the key functionality of being embedded.

We describe a novel approach for compressing truncated signed distance fields (TSDF) stored in 3D voxel grids, and their corresponding textures. To compress the TSDF, our method relies on a block-based neural network architecture trained end-to-end, achieving state-of-the-art rate-distortion trade-off. To prevent topological errors, we losslessly com- press the signs of the TSDF, which also upper bounds the reconstruction error by the voxel size. To compress the corresponding texture, we designed a fast block-based UV parameterization, generating coherent texture maps that can be effectively compressed using existing video compression algorithms. We demonstrate the performance of our algo- rithms on two 4D performance capture datasets, reducing bitrate by 66% for the same distortion, or alternatively re- ducing the distortion by 50% for the same bitrate, compared to the state-of-the-art.

We introduce the Region Adaptive Graph Fourier Transform (RAGFT) for compression of 3D point cloud attributes. The RA-GFT is a multiresolution transform, formed by combining spatially localized block transforms. We assume the points are organized by a family of nested partitions represented by a rooted tree. At each resolution level, attributes are processed in clusters using block transforms. Each block transform produces a single approximation (DC) coefficient, and various detail (AC) coefficients. The DC coefficients are promoted up the tree to the next (lower resolution) level, where the process can be repeated until reaching the root. Since clusters may have a different numbers of points, each block transform must incorporate the relative importance of each coefficient. For this, we introduce the Q-normalized graph Laplacian, and propose using its eigenvectors as the block transform. The RA-GFT achieves better complexity-performance trade-offs than previous approaches. In particular, it outperforms the Region Adaptive Haar Transform (RAHT) by up to 2.5 dB, with a small complexity overhead.

Algorithms for creating saliency maps are well established for images, even though there is no literature on such methods for point clouds. We use orthographic projections in 2D planes which are subject to well established saliency detection algorithms to create a 3D saliency map. The results of each saliency map are projected to the 3D voxels and the results of the many projections are used to generate a 3D saliency map. Simple compression tests were carried using soft region-of-interest maps. Results have shown an increase in the quality of the voxels inside the selective regions of increased levels of interest.

Compression of point clouds has so far been confined to coding the positions of a discrete set of points in space and the attributes of those discrete points. We introduce an alternative approach based on volumetric functions, which are functions defined not just on a finite set of points, but throughout space. As in regression analysis, volumetric functions are continuous functions that are able to interpolate values on a finite set of points as linear combinations of continuous basis functions. Using a B-spline wavelet basis, we are able to code volumetric functions representing both geometry and attributes. Geometry compression is addressed in Part II of this paper, while attribute compression is addressed in Part I. Attributes are represented by a volumetric function whose coefficients can be regarded as a critically sampled orthonormal transform that generalizes the recent successful region-adaptive hierarchical (or Haar) transform to higher orders. Experimental results show that attribute compression using higher order volumetric functions is an improvement over the first order functions used in the emerging MPEG Point Cloud Compression standard.

Compression of point clouds has so far been confined to coding the positions of a discrete set of points in space and the attributes of those discrete points. We introduce an alternative approach based on volumetric functions, which are functions defined not just on a finite set of points, but throughout space. As in regression analysis, volumetric functions are continuous functions that are able to interpolate values on a finite set of points as linear combinations of continuous basis functions. Using a B-spline wavelet basis, we are able to code volumetric functions representing both geometry and attributes. Attribute compression is addressed in Part I of this paper, while geometry compression is addressed in Part II. Geometry is represented implicitly as the level set of a volumetric function (the signed distance function or similar). Experimental results show that geometry compression using volumetric functions improves over the methods used in the emerging MPEG Point Cloud Compression (G-PCC) standard.

We introduce Region-of-Interest (ROI) coding for point cloud attributes, using an input-weighted distortion measure where the weights are determined by the ROI. In terms of coding, we use the Region Adaptive Hierarchical Transform (RAHT), which relies on a set of weights. We use a measure-theoretic interpretation of RAHT to determine that the weights of the transform should be set to the weights of the distortion measure. The ROI is chosen as the 3D region of the face, which is detected from a set of 2D projections using the well-known Viola-Jones algorithm. Experimental results show subjectively meaningful improvements (7-8 dB PSNR) in a face ROI with subjectively insignificant degradations (under 1 dB PSNR) in the non-ROI.

A recently-introduced coder based on region-adaptive hierarchical transform (RAHT) is being considered as a standard for the compression of point cloud attributes at moving picture experts group. The RAHT coefficients can be encoded in many ways and the transform is based on a series of orthogonal 2 × 2 transform matrices with geometry-dependent floating-point entries. In order to remove computation ambiguity and facilitate deployment, fixed-point operations are often preferred. In this letter, we present an alternative RAHT description that allows for fixed-point implementation of its transform steps. It is based on matrix decompositions akin to lifting steps and a scaling of the quantization steps. Results are presented to show that the new fixed-point transform is, in practical terms, equivalent to the floating-point RAHT. For that we use a reasonable number of precision bits for the integer operations, e.g. 8 b or more.

Point clouds have been recently used in applications involving real-time capture and rendering of 3D objects. In a point cloud, for practical reasons, each point or voxel is usually associated with one single color along with other attributes. The region-adaptive hierarchical transform (RAHT) coder has been proposed for single-color point clouds. The cloud is usually captured by many cameras and the colors are averaged in some fashion to yield the point color. This approach may not be very realistic since, in real world objects, the reflected light may significantly change with the viewing angle, especially if specular surfaces are present. For that, we are interested in a more complete representation, the plenoptic point cloud, wherein every point has associated colors in all directions. Here, we propose a compression method for such a representation. Instead of encoding a continuous function, since there is only a finite number of cameras, it makes sense to compress as many colors per voxel as cameras, and to leave any intermediary color rendering interpolation to the decoder. Hence, each voxel is associated with a vector of color values, for each color component. We have here developed and evaluated four methods to expand the RAHT coder to encompass the multiple colors case. Experiments with synthetic data helped us to correlate specularity with the compression, since object specularity, at a given point in space, directly affects color disparity among the cameras, impacting the coder performance. Simulations were carried out using natural (captured) data and results are presented as rate-distortion curves that show that a combination of Kahunen-Loève transform and RAHT achieves the best performance.

Volumetric media, popularly known as holograms, need to be delivered to users using both on-demand and live streaming, for new augmented reality (AR) and virtual reality (VR) experiences. As in video streaming, hologram streaming must support network adaptivity and fast startup, but must also moderate large bandwidths, multiple simultaneously streaming objects, and frequent user interaction, which requires low delay. In this paper, we introduce the first system designed specifically for streaming volumetric media. The system reduces bandwidth by introducing 3D tiles, and culling them or reducing their level of detail depending on their relation to the user's view frustum and distance to the user. To allocate bits among different tiles across multiple objects, we introduce a simple greedy yet provably optimal algorithm for rate-utility optimization, whose utility measures is based not only on the underlying quality of the representation, but on the level of detail relative to the user's viewpoint and device resolution. Simulation results show that the proposed algorithm provides superior quality compared to existing video-streaming approaches adapted to hologram streaming, in terms of utility and user experience over variable, throughput-constrained networks.

Surface Light Fields (SLF) have previously been proposed for representing 3D scenes under complex lighting conditions' enabling immersive viewing experiences from arbitrary observation directions. In this work, we present a new approach for SLF representation and a framework for SLF compression. Specifically, the SLF is compactly represented in a B-Spline wavelet basis. This representation is capable of modeling diverse surface materials and complex lighting conditions. The coefficients of the B-Spline wavelet are then compressed by removing the spatial redundancy over surface points. Compared with image based light field compression, the proposed scheme is functionally advanced because it enables rendering objects from arbitrary viewpoints with both good quality and high efficiency. In terms of bitrate and distortion, experimental results have shown that the proposed method can achieve competitive performance but with much lower decoder computational complexity, indicating its potential in practical virtual and augmented reality applications.

Point clouds have recently gained interest for the represention of 3D scenes in augmented and virtual reality. In real-time applications point clouds typically assume one color per point. While this approach is suited to represent diffuse objects, it is less realistic with specular surfaces. We consider the compression of plenoptic point clouds, wherein each voxel is associated to colors as seen by different angles. We propose an efficiently compressible representation to incorporate the plenoptic information of each voxel. We have proposed three compression methods, one based on a cylindrical projection and two others based on the intersection of the line of view with the voxel's face, one using flat boundaries and the other using a spherical boundary. Extensive tests have shown that the last two have the best performance, which are much superior than independently encoding the color attributes from each of the cameras point of views.

We present a context-driven method to encode nodes of an octree, which is typically used to encode the point-cloud geometry. Instead of using one bit per node of the tree, the context allows for deriving probabilities for that node based on distances of the actual voxel to the voxels in a reference point cloud. Accurate probabilities of the node state allow for the use of an arithmetic coder to reduce the bit rate. Results point to potentially large reductions in rate if there is a good model from which to derive the context, i.e., one can get large reductions if the reference-cloud geometry is close enough to the one being encoded.

Sparse signal representation has proven to be an extremely powerful tool in a wide range of engineering applications. However, most of the existing techniques are designed for regular data (such as audio signals and images/videos) that uniformly lies in regular Euclidian spaces. This paper aims at extending sparse representation for irregular data (such as colors of 3D point clouds) that is defined on irregular domains embedded in Euclidean spaces. Dealing with the irregular structure of such data via a virtual adaptive sampling process, we formulate sparse representation as an ℓ0-norm regularized optimization problem. Experimental results show that the proposed algorithm outperforms the state-of-the-art algorithm to a large extent: with the same number of nonzero coefficients, we improve the reconstruction quality up to 5 dB; conversely, fixing the reconstruction quality, our method uses only 55% coefficients. Using compressive sensing theory, we provide an intuitive explanation on how and why our algorithm works well in practice.

We introduce a compressible representation of 3D geometry (including its attributes, such as color texture) intermediate between polygonal meshes and point clouds called a polygon cloud. Polygon clouds, compared to polygonal meshes, are more robust to live capture noise and artifacts. Furthermore, dynamic polygon clouds, compared to dynamic point clouds, are easier to compress, if certain challenges are addressed. In this paper, we propose methods for compressing dynamic polygon clouds using transform coding of color and motion residuals. We find that, compared to static polygon clouds and a fortiori static point clouds, dynamic polygon clouds can improve color compression by up to 2-3 dB in fidelity, and can improve geometry compression up to a factor of 2-5 in bit rate.

3D immersive communications are trending as real-time point clouds capture and display of point cloud video become feasible. This paper presents a novel motion-compensated approach to encoding dynamic voxelized point clouds (VPC) at low bit rates. A simple coder breaks the VPC into blocks which are intra-frame coded or replaced by a motion-compensated version of a block in the previous frame. The decision is optimized in a rate-distortion sense, encoding with distortion both geometry and the color, at reduced bit-rates. In-loop filtering is employed to minimize compression artifacts caused by distortion in the geometry information. Simulations reveal that this simple motion compensated coder can efficiently extend the compression range of dynamic voxelized point clouds to rates below what intra-frame coding alone can accommodate, trading rate for geometry accuracy.

We propose using stationary Gaussian processes (GPs) to model the statistics of the signal on points in a point cloud, which can be considered samples of a GP at the positions of the points. Furthermore, we propose using Gaussian process transforms (GPTs), which are Karhunen-Loève transforms of the GP, as the basis of transform coding of the signal. Focusing on colored 3D point clouds, we propose a transform coder that breaks the point cloud into blocks, transforms the blocks using GPTs, and entropy codes the quantized coefficients. The GPT for each block is derived from both the covariance function of the GP and the locations of the points in the block, which are separately encoded. The covariance function of the GP is parameterized, and its parameters are sent as side information. The quantized coefficients are sorted by the eigenvalues of the GPTs, binned, and encoded using an arithmetic coder with bin-dependent Laplacian models, whose parameters are also sent as side information. Results indicate that transform coding of 3D point cloud colors using the proposed GPT and entropy coding achieves superior compression performance on most of our data sets.

Dynamic point clouds are a potential new frontier in visual communication systems. A few articles have addressed the compression of point clouds, but very few references exist on exploring temporal redundancies. This paper presents a novel motion-compensated approach to encoding dynamic voxelized point clouds at low bit rates. A simple coder breaks the voxelized point cloud at each frame into blocks of voxels. Each block is either encoded in intra-frame mode or is replaced by a motion-compensated version of a block in the previous frame. The decision is optimized in a rate-distortion sense. In this way, both the geometry and the color are encoded with distortion, allowing for reduced bit-rates. In-loop filtering is employed to minimize compression artifacts caused by distortion in the geometry information. Simulations reveal that this simple motion-compensated coder can efficiently extend the compression range of dynamic voxelized point clouds to rates below what intra-frame coding alone can accommodate, trading rate for geometry accuracy.

We present a new mathematical framework for multi-view surface reconstruction from a set of calibrated color and depth images. We estimate the occupancy probability of points in space along sight rays, and combine these estimates using a normalized product derived from Bayes' rule. The advantage of this approach is that the free space constraint is a natural consequence of the formulation, and not a separate logical operation. We present a single closed form implicit expression for the reconstructed surface in terms of the image data and camera projections, making analytic properties such as surface normals not only easy to compute, but exact. This expression can be efficiently evaluated on the GPU, making it ideal for high performance real-time applications, such as live human body capture for immersive telepresence.

The advent of advanced acquisition techniques in 3D media applications has led to an increasing trend of capturing dynamic objects and scenes via 3D point cloud sequences. This form of data is composed of time-indexed frames, each consisting of a collection of points with position and color attributes. Compression of such datasets is challenging because of the lack of efficient techniques for exploiting spatial and temporal correlations between the attributes. In our approach, we create an intermediate high-resolution representation of the point clouds, using consistent subdivisional triangular meshes, that captures all the features of the underlying object or scene. This representation is easy to obtain, significantly simplifies motion compensation and allows us to design efficient wavelet transforms using the recently developed framework of Biorthogonal Graph Wavelet Filterbanks. Preliminary experiments show that our approach can be an effective compression technique for 3D point cloud sequences.

We introduce the Gaussian Process Transform (GPT), an orthogonal transform for signals defined on a finite but otherwise arbitrary set of points in a Euclidean domain. The GPT is obtained as the Karhunen-Loéve Transform (KLT) of the marginalization of a Gaussian Process defined on the domain. Compared to the Graph Transform (GT), which is the KLT of a Gauss Markov Random Field over the same set of points whose neighborhood structure is inherited from the Euclidean domain, the GPT has up to 6 dB higher coding gain.

Interactive real-time streaming applications such as audio-video conferencing, online gaming and app streaming, place stringent requirements on the network in terms of delay, jitter, and packet loss. Many of these applications inherently involve client-to-client communication, which is particularly challenging since the performance requirements need to be met while traversing the public wide-area network (WAN). This is different from the typical situation of cloud-to-client communication, where the WAN can often be bypassed by moving a communication end-point to a cloud “edge”, close to the client. Can we nevertheless take advantage of cloud resources to improve the performance of real-time client-to-client streaming over the WAN?

We present an end-to-end system for augmented and virtual reality telepresence, called Holoportation. Our system demonstrates high-quality, real-time 3D reconstructions of an entire space, including people, furniture and objects, using a set of new depth cameras. These 3D models can also be transmitted in real-time to remote users. This allows users wearing virtual or augmented reality displays to see, hear and interact with remote participants in 3D, almost as if they were present in the same physical space. From an audio-visual perspective, communicating and interacting with remote users edges closer to face-to-face communication. This paper describes the Holoportation technical system in full, its key interactive capabilities, the application scenarios it enables, and an initial qualitative study of using this new communication medium.

The accuracy of scene flow is restricted by several challenges such as occlusion and large displacement motion. When occlusion happens, the positions inside the occluded regions lose their corresponding counterparts in preceding and succeeding frames. Large displacement motion will increase the complexity of motion modeling and computation. Moreover, occlusion and large displacement motion are highly related problems in scene flow estimation, e.g., large displacement motion often leads to considerably occluded regions in the scene. An improved dense scene flow method based on red-green-blue-depth (RGB-D) data is proposed in this paper. To handle occlusion, we model the occlusion status for each point in our problem formulation, and jointly estimate the scene flow and occluded regions. To deal with large displacement motion, we employ an over-parameterized scene flow representation to model both the rotation and translation components of the scene flow, since large displacement motion cannot be well approximated using translational motion only. Furthermore, we employ a two-stage optimization procedure for this overparameterized scene flow representation. In the first stage, we propose a new RGB-D PatchMatch method, which is mainly applied in the RGB-D image space to reduce the computational complexity introduced by the large displacement motion. According to the quantitative evaluation based on the Middlebury data set, our method outperforms other published methods. The improved performance is also comprehensively confirmed on the real data acquired by Kinect sensor.

In free-viewpoint video, there is a recent trend to represent scene objects as solids rather than using multiple depth maps. Point clouds have been used in computer graphics for a long time, and with the recent possibility of real-time capturing and rendering, point clouds have been favored over meshes in order to save computation. Each point in the cloud is associated with its 3D position and its color. We devise a method to compress the colors in point clouds, which is based on a hierarchical transform and arithmetic coding. The transform is a hierarchical sub-band transform that resembles an adaptive variation of a Haar wavelet. The arithmetic encoding of the coefficients assumes Laplace distributions, one per sub-band. The Laplace parameter for each distribution is transmitted to the decoder using a custom method. The geometry of the point cloud is encoded using the well-established octtree scanning. Results show that the proposed solution performs comparably with the current state-of-the-art, while being much more computationally efficient. We believe this paper represents the state of the art in intra-frame compression of point clouds for real-time 3D video.

This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames share some similarities, motion estimation is key to effective compression of these sequences. It, however, remains a challenging problem as the point cloud frames have varying numbers of points without explicit correspondence information. We represent the time-varying geometry of these sequences with a set of graphs, and consider 3D positions and color attributes of the point clouds as signals on the vertices of the graphs. We then cast motion estimation as a feature-matching problem between successive graphs. The motion is estimated on a sparse set of representative vertices using new spectral graph wavelet descriptors. A dense motion field is eventually interpolated by solving a graph-based regularization problem. The estimated motion is finally used for removing the temporal redundancy in the predictive coding of the 3D positions and the color characteristics of the point cloud sequences. Experimental results demonstrate that our method is able to accurately estimate the motion between consecutive frames. Moreover, motion estimation is shown to bring a significant improvement in terms of the overall compression performance of the sequence. To the best of our knowledge, this is the first paper that exploits both the spatial correlation inside each frame (through the graph) and the temporal correlation between the frames (through the motion estimation) to compress the color and the geometry of 3D point cloud sequences in an efficient way.

ImmerseBoard is a system for remote collaboration through a digital whiteboard that gives participants a 3D immersive experience, enabled only by an RGBD camera (Microsoft Kinect) mounted on the side of a large touch display. Using 3D processing of the depth images, life-sized rendering, and novel visualizations, ImmerseBoard emulates writing side-by-side on a physical whiteboard, or alternatively on a mirror. User studies involving three tasks show that compared to standard video conferencing with a digital whiteboard, ImmerseBoard provides participants with a quantitatively better ability to estimate their remote partners' eye gaze direction, gesture direction, intention, and level of agreement. Moreover, these quantitative capabilities translate qualitatively into a heightened sense of being together and a more enjoyable experience. ImmerseBoard's form factor is suitable for practical and easy installation in homes and offices.

This paper addresses the problem of motion estimation in 3D point cloud sequences that are characterized by moving 3D positions and color attributes. Motion estimation is key to effective compression of these sequences, but it remains a challenging problem as the temporally successive frames have varying sizes without explicit correspondence information. We represent the time-varying geometry of these sequences with a set of graphs, and consider 3D positions and color attributes of the points clouds as signals on the vertices of the graph. We then cast motion estimation as a feature matching problem between successive graphs. The motion is estimated on a sparse set of representative vertices using new spectral graph wavelet descriptors. A dense motion field is eventually interpolated by solving a graph-based regularization problem. The estimated motion is finally used for color compensation in the compression of 3D point cloud sequences. Experimental results demonstrate that our method is able to accurately estimate the motion and to bring significant improvement in terms of color compression performance.

We propose a system that augments touch input with visual understanding of the user to improve interaction with a large touch-sensitive display. A commodity color plus depth sensor such as Microsoft Kinect adds the visual modality and enables new interactions beyond touch. Through visual analysis, the system understands where the user is, who the user is, and what the user is doing even before the user touches the display. Such information is used to enhance interaction in multiple ways. For example, a user can use simple gestures to bring up menu items such as color palette and soft keyboard; menu items can be shown where the user is and can follow the user; hovering can show information to the user before the user commits to touch; the user can perform different functions (for example writing and erasing) with different hands; and the user's preference profile can be maintained, distinct from other users. User studies are conducted and the users very much appreciate the value of these and other enhanced interactions.

Transmitting depth maps captured from multiple viewpoints of a 3-D scene enables a wide range of receiver-side 3-D applications, including virtual view synthesis via depth-image-based rendering (DIBR). Observing that compressed depth maps from different viewpoints constitute multiple descriptions (MD) of the same signal, we propose to reconstruct 3-D surfaces of the scene by considering multiple compressed depth maps jointly. Specifically, we propose an alternating projection algorithm, inspired by the theory of projection onto convex sets (POCS), which at convergence returns a 3-D surface that satisfies three sets of conditions: spatial smoothness prior, quantization bin constraints in the block transform domain, and inter-view consistency. We present a theoretical proof that shows convergence of our algorithm under benign conditions. Compared to existing multiview depth map denoising schemes and single image de-quantization schemes, our proposed solution achieves higher objective quality for both reconstructed depth maps and synthesized virtual views.

The next step in immersive communication beyond video from a single camera is object-based free viewpoint video, which is the capture and compression of a dynamic object such that it can be reconstructed and viewed from an arbitrary viewpoint. The moving human body is a particularly useful subclass of dynamic object for object-based free viewpoint video relevant to both telepresence and entertainment. In this paper, we compress moving human body sequences by applying recently developed Graph Wavelet Filter Banks to time-varying geometry and color signals living on a mesh representation of the human body. This model-based approach significantly outperforms state-of-the-art coding of the human body represented as ordinary depth plus color video sequences.

Transmitting compactly represented geometry of a dynamic 3D scene from a sender can enable a multitude of imaging functionalities at a receiver, such as synthesis of virtual images at freely chosen viewpoints via depth-image-based rendering. While depth maps—projections of 3D geometry onto 2D image planes at chosen camera viewpoints-can nowadays be readily captured by inexpensive depth sensors, they are often corrupted by non-negligible acquisition noise. Given depth maps need to be denoised and compressed at the encoder for efficient network transmission to the decoder, in this paper, we consider the denoising and compression problems jointly, arguing that doing so will result in a better overall performance than the alternative of solving the two problems separately in two stages. Specifically, we formulate a rate-constrained estimation problem, where given a set of observed noise-corrupted depth maps, the most probable (maximum a posteriori (MAP)) 3D surface is sought within a search space of surfaces with representation size no larger than a prespecified rate constraint. Our rate-constrained MAP solution reduces to the conventional unconstrained MAP 3D surface reconstruction solution if the rate constraint is loose. To solve our posed rate-constrained estimation problem, we propose an iterative algorithm, where in each iteration the structure (object boundaries) and the texture (surfaces within the object boundaries) of the depth maps are optimized alternately. Using the MVC codec for compression of multiview depth video and MPEG free viewpoint video sequences as input, experimental results show that rate-constrained estimated 3D surfaces computed by our algorithm can reduce coding rate of depth maps by up to 32% compared with unconstrained estimated surfaces for the same quality of synthesized virtual views at the decoder.

We propose a framework for simultaneous phase unwrapping and multipath interference cancellation (SPUMIC) in homodyne time-of-flight (ToF) cameras. Our multi-frequency acquisition framework is based on parametric modeling of the multipath interference phenomena. We use robust spectral estimation methods with low computational complexity to detect and estimate multipath parameters. Using simulations and analysis we demonstrate that our proposed solution is implementable in real-time on existing ToF cameras without requiring any hardware modifications.

Transmitting compactly represented geometry of a dynamic scene from a sender can enable a multitude of 3D imaging functionalities at a receiver, such as synthesis of virtual images from freely chosen viewpoints via depth-image-based rendering (DIBR). While depth maps can now be readily captured using inexpensive depth sensors, they are often corrupted by non-negligible acquisition noise. In this paper, we derive 3D surfaces of a dynamic scene from noise-corrupted depth maps in a rate-distortion (RD) optimal manner. Specifically, unlike previous work that finds the most likely (e.g., maximum likelihood) 3D surface from noisy observations regardless of representation size, we judiciously search for the best fitting (i.e., minimum distortion) 3D surface subject to a bitrate constraint. Our RD-optimal solution reduces to the maximum likelihood solution as the rate constraint is loosened. Using the MVC codec for compression of multiview depth video and MPEG free viewpoint test sequences as input, experimental results show that RD-optimized 3D reconstructions computed by our algorithm outperform unprocessed depth maps by up to 2:42dB in PSNR of synthesized virtual views at the decoder for the same bitrate.

In a network, the location of the node on which a service is computed is inextricably linked to the locations of the paths through which the service communicates. Hence, service location can have a profound effect on quality of service, especially for communication-centric applications such as real-time multimedia. In this paper, we propose an online algorithm that uses pricing to consider server load, route congestion, and propagation delay jointly when locating servers and routes for real-time multimedia services in a network with fixed computing and communication capacities. The algorithm is online in the sense that it is able to sequentially allocate resources for services with long and unknown duration as demands arrive, without the benefit of looking ahead to later demands. By formulating the problem as one of lowest cost subgraph packing, we prove that our algorithm is neverthelessC-competitive with the optimal algorithm that looks ahead, meaning that our performance is within a constant factorCof optimal, as measured by the total number of service demands satisfied, or total user utility. Using mixing services as an example, we show through experimental results that our algorithm can adapt to cross traffic and automatically route around congestion and failure of nodes and edges, can reduce latency by 40% or more, and can pack 20% more sessions or alternatively can double the number of sessions before significant call rejection, compared with conventional approaches.

The last great advances in immersive communication were the invention of the telephone over 137 years ago and the invention of the video telephone (né television) over 86 years ago. However, a perfect storm is brewing for the next advance in immersive communication, thanks to the convergence of massive amounts of computation, bandwidth, resolution, new sensors, and new displays. It could well be the Multimedia community that turns this brew into the next great advance in immersive communication, something akin to teleportation.

Traditional multiparty audio or video conferencing uses a single node, sometimes called a multipoint control unit, or MCU, to mix audio data for the conference. We introduce a novel mixer, called a Virtual Mixer, which performs mixing in a distributed way over the network. The Virtual Mixer topology is optimized over Steiner trees using a metric of either average pairwise delay (APD) or maximum pairwise delay (MPD). Since the topology is adapted to the particular set of clients and servers available in the cloud, optimization speed is important. In order to solve this NP-hard Steiner tree optimization, we propose heuristic algorithms for finding the Pairwise-delay-optimal Tree (PT) for both APD and MPD, which are orders of magnitude faster than exhaustive search, yet find trees with delays that are minimal or within a few percent of minimal. We show through experiments both on a corporate intranet and on up to 12 PlanetLab nodes that Virtual Mixing can reduce both the APD and the MPD between clients by upwards of 50%, compared with the existing MCU-based and P2P-based mixing approaches.

Commodity depth cameras have attracted a lot of research interest recently, in particular the structured-light based Kinect cameras available on the mass market. One important application of such cameras is 3D scene reconstruction and view synthesis. However, a single depth camera often has limited field of view and there is missing depth information when synthesizing a virtual view from a new viewpoint. In this paper, we study the problem of 3D scene reconstruction from multiple structured-light based depth cameras. Since multiple cameras may cause severe interference in the regions where the projected light overlaps, we present a novel planesweeping based algorithm to handle such interference. The proposed algorithm takes into account the correlation between multiple projectors and the infrared images as well as the correlation between the infrared images, thereby recovering the depth information for both overlapped and non-overlapped regions. Simulation results demonstrate that the proposed solution is very effective on various scenes.

The most significant problem in generating virtual views from a limited number of video camera views is handling areas that have become dis-occluded by shifting the virtual view away from the camera view. We propose using temporal information to address this problem, based on the notion that dis-occluded areas may have been seen by some camera in some previous frames. We formulate the problem as one of estimating the underlying state of the object in a stochastic dynamical system, given a sequence of observations. We apply the formulation to improving the visual quality of virtual views generated from a single “color plus depth” camera, and show that our algorithm achieves better results than depth image based rendering using standard inpainting.

Augmented reality applications have focused on visually integrating virtual objects into real environments. In this paper, we propose an auditory augmented reality, where we integrate acoustic virtual objects into the real world. We sonify objects that do not intrinsically produce sound, with the purpose of revealing additional information about them. Using spatialized (3D) audio synthesis, acoustic virtual objects are placed at specific real-world coordinates, obviating the need to explicitly tell the user where they are. Thus, by leveraging the innate human capacity for 3D sound source localization and source separation, we create an audio natural user interface. In contrast with previous work, we do not create acoustic scenes by transducing low-level (for instance, pixel-based) visual information. Instead, we use computer vision methods to identify high-level features of interest in an RGB-D stream, which are then sonified as virtual objects at their respective real-world coordinates. Since our visual and auditory senses are inherently spatial, this technique naturally maps between these two modalities, creating intuitive representations. We evaluate this concept with a head-mounted device, featuring modes that sonify flat surfaces, navigable paths and human faces.

Communication has seen enormous advances over the past 100 years including radio, television, mobile phones, video conferencing, and Internet-based voice and video calling. Still, remote communication remains less natural and more fatiguing than face-to-face. The vision of immersive communication is to enable natural experiences and interactions with remote people and environments in ways that suspend disbelief in being there. This paper briefly describes the current state-of-the-art of immersive communication, provides a vision of the future and the associated benefits, and considers the technical challenges in achieving that vision. The attributes of immersive communication are described, together with the frontiers of video and audio for achieving them. We emphasize that the success of these systems must be judged by their impact on the people who use them. Recent high-quality video conferencing systems are beginning to deliver a natural experience-when all participants are in custom-designed studios. Ongoing research aims to extend the experience to a broader range of environments. Augmented reality has the potential to make remote communication even better than being physically present. Future natural and effective immersive experiences will be created by drawing upon intertwined research areas including multimedia signal processing, computer vision, graphics, networking, sensors, displays and sound reproduction systems, haptics, and perceptual modeling and psychophysics.

In this paper, we study the problem of utility maximization in peer-to-peer (P2P) systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. For certain P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by intrasession and intersession network coding. This observation allows us to develop a simple multitree formulation for the problem. For the resulting nonstrictly concave optimization problem, we develop a Primal-dual distributed algorithm and prove its global convergence using our proposed sufficient conditions. These conditions are general and add understanding to the convergence of primal-dual algorithms under nonstrictly concave settings. We implement the proposed distributed algorithm in a peer-assisted multiparty conferencing system by utilizing only end-to-end delay measurements between P2P nodes. We demonstrate its superior performance through actual experiments on a LAN testbed and the Internet.

The convergence of games and online social platforms is an exploding phenomena. The continued success of social games hinges critically on the ability to deliver smooth and highly-interactive experiences to end-users. However, it is extremely challenging to satisfy the stringent performance requirements of online social games.

We propose a novel system to analyze gestural and nonverbal cues of participants in video conferencing. These cues have previously been referred to as “honest signals” and are usually associated with the underlying cognitive state of the participants. The presented system analyzes a set of audio-visual, non-linguistic features in real time from the audio and video streams of two participants in a video conference. We show how these features can be used to compute indicators of the overall quality and type of conversation being held. The system also provides visual feedback to the participants, who then have the choice of modifying their conversational style in order to achieve the desired outcome of the video conference. Experiments on real-life data show that the system can predict the type of conversation with high accuracy using the non-linguistic signals only. Qualitative user studies highlight the positive effects of increased awareness amongst the participants about their own gestural and non-verbal cues.

With increasing computation power, network bandwidth, and improvements in display and capture technologies, fully immersive conferencing and tele-immersion is becoming ever closer to reality. Outside of video, one of the key components needed is high quality spatialized audio. This paper presents an implementation of a relatively low complexity, simple solution which allows realistic audio spatialization of arbitrary positions in a 3D video conference. When combined with pose tracking, it also allows the audio to change relative to which position on the screen the viewer is looking at.

Depth cameras are gaining interest rapidly in the market as depth plus RGB is being used for a variety of applications ranging from foreground/background segmentation, face tracking, activity detection, and free viewpoint video rendering. In this paper, we present a low-complexity, near-lossless codec for coding depth maps. This coding requires no buffering of video frames, is table-less, can encode or decode a frame in close to 5ms with little code optimization, and provides between 7:1 to 16:1 compression ratio for near-lossless coding of 16-bit depth maps generated by the Kinect camera.

Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are nonreceiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations. In this paper, we develop a family of constructive, polynomial-time algorithms that can compute P2P streaming capacity and the associated multicast trees, arbitrarily accurately for seven formulations, to a factor of 4-approximation for two formulations, and to a factor of log of the number of receivers for two formulations. The optimization problem is reformulated in each case so as to convert the combinatorial problem into a linear program with an exponential number of variables. The linear program is then solved using a primal-dual approach. The algorithms combine an outer loop of primal-dual update with an inner loop of smallest price tree construction, driven by the update of dual variables in the outer loop. We show that when the construction of smallest price tree can be carried out arbitrarily accurately in polynomial time, so can the computation of P2P streaming capacity. We also develop several efficient algorithms for smallest price tree construction. Using the developed algorithms, we investigate the impact of several factors on P2P streaming capacity using topologies derived from statistics of uplink capacities of Internet hosts.

We consider multi-rate peer-to-peer multiparty video conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video bitrate. We study and address the unique challenges introduced by maximizing utility in the multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop Primal and Primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach converges to optimal bitrates to improve user experience and offers automatic adaptation to network conditions and user preferences.

Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP Complete in general. Then, for the case of node out-degree bound, through the construction of a “Bubble algorithm”, we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a “Cluster-Tree algorithm” that provides probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

We consider multi-rate peer-to-peer multi-party conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video rate. We study and address the unique challenges introduced by multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop primal and primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach offers low end-to-end delay, low complexity and high throughput, along with automatic adaptation to network conditions and user preferences.

Motivated by P2P file transfer applications (e.g., BitTorrent) on the Internet, this paper considers the problem of delivering a file from a server to multiple receivers in a P2P network. Each receiver has an associated delay in receiving the file. We aim at understanding the optimal delay region, i.e., the set of all possible delay vectors that can be achieved. Previous work has addressed the problem of delivering the file to all receivers in minimum amount of time (equivalently, minimizing the maximum delay to the receivers), assuming peer uplinks are the only bottleneck in the network. This paper shows that it is in fact possible to significantly reduce the average delay at a slight increase in the maximum delay. Moreover, given an order at which the receivers finish downloading, the optimal delay region is characterized by a system of linear inequalities. Any point in the optimal delay region can be achieved by linear network coding. We also propose a simple routing scheme that has near-optimal empirical performance.

From an audio perspective, the present state of teleconferencing technology leaves something to be desired; speaker overlap is one of the causes of this inadequate performance. To that end, this paper presents a frequency-domain implementation of convolutive BSS specifically designed for the nature of the teleconferencing environment. In addition to presenting a novel depermutation scheme, this paper presents a least-squares post-processing scheme, which exploits segments during which only a subset of all speakers are active. Experiments with simulated and real data demonstrate the ability of the proposed methods to provide SIRs at or near that of the adaptive noise cancellation (ANC) solution which is obtained under idealistic assumptions that the ANC filters are adapted with one source being on at a time.

We consider multi-source multicast communication scenarios in which each node has an aggregate outbound traffic capacity and can directly communicate with any other node. This is motivated by peer-to-peer (P2P) information dissemination applications on the Internet in which the uplink capacity of nodes is usually the bottleneck, being several times smaller than the downlink capacity. We also allow the communication in a group to be helped by non-receiver nodes (with respect to that group) as relays. Extending an earlier result for the single source case, we show that when coding is not allowed across sources, routing is optimal. Also, as a rather surprising discovery, we show that when all groups have pairwise identical or disjoint receivers, routing is optimal even when coding across sources is allowed. Moreover, routing along a linear number of trees per source is sufficient to achieve this. The latter scenario is common in multiparty conferencing systems, hence our results have interesting practical applications in the design of infrastructure-less P2P multiparty conferencing systems.

We have found that viewing recorded meetings using traditional meeting viewers whose interfaces consist of an automatic speaker and a fixed context view does not provide sufficient information and control to the users. In particular, a survey of users who watch meeting recordings on a regular basis revealed that it is also useful to provide (1) speaker-related information, including who the speaker is talking to, looking at, and being interrupted by, and (2) more control of the interface, including changing the relative sizes of the speaker and context views and navigating within the context view. We present a 3D interface prototype designed specifically to meet these requirements when viewing recorded meetings. We describe in detail the results of a user study comparing the effectiveness of the new and traditional style interfaces with respect to these requirements. Based on this study, we present a set of guidelines for future interfaces.

In this paper, we study the problem of utility maximization in P2P systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. This may be understood as extending Kelly's seminal framework from single-path unicast over general topology to multi-path multicast over P2P topology, with network coding allowed. For certain classes of popular P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by (multi-source) network coding. This simplification result allows us to develop a new multi-tree routing formulation for the problem. Despite of the negative results in literature on applying Primal-dual algorithms to maximize utility under multi-path settings, we have been able to develop a Primal-dual distributed algorithm to maximize the aggregate utility under the multi-path routing environments. Utilizing our proposed sufficient condition, we show global exponential convergence of the Primal-dual algorithm to the optimal solution under different P2P communication scenarios we study. The algorithm can be implemented by utilizing only end-to-end delay measurements between P2P nodes; hence, it can be readily deployed on today's Internet. To support this claim, we have implemented the Primal-dual algorithm for use in a peer-assisted multi-party conferencing system and evaluated its performance through actual experiments on a LAN testbed and the Internet.

We present an energy-based technique to estimate both microphone and speaker/talker locations from an ad hoc network of microphones. An example of such ad hoc microphone network is a set of microphones built in the laptops that some meeting participants bring in a meeting room. Compared with traditional sound source localization approaches based on time of flight, our technique does not require accurate synchronization, and it does not require each laptop to emit special signals. We estimate the meeting participants' positions based on average energies of their speech signals. In addition, we present a technique, which is independent of the volumes of the speakers, to estimate the relative gains of the microphones. This is crucial to aggregate various audio channels from the ad hoc microphone network into a single stream for audio conferencing.

This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The work by Ho et al. 2004 demonstrates that random network coding can solve this problem at the potentially high cost of jointly decoding the source and the network code. Motivated by complexity considerations we consider the performance of separate source and network codes. Previous work by Effros et al. 2003 demonstrates the failure of separation between source and network codes for nonmulticast networks. We demonstrate that failure for multicast networks. We study networks with capacity constraints on edges. It is shown that the problem with two sources and two receivers is always separable. Counterexamples are presented for other cases.

This paper addresses the problem of streaming packetized media over a lossy packet network in a rate-distortion optimized way. We show that although the data units in a media presentation generally depend on each other according to a directed acyclic graph, the problem of rate-distortion optimized streaming of an entire presentation can be reduced to the problem of error-cost optimized transmission of an isolated data unit. We show how to solve the latter problem in a variety of scenarios, including the important common scenario of sender-driven streaming with feedback over a best-effort network, which we couch in the framework of Markov decision processes. We derive a fast practical algorithm for nearly optimal streaming in this scenario, and we derive a general purpose iterative descent algorithm for locally optimal streaming in arbitrary scenarios. Experimental results show that systems based on our algorithms have steady-state gains of 2-6 dB or more over systems that are not rate-distortion optimized. Furthermore, our systems essentially achieve the best possible performance: the operational distortion-rate function of the source at the capacity of the packet erasure channel.

We propose a scheme for building peer-to-peer overlay networks for broadcasting using network coding. The scheme addresses many practical issues such as scalability, robustness, constraints on bandwidth, and locality of decisions. We analyze the system theoretically and prove near optimal bounds on the parameters defining robustness and scalability. As a result we show that the effects of failures are contained locally, allowing the network to grow exponentially with server load. We also argue that adversarial failures are no more harmful than random failures.

In this paper, the network planning problem in wireless ad hoc networks is formulated as the problem of allocating physical and medium access layer resources or supplies to minimize a cost function, while fulfilling certain end-to-end communication demands, which are given as a collection of multicast sessions with desired transmission rates. We propose an iterative cross-layer optimization, which alternates between: 1) jointly optimizing the timesharing in the medium access layer and the sum of max of flows assignment in the network layer and 2) updating the operational states in the physical layer. We consider two objectives, minimizing aggregate congestion and minimizing power consumption, respectively, corresponding to operating in a bandwidth-limited regime and in an energy-limited regime. The end result is a set of achievable tradeoffs between throughput and energy efficiency, in a given wireless network with a given traffic pattern. We evaluate our approach quantitatively by simulations of community wireless networks and compare with designs that decouple the layers. We demonstrate that significant performance advantages can be achieved by adopting a full-fledged cross-layer optimization. Furthermore, we observe that optimized solutions generally profit from network coding, physical-layer broadcasting, and traffic-dependent physical states.

The minimum energy required to transmit one bit of information through a network characterizes the most economical way to communicate in a network. In this paper, we show that, under a layered model of wireless networks, the minimum energy-per-bit for multicasting in a mobile ad hoc network can be found by a linear program; the minimum energy-per-bit can be attained by performing network coding. Compared with conventional routing solutions, network coding not only allows a potentially lower energy-per-bit to be achieved, but also enables the optimal solution to be found in polynomial time, in sharp contrast with the NP-hardness of constructing the minimum-energy multicast tree as the optimal routing solution. We further show that the minimum energy multicast formulation is equivalent to a cost minimization with linear edge-based pricing, where the edge prices are the energy-per-bits of the corresponding physical broadcast links. This paper also investigates minimum energy multicasting with routing. Due to the linearity of the pricing scheme, the minimum energy-per-bit for routing is achievable by using a single distribution tree. A characterization of the admissible rate region for routing with a single tree is presented. The minimum energy-per-bit for multicasting with routing is found by an integer linear program. We show that the relaxation of this integer linear program, studied earlier in the Steiner tree literature, can now be interpreted as the optimization for minimum energy multicasting with network coding. In short, this paper presents a unifying study of minimum energy multicasting with network coding and routing.

The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.

Network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast is compared in this paper. To enable the comparison, we develop greedy tree packing algorithms that repeatedly pack the maximum-rate distribution tree and a greedy tree packing algorithm based on Lovasz' proof to Edmonds' theorem. We then investigate the potential advantages of network coding over routing. In terms of throughput, tree packing performs comparably to network coding on the network graphs of six Internet service providers. However, network coding offers additional benefits, including fewer network resources consumed, ease of management, and robustness.

The minimum energy required to transmit a bit of information through a network characterizes the most economical way to communicate in a network. In this paper, we show that under a simplified layered model of wireless networks, the minimum-energy multicast problem in mobile ad hoc networks is solvable as a linear program, assuming network coding. Compared with conventional routing solutions, network coding not only promises a potentially lower energy-per-bit, but also enables finding the optimal solution in polynomial time, in sharp contrast with the NP-hardness of constructing the minimum-energy multicast tree as the optimal routing solution.

This paper addresses the problem of streaming packetized media over a lossy packet network to a wireless client, in a rate-distortion optimized way. We introduce an incremental redundancy error-correction scheme that combats the effects of both packet loss and bit errors in an end-to-end fashion, without support from the underlying network or from an intermediate base station. The scheme is employed within an optimization framework that enables the sender to compute which packets it should send, out of all the packets it could send at a given transmission opportunity, in order to meet an average transmission-rate constraint while minimizing the average end-to-end distortion. Experimental results show that our system is robust and maintains quality of service over a wide range of channel conditions. Up to 8 dB performance gains are registered over systems that are not rate-distortion optimized, at bit-error rates as large as 10/sup -2/.

Video standards make use of a video complexity verifier (VCV) to characterize and regulate the decoding complexity of a compliant bitstream. In previous VCV models, the minimum level of computational capacity required to decode a given bitstream is strictly related to the peak decoding complexity of an individual frame in the sequence. This contribution presents a new VCV model, which is more flexible than prior VCV models. The proposed VCV model permits the bitstream to be decoded by devices operating at significantly smaller levels of peak computational capacity. The trade-off is a slight increase in additional delay and memory. Simulation results illustrate these benefits of the new VCV model.

We consider the problem of distributing "live" streaming media content to a potentially large and highly dynamic population of hosts. Peer-to-peer content distribution is attractive in this setting because the bandwidth available to serve content scales with demand. A key challenge, however, is making content distribution robust to peer transience. Our approach to providing robustness is to introduce redundance; both in network paths and in data. We use multiple, diverse distribution trees to provide redundancy in network paths and multiple description coding (MDC) to provide redundancy in data. We present a simple tree management algorithm that provides the necessary path diversity and describe an adaptation framework for MDC based on scalable receiver feedback. We evaluate these using MDC applied to real video data coupled with real usage traces from a major news site that experienced a large flash crowd for live streaming content. Our results show very significant benefits in using multiple distribution trees and MDC, with a 22 dB improvement in PSNR in some cases.

In video coding standards, a compliant bit stream must be decoded by a hypothetical decoder that is conceptually connected to the output of an encoder and consists of a decoder buffer, a decoder, and a display unit. This virtual decoder is known as the hypothetical reference decoder (HRD) in H.263 and the video buffering verifier in MPEG. The encoder must create a bit stream so that the hypothetical decoder buffer does not overflow or underflow. These previous decoder models assume that a given bit stream will be transmitted through a channel of a known bit rate and will be decoded (after a given buffering delay) by a device of some given buffer size. Therefore, these models are quite rigid and do not address the requirements of many of today's important video applications such as broadcasting video live or streaming pre-encoded video on demand over network paths with various peak bit rates to devices with various buffer sizes. In this paper, we present a new HRD for H.264/AVC that is more general and flexible than those defined in prior standards and provides significant additional benefits.

An entropy-constrained quantizer Q is optimal if it minimizes the expected distortion D(Q) subject to a constraint on the output entropy H(Q). We use the Lagrangian formulation to show the existence and study the structure of optimal entropy-constrained quantizers that achieve a point on the lower convex hull of the operational distortion-rate function D/sub h/(R) = inf/sub Q/{D(Q) : H(Q) /spl les/ R}. In general, an optimal entropy-constrained quantizer may have a countably infinite number of codewords. Our main results show that if the tail of the source distribution is sufficiently light (resp., heavy) with respect to the distortion measure, the Lagrangian-optimal entropy-constrained quantizer has a finite (resp., infinite) number of codewords. In particular, for the squared error distortion measure, if the tail of the source distribution is lighter than the tail of a Gaussian distribution, then the Lagrangian-optimal quantizer has only a finite number of codewords, while if the tail is heavier than that of the Gaussian, the Lagrangian-optimal quantizer has an infinite number of codewords.

We consider the problem of streaming packetized media over the Internet from a server through a base station to a wireless client, in a rate-distortion optimized way. For error control, we employ an incremental redundancy scheme, in which the server can incrementally transmit parity packets in response to negative acknowledgements fed back from the client. 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.

This paper addresses the problem of streaming packetized media over a lossy packet network to a wireless client, in a rate-distortion optimized way. We introduce an incremental redundancy scheme that combats the effects of both packet loss and bit errors in an end-to-end fashion, without support from the underlying network or from an intermediate base station. The scheme is combined with an optimization framework that enables the sender to compute which packets it should send, out of all the packets it could send at a given transmission opportunity, in order to meet an average rate constraint while minimizing the average end-to-end distortion. Experimental results show that our system is robust and maintains a quality of service over a wide range of channel conditions. Up to 8 dB performance gains are registered over systems that are not rate-distortion optimized, at bit error rates as large as 10−2.

Caching of Internet content in caches local to users is beneficial to both users and the network, because it reduces retrieval times for the user as well as reduces load on the network. However, it comes at the cost of storage in the cache, which can be large, particularly when multimedia objects are cached. In this paper, we address the problem of caching multimedia objects such as audio and video streams, in a cost-distortion optimized way. That is, we seek caching policies that minimize the cost of both storage and transmission while minimizing the distortion seen by the user (or equivalently, maximizing the quality seen by the user). Simulation results demonstrate that caching in a cost-distortion optimized manner leads to significant improvements over the case where no caching is performed.

Video coding standards require that a compliant bit stream be decodable by a hypothetical decoder that is conceptually connected to the output of an encoder and consists of a decoder buffer, a decoder, and a display unit. The encoder must create a bit stream so that the hypothetical decoder buffer does not overflow or underflow. Previous decoder models assume that a given bit stream will be transmitted through a channel of a given constant bit rate and will be decoded (after a given buffering delay) by a device of some given buffer size. Therefore, these models are quite rigid and do not address the requirements of many of today's important video applications such as broadcasting live video or streaming pre-encoded video on demand over network paths with various peak bit rates to devices with various buffer sizes. In this contribution, we present a new hypothetical reference decoder for JVT that is more general and flexible than those defined in prior standards and provides significant additional benefits.

We address the problem of multimedia streaming over DiffServ networks that offer various qualities of service (QoS) at different price points. In particular, we seek cost-distortion optimized transmission policies that minimize the distortion seen by the client under a cost constraint. Our results show that for on-demand streaming of stored media, DiffServ networks provide little or no gain over networks that offers only a single, cost-effective, QoS. However, for real-time conversational communication or multicast streaming, optimized transmission over DiffServ networks can perform better than optimized transmission over any single QoS by over 2 dB at the same cost.

In this paper, we discuss the problem of distributing streaming media content, both live and on-demand, to a large number of hosts in a scalable way. Our work is set in the context of the traditional client-server framework. Specifically, we consider the problem that arises when the server is overwhelmed by the volume of requests from its clients. As a solution, we propose Cooperative Networking (CoopNet), where clients cooperate to distribute content, thereby alleviating the load on the server. We discuss the proposed solution in some detail, pointing out the interesting research issues that arise, and present a preliminary evaluation using traces gathered at a busy news site during the ash crowd that occurred on September 11, 2001.

This paper addresses the problem of streaming packetized media over a lossy packet network, in a rate-distortion optimized way. Out of all the packets that a sender could transmit at a given transmission opportunity, we show how the sender should compute which packets, if any, to transmit in order to meet an average rate constraint while minimizing the average end-to-end distortion. Experimental results show that our system has steady-state gains of 3-7 dB or more over systems that are not rate-distortion optimized.

We consider the problem of error control for receiver-driven layered multicast of audio and video over the Internet. The sender injects into the network multiple source layers and multiple channel coding (parity) layers, some of which are delayed relative to the source, Each receiver subscribes to the number of source layers and the number of parity layers that optimizes the receiver's quality for its available bandwidth and packet loss probability. We augment this layered FEC system with layered pseudo-ARQ. Although feedback is normally problematic in broadcast situations, ARQ can be simulated by having the receivers subscribe and unsubscribe to the delayed parity layers to receive missing information. This pseudo-ARQ scheme avoids an implosion of repeat requests at the sender and is scalable to an unlimited number of receivers, We show gains of 4-18 dB on channels with 20% loss over systems without error control and additional gains of 1-13 dB when FEC is augmented by pseudo-ARQ in a hybrid system, Optimal error control in the hybrid system is achieved by an optimal policy for a Markov decision process.

We consider the problem of joint source/channel coding of real-time sources, such as audio and video, for the purpose of multicasting over the Internet. The sender injects into the network multiple source layers and multiple channel (parity) layers, some of which are delayed relative to the source. Each receiver subscribes to the number of source layers and the number of channel layers that optimizes the source-channel rate allocation for that receiver's available bandwidth and packet loss probability. We augment this layered FEC system with layered ARQ. Although feedback is normally problematic in broadcast situations, ARQ is simulated by having the receivers subscribe and unsubscribe to the delayed channel coding layers to receive missing information. This pseudo-ARQ scheme avoids an implosion of repeat requests at the sender, and is scalable to an unlimited number of receivers. We show gains of up to 18 dB on channels with 20% loss over systems without error control, and additional gains of up to 13 dB when FEC is augmented by pseudo-ARQ in a hybrid system. The hybrid system is controlled by an optimal policy for a Markov decision process.

This paper presents a POCS-based algorithm for consistent reconstruction of a signal x/spl isin/R/sup K/ from any subset of quantized coefficients y/spl epsiv/R/sup N/ in an N/spl times/K overcomplete frame expansion y=Fx, N=2K. By choosing the frame operator F to be the concatenation of two K/spl times/K invertible transforms, the projections may be computed in R/sup K/ using only the transforms and their inverses, rather than in the larger space R/sup N/ using the pseudo-inverse as proposed in earlier work. This enables practical reconstructions from overcomplete frame expansions based on wavelet, subband, or lapped transforms of an entire image, which has heretofore not been possible.

Three-dimensional (2D+T) wavelet coding of video using SPIHT has been shown to outperform standard predictive video coders on complex high-motion sequences, and is competitive with standard predictive video coders on simple low-motion sequences. However, on a number of typical moderate-motion sequences characterized by largely rigid motions, 3D SPIHT performs several dB worse than motion-compensated predictive coders, because it is does not take advantage of the real physical motion underlying the scene. We introduce global motion compensation for 3D subband video coders, and find 0.5 to 2 dB gain on sequences with dominant background motion. Our approach is a hybrid of video coding based on sprites, or mosaics, and subband coding.

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

The state of the standardization of the Systems part of ISO/IEC JTC1/SC29/WG11 (MPEG-4 Systems) as specified early 1997 is presented. First, a rationale and the architecture of the complete Systems are described. Based on the rapid technological advances in software and in hardware, the MPEG-4 Systems provides for a framework for the integration of natural and synthetic streamed and synchronised media. The different fields of interest in Systems are then developed from the description of audiovisual scenes to the definition of the multiplex. The programmability of the standard is described for composition and decompression and the language adopted by MPEG-4 on purpose of syntax description is fully detailed. Finally, a conclusion and the future evolutions of the specifications are presented.

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

A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that "quantizes" the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n/sup -1/ log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n/sup -1/) when the universe of sources is countable, and as O(n/sup -1+/spl epsiv//) when the universe of sources is infinite-dimensional, under appropriate conditions.

This paper presents techniques for the design of generic block transform based vector quantizer encoders implemented by table lookups. In these table lookup encoders, input vectors to the encoders are used directly as addresses in code tables to choose the codewords. There is no need to perform the forward or reverse transforms. They are implemented in the tables. In order to preserve manageable table sizes for large dimension VQ's, we use hierarchical structures to quantize the vector successively in stages. Since both the encoder and decoder are implemented by table lookups, there are no arithmetic computations required in the final system implementation. The algorithms are a novel combination of any generic block transform (DCT, Haar, WHT) and hierarchical vector quantization. They use perceptual weighting and subjective distortion measures in the design of VQ's. They are unique in that both the encoder and the decoder are implemented with only table lookups and are amenable to efficient software and hardware solutions.

We introduce a two-stage bit allocation algorithm analogous to the algorithm for weighted universal vector quantization (WUVQ). The encoder uses a collection of possible bit allocations (typically in the form of a collection of quantization matrices) rather than a single bit allocation (or single quantization matrix). We describe both an encoding algorithm for achieving optimal compression using a collection of bit allocations and a technique for designing locally optimal collections of bit allocations. We demonstrate performance on a JPEG style coder using the mean squared error (MSE) distortion measure. On a sequence of medical brain scans, the algorithm achieves up to 2.5 dB improvement over a single bit allocation system, up to 5 dB improvement over a WUVQ with first- and second-stage vector dimensions equal to 16 and 4 respectively, and up to 12 dB improvement over an entropy constrained vector quantizer (ECVQ) using 4 dimensional vectors.

This paper presents an algorithm for scalable compression using tree structured vector quantization (TSVQ) of perceptually weighted block, lapped, or wavelet transforms. The algorithm produces an embedded bit-stream to support decoders with various spatial and temporal resolutions. Bandwidth scalability with a dynamic range from a few kbps to several Mbps is provided. The algorithm further supports decoders with varying alphabet size, computation, memory, latency and power requirements. The embedded bit-stream produced is prioritized with bits arranged in order of visual importance. The algorithm also allows easy joint-source channel coding on heterogenous networks. The subjective quality of compressed images improves significantly by the use of perceptual distortion measures.

We introduce a two-stage universal transform code for image compression. The code combines Karhunen-Loeve transform coding with weighted universal bit allocation (WUBA) in a two-stage algorithm analogous to the algorithm for weighted universal vector quantization (WUVQ). The encoder uses a collection of transform/bit allocation pairs rather than a single transform/bit allocation pair (as in JPEG) or a single transform with a variety of bit allocations (as in WUBA). We describe both an encoding algorithm for achieving optimal compression using a collection of transform/bit allocation pairs and a technique for designing locally optimal collections of transform/bit allocation pairs. We demonstrate the performance using the mean squared error distortion measure. On a sequence of combined text and gray scale images, the algorithm achieves up to a 2 dB improvement over a JPEG style coder using the discrete cosine transform (DCT) and an optimal collection of bit allocations, up to a 3 dB improvement over a JPEG style coder using the DCT and a single (optimal) bit allocation, up to 6 dB over an entropy constrained WUVQ with first- and second-stage vector dimensions equal to 16 and 4 respectively, and up to a 10 dB improvement over an entropy constrained vector quantizer (ECVQ) with a vector dimension of 4.

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

The deterministic annealing algorithm for data clustering is extended to address the trellis quantizer design problem. The approach is derived within information theory and probability theory, using the principle of maximum entropy to induce a distribution over all possible path encodings of the training set. The resulting method is intimately connected to estimation procedures on Markov chains. Performance gains over known methods are obtained for memoryless, multimodal scalar sources as well as for the vector Gaussian and Laplacian sources. The method is also suggested for an estimation problem in hidden Markov models. For a Gaussian mixture state example, this approach achieves a greater likelihood value than the best result of standard Baum-Welch re-estimation, based on numerous initializations within the data.>

We introduce a method for locally optimal variable-to-variable length source coding with distortion, and apply it to coding the linear predictive coefficients of speech. The method is similar to entropy-constrained vector quantization, but it uses a dynamic programming algorithm to encode. The method automatically discovers variable-length source structure, in this case the acoustic-phonetic structure of speech. Using this structure, it is possible to compress the linear predictive coefficients of speech to one-third the rate of entropy-constrained vector quantization of speech, with no increase in spectral distortion. Auditory tests reveal that using this method, the spectral component of speech can be coded naturally and intelligibly to as low as 50 bits per second.>

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

Document image decoding (DID) is a proposed generic framework for document recognition that is based on an explicit communication theory view of the processes of document creation, transmission and interpretation. This paper presents a brief summary of work in DID carried out at the Xerox Palo Alto Research Center over the past several years.>

This paper addresses the problem of collaborative video over "heterogeneous" networks. Current standards for video compression are not designed to deal with this problem. We define an additional set of metrics (i.e., in addition to the standard rate versus distortion measure) to evaluate compression algorithms for this application. We then present an efficient algorithm for video compression in such an environment. The algorithm is a novel combination of the discrete wavelet transform and hierarchical vector quantization. It is unique in that both the encoder and the decoder are implemented with only table lookups and are amenable to efficient software and hardware solutions.>

Document image decoding (DID) is a communication theory approach to document image recognition. In DID, a document recognition problem is viewed as consisting of three elements: an image generator, a noisy channel and an image decoder. A document image generator is a Markov source (stochastic finite-state automaton) that combines a message source with an imager. The message source produces a string of symbols, or text, that contains the information to be transmitted. The imager is modeled as a finite-state transducer that converts the 1D message string into an ideal 2D bitmap. The channel transforms the ideal image into a noisy observed image. The decoder estimates the message, given the observed image, by finding the a posteriori most probable path through the combined source and channel models using a Viterbi-like dynamic programming algorithm. The proposed approach is illustrated on the problem of decoding scanned telephone yellow pages to extract names and numbers from the listings. A finite-state model for yellow page columns was constructed and used to decode a database of scanned column images containing about 1100 individual listings.>

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

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

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

A framework for document image recognition, called document image decoding (DID), that supports the automatic generation of custom document recognition systems from user-specified document models is discussed. A document recognition problem is viewed as consisting of a message source, an imager, a noisy channel, and an image decoder (recognizer). The inputs to a decoder generator are explicit models for the message source, imager and channel; the output is a specialized program that decodes an image in terms of these models. The models used in DID are based on a stochastic attribute grammar model of document production. Use of an automatically generated decoder to analyze telephone yellow pages is described.>

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

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

An iterative algorithm that finds a locally optimal partition for an arbitrary loss function, in time linear in N for each iteration is presented. The algorithm is a K-means-like clustering algorithm that uses as its distance measure a generalization of Kullback's information divergence. Moreover, it is proven that the globally optimal partition must satisfy a nearest neighbour condition using divergence as the distance measure. These results generalize similar results of L. Breiman et al. (1984) to an arbitrary number of classes or regression variables and to an arbitrary number of bills. Experimental results on a text-to-speech example are provided and additional applications of the algorithm, including the design of variable combinations, surrogate splits, composite nodes, and decision graphs, are suggested.>

Vector quantization (VQ) followed by entropy coding is used to compress linear predictive coefficients (LPCs) of speech into a variable-rate representation with distortion. It is shown in the LPC case that when a conditional entropy coder is used i.e., when the entropy code used for the current codeword is conditioned on the previous codeword, then a conditional version of entropy constrained vector quantizer (ECVQ) outperforms a conditional version of the straightforward approach by over 27%. Thus, conditioning restores the usual gain of ECVQ over standard VQ. This 27% reduction in bit rate is over and above the 42% reduction in bit rate already obtained by using a conditional rather than memoryless entropy coder in the straightforward approach. The product of these reductions is an overall reduction of 60% in average rate from the original, fixed-rate LPC system.>

Asymptotic expressions for the capacity of an associative memory proposed by P. Kanerva (1984) are derived. Capacity is defined as the maximum number of random binary words that can be stored at random addresses so that the probability that a word is in error is arbitrarily small when it is retrieved by an n-bit address containing fewer than delta n errors, delta>

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