Meaningful Information

The information in an individual finite object (like a binary string) is commonly measured by its Kolmogorov complexity. One can divide that information into two parts: the information accounting for the useful regularity present in the object and the information accounting for the remaining accidental information. There can be several ways (model classes) in which the regularity is expressed. Kolmogorov has proposed the model class of finite sets, generalized later to computable probability mass functions. The resulting theory, known as Algorithmic Statistics, analyzes the algorithmic sufficient statistic when the statistic is restricted to the given model class. However, the most general way to proceed is perhaps to express the useful information as a total recursive function. The resulting measure has been called the "sophistication" of the object. We develop the theory of recursive functions statistic, the maximum and minimum value, the existence of absolutely nonstochastic objects (that have maximal sophistication-all the information in them is meaningful and there is no residual randomness), determine its relation with the more restricted model classes of finite sets, and computable probability distributions, in particular with respect to the algorithmic (Kolmogorov) minimal sufficient statistic, the relation to the halting problem and further algorithmic properties     

Rate-Distortion Coding Simulation for Color Images

We propose a distortion measure for color images, based on a mathematical model of color vision, and supported by subjective image quality evaluations. The visual model is configured after a simplified schematic of the retina's physiology and it transforms the red, green and blue image components into a representation that is consistent with major psychophysical phenomena. The distortion criterion proposed consists of measuring the mean square error in the above representation space. Consistency of the measure with human quality judgment is supported by a subjective ranking experiment, using images distorted in various ways by addition of noise. An optimal coder (in the rate distortion sense) is also simulated, which minimizes the distortion measured as proposed. The resulting image provides a quality standard at the rate distortion bound, against which actual coders can be compared. Finally it is observed that from a statistical point of view, the model's output is a near ideal color image representation for efficient coding.     

基于失真-量化模型的视频编码算法优化

失真-量化(D-Q)在视频编码率失真模型中起着关键作用,对主流D-Q模型进行了梳理,对这些模型的准确度和复杂度进行了详细对比,并分析它们各自适用的场合。通过模型验证,发现基于柯西分布的D-Q模型复杂度最低,但是准确度跟其他模型相比略低,就此问题对基于柯西分布的D-Q模型做了改进,以提高模型的精确度,使其更好地应用在率失真优化模式选择和码率控制的算法优化中。     

Kolmogorov's structure functions and model selection

In 1974, Kolmogorov proposed a nonprobabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The "structure function" of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best fitting model in the class irrespective of whether the "true" model is in the model class considered or not. In this setting, this happens with certainty, rather than with high probability as is in the classical case. We precisely quantify the goodness-of-fit of an individual model with respect to individual data. We show that-within the obvious constraints-every graph is realized by the structure function of some data. We determine the (un)computability properties of the various functions contemplated and of the "algorithmic minimal sufficient statistic.".     

Image distortion analysis based on normalized perceptual information distance

Image distortion analysis is a fundamental issue in many image processing problems, including compression, restoration, recognition, classification, and retrieval. Traditional image distortion evaluation approaches tend to be heuristic and are often limited to specific application environment. In this work, we investigate the problem of image distortion measurement based on the theory of Kolmogorov complexity, which has rarely been studied in the context of image processing. This work is motivated by the normalized information distance (NID) measure that has been shown to be a valid and universal distance metric applicable to similarity measurement of any two objects (Li et al. in IEEE Trans Inf Theory 50:3250–3264, 2004). Similar to Kolmogorov complexity, NID is non-computable. A useful practical solution is to approximate it using normalized compression distance (NCD) (Li et al. in IEEE Trans Inf Theory 50:3250–3264, 2004), which has led to impressive results in many applications such as construction of phylogeny trees using DNA sequences (Li et al. in IEEE Trans Inf Theory 50:3250–3264, 2004). In our earlier work, we showed that direct use of NCD on image processing problems is difficult and proposed a normalized conditional compression distance (NCCD) measure (Nikvand and Wang, 2010), which has significantly wider applicability than existing image similarity/distortion measures. To assess the distortions between two images, we first transform them into the wavelet transform domain. Assuming stationarity and good decorrelation of wavelet coefficients beyond local regions and across wavelet subbands, the Kolmogorov complexity may be approximated using Shannon entropy (Cover et al. in Elements of information theory. Wiley-Interscience, New York, 1991). Inspired by Sheikh and Bovik (IEEE Trans Image Process 15(2):430–444, 2006), we adopt a Gaussian scale mixture model for clusters of neighboring wavelet coefficients and a Gaussian channel model for the noise distortions in the human visual system. Combining these assumptions with the NID framework, we derive a novel normalized perceptual information distance measure, where maximal likelihood estimation and least square regression are employed for parameter fitting. We validate the proposed distortion measure using three large-scale, publicly available, and subject-rated image databases, which include a wide range of practical image distortion types and levels. Our results demonstrate the good prediction power of the proposed method for perceptual image distortions.     

