Rate-distortion methods for image and video compression

In this article we provide an overview of rate-distortion (R-D) based optimization techniques and their practical application to image and video coding. We begin with a short discussion of classical rate-distortion theory and then we show how in many practical coding scenarios, such as in standards-compliant coding environments, resource allocation can be put in an R-D framework. We then introduce two popular techniques for resource allocation, namely, Lagrangian optimization and dynamic programming. After a discussion of these techniques as well as some of their extensions, we conclude with a quick review of literature in these areas citing a number of applications related to image and video compression and transmission     

Rate-distortion optimization of scalable video codecs

In this paper joint optimization of layers in the layered video coding is investigated. Through theoretical analysis and simulations, it is shown that, due to higher interactions between the layers in a SNR scalable codec, this type of layering technique benefits most from joint optimization of the layers. A method for joint optimization is then proposed, and its compression efficiency is contrasted against the separate optimization and an optimized single layer coder. It is shown that, in joint optimization of SNR scalable coders when the quantization step size of the enhancement layer is larger than half the step size of the base layer, an additional improvement is gained by not sending the enhancement zero valued quantized coefficients, provided they are quantized at the base-layer. This will result in a non-standard bitstream syntax and as an alternative for standard syntax, one may skip the inter coded enhancement macroblocks. Through extensive tests it is shown that while separate optimization of SNR coders is inferior to single layer coder by more than 2 dB, with joint optimization this gap is reduced to 0.3–0.5 dB. We have shown that through joint optimization quality of the base layer video is also improved over the separate optimization. It is also shown that spatial scalability like SNR scalability does benefit from joint optimization, though not being able to exploit the relation between the quantizer step sizes. The amount of improvement depends on the interpolation artifacts of upsampled base-layer and the residual quantization distortion of this layer. Hence, the degree of improvement depends on image contents as well as the bit rate budget. Simulation results show that joint optimization of spatial scalable coders is about 0.5–1 dB inferior to the single layer optimized coder, where its separate optimization counterpart like SNR scalability is more than 2 dB worse.     

基于感兴趣区域的HEVC压缩性能优化

根据人类视觉系统(HVS)对纹理复杂及运动区域具有较强感知度的特点,提出了一种基于感兴趣区域的高效率视频编码(HEVC)压缩性能优化算法.首先使用Sobel梯度检测算子和运动矢量分别检测纹理复杂区域和运动区域,把检测到的纹理复杂及运动区域定义为感兴趣区域;再对感兴趣区域分级,通过调整量化参数(QP),优化比特分配.实验结果表明,与HEVC标准算法相比,所提算法码率平均减少了15.29％,时间平均节省了11.38％.     

Rate-distortion optimal video summary generation.

The need for video summarization originates primarily from a viewing time constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth, and/or power are limited. The summarization process inevitably introduces distortion. The amount of summarization distortion is related to its "conciseness," or the number of frames available in the summary. If there are m frames in the original sequence and n frames in the summary, we define the summarization rate as m/n, to characterize this "conciseness". We also develop a new summarization distortion metric and formulate the summarization problem as a rate-distortion optimization problem. Optimal algorithms based on dynamic programming are presented and compared experimentally with heuristic algorithms. Practical constraints, like the maximum number of frames that can be skipped, are also considered in the formulation and solution of the problem.     

Rate-distortion based real-time wireless video streaming

This paper presents wireless video streaming techniques that exploit the characteristics of video content, transmission history, and physical layer channels to enable real-time efficient video streaming over wireless networks to a wireless client. The key contribution of the proposed video streaming techniques is the use of rate-distortion based, but simplified, low complexity packet scheduling as well as forward error correction (FEC) rate selection. To this end, we develop an optimization framework that jointly schedules the packets and selects the FEC rates. The rate-distortion optimized packet scheduling and FEC rate selection provides the optimum quality video on the receiver side albeit at a high computational cost. By some intelligent approximations, rate distortion optimized packet scheduling and FEC rate selection technique is transformed into two sub-optimal but low complexity video streaming techniques that can provide high video quality. We perform extensive simulations to understand the performance of our proposed techniques under different scenarios. Results show that, the proposed techniques improve video quality on the average by 4 dB. We conclude that significant benefits to end-user experience can be obtained by using such video streaming methods.     

