Iterative search strategy with selective bi-directional prediction for low complexity multiview video coding

The multiview video coding (MVC) extension of H.264/AVC is the emerging standard for compression of impressive 3D and free-viewpoint video. The coding structure in MVC adopts motion and disparity estimation to exploit temporal and inter-view dependencies in MVC. It results in a considerable increase in encoding complexity. Most of the computational burden comes from uni-directional and bi-directional prediction. In this paper, an iterative search strategy is designed to speed up the uni-directional prediction in MVC. It can work with an adaptive search range adjustment through a confidence measure of a loop constraint to obtain both motion and disparity vectors jointly. Furthermore, a selective bi-directional prediction algorithm is proposed to enhance the coding performance by analyzing the statistical characteristics of bi-directional prediction in MVC. Experimental results demonstrate that, by using the proposed fast search, the temporal and inter-view redundancies of multiview video can be eliminated sufficiently with low complexity.     

Improved inter-view correlations for low complexity MV-HEVC

The more advanced multi-view extension, MV-HEVC, effectively exploits visual similarities between multi-view videos and enables high compression efficiency. Each view in the multi-view sequence depends on the captured scene, the distance between cameras and recording angles. Increasing the distance between dependent viewpoints generates an inter-view disparity. This impacts the inter-view similarities, affects the disparity estimation and further increases the computational complexity of the MV-HEVC encoder. In this paper, an efficient earlier disparity estimation is proposed for low complexity MV-HEVC. This algorithm is based on reducing the complexity of disparity estimation by eliminating the inter-view offset. Moreover, the inter-view similarities are controlled by considering the reliability of each coding unit size in the search range. This reliability is estimated by reducing the number of searching points within a new limited window. For reliable motion estimation, we further proposed an earlier decision of coding units splitting in the dependent views according to those in the reference views. Experimental results show that the proposed algorithm can achieve an average encoding time saving of 20.37%–40,61% with marginal performance degradation.     

Content-Aware Fast Motion Estimation Algorithm

In this paper, we propose the Content-Aware Fast Motion Estimation Algorithm (CAFME) that can reduce computation complexity of motion estimation (ME) in H.264/AVC while maintaining almost the same coding efficiency. Motion estimation can be divided into two phases: searching phase and matching phase. In searching phase, we propose the Simple Dynamic Search Range Algorithm (SDSR) based on video characteristics to reduce the number of search points (SP). In matching phase, we integrate the Successive Elimination Algorithm (SEA) and the integral frame to develop a new SEA for H.264/AVC video compression standard, called Successive Elimination Algorithm with Integral Frame (SEAIF). Besides, we also propose the Early Termination Algorithm (ETA) to early terminate the motion estimation of current block.We implement the proposed algorithm in the reference software JM9.4 of H.264/AVC and the experimental results show that our proposed algorithm can reduce the number of search points about 93.1%, encoding time about 42%, while maintaining almost the same bitrate and PSNR.     

Fast macroblock encoding algorithm based on rate-distortion activity for multiview video coding

Multiview video coding (MVC) is the appendix H of H.264/AVC, and it requires a great amount of time to compress multiple viewpoints׳ video with complex prediction structures. To reduce the whole computational complexity of MVC, this paper proposes a fast macroblock (MB) encoding algorithm based on rate-distortion (RD) activity, and it includes the fast mode decision and the fast motion/disparity estimation. First, the RD activity type of the current MB is calculated by utilizing the Skip/Direct RD cost and the average RD costs of classified MB modes. Then, through utilizing the RD activity type and RD costs of the estimated modes, the selection of candidate modes, the early decision of Skip/Direct mode, and the reduction of Inter8×8 mode estimation are all presented in the fast mode decision. By using the RD activity type and the correlations of vectors, the selection of search center and the prediction of search range are introduced in the fast motion/disparity estimation. In addition, the proposed algorithm can be applied to temporal and inter-view views as well as anchor and non-anchor frames. An experiment with a wide range of video scenes, camera setups and quantization parameters was implemented, and the results confirmed that the proposed algorithm can reduce the encoding time significantly while maintaining a similar RD performance as the original MVC encoder. Compared to the state-of-the-art algorithms, the proposed algorithm also demonstrated better performances in the various test cases.     

