用于视频编码运动估计的搜索方法

摘要

本发明公开了一种用于视频编码运动估计的搜索方法。该搜索方法首先利用空域和时域相邻块的预测运动矢量确定初始搜索点，然后根据视频序列运动矢量的方向选择不同的搜索策略，对静止块和准静止块直接中止搜索，在搜索过程中针对视频序列的内容特性和运动复杂度自适应地选择菱形模式和三角形模式，从而在保证搜索精度的同时有效地提高了搜索速度。

权利要求

1.一种用于视频编码运动估计的搜索方法，其特征在于包括如下的步骤：

第1步：如果初始搜索点（O）的绝对差值和小于预定阈值，则搜索结束，否则进入菱形搜索模式；先计算菱形的四个顶点（A）、（B）、（C）和（D）的绝对差值和；如果初始搜索点（O）的绝对差值和最小，则搜索结束；如果绝对差值和最小的点为该菱形的顶点（A），则进入第

2步；

第2步：比较（B）、（C）、（D）和（O）的绝对差值和；如（B）或（D）点的绝对差值和为最小值，则进入第6步；否则进入第一三角形搜索模式，该第一三角形搜索模式是以第1步中的顶点（A）为外心，以（X）、（Y）和（Z）为顶点的等腰三角形；分别计算（X）、（Y）和（Z）的绝对差值和并与（A）的绝对差值和比较，如（A）点的绝对差值和最小，则搜索结束；如（X）点的绝对差值和最小，则进入第3步；如（Y）点的绝对差值和最小，则进入第4步；如（Z）点的绝对差值和最小，则进入第5步；

第3步：进入第二三角形搜索模式，该第二三角形搜索模式是以顶点（X）为外心，以（B）、（Y'）和（Z'）为顶点的等腰三角形；分别计算（Y'）、（Z'）的绝对差值和并与（X）的绝对差值和比较,如（X）点的绝对差值和最小，则搜索结束；如（Y'）点的绝对差值和最小，则返回第3步；如（Z'）点的绝对差值和最小，则进入第4步；

第4步：进入第三三角形搜索模式，该第三三角形搜索模式是以顶点（Y）为外心，以（X'）、（Y'）和（Z'）为顶点的等腰三角形；分别计算（X'）、（Y'）、（Z'）的绝对差值和并与（Y）的绝对差值和比较,如（Y）点的绝对差值和最小，则搜索结束；如（Y'）点的绝对差值和最小，则返回第4步；如（Z'）点的绝对差值和最小，则进入第5步；如（X'）点的绝对差值和最小，则进入第3步；

第5步：进入第四三角形搜索模式，该第四三角形搜索模式是以顶点（Z）为外心，以（D）、（X'）和（Y）为顶点的等腰三角形；分别计算（X'）、（Y'）的绝对差值和并与（Z）的绝对差值和比较,如（Z）点的绝对差值和最小，则搜索结束；如（Y'）点的绝对差值和最小，则返回第5步；如（X'）点的绝对差值和最小，则进入第4步；

第6步：进入第五三角形搜索模式，该第五三角形搜索模式是以（A）、（X）和（Y）为顶点的等腰三角形；分别计算（X）、（Y）的绝对差值和并与（A）的绝对差值和比较,如（A）点的绝对差值和最小，则搜索结束；如另一顶点的绝对差值和最小，则进入第7步；

第7步：进入第六三角形搜索模式，在另一顶点的绝对差值和最小的情况下，该第六三角形搜索模式是以该另一顶点、（A'）和（B'）为顶点的等腰三角形；分别计算（A'）、（B'）的绝对差值和并与该另一顶点的绝对差值和比较,如该另一顶点的绝对差值和最小，则搜索结束；否则重复第7步。

2.如权利要求1所述的用于视频编码运动估计的搜索方法，其特征在于：

在第1步中，将当前编码块左上角坐标加上前一编码块的预测运动矢量在参考帧中的坐标位置定义为初始搜索点（O）。

