Generic deep learning (DL) networks for image restoration like denoising and interpolation lack mathematical interpretability, require voluminous training data to tune large parameter sets, and are fragile in the face of covariate shift. To address these shortcomings, we build interpretable networks by unrolling variants of a graph-based optimization algorithm of different complexities. Specifically, for a general linear image formation model, we first formulate a convex quadratic programming (QP) problem with a new $\ell _{2}$ -norm graph smoothness prior called gradient graph Laplacian regularizer (GGLR) that promotes piecewise planar (PWP) signal reconstruction. To solve the posed unconstrained QP problem, instead of computing a linear system solution straightforwardly, we introduce a variable number of auxiliary variables and correspondingly design a family of ADMM algorithms. We then unroll them into variable-complexity feedforward networks, amenable to parameter tuning via back-propagation. More complex unrolled networks require more labeled data to train more parameters, but have better overall performance. The unrolled networks have periodic insertions of a graph learning module, akin to a self-attention mechanism in a transformer architecture, to learn pairwise similarity structure inherent in data. Experimental results show that our unrolled networks perform competitively to generic DL networks in image restoration quality while using only a fraction of parameters, and demonstrate improved robustness to covariate shift.

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

Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph has no cycles of odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map simply to ones in a similarity-transformed positive graph Laplacian, thus enabling reuse of well-studied spectral filters designed for positive graphs. We propose a fast method to learn a balanced signed graph Laplacian directly from data. Specifically, for each node i, to determine its polarity βi∈{−1,1} and edge weights $\left\{ {{w_{i,j}}} \right\}_{j = 1}^N$, we extend a sparse inverse covariance formulation based on linear programming (LP) called CLIME, by adding linear constraints to enforce "consistent" signs of edge weights $\left\{ {{w_{i,j}}} \right\}_{j = 1}^N$ with the polarities of connected nodes—i.e., positive/negative edges connect nodes of same/opposing polarities. For each LP, we adopt projections on convex set (POCS) to determine a suitable CLIME parameter ρ > 0 that guarantees LP feasibility. We solve the resulting LP via an off-the-shelf LP solver. Experiments on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables the use of spectral filters and graph neural networks designed for positive graphs on balanced signed graphs.

Conventional model-based image denoising optimizations employ convex regularization terms, such as total variation (TV) that convexifies the ℓ0-norm to promote sparse signal representation. Instead, we propose a new non-convex total variation term in a graph setting (NC-GTV), such that when combined with an ℓ2-norm fidelity term for denoising, leads to a convex objective with no extraneous local minima. We define NC-GTV using a new graph variant of the Huber function, interpretable as a Moreau envelope. The crux is the selection of a parameter a characterizing the graph Huber function that ensures overall objective convexity; we efficiently compute a via an adaptation of Gershgorin Circle Theorem (GCT). To minimize the convex objective, we design a linear-time algorithm based on Alternating Direction Method of Multipliers (ADMM) and unroll it into a lightweight feed-forward network for data-driven parameter learning. Experiments show that our method outperforms unrolled GTV and other representative image denoising schemes, while employing far fewer network parameters.

A basic premise in graph signal processing (GSP) is that a graph encoding pairwise (anti-)correlations of the targeted signal as edge weights is leveraged for graph filtering. Existing fast graph sampling schemes are designed and tested only for positive graphs describing positive correlations. However, there are many real-world datasets exhibiting strong anti-correlations, and thus a suitable model is a signed graph, containing both positive and negative edge weights. In this paper, we propose the first linear-time method for sampling signed graphs, centered on the concept of balanced signed graphs. Specifically, given an empirical covariance data matrix , we first learn a sparse inverse matrix , interpreted as a graph Laplacian corresponding to a signed graph . We approximate with a balanced signed graph via fast edge weight augmentation in linear time, where the eigenpairs of Laplacian for are graph frequencies. Next, we select a node subset for sampling to minimize the error of the signal interpolated from samples in two steps. We first align all Gershgorin disc left-ends of Laplacian at the smallest eigenvalue via similarity transform , leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA). We then perform sampling on using a previous fast Gershgorin disc alignment sampling (GDAS) scheme. Experiments show that our signed graph sampling method outperformed fast sampling schemes designed for positive graphs on various datasets with anti-correlations.

Depth images captured by Time-of-Flight (ToF) sensors are subject to severe noise. Recent approaches based on deep neural networks achieve good depth denoising performance in synthetic data, but the application to real-world data is limited, due to the complexity of actual depth noise characteristics and the difficulty in acquiring ground truth. In this paper, we propose a novel ToF depth denoising network based on unrolled graph Laplacian regularization to “robustify” the network against both noise complexity and dataset deficiency. Unlike previous schemes that are ignorant of underlying ToF imaging mechanism, we formulate a fidelity term in the optimization problem to adapt to the depth probabilistic distribution with spatially-varying noise variance. Then, we add quadratic graph Laplacian regularization as the smoothness prior, leading to a maximum a posteriori problem that is optimized efficiently by solving a linear system of equations. We unroll the solution into iterative filters so that parameters used in the optimization and graph construction are amendable to data-driven tuning. Because the resulting network is built using domain knowledge of ToF imaging principle and graph prior, it is robust against overfitting to synthetic training data. Experimental results demonstrate that the proposal outperforms existing schemes in ToF depth denoising on synthetic FLAT dataset and generalizes well to real Kinectv2 dataset.

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.

We revisit the well-studied image segmentation problem from a soft labeling perspective: instead of estimating integer labels per pixel indicating a finite set of classes, each pixel is assigned a real number that conveys the level of uncertainty in the estimated class label. Soft labels are useful, for example, for subsequent human editing or composition. Specifically, given a set of pre-computed super-pixel labels and feature vectors per pixel, we formulate a convex optimization objective regularized by signal-dependent gradient graph Laplacian regularizers (GGLR), which promotes piecewise planar (PWP) signal reconstruction. Unlike a previous well-known soft segmentation scheme that requires expensive computation of the first 100 eigenvectors, our optimization can be solved efficiently in linear time via conjugate gradient (CG). Experimental results show that our method produces satisfactory soft labels per pixel for images in two public datasets at a reduced computation cost compared to the previous soft segmentation scheme.

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

A noise-corrupted image often requires interpolation. Given a linear denoiser and a linear interpolator, when should the operations be independently executed in separate steps, and when should they be combined and jointly optimized? We study joint denoising / interpolation of images from a mixed graph filtering perspective: we model denoising using an undirected graph, and interpolation using a directed graph. We first prove that, under mild conditions, a linear denoiser is a solution graph filter to a maximum a posteriori (MAP) problem using an undirected graph smoothness prior, while a linear interpolator is a solution to a MAP problem using a directed graph smoothness prior. Next, we study two variants of the joint interpolation / denoising problem: a graph-based denoiser followed by an interpolator has an optimal separable solution, while an interpolator followed by a denoiser has an optimal non-separable solution. Experiments show that our joint denoising / interpolation method outperformed separate approaches noticeably.

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

Spectral images periodically captured by satellites are often obscured by clouds. For crop monitoring, cloud removal—called “declouding”—in satellite images is important, so that crop growth at a field level can be estimated from restored images. In this paper, we adopt a graph signal processing (GSP) approach to satellite image declouding to capture neighboring pixel correlations that persist over time. We first assume an atmospherical scattering model (ASM) for image formation, where observation $\mathbf{y}$ is a product of piecewise constant (PWC) target image x and piecewise planar (PWP) transmission map t. To decompose y back into $\mathbf{x}$ and $\mathbf{t}$, we formulate respective quadratic programming (QP) problems, without / with box constraints, using — graph Laplacian regularizer (GLR) / gradient graph Laplacian regularizer (GGLR) as prior, to compute $\mathbf{x} / \mathbf{t}$ alternately. For efficient optimization, we compute $\mathbf{x}$ in an unconstrained QP via conjugate gradient (CG) without matrix inverse, while we compute t in a constrained QP via proximal gradient descent (PGD). We unroll iterations of our alternating algorithm into neural layers for end-to-end data-driven parameter optimization, resulting in an interpretable, algorithm-specific feed-forward network. Experimental results show that our unrolled network outperforms model-based and pure deeplearning schemes in declouded image quality, objectively and subjectively.

An image denoiser can be used for a wide range of restoration problems via the Plug-and-Play (PnP) architecture. In this paper, we propose a general framework to build an interpretable graph-based deep denoiser (GDD) by unrolling a solution to a maximum a posteriori (MAP) problem equipped with a graph Laplacian regularizer (GLR) as signal prior. Leveraging a recent theorem showing that any (pseudo-)linear denoiser $\boldsymbol{\Psi}$, under mild conditions, can be mapped to a solution of a MAP denoising problem regularized using GLR, we first initialize a graph Laplacian matrix $\mathbf{L}$ via truncated Taylor Series Expansion (TSE) of $\Psi^{-1}$. Then, we compute the MAP linear system solution by unrolling iterations of the conjugate gradient (CG) algorithm into a sequence of neural layers as a feed-forward network—one that is amenable to parameter tuning. The resulting GDD network is “graph-interpretable”, low in parameter count, and easy to initialize thanks to $\mathbf{L}$ derived from a known well-performing denoiser $\boldsymbol{\Psi}$. Experimental results show that GDD achieves competitive image denoising performance compared to competitors, but employing far fewer parameters, and is more robust to covariate shift.

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

Viral information like rumors or fake news is spread over a communication network like a virus infection in a unidirectional manner: entity$i$conveys information to a neighbor$j$, resulting in two equally informed (infected) parties. Existing graph diffusion processes focus only on bidirectional diffusion on an undirected graph. Instead, leveraging recent research in graph signal processing (GSP), we propose a new directed acyclic graph (DAG) diffusion process to estimate the probability$x_{i}(t)$of node$i$'s infection at time$t$given an initial infected source node$s$, where$x_{i}(\infty)=1$. Specifically, given an undirected positive graph modeling node-to-node communication, we first estimate its graph embedding: a latent coordinate for each graph node in an assumed low-dimensional manifold space via extreme eigenvectors computed using LOBPCG. Next, we construct a DAG based on Euclidean distances between latent coordinates. Spectrally, we prove that the asymmetric DAG Laplacian matrix contains real non-negative eigenvalues, and that the DAG diffusion converges to the all-infection vector$\mathbf{x}(\infty)=1$as$t\rightarrow\infty$. Simulations show that our DAG diffusion process accurately estimates the probabilities of node infection over a variety of graph structures at different time instants.

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

During the Covid-19 pandemic, like the vast majority of countries in the world, Canada was under government-mandated lockdown, creating unprecedented challenges for the higher education system. This has exacerbated the problem of gender and ethnic inequalities in the STEM field due to the sudden disappearance of in-person communication and communities that had supported minority groups. To provide emergency support and reduce the known gender / ethnic gap, at York University in Toronto we designed a 3D imaging project for Ontario’s high school (HS) students, as part of an annual summer outreach program in the Lassonde School of Engineering. The project aims to create an equitable opportunity for HS students, providing a comprehensive introduction to image processing through experiential learning. We document our design methodology and experiences in the project, as well as feedback and evaluations from participants at all levels. We believe such documentation is valuable to promote gender- and ethnic-balanced education in image processing and the broader STEM field in the future, in an increasingly unpredictable environment due to climate change.

Graph sampling is the problem of choosing a node subset via sampling matrix H ∈ {0, 1}K×Nto collect samples y = Hx ∈ℝK, KNcan be reconstructed in high fidelity. While sampling on undirected graphs is well studied, we propose the first eigen-decomposition-free sampling scheme tailored specifically for directed graphs, leveraging a previous undirected graph sampling method based on Gershgorin disc alignment (GDAS). Concretely, given a directed positive graph ${{\mathcal{G}}^d}$ specified by random-walk graph Laplacian matrix Lrw, we first define reconstruction of a smooth signal x∗from samples y using graph shift variation (GSV) $\left\| {{{\mathbf{L}}_{rw}}{\mathbf{x}}} \right\|_2^2$ as a signal prior. To minimize the worst-case reconstruction error of the linear system solution x∗= C−1H⊤y with symmetric coefficient matrix${\mathbf{C}} = {{\mathbf{H}}^ \top }{\mathbf{H}} + \mu {\mathbf{L}}_{rw}^ \top {{\mathbf{L}}_{rw}}$, the E-optimality sampling objective is to choose H to maximize the smallest eigenvalue λmin(C) of C. To circumvent eigen-decomposition, we maximize instead a lower bound $\lambda _{\min }^ - \left( {{\mathbf{SC}}{{\mathbf{S}}^{ - 1}}} \right)$ of λmin(C)—smallest Gershgorin disc left-end of a similarity transform of C—via a variant of GDAS based on Gershgorin circle theorem (GCT). Experimental results show that our sampling method yielded smaller signal reconstruction errors at a faster speed compared to competing schemes.

A graph convolutional network (GCN) employs a graph filtering kernel tailored for data with irregular structures. However, simply stacking more GCN layers does not improve performance; instead, the output converges to an uninformative low-dimensional subspace, where the convergence rate is characterized by the graph spectrum— this is the known over-smoothing problem in GCN. In this paper, we propose a sparse graph learning algorithm incorporating a new spectrum prior to compute a graph topology that circumvents over-smoothing while preserving pairwise correlations inherent in data. Specifically, based on a spectral analysis of multilayer GCN output, we derive a spectrum prior for the graph Laplacian matrix L to robustify the model expressiveness against over-smoothing. Then, we formulate a sparse graph learning problem with the spectrum prior, solved efficiently via block coordinate descent (BCD). Moreover, we optimize the weight parameter trading off the fidelity term with the spectrum prior, based on data smoothness on the original graph learned without spectrum manipulation. The output L is then normalized for supervised GCN training. Experiments show that our proposal produced deeper GCNs and higher prediction accuracy for regression and classification tasks compared to competing schemes.

Images captured in poorly lit conditions are often corrupted by acquisition noise. Leveraging recent advances in graph-based regularization, we propose a fast Retinex-based restoration scheme that denoises and contrast-enhances an image. Specifically, by Retinex theory we first assume that each image pixel is a multiplication of its reflectance and illumination components. We next assume that the reflectance and illumination components are piecewise constant (PWC) and continuous piecewise planar (PWP) signals, which can be recovered via graph Laplacian regularizer (GLR) and gradient graph Laplacian regularizer (GGLR) respectively. We formulate quadratic objectives regularized by GLR and GGLR, which are minimized alternately until convergence by solving linear systems—with improved condition numbers via proposed preconditioners—via conjugate gradient (CG) efficiently. Experimental results show that our algorithm achieves competitive visual image quality while reducing computation complexity noticeably.

In agronomics, predicting crop yield at a per field / county granularity is important for farmers to minimize uncertainty and plan seeding for the next crop cycle. While state-of-the-art prediction techniques employ graph convolutional nets (GCN) to predict future crop yields given relevant features and crop yields of previous years, a dense underlying graph kernel requires long training and execution time. In this paper, we propose a graph sparsification method based on the Fiedler number to remove edges from a complete graph kernel, in order to lower the complexity of GCN training / execution. Specifically, we first show that greedily removing an edge at a time that induces the minimal change in the second eigenvalue leads to a sparse graph with good GCN performance. We then propose a fast method to choose an edge for removal per iteration based on an eigenvalue perturbation theorem. Experiments show that our Fiedler-based method produces a sparse graph with good GCN performance compared to other graph sparsification schemes in crop yield prediction.

Point cloud (PC)—a collection of discrete geometric samples of a 3D object’s surface—is typically large, which entails expensive subsequent operations. Thus, PC sub-sampling is of practical importance. Previous model-based sub-sampling schemes are ad-hoc in design and do not preserve the overall shape sufficiently well, while previous data-driven schemes are trained for specific pre-determined input PC sizes and sub-sampling rates and thus do not generalize well. Leveraging advances in graph sampling, we propose a fast PC sub-sampling algorithm of linear time complexity that chooses a 3D point subset while minimizing a global reconstruction error. Specifically, to articulate a sampling objective, we first assume a super-resolution (SR) method based on feature graph Laplacian regularization (FGLR) that reconstructs the original high-res PC, given points chosen by a sampling matrix${\mathbf H}$. We prove that minimizing a worst-case SR reconstruction error is equivalent to maximizing the smallest eigenvalue$\lambda _{\min }$of matrix${\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}$, where${\boldsymbol{\mathcal{L}}}$is a symmetric, positive semi-definite matrix derived from a neighborhood graph connecting the 3D points. To arrive at a fast algorithm, instead of maximizing$\lambda _{\min }$, we maximize a lower bound$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}})$via selection of${\mathbf H}$—this translates to a graph sampling problem for a signed graph${\mathcal G}$with self-loops specified by graph Laplacian${\boldsymbol{\mathcal{L}}}$. We tackle this general graph sampling problem in three steps. First, we approximate${\mathcal G}$with a balanced graph${\mathcal G}_B$specified by Laplacian${\boldsymbol{\mathcal{L}}}_B$. Second, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we perform a similarity transform${\boldsymbol{\mathcal{L}}}_p~=~{\mathbf S}{\boldsymbol{\mathcal{L}}}_B {\mathbf S}^{-1}$, so that all Gershgorin disc left-ends of${\boldsymbol{\mathcal{L}}}_p$are aligned exactly at$\lambda _{\min }({\boldsymbol{\mathcal{L}}}_B)$. Finally, we choose samples on${\mathcal G}_B$using a previous graph sampling algorithm to maximize$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}_p)$in linear time. Experimental results show that 3D points chosen by our algorithm outperformed competing schemes both numerically and visually in reconstruction quality.

In graph signal processing (GSP), an appropriate underlying graph encodes pairwise (anti-)correlations of targeted discrete signals as edge weights. However, existing fast graph sampling schemes are designed and tested for positive graphs describing only positive correlations. In this paper, we show that for datasets with inherent strong anti-correlations, a suitable graph structure is instead a signed graph with both positive and negative edge weights, and in response, we propose a linear-time signed graph sampling method. Specifically, given an empirical covariance data matrix ${\mathbf{\bar C}}$, we first employ graphical lasso to learn a sparse inverse matrix $\mathcal{L}$, interpreted as a generalized graph Laplacian for signed graph $\mathcal{G}$. We then propose a fast signed graph sampling scheme containing three steps: i) augment $\mathcal{G}$ to a balanced graph ${\mathcal{G}_B}$, ii) align all Gershgorin disc left-ends of corresponding Laplacian ${\mathcal{L}_B}$ at smallest eigenvalue ${\lambda _{\min }}\left( {{\mathcal{L}_B}} \right)$ via similarity transform ${\mathcal{L}_p} = {\mathbf{S}}{\mathcal{L}_B}{{\mathbf{S}}^{ - 1}}$, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA), and iii) perform sampling on ${\mathcal{L}_p}$ using a previous fast Gershgorin disc alignment sampling scheme (GDAS). Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on two political voting datasets.

We study the problem of efficiently summarizing a short video into several keyframes, leveraging recent progress in fast graph sampling. Specifically, we first construct a similarity path graph (SPG) G, represented by graph Laplacian matrix L, where the similarities between adjacent frames are encoded as positive edge weights. We show that maximizing the smallest eigenvalue λmin(B) of a coefficient matrix B = diag(a) + µL, where a is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We prove that, after partitioning $\mathcal{G}$ into Q sub-graphs $\left\{ {{\mathcal{G}^q}} \right\}_{q = 1}^Q$, the smallest Gershgorin circle theorem (GCT) lower bound of Q corresponding coefficient matrices—${\min _q}\lambda _{\min }^ - \left( {{{\mathbf{B}}^q}} \right)$—is a lower bound for λmin(B). This inspires a fast graph sampling algorithm to iteratively partition $\mathcal{G}$ into Q sub-graphs using Q samples (keyframes), while maximizing $\lambda _{\min }^ - \left( {{{\mathbf{B}}^q}} \right)$ for each sub-graph ${\mathcal{G}^q}$. Experimental results show that our algorithm achieves comparable video summarization performance as state-of-the-art methods, at a substantially reduced complexity.

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.

A light field (LF) image is composed of multiple sub-aperture images (SAIs) from slightly offset viewpoints. To denoise a noise-corrupted LF image, leveraging recent development in deep algorithm unfolding, we pursue a hybrid graph-model-based / data-driven approach. Specifically, we first connect each pixel in a target patch of an SAI to neighboring pixels within the patch, and to pixels in co-located "similar" patches in adjacent SAIs. Given graph connectivity, we formulate a maximum a posteriori (MAP) problem using graph total variation (GTV) as signal prior. We then unroll the iterations of a corresponding optimization algorithm into a sequence of neural layers. In each unrolled layer, we learn relevant features per pixel from data using a convolutional neural net (CNN) in a supervised manner, so that edge weights can be computed as functions of feature distances. Each neural layer can be interpreted as a graph low-pass filter for a 4D LF image patch. Experiments show that our proposal outperformed two model-based and two deep-learning-based implementations in numerical and visual comparisons.

Given a convex and differentiable objective$Q({\mathbf M})$for a real symmetric matrix${\mathbf M}$in the positive definite (PD) cone—used to compute Mahalanobis distances—we propose a fast general metric learning framework that is entirely projection-free. We first assume that${\mathbf M}$resides in a space${\mathcal S}$of generalized graph Laplacian matrices corresponding to balanced signed graphs.${\mathbf M}\in {\mathcal S}$that is also PD is called a graph metric matrix. Unlike low-rank metric matrices common in the literature,${\mathcal S}$includes the important diagonal-only matrices as a special case. The key theorem to circumvent full eigen-decomposition and enable fast metric matrix optimization is Gershgorin disc perfect alignment (GDPA): given${\mathbf M}\in {\mathcal S}$and diagonal matrix${\mathbf S}$, where$S_{ii} = 1/v_i$and${\mathbf v}$is the first eigenvector of${\mathbf M}$, we prove that Gershgorin disc left-ends of similarity transform${\mathbf B}= {\mathbf S}{\mathbf M}{\mathbf S}^{-1}$are perfectly aligned at the smallest eigenvalue$\lambda _{\min }$. Using this theorem, we replace the PD cone constraint in the metric learning problem with tightest possible linear constraints per iteration, so that the alternating optimization of the diagonal / off-diagonal terms in${\mathbf M}$can be solved efficiently as linear programs via the Frank-Wolfe method. We update${\mathbf v}$using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as entries in${\mathbf M}$are optimized successively. Experiments show that our graph metric optimization is significantly faster than cone-projection schemes, and produces competitive binary classification performance.