一种适用于AVS-M的自适应快速运动估计算法

为了减小移动视频编码标准(AVS-M)中运动估计模块的复杂度,提出了一种快速、有效的块匹配运动估计算法.该算法充分利用了视频图像中运动矢量场的中心偏置特性和时空相关性,根据运动类型自适应的选择搜索起点和搜索策略,结合改进的搜索模板和高效搜索中止准则,有效地降低了运动估计的运算量.实验结果表明,该算法在保证搜索精度的同时,大大减少了搜索点数.     

A variable block size motion estimation algorithm for real-time H.264 video encoding

This paper presents an efficient variable block size motion estimation algorithm for use in real-time H.264 video encoder implementation. In this recursive motion estimation algorithm, results of variable block size modes and motion vectors previously obtained for neighboring macroblocks are used in determining the best mode and motion vectors for encoding the current macroblock. Considering only a limited number of well chosen candidates helps reduce the computational complexity drastically. An additional fine search stage to refine the initially selected motion vector enhances the motion estimator accuracy and SNR performance to a value close to that of full search algorithm. The proposed methods result in over 80% reduction in the encoding time over full search reference implementation and around 55% improvement in the encoding time over the fast motion estimation algorithm (FME) of the reference implementation. The average SNR and compression performance do not show significant difference from the reference implementation. Results based on a number of video sequences are presented to demonstrate the advantage of using the proposed motion estimation technique.     

VLSI Architecture of Block Matching Algorithms for Motion Estimation in High Efficiency Video Coding

High-efficiency video coding (HEVC) is a latest video coding standard and the motion estimation unit is the most important block. The work presents the different types of Matching Criteria for Block-Based Motion Estimation technique in HEVC standard. HEVC requires fast motion estimation algorithms to have better real time performance. The hardware implementation of motion estimation helps to achieve high speed though parallel processing. An improved block matching technique is designed with reduced blocks for HEVC. The proposed method has less execution time where only blocks having motion are compared for prediction computation. The searching time complexity is dependent on the number of blocks that are having motion. The searching time of frame having small motion can be reduced to 80–85% as compared to the traditional full search algorithm. In the paper, sum of absolute difference, mean square error and mean absolute difference are computed to find the best matching algorithm for HEVC. However, SAD has less computational complexity with compare to other matching criteria. The results suggest that proposed motion estimation algorithm has better performance with compare to similar previous work.

     

基于矢量预测的快速运动估计搜索算法

基于H.264视频编码标准的编解码过程中,运动估计的时间大概要占总编码时间的70%(1个参考帧)到90%(5个参考帧)。对于H.264标准的新特点,传统的全搜索算法的精度高,但计算量太大,不能应用于实时处理;经典的菱形等算法搜索模式简单,易于实现,但容易陷入局部无穷小。采用了一种基于运动矢量预测的快速运动估计搜索算法。该方法首先利用运动矢量的时、空间相关性得到预测矢量,然后利用非对称十字型搜索确定运动估计的起始点,最后采用经典的菱形算法进行运动估计。实验结果表明,相比UMHexagonS快速搜索算法,该算法能够在码率增加不超过1%,信噪比下降不超过0.1 dB的情况下,运动估计速度有较大提高。     

基于HEVC六边形运动估计算法的VLSI设计

运动估计是HEVC中计算量最大、耗时最多的模块。为了加速编码过程,设计了适用于HEVC运动估计的六边形搜索算法的VLSI架构。该架构支持HEVC标准中的尺寸可变块设计,并且充分考虑六边形模板的数据复用特点,在PE阵列中使用流水线的组织策略,有效降低了片上缓存的访问次数。采用SMIC 65 nm工艺综合该电路,最高工作频率可达100 MHz,电路规模101 k门,能够满足高清视频（1 920×1 080,60帧/秒）的实时编码要求。     

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).     