Dynamic computational complexity and bit allocation for optimizing H.264/AVC video compression

In this work, we present a novel approach for optimizing H.264/AVC video compression by dynamically allocating computational complexity (such as a number of CPU clocks) and bits for encoding each coding element (basic unit) within a video sequence, according to its predicted MAD (mean absolute difference). Our approach is based on a computational complexity–rate–distortion (C–R–D) analysis, which adds a complexity dimension to the conventional rate–distortion (R–D) analysis. Both theoretically and experimentally, we prove that by implementing the proposed approach for the dynamic allocation better results are achieved. We also prove that the optimal computational complexity allocation along with optimal bit allocation is better than the constant computational complexity allocation along with optimal bit allocation. In addition, we present a method and system for implementing the proposed approach, and for controlling computational complexity and bit allocation in real-time and off-line video coding. We divide each frame into one or more basic units, wherein each basic unit consists of at least one macroblock (MB), whose contents are related to a number of coding modes. We determine how much computational complexity and bits should be allocated for encoding each basic unit, and then allocate a corresponding group of coding modes and a quantization step-size, according to the estimated distortion (calculated by a linear regression model) of each basic unit and according to the remaining computational complexity and bits for encoding remaining basic units. For allocating the corresponding group of coding modes and the quantization step-size, we develop computational complexity–complexity step–rate (C–I–R) and rate–quantization step-size–computational complexity (R–Q–C) models.     

Content-adaptive bitstream-layer model for coding distortion assessment of H.264/AVC networked video

Bitstream-layer models are designed to use the information extracted from both packet headers and payload for real-time and non-intrusive quality monitoring of networked video. This paper proposes a content-adaptive bitstream-layer (CABL) model for coding distortion assessment of H.264/AVC networked video. Firstly, the fundamental relationship between perceived coding distortion and quantization parameter (QP) is established. Then, considering the fact that the perceived coding distortion of a networked video significantly relies on both the spatial and temporal characteristics of video content, spatial and temporal complexities are incorporated in the proposed model. Assuming that the residuals before Discrete Cosine Transform (DCT) keep to the Laplace distribution, the scale parameters of the Laplace distribution are estimated utilizing QP and quantized coefficients on the basis of the Parseval theorem firstly. Then the spatial complexity is evaluated using QP and the scale parameters. Meanwhile, the temporal complexity is obtained using the weighted motion vectors (MV) considering the variations in temporal masking extent for high motion regions and low motion regions, respectively. Both the two characteristics of video content are extracted from the compressed bitstream without resorting to a complete decoding. Using content related information, the proposed model is able to adapt to different video contents. Experimental results show that the overall performance of CABL model significantly outperforms that of the P.1202.1 model and other coding distortion assessment models in terms of widely used performance criteria, including the Pearson Correlation Coefficient (PCC), the Spearman Rank Order Correlation Coefficient (SROCC), the Root-Mean-Squared Error (RMSE) and the Outlier Ratio (OR).     

Optimizing Motion Compensated Prediction for Error Resilient Video Coding

This paper is concerned with optimization of the motion compensated prediction framework to improve the error resilience of video coding for transmission over lossy networks. First, accurate end-to-end distortion estimation is employed to optimize both motion estimation and prediction within an overall rate-distortion framework. Low complexity practical variants are proposed: a method to approximate the optimal motion via simple distortion and source coding rate models, and a source-channel prediction method that uses the expected decoder reference frame for prediction. Second, reference frame generation is revisited as a problem of filter design to optimize the error resilience versus coding efficiency tradeoff. The special cases of leaky prediction and weighted prediction (i.e., finite impulse response filtering), are analyzed. A novel reference frame generation approach, called ?generalized source-channel prediction?, is proposed, which involves infinite impulse response filtering. Experimental results show significant performance gains and substantiate the effectiveness of the proposed encoder optimization approaches.     

