Fast mode decision algorithm for intra prediction in H.264/AVC with integer transform and adaptive threshold

Compared with other existing video coding standards, H.264/AVC can achieve a significant improvement in compression performances. A robust criterion named the rate distortion optimization (RDO) is employed to select the optimal coding modes and motion vectors for each macroblock (MB), which achieves a high compression ratio while leading to a great increase in the complexity and computational load unfortunately. In this paper, a fast mode decision algorithm for H.264/AVC intra prediction based on integer transform and adaptive threshold is proposed. Before the intra prediction, integer transform operations on the original image are executed to find the directions of local textures. According to this direction, only a small part of the possible intra prediction modes are tested for RDO calculation at the first step. If the minimum mean absolute error (MMAE) of the reconstructed block corresponding to the best mode is smaller than an adaptive threshold which depends on the quantization parameter (QP), the RDO calculation is terminated. Otherwise, more possible modes need to be tested. The adaptive threshold aims to balance the compression performance and the computational load. Simulation results with various video sequences show that the fast mode decision algorithm proposed in this paper can accelerate the encoding speed significantly only with negligible PSNR loss or bit rate increment. This work is supported in part by China National Natural Science Foundation (CNSF) under Project No.60572045, the Ministry of Education of China Ph.D. Program Foundation under Project No.20050698033, and by a Cooperation Project (2005.7– 2007.7) with Microsoft Research Asia.     

一种H.264/AVC帧内预测模式的快速选择算法

H.264/AVC帧内预测技术采用率失真优化策略进行最优化编码模式选择,提高了I帧的编码效率,但同时也提高了计算复杂度。本文提出了一种帧内预测模式的快速选择算法,基于亮度块的方向特性,通过一些复杂度不大的计算,选择少数几个可能性较大的预测模式进行率失真代价计算,得到最佳亮度预测模式,并以 计算代替率失真代价计算选择最佳色度预测模式,降低了计算复杂度,提高了编码速度。实验结果表明,本文提出的算法在保证图像质量的同时,编码时间平均降低了48%,而码率增加很小。     

A Fast Intra Skip Detection Algorithm for H.264/AVC Video Encoding

A fast intra skip detection algorithm based on the rate‐distortion (RD) cost for an inter frame (P‐slices) is proposed for H.264/AVC video encoding. In the H.264/AVC coding standard, a robust rate‐distortion optimization technique is used to select the best coding mode and reference frame for each macroblock (MB). There are three types of intra predictions according to profiles. These are 16×16 and 4×4 intra predictions for luminance and an 8×8 intra prediction for chroma. For the high profile, an 8×8 intra prediction has been added for luminance. The 4×4 prediction mode has 9 prediction directions with 4 directions for 16×16 and 8×8 luma, and 8×8 chrominance. In addition to the inter mode search procedure, an intra mode search causes a significant increase in the complexity and computational load for an inter frame. To reduce the computational load of the intra mode search at the inter frame, the RD costs of the neighborhood MBs for the current MB are used and we propose an adaptive thresholding scheme for the intra skip extraction. We verified the performance of the proposed scheme through comparative analysis of experimental results using joint model reference software. The overall encoding time was reduced up to 32% for the IPPP sequence type and 35% for the IBBPBBP sequence type.     

H.264 High Profile的帧内预测模式快速判决算法研究

为降低H.264 High Profile帧内预测模式判决的复杂度,提出了2方面的改进:1)在模式判决的第1阶段即块大小判决,提出了1种自适应阈值来排除不可能的块大小;2)在模式判决的第2阶段即预测模式判决,利用8×8模式判决的最优模式及最可能模式和SATD值来减少4×4的待选模式。与JM参考软件的对比结果表明,在不影响图像质量的前提下,提出的算法能减少平均61%的时间。     

VLC table prediction for CAVLC in H.264/AVC using correlation,statistics, and structural characteristics of mode information

The H.264/AVC video coding standard adopted context-based adaptive variable length coding (CAVLC) as an entropy coding tool. By combining adaptive variable length coding (VLC) with context modeling, we can achieve a high coding performance. However, CAVLC in H.264/AVC has the problem that VLC table prediction is not always accurate. In this paper, we propose a new VLC table prediction algorithm using the correlation between coding modes of the current and neighboring sub-blocks and the statistics of mode distribution in both intra and inter frames. In addition, we can further increase correctness of VLC table prediction considering the structural characteristics of mode information in inter frames. Experimental results show that the proposed algorithm increases correctness of VLC table prediction by 10.07% and reduces the bit rate by 1.21% on average without significant increment of encoding time.     

