一种用于运动估计的十字六边形搜索算法

提出了一种十字六边形搜索算法用于快速运动估计。该算法利用了运动矢量的中心偏置性和相关性，运动估计时通过预测确定搜索起始点，在搜索前期利用十字模板结合提前退出技术优先搜索起始点附近的局部区域，后期则改用六边形模板扩大搜索范围并完成运动估计。实验证明该算法与原始的六边形搜索算法相比平均减少了45%的搜索点数，与一些新的快速搜索算法相比，在搜索精度基本相似的情况下也有效地降低了运动估计的运算复杂度。     

基于多模板搜索的快速运动估计算法

提出了一种采用多个六边形模板进行快速块匹配运动估计的新方法。该算法(MPMVFAST)充分利用了序列图像中运动矢量场的中心偏置特性和时空相关性,根据运动类型自适应的选择搜索策略和搜索起始点,结合垂直和水平方向的两个六边形搜索模板,并采用内部简易搜索算法,同时利用有效的判断中止准则结束搜索。与现有算法相比,该算法有效地减少了搜索点数,搜索精度接近于全搜索法。     

基于多模板快速搜索的运动估计算法优化研究

针对视频编码中运动估计算法运算复杂的问题,研究了一种提前终止准则和多模板快速搜索算法相结合的优化算法;该算法基于混合非对称十字多六边形搜索(UMHexagonS)算法,结合现有视频编码标准,首先对满足提前终止准则的当前块及时终止起始点搜索,然后采用非均匀多六边形部分搜索模板和六边形与小十字形相结合的并行搜索模板,分别对非均匀多六边形搜索和扩展的六边形搜索两方面做了优化;实验结果表明,该算法在保证视频质量的情况下,没有增加码率,且有效地节省了运动估计时间(约28%),降低了算法的复杂度。     

浅谈一种线性预测搜索方向的运动估计算法

为了减小快速运动估计算法的搜索速度和提高运动补偿的准确性,本文提出了一种线性预测搜索方向的快速运动估计算法。该算法在正方形模板块失真匹配的基础上,确定中心点到最小误差点为搜索方向,在此方向上不断延伸一个点进行块失真匹配,直至下一个点的块失真大于当前点的块失真。以当前点作为最小误差点,重复以上操作,直至找到最优点结束搜索。实验表明本算法在保证图像质量的情况下搜索速度比DS搜索算法提高1.5倍左右。     

基于六边形的运动矢量场自适应搜索算法

提出了一种基于六边形的运动矢量场自适应搜索算法,该算法充分利用了序列图像中运动矢量场的中心偏置性和时空相关性,结合六边形搜索法和小菱形搜索法,根据运动类型自适应的选择搜索策略和搜索起始点,同时设定阈值对静止块直接中止搜索。实验结果表明,该算法的搜索速度优于现有的快速运动估计算法,搜索精度接近于全搜索法。     

一种有效的自适应运动估计搜索算法

提出了一种新的基于运动矢量场、方向自适应和半像素搜索的快速搜索算法(M-DAHS)。该算法根据图像序列运动矢量场的中心偏置性和时空相关性进行预判,对静止块设定阈值直接终止搜索;非静止块根据运动类型自适应选择搜索起始点和搜索策略。搜索模板具有很强的方向自适应性,对于小运动块采用菱形-线性搜索,其他块使用六边形-菱形搜索算法。整像素搜索完毕后,再以十字优先原则进行半像素搜索。实验结果表明,该算法性能优越,搜索速度快,搜索精度高,且搜索精度可以非常接近全搜索算法。     

H.264中快速运动估计算法的一种改进方案*

UMHexagonS是视频编码标准H.264的一种快速整像素运动估计算法,该算法较之全搜索算法在性能上有很大提高,但仍存在运算量大、复杂度高、耗时等问题。利用提前中止思想,在螺旋搜索和多层次大六边形搜索阶段增加提前中止条件,加速算法中止,然后用特殊的改进模板搜索法替换螺旋搜索策略,快速匹配最佳点。在JM10.2测试模型上进行了算法验证,实验结果表明,改进算法在保证编码性能的同时,可以有效地减少5%～15%的运动估计时间。     

