We introduce Region-Adaptive Learned Hierarchical Encoding (RALHE) for 3D Gaussian Splatting (3DGS) data. While 3DGS has recently become popular for novel view synthesis, the size of trained models limits its deployment in bandwidth-constrained applications such as volumetric media streaming. To address this, we propose a learned hierarchical latent representation that builds upon the principles of “overfitted” learned image compression (e.g., Cool-Chic and C3) to efficiently encode 3DGS attributes. Unlike images, 3DGS data have irregular spatial distributions of Gaussians (geometry) and consist of multiple attributes (signals) defined on the irregular geometry. Our codec is designed to account for these differences between images and 3DGS. Specifically, we leverage the octree structure of the voxelized 3DGS geometry to obtain a hierarchical multi-resolution representation. Our approach overfits latents to each Gaussian attribute under a global rate constraint. These latents are decoded independently through a lightweight decoder network. To estimate the bitrate during training, we employ an autoregressive probability model that leverages octree-derived contexts from the 3D point structure. The multi-resolution latents, decoder, and autoregressive entropy coding networks are jointly optimized for each Gaussian attribute. Experiments on 3DGS models from the Synthetic-NeRF dataset demonstrate that the proposed RALHE compression framework achieves a rendering PSNR gain of up to 2 dB at low bitrates ($\leq 1 \text{MB}$) compared to the baseline 3DGS compression methods.

Many images and videos are primarily processed by computer vision algorithms, involving only occasional human inspection. When this content requires compression before processing, e.g., in distributed applications, coding methods must optimize for both visual quality and downstream task performance. We first show that, given the features obtained from the original and the decoded images, an approach to reduce the effect of compression on a task loss is to perform rate-distortion optimization (RDO) using the distance between features as a distortion metric. However, optimizing directly such a rate-distortion trade-off requires an iterative workflow of encoding, decoding, and feature evaluation for each coding parameter, which is computationally impractical. We address this problem by simplifying the RDO formulation to make the distortion term computable using block-based encoders. We first apply Taylor's expansion to the feature extractor, recasting the feature distance as a quadratic metric with the Jacobian matrix of the neural network. Then, we replace the linearized metric with a block-wise approximation, which we call input-dependent squared error (IDSE). To reduce computational complexity, we approximate IDSE using Jacobian sketches. The resulting loss can be evaluated block-wise in the transform domain and combined with the sum of squared errors (SSE) to address both visual quality and computer vision performance. Simulations with AVC across multiple feature extractors and downstream neural networks show up to 10% bit-rate savings for the same computer vision accuracy compared to RDO based on SSE, with no decoder complexity overhead and just a 7% encoder complexity increase.

This paper develops fast graph Fourier transform (GFT) algorithms with O(nlogn) runtime complexity for rank-one updates of the path graph. We first show that several commonly-used audio and video coding transforms belong to this class of GFTs, which we denote by DCT+. Next, starting from an arbitrary generalized graph Laplacian and using rank-one perturbation theory, we provide a factorization for the GFT after perturbation. This factorization is our central result and reveals a progressive structure: we first apply the unperturbed Laplacian’s GFT and then multiply the result by a Cauchy matrix. By specializing this decomposition to path graphs and exploiting the properties of Cauchy matrices, we show that Fast DCT+ algorithms exist. We also demonstrate that progressivity can speed up computations in applications involving multiple transforms related by rank-one perturbations (e.g., video coding) when combined with pruning strategies. Our results can be extended to other graphs and rank-k perturbations. Runtime analyses show that Fast DCT+ provides computational gains over the naive method for graph sizes larger than 64, with runtime approximately equal to that of 8 DCTs.

Choosing an appropriate frequency definition and norm is critical in graph signal sampling and reconstruction. Most previous works define frequencies based on the spectral properties of the graph and use the same frequency definition and ℓ2-norm for optimization for all sampling sets. Our previous work demonstrated that using a sampling-set-dependent norm (and corresponding frequency definition) can address challenges in conventional bandlimited approximations for graph signals, particularly with model mismatches and irregularly distributed data. This work proposes a method for selecting sampling sets tailored to the sampling-set-adaptive GFT-based interpolation. When the graph models the inverse covariance of the data, we show that this adaptive GFT enables tracking bandlimited model mismatch error and its effect in reconstruction, leveraging the spectral folding property, analogous to aliasing error in classical DSP. We propose a sampling set selection algorithm to minimize the worst-case bandlimited model mismatch error. We consider partitioning a set of sensors sampling a continuous spatial process as an application. Our experiments show that sampling and reconstruction using sampling-set-adaptive GFT significantly outperform methods that used fixed GFTs and bandwidth-based criterion.

In real-time applications utilizing point clouds, no-reference point cloud quality assessment (NR-PCQA) methods are essential to improve the accuracy of downstream tasks. For example, in point cloud denoising, NR-PCQA results can be benchmarks for determining the optimal parameters when reference data are unavailable. This paper presents an accurate and fast NR-PCQA method based on graph signal processing. First, we propose new features derived from graph signal variation (GSV) to train a support vector regression model. These features improve the correlation with subjective scores and the robustness against inaccurate graph construction. Second, we present a point selection technique based on graph edge weights that allows us to exclude less relevant points, which results in a precise PCQA. Third, we propose a diagonal scan-line graph (DSLG) construction with a superior tradeoff between accurate and fast graph construction. Our experiments demonstrate improved accuracy and computation time compared with conventional methods with three types of open datasets.

We introduce a novel uncertainty principle for generalized graph signals that extends classical time-frequency and graph uncertainty principles into a unified framework. By defining joint vertex-time and spectral-frequency spreads, we quantify signal localization across these domains, revealing a trade-off between them. This framework allows us to identify a class of signals with maximal energy concentration in both domains, forming the fundamental atoms for a new joint vertex-time dictionary. This dictionary enhances signal reconstruction under practical constraints, such as intermittent data, commonly encountered in sensor and social networks. Numerical experiments on real-world datasets demonstrate the effectiveness of the proposed approach, showing improved reconstruction accuracy and noise robustness compared to existing methods.

Service providers must encode a large volume of noisy videos to meet the demand for user-generated content (UGC) in online video-sharing platforms. However, low-quality UGC challenges conventional codecs based on rate-distortion optimization (RDO) with full-reference metrics (FRMs). While effective for pristine videos, FRMs drive codecs to preserve artifacts when the input is degraded, resulting in suboptimal compression. A more suitable approach used to assess UGC quality is based on non-reference metrics (NRMs). However, RDO with NRMs as a measure of distortion requires an iterative workflow of encoding, decoding, and metric evaluation, which is computationally impractical. This paper overcomes this limitation by linearizing the NRM around the uncompressed video. The resulting cost function enables block-wise bit allocation in the transform domain by estimating the alignment of the quantization error with the gradient of the NRM. To avoid large deviations from the input, we add sum of squared errors (SSE) regularization. We derive expressions for both the SSE regularization parameter and the Lagrangian, akin to the relationship used for SSE-RDO. Experiments with images and videos show bitrate savings of more than 30% over SSE-RDO using the target NRM, with no decoder complexity overhead and minimal encoder complexity increase.

Data-dependent transforms are increasingly being incorporated into next-generation video coding systems such as AVM, a codec under development by the Alliance for Open Media (AOM), and VVC. To circumvent the computational complexities associated with implementing non-separable data-dependent transforms, combinations of separable primary transforms and non-separable secondary transforms have been studied and integrated into video coding standards. These codecs often utilize rate-distortion optimized transforms (RDOT) to ensure that the new transforms complement existing transforms like the DCT and the ADST. In this work, we propose an optimization framework for jointly designing primary and secondary transforms from data through a rate-distortion optimized clustering. Primary transforms are assumed to follow a path-graph model, while secondary transforms are non-separable. We empirically evaluate our proposed approach using AVM residual data and demonstrate that 1) the joint clustering method achieves lower total RD cost in the RDOT design framework, and 2) jointly optimized separable path-graph transforms (SPGT) provide better coding efficiency compared to separable KLTs obtained from the same data.

We present a novel compression framework for 3D Gaussian splatting (3DGS) data that leverages transform coding tools originally developed for point clouds. Contrary to existing 3DGS compression methods, our approach can produce compressed 3DGS models at multiple bitrates in a computationally efficient way. Point cloud voxelization is a discretization technique that point cloud codecs use to improve coding efficiency while enabling the use of fast transform coding algorithms. We propose an adaptive voxelization algorithm tailored to 3DGS data, to avoid the inefficiencies introduced by uniform voxelization used in point cloud codecs. We ensure the positions of larger volume Gaussians are represented at high resolution, as these significantly impact rendering quality. Meanwhile, a low-resolution representation is used for dense regions with smaller Gaussians, which have a relatively lower impact on rendering quality. This adaptive voxelization approach significantly reduces the number of Gaussians and the bitrate required to encode the 3DGS data. After voxelization, many Gaussians are moved or eliminated. Thus, we propose to fine-tune/recolor the remaining 3DGS attributes with an initialization that can reduce the amount of retraining required. Experimental results on pre-trained datasets show that our proposed compression framework outperforms existing methods.

Indirect surveys, in which respondents provide information about other people they know, have been proposed for estimating (nowcasting) the size of a hidden population where privacy is important or the hidden population is hard to reach. Examples include estimating casualties in an earthquake, conditions among female sex workers, and the prevalence of drug use and infectious diseases. The Network Scale-up Method (NSUM) is the classical approach to developing estimates from indirect surveys, but it was designed for one-shot surveys. Further, it requires certain assumptions and asking for or estimating the number of individuals in each respondent's network. In recent years, surveys have been increasingly deployed online and can collect data continuously (e.g., COVID-19 surveys on Facebook during much of the pandemic). Conventional NSUM can be applied to these scenarios by analyzing the data independently at each point in time, but this misses the opportunity of leveraging the temporal dimension. We propose to use the responses from indirect surveys collected over time and develop analytical tools (i) to prove that indirect surveys can provide better estimates for the trends of the hidden population over time, as compared to direct surveys and (ii) to identify appropriate temporal aggregations to improve the estimates. We demonstrate through extensive simulations that our approach outperforms traditional NSUM and direct surveying methods. We also empirically demonstrate the superiority of our approach on a real indirect survey dataset of COVID-19 cases.

A basic premise in graph signal processing (GSP) is the existence of an underlying graph capturing pairwise similarities/correlations between nodes, using which graph filtering tasks such as denoising and interpolation are performed. In practice, node-to-node similarities often evolve over time, and thus, ideally, the graph structure should adapt accordingly. In this paper, we model the temporal changes in the adjacency matrix between two consecutive time instants as a low-rank matrix. Specifically, given an initial graph structure, we jointly interpolate a partial signal and estimate a graph at later times using graph signal smoothness priors and a low-rank prior for the adjacency difference matrix. We alternate optimization steps: given a fixed graph, the signal is computed as a solution to a linear system using conjugate gradient (CG), and given a fixed signal, the adjacency matrix is optimized via a new variant of proximal gradient descent (PGD). Experiments show that our joint optimization produces better interpolation results than existing graph learning schemes.

In this study, we challenge the traditional approach of frequency analysis on directed graphs, which typically relies on a single measure of signal variation such as total variation. We argue that the inherent directionality in directed graphs necessitates a multifaceted analytical approach that incorporates multiple signal variations definitions. Our methodology leverages the polar decomposition to define two distinct variations, each associated with different matrices derived from this decomposition. This approach provides a novel interpretation in the node domain and reveals aspects of graph signals that may be overlooked with a singular measure of variation. Additionally, we develop graph filters specifically designed to smooth graph signals in accordance with our proposed variations. These filters allow for bypassing costly filtering operations associated with the original graph through effective cascading. We demonstrate the efficacy of our methodology using an M-block cyclic graph example, validating our claims and showcasing the advantages of our multifaceted approach in analyzing signals on directed graphs.

In most work to date, graph signal sampling and reconstruction algorithms are intrinsically tied to graph properties, assuming bandlimitedness and optimal sampling set choices. However, practical scenarios often defy these assumptions, leading to suboptimal performance. In the context of sampling and reconstruction, graph irregularities lead to varying contributions from sampled nodes for interpolation and differing levels of reliability for interpolated nodes. The existing graph Fourier transform (GFT)-based methods in the literature make bandlimited signal approximations without considering graph irregularities and the relative significance of nodes, resulting in suboptimal reconstruction performance under various mismatch conditions. In this paper, we leverage the GFT equipped with a specific inner product to address graph irregularities and account for the relative importance of nodes during the bandlimited signal approximation and interpolation process. Empirical evidence demonstrates that the proposed method outperforms other GFT-based approaches for bandlimited signal interpolation in challenging scenarios, such as sampling sets selected independently of the underlying graph, low sampling rates, and high noise levels.

In this paper, we propose a method, based on graph signal processing, to optimize the choice of k in k-nearest neighbor graphs (kNNGs). kNN is one of the most popular approaches and is widely used in machine learning and signal processing. The parameter k represents the number of neighbors that are connected to the target node; however, its appropriate selection is still a challenging problem. Therefore, most kNNGs use ad hoc selection methods for k. In the proposed method, we assume that a different k can be chosen for each node. We formulate a discrete optimization problem to seek the best k with a constraint on the sum of distances of the connected nodes. The optimal k values are efficiently obtained without solving a complex optimization. Furthermore, we reveal that the proposed method is closely related to existing graph learning methods. In experiments on real datasets, we demonstrate that the kNNGs obtained with our method are sparse and can determine an appropriate variable number of edges per node. We validate the effectiveness of the proposed method for point cloud denoising, comparing our denoising performance with achievable graph construction methods that can be scaled to typical point cloud sizes (e.g., thousands of nodes).

Point clouds are utilized in various 3D applications such as cross-reality (XR) and realistic 3D displays. In some applications, e.g., for live streaming using a 3D point cloud, real-time point cloud denoising methods are required to enhance the visual quality. However, conventional high-precision denoising methods cannot be executed in real time for large-scale point clouds owing to the complexity of graph constructions with K nearest neighbors and noise level estimation. This paper proposes a fast graph-based denoising (FGBD) for a large-scale point cloud. First, high-speed graph construction is achieved by scanning a point cloud in various directions and searching adjacent neighborhoods on the scanning lines. Second, we propose a fast noise level estimation method using eigenvalues of the covariance matrix on a graph. Finally, we also propose a new low-cost filter selection method to enhance denoising accuracy to compensate for the degradation caused by the acceleration algorithms. In our experiments, we succeeded in reducing the processing time dramatically while maintaining accuracy relative to conventional denoising methods. Denoising was performed at 30fps, with frames containing approximately 1 million points.

This paper proposes a compression framework for adjacency matrices of weighted graphs based on graph filter banks. Adjacency matrices are widely used mathematical representations of graphs and are used in various applications in signal processing, machine learning, and data mining. In many problems of interest, these adjacency matrices can be large, so efficient compression methods are crucial. In this paper, we propose a lossy compression of weighted adjacency matrices, where the binary adjacency information is encoded losslessly (so the topological information of the graph is preserved) while the edge weights are compressed lossily. For the edge weight compression, the target graph is converted into a line graph, whose nodes correspond to the edges of the original graph, and where the original edge weights are regarded as a graph signal on the line graph. We then transform the edge weights on the line graph with a graph filter bank for sparse representation. Experiments on synthetic data validate the effectiveness of the proposed method by comparing it with existing lossy matrix compression methods.

Point clouds in 3D applications frequently experience quality degradation during processing, e.g., scanning and compression. Reliable point cloud quality assessment (PCQA) is important for developing compression algorithms with good bitrate-quality trade-offs and techniques for quality improvement (e.g., denoising). This paper introduces a full-reference (FR) PCQA method utilizing spectral graph wavelets (SGWs). First, we propose novel SGW-based PCQA metrics that compare SGW coefficients of coordinate and color signals between reference and distorted point clouds. Second, we achieve accurate PCQA by integrating several conventional FR metrics and our SGW-based metrics using support vector regression. To our knowledge, this is the first study to introduce SGWs for PCQA. Experimental results demonstrate the proposed PCQA metric is more accurately correlated with subjective quality scores compared to conventional PCQA metrics.

With the increasing number of images and videos consumed by computer vision algorithms, compression methods are evolving to consider both perceptual quality and performance in downstream tasks. Traditional codecs can tackle this problem by performing rate-distortion optimization (RDO) to minimize the distance at the output of a feature extractor. However, neural network non-linearities can make the rate-distortion landscape irregular, leading to reconstructions with poor visual quality even for high bit rates. Moreover, RDO decisions are made block-wise, while the feature extractor requires the whole image to exploit global information. In this paper, we address these limitations in three steps. First, we apply Taylor's expansion to the feature extractor, recasting the metric as an input-dependent squared error involving the Jacobian matrix of the neural network. Second, we make a localization assumption to compute the metric block-wise. Finally, we use randomized dimensionality reduction techniques to approximate the Jacobian. The resulting expression is monotonic with the rate and can be evaluated in the transform domain. Simulations with AVC show that our approach provides bit-rate savings while preserving accuracy in downstream tasks with less complexity than using the feature distance directly.

We present a novel method to correct flying pixels within data captured by Time-of-flight (ToF) sensors. Flying pixel (FP) artifacts occur when signals from foreground and background objects reach the same sensor pixel, leading to a confident yet incorrect depth estimation in space-floating between two objects. Commercial RGB-D cameras have a complementary setup consisting of ToF sensors to capture depth in addition to RGB cameras. We propose a novel method to correct FPs by leveraging the aligned RGB and depth image in such RGB-D cameras to estimate the true depth values of FPs. Our method defines a 3D neighborhood around each point, representing a “field of view” that mirrors the acquisition process of ToF cameras. We propose a two-step iterative correction algorithm in which the FPs are first identified. Then, we estimate the true depth value of FPs by solving a least-squares optimization problem. Experimental results show that our proposed algorithm estimates the depth value of FPs as accurately as other algorithms in the literature.

Current video coding standards, including H.264/AVC, HEVC, and VVC, employ discrete cosine transform (DCT), discrete sine transform (DST), and secondary Karhunen-Loéve transforms (KLTs) to decorrelate the intra-prediction residuals. However, the efficiency of these transforms in decorrelation can be limited when the signal has a non-smooth and non-periodic structure, such as those occurring in textures with intricate patterns. This paper introduces a novel adaptive separable path graph-based transform (GBT) that can provide better decorrelation than the DCT for intra-predicted texture data. The proposed GBT is learned in an online scenario with sequential$K$-means clustering, which groups similar blocks during encoding and decoding to adaptively learn the GBT for the current block from previously reconstructed areas with similar characteristics. A signaling overhead is added to the bitstream of each coding block to indicate the usage of the proposed graph-based transform. We assess the performance of this method combined with H.264/AVC intra-coding tools and demonstrate that it can significantly outperform H.264/AVC DCT for intra-predicted texture data.

In numerous graph signal processing applications, data is often missing for a variety of reasons, and predicting the missing data is essential. In this paper, we consider data on graphs modeled as bandlimited graph signals. Predicting or reconstructing the unknown signal values for such a model requires an estimate of the signal bandwidth. In this paper, we address the problem of estimating the reconstruction errors, minimizing which would thereby provide an estimate of the signal bandwidth. In doing so, we design a cross-validation approach needed for stable graph signal reconstruction and propose a method for estimating the reconstruction errors for different choices of signal bandwidth. Using this technique, we are able to estimate the reconstruction error on a variety of real-world graphs.

Point clouds are utilized in many 3-D applications such as cross-reality (XR) and realistic 3-D display. They consist of a set of points with 3-D coordinates and associated color signals. These color signals are often perturbed by noise induced by the measurement errors of scanning devices. In this paper, we propose a point cloud denoising method for color signals. Since many conventional methods for point cloud color denoising are based on a low-pass filter in the graph spectral domain, denoising accuracy is affected by the choice of graph. We propose a graph construction method using 3-D patch-based similarity, in which the similarity is calculated with small 3-D patches around the connected points. This is in contrast with conventional graph construction methods for denoising, which are based on point properties such as pairwise point distances and differences in color. Second, we propose a low-pass filtering method where the frequency response is chosen automatically depending on the estimated noise level. Our experimental results show that our proposed method, 3-D patch-based similarity (3DPBS), achieves the best denoising accuracy compared with graph-based state-of-the-art methods.

Point cloud applications suffer from geometric noise caused by measurement errors induced by the point cloud acquisition system. We propose a novel graph construction method, surface-consistent non-negative kernel regression (SC-NNK), that can achieve more accurate denoising of geometry information in combination with spectral graph wavelet transforms (SGWTs). Unlike conventional graph construction methods such as the K-nearest neighbor (KNN), which have been adopted in previous SGWT-based geometry denoising methods, SC-NNK graphs consider geometrical and frequency characteristics to remove redundant edge connections from a KNN graph. In addition, we propose a novel noise level estimation method that achieves improved accuracy by detecting flat surfaces in point clouds, resulting in better wavelet shrinkage thresholds for denoising. Our experimental results show that the proposed method outperforms recent deep-learning-based and graph-based state-of-the-art denoising methods.

User generated content (UGC) refers to videos that are uploaded by users and shared over the Internet. UGC may have low quality due to noise and previous compression. When re-encoding UGC for streaming or downloading, a traditional video coding pipeline will perform rate-distortion (RD) optimization to choose coding parameters. However, in the UGC video coding case, since the input is not pristine, quality “saturation” (or even degradation) can be observed, i.e., increased bitrate only leads to improved representation of coding artifacts and noise present in the UGC input. In this paper, we study the saturation problem in UGC compression, where the goal is to identify and avoid during encoding, the coding parameters and rates that lead to quality saturation. We proposed a geometric criterion for saturation detection that works with rate-distortion optimization, and only requires a few frames from the UGC video. In addition, we show how to combine the proposed saturation detection method with existing video coding systems that implement rate-distortion optimization for efficient compression of UGC videos.

Most codec designs rely on the mean squared error (MSE) as a fidelity metric in rate-distortion optimization, which allows to choose the optimal parameters in the transform domain but may fail to reflect perceptual quality. Alternative distortion metrics, such as the structural similarity index (SSIM), can be computed only pixel-wise, so they cannot be used directly for transform-domain bit allocation. Recently, the irregularity-aware graph Fourier transform (IAGFT) emerged as a means to include pixel-wise perceptual information in the transform design. This paper extends this idea by also learning a graph (and corresponding transform) for sets of blocks that share similar perceptual characteristics and are observed to differ statistically, leading to different learned graphs. We demonstrate the effectiveness of our method with both SSIM- and saliency-based criteria. We also propose a framework to derive separable transforms, including separable IAGFTs. An empirical evaluation based on the 5th CLIC dataset shows that our approach achieves improvements in terms of MS-SSIM with respect to existing methods.

When streaming 360° video, it is possible to reduce bandwidth by 5× with approaches that spatially segment video into tiles and only stream the user's viewport. Unfortunately, it is difficult to accurately predict a user's viewport even 2--3 seconds before playback. This results in rebuffering events owing to misprediction of a user's viewport or network bandwidth dips, which hurts interactive experience. However, avoiding rebuffering by naively skipping tiles that do not arrive by the playback deadline may lead to incomplete viewports and degraded experience.

Motivated by the success of fractional pixel motion in video coding, we explore the design of motion estimation with fractional-voxel resolution for compression of color attributes of dynamic 3D point clouds. Our proposed block-based fractional-voxel motion estimation scheme takes into account the fundamental differences between point clouds and videos, i.e., the irregularity of the distribution of voxels within a frame and across frames. We show that motion compensation can benefit from the higher resolution reference and more accurate displacements provided by fractional precision. Our proposed scheme significantly outperforms comparable methods that only use integer motion. The proposed scheme can be combined with and add sizeable gains to state-of-the-art systems that use transforms such as Region Adaptive Graph Fourier Transform and Region Adaptive Haar Transform.

Feature spaces in the deep layers of convolutional neural networks (CNNs) are often very high-dimensional and difficult to inter-pret. However, convolutional layers consist of multiple channels that are activated by different types of inputs, which suggests that more insights may be gained by studying the channels and how they relate to each other. In this paper, we first analyze theoretically channel-wise non-negative kernel (CW-NNK) regression graphs, which allow us to quantify the overlap between channels and, indirectly, the intrinsic dimension of the data representation manifold. We find that redundancy between channels is significant and varies with the layer depth and the level of regularization during training. Additionally, we observe that there is a correlation between channel overlap in the last convolutional layer and generalization performance. Our experimental results demonstrate that these techniques can lead to a better understanding of deep representations.

Spatio-temporal graph convolutional networks (STGCN) have become popular recently because they can handle structured data with dynamic temporal variations. However, the lack of interpretability limits the potential application of STGCNs. Gradient-based class activation maps (Grad-CAM) are a popular technique to interpret convolutional neural networks for grid structured data such as images. In this paper, we design an extension of Grad-CAMs for spatio temporal graph convolution (STG-Grad-CAM) to improve the interpretability of STGCNs. As a proof of concept we provide results for a skeleton-based activity recognition task. We show which body joints are responsible for a particular task and how their temporal dynamics contribute to the classification output. We present a brief study of the interpretability of a recognition task by changing the model depth and the training and testing protocol. To find the efficacy of STG-Grad-CAM, we compute faithfulness of STG-Grad-CAM to the model measured by the impact of occlusions to the graph nodes. For explainability of STGCN, we compute contrastivity of the model for different classes based on the outcome of STG-Grad-CAM. In the cross-person setting, we observe better contrastivity than the cross-view setting.

Active learning aims to reduce the cost of labeling through selective sampling. Despite reported empirical success over passive learning, many popular active learning heuristics such as uncertainty sampling still lack satisfying theoretical guarantees. Towards closing the gap between practical use and theoretical understanding in active learning, we propose to characterize the exact behavior of uncertainty sampling for high-dimensional Gaussian mixture data, in a modern regime of big data where the numbers of samples and features are commensurately large. Through a sharp characterization of the learning results, our analysis sheds light on the important question of when uncertainty sampling works better than passive learning. Our results show that the effectiveness of uncertainty sampling is not always ensured. In fact it depends crucially on the choice of i) an adequate initial classifier used to start the active sampling process and ii) a proper loss function that allows an adaptive treatment of samples queried at various steps.

We propose a novel graph-based denoising method to correct the quantization error (step noise) arising in the process of generating the visual hull, a commonly used technique to synthesize free-viewpoint video. To reduce this step noise effectively, we propose two new notions of consistency, pixel value consistency and normal vector consistency. The resulting denoising method involves a first step of graph construction using the proposed consistency metrics, followed by graph filtering of the 3D point cloud coordinates. Our experiments show that our approach provides visually and quantitatively better performance than state-of-the-art methods.

We introduce chroma subsampling for 3D point cloud attribute compression by proposing a novel technique to sample points irregularly placed in 3D space. While most current video compression standards use chroma subsampling, these chroma subsampling methods cannot be directly applied to 3D point clouds, given their irregularity and sparsity. In this work, we develop a framework to incorporate chroma subsampling into geometry-based point cloud encoders, such as region adaptive hierarchical transform (RAHT) and region adaptive graph Fourier transform (RAGFT). We propose different sampling patterns on a regular 3D grid to sample the points at different rates. We use a simple graph-based nearest neighbor interpolation technique to reconstruct the full resolution point cloud at the decoder end. Experimental results demonstrate that our proposed method provides significant coding gains with negligible impact on the reconstruction quality. For some sequences, we observe a bitrate reduction of 10-15% under the Bjontegaard metric. More generally, perceptual masking makes it possible to achieve larger bitrate reductions without visible changes in quality.

Many applications that use point clouds, such as 3D immersive telepresence, suffer from geometric quality degradation. This noise may be caused by measurement errors of the capturing device or by the point cloud estimation method. In this paper, we propose a novel graph-based point cloud denoising approach using the spectral graph wavelet transform (SGWT) and graph wavelet shrinkage. Unlike conventional SGWT-based denoising methods, the proposed wavelet shrinkage thresholds are determined based on the normal vector at each point and are thus based on the local geometric structure of the point cloud. This approach avoids excessive wavelet shrinkage, which can lead to the loss of complex geometric structure. Experimental results show that the proposed method achieves the best accuracy as compared with recent deep-learning-based and graph-based state-of-the-art denoising methods.