一种新的H.264/AVC帧内编码快速算法

针对H.264/AVC帧内编码算法采用率失真优化(RDO)算法提升编码性能导致运算复杂度增加这一问题,提出了一种新的帧内编码快速算法。该算法采用待预测块的纹理方向误差值判断待编码块的纹理特征,结合相邻块的预测模式相关性减少须遍历预测模式的数量,并结合全零块检测的提前终止判定准则加快编码速度。实验结果表明,与标准算法相比,该算法在保证输出码率和图像质量基本不变的情况下能够将帧内编码时间减少约67.2%,显著提高了H.264的帧内编码效率。     

Improved mode decision algorithm based on residues and early zero block detection in H.264/AVC

Video compression standard H.264/AVC outperforms previous standards in terms of coding efficiency but at the cost of higher computational complexity. In H.264/AVC, the variable block size full motion estimation is the most time-consuming operation. This paper presents a method to reduce the complexity of motion estimation in two stages. The first stage exploits the similarities between frames for early SKIP mode decision for a macroblock (MB) based upon a criteria formulated on the basis of the statistics of the frame difference residues. MBs that fail to qualify for the SKIP mode in the first stage spills over to the second stage where mode decision depends upon the number of zero blocks (ZB) in the MB. The study of the full search motion estimation on different sequences show that there is a strong dependence between the number of ZBs in a MB and the likelihood of a particular mode being selected. The proposed algorithm utilizes this relationship for early mode decision for a MB. The algorithm is evaluated using a wide range of test sequences from different classes. Experimental results show that the proposed algorithm gives considerable saving in encoding time and search points in the range of 36–87%. Furthermore, despite the reduction in computational complexity, the coding efficiency (picture quality and bitrate) in the proposed method is comparable to the H.264/AVC standard software Joint Model (JM12.4).     

General Architecture for MPEG-2/H.263/H.264/AVC to H.264/AVC Intra Frame Transcoding

The latest international video-coding standard H.264/AVC significantly achieves better coding performance compared to prior video coding standards such as MPEG-2 and H.263, which have been widely used in today’s digital video applications. To provide the interoperability between different coding standards, this paper proposes an efficient architecture for MPEG-2/H.263/H.264/AVC to H.264/AVC intra frame transcoding, using the original information such as discrete cosine transform (DCT) coefficients and coded mode type. Low-frequency components of DCT coefficients and a novel rate distortion cost function are used to select a set of candidate modes for rate distortion optimization (RDO) decision. For H.263 and H.264/AVC, a mode refinement scheme is utilized to eliminate unlikely modes before RDO mode decision, based on coded mode information. The experimental results, conducted on JM12.2 with fast C8MB mode decision, reveal that average 58%, 59% and 60% of computation (re-encoding) time can be saved for MPEG-2, H.263, H.264/AVC to H.264/AVC intra frame transcodings respectively, while preserving good coding performance when compared with complex cascaded pixel domain transcoding (CCPDT); or average 88% (a speed up factor of 8) when compared with CCPDT without considering fast C8MB. The proposed algorithm for H.264/AVC homogeneous transcoding is also compared to the simple cascaded pixel domain transcoding (with original mode reuse). The results of this comparison indicate that the proposed algorithm significantly outperforms the mode reuse algorithm in coding performance, with only slightly higher computation.     

Low complexity encoder optimization for HEVC

High Efficiency Video Coding (HEVC) improved the coding efficiency significantly. Compared to its predecessor H.264/AVC, it can provide equivalent subjective quality with more than 57% bit rate reduction. However, the improvement on coding efficiency is obtained at the expense of much more intensive computation complexity. In this paper, based on an overall analysis of computation complexity at the HEVC encoder, a low complexity encoder optimization scheme is proposed by reducing the number of available candidates for evaluation in terms of the intra prediction mode decision, early termination of coding unit (CU) splitting and adaptive reference frame selection. With the proposed scheme, the rate distortion optimization (RDO) technique of HEVC can be implemented in a low-complexity way for complexity-constrained encoders. Experimental results demonstrate that, compared with the original HEVC reference encoder implementation, the proposed optimization scheme can achieve more than 40% complexity reduction on average with coding performance degradation as only 0.43% which can be ignorable.     

快速帧内预测模式选择新方法