Modern media data such as 360° videos and light field (LF) images are typically captured in much higher dimensions than the observers’ visual displays. To efficiently browse high-dimensional media, a navigational streaming model is considered: a client navigates the media space by dictating a navigation path to a server, who in response transmits the corresponding pre-encoded media data units (MDU) to the client one-by-one in sequence. Assuming that the MDU quality is pre-chosen and fixed, the problem resides in selecting and storing redundant representations of MDUs at the server in order to best trade off storage and transmission costs, while enabling adequate user’s random access. We address this problem with a landmark-based MDU optimization framework. The media space is divided into neighborhoods, each containing one landmark (a chosen MDU). MDUs in a neighborhood use the associated landmark as a predictor for inter-coding. Thus, for any MDU transition within the same neighborhood, only one inter-coded MDU transmission is required when the landmark resides in the decoder buffer. It results in lower transmission cost and enables navigational random access. To optimize an MDU structure, we employ tree-structured vector quantizer (TSVQ) to first optimize landmark locations, then iteratively add P-MDUs as refinements using a fast branch-and-bound technique. Taking interactive LF images and viewport adaptive 360° images as illustrative applications, and I-, P- and previously proposed merge frames to intra- and inter-code MDUs, we show experimentally that landmarked MDU structures can noticeably reduce the expected transmission cost compared with MDU structures without landmarks.

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).

Point cloud (PC) is a collection of discrete geometric samples of a physical object in 3D space. A PC video consists of temporal frames evenly spaced in time, each containing a static PC at one time instant. PCs in adjacent frames typically do not have point-to-point (P2P) correspondence, and thus exploiting temporal redundancy for PC restoration across frames is difficult. In this paper, we focus on the super-resolution (SR) problem for PC video: increase point density of PCs in video frames while preserving salient geometric features consistently across time. We accomplish this with two ideas. First, we establish partial P2P coupling between PCs of adjacent frames by interpolating interior points in a low-resolution PC patch in frame t and translating them to a corresponding patch in frame t+1 , via a motion model computed by iterative closest point (ICP). Second, we promote piecewise smoothness in 3D geometry in each patch using feature graph Laplacian regularizer (FGLR) in an easily computable quadratic form. The two ideas translate to an unconstrained quadratic programming (QP) problem with a system of linear equations as solution-one where we ensure the numerical stability by upper-bounding the condition number of the coefficient matrix. Finally, to improve the accuracy of the ICP motion model, we re-sample points in a super-resolved patch at time t to better match a low-resolution patch at time t+1 via bipartite graph matching after each SR iteration. Experimental results show temporally consistent super-resolved PC videos generated by our scheme, outperforming SR competitors that optimized on a per-frame basis, in two established PC metrics.

A 3D point cloud is typically constructed from depth measurements acquired by sensors at one or more viewpoints. The measurements suffer from both quantization and noise corruption. To improve quality, previous works denoise a point cloud a posteriori after projecting the imperfect depth data onto 3D space. Instead, we enhance depth measurements directly on the sensed images a priori, before synthesizing a 3D point cloud. By enhancing near the physical sensing process, we tailor our optimization to our depth formation model before subsequent processing steps that obscure measurement errors. Specifically, we model depth formation as a combined process of signal-dependent noise addition and non-uniform log-based quantization. The designed model is validated (with parameters fitted) using collected empirical data from a representative depth sensor. To enhance each pixel row in a depth image, we first encode intra-view similarities between available row pixels as edge weights via feature graph learning. We next establish inter-view similarities with another rectified depth image via viewpoint mapping and sparse linear interpolation. This leads to a maximum a posteriori (MAP) graph filtering objective that is convex and differentiable. We minimize the objective efficiently using accelerated gradient descent (AGD), where the optimal step size is approximated via Gershgorin circle theorem (GCT). Experiments show that our method significantly outperformed recent point cloud denoising schemes and state-of-the-art image denoising schemes in two established point cloud quality metrics.

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.

While deep learning (DL) architectures like convolutional neural networks (CNNs) have enabled effective solutions in image denoising, in general their implementations overly rely on training data, lack interpretability, and require tuning of a large parameter set. In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design—one that utilizes interpretable analytical low-pass graph filters and employs 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN. Specifically, to construct a suitable similarity graph for graph spectral filtering, we first adopt a CNN to learn feature representations per pixel, and then compute feature distances to establish edge weights. Given a constructed graph, we next formulate a convex optimization problem for denoising using a graph total variation (GTV) prior. Via a l1graph Laplacian reformulation, we interpret its solution in an iterative procedure as a graph low-pass filter and derive its frequency response. For fast filter implementation, we realize this response using a Lanczos approximation. Experimental results show that in the case of statistical mistmatch, our algorithm outperformed DnCNN by up to 3dB in PSNR.

Manifold landmarking is the problem of selecting a subset of discrete locations on a continuous manifold for label assignment, in order to reduce interpolation error of subsequent semi-supervised learning. In this paper, we select landmarks to minimize the condition number (λmax/λmin) of a submatrix of an alignment matrix Φ, which is equivalent to minimizing an interpolation error bound. Specifically, we design an efficient greedy scheme, where at each iteration t + 1 we choose one landmark i (thus deleting the corresponding row and column i of Φt) so that the resulting submatrix Φt+1has the smallest condition number. Towards fast landmark selection, at iteration t + 1, we first compute the two extreme eignevectors v1and vNcorresponding to λminand λmaxof Φtvia known methods like LOBPCG. We show that λmin(λmax) of submatrix Φt+1, from deleting the chosen row-column pair, can be approximated by an upper (lower) bound that is an easily computable function of eigen-pair {v1, λmin} ({vN, λmax}) of Φt. The error bounds of the obtained approximations can be numerically computed during the greedy step. Leveraging these proofs, we minimize a bound of the condition number for submatrix Φt+1at each greedy step t + 1. Experiments on synthetic and real-world manifold data demonstrate the superiority of our proposed landmarking algorithm compared to several state-of-the-art schemes.

In the graph signal processing (GSP) literature, it has been shown that signal-dependent graph Laplacian regularizer (GLR) can efficiently promote piecewise constant (PWC) signal reconstruction for various image restoration tasks. However, for planar image patches, like total variation (TV), GLR may suffer from the well-known “staircase” effect. To remedy this problem, we generalize GLR to gradient graph Laplacian regularizer (GGLR) that provably promotes piecewise planar (PWP) signal reconstruction for the image interpolation problem—a 2D grid with random missing pixels that requires completion. Specifically, we first construct two higher-order gradient graphs to connect local horizontal and vertical gradients. Each local gradient is estimated using structure tensor, which is robust using known pixels in a small neighborhood, mitigating the problem of larger noise variance when computing gradient of gradients. Moreover, unlike total generalized variation (TGV), GGLR retains the quadratic form of GLR, leading to an unconstrained quadratic programming (QP) problem per iteration that can be solved quickly using conjugate gradient (CG). We derive the means-square-error minimizing weight parameter for GGLR, trading off bias and variance of the signal estimate. Experiments show that GGLR outperformed competing schemes in interpolation quality for severely damaged images at a reduced complexity.

Ultra-high definition (UHD) 360 videos encoded in fine quality are typically too large to stream in its entirety over bandwidth (BW)-constrained networks. One popular approach is to interactively extract and send a spatial sub-region corresponding to a viewer's current field-of-view (FoV) in a head-mounted display (HMD) for more BW-efficient streaming. Due to the non-negligible round-trip-time (RTT) delay between server and client, accurate head movement prediction foretelling a viewer's future FoVs is essential. In this paper, we cast the head movement prediction task as a sparse directed graph learning problem: three sources of relevant information-collected viewers' head movement traces, a 360 image saliency map, and a biological human head model-are distilled into a view transition Markov model. Specifically, we formulate a constrained maximum a posteriori (MAP) problem with likelihood and prior terms defined using the three information sources. We solve the MAP problem alternately using a hybrid iterative reweighted least square (IRLS) and Frank-Wolfe (FW) optimization strategy. In each FW iteration, a linear program (LP) is solved, whose runtime is reduced thanks to warm start initialization. Having estimated a Markov model from data, we employ it to optimize a tile-based 360 video streaming system. Extensive experiments show that our head movement prediction scheme noticeably outperformed existing proposals, and our optimized tile-based streaming scheme outperformed competitors in rate-distortion performance.

3D point clouds acquired by low-cost sensors are often in lower spatial resolutions than desired for rendering images on high-resolution displays. In this paper, we propose a fast super-resolution (SR) algorithm for color 3D point clouds. We first populate a target low-res point cloud with added interior points. We refine the newly added 3D coordinates and their RGB values by minimizing a graph total variation (GTV) term of connected points' surface normals and RGB values respectively. Unlike non-local methods that require computation-intensive searches of similar patches in a large defined space, our algorithm is inherently local and performs smoothing of newly inserted points only with respect to neighboring points. Moreover, differing from our previous GTV-based SR algorithm that employs gradient descent procedures with sensitive step size parameters due to GTV's non-smooth l1-norm, we rewrite the l1objective into a linear proxy, so that together with constraints on surface normals / RGB values, it can be solved efficiently as a parameter-free linear program (LP). Experimental results show that our algorithm outperforms competing non-graph-based point cloud SR schemes, and is significantly faster than our previous graph-based SR method.

Conventional video coding schemes employ a hybrid motion prediction / residual transform coding paradigm, which only exploits redundancy in individual pairs of video frames for compression gain. However, rigid geometric structures in 3D space—e.g., a building in a scene’s background—persist across time in a large frame group. Thus if one can extract and encode the geometric structure, then redundancy across the entire frame group can be removed in one shot. In this paper, we extract a best-fitting "semi-regular" geometric structure from a target spatial region in a frame group, which is encoded separately as a unified signal predictor for these frames. By semi-regular, we mean its geometry is simple enough that its shape parameters can be encoded cheaply. This semi-regular structure kernel approximates the 3D shape of an object in the video, on which we project pixels from the frame group to a carefully spaced 2D grid overlaid on the kernel. We encode the projected pixels as an intra-frame using HEVC. The decoded pixels are then back-projected to each frame as the predictor, and the resulting prediction residuals are transform-coded. Experimental results show that employing a semi-regular geometric kernel—a folded 2D plane in our realization—improves coding performance over native HEVC implementation and our previous regular kernel based scheme.

While convolutional neural nets (CNNs) have achieved remarkable performance for a wide range of inverse imaging applications, the filter coefficients are computed in a purely data-driven manner and are not explainable. Inspired by an analytically derived CNN by Hadji et al., in this paper we construct a new layered graph neural net (GNN) using GraphBio as our graph filter. Unlike convolutional filters in previous GNNs, our employed GraphBio is analytically defined and requires no training, and we optimize the end-to-end system only via learning of appropriate graph topology at each layer. In signal filtering terms, it means that our linear graph filter at each layer is always intrepretable as low-pass with known biorthogonal conditions, while the graph spectrum itself is optimized via data training. As an example application, we show that our analytical GNN achieves image denoising performance comparable to a state-of-the-art CNN-based scheme when the training and testing data share the same statistics, and when they differ, our analytical GNN outperforms it by more than 1dB in PSNR.

We propose a general projection-free metric learning framework, where the minimization objective ${\min _{{\mathbf{M}} \in \mathcal{S}}}Q({\mathbf{M}})$ is a convex differentiable function of the metric matrix M, and M resides in the set S of generalized graph Laplacian matrices for connected graphs with positive edge weights and node degrees. Unlike low-rank metric matrices common in the literature, S includes the important positivediagonal-only matrices as a special case in the limit. The key idea for fast optimization is to rewrite the positive definite cone constraint in S as signal-adaptive linear constraints via Gershgorin disc alignment, so that the alternating optimization of the diagonal and offdiagonal terms in M can be solved efficiently as linear programs via Frank-Wolfe iterations. We prove that left-ends of the Gershgorin discs can be aligned perfectly using the first eigenvector v of M, which we update iteratively using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as diagonal / off-diagonal terms are optimized. Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.

High-definition 360 videos encoded in fine quality are typically too large in size to stream in its entirety over bandwidth (BW)-constrained networks. One popular remedy is to interactively extract and send a spatial sub-region corresponding to a viewer's current field-of-view (FoV) in a head-mounted display (HMD) for more BW-efficient streaming. Due to the non-negligible round-trip-time (RTT) delay between server and client, accurate head movement prediction that foretells a viewer's future FoVs is essential. Existing approaches are either overly simplistic in modelling and predict poorly when RTT is large, or are over-reliant on data-driven learning, resulting in inflexible models that are not robust to RTT heterogeneity. In this paper, we cast the head movement prediction task as a sparse directed graph learning problem, where three sources of relevant information-a 360 image saliency map, collected viewers' head movement traces, and a biological head rotation model-are aggregated into a unified Markov model. Specifically, we formulate a constrained optimization problem to minimize an l2-norm fidelity term and a sparsity term, corresponding to trace data / saliency consistency and a sparse graph model prior respectively. We solve the problem alternately using a hybrid iterative reweighted least square (IRLS) and Frank-Wolfe optimization strategy. Extensive experiments show that our head movement prediction scheme noticeably outperforms existing proposals across a wide range of RTTs.

Point cloud-a collection of geometric samples of a physical object in 3D space-can be very large in size, which entails a large computation cost for many imaging applications. In this paper, we reduce the size of a point cloud towards a more compact representation via optimal sub-sampling. Specifically, we first derive a sampling objective that maximizes the stability (maximizes the smallest eigenvalue λmin(B) of a coefficient matrix B = HTH + μL) of a linear system super-resolving a sub-sampled point cloud. To circumvent eigen-decomposition, we maximize instead a lower bound λmin-(B) using a fast graph sampling scheme called Gershgorin disc alignment (GDA) based on the well-known Gershgorin circle theorem. However, GDA requires that the disc left-ends of real matrix L are initially aligned at the same value, which is not the case for point clouds. Orthogonally, we recently derived a matrix theorem proving that disc left-ends of a generalized graph Laplacian matrix for a balanced and irreducible signed graph can be perfectly aligned via a similarity transform using the matrix's first eigenvector. Leveraging this work, we first interpret L as a generalized graph Laplacian matrix and balance the underlying graph. We then align disc left-ends of the resulting generalized graph Laplacian of the balanced graph using its first eigenvector, in order to employ GDA for point cloud sampling. Experiments show that our sampling method outperforms competing methods in super-resolved point cloud quality.

To compose a 360° image from a rig with multiple fisheye cameras, a conventional processing pipeline first performs demosaicking on each fisheye camera’s Bayer-patterned grid, then translates demosaicked pixels from the camera grid to a rectified image grid—thus performing two image interpolation steps in sequence. Hence interpolation errors can accumulate, and acquisition noise in the captured pixels can pollute neighbors in two consecutive processing stages. In this paper, we propose a joint processing framework that performs demosaicking and grid-to-grid mapping simultaneously—thus limiting noise pollution to one interpolation. Specifically, we first obtain a reverse mapping function from a regular on-grid location in the rectified image to an irregular off-grid location in the camera’s Bayer-patterned image. For each pair of adjacent pixels in the rectified grid, we estimate its gradient using the pair’s neighboring pixel gradients in three colors in the Bayer-patterned grid. We construct a similarity graph based on the estimated gradients, and interpolate pixels in the rectified grid directly via graph Laplacian regularization (GLR). Experiments show that our joint method outperforms several competing local methods that execute demosaicking and rectification in sequence, by up to 0.52 dB in PSNR and 0.086 in SSIM on the publicly available dataset, and by up to 5.53dB in PSNR and 0.411 in SSIM on the in-house constructed dataset.

A 3D point cloud is often synthesized from depth measurements collected by sensors at different viewpoints. The acquired measurements are typically both coarse in precision and corrupted by noise. To improve quality, previous works denoise a synthesized 3D point cloud a posteriori, after projecting the imperfect depth data onto the 3D space. Instead, we enhance depth measurements on the sensed images a priori, exploiting inherent 3D geometric correlation across views, before synthesizing a 3D point cloud from the improved measurements. By enhancing closer to the actual sensing process, we benefit from optimization targeting specifically the depth image formation model, before subsequent processing steps that can further obscure measurement errors. Mathematically, for each pixel row in a pair of rectified viewpoint depth images, we first construct a graph reflecting inter-pixel similarities via metric learning using data in previous enhanced rows. To optimize left and right viewpoint images simultaneously, we write a non-linear mapping function from left pixel row to the right based on 3D geometry relations. We formulate a MAP optimization problem, which, after suitable linear approximations, results in an unconstrained convex and differentiable objective, solvable using fast gradient method (FGM). Experimental results show that our method noticeably outperforms recent denoising algorithms that enhance after 3D point clouds are synthesized.

Point cloud is a collection of 3D coordinates that are discrete geometric samples of an object's 2D surfaces. Imperfection in the acquisition process means that point clouds are often corrupted with noise. Building on recent advances in graph signal processing, we design local algorithms for 3D point cloud denoising. Specifically, we design a signal-dependent feature graph Laplacian regularizer (SDFGLR) that assumes surface normals computed from point coordinates are piecewise smooth with respect to a signal-dependent graph Laplacian matrix. Using SDFGLR as a signal prior, we formulate an optimization problem with a general 'p-norm fidelity term that can explicitly remove only two types of additive noise: small but non-sparse noise like Gaussian (using '2 fidelity term) and large but sparser noise like Laplacian (using '1 fidelity term). To establish a linear relationship between normals and 3D point coordinates, we first perform bipartite graph approximation to divide the point cloud into two disjoint node sets (red and blue). We then optimize the red and blue nodes' coordinates alternately. For '2-norm fidelity term, we iteratively solve an unconstrained quadratic programming (QP) problem, efficiently computed using conjugate gradient with a bounded condition number to ensure numerical stability. For '1-norm fidelity term, we iteratively minimize an '1-'2 cost function using accelerated proximal gradient (APG), where a good step size is chosen via Lipschitz continuity analysis. Finally, we propose simple mean and median filters for flat patches of a given point cloud to estimate the noise variance given the noise type, which in turn is used to compute a weight parameter trading off the fidelity term and signal prior in the problem formulation. Extensive experiments show state-of-the-art denoising performance among local methods using our proposed algorithms.

3D point cloud-a new signal representation of volumetric objects-is a discrete collection of triples marking exterior object surface locations in 3D space. Conventional imperfect acquisition processes of 3D point cloud-e.g., stereo-matching from multiple viewpoint images or depth data acquired directly from active light sensors-imply non-negligible noise in the data. In this paper, we extend a previously proposed low-dimensional manifold model for the image patches to surface patches in the point cloud, and seek self-similar patches to denoise them simultaneously using the patch manifold prior. Due to discrete observations of the patches on the manifold, we approximate the manifold dimension computation defined in the continuous domain with a patch-based graph Laplacian regularizer, and propose a new discrete patch distance measure to quantify the similarity between two same-sized surface patches for graph construction that is robust to noise. We show that our graph Laplacian regularizer leads to speedy implementation and has desirable numerical stability properties given its natural graph spectral interpretation. Extensive simulation results show that our proposed denoising scheme outperforms state-of-the-art methods in objective metrics and better preserves visually salient structural features like edges.

Graph sampling with noise is a fundamental problem in graph signal processing (GSP). Previous works assume an unbiased least square (LS) signal reconstruction scheme and select samples greedily via expensive extreme eigenvector computation. A popular biased scheme using graph Laplacian regularization (GLR) solves a system of linear equations for its reconstruction. Assuming this GLR-based scheme, we propose a reconstruction-cognizant sampling strategy to maximize the numerical stability of the linear system-i.e., minimize the condition number of the coefficient matrix. Specifically, we maximize the eigenvalue lower bounds of the matrix, represented by left-ends of Gershgorin discs of the coefficient matrix. To accomplish this efficiently, we propose an iterative algorithm to traverse the graph nodes via Breadth First Search (BFS) and align the left-ends of all corresponding Gershgorin discs at lower-bound threshold T using two basic operations: disc shifting and scaling. We then perform binary search to maximize T given a sample budget K. Experiments on real graph data show that the proposed algorithm can effectively promote large eigenvalue lower bounds, and the reconstruction MSE is the same or smaller than existing sampling methods for different budget K at much lower complexity.

Graph sampling with independent noise towards minimum mean square error (MMSE) leads to the known A-optimality criterion, which is computation-intensive to evaluate and NP-hard to optimize. In this paper, we propose a new low-complexity sampling strategy based on Neumann series that circumvents large matrix inversion and eigen-decomposition. We first prove that a DC-shifted A-optimality criterion is equivalent to an objective computed using the inverse of a sub-matrix of an ideal graph low-pass (LP) filter. The LP filter matrix can be approximated efficiently via fast Graph Fourier Transform (FGFT). Using the shifted A-optimality objective as a proxy, we then propose a fast algorithm to greedily select samples one-by-one based on a matrix inversion lemma with simple matrix updates. We show that the obtained solution has a performance upper bound via super-modularity analysis. Simulation results show that our proposed sampling strategy has lower complexity and outperforms several existing deterministic sampling schemes.

With growing interest in data-driven classification, deep learning is now prevalent due to its ability to learn feature mapping functions solely from data. For very small training sets, however, deep learning, even with traditional regularization techniques, often overfits, resulting in sub-par classification performance. In this paper, we propose a novel binary classifier deep learning method, based on an iterative quadratic programming (QP) formulation with a graph Laplacian regularizer (GLR), combining the merits of model-based and data-driven approaches. Specifically, the proposed network employs a convolutional neural network (CNN) to learn deep features, which are used to define edge weights for a graph to pose a convex QP problem. Further, we design a novel loss function to penalize samples at the class boundary during semi-supervised learning. Results demonstrate that, given a small-size training dataset, our network outperforms several state-of-the-art classifiers, including CNN, model-based GLR and dynamic graph CNN classifiers.

Point cloud is a collection of 3D coordinates that are discrete geometric samples of an object's 2D surfaces. Using a low-cost 3D scanner to acquire data means that point clouds are often in lower resolution than desired for rendering on high-resolution displays. Building on recent advances in graph signal processing, we design a local algorithm for 3D point cloud super-resolution (SR). First, we initialize new points at centroids of local triangles formed using the low-resolution point cloud, and connect all points using a k-nearest-neighbor graph. Then, to establish a linear relationship between surface normals and 3D point coordinates, we perform bipartite graph approximation to divide all nodes into two disjoint sets, which are optimized alternately until convergence. For each node set, to promote piecewise smooth (PWS) 2D surfaces, we design a graph total variation (GTV) objective for nearby surface normals, under the constraint that coordinates of the original points are preserved. We pursue an augmented Lagrangian approach to tackle the optimization, and solve the unconstrained equivalent using the alternating method of multipliers (ADMM). Extensive experiments show that our proposed point cloud SR algorithm outperforms competing schemes objectively and subjectively for a large variety of point clouds.

Point cloud is a collection of 3D coordinates and associated color information, which are discrete samples of an object's 2D surfaces. Imperfection in the acquisition process means that point clouds are often corrupted with noise in both geometric and color spaces. Building on recent advances in graph signal processing, we design two algorithms for 3D point cloud color denoising. Specifically, we develop a smoothness notion for 3D color point clouds using graph Laplacian regularizer (GLR) or graph total variation (GTV) priors defined on the RGB space to promote piecewise smoothness (PWS) of RGB values. Using GLR or GTV as signal prior, we formulate the point cloud color denoising problem as a maximum a posteriori (MAP) estimation problem. For the GLR prior, the MAP formulation leads to an unconstrained quadratic programming (QP) problem, which can be efficiently computed using conjugate gradient (CG). For the GTV prior, the MAP formulation results in an ℓ1-ℓ2cost function; we minimize it using alternating direction method of multipliers (ADMM) and proximal gradient descent, where a good step size is chosen via Lipschitz continuity analysis. Extensive experiments show satisfactory denoising performance using our proposed algorithms.