Transform coding to sparsify signal representations remains crucial in an image compression pipeline. While the Karhunen-Loève transform (KLT) computed from an empirical covariance matrix ${\mathbf{\bar C}}$ is theoretically optimal for a stationary process, in practice, collecting sufficient statistics from a non-stationary image to reliably estimate ${\mathbf{\bar C}}$ can be difficult. In this paper, to encode an intra-prediction residual block, we pursue a hybrid model-based / data-driven approach: the first K eigenvectors of a transform matrix are derived from a statistical model, e.g., the asymmetric discrete sine transform (ADST), for stability, while the remaining N −K are computed from ${\mathbf{\bar C}}$ for data adaptivity. The transform computation is posed as a graph learning problem, where we seek a graph Laplacian matrix minimizing a graphical lasso objective inside a convex cone sharing the first K eigenvectors in a Hilbert space of real symmetric matrices. We efficiently solve the problem via augmented Lagrangian relaxation and proximal gradient (PG). Using open-source WebP as a baseline image codec, experimental results show that our hybrid graph transform achieved better coding performance than discrete cosine transform (DCT), ADST and KLT, and better stability than KLT.

Intra prediction is an important technique to improve coding efficiency by exploiting the spatial redundancy present in typical video sequences. In video coding standards such as H.264/AVC, HEVC and VVC, directional predictors are utilized to generate prediction along a single direction within a block to be coded. However, these predictors fail to generate an accurate prediction when the block contains complex patterns such as periodic textures. In this paper, we propose a graph-based inpainting method that can handle both regular and near-regular textures. The proposed inpainting method utilizes a total variation model associated with the Laplacian matrix of a graph, whose edge weights are a function of pixel patch distance. We evaluate the performance of our proposed method as an additional prediction mode combined with the H.264/AVC coding standard. Experimental results show that the proposed method can significantly outperform H.264/AVC predictors in areas with high frequency periodic patterns.

Video shared over the internet is commonly referred to as user generated content (UGC). UGC video may have low quality due to various factors including previous compression. UGC video is uploaded by users, and then it is re-encoded to be made available at various levels of quality. In a traditional video coding pipeline the encoder parameters are optimized to minimize a rate-distortion criterion, but when the input signal has low quality, this results in sub-optimal coding parameters optimized to preserve undesirable artifacts. In this paper we formulate the UGC compression problem as that of compression of a noisy/corrupted source. The noisy source coding theorem reveals that an optimal UGC compression system is comprised of optimal denoising of the UGC signal, followed by compression of the denoised signal. Since optimal denoising is unattainable and users may be against modification of their content, we propose encoding the UGC signal, and using denoised references only to compute distortion, so the encoding process can be guided towards perceptually better solutions. We demonstrate the effectiveness of the proposed strategy for JPEG compression of UGC images and videos.

Technologies such as radiometry, radar or synthetic aperture radar have demonstrated the potential of remote sensing to observe the Earth's land surface and estimate variables that influence the climate system. Among the remote sensed variables, soil moisture has be-come increasingly important as the impacts of climate change on water resources continue to intensify. Soil moisture products, nor-mally retrieved from microwave remote sensing data, are typically not suitable for regional hydrological and agricultural applications such as irrigation management and flood predictions, due to their coarse spatial resolution. Providing accurate information on soil moisture at an appropriate temporal and spatial scale is challenging for traditional interpolation methods, due to the high variability of soil moisture. Aiming to provide fine resolution soil moisture es-timations, in this paper we evaluate the performance of our proposed graph-based downscaling method to obtain fine resolution soil moisture data$(9km)$from coarse satellite observations$(9km)$using very fine resolution evapotranspiration data$(30m)$. Our approach for-mulates the data interpolation problem as a signal reconstruction on a graph, where coarse soil moisture observations are signals at the nodes, while high resolution evapotranspiration data is used to compute the weights of the edges connecting the nodes.

In point cloud compression, exploiting temporal redundancy for inter predictive coding is challenging because of the irregular geometry. This paper proposes an efficient block-based inter-coding scheme for color attribute compression. The scheme includes integer-precision motion estimation and an adaptive graph based in-loop filtering scheme for improved attribute prediction. The proposed block-based motion estimation scheme consists of an initial motion search that exploits geometric and color attributes, followed by a motion refinement that only minimizes color prediction error. To further improve color prediction, we propose a vertex-domain low-pass graph filtering scheme that can adaptively remove noise from predictors computed from motion estimation with different accuracy. Our experiments demonstrate significant coding gain over state-of-the-art coding methods.

An unfocused plenoptic light field (LF) camera places an array of microlenses in front of an image sensor in order to separately capture different directional rays arriving at an image pixel. Using a conventional Bayer pattern, data captured at each pixel is a single color component (R, G or B). The sensed data then undergoes demosaicking (interpolation of RGB components per pixel) and conversion to an array of sub-aperture images (SAIs). In this paper, we propose a new LF image coding scheme based on graph lifting transform (GLT), where the acquired sensor data are coded in the original captured form without pre-processing. Specifically, we directly map raw sensed color data to the SAIs, resulting in sparsely distributed color pixels on 2D grids, and perform demosaicking at the receiver after decoding. To exploit spatial correlation among the sparse pixels, we propose a novel intra-prediction scheme, where the prediction kernel is determined according to the local gradient estimated from already coded neighboring pixel blocks. We then connect the pixels by forming a graph, modeling the prediction residuals statistically as a Gaussian Markov Random Field (GMRF). The optimal edge weights are computed via a graph learning method using a set of training SAIs. The residual data is encoded via low-complexity GLT. Experiments show that at high PSNRs-important for archiving and instant storage scenarios-our method outperformed significantly a conventional light field image coding scheme with demosaicking followed by High Efficiency Video Coding (HEVC).

Learning a suitable graph is an important precursor to many graph signal processing (GSP) pipelines, such as graph signal compression and denoising. Previous graph learning algorithms either i) make assumptions on graph connectivity (e.g., graph sparsity), or ii) make edge weight assumptions such as positive edges only. In this paper, given an empirical covariance matrix ${\mathbf{\bar C}}$ computed from data as input, we consider an eigen-structural assumption on the graph Laplacian matrix L: the first K eigenvectors of L are pre-selected, e.g., based on domain-specific criteria, and the remaining eigenvectors are then learned from data. One example use case is image coding, where the first eigenvector is pre-chosen to be constant, regardless of available observed data. We first prove that the subspace $\mathcal{H}_{\mathbf{u}}^ + $ of symmetric positive semi-definite (PSD) matrices with the first K eigenvectors being {uk} in a defined Hilbert space is a convex cone. We then construct an operator to project a given positive definite (PD) matrix L to $\mathcal{H}_{\mathbf{u}}^ + $, inspired by the Gram-Schmidt procedure. Finally, we design an efficient hybrid graphical lasso / projection algorithm to compute the most suitable graph Laplacian matrix ${{\mathbf{L}}^ * } \in \mathcal{H}_{\mathbf{u}}^ + $ given ${\mathbf{\bar C}}$. Experimental results show that given the first K eigenvectors as a prior, our algorithm outperforms competing graph learning schemes using a variety of graph comparison metrics.

Understanding complex hand actions, such as assembly tasks or kitchen activities, from hand skeleton data is an important yet challenging task. In this paper, we analyze hand skeleton-based complex activities by modeling dynamic hand skeletons through a spatiotemporal graph convolutional neural network (ST-GCN). This model jointly learns and extracts Spatio-temporal features for activity recognition. Our proposed technique, Symmetric Sub-graph spatio-temporal graph convolutional neural network (S2-ST-GCN), exploits the symmetric nature of hand graphs to decompose them into smaller sub-graphs, which allow us to build a separate temporal model for the relative motion of the fingers. This subgraph approach can be implemented efficiently by preprocessing input data using a Haar unit based orthogonal matrix. Then, in addition to spatial filters, separate temporal filters can be learned for each sub-graph. We evaluate the performance of the proposed method on the First-Person Hand Action dataset. While the proposed method shows comparable performance with the state of the art methods in train:test=1:1 setting, it achieves this with greater stability. Furthermore, we demonstrate significant performance improvement in comparison to state of the art methods in the cross-person setting, where the model did not come across a test subject's data while learning. S2-ST-GCN also shows superior performance than a finger-based decomposition of the hand graph where no preprocessing is applied.

This paper presents a graph learning framework to produce sparse and accurate graphs from network data. While our formulation is inspired by the graphical lasso, a key difference is the use of a nonconvex alternative of the ℓ1norm as well as a quadratic term to ensure overall convexity. Specifically, the weakly-convex minimax concave penalty (MCP) is used, which is given by subtracting the Huber function from the ℓ1norm, inducing a less-biased sparse solution than ℓ1. In our framework, the graph Laplacian is represented by a linear transform of the vector corresponding to its upper triangular part. Via a reformulation relying on the Moreau decomposition, the problem can be solved by the primal-dual splitting method. An admissible choice of parameters for provable convergence is presented. Numerical examples show that the proposed method significantly outperforms its ℓ1-based counterpart for sparse grid graphs.

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.

Biorthogonal graph wavelet filterbanks, also known as GraphBior, are one of the most popular graph transforms used in image compression, but up to now, they could be designed based on two known admissible fundamental matrices: i) the random walk Laplacian, which heavily penalizes low degree pixels, and ii) the normalized Laplacian, which lacks a zero-DC response. By exploiting a new extension of the admissibility condition in GraphBior we propose a new fundamental matrix with the goal of distributing the errors of GraphBior more uniformly across pixels with different node degrees. Furthermore the proposed matrix preserves high energy compaction linked to the zero-DC GraphBior variation.

Using hand skeleton data to understand complex hand actions, such as assembly tasks or kitchen activities, is an important yet challenging task. This paper introduces an unsupervised hand graph-based spatio-temporal feature extraction method. To evaluate the efficacy of the proposed representation, we consider action segmentation and recognition tasks. The segmentation problem involves an assembling task in an industrial setting, while the recognition problem deals with kitchen and office activities. For both tasks, we propose novel notions of stability, loss function stability (LFS) and estimation stability with cross-validation (ESCV), that are used to quantify the robustness of achieved solutions. Our proposed feature extraction leads to classification performance comparable to state of the art methods, while achieving significantly better accuracy and stability in a cross-person setting. The proposed method also outperforms the existing methods in the segmentation task in terms of accuracy and shows robustness to any change in the input hyper-parameters.

Traditional block-based transforms are based on applying a single transform to all blocks. As an alternative, better performance in image and video processing and representation can be achieved by choosing one among a discrete set of transforms for each block. As an example, our recently proposed set of multiple transforms called Symmetry-Based Graph Fourier Transforms (SBGFTs) have shown good performance in terms of energy compaction, improving HEVC intra coding performance when used to replace the Discrete Cosine Transform (DCT). This paper further explores the performance of the SBGFTs in a multiple transforms, non-linear approximation perspective, by comparing them with two alternative sets of orthogonal transforms, namely, the Karhunen-Loève Transform (KLT) and the Sparse Orthonormal Transform (SOT). Experimental results confirm that SBGFTs achieve superior representation ability in this context as well, suggesting that they could assume a central role in image compression.

We propose an intra frame predictive strategy for compression of 3D point cloud attributes. Our approach is integrated with the region adaptive graph Fourier transform (RAGFT), a multi-resolution transform formed by a composition of localized block transforms, which produces a set of low pass (approximation) and high pass (detail) coefficients at multiple resolutions. Since the transform operations are spatially localized, RAGFT coefficients at a given resolution may still be correlated. To exploit this phenomenon, we propose an intraprediction strategy, in which decoded approximation coefficients are used to predict uncoded detail coefficients. The prediction residuals are then quantized and entropy coded. For the 8i dataset, we obtain gains up to 0. 5db as compared to intra predicted point cloud compresion based on the region adaptive Haar transform (RAHT).

We present an efficient voxelization method to encode the geometry and attributes of 3D point clouds obtained from autonomous vehicles. Due to the circular scanning trajectory of sensors, the geometry of LiDAR point clouds is inherently different from that of point clouds captured from RGBD cameras. Our method exploits these specific properties to representing points in cylindrical coordinates instead of conventional Cartesian coordinates. We demonstrate that Region Adaptive Hierarchical Transform (RAHT) can be extended to this setting, leading to attribute encoding based on a volumetric partition in cylindrical coordinates. Experimental results show that our proposed voxelization outperforms conventional approaches based on Cartesian coordinates for this type of data. We observe a significant improvement in attribute coding performance with 5-10% reduction in bitrate and octree representation with 35-45% reduction in bits.

In this paper we study covariance estimation with missing data. We consider missing data mechanisms that can be independent of the data, or have a time varying dependency. Additionally, observed variables may have arbitrary (non uniform) and dependent observation probabilities. For each mechanism, we construct an unbiased estimator and obtain bounds for the expected value of their estimation error in operator norm. Our bounds are equivalent, up to constant and logarithmic factors, to state of the art bounds for complete and uniform missing observations. Furthermore, for the more general non uniform and dependent cases, the proposed bounds are new or improve upon previous results. Our error estimates depend on quantities we callscaled effective rank, which generalize the effective rank to account for missing observations. All the estimators studied in this work have the same asymptotic convergence rate (up to logarithmic factors).

Graph vertex sampling set selection aims at selecting a set of vertices of a graph such that the space of graph signals that can be reconstructed exactly from those samples alone is maximal. In this context, we propose to extend sampling set selection based on spectral proxies to arbitrary Hilbert spaces of graph signals. Enabling arbitrary inner product of graph signals allows then to better account for vertex importance on the graph for a sampling adapted to the application. We first state how the change of inner product impacts sampling set selection and reconstruction, and then apply it in the context of geometric graphs to highlight how choosing an alternative inner product matrix can help sampling set selection and reconstruction.

In most cases deep learning architectures are trained disregarding the amount of operations and energy consumption. However, some applications, like embedded systems, can be resource-constrained during inference. A popular approach to reduce the size of a deep learning architecture consists in distilling knowledge from a bigger network (teacher) to a smaller one (student). Directly training the student to mimic the teacher representation can be effective, but it requires that both share the same latent space dimensions. In this work, we focus instead on relative knowledge distillation (RKD), which considers the geometry of the respective latent spaces, allowing for dimension-agnostic transfer of knowledge. Specifically we introduce a graph-based RKD method, in which graphs are used to capture the geometry of latent spaces. Using classical computer vision benchmarks, we demonstrate the ability of the proposed method to efficiently distillate knowledge from the teacher to the student, leading to better accuracy for the same budget as compared to existing RKD alternatives.

Data driven graph constructions are often used in machine learning applications. However, learning an optimal graph from data is still a challenging task. K-nearest neighbor and -neighborhood methods are among the most common graph construction methods, due to their computational simplicity, but the choice of parameters such as K and associated with these methods is often ad hoc and lacks a clear interpretation. The main novelty of this paper is to formulate graph construction as the problem of finding a sparse signal approximation in kernel space, and identifying key similarities between methods in signal approximation and existing graph learning methods. We propose non-negative kernel regression (NNK), an improved approach for graph construction with interesting geometric and theoretical properties. We demonstrate experimentally the efficiency of NNK graphs, their robustness to choice of sparsity K and show that they can outperform state of the art graph methods in semi supervised learning tasks.

In image and video coding applications, distortion has been traditionally measured using mean square error (MSE), which suggests the use of orthogonal transforms, such as the discrete cosine transform (DCT). Perceptual metrics such as Structural Similarity (SSIM) are typically used after encoding, but not tied to the encoding process. In this paper, we consider an alternative framework where the goal is to optimize a weighted MSE metric, where different weights can be assigned to each pixel so as to reflect their relative importance in terms of perceptual image quality. For this purpose, we propose a novel transform coding scheme based on irregularity-aware graph Fourier transform (IAGFT), where the induced IAGFT is orthogonal, but the orthogonality is defined with respect to an inner product corresponding to the weighted MSE. We propose to use weights derived from local variances of the input image, such that the weighted MSE aligns with SSIM. In this way, the associated IAGFT can achieve a coding efficiency improvement in SSIM with respect to conventional transform coding based on DCT. Our experimental results show a compression gain in terms of multi-scale SSIM on test images.

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.

Graphs are useful to interpret widely used image processing methods, e.g., bilateral filtering, or to develop new ones, e.g., kernel based techniques. However, simple graph constructions are often used, where edge weight and connectivity depend on a few parameters. In particular, the sparsity of the graph is determined by the choice of a window size. As an alternative, we extend and adapt to images recently introduced non negative kernel regression (NNK) graph construction. In NNK graphs sparsity adapts to intrinsic data properties. Moreover, while previous work considered NNK graphs in generic settings, here we develop novel algorithms that take advantage of image properties, so that the NNK approach can scale to large images. Our experiments show that sparse NNK graphs achieve improved energy compaction and denoising performance when compared to using graphs directly derived from the bilateral filter.

With the advancement of reliable, fast, portable acquisition systems, human motion capture data is becoming widely used in many industrial, medical, and surveillance applications. These systems can track multiple people simultaneously, providing full-body skeletal keypoints as well as more detailed landmarks in face, hands and feet. This leads to a huge amount of skeleton data to be transmitted or stored. In this paper, we introduce Graph-based Skeleton Compression (GSC), an efficient graph-based method for nearly lossless compression. We use a separable spatio-temporal graph transform along with non-uniform quantization, coefficient scanning and entropy coding with run-length codes for nearly lossless compression. We evaluate the compression performance of the proposed method on the large NTU-RGB activity dataset. Our method outperforms a 1D discrete cosine transform method applied along temporal direction. In near-lossless mode our proposed compression does not affect action recognition performance.

While deep learning is a powerful tool for many applications, there has been only limited research about selection of data for training, i.e., instance selection, which enhances deep learning scalability by saving computational resources. This can be attributed in part to the difficulty of interpreting deep learning models. While some graph-based methods have been proposed to improve performance and interpret behavior of deep learning, the instance selection problem has not been addressed from a graph perspective. In this paper, we analyze the behavior of deep learning outputs by using the K-nearest neighbor (KNN) graph construction. We observe that when a directed KNN graph is constructed, instead of the more conventional undirected KNN, a large number of instances become isolated nodes, i.e., they do not belong to the directed neighborhoods of any other nodes. Based on this, we propose two new instance selection methods, that both lead to fewer isolated nodes, by either directly eliminating them (minimization approach) or by connecting them more strongly to other points (maximization). Our experiments show that our proposed maximization method leads to better performance than random selection and recent methods for instance selection.

In many state-of-the-art compression systems, signal transformation is an integral part of the encoding and decoding process, where transforms provide compact representations for the signals of interest. This paper introduces a class of transforms called graph-based transforms (GBTs) for video compression, and proposes two different techniques to design GBTs. In the first technique, we formulate an optimization problem to learn graphs from data and provide solutions for optimal separable and nonseparable GBT designs, called GL-GBTs. The optimality of the proposed GL-GBTs is also theoretically analyzed based on Gaussian-Markov random field (GMRF) models for intra and inter predicted block signals. The second technique develops edge-adaptive GBTs (EA-GBTs) in order to flexibly adapt transforms to block signals with image edges (discontinuities). The advantages of EA-GBTs are both theoretically and empirically demonstrated. Our experimental results show that the proposed transforms can significantly outperform the traditional Karhunen-Loeve transform (KLT).

Analysis of hand skeleton data can be used to understand patterns in manipulation and assembly tasks. This paper introduces a graph-based representation of hand skeleton data and proposes a method to perform unsupervised temporal segmentation of a sequence of sub-tasks in order to evaluate the efficiency of an assembly task. We explore the properties of different choices of hand graphs and their spectral decomposition. A comparative performance of these graphs is presented in the context of complex activity segmentation. We show that the spectral graph features extracted from 2D hand motion data outperform the direct use of motion vectors as features. We also make the collected hand position data available to the research community to facilitate further development in this direction.

This paper proposes a coded distributed graph processing framework to alleviate the communication bottleneck in large-scale distributed graph processing. In particular, we propose a topology-aware coded computing (TACC) algorithm that has two salient features. First, we propose a topology-aware graph allocation strategy. Second, we propose a coded aggregation scheme that combines the intermediate computations for graph processes while constructing coded messages. The proposed setup builds on a trade-off between computation and communication, in that increasing the computation load at the distributed parties can in turn reduce the communication load. We demonstrate the effectiveness of the TACC algorithm by comparing the communication load with existing setups on a Google web graph for PageRank computations. In particular, we show that the proposed coding strategy can lead up to 82% improvement in reducing the communication load when compared to the state-of-the-art.

This paper considers the graph signal sampling problem when some of the selected samples are lost or unavailable due to sensor failures or adversarial erasures. We formulate a robust graph signal sampling problem where only a subset of selected samples are received, and the goal is to maximize the worst-case performance. We propose a novel greedy robust sample selection algorithm and study its performance guarantees. Our numerical results demonstrate the performance improvement of the proposed algorithm over the existing schemes.

Lapped transforms are transform coding tools with basis functions that overlap across blocks in order to reduce blocking artifacts. In this work, we take the uniform line graph model interpretation of the discrete cosine transform (DCT) and extend it to lapped transforms. We first extend the conditions of perfect reconstruction and orthogonality to lapped transforms on graphs, where different transforms are allowed for different blocks. Then, with the focus on line graphs, we design a lapped graph Fourier transform (LGFT) that has these properties, with significantly reduced blocking artifact. Experimental results show that the proposed LGFT can achieve improved transform coding gain as compared to other existing transforms.

We propose a method for graph learning from spatiotemporal measurements. We aim at inferring time-varying graphs under the assumption that changes in graph topology and weights are sparse in time. The problem is formulated as a convex optimization problem to impose a constraint on the temporal relation of the time-varying graph. Experimental results with synthetic data show the effectiveness of our proposed method.

The Discrete Cosine Transform (DCT) is widely deployed by modern image and video coding standards such as JPEG and H.26x. In most cases, the DCT is applied in a separable manner to rows and columns, which limits its ability to represent signals with diagonal orientation. As an alternative, non-separable transforms can represent signals with different orientations, but are significantly more computationally complex. To address this problem, in this paper we propose a set of non-separable Symmetry-Based Graph Fourier Transforms (SBGFTs), whose symmetric structures lead to a faster implementation. We study a practical image coding scenario that exploits the proposed SBGFTs, where for each intra predicted image residual block the optimal graph is chosen by solving a graph-based Rate-Distortion (R-D) problem. Experimental results indicate a coding efficiency higher than JPEG and JPEG2000.

In this paper we study the problem of inexact weighted graph matching, where the goal is to find the correspondence between the vertices of two similar graphs. We propose a novel multi-resolution approach that improves the performance of single resolution graph matching which can be jointly combined with state-of-the art graph matching algorithms. Spectral graph matching determines the best correspondence between the graphs at each resolution by identifying vertex permutations that minimize the distance between the spectrum of the two graphs. To obtain graphs at lower resolutions, we propose a graph downsampling method that aims at selecting nodes in each graph so as to guarantee that matching at the lower resolutions will be possible. A key contribution of our work is to estimate the reliability of matching at each resolution and then use this information to obtain a weighted matching reliability across all resolutions. A comparison with other spectral graph matching algorithms demonstrates the benefits of the proposed approach.

Understanding human activity based on sensor information is required in many applications and has been an active research area. With the advancement of depth sensors and tracking algorithms, systems for human motion activity analysis can be built by combining off-the-shelf motion tracking systems with application-dependent learning tools to extract higher semantic level information. Many of these motion tracking systems provide raw motion data registered to the skeletal joints in the human body. In this paper, we propose novel representations for human motion data using the skeleton-based graph structure along with techniques in graph signal processing. Methods for graph construction and their corresponding basis functions are discussed. The proposed representations can achieve comparable classification performance in action recognition tasks while additionally being more robust to noise and missing data.

We study the problem of sampling signals on a graph and allocating rate to each vertex in the sampling set, in a scenario where information sampled at each of the graph nodes needs to be compressed for transmission. We formulate this problem as a constrained quadratic programming optimization and obtain analytic results stating that the reconstruction error due to quantization should be equally distributed over the nodes involved. Our solution can also be used to remove samples from an already selected sampling set with low additional complexity. We demonstrate through experiments that the optimal solution yields improved performance on various graphs.

Two channel critically sampled filter banks for signal over graph domains were first proposed for undirected bipartite graphs by Narang and Ortega. Extension to the M-channel critically sampled case for balanced M-block cyclic graphs was then proposed by Teke and Vaidynathan but the filter bank does not achieve strict perfect reconstruction (PR), only generalized PR. In this letter, we consider the more general case of filter banks on unbalanced M-block cyclic graphs where strict PR is achieved. A polyphase analysis to derive the implementation structures in the downsampled domain is presented here. The relevant system/filter matrices have interesting cyclic properties and projection operators are needed to map signals between subgraphs.

Graph-based methods have been quite successful in solving unsupervised and semi-supervised learning problems, as they provide a means to capture the underlying geometry of the dataset. It is often desirable for the constructed graph to satisfy two properties: first, data points that are similar in the feature space should be strongly connected on the graph, and second, the class label information should vary smoothly with respect to the graph, where smoothness is measured using the spectral properties of the graph Laplacian matrix. Recent works have justified some of these smoothness conditions by showing that they are strongly linked to the semi-supervised smoothness assumption and its variants. In this work, we reinforce this connection by viewing the problem from a graph sampling theoretic perspective, where class indicator functions are treated as bandlimited graph signals (in the eigenvector basis of the graph Laplacian) and label prediction as a bandlimited reconstruction problem. Our approach involves analyzing the bandwidth of class indicator signals generated from statistical data models with separable and nonseparable classes. These models are quite general and mimic the nature of most real-world datasets. Our results show that in the asymptotic limit, the bandwidth of any class indicator is also closely related to the geometry of the dataset. This allows one to theoretically justify the assumption of bandlimitedness of class indicator signals, thereby providing a sampling theoretic interpretation of graph-based semi-supervised classification.

A common smoothness model used in graph based regularization approaches is to require the energy of signals to be small with respect to the graph Laplacian of the graph. In this paper, we suggest an alternative approach which can effectively incorporate the high frequency information of the graph for unsupervised piece-wise smooth manifold denoising using Spectral Graph Wavelets. Our approach is based on a novel technique to remove noise from SGW coefficients estimated from a local tangent space based graph, which allows us to effectively regularize manifolds with singularities, such as for example intersecting manifolds. Experimental results on synthetic and real datasets in computer vision applications show that our proposed approach outperforms the state of the art, and is an effective tool to remove noise from manifolds with complex structures without over-smoothing at discontinuities.

We consider the problem of sampling signals defined on the nodes of a graph. This problem arises in many contexts where the data is not structured and needs to be reconstructed from a few samples. While other graph signal sampling techniques have been recently developed in the literature, these are based on graph spectral concepts. In contrast, here we develop a method that incorporates distances between graph vertices, and thus can provide additional insights about desirable properties of sampling sets relative to state-of-the-art techniques. We compare the accuracy of our method with two other fast methods in the literature and show that it achieves similar performance.

The first step in solving a classification problem is to collect and label a sufficient amount of training data. Given the time and cost associated to data labeling, crowdsourcing systems (e.g., Amazon Mechanical Turk) are often used. However, one of the key disadvantages of crowdsourcing systems is the presence of spammers or workers who are not as skilled or careful, thus leading to many false labels being assigned. This paper addresses this problem by proposing a novel algorithm based on graph signal sampling theory, which optimally assigns data to different workers for labeling by taking into account the expected quality of labeling provided by each worker. Our simulation of the labeling process using these schemes shows that the classification error can be reduced significantly with respect to a random assignment of workers.

We study covariance matrix estimation for the case of partially observed random vectors, where different samples contain different subsets of vector coordinates. Each observation is the product of the variable of interest with a 0 - 1 Bernoulli random variable. We analyze an unbiased covariance estimator under this model, and derive an error bound that reveals relations between the sub-sampling probabilities and the entries of the covariance matrix. We apply our analysis in an active learning framework, where the expected number of observed variables is small compared to the dimension of the vector of interest, and propose a design of optimal sub-sampling probabilities and an active covariance matrix estimation algorithm.

This paper presents a framework for perfect reconstruction two-channel critically-sampled graph filter banks with spectral domain sampling. Graph signals have a unique characteristic: sampling in the vertex and graph spectral domains are generally different, in contrast to classical signal processing. Conventional graph filter banks are designed using vertex domain sampling, whereas the proposed approach utilizes a novel spectral domain sampling. Our proposed technique leads to perfect reconstruction transforms for any type of undirected graphs and can be applied both to combinatorial and symmetric normalized graph Laplacians. Some filter bank designs and an experiment on nonlinear approximation are shown to validate their effectiveness.

It is well-known that the application of the Discrete Cosine Transform (DCT) in transform coding schemes is justified by the fact that it belongs to a family of transforms asymptotically equivalent to the Karhunen-Loeve Transform (KLT) of a first order Markov process. However, when the pixel-to-pixel correlation is low the DCT does not provide a compression performance comparable with the KLT. In this paper, we propose a set of symmetry-based Graph Fourier Transforms (GFT) whose associated graphs present a totally or partially symmetric grid. We show that this family of transforms well represents both natural images and residual signals outperforming the DCT in terms of energy compaction. We also investigate how to reduce the cardinality of the set of transforms through an analysis that studies the relation between efficient symmetry-based GFTs and the directional modes used in H.265 standard. Experimental results indicate that coding efficiency is high.