为了提高编码性能,H.264采用了RDO(率失真优化),但与此同时带来的是计算复杂度的增加.本文着重分析了H.264中快速帧内预测模式选择的问题.为了降低帧内预测模式选择的计算复杂度,提出了一种高效的快速帧内预测模式选择算法.首先,对Pan的基于边缘方向直方图的快速算法进行了改进,同时提出了基于参考象素特征的4×4快速帧内预测模式选择算法,并将两者进行了结合.实验结果表明,本文算法和H.264校验模型JM61相比,I帧编码时间降低61%~69%,而PSNR基本保持不变,输出码率仅略有增加;与Pan的基于边缘方向直方图快速算法相比,本文算法的I帧编码时间降低12%~33%,PSNR和输出码率均基本保持不变.     

融合宏块平坦度和时空相关性的预测模式选择算法

H.264/AVC以巨大编码复杂度为代价,在获得更高压缩率的同时,编码实时性也随之降低。针对视频编码中重要且耗时的帧间预测技术,分析了宏块平坦度和时空相关性,提出了一种快速的预测模式选择算法。仿真实验结果表明,本文提出算法与H.264/AVC(JM12.2)标准算法相比,在保持重建视频图像质量和输出码流结构的前提下,平均节省约70%的编码时间,并继承了H.264/AVC低码率的编码优势。     

Enhanced Inter Mode Decision Based on Contextual Prediction for P‐Slices in H.264/AVC Video Coding

We propose a fast macroblock mode prediction and decision algorithm based on contextual information for P‐slices in the H.264/AVC video standard, in which the mode prediction part is composed of intra and inter modes. There are nine 4×4 and four 16×16 modes in the intra mode prediction, and seven block types exist for the best coding gain based on rate‐distortion optimization. This scheme gives rise to exhaustive computations (search) in the coding procedure. To overcome this problem, a fast inter mode prediction scheme is applied that uses contextual mode information for P‐slices. We verify the performance of the proposed scheme through a comparative analysis of experimental results. The suggested mode search procedure increased more than 57% in speed compared to a full mode search and more than 20% compared to the other methods.     

Parallel fast inter mode decision for H.264/AVC encoding

For H.264/AVC encoding, the mode selection process consumes a large proportion of the overall computation. To reduce this burden, various fast mode decision algorithms have been proposed. The current fast mode decision algorithms usually exploit the relationship among the coding modes and use the context-based approach to reduce the number of modes to be checked for both intra coding and inter coding. The parallel capacity of hardware architectures are also taken into consideration. However, almost all the parallel fast mode decision designs are focusing on intra coding. In this paper, a hardware friendly parallel fast inter mode decision method is proposed. With the proposed method, the inter mode decision can be conducted efficiently in one pass and significant encoding speedup can be achieved with negligible coding efficiency loss. Moreover, the proposed method can be easily mapped to hardware architecture which can be used for the real-time video encoding.     

Improved lossless intra coding for H.264/MPEG-4 AVC.

A new lossless intra coding method based on sample-by-sample differential pulse code modulation (DPCM) is presented as an enhancement of the H.264/MPEG-4 AVC standard. The H.264/AVC design includes a multidirectional spatial prediction method to reduce spatial redundancy by using neighboring samples as a prediction for the samples in a block of data to be encoded. In the new lossless intra coding method, the spatial prediction is performed based on samplewise DPCM instead of in the block-based manner used in the current H.264/AVC standard, while the block structure is retained for the residual difference entropy coding process. We show that the new method, based on samplewise DPCM, does not have a major complexity penalty, despite its apparent pipeline dependencies. Experiments show that the new lossless intra coding method reduces the bit rate by approximately 12% in comparison with the lossless intra coding method previously included in the H.264/AVC standard. As a result, the new method is currently being adopted into the H.264/AVC standard in a new enhancement project.     

Fast mode decision algorithm for H.264 inter-prediction

A fast mode decision algorithm for H.264/AVC inter-prediction to reduce computational complexity of the H.264 encoder is presented. Experimental results show that the algorithm can save the entire encoding time by 77% on average while introducing only negligible loss in PSNR value and small increment of bit rate.     

基于H.264预测模式选择的并行算法

针对H.264编码器提出了一种基于线程级别的并行化算法,用于快速RDO模式决策,可以有效地解决H.264编码器帧内模式决策和帧间模式决策之间的数据依赖性,开发出线性级别的并行快速模式决策算法。此外,该方法可以容易地映射到硬件架构,同时采用改进的比特率估计算法和低复杂性的整数失真估计方法。实验结果表明,文中算法减少了总编码时间,降低了运动估计ME的计算开销,同时保持较低的PSNR损失和比特率增加。     

Enhanced SATD-based cost function for mode selection of H.264/AVC intra coding