Rate-distortion optimized unequal loss protection for FGS compressed video

Video communication with quality of service (QoS) is an important and challenging task. The transmitted video stream must be able to afford the bandwidth variance and unavoidable packet loss in the Internet. In particular, fine-granular-scalability (FGS) video coding has been adopted by the MPEG-4 standard as the core video-compression method for streaming applications. From this inception, the FGS scalability structure was designed to be packet resilient especially under unequal loss protection (ULP). In this paper, we use ULP to protect FGS compressed video, and under the restriction of the network bandwidth, joint source-channel rate-distortion based optimization is performed in bit allocation to minimize the end-to-end distortion. Simulation results demonstrate effectiveness of our approach.     

Rate-distortion optimized rate-allocation for motion-compensated predictive video codecs using PixelRank

Inter-frame dependencies are usually ignored in video encoder coding parameter selection. This gives a non-optimal solution and degrades the compression performance. A mathematical model to estimate the importance of each pixel on the reconstructed video quality, called PixelRank, is developed in this paper. Theoretical analysis on the parameters used for PixelRank score calculation dealing with the video coding optimization problem is also given. The PixelRank algorithm tracks the importance of each pixel and distributes the PixelRank scores. With the PixelRank scores for all the pixels, MB-based quantization parameters are adjusted accordingly. Based on this technique, the rate can be allocated more accurately according to the importance of the pixels, thus achieving better overall rate-distortion performance. Compared to the non-optimized scheme in H.264/AVC, the proposed scheme can reduce 13.53% of the average bitrate and up to 25.17% of bitrate in the simulations.     

Rate-distortion driven decoder-side bitplane mode decision for distributed video coding

Distributed video coding (DVC) features simple encoders but complex decoders, which lies in contrast to conventional video compression solutions such as H.264/AVC. This shift in complexity is realized by performing motion estimation at the decoder side instead of at the encoder, which brings a number of problems that need to be dealt with. One of these problems is that, while employing different coding modes yields significant coding gains in classical video compression systems, it is still difficult to fully exploit this in DVC without increasing the complexity at the encoder side. Therefore, in this paper, instead of using an encoder-side approach, techniques for decoder-side mode decision are proposed. A rate-distortion model is derived that takes into account the position of the side information in the quantization bin. This model is then used to perform mode decision at the coefficient level and bitplane level. Average rate gains of 13–28% over the state-of-the-art DISCOVER codec are reported, for a GOP of size four, for several test sequences.     

Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images.

This paper presents novel coding algorithms based on tree-structured segmentation, which achieve the correct asymptotic rate-distortion (R-D) behavior for a simple class of signals, known as piecewise polynomials, by using an R-D based prune and join scheme. For the one-dimensional case, our scheme is based on binary-tree segmentation of the signal. This scheme approximates the signal segments using polynomial models and utilizes an R-D optimal bit allocation strategy among the different signal segments. The scheme further encodes similar neighbors jointly to achieve the correct exponentially decaying R-D behavior (D(R) - c(o)2(-c1R)), thus improving over classic wavelet schemes. We also prove that the computational complexity of the scheme is of O(N log N). We then show the extension of this scheme to the two-dimensional case using a quadtree. This quadtree-coding scheme also achieves an exponentially decaying R-D behavior, for the polygonal image model composed of a white polygon-shaped object against a uniform black background, with low computational cost of O(N log N). Again, the key is an R-D optimized prune and join strategy. Finally, we conclude with numerical results, which show that the proposed quadtree-coding scheme outperforms JPEG2000 by about 1 dB for real images, like cameraman, at low rates of around 0.15 bpp.     

