分数像素快速块匹配运动估计方法综述

介绍了视频压缩中分数像素快速块匹配运动估计的基础原理,由于全搜索算法计算量很大,需要发展快速算法。对现有快速算法进行了研究总结,介绍了所应用的数学模型、向量预测、搜索优化、提前终止4个关键技术及代表算法。最后对分数像素快速块匹配运动估计方法进行了总结和展望。     

一种快速块运动估计的分级筛选方法

该文提出了一种新的快速块匹配运动估计方法,分级筛选法。该方法将搜索最佳匹配块的过程 分为若干个筛选级别,在初始的级别中用很少的运算代价通过简单的特征匹配先淘汰一部分候选块;然后在上一级剩余的候选块中,逐级用更加细致的特征继续筛选;直至找到最佳匹配块。实验结果表明,在估计精度非常相近的前提下,该文方法的速度是全搜索方法的12~14倍,而且该方法有很好的稳定性。     

New adaptive partial distortion search using clustered pixel matching error characteristic.

In order to reduce the computation load, many conventional fast block-matching algorithms have been developed to reduce the set of possible searching points in the search window. All of these algorithms produce some quality degradation of a predicted image. Alternatively, another kind of fast block-matching algorithms which do not introduce any prediction error as compared with the full-search algorithm is to reduce the number of necessary matching evaluations for every searching point in the search window. The partial distortion search (PDS) is a well-known technique of the second kind of algorithms. In the literature, many researches tried to improve both lossy and lossless block-matching algorithms by making use of an assumption that pixels with larger gradient magnitudes have larger matching errors on average. Based on a simple analysis, it is found that, on average, pixel matching errors with similar magnitudes tend to appear in clusters for natural video sequences. By using this clustering characteristic, we propose an adaptive PDS algorithm which significantly improves the computation efficiency of the original PDS. This approach is much better than other algorithms which make use of the pixel gradients. Furthermore, the proposed algorithm is most suitable for motion estimation of both opaque and boundary macroblocks of an arbitrary-shaped object in MPEG-4 coding.     

A new block-based motion estimation algorithm

The conventional motion estimation algorithms used in digital television coding can roughly be classified into two categories, namely the block-matching method and the recursive method. Each of them has its own strong points. In this paper, a new type of block-based motion estimation algorithm is presented, which is based on the block-recursive (gradient) method and makes use of some of the merits of the block-matching method. For a moderate translational motion, motion estimation with a subpel precision can conveniently be obtained with only a couple of recursive searches, and for a violent or complicated motion which cannot be estimated by any block-based algorithm, the local minimum of prediction errors can always be found. Our experiments show that the proposed algorithm is efficient and reliable, and obviously superior to the conventional block-recursive algorithms and the fast block-matching algorithms. The performance of the proposed algorithm tends almost to the optimum of the full search algorithm with the same estimation precision, but the computational effort is much less than that of the full search algorithm.     

Modified four-step block-matching algorithm efficient for hardwareimplementation

A new fast block-matching algorithm, the modified four-step search (MFSS) algorithm, is presented. Simulation results and hardware implementation results designed using VHDL show that MFSS has a better performance and is more suitable for hardware realisation than the existing fast algorithms     

A low-power VLSI implementation for fast full-search variable block size motion estimation

Variable block size motion estimation (VBSME) is becoming the new coding technique in H.264/AVC. This article presents a low-power VLSI implementation for VBSME, which employs a fast full-search block-matching algorithm to reduce power consumption, while preserving the optimal motion vectors (MVs). The fast full-search algorithm is based on the comparison of the current minimum sum of absolute difference (SAD) to a conservative lower bound so that unnecessary SAD calculations can be eliminated. We first experimentally determine the specific conservative lower bound of SAD and then implement the fast full-search algorithm in FPGA and 0.18?µm CMOS technology. To the best of our knowledge, this is the first time that a fast full-search block-matching algorithm is explored to reduce power consumption in the context of VBSME and implemented in hardware. Experiment results show that the proposed design can save power consumption by 45% compared to conventional VBSME designs that give optimal MV based on the full-search algorithms.     