Blind image deblurring, i.e., deblurring without knowledge of the blur kernel, is a highly ill-posed problem. The problem can be solved in two parts: i) estimate a blur kernel from the blurry image, and ii) given an estimated blur kernel, de-convolve the blurry input to restore the target image. In this paper, we propose a graph-based blind image deblurring algorithm by interpreting an image patch as a signal on a weighted graph. Specifically, we first argue that a skeleton image-a proxy that retains the strong gradients of the target but smooths out the details-can be used to accurately estimate the blur kernel and has a unique bi-modal edge weight distribution. Then, we design a reweighted graph total variation (RGTV) prior that can efficiently promote a bi-modal edge weight distribution given a blurry patch. Further, to analyze RGTV in the graph frequency domain, we introduce a new weight function to represent RGTV as a graph l1-Laplacian regularizer. This leads to a graph spectral filtering interpretation of the prior with desirable properties, including robustness to noise and blur, strong piecewise smooth (PWS) filtering and sharpness promotion. Minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. Leveraging the new graph spectral interpretation for RGTV, we design an efficient algorithm that solves for the skeleton image and the blur kernel alternately. Specifically for Gaussian blur, we propose a further speedup strategy for blind Gaussian deblurring using accelerated graph spectral filtering. Finally, with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results demonstrate that our algorithm successfully restores latent sharp images and outperforms state-of-the-art methods quantitatively and qualitatively.

Though generative adversarial networks (GANs) can hallucinate high-quality high-resolution (HR) faces from low-resolution (LR) faces, they cannot ensure identity preservation during face hallucination, making the HR faces difficult to recognize. To address this problem, we propose a Siamese GAN (SiGAN) to reconstruct HR faces that visually resemble their corresponding identities. On top of a Siamese network, the proposed SiGAN consists of a pair of two identical generators and one discriminator. We incorporate reconstruction error and identity label information in the loss function of SiGAN in a pairwise manner. By iteratively optimizing the loss functions of the generator pair and the discriminator of SiGAN, we not only achieve visually-pleasing face reconstruction but also ensure that the reconstructed information is useful for identity recognition. Experimental results demonstrate that SiGAN significantly outperforms existing face hallucination GANs in objective face verification performance while achieving promising visual-quality reconstruction. Moreover, for input LR faces with unseen identities that are not part of the training dataset, SiGAN can still achieve reasonable performance.

JPEG images captured in poor lighting conditions suffer from both low luminance contrast and coarse quantization artifacts due to lossy compression. Performing dequantization and contrast enhancement in separate back-to-back steps would amplify the residual compression artifacts, resulting in low visual quality. Leveraging on recent development in graph signal processing (GSP), we propose to jointly dequantize and contrast-enhance such images in a single graph-signal restoration framework. Specifically, we separate each observed pixel patch into illumination and reflectance via Retinex theory, where we define generalized smoothness prior and signed graph smoothness prior according to their respective unique signal characteristics. Given only a transform-coded image patch, we compute robust edge weights for each graph via low-pass filtering in the dual graph domain. We compute the illumination and reflectance components for each patch alternately, adopting accelerated proximal gradient (APG) algorithms in the transform domain, with backtracking line search for further speedup. Experimental results show that our generated images outperform the state-of-the-art schemes noticeably in the subjective quality evaluation.

Blind image deblurring, i.e., deblurring without knowledge of the blur kernel, is a highly ill-posed problem. The problem can be solved in two parts: i) estimate a blur kernel from the blurry image, and ii) given estimated blur kernel, de-convolve blurry input to restore the target image. In this paper, by interpreting an image patch as a signal on a weighted graph, we first argue that a skeleton image-a proxy that retains the strong gradients of the target but smooths out the details-can be used to accurately estimate the blur kernel and has a unique bi-modal edge weight distribution. We then design a reweighted graph total variation (RGTV) prior that can efficiently promote bi-modal edge weight distribution given a blurry patch. However, minimizing a blind image deblurring objective with RGTV results in a non-convex non-differentiable optimization problem. We propose a fast algorithm that solves for the skeleton image and the blur kernel alternately. Finally with the computed blur kernel, recent non-blind image deblurring algorithms can be applied to restore the target image. Experimental results show that our algorithm can robustly estimate the blur kernel with large kernel size, and the reconstructed sharp image is competitive against the state-of-the-art methods.

Light field data captured by a lenslet-based image sensor is typically demosaicked, aligned and rearranged into a series of sub-aperture (viewpoint) images, before a disparity-compensated coding scheme is employed for compression. In this paper, we focus on the problem of soft decoding of block-based compressed sub-aperture images at the decoder: given quantization bin indices of DCT coefficients of non-overlapping code blocks, we select appropriate coefficient values that are low-pass filtered using graph spectral filters and view-consistent across sub-aperture images via projection on convex sets (POCS). Specifically, after an initial pixel estimate, we low-pass filter each pixel block using accelerated graph filters based on the Lanczos method. We then map filtered pixels to a neighborhood of sub-aperture images based on estimated disparity to enforce indexed quantization bin constraints of multiple images. Experimental results show that our algorithm achieves PSNR gain of 2.34dB over JPEG hard decoding.

Reversible data hiding (RDH) is desirable in applications where both the hidden message and the cover image need to be recovered without loss. Among many RDH approaches is prediction-error expansion (PEE), containing two steps: i) prediction of a target pixel value, and ii) embedding according to the value of the prediction error. In general, higher prediction performance leads to larger embedding capacity and/or lower signal distortion. Leveraging on recent advances in graph signal processing (GSP), we pose pixel prediction as a graph-signal restoration problem, and design non-local graph-based prediction schemes where the appropriate edge weights of the underlying graph are computed using a similar patch searched in a semi-local neighborhood. Specifically, for each candidate patch, we first examine eigenvalues of its structure tensor to estimate its local smoothness. If sufficiently smooth, we pose a maximum a posteriori (MAP) problem using either a quadratic Laplacian regularizer or a graph total variation (GTV) term as signal prior. While the MAP problem using the first prior has a closed-form solution, we design an efficient algorithm for the second prior using alternating direction method of multipliers (ADMM) with nested proximal gradient descent. Finally, hidden message will be embedded into the image according to the resulting prediction errors. Experimental results show that with better quality GSP-based prediction, at low capacity the visual quality of the embedded image exceeds state-of-the-art methods noticeably.

New visual media types like light field images and point clouds are often irregularly sampled data in 2D or 3D space. While coding of irregularly sampled data has enjoyed recent progress due to the advent of graph-based coding tools like graph transforms and wavelets, the absence of efficiently coded side information (SI) limits the adaptivity and hence the coding efficiency of these tools. In this paper, we present a general methodology to code a path through a geometric planar graph-a generalization of a contour in a 2D image-to partition irregular samples in 2D / 3D space. The encoded partition boundary can subsequently be used to assign appropriate weights of edges connecting samples across the boundary for more efficient graph-based coding. Specifically, for the 2D case, we first construct a graph based on a Voronoi map computed from the irregularly sampled locations. We show that the Voronoi map boundaries represent the best local unbiased estimator of edge directions in the original continuous 2D signal. For the 3D case, we project a local window of 3D points onto a best-fitted plane, then construct a planar graph based on a Voronoi map as done in the 2D case. The local window is then shifted for the next iteration in the direction of the coded path. For a given constructed graph, knowing the maximum degree of each node, we design an alphabet to designate outgoing edges and assign a probability for each using linear regression of past path segment and Von Mises distribution with locally optimized parameters. Given assigned probabilities, arithmetic coding is used to encode a sequence of symbols in the alphabet into a bitstream. Experimental results show that our proposed method outperforms state-of-the-art contour coding on 2D grid, and uniform probability assignment in the 3D case.

Due to the large size of a light field image, compressing and transmitting the entire data to a client before rendering any image for observation would incur a significant startup delay. In response, in interactive light field streaming (ILFS) a server synthesizes and transmits a new viewpoint image as a combination of sub-aperture images (SAIs) per user request. However, in so doing the client relies entirely on the server for reconstruction of every requested image. In this paper, we extend a previous proposal of progressive light field data transmission strategy, where the client can incrementally learn SAIs over time. Specifically, requested focal-point images are synthesized using carefully chosen weighted linear combinations of SAIs, so that recovery of SAIs amounts to inversion of a lower-triangular weight matrix-a matrix structure that enables SAI recovery without amplifying quantization noise due to lossy image coding. We design an objective function to encourage specific combinations of SAIs to increase rank of the lower-triangular weight matrix for fast SAI recovery. This new proposal reduces the size of the initial user's cache and the total number of transmitted images compared to our previous work. Experimental results show that our scheme can outperform ILFS by up to 70% in terms of BD-rate.

How to use a deep convolutional neural network (CNN) to efficiently and effectively learn representations of a large unlabeled set of images and group them into clusters remains a challenging problem. To address this problem, we propose a Siamese clustering CNN (SC-CNN) to iteratively learn discriminative representations for image clustering. Based on the proposed SC-CNN, we employ a mini-batch-based joint pairwise representation learning and clustering scheme to make the computation and storage cost efficient for large-scale image clustering on a personal computer with a commercial GPU graphic card. On top of SC-CNN, the proposed pairwise learning scheme effectively learns discriminative representations by appropriately selecting same-cluster and different-cluster image pairs from the results of each clustering iteration. Experimental results demonstrate that the proposed method outperforms start-of-the-art clustering schemes in clustering accuracy on public image sets.

Conventional video coding approaches follow a hybrid motion prediction / residual transform coding paradigm, which limits the discovery of redundancy to individual pairs of video frames. On the other hand, computer vision techniques like structure-from-motion (SfM) have long exploited redundancy across a large group of frames to estimate a rigid 3D object structure. In this paper, leveraging on previous SfM techniques, we construct a rate-distortion (RD) optimized 3D planar model from a target spatial region in a frame group as a unified signal predictor for these frames. The prediction accuracy of the model is optimally traded off with the cost of coding such representation as side information (SI). Specifically, we approximate a roughly flat spatial region in the video as a 2D plane in 3D space, and project pixels from the frame group to a 2D grid on the plane with appropriate density. The boundary of the irregularly shaped pixel body on the plane is first coded using arithmetic edge coding (AEC), and then the body is encapsulated into a tight-fitting rectangular region, which is encoded as an intra-frame using HEVC. The pixels inside the rectangle but outside the pixel body-called don't care region (DCR)-are filled optimally by minimizing an l1-norm of the transform coefficients using linear programming. Experimental results show that the RD-optimized planar model improves coding performance over native HEVC implementation.

Image stitching-composition of different viewpoint images to form a 360-degree panoramic image-is an essential component towards immersive applications like VR and AR. A no-reference (NR) quality metric specifically designed to evaluate stitched panoramic images is highly desirable when ground-truth reference images are not available. In this paper, we use Convolutional Sparse Coding (CSC) with a set of convolutional filters to locate stitching-specific distortions in a target image, and design trained kernels to quantify the compound effects of multiple distortion types in a local region. Specifically, our contributions are: i) a training database labeled with location information of the distortion regions is released; ii) a NR metric is proposed to accurately assess stitching-specific artifacts like ghosting using convolutional sparse coding; and iii) a novel sequential feature selection algorithm is proposed to quantify the aforementioned compound distortion effects. In extensive experiments, we show that the performance of our proposed NR metric is comparable to the state-of-the-art full-reference metrics designed for stitched images.

Acquired 3D point cloud data, whether from active sensors directly or from stereo-matching algorithms indirectly, typically contain non-negligible noise. To address the point cloud denoising problem, we propose a local graph-based algorithm. Specifically, given a $k$ -nearest-neighbor graph of the 3D points, we first approximate it with a bipartite graph (independent sets of red and blue nodes) using a KL divergence criterion. For each partite of nodes (say red), we first define surface normal of each red node using 3D coordinates of neighboring blue nodes, so that red node normals n can be written as a linear function of red node coordinates p. We then formulate a convex optimization problem, with a quadratic fidelity term $\Vert \mathbf{p}-\mathbf{q}\Vert_{2}^{2}$ given noisy observed red coordinates q and a graph total variation (GTV) regularization term for surface normals of neighboring red nodes. We minimize the resulting $l_{2}-l_{1}$-norm using alternating direction method of multipliers (ADMM) and proximal gradient descent. The two partites of nodes are alternately optimized until convergence. Experimental results show that compared to state-of-the-art schemes with similar complexity, our proposed algorithm achieves the best overall denoising performance objectively and subjectively.

Light field cameras capture the emanated light from a scene. This type of images allows for changing point of views or focal points by processing the captured information. Recently, a Progressive Light Field Communication (PLFC) was proposed. PLFC addresses an interactive Light Field (LF) streaming framework, where a client requests a certain view or focal point and a server synthesizes and transmits each requested image as a linear combination of Sub-Aperture Images (SAI). The main idea of PLFC is that as the virtual views are transmitted, the client gradually learns information about the LF, so eventually the client may posses enough information to locally create the virtual view at the required quality, avoiding the transmission of a new image. In order to PLFC work, an optimization algorithm which selects the SAIs that are used to create a certain virtual view is requested. Here, we improve over the previous PLFC proposal by presenting a method that focuses on a refinement algorithm for SAI selection, using dynamic Quantization Parameter (QP) during encoding, using an automatic method to determine the Lagrangian multiplier during optimization and modifying how the initial required cache is created. These proposed changes in the algorithm produce significant gains. The results shows gains up to 85.8% on BD-rate compared to trivial LF transmissions, whereas they're up to 32.8% compared to previous PLFC.

Recent advent of graph signal processing (GSP) has spurred intensive studies of signals that live naturally on irregular data kernels described by graphs (e.g., social networks, wireless sensor networks). Though a digital image contains pixels that reside on a regularly sampled 2-D grid, if one can design an appropriate underlying graph connecting pixels with weights that reflect the image structure, then one can interpret the image (or image patch) as a signal on a graph, and apply GSP tools for processing and analysis of the signal in graph spectral domain. In this paper, we overview recent graph spectral techniques in GSP specifically for image/video processing. The topics covered include image compression, image restoration, image filtering, and image segmentation.

In this letter, we introduce several algorithms for geometry inpainting of three-dimensional (3-D) point clouds with large holes. The algorithms are exemplar based. Hole filling is performed iteratively using templates near the hole boundary to find the best matching regions elsewhere in the cloud, from where existing points are transferred to the hole. We propose two improvements over the previous work on exemplar-based hole filling. The first one is adaptive template size selection in each iteration, which simultaneously leads to higher accuracy and lower execution time. The second improvement is a nonrigid transformation to better align the candidate set of points with the template before the point transfer, which leads to even higher accuracy. We demonstrate the algorithm's ability to fill holes that are difficult or impossible to fill by existing methods.

Graph signal processing (GSP) studies signals that live on irregular data kernels described by graphs. One fundamental problem in GSP is sampling-from which subset of graph nodes to collect samples in order to reconstruct a bandlimited graph signal in high fidelity. In this letter, we seek a sampling strategy that minimizes the mean square error (MSE) of the reconstructed bandlimited graph signals assuming an independent and identically distributed noise model-leading naturally to the A-optimal design criterion. To avoid matrix inversion, we first prove that the inverse of the information matrix in the A-optimal criterion is equivalent to a Neumann matrix series. We then transform the truncated Neumann series-based sampling problem into an equivalent expression that replaces eigenvectors of the Laplacian operator with a submatrix of an ideal low-pass graph filter. Finally, we approximate the ideal filter using a Chebyshev matrix polynomial. We design a greedy algorithm to iteratively minimize the simplified objective. For signal reconstruction, we propose an accompanied signal reconstruction strategy that reuses the approximated filter submatrix and is provably more robust than conventional least square recovery. Simulation results show that our sampling strategy outperforms two previous strategies in MSE performance at comparable complexity.

A depth image provides partial geometric information of a 3D scene, namely the shapes of physical objects as observed from a particular viewpoint. This information is important when synthesizing images of different virtual camera viewpoints via depth-image-based rendering (DIBR). It has been shown that depth images can be efficiently coded using contour-adaptive codecs that preserve edge sharpness, resulting in visually pleasing DIBR-synthesized images. However, contours are typically losslessly coded as side information, which is expensive if the object shapes are complex. In this paper, we pursue a new paradigm in depth image coding for color-plus-depth representation of a 3D scene: in a pre-processing step, we pro-actively simplify object shapes in a depth and color image pair to reduce depth coding cost, at a penalty of a slight increase in synthesized view distortion. Specifically, we first mathematically derive a distortion upper-bound proxy for 3DSwIM—a quality metric tailored for DIBR-synthesized images. This proxy reduces inter-dependency among pixel rows in a block to ease optimization. We then approximate object contours via a dynamic programming algorithm to optimally tradeoff coding the cost of contours using arithmetic edge coding with our proposed view synthesis distortion proxy. We modify the depth and color images according to the approximated object contours in an inter-view consistent manner. These are then coded, respectively, using a contour-adaptive image codec based on graph Fourier transform for edge preservation and High Efficiency Video Coding (HEVC) intra. Experimental results show that by maintaining sharp but simplified object contours during contour-adaptive coding, for the same visual quality of DIBR-synthesized virtual views, our proposal can reduce depth image coding rate by up to 22% in 3DSwIM and 42% in peak signal-to-noise ratio compared with alternative coding strategies, such as HEVC intra.

Millions of user-generated images are uploaded to social media sites like Facebook daily, which translate to a large storage cost. However, there exists an asymmetry in upload and download data: only a fraction of the uploaded images are subsequently retrieved for viewing. In this paper, we propose a cloud storage system that reduces the storage cost of all uploaded JPEG photos, at the expense of a controlled increase in computation mainly during download of requested image subset. Specifically, the system first selectively re-encodes code blocks of uploaded JPEG images using coarser quantization parameters for smaller storage sizes. Then during download, the system exploits known signal priors-sparsity prior and graph-signal smoothness prior-for reverse mapping to recover original fine quantization bin indices, with either deterministic guarantee (lossless mode) or statistical guarantee (near-lossless mode). For fast reverse mapping, we use small dictionaries and sparse graphs that are tailored for specific clusters of similar blocks, which are classified via tree-structured vector quantizer. During image upload, cluster indices identifying the appropriate dictionaries and graphs for the re-quantized blocks are encoded as side information using a differential distributed source coding scheme to facilitate reverse mapping during image download. Experimental results show that our system can reap significant storage savings (up to 12.05%) at roughly the same image PSNR (within 0.18 dB).

The advent of depth sensing technologies means that the extraction of object contours in images-a common and important pre-processing step for later higher level computer vision tasks like object detection and human action recognition-has become easier. However, captured depth images contain acquisition noise and the detected contours suffer from errors as a result. In this paper, we propose to jointly denoise and compress detected contours in an image for bandwidth-constrained transmission to a client, who can then carry out aforementioned application-specific tasks using the decoded contours as input. First, we prove theoretically that in general a joint denoising/compression approach can outperform a separate two-stage approach that first denoises then encodes contours lossily. Adopting a joint approach, we propose a burst error model that models typical errors encountered in an observed string of directional edges. We then formulate a rate-constrained maximum a posteriori problem that trades off the posterior probability of an estimated string given with its code rate. We design a dynamic programming algorithm that solves the posed problem optimally, and propose a compact context representation called total suffix tree that can reduce complexity of the algorithm dramatically. To the best of our knowledge, we are the first in the literature to study the problem of joint denoising/compression of image contours and offer a computation-efficient optimization algorithm. Experimental results show that our joint denoising/compression scheme can reduce bitrate by up to 18% compared with a competing separate scheme at comparable visual quality.

The design of energy- and spectrally efficient Wireless Sensor Networks (WSN) is crucial to support the upcoming expansion of Internet-of-Things (IoT) mobile data traffic. In this work, we consider an energy harvesting WSN where sensor data are periodically reported to a Fusion Center (FC) by a sparse set of active sensors. Unlike most existing works, the transmit power levels of each sensor are assumed to be unknown at the FC in this distributed setting. We address the inverse problem of joint signal / power restoration at the FC-a challenging under-determined separation problem. To regularize the ill-posed problem, we assume both a graph-signal smoothness prior (signal is smooth with respect to a graph modeling spatial correlations among sensors) and a sparsity power prior for the two unknown variables. We design an efficient algorithm by alternately fixing one variable and solving for the other until convergence. Specifically, when the signal is fixed, we solve for the power vector using Simplex pivoting in linear programming (LP) to iteratively identify sparse feasible solutions, locally minimizing an objective. Simulation results show that our proposal can achieve very low reconstruction errors and outperform conventional schemes.

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.

Virtual reality (VR) video provides an immersive 360 viewing experience to a user wearing a head-mounted display: as the user rotates his head, correspondingly different fields-of-view (FoV) of the 360 video are rendered for observation. Transmitting the entire 360 video in high quality over bandwidth-constrained networks from server to client for real-time playback is challenging. In this paper we propose a multi-stream switching framework for VR video streaming: the server preencodes a set of VR video streams covering different view ranges that account for server-client round trip time (RTT) delay, and during streaming the server transmits and switches streams according to a user's detected head rotation angle. For a given RTT, we formulate an optimization to seek multiple VR streams of different view ranges and the head-angle-to-stream mapping function simultaneously, in order to minimize the expected distortion subject to bandwidth and storage constraints. We propose an alternating algorithm that, at each iteration, computes the optimal streams while keeping the mapping function fixed and vice versa. Experiments show that for the same bandwidth, our multi-stream switching scheme outperforms a non-switching single-stream approach by up to 2.9dB in PSNR.

Light field (LF) imaging captures multiple intensities and directions of light per pixel during acquisition in a 3D scene, so that novel images of different viewpoints or focal points can be synthesized. However, transmitting all LF data before viewer observation incurs a large startup delay. To avoid such delay, we propose a new interactive LF streaming framework, where a client periodically requests viewpoint images, and in response a server synthesizes and transmits each requested image as a carefully chosen sparse linear combination of sub-aperture images. For each received synthesized image, the client “decodes” and recovers a new sub-aperture image using a cache of known sub-aperture images. As the cache of decoded sub-aperture images grows over time, the client becomes capable of synthesizing new view/focal point images, reducing overall transmission cost. Experimental results show that our proposed scheme can deliver synthesized images at high quality, even though only sparse sub-aperture images are used for synthesis. Moreover, compared with a scenario where the requested synthesized images are always transmitted, our proposed scheme achieves a significant reduction in accumulated rate when a sufficient number of images are transmitted.

