Overlapped block motion compensation: an estimation-theoreticapproach

We present an estimation-theoretic analysis of motion compensation that, when used with fields of block-based motion vectors, leads to the development of overlapped block algorithms with improved compensation accuracy. Overlapped block motion compensation (OBMC) is formulated as a probabilistic linear estimator of pixel intensities given the limited block motion information available to the decoder. Although overlapped techniques have been observed to reduce blocking artifacts in video coding, this analysis establishes for the first time how (and why) OBMC can offer substantial reductions in prediction error as well, even with no change in the encoder's search and no extra side information. Performance can be further enhanced with the use of state variable conditioning in the compensation process. We describe the design of optimized windows for OBMC. We also demonstrate how, with additional encoder complexity, a motion estimation algorithm optimized for OBMC offers further significant gains in compensation accuracy. Overall mean-square prediction improvements in the range of 16 to 40% (0.8 to 2.2 dB) are demonstrated     

Motion estimation methods for overlapped block motion compensation

An extension of conventional block motion compensation (BMC), overlapped block motion compensation (OBMC) has been shown to reduce residual errors and blocking effects in motion-compensated video. However, the overlap creates a noncausal spatial dependence between blocks and complicates motion estimation (ME) for OBMC. Iterative methods have traditionally been employed for overlapped block motion estimation (OBME). For compression, the rate for the motion vector field (MVF) may also be constrained. This work considers several rate-constrained OBME algorithms, both iterative and noniterative. Experiments demonstrate that a simple raster-scan algorithm is effective as a suboptimal, noniterative solution, with comparable or better rate-distortion performance and computational complexity than iterative OBME algorithms. Depending on the application, either this method or a simple block-matching algorithm plus iteration are the most attractive of the tested OBME schemes.     

Extended analysis of motion-compensated frame difference for block-based motion prediction error.

In the past, most design and optimization work on hybrid video codecs relied mainly on experimental evidence. A proper theoretical model is always desirable, since this allows us to explain the phenomena of existing codecs and to design better ones. In this paper, we make use of the first-order Markov model to derive an approximated separable autocorrelation model for the block-based motion compensation frame difference (MCFD) signal. A major assumption of our derivation is that the net deformation of pixels is directional, in general, rather than a uniform error distribution in a block. We have also shown that the imperfect block-based motion compensation is significant to the theoretical study and the behavior of motion-compensated codecs. Results of our experimental work show that the derived model can describe the statistical characteristics of the MCFD signals accurately. The model also shows that the imperfectly formulated block-based motion compensation can result in an incorrect MCFD autocorrelation function while, conversely, it can form a better block-based motion compensation scheme.     

A parametric solution for optimal overlapped block motioncompensation

We find the optimal window for overlapped block motion compensation (OBMC) by statistically modeling the motion field, the field of block motion estimates and their relationship. This enables us to show how the optimal OBMC window is affected by random field parameters, such as the variance of the motion field and the correlation coefficients of both the intensity field and the motion field. The OBMC window obtained in this fashion is shown to have good performance in reducing the prediction error. Furthermore, this parametric solution provides insight into motion uncertainty and the overlapped motion compensation process.     

New windowing techniques for variable-size block motioncompensation

The conventional overlapped block motion compensation (OBMC) technique, although effective in reducing the blocking effect for fixed-size partitioned frames, cannot be readily used for a frame partitioned region-wise or using variable-size blocks. The generalised OBMC (GOBMC) method, even though generally applicable, is not very effective in reducing the blocking effect and prediction error. Two windowing techniques are presented to reduce the blocking effect for a frame partitioned region-wise or using variable-size blocks. In the first technique, a virtual re-partitioning operation is employed, which maps a partitioned frame into its corresponding fully partitioned frame at the bottom level of the quadtree so that each resulting block has eight neighbouring blocks. In the second technique, the virtual re-partitioning operation for a given block (region) is carried out adaptively and performed locally; however, blocks (regions) need not always be virtually partitioned to the bottom level. Compared to the GOBMC method, the proposed techniques make use of more pixels in the close vicinity of boundaries of the regions in the windowing operation. Simulation results are included of applying the proposed techniques on a number of MPEG video sequences. These results indicate that the proposed techniques are superior to the GOBMC method in terms of reducing the prediction error as well as the blocking effect     

