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

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

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

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

This paper introduces row-column transforms (RCTs) which are 2D non-separable transforms defined with the aid of a set of 1-D linear transforms and a basis ordering permutation. We propose a novel method for the design of row-column transforms that approximate desired complex transforms (such as KLTs, SOTs, etc.) so that most of the performance of the approximated transforms is retained at significantly reduced complexity. Given a non-separable block transform of interest, our method designs an RCT by (i) optimizing a set of 1-D transforms applied to rows and columns of the signal block and (ii) finding the best transform coefficient ordering permutation. Our experimental results show that optimized RCTs closely approach the compression performance of the desired non-separable transforms while retaining the computational complexity of separable transforms.

We propose an algorithm that accomplishes transform-coded, spatiotemporal, pel-recursive video compression. Traditional pel-recursive coders obtain sophisticated spatio-temporal predictions for the current pixel based on previously decoded data. The resulting per-pixel prediction errors are encoded independently so that the decoder can use previously-encoded pixels in the prediction of the current. It is well-known that pel-recursive coders significantly under-perform modern hybrid coders which use comparatively very simple predictors but transform code the prediction errors. Our algorithm combines the accurate predictors of pel-recursive techniques with transform coders so that the strengths of both approaches can be taken advantage of. In the proposed work, the decoder transform decodes the residuals for a block and then acts like a simple pel-recursive decoder for the pixels of that block. We show that the proposed algorithm can be seen as the use of a pel-recursion enabling transform at the encoder, which generates and encodes the correct transform coefficients to avoid error propagation at the decoder. A straightforward implementation of our work (implemented as an extension of HEVC that preserves independent decodability of INTER blocks) shows compression improvements over the baseline HEVC.

We consider the motion-compensated temporal prediction loop at the heart of modern video coders. Rather than using motion-compensated reference frame blocks directly as predictors, we incorporate their spatially-filtered versions into the prediction loop. We design adaptive filters that are geared toward successful prediction over sophisticated temporal evolutions involving lighting changes, focus changes, structured noise, and so on. The spatially and temporally varying nature of such video evolutions requires the learning and transmission of many filters, necessitating parameter reduction for compression and related applications. Unlike earlier work that tries to limit parameters by using a small set of general filters, or by restricting to symmetric filters, etc., we propose a novel parametrization of filters in terms of a set of base-filter kernels and modulation weights. Given a filter dictionary of K-tap filters, our work can be seen as providing a reduced-rank, prediction-optimal approximation of this dictionary that represents its filters with K' ≪ K parameters.

We study the INTRA-prediction operation employed in hybrid video coders where sample values to be compressed are predicted using previously-decoded context values and the prediction errors are transform coded. Given the context values this procedure can be argued to be rate-distortion optimal for Gaussian signals. Yet natural images and video contain many structures that do not readily fit into Gaussian signal assumptions. Targeting such structures we propose a technique that predicts each sample using the context values and samples that are jointly transform coded with the predicted sample. We show that this joint, non-causal encoding can be represented with a nonorthogonal transform whose form and parameters we derive. We augment the HEVC standard with our work and show significant compression improvements on images/video that contain directional structures.

We propose new techniques to improve hybrid coding of images and video, without increasing decoder complexity, by controlling quantization effects in spatial and frequency domains, and finding optimal quantized coefficients via optimization. Additional compression is achieved by finding sets of optimal parameters, determined using training techniques. Experimental results confirm that the new method is able to provide better compression, both in objective measures, like signal-to-noise ratios, and also subjective, by reducing visually annoying blocking and banding artifacts.

This letter proposes a novel warping-based method for the content-driven retargeting of stereoscopic images. Conventional algorithms in single image retargeting generally do not consider the scene depth saliency and disparity consistency when applied independently to left and right images . Therefore, the salient region and stereoscopic correlation of independently retargeted images can become corrupted. On the other hand, the proposed algorithm retains the stereo consistency of the retargeted images by matching the vertices of the grid and preserving the correspondence between them. Vertex disparity is propagated by a GPU interpolation to construct a sparse disparity map. To improve the capability of preserving visually important regions, the sparse disparity is used in conjunction with the image gradient in a saliency map computation. The experimental results show that the proposed method retains the correct disparity, while the salient objects remain undistorted in the retargeted stereoscopic image pairs.

This paper presents a new approach for estimating the disparity search range in stereo video that enforces temporal consistency. Reliable search range estimation is very important since an incorrect estimate causes most stereo matching methods to get trapped in local minima or produce unstable results over time. In this work, the search range is estimated based on a disparity histogram that is generated with sparse feature matching algorithms such as SURF. To achieve more stable results over time, we further propose to enforce temporal consistency by calculating a weighted sum of temporally-neighboring histograms, where the weights are determined by the similarity of depth distribution between frames. Experimental results show that this proposed method yields accurate disparity search ranges for several challenging stereo videos and is robust to various forms of noise, scene complexity and camera configurations.