3.如权利要求2所述的用于视频编码运动估计的搜索方法，其特征在于：

编码块的预测运动矢量为相邻块运动矢量的中值，其中相邻块包括参考帧中的时域相邻块和当前帧中所述编码块的三个空域相邻块。

4.如权利要求1所述的用于视频编码运动估计的搜索方法，其特征在于：

在第1步中，所述菱形搜索模式是以初始搜索点（O）为中心，步长为1个像素点向左、右、上和下扩展形成的一个菱形。

5.如权利要求1所述的用于视频编码运动估计的搜索方法，其特征在于：

在第1步中，所述阈值用于检测出静止块和准静止块，对静止块和准静止块直接中止搜索。

6.如权利要求5所述的用于视频编码运动估计的搜索方法，其特征在于：

所述阈值为512。

说明书

用于视频编码运动估计的搜索方法

技术领域

[0001] 本发明涉及一种用于视频编码运动估计的搜索方法，尤其涉及一种针对信源编码的需要，基于菱形和三角形自适应的视频编码运动估计搜索方法，属于数字图像处理技术领域。

背景技术

[0002] 运动估计是从视频序列中抽取运动信息的一整套技术。它是整个视频编码解决方案中计算量最大的部分，通常在一个视频压缩运算中运动估计约占总计算量的50％～60％。因此，运动估计性能的优劣直接影响到整个视频编码解决方案的运行效率和整个视频序列的重构质量，寻找简单、高效、快速的运动估计方法是至关重要的。

[0003] 在各种运动估计方法中，块匹配方法具有简单、高效的优点，因此被很多国际视频编码标准所采纳，并得到广泛的应用。基于块匹配的运动估计方法是减少时间冗余信息的有效解决方案。

[0004] 另一方面，目前用于运动估计的搜索方法有很多种，其中全搜索运动估计方法(Full Search method，简写为FS)的优点是产生的残差系数最小，但其巨大的时间开销和计算量是实时视频编码解决方案所不能接受的。同时，尽管FS能搜索到精度最高的运动矢量，但其运动矢量场未必均匀，从而造成总体的编码效率不一定最优。

[0005] 为了减少FS方法的运动估计搜索复杂度，现在已经出现了许多改进的运动估计方法，如Jain提出的二维对数搜索方法(TwoDimensional Logarithmic Search，TDLS)，跟踪最小失真方向并降低了计算复杂度。另一种著名方法是三步搜索方法(Three Step Search，TSS)，它在搜索窗内只搜索25个点，而FS要搜索225个点。后来有很多方法针对TSS做了进一步的修改，例如新三步搜索方法(New ThreeStep Search，NTSS)，该方法在第一步进行了中心偏置模式处理。另一种是有效的三步搜索方法(Efficient Three Step Search，ETSS)，该方法在第一步应用了小菱形模式，并且在搜索区域内不限制搜索步骤。Puri等人提出了混合TDLS和TSS的正交搜索方法(OrthogonalSearch，OS)。Ghanbari提出的交叉搜索方法(Cross Search，CS)和TDLS十分相似。Po等人应用了真实视频序列的中心偏置特性提出了四步搜索方法(Four-step Search，4SS)。2000年Zhu等人提出了菱形搜索方法(Diamond Search，DS)，该方法以其卓越的搜索精度和搜索速度被广泛应用。

[0006] DS搜索方法的一个实施示例如图1所示。它有两个不同的固定模式，一个是大菱形搜索模式LDSP(Large Diamond Search Pattern)，另一个小菱形搜索模式SDSP(Small Diamond Search Pattern)。该搜索方法能够十分精确地找到全局最小点。然而，DS搜索方法的处理过程中一直使用固定的搜索模式，没有考虑视频序列的内容特性和运动复杂度，将会搜索一些没有必要的点，从而造成计算资源的浪费。

发明内容

