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     

Block-based frequency scalable technique for efficient hierarchical coding

In this paper, we propose a block-based frequency scalable technique for efficient hierarchical coding. The proposed technique divides an image into its multiple resolution versions, based on the spectral properties of discrete cosine transform (DCT) kernels. We present that spectral decomposition, downsampling, and DCT operations are performed effectively over input DCT coefficients of one-dimensional (1-D) and two-dimensional (2-D) signals by using the proposed transform matrices. The proposed image coder is observed to reduce the computational complexity and the memory buffer size with a higher peak signal-to-noise ratio (PSNR), when compared with the traditional hierarchical image coder. In addition, the proposed architecture can preserve compatibility easily with the previous DCT-based image coder.     

H.263甚低速率图像编码的全局判决实现方法

本文对Ｈ．２６３编码算法的现有实现方法作了深入的分析,首先发现变换部分存在大量无效运算,提出了在变换前加判决的前变换判决的编码方案,以压缩无效的变换运算;其次发现运动估计部分由于忽略了图像场景的分级运动而存在一定的无效搜索运算,提出了基于分级运动的可变搜索域法来压缩无效的搜索运算;最后将前变换判决方案与运动估计的可变搜索域法有机地结合在一起,提出了全局判决编码方案,从而比较全面地改进了现有实现方法,因而能大幅度地提高编码器的编码速度．     

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

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

A DCT/DST-based error propagation-free data hiding algorithm for HEVC intra-coded frames

Currently, two error propagation-free discrete cosine transform (DCT)-based data hiding algorithms, one by Ma et al. and the other by Lin et al., were presented for H.264/AVC intra-coded frames. However, the state-of-the-art video codec, high efficiency video coding (HEVC), adopts both integer DCT and discrete sine transform (DST) such that the previous DCT-based algorithms cannot fully utilize available capacity for data hiding in HEVC. This paper presents the first DCT/DST-based data hiding algorithm for HEVC intra-coded frames where the block DCT and DST coefficient characteristics are investigated to locate the transformed coefficients that can be perturbed without propagating errors to neighboring blocks. Experimental results confirm the merits of the proposed algorithm in providing the intra-frame error propagation-free advantage, the quality improvement for marked images, the compression power inherited from HEVC, and the superiority of embedding capacity for low bitrate coding when compared with the previous two algorithms for H.264/AVC.     

The quantized DCT and its application to DCT-based video coding

The two-dimensional (2-D) discrete cosine transform (DCT) and the subsequent quantization of the transform coefficients are two computationally demanding steps of any DCT-based video encoder. In this paper, we propose an efficient joint implementation of these two steps, where the precision in computing the DCT can be exchanged for a reduction in the computational complexity. First, the quantization is embedded in the DCT, thus eliminating the need to explicitly quantize the transform coefficients. A multiplierless integer implementation of the quantized DCT (QDCT) is then proposed that performs shift and add operations instead of full multiplications. A sequence of multiplierless QDCT algorithms is obtained with increasing precision and number of computations. Finally, further savings in computations are obtained by terminating the DCT computations whenever intermediate results indicate that the transform and quantization steps will likely result in a block of zero values. The proposed algorithms are applied to, and results are presented for, high-quality MPEG-2 and low bit rate H.263 video encoding.     

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.

     

Computation reduction for standard-based video encoders based on the energy preservation property of DCT

Based on the energy preservation property of DCT, an optimization technique for motion estimation (ME), DCT, and quantization for standard-based video encoders is developed. First, a stopping criterion for ME is proposed to reduce the number of checking points in finding the motion vectors, and save the computations. The advantage of introducing such a stopping criterion lies in its adaptability to the quantization parameter and applicability to various fast ME algorithms. Then, the DCT and quantization are jointly optimized by tracing the remaining signal energy and removing unnecessary calculations in the process of DCT and quantization. A pruned 2-D DCT based on Huang's fast DCT algorithm is presented to demonstrate the superiority of this algorithm to the full DCT and an existing all-zero block detection method. Although proved to be computationally efficient, the algorithms introduce no obvious quality loss.     

计算能力可伸缩的运动估计率失真优化