Rate-distortion (RD) optimization is an important tool in many video compression standards and can be used for transform selection. However, this is typically very computationally demanding because a full RD search involves the computation of transform co-efficients for each candidate transform. In this paper, we propose an approach that uses sparse Laplacian operators to estimate the RD cost by computing a weighted squared sum of transform coefficients, without having to compute the actual transform coefficients. We demonstrate experimentally how our method can be applied for transform selection. Implemented in the AV1 encoder, our approach yields a significant speed-up in encoding time with a small increase in bitrate.

Graph-theoretical methods are being increasingly used in areas of interest within the IEEE and beyond. Graphs are mathematical abstractions that can be used to represent networks of various types: physical (e.g., the internet or electrical networks), biological (e.g., brain networks), or social (e.g., online social networks). Furthermore, graphs can provide tools for flexible representation of data sets in which data points have irregular positions with respect to each other. Common examples of this include data sets acquired by a sensor network, where uniform sensor placement may not be possible, or machine learning data sets, where training samples are not uniformly distributed in feature space. In some instances, a graph representation arises as a natural way to describe the problem, while in other areas, e.g., image processing, they are being used to develop powerful, content-dependent alternatives to conventional processing tools.

Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas in GSP and their connection to conventional digital signal processing, along with a brief historical perspective to highlight how concepts recently developed in GSP build on top of prior research in other areas. We then summarize recent advances in developing basic GSP tools, including methods for sampling, filtering, or graph learning. Next, we review progress in several application areas using GSP, including processing and analysis of sensor network data, biological data, and applications to image processing and machine learning.

In this paper, we describe and optimize a general scheme based on lifting transforms on graphs for video coding. A graph is constructed to represent the video signal. Each pixel becomes a node in the graph and links between nodes represent similarity between them. Therefore, spatial neighbors and temporal motion-related pixels can be linked, while nonsimilar pixels (e.g., pixels across an edge) may not be. Then, a lifting-based transform, in which filtering operations are performed using linked nodes, is applied to this graph, leading to a 3D (spatio-temporal) directional transform, which can be viewed as an extension of wavelet transforms for video. The design of the proposed scheme requires four main steps: 1) graph construction; 2) graph splitting; 3) filter design; and 4) extension of the transform to different levels of decomposition. We focus on the optimization of these steps in order to obtain an effective transform for video coding. Furthermore, based on this scheme, we propose a coefficient reordering method and an entropy coder leading to a complete video encoder that achieves better coding performance than a motion-compensated temporal filtering wavelet-based encoder, and a simple encoder derived from H.264/AVC that makes use of similar tools as our proposed encoder (reference software JM15.1 configured to use one reference frame, no subpixel motion estimation, and 16 × 16 inter and 4 × 4 intra modes).

Current formulations of critically-sampled graph wavelet filterbanks work only for bipartite graphs where downsampling signals on either partition leads to a spectrum folding phenomenon. The lack of such a natural downsampling scheme for arbitrary graphs poses difficulties in designing filterbanks. In this paper, we propose a critical sampling scheme on an arbitrary graph that chooses a sampling set for each channel, given a set of analysis/synthesis filters, by seeking to minimize a bound on the overall reconstruction error associated with the filterbank. Our algorithm is efficient since it requires a few simple graph filtering operations in each iteration. Our initial experiments show that its output is consistent with the sampling scheme for bipartite graphs and results in superior performance over other methods.

The bilateral filter (BF) is a prominent tool for adaptive, structure-preserving image filtering. It can be interpreted as a graph-based filter, where the nodes of the graph correspond to image pixels and link weights correspond to filter coefficients. Graphs associated to BFs of typical sizes used in practice are very dense. In this paper, we propose an efficient method for constructing a sparse graph for adaptive filtering of an image. The Laplacian matrix of the proposed sparse graph approximates the inverse of a dense BF kernel matrix. This is analogous to the idea of finding a sparse inverse covariance of a Gaussian Markov random field (GMRF) with a dense covariance matrix. The eigenvectors of the proposed graph Laplacian are approximately equal to the eigenvectors of the BF graph and allow for low frequency representation of the image similar to the BF eigenvectors. Filters in the form of polynomials of this sparse Laplacian offer a more flexible and less computationally complex alternative to a dense BF, with similar performance.

In this paper, we extend the recent definition of graph stationarity into a definition of local stationarity. Doing so, we present a metric to assess local stationarity using projections on localized atoms on the graph. Energy of these projections defines the local power spectrum of the signal. We use this local power spectrum to characterize local stationarity and identify sources of non-stationarity through differences of local power spectrum. Finally, we take advantage of the knowledge of the spectrum of the atoms to give a new power spectrum estimator.

The GraSP toolbox aims at processing and visualizing graphs and graphs signal with ease. In the demo, we show those capabilities using several examples from the literature and from our own experiments.

Learning graph topology from data is challenging. Previous work leads to learning graphs on which the graph signals used for training are smooth. In this paper, we propose an optimization framework for learning multiple graphs, each associated to a class of signals, such that representation of signals within a class and discrimination of signals in different classes are both taken into consideration. A Fisher-LDA-like term is included in the optimization objective function in addition to the conventional Gaussian ML objective. A block coordinate descent algorithm is then developed to estimate optimal graphs for different categories of signals, which are then used to efficiently classify the different signals. Experiments on synthetic data demonstrate that our proposed method can achieve better discrimination between the learned graphs, leading to improvements in subsequent classification tasks.

When a line graph is symmetric, the associated graph Fourier transform has a fast implementation. In this paper, we extend this idea to the 2D non-separable case, where the graph of interest is a square-shaped grid. We investigate a number of symmetry types for 2D grids. Then, for each type of symmetry we derive a block-diagonalization form of the graph Laplacian matrix, based on which fast implementations with reduced number of multiplications can be obtained. We show that for moderate block sizes, certain types of grid symmetry enable us to design non-separable block transforms that have computational complexities comparable to those of separable ones.

This paper addresses the problem of finding optimal sensor placement, i.e., determining F sensor positions from N possible locations. We propose a sensor selection method based on the localization operator of graph signal processing. This method can select sensors while considering the localizations both in graph vertex domain and graph spectral domain and is fast, since eigendecomposition of graph Laplacian matrix is not required. We also propose an interpretation of the conventional node selection based on graph sampling theory by using the graph localization operators. Experiments on selected sensor location, execution time and prediction error comparisons are conducted to show the effectiveness of our approach.

A plenoptic light field (LF) camera places an array of microlenses in front of an image sensor, in order to separately capture different directional rays arriving at an image pixel. Using a Bayer pattern, data captured at each pixel is a single color component (R, G or B). The sensed data then undergoes demosaicking (interpolation of RGB components per pixel) and conversion to a series of subaperture images. In this paper, we propose a novel LF image coding scheme based on graph lifting transform, where the acquired sensor data are coded in their original form without pre-processing. Specifically, demosaicking is not performed, and instead we first map raw sensed color data directly to subaperture image 2D grids, then encode the color pixels, which are sparse in spatial distribution, via a graph lifting transform. Our method avoids redundancies stemming from demosaicking, and operates in the original RGB domain without color conversion and sub-sampling. The graph lifting transform efficiently encodes irregularly spaced pixels in each subaperture image, resulting in compact representations. Experiments show that at high PSNRs - important for archiving and instant storage scenarios - our method outperforms demosaicking followed by intra-only High Efficiency Video Coding (HEVC) significantly.

In this paper, we propose an efficient graph learning approach for fast graph Fourier transform. We consider a maximum likelihood problem with additional constraints based on a matrix factorization of the graph Laplacian matrix, such that its eigenmatrix is a product of a block diagonal matrix and a butterfly-like matrix. We show that a special case of this problem reduces to a learning problem with constraints enforcing certain graph symmetries. Then, we provide an efficient approximation approach for the general problem without enforcing any symmetry constraint. We use this approach to design a fast nonseparable transform for intra predictive residual blocks in video compression. The resulting transform achieves a better rate-distortion performance than the 2D DCT and the hybrid DCT/ADST transform.

Orthogonal transforms are one of the most important components of a video encoder system. They are applied to residual block images obtained as the difference between a target and its prediction. In this paper we propose a framework to design separable transforms from prediction residual statistics. We model the data as a 2D Gaussian Markov random field and approximate its inverse covariance by a matrix with a separable structure, thus explicitly constructing a separable orthonormal matrix that approximates the KLT. Our designed transforms can adapt to prediction residual statistics, have low complexity (compared to non separable transforms), require selecting few parameters and outperform hybrid DCT/ADST separable transform for intra coding of AV1 residuals.

Hyperspectral imaging captures the spectral responses of different wavelengths per pixel for an entire image. Because the number of spectral bands is large, efficient compression of hyperspectral images is important. Leveraging on recent advances in graph signal processing (GSP), in this paper we propose to encode a hyperspectral image in groups of ω spectral bands using graph wavelets, exploiting correlations along both the spatial and the spectral dimensions. Specifically, along the spatial dimension, we estimate the inter-pixel correlations for all adjacent pixel pairs from the last image in the previous coded band group. Along the spectral dimension, we first divide an image into different spatial regions with similar spectral responses, and encode the spectral signature (correlations along the spectrum) for each region as side information (SI). The spatial / spectral correlations are used to compute edge weights to construct a graph for signal-adaptive graph wavelet based compression. Experimental results suggest that our proposal can outperform existing schemes noticeably at comparable complexity.

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.

In this paper, we propose a graph-based lifting transform for intra-predicted video sequences. The transform can approximate the performance of a Graph Fourier Transform (GFT) for a given graph, but does not require computing eigenvectors. A predict-update bipartition is designed based on a Gaussian Markov Random Field (GMRF) model with the goal to minimize the energy in the prediction set. Additionally, a novel re-connection method is applied for multi-level graphs, leading to significant gain for the proposed bipartition method and for the conventional MaxCut based bipartition. Experiments on intra-predicted video sequences show that the proposed method, even considering the extra overhead for edge information, outperforms the Discrete Cosine Transform (DCT) and approximates the performance of the higher complexity GFT.

We propose a new framework for manifold denoising using the Spectral Graph Wavelet transform, which enables non-iterative denoising directly in the graph frequency domain, an approach inspired by conventional wavelet-based signal denoising methods. We theoretically justify our approach, based on the fact that for smooth manifolds the coordinate information tends to create energy in the low spectral graph wavelet coefficients, while the noise affects all frequency bands in a similar way. Experimental results show that our suggested manifold frequency denoising (MFD) approach significantly outperforms the state of the art manifold denosing methods, and is robust to a wide range of parameter selections, e.g., the choice of k nearest neighbor connectivity of the graph.

This paper introduces a novel framework for combining multiple weighted graphs into a single optimized weighted graph. In our framework, we first develop a statistical formulation for the graph combining problem with a maximum likelihood criterion, and derive its optimality conditions. We then use these conditions to formulate the deterministic graph combining problem and propose a solution. Our experimental results show that the proposed solution provides better modeling compared to the commonly used averaging method. The introduced framework has various applications in signal processing and machine learning.

This paper studies graph-based active learning, where the goal is to reconstruct a binary signal defined on the nodes of a weighted graph, by sampling it on a small subset of the nodes. A new sampling algorithm is proposed, which sequentially selects the graph nodes to be sampled, based on an aggressive search for the boundary of the signal over the graph. The algorithm generalizes a recent method for sampling nodes in unweighted graphs. The generalization improves the sampling performance using the information gained from the available graph weights. An analysis of the number of samples required by the proposed algorithm is provided, and the gain over the unweighted method is further demonstrated in simulations. Additionally, the proposed method is compared with an alternative state-of-the-art method, which is based on the graph's spectral properties. It is shown that the proposed method significantly outperforms the spectral sampling method, if the signal needs to be predicted with high accuracy. On the other hand, if a higher level of inaccuracy is tolerable, then the spectral method outperforms the proposed aggressive search method. Consequently, we propose a hybrid method, which is shown to combine the advantages of both approaches.

Moving object segmentation in video has uses in many applications and is a particularly challenging task when the video is acquired by a moving camera. Typical approaches that rely on principal component analysis (PCA) tend to extract scattered sparse components of the moving objects and generally fail in extracting dense object segmentations. In this paper, a novel label propagation framework based on motion vanishing point (MVP) analysis is proposed to address the challenges. A weighted graph is constructed with image pixels as nodes and the MVP-guided approach is used to define the graph weights. Label propagation is then performed by incorporating the graph Laplacian. In addition, a PCA result is used to initialize the foreground/background labels. Experiments on the Hopkins data set of outdoor sequences captured by a hand-held moving camera demonstrate that the proposed label propagation method outperforms state-of-the-art PCA and spectral clustering methods for a dense segmentation task. Moreover, the framework is capable of correcting mislabeled foreground pixels and thus does not require accurate initial label assignment.

Graph signal processing models high dimensional data as functions on the vertices of a graph. This theory is constructed upon the interpretation of the eigenvectors of the Laplacian matrix as the Fourier transform for graph signals. We formulate the graph learning problem as a precision matrix estimation with generalized Laplacian constraints, and we propose a new optimization algorithm. Our formulation takes a covariance matrix as input and at each iteration updates one row/column of the precision matrix by solving a non-negative quadratic program. Experiments using synthetic data with generalized Laplacian precision matrix show that our method detects the nonzero entries and it estimates its values more precisely than the graphical Lasso. For texture images we obtain graphs whose edges follow the orientation. We show our graphs are more sparse than the ones obtained using other graph learning methods.

We consider the problem of selecting optimal sensor placements. The proposed approach is based on the sampling theorem of graph signals. We choose sensors that maximize the graph cut-off frequency, i.e., the most informative sensors for predicting the values on unselected sensors. We study the existing methods in the context of graph signal processing and clarify the relationship between these methods and the proposed approach. The effectiveness of our approach is verified through numerical experiments, showing advantages in prediction error and execution time.

The ever increasing quantity of user generated photos, nearly all compressed using JPEG, has created a growing storage burden on photo storage and sharing services. This creates the need for compression techniques that take JPEG compressed images as inputs. In this paper we propose two novel very low complexity codecs, ROMP and L-ROMP to recompress JPEG photos, achieving increased coding efficiency by making use of very large entropy coding tables. ROMP is a lossless JPEG recompression codec that achieves 15% average gains over JPEG, while L-ROMP is a lossy codec that can achieve 29% average compression gains over JPEG, by applying coefficient thresholding based on a perceptual criterion to a JPEG image before using the entropy coding of ROMP.

The observation of frequency folding in graph spectrum during down-sampling for signals on bipartite graphs-analogous to the same phenomenon in Fourier domain for regularly sampled signals-has led to the development of critically sampled wavelet filterbanks such as GraphBior. However, typical graph-signals live on general graphs that are not necessarily bipartite. To decompose a non-bipartite graph into a series of bipartite subgraphs so that two-channel filterbanks can be applied iteratively, we propose a new algorithm based on two criteria easily computed in the vertex domain aiming at compact signal representation in the wavelet domain. Given that filterbanks have minimal frequency discrimination at 1, the first criterion aims to minimize the multiplicity of mid graph frequency 1. The second criterion aims to preserve the edge structure of the original graph, which may reflect correlations among signal samples, so that a signal projected on approximated bipartite subgraphs can nonetheless be well represented using low frequency components. Experimental results show that our proposed bipartite subgraph decomposition outperforms competing proposals in terms of energy compaction.

In this paper, we propose a new edge model for edge adaptive graph-based transforms (EA-GBTs) in video compression. In particular, we consider step and ramp edge models to design graphs used for defining transforms, and compare their performance on coding intra and inter predicted residual blocks. In order to reduce the signaling overhead of block-adaptive coding, a new edge coding method is introduced for the ramp model. Our experimental results show that the proposed methods outperform classical DCT-based encoding and that ramp edge models provide better performance than step edge models for intra predicted residuals.

This paper introduces a novel class of transforms, called graph-based separable transforms (GBSTs), based on two line graphs with optimized weights. For the optimal GBST construction, we formulate a graph learning problem to design two separate line graphs using row-wise and column-wise residual block statistics, respectively. We also analyze the optimality of resulting separable transforms for both intra and inter predicted residual block models. Moreover, we show that separable DCT and ADST (DST-7) are special cases of the GBSTs. Our experimental results demonstrate that the proposed optimized transforms outperform 2-D DCT/ADST and separable KLT.

Segmentation of moving objects in a scene is difficult for non-stationary cameras, and especially challenging in the presence of fast and unstable egomotion, e.g., as encountered with car-mounted cameras or wearable devices. Based on an analysis of motion vanishing points of the scene and estimated depth, a geometric model that relates extracted 2D motion to a 3D motion field relative to the camera is derived. Observing that the 3D motion field is piece-wise smooth, a constrained optimization problem that considers group sparsity is formulated to recover the 3D motion field from the 2D motion. The recovered 3D motion field is then clustered to provide the segmentation of moving objects. Experiments are performed using the KITTI Vision Benchmark Suite and demonstrate that the proposed framework provides a dense segmentation of moving objects that is robust to the challenging conditions inherent with car driving sequences.

A light field (LF) is a 2D array of closely spaced viewpoint images of a static 3D scene. In an interactive LF streaming (ILFS) scenario, a user successively requests desired neighboring viewpoints for observation, and in response the server must transmit pre-encoded data for correct decoding of the requested viewpoint images. Designing frame structures for ILFS is challenging, since at encoding time it is not known what navigation path a user will take, making differential coding very difficult to employ. In this paper, leveraging on a recent work on the merge operator - a new distributed source coding technique that efficiently merges differences among a set of side information (SI) frames into an identical reconstruction - we design redundant frame structures that facilitate ILFS, trading off expected transmission cost with total storage size. Specifically, we first propose a new view interaction model that captures view navigation tendencies of typical users. Assuming a flexible one-frame buffer at the decoder, we then derive a set of recursive equations that compute the expected transmission cost for a navigation lifetime of T views, given the proposed interaction model and a pre-encoded frame structure. Finally, we propose an algorithm that greedily builds a redundant frame structure, minimizing a weighted sum of expected transmission cost and total storage size. Experimental results show that our proposed algorithm generates frame structures with better transmission / storage tradeoffs than competing schemes.