基于自适应搜索模板的快速运动估计算法

为了降低快速运动估计的计算复杂度,避免小菱形搜索算法带来的局部最优点问题,提出了自适应搜索模板的估计算法.该算法在搜索时根据SAD值的变化快慢和相邻帧之间时间相关性自适应选择搜索模板.实验表明,使用该算法编码,码流大小与使用菱形搜索算法和六边形搜索算法差距为±0.6%,搜索点数为菱形算法的72%～77%,六边形算法的83%～86%.在减少搜索点数的情况下有效地避免了局部最优点问题.     

基于可变分块尺寸的多模板运动估计算法

H.264视频编码标准中, 运动估计占用了编码器极大的计算量. 针对快速块匹配运动估计, 提出了一种基于可变分块尺寸的多模板六边形搜索算法. 该算法根据H.264中七种不同的宏块划分, 自适应地采用大六边形和水平扁六边形、竖直扁六边形等模板来进行运动估计. 相对于传统六边形算法, 在增加匹配灵活性的同时, 还可以更好地覆盖整个分块. 仿真结果表明, 在重建图像质量接近全搜索(Full search, FS)的同时, 比六边形算法减少了约10%的搜索点数.     

H.264块运动估计自适应快速搜索算法研究

H.264视频编解码标准中由于运动搜索部分占整个编码时间的权重很大,所以运动搜索算法的优劣直接影响整个编码的效率。对编码运动估计理论进行了研究,采用六边形和小菱形相结合的方法,提出了一种新的自适应快速搜索算法来改善搜索效率。自适应快速搜索算法模式由当前块运动强度来决定,当当前块处于剧烈运动时,该算法选择六边形图形搜索算法;当当前块处于缓慢运动时,该算法选择小菱形图形搜索算法。实验结果表明该算法相比其他自适应算法以及单纯使用一种搜索图形节约了搜索时间,同时率失真性能影响甚微。     

基于多级顺序排除算法(MSEA)的改进

块匹配运动估计是视频编码国际标准中广泛采用的关键技术.许多快速块匹配法通过限制搜索点数来减少运算量,但与全搜索算法相比极易出现匹配误差.该文介绍了一种应用新的判别条件的多级顺序排除算法（MSEA）,并在此基础上提出一种新的算法,该算法引入了尺度化的部分失真消除（PDE）技术,用于尺度化累积部分误差和当前最小误差.实验证明,相对于一脉相承的同为穷举搜索算法的全搜索算法（FS）、顺序排除算法（SEA）、多级顺序排除算法（MSEA）等,该算法大幅度提高了搜索效率.与多级顺序排除算法相比,平均每宏块节省了大约75%的运算次数.该算法在保证图像质量的前提下,使视频编码的速度大大提高.     

自适应消除的高效UMHexagonS算法

针对当前H.264/AVC视频标准的非对称十字型交叉多六边形网格搜索（UMHexagonS）算法搜索点数多的问题,提出了一种快速搜索提前中止策略的UMHexagonS算法。采用渐进消除算法的自适应消除思想,对不满足快速匹配判别条件的子块提前结束搜索,仿真结果表明,与传统法相比,改进算法在不损失编码效率的情况下,运动估计时间速率提高了约30.52%~60.7%,有效提高了编码的实时性。     

基于连续消除的正方形-菱形运动估计算法

在基于搜索起点预测和正方形-菱形算法(SDS)的基础上,结合连续消除算法(SEA),提出了一种新的运动估计算法:基于连续消除的正方形.菱形运动估计算法(SEA-SDS).实验结果表明,该算法以比较小的代价取得了与全搜索算法(FS)相当的效果;在搜索次数和精度方面均优于菱形(DS)和正方形-菱形(SDS)快速运动估计算法.     

All-layer search algorithm using mean inequality and improved checkerboard partial distortion search for fast motion estimation