一种优于SAD的匹配准则及其快速算法

本文根据运动估计后的残差图像DCT交流系数的统计分布规律，推导出了一种块匹配运动估计的匹配准则，并针对该匹配准则需要较多乘法运算的缺点，设计了快速算法以减少计算量。实验结果表明对有亮度变化的帧，该匹配准则可以取得比SAD匹配准则更好的图像质量，同时快速算法可以减少约80％的乘法计算量。     

一种基于生物地理优化的快速运动估计算法

为了提高视频编码中运动估计的性能,该文提出了一种新的基于生物地理优化的快速运动估计算法。该算法以运动矢量的特性为基础,通过生物地理优化算法的迁徙和变异操作搜索全局最优解,克服了以往快速搜索算法容易陷入局部最优的缺点,同时采用了早期和迭代终止策略,进一步简化运算复杂度。实验表明,该算法的整体性能高于以往快速搜索算法,可以有效兼顾搜索精度和速度的要求。由于实现简单和适用面广,该算法能满足实时视频编码的需求。     

The cross-search algorithm for motion estimation [image coding]

A fast block-matching algorithm for motion estimation is presented. It is based on a logarithmic step where, in each search step, only four locations are tested. For a motion displacement of w pels/frame, this technique requires 5+4 log₂w computations to locate the best match. Using sequences of CIF standard pictures, the interframe motion compensated prediction error with this technique is compared to the other fast methods. The computational complexity of this algorithm is also compared against those methods     

用于快速块匹配运动估计的自适应十字模式搜索

该文提出了一种新的快速块匹配运动估计算法,即自适应十字模式搜索。它综合了固定模式搜索和空间柑关搜索两方面的优点,与目前很流行的菱形搜索(DS)相比具有较好的性能。     

基于灰度投影和块匹配相结合的稳像算法

在视频稳像过程中为兼顾算法的精度与效率,本文通过分析稳像的原理及目前常用的几种算法,提出了一种基于灰度投影和块匹配相结合的匹配策略.首先运用灰度投影算法来缩小块匹配的待匹配区域,然后运用块匹配算法进行运动估计与补偿.在此过程中,充分地体现了灰度投影算法运算量小以及块匹配算法精度高的特点.实验结果表明在保持块匹配算法优势的同时降低了算法的运算复杂度.     

一种改进的奇偶阵列结构运动估计器设计

提出了一种改进的奇偶阵列计算结构的运动估计器架构,该运动估计器利用了二维数据复用并能够实现全搜索法。设计了运动估计器的状态机控制逻辑,在其控制下,运动估计器的处理单元达到了100%的利用率。本运动估计器实现了高速、并行的运算,从而可以应用在高清视频的实时后处理等场合。     

基于H.263的实时视频编码技术研究

为了提高H．263编码技术现有算法的执行效率，本文提出了一种基于时域预测的预判零方法，该方法在保证一定图像质量的条件下具有较高的判别效率，能节约大量的编码时间：并在此基础上结合“钻石”运动搜索算法、MMX优化技术，实现了利用软件进行实时视频编码。     

Fast full-search block-matching algorithm for motion-compensatedvideo compression

This paper proposes a fast block-matching algorithm that uses three fast matching error measures, besides the conventional mean-absolute error (MAE) or mean-square error (MSE). An incoming reference block in the current frame is compared to candidate blocks within the search window using multiple matching criteria. These three fast matching error measures are established on the integral projections, having the advantages of being good block features and having simple complexity in measuring matching errors. Most of the candidate blocks can be rejected only by calculating one or more of the three fast matching error measures. The time-consuming computations of MSE or MAE are performed on only a few candidate blocks that first pass all three fast matching criteria. Simulation results show that a reduction of over 86% in computations is achieved after integrating the three fast matching criteria into the full-search algorithm, while ensuring optimal accuracy     