[0007] 针对现有技术的不足，本发明所要解决的技术问题在于提供一种新的视频编码运动估计搜索方法。该搜索方法针对信源编码的需要，基于菱形和三角形自适应进行视频编码运动估计。

[0008] 为实现上述的发明目的，本发明采用下述的技术方案：

[0009] 一种用于视频编码运动估计的搜索方法，其特征在于包括如下的步骤：

[0010] 第1步：如果初始搜索点O的绝对差值和小于预定阈值，则搜索结束，否则进入菱形搜索模式；先计算菱形的四个顶点A、B、C和D的绝对差值和；如果初始搜索点O的绝对差值和最小，则搜索结束；如果绝对差值和最小的点为该菱形的顶点A，则进入第2步；

[0011] 第2步：比较B、C、D和O的绝对差值和；如B或D点的绝对差值和为最小值，则进入第6步；否则进入第一三角形搜索模式，该第一三角形搜索模式是以第1步中的顶点A为外心，以X、Y和Z为顶点的等腰三角形；分别计算X、Y和Z的绝对差值和并与A的绝对差值和比较，如A点的绝对差值和最小，则搜索结束；如X点的绝对差值和最小，则进入第3步；如Y点的绝对差值和最小，则进入第4步；如Z点的绝对差值和最小，则进入第5步；

[0012] 第3步：进入第二三角形搜索模式，该第二三角形搜索模式是以顶点X为外心，以B、Y’和Z’为顶点的等腰三角形；分别计算Y’、Z’的绝对差值和并与X的绝对差值和比较，如X点的绝对差值和最小，则搜索结束；如Y’点的绝对差值和最小，则返回第3步；如Z’点的绝对差值和最小，则进入第4步；

[0013] 第4步：进入第三三角形搜索模式，该第三三角形搜索模式是以顶点Y为外心，以X’、Y’和Z’为顶点的等腰三角形；分别计算X’、Y’、Z’的绝对差值和并与Y的绝对差值和比较，如Y点的绝对差值和最小，则搜索结束；如Y’点的绝对差值和最小，则返回第4步；如Z’点的绝对差值和最小，则进入第5步；如X’点的绝对差值和最小，则进入第3步；

[0014] 第5步：进入第四三角形搜索模式，该第四三角形搜索模式是以顶点Z为外心，以D、X’和Y为顶点的等腰三角形；分别计算X’、Y’的绝对差值和并与Z的绝对差值和比较，如Z点的绝对差值和最小，则搜索结束；如Y’点的绝对差值和最小，则返回第5步；如X’点的绝对差值和最小，则进入第4步；

[0015] 第6步：进入第五三角形搜索模式，该第五三角形搜索模式是以A、X和Y为顶点的等腰三角形；分别计算X、Y的绝对差值和并与A的绝对差值和比较，如A点的绝对差值和最小，则搜索结束；如X或Y点的绝对差值和最小，则进入第7步；

[0016] 第7步：进入第六三角形搜索模式，在X点的绝对差值和最小的情况下，该第六三角形搜索模式是以X、A’和B’为顶点的等腰三角形；分别计算A’、B’的绝对差值和并与X的绝对差值和比较，如X点的绝对差值和最小，则搜索结束；否则重复第7步；在Y点的绝对差值和最小的情况下依此类推。

[0017] 其中，在第1步中，将当前编码块左上角坐标加上前一编码块的预测运动矢量在参考帧中的坐标位置定义为初始搜索点O。编码块的预测运动矢量为相邻块运动矢量的中值，其中相邻块包括参考帧中的时域相邻块和当前帧中所述编码块的三个空域相邻块。

[0018] 所述菱形搜索模式是以初始搜索点O为中心，步长为1个像素点向左、右、上和下扩展形成的一个菱形。

[0019] 所述阈值用于检测出静止块和准静止块，对静止块和准静止块直接中止搜索。

[0020] 本发明所提供的基于菱形和三角形自适应的视频编码运动估计搜索方法可以自适应地选择初始搜索点以避免陷于局部最小，在搜索过程中针对视频序列的内容特性和运动复杂度自适应的选择菱形模式和三角形模式进行搜索，在保证图像质量的前提下极大的提高了运动估计的搜索速度。

