Fast multiresolution motion estimation algorithms for wavelet-based scalable video coding

Motion estimation and compensation in wavelet domain have received much attention recently. To overcome the inefficiency of motion estimation in critically sampled wavelet domain, the low-band-shift (LBS) method and the complete-to-overcomplete discrete wavelet transform (CODWT) method are proposed for motion estimation in shift-invariant wavelet domain. However, a major disadvantage of these methods is the computational complexity. Although the CODWT method has reduced the computational complexity by skipping the inverse wavelet transform and making the direct link between the critically sampled subbands and the shift-invariant subbands, the full search algorithm (FSA) increases it. In this paper, we proposed two fast multiresolution motion estimation algorithms in shift-invariant wavelet domain: one is the wavelet matching error characteristic based partial distortion search (WMEC-PDS) algorithm, which improves computational efficiency of conventional partial distortion search algorithms while keeping the same estimate accuracy as the FSA; another is the anisotropic double cross search (ADCS) algorithm using multiresolution-spatio-temporal context, which provides a significantly computational load reduction while only introducing negligible distortion compared with the FSA. Due to the multiresolution nature, both the proposed approaches can be applied to wavelet-based scalable video coding. Experimental results show the superiority of the proposed fast motion estimation algorithms against other fast algorithms in terms of speed-up and quality.     

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…     

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.     

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.

     

Parabolic Motion-Vector Re-estimation Algorithm for Compressed Video Downscaling

For multimedia communications, there is a need to downscale a video prior to transmission because of the limitation of the bandwidth of a channel, and/or the different standards between transcoders. However, performing motion estimation in the downscaled video is computational intensive. In this paper, a parabolic motion vector re-estimation (PMVR) algorithm is proposed to predict motion vectors of the downscaled video. The proposed algorithm can significantly reduce computational complexity with slight PSNR degradation, in comparison with full search algorithm. Experimental results show that, with few additional computation, the proposed algorithm achieves a much higher quality than several existing algorithms.     

A fast full search motion estimation algorithm using sequentialrejection of candidates from hierarchical decision structure

We propose a new as well as fast full search (FS) motion estimation algorithm for video coding. The computational reduction comes from sequential rejection of impossible candidates with derived formula and subblock norms. Our algorithm reduces more the computations than the FS motion estimation algorithms previously developed     

DCT-based motion estimation

We propose novel discrete cosine transform (DCT) pseudophase techniques to estimate shift/delay between two one-dimensional(1-D) signals directly from their DCT coefficients by computing the pseudophase shift hidden in DCT and then employing the sinusoidal orthogonal principles, applicable to signal delay estimation remote sensing. Under the two-dimensional (2-D) translational motion model, we further extend the pseudophase techniques to the DCT-based motion estimation (DXT-ME) algorithm for 2-D signals/images. The DXT-ME algorithm has certain advantages over the commonly used full search block-matching approach (BKM-ME) for application to video coding despite certain limitations. In addition to its robustness in a noisy environment and low computational complexity, O(M(2)) for an MxM search range in comparison to the O(N(2).M(2)) complexity of BKM-ME for an NxN block, its ability to estimate motion completely in DCT domain makes possible the fully DCT-based motion-compensated video coder structure, which has only one major component in the feedback loop instead of three as in the conventional hybrid video coder design, and thus results in a higher system throughput. Furthermore, combination of the DCT and motion estimation units can provide space for further optimization of the overall coder. In addition, the DXT-ME algorithm has solely highly parallel local operations and this property makes feasible parallel implementation suitable for very large scale integration (VLSI) design. Simulation on a number of video sequences is presented with comparison to BKM-ME and other fast block search algorithms for video coding applications even though DXT-ME is completely different from any block search algorithms.     

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

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

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

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

一种起点预测的十字形快速运动估计算法

基于时运动矢量概率分布的方向性中心偏移特性和起点预测搜索技术的研究,提出了一种起点预测的十字形快速运动估计算法(IPPAFA),在保持搜索精度的同时有效降低了计算复杂度。实验结果表明,在图像质量几乎不下降的情况下,与钻石搜索算法(DS)和运动矢量场自适应搜索算法(MVFAST)相比,该算法在速度和准确性方面都优于传统的快速运动估计算法。     

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.     