Recent advent in graph signal processing (GSP) has led to the development of new graph-based transforms and wavelets for image / video coding, where the underlying graph describes inter-pixel correlations. In this paper, we develop a new transform called signed graph Fourier transform (SGFT), where the underlying graph G contains negative edges that describe anti-correlations between pixel pairs. Specifically, we first construct a one-state Markov process that models both inter-pixel correlations and anti-correlations. We then derive the corresponding precision matrix, and show that the loopy graph Laplacian matrix Q of a graph G with a negative edge and two self-loops at its end nodes is approximately equivalent. This proves that the eigenvectors of Q - called SGFT - approximates the optimal Karhunen-Loève Transform (KLT). We show the importance of the self-loops in G to ensure Q is positive semi-definite. We prove that the first eigenvector of Q is piecewise constant (PWC), and thus can well approximate a piecewise smooth (PWS) signal like a depth image. Experimental results show that a block-based coding scheme based on SGFT outperforms a previous scheme using graph transforms with only positive edges for several depth images.

Light field imaging enables a user to navigate and observe a static 3D scene from different viewpoints. Downloading the entire data prior to navigation would incur a large startup delay. Instead, previous works propose an interactive light field streaming (ILFS) framework, where a user periodically requests a viewpoint, and in response the server transmits a presynthesized and encoded viewpoint image. Using I-frame, P-frame and previously proposed merge frame that facilitates view-switches, the challenge is how to design and pre-encode a storage-constrained frame structure to enable efficient view navigation. In this paper, we initialize “landmarks” into a structure to improve ILFS performance. A landmark is a designated view with P-frames to/from each neighborhood view, so that any viewpoint image can transition to any other viewpoint image by first visiting a landmark, and then from the landmark to the destination view. This results in a transmission cost of only two P-frames. Using a Lloyd's algorithm variant, we first incrementally insert into a frame structure landmarks one at a time at locally optimal locations. We then employ a greedy algorithm to add / subtract P-frames based on a rate-storage criterion. Experimental results show that our proposed structures have noticeably lower expected transmission cost for the same storage than structures generated by a previous greedy algorithm.

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.

Compression of arbitrary 3D geometry like a human figure in 3D space is challenging. Existing 3D representations like point cloud require encoding of input-specified 3D coordinates, resulting in a large overhead. In this paper, assuming that there exists an underlying smooth 2D manifold in 3D space that describes the geometric shape of a target object, we develop a new progressive 3D geometry representation that signal-adaptively identifies new samples on the manifold surface and encodes them efficiently as graph-signals. Specifically, at each iteration, using previous encoded samples in 3D space, the encoder and decoder first synchronously interpolate a continuous sampling kernel (a 3D mesh) - an approximation of the target surface. We next distribute new sample locations on the continuous kernel based on locally computed kernel curvatures, and compute the signed distances between sample locations and the target surface as sample values. Finally, we connect new discrete samples into a graph for graph-based transform coding of the sample values, which are transmitted to the decoder to refine 3D reconstruction. Experimental results show that our coding scheme outperforms an existing mesh-bsed approach significantly at the low-bitrate region for two different datasets.

Politicians in the same political party often share the same views on social issues and legislative agendas. By mining patterns in TV news co-appearances and Twitter followers, in this paper we estimate political leanings (left / right) of unknown individuals, and detect outlier politicians who have views different from their colleagues in the same party, from a graph signal processing (GSP) perspective. Specifically, we first construct a similarity graph with politicians as nodes, where a positive edge connects two politicians with sizable shared Twitter followers, and a negative edge connects two politicians appearing in the same TV news segment (and thus likely take opposite stands on the same issue). Given a graph with both positive and negative edges, we propose a new graph-signal smoothness prior based on a constructed generalized graph Laplacian matrix that is guaranteed to be positive semi-definite. We formulate a graph-signal restoration problem that can be solved in closed form. Experimental results show that political leanings of unknown individuals can be reliably estimated and outlier politicians can be detected.

We study semi-supervised learning for image classifiers from a graph signal processing (GSP) perspective. Specifically, by viewing a binary classifier as a graph-signal in a high-dimensional feature space, we cast classifier learning as a signal restoration problem via a classical maximum a posteriori (MAP) formulation. Unlike previous graph-signal restoration works, we consider in addition edges with negative weights expressing dissimilarity between samples. We make two key contributions by interpreting a graph as an electrical circuit. First, for graph construction we show how “effective resistance” can guide node pair selection for negative edge insertions. Second, for classification that tolerates a small rejection rate, we define generalized smoothness on graphs that promotes ambiguity in the classifier signal, so that unsure estimated samples can be rejected. We show that generalized graph-signal smoothness is equivalent to satisfying Kirchhoff's current law (KCL) at a given node-this explains why negative edges should not be used to compute generalized smoothness on graphs. Finally, we propose an algorithm based on iterative reweighted least squares (IRLS) that solves the posed MAP problem efficiently. Simulation results show that our algorithm outperforms both SVM variants and graph-based classifiers using positive-edge graphs noticeably.

In free viewpoint television (FTV) application scenario, views that synthesized with depth image-based rendering (DIBR) techniques mainly contain special artifacts like geometric distortions. These artifacts may affect the structure of images/videos by changing the global contour characteristics and thus are annoying for human observers. Context tree based contour coding scheme can be a good tool to measure such structure loss since the more geometric distortion there is in the synthesized view the lager the gap between the encoding cost of the reference and synthesized views. In this paper, we investigate whether such overall encoding cost can be related to perceptual annoyance reflecting in quality score and propose a variable-length context tree based image quality assessment (CT-IQA) scheme. This scheme quantify (1) the overall structure dissimilarity and (2) dissimilarities in various contour characteristics between the reference and synthesized views. The proposed metric is robust to global shifting artifact that is over penalized by traditional metrics. According to the experimental results on the IRCCyn/IVC DIBR image database, the performance of the proposed CT-IQA is promising.

Holes can arise in 3D point clouds due to a number of reasons such as incomplete scans, occlusions, and packet loss. We present an exemplar-based framework for hole filling in 3D point clouds, which exploits non-local self similarity to provide plausible reconstruction even for large holes and complex surfaces. Points along the hole boundary are given priority that determines the order in which they are processed. Hole filling is performed iteratively and uses templates near the hole boundary to find the best matching regions elsewhere in the cloud, from where existing points are transferred to the hole. The proposed method has been compared with several existing methods and has shown superior results, both visually and in terms of the Hausdorff distance.

Given the prevalence of joint photographic experts group (JPEG) compressed images, optimizing image reconstruction from the compressed format remains an important problem. Instead of simply reconstructing a pixel block from the centers of indexed discrete cosine transform (DCT) coefficient quantization bins (hard decoding), soft decoding reconstructs a block by selecting appropriate coefficient values within the indexed bins with the help of signal priors. The challenge thus lies in how to define suitable priors and apply them effectively. In this paper, we combine three image priors-Laplacian prior for DCT coefficients, sparsity prior, and graph-signal smoothness prior for image patches-to construct an efficient JPEG soft decoding algorithm. Specifically, we first use the Laplacian prior to compute a minimum mean square error initial solution for each code block. Next, we show that while the sparsity prior can reduce block artifacts, limiting the size of the overcomplete dictionary (to lower computation) would lead to poor recovery of high DCT frequencies. To alleviate this problem, we design a new graph-signal smoothness prior (desired signal has mainly low graph frequencies) based on the left eigenvectors of the random walk graph Laplacian matrix (LERaG). Compared with the previous graph-signal smoothness priors, LERaG has desirable image filtering properties with low computation overhead. We demonstrate how LERaG can facilitate recovery of high DCT frequencies of a piecewise smooth signal via an interpretation of low graph frequency components as relaxed solutions to normalized cut in spectral clustering. Finally, we construct a soft decoding algorithm using the three signal priors with appropriate prior weights. Experimental results show that our proposal outperforms the state-of-the-art soft decoding algorithms in both objective and subjective evaluations noticeably.

Inverse imaging problems are inherently underdetermined, and hence, it is important to employ appropriate image priors for regularization. One recent popular prior-the graph Laplacian regularizer-assumes that the target pixel patch is smooth with respect to an appropriately chosen graph. However, the mechanisms and implications of imposing the graph Laplacian regularizer on the original inverse problem are not well understood. To address this problem, in this paper, we interpret neighborhood graphs of pixel patches as discrete counterparts of Riemannian manifolds and perform analysis in the continuous domain, providing insights into several fundamental aspects of graph Laplacian regularization for image denoising. Specifically, we first show the convergence of the graph Laplacian regularizer to a continuous-domain functional, integrating a norm measured in a locally adaptive metric space. Focusing on image denoising, we derive an optimal metric space assuming non-local self-similarity of pixel patches, leading to an optimal graph Laplacian regularizer for denoising in the discrete domain. We then interpret graph Laplacian regularization as an anisotropic diffusion scheme to explain its behavior during iterations, e.g., its tendency to promote piecewise smooth signals under certain settings. To verify our analysis, an iterative image denoising algorithm is developed. Experimental results show that our algorithm performs competitively with state-of-the-art denoising methods, such as BM3D for natural images, and outperforms them significantly for piecewise smooth images.

Efficient encoding of object contours in images can facilitate advanced image/video compression techniques, such as shape-adaptive transform coding or motion prediction of arbitrarily shaped pixel blocks. We study the problem of lossless and lossy compression of detected contours in images. Specifically, we first convert a detected object contour into a sequence of directional symbols drawn from a small alphabet. To encode the symbol sequence using arithmetic coding, we compute an optimal variable-length context tree (VCT) T via a maximum a posterior (MAP) formulation to estimate symbols' conditional probabilities. MAP can avoid overfitting given a small training set X of past symbol sequences by identifying a VCT T with high likelihood P(X|T) of observing X given T , using a geometric prior P(T) stating that image contours are more often straight than curvy. For the lossy case, we design fast dynamic programming (DP) algorithms that optimally trade off coding rate of an approximate contour [Formula: see text] given a VCT T with two notions of distortion of [Formula: see text] with respect to the original contour x. To reduce the size of the DP tables, a total suffix tree is derived from a given VCT T for compact table entry indexing, reducing complexity. Experimental results show that for lossless contour coding, our proposed algorithm outperforms state-of-the-art context-based schemes consistently for both small and large training datasets. For lossy contour coding, our algorithms outperform comparable schemes in the literature in rate-distortion performance.

Low-cost depth sensors, such as Microsoft Kinect, have potential for noncontact health monitoring that is robust to ambient lighting conditions. However, captured depth images typically suffer from high acquisition noise, and hence, processing them to estimate biometrics is difficult. In this paper, we propose to capture depth video of a human subject using Kinect 2.0 to estimate his/her heart rate and rhythm; as blood is pumped from the heart to circulate through the head, tiny oscillatory head motion due to Newtonian mechanics can be detected for periodicity analysis. Specifically, we first restore a captured depth video via a joint bit-depth enhancement/denoising procedure, using a graph-signal smoothness prior for regularization. Second, we track an automatically detected head region throughout the depth video to deduce 3D motion vectors. The detected vectors are fed back to the depth restoration module in a loop to ensure that the motion information in two modules is consistent, improving performance of both restoration and motion tracking. Third, the computed 3D motion vectors are projected onto its principal component for 1D signal analysis, composed of trend removal, bandpass filtering, and wavelet-based motion denoising. Finally, the heart rate is estimated via Welch power spectrum analysis, and the heart rhythm is computed via peak detection. Experimental results show accurate estimation of the heart rate and rhythm using our proposed algorithm as compared to rate and rhythm estimated by a portable oximeter.

Obstructive sleep apnea, characterized by repetitive obstruction in the upper airway during sleep, is a common sleep disorder that could significantly compromise sleep quality and quality of life in general. The obstructive respiratory events can be detected by attended in-laboratory or unattended ambulatory sleep studies. Such studies require many attachments to a patient's body to track respiratory and physiological changes, which can be uncomfortable and compromise the patient's sleep quality. In this paper, we propose to record depth video and audio of a patient using a Microsoft Kinect camera during his/her sleep, and extract relevant features to correlate with obstructive respiratory events scored manually by a scientific officer based on data collected by Philips system Alice6 LDxS that is commonly used in sleep clinics. Specifically, we first propose an alternating-frame H.264 video encoding scheme and bit recovery scheme at the decoder. Next, we perform depth video temporal denoising using a motion vector graph smoothness prior. Then, we build a dual-ellipse model and track a patient's chest and abdominal movements in the denoised videos. Finally, we extract features from both depth video and audio for classifier training and respiratory event detection. Experimental results show 1) that our depth video compression scheme outperforms a competitor that records only the 8 most significant bits, 2) our graph-based temporal denoising scheme reduces the flickering effect without over-smoothing, and 3) our trained classifiers can deduce respiratory events scored manually based on data collected by system Alice6 LDxS with high accuracy.

Social media sites like Facebook are obligated to store all photos uploaded by an ever growing user base-which translates to an increasingly expensive storage cost-but only a fraction of uploaded images are revisited thereafter. In this paper, we propose a cloud storage system that trades off computation of a small fraction of requested images with storage of all photos. The key idea is to re-encode uploaded JPEG photos with coarser quantization parameters (QP) for permanent storage, then exploit a signal sparsity prior during inverse mapping to recover fine quantization bin indices via a maximum a posteriori (MAP) formulation. Because by design the system guarantees recovery of an original compressed image (either with exactly the same input fine quantization bin indices or has visual quality indistinguishable by human eyes), from the user's viewpoint it is a normal cloud storage, while from the operator's viewpoint there is pure compression gain and hence lower storage cost. Experimental results show that our storage system can reap significant storage savings (up to 20%) at roughly the same image PSNR (within 0.13dB).

Instead of lossily coding depth images resulting in undesirable geometric distortion, graph-based representation (GBR) describes disparity information as a graph with a controllable accuracy. In this paper, we propose a more compact graphical representation called GBR-plus to code both disparity and color information of a target view given a reference view. Specifically, first we differentiate between disocclusion holes (occluded spatial regions in the reference view) and rounding holes (insufficiently sampled regions in the reference view) in the synthesized target view, so that the decoder can optionally complete rounding holes via signal interpolation without coding overhead. Second, we use a compact graphical representation to delimit disparity-shifted boundaries of objects in the target view, which is coded losslessly. Finally, color pixels in disocclusion holes are predicted using adjacent background pixels as predictors, and prediction residuals in a local neighborhood are coded using Graph Fourier Transform (GFT). Experimental results show that GBR-plus outperforms previous GBR, and has comparable performance as HEVC at mid to high bitrates with lower encoder complexity.

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.

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.

Sensitivity to spatial details drops across the visual periphery, and hence video streaming systems that gracefully degrades quality away from the viewpoint of the observer, provides an optimum viewing experience with potentially large bitrate savings. As reaction latency is an important performance parameter of such systems, good prediction of future gaze locations at the transmission end is very important. A major research question here is: whether a gaze prediction model designed using a pristine undistorted video, is also able to predict the gaze pattern of users when they watch a distorted/ adaptively distorted version of the same video. With several improvements to existing gaze prediction schemes, in combination with a controlled subjective experiment, we confirm not only that HEVC coding distortions have no significant impact on the predictability of gaze patterns, but also that gaze prediction errors can be restricted to 1.5 degrees of viewing angle for a round trip delay of up to 200ms.

The advent of depth sensing technologies has eased the detection of object contours in images. For efficient image compression, coded contours can enable edge-adaptive coding techniques such as graph Fourier transform (GFT) and arbitrarily shaped sub-block motion prediction. However, acquisition noise in captured depth images means that detected contours also suffer from errors. In this paper, we propose to jointly denoise and compress detected contours in an image. Specifically, we first propose a burst error model that models typical errors encountered in an observed string y of directional edges. We then formulate a rate-constrained maximum a posteriori (MAP) problem that trades off the posterior probability P(x|y) of an estimated string x given y with its code rate R(x). Given our burst error model, we show that the negative log of the likelihood P(y|x) can be written as a simple sum of burst error events, error symbols and burst lengths, while the geometric prior P(x) states intuitively that contours are more likely straight than curvy. We design a dynamic programming (DP) algorithm that solves the posed problem optimally. Experimental results show that our joint denoising / compression scheme outperformed a competing separate scheme in rate-distortion performance noticeably.

The use of strong lighting contrast to accentuate objects and figures in a painting—called Chiaroscuro—is popular among Renaissance painters such as Caravaggio, La Tour and Rembrandt. In this paper, we propose a new metric called LuCo to quantify the extent to which Chiaroscuro is employed by an artist in a painting. This measurement could be used to assess the capability of any system to fulfill the original artistic intention and consequently ensure minimal disruptions of Quality of Experience. We first argue that Chiaroscuro is a device for artists to draw attention to specific spatial regions; thus it can be understood as a restricted notion of visual saliency computed using only luminance features. Operationally, using a set of local luminance patches we first compute a Bayesian surprise value, where the prior and posterior probabilities are computed assuming a Gaussian Markov Random Field (GMRF) model. Inverse covariance matrices of the GMRF model are estimated via sparse graph learning for robustness. We construct a histogram using the computed surprise values from different local patches in a painting. Finally, we compute a skewness parameter for the constructed histogram as our LuCo score: large skewness means luminance surprises are either very small or very large, meaning that the artist accentuated lighting contrast in the painting. Experimental results show that paintings by Chiaroscuro artists have higher LuCo scores than 19th century French Impressionists, and Rembrandt's self-portraits have increasingly higher LuCo scores as he aged except for his late period—both trends are in agreement with art historians' interpretations.

Block-based image or video coding standards (e.g. JPEG) compress an image lossily by quantizing transform coefficients of non-overlapping pixel blocks. If the chosen quantization parameters (QP) are large, then hard decoding of a compressed image—using indexed quantization bin centers as reconstructed transform coefficients—can lead to unpleasant blocking artifacts. Leveraging on recent advances in graph signal processing (GSP), we propose a dequantization scheme specifically for piecewise smooth (PWS) images: images with sharp object boundaries and smooth interior surfaces. We first mathematically define a PWS image as a low-frequency signal with respect to an inter-pixel similarity graph with edges of weights 1 or 0. Using quantization bin boundaries as constraints, we then jointly optimize the desired graph-signal and the similarity graph in a unified framework. A generalization to consider generalized piecewise smooth (GPWS) images—where sharp object boundaries are replaced by transition regions—is also proposed. Experimental results show that our proposed scheme outperforms a state-of-the-art dequantization method by 1 dB on average in PSNR.

Presents a listing of the new Associate Editors for this issue of the publication.

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 free viewpoint video systems, a user has the freedom to select a virtual view from which an image of the 3D scene is rendered, and the scene is commonly represented by color and depth images of multiple nearby viewpoints. In such representation, there exists data redundancy across multiple dimensions: 1) a 3D voxel may be represented by pixels in multiple viewpoint images (inter-view redundancy); 2) a pixel patch may recur in a distant spatial region of the same image due to self-similarity (inter-patch redundancy); and 3) pixels in a local spatial region tend to be similar (inter-pixel redundancy). It is important to exploit these redundancies during inter-view prediction toward effective multiview video compression. In this paper, we propose an encoder-driven inpainting strategy for inter-view predictive coding, where explicit instructions are transmitted minimally, and the decoder is left to independently recover remaining missing data via inpainting, resulting in lower coding overhead. In particular, after pixels in a reference view are projected to a target view via depth-image-based rendering at the decoder, the remaining holes in the target view are filled via an inpainting process in a block-by-block manner. First, blocks are ordered in terms of difficulty-to-inpaint by the decoder. Then, explicit instructions are only sent for the reconstruction of the most difficult blocks. In particular, the missing pixels are explicitly coded via a graph Fourier transform or a sparsification procedure using discrete cosine transform, leading to low coding cost. For blocks that are easy to inpaint, the decoder independently completes missing pixels via template-based inpainting. We apply our proposed scheme to frames in a prediction structure defined by JCT-3V where inter-view prediction is dominant, and experimentally we show that our scheme achieves up to 3-dB gain in peak-signal-to-noise-ratio in reconstructed image quality over a comparable 3D-High Efficiency Video Coding implementation using fixed 16 $\times $ 16 block size.

When images at low bit-depth are rendered at high bit-depth displays, missing least significant bits needs to be estimated. We study the image bit-depth enhancement problem: estimating an original image from its quantized version from a minimum mean squared error (MMSE) perspective. We first argue that a graph-signal smoothness prior-one defined on a graph embedding the image structure-is an appropriate prior for the bit-depth enhancement problem. We next show that directly solving for the MMSE solution is, in general, too computationally expensive to be practical. We then propose an efficient approximation strategy. In particular, we first estimate the ac component of the desired signal in a maximum a posteriori formulation, efficiently computed via convex programming. We then compute the dc component with an MMSE criterion in a closed form given the computed ac component. Experiments show that our proposed two-step approach has improved performance over the conventional bit-depth enhancement schemes in both objective and subjective comparisons.

The “color-plus-depth” format represents a 3D scene using multiple color and depth images captured by an array of closely spaced cameras. Using this format, a novel image as observed from a horizontally shifted virtual viewpoint can be synthesized via depth-image-based rendering (DIBR), using neighboring camera-captured viewpoint images as reference. In this paper, using the same popularized color-plus-depth representation, we propose to construct, in addition, novel images as observed from virtual viewpoints closer to the 3D scene, enabling a new dimension of view navigation. To construct this new image type, we first perform a new DIBR pixel-mapping for z-dimensional camera movement. We then identify expansion holes-a new kind of missing pixels unique in z-dimensional DIBR-mapped images-using a depth layering procedure. To fill expansion holes we formulate a patch-based maximum a posteriori problem, where the patches are appropriately spaced using diamond tiling. Leveraging on recent advances in graph signal processing, we define a graph-signal smoothness prior to regularize the inverse problem. Finally, we design a fast iterative reweighted least square algorithm to solve the posed problem efficiently. Experimental results show that our z-dimensional synthesized images outperform images rendered by a naı̈ve modification of VSRS 3.5 by up to 4.01 dB.

In multiview applications, camera views can be used as reference views to synthesize additional virtual viewpoints, allowing users to freely navigate within a 3D scene. However, bandwidth constraints may restrict the number of reference views sent to clients, limiting the quality of the synthesized viewpoints. In this work, we study the problem of in-network reference view synthesis aimed at improving the navigation quality at the clients. We consider a distributed cloud network architecture, where data stored in a main cloud is delivered to end users with the help of cloudlets, i.e., resource-rich proxies close to the users. We argue that, in case of limited bandwidth from the cloudlet to the users, re-sampling at the couldlet the viewpoints of the 3D scene (i.e., synthesizing novel virtual views in the cloudlets to be used as new references to the decoder) is beneficial compared to mere subsampling of the original set of camera views. We therefore cast a new reference view selection problem that seeks the subset of views minimizing the distortion over a view navigation window defined by the user under bandwidth constraints. We prove that the problem is NP-hard, and we propose an effective polynomial time algorithm using dynamic programming to solve the optimization problem under general assumptions that cover most of the multiview scenarios in practice. Simulation results confirm the performance gain offered by virtual view synthesis in the network.