附图说明

[0021] 下面结合附图和具体实施方式对本发明作进一步的详细说明。

[0022] 图1为现有DS搜索方法的搜索示例图；

[0023] 图2为通过预测运动矢量确定初始搜索点的示意图；

[0024] 图 3(a) ～ 图 3(d) 分 别 为“Beijing Weather Girl”、“WomanDrinking”、“Circus”and“Mobile Hands”视频序列的预测运动矢量差分分布图；

[0025] 图4(a)～图4(f)为本发明所提供的基于菱形和三角形自适应的视频编码运动估计搜索方法的搜索策略示意图；

[0026] 图5(a)为“Beijing Weather Girl”视频序列的搜索点数比较曲线图，图5(b)为“Beijing Weather Girl”视频序列的峰值信噪比的比较曲线图；

[0027] 图6(a)为“Woman Drinking”视频序列的搜索点数比较曲线图，图6(b)为“Woman Drinking”视频序列的峰值信噪比的比较曲线图；

[0028] 图7(a)为“Circus”视频序列的搜索点数比较曲线图，图7(b)为“Circus”视频序列的峰值信噪比的比较曲线图；

[0029] 图8(a)为“Mobile Hands”视频序列的搜索点数比较曲线图，图8(b)为“Mobile Hands”视频序列的峰值信噪比的比较曲线图。

具体实施方式

[0030] 本专利申请提出了一种基于菱形和三角形自适应的视频编码运动估计搜索(简称为DTAS)方法。该DTAS方法的基本思路在于：首先利用空域和时域相邻块的预测运动矢量确定初始搜索点，然后根据视频序列运动矢量的方向选择不同的搜索策略，对静止块和准静止块直接中止搜索，在搜索过程中针对视频序列的内容特性和运动复杂度自适应地选择菱形模式和三角形模式，从而在保证搜索精度的同时有效地提高了搜索速度。

[0031] 参考图2，首先通过预测运动矢量确定初始搜索点O。为了取得一个尽可能靠近全局最小点的初始搜索点，选择合适的预测运动矢量显得十分重要。为了获得当前块精确的预测运动矢量，需要考虑2个因素：1)包含相邻块区域(ROS)的确定。2)计算预测运动矢量的方法。

[0032] 包含相邻块区域(ROS)定义如下：ROS＝{MB0，MB1，MB2，MB3}，其中MB0表示参考帧中时域相邻块，而其它3个块MBi表示当前帧中编码块的空域相邻块。如果相邻块的运动矢量为MV0，MV1，MV2和MV3，那么编码块的预测运动矢量MVcurrent为相邻块运动矢量的中值。定义如下：MVcurrent＝median(MV0，MV1，MV2，MV3)

[0033] 当前编码块左上角坐标加上前一编码块的预测运动矢量MVcurrent在参考帧中的坐标位置定义为初始搜索点O。

[0034] 自适应运动估计的目的就是通过选择合适的初始搜索点在搜索区域内有效地适应移动对象，这样做的好处在于容易找到真正合适的运动矢量并减少计算量。

[0035] 在本DTAS方法中，采用绝对差值和(SAD)为块匹配失真函数。SAD的定义为：其中fk(m，n)表示当前编码帧中位置为(m，n)的灰
度值，fk-1(m，n)表示参考帧中位置为(m，n)的灰度值。(i，j)表示当前编码图像块和参考图像块之间的位移。

[0036] 另一方面，发明人用四个视频序列进行预测运动矢量差分分布图实验，图3(a)～图3(d)分别为“Beijing WeatherGirl”、“WomanDrinking”、“Circus”and“Mobile Hands”视频序列的预测运动矢量差分分布图，这些视频序列包含了各种复杂度运动对象。从这些预测运动矢量差分的分布图可知，预测运动矢量差分通常高度集中在以原点为中心的2个像素宽的区域内。因此设置阈值T用于检测出静止块和准静止块，对静止块和准静止块直接中止搜索，从而加快搜索速度。在本DTAS方法中，实验结果显示当T设置为512时虚警概率最小。