不同硬件设备具有不同的计算能力,能否在任意给定计算能力约束下达到最好的编码效率,是当前视频编码研究领域的一个极具挑战性问题.同时,随着分块结构越来越灵活的编码标准不断出现（如：HEVC,H.264等）,运动估计不得不反复地应用在大小不同的各种分块上,导致其对编码总体计算复杂度的影响愈加重要.在此背景下,本文提出了一种针对运动估计的计算能力可伸缩（Complexity scalable）优化算法.我们通过对运动估计过程中预测失真度和计算复杂度的变化规律建模,发现根据各宏块的特性设置不同的预测失真度阈值可以优化地分配计算资源.而该阈值的大小则恰恰是各宏块的最小预测失真度加上一个由复杂度约束统一决定的偏移量.有鉴于此,我们进一步构造了计算能力可伸缩的优化运动估计算法,在不增加额外计算量的前提下,快速地得到各个宏块所对应的优化阈值,并完成运动估计.通过实验分析,该算法不仅具备自动适应不同计算复杂度约束的能力,而且在任意给定的复杂度约束下,都能提供优化的编码性能.     

基于三维递归搜索的多级运动估计视频帧率上转换算法

运动补偿插帧是目前主要的帧率上转换方法。为减小内插帧中的块效应,并降低运算量以满足实时高清视频应用,该文提出了一种基于3维递归搜索(3-D Recursive Search, 3-D RS)的多级块匹配运动估计视频帧率上转换算法。该算法将3-D RS与双向运动估计相结合,首先对序列中相邻帧进行由粗到精的三级运动估计,再利用简化的中值滤波器平滑运动矢量场,最后通过线性插值补偿得到内插帧。实验结果表明,与现有的运动补偿插帧算法相比,该算法内插帧的主、客观质量都有所提高,且算法复杂度低,有很强的实用性。     

A complexity-bounded motion estimation algorithm

The full search motion estimation algorithm for video coding is a procedure of high computational cost. For this reason, in real-time low-power applications, low-cost motion estimation algorithms are viable solutions. A novel reduced complexity motion estimation algorithm is presented. It conjugates the reduction of computational load with good encoding efficiency. It exploits the past history of the motion field to predict the current motion field. A successive refinement phase gives the final motion field. This approach leads to a sensible reduction in the number of motion vector that have to be tested. The complexity is lower than any other algorithm algorithms known to the authors, in the literature, it is constant as there is no recursivity in the algorithm and independent of any search window area size. Experimental evaluations have shown the robustness of the algorithm when applied on a wide set of video sequences-a good performance compared to other reduced complexity algorithms and negligible loss of efficiency versus the full search algorithm.     

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.     

A Modified Block Matching Motion Estimation Algorithm for the Very Low Bit-Rate video Coding

1IntroductionMohonestimationplaysanimportantroleindigitalvideocompression.Block-matchingtechniquehasbeenadoptedinmanyvideocompressionstandardssuchasH.261,MPEG-l,MPEG-2andH.263.Eventhoughthealgorithmtoestimatethemotionvectorsisnotspecifiedexplicitly.However,despiteitssuccessfulapplications,itproducesarathernoisyinchonfield.Inverylowbit-ratevideocodingapplications,theamountofthesideinformationfortheinchonfieldrepresentsanimPOrtantportionofthetotalbit-rate.Therefore,motionestimatetechniques…     

减少低比特率视频编码计算复杂性的一种新方法

提出了一种改进的预先判断视频编码中全零系数的判别准则,用于减少低比特率视频编码过程中的冗余计算及运动估计算法的计算复杂性.实验结果表明,对典型的可视电话视频序列(如Claire),有50%以上的亮度块被判别为全零系数块,运动估计的平均搜索次数也减少了30%以上.该方法可被用于减少软件编码器的运算量及其硬件电路的功耗.     

Motion analysis in 3D DCT domain and its application to video coding