Rate-distortion analysis of motion-compensated rate scalable video.

Generally speaking, rate scalable video systems today are evaluated operationally, meaning that the algorithm is implemented and the rate-distortion performance is evaluated for an example set of inputs. However, in these cases it is difficult to separate the artifacts caused by the compression algorithm and data set with general trends associated with scalability. In this paper, we derive and evaluate theoretical rate-distortion performance bounds for both layered and continuously rate scalable video compression algorithms which use a single motion-compensated prediction (MCP) loop. These bounds are derived using rate-distortion theory based on an optimum mean-square error (MSE) quantizer, and are thus applicable to all methods of intraframe encoding which use MSE as a distortion measure. By specifying translatory motion and using an approximation of the predicted error frame power spectral density, it is possible to derive parametric versions of the rate-distortion functions which are based solely on the input power spectral density and the accuracy of the motion-compensated prediction. The theory is applicable to systems which allow prediction drift, such as the data-partitioning and SNR-scalability schemes in MPEG-2, as well as those with zero prediction drift such as fine granularity scalability MPEG-4. For systems which allow prediction drift we show that optimum motion compensation is a sufficient condition for stability of the decoding system.     

Rate-distortion optimized hybrid error control for real-time packetized video transmission.

The problem of application-layer error control for real-time video transmission over packet lossy networks is commonly addressed via joint source-channel coding (JSCC), where source coding and forward error correction (FEC) are jointly designed to compensate for packet losses. In this paper, we consider hybrid application-layer error correction consisting of FEC and retransmissions. The study is carried out in an integrated joint source-channel coding (IJSCC) framework, where error resilient source coding, channel coding, and error concealment are jointly considered in order to achieve the best video delivery quality. We first show the advantage of the proposed IJSCC framework as compared to a sequential JSCC approach, where error resilient source coding and channel coding are not fully integrated. In the USCC framework, we also study the performance of different error control scenarios, such as pure FEC, pure retransmission, and their combination. Pure FEC and application layer retransmissions are shown to each achieve optimal results depending on the packet loss rates and the round-trip time. A hybrid of FEC and retransmissions is shown to outperform each component individually due to its greater flexibility.     

可变尺寸块运动估计的R—D优化

本文应用率失真理论在固定码率的前提下对可变尺寸块运动估计过程进行R－D优化,获得了最佳预测块划分和最小运动补偿误差,并提出了基于树形结构的运动矢量编码方案。R－D优化问题的求解通过引入失真度－码率梯度,将R－D优化与分层运动估计结合在一起,克服了GP－BFOS算法需要对各个分块层次进行运动估计及所得局部最优解严格位于R－D曲线凸包络线上的弊病。软件模拟结果显示本算法大大降低了G－BFOS优化算法的计算量,且运动补偿RSNR值高于G－BFOS算法结果。     

Rate-distortion estimation for fast JPEG2000 compression at low bit-rates

In JPEG2000 block coding, all coding passes are generated before rate allocation is performed among code blocks. Unwanted passes are then discarded. For low bit-rate coding, this results in a large number of coding passes being discarded. A rate-distortion estimation method that enables precompression rate-distortion optimisation to be carried out, wherein only the required passes need to be coded is presented. Experiments using the proposed technique demonstrate speed-up factors ranging from 1.17 to 1.78 at 0.0625 bpp, for JPEG2000 compression.     

Rate-distortion optimized unequal loss protection for video transmission over packet erasure channels