Fast full search motion estimation algorithm using various matchingscans in video coding

To reduce the amount of computation in a full search (FS) algorithm for fast motion estimation, we propose a novel and fast FS motion estimation algorithm. The computational reduction without any degradation in the predicted image comes from fast elimination of impossible motion vectors. We obtain faster elimination of inappropriate motion vectors using efficient matching units from localization of the complex area in image data. We show three properties in block matching of motion estimation. We suggest two fast matching scan algorithms, one from adaptive matching scan and the other from fixed dithering order. Experimentally, we remove the unnecessary computations by about 30% with our proposed algorithm compared to conventional fast matching scan algorithms     

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

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

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

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

一种新的使用两种比特分辨率图象的块匹配运动估计算法及其低功耗VLSI结构

本文给出了一种新的块匹配运动估计算法,它根据视频图像内容的复杂程度自适应地选择常规的或者低比特分辨率的图像来进行块匹配,并且采用了一种混合使用两种比特分辨率图像的新望远镜搜索算法.模拟结果表明,新算法具有较低的计算复杂性,并且能够保证较好的视频质量.基于该算法,我们设计了一种新的脉动阵列结构的搜索引擎.该引擎具有可分割的数据通道,从而在使用低比特分辨率图像进行块匹配时能够通过加强处理的并行性来提高吞吐率.新的运动估计器可工作在较低的时钟频率和电源电压之下,具有低的功耗消耗.     

270 MHz Full HD H.264/AVC High Profile Encoder with Shared Multibank Memory‐Based Fast Motion Estimation

We present a full HD (1080p) H.264/AVC High Profile hardware encoder based on fast motion estimation (ME). Most processing cycles are occupied with ME and use external memory access to fetch samples, which degrades the performance of the encoder. A novel approach to fast ME which uses shared multibank memory can solve these problems. The proposed pixel subsampling ME algorithm is suitable for fast motion vector searches for high‐quality resolution images. The proposed algorithm achieves an 87.5% reduction of computational complexity compared with the full search algorithm in the JM reference software, while sustaining the video quality without any conspicuous PSNR loss. The usage amount of shared multibank memory between the coarse ME and fine ME blocks is 93.6%, which saves external memory access cycles and speeds up ME. It is feasible to perform the algorithm at a 270 MHz clock speed for 30 frame/s real‐time full HD encoding. Its total gate count is 872k, and internal SRAM size is 41.8 kB.     

Improved hierarchical search block matching algorithm by usingmultiple motion vector candidates

The authors describe a hierarchical search block matching algorithm capable of handling large motion in real time motion estimation for existing video compression standards. The algorithm uses multiple motion vector candidates based on an interframe difference measure and a spatial motion-field correlation, respectively. In MPEG-2 application, the encoder adopting the proposed algorithm provides nearly the same performance as the conventional encoder adopting the full search block matching algorithm, with only 0.9% computational complexity for motion estimation     

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

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

Motion estimation for video compression using Kalman filtering

Motion estimation plays an important role for the compression of video signals. This paper presents a new block-based motion estimation method using Kalman filtering. The new method utilizes the predicted motion and measured motion to obtain an optimal estimate of motion vector. The autoregressive models are employed to fit the motion correlation between neighboring blocks and then achieve predicted motion information. The measured motion information is obtained by the conventional block-based fast search schemes. Several algorithms based on either one- or two dimensional models using either nonadaptive or adaptive Kalman filters are developed. The analysis of computational complexity and the simulation results indicate that the proposed method achieves significant savings on computation along with smoother motion vector fields and similar picture quality, when compared to the conventional full search algorithm     

Motion estimation with low resolution distortion metric

Considering all possible candidate motion vectors in a given search area and calculating a distortion measure at every search position, as with the full-search block-matching motion estimation algorithm (FSBME), places a prohibitively high computational burden on the video encoder, making it unsuitable for real-time/portable video applications. To reduce computational complexity while maintaining accuracy, a new version of the reduced-bit, sum of absolute difference (RBSAD) algorithm is presented, which allows for optional correction to full resolution (FSBME) when appropriate. Analysis of a number of video sequence shows that this correction is required for blocks for which there is little motion between frames.