Global, constant-velocity, translational motion in an image sequence induces a characteristic energy footprint in the Fourier-transform (FT) domain; spectrum is limited to a plane with orientation defined by the direction of motion. By detecting these spectral occupancy planes, methods have been proposed to estimate such global motion. Since the discrete cosine transform (DCT) is a ubiquitous tool of all video compression standards to date, we investigate in this paper properties of motion in the DCT domain. We show that global, constant-velocity, translational motion in an image sequence induces in the DCT domain spectral occupancy planes, similarly to the FT domain. Unlike in the FT case, however, these planes are subject to spectral folding. Based on this analysis, we propose a motion estimation method in the DCT domain, and we show that results comparable to standard block matching can be obtained. Moreover, by realizing that significant energy in the DCT domain concentrates around a folded plane, we propose a new approach to video compression. The approach is based on 3D DCT applied to a group of frames, followed by motion-adaptive scanning of DCT coefficients (akin to “zig-zag” scanning in MPEG coders), their adaptive quantization, and final entropy coding. We discuss the design of the complete 3D DCT coder and we carry out a performance comparison of the new coder with ubiquitous hybrid coders.     

一种适用于H.263的运动估计搜索算法

本文提出了一种用于视频编码快速运动估计的基于中心三步法（ＣＴＳＳ）的块匹配搜索算法。结果表明,这种算法与Ｈ．２６３的可选项结合使用时,大大减少了块匹配的计算量,并可获得与全搜索算法相当的图像质量、信噪比和编码比特数。     

A multilevel successive elimination algorithm for block matchingmotion estimation

An efficient algorithm is proposed to reduce the computation cost of block matching algorithms for motion estimation in video coding. Based on a new insight in block matching algorithms, we extend the successive elimination algorithm to a multilevel case. By using the sum norms of the blocks and the subblocks, tighter and tighter decision boundaries can be obtained for eliminating the search positions. The efficiency of the proposed algorithm combined with the full search algorithm and several fast search algorithms is verified by simulation results.     

Invertible temporal subband/wavelet filter banks with half-pixel-accurate motion compensation

Three-dimensional (3-D) subband/wavelet coding with motion compensation has been demonstrated to be an efficient technique for video coding applications in some recent research works. When motion compensation is performed with half-pixel accuracy, images need to be interpolated in both temporal subband analysis and synthesis stages. The resulting subband filter banks developed in these former algorithms were not invertible due to image interpolation. In this paper, an invertible temporal analysis/synthesis system with half-pixel-accurate motion compensation is presented. We look at temporal decomposition of image sequences as a kind of down-conversion of the sampling lattices. The earlier motion-compensated (MC) interlaced/progressive scan conversion scheme is extended for temporal subband analysis/synthesis. The proposed subband/wavelet filter banks allow perfect reconstruction of the decomposed video signal while retaining high energy compaction of subband transforms. The invertible filter banks are then utilized in our 3-D subband video coder. This video coding system does not contain the temporal DPCM loop employed in the conventional hybrid coder and the earlier MC 3-D subband coders. The experimental results show a significant PSNR improvement by the proposed method. The generalization of our algorithm for MC temporal filtering at arbitrary subpixel accuracy is also discussed.     

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

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

Motion Estimation Algorithms Using the Deformation of Planar Hierarchical Mesh Grid for Videoconferencing Applications at Low Bit-rate Transmission

This paper studies the issue of reducing the temporal redundancy between consecutive frames of a videoconferencing sequence at low bit-rate transmission. To overcome the drawbacks of the traditional block matching algorithm implemented in the most current video coding standards, we propose to better describe the motion of objects through the deformation of planar rectangular mesh grid adapted to the edges of the moving objects in the scene. The traditional inter coding modes are then replaced by two new classes of encoding algorithms. The first one concerns the B-frames where the problem of motion estimation is solved by a bidirectional prediction algorithm which reconstructs the quadrilateral mesh grids without any coding cost. The second class of algorithm much more complex than the first one is specific to the P-frames based on the principle of merging two hierarchical grids of reference. This algorithm addresses not only the motion estimation problem based on the adaptive quadrilateral mesh grid but also the issue of the relevant information (e.g. the positions of the nodes, the connectivity of each quadrilateral mesh of the grid and the motion compensation) to efficiently encode. The implementation of these algorithms in a complete coding scheme offers good performance compared to the H.264/AVC video coder at low bit-rate transmission.