The stochastic block model (SBM) is an important generative model for random graphs in network science and machine learning, useful for benchmarking community detection (or clustering) algorithms. The symmetric SBM generates a graph with 2n nodes which cluster into two equally sized communities. Nodes connect with probability p within a community and q across different communities. We consider the case of p = a ln(n)/n and q = b ln(n)/n. In this case, it was recently shown that recovering the community membership (or label) of every node with high probability (w.h.p.) using only the graph is possible if and only if the Chernoff-Hellinger (CH) divergence D(a; b) = (√a - √a)2≥ 1. In this work, we study if, and by how much, community detection below the clustering threshold (i.e. D(a; b)1-D(a;b). The validity of our results is demonstrated through numerical experiments.

In this paper, we study graph-based transforms for inter predictive video coding. We are motivated by the fact that symmetries in the transform basis are very beneficial for computational efficiency. Based on this, we describe the relationship between bisymmetric matrices and the butterfly structure in fast transform algorithms. We introduce a new class of transforms called Symmetric Line Graph Transforms (SLGTs), of which the discrete cosine transform (DCT) is one particular case. As is well known in the case of the DCT, the bisymmetry property allows us to reduce the number of multiplications by half. We show that, beyond the DCT, useful SLGTs can be defined that have efficient implementation. We propose a specific SLGT that is shown to outperform the DCT for classes of inter residual blocks. While the proposed SLGT approaches the performance of a Karhunen Loeve Transform (KLT) at certain distortion levels, it has lower computation cost.

The ability to efficiently switch from one pre-encoded video stream to another (e.g., for bitrate adaptation or view switching) is important for many interactive streaming applications. Recently, stream-switching mechanisms based on distributed source coding (DSC) have been proposed. In order to reduce the overall transmission rate, these approaches provide a merge mechanism, where information is sent to the decoder, such that the exact same frame can be reconstructed given that any one of a known set of side information (SI) frames is available at the decoder (e.g., each SI frame may correspond to a different stream from which we are switching). However, the use of bit-plane coding and channel coding in many DSC approaches leads to complex coding and decoding. In this paper, we propose an alternative approach for merging multiple SI frames, using a piecewise constant (PWC) function as the merge operator. In our approach, for each block to be reconstructed, a series of parameters of these PWC merge functions are transmitted in order to guarantee identical reconstruction given the known SI blocks. We consider two different scenarios. In the first case, a target frame is first given, and then merge parameters are chosen, so that this frame can be reconstructed exactly at the decoder. In contrast, in the second scenario, the reconstructed frame and the merge parameters are jointly optimized to meet a rate-distortion criteria. Experiments show that for both scenarios, our proposed merge techniques can outperform both a recent approach based on DSC and the SP-frame approach in H.264, in terms of compression efficiency and decoder complexity.

In social media analysis, one critical task is detecting a burst of topics or buzz , which is reflected by extremely frequent mentions of certain keywords in a short-time interval. Detecting buzz not only provides useful insights into the information propagation mechanism, but also plays an essential role in preventing malicious rumors. However, buzz modeling is a challenging task because a buzz time-series often exhibits sudden spikes and heavy tails, wherein most existing time-series models fail. In this article, we propose novel buzz modeling approaches that capture the rise and fade temporal patterns via Product Lifecycle (PLC) model, a classical concept in economics. More specifically, we propose to model multiple peaks in buzz time-series with PLC mixture or PLC group mixture and develop a probabilistic graphical model (K-Mixture of Product Lifecycle ( K-MPLC ) to automatically discover inherent lifecycle patterns within a collection of buzzes. Furthermore, we effectively utilize the model parameters of PLC mixture or PLC group mixture for burst prediction. Our experimental results show that our proposed methods significantly outperform existing leading approaches on buzz clustering and buzz-type prediction.

Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. In this paper, we consider a statistical setting for semi-supervised learning and provide a formal justification of the recently introduced framework of bandlimited interpolation of graph signals. Our analysis leads to the interpretation that, given enough labeled data, this method is very closely related to a constrained low density separation problem as the number of data points tends to infinity. We demonstrate the practical utility of our results through simple experiments.

Spectrum sensing is an essential functionality of cognitive radio wireless networks (CRWNs) that enables detecting unused frequency sub-bands for dynamic spectrum access. This paper proposes a compressed spectrum sensing framework by (i) constructing a sparsity basis in wavelet domain that helps compressed sensing at sub-Nyquist rates and (ii) applying a wavelet-based singularity detector on the reconstructed signal to identify available frequency sub-bands with low complexity. In particular, for the compressed sensing, an optimized Haar wavelet basis is employed to sparsely represent piecewise constant (PWC) signals which closely approximates the frequency spectrum of a sensed signal. Our simulation results show that our proposed framework outperforms existing compressed spectrum sensing methods by providing higher accuracy at lower sampling rates.

We give a probabilistic interpretation of sampling theory of graph signals. To do this, we first define a generative model for the data using a pairwise Gaussian random field (GRF) which depends on the graph. We show that, under certain conditions, reconstructing a graph signal from a subset of its samples by least squares is equivalent to performing MAP inference on an approximation of this GRF which has a low rank covariance matrix. We then show that a sampling set of given size with the largest associated cut-off frequency, which is optimal from a sampling theoretic point of view, minimizes the worst case predictive covariance of the MAP estimate on the GRF. This interpretation also gives an intuitive explanation for the superior performance of the sampling theoretic approach to active semi-supervised classification.

Image denoising is an under-determined problem, and hence it is important to define appropriate image priors for regularization. One recent popular prior is the graph Laplacian regularizer, where a given pixel patch is assumed to be smooth in the graph-signal domain. The strength and direction of the resulting graph-based filter are computed from the graph's edge weights. In this paper, we derive the optimal edge weights for local graph-based filtering using gradient estimates from non-local pixel patches that are self-similar. To analyze the effects of the gradient estimates on the graph Laplacian regularizer, we first show theoretically that, given graph-signal hDis a set of discrete samples on continuous function h(x; y) in a closed region Ω, graph Laplacian regularizer (hD)TLhDconverges to a continuous functional SΩintegrating gradient norm of h in metric space G-i.e., (∇h)TG-1(∇h)-over Ω. We then derive the optimal metric space G*: one that leads to a graph Laplacian regularizer that is discriminant when the gradient estimates are accurate, and robust when the gradient estimates are noisy. Finally, having derived G* we compute the corresponding edge weights to define the Laplacian L used for filtering. Experimental results show that our image denoising algorithm using the per-patch optimal metric space G* outperforms non-local means (NLM) by up to 1.5 dB in PSNR.

In video coding, motion compensation is an essential tool to obtain residual block signals whose transform coefficients are encoded. This paper proposes novel graph-based transforms (GBTs) for coding inter-predicted residual block signals. Our contribution is twofold: (i) We develop edge adaptive GBTs (EA-GBTs) derived from graphs estimated from residual blocks, and (ii) we design template adaptive GBTs (TA-GBTs) by introducing simplified graph templates generating different set of GBTs with low transform signaling overhead. Our experimental results show that proposed methods significantly outperform traditional DCT and KLT in terms of rate-distortion performance.

We present a novel edge adaptive depth map coding based on lifting on graphs. The transform is localized, of low complexity, and guarantees perfect reconstruction as long as a proper predict-update split is defined. During the transform process, data in the prediction set are predicted by data in the update set; the prediction errors are then stored for encoding. In order to reduce the energy of the prediction residue, we propose to use optimized sampling on graphs to select the update set. Experiments show that the optimized sampling approach achieves better results than the conventional maximum cut based splitting in terms of transform efficiency and reconstruction quality. In addition, performance using the lifting transform is comparable to the state-of-the-art graph based depth map encoder using graph Fourier transform (GFT), which requires high complexity for signal projection.

The Karhunen-Loeve transform (KLT) is known to be optimal for decorrelating stationary Gaussian processes, and it provides effective transform coding of images. Although the KLT allows efficient representations for such signals, the transform itself is completely data-driven and computationally complex. This paper proposes a new class of transforms called graph template transforms (GTTs) that approximate the KLT by exploiting a priori information known about signals represented by a graph-template. In order to construct a GTT (i) a design matrix leading to a class of transforms is defined, then (ii) a constrained optimization framework is employed to learn graphs based on given graph templates structuring a priori known information. Our experimental results show that some instances of the proposed GTTs can closely achieve the rate-distortion performance of KLT with significantly less complexity.

Intra-prediction is employed in block-based image coding to reduce energy in the prediction residual before transform coding. Conventional intra-prediction schemes copy directly from known pixels across block boundaries as prediction. In this letter, we first cluster differences between neighboring pixel pairs. Then, for each pixel pair, we add the cluster mean to the known pixel for prediction of the neighboring unknown pixel. The cluster indices are transmitted per block, allowing the decoder to mimic the same intra-prediction. We then propose an optimized transform for the prediction residual, based on a generalized version of previously developed Graph Fourier Transform (GFT). Experimental results show that our generalized intra-prediction plus transform coding outperforms combinations of previous intra-prediction and ADST coding by 2.5 dB in PSNR on average.

Piecewise smooth (PWS) images (e.g., depth maps or animation images) contain unique signal characteristics such as sharp object boundaries and slowly varying interior surfaces. Leveraging on recent advances in graph signal processing, in this paper, we propose to compress the PWS images using suitable graph Fourier transforms (GFTs) to minimize the total signal representation cost of each pixel block, considering both the sparsity of the signal's transform coefficients and the compactness of transform description. Unlike fixed transforms, such as the discrete cosine transform, we can adapt GFT to a particular class of pixel blocks. In particular, we select one among a defined search space of GFTs to minimize total representation cost via our proposed algorithms, leveraging on graph optimization techniques, such as spectral clustering and minimum graph cuts. Furthermore, for practical implementation of GFT, we introduce two techniques to reduce computation complexity. First, at the encoder, we low-pass filter and downsample a high-resolution (HR) pixel block to obtain a low-resolution (LR) one, so that a LR-GFT can be employed. At the decoder, upsampling and interpolation are performed adaptively along HR boundaries coded using arithmetic edge coding, so that sharp object boundaries can be well preserved. Second, instead of computing GFT from a graph in real-time via eigen-decomposition, the most popular LR-GFTs are pre-computed and stored in a table for lookup during encoding and decoding. Using depth maps and computer-graphics images as examples of the PWS images, experimental results show that our proposed multiresolution-GFT scheme outperforms H.264 intra by 6.8 dB on average in peak signal-to-noise ratio at the same bit rate.

In order to improve 3D video coding efficiency, we propose methods to estimate rendered view distortion in synthesized views as a function of the depth map quantization error. Our approach starts by calculating the geometric error caused by the depth map error based on the camera parameters. Then, we estimate the rendered view distortion based on the local video characteristics. The estimated rendered view distortion is used in the rate-distortion optimized mode selection for depth map coding. A Lagrange multiplier is derived using the proposed distortion metric, which is estimated based on an autoregressive model. Experimental results show the efficiency of the proposed methods, with average savings of 43% in depth map bitrate as compared with encoding the depth maps using the same coding tools but with the rate-distortion optimization based on the conventional distortion metric.

In this paper, we propose a new geometry representation method for multiview image sets. Our approach relies on graphs to describe the multiview geometry information in a compact and controllable way. The links of the graph connect pixels in different images and describe the proximity between pixels in 3D space. These connections are dependent on the geometry of the scene and provide the right amount of information that is necessary for coding and reconstructing multiple views. Our multiview image representation is very compact and adapts the transmitted geometry information as a function of the complexity of the prediction performed at the decoder side. To achieve this, our graph-based representation (GBR) carefully selects the amount of geometry information needed before coding. This is in contrast with depth coding, which directly compresses with losses the original geometry signal, thus making it difficult to quantify the impact of coding errors on geometry-based interpolation. We present the principles of this GBR and we build an efficient coding algorithm to represent it. We compare our GBR approach to classical depth compression methods and compare their respective view synthesis qualities as a function of the compactness of the geometry description. We show that GBR can achieve significant gains in geometry coding rate over depth-based schemes operating at similar quality. Experimental results demonstrate the potential of this new representation.

In this paper, we extend the Nyquist-Shannon theory of sampling to signals defined on arbitrary graphs. Using spectral graph theory, we establish a cut-off frequency for all bandlimited graph signals that can be perfectly reconstructed from samples on a given subset of nodes. The result is analogous to the concept of Nyquist frequency in traditional signal processing. We consider practical ways of computing this cut-off and show that it is an improvement over previous results. We also propose a greedy algorithm to search for the smallest possible sampling set that guarantees unique recovery for a signal of given bandwidth. The efficacy of these results is verified through simple examples.

This paper introduces a novel spectral anomaly detection method by developing a graph-based filtering framework. In particular, we consider the problem of unsupervised data anomaly detection over wireless sensor networks (WSNs) where sensor measurements are represented as signals on a graph. In our framework, graphs are chosen to capture useful proximity information about measured data. The associated graph-based filters are then employed to project the graph signals on normal and anomaly subspaces, and resulting projections are used in detection of data anomalies. The proposed approach has two main advantages over the standard spectral technique, principal component analysis (PCA). Firstly, graph-based filtering allows us to incorporate structural information known a priori (e.g., distance between sensors) in addition to data. Secondly, it provides localized transformations leading to effective distributed anomaly detection. Our experimental results show that our proposed solution outperforms PCA-based and distributed clustering-based anomaly detection methods in terms of receiver operating characteristics (ROCs).

Depth images are often presented at a lower spatial resolution, either due to limitations in the acquisition of the depth or to increase compression efficiency. As a result, upsampling low-resolution depth images to a higher spatial resolution is typically required prior to depth image based rendering. In this paper, depth enhancement and up-sampling techniques are proposed using a graph-based formulation. In one scheme, the depth is first upsampled using a conventional method, then followed by a graph-based joint bilateral filtering to enhance edges and reduce noise. A second scheme avoids the two-step processing and upsamples the depth directly using the proposed graph-based joint bilateral upsampling. Both filtering and interpolation problems are formulated as regularization problems and the solutions are different from conventional approaches. Further, we also studied operations on different graph structures such as star graph and 8-connected graph. Experimental results show that the proposed methods produce slightly more accurate depth at the full resolution with improved rendering quality of intermediate views.

In social media analysis, one critical task is detecting burst of topics or buzz, which is reflected by extremely frequent mentions of certain key words in a short time interval. Detecting buzz not only provides useful insights into the information propagation mechanism, but also plays an essential role in preventing malicious rumors. However, buzz modeling is a challenging task because a buzz time-series usually exhibits sudden spikes and heavy tails, which fails most existing time-series models. To deal with buzz time-series sequences, we propose a novel time-series modeling approach which captures the rise and fade temporal patterns via Product Life Cycle (PLC) models, a classical concept in economics. More specifically, we propose a mixture of PLC models to capture the multiple peaks in buzz time-series and furthermore develop a probabilistic graphical model (K-MPLC) to automatically discover inherent life cycle patterns within a collection of buzzes. Our experiment results show that our proposed method significantly outperforms existing state-of-the-art approaches on buzzes clustering.

Providing better representation methods for motion capture data can lead to improved performance in terms of classification, recognition, synthesis and dimensionality reduction. In this paper, we propose a novel representation method inspired by algebraic and spectral graph theoretic concepts. Our proposed method represents motion data in a space constructed with bases for skeleton-like graphs. We introduce two criteria and as well as its influences on the generated bases. With experiments on CMU MoCap database, we will also discuss how this method may act as a good preprocessing tool in order to enhance the further analysis steps on MoCap data.

Multi-view video transmission poses great challenges because of its data size and dimension. Therefore, how to design efficient 3D scene representations and coding (of luminance and geometry) has become a critical research topic. Recently, the graph-based representation (GBR) is introduced, which provides a lossless compression of multi-view geometry by connecting informative pixels among views. This representation has been shown as a promising alternative to the classical depth-based representation, where the view synthesis accuracy is hard to control. In this work, we study the luminance compression under GBR, which is not well considered in existing literature. With a proper structural reformulation, we show that the graph-based transform can be applied on the GBR paradigm, hence better extracting the correlation among pixels along graph connections. Moreover, we extend the popular SPIHT coding scheme to further improve coding efficiency. The experimental results show that our method leads to better RD coding performance as compared the classical luminance coding algorithms.

In stereo video applications, the quality of the two views may vary based on different camera capturing conditions and setup, compression/transmission, and sensor noise. Although some studies show that the perceived video quality may not be significantly affected by the lower quality view, maintaining a similar video quality is still desired in order to prevent eye strain during extended viewing sessions. In this paper, we study a graph-based approach to enhance the lower quality views by referring to the high quality view in addition to an accompanying depth map. We construct a graphical signal model with joint bilateral edge weights and show that graph-based joint bilateral filtering can better suppress several types of noises, e.g., Gaussian, motion as well as quantization noise.

Gesture dynamic pattern is an essential indicator of emotions or attitudes during human communication. However, there might exist great variability of gesture dynamics among gesture sequences within the same emotion, which form a major obstacle to detect emotion from body motion in general interpersonal interactions. In this paper, we propose a graph-based framework for modeling gesture dynamics towards attitude recognition. We demonstrate that the dynamics derived from a weighted graph based method provide a better separation between distinct emotion classes and maintain less variability within the same emotion class. This helps capture salient dynamic patterns for specific emotions by removing interaction-dependent variations. In this framework, we represent each gesture sequence as an undirected graph of connected gesture units and use the graph-based transform to generate features to describe gesture dynamics. In our experiments, we apply the graph-based dynamics for attitude recognition, i.e., classifying the attitude of an individual as friendly or conflictive. Experimental results verify the effectiveness of our approach.

We consider the problem of offline, pool-based active semi-supervised learning on graphs. This problem is important when the labeled data is scarce and expensive whereas unlabeled data is easily available. The data points are represented by the vertices of an undirected graph with the similarity between them captured by the edge weights. Given a target number of nodes to label, the goal is to choose those nodes that are most informative and then predict the unknown labels. We propose a novel framework for this problem based on our recent results on sampling theory for graph signals. A graph signal is a real-valued function defined on each node of the graph. A notion of frequency for such signals can be defined using the spectrum of the graph Laplacian matrix. The sampling theory for graph signals aims to extend the traditional Nyquist-Shannon sampling theory by allowing us to identify the class of graph signals that can be reconstructed from their values on a subset of vertices. This approach allows us to define a criterion for active learning based on sampling set selection which aims at maximizing the frequency of the signals that can be reconstructed from their samples on the set. Experiments show the effectiveness of our method.

Modern data processing tasks frequently involve structured data, for example signals defined on the vertex set of a weighted graph. In this paper, we address the problem of inference of mobility patterns from data defined on geographical graphs based on spatially localized events. Specifically, we propose a model-based approach where we build a signal model for each of the expected mobility patterns. We then analyze the characteristics of the signal models by studying their spectral representations using wavelets defined on graphs, which enables us to build efficient classifier in the spectral domain. Experiments on data gathered from photo-taking events in Flickr show that we can efficiently infer mobility patterns using only coarse aggregated information, which is certainly interesting in terms of privacy protection.

To design an energy-efficient UWB ranging system, we propose a compressive sampling (CS) technique tightly coupled to a recently proposed hardware. Our goal is to design a system that is robust to high noise and consumes less energy while providing reliable localization. In this work, we first introduce a representation of UWB signals as group sparse signals with the number of groups corresponding to the number of objects in the environment. Also, we design an efficient measurement system that is constructed using low-density parity-check (LDPC) matrix, in order to satisfy several constraints imposed by the hardware: non-negative integer entries in measurement (sensing) matrix, constant row-wise sum of non-zero entries in the matrix, and a unique structure characterized by Kronecker product. To enhance performance, we propose a window-based reweighted L1minimization that outperforms other existing algorithms in our simulation. The result shows that our proposed method can achieve reliable target-localization, while using only 40% of the scanning (sampling) time required by the sequential scanning scheme, even in highly-noisy environments.

Using texture and depth maps of a single reference viewpoint, depth-image-based rendering (DIBR) can synthesize a novel viewpoint image by translating texture pixels of the reference view to a virtual view, where synthesized pixel locations are derived from the associated depth pixel values. When the virtual viewpoint is located much closer to the 3D scene than the reference view (camera movement in the z-dimension), objects closer to the camera will increase in size in the virtual view faster than objects further away. A large increase in object size means that a patch of pixels sampled from an object surface in the reference view will be scattered to a larger spatial area, resulting in expansion holes. In this paper, we investigate the problem of identification and filling of expansion holes. We first propose a method based on depth histogram to identify missing or erroneously translated pixels as expansion holes. We then propose two techniques to fill in expansion holes with different computation complexity: i) linear interpolation, and ii) graph-based interpolation with a sparsity prior. Experimental results show that proper identification and filling of expansion holes can dramatically outperform inpainting procedure employed in VSRS 3.5 (up to 4.25dB).

We propose a new approach for describing the geometry information of multiview image representations. Rather than transmitting the raw geometry of the scene, under the form of depth information, we build a graph that represents the connections between corresponding pixels in different views in a multiview image set. The graph starts with the reference image and recursively represents the next levels (i.e., images) by storing the new pixels (those that cannot be derived from the previous image) and their connections to the lower level. The decoder uses these connections to recover the multiple images. In addition to being natural and more easily controlled, the proposed graph-based representation can be compressed more efficiently than depth images. This new representation offers promising perspectives for effective and flexible coding in multiview imaging.