Free viewpoint video (FVV) offers compelling interactive experience by allowing users to switch to any viewing angle at any time. An FVV is composed of a large number of camera-captured anchor views, with virtual views (not captured by any camera) rendered from their nearby anchors using techniques such as depth-image-based rendering (DIBR). We consider a group of wireless users who may interact with an FVV by independently switching views. We study a novel live FVV streaming network where each user pulls a subset of anchors from the server via a primary channel. To enhance anchor availability at each user, a user generates network-coded (NC) packets using some of its anchors and broadcasts them to its direct neighbors via a secondary channel. Given limited primary and secondary channel bandwidths at the devices, we seek to maximize the received video quality (i.e., minimize distortion) by jointly optimizing the set of anchors each device pulls and the anchor combination to generate NC packets. To our best knowledge, this is among the first body of work addressing such joint optimization problem for wireless live FVV streaming with NC-based collaboration. We first formulate the problem and show that it is NP-hard. We then propose a scalable and effective algorithm called PAFV (Peer-Assisted Freeview Video). In PAFV, each node collaboratively and distributedly decides on the anchors to pull and NC packets to share so as to minimize video distortion in its neighborhood. Extensive simulation studies show that PAFV outperforms other algorithms, achieving substantially lower video distortion (often by more than 20-50%) with significantly less redundancy (by as much as 70%). Our Android-based video experiment further confirms the effectiveness of PAFV over comparison schemes.

Images and videos are often captured in poor light conditions, resulting in low-contrast images that are corrupted by acquisition noise. To recreate a high-quality image for visual observation, the captured image must be denoised and contrastenhanced. Conventional methods perform these two tasks in two separate stages: an image is first denoised, followed by an enhancement procedure. In this paper, we propose to jointly denoise and enhance an image in one unified optimization framework. The crux of the optimization rests on the definition of the enhancement operator, described by a graph Laplacian matrix H. The operator must enhance the high frequency details of the original image without amplifying additive noise. We propose a graph-based low-pass filtering approach to denoise edge weights in the graph, resulting in a more robust estimate of H. Experimental results show that our proposed joint approach can outperform the separate approach in demonstrable image quality.

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.

Given the prevalence of JPEG compressed images on the Internet, image reconstruction from the compressed format remains an important and practical problem. Instead of simply reconstructing a pixel block from the centers of assigned DCT coefficient quantization bins (hard decoding), we propose to jointly reconstruct a neighborhood group of pixel patches using two image priors while satisfying the quantization bin constraints. First, we assume that a pixel patch can be approximated as a sparse linear combination of atoms from an offline-learned over-complete dictionary. Second, we assume that a patch, when interpreted as a graph-signal, is smooth with respect to an appropriately defined graph that captures the estimated structure of the target image. Finally, neighboring patches in the optimization have sufficient overlaps and are forced to be consistent, so that blocking artifacts typical in JPEG decoded images are avoided. To find the optimal group of patches, we formulate a constrained optimization problem and propose a fast alternating algorithm to find locally optimal solutions. Experimental results show that our proposed algorithm outperforms state-of-the-art soft decoding algorithms by up to 1.47dB in PSNR.

Interactive free viewpoint video offers the possibility for each user to independently choose the views of a 3D scene to be displayed at the decoder. The visual content is commonly represented by N texture and depth map pairs that capture different viewpoints. A server selects an appropriate subset of M ≤ N views for transmission, so that the user can freely navigate in the corresponding window of viewpoints without being affected by network delay. During navigation, a user can synthesize any intermediate virtual view image in the navigation window via depth-image-based rendering (DIBR) using two nearby camera views as references. When the available bandwidth is too small to transmit all camera views typically used to synthesize views in the navigation window, we propose to synthesize intermediate virtual views as new references for transmission - a resampling of viewpoints for the 3D scene - so that the synthesized view distortion within the navigation window is minimized. We formulate a combinatorial optimization problem to find the best set of M virtual views to synthesize as new references, and show that the problem is NP-hard. We approximate the original problem with a new reference view equivalence model and derive in this case an optimal dynamic programming algorithm to determine the best set of M views to be transmitted to each user. Experimental results show that synthesizing virtual views as new references for client-side view synthesis can outperform simple selection from camera views by up to 0.73dB in synthesized view quality.

Depth sensors like Microsoft Kinect can acquire partial geometric information in a 3D scene via captured depth images, with potential application to non-contact health monitoring. However, captured depth videos typically suffer from low bit-depth representation and acquisition noise corruption, and hence using them to deduce health metrics that require tracking subtle 3D structural details is difficult. In this paper, we propose to capture depth video using Kinect 2.0 to estimate the heart rate of a human subject; as blood is pumped to circulate through the head, tiny oscillatory head motion can be detected for periodicity analysis. Specifically, we first perform a joint bit-depth enhancement / denoising procedure to improve the quality of the captured depth images, using a graph-signal smoothness prior for regularization. We then track an automatically detected nose region throughout the depth video to deduce 3D motion vectors. The deduced 3D vectors are then analyzed via principal component analysis to estimate heart rate. Experimental results show improved tracking accuracy using our proposed joint bit-depth enhancement / denoising procedure, and estimated heart rates are close to ground truth.

A depth image provides geometric information of a 3D scene, namely the shapes of physical objects captured from a particular viewpoint. This information is important for synthesizing images corresponding to different virtual camera viewpoints via depth-image-based rendering (DIBR). Since it has been shown that blurring of object contours in the depth images leads to bleeding artefacts in virtual images. The most effective way to compress depth images relies on edge-adaptive image codecs that preserve contours, which are losslessly coded as side information (SI). However, lossless coding of the exact object contours can be expensive. In this paper, we argue that the contours themselves can be suitably approximated to save bits, while the depth images piecewise smooth (PWS) characteristic stays preserved. Specifically, we first propose a metric that estimates contour coding rate based on edge statistics. Given an initial rate estimate, we then pro-actively approximate object contours in a way that guarantees rate reduction when coded using arithmetic edge coding (AEC) as SI. Given the sharp but approximated contours, we finally encode the image using an edge-adaptive image codec with graph Fourier transform (GFT) for edge preservation. We show in our experiments that by maintaining sharp but slightly inaccurate object contours, the resulting quality of virtual views synthesized via DIBR exceeds those synthesized using depth images compressed with edge-adaptive codecs that losslessly encode object contours as SI, in particular when the total coding rate budget is low. This confirms that optimized coding of depth images results in an effective tradeoff in the representation of contour and respective depth information.

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.

A well-known problem in video conferencing is gaze mismatch. Instead of relying exclusively on online captured data for rendering, a recent work first trains offline dictionaries using a large image database of movie and TV stars to learn "beautiful" features. During real-time conferencing, one can then simultaneously correct gaze and beautify the subject's facial components in single images by seeking sparse linear combination of pre-trained dictionary atoms for face reconstruction. Extending on this work, we focus on joint gaze correction / face beautification for video. First, we define a large search space invariant to scale, shift and rotation for facial feature beautification based on SIFT. We then address two practical issues unique to video: i) how beautified results can be temporally consistent across group of pictures (GOP), and ii) how blinking eyes can be beautified even though the training database contains only open-eye facial images. Experimental results show that our method achieves the desired temporal consistency, and the blinking process is smooth and natural.

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.

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

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 free viewpoint video, a viewer can choose at will any camera angle or the so-called “virtual view” to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera views via depth-image-based rendering (DIBR). We consider, for the first time, collaborative live streaming of a free viewpoint video, where a group of users may interactively pull and cooperatively share streams of different anchor views. There is a cost to access the anchor views from the live source, a cost to “reconfigure” the peer network due to a change in selected anchors during view switching, and a distortion cost due to the distance of the virtual views to the received anchor views at users. We optimize the anchor views allocated to users so as to minimize the overall streaming cost given by the access cost, reconfiguration cost, and view distortion cost. We first show that, if the reconfiguration cost due to view switching is negligible, the view allocation problem can be optimally and efficiently solved in polynomial time using dynamic programming. For the case of non-negligible reconfiguration cost, the problem becomes NP-hard. We thus present a locally optimal and centralized algorithm inspired by Lloyd's algorithm used in non-uniform scalar quantization. We further propose a distributed algorithm with convergence guarantee, where each peer group independently makes merge-and-split decisions with a well-defined fairness criteria. Simulation results show that our algorithms achieve low streaming cost due to its excellent anchor view allocation.

Compression of dynamic 3D geometry obtained from depth sensors is challenging, because noise and temporal inconsistency inherent in acquisition of depth data means there is no one-to-one correspondence between sets of 3D points in consecutive time instants. In this paper, instead of coding 3D points (or meshes) directly, we propose to represent an object's 3D geometry as a collection of tile images. Specifically, we first place a set of image tiles around an object. Then, we project the object's 3D geometry onto the tiles that are interpreted as 2D depth images, which we subsequently encode using a modified multiview image codec tuned for piecewise smooth signals. The crux of the tile image framework is the “optimal” placement of image tiles - one that yields the best tradeoff in rate and distortion. We show that if only planar and cylindrical tiles are considered, then the optimal placement problem for K tiles can be mapped to a tractable piece-wise linear approximation problem. We propose an efficient dynamic programming algorithm to find an optimal solution to the piecewise linear approximation problem. Experimental results show that optimal tiling outperforms naïve tiling by up to 35% in rate reduction, and graph transform can further exploit the smoothness of the tile images for coding gain.

Although images as viewed from intermediate virtual viewpoints can be synthesized using texture and depth maps from nearby camera views via depth-image-based rendering (DIBR), the rendered images contain disocclusion holes - spatial regions that were not visible in the reference views due to foreground object occlusion - that requires proper filling. In this paper, we introduce a new signal prior into the hole filling problem formulation: given disocclusion holes are part of the background and background tends to have low visual saliency, the extrapolated signal into the holes must also be of low saliency. Mathematically, we add a low-saliency prior to an exemplar-based inpainting algorithm, so that the best-matched block has both small matching cost and is of low visual saliency. Moreover, we compute a suitable Lagrange multiplier value for the saliency cost term via analysis of the reference images. Experimental results show that using a low-saliency prior can improve performance by 0.5 dB over a previous hole filling scheme.

Images are often decoded with noise at receiver due to capturing errors and/or signal quantization during compression. Further, it is often necessary to display a decoded image at a higher resolution than the captured one, given available high-resolution (HR) display or a need to zoom-in for detailed examination. In this paper, we address the problems of image denoising and super-resolution (SR) jointly in one unified graph-based framework, focusing on a special class of signals called generalized piecewise smooth (GPWS) images. GPWS images are composed mostly of smooth regions connected by transition regions, and represent an important subclass of images, including cartoon, sub-regions of video frames with captions, graphics images in video games, etc. Like our previous work on piecewise smooth (PWS) images, GPWS images also imply simple-enough graph representations in the pixel domain, so that suitable graph-based filtering techniques can be readily applied. Specifically, leveraging on previous work on graph spectral analysis, for a given pixel block in low-resolution (LR) we first use the second eigenvector of a computed graph Laplacian matrix to identify a hard boundary, and then use the third eigenvector to identify two piecewise smooth regions and a transition region that separates them. The LR hard boundary is then super-resolved into HR via a procedure based on local self-similarity, while graph weights of the LR transition region is mapped to those of the HR transition region via polynomial fitting. Using the computed HR boundary and weights in the transition region, we construct a suitable HR graph corresponding to the LR counterpart, and perform joint denoising / SR using a graph smoothness prior. Experimental results show that our proposed algorithm outperforms two representative separable denoising / SR schemes in both subjective and objective quality.

Gaze mismatch is a common problem in video conferencing, where the viewpoint captured by a camera (usually located above or below a display monitor) is not aligned with the gaze direction of the human subject, who typically looks at his counterpart in the center of the screen. This means that the two parties cannot converse eye-to-eye, hampering the quality of visual communication. One conventional approach to the gaze mismatch problem is to synthesize a gaze-corrected face image as viewed from center of the screen via depth-image-based rendering (DIBR), assuming texture and depth maps are available at the camera-captured viewpoint(s). Due to self-occlusion, however, there will be missing pixels in the DIBR-synthesized view image that require satisfactory filling. In this paper, we propose to jointly solve the hole-filling problem and the face beautification problem (subtle modifications of facial features to enhance attractiveness of the rendered face) via a unified dual sparse coding framework. Specifically, we first train two dictionaries separately: one for face images of the intended conference subject, one for images of “beautiful” human faces. During synthesis, we simultaneously seek two code vectors - one is sparse in the first dictionary and explains the available DIBR-synthesized pixels, the other is sparse in the second dictionary and matches well with the first vector up to a restricted linear transform. This ensures a good match with the intended target face, while increasing proximity to “beautiful” facial features to improve attractiveness. Experimental results show naturally rendered human faces with noticeably improved attractiveness.

While modern displays offer high dynamic range (HDR) with large bit-depth for each rendered pixel, the bulk of legacy image and video contents were captured using cameras with shallower bit-depth. In this paper, we study the bit-depth enhancement problem for images, so that a high bit-depth (HBD) image can be reconstructed from an input low bit-depth (LBD) image. The key idea is to apply appropriate smoothing given the constraints that reconstructed signal must lie within the per-pixel quantization bins. Specifically, we first define smoothness via a signal-dependent graph Laplacian, so that natural image gradients can nonetheless be interpreted as low frequencies. Given defined smoothness prior and observed LBD image, we then demonstrate that computing the most probable signal via maximum a posteriori (MAP) estimation can lead to large expected distortion. However, we argue that MAP can still be used to efficiently estimate the AC component of the desired HBD signal, which along with a distortion-minimizing DC component, can result in a good approximate solution that minimizes the expected distortion. Experimental results show that our proposed method outperforms existing bit-depth enhancement methods in terms of reconstruction error.

Quality of sleep greatly affects a person's physiological well-being. Traditional sleep monitoring systems are expensive in cost and intrusive enough that they disturb the natural sleep of clinical patients. In our previous work, we proposed a non-intrusive sleep monitoring system to first record depth video in real-time, then offline analyze recorded depth data to track a patient's chest and abdomen movements over time. Detection of abnormal breathing is then interpreted as episodes of apnoea or hypopnoea. Leveraging on recent advances in graph signal processing (GSP), in this paper we propose two new additions to further improve our sleep monitoring system. First, temporal denoising is performed using a block motion vector smoothness prior expressed in the graph-signal domain, so that unwanted temporal flickering can be removed. Second, a graph-based event classification scheme is proposed, so that detection of apnoea / hypopnoea can be performed accurately and robustly. Experimental results show first that graph-based temporal denoising scheme outperforms an implementation of temporal median filter in terms of flicker removal. Second, we show that our graph-based event classification scheme is noticeably more robust to errors in training data than two conventional implementations of support vector machine (SVM).

Transmitting texture and depth images of captured camera view(s) of a 3D scene enables a receiver to synthesize novel virtual viewpoint images via Depth-Image-Based Rendering (DIBR). However, a DIBR-synthesized image often contains disocclusion holes, which are spatial regions in the virtual view image that were occluded by foreground objects in the captured camera view(s). In this paper, we propose to complete these disocclusion holes by exploiting the self-similarity characteristic of natural images via nonlocal template-matching (TM). Specifically, we first define self-similarity as nonlocal recurrences of pixel patches within the same image across different scales-one characterization of self-similarity in a given image is the scale range in which these patch recurrences take place. Then, at encoder we segment an image into multiple depth layers using available per-pixel depth values, and characterize self-similarity in each layer with a scale range; scale ranges for all layers are transmitted as side information to the decoder. At decoder, disocclusion holes are completed via TM on a per-layer basis by searching for similar patches within the designated scale range. Experimental results show that our method improves the quality of rendered images over previous disocclusion hole-filling algorithms by up to 3.9dB in PSNR.

Depth image compression is important for compact representation of 3D visual data in texture-plus-depth format, where texture and depth maps from one or more viewpoints are encoded and transmitted. A decoder can then synthesize a freely chosen virtual view via depth-image-based rendering using nearby coded texture and depth maps as reference. Further, depth information can be used in other image processing applications beyond view synthesis, such as object identification, segmentation, and so on. In this paper, we leverage on the observation that neighboring pixels of similar depth have similar motion to efficiently encode depth video. Specifically, we divide a depth block containing two zones of distinct values (e.g., foreground and background) into two arbitrarily shaped regions (sub-blocks) along the dividing boundary before performing separate motion prediction (MP). While such arbitrarily shaped sub-block MP can lead to very small prediction residuals (resulting in few bits required for residual coding), it incurs an overhead to transmit the dividing boundaries for sub-block identification at decoder. To minimize this overhead, we first devise a scheme called arithmetic edge coding (AEC) to efficiently code boundaries that divide blocks into sub-blocks. Specifically, we propose to incorporate the boundary geometrical correlation in an adaptive arithmetic coder in the form of a statistical model. Then, we propose two optimization procedures to further improve the edge coding performance of AEC for a given depth image. The first procedure operates within a code block, and allows lossy compression of the detected block boundary to lower the cost of AEC, with an option to augment boundary depth pixel values matching the new boundary, given the augmented pixels do not adversely affect synthesized view distortion. The second procedure operates across code blocks, and systematically identifies blocks along an object contour that should be coded using sub-block MP via a rate-distortion optimized trellis. Experimental results show an average overall bitrate reduction of up to 33% over classical H.264/AVC.

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

Free-viewpoint video conferencing allows a participant to observe the remote 3D scene from any freely chosen viewpoint. An intermediate virtual viewpoint image is typically synthesized using two pairs of transmitted texture and depth maps from two neighboring captured viewpoints via depth-image-based rendering (DIBR). To maintain high quality of synthesized images, it is imperative to contain the adverse effects of network packet losses that may arise during texture and depth video transmission. Towards this goal, we develop an integrated approach that exploits the representation redundancy inherent in the multiple streamed videos-a voxel in the 3D scene visible to two captured views is sampled and coded twice in the two views. In particular, at the receiver we first develop an error concealment strategy that adaptively blends corresponding pixels in the two captured views during DIBR, so that pixels from the more reliable transmitted view are weighted more heavily. We then couple it with a sender-side optimization of reference picture selection (RPS) during real-time video coding, so that blocks containing pixel samples of voxels that are visible in both views are more error-resiliently coded in one view only, given adaptive blending will mitigate errors in the other view. Further, synthesized view distortion sensitivities to texture versus depth errors are analyzed, so that relative importance of texture and depth code blocks can be computed for system-wide RPS optimization. Finally, quantization parameter (QP) is adaptively selected per frame, optimally trading off source distortion due to compression with channel distortion due to potential packet losses. Experimental results show that the proposed scheme can outperform previous work by up to 2.9 dB at 5% packet loss rate.

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request any one of many captured views for playback. Moreover, the client can periodically freeze the video in time and switch to neighboring views for a compelling look-around visual effect. We consider distributed content servers to support large-scale interactive multiview video service. These servers collaboratively replicate and access video contents. We study two challenges in this setting: what is an efficient coding structure that supports interactive view switching and, given that, what to replicate in each server in order to minimize the cost incurred by interactive temporal and view switches? We first propose a redundant coding structure that facilitates interactive view-switching, trading off storage with transmission rate. Using the coding structure, we next propose a content replication strategy that takes advantage of indirect hit to lower view-switching cost: in the event that the exact requested view is not available locally, the local server can fetch a different but correlated view from the other servers, so that the remote repository only needs to supply the pre-encoded view differential. We formulate the video content replication problem to minimize the switching cost as an integer linear programming (ILP) problem and show that it is NP-hard. We first propose an LP relaxation and rounding algorithm (termed Minimum Eviction) with bounded approximation error. We then study a more scalable solution based on dynamic programming and Lagrangian optimization (DPLO) with little sacrifice in performance. Simulation results show that our replication algorithms achieve substantially lower switching cost compared to other content replication schemes.

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).

Visual saliency is a probabilistic estimate of how likely a given spatial area in an image or video is to attract human visual attention relative to other areas. Bottom-up saliency models aggregate low-level image features like luminance and color contrast, flicker, 2D motion, etc. to construct a plausible saliency map. In this paper, we introduce 3D motion (object movements towards or away from the observer) into bottom-up video saliency modeling. Given availability of per-pixel depth maps, we first propose a novel algorithm to estimate 3D motion vectors (3DMVs) for arbitrarily shaped sub-blocks in texture-plus-depth videos. We then derive two feature channels from 3DMVs to be incorporated into a widely accepted bottom-up saliency model. Experiments on subjective quality of Region-of-Interest (ROI) based video coding show that our enriched saliency model with 3DMV channels is more accurate in estimating human visual attention.

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.

Free viewpoint video enables a client to interactively choose a viewpoint from which to synthesize an image via depth-image-based rendering (DIBR). However, synthesizing a novel viewpoint image using texture and depth maps from two nearby views entails a sizable computation overhead. Further, to reduce transmission rate, recent proposals synthesize the second reference view itself using texture and depth maps of the first reference view via a complex inpainting algorithm to complete large disocclusion holes in the second reference image-a small amount of auxiliary information (AI) is transmitted by sender to aid the inpainting process-resulting in an even higher computation cost. In this paper, we study the optimal tradeoff between transmission rate and client-side complexity, so that in the event that a client device is computation-constrained, complexity of DIBR-based view synthesis can be scalably reduced at the expense of a controlled increase in transmission rate. Specifically, for standard view synthesis paradigm that requires texture and depth maps of two neighboring reference views, we design a dynamic programming algorithm to select the optimal subset of intermediate virtual views for rendering and encoding at server, so that a client performs only video decoding of these views, reducing overall view synthesis complexity. For new view synthesis paradigm that synthesizes the second reference view itself from the first, we optimize the transmission of AI used to assist inpainting of large disocclusion holes, so that some computation-expensive exemplar block search operations are avoided, reducing inpainting complexity. Experimental results show that the proposed schemes can scalably and gracefully reduce client-side complexity, and the proposed optimizations achieve better rate-complexity tradeoff than competing schemes.

In free viewpoint video, texture and depth maps from two camera-captured viewpoints are transmitted, so that at receiver, a novel virtual view chosen by the client can be synthesized via depth-image-based rendering (DIBR). When irrecoverable packet losses occur during transmission-typically affecting less important spatial regions in the video given unequal error protection (UEP) is deployed-appropriate error concealment strategies must be used at decoder to minimize resulting visual degradation in the synthesized view. Towards this goal, we propose a new optimization framework based on visual saliency to combine two different concealment techniques. First, given a pixel in the virtual view is typically constructed as a convex combination of corresponding pixels in the left and right captured views, weighted pixel blending (WPB) readjusts the weights in the linear sum to reflect the expected error in code blocks that contain the corresponding pixels. Second, exemplar-based patch matching (EPM) finds the most similar patches in the known spatial region to complete missing pixels in the unknown region. To choose between candidates constructed using the two techniques when filling a given pixel patch in the synthesized view, we first compute a weighted sum of expected error and visual saliency for each candidate patch. The candidate with the smaller sum (one with small expected error and visual saliency, so that even if errors do occur, they do not stand out visually) is selected for pixel completion. Experimental results show that our scheme can outperform the use of co-located blocks from a previous frame by up to 0.7dB in PSNR and improve subjective visual quality.

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.