[0037] 该DTAS方法的具体搜索策略如图4(a)～图4(f)所示，包括如下的步骤：

[0038] 第1步：参考图4(a)，如果初始搜索点O的绝对差值和SAD(O)＜阈值T，则搜索结束。否则进入菱形搜索模式ABCD，该菱形搜索模式是以初始搜索点O为中心，步长为1个像素点向左、右、上和下扩展形成的一个菱形，A、B、C和D点为该菱形的四个顶点。先计算该菱形四个顶点A、B、C和D的SAD值。如果初始搜索点O点的SAD最小，则搜索结束；如果最小SAD点为该菱形的四个顶点之一(如A点，其它三点依次类推)，则进入第2步。

[0039] 第2步：参考图4(a)，比较B、C、D和O各点的SAD值。如B或D点的SAD值为最小值，则进入第6步；否则进入三角形搜索模式XYZ，该三角形搜索模式是以第1步中的菱形顶点A为外心，形成的一个以X、Y和Z为顶点的等腰三角形XYZ。计算X、Y、Z的SAD值并与A点的SAD值比较，如A点的SAD值最小，则搜索结束；如X点的SAD值最小，则进入第3步；如Y点的SAD值最小，则进入第4步；如Z点的SAD值最小，则进入第5步。

[0040] 第3步：参考图4(b)，进入三角形搜索模式BY’Z’，该三角形搜索模式是以三角形顶点X为外心，形成的一个以B、Y’和Z’为顶点的等腰三角形BY’Z’。计算Y’、Z’的SAD值并与X点的SAD值比较，如X点的SAD值最小，则搜索结束；如Y’点的SAD值最小，则返回第3步；如Z’点的SAD值最小，则进入第4步；

[0041] 第4步：参考图4(c)，进入三角形搜索模式X’Y’Z’，该三角形搜索模式是以三角形顶点Y为外心，形成的一个以X’、Y’和Z’为顶点的等腰三角形X’Y’Z’。计算X’、Y’、Z’的SAD值并与Y点的SAD值比较，如Y点的SAD值最小，则搜索结束；如Y’点的SAD值最小，则返回第4步；如Z’点的SAD值最小，则进入第5步；如X’点的SAD值最小，则进入第3步；

[0042] 第5步：参考图4(d)，进入三角形搜索模式DX’Y’，该三角形搜索模式是以三角形顶点Z为外心，形成的一个以D、X’和Y为顶点的等腰三角形DX’Y。计算X’、Y’的SAD值并与Z点的SAD值比较，如Z点的SAD值最小，则搜索结束；如Y’点的SAD值最小，则返回第5步；如X’点的SAD值最小，则进入第4步；

[0043] 第6步：参考图4(e)，进入三角形搜索模式AXY，该三角形搜索模式是以菱形顶点A为顶点，形成的一个以A、X和Y为顶点的等腰三角形AXY。计算X、Y的SAD值并与A点的SAD值比较，如A点的SAD值最小，则搜索结束；如X或Y点的SAD值最小(如X点的SAD值最小)，则进入第7步；

[0044] 第7步：参考图4(f)，进入三角形搜索模式XA’B’，该三角形搜索模式是以三角形顶点X为顶点，形成的一个以X、A’和B’为顶点的等腰三角形XA’B’。计算A’、B’的SAD值并与X点的SAD值比较，如X点的SAD值最小，则搜索结束；否则重复第7步。

[0045] 上述的DTAS方法可以解决经典运动估计方法中存在的一些缺陷，例如搜索的最佳匹配点容易陷于局部最小点，忽略视频序列的内容特性和运动复杂度，搜索一些没有必要的点从而造成计算资源的浪费等等。