In this paper, we propose a novel algorithm to interpolate data defined on graphs, using signal processing concepts. The interpolation of missing values from known samples appears in various applications, such as matrix/vector completion, sampling of high-dimensional data, semi-supervised learning etc. In this paper, we formulate the data interpolation problem as a signal reconstruction problem on a graph, where a graph signal is defined as the information attached to each node (scalar or vector values mapped to the set of vertices/edges of the graph). We use recent results for sampling in graphs to find classes of bandlimited (BL) graph signals that can be reconstructed from their partially observed samples. The interpolated signal is obtained by projecting the input signal into the appropriate BL graph signal space. Additionally, we impose a `bilateral' weighting scheme on the links between known samples, which further improves accuracy. We use our proposed method for collaborative filtering in recommendation systems. Preliminary results show a very favorable trade-off between accuracy and complexity, compared to state of the art algorithms.

The ability to efficiently switch from one pre-encoded video stream to another is a valuable attribute for a variety of interactive streaming applications, such as switching among streams of the same video encoded in different bit-rates for real-time bandwidth adaptation, or view-switching among videos capturing the same dynamic 3D scene but from different viewpoints. It is well known that intra-coded I-frames can be used at switch boundaries to facilitate stream-switching. However, the size of an I-frame is large, making frequent insertion impractical. A recent proposal towards a more efficient stream-switching mechanism is distributed source coding (D-SC), which exploits worst-case correlation between a set of potential predictor frames in the decoder buffer (called side information (SI) frames) and a target frame to lower encoding rate. However, the conventional use of bit-plane and channel coding means the encoding and decoding complexity of DSC frames is large. In this paper, we pursue a novel approach to the stream-switching problem based on the concept of “signal merging”, using piecewise constant (p-wc) function as the merge operator. Specifically, we propose a new merge mode for a code block, where for each k-th transform coefficient in the block, we encode appropriate step size and horizontal shift parameters at the encoder, so that the resulting floor function at the decoder can map corresponding coefficients from any SI frame to the same reconstructed value, resulting in an identically merged signal. The selection of shift parameter per coefficient, as well as coding modes between intra and merge per block, are optimized in a rate-distortion (RD) optimal manner. Experiments show encouraging coding gain over a previous implementation of DSC frame at low-to mid-bitrates at reduced computation complexity.

In this paper we study the bilateral filter proposed by Tomasi and Manduchi and show that it can be viewed as a spectral domain transform defined on a weighted graph. The nodes of this graph represent the pixels in the image and a graph signal defined on the nodes represents the intensity values. Edge weights in the graph correspond to the bilateral filter coefficients and hence are data adaptive. The graph spectrum is defined in terms of the eigenvalues and eigenvectors of the graph Laplacian matrix. We use this spectral interpretation to generalize the bilateral filter and propose new spectral designs of “bilateral-like” filters. We show that these spectral filters can be implemented with k-iterative bilateral filtering operations and do not require expensive diagonalization of the Laplacian matrix.

The basis functions of lifting transform on graphs are completely determined by finding a bipartition of the graph and defining the prediction and update filters to be used. In this work we consider the design of prediction filters that minimize the quadratic prediction error and therefore the energy of the detail coefficients, which will give rise to higher energy compaction. Then, to determine the graph bipartition, we propose a distributed maximum-cut algorithm that significantly reduces the computational cost with respect to the centralized version used in our previous work. The proposed techniques show improvements in coding performance and computational cost as compared to our previous work.

In this paper, we propose a new intra-frame coding approach using the predictive graph transform (PGT). The predicted block together with the reference pixels are modeled as a normal distributed random vector with respect to a graph whose edges represent the correlations between pixels. This model is more flexible than the Gaussian Markov random field (GMRF) model in the sense that it enables us to adapt the graph both before and after the collection of the statistics. The optimal prediction and the transform of the prediction residual are then derived jointly. Two PGT based intra coding schemes are proposed: one is based on global image statistics and the other is mode-adaptive, i.e., the graph is adaptive to different directional modes defined in H.264/AVC. The simulations show the advantage of our proposed approach over standard intra predictive transform coding in terms of both prediction quality and coding gain assuming the model parameters are known at decoder.

Advanced multiview video systems are able to generate intermediate viewpoints of a 3D scene. In addition to the texture content, corresponding depth is associated with each viewpoint. To improve the coding efficiency of such content, view synthesis prediction can be used to further reduce inter-view redundancy in addition to traditional disparity compensated prediction. However, the predictor generated from the view synthesis process is affected by several factors, including signal properties of the texture, the accuracy of the depth and complexity of the scene, as well as coding errors in both the texture and depth. This paper presents an analysis of view synthesis prediction performance considering these factors. Based on this analysis, an adaptive depth quantization scheme is proposed to improve the depth coding, leading to better view synthesis prediction and overall coding efficiency gains. The proposed scheme is able to achieve an average bit rate savings of 0.9% on the coded and synthesized video with a maximum gain of up to 11.7% on the dependent views in the context of an HEVC-based codec.

Depth map coding plays a crucial role in 3D Video communication systems based on the “Multi-view Video plus Depth” representation as view synthesis performance is strongly affected by the accuracy of depth information, especially at edges in the depth map image. In this paper an efficient algorithm for edge-preserving intra depth compression based on H.264/AVC is presented. The proposed method introduces a new Intra mode specifically targeted to depth macroblocks with arbitrarily shaped edges, which are typically not efficiently represented by DCT. Edge macroblocks are partitioned into two regions each approximated by a flat surface. Edge information is encoded by means of context-coding with an adaptive template. As a novel element, the proposed method allows exploiting the edge structure of previously encoded edge macroblocks during the context-coding step to further increase compression performance. Experiments show that the proposed Intra mode can improve view synthesis performance: average Bjøntegaard bit rate savings of 25% have been reported over a standard H.264/AVC Intra coder.

We introduce a novel spectro-temporal representation of speech by applying directional derivative filters to the Melspectrogram, with the aim of improving the robustness of automatic speech recognition. Previous studies have shown that two-dimensional wavelet functions, when tuned to appropriate spectral scales and temporal rates, are able to accurately capture the acoustic modulations of speech, even in high noise conditions. Therefore, spectro-temporal features extracted from the wavelet transformation of the spectrogram, offer additional noise robustness to important signal processing tasks, such as voice activity detection and speech recognition. In this paper, we explore the use of the steerable pyramid, a directional wavelet transform that is common in image processing, to derive a spectro-temporal feature representation of speech that can serve as an alternative to cepstral derivatives and Gabor filterbank features. We discuss their application for the task of robust automatic speech recognition. Experiments conducted on the Aurora-2 database demonstrate their competitive robustness to other state-of-the-art speech features, especially in low signalto-noise ratio conditions. Index Terms: spectro-temporal features, automatic speech recognition, directional wavelet transforms

This demo abstract describes an initial design of a new adaptive video streaming protocol for device-to-device WiFi-based mobile platforms and its software implementation. For the demonstration, two mobile servers and two mobile users will be deployed verifying that our device-to-device adaptive video streaming implementation works with desirable user experience.

Mosaicked color filter arrays and demosaicking methods for multispectral images have been proposed in recent years. Several studies have evaluated the multispectral filter array (MSFA) pattern, but a method to optimize the pattern has not been proposed. We focus on the spatial arrangement of MSFAs to improve the demosaicked image quality. To evaluate the filter arrangement, we propose a new metric that uses both the spatial and spectral correlation of the filters. The arrangement is optimized by using simulated annealing and the proposed metric. An advantage of the proposed metric and its optimization is that they do not need to use image data. Experimental results show that the new metric is proportional to the peak-to-signal noise ratio (PSNR) and that a higher PSNR can be obtained by minimizing the metric using simulated annealing.

A novel framework for the analysis and optimization of wireless networks operations is proposed. The temporal evolution of the state of the network is modeled as the trajectory of the state of a Finite State Machine (FSM). The state space of the FSM and the statistics of state transition are represented as a directed graph. Graph reduction and transform techniques are proposed to reduce the dimension of the graph associated with the FSM and analyze the properties of functions defined on its state space. The proposed methodology is based on the intrinsic multi-dimensional/multi-scale structure of the state space of the FSM and enables the analysis and minimization of cost-to-go functions, i.e., functions measuring the expected long-term cost associated with a control strategy, on coarser versions of the original graph.

In this paper a graph-based transform is proposed as an alternative to the discrete cosine transform. An image or video signal is represented as a graph signal, where the graph is generated so as not to cross an image edge in a local region, i.e., square block. Then, spectral representation of graph signal is used to form transform kernels by finding eigenvectors of Laplacian matrix of the graph. This method requires to include additional information, i.e., edge map or adjacency matrix, into a bitstream so that a decoder can regenerate the exactly same graph used at an encoder. The novelty of this paper includes finding the optimal adjacency matrix and compressing it using context-based adaptive binary arithmetic coding. Coding efficiency improvement can be achieved when an image block contains arbitrarily shaped edges by applying the transform not across the edges. The proposed transform is applied to coding depth maps used for view synthesis in a multi-view video coding system, and provides 14% bit rate savings on average.

In our previous work, we observed an “aliasing” phenomenon for functions defined on bipartite graphs which is analogous to aliasing occurring in the downsampling of regular 1-dimensional signals. We exploited these concepts to design critically sampled two-channel wavelet filterbanks for any bipartite graph. For arbitrary graphs, we proposed a bipartite subgraph decomposition scheme to decompose the graph into edge-disjoint bipartite subgraphs and apply filtering and downsampling separately on each subgraph. This leads to the design of multi-dimensional separable filterbanks on graphs. In this paper, we study these bipartite decompositions in more detail. In particular, we describe the meaning of dimensionality in the subgraph decomposition of arbitrary graphs and define some graph based metrics based on this understanding. Subsequently, we propose a heuristics based algorithm for bipartite subgraph decomposition and compare it with other non-optimized algorithms. The results show both qualitative and quantitative improvements in the decomposed bipartite subgraphs with the proposed heuristics.

We propose a pixel prediction algorithm, which learns a regression function corresponding to each context. A context refers to a group of pixels, that have similar correlations with its neighboring pixels. We propose to form a pixel's feature vector by its neighboring pixels' ratios, so that they better capture the pixel properties described by the regression weights. Then we use K-means clustering to classify the feature vectors of all pixels into several contexts. Clustering reduces pixel randomness within each context, thus reducing prediction error. We apply three regression algorithms, the least square, quantile and lasso regression, which assume different loss function and regularization. Experimental results demonstrate that all context based regression methods have outperformed conventional pixel predictors. Among them, quantile regression, which assumes l1-norm loss function has the best result. It has 3.1% less bits per pixel (bpp) than least square prediction with 12 neighboring pixels.

In this paper we present an adaptive compressed sensing (CS) framework for depth map compression using a family of graph-based transforms (GBT). To improve overall performance, we propose a greedy algorithm that selects for each block a GBT minimizing a metric, based on average mutual coherence, that takes into consideration both the edge structure of the block and the characteristics of the CS measurement matrix. This algorithm uses a low-complexity estimate of the mutual coherence, so that explicit construction of the GBT at the encoder is not required in the iterative process. As compared to coding using H.264/AVC, the proposed approach applied to intra-frames shows an average of 39 % bitrate savings or 3.8 dB PSNR gain for views rendered using a depth image based rendering (DIBR) technique.

To account for the unique characteristics and limitations of the human visual system (HVS) when perceiving images, a variety of perceptual quality metrics have been proposed in the literature. Tailoring rate-distortion (RD) optimization for each metric is cumbersome and time-consuming. In this paper, we propose a general RD-optimization strategy called “transform domain bounding box” (BB) that can easily adapt to different quality metrics for JPEG-like block-based encoding of images. First, we define an objective function that is a weighted sum of the l0-norm of the transform coefficients (a proxy for rate) and distortion from the transform domain representation. Next, for a given distortion target τ, we define a don't care region (DCR) that specifies a search region of representations with distortion ≤τ. We then show that the sparsest transform domain representation (lowest encoding rate) inside a BB that tightly contains the DCR can be constructed efficiently. Varying τ to induce different DCRs and corresponding BBs results in a set of constructed sparse representations of different sparsity counts, and the one that optimally trades off rate and distortion can be easily identified as solution to our objective. We show that our proposed BB strategy can be easily re-targeted for three common quality metrics: MSE, MSE-HVS-M and SSIM. Experimental results show that our BB strategy outperformed unoptimized JPEG compression by up to 1dB in PSNR when distortion metric is MSE, up to 2dB when metric is MSE-HVS-M, and up to 0.005 when metric is SSIM.

Many RGB digital cameras use a Bayer color filter array. In these cameras a full-resolution image is obtained from a mosaicked image by interpolation, and then the full resolution image is encoded. Similarly, mosaicked color filter arrays and interpolation methods for multispectral images have been proposed in recent years. The resulting full-resolution mutispectral images need to be encoded efficiently. This paper presents a new image compression method for one-shot multispectral imaging system. The proposed approach encodes the mosaicked multi-spectral image before interpolation. The decoder interpolates the image after decoding to reconstruct a full-resolution image. The simulation results show that the proposed method outperforms a conventional method, which encodes the full-resolution image after interpolation, at almost all bit rates. We also propose a heuristic color filter array design for our method that leads to lower bit rate.

To enable synthesis of any desired intermediate view between two captured views at decoder via depth-image-based rendering (DIBR), both texture and depth maps from the captured viewpoints must be encoded and transmitted in a format known as texture-plus-depth. In this paper, we focus on the compression of depth maps across time to lower the overall bitrate in texture-plus-depth format. We observe that depth maps are not directly viewed, but are only used to provide geometric information of the captured scene for view synthesis at decoder. Thus, as long as the resulting geometric error does not lead to unacceptable synthesized view quality, each depth pixel only needs to be reconstructed at the decoder coarsely within a tolerable range. We first formalize the notion of tolerable range per depth pixel as don't care region (DCR), by studying the synthesized view distortion sensitivity to the pixel value - a sensitive depth pixel will have a narrow DCR, and vice versa. Given per-pixel DCRs, we then modify inter-prediction modes during motion prediction to search for a predictor block matching per-pixel DCRs in a target block (rather than the fixed ground truth depth signal in a target block), in order to lower the energy of the prediction residual for the block. We implemented our DCR-based motion prediction scheme inside H.264; our encoded bitstreams remain 100% standard compliant. We show experimentally that our proposed encoding scheme can reduce the bitrate of depth maps coded with baseline H.264 by over 28%.

We present a new graph-based transform for video signals using wavelet lifting. Graphs are created to capture spatial and temporal correlations in video sequences. Our new transforms allow spatial and temporal correlation to be jointly exploited, in contrast to existing techniques, such as motion compensated temporal filtering, which can be seen as "separable" transforms, since spatial and temporal filtering are performed separately. We design efficient ways to form the graphs and to design the prediction and update filters for different levels of the lifting transform as a function of expected degree of correlation between pixels. Our initial results are promising, with improvements in performance as compared to existing methods in terms of PSNR as a function of the percentage of retained coefficients of the transform.

In our previous work [1, 2] we studied detection of anomalies in packet arrival times for computer networks, most detection of denial of-service (DoS) attacks in Internet traffic. In this paper we reformulate the detection method proposed in [1] using renewal theory, providing several useful extensions. This reformulation also leads to a method that would be applicable to numerous real life signals that exist as discrete events, e.g., biological signals. Most importantly renewal theory allows us to characterize the performance of our detector and determine theoretical bounds on the time-to-detection. Compared to alternative methods that use frequency spectra or event arrival rates for detection our method is shown to be superior in terms of time-to-detection. Further, unlike rate based techniques, our method can estimate the multiple periods when multiple periodic anomalies occur simultaneously.

In this paper we present methods for downsampling datasets defined on graphs (i.e., graph-signals) by extending downsampling results for traditional N-dimensional signals. In particular, we study the spectral properties of k-regular bipartite graphs (K-RBG) and prove that downsampling in these graphs is governed by a Nyquist-like criteria. The results are useful for designing critically sampled filter-banks in various data-domains where the underlying relations between data locations can be represented by undirected graphs. In order to illustrate our results we represent images as a set of k-RBG graphs and apply our downsampling results to them. The results show that common 2-D lattice downsampling methods can be seen special cases of (K-RBG) based downsampling. Further we demonstrate new downsampling schemes for images with non-rectangular connectivity.

Compression of depth maps is important for “texture plus depth” format of multiview images, which enables synthesis of novel intermediate views via depth-image-based rendering (DIBR) at decoder. Previous depth map coding schemes exploit unique depth data characteristics to compactly and faithfully reproduce the original signal. In contrast, since depth map is only a means to the end of view synthesis and not itself viewed, in this paper we explicitly manipulate depth values, without causing severe synthesized view distortion, in order to maximize representation sparsity in the transform domain for compression gain - we call this process transform domain spar-sification (TDS). Specifically, for each pixel in the depth map, we first define a quadratic penalty function, with minimum at ground truth depth value, based on synthesized view's distortion sensitivity to the pixel's depth value during DIBR. We then define an objective for a depth signal in a block as a weighted sum of: i) signal's sparsity in the transform domain, and ii) per-pixel synthesized view distortion penalties for the chosen signal. Given that sparsity (l0-norm) is non-convex and difficult to optimize, we replace the l0-norm in the objective with a computationally inexpensive weighted l2-norm; the optimization is then an unconstrained quadratic program, solvable via a set of linear equations. For the weighted l2-norm to promote sparsity, we solve the optimization iteratively, where at each iteration weights are readjusted to mimic sparsity-promoting lτ-norm, 0 ≤ τ ≤ 1. Using JPEG as an example transform codec, we show that our TDS approach gained up to 1.7dB in rate-distortion performance for the interpolated view over compression of unaltered depth maps.

Interactive navigation of large high-dimensional media datasets aims at allowing viewers to freely navigate content, selecting a subset of the high-dimensional visual data of interest for display. An example application would be remote visualization of an arbitrary 2-D planar cut from a large volumetric dataset with random access. In our previous work, we proposed a server-client based data representation and retrieval system using overlapping rotated tiles to represent the dataset, which lower the bandwidth required for accessing a random plane from large volume data. This leads to the question of how best to represent these rotated tiles for compression. In this paper we present a non-interpolated symmetric mapping algorithm, which maps each voxel in the original image to a rotated Cartesian grid point. We will show that this approach outperforms tile representation methods based on interpolation and non-symmetric mapping. In particular, the lack of interpolation means that complexity is significantly lower. Moreover, especially at high rates, remapping without interpolation will be shown to lead to overall better RD performance and the more symmetric the mapping is, the better RD performance will be achieved. Furthermore, a metric is proposed for automatically checking the mapping symmetry and measuring the percentage of the non-symmetric mapped points in the non-symmetric mapping algorithms.

We propose a complete video encoder based on directional "non- separable" transforms that allow spatial and temporal correlation to be jointly exploited. These lifting-based wavelet transforms are applied on graphs that link pixels in a video sequence based on motion information. In this paper, we first consider a low complexity version of this transform, which can operate on subgraphs without significant loss in performance. We then study coefficient reordering techniques that lead to a more realistic and efficient encoder that the one we presented in our earlier work. Our proposed technique shows encouraging results as compared to a comparable scheme based on the DCT transform.

In this paper we present a simple distributed transform for data-gathering applications for arbitrary networks that achieves significant gains over raw data transmission, while requiring minimal coordination between nodes. In most spatial compression schemes some nodes (i.e., raw nodes) need to transmit raw data before spatial compression can be performed. Nodes that receive raw data (i.e., aggregating nodes) can then perform spatial compression. Thus, most spatial compression schemes require some raw-aggregating node assignment (RANA) to enable compression. Since transmitting raw data usually requires more bits than transmitting compressed data, we seek to find RANAs that select raw nodes in order to minimize overall energy consumption in the network. We formulate the problem of optimally selecting raw nodes as a set cover problem and propose distributed solutions for a variety of scenarios, including single-sink, multi-sink and gossip-based networks.

A novel method for optical coherence tomography retinal image segmentation utilizing sparsity constraints is demonstrated. Retinal images are sparse in the layer domain. The algorithm thus transforms an input retinal image into a layer-like domain, and then uses graph theory and dynamic programming to extract the retinal layers from the sparse representation. The number of identified boundaries is not fixed and is determined by the algorithm at run-time. Results show that this method can segment up to nine layer boundaries without making overly restrictive assumptions about anatomic structure.

To improve rendered view quality in a 3-D video system, we propose to encode and transmit depth transition data, which represents, for each pixel in a frame, the location in between two existing views where the depth corresponding to that pixel changes. Given the highly localized and non-linear characteristics of rendered view distortion, it is possible to achieve better coding performance by providing this depth transition data only for subjectively important regions. In this paper, a method to apply the depth transition data to the view rendering procedure is proposed. Experimental results verify that improvements in subjective quality can be achieved by the proposed method.

Traditional multiview video coding schemes compress all captured video frames exploiting all possible inter-view and temporal frame correlation for coding gain, creating complex inter-frame dependencies in the process. In contrast, interactive multiview video streaming (IMVS) demands data navigation flexibility in the frame structure design, so that server can send only a single periodically selected video view for decoding and display at client, saving transmission bandwidth. In this paper, we generalize previous IMVS frame structure optimization to allow a client to request an arbitrary virtual view; i.e., the server sends two adjacent coded views for the client to synthesize the desired virtual view. Since existing IMVS schemes transmit only one view at a time, they employ only cross-time pre diction; i.e., the frame of previous time instant from which the client switches is used as predictor for the requested view. In our new scenario, two coded views are transmitted, thus within-time prediction can also be used, where the coded frame of one transmitted view is used to predict the frame of the other view of same time instant. Using I-frames, P-frames and Merge (M-) frames as building blocks, we formulate a Lagrangian problem to find the optimal frame structure for a desired storage/streaming rate tradeoff, with the right mixture of cross-time / within-time prediction types. Experiments show that for the same storage cost, the expected streaming rate of the proposed structure can be 40% lower than that of the I-frame-only structure, and 9% lower than that of the structure using M-frames but with cross-time prediction only.

Depth map compression is important for compact “texture-plus-depth” representation of a 3D scene, where texture and depth maps captured from multiple camera viewpoints are coded into the same format. Having received such format, the decoder can synthesize any novel intermediate view using texture and depth maps of two neighboring captured views via depth-image-based rendering (DIBR). In this paper, we combine two previously proposed depth map compression techniques that promote sparsity in the transform domain for coding gain-graph-based transform (GBT) and transform domain sparsification (TDS) - together under one unified optimization framework. The key to combining GBT and TDS is to adaptively select the simplest transform per block that leads to a sparse representation. For blocks without detected prominent edges, the synthesized view's distortion sensitivity to depth map errors is low, and TDS can effectively identify a sparse depth signal in fixed DCT domain within a large search space of good signals with small synthesized view distortion. For blocks with detected prominent edges, the synthesized view's distortion sensitivity to depth map errors is high, and the search space of good depth signals for TDS to find sparse representations in DCT domain is small. In this case, GBT is first performed on a graph defining all detected edges, so that filtering across edges is avoided, resulting in a sparsity count ρ in GBT. We then incrementally add the most important edge to an initial no-edge graph, each time performing TDS in the resulting GBT domain, until the same sparsity count ρ is achieved. Experimentation on two sets of multiview images showed gain of up to 0.7dB in PSNR in synthesized view quality compared to previous techniques that employ either GBT or TDS alone.

While much of multiview video coding focuses on the rate-distortion performance of compressing all frames of all views for storage or non-interactive video delivery over networks, we address the problem of designing a frame structure to enable interactive multiview streaming, where clients can interactively switch views during video playback. Thus, as a client is playing back successive frames (in time) for a given view, it can send a request to the server to switch to a different view while continuing uninterrupted temporal playback. Noting that standard tools for random access (i.e., I-frame insertion) can be bandwidth-inefficient for this application, we propose a redundant representation of I-, P-, and "merge" frames, where each original picture can be encoded into multiple versions, appropriately trading off expected transmission rate with storage, to facilitate view switching. We first present ad hoc frame structures with good performance when the view-switching probabilities are either very large or very small. We then present optimization algorithms that generate more general frame structures with better overall performance for the general case. We show in our experiments that we can generate redundant frame structures offering a range of tradeoff points between transmission and storage, e.g., outperforming simple I-frame insertion structures by up to 45% in terms of bandwidth efficiency at twice the storage cost.

The encoding of both texture and depth maps of multiview images, captured by a set of spatially correlated cameras, is important for any 3-D visual communication system based on depth-image-based rendering (DIBR). In this paper, we address the problem of efficient bit allocation among texture and depth maps of multiview images. More specifically, suppose we are given a coding tool to encode texture and depth maps at the encoder and a view-synthesis tool to construct intermediate views at the decoder using neighboring encoded texture and depth maps. Our goal is to determine how to best select captured views for encoding and distribute available bits among texture and depth maps of selected coded views, such that the visual distortion of desired constructed views is minimized. First, in order to obtain at the encoder a low complexity estimate of the visual quality of a large number of desired synthesized views, we derive a cubic distortion model based on basic DIBR properties, whose parameters are obtained using only a small number of viewpoint samples. Then, we demonstrate that the optimal selection of coded views and quantization levels for corresponding texture and depth maps is equivalent to the shortest path in a specially constructed 3-D trellis. Finally, we show that, using the assumptions of monotonicity in the predictor's quantization level and distance, suboptimal solutions can be efficiently pruned from the feasible space during solution search. Experiments show that our proposed efficient selection of coded views and quantization levels for corresponding texture and depth maps outperforms an alternative scheme using constant quantization levels for all maps (commonly used in video standard implementations) by up to 1.5 dB. Moreover, the complexity of our scheme can be reduced by at least 80% over the full solution search.

Remote visualization of an arbitrary 2-D planar "cut" from a large volumetric dataset with random access has both gained importance and posed significant challenges over the past few years in industrial and medical applications. In this paper, a prediction model is presented that relates transmission efficiency to voxel coverage statistics for a fast random 2-D image retrieval system. This model can be for parameter selection and also provides insights that lead us to propose a new 3D rectangular tiling scheme, which achieves an additional 10% - 30% reduction in average transmission rate as compared to our previously proposed technique, e.g.,a nearly 30%/45% reduction in the average transmission rate at the cost of a factor of ten/fifteen in storage overhead compared to traditional cubic tiling. Furthermore, this approach leads to improved random access, with less storage and run-time memory required at the client.

We consider travel time tomography problems involving detection of high contrast, discrete high velocity lines. This results in a discrete nonlinear inverse problem, for which traditional least-squares reconstruction algorithms are not suitable, as they tend to result in oscillations in the estimated values of the ray-path matrix. We propose a new algorithm that provides a more stable reconstruction for high contrast velocity scenarios. Our approach is based on using multiple candidate discrete high velocity lines along with a probabilistic mixture model that captures the likelihood of each of the lines. We propose an iterative algorithm based on a graphical model that successively updates the length and probability of these line structures. Preliminary simulation results show that exact reconstruction can be achieved in cases when the ground-truth lines are a subset of candidate structures.

Applications to evaluate Internet quality-of-service and increase network security are essential to maintaining reliability and high performance in computer networks. These applications typically use very accurate, but high cost, hardware measurement systems. Alternate, less expensive software based systems are often impractical for use with analysis applications because they reduce the number and accuracy of measurements using a technique called interrupt coalescence, which can be viewed as a form of sampling. The goal of this paper is to optimize the way interrupt coalescence groups packets into measurements so as to retain as much of the packet timing information as possible. Our optimized solution produces estimates of timing distributions much closer to those obtained using hardware based systems. Further we show that for a real Internet analysis application, periodic signal detection, using measurements generated with our method improved detection times by at least 36%.

We design lifting-based wavelet transforms for any arbitrary communication graph in a wireless sensor network (WSN). Since transmitting raw data bits along the routing trees in WSN usually requires more bits than transmitting encoded data, we seek to minimize raw data transmissions in the network. We especially focus on unidirectional transforms which are computed as data is forwarded towards the sink on a routing tree. We formalize the problem of minimizing the number of raw data transmitting nodes as a weighted set cover problem and provide greedy approximations. We compare our method with existing distributed wavelet transforms on communication graphs. The results validate that our proposed transforms reduce the total energy consumption in the network with respect to existing designs.

Interactive multiview video streaming (IMVS) is an application where, as the streaming multiview video is played back in time, an observer iteratively requests one of many available views at the server. In response, the server sends the appropriate pre-encoded data to the observer, with data chosen for transmission depending on the specific transmitted data available in the observer's cache. The primary challenge in IMVS is to design a structure for the pre-encoded multiview data, so that during an IMVS streaming session, the transmission rate is appropriately traded off with the pre-encoded data storage size. Previously, we have developed novel distributed source coding (DSC) based frame configurations to optimize the said tradeoff, outperforming periodical insertions of I-frames in both transmission and storage costs. In this paper, we show that by exploiting the freedom to choose a target decoded frame at a view switching point for DSC, further performance gains can be achieved: by up to 0.7 dB in our experiments.

Random access for remote visualization of an arbitrary 2-D planar cut from a large volumetric dataset poses significant challenges in terms bandwidth, storage and memory requirements. In our previous work, we have proposed a fast random image 3D retrieval system, which use overlapping rotated tiles to represent the dataset. This approach achieves a significant reduction in average transmission rate as compared to traditional cubic tiling. Additionally, this approach leads to improved random access, with less storage and runtime memory required at the client. In this paper, we first describe the details of our 3D compression technique. Then, we propose a new wavelet based approach, which can achieve 25% reduction in the average transmission rate at the cost of a factor of five in storage overhead (half of what was required for our previously proposed method).

Discrete tomography (DT) focuses on the reconstruction of a discrete valued image from few projection angles. Prior knowledge about the image can greatly increase the quality of the reconstructed image, especially when a small number of projections are available. In this paper, we show that DT can be formulated as a sparse signal recovery problem. By using a well designed dictionary, it is possible to represent a binary image with very few coefficients. Starting from this concept, we modify the reweighed l1algorithm to achieve a sparse solution and preserve the binary property of image. Preliminary simulation results show that our algorithm can outperform conventional continuous reconstruction methods in cases when very limited data is available.

In this paper, we propose two-channel filter-bank designs for signals defined on arbitrary graphs. These filter-banks are local, invertible and critically sampled. Depending on the chosen downsampling method, we obtain two design techniques. We propose general 2-channel transforms, where output signal is downsampled to guarantee invertibility. We also propose a lifting-based approach, where signals are downsampled before applying the transforms. Our proposed transforms are polynomials of the graph Laplacian matrix and have a simple spectral interpretation.

This work proposes a new intra prediction coding scheme for depth map images used in view interpolation. The main goal is to design a prediction scheme which can reduce the prediction error energy in blocks with arbitrary edge shapes. This will reduce the rate needed to encode such blocks while also eliminating some of the annoying artifacts caused by quantization. Since depth maps typically consist of smooth regions separated by edges, we find it sufficient to design prediction schemes which can make effective use of edge information. Working from the intra prediction framework in H.264, we provide a graph representation of pixels in a block and pixels from previously coded blocks and construct an edge-aware prediction scheme based on this. We also employ existing rate-distortion (RD) optimization methods to further improve the coding performance. Our proposed methods reduce the bit rate for depth maps by up to 29% for a fixed interpolated PSNR for some sequences.

Sets of multi-view images that capture plenoptic information from different viewpoints are typically related by geometric constraints. The proper analysis of these constraints is key to the definition of consistent compact representations of such images. We propose an algorithm for joint sparse approximation of multi-view images driven by epipolar geometry considerations. We extend greedy pursuit algorithms, such that the representation of multi-view images into linear combination of geometric atoms is able to balance approximation error and geometric consistency. We further add a rate penalty constraint that favors representations with small entropy towards efficient coding applications. Experimental results illustrate the trade-off between approximation, geometry and rate constraints in the representation of stereo omnidirectional images. In particular, we show that geometry constraints lead to a consistent description of the correlation among views, which is particularly beneficial for scene analysis or view interpolation applications. At the same time, we show that the rate constraint leads to compact representations, possibly to the detriment of geometry consistency.

Compression of depth maps is important for “image plus depth” representation of multiview images, which enables synthesis of novel intermediate views via depth-image-based rendering (DIBR) at decoder. Previous depth map coding schemes exploit unique depth characteristics to compactly and faithfully reproduce the original signal. In contrast, given that depth maps are not directly viewed but are only used for view synthesis, in this paper we manipulate depth values themselves, without causing severe synthesized view distortion, in order to maximize sparsity in the transform domain for compression gain. We formulate the sparsity maximization problem as an l0-norm optimization. Given l0-norm optimization is hard in general, we first find a sparse representation by iteratively solving a weighted l1minimization via linear programming (LP). We then design a heuristic to push resulting LP solution away from constraint boundaries to avoid quantization errors. Using JPEG as an example transform codec, we show that our approach gained up to 2.5 dB in rate-distortion performance for the interpolated view.

The objective of this work is to develop a new 3-D video coding system which can provide better coding efficiency with improved subjective quality as compared to existing 3-D video systems. We have analyzed the distortions that occur in rendered views generated using depth image based rendering (DIBR) and classified them in order to evaluate their impact on subjective quality. As a result, we found that depth map coding distortion leads to “erosion artifacts” at object boundaries, which lead to significant degradation in perceptual quality. To solve this problem, we propose a solution in which depth transition data is encoded and transmitted to the decoder. Depth transition data for a given pixel indicates the camera position for which this pixel's depth will change. A main reason to consider transmitting explicitly this information is that it can be used to improve view interpolation at many different intermediate camera positions. Simulation results show that the subjective quality can be significantly improved by reducing the effect of erosion artifacts, using our proposed depth transition data. Maximum PSNR gains of about 0.5 dB can also be observed.

For the purpose of this paper we group, under the generic term multiview video, different systems for which multiple standard video cameras and, possibly, additional depth-capturing cameras, are used. Video is then presented to the user using special glasses or displays. Research work in this area has focused on topics ranging from designing compression techniques to developing new 3D displays. In this paper we primarily consider the challenges involved in developing efficient compression tools. Our primary observation is that the “right” coding tools could depend heavily on choices made for content capture, display and communication. This is of course true for conventional video coding as well. But we will argue that it is even more important to address these issues for multiview video because there are much greater differences between different application scenarios (as compared to conventional video). The risk is that coding tools that are too narrowly focused on a specific application scenario may not be at all suitable for others. We focus specifically on three factors for which there exists significant uncertainty, namely, displays, depth estimation and content delivery. Our goal is not to discuss in detail current and future approaches (e.g., emerging alternative display technologies), but rather to show how these various approaches may have an impact on compression system design.

In this work a new set of edge-adaptive transforms (EATs) is presented as an alternative to the standard DCTs used in image and video coding applications. These transforms avoid filtering across edges in each image block, thus, they avoid creating large high frequency coefficients. These transforms are then combined with the DCT in H.264/AVC and a transform mode selection algorithm is used to choose between DCT and EAT in an RD-optimized manner. These transforms are applied to coding depth maps used for view synthesis in a multi-view video coding system, and provides up to 29% bit rate reduction for a fixed quality in the synthesized views.

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

Volume visualization with random data access poses significant challenges. While tiling techniques lead to simple implementations, they are not well suited for cases where the goal is to access arbitrarily located subdimensional datasets (e.g., being able to display an arbitrary 2D planar ldquocutrdquo from a 3D volume). Significant effort has been devoted to volumetric data compression, with most techniques proposing to tile volumes into cuboid subvolumes to enable random access. In this paper we show that, in cases where subdimensional datasets are accessed, this leads to significant transmission inefficiency. As an alternative, we propose novel server-client based data representation and retrieval methods which can be used for fast random access of oblique plane from 3D volume datasets. In this paper, 3D experiments are shown but the approach may be extended to higher dimensional datasets. We use multiple redundant tilings of the 3D object, where each tiling has a different orientation.We discuss the 3D rectangular tiling scheme and two main algorithm components of such 3D system, namely, (i) a search algorithm to determine which tiles should be retrieved for a given query and (ii) a mapping algorithm to enable efficient encoding without interpolation of rotated tiles. In exchange for increased server storage, we demonstrate that significant reductions in average transmission rate can be achieved relative to conventional cubic tiling techniques, e.g., nearly 40% reduction in average transmission rate for less than a factor of twenty overhead in storage before compression. Note that, as shown in our earlier work on the 2D case, the storage overhead will be lower after compression (e.g., in 2D the relative increase in storage in the compressed domain was at least a factor of two lower than in the uncompressed domain).

This paper introduces the design of context-based models of contours in the wavelet domain, which are used to construct generalized lifting (GL) mappings for image compression. The GL context-based mapping may significantly reduce the signal energy and the resulting bitrate. Here, we propose a strategy to define a reduced set of structured models to design the GL. The models capture the contour structures and are contrast-invariant. Initial experimental results applying the strategy on a wavelet subband exhibit potential gains. Iterations of the GL scheme as well as an adaptive entropy coding strategy may increase the coding gain.

We develop energy-efficient, adaptive distributed transforms for data gathering in wireless sensor networks. In particular, we consider a class of unidirectional transforms that are computed as data is forwarded to the sink along a given routing tree and develop a tree-based Karhunen-Loeve Transform (KLT) that is optimal in that it achieves maximum data de-correlation among this class of transforms. As an alternative to this KLT (which incurs communication overhead in order to learn second order data statistics), we propose a backward adaptive filter optimization algorithm for distributed wavelet transforms that i) achieves near optimal performance and ii) has no communication overhead in learning statistics.

This work presents a class of unidirectional lifting-based wavelet transforms for an arbitrary communication graph in a wireless sensor network. These transforms are unidirectional in the sense that they are computed as data is forwarded towards the sink on a routing tree. We derive a set of conditions under which a lifting transform is unidirectional, then find the full set of those transforms. Among this set, we construct a unidirectional transform that allows nodes to transform their own data using data forwarded to them from their descendants in the tree and data broadcasted to them from their neighbors not in the tree. This provides a higher quality data representation than existing methods for a fixed communication cost.

In this paper, block diagonal linear discriminant analysis (BDLDA) is improved and applied to gene expression data. BDLDA is a classification tool with embedded feature selection, that has demonstrated good performance on simulated data. However, by using cross validation in training, BDLDA is time consuming, thus not an appropriate algorithm for gene expression data, which has a large number of features and relatively small number of samples. In our algorithm, estimated error rate is used as a measure to choose the best model. The algorithm is optimized by repeating the model construction procedure with previously selected features removed, which leads to increased classification robustness. Our algorithm is tested using 10 fold cross validation. In most simulated and real data, our method outperforms the state-of-the-art techniques, showing promise for its use in microarray classification problems. The resulting block structure allows to identify discriminating correlated genes, which is potentially useful in cancer research.

Information theoretical region merging techniques have been shown to provide a state-of-the-art unified solution for natural and texture image segmentation. Here, we study how the segmentation results can be further improved by a more accurate estimation of the statistical model characterizing the regions. Concretely, we explore four density estimators that can be used for pdf or joint pdf estimation. The first three are based on different quantization strategies: a general uniform quantization, an MDL-based uniform quantization, and a data-dependent partitioning and estimation. The fourth strategy is based on a computationally efficient kernel-based estimator (averaged shifted histogram). Finally, all estimators are objectively evaluated using a database with available ground truth partitions.

To reduce the computational burden of the nearest neighbor search (NNS) problem, most existing algorithms focus on `preprocessing' the data set to reduce the number of objects to be examined for each querying operation (e.g., efficient data structures, metric space transforms). In this paper we present a quantization based nearest-neighbor-preserving metric approximation algorithm (QNNM) that leads to further complexity reduction by simplifying the metric computation. The proposed algorithm is based on three observations: (i) the query vector is fixed during the entire search process, (ii) the-minimum distance exhibits an extreme value distribution, and (iii) there is high homogeneity of viewpoints. Based on these, QNNM approximates original/benchmark metric in terms of preserving the fidelity of NNS rather than the distance itself, while achieving significantly lower complexity using a query-dependent quantizer. We formulate a quantizer design problem where the goal is to minimize the average NNS error. We show how the query adaptive quantizers can be designed off-line without prior knowledge of the query and present an efficient and specifically tailored off-line optimization algorithm to find such optimal quantizer. Experimental results in a motion estimation (ME) application show minimal performance degradation (average 0.05 dB loss) when using optimized 1-bit quantizer.

While multiview video coding typically focuses on the rate-distortion performance of compressing all frames of all views, we address the problem of designing a pre-encoded frame structure for a streaming server to enable a new functionality-interactive multiview switching, where a streaming client can send requests periodically to a server to switch to different views while continuing uninterrupted temporal playback of streaming video. We observe that providing bandwidth-efficient interactive view switching usually comes at the price of additional overall storage. Thus, our goal is to find a frame structure that minimizes the expected transmission rate during interactive multiview streaming, subject to a storage constraint. Noting that standard tools for random access (i.e., I-frame insertion) can be bandwidth-inefficient for this functionality, we propose to automatically generate a structure, combining I-frames, redundant P-frames and Distributed Source Coded (DSC) frames, in a near-optimal fashion to facilitate view switching. We present three new DSC techniques for view switching and discuss how these techniques can be integrated into an optimization framework. We show experimentally that near-optimal coding structures using DSC frames, in addition to I- and P-frames, reduce transmission cost over structures using I-frames only for view switching by up to 28%, and over structures using I- and P-frames only by up to 20% for the same storage cost.

Video representations that support view synthesis based on depth maps, such as multiview plus depth (MVD), have been recently proposed, raising interest in efficient tools for depth map coding. In this paper, we derive a new distortion metric that takes into consideration camera parameters and global video characteristics in order to quantify the effect of lossy coding of depth maps on synthesized view quality. In addition, a new skip mode selection method is proposed based on local video characteristics. Experimental results with the proposed mode selection scheme show coding gains of up to 2 dB for the synthesized views, as well as better subjective quality.

We investigate coding tools for interactive multiview streaming (IMVS), where clients interactively request desired views for successive video frames, and in response the server sends the appropriate pre-compressed video data to the clients. Solution based on using only I-frames to support view switching would incur high transmission cost, while for that based on using only P-frames to encode every possible traversal, although it can minimize transmission cost, prohibitive server's storage may be required. Therefore, efficient solutions for IMVS need to consider the trade-off between transmission and storage cost. In this paper, we study the potential use of distributed source coding (DSC) in IMVS. Specifically, we propose two DSC constructions that could achieve good transmission-storage trade-offs. Central to these constructions is a method that can efficiently encode the least significant bits (LSB) of a frame to be decoded, leading to competitive storage and transmission requirements. Experiment results demonstrate these constructions compare favorably to existing tools, and could be valuable for interactive multiview streaming.

In this work we consider the design of the lifting filters and trees used in a separable tree-based wavelet transform. We first consider the use of improved prediction filters, optimized to represent more efficiently smooth signals for arbitrary tree structures. We then consider the design of update filters that are orthogonal to neighboring prediction operators. While the corresponding decomposition is not fully orthogonal, near orthogonality between prediction and update operators leads to significant improvements in energy compaction. Finally we consider the design of trees that (i) avoid filtering across discontinuities in an image to reduce the amount of high frequency energy, while (ii) maintaining some regularity in the downsampled grids over multiple levels of decomposition in order to achieve good spatial localization of filtering.

MOTIVATION: The complexity of a large number of recently discovered copy number polymorphisms is much higher than initially thought, thus making it more difficult to detect them in the presence of significant measurement noise. In this scenario, separate normalization and segmentation is prone to lead to many false detections of changes in copy number. New approaches capable of jointly modeling the copy number and the non-copy number (noise) hybridization effects across multiple samples will potentially lead to more accurate results. METHODS: In this article, the genome alteration detection analysis (GADA) approach introduced in our previous work is extended to a multiple sample model. The copy number component is independent for each sample and uses a sparse Bayesian prior, while the reference hybridization level is not necessarily sparse but identical on all samples. The expectation maximization (EM) algorithm used to fit the model iteratively determines whether the observed hybridization levels are more likely due to a copy number variation or to a shared hybridization bias. RESULTS: The new proposed approach is compared with the currently used strategy of separate normalization followed by independent segmentation of each array. Real microarray data obtained from HapMap samples are randomly partitioned to create different reference sets. Using the new approach, copy number and reference intensity estimates are significantly less variable if the reference set changes; and a higher consistency on copy numbers detected within HapMap family trios is obtained. Finally, the running time to fit the model grows linearly in the number samples and probes. AVAILABILITY: http://biron.usc.edu/~piquereg/GADA.

We propose a novel computation control method for variable-complexity Fano decoders with buffers. Our method substantially lowers the rates of data block loss associated with conventional Fano decoders. For reasonably large buffer sizes, our method outperforms Layland's buffer management scheme with block loss rates close to the theoretical lower bound.

This paper extends rate-distortion optimized streaming techniques to operate on a general class of coding formats that explicitly support redundancy in their coding structure. Examples include multiple description layered coding (MDLC) and multiple independently encoded versions of a video source. Such source codecs usually produce multiple decoding paths, while previous work on video streaming has mostly focused on those encoding techniques that only generate a single decoding path. A new source model called Directed Acyclic HyperGraph is introduced to describe the dependency and redundancy relationship between different video data units with multiple decoding paths. Based on this model, we then propose two rate-distortion based packet scheduling algorithms, i.e., Lagrangian optimization and a greedy algorithm, to dynamically adjust the system's real-time redundancy to match the channel behavior. The proposed streaming system introduces two types of redundancies, namely, source redundancy and transport redundancy. This paper presents a detailed performance analysis of the individual benefits for error robustness provided by these redundancies and their interplay. Experimental results show that our proposed system with both redundancies achieves the best end-to-end performance on real-time video communication over a wide range of network scenarios.