In free viewpoint video, a user can pull texture and depth videos captured from two nearby reference viewpoints to synthesize his chosen intermediate virtual view for observation via depth-image-based rendering (DIBR). For users who are observing the same video at the same time but not necessarily from the same virtual viewpoint, they have incentive to pull the same reference views so that the streaming cost can be shared. On the other hand, in general distortion of a synthesized virtual view increases with its distance to the reference views, and so a user also has incentive to select reference views that tightly “sandwich” his chosen virtual view, minimizing distortion. In a previous work, reference view sharing strategies-ones that optimally trade off shared streaming costs with synthesized view distortions-were investigated for the case when users are first divided into groups, and each user group independently pulls two reference views and shares the resulting streaming cost. In this paper, we generalize the previous notion of user group, so that a user can simultaneously belong to two groups, and each group shares the streaming cost of a single view. We also aim to find a Nash Equilibrium (NE) solution of reference view selection, which is stable and from which no one has incentive to unilaterally deviate. Specifically, we first derive a lemma based on known properties of synthesized view distortion functions. We then design a search algorithm to find a NE solution, leveraging on the derived lemma to reduce search complexity. Experimental results show that the stable NE solution increases the overall cost only slightly when compared to the unstable optimal reference selection that gives the lowest overall cost. Further, a larger network will give a lower average cost for each user, and thus, users tend to join large networks for cooperation.

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

Depth maps, characterizing per-pixel physical distance between objects in a 3D scene and a capturing camera, can now be readily acquired using inexpensive active sensors such as Microsoft Kinect. However, the acquired depth maps are often corrupted due to surface reflection or sensor noise. In this paper, we build on two previously developed works in the image denoising literature to restore single depth maps-i.e., to jointly exploit local smoothness and nonlocal self-similarity of a depth map. Specifically, we propose to first cluster similar patches in a depth image and compute an average patch, from which we deduce a graph describing correlations among adjacent pixels. Then we transform similar patches to the same graph-based transform (GBT) domain, where the GBT basis vectors are learned from the derived correlation graph. Finally, we perform an iterative thresholding procedure in the GBT domain to enforce group sparsity. Experimental results show that for single depth maps corrupted with additive white Gaussian noise (AWGN), our proposed NLGBT denoising algorithm can outperform state-of-the-art image denoising methods such as BM3D by up to 2.37dB in terms of PSNR.

Visual saliency is a probabilistic estimate of how likely a spatial area in an image or video frame is to attract human visual attention relative to other areas. When existing bottom-up saliency models aggregate low-level features to construct a plausible saliency map, only 2-D motion cues are used as motion features, even though videos typically capture dynamic 3-D scenes. In this paper, we introduce 3-D motion into bottom-up saliency modeling for texture-plus-depth videos. We first propose an efficient 3-D motion estimation algorithm, which computes a 3-D motion vector (3DMV) for each sub-block in the frame. Using the computed 3DMVs, we then derive several saliency channels (called 3DMV channels), which are incorporated into a bottom-up saliency model to obtain enhanced saliency maps. Experiments tracking human gaze show that incorporating our 3DMV channels into bottom-up saliency model significantly improves the accuracy of derived saliency maps.

In interactive multiview video streaming (IMVS), a user observes one view at a time, but can periodically switch to a desired neighboring captured view as the video is played back in time. Previous IMVS works focus on efficient compression techniques that facilitate interactive view switching. In this paper, in addition to the loss-resilient aspect during network streaming we address how to design efficient coding tools and optimize frame structure for transmission to facilitate view switching and contain error propagation in differentially coded video due to packet losses. We first design a new unified distributed source coding (uDSC) frame-a new coding tool that simultaneously offers view switching and loss-resilient capabilities-for periodic insertion into the multiview frame structure. After inserting uDSC-frames into the coding structure, we schedule packets for network transmission in a rate-distortion optimal manner for both wireless multicast and wired unicast streaming scenarios. For wireless multicast over a Gilbert-Elliott loss model, frames in a group of pictures are packetized and reordered, so that uDSC frames are correctly decoded with high probability, mitigating error propagation. For wired unicast, we use a Markov decision process to optimize packet transmission to minimize expected distortion given a bandwidth constraint. Experimental results show that systems that insert uDSC frames and optimize packet transmission can outperform other competing coding schemes by up to 2.8 and 11.6 dB in wireless multicast and wired unicast streaming scenarios, respectively.

Enabling users to interactively navigate through different viewpoints of a static scene is a new interesting functionality in 3D streaming systems. While it opens exciting perspectives toward rich multimedia applications, it requires the design of novel representations and coding techniques to solve the new challenges imposed by the interactive navigation. In particular, the encoder must prepare a priori a compressed media stream that is flexible enough to enable the free selection of multiview navigation paths by different streaming media clients. Interactivity clearly brings new design constraints: the encoder is unaware of the exact decoding process, while the decoder has to reconstruct information from incomplete subsets of data since the server generally cannot transmit images for all possible viewpoints due to resource constrains. In this paper, we propose a novel multiview data representation that permits us to satisfy bandwidth and storage constraints in an interactive multiview streaming system. In particular, we partition the multiview navigation domain into segments, each of which is described by a reference image (color and depth data) and some auxiliary information. The auxiliary information enables the client to recreate any viewpoint in the navigation segment via view synthesis. The decoder is then able to navigate freely in the segment without further data request to the server; it requests additional data only when it moves to a different segment. We discuss the benefits of this novel representation in interactive navigation systems and further propose a method to optimize the partitioning of the navigation domain into independent segments, under bandwidth and storage constraints. Experimental results confirm the potential of the proposed representation; namely, our system leads to similar compression performance as classical inter-view coding, while it provides the high level of flexibility that is required for interactive streaming. Because of these unique properties, our new framework represents a promising solution for 3D data representation in novel interactive multimedia services.

Eye gaze is now used as a content adaptation trigger in interactive media applications, such as customized advertisement in video, and bit allocation in streaming video based on region-of-interest (ROI). The reaction time of a gaze-based networked system, however, is lower-bounded by the network round trip time (RTT). Furthermore, only low-sampling-rate gaze data is available when commonly available webcam is employed for gaze tracking. To realize responsive adaptation of media content even under non-negligible RTT and using common low-cost webcams, we propose a Hidden Markov Model (HMM) based gaze-prediction system that utilizes the visual saliency of the content being viewed. Specifically, our HMM has two states corresponding to two of human's intrinsic gaze behavioral movements, and its model parameters are derived offline via analysis of each video's visual saliency maps. Due to the strong prior of likely gaze locations offered by saliency information, accurate runtime gaze prediction is possible even under large RTT and using common webcam. We demonstrate the applicability of our low-cost gaze prediction system by focusing on ROI-based bit allocation for networked video streaming. To reduce transmission rate of a video stream without degrading viewer's perceived visual quality, we allocate more bits to encode the viewer's current spatial ROI, while devoting fewer bits in other spatial regions. The challenge lies in overcoming the delay between the time a viewer's ROI is detected by gaze tracking, to the time the effected video is encoded, delivered and displayed at the viewer's terminal. To this end, we use our proposed low-cost gaze prediction system to predict future eye gaze locations, so that optimized bit allocation can be performed for future frames. Through extensive subjective testing, we show that bit-rate can be reduced by up to 29% without noticeable visual quality degradation when RTT is as high as 200 ms.

Error concealment in packet-loss-corrupted streaming video is inherently an under-determined problem, as there are insufficient number of well-defined criteria to recover the missing blocks perfectly. When a Region-of-Interest (ROI) based unequal error protection (UEP) scheme is deployed during video streaming-i.e., more visually salient regions are strongly protected-a lost block is likely to be of low saliency in the original frame. In this paper, we propose to add a low-saliency prior to the error concealment problem as a regularization term. It serves two purposes. First, in ROI-based UEP video streaming, low-saliency prior provides the correct side information for the client to identify the correct replacement blocks for concealment. Second, in the event that a perfectly matched block cannot be unambiguously identified, the low-saliency prior reduces viewer's visual attention on the loss-stricken region, resulting in higher overall subjective quality. We study the effectiveness of a low-saliency prior in the context of a previously proposed RECAP error concealment system. RECAP transmits a low-resolution (LR) version of an image alongside the original high-resolution (HR) version, so that if blocks in the HR version are lost, the correctly-received LR version can serve as a template for matching of suitable replacement blocks from a previously correctly-decoded HR frame. We add a low-saliency prior to the block identification process, so that only replacement candidate blocks with good match and low saliency can be selected. Further, we develop a low-complexity convex approximation to the well known Itti-Koch-Niebur saliency model, which enables the low-saliency error concealment problem to be solved efficiently. Experimental results show that: i) PSNR of the error-concealed frames can be increased dramatically (up to 3.6 dB over the original RECAP), showing the effectiveness of a low-saliency prior in the under-determined error concealment problem; and ii) subjective quality of the repaired video using our proposal, as confirmed by an extensive user study, is better than the original RECAP.

By transmitting texture and depth videos from two adjacent captured viewpoints, a client can synthesize via depth-image-based rendering (DIBR) any intermediate virtual view of the scene, determined by the dynamic movement of the client's head. In so doing, depth perception of the 3D scene will be created through motion parallax. Due to the stringent playback deadline of interactive free viewpoint video, burst packet losses in the texture and depth video streams caused by transmission over unreliable channels are difficult to overcome and can severely degrade the synthesized view quality at the client. We propose a multiple description coding (MDC) of free viewpoint video in texture-plus-depth format that will be transmitted on two disjoint network paths. Specifically, we encode even frames of the left view and odd frames of the right view separately as one description and transmit it on path one. Similarly, we encode odd frames of the left view and even frames of the right view as the second description and transmit it on path two. Appropriate quantization parameters (QP) are selected for each description, such that its data rate matches optimally the available transmission bandwidth on each of the two paths. If the receiver receives one description but not the other due to burst loss on one of the paths, it can still partially reconstruct the missing frames in the loss-corrupted description using a computationally efficient DIBR-based recovery scheme that we design. Extensive experimental results show that our MDC streaming system can outperform the traditional single-path single-description transmission scheme by up to 7dB in Peak Signal-to-Noise Ratio (PSNR) of the synthesized intermediate view at the receiving client.

Light field is a large set of spatially correlated images of the same static scene captured using a 2D array of closely spaced cameras. Interactive light field streaming is the application where a client continuously requests successive light field images along a view trajectory of his choosing, and in response the server transmits appropriate data for the client to correctly reconstruct desired images. The technical challenge is how to encode captured light field images into a reasonably sized frame structure a priori (without knowing eventual clients' view trajectories), so that at stream time, expected server transmission rate can be minimized, while satisfying client's view-switch requests. In this paper, using I-frames, redundant P-frames and distributed source coding (DSC) frames as building blocks, we design coding structures to optimally trade off storage size of the frame structure with expected server transmission rate. The key novelty is to facilitate the use of “landmarks” in the structure-popular reference frames cached in the decoder buffer-so that the probability of having at least one useful predictor frame available in the buffer for disparity compensation is greatly increased. We first derive recursive equations to find the optimal caching strategy for a given coding structure. We then formulate the structure design problem as a Lagrangian minimization, and propose fast heuristics to find near-optimal solutions. Experimental results show that the expected server streaming rate can be reduced by up to 93.6% compared to an I-frame-only structure, at twice the storage required.

In interactive multiview video streaming (IMVS), users can periodically select one out of many captured views available for observation as video is played back in time. In single-view video streaming, to reduce server's upload burden, cooperative strategies where peers share received packets of the same video have proven to be effective, and incentive mechanisms are designed to stimulate user cooperation. Exploiting user cooperation in high dimensional IMVS, however, is more challenging. First, small number of peers in a local area are likely watching different views among large number of views available, making it difficult for a peer to find partners of the exact same view to cooperate. Second, even if a peer can identify cooperative partners of the same view, they will soon be watching different views after independent view-switching. In this paper, we study the use of a multiview video frame structure for IMVS that facilitates cooperative view switching, where even if peers are observing different views, they can nonetheless help each other. To stimulate user cooperation, we model peers' interaction as an indirect reciprocity game. Using Markov decision process (MDP) as a formalism, each peer makes distributed decisions to maximize his aggregate utilities within his lifetime. Simulation results show that when the cost to help others is much smaller than the utility gained from others' help, users fully cooperate. As the cost-to-gain ratio increases, users tend to behave differently at different views: given peers can predict their future view navigation paths probabilistically, a peer likely to enter a view-switching path not requiring others' help will have less incentive to cooperate. When the cost-to-gain ratio is very large, no users will cooperate.

Because of differential coding used in standard video compression algorithms to exploit temporal correlation in adjacent frames for coding gain a frame lost in network will cause error propagation in subsequent frames at the decoder Previously proposed distributed source coding (DSC) frames can be periodically inserted to halt this error propagation by overcoming the uncertainty at encoder of which frames will be correctly received at decoder without resorting to large intra-coded I-frames In the case of interactive multiview video streaming (IMVS) where a user watches one of M available captured views at a time but can periodically select and switch to a neighboring view the encoder must encode multiview video to enable this view-switching interactivity without knowing the exact view trajectories taken by viewers at stream time In this paper we propose a unified DSC frame construction for IMVS so that the encoder can overcome both types of uncertainty in a coding-efficient manner; ie halt error propagation in differentially coded multiview video and facilitate periodic interactive view-switching at the same time Having the additional unified DSC frames we design a multiview frame structure to maximize the expected number of correctly decoded frames at decoder for a given bandwidth constraint We develop a fast algorithm to find locally optimal structure parameters and packetization and packet reordering strategies for transmission Experimental results show that our optimized frame structures using unified DSC frames outperform naïve structures using I- and P-frames only by up to 49% in fraction of correctly decoded frames under typical network condition.

Depth map compression is important for compact representation of 3D visual data in “texture-plus-depth” format, where texture and depth maps of multiple closely spaced viewpoints are encoded and transmitted. A decoder can then freely synthesize any chosen inter-mediate view via depth-image-based rendering (DIBR) using neighboring coded texture and depth maps as anchors. In this work, we leverage on the observation that “pixels of similar depth have similar motion” to efficiently encode depth video. Specifically, we divide a depth block containing two zones of distinct values (e.g., foreground and background) into two sub-blocks along the dividing edge before performing separate motion prediction. While doing such arbitrarily shaped sub-block motion prediction can lead to very small prediction residuals (resulting in few bits required to code them), it incurs an overhead to losslessly encode dividing edges for sub-block identification. To minimize this overhead, we first devise an edge prediction scheme based on linear regression to predict the next edge direction in a contiguous contour. From the predicted edge direction, we assign probabilities to each possible edge direction using the von Mises distribution, which are subsequently inputted to a conditional arithmetic codec for entropy coding. Experimental results show an average overall bitrate reduction of up to 30% over classical H.264 implementation.

Depth map compression is important for efficient network transmission of 3D visual data in texture-plus-depth format, where the observer can synthesize an image of a freely chosen viewpoint via depth-image-based rendering (DIBR) using received neighboring texture and depth maps as anchors. Unlike texture maps, depth maps exhibit unique characteristics like smooth interior surfaces and sharp edges that can be exploited for coding gain. In this paper, we propose a multi-resolution approach to depth map compression using previously proposed graph-based transform (GBT). The key idea is to treat smooth surfaces and sharp edges of large code blocks separately and encode them in different resolutions: encode edges in original high resolution (HR) to preserve sharpness, and encode smooth surfaces in low-pass-filtered and down-sampled low resolution (LR) to save coding bits. Because GBT does not filter across edges, it produces small or zero high-frequency components when coding smooth-surface depth maps and leads to a compact representation in the transform domain. By encoding down-sampled surface regions in LR GBT, we achieve representation compactness for a large block without the high computation complexity associated with an adaptive large-block GBT. At the decoder, encoded LR surfaces are up-sampled and interpolated while preserving encoded HR edges. Experimental results show that our proposed multi-resolution approach using GBT reduced bitrate by 68% compared to native H.264 intra with DCT encoding original HR depth maps, and by 55% compared to single-resolution GBT encoding small blocks.

In a free-viewpoint video conferencing system, the viewer can choose any desired viewpoint of the 3D scene for observation. Rendering of images for arbitrarily chosen viewpoint can be achieved through depth-image-based rendering (DIBR), which typically employs “texture-plus-depth” video format for 3D data exchange. Robust and timely transmission of multiple texture and depth maps over bandwidth-constrained and loss-prone networks is a challenging problem. In this paper, we optimize transmission of multiview video in texture-plus-depth format over a lossy channel for free viewpoint synthesis at decoder. In particular, we construct a recursive model to estimate the distortion in synthesized view due to errors in both texture and depth maps, and formulate a rate-distortion optimization problem to select reference pictures for macroblock encoding in H.264 in a computation-efficient way, in order to provide unequal protection to different macroblocks. Results show that the proposed scheme can outperform random insertion of intra refresh blocks by up to 0.73 dB at 5% loss.

An important question in the design of interactive multiview systems consists in determining the information needed by the decoder for high quality navigation between the views. Most of the existing techniques focus on the captured sequences and only consider their transmission, which does not guarantee consistency among receiver-generated frames of chosen virtual views. In this work, we propose a solution that additional transmits auxiliary information in order to help the construction of synthesized views, especially in the occluded areas. Comparative results with existing approaches validate this novel representation of multiview data for interactive navigation. We show that decoding quality and consistency among frames are improved with only a small share of additional information.

Error concealment in packet-loss-corrupted streaming video is inherently an under-determined problem, as there are insufficient number of well-defined criteria to recover the missing blocks perfectly. When a Region-of-Interest (ROI) based unequal error protection (UEP) scheme is deployed during video streaming -- i.e., more visually salient regions are strongly protected -- a %(e.g., using strong Forward Error Correction (FEC) codes) -- a lost block is likely to be of low saliency in the original frame. In this paper, we propose to add a low-saliency prior to the error concealment problem as a regularization term. It serves two purposes. First, in ROI-based UEP video streaming, low-saliency prior provides the right side information for the client to identify the correct replacement blocks for concealment. Second, in the event that a perfectly matched block cannot be unambiguously identified, the low-saliency prior reduces viewer's visual attention on the loss-stricken region, resulting in higher overall subjective quality. We study the effectiveness of a low-saliency prior in the context of a previously proposed RECAP[1] error concealment system. RECAP transmits a low-resolution (LR) version of an image alongside the original high-resolution (HR) version, so that if blocks in the HR version are lost, the correctly-received LR version can serve as a template for matching of suitable replacement blocks from a previously correctly-decoded HR frame. We add a low-saliency prior to the block identification process, so that only replacement candidate blocks with good match and low saliency can be selected. Further, we design and apply four saliency reduction operators iteratively in a loop, in order to reduce the saliency of candidate blocks. Experimental results show that: i) PSNR of the error-concealed frames can be increased dramatically (up to $3.2$dB over the original RECAP), showing the effectiveness of a low-saliency prior in the under-determined error concealment problem, and ii) subjective quality of the repaired video using our proposal, as confirmed by an extensive user study, is better than the original RECAP.

Multiview video refers to the simultaneous capturing of multiple video views with an array of closely spaced cameras. In an interactive multiview video streaming (IMVS) system, a client can play back the content in time in a single view, and may observe a scene of interest by switching to different viewpoints. Users independently choose their own view navigation paths through the high-dimensional multiview data. Distributed servers are deployed to collaboratively replicate video content in order to support user scalability. Such a system typically presents challenges in both coding and content replication. In coding, the multiview video must be encoded in order to support efficient view-switching and distributed replication. In content replication, it is important to decide which data blocks to store at each server to facilitate view-switches at any time. In this paper, we co-design a coding structure and a distributed content replication strategy. First, we propose a coding structure based on redundant P-frames and distributed source coding (DSC) frames to achieve efficiency in coding, view switches and content replication. We then propose a heuristic-based distributed and cooperative replication strategy to take advantage of the correlation between the multiple views for resource-effective content delivery. Simulation results show that our coding and replication co-design is cost-effective in supporting IMVS services.

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.

When transmitting the so-called “texture-plus-depth” video format, texture and depth maps from the same viewpoint exhibit high correlation. Coded bits from one map can then be used as side information to encode the other. In this paper, we propose to use the depth information to divide the corresponding block in texture map into arbitrarily shaped regions (sub-blocks) for separate motion estimation (ME) and motion compensation (MC). We implemented our proposed sub-block motion prediction (MP) method for texture map coding using depth information as a new coding mode (z-mode) in H.264. Nonetheless, in practical experiments one can observe either a misalignment between texture and depth edges, or an aliasing effect at the texture boundaries. To overcome this issue, z-mode offers two MC types: i) non-overlapping MC, and ii) overlapping MC. In the latter case, overlapped sub-blocks after ME are alpha-blended using a properly designed filter. Moreover, the MV of each sub-block in z-mode is predicted using a Laplacian-weighted average of MVs of neighboring blocks of similar depth. Experimental results show that using z-mode, coding performance of the texture map can be improved by up to 0.7dB compared to native H.264 implementation at high bitrate.

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%.

The ability of a person to perceive image details falls precipitously with larger angle away from his visual focus. At any given bitrate, perceived visual quality can be improved by employing region-of-interest (ROI) coding, where higher encoding quality is judiciously applied only to regions close to a viewer's focal point. Straight-forward matching of viewer's focal point with ROI coding using a live encoder, however, is computation-intensive. In this paper, we propose a system that supports ROI coding without the need of a live encoder. The system is based on dynamic switching between two pre-encoded streams of the same content: one at high quality (HQ), and the other at mixed quality (MQ), where quality of a spatial region depends on its pre-computed visual saliency values. Distributed source coding (DSC) frames are periodically inserted to facilitate switching. Using a Hidden Markov Model (HMM) to model a viewer's temporal gaze movement, MQ stream is pre-encoded based on ROI coding to minimize the expected streaming rate, while keeping the probability of a viewer observing low quality (LQ) spatial regions below an application-specific ϵ. At stream time, the viewer's gaze locations are collected and transmitted to server for intelligent stream switching. In particular, server employs MQ stream only if: i) viewer's tracked gaze location falls inside the high-saliency regions, and ii) the probability that a viewer's gaze point will soon move outside high-saliency regions, computed using tracked gaze data and updated saliency values, is below ϵ. Experiments showed that video streaming rate can be reduced by up to 44%, and subjective quality is noticeably better than a competing scheme at the same rate where the entire video is encoded using equal quantization.