[0046] 另外，在预测运动矢量差分规律方面，发明人通过大量的实验发现，预测运动矢量差分的分布是高度集中的。利用运动矢量的预测技术，即用当前帧中当前编码块的左、上、右上相邻块和参考帧中对应位置的块的运动矢量作为预测运动矢量，可以得到预测运动矢量差分分布。

[0047] 发明人通过对大量不同类型视频序列的预测运动矢量差分分布图分析，获知预测运动矢量差分分布跟视频内容的运动复杂度高度相关。对于低复杂度的视频，预测运动矢量差分更多的向初始搜索点集中。这是因为平滑有序的预测运动矢量跟真正的运动矢量有更密切的相互关系，并且产生更少的预测误差。基于这种关系，本DTAS方法能够通过菱形模式和三角形模式的转换，自适应地改变搜索区域，从而避免不必要的搜索。

[0048] 本DTAS方法实现的技术效果可以用曲线图和表格的形式予以体现。其中，从图像质量和计算复杂度两方面比较FS、DS和DTAS方法，用峰值信噪比PSNR表示图像质量，用每帧平均搜索点数表示计算复杂度，用ΔPSNR比较DS和DTAS方法的质量性能，用加速比SUR描述DTAS相对于DS方法的提速。此处的SUR定义如下：SUR＝PNDS/PNDTAS。其中PNDS表示DS方法每个块的搜索点数，PNDTAS表示DTAS方法每个块的搜索点数。

[0049] 发明人用“Beijing Weather Girl”、“Woman Drinking”、“Circus”and“Mobile Hands”这四个视频序列来进行实验，这些视频序列包含了各种复杂度运动对象。块的大小被固定为16×16，搜索范围为±7像素点，只对亮度信号进行运动估计。

[0050] 根据每帧的峰值信噪比PSNR和搜索点数，对DS、FS和DTAS三种方法进行性能比较结果如图5至图8所示，可以看出DTAS方法图像质量十分接近DS和FS方法，而搜索点数却大幅度下降。

[0051] 对于这四个视频序列一百帧的平均峰值信噪比和搜索点数描述如表1和表2中。表1给出了各种方法平均搜索点数，通过比较可知，DS方法的计算量是DTAS方法计算量的
2.8～10.24倍。表2给出了各种方法的平均峰值信噪比PSNR，可以看出DTAS方法的PSNR十分接近DS或者FS方法。对于不同类型视频序列根据加速比SUR和峰值信噪比PSNR可以看出DTAS方法性能远远超过DS方法，达到几乎一致的精度，而DTAS方法的计算量却远远少于DS方法。同时值得注意的是DTAS方法针对不同类型的视频序列展示的性能都表现出相当的稳定性。

[0052]Beijing Weather Girl Woman Drinking Circus Mobile Hands
FS 225 225 225 225
DS 12.50 17.00 16.46 22.82
DTAS 1.22 5.30 5.88 5.10
SUR 10.24 3.21 2.80 4.47

[0053] 表1平均搜索点数比较(次/块)

[0054]Beijing Weather Girl Woman Drinking Circus Mobile Hands
FS 40.137 36.655 36.163 37.724
DS 40.082 36.645 36.107 37.684
DTAS 39.944 36.619 36.078 37.729
ΔPSNR -0.138 -0.026 -0.029 +0.045

[0055] 表2平均峰值信噪比PSNR比较(单位：dB)

[0056] 上述实验结果表明，对于各种不同运动程度的视频序列，本发明所提供的DTAS方法不但可以获得和DS方法基本相同的图像质量，而且加速比SUR达到2.80～10.24，大大降低了块匹配的计算量，因此本DTAS方法更加适用于实时性要求比较高的场合。

[0057] 上面对本发明所述的用于视频编码运动估计的搜索方法进行了详细的说明，对于本技术领域的一般技术人员来说，再不背离本发明所属技术方案的精神和权利要求范围的情况下对它进行的各种显而易见的改变都在本发明的保护范围之内。