Efficiency analysis of multihypothesis motion-compensatedprediction for video coding

Overlapped block motion compensation or B-frames are examples of multihypothesis motion compensation where several motion-compensated signals are superimposed to reduce the bit-rate of a video codec. This paper extends the wide-sense stationary theory of motion-compensated prediction (MCP) for hybrid video codecs to multihypothesis motion compensation. The power spectrum of the prediction error is related to the displacement error probability density functions (pdfs) of an arbitrary number of hypotheses in a closed-form expression. We then study the influence of motion compensation accuracy on the efficiency of multihypothesis motion compensation as well as the influence of the residual noise level and the gain from optimal combination of N hypotheses. For the noise-free limiting case, doubling the number of (equally good) hypotheses can yield a gain of up to 1/2 bits/sample, while doubling the accuracy of motion compensation can additionally reduce the bit-rate by up to 1 bit/sample independent of N. For realistic noise levels, it is shown that the introduction of B-frames or overlapped block motion compensation can provide larger gains than doubling motion compensation accuracy. Spatial filtering of the motion-compensated candidate signals becomes less important if more hypotheses are combined. The critical accuracy beyond which the gain due to more accurate motion compensation is small moves to larger displacement error variances with increasing noise and increasing number of hypotheses N. Hence, sub-pel accurate motion compensation becomes less important with multihypothesis MCP. The theoretical insights are confirmed by experimental results for overlapped block motion compensation, B-frames, and multiframe motion-compensated prediction with up to eight hypotheses from ten previous frames.     

A multistage motion vector processing method for motion-compensated frame interpolation.

In this paper, a novel, low-complexity motion vector processing algorithm at the decoder is proposed for motion-compensated frame interpolation or frame rate up-conversion. We address the problems of having broken edges and deformed structures in an interpolated frame by hierarchically refining motion vectors on different block sizes. Our method explicitly considers the reliability of each received motion vector and has the capability of preserving the structure information. This is achieved by analyzing the distribution of residual energies and effectively merging blocks that have unreliable motion vectors. The motion vector reliability information is also used as a prior knowledge in motion vector refinement using a constrained vector median filter to avoid choosing identical unreliable one. We also propose using chrominance information in our method. Experimental results show that the proposed scheme has better visual quality and is also robust, even in video sequences with complex scenes and fast motion.     

自适应联合相邻运动矢量的运动补偿插值算法

帧率上采样作为一种视频后处理技术,通过对原始视频插值得到高帧率视频,满足人们对高帧率视频的需求.传统基于重叠块的插值补偿算法会带来块效应或鬼影现象.为了解决这一问题,人们提出联合匹配块及其相邻块预测的方法,但是复杂度高,效果不明显.基于以上几点,本文提出一种自适应联合相邻运动矢量的运动补偿插值算法(Joint Motion-Compensated In-terpolation Algorithm Using Adjacent Block Motion Vectors Adaptively,AJ-MCI).在该算法中,将运动矢量矫正和运动补偿插值算法相结合,同时运动补偿模块中自适应地联合相邻匹配块,以最大限度刻画真实运动轨迹.实验结果表明,本文算法能很好的提升视频的主客观质量,同时保持较低计算复杂度.     

Optimal temporal interpolation filter for motion-compensated frame rate up conversion.

Frame rate up conversion (FRUC) methods that employ motion have been proven to provide better image quality compared to nonmotion-based methods. While motion-based methods improve the quality of interpolation, artifacts are introduced in the presence of incorrect motion vectors. In this paper, we study the design problem of optimal temporal interpolation filter for motion-compensated FRUC (MC-FRUC). The optimal filter is obtained by minimizing the prediction error variance between the original frame and the interpolated frame. In FRUC applications, the original frame that is skipped is not available at the decoder, so models for the power spectral density of the original signal and prediction error are used to formulate the problem. The closed-form solution for the filter is obtained by Lagrange multipliers and statistical motion vector error modeling. The effect of motion vector errors on resulting optimal filters and prediction error is analyzed. The performance of the optimal filter is compared to nonadaptive temporal averaging filters by using two different motion vector reliability measures. The results confirm that to improve the quality of temporal interpolation in MC, the interpolation filter should be designed based on the reliability of motion vectors and the statistics of the MC prediction error.     

An analysis of the efficiency of different SNR-scalable strategies for video coders.