In H.264/AVC, the concept of rate-distortion optimization (RDO) mode decision has proven to be an important coding tool. However, this mode decision method makes the encoding process extremely complex, especially in the computation of the rate-distortion cost function, which includes the computations of the sum of squared difference (SSD) between the original and reconstructed image blocks and context-based entropy coding of the block. In this paper, we propose an enhanced low-complexity cost function for H.264/AVC intra 4 × 4 and 8 × 8 mode selections. The enhanced cost function uses sum of absolute Hadamard-transformed differences (SATD) and mean absolute deviation of the residual block to estimate distortion part of the cost function. A threshold-based large coefficients count is also used for estimating the bit-rate part. The proposed method improves the rate-distortion performance of conventional fast cost functions while maintaining low complexity requirement. As a result, the encoding process can be significantly accelerated with the use of the proposed cost function. Simulation results confirm that the proposed method reduces about 83.74 % computation of intra encoding of JM 12.4 encoder with negligible rate-distortion performance degradation.     

Low-Complexity Intra-Coding Scheme for HEVC

Compared with H.264/AVC, the latest video standard High Efficiency Video Coding (HEVC) known as H.265 improves the coding efficiency by adopting the quadtree splitting structure which is flexible in representing various textural and structural information in images. However, the computational complexity is dramatically increased, especially in the intra-mode decision process owing to supporting more partitions and modes. In this paper, we propose a low-complexity algorithm for HEVC intra-coding, which consists of a fast coding unit (CU) size decision (FCUSD) method and a fast prediction unit (PU) mode decision (FPUMD) method. In FCUSD, unnecessary CU sizes are skipped early according to the depth level of neighboring CUs and the rate distortion (RD) cost threshold derived from the former coded frame. In FPUMD, the PU mode and RD cost correlations between different depth levels are utilized to terminate unnecessary candidate modes. Experimental results demonstrate that the proposed algorithm can achieve about 50.99 % computational complexity reduction on average with 1.18 % BD-rate increase and 0.08 dB BD-psnr loss.     

Efficient Inter Prediction Mode Decision Method for Fast Motion Estimation in High Efficiency Video Coding

High Efficiency Video Coding (HEVC) is the most recent video coding standard to achieve a higher coding performance than the previous H.264/AVC. In order to accomplish this improved coding performance, HEVC adopted several advanced coding tools; however, these cause heavy computational complexity. Similar to previous video coding standards, motion estimation (ME) of HEVC requires the most computational complexity; this is because ME is conducted for three inter prediction modes — namely, uniprediction in list 0, uniprediction in list 1, and biprediction. In this paper, we propose an efficient inter prediction mode (EIPM) decision method to reduce the complexity of ME. The proposed EIPM method computes the priority of all inter prediction modes and performs ME only on a selected inter prediction mode. Experimental results show that the proposed method reduces computational complexity arising from ME by up to 51.76% and achieves near similar coding performance compared to HEVC test model version 10.1.     

Fast Interframe mode decision algorithm based on mode mapping and MB activity for MPEG-2 to H.264/AVC transcoding

Recently the latest video coding standard H.264/AVC is widely used for the mobile and low bitrate video codec in the various multimedia terminals. On the other hand, the MPEG-2 MP@HL codec has become the center of digital video contents since it is the standard codec for the Digital TV (DTV). To provide the bridge between the contents in MPEG-2 and mobile terminals, the transcoding of MPEG-2 contents into H.264/AVC format is an inevitable technology in the digital video market. The main bottleneck in the process lies in the computational complexity. In H.264/AVC, the variable block size (VBS) mode decision (MD) is used in the Interframe for the improved performance in the motion compensated prediction. For the macroblock (MB) which cannot be accurately predicted with one motion vector (MV), it is partitioned into smaller blocks and predicted with different MVs. In addition, SKIP and Intra modes are also permitted in the Interframe MD of H.264/AVC to further ameliorate the encoding performance. With the VBS MD technology, the Inter prediction accuracy can be improved significantly. However, the incidental side-effect is the high computational complexity. In this paper, we propose a fast Interframe MD algorithm for MPEG-2 to H.264/AVC transcoding. The relationships between SKIP and Intra modes are detected at first to map these two kinds of modes directly from MPEG-2 to H.264/AVC. And then the MB activity will be scaled by the residual DCT energy obtained from the MPEG-2 decoding process to estimate the block sizes of the MB mode for H.264/AVC Interframe MD. In our proposed method, the original redundant candidate modes can be eliminated effectively, resulting in the reduction of the computational complexity. It can reduce about 85% Rate-to-Distortion Cost (RDCost) computing and 45% entire processing time compared with the well-known cascaded transcoder while maintaining the video quality.