Video transmission over networks often suffers from packet loss due to network congestions and stringent end-to-end delay constraints. In this paper, we develop a Rate-Distortion optimized Unequal Loss Protection (RD-ULP) scheme to combat packet loss. Based on packet-level transmission distortion modeling, we estimate the amount of contribution of each video packet to the reconstructed video quality, which defines the priority level of each packet. Unequal amounts of protection are then allocated to different video packets according to their priority levels and the dynamic channel conditions. The proposed RD-ULP resource allocation problem is formulated as a constrained nonlinear optimization problem. An optimization algorithm based on Particle Swarm Optimization (PSO) is then developed to solve the optimal resource allocation problem. Our extensive experimental results demonstrate the effectiveness of the proposed RD-ULP scheme, which outperforms existing methods by up to 2 dB in the reconstructed video quality.     

Fast embedded compression for video

An embedded coding algorithm creates a compressed bit stream that can be truncated to produce reduced resolution versions of the original image. Unfortunately, such algorithms are relatively slow. We introduce two new concepts in an effort to address this problem: adaptive embedding and cache-based zerotree processing.     

Weighted finite automata for video compression

Weighted finite automata (WFA) exploit self-similarities within single pictures and also sequences of pictures to remove spatial and temporal redundancies. Their implementation then combines techniques from hierarchical methods related to quadtrees and from vector quantization to achieve performance results for low bit rates which can be put on a par with state-of-the-art codecs like embedded zero-tree wavelet coding. Due to their simple mathematical structure, WFA provide an ideal platform for efficient hybrid compression methods. Therefore, WFA were chosen as a starting point for a fractal-like video compression integrating a hierarchical motion compensation as well as an option to vary the compression quality between “centers of interest” and “background” in a flexible manner     

Multidimensional quantizers for scalable video compression

Scalable video compression requires the creation of an encoded bit stream that may be decoded in part if channel bandwidth drops, decoder resources are limited, or a smaller image than the source is desired. A separable spatiotemporal subband decomposition is combined with vector and lattice quantizers modified so that the individual subbands may be decoded scalably. This results in finer bandwidth control and more flexibility than simply discarding entire subbands     

立体图像序列的压缩方法

首先介绍了立体视觉的基本原理，然后对立体图像的压缩方法分四类进行了综述。对其中用于立体图像序列的两种主要方法：基于“块”匹配的立体图像压缩方法和基于物体的立体图像压缩方法进行了深入探讨。通过对已有成果进行总结和分类，剖析了两种方法的优、缺点，并提出了一些还需要深入研究的问题，如：残差图像编码、遮挡检测、更精确的场景分割等。     

Rate-distortion optimal video transport over IP allowing packets with bit errors.

We propose new models and methods for rate-distortion (RD) optimal video delivery over IP, when packets with bit errors are also delivered. In particular, we propose RD optimal methods for slicing and unequal error protection (UEP) of packets over IP allowing transmission of packets with bit errors. The proposed framework can be employed in a classical independent-layer transport model for optimal slicing, as well as in a cross-layer transport model for optimal slicing and UEP, where the forward error correction (FEC) coding is performed at the link layer, but the application controls the FEC code rate with the constraint that a given IP packet is subject to constant channel protection. The proposed method uses a novel dynamic programming approach to determine the optimal slicing and UEP configuration for each video frame in a practical manner, that is compliant with the AVC/H.264 standard. We also propose new rate and distortion estimation techniques at the encoder side in order to efficiently evaluate the objective function for a slice configuration. The cross-layer formulation option effectively determines which regions of a frame should be protected better; hence, it can be considered as a spatial UEP scheme. We successfully demonstrate, by means of experimental results, that each component of the proposed system provides significant gains, up to 2.0 dB, compared to competitive methods.     

Morphological operators for image and video compression

This paper deals with the use of some morphological tools for image and video coding. Mathematical morphology can be considered as a shape-oriented approach to signal processing, and some of its features make it very useful for compression. Rather than describing a coding algorithm, the purpose of this paper is to describe some morphological tools that have proved attractive for compression. Four sets of morphological transformations are presented: connected operators, the region-growing version of the watershed, the geodesic skeleton, and a morphological interpolation technique. The authors discuss their implementation, and show how they can be used for image and video segmentation, contour coding, and texture coding.