MPEG-2编码芯片中运动估计电路的设计

运动估计是视频压缩中最重要的环节，文章讨论了运动估计的基本原理并分析了其特点，采用了三步分层搜索算法．设计了一种基于MPEG-2的主档次标准的9PE全并行结构的高速运动估计电路，并通过FPGA验证，系统时钟频率达到35MHz，性能达到了实时编码的要求。     

基于运动矢量场和方向自适应的快速运动估计算法

该文提出了一种基于运动矢量场和方向自适应的快速搜索算法。算法针对序列图像的运动矢量场所具有的中心偏置性和时空相关性进行预判,对静止块设定阈值直接中止搜索;根据运动类型自适应选择搜索起始点和搜索策略;采用了两种新的混合搜索方法,对小运动和大运动宏块使用线性-菱形搜索,对中等运动块使用六边形-菱形搜索算法,搜索模板具有强烈的方向特性。实验结果表明,该文算法的搜索速度和搜索精度优于现有的快速运动估计算法,而搜索精度非常接近于全搜索法。     

A new diamond search algorithm for fast block-matching motionestimation

Based on the study of motion vector distribution from several commonly used test image sequences, a new diamond search (DS) algorithm for fast block-matching motion estimation (BMME) is proposed in this paper. Simulation results demonstrate that the proposed DS algorithm greatly outperforms the well-known three-step search (TSS) algorithm. Compared with the new three-step search (NTSS) algorithm, the DS algorithm achieves close performance but requires less computation by up to 22% on average. Experimental results also show that the DS algorithm is better than the four-step search (4SS) and block-based gradient descent search (BBGDS), in terms of mean-square error performance and required number of search points.     

一种运动自适应的帧内插算法

本文提出了一种运动自适应的帧内插算法,可以用于逐行扫描的数字视频系统中做帧速率转换。该算法首先采用了线性预测块匹配搜索算法来估计内插帧中每一个象素的运动矢量;然后对得到的运动场进行中值滤波和判别,剔除运动不一致或错误的运动矢量;最后沿着运动轨迹线性内插得到内插帧的象素值。仿真分析表明本文提出的算法,在一个大的搜索区域进行快速搜索和判别,可以有效地解决内插帧中快速运动目标的运动模糊和有切换帧时的图象重叠,提高了帧速率转换中内插帧的主观视觉质量。     

一种基于H．264的有效运动估计算法

运动估计算法是实时视频编解码技术的研究重点，高精度的匹配和补偿可以减少预测误差，提高视频图像的压缩效果．为降低在视频编码标准H．264中运动估计的高计算复杂度问题，提出了采用一种基于节点模型的可变形块匹配运动估计算法来搜索最佳运动矢量．该算法充分利用了H．264运动矢量的的统计特性和相关性，并采用基于像素差值分类的运动估计匹配准则．实验表明，在编码性能损失很小的条件下，该算法有效降低了视频压缩编码中运动估计的运算复杂度．     

Fast variable-size block motion estimation for efficient H.264/AVC encoding

In this paper, an efficient algorithm is proposed to reduce the computational complexity of variable-size block-matching motion estimation. We first investigate features of multiple candidate search centers, adaptive initial-blocksizes, search patterns, and search step-sizes, to match different motion characteristics and block-sizes. To avoid being trapped in local minima, the proposed algorithm uses multiple candidate motion vectors, which are obtained from different block-sizes. To further reduce the computation cost, a threshold-based early stop strategy according to the quantization parameter is suggested. With adaptive initial block-sizes, a merge-or-skip strategy is also proposed to reduce the computation for the final block-size decision. For the H.264/AVC encoder, simulations show that the proposed algorithms can speed up about 2.6–3.9 times of the original JM v6.1d encoder, which uses fast full-search for all block-sizes, and still maintain a comparable rate-distortion performance.