Community streaming is an enhanced form of joint content viewing where a sense of community is reinforced by the addition of interactive visual overlays, controlled in real-time by viewers, on top of a shared video stream. As a concrete example, we describe a community video system called ECHO, where personalized avatars are overlaid on top of a real-time encoded video stream of an Internet game for multicast consumption. Recognizing that only the visual overlays are generated live, we propose schemes that encode and schedule the live and non-live portions of the overlaid video separately in order to exploit the difference in delay sensitivity of the two, leading to video streams that contain two sub-streams with different delay constraints. We show that, in the known channel case, a low complexity ldquoearliest deadline firstrdquo packet scheduling algorithm minimizes receiver buffer delay. We also analyze the case where multiple streams are multiplexed, which allows us to quantify the potential gains of allowing different delay constraints for different sub-streams. We show that a ldquowater fillingrdquo strategy maximizes the total number of streams that can be supported. Simulation results show that the bandwidth necessary to maintain low-latency for visual overlays is reduced by about 40% when our proposed sub-stream approach is used. For multiplexing of multiple streams, our approach can increase the number of supported streams (e.g., a 30% increase when around ten streams are multiplexed).

We address the design and optimization of an energy-efficient lifting-based 2D transform for wireless sensor networks with irregular spatial sampling. The 2D transform is designed to allow for unidirectional computation found in existing path-wise transforms, thereby eliminating costly backward transmissions often required by existing 2D transforms, while simultaneously achieving greater data decorrelation than those path-wise transforms. We also propose a framework for optimizing the 2D transform via an extension of standard dynamic programming (DP) algorithms, where a selection is made among alternative coding schemes (e.g., different number of levels in the wavelet decomposition). A recursive DP formulation is provided and an algorithm is given that finds the minimum cost coding scheme assignment for our proposed 2D transform.

Block-based motion and disparity compensation are popular techniques to exploit correlation between video frames. Block sizes used for compensation can be chosen to achieve a good trade-off between signaling overhead and prediction accuracy. However, motion field boundaries correspond to objects having arbitrary shapes; this limits the accuracy of block-based compensation, even when small block sizes are chosen. In this paper we seek to enable compensation based on arbitrarily-shaped regions, while preserving an essentially block-based compensation architecture. To do so, we propose tools for implicit block-segmentation and predictor selection. Given two candidate block predictors, segmentation is applied to the difference of predictors. Then a weighted sum of predictors in each segment is selected for prediction. Simulation results show improvements in rate-distortion (R-D) performance, as compared to the standard quad tree approach in H.264/AVC.

In this paper, we consider compensation of focus mismatches for frames that are encoded with inter-view bi-prediction (B-frames) in multiview coding (MVC). We start with an analysis of a multiview system with focus mismatches, to demonstrate that a B-frame may suffer from different types of mismatches with respect to the frames from different views used as references. As compared to our previous work for inter-view P-frames, filter estimation for B-frames has to consider not only the depth-dependency of focus mismatches, but also i) the possibility that the two predictors, from different directions, exhibit different types of prediction mismatches, and ii) the effect of bi-predictive search on the generation of filtered references. We show that, designing filters only for the averaged bi- predictors could lead to a suboptimal solution when combined with conventional bi-predictive search schemes. Instead, we propose a filter design approach that estimates two sets of depth-related filters, each set compensating for the focus mismatches exhibit in one of the two references used for bi-directional prediction. Simulation results shows that for views coded with inter-view bi-prediction, the proposed method provides up to 0.8 dB gain over current H.264/AVC in the sequences we tested.

In this work, we present a method for achieving a compact image representation by applying wavelet lifting along an arbitrary combination of trees. This is done by extending a lifting transform along a single tree to a series of lifting transforms along a number of different trees, each of which exploits directionality differently. The trees are constructed in ways that force tree edges to follow the geometric flows inherent in images. In particular, we propose a method for constructing trees that trace out geometric flows using edges in the image. Our preliminary results demonstrate promising performance in terms of PSNR as a function of the percentage of retained coefficients, motivating its potential for image coding.

The segmental eigenvoice method has been proposed to provide rapid speaker adaptation with limited amounts of adaptation data.In this method, the speaker-vector space is clustered to several subspaces and PCA is applied to each of the resulting subspaces.In this paper, we propose two new techniques to improve the performance of this segmental eigenvoice approach.First, we propose a soft-clustering method in which each element in a speaker vector can be assigned to more than one cluster.Second, those elements far apart from any of the clusters are removed.Our experiments using the JNAS and S-JNAS databases show that the proposed method outperforms both the original eigenvoice and the segmental eigenvoice methods, e.g., 3.3% average improvement when only 10 utterances are used for adaptation.

We address the joint optimization of routing and compression for wireless sensor networks using a lifting-based 2D transform that can be computed along arbitrary routing trees. The proposed 2D transform allows for unidirectional computation, thereby eliminating costly backward transmissions often required by existing 2D transforms. We also propose a framework for optimizing the transform by selecting among a different set of coding schemes (i.e., different levels in the wavelet decomposition). Since our transform can operate on arbitrary routing trees, we focus on the problem of jointly optimizing routing trees based on inter-node data correlation and inter-node distance. The two extreme solutions would be i) to route data along paths that maximize inter-node data correlation (at the risk of increasing transport costs), corresponding to a minimum spanning tree (MST), or ii) to follow shortest path tree (SPT) routing (where inter-node data correlation may not be as high). We propose an optimization technique that exhaustively searches for the optimal tree over a set of combinations of MST and SPT. We also propose a heuristic approximation algorithm that is amenable for use on larger networks and with which we observe total cost reductions close to 10% for some of the data.

While most multiview coding techniques focus on compressing all frames in a multiview video sequence in a rate-distortion optimal manner, in this paper we address the problem of interactive multiview streaming, where we minimize the expected transmission rate of an interactive multiview video stream, where the observer can select the view of the next frame, subject to a storage constraint. We show that gains can be achieved by optimizing the trade-off between overall storage and transmission rate, i.e., by storing a more redundant multiview representation (where some frames are encoded more than once, each time using a different reference frame) it is possible to reduce the overall bandwidth needed for online interactive viewing. We show that our proposed redundant representation can reduce the transmission cost of interactive multiview streaming by up to 65% as compared to a good non-redundant representation for the same storage constraint.

MOTIVATION: Genomic instability in cancer leads to abnormal genome copy number alterations (CNA) that are associated with the development and behavior of tumors. Advances in microarray technology have allowed for greater resolution in detection of DNA copy number changes (amplifications or deletions) across the genome. However, the increase in number of measured signals and accompanying noise from the array probes present a challenge in accurate and fast identification of breakpoints that define CNA. This article proposes a novel detection technique that exploits the use of piece wise constant (PWC) vectors to represent genome copy number and sparse Bayesian learning (SBL) to detect CNA breakpoints. METHODS: First, a compact linear algebra representation for the genome copy number is developed from normalized probe intensities. Second, SBL is applied and optimized to infer locations where copy number changes occur. Third, a backward elimination (BE) procedure is used to rank the inferred breakpoints; and a cut-off point can be efficiently adjusted in this procedure to control for the false discovery rate (FDR). RESULTS: The performance of our algorithm is evaluated using simulated and real genome datasets and compared to other existing techniques. Our approach achieves the highest accuracy and lowest FDR while improving computational speed by several orders of magnitude. The proposed algorithm has been developed into a free standing software application (GADA, Genome Alteration Detection Algorithm). AVAILABILITY: http://biron.usc.edu/~piquereg/GADA

In many practical distributed source coding (DSC) applications, correlation information has to be estimated at the encoder in order to determine the encoding rate. Coding efficiency depends strongly on the accuracy of this correlation estimation. While error in estimation is inevitable, the impact of estimation error on compression efficiency has not been sufficiently studied for the DSC problem. In this paper,we study correlation estimation subject to rate and complexity constraints, and its impact on coding efficiency in a DSC framework for practical distributed image and video applications. We focus on, in particular, applications where binary correlation models are exploited for Slepian-Wolf coding and sampling techniques are used to estimate the correlation, while extensions to other correlation models would also be briefly discussed. In the first part of this paper, we investigate the compression of binary data. We first propose a model to characterize the relationship between the number of samples used in estimation and the coding rate penalty, in the case of encoding of a single binary source. The model is then extended to scenarios where multiple binary sources are compressed, and based on the model we propose an algorithm to determine the number of samples allocated to different sources so that the overall rate penalty can be minimized, subject to a constraint on the total number of samples. The second part of this paper studies compression of continuous valued data. We propose a model-based estimation for the particular but important situations where binary bit-planes are extracted from a continuous-valued input source, and each bit-plane is compressed using DSC. The proposed model-based method first estimates the source and correlation noise models using continuous valued samples, and then uses the models to derive the bit-plane statistics analytically. We also extend the model-based estimation to the cases when bit-planes are extracted based on the significance of the data, similar to those commonly used in wavelet-based applications. Experimental results, including some based on hyperspectral image compression, demonstrate the effectiveness of the proposed algorithms.

A method to establish correspondences between regions belonging to independent segmentations of multiple views of a scene is presented. The trade-off between color similarity and projective similarity of the matching regions is formulated in terms of a constrained optimization, analogous to a rate-distortion budget-constrained allocation problem, and solved using Lagrangian optimization techniques.

In this paper, we apply dynamic voltage scaling (DVS) to the matching metric computation (MMC) used within motion estimation (ME) in typical video encoders. Our approach is based on "soft DSP" concepts. We analyze the effect of ME errors (due to DVS) in overall coding performance. We propose a model for the resulting rate increase (at a given fixed quantization parameter) as a function of input characteristics and input voltage, for given ME algorithm and MMC architecture. This model is validated using simulations. We then compare ME algorithms and MMC architectures, and propose a method for power saving of the ME process that depend on input characteristics and desired coding performance. As an illustration of the potential benefits of allowing computation errors, we show that allowing errors that lead to a small rate increase (about 3%) produces 37% power savings in the ME process, as compared to not using DVS. An essentially "error-free" DVS approach (no rate penalty) can achieve around 10% power savings.

We propose an adaptive filtering approach for coding video that exhibits localized camera focus changes, e.g., such that different portions of a video frame can undergo different blurriness/sharpness changes with respect to corresponding areas in frames used for prediction. First we obtain, for each macroblock, the filter that provides maximum reduction in residual energy, when applied to the reference macroblock before to motion compensation. Then, starting from the block-wise filter parameters, we divide the macroblocks into classes, by clustering macroblocks that have been assigned "similar" filters. Finally, for each class, a two-dimensional filter is designed to minimize the average residual energy for all macroblocks in the class. The resulting filters are applied to the reference frames to generate better matches for motion compensation. Simulation results shows that the proposed method provides up to 1 dB gain over current H.264 for certain sequences. As compared to H.264 with multiple reference frames, the coding gain is about 0.5 dB.

Alterations in the number of DNA copies are very common in tumor cells and may have a very important role in cancer development and progression. New array platforms provide means to analyze the copy number by comparing the hybridization intensities of thousands of DNA sections along the genome. However, detecting and locating the copy number changes from this data is a very challenging task due to the large amount of biological processes that affect hybridization and cannot be controlled. This paper proposes a new technique that exploits the key characteristic that the DNA copy number is piecewise-constant along the genome. First, wavelet footprints are used to obtain a basis for representing the DNA copy number that is maximally sparse in the number of copy number change points. Second, sparse Bayesian learning is applied to infer the copy number changes from noisy array probe intensities. Results demonstrate that sparse Bayesian learning has better performance than matching pursuits methods for this high coherence dictionary. Finally, our results are also shown to be very competitive in performance as compared to state-of-the-art methods for copy number detection.

Numerous approaches for distributed video coding have been recently proposed. One of main motivations for these techniques is the possibility of achieving complexity tradeoffs between the encoder and the decoder that may not be feasible in the context of conventional video coding. In our previous work, a maximum likelihood (ML) method for motion estimation at the decoder was proposed. It was shown that the ML method, designed based on the PRISM architecture, induces no additional rate cost, and is able to work with existing methods, e.g. those based on hash functions or CRC, to improve overall decoding PSNR. In this work, we present a rate-distortion analysis of our ML method. This analysis, given a correlation model for the video data, allows us to improve bit allocation at the encoder, i.e., the decision on the number of cosets to be used to represent various types of video information. We also signal "end of block" (EOB) in coding to further exploit the energy compaction. Our experiments demonstrate significant improvements PSNR up to 1.5 dB from RD optimized bit allocation.

In this paper, we propose power efficient motion estimation (ME) using multiple imprecise sum of absolute difference (SAD) metric computations. We extend the recent work of Varatkar et al (2006) by providing analytical solutions based on modelling of computation errors due to voltage overscaling (VOS) and sub-sampling (SS). Results show that our solutions provide significantly better performance in the sense of rate increase for fixed QP, e.g., less than 5% increase, while in Varatkar et al (2006) the rate increase could be as high as 20%. It allows us to apply lower voltage which leads to additional power saving. Our analysis also allows us to compare different ME algorithms (e.g., full search vs. a fast algorithm) and SAD computation architectures (parallel vs. serial) in terms of their robustness to imprecise metric computations and their power efficiency. Finally, we demonstrate that additional power savings can be achieved by removing redundancy between the various computations.

We investigate video compression techniques to address problems that requireflexible video decoding. In these, the encoder has access to a number of candidate predictors that allow it to exploit source signal correlation, but only a subset of these predictors will be available at the decoder. Crucially, the encoderdoes notknow which predictors will be available. Flexible decoding is important in a number of applications including frame-by-frame forward and backward video playback, multiview video, bitstreams switching, robust video transmission, etc. The main challenge to support flexible decoding is that the encoder needs to compress a current frame under the uncertainty on the predictor at decoder. An approach based on conventional "closed loop" prediction, e.g., motion-compensated predictive (MCP) coding in the case of video, could be developed by including multiple possible prediction residues in the bitstream, but this would lead to a considerable coding performance penalty, if all possible predictor combinations are supported, or to drifting, if only some combinations are. Moreover, it is not possible in general to guarantee that decoded versions under different prediction scenarios will be identical. In this paper, we propose a distributed source coding (DSC) based algorithm to tackle the problem. The main novelties of the proposed algorithm are that it incorporates different macroblock modes and significance coding within the DSC framework. This, combined with a judicious exploitation of correlation statistics, allows us to achieve competitive coding performance. Using forward/backward video playback as an example, we demonstrate the proposed algorithm can outperform a solution based on MCP coding.

The progress of VLSI technology towards deep sub-micron feature sizes, e.g., sub-100 nanometer technology, has created a growing impact of hardware defects and fabrication process variability, which lead to reductions in yield rate. To address these problems, a new approach, system-level error tolerance (ET), has been recently introduced. Considering that a significant percentage of the entire chip production is discarded due to minor imperfections, this approach is based on accepting imperfect chips that introduce imperceptible/acceptable system-level degradation; this leads to increases in overall effective yield. In this paper, we investigate the impact of hardware faults on the video compression performance, with a focus on the motion estimation (ME) process. More specifically, we provide an analytical formulation of the impact of single and multiple stuck-at-faults within ME computation. We further present a model for estimating the system-level performance degradation due to such faults, which can be used for the error tolerance based decision strategy of accepting a given faulty chip. We also show how different faults and ME search algorithms compare in terms of error tolerance and define the characteristics of search algorithm that lead to increased error tolerance. Finally, we show that different hardware architectures performing the same metric computation have different error tolerance characteristics and we present the optimal ME hardware architecture in terms of error tolerance. While we focus on ME hardware, our work could also applied to systems (e.g., classifiers, matching pursuits, vector quantization) where a selection is made among several alternatives (e.g., class label, basis function, quantization codeword) based on which choice minimizes an additive metric of interest.

We consider the problem of coding multi-view video that exhibits mismatches in frames from different views. Such mismatches could be caused by heterogeneous cameras and/or different shooting positions of the cameras. In particular, we consider focus mismatches across views, i.e., such that different portions of a video frame can undergo different blurriness/sharpness changes with respect to the corresponding areas in frames from the other views. We propose an adaptive filtering approach for cross-view prediction in multi-view video coding. The disparity fields are exploited as an estimation of scene depth. An Expectation-maximization (EM) algorithm is applied to classify the disparity vectors into groups. Based on the classification result, a video frame is partitioned into regions with different scene-depth levels. Finally, for each scene-depth level, a two-dimensional filter is designed to minimize the average residual energy of cross-view prediction for all blocks in the class. The resulting filters are applied to the reference frames to generate better matches for cross-view prediction. Simulation results show that, when encoding across views, the proposed method achieves up to 0.8dB gain over current H.264 video coding.

We propose new tools for multiview video coding (MVC) that aim to compensate for mismatches between video frames corresponding to different views. Such mismatches could be caused by different shooting positions of the cameras and/or heterogeneous camera settings. In particular, we consider illumination and focus mismatches across views, i.e., such that different portions of a video frame can undergo different illumination and blurriness/sharpness changes with respect to the corresponding areas in frames from the other views. Models for illumination and focus mismatches are proposed and new coding tools are developed from the models. We propose a block-based illumination compensation (IC) technique and a depth-dependent adaptive reference filtering (ARF) approach for cross-view prediction in multiview video coding. In IC, disparity field and illumination changes are jointly computed as part of the disparity estimation search. IC can be adaptively applied by taking into account the rate-distortion characteristics of each block. For ARF, the disparity fields are used to estimate scene depth, such that video frames are first divided into regions with different scene-depth levels. A 2-D filter is then selected for each scene-depth level. These filters are chosen to minimize residual energy, with the goal of compensating for focus mismatches. The resulting filters are applied to the reference frames to generate better matches for cross-view prediction. Furthermore, we propose a coding system that combines IC and ARF. Adjustments are made so as to maximize the gains achieved by using both coding tools, while reducing the complexity of the final integrated system. We analyze the complexity of all proposed methods and present simulation results of IC, ARF and combined system for different multiview sequences based on the H.264/AVC reference codec. When applying the proposed tool to cross-view coding we observe gains of up 1.3 dB as compared to directly using an H.264/AVC codec to perform predictive coding across views.

We address a scenario where energy-constrained sensors in a wireless sensor network can choose among different distributed coding schemes to encode their data. We propose a framework where the network is described as a graph, with sensors representing the nodes, and where communication and processing costs are associated to edge weights and the coding schemes associated to states of operation. After describing data transitions and edge costs, we show that a shortest-path algorithm can be used to find the optimum network configuration, i.e., the one that leads to the lowest overall energy consumption

In this paper, we propose a distributed source localization algorithm based on the Maximum A Posteriori (MAP) criterion, where the observations generated by each of the distributed sensors are quantized before being transmitted to a fusion node for localization. If the source signal energy is known, each quantized sensor reading corresponds to a region in which the source can be located. Aggregating the information obtained from multiple sensors corresponds to generating intersections between the regions. In our previous work we developed quantizer design techniques aimed at optimizing localization accuracy for a given aggregate rate. In this paper we develop localization algorithms based on estimating the likelihood of each of the intersection regions. This likelihood can incorporate uncertainty about the source signal energy as well as measurement noise. We show that the computational complexity of the algorithm can be significantly reduced by taking into account the correlation of the received quantized data. We also propose a technique, based on a weighted average of estimators, to address the case when the signal energy is unknown. Our simulation results show that our localization algorithm achieves good performance with reasonable complexity as compared with Minimum Mean Square Error (MMSE) estimation.

Model selection and feature selection are usually considered two separate tasks. For example, in a linear discriminant analysis (LDA) setting, a modeling assumption is typically made first (e.g., a full or a diagonal covariance matrix can be chosen) and then with this model the feature subset providing the best prediction performance is selected. If limited training data is available, then the number of parameters of a model that can be reliably estimated will also be limited. In the context of LDA, model selection basically entails simplifying the covariance matrix by setting to zero some of this components. This leads to different block diagonal matrix structures (e.g., full/diagonal) which involve different sets of features and require different parameters to be estimated. In this paper we argue that LDA feature and parameter selection should be done jointly; and we propose a greedy algorithm for joint selection of features and of a block diagonal structure for the covariance matrix. To the best of our knowledge this is the first time such a joint design has been proposed in the context of LDA. The choice of a block diagonal structure is motivated by microarray classification problems, where we have a very large amount of features, i.e., genes, that are expected to be corregulated in small groups. Results obtained with artificial datasets show that the algorithm can flexibly choose an adequate covariance matrix structure according to the size of the training set and the generating distribution. Our results consistently outperform those achieved with other LDA based techniques

In this paper we study the computation error tolerance properties of motion estimation algorithms. We are motivated by two scenarios where hardware systems may introduce computation errors. First, we consider hardware faults such as those arising in a typical fabrication process. Second, we consider "soft" errors due to voltage scaling, which can arise when operating at a lower voltage than specified for the system. Current practice is to discard all faulty systems. However there is an increasing interest in tools that can identify faulty systems which provide acceptable performance. We show that motion estimation (ME) algorithms exhibit significant error tolerance in these two scenarios. We propose simple error models and use these to provide insights into what features in these ME algorithms lead to increased error tolerance. Our comparison of the full search ME and a state of the art fast ME approach in the context of H.264/AVC shows that while both techniques are error tolerant, the faster algorithm is in fact more robust to computation errors.

In many practical distributed source coding (DSC) applications correlation information has to be obtained at the encoder in order to determine the encoding rate. Coding efficiency depends strongly on the accuracy of this correlation estimation, which often has to be performed under rate and complexity constraints. In this paper we focus on correlation estimation for wavelet-based DSC. We extend our previously proposed model-based estimation techniques, which provided accurate estimates of bit-plane level correlation under rate constraints, in the simple case where bit-planes are generated from the binary representation of the sources. To extend the model-based approach to wavelet-based DSC, we need to address two issues. Firstly, in order to improve coding efficiency, bit-planes are typically generated by more sophisticated algorithms in wavelet-based DSC (e.g., by deciding on the bitplane scan order based on coefficient "significance"), which makes model-based estimation more challenging. Secondly, certain wavelet subbands may not have enough coefficients for reliable model estimation, so that model-based techniques alone may not be sufficiently accurate. We propose solutions to these problems and, using a DSC-based hyperspectral image system as example, we demonstrate that model-based estimation can lead to efficient system implementation with lower computational and data exchange requirements, and improved parallelism, while incurring only small degradation in coding efficiency.

We address the problem of energy consumption reduction for wireless sensor networks, where each of the sensors has limited power and acquires data that should be transmitted to a central node. The final goal is to have a reconstructed version of the data measurements at the central node, with the sensors spending as little energy as possible, for a given data reconstruction accuracy. In our scenario, sensors in the network have a choice of different coding schemes to achieve varying levels of compression. The compression algorithms considered are based on the lifting factorization of the wavelet transform, and exploit the natural data flow in the network to aggregate data by computing partial wavelet coefficients that are refined as data flows towards the central node. The proposed algorithm operates by first selecting a routing strategy through the network. Then, for each route, an optimal combination of data representation algorithms i.e. assignment at each node, is selected. A simple heuristic is used to determine the data representation technique to use once path merges are taken into consideration. We demonstrate that by optimizing the coding algorithm selection the overall energy consumption can be significantly reduced when compared to the case when data is just quantized and forwarded to the central node. Moreover, the proposed algorithm provides a tool to compare different routing techniques and identify those that are most efficient overall, for given node locations. We evaluate the algorithm using both a second-order autoregressive (AR) model and empirical data from a real wireless sensor network deployment.

Hyperspectral images have correlation at the level of pixels; moreover, images from neighboring frequency bands are also closely correlated. In this paper, we propose to use distributed source coding to exploit this correlation with an eye to a more efficient hardware implementation. Slepian-Wolf and Wyner-Ziv based correlated coding theorems have quantified how much additional rate reduction can be obtained. In order to better exploit these correlations, we first propose a prediction model to align images. This model is based on linear prediction techniques and it is simple and shown to be effective for hyperspectral images. We then propose a coding scheme to exploit these correlations. A set-partitioning approach is used on wavelet transformed data to extract bitplanes. Under our correlation model, bitplanes from neighboring bands are correlated and we then use a low-density parity-check based Slepian-Wolf code to exploit this bitplane level correlation. This scheme is appealing for hardware implementation as it is easy to parallelize and it has modest memory requirements. As for coding performance, our preliminary results for high correlation spectral bands from the NASA AVIRIS dataset show, at medium to high reconstructed qualities, gains of about a factor of 3 in compression efficiency as compared to encoding the spectral bands independently using SPIHT.

We address the problem of compression for wireless sensor networks, where each of the sensors has limited power, and acquires data that should be sent to a central node. The final goal is to have a reconstructed version of the sampled field at the central node, with the sensors spending as little energy as possible. We propose a distributed compression algorithm for multihop, distributed sensor networks based on the lifting factorization of the wavelet transform that exploits the natural data flow in the network to aggregate data by computing partial wavelet coefficients that are refined as the data flows towards the central node. A key result of our work is that by performing partial computations we greatly reduce unnecessary transmission, significantly reducing the overall energy consumption.

In this paper, we propose a quantizer design algorithm that is optimized for source localization in sensor networks. For these applications, the goal is to minimize the amount of information that the sensor nodes have to exchange in order to achieve a certain source localization accuracy. We show that to achieve this goal requires the use of "application-specific" quantizers. Our proposed quantizer design algorithm uses a cost function that takes into account the distance between the actual source position and the position estimated based on quantized data. We apply this algorithm to a system where an acoustic sensor model is employed for localization. For this case we introduce the equally distance-divided quantizer (EDQ), designed so that quantizer partitions correspond to a uniform partitioning in terms of distance. Our simulations show the improved performance of our quantizer over traditional quantizer designs. They also show that an optimized bit allocation leads to significant improvements in localization performance with respect to a bit allocation that uses the same number of bits for each node.

Distributed source coding (DSC) depends strongly on accurate knowledge of correlation between sources. Previous works have reported capacity-approaching code constructions when exact knowledge of correlation is available at the encoder. However, in many applications exact correlation information may not be available, and correlation estimation is necessary. While error in estimation is inevitable, the impact of estimation error on compression efficiency has not been sufficiently studied for the DSC problem. In this paper we study correlation estimation subject to complexity constraints, and its impact on coding efficiency in a DSC framework. In particular, we consider the case where estimation entails information exchange between spatially separate sources and thus correlation estimation is subject to rate constraints. We first derive optimal strategies for information exchange that minimize the rate penalty due to inaccurate estimation, under constraints on the number of bits that can be exchanged between sources. Experimental results show that significant gain is possible by optimally exchanging information. We then derive analytical expressions to quantify the rate penalty, and analyze how rate penalty changes with a priori knowledge of correlation. In addition, we present a model-based estimation method which can achieve more accurate estimation results compared to directly inspecting the data.

We consider the bit allocation problem in multiview video coding (MVC). A dependent coding technique using trellis expansion and the Viterbi algorithm (VA) is proposed, which takes into account dependencies across time and views. We note that, typically, optimal quantizer choices have the following properties: i) quantization choices tend to be similar for frames that are consecutive (in time or in view), ii) better quantization tends to be used for frames closer to the root of the dependency tree. We propose a search algorithm to speed up the optimization of quantization choices. Our results indicate significant gains can be achieved by an appropriate selection of bit allocation across frames.

In this paper, we propose a quantizer design algorithm that is optimized for source localization in sensor networks. For this application, the goal is to minimize the amount of information that the sensor nodes have to exchange in order to achieve a certain source localization accuracy. We show that this goal can be achieved more efficiently when "application-specific" quantizers are used. Our proposed quantizer design algorithm uses a cost function that takes into account the distance between the actual source position and the position estimated based on quantized data. We also propose a distributed encoding algorithm that is applied after quantization and achieves rate savings by merging quantization bins without any degradation of localization performance. The merging technique in the encoding algorithm exploits the fact that certain combinations of quantization bins at each node cannot occur because the corresponding spatial regions have an empty intersection. We apply these algorithms to a system where an acoustic sensor model is employed for localization. For this case, we introduce the equally distance-divided quantizer (EDQ), designed so that quantizer partitions correspond to a uniform partitioning in terms of distance. Our simulations show the improved performance of our quantizer over traditional quantizer designs. In addition, they show rate savings (32.8%, 5 nodes, 4 bits per node) when our novel bin-merging algorithms are used. Our results also show that an optimized bit allocation leads to significant improvements in localization performance with respect to a bit allocation that uses the same number of bits for each node.

We address the problem of compression for wireless sensor networks, where each of the sensors has limited power, and acquires data that should be sent to a remote central node. The final goal is to have a reconstructed version of the sampled field at the central node, with the sensors spending as little energy as possible. We propose a distributed wavelet algorithm, based on the lifting scheme, as a means to decorrelate data at the nodes by exchanging information between neighboring sensors. A key result of our work is that by using a locally adaptive distributed transform it is possible to optimize overall power consumption by operating at the right trade-off point between local processing and transmission costs.