基于最大可容忍深度失真模型的低复杂度深度视频编码

在保证虚拟视点绘制质量的前提下,如何降低深 度视频的编码复杂度是一个亟需解决的问题。本文提出了一 种基于最大可容忍深度失真(MTDD,maximum tolerable d epth distortion)模型的低复杂度深度编码算法,将MTDD模型引 入 到率失真(RD)代价函数,通过对编码单元(CU)进行失真度量判决 ,如果对当前CU进 行编码不会导致可察觉的绘制失真,则失真度量只考虑深度编码失真,否则失真度量同时考 虑深度编码失真和视点 合成失真(VSD),从而降低编码复杂度。实验结果表明,所 提出的算法在不 降低虚拟视点绘制质量和不增加编码码率的情况下,能显著降低深度视频的编码复杂度。     

一种新的视频编码二次率失真模型及其性能分析

基于对视频编码比特率与内容复杂度之间关系的研究,该文提出了一种新的视频编码二次率失真模型。该模型保留泰勒级数中的常数项,并通过合理引入内容复杂度,提高了描述实际信源率失真特性的准确性。大量实验分析表明该模型具有良好的性能,可广泛应用于各种速率控制算法以及其他使用率失真模型的场合,以提高视频编码器的率失真性能。     

Distortion variation minimization in real-time video coding

In this paper, we review the rate distortion tradeoff issues in real-time video coding and introduce a minimum variation (MINVAR) distortion criterion based approach. The MINVAR based rate distortion tradeoff framework provides a local optimization strategy as a rate control mechanism in real-time video coding applications by minimizing the distortion variation while the corresponding bit rate fluctuation is limited by utilizing the encoder buffer. The proposed approach aims to achieve a smooth decoded picture quality for pleasing human visual experience. The performance of the proposed method is evaluated with H.264. The experimental results demonstrate that using the proposed approach, the decoded picture quality is smoother than the traditional H.264 joint model (JM) rate control without sacrificing global quality such that a better subjective visual quality is guaranteed.     

A Fast Intra‐Prediction Method in HEVC Using Rate‐Distortion Estimation Based on Hadamard Transform

A fast intra‐prediction method is proposed for High Efficiency Video Coding (HEVC) using a fast intra‐mode decision and fast coding unit (CU) size decision. HEVC supports very sophisticated intra modes and a recursive quadtree‐based CU structure. To provide a high coding efficiency, the mode and CU size are selected in a rate‐distortion optimized manner. This causes a high computational complexity in the encoder, and, for practical applications, the complexity should be significantly reduced. In this paper, among the many predefined modes, the intra‐prediction mode is chosen without rate‐distortion optimization processes, instead using the difference between the minimum and second minimum of the rate‐distortion cost estimation based on the Hadamard transform. The experiment results show that the proposed method achieves a 49.04% reduction in the intra‐prediction time and a 32.74% reduction in the total encoding time with a nearly similar coding performance to that of HEVC test model 2.1.     

DVFS-aware motion estimation design scheme based on bandwidth–rate–distortion optimization in application processor systems

In this paper, a novel dynamic voltage–frequency scaling-aware (DVFS-aware) bandwidth- efficient motion estimation (ME) scheme is presented for mobile application processor (AP) systems. Under volatile operating performance conditions due to the power management mechanism, we model the coding bandwidth (BW) and coding performance for the video processor as a convex function of the working frequency. In this paper, we present a bandwidth–rate–distortion (B–R–D) optimized framework that will guarantee the smallest possible rate–distortion cost among coding BW constraints applied in video coding design. By formulating the coding bandwidth-constrained ME problem as an optimization problem, known convex optimization theory can be applied to yield optimal resource-constrained compression. Using varied CIF (352×288)- and HP (1280×720)-sized video sequences with different motion activities over our proposed DVFS-aware video coding approach, the excellent results in terms of coding performance and coding bandwidth savings are obtained. With negligible quality loss, the proposed scheme under coding BW constraints achieves 45–65% coding BW usage reduction over HD-sized 30 frame/s video coding.     