一种基于子搜索格雷码核的快速视频块运动估计算法

快速视频块运动估计是视频编码中的一个重要问题。在格雷码核( GCK)算法的基础上,提出一种改进的子搜索格雷码核( Sub-GCK)算法。理论上的计算复杂度分析表明：提出的子搜索格雷码核算法的运算量大约为原始格雷码核算法的22.1%。实验比较了子搜索格雷码核算法、原始格雷码核算法和其他几种常见的运动估计算法的编码性能,结果显示：新算法在保证编码质量的前提下,有效降低了运动估计时间,时间约为原始格雷码核算法的41.9%。     

一种用于H.264的改进UMHexagonS算法

在运动估计中,H.264以增加的编码复杂性为代价获得了非常好的性能.基于对现有文献的研究,提出了一种改进的UMHexagonS算法.首先,在UMHexagonS的非对称十字交叉搜索中增加了8个搜索点,以改善算法在垂直方向上运动的适应性;其次,为提高编码效率,将UMHexagonS算法的小矩形窗口全搜索分为两个步骤;然后,在UMHexagonS的非均匀多层次六边形网格搜索中采用了一种并行算法,进一步提高算法的运动估计性能;最后,采用三点搜索法来替代小菱形搜索,原始的小菱形搜索只作为满足提前终止最佳情况的跳转对象.仿真表明,相比于UMHexagonS算法,提出的改进算法在视频压缩编码速度和重建图像的质量都具有更好的性能.     

Selective Disparity Estimation and Variable Size Motion Estimation Based on Motion Homogeneity for Multi-View Coding

Multi-view video coding (MVC) is an ongoing standard in which variable size disparity estimation (DE) and motion estimation (ME) are both employed to select the best coding mode for each macroblock (MB). This technique achieves the highest possible coding efficiency, but it results in extremely large encoding time which obstructs it from practical use. In this paper, a fast DE and ME algorithm based on motion homogeneity is proposed to reduce MVC computational complexity. The basic idea of the method is to utilize the spatial property of motion field in prediction where DE and variable size ME are needed, and only in these regions DE and variable size ME are enabled. The motion field is generated by the corresponding motion vectors (MVs) in spatial window. Simulation results show that the proposed algorithm can save 63% average computational complexity, with negligible loss of coding efficiency.      

Efficient tree structured motion estimation using successive elimination

In H.264/AVC, tree structured motion estimation enhances the coding efficiency significantly while dramatically increasing the computational complexity of block matching. In the paper, a successive elimination algorithm (SEA) is implemented in tree structured motion estimation with a simple and effective method to determine the initial motion vector, which exploits the strong correlation among the partially overlapped variable-size blocks. With identical performance to a full search algorithm, computations for block matching can be reduced to 1%-20%. Further, the SEA can be improved by incorporating two early termination conditions, then named 'Quick SEA'. Finally, a novel fast motion estimation algorithm, successive elimination diamond search (SEDS), is proposed by efficiently integrating the Quick SEA and a modified diamond search pattern. Simulation results show that the proposed Quick SEA can reduce the computational complexity of block matching by 3-5 times compared to the basic SEA. SEDS further reduces by about one-half the computations of Quick SEA. With similar rate distortion performance, 0.2%-1% block matching distortion is calculated for SEDS with corresponding speed-up factors of 100 to 500 in comparison with the full search algorithm.     

Parallel spiral search algorithm applied to integer motion estimation

Thanks to its flexible coding structure, high-efficiency video coding (HEVC) can save more coding bit rates than the previous standard, H.264. However, it also increases the complexity of integer-pixel motion estimation (IME). To speed up the encoding process, we propose a parallel spiral search (PSS) algorithm, which features the following characteristics and advantages. First, the proposed algorithm is hardware-friendly. PSS has both a fix search order that cuts the correlation between search points and a high data reuse level that facilitates the pipeline application in hardware implementation. Second, the PSS algorithm processes all prediction units (PU) blocks in parallel, which speeds up the RD calculation. Finally, the early termination strategy is proposed to end the search for unnecessary search points and further reduce search time. Experimental results show that the proposed algorithm outperforms other popular hardware-oriented IME algorithms in terms of coding speed, with the same loss of RD performance. Compared with the default full search algorithm (FSA) in the HEVC test model HM-16.7, the proposed algorithm achieves average time saving ratio of up to 92.55%, with BD-PSNR loss of 0.056 dB and an increase by 1.38% in terms of BD-BR.     