The paper proposes modifications to improve the recognition performance obtainable by the ETSI standard distributed speech recognition encoder, Aurora (ES 201 108, 2000). The proposed modifications are standard compliant, i.e., they require no algorithmic modifications to the Aurora operation. Performance improvements are achieved by distributing the available bit budget among Aurora's seven (different) 2-dimension vector quantizers (VQs) more efficiently. Improved bit-allocation to the different sub-vectors is achieved by incorporating the importance for recognition of each of the sub-vectors into the bit-allocation algorithm. The available bits are efficiently distributed among the sub-vectors by allocating a larger fraction of the available bits to the more important sub-vectors and hence maximizing recognition accuracy. The proposed bit-allocation algorithm is based on a novel mutual information (MI) measure. The MI measure quantifies the information content between a sub-vector and the class label and hence is a good indicator of the importance of the coefficient for recognition. It is shown that the proposed MI based method outperforms both the standard Aurora encoder and an encoder designed using traditional mean square error based bit-allocation. For the TIDIGITS connected digits recognition task, a 15.2% relative decrease in word error rate (WER) is possible with the proposed modified MI based Aurora encoder when compared to the recognition performance achieved using the standard Aurora encoder.

Multiframe motion compensated prediction can achieve high prediction gain with additional frame buffer memory requirement. For mobile-telephony applications which utilize mobile processor and relatively small memory space, reducing the memory requirement is very important. In this paper, we propose an efficient memory management control technique, which reduces memory requirement for storing reference frames at the decoder side. Our proposed technique is a frame-based memory management scheme which discards the reference frames that are least important in terms of prediction gain performance. The optimal solution for this problem requires checking all the rate performance degradation for all the combination of discarded reference frames and therefore we propose a greedy search that checks a subset of reference frame combinations.

The discrete cosine transform (DCT) is one of the major components in most of image and video compression systems. The variable complexity algorithm framework has been applied successfully to achieve complexity savings in the computation of the inverse DCT in decoders. These gains can be achieved due to the highly predictable sparseness of the quantized DCT coefficients in natural image/video data. With the increasing demand for instant video messaging and two-way video transmission over mobile communication systems running on general-purpose embedded processors, the encoding complexity needs to be optimized. In this paper, we focus on complexity reduction techniques for the forward DCT, which is one of the more computationally intensive tasks in the encoder. Unlike the inverse DCT, the forward DCT does not operate on sparse input data, but rather generates sparse output data. Thus, complexity reduction must be obtained using different methods from those used for the inverse DCT. In the literature, two major approaches have been applied to speed up the forward DCT computation, namely, frequency selection, in which only a subset of DCT coefficients is computed, and accuracy selection, in which all the DCT coefficients are computed with reduced accuracy. These two approaches can achieve significant computation savings with minor output quality degradation, as long as the coding parameters are such that the quantization error is larger than the error due to the approximate DCT computation. Thus, in order to be useful, these algorithms have to be combined using an efficient mechanism that can select the "right" level of approximation as a function of the characteristics of the input and the target rate, a selection that is often based on heuristic criteria. In this paper, we consider two previously proposed fast, variable complexity, forward DCT algorithms, one based on frequency selection, the other based on accuracy selection. We provide an explicit analysis of the additional distortion that each scheme introduces as a function of the quantization parameter and the variance of the input block. This analysis then allows us to improve the performance of these algorithms by making it possible to select the best approximation level for each block and a target quantization parameter. We also propose a hybrid algorithm that combines both forms of complexity reduction in order to achieve overall better performance over a broader range of operating rates. We show how our techniques lead to scalable implementations where complexity can be reduced if needed, at the cost of small reductions in video quality. Our hybrid algorithm can speed up the DCT and quantization process by close to a factor of 4 as compared to fixed-complexity forward DCT implementations, with only a slight quality degradation in PSNR.

In this paper, we propose a new rotation-invariant image retrieval system based on steerable pyramids and the concept of angular alignment across scales. First, we define energy-based texture features which are steerable under rotation, i.e., such that features corresponding to the rotated version of an image can be easily obtained from the features of the original (non-rotated) image. We also propose an approach to measure similarity between images that is robust to rotation; images are compared after being aligned in angle. The retrieval process is performed by means of a decision tree classifier where the angular alignment is performed at each node in the tree. To demonstrate the effectiveness of our system we consider a distributed image classification system, where the feature encoder and the classifier are physically apart and thus features are compressed before being transmitted. Our results of retrieval performance versus rate show a clear gain with respect to a wavelet transform (as an example, for the same rate, the retrieval precision is increased from 40% to 65%).

We propose a new algorithm for the real-time control of an inter-frame video coder operating with a variable rate channel such as wireless channels or the Internet. Using techniques of stochastic dynamic programming we obtain off-line optimal policies from stochastic models of the channel and coder which minimize the average expected distortion. The on-line complexity of our approach is only that required to identify the state of the system (source and channel). The state of the channel is obtained based on the ARQ error-control mechanism, and the source state is computed as complexity measurements on each incoming frame. Simulation results based on this new approach are provided and compared to other proposed rate-control strategies. They show how our model-based optimal policies outperform the other considered approaches keeping a negligible on-line computational cost. This result is very interesting when considering an alternative to traditional costly solutions based on deterministic dynamic programming.

In this paper, we propose an adaptive motion search window location algorithm which incorporates multiresolution motion estimation information and the motion vector information predicted from neighboring encoded blocks. To reduce the computational complexity, we employ the spatial and temporal search range reduction that we proposed in H. Chung, A. Ortega (2002). Our proposed fast search is implemented and tested in the emerging H.264 encoder reference software (JM5.0c). The proposed motion estimation algorithm is implemented in the low-complexity mode of motion estimation and mode decision (T. Wiegand (2002)). We compare the proposed algorithm with the full-search method which checks the distortion values of all the candidates in the given search area. With respect to the full-search method, our proposed algorithm has two advantages. First, due to the spatial and temporal search range reduction, our algorithm is faster. Second, due to the multiresolution search, our proposed algorithm can use larger motion search range with small additional complexity. The proposed algorithm can significantly reduce the computational complexity of motion estimation with slight increase in bit rate as compared to a full-search that covers the same motion range over which our proposed fast search operates. The proposed algorithm provides particularly significant gains for video sequences that contain large motions.

The vast majority of practical image coding systems used today are based on the transform coding paradigm, where image blocks are projected into a series of basis functions, and the expansion coefficients are subsequently quantized. In this paper we introduce a novel constrained vector quantizer (VQ), which we call seg-VQ. As an extension of the transform coding framework, in our approach codevectors are constrained to be located on a series of line segments in the multidimensional space. These segments are designed sequentially based on a training set. The advantages of seg-VQ are twofold: first, the encoding complexity is proportional to the number of segments rather than to the number of codevectors, and second, it can efficiently exploit the directional preferences (correlations) in sources such as images. For image sources, at low dimensions (e.g., 4 by 4 blocks), at the same encoding complexity with TSVQ, seg-VQ outperforms TSVQ by 0.5 dB at 0.4375 bpp achieving a performance close to unconstrained VQ obtained by pairwise nearest neighbor (PNN) initialized GLA. At higher dimensions (e.g., 8 by 8 blocks) we use multistage seg-VQ where the input block (as in transform coding) is projected into a series of segments in order to be quantized.

In this work we tackle the problem of error propagation that packet losses can cause in commonly used predictive video coding environments. Using unbalanced multiple description coding (UMDC) to generate redundant source data, we apply the consistency sequence estimation (CSE) algorithm for estimating the lost data. The CSE algorithm, proposed by Singh and Ortega for a 1-D input source signal in a DPCM context, uses a sequence search to verify the consistency of the estimates with the received data. The novelty of our work is the extension of the CSE algorithm to a block matching ME/MC video coder (such as H.263). To reach this aim we propose to work in the spatial domain. Among the advantages of the proposed error resilience scheme are its low-complexity and its compatibility with standard video coders.

In distributed classification applications, due to computational constraints, data acquired by low complexity clients is compressed and transmitted to a remote server for classification. In this paper the design of optimal quantization for distributed classification applications is considered and evaluated in the context of a speech recognition task. The proposed encoder minimizes the detrimental effect compression has on classification performance. Specifically, the proposed methods concentrate on designing low dimension encoders. Here individual encoders independently quantize sub-dimensions of a high dimension vector used for classification. The main novelty of the work is the introduction of mutual information as a metric for designing compression algorithms in classification applications. Given a rate constraint, the proposed algorithm minimizes the mutual information loss due to compression. Alternatively it ensures that the compressed data used for classification retains maximal information about the class labels. An iterative empirical algorithm (similar to the Lloyd algorithm) is provided to design quantizers for this new distortion measure. Additionally, mutual information is also used to propose a rate-allocation scheme where rates are allocated to the sub-dimensions of a vector (which are independently encoded) to satisfy a given rate constraint. The results obtained indicate that mutual information is a better metric (when compared to mean square error) for optimizing encoders used in distributed classification applications. In a distributed spoken names recognition task, the proposed mutual information based rate-allocation reduces by a factor of six the increase in WER due to compression when compared to a heuristic rate-allocation.

This paper presents a new framework for Peer-to-Peer Adaptive Layered Streaming, called PALS. PALS is a receiver-driven approach for quality adaptive playback of layer encoded streaming media from a group of congestion controlled sender peers to a single receiver peer. Since the effective throughput from each sender is variable and not known a priori, it is challenging to coordinate delivery among active senders. In PALS, the receiver orchestrates coordinated delivery among active senders by adaptively determining: 1) a subset of senders that maximize overall throughput, 2) overall quality (i.e. number of layers) that can be delivered from these senders as well as distribution of overall throughput among active layers, and most importantly 3) required packets to be delivered by each active sender in order to effectively cope with any sudden change in throughput from individual senders. We describe PALS framework, identify key components of the framework and their interesting design challenges, present sample solution for the key components, and present our preliminary results.

Sensor networks have emerged as a fundamentally new tool for monitoring inaccessible environments. They are distinguished from traditional sensors by strict limitations on system bandwidth and sensor energy resources. These constraints motivate the use of data compression at each sensor. Location finding is an important application of sensor networks, and estimation of the time delay between data from different sensors is a key step in localization. In this work, new quantizer designs specific to the time-delay estimation problem in sensor networks are presented. The goal for these new application-specific encoders is to achieve the best time delay estimate at a given bandwidth budget or latency bound, or minimize the rate required to reach an estimate with desired accuracy.

We study construction of structured regular quantizers for overcomplete expansions in /spl Ropf//sup N/. Our goal is to design structured quantizers which allow simple reconstruction algorithms with low complexity and which have good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that the same uniform scalar quantizer was used on all the expansion coefficients. Several approaches have been proposed to improve the reconstruction accuracy, with some of these methods having significant complexity. Instead, we consider the joint design of the overcomplete expansion and the scalar quantizers (allowing different step sizes) in such a way as to produce an equivalent vector quantizer (EVQ) with periodic structure. The construction of a periodic quantizer is based on lattices in /spl Ropf//sup N/ and the concept of geometrically scaled- similar sublattices. The periodicity makes it possible to achieve good accuracy using simple reconstruction algorithms (e.g., linear reconstruction or a small lookup table).

In optimal product vector quantization (VQ) sub-vectors within a vector are encoded separately. Optimal product VQ (PVQ) aims at maximizing the rate-distortion (RD) performance. We consider scenarios where PVQ is used to approximate the labeling obtained from an existing higher dimension quantizer or classifier. We present an efficient design technique under the labeling constraints and we show that performance is significantly improved if these are taken into account. We present two examples where this technique can be used. First we consider a PVQ designed to approximate a higher dimension classifier. In this case we show that with a small penalty in distortion (e.g., 0.04 dB loss) we can reduce significantly the misclassification (e.g., 48% relative reduction, 4.6% absolute reduction) with respect to a standard PVQ design. In our second example we show how hierarchical VQ (HVQ) can be used as a preprocessing stage for a standard unstructured VQ such that the HVQ stage enables a significant reduction of the codeword candidates to be searched in the VQ stage. Here again we show how HVQ designed to optimize the labeling enables a further reduction in complexity as the HVQ partition is designed to approximate the standard VQ partition.

We propose a new low complexity motion estimation (ME) algorithm using multiresolution motion search for long term memory motion compensation (LTMC). While multiresolution motion search has been used for standard single-frame motion compensation, here we introduce several novel techniques to exploit it efficiently in the context of LTMC. The proposed algorithm compute a coarse motion vector from a lower resolution sequence to locate motion search windows (MSW). Because the coarse motion vectors are good approximations to the actual vectors, small MSW whose sizes are chosen based on the error surface smoothness information can be used without significant loss in quality, leading to significant reduction in complexity. Our approach also incorporates temporal reduction of the motion search range to reduce the complexity further. The proposed algorithm provides particularly significant gains for video sequences which contain large motions, where directed search also results in promising gains in PSNR over non-directed search.

We introduce a novel rate-distortion (RD) model for images coded with a progressive wavelet coder, such as SPIHT (set partitioning in hierarchical trees) or JPEG2000, and especially designed to capture RD behavior when different parts of an image are refined at different speeds. Our model is an extension of Mallat's model (Mallat and Falzon 1998), which takes into account that the rates used are not necessarily the same throughout the image. Because of the different rates, certain modeling approximations (e.g., those for coarse quantization) can not be used uniformly throughout the image. Allocating different numbers of bits to different regions in an image is a problem that appears in applications such as region of interest (ROI) coding or multiple description coding (MDC), where the wavelet coefficients are divided by different factors before coding to enable different bit allocations to different regions. We show that the proposed RD model provides a more accurate estimate than Mallat's model.

In this paper, we consider the problem of rate control for video transmission over variable bit rate (VBR) channels. We focus on finding off-line optimal rate control for VBR transmission with a token bucket policing function. To ensure a maximum minimum quality is obtained over all data units, we introduce a minimum maximum distortion (MMAX) criterion in this channel-constrained problem. We show that, due to the channel constraints, a MMAX solution leads to a relatively low average distortion, because the total rate budget is not completely utilized. Therefore, after finding a MMAX solution, an additional minimization of average distortion (MMAX+) criterion is proposed to increase overall quality of the data sequence by using remaining resources. The proposed algorithms lead to an increase in average quality with respect to the MMAX solution, while providing a much more constant quality than MMSE solutions. Moreover we show how the MMAX+ approach can be implemented with low complexity.

Immersive environments provide an artificial world to surround users. These environments consist of a composition of various types of immersidata: unique data types that are combined to render a virtual experience. To construct such an environment, immersidata acquisition is indispensable for storage and future query. However, this is challenging because of the real time demands and sizeable amounts of data to be managed. We propose and evaluate alternative techniques for achieving efficient sampling and compression of one immersidata type, the haptic data, which describes the movement, rotation, and force associated with user-directed objects in an immersive environment. Our experiments identify the benefits and limitations of various techniques in terms of their data storage, bandwidth and accuracy.

Proxy caching has been used to speed up Web browsing and reduce networking costs. In this paper, we study the extension of proxy caching techniques to streaming video applications. A trivial extension consists of storing complete video sequences in the cache. However, this may not be applicable in situations where the video objects are very large and proxy cache space is limited. We show that the approaches proposed in this paper (referred to as selective caching), where only a few frames are cached, can also contribute to significant improvements in the overall performance. In particular, we discuss two network environments for streaming video, namely, quality-of-service (QoS) networks and best-effort networks (Internet). For QoS networks, the video caching goal is to reduce the network bandwidth costs; for best-effort networks, the goal is to increase the robustness of continuous playback against poor network conditions (such as congestion, delay, and loss). Two different selective caching algorithms (SCQ and SCB) are proposed, one for each network scenario, to increase the relevant overall performance metric in each case, while requiring only a fraction of the video stream to be cached. The main contribution of our work is to provide algorithms that are efficient even when the buffer memory available at the client is limited. These algorithms are also scalable so that when changes in the environment occur it is possible, with low complexity, to modify the allocation of cache space to different video sequences.

We introduce a new approach to deal with the transmission of real-time video over wireless channels, based on a priori stochastic models for both source and channel. This new problem formulation captures in a natural way the stochastic nature of the channel as well as the uncertainty regarding the properties of the video sequence. Our formulation leads to an optimal control problem that can be solved off-line, employing standard stochastic dynamic programming techniques. The outcome of this optimization is an off-line control policy that is optimal in the sense of minimizing the average coding distortion. The on-line computational cost of the new approach is thus very low: all that is required during run-time is to identify the state of the system (source and channel). Unlike other optimization-based rate control techniques, which require a search for the optimal operating point, the operating points here for each allowable state of the system have been precalculated. We consider wireless packet-based transmission with Automatic Repeat reQuest (ARQ) error control. While a standard model has been adopted to characterize the channel behavior, a new model based on the concept of coding complexity has been devised in order to characterize the video source. Simulation results based on this new approach are provided and compared to other proposed rate-control strategies. They show how the use of model-based optimal policies has negligible on-line computational cost while providing a transmission quality comparable to that achieved with more costly deterministic dynamic programming techniques, and significantly better than for simpler algorithms that do not explicitly take into account the channel state.

We study the construction of structured regular quantizers for overcomplete expansions in R/sup N/. Our goal is to design structured quantizers allowing simple reconstruction algorithms with low (memory and computational) complexity and having good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that uniform scalar quantization with the same stepsize was used on the redundant expansion and then has dealt with more complex methods to improve the reconstruction. Instead, we consider the design of scalar quantizers with different stepsizes for each coefficient of an overcomplete expansion in such a way as to produce an equivalent vector quantizer with periodic structure. The periodicity makes it possible to achieve good accuracy using simple reconstruction algorithms from the quantized coefficients of the overcomplete expansion.

Fano sequential decoders are variable complexity convolutional decoders, which have the desirable property of operating with very low computation at high SNR. In portable mobile communications, it is often desirable to trade BER with decoder complexity/power consumption. However, the variable complexity nature of the Fano algorithm means that buffers are required for the Fano decoder due to large variations in processing delays. In this paper, we formulate the buffer control problem as one that seeks to minimize the overall probability of block loss, subject to a finite buffer size constraint. The overall probability of block loss is comprised of two terms, corresponding to loss due to excessive bit errors and decoder buffer overflow, respectively. This leads to an interesting trade-off, as faster decoding often means higher bit error rate. Based on the joint distribution of decoding complexity and BER, at each decoding stage, we find an optimal Fano decoder parameter (/spl Delta/) to minimize block loss. In addition, we propose a simple real-time table lookup algorithm that implements the /spl Delta/ control policy. Simulation results demonstrate the superior performance of the proposed algorithm.

The use of quantized redundant expansions is useful in applications where the cost of having oversampling in the representation is much lower than the use of a high-resolution quantization (e.g., oversampled A/D). Most work to date has assumed that simple uniform quantization was used on the redundant expansion and then has dealt with methods to improve the reconstruction. Instead, we consider the design of quantizers for overcomplete expansions. Our goal is to design quantizers such that simple reconstruction algorithms (e.g., linear) provide as good reconstructions as with more complex algorithms. We achieve this goal by designing quantizers with different step sizes for each coefficient of the expansion in such a way as to produce a quantizer with periodic structure.

We combine recent theoretical and algorithmic advances in the area of information-hiding with the current mature knowledge-base in the human audio perception system to propose a novel audio data-hiding technique that significantly pushes the state-of-the-art in the field. Our work is based on a combination of advances in two disjoint fields: information-hiding and human auditory masking. The field of information-hiding has recently seen a resurgence due to advances in the understanding of fundamental bounds from information theory. By integrating this with the human perceptual system knowledge that has been successfully exploited for several years in the audio compression community, we derive a new and improved audio data-hiding technique that finds application in a number of exciting scenarios like music enhancement and digital communications over analog data channels. Our preliminary results show that we can embed data at a rate an order of magnitude higher than existing audio data hiding systems, while being robust to channel noise.

We study the transmission of real-time video over wireless channels, proposing a formulation of the problem that includes a priori stochastic models for both source and channel. Using techniques of stochastic dynamic programming, we obtain offline optimal policies for each system state that minimize the average expected frame distortion. The online complexity of our approach is only that required to identify the state of the system (source and channel). The state of the channel is obtained based on the ARQ error-control mechanism, and the source state is computed as a complexity measurement on each incoming frame. Simulation results based on this new approach are provided and compared to other proposed rate-control strategies. They show how our model-based optimal policies require negligible on-line computational cost while providing a transmission quality comparable to that achieved with more complex deterministic dynamic programming techniques, and better than for simpler algorithms such as TMN.

We propose a new approach for image compression in digital cameras, where the goal is to achieve better quality at a given rate by using the characteristics of a Bayer color filter array. Most digital cameras produce color images by using one CCD plate and each pixel in an image has only one color component, so an interpolation method is needed to produce a full color image. After finishing an image processing stage, in order to reduce the memory requirements of the camera, a lossless or lossy compression stage, using a coder such as JPEG, often follows. Before decreasing redundancy in a compression stage, redundancy is increased in an interpolation stage. We propose an algorithm for image compression, in which the order of the compression and interpolation stages is reversed to avoid increasing redundancy before compression. We introduce the image transform to compress uninterpolated images with JPEG. Our simulations show that the result of our algorithm is better than conventional methods for all compression ranges. This proposed algorithm provides not only better quality but also lower complexity because the number of luminance data of our method is only half of that of conventional methods.

Based on message-passing techniques, a novel iterative grid algorithm for the general two-dimensional (2D) digital least metric (DLM) problem is proposed and applied to image halftoning. The algorithm attempts to achieve a globally optimal solution via a local-metric computation and message passing as opposed to other 2D iterative global-metric optimizations such as simulated annealing and toggle/swap scheme. A reduced-complexity version of the proposed digital image halftoning technique is demonstrated. Results show that the quality of the halftone images is comparable to that of the state-of-the-art toggle/swap algorithm. Since the algorithm is not constrained by the specific metric used, the proposed method is directly applicable to other digital image processing tasks (eg, optimal near-lossless coding or entropy-constrained halftoning).

In this paper a novel loss recovery technique is proposed for multimedia communications over lossy packet networks. The proposed technique uses a combination of recent results on multiple description coding and erasure recovery codes in channel coding. The uniqueness of the proposed technique lies in its ability to recover not only the data carried in lost packets, but also the decoding state for successive packets. Experimental results on image and speech coding show that the proposed technique has excellent coding performance compared to some of the best results published and it can also significantly reduce the error propagation in successive packets due to packet losses. 1.

In software implementations of image processing algorithms, efficient cache utilization is one of the most important factors to accomplish high performance microprocessor computing. In this paper, we propose a cache efficient block-based wavelet decomposition procedure and provide an analysis for the 2D wavelet transform. The wavelet transform is the core algorithm for the JPEG2000 compression standard, which can achieve higher compression ratio than the original JPEG standard while not suffering from the block boundary artifacts that appear at low rates when a DCT based algorithm such as JPEG is used. On the other hand, wavelet transform is a memory consuming algorithm and it turns out that many cache misses occur in the microprocessor computation process. This paper introduces a theoretical analysis to predict the most cache effective block-size to be used, given the cache size and image sizes. The simulation results achieved with a microprocessor architecture simulator confirm the cache efficiency predictions obtained with our theoretical analysis.

We address the problem of allocating bits to the different regions in an image coded with a progressive wavelet coder such as SPIHT (Set Partitioning in Hierarchical Trees) [1]. This type of problem appears in applications such as Region of Interest (ROI) coding or Multiple Description Coding (MDC). The wavelet coefficients in both cases are divided by different factors before coding to enable different bit allocation to different regions, because the coefficients in each region are refined at different speeds. While this is a popular approach for ROI coding [2, 3], we propose using it for MDC as well. In this work, we introduce a priority scaling factor ( ) as a dividing factor. The main contribution of this work is to provide an analytical technique to determine what the should be, given criteria such as relative importance of the regions in ROI coding or degree of redundancy in an MDC. Our approach is based on an approximation to Mallat's model [4]. We show how our selection of is basically the same as that obtained by optimization of empirical data, with significantly less complexity. 1.

We propose a scalable recognition system for reducing recognition complexity. Scalable recognition can be combined with scalable compression in a distributed speech recognition (DSR) application to reduce both the computational load and the bandwidth requirement at the server. A low complexity preprocessor is used to eliminate the unlikely classes so that the complex recognizer can use the reduced subset of classes to recognize the unknown utterance. It is shown that by using our system it is fairly straightforward to trade-off reductions in complexity for performance degradation. Results of preliminary experiments using the TI-46 word digit database show that the proposed scalable approach can provide a 40 % speed up, while operating under 1.05 kbps, compared to the baseline recognition using uncompressed speech. 1.

We present an unbalanced MDC video system where two bitstreams are generated, both independently decodable and compliant with the standard H.263 video decoder, and study the performance of the system in providing robustness in transmission over a packet network.

In this paper, two new system architectures, overlap-state sequential and split-and-merge parallel, are proposed based on a novel boundary postprocessing technique for the computation of the discrete wavelet transform (DWT). The basic idea is to introduce multilevel partial computations for samples near data boundaries based on a finite state machine model of the DWT derived from the lifting scheme. The key observation is that these partially computed (lifted) results can also be stored back to their original locations and the transform can be continued anytime later as long as these partial computed results are preserved. It is shown that such an extension of the in-place calculation feature of the original lifting algorithm greatly helps to reduce the extra buffer and communication overheads, in sequential and parallel system implementations, respectively. Performance analysis and experimental results show that, for the Daubechies (see J.Fourier Anal. Appl., vol.4, no.3, p.247-69, 1998) (9,7) wavelet filters, using the proposed boundary postprocessing technique, the minimal required buffer size in the line-based sequential DWT algorithm is 40% less than the best available approach. In the parallel DWT algorithm we show 30% faster performance than existing approaches.

Motion search is by far the most complex operation to be performed in a video encoder. This paper proposes a novel fast matching algorithm to help speed up the computation of the matching (distance) metric used in the search, e.g., the sum of absolute difference (SAD). Based on a partial distance technique, our algorithm reduces complexity by terminating the SAD calculation early once it becomes clear that, given the partial SAD, it is likely that the total SAD will exceed that of the best candidate encountered so far in the search. The key idea is to introduce models to describe the probability distribution of the total distance given a measured partial distance. These models enable us to evaluate the risk involved in "trusting" a distance estimate obtained from a partial distance. By varying the amount of risk we are willing to take, we ran increase the speed, but we may also eliminate some good candidates too early, and thus increase the distortion of the decoded sequence. Because our approach requires knowledge of the statistical characteristics of the input, we also propose two approaches that allow these models to be obtained online. Our experimental results (based on an actual software implementation of an MPEG encoder) demonstrate that significant gains can be achieved with this approach. For example, reductions in the motion estimation computation time as compared with the original partial-distance search (where computation stops if the partial SAD is already larger than the SAD of the best candidate so far) can be as high as 45% for 2-D log search and 65% for exhaustive full search with a small penalty of 0.1-dB degradation in PSNR of the reconstructed sequences.

In applications where compression has to be performed under varying complexity constraints (e.g., with hardware having to operate in reduced power mode) it is beneficial to design compression algorithms that allow some degree of complexity scalability. In this paper we explore complexity scalability for transform coding algorithms. We show that a variable complexity algorithm (VCA), which uses energy thresholds to determine the number of coefficients to be computed for each input, is preferable to other alternatives such as a pruned transform, where the same number of coefficients is computed for the whole image. We show that the benefits include not only a higher degree of scalability, but also increased compression performance, as we take advantage of the energy classification that is needed for VCA operation and design quantizers that match each class. We provide expressions for the average complexity as well as rate/distortion relations for a generic N-point VCA transform. For a two point case, we present closed-form relations describing the variance changes in two classes. In addition, rate-distortion-complexity relations are also empirically obtained. We apply VCA to eight-point KLT and 8/spl times/8 DCT in the JPEG framework and experiments show that the VCA approach is superior in rate/distortion performance at low rates compared to the standard transform coding techniques.

We present a class of algorithms that use a partial distance metric to speedup the motion estimation process. The partial distance metric is used within the motion search to eliminate unlikely candidates through a thresholding process that enables computation scalability. We also propose a multiresolution variant which further reduces the complexity. Our results are comparable to state of the art approaches present a regular structure and are computationally scalable.

We study rate-complexity-distortion (R-C-D) tradeoffs for video coding, where we focus on the complexity of computing the inverse DCT. A quadtree coding approach is used and the quadtree is optimized based on the constraints of not only a rate budget but also decoding complexity budget. We employ a variable complexity algorithm (VCA) for the IDCT in order to obtain better complexity result. The main novelty of this work is to demonstrate that VCA approaches combined with R-C-D optimization can provide better results (e.g., lower rate at same distortion and complexity) than approaches proposed in the past, which relied on fixed blocksize and fixed complexity techniques.