Vocal system phase coder for sinusoidal speech coders

A new phase coding algorithm working in the pitch-cycle waveform domain is introduced. It provides accurate phase coding at low bit cost, thus being suitable for low bit rate sinusoidal coders. Its performance is analysed inside a multiband excitation (MBE) coder with improved onset representation. In this context, the introduction of original phase information by means of the proposed coding algorithm provides noticeable quality improvement without significantly increasing the complexity and total bit rate of the coder     

Segment-based view synthesis optimization scheme in 3D-HEVC

The 3D extension of high efficiency video coding (3D-HEVC) adopts a view synthesis optimization (VSO) technique to improve the quality of synthesized views for depth map coding. The exact synthesized view distortion change (SVDC) is calculated in VSO which in turn brings huge coding complexity to the 3D-HEVC encoder due to the real view synthesis process. This work presents a scheme aimed at reducing coding complexity of the SVDC calculating process in the 3D-HEVC encoder. It skips line segments of pixels with variable lengths based on information from both of the textures and depth maps in the SVDC calculation. Experimental results demonstrate that the proposed scheme can reduce the coding complexity without any significant loss in rate distortion performance for the synthesized views.     

A two-pass rate control algorithm for H.264/AVC high definition video coding

In this paper, we propose a novel two-pass rate control algorithm to achieve constant quality for H.264/AVC high definition video coding. With the first-pass collected rate and distortion information and the built model of scene complexity, the encoder can determine the expected distortion which could be achieved in the second-pass encoding under the target bit rate. According to the built linear distortion-quantizer (D-Q) model, before encoding one frame, the quantization parameter can be solved to realize constant quality encoding. After encoding one frame, the model parameters will be updated with linear regression method to ensure the prediction accuracy of the quantization parameter of next encoded frame with the same coding type. In order to obtain the expected distortion of each frame under the target bit rate, a GOP-level bit allocation scheme is also designed to adjust the target bit rate of each GOP based on the scene complexity of the GOP in the second-pass encoding. In addition, the effect of scene change on the updating of D-Q model is considered. The model will be re-initialized at the scene change to minimize modeling error. The experimental results show that compared with the latest two-pass rate control algorithm, our proposed algorithm can significantly improve the bit control accuracy at comparable coding performance in terms of constant quality and average PSNR. On average, the improvement of bit control accuracy achieved about 90%.     

基于统计建模的HEVC快速率失真估计算法

针对高效视频编码(HEVC)率失真优化过程中复杂的码率与失真计算,提出一种高准确性的快速率失真估计模型。该算法评估熵编码中不同语法元素的贡献百分比,并逐个开发语法元素的码率模型以构建整个TU级模型。首先,对系数进行自适应加权,以区分不同系数对码率的不均匀贡献。然后,定义位置参数以描述一个块内非零系数可能的分布模式。通过统计方式对大量样本的模型参数进行微调,得出最终线性码率模型。最后,建立了变换域失真模型来省略不必要的重构过程。实验结果表明,所提算法在RA配置下,可以实现49.76%的复杂度降低,而BD-BR仅增加1.74%。     

Complexity-constrained best-basis wavelet packet algorithm forimage compression

The concept of adapted waveform analysis using a best-basis selection out of a predefined library of wavelet packet (WP) bases allows an efficient image representation for the purpose of compression. Image coding methods based on the best-basis WP representation have shown significant coding gains for some image classes compared with methods using a fixed dyadic structured wavelet basis, at the expense however, of considerably higher computational complexity. A modification of the best-basis method, the so-called complexity constrained best-basis algorithm (CCBB), is proposed which parameterises the complexity gap between the fast (standard) wavelet transform and the best wavelet packet basis of a maximal WP library. This new approach allows a `suboptimal' best basis to be found with respect to a given budget of computational complexity or, in other words, it offers an instrument to control the trade-off between compression speed and, coding efficiency. Experimental results are presented for image coding applications showing a highly nonlinear relationship between the rate-distortion performance and the computational complexity in such a way that a relatively small increase in complexity with respect to the standard wavelet basis results in a relatively high rate distortion gain