一种基于H.264/AVC的高效块匹配搜索算法

本文针对H.264/AVC的编码特点,提出了一种利用时空域运动相关性的快速块匹配搜索算法.该算法充分利用了视频序列的运动程度与宏块编码模式间的关联特性以及运动矢量的统计特征,明显减少了运动估计的搜索复杂度.实验表明,本文方法的搜索速度分别比FS和DS算法平均提高了77.96%和32.19%;重建图像的PSNR比DS算法平均提高了0.06dB,更接近FS算法的编码质量.     

Computation-aware fast motion estimation for H.264/AVC using image indexing

The key to designing a real-time video coding system is efficient motion estimation, which reduces temporal redundancies. The motion estimation of the H.264/AVC coding standard can use multiple references and multiple block sizes to improve rate-distortion performance. The computational complexity of H.264 is linearly dependent on the number of allowed reference frames and block sizes using a full exhaustive search. Many fast block-matching algorithms reduce the computational complexity of motion estimation by carefully designing search patterns with different shapes or sizes, which have a significant impact on the search speed and distortion performance. However, the search speed and the distortion performance often conflict with each other in these methods, and their high computational complexity incurs a large amount of memory access. This paper presents a novel block-matching scheme with image indexing, which sets a proper priority list of search points, to encode a H.264 video sequence. This study also proposes a computation-aware motion estimation method for the H.264/AVC. Experimental results show that the proposed method achieves good performance and offers a new way to design a cost-effective real-time video coding system.     

多搜索中心的运动估计快速算法

块大小可变的运动估计方法能提高视频编码性能,但也增加了计算时间.为了加快运动估计计算,本文提出了一种基于多搜索中心预测和搜索范围动态调整的快速算法.多搜索中心预测方法对当前宏块时间和空间上相邻块的运动向量进行分析,得出多个预测向量作为运动估计的搜索中心.相比传统预测方法,多搜索中心预测最高可提高约14.6%的预测精度....     

An efficient computation-constrained block-based motion estimationalgorithm for low bit rate video coding

We present an efficient computation constrained block-based motion vector estimation algorithm for low bit rate video coding that yields good tradeoffs between motion estimation distortion and number of computations. A reliable predictor determines the search origin, localizing the search process. An efficient search pattern exploits structural constraints within the motion field. A flexible cost measure used to terminate the search allows simultaneous control of the motion estimation distortion and the computational cost. Experimental results demonstrate the viability of the proposed algorithm in low bit rate video coding applications. The resulting low bit rate video encoder yields essentially the same levels of rate-distortion performance and subjective quality achieved by the UBC H.263+ video coding reference software. However, the proposed motion estimation algorithm provides substantially higher encoding speed as well as graceful computational degradation capabilities.     

Early SKIP mode decision for MVC using inter-view correlation

In the joint multiview video model (JMVM) proposed by JVT, the variable block-size motion estimation (ME) and disparity estimation (DE) have been employed to determine the best coding mode for each macroblock (MB). These give a high coding efficiency for multiview video coding (MVC), however, they cause a very high computational complexity in encoding system. This paper proposes to reduce the complexities of the ME and DE processes with an early SKIP mode decision algorithm based on the analysis of prediction mode distribution regarding the corresponding MBs in the neighbor view. In this method, the mode decision procedures of most of MBs can be early terminated, and thus much of computation for ME and DE can be greatly reduced. Simulation results demonstrate that our algorithm can achieve computational saving of 46–57% (depending on the tested sequences) with no significant loss of rate-distortion performance.