This paper proposes a novel method for handling occluded pixels in stereo images based on a probabilistic voting framework that utilizes a novel support-and-decision process. Occlusion handling aims to assign a reasonable disparity value to occluded pixels in the disparity maps. In an initial step, disparities and their corresponding supports at the occluded pixels are calculated using a probabilistic voting method using the disparities at visible pixels. In this way, the visible pixel information is propagated when the disparities and supports at the occluded pixels are computed. The final disparities for occluded pixels are then computed through an iterative support-and-decision process to propagate the information inside the occluded pixel region. An acceleration technique is also proposed to improve the performance of the iterative support-and-decision process. Experimental results show that the proposed occlusion handling method works well for several challenging stereo images.

Depth image-based rendering (DIBR) is generally used to synthesize virtual view images in free viewpoint television (FTV) and three-dimensional (3-D) video. One of the main problems in DIBR is how to fill the holes caused by disocclusion regions and inaccurate depth values. In this paper, we propose a new hole filling method using a depth based in-painting technique. Experimental results show that the proposed hole filling method provides improved rendering quality both objectively and subjectively.

It is well-known that large depth-coding errors typically occurring around depth edge areas lead to distorted object boundaries in the synthesized texture images. This paper proposes a multi-layered coding approach for depth images as a complement to the popular edge-aware approaches such as those based on platelets. It is shown that guaranteeing a near-lossless bound on the depth values around the edges by adding extra enhancement layers is an effective way to improve the visual quality of the synthesized images.

A depth image represents three-dimensional (3-D) scene information and is commonly used for depth image-based rendering (DIBR) to support 3-D video and free-viewpoint video applications. The virtual view is generally rendered by the DIBR technique and its quality depends highly on the quality of depth image. Thus, efficient depth coding is crucial to realize the 3-D video system. In this letter, we propose a depth reconstruction filter and depth down/up sampling techniques to improve depth coding performance. Experimental results demonstrate that the proposed methods reduce the bit-rate for depth coding and achieve better rendering quality.

A fuzzy filter adaptive to both sample's activity and the relative position between samples is proposed to reduce the artifacts in compressed multidimensional signals. For JPEG images, the fuzzy spatial filter is based on the directional characteristics of ringing artifacts along the strong edges. For compressed video sequences, the motion compensated spatiotemporal filter (MCSTF) is applied to intraframe and interframe pixels to deal with both spatial and temporal artifacts. A new metric which considers the tracking characteristic of human eyes is proposed to evaluate the flickering artifacts. Simulations on compressed images and videos show improvement in artifact reduction of the proposed adaptive fuzzy filter over other conventional spatial or temporal filtering approaches.

We propose a novel method to reduce both blocking and ringing artifacts in compressed images and videos. Based on the directional characteristics of ringing artifacts along edges, we use a directional fuzzy filter which is adaptive to the direction of the ringing artifact. The filter exploits the spatial order, the rank order and the spread information of the signal together with the position of the pixels to enhance the quality of the compressed image. Simulations results on compressed images and videos having simple and complex edges show the improvement of the proposed directional fuzzy filter over the conventional fuzzy filtering and other approaches.

This paper addresses signal processing issues related to coded representation, reconstruction and rendering of multiview video for 3D displays. We provide an overview of standardization efforts for multiview video that are aimed at reducing data rates required to represent the multiview video in compressed form. We then present an anti-aliasing filtering technique that effectively eliminates ghosting artifacts when rendering multiview video on 3D displays. Since high-frequency components of the signal are removed, substantial reductions in the compressed data rate could also be realized. Finally, we discuss the importance of scalability in the context of multiview video coding and suggest a combined anti-aliasing and scalable decoding scheme to minimize decoding resources for a given 3D display.

We propose a rate-distortion optimized framework that incorporates view synthesis for improved prediction in multiview video coding. In the proposed scheme, block-based depth and correction vectors are encoded and used at the decoder to generate the view synthesis prediction data. The proposed method employs variable block-size depth/motion search, optimal mode decision including view synthesis prediction, and CABAC encoding of depth and correction vectors. A sub-pixel reference matching technique is also introduced to improve prediction accuracy of the view synthesis prediction. Novel variants of the skip and direct modes are presented, which infer the depth and correction vector information from neighboring blocks in a synthesized reference picture to reduce the bits needed for the view synthesis prediction mode. Experimental results demonstrate improved coding efficiency with the proposed techniques.