In this paper, we analyze the efficiency of three signal-to-noise scalable strategies for video coders using single-loop motion-compensated prediction (MCP). In our analysis, we assume the video sequences have uniform and constant translational motion and we model MCP as a stochastic filter. We also assume an exponential model for the distortion-rate function of the intraframe coding. The analysis is divided into two parts: the steady-state analysis and the transient analysis. In the first part, only the steady-state response of the coders is taken into account, and, thus, this analysis allows us to asses approximately the efficiency of coders with long input sequences. The transitory analysis considers both the transient and the steady-state responses of the coders, which makes it appropriate to analyze coders using periodic intraframes or with short input sequences. To validate our analysis, theoretical results have been compared to results from encodings of real video sequences using the scalable adaptive motion compensated wavelet video coder. We show that our theoretical analysis effectively describes qualitatively the main trends of every video coding strategy.     

Edge oriented block motion estimation for video coding

Intensity-based block motion estimation and compensation algorithms are widely used to exploit temporal redundancies in video coding, although they suffer from several drawbacks. One of the problems is that blocks located on boundaries of moving objects are not estimated accurately. It causes poor motion-compensated prediction along the moving edges to which the human visual system is very sensitive. By considering the characteristics of block motions for typical image sequences, an intelligent classifier is proposed to separate blocks containing moving edges to improve on conventional intensity-based block matching approaches. The motion vectors of these blocks are computed using edge matching techniques, so that the motion-compensated frames are tied more closely to the physical features. The proposed method can then make use of this accurate motion information for edge blocks to compute the remaining non-edged blocks. Consequently, a fast and efficient block motion estimation algorithm is developed. Experimental results show that this approach gives a significant improvement in accuracy for motion-compensated frames and computational complexity, in comparison with the traditional intensity-based block motion estimation methods     

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.     

Temporal image sequence prediction using motion field interpolation

A new method for motion-compensated temporal prediction of image sequences is proposed. Motion vector fields in natural scenes should possess two basic properties. First, the field should be smoothly varying within moving objects to compensate for nonrigid or rotational motion, and scaling of objects. Second, the field should be discontinuous along the boundaries of the objects. In the proposed method the motion vector field is modelled using finite element methods and interpolated using adaptive interpolators to satisfy the above-stated requirements. This is particularly important when only very sparse estimates of motion vector fields are available in the decoder due to bit-rate constraints limiting the amount of overhead information that can be transmitted. The proposed prediction method can be applied for low-bit-rate video coding in conventional codecs based on motion-compensated prediction and transform coding, as well as in model-based codecs. The performance of the proposed method is compared with standard motion-compensated prediction based on block matching. It is shown that for simple video telephony scenes a reduction of more than 30% in the energy of the prediction error can be achieved with an unchanged number of transmitted motion vectors and with only a modest increase in computational complexity. When implemented in an H.261 codec the new prediction method can improve the peak SNR 1–2 dB producing a significant visual improvement.     

Object-based estimation of dense motion fields

Motion estimation belongs to key techniques in image sequence processing. Segmentation of the motion fields such that, ideally, each independently moving object uniquely corresponds to one region, is one of the essential elements in object-based image processing. This paper is concerned with unsupervised simultaneous estimation of dense motion fields and their segmentations. It is based on a stochastic model relating image intensities to motion information. Based on the analysis of natural images, a region-based model of motion-compensated prediction error is proposed. In each region the error is modeled by a white stationary generalized Gaussian random process. The motion field and its segmentation are themselves modeled by a compound Gibbs/Markov random field accounting for statistical bindings in spatial direction and along the direction of motion trajectories. The a posteriori distribution of the motion field for a given image sequence is formulated as an objective function, such that its maximization results in the MAP estimate. A deterministic multiscale relaxation technique with regular structure is employed for optimization of the objective function. Simulation results are in a good agreement with human perception for both the motion fields and their segmentations.     

Implementation of Multiple Macroblock Mode Overlapped Block Motion Compensation for Wavelet Video Coding