Block-matching motion estimation algorithm is used in many video compression coding systems because it could greatly reduce the temporal redundancy between the consequent video sequences. In this paper, an all-layer search algorithm using mean inequality and improved checkerboard partial distortion search scheme for fast block-matching motion estimation is proposed. A layer in the proposed method refers to a processed image which is derived from the reference frame or the adjacent lower layer. Firstly, the proposed algorithm constructs all layers from the reference frame or the adjacent lower layer by summing up all pixels over a sub-block. Then, a new mean inequality elimination method is introduced to reject a lot of unnecessary candidate search points on the top layers before calculating the real block matching distortion. Finally, the proposed algorithm utilizes an improved checkerboard partial distortion search scheme in the process of the real block distortion calculation on the following layers to further reduce the amount of computation. Experimental results show that the proposed algorithm can effectively reduce the computational complexity of motion estimation meanwhile guarantee the matching quality compared to other motion estimation algorithms. Compared to the full search algorithm, the proposed algorithm can reduce 97.30 % computational complexity with a negligible degradation of the peak signal to noise ratio (PSNR). Compared to the diamond search algorithm, directional gradient descent search algorithm, partial distortion search algorithm, transform-domain successive elimination algorithm and two-layer motion estimation algorithm, the proposed algorithm can also save 63.56 %, 52.73 %, 92.87 %, 85.77 % and 33.96 % computational complexity, respectively.     

H．264中带有中途停止的多层逐次消元运动估计算法

H．264视频压缩标准采用多模式运动估计，可以有效减少块匹配预测误差，但随着模式选择的增多，算法计算量成倍增加。为此，提出一种带有中途停止的多层逐次消元运动估计算法(MSEHS)。该算法根据模式分布规律，使用多层逐次消元法加速大块模式的搜索过程，并且提出中途停止准则，判断是否继续进行小块模式的搜索。这样既保证了多模式运动估计的优点，又减少了冗余计算。实验结果表明，该算法比全搜索算法整体速度提高了近4倍，同时可以保持与全搜索算法非常接近的图像质量和比特率。     

A fast nearest-neighbor algorithm based on a principal axis searchtree

A new fast nearest-neighbor algorithm is described that uses principal component analysis to build an efficient search tree. At each node in the tree, the data set is partitioned along the direction of maximum variance. The search algorithm efficiently uses a depth-first search and a new elimination criterion. The new algorithm was compared to 16 other fast nearest-neighbor algorithms on three types of common benchmark data sets including problems from time series prediction and image vector quantization. This comparative study illustrates the strengths and weaknesses of all of the leading algorithms. The new algorithm performed very well on all of the data sets and was consistently ranked among the top three algorithms     

基于预测码矢的快速搜索新算法

在ｋ维欧氏空间Ｒｋ中，给定一个有限子集Ｗ及一个向量ｘ，如何搜索Ｗ中与ｘ距离最近的向量，具有重要的实际应用价值，尤其在图象的矢量量化编码、神经网络模式识别［１］等问题中，快速搜索起决定性的作用。在分析已有快速搜索算法的基础上，给出一种新的快速搜索算法，该算法利用图象相邻块的码书地址，作为当前块的预测值，使搜索空间缩小更快。     

一种群模式全局搜索算法

由于模式搜索算法易陷入局部极值且效率低。受群智能算法的启发,结合模式搜索算法,提出一种全局优化算法——群模式全局搜索算法。该算法引入群智能的思想,包含4个操作:模式探测、模式移动、模式学习、模式扩散,具有较强的局部-全局搜索能力,且收敛速度快、稳定性好。对benchmark函数集进行仿真并与其它多个算法对比,实验结果证实该算法的有效性。     

解无约束全局优化问题的一个新的进化算法及其收敛性

文章利用一维搜索与局部极小点的消去技术设计了一个新的进化算法。此算法在迭代过程中,可不断消除那些比目前已找到的最好点差的局部极小点,从而使局部极小点的数目随着迭代的进行大量地减少,使算法更易找出全局极小点。另外,将一维搜索巧妙地用于算法之中,加快了收敛速度。并且证明了算法的全局收敛性,最后的数值实验也表明新算法十分有效。