Multi-view 3D displays are preferable to other stereoscopic display technologies because they provide autostereoscopic viewing from any viewpoint without special glasses. However, they require a large number of pixels to achieve high image quality. Therefore, data compression is a major issue for this approach. In this paper, we present a framework for efficient compression of multi-view video streams for multi-view 3D displays. Our goal is to optimize image quality without increasing the required data bandwidth. We achieve this by taking into account a precise notion of the multi-dimensional display bandwidth. The display bandwidth implies that scene elements that appear at a given distance from the display become increasingly blurry as the distance grows. Our main contribution is to enhance conventional multi-view compression pipelines with an additional pre-filtering step that bandlimits the multi-view signal to the display bandwidth. This imposes a shallow depth of field on the input images, thereby removing high frequency content. We show that this pre-filtering step leads to increased image quality compared to state-of-the-art multi-view coding at equal bitrate. We present results of an extensive user study that corroborate the benefits of our approach. Our work suggests that display pre-filtering will be a fundamental component in signal processing for 3D displays, and that any multi-view compression scheme will benefit from our pre-filtering technique.

In this paper, we present a two-stage near-lossless compression scheme. It belongs to the class of "lossy plus residual coding" and consists of a wavelet-based lossy layer followed by arithmetic coding of the quantized residual to guarantee a given L(infinity) error bound in the pixel domain. We focus on the selection of the optimum bit rate for the lossy layer to achieve the minimum total bit rate. Unlike other similar lossy plus lossless approaches using a wavelet-based lossy layer, the proposed method does not require iteration of decoding and inverse discrete wavelet transform in succession to locate the optimum bit rate. We propose a simple method to estimate the optimal bit rate, with a theoretical justification based on the critical rate argument from the rate-distortion theory and the independence of the residual error.

In this paper, we elaborate on denoising schemes based on lossy compression. First, we provide an alternative interpretation of the so-called Occam filter and relate it with the complexity-regularized denoising schemes in the literature. Next, we discuss about the 'critical distortion' of a noisy source and argue that optimal denoising is achieved at the corresponding critical encoding rate rather than at the encoding rates suggested by other compression-based denoisers. Finally, we discuss the so-called 'indirect rate distortion problem'. We focus particularly on the high bit-rate encoding of noisy sources and show lossless compression of a denoised source is often very wasteful of bits, and suggest a simple way of determining an appropriate bit-rate for compressing a denoised source economically while retaining its initial denoised quality.

Many technical imaging applications, like coding "images" of digital elevation maps, require extracting regions of compressed images in which the pixel values are within a predefined range, and there is a need for coding methods that allow finding these regions efficiently, without having to decompress the whole image. A series of techniques to solve this problem is presented. First, it shows that many of the linear transforms commonly used for image compression can be used for that purpose by proving that the inclusion of nonlinear factors (like minimum or maximum pixel value in a block) does not render the transformation irreversible, and can be made to have very limited impact on the compression efficiency. For example, it shows how the "DC" coefficient of an 8/spl times/8 discrete cosine transform (DCT) can be replaced by the minimum or maximum in the 8/spl times/8 block. This result is valid for a large set of transforms, including the DCT, Walsh-Hadamard, and dyadic Haar transforms, and valid for any type of order-statistic filter output. Next, it shows the results also apply to the quantized transform coefficient cases as well as integer-to-integer transforms. The choices for coding the minimum and maximum values simultaneously, while providing quick access to pixel range and efficient compression were finally studied.

In this paper, we investigate a two-stage near-lossless compression scheme. It is in the spirit of "lossy plus residual coding" and consists of a wavelet-based lossy layer followed by an arithmetic coding of the quantized residual to guarantee a given L/sup /spl infin// error bound in the pixel domain. Our focus is on the selection of the optimum bit rate for the lossy layer to achieve the minimum total bit rate. Unlike other similar lossy plus lossless approaches using a wavelet-based lossy layer, the proposed method does not require iteration of decoding and the IWT(Inverse Wavelet Transform) to locate the optimum bit rate. We propose a simple method to estimate the optimal bit rate and provide a theoretical justification for it. It is based on the 'critical rate' argument from the Rate-Distortion theory and 'whiteness' of the residual.

Technical imaging applications such as coding "images" of digital elevation maps, require extracting regions of compressed images with the pixel values within a pre-defined range, without having to decompress the whole image. Previously, we introduced a class of nonlinear transforms which are small modifications of linear transforms to facilitate a search for the regions with pixel values below (above) a given 'threshold', without incurring any penalty in coding efficiency. However, coding efficiency had to be somewhat compromised when searching for regions with a given pixel 'range', especially at high coding rates. In this paper, we propose an improved method of pixel 'range' coding to deal with the aforementioned problem. Results show significant improvements in coding efficiency.