We motivate the need for lookahead search in a context-based entropy coder. An efficient algorithm based on modeling of the context coder as a finite state machine is presented. A key contribution of this paper is the use of the per survivor processing (PSP) principle to enable a lookahead search in scenarios where adaptive entropy coding is used. Our results show that lookahead searches based on PSP result in performance improvements over traditional schemes.

We propose a modified overlapped block-matching (OBM) scheme for stereo image coding. OBM has been used in video coding but, to the best of our knowledge, it has not been applied to stereo image coding to date. In video coding, OBM has proven useful in reducing blocking artifacts (since multiple vectors can be used for each block), while also maintaining most of the advantages of fixed-size block matching. There are two main novelties in this work. First, we show that OBM techniques can be successfully applied to stereo image coding. Second, we take advantage of the smoothness properties typically found in disparity fields to further improve the performance of OBM in this particular application. Specifically, we note that practical OBM approaches use noniterative estimation techniques, which produce lower quality estimates than iterative methods. By introducing smoothness constraints into the noniterative DV computation, we improve the quality of the estimated disparity as compared to standard noniterative OBM approaches. In addition, we propose a disparity estimation/compensation approach using adaptive windows with variable shapes, which results in a reduction in complexity. We provide experimental results that show that our proposed hybrid OBM scheme achieves a PSNR gain (about 1.5-2 dB) as compared to a simple block-based scheme, with some slight PSNR gains (about 0.2-0.5 dB) in a reduced complexity, as compared to an approach based on standard OBM with half-pixel accuracy.

This paper addresses the problem of low memory wavelet image compression. While wavelet or subband coding of images has been shown to be superior to more traditional transform coding techniques, little attention has been paid until recently to the important issue of whether both the wavelet transforms and the subsequent coding can be implemented in low memory without significant loss in performance. We present a complete system to perform low memory wavelet image coding. Our approach is "line-based" in that the images are read line by line and only the minimum required number of lines is kept in memory. There are two main contributions of our work. First, we introduce a line-based approach for the implementation of the wavelet transform, which yields the same results as a "normal" implementation, but where, unlike prior work, we address memory issues arising from the need to synchronize encoder and decoder. Second, we propose a novel context-based encoder which requires no global information and stores only a local set of wavelet coefficients. This low memory coder achieves performance comparable to state of the art coders at a fraction of their memory utilization.

We consider the problem of searching for the best match for an input among a set of vectors, according to some predetermined metric. Examples of this problem include the search for the best match for an input in a VQ encoder and the search for a motion vector in motion estimation-based video coding. We propose an approach that computes a partial distance metric and uses prior probabilistic knowledge of the reliability of the estimate to decide on whether to stop the distance computation. This is achieved with a simple hypothesis testing and the result, an extension of the partial distance technique of Bei and Gray (1985) provides additional computation savings at the cost of a (controllable) loss in matching performance.

We propose a two-stage transform design technique for multiple description transform coding. The first stage is the structure design in which we enforce a scaling-rotation factorization of the transform and we further constrain the transform for specific channel conditions using the knowledge of the input correlation matrix and the desired output correlation matrix. In the second stage, magnitude design, we find the optimal transform from all admissible transforms given by the structure design using the numerical algorithm proposed by Goyal et al. (see Proc. of IEEE Data Compression Conference, 1998). Such a design enables a structured transform framework which reduces both the design and implementation complexities compared to an exhaustive search through the whole space of nonorthogonal transforms. We give two examples to illustrate the design idea, the scaling-Hadamard transform for equal rate channels and the scaling-DST transform for sequential protection channels.

As wavelet-based image coding is set to became more widely used (e.g. with the completion of the JPEG2000 standard), memory efficiency for wavelet-based coding is becoming an increasingly important issue. In this paper we present a complete system to perform low memory wavelet image coding. Our approach is "line-based" in that the images are read line by line and only the minimum required number of lines is kept in memory. The line-based transform is combined with a low memory entropy coder that does not require any global image information. Our system achieves a large (two orders of magnitude) reduction in memory requirements compared to other available coders, with limited performance loss (e.g., less than 0.5 dB).

In this paper, a boundary postprocessing technique is proposed to compute the discrete wavelet transform (DWT) near block boundaries. The basic idea is to take advantage of available lifting filterbank factorizations to model the DWT as a Finite State Machine (FSM). The proposed technique can reduce the size of auxiliary buffers in block-based DWT implementations and reduce the communication overhead between adjacent blocks. Two new DWT system architectures, Overlap-State sequential and Split-and-Merge parallel, are presented using this technique. Experimental results show that, for the popular (9, 7) filters, the size of auxiliary buffers can be reduced by 42% and that the parallel algorithm is 30% faster than existing approaches.

In this paper, we propose a novel hierarchical disparity estimation/compensation (DE/DC) algorithm for stereo image coding. One way to limit the well-known drawbacks of block matching (e.g., inaccurate disparity and blocking artifacts in the decoded image) is to resort to variable size block matching (VSBM). However, VSMB may result in an inconsistent disparity estimation (i.e., such that the estimated disparity field does not correspond to the true disparity) especially as the subblock becomes small, thus leading to high frequency energy at block boundaries in the residue image. To address these problems, in this paper we propose a hybrid quadtree-based DE/DC scheme, where a Markov Random Field (MRF) model is used in combination with VSBM and selective overlapped disparity compensation to improve the disparity field consistency and lead to higher coding efficiency. Our experimental results demonstrate that the proposed block segmentation scheme achieves a higher PSNR and a more consistent disparity field, as compared to conventional VSBM schemes.

Transform coding techniques are popular for their excellent lossy compression for natural images but fall short with "simple" images, i.e. images represented by a sparse subset of the available intensity values. In this paper we propose a novel image-domain compression technique aiming at simple images. The proposed method is a context-adaptive bitplane coder where each bitplane is encoded using a binary arithmetic coder. Our novel context modeling scheme allows to exploit the strong correlation across the bitplanes of simple images. Together with the scalable bitplane reduction technique proposed for increased compression efficiency, our bitplane coder produces an SNR-scalable embedded bitstream that is lossless when completely decoded.

We propose an algorithm for erasure recovery in predictive coding schemes, where erasures can cause catastrophic error propagation. The recovery algorithm is based on sending multiple descriptions of the source and using a deterministic distance measure to find the most likely estimate for the lost data, given the received data and the side information. Results show that we can recover from short burst erasures and that for long bursts (more than 10% of the samples are lost) we can recover to within 0.4 dB of the original DPCM performance.

We study the problem of rate control for transmission of video over burst-error wireless channels, i.e., channels such that errors tend to occur in clusters during fading periods. In particular we consider a scenario consisting of packet based transmission with automatic repeat request (ARQ) error control and a back channel. We start by showing how the delay constraints in real time video transmission can be translated into rate constraints at the encoder, where the applicable rate constraints at a given time depend on future channel rates. With the acknowledgments received through the back channel we have an estimate of the current channel state. This information, combined with an a priori model of the channel, allows us to statistically model the future channel rates. Thus the rate constraints at the encoder can be expressed in terms of the expected channel behavior. We can then formalize a rate distortion optimization problem, namely, that of assigning quantizers to each of the video blocks stored in the encoder buffer such that the quality of the received video is maximized. This requires that the rate constraints be included in the optimization, since violating a rate constraint is equivalent to violating a delay constraint and thus results in losing a video block. We formalize two possible approaches. The first one seeks to minimize the distortion for the expected rate constraints given the channel model and current observation. The second approach seeks to allocate bits so as to minimize the expected distortion for the given model. We use both dynamic programming and Lagrangian optimization approaches to solve these problems. Our simulation results demonstrate that both the video distortion at the decoder and packet loss rate can be significantly reduced when incorporating the channel information provided by the feedback channel and the a priori model into the rate control algorithm.

Research in coding of stereo images has focused mostly on the issue of disparity estimation to exploit the redundancy between the two images in a stereo pair, with less attention being devoted to the equally important problem of allocating bits between the two images. This bit allocation problem is complicated by the dependencies arising from using a prediction based on the quantized reference images. We address the problem of blockwise bit allocation for coding of stereo images and show how, given the special characteristics of the disparity field, one can achieve an optimal solution with reasonable complexity, whereas in similar problems in motion compensated video only approximate solutions are feasible. We present algorithms based on dynamic programming that provide the optimal blockwise bit allocation. Our experiments based on a modified JPEG coder show that the proposed scheme achieves higher mean peak signal-to-noise ratio over the two frames (0.2-0.5 dB improvements) as compared with blockwise independent quantization. We also propose a fast algorithm that provides most of the gain at a fraction of the complexity.

Adaptive compression methods have been a key component of many proposed subband (or wavelet) image coding techniques. This paper deals with a particular type of adaptive subband image coding where we focus on the image coder's ability to adjust itself "on the fly" to the spatially varying statistical nature of image contents. This backward adaptation is distinguished from more frequently used forward adaptation in that forward adaptation selects the best operating parameters from a predesigned set and thus uses considerable amount of side information in order for the encoder and the decoder to operate with the same parameters. Specifically, we present backward adaptive quantization using a new context-based classification technique which classifies each subband coefficient based on the surrounding quantized coefficients. We couple this classification with online parametric adaptation of the quantizer applied to each class. A simple uniform threshold quantizer is employed as the baseline quantizer for which adaptation is achieved. Our subband image coder based on the proposed adaptive classification quantization idea exhibits excellent rate-distortion performance, in particular at very low rates. For popular test images, it is comparable or superior to most of the state-of-the-art coders in the literature.

In this work we propose a novel algorithm for wavelet based image compression with very low memory requirements. The wavelet transform is performed progressively and we only require that a reduced number of lines from the original image be stored at any given time. The result of the wavelet transform is the same as if we were operating on the whole image, the only difference being that the coefficients of different subbands are generated in an interleaved fashion. We begin encoding the (interleaved) wavelet coefficients as soon as they become available. We classify each new coefficient in one of several classes, each corresponding to a different probability model, with the models being adapted on the fly for each image. Our scheme is fully backward adaptive and it relies only on coefficients that have already been transmitted. Our experiments demonstrate that our coder is still very competitive with respect to similar state-of-the-art coders. It is noted that schemes based on zero trees or bit plane encoding basically require the whole image to be transformed (or else have to be implemented using tiling). The features of the algorithm make it well suited for a low memory mode coding within the emerging JPEG2000 standard.

We propose a rate control algorithm based on Lagrangian optimization for video transmission over burst-error channels. In our rate control approach, the delay and channel capacity constraints in the video transmission are translated into rate constraints at the encoder. Given that a feedback channel is available, the rate control mechanism can dynamically adjust the video encoding rate to meet the changing rate constraints as the channel conditions vary. Lagrangian optimization is used to find the optimal bit-allocation for the input video frames under the rate constraints, with the objective of minimizing the overall distortion at the decoder. We show how the performance of the transmission system, as measured in terms of the received video quality or the data loss rate, can be improved when information about the channel state is available and the encoder has an a priori probabilistic model of the channel behavior.

A correspondence between the problem of two-dimensional digital least metric (DLM) fitting and data detection in serially concatenated systems in digital communication theory is described. Nearly optimal detection algorithms based on previous advances in iterative detection/decoding are applied to the DLM problem for two applications in digital image compression. The first application is least squares halftoning of digital images. The second is near-lossless (i.e., error constrained) minimum-entropy image compression. In both applications the use of the iterative algorithm yields significant improvements, measured in terms of residual metric, relative to previously suggested approaches to the DLM problem.

We address practical issues which arise in the implementation of optimized cache replenishment algorithms within a "soft" caching framework. We study the algorithms that have been proposed for optimized soft caching and simulate them using actual proxy traces. Our objective is to determine what compromises have to be made in order to approximate the desired optimal performance while maintaining a complexity level sufficiently low to enable a real-time implementation.

We propose an automatic repeat request (ARQ)/forward error correction (FEC) scheme for synchronous transmission of video over a binary symmetric constant rate channel. The approach consists of jointly allocating source and channel rates to video blocks from a given admissible set subject to the buffer or equivalently end-end delay constraints. The channel codes used are the popular class of powerful FEC codes known as rate-compatible punctured convolutional (RCPC) codes. The method used involves independent coding of the video units and optimization of the end-to-end expected delivered video quality. The existence of a return channel is assumed through which the decoder informs the encoder about the success/failure of the transmission. In the event of a failure, incremental parity information is sent to the decoder for correcting errors and a reallocation performed at the encoder. The simulations done point out the efficacy of the proposed scheme.

The authors examine the transport and storage of video compressed with a variable bit rate (VBR). They focus primarily on networked video, although they also briefly consider other applications of VBR video, including satellite transmission (channel sharing), playback of stored video, and wireless transport. Packet video research requires careful integration between the network and the video systems; however, a major stumbling block has resulted because commonly used terms are often interpreted differently by the video and networking communities. The paper then, has two main goals: (i) to clarify the definitions of terms that are often used with different meaning by networking and video-coding researchers and (ii) to explore the tradeoffs entailed by each of the various modalities of VBR transmission (unconstrained, shaped, constrained, and feedback). In particular, they evaluate the tradeoff among the advantages (better video quality, less delay, and more calls) that were identified by early proponents of VBR video transmission. An underlying theme of this paper is that increased interaction between the video and network design has potential for improving overall decoded video quality without changing the network capacity.

Digital video's increased popularity has been driven to a large extent by a flurry of international standards (MPEG-1, MPEG-2, H.263, etc). In most standards, the rate control scheme, which plays an important role in improving and stabilizing the decoding and playback quality, is not defined, and thus different strategies can be implemented in each encoder design. Several rate-distortion (R-D)-based techniques have been proposed aimed at the best possible quality for a given channel rate and buffer size. These approaches are complex because they require the R-D characteristics of the input data to be measured before making quantization assignment decisions. We show how the complexity of computing the R-D data can be reduced without significantly reducing the performance of the optimization procedure. We propose two methods which provide successive reductions in complexity by: (1) using models to interpolate the rate and distortion characteristics, and (2) using past frames instead of current ones to determine the models. Our first method is applicable to situations (e.g., broadcast video) where a long encoding delay is possible, while our second approach is more useful for computation-constrained interactive video applications. The first method can also be used to benchmark other approaches. Both methods can achieve over 1 dB peak signal-to-noise rate (PSNR) gain over simple methods like the MPEG Test Model 5 (TM5) rate control, with even greater gains during scene change transitions. In addition, both methods make few a priori assumptions and provide robustness in their performance over a range of video sources and encoding rates. In terms of complexity, our first algorithm roughly doubles the encoding time as compared to simpler techniques (such as TM5). However, the complexity is greatly reduced as compared to methods which exactly measure the R-D data. Our second algorithm has a complexity marginally higher than TM5 and a PSNR performance slightly lower than that of the first approach.

We present an adaptive image coding algorithm based on novel backward-adaptive quantization/classification techniques. We use a simple uniform scalar quantizer to quantize the image subbands. Our algorithm puts the coefficient into one of several classes depending on the values of neighboring previously quantized coefficients. These previously quantized coefficients form contexts which are used to characterize the subband data. To each context type corresponds a different probability model and thus each subband coefficient is compressed with an arithmetic coder having the appropriate model depending on that coefficient's neighborhood. We show how the context selection can be driven by rate-distortion criteria, by choosing the contexts in a way that the total distortion for a given bit rate is minimized. Moreover the probability models for each context are initialized/updated in a very efficient way so that practically no overhead information has to be sent to the decoder. Our results are comparable or in some cases better than the recent state of the art, with our algorithm being simpler than most of the published algorithms of comparable performance.

We present a general framework for variable complexity algorithms (VCA) and study the related issue of defining a minimum average complexity implementation. As an example we consider implementations of the inverse DCT (IDCT) which minimize the average computation time by taking advantage of the sparseness of the quantized input data. Since the decoding speed depends on the number of zeros in the input we then present a formulation that enables the encoder to optimize its quantizer selection so as to meet a prescribed "decoding time budget". This leads to a complexity-distortion optimization technique which is analogous to well known techniques for rate-distortion optimization. In our experiments we demonstrate significant reductions in decoding time.

In low rate motion-compensated video coding, the rate required to encode the motion field can become a significant portion of the overall rate budget. This motivates us to investigate methods to efficiently, and losslessly, encode the motion field. Reductions in the required motion field bit rate allow increasing the rate for the residue images or may permit a higher density motion field to be used. We consider adaptive context modeling techniques, such as those proposed in image coding applications, and explore their effectiveness for coding the motion data. We rely on various forward/backward context selection algorithms, and demonstrate how forward adaptation, based on alphabet partitioning approaches, can result in performance improvements over purely backward adaptive methods. We observe substantial reductions in rate, especially for dense motion fields, when comparing with popular differential coding schemes using VLC tables, such as those in the H.263 standard.

In digital video coding, the rate control scheme is essential to regulate the output data rate and maintain the output quality. The control scheme defined in MPEG Test Model 5 provides a solution with very light computational overhead, but the results are not guaranteed to be good for all video sources and channel rates without resorting to a manual "tweaking" of the control parameters, with many trial-and-error encoding tests. In this paper, we propose a rate-distortion based control scheme where we use pre-filtering and block classification to achieve higher quality at low rates. In particular, we show how to efficiently include the pre-filtering parameters as part of the rate control optimization process. Our coded sequences are compatible with standard MPEG decoders and our method is suitable for channel rates lower than those normally used for MPEG-1 sequences (around 1 Mbps), but which may be more appropriate for Internet applications. In addition, our algorithm is generic and can be readily be extended for H.263/MPEG-4 encoders. Our results show significant reductions of the blockiness usually encountered at low rates, when compared to schemes such as TM5.

Variable bit rate (VBR) transmission is widely regarded as the best solution for the transport of compressed image and video data, both in terms of network utilization and quality of data decoded at the receiver. However, significant problems remain unsolved to make this a viable approach. One of these problems is that of efficiently matching characteristics of the VBR source to those of the channel, in order to maximize end-to-end system performance. In this work, we propose a model for the channel based on which the source can make optimal decisions regarding bit allocation and rate control. This model consists of N queues, for each of which the source negotiates with the network statistical performance guarantees, consisting of allowable average transmission and packet loss rates. Based on such a channel description, the source determines how to allocate packets to each queue, to minimize the expected distortion of the images reconstructed at the receiver. A provably optimal algorithm for computing such bit allocations is the core of this work. Simulation results are presented.

This paper presents a novel approach to image caching for image databases, Web browsers, proxies and other similar applications. Current caches employ a hard strategy: either the image is stored in the cache, or it is not. In a soft cache, a variable amount of memory is assigned to each image. This is ideally matched to progressive image file formats. Our strategy for optimal soft caching considers the image download delay as a distortion measure. Then the minimization of the expected delay can be carried out in an operational rate-distortion framework. We present optimal theoretical solutions as well as simulation results.

The vast majority of current Internet traffic is generated by web browsing applications. Proxy caching, which allows some of the most popular web objects to be cached at intermediate nodes within the network, has been shown to provide substantial performance improvements. In this paper we argue that image-specific caching strategies are desirable and will result in improved performance over approaches treating all objects alike. We propose that Soft Caching, where an image can be cached at one of a set of levels of resolutions, can benefit the overall performance when combined with cache management strategies that estimate, for each object, both the bandwidth to the server where the object is stored and the appropriate resolution level demanded by the user. We formalize the cache management problem under these conditions and describe an experimental system to test these techniques.

Variable bit-rate (VBR) transmission of video over ATM networks has long been said to provide substantial benefits, both in terms of network utilization and video quality, when compared with conventional constant bit-rate (CBR) approaches. However, realistic VBR transmission environments will certainly impose constraints on the rate that each source can submit to the network. We formalize the problem of optimizing the quality of the transmitted video by jointly selecting the source rate (number of bits used for a given frame) and the channel rate (number of bits transmitted during a given frame interval). This selection is subject to two sets of constraints, namely, (1) the end-to-end delay has to be constant to allow for real-time video display and (2) the transmission rate has to be consistent with the traffic parameters negotiated by user and network. For a general class of constraints, including such popular ones as the leaky bucket, we introduce an algorithm to find the optimal solution to this problem. This algorithm allows us to compare VBR and CBR under the same end-to-end delay constraints. Our results indicate that variable-rate transmission can increase the quality of the decoded sequences without increases in the end-to-end delay. Finally, we show that for the leaky-bucket channel, the channel constraints can be combined with the buffer constraints, such that the system is identical to CBR transmission with an additional, infrequently imposed constraint. Therefore, video quality with a leaky-bucket channel can achieve the same quality of a CBR channel with larger physical buffers, without adding to the physical delay in the system.

In this paper, we introduce a novel technique for adaptive scalar quantization. Adaptivity is useful in applications, including image compression, where the statistics of the source are either not known a priori or will change over time. Our algorithm uses previously quantized samples to estimate the distribution of the source, and does not require that side information be sent in order to adapt to changing source statistics. Our quantization scheme is thus backward adaptive. We propose that an adaptive quantizer can be separated into two building blocks, namely, model estimation and quantizer design. The model estimation produces an estimate of the changing source probability density function, which is then used to redesign the quantizer using standard techniques. We introduce nonparametric estimation techniques that only assume smoothness of the input distribution. We discuss the various sources of error in our estimation and argue that, for a wide class of sources with a smooth probability density function (pdf), we provide a good approximation to a "universal" quantizer, with the approximation becoming better as the rate increases. We study the performance of our scheme and show how the loss due to adaptivity is minimal in typical scenarios. In particular, we provide examples and show how our technique can achieve signal-to-noise ratios within 0.05 dB of the optimal Lloyd-Max quantizer for a memoryless source, while achieving over 1.5 dB gain over a fixed quantizer for a bimodal source.

We present a new Lagrangian-based iterative technique for rate-distortion optimization under multiple rate constraints. We show how for sets of "linear" constraints this technique can be proven to be optimal up to a convex hull approximation. As an application we consider the problem of optimal buffer-constrained bit allocation. Our technique can be used to find an excellent approximation to the solutions achieved using dynamic programming. In cases where the buffer size is relatively large our approach shows a significant reduction in complexity as compared to dynamic programming.

A key part of any efficient source coder involves the optimal allocation of bit rate among a discrete set of competing quantization choices, as employed in the selected coding paradigm. This can be classified under the general label of budget-constrained discrete optimization, with coding applications including optimal bit allocation in scalar or vector quantizer based frameworks, entropy-constrained quantization frameworks, and codebook search for scalar-vector quantization (SVQ). For this class of problems dynamic programming (DP) methods (such as the Viterbi algorithm) provide the optimal solution. However DP is typically very costly computationally. An alternate technique to solving this class of problems uses Lagrange multipliers. This approach is much more efficient than DP but cannot guarantee optimality in general as it limits itself to convex-hull operating points, which may be sparse in many applications. We propose a novel hybrid technique that combines the speed of the Lagrangian approach with the versatility of the DP technique that is aimed at extracting the "best of both worlds". We present an application of our hybrid technique to the codebook search problem for SVQ, demonstrating significantly improved speed over the previously proposed DP-based search methods while mitigating the suboptimality of the Lagrangian based approach.

Subband image coding techniques owe much of their success to an effective use of adaptive quantization and adaptive entropy coding. It is often the case that adaptive quantization is achieved by defining a discrete set of quantizers from which one is chosen for a given set of coefficients. This type of forward adaptation thus requires that overhead information (the choice of quantizer) be sent to the decoder. Then, the quantized coefficients are transmitted using adaptive entropy coding, typically through backward adaptive arithmetic coding. We show that a combination of forward and backward adaptation methods can be used to update the quantizers thus reducing the overhead requirements while still providing good performance. Specifically, we present an algorithm where each coefficient is classified into several classes based on the past quantized data and where the quantizer to be used for each class can itself be adapted on the fly.

In this paper, we present a rate control algorithm for MPEG video. The goal is to minimize the distortion while keeping the change in distortion between consecutive frames small. We formulate this goal as a constrained optimization problem and find a solution using an iterative gradient search method. To reduce the computation cost, we propose a model based on spline curves to approximate the rate distortion functions which also takes into account the frame dependencies. Simulations on short video sequences show that, at the same bit rate and buffer constraint, our technique generates output sequences with smaller and more stable mean square error than other approaches, while maintaining strictly constant bit rate for every group of pictures, at the expense of higher computation cost.

Video transmission over wireless links is an emerging application which involves a time-varying channel. In this paper we propose that rate control algorithms should be used at the video encoders, along with models of the channel behavior, to improve the performance of such systems. Rather than letting information be lost as the channel conditions change, in our scheme channel state information is fed back to the encoder. We propose a method, based on dynamic programming, to compute the rate-distortion performance for a given channel and source realization. We show how the rate-distortion performance changes with end-to-end delay and feedback delay.

We propose to extend some of the ideas of adaptive lossless compression to design an adaptive quantization algorithm. Noting that the performance of an arithmetic coder is as good as its estimation of the statistics of the input, we split our quantizer into two building blocks: model estimation and quantizer design. The main idea is that, as long as the model estimation manages to track down the changes in source statistics, a standard quantizer design technique which assumes that the source follows the estimated model can be used. As an example of this type of design we study an adaptive scalar quantization scheme where we impose the restriction that no side information can be sent, i.e. encoder and decoder must perform their adaptation based on the quantized information.>

Studies the tradeoffs involved in choosing the bit allocation in a multiresolution remote image retrieval system. Such a system uses a multiresolution image coding scheme so that a user accessing the database will first see a coarse version of the images and will be able to accept or discard a given image faster, without needing to receive all the image data. The authors formalize the problem of choosing the bit allocation (e.g., in the two resolution case, how many bits should be given to the coarse image and the additional information, respectively?) so that the overall delay in the query is minimized. They provide analytical methods to find the optimal solution under different configurations and show how a good choice of the bit allocation results in a significant reduction of the overall delay in the query (by up to a factor of two in some cases).>

The authors formalize the description of the buffer-constrained adaptive quantization problem. For a given set of admissible quantizers used to code a discrete nonstationary signal sequence in a buffer-constrained environment, they formulate the optimal solution. They also develop slightly suboptimal but much faster approximations. These solutions are valid for any globally minimum distortion criterion, which is additive over the individual elements of the sequence. As a first step, they define the problem as one of constrained, discrete optimization and establish its equivalence to some of the problems studied in the field of integer programming. Forward dynamic programming using the Viterbi algorithm is shown to provide a way of computing the optimal solution. Then, they provide a heuristic algorithm based on Lagrangian optimization using an operational rate-distortion framework that, with computing complexity reduced by an order of magnitude, approaches the optimally achievable performance. The algorithms can serve as a benchmark for assessing the performance of buffer control strategies and are useful for applications such as multimedia workstation displays, video encoding for CD-ROMs, and buffered JPEG coding environments, where processing delay is not a concern but decoding buffer size has to be minimized.

We address the problem of efficient bit allocation in a dependent coding environment. While optimal bit allocation for independently coded signal blocks has been studied in the literature, we extend these techniques to the more general temporally and spatially dependent coding scenarios. Of particular interest are the topical MPEG video coder and multiresolution coders. Our approach uses an operational rate-distortion (R-D) framework for arbitrary quantizer sets. We show how a certain monotonicity property of the dependent R-D curves can be exploited in formulating fast ways to obtain optimal and near-optimal solutions. We illustrate the application of this property in specifying intelligent pruning conditions to eliminate suboptimal operating points for the MPEG allocation problem, for which we also point out fast nearly-optimal heuristics. Additionally, we formulate an efficient allocation strategy for multiresolution coders, using the spatial pyramid coder as an example. We then extend this analysis to a spatio-temporal 3-D pyramidal coding scheme. We tackle the compatibility problem of optimizing full-resolution quality while simultaneously catering to subresolution bit rate or quality constraints. We show how to obtain fast solutions that provide nearly optimal (typically within 0.3 dB) full resolution quality while providing much better performance for the subresolution layer (typically 2-3 dB better than the full-resolution optimal solution).

The use of multiresolution (MR) joint source-channel coding in the context of digital terrestrial broadcasting of high-definition television (HDTV) is shown to be an efficient alternative to single-resolution techniques, which suffer from a sharp threshold effect in the fringes of the broadcast area. It is shown how matched multiresolution source and channel coding can provide a stepwise graceful degradation and improve the behavior, in terms of coverage and robustness of the transmission scheme, over systems not specifically designed for broadcast situations. The alternative available for multiresolution transmission through embedded modulation and error correction codes are examined. It is also shown how multiresolution trellis-coded modulation (TCM) can be used to increase coverage range. Coding results and simulations of noisy transmission are presented, and tradeoffs are discussed.>