In interactive multiview video streaming (IMVS), a client receives and observes one of many available viewpoints of the same scene and periodically requests from the server view switches to neighboring views, as the video is played back in time uninterruptedly. One key technical challenge is to design a frame coding structure that facilitates periodic view switching and achieves an optimal tradeoff between storage cost and expected transmission rate. In this paper, we first propose three significant improvements over existing IMVS systems and then study the corresponding frame structure optimization. First, using depth-image-based rendering, the new IMVS system enables free viewpoint switching, i.e., by encoding and transmitting both texture and depth maps of captured views, a client can select and synthesize any virtual view from an almost continuum of viewpoints between the left-most and right-most captured views. Second, the IMVS system adopts a more realistic Markovian view-switching model with memory that more accurately captures user behaviors than previous memoryless models . A view-switching model is used in predicting client's future view-switching patterns. Third, assuming that the round-trip-time (RTT) delay during server-client communication is nonnegligible, during an IMVS session, the IMVS system additionally transmits redundant frames RTT into future playback, so that zero-delay view switching can be achieved. Given these improvements, we formalize a new joint optimization of the frame coding structure, transmission schedule, and quantization parameters of the texture and depth maps of multiple camera views. We propose an iterative algorithm to achieve fast and near-optimal solutions. The convergence of the algorithm is also demonstrated. Experimental results show that the proposed optimized rate-allocation method requires 38% lower transmission rate than the fixed rate-allocation scheme. In addition, with the same storage, the transmission rate of the optimized frame structure can be up to 55% lower than that of an I-frame-only structure and 27% lower than that of the structure without distributed source coding frames.

In order to allow sufficient amount of light into the image sen sor, videos captured in poor lighting conditions typically have low frame rate and frame exposure time equals to inter-frame period-commonly called full exposure time (FET). FET low-frame-rate videos are common in situations where lighting cannot be improved a priori due to practical (e.g., large physical distance between camera and captured objects) or economical (e.g., long duration of night-time surveillance) reasons. Previous work in computer vision has shown that content at a desired higher frame rate can be recovered (to some extent) from the captured FET video using self-similarity-based temporal super-resolution. From an end-to-end communication standpoint, however, the following practical question remains: what is the most compact representation of the captured FET video at encoder, given that a higher frame rate reconstruction is desired at the decoder? In this paper, we present a compression strategy, where, for a given targeted rate-distortion (RD) tradeoff, FET video frames at appropriate temporal resolutions are selected for encoding using standard H.264 tools at encoder. At the decoder, temporal super-resolution is performed on the decoded frames to synthesize the desired high frame rate video. We formulate the selection of individual FET frames at different temporal resolutions as a shortest path problem to minimize Lagrangian cost of the encoded sequence. Then, we propose a computation-efficient algorithm based on monotonicity in predictor's temporal resolution to find the shortest path. Experiments show that our strategy outperforms an alternative naive approach of encoding all FET frames as is and performing temporal super-resolution at decoder by up to 1.1dB at the same bitrate.

Video multicast over Wireless Wide Area Networks (WWAN) is difficult because of unavoidable packet losses and impracticality of retransmission on a per packet, per client basis, due to the known NAK implosion problem. Recent approach exploits clients' cooperation for packet recovery, so that a peer group's received WWAN packets are shared using a secondary network like Wireless Local Area Network (WLAN). For multiview video multicast, where a client can switch views interactively by subscribing to different WWAN multicast channels streaming different views, two new difficulties arise. First, system must provide timely view-switching mechanism, so that client can switch to a desired view quickly for correct decoding and display. Second, it is difficult for system to leverage neighboring peers for cooperative loss recovery, since neighbors are more likely to be subscribing to different views than a loss-stricken peer. In this paper, we use Distributed Source Coding (DSC), a new compression tool in video coding, to solve both problems. Each DSC frame is encoded with a set of predictor frames, and correct decoding only requires one of the predictors in the set to be available at decoder. Periodic insertion of DSC frames into video streams then enables a peer to switch from view v to v' at the DSC frame boundary, assuming DSC frame of view v' was encoded using a frame in view v as one predictor. For the same assumption, a neighbor watching view v can help a peer watching view v' evade error propagation resulting from earlier losses and resume decoding at the DSC boundary. Experiments show that optimized usage of DSC frames in a coding structure, where unequal error protection is enabled to decrease the probability of decoding failure earlier in a group of pictures, outperforms a structure using I-frames instead for view switching by up to 11 dB in video quality in typical WWAN network loss environment.

To provide live streaming service to mobile users, traditionally each user pulls content from a server over his cellular network. In order to overcome the scalability problem of last-hop bandwidth bottleneck, mobile peer-to-peer (P2P) streaming can be used where mobile devices relay their stream received in a multi-hop manner by means of a secondary channel (such as Wi-Fi or bluetooth). We investigate the design of distributed algorithm termed LocalTree, which minimizes the number of broadcasters while meeting a certain video quality requirement under peer churns. We first formulate the problem and show that it is NP-hard, and hence propose LocalTree which achieves robustness similar to an unstructured mesh and low delay similar to a global tree. Simulation results show that LocalTree outperforms other algorithms substantially in terms of number of broadcasters used (by as much as 50%).

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.

In order to allow sufficient amount of light into the image sensor, videos captured in poor lighting conditions typically have low frame rate and frame exposure time equals to inter-frame period - commonly called full exposure time (FET). FET low-frame-rate videos are common in situations where lighting cannot be improved a priori due to practical (e.g., large physical distance between camera and captured objects) or economical (e.g., long duration of nighttime surveillance) reasons. Previous computer vision work has shown that content at a desired higher frame rate can be recovered (to some degree of precision) from the captured FET video using self-similarity-based temporal super-resolution. For a network streaming scenario, where a client receives a FET video stream from a server and plays back in real-time, the following practical question remains, however: what is the most suitable representation of the captured FET video at encoder, given that a video at higher frame rate must be constructed at the decoder at low complexity? In this paper, we present an adaptive frame and quantization parameter (QP) selection strategy, where, for a given targeted rate-distortion (RD) tradeoff, FET video frames at appropriate temporal resolutions and QP are selected for encoding using standard H.264 tools at encoder. At the decoder, temporal super-resolution is performed at low complexity on the decoded frames to synthesize the desired high frame rate video for display in real-time. We formulate the selection of individual FET frames at different temporal resolutions and QP as a shortest path problem to minimize Lagrangian cost of the encoded sequence. Then, we propose a computation-efficient algorithm based on monotonicity in predictor's temporal resolution and QP to find the shortest path. Experiments show that our strategy outperforms alternative naıve non-adaptive approaches by up to 1.3dB at the same bitrate.

Irrecoverable data loss is inevitable for low-delay video conferencing over typical loss-prone networks such as the Internet. A semi-super-resolution (SSR) framework has been previously proposed to supply an additional low-resolution (LR) thumbnail to aid error concealment when the high-resolution (HR) image is lost. Super-resolution is an ill-posed problem, however, and previous block-search based SSR methods tend to produce discontinuities in output images, which can be objectionable, especially in human faces where the focus of a viewer usually lies. In this paper, we propose to recover a human face in a lost frame using the same SSR framework, but by operating on the entire face at a time. We leverage on a recent work called robust principal component analysis (RPCA), where the “salient” features (human face in our scenario) in a sequence of previous HR frames can be recovered despite the presence of gross but sparse errors. We propose and derive various improved methods to solve the SSR problem using RPCA. Beyond robust recovery of the human face, transformations of the face in previous HR frames are also deduced, so that the recovered face can be appropriately transformed in the lost frame for natural viewing. Experimental results show that our face-based approach gives much improved face recovery compared to previous SSR block searches.

Interactive multiview video streaming (IMVS) is an application that streams to a client one out of N available video views for observation, but client can periodically request switches to neighboring views as the video is played back uninterrupted in time. Previous IMVS works focused on the design of a frame structure at encoding time, trading off expected transmission rate with storage, without knowing the exact view trajectory a client may select at stream time. None of the existing IMVS schemes, however, explicitly addressed the network delay problem, and so a client will suffer a round trip time (RTT) delay for each requested view-switch. In this pa- per, we optimize frame structure for a bounded RTT, so that a client can switch to neighboring views as the video is played back without view-switching delay. The key idea is to send additional views likely to be requested by a client within one RTT beyond the current requested view. Each required set of contiguous views (corresponding to a given current requested single view) are pre-encoded using frames of previously transmitted set of views as predictors to lower transmission rate. Using I-, P- and distributed source coding (DSC) frames, we first formulate the structure design problem as a Lagrangian minimization for a desired bandwidth/storage tradeoff. We then develop a low-complexity greedy algorithm to automatically generate a good structure. Experimental results show that for the same storage cost, the transmission rate of the proposed structure can be 42% lower than that of I-frame-only structure, and 8% lower than that of the structure without DSC frames.

Light field is a large set of spatially correlated images of the same static scene captured using a 2D array of closely spaced cameras. Interactive light field streaming is the application where a client continuously requests successive light field images along a view trajectory of her choosing, and in response the server transmits appropriate data for the client to correctly reconstruct desired images. The technical challenge is how to encode captured light field images into a reasonably sized frame structure a priori (without knowing eventual clients' view trajectories), so that during streaming session, expected server transmission rate can be minimized, while satisfying client's view requests. In this paper, we design efficient frame structures, using I-frames, redundant P-frames and distributed source coding (DSC) frames as building blocks, to optimally trade off storage size of the frame structure with expected server transmission rate. The key novelty is to optimize structures in such a way that decoded images in caches of neighboring cooperative peers, connected together via a secondary network such as ad hoc WLAN for content sharing, can be reused to further decrease the server-to-client transmission rate. We formulate the structure design problem as a Lagrangian minimization, and propose fast heuristics to find near-optimal solutions. Experimental results show that the expected server streaming rate can be reduced by up to 83% compared to an I-frame-only structure, at less than twice the storage required.

With the advent of eye gaze tracking technology, eye gaze is increasingly being used as a media interaction trigger in a variety of applications, such as eye typing, video content customization, and network video streaming based on region-of-interest (ROI). The reaction time of a gaze-based networked system, however, is in practice lower-bounded by the round trip time (RTT) of today's networks, which can be large. To improve the efficacy of gaze-based networked systems, in the paper we propose a Hidden Markov Model (HMM)-based gaze prediction strategy to predict future gaze locations to lower end-to-end reaction delay. We first design an HMM with three states corresponding to human's three major types of intrinsic eye movements. HMM parameters are obtained offline on a per-video basis during training phase. During testing phase, a window of noisy gaze observations are collected in real-time as input to a forward algorithm, which computes the most likely HMM state. Given the deduced HMM state, linear prediction is used to predict gaze location RTT seconds into the future. We demonstrate the applicability of our gaze prediction strategy by focusing on ROI-based bit allocation for network video streaming. To reduce transmission rate of a video stream without degrading viewer's perceived visual quality, we allocate more bits to encode the viewer's current spatial ROI, while devoting fewer bits in other spatial regions. The challenge lies in overcoming the delay between the time a viewer's ROI is detected by gaze tracking, to the time the effected video is encoded, delivered and displayed at the viewer's terminal. To this end, we use our proposed gaze-prediction strategy to predict future eye gaze locations, so that optimized bit allocation can be performed for future frames. Our experiments show that bit rate can be reduced by 21% without noticeable visual quality degradation when end-to-end network delay is as high as 200ms.

Error resilient video broadcast over Wireless Wide Area Networks (WWAN) remains difficult due to unavoidable packet losses (a result of the underlying unreliable and time-varying transmission medium) and unavailability of per-packet, per-user retransmissions (stemming from the well-known NAK implosion problem). Previous cooperative solutions for multi-homed devices listening to the same video broadcast call for local recovery via packet sharing: assuming peers are physically located more than one transmission wavelength apart, channels to the streaming source are statistically independent, and peers can exchange different subsets of received packets with neighbors via a secondary network like ad hoc Wireless Local Area Net work (WLAN) to alleviate individual WWAN packet losses. While it is known that using structured network coding (SNC) to encode received packets before peer exchange can further improve packet repair performance, the decisions of who should send repair packets encoded in what SNC types at available transmission opportunities were not optimized in any formal way. In this paper, we propose a distributed decision making strategy based on Markov decision process (MDP), so that each peer can make locally optimal transmission decisions based on observations eavesdropped on the WLAN channel. Our proposed MDP is both computationally scalable and peer-adaptive, so that state transition probabilities in MDP can be appropriately estimated based on observed aggregate behavior of other peers. Experiments show that decisions made using our proposed MDP outperformed decisions made by a random scheme by at least 4dB in PSNR in received video quality.

“Texture-plus-depth” has become a popular coding format for multiview image compression, where a decoder can synthesize images at intermediate viewpoints using encoded texture and depth maps of closest captured view locations via depth-image-based rendering (DIBR). As in other resource-constrained scenarios, limited available bits must be optimally distributed among captured texture and depth maps to minimize the expected signal distortion at the decoder. A specific challenge of multiview image compression for DIBR is that the encoder must allocate bits without the knowledge of how many and which specific virtual views will be synthesized at the decoder for viewing. In this paper, we derive a cubic synthesized view distortion model to describe the visual quality of an interpolated view as a function of the view's location. Given the model, one can easily find the virtual view location between two coded views where the maximum synthesized distortion occurs. Using a multiview image codec based on shape-adaptive wavelet transform, we show how optimal bit allocation can be performed to minimize the maximum view synthesis distortion at any intermediate viewpoint. Our experimental results show that the optimal bit allocation can outperform a common uniform bit allocation scheme by up to 1.0dB in coding efficiency performance, while simultaneously being competitive to a state-of-the-art H.264 codec.

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.

Receivers of wireless video broadcast can suffer catastrophic decoding errors when experiencing heavy packet losses due to transmission channel fades. Cooperative repair schemes, exploiting the "uncorrelatedness" in wireless channels of peers physically located more than one transmission wavelength apart, call for neighboring peers listening to the same video stream to locally share received packets via a secondary network. Since the likelihood of the entire peer group suffering fades in statistically independent channels at the same time is very small, cooperative peers can collectively recover lost packets via local packet sharing with high probability. For interactive multiview video streaming (IMVS), where a client receives and watches only one periodically selected view out of N available, the packet recovery problem is more challenging, since the likelihood of a neighboring cooperative peer watching the same view as a channel-corrupted peer is now 1/N. To enable cooperative recovery even when neighboring peers are watching different but correlated video views, cleverly designed redundantly coded in formation (RCI) such as Distributed Source Coded (DSC) frames are inserted into streams of different views. On one hand, RCI in the video streams promotes cooperative repair among peers watching different views; on the other, it leaves fewer available bits for channel coding, given a fixed transmission budget, to combat channel noise. In this paper, using game theoretical analysis, we search for the optimal amount of RCI in the video streams to foster the right balance between cooperation among peers and leftover bits for channel coding to maximize decoding success. Experimental results show that expected video decoding probability can be increased noticeably compared to non-optimized resource allocation schemes.

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.

Error resilient video multicast over Wireless Wide Area Networks (WWAN) is difficult because of unavoidable packet losses and impracticality of retransmission on a per packet, per client basis due to the well-known NAK implosion problem. In response, Cooperative Peer-to-peer Repair (CPR) calls for multi-homed devices listening to the same video multicast to locally exchange received WWAN packets via a secondary network like ad hoc Wireless Local Area Network (WLAN) to alleviate individual WWAN packet losses. When videos of the interested 3D scene are captured by multiple closely spaced cameras, each video can be encoded into a separate video stream and transmitted on its own WWAN multicast channel. Clients can then switch observation viewpoints periodically by simply re-subscribing to different WWAN multicast channels- a scenario called interactive multiview video streaming (IMVS). IMVS complicates the CPR WWAN loss recovery process, however, since neighbors of a loss-stricken peer can now be watching different views. In this paper, we optimize the decision process for individual peers during CPR for recovery of multiview video content in IMVS. In particular, for each available transmission opportunity, a peer decides-using Markov decision process as a mathematical formalism-whether to transmit, and if so, how the CPR packet should be encoded using structured network coding (SNC). A loss-stricken peer can then either recover using received CPR packets of the same view, or using packets of two adjacent views and subsequent view interpolation via image-based rendering. Experiments show that decisions made using our proposed MDP outperforms decisions made by a random scheme by at least 1.8dB in PSNR in received video quality in typical network scenario.

Because of unavoidable wireless packet losses and inapplicability of retransmission-based schemes due to the well-known negative acknowledgment implosion problem, providing high quality video multicast over wireless wide area networks (WWAN) remains difficult. Traditional joint source/channel coding (JSCC) schemes for video multicast target a chosen th-percentile WWAN user. Users with poorer reception than th-percentile user (poor users) suffer substantial channel losses, while users with better reception (rich users) have more channel coding than necessary, resulting in sub-optimal video quality. In this paper, we recast the WWAN JSCC problem in a new setting called cooperative peer-to-peer repair (CPR), where users have both WWAN and wireless local area network (WLAN) interfaces and use the latter to exchange received WWAN packets locally. Given CPR can mitigate some WWAN losses via cooperative peer exchanges, a CPR-aware JSCC scheme can now allocate more bits to source coding to minimize source quantization noise without suffering more packet losses, leading to smaller overall visual distortion. Through CPR, this quality improvement is in fact reaped by all peers in the collective, not just a targeted th-percentile user. To efficiently implement both WWAN forward error correction and WLAN CPR repairs, we propose to use network coding for this dual purpose to reduce decoding complexity and maximize packet recovery at the peers. We show that a CPR-aware JSCC scheme dramatically improves video quality: by up to 8.7 dB in peak signal-to-noise ratio for the entire peer group over JSCC scheme without CPR, and by up to 6.0 dB over a CPR-ignorant JSCC scheme with CPR.

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.

For low-delay streaming of pre-encoded video over lossy networks, fast recovery from decoding errors typically involves use of frequent intra-coded frames, which incurs high bandwidth cost. In this paper, we present a redundant representation of video using a bandwidth-efficient but non-resilient main bitstream, and an additional auxiliary bitstream dedicated to recovery from losses in the main bitstream. In particular, we insert primary SP-frames periodically into the main bitstream, and encode corresponding secondary SP-frames and reconstructed P-frames in the auxiliary stream. When a frame loss occurs, a reconstructed P-frame is first sent to re-synchronize decoder back to normal motion compensation loop, then a secondary SP-frame corresponding to the location of the next pre-inserted primary SP-frame in the main stream is sent thereafter, eliminating coding drift. Results show that proposed method out-performs non-redundant representation of I-frame insertion by up to 11 frames in recovery time, and out-performed redundant representation of only reconstructed P-frames by up to 2.2dB in average PSNR.

By exploiting multiple network interfaces on one device, e.g., Wireless Wide Area Network (WWAN) and Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast/multicast packets can perform Cooperative Peer-to-peer Repair (CPR) by exchanging received WWAN packets with their local WLAN peers. This effectively improves the transmission success from a WWAN broadcast/multicast source to a CPR collective. In this paper, we propose a novel joint source/channel bit allocation scheme for WWAN scalable video multicast that leverages the CPR paradigm. One key observation is that given a peer can successfully receive a packet either from theWWAN channel directly, or via a CPR neighbor using ad-hoc WLAN connections, more bits can be redistributed from channel to source coding out of a fixed WWAN bit budget to further minimize individual node's expected visual distortion. In our proposal, groups of peers requiring different video resolutions are assigned to the same multicast group, and we perform one WWAN resource allocation and subsequent CPR over heterogeneous peers of different resolutions together. Our simulations show that our joint multicast group optimization can improve video quality by up to 2.84 dB, compared to a scheme where both WWAN resource allocation and WLAN CPR are separately performed for heterogeneous peers.

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.

The encoding of both texture and depth maps of a set of multi-view images, captured by a set of spatially correlated cameras, is important for any 3D visual communication systems based on depth-image-based rendering (DIBR). In this paper, we address the problem of efficient bit allocation among texture and depth maps of multi-view images. We pose the following question: for chosen (1) coding tool to encode texture and depth maps at the encoder and (2) view synthesis tool to reconstruct uncoded views at the decoder, how to best select captured views for encoding and distribute available bits among texture and depth maps of selected coded views, such that visual distortion of a “metric” of reconstructed views is minimized. We show that using the monotonicity assumption, suboptimal solutions can be efficiently pruned from the feasible space during parameter search. Our experiments show that optimal selection of coded views and associated quantization levels for texture and depth maps can outperform a heuristic scheme using constant levels for all maps (commonly used in the standard implementations) by up to 2.0dB. Moreover, the complexity of our scheme can be reduced by up to 66% over full search without loss of optimality.

Recent research has exploited the multi-homing property (one terminal with multiple network interfaces) of modern devices to improve communication performance in wireless networks. Cooperative Peer-to-peer Repair (CPR) is one example where given simultaneous connections to both a Wireless Wide Area Network (WWAN) and an ad-hoc Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast packets can exchange received WWAN packets with their ad-hoc WLAN peers for local recovery. In our previous work, we have shown that by using Network Coding (NC) to linearly combine received packets into new CPR packets for local exchanges, packet recovery can be improved. Moreover, by imposing Structure on Network Coding (SNC) when encoding a CPR packet, decoding of at least the important packets becomes possible in the event when insufficient number of CPR packets were received for full recovery. Given SNC is used during CPR, the key decision for each peer is to determine which SNC type to encode a repair packet at each WLAN transmission opportunity. The decision is further complicated by the observation that peers in general receive different numbers of CPR packets from neighbors due to varying amount of WLAN link contentions and interference experienced. In this paper, we propose a novel counter-based deterministic SNC type selection scheme. Using this approach, we show that a simple local optimization procedure, taking advantage of available neighbors' state information, can be easily implemented to further improved CPR performance. Simulation results show that our proposed scheme outperformed our previous randomized SNC type selection scheme by up to 1.87dB.

Novel coding tools have been proposed recently to encode texture and depth maps of multiview images, exploiting inter-view correlations, for depth-image-based rendering (DIBR). However, the important associated bit allocation problem for DIBR remains open: for chosen view coding and synthesis tools, how to allocate bits among texture and depth maps across encoded views, so that the fidelity of a set of V views reconstructed at the decoder is maximized, for a fixed bitrate budget? In this paper, we present an optimization strategy to select subset of texture and depth maps of the original V views for encoding at appropriate quantization levels, so that at the decoder, the combined quality of decoded views (using encoded texture maps) and synthesized views (using encoded texture and depth maps of neighboring views) is maximized. We show that using the monotonicity property, complexity of our strategy can be greatly reduced. Experiments show that using our strategy, one can achieve up to 0.83dB gain in PSNR improvement over a heuristic scheme of encoding only texture maps of all V views at constant quantization levels. Further, computation can be reduced by up to 66% over a full parameter search approach.

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.

We consider the scenario of view synthesis via depth-image based rendering in multi-view imaging. We formulate a resource allocation problem of jointly assigning an optimal number of bits to compressed texture and depth images such that the maximum distortion of a synthesized view over a continuum of viewpoints between two encoded reference views is minimized, for a given bit budget. We construct simple yet accurate image models that characterize the pixel values at similar depths as first-order Gaussian auto-regressive processes. Based on our models, we derive an optimization procedure that numerically solves the formulated min-max problem using Lagrange relaxation. Through simulations we show that, for two captured views scenario, our optimization provides a significant gain (up to 2dB) in quality of the synthesized views for the same overall bit rate over a heuristic quantization that selects only two quantizers — one for the encoded texture images and the other for the depth images.

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.

In the above titled paper (ibid., vol. 11, no. 4, pp. 730-741, Jun. 09), simulation errors were discovered. This errata outlines a corrective derivation and presents updated simulation results.

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.

Because of frequent wireless packet losses and inapplicability of retransmission-based schemes due to the wellknown NAK implosion problem, providing high quality video multicast over wireless wide area networks (WWAN) remains difficult. Traditional joint source/channel coding schemes for video multicast-optimal bit allocation among source coding and channel coding such as forward error correction (FEC) subject to a bitrate constraint-target a chosen nth-percentile WWAN user. Not only is FEC bitwise expensive, users with poorer reception than nth-percentile user suffer substantial channel losses, while users with better reception have more channel coding than necessary, meaning too few bits are devoted for source coding to reduce quantization noise and sub-optimal video quality. Instead, in this paper we perform joint source/channel coding of WWAN video multicast for an entire collective of multi-homed ad-hoc peers in the same multicast group and connected via wireless local area networks (WLAN). In a cooperative peer-to-peer repair (CPR) scenario, after each peer received a different subset of WWAN packets, the peer group repairs WWAN losses locally by packet-forwarding to each other via WLAN. From an end-to-end system view, CPR means that a packet can be transmitted from source to a peer either via WWAN directly, or via WLAN local repairs exploiting neighboring peers' WWAN links; the overall more general transmission condition means a clever joint source/channel coding scheme can now allocate more bits to source coding without suffering more packet losses, leading to higher video quality. To efficiently implement both WWAN FEC and WLAN CPR repairs, we propose to use network coding for this dual purpose to reduce decoding complexity at the peers. We show through simulations that using our proposed scheme dramatically improves video quality over existing optimization scheme where joint source/channel coding was performed, but WLAN CPR was not used, by up to 8.4 dB, and over scheme when WLAN CPR and WWAN joint source/channel coding were performed separately by up to 4.4 dB.

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 a scenario where each peer of an ad-hoc wireless local area network (WLAN) receives one of many available video streams from a wireless wide area network (WWAN), we propose a network-coding-based cooperative repair framework for the ad-hoc peer group to improve broadcast video quality during channel losses. Specifically, we first impose network coding structures globally, and then select the appropriate video streams and network coding types within the structures locally, so that repair can be optimized for broadcast video in a rate-distortion manner. Innovative probability—the likelihood that a repair packet is useful in data recovery to a receiving peer—is analyzed in this setting for accurate optimization of the network codes. Our simulation results show that by using our framework, video quality can be improved by up to 19.71 dB over un-repaired video stream and by up to 5.39 dB over video stream using traditional unstructured network coding.

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).