This paper proposes a hybrid video coding framework based on discrete wavelet transform and multiple macroblock mode overlapped block motion compensation (OBMC). Studying the neighborhood in multiple macroblock mode situations, we set rules for the selection of neighboring blocks in OBMC. Based on experimental results, the raised cosine window and the best neighboring blocks are chosen for their outstanding performance. The multiple macroblock mode OBMC has a good performance in reducing the blocking effect, and the coding efficiency is improved. The proposed scheme can provide a 1 dB coding gain compared to MPEG-4, and its performance is close to the latest H.264 standard. From a subjective point of view, the new framework is also better than the standards.     

Predictive RD optimized motion estimation for very low bit-ratevideo coding

Predictive rate-distortion (RD) optimized motion estimation techniques are studied and developed for very low bit-rate video coding. Four types of predictors are studied: mean, weighted mean, median, and statistical mean. The weighted mean is obtained using conventional linear prediction techniques. The statistical mean is obtained using a finite-state machine modeling method based on dynamic vector quantization. By employing prediction, the motion vector search can then be constrained to a small area. The effective search area is reduced further by varying its size based on the local statistics of the motion field, through using a Lagrangian as the search matching measure and imposing probabilistic models during the search process. The proposed motion estimation techniques are analyzed within a simple DCT-based video coding framework, where an RD criterion is used for alternating among three coding modes for each 8×8 block: motion only, motion-compensated prediction and DCT, and intra-DCT. Experimental results indicate that our techniques yield very good computation-performance tradeoffs. When such techniques are applied to an RD optimized H.263 framework at very low bit rates, the resulting H.263 compliant video coder is shown to outperform the H.263 TMN5 coder in terms of compression performance and computations simultaneously     

Rate-Distortion Optimized Motion-Compensated Prediction for Packet Loss Resilient Video Coding

A rate-distortion optimized motion-compensated prediction method for robust video coding is proposed. Contrasting methods from the conventional literature, the proposed approach uses the expected reconstructed distortion after transmission, instead of the displaced frame difference in motion estimation. Initially, the end-to-end reconstructed distortion is estimated through a recursive per-pixel estimation algorithm. Then the total bit rate for motion-compensated encoding is predicted using a suitable rate distortion model. The results are fed into the Lagrangian optimization at the encoder to perform motion estimation. Here, the encoder automatically finds an optimized motion compensated prediction by estimating the best tradeoff between coding efficiency and end-to-end distortion. Finally, rate-distortion optimization is applied again to estimate the macroblock mode. This process uses previously selected optimized motion vectors and their corresponding reference frames. It also considers intraprediction. Extensive computer simulations in lossy channel environments were conducted to assess the performance of the proposed method. Selected results for both single and multiple reference frames settings are described. A comparative evaluation using other conventional techniques from the literature was also conducted. Furthermore, the effects of mismatches between the actual channel packet loss rate and the one assumed at the encoder side have been evaluated and reported in this paper     

Robust global motion estimation oriented to video object segmentation.

Most global motion estimation (GME) methods are oriented to video coding while video object segmentation methods either assume no global motion (GM) or directly adopt a coding-oriented method to compensate for GM. This paper proposes a hierarchical differential GME method oriented to video object segmentation. A scheme which combines three-step search and motion parameters prediction is proposed for initial estimation to increase efficiency. A robust estimator that uses object information to reject outliers introduced by local motion is also proposed. For the first frame, when the object information is unavailable, a robust estimator is proposed which rejects outliers by examining their distribution in local neighborhoods of the error between the current and the motion-compensated previous frame. Subjective and objective results show that the proposed method is more robust, more oriented to video object segmentation, and faster than the referenced methods.     

A Motion Picture Coding Algorithm Using Adaptive DCT Encoding Based on Coefficient Power Distribution Classification

A motion picture coding algorithm using motion-compensated interframe prediction and the adaptive discrete cosine transform (DCT) encoding technique is proposed. High coding efficiency is obtained by the adaptive DCT encoding technique in which encoding parameters are fitted to widely varying characteristics of the interframe differential signal. Segmented DCT subblocks of interframe prediction error are classified into categories based on their coefficient power distribution characteristics. The adaptation gain results from using a suitable variable word length code set designated by the above classification for encoding each quantization index of DCT coefficients. In addition, a new coding parameter control method is introduced based on the information rate estimation of the current frame. This classification promotes high stability because good estimation accuracy of bits consumption for each DCT subblock is obtained by utilizing the category indexes. Simulation results show that the proposed algorithm has enough coding efficiency to transmit videoconferencing motion pictures through a 384 kbit/s channel.