Multimedia Broadcast/Multicast Service (MBMS) allows a common broadcast channel to be shared by users interested in identical content. We explore the problem of enhancing MBMS resilience by repairing packets lost during broadcast. Since MBMS broadcast consumes expensive 3G resources, we leverage the ubiquity of multi-homed mobile devices i.e., devices having both cellular and IEEE 802.11 wireless interfaces. We thus accomplish out-of-band repair of MBMS packet losses through an ad-hoc, peer-to-peer 802.11-based network. A fundamental challenge in scheduling repair transmissions is handling interference between distributed nodes. We present DiCoR, a fully distributed protocol for CPR. Our protocol does not assume any a priori knowledge of the network topology or peer losses, and is resilient to dynamic network changes due to node mobility or the continuous joining and leaving of peers. Detailed simulation experiments, under realistic loss models and network conditions, demonstrate that DiCoR presents a viable solution for timely out-of-band loss repair of MBMS real-time broadcast.

Cooperative Peer-to-Peer Repair (CPR) has been proposed to recover from packet losses incurred during 3G broadcast. CPR leverages the increasing presence of multi-homed mobile devices having both 3G cellular and IEEE 802.11 wireless interfaces. Mobile devices can, therefore, draw upon IEEE 802.11 peering links to cooperatively achieve out-of-band repair of 3G broadcasting losses. This paper considers the problem of employing Network Coding (NC) to exploit the broadcast nature of the wireless medium towards enhancing the efficiency of CPR. We show that the minimum latency scheduling problem for NC based CPR (NC-CPR) is NP-Hard. We present heuristics for NC-CPR that assume a priori topology and packet loss information. Insights gained from our heuristics are leveraged to propose NC-DCPR, a fully distributed protocol for NC-CPR. We conduct extensive simulation experiments under realistic network conditions. Our results show that employing network coding significantly improves the efficiency of CPR.

This paper studies the temporal error propagation of small errors in a single frame for H.264 video. Such small errors can arise due to imperfect recovery from loss, e.g., through error concealment. The key contribution of this paper include demonstrating empirically that small errors tend to amplify over time, and is primarily caused by rounding errors in motion compensation and selective application of deblocking filter based on thresholding. Some methods of reducing error amplification is also presented.

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.

By providing coding ability at intermediate nodes, network coding has been shown to improve throughput in wireless broadcast/multicast networks. Considering a scenario where wireless ad-hoc peers cooperatively relay packets to each other to recover packets lost during MBMS broadcast, we show that by first imposing coding structures globally and then selecting the appropriate types within the structures locally, network coding can be optimized for video streaming in a rate-distortion manner. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71 dB over un-repaired video stream and by up to 8.34 dB over video stream using traditional unstructured network coding.

By providing coding ability at intermediate nodes, network coding has been shown to improve network throughput in broadcast/multicast wireless networks. In this paper, we show that by imposing coding structure, network coding can be further optimized specifically for video streaming in a rate-distortion manner, in a scenario where wireless adhoc peers cooperatively relay packets to each other to repair packet losses during MBMS broadcast. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71dB over un-repaired video stream and by up to 7.90dB over video stream using traditional unstructured network coding.

A key challenge to low-latency wireless video streaming, where persistent retransmission is impractical, is error control. While SP-frame adaptation of H.264 has potential to mitigate error propagation, streaming server is often either situated too far to react in a timely fashion to client feedbacks, or too computationally constrained to perform the necessarily complex adaptation simultaneously for multiple clients in different sessions. In this paper, we present an innovative error control mechanism using SP-frames of H.264 and performed by a network intermediary for video streaming to a wireless client. Using an intermediary means it is more responsive to client feedbacks due to its close proximity, and it can offload computation complexity from the streaming server. Simulation shows that about 2 dB improvement in PSNR is achievable for video streaming with low latency requirements over traditional schemes using I and P-frames only.

This paper explores how to leverage IEEE802.11-based cooperative peer-to-peer repair (CPR) to enhance the reliability of wireless multimedia broadcasting. We first formulate the CPR problem and present an algorithm that assumes global state information to optimally schedule CPR transmissions. Based on insights gained from the optimal algorithm, we propose a fully distributed CPR (DCPR) protocol. Simulation results demonstrate that the DCPR protocol can effectively enhance the reliability of wireless broadcast services with a repair latency comparable to that of optimal scheduling.

Recent video coding standards such as H.264 offer the flexibility to select reference frames during motion estimation for predicted frames. In this paper, we study the optimization problem of jointly selecting the best set of reference frames and their associated transport QoS levels in a multipath streaming setting. The application of traditional Lagrangian techniques to this optimization problem suffers from either bounded worst case error but high complexity or low complexity but undetermined worst case error. Instead, we present two optimization algorithms that solve the problem globally optimally with high complexity and locally optimally with lower complexity. We then present rounding methods to further reduce computation complexity of the second dynamic programming-based algorithm at the expense of degrading solution quality. Results show that our low-complexity dynamic programming algorithm achieves results comparable to the optimal but high-complexity algorithm, and that gradual tradeoff between complexity and optimization quality can be achieved by our rounding techniques

SP-frame is a new picture type of H.264 that can identically reconstruct a picture using any one of several reference frames. In this paper, we discuss how this property can be exploited for controlling error propagation caused by packet losses. We first illustrate the benefits of the scheme through example. We then present results for optimized streaming where PSNR performance of a proposed usage of SP-frames is compared to that of P-frames only. Results show that using SP-frames can noticeably reduce distortion caused by burst packet losses compare to schemes based on P-frames only.

Modern mobile devices are multi-homed with WLAN and WWAN communication interfaces. In a community of nodes with such multi-homed devices-locally inter-connected via high-speed WLAN but each globally connected to larger networks via low-speed WWAN, striping high-volume traffic from remote large networks over a bundle of low speed WWAN links can overcome the bandwidth mismatch problem between WLAN and WWAN. In our previous work, we showed that a packet striping system for such multi-homed devices-a mapping of delay-sensitive packets by an intermediate gateway to multiple channels using combination of retransmissions (ARQ) and forward error corrections (FEC)-can dramatically enhance the overall performance. In this paper, we improve upon a previous algorithm in two respects. First, by introducing two-tier dynamic programming tables to memoize computed solutions, packet striping decisions translate to simple table lookup operations given stationary network statistics. Doing so drastically reduces striping operation complexity. Second, new weighting functions are introduced into the hybrid ARQ/FEC algorithm to drive the long-term striping system evolution away from pathological local minima that are far from the global optimum. Results show the new algorithm performs efficiently and gives improved performance by avoiding local minima compared to the previous algorithm

Video coding standards like H.264 offer the flexibility to select reference frames during motion estimation for predicted frames. We investigate the packet scheduling problem of streaming video over lossy networks from a real-time encoder with flexible reference frame. In particular, we consider a multi-path streaming setting where each predicted frame of video, in addition to the flexibility to select a reference frame, can schedule one or multiple transmissions on one or multiple delivery paths for the upcoming optimization period. We present an algorithm based on dynamic programming that provides a locally optimal solution with high complexity. We then present a rounding method to reduce computation complexity at the expense of degrading solution quality. Results show that our algorithm performs noticeably better than a greedy scheme, and graceful tradeoff between complexity and solution quality can be achieved

In a multi-source video streaming system, premature draining of low-power nodes can cause sudden failures of peer connections and degrade streaming performance. To solve this problem, we propose an energy-aware scheduling (EAS) scheme to better distribute the streaming load among different peers by jointly considering network conditions and node energy levels. We model the proposed scheme using a rate/energy-distortion optimization framework and heuristically solve it using the concept of asynchronous clocks. Simulation studies show that the proposed EAS scheme can achieve comparable streaming quality while consuming less energy.

Unlike non-time-critical applications like email and file transfer, network games demand timely data delivery to maintain the seemingly interactive presence of players in the virtual game world. Yet the inherently large transmission delay mean and variance of 3G cellular links make on-time game data delivery difficult. Further complicating the timely game data delivery problem is the frequent packet drops at these links due to inter-symbol interference, fading and shadowing at the physical layer. In this paper, we propose a proxy architecture that enhances the timeliness and reliability of data delivery of interactive games over 3G wireless networks. In particular, a performance enhancing proxy is designed to optimize a new time-critical data type—variable-deadline data, where the utility of a datum is inversely proportional to the time required to deliver it. We show how a carefully designed and configured proxy can noticeably improve the delivery of network game data.

Multi-homed mobile devices have multiple wireless communication interfaces, each connecting to the Internet via a low speed and bursty WAN link such as a cellular link. We propose a packet striping system for such multi-homed devices — a mapping of packets by agateway to multiple channels, such that the overall performance is enhanced. We model and analyze the striping of delay-sensitive packets over multiple burst-loss channels. We derive the expected packet loss ratio when FEC (Forward Error Correction) and retransmissions are applied for error protection over multiple channels. We next model and analyze the case when the channels are bandwidth-limited. We develop a dynamic programming based algorithm that solves the optimal striping problem for the ARQ, the FEC, and the hybrid FEC/ARQ case.

Recent video coding standards such as H. 264 offer the flexibility to select reference frames during motion estimation for predicted frames. In this paper, by tracking loss compensation during distortion minimization, we improve upon an earlier proposal to jointly select reference frame, level of QoS and transmission path for each video frame in a multi-path streaming scenario. An algorithm that efficiently calculates the loss compensation value of an earlier correctly decodeable frame during error concealment is presented. Results show significant streaming quality improvement when loss compensation is used.

Multi-homed mobile devices have multiple wireless communication interfaces, each connecting to the Internet via a long range but low speed and bursty WAN link such as a cellular link. We propose a packet striping system for such multi-homed devices - a mapping of delay-sensitive packets by an intermediate gateway to multiple channels, such that the overall performance is enhanced. In particular, we model and analyze the striping of delay-sensitive packets over multiple burst-loss channels with random delays. We first derive the expected packet loss ratio when forward error correction (FEC) is applied for error protection over multiple channels. We next model and analyze the case when the channels are bandwidth-limited with shifted-gamma-distributed transmission delays. We develop a dynamic programming-based algorithm that solves the optimal striping problem for the ARQ, the FEC, and the hybrid FEC/ARQ case.

SP-frame is a new picture type supported by H.264. The traditional usage of SP-frames is for switching between different compressed bit-streams. In this paper, we proposed and evaluated a scheme that uses SP frames as a mechanism to switch within a single compressed stream for the purpose of achieving error resilience and rate scalability. We have only considered the restricted but practical case in which only one secondary SP frame is allowed for every primary SP frame. Nevertheless, simulation results show that the technique can significantly increase the chance of video frames meeting their deadlines, and also improve overall PSNR.

Feedback adaptation has been the basis for many media streaming schemes, whereby the media being sent is adapted in real time according to feedback information about the observed network state and application state. Central to the success of such adaptive schemes, the feedback must: 1) arrive in a timely manner and 2) carry enough information to effect useful adaptation. In this paper, we examine the use of feedback adaptation for media streaming in 3G wireless networks, where the media servers are located in wired networks while the clients are wireless. We argue that end-to-end feedback adaptation using only information provided by 3G standards is neither timely nor contain enough information for media adaptation at the server. We first show how the introduction of a streaming agent (SA) at the junction of the wired and wireless network can be used to provide useful information in a timely manner for media adaptation. We then show how optimization algorithms can be designed to take advantage of SA feedbacks to improve performance. The improvement of SA feedbacks in peak signal-to-noise ratio is significant over nonagent-based systems.

In addition to network congestion, a link/node failure is another major cause of performance degradation for video streaming over the Internet. Such failures may be followed by a long routing instability period, during which packets can be black-holed due to invalid paths or caught in routing loops. This paper proposes a routing proxy approach to improve media streaming adaptation against both link/node failures and network congestion. In particular, we first argue that it is important to distinguish between network performance degradation due to network congestion versus link/node failures, and then model link/node failures using empirical models derived from measurements. We then show how by means of proper congestion control, such timely notifications from the network layer can be exploited at the streaming server to improve the performance of a rate-adaptive automatic retransmission request (ARQ) video streaming scheme. Simulation results show that a rate-adaptive streaming scheme using feedbacks from our proposed proxy can recover much faster from link/node failures than a scheme without such feedbacks.

This paper proposes a joint server/peer video streaming architecture for wireless networks, where a receiver can access a video server via an access point using the infrastructure mode and at the same lime communicate with its peers using the ad hoc mode of its IEEE 802.11 interface card. We introduce a joint infrastructure/peer-to-peer, receiver-driven streaming scheme, and formulate it as a combinatorial optimization problem. We decouple the problem into two steps: first selecting the sender (server or peer) by introducing asynchronous clocks, and then applying point-to-point rate-distortion optimization algorithm between a specific sender-receiver pair. Simulation results show that our joint approach has better performance than those systems with single server or with round-robin selection scheme.

A network agent located at the junction of wired and wireless networks can provide additional feedback information to streaming media servers to supplement feedbacks from clients. Specifically, it has been shown that feedbacks from the network agent have lower latency, and they can be used in conjunction with client feedbacks to effect proper congestion control. In this work, we propose the double-feedback streaming agent (DFSA) which further allows the detection of discrepancies in the transmission constraints of the wired and wireless networks. By working together with the streaming server and client, DFSA reduces overall packet losses by exploiting the excess capacity Of the path with more capacity. We show how DFSA can be used to support three modes of operation tailored for different delay requirements of streaming applications. Simulation results under high wireless latency show significant improvement of media quality using DFSA over non-agent-based and earlier agent-based streaming systems.

New video coding standards such as H.264 offer the flexibility to select from a number of reference frames for motion-estimation for a given predicted frame. In this paper, we propose an optimization algorithm using dynamic programming that exploits this flexibility for multipath streaming simultaneously streaming over two transmission paths with different bandwidths and loss rates. A rounding technique is employed to scale the complexity of the algorithm down at the cost of degrading solution quality. Results show significant streaming quality improvement over a conventional multiple description scheme.

In new video coding standards such as H.26L, predicted frame has the flexibility to select its reference frame from a number of previous frames for motion prediction. In this paper, we propose an optimization algorithm using dynamic programming that jointly exploits this flexibility with available network QoS for optimal streaming performance. A rounding technique is employed to scale the complexity of the algorithm down at the expense of gracefully degrading solution quality. Results show significant streaming quality improvement over an ad-hoc scheme.

A network agent located at the junction of wired and wireless networks can provide additional feedback information to streaming servers to supplement feedback from clients. Specifically, it has been shown that feedbacks from the network agent have lower latency, and can be used in conjunction with client feedbacks to effect proper congestion control. In this work, we propose the double feedback streaming agent (DFSA) which further allows the detection of discrepancies in the transmission constraints of the wired and wireless networks. By working together with the streaming server and client, DFSA reduce overall packet losses by exploiting the excess capacity of the path with more capacity. We show how DFSA can be used to support three modes of operation tailored for different delay requirements of streaming applications. Simulation results show noticeable improvement of media quality using DFSA over existing streaming systems.

The heterogeneity of today's computing environment means computation-intensive signal processing algorithms must be optimized for performance in a machine dependent fashion. In this paper, we present a dynamic memory model and associated optimization framework that finds a machine-dependent, near-optimal implementation of an algorithm by exploiting the computation-memory tradeoff. By optimal, we mean an implementation that has the fastest running time given the specification of the machine memory hierarchy. We discuss two instantiations of the framework: fast IP address lookup, and fast nonuniform scalar quantizer and unstructured vector quantizer encoding. Experiments show that both instantiations outperform techniques that ignore this computation-memory tradeoff.

Feedback adaptation has been the basis for many media streaming schemes whereby the media being sent is adapted according to feedback information about the channel. Central to the success of such adaptive schemes, the feedback must (1) arrive in a timely manner, and (2) carry enough information to effect useful adaptation. We examine the use of feedback adaptation for media streaming in a 3G wireless network, where the media servers are located in wired networks while the clients are wireless. We argue that end-to-end feedback adaptation using only information provided by 3G standards is neither timely, nor contain enough information for media adaptation at the server. We then show how the introduction of an streaming agent (SA) at the junction of the wired and wireless network can be used to provide useful information in a timely manner for media adaptation.

Regardless of the network loss process, a central problem in rate-distortion optimized video streaming is the modeling of the resulting distortion associated with the loss of different subsets of data units. When the dependency among data units is modeled by a directed acyclic graph, previous work has modeled the distortion contribution of a data unit based on only two events: whether or not the data unit and all its dependent data units are available. The restriction to only two events allows the use of a single scalar to represent the distortion contribution of a data unit, and at the same time limits its accuracy. We consider the general case when a data unit can assume different distortion contributions when different subsets of its dependent data units are available. Rate-distortion optimized streaming using the general model is performed to demonstrate the possible gains.

The rapid progress of computers and today's heterogeneous computing environment means computation-intensive signal processing algorithms must be optimized for performance in a machine dependent fashion. We present formal machine-dependent optimizations of scalar and vector quantizer encoders. Using a dynamic memory model, the optimal computation-memory tradeoff is exploited to minimize the encoding time. Experiments show marked improvements over existing techniques.

We propose an efficient bit allocation algorithm for a joint source/channel video codec over noisy channels. The approach is to distribute the available source and channel coding bits among the subbands in such a way that the expected distortion is minimized. The constructed distortion curves bound the performance degradation should the channel be estimated incorrectly. The algorithm can be used in other similar distortion minimization problems with two constraints, such as power or complexity.

Implementation of variable-length code (VLC) decoders can involve a tradeoff between the number of decoding steps and memory usage. In this paper, we proposed a novel scheme for optimizing this tradeoff using a machine model abstracted from general purpose processors with hierarchical memories. We formulate the VLC decode problem as an optimization problem where the objective is to minimize the average decoding time. After showing that the problem is NP-complete, we present a Lagrangian algorithm that finds an approximate solution with bounded error. An implementation is automatically synthesized by a code generator. To demonstrate the efficacy of our approach, we conducted experiments of decoding codebooks for a pruned tree-structured vector quantizer and H.263 motion vector that show a performance gain of our proposed algorithm over single table lookup implementation and logic implementation.

Media processing algorithms are typically computationally intensive, and in complexity constrained environments, finding the most computationally efficient algorithm is critical. In this paper, we present an attribute grammar based framework which captures the computational complexity of an algorithm in a machine-dependent manner. Using this formalism, a media processing algorithm can be optimally and automatically tuned to a particular machine by a problem specific optimizer. Moreover, the tradeoff between performance and execution time on a specific machine can be controlled and thus exploited to optimize overall performance. To illustrate the viability of our approach, we applied it to the variable-length code (VLC) decoding problem and show that the optimal VLC decoding algorithm can be found using the framework. Tradeoff between coding efficiency and decoding speed of Huffman code can be exploited by employing length-limited code.

The design of software-based algorithms for fast IP address lookup targeted for general purpose processors has received tremendous attention in recent years due to its low cost implementation and flexibility. However, all work to date fails to account for the hierarchical memory structure of the processor when designing algorithms. In this work, we propose a dynamic memory model that captures data movement between hierarchical memories and the memory access cost. Using the model, we formulate the design of IP address lookup algorithms as a well-defined optimization problem that minimizes an algorithm's average lookup time. We first show the problem is NP-hard. We then present an optimization framework and associated algorithm based on Lagrange multipliers that terminates in a bounded-error solution. Simulation shows the synthesized algorithm has noticeable performance gain over existing techniques.

The design of lookup tables for fast IP address lookup algorithms using a general processor is formalized as an optimization problem. A cost model that models the access times and sizes of the hierarchical memory structure of the processor is formulated. Two algorithms, using dynamic programming and Lagrange multipliers, solve the optimization problem optimally and approximately respectively. Experimental results show our algorithms have visible improvements over existing ones in the literature.

We propose an optimal bit allocation strategy for a joint source/channel video codec over noisy channel when the channel state is assumed to be known. Our approach is to partition source and channel coding bits in such a way that the expected distortion is minimized. The particular source coding algorithm we use is rate scalable and is based on 3D subband coding with multi-rate quantization. We show that using this strategy, transmission of video over very noisy channels still renders acceptable visual quality, and outperforms schemes that use equal error protection only. The flexibility of the algorithm also permits the bit allocation to be selected optimally when the channel state is in the form of a probability distribution instead of a deterministic state.