英语原文共 5 页
基于块的运动估计使用混合六边形风筝交叉菱形搜索算法
2014年国际通信与信号处理会议
摘要-运动估计在运动补偿与混合DCT视频编码方案中发挥着关键性的作用。为了降低寻找最佳匹配块的计算复杂度，已经提出了许多快速搜索算法。本文所提出的混合六边形风筝交叉菱形搜索（HYBHKS）算法是基于六边形搜索（HEXS）和风筝交叉菱形搜索（KCDS）模式的自适应切换，以便以快速方式获得最佳匹配块。为了具有良好的初始位置，空间相关性和时间相关性用于运动矢量预测。实验结果表明，HYBHKS（混合六边形风筝交叉菱形搜索算法）在保持相似压缩比，结构相似性指数和峰值信噪比的情况下，使用的搜索点数量方面远低于KCDS算法和HEXS算法。
索引词（关键词）-非对称风筝模式，交叉中心偏压特性，运动估计，运动矢量预测，空间相关性，时间相关性。
- 介绍
运动估计（ME）是确定描述视频中一帧到另一帧的变换的运动矢量的过程，它减少了视频图像帧之间的时间冗余。确定运动矢量的最简单方法是将每一个图像帧划分为块，并在一定的匹配准则下，将其与参考帧中的搜索窗口进行块匹配，这被称为块匹配算法（BMA）[1]。由于解码器仅由重建帧组成，所以为了完成块匹配，需要将当前帧中的块与先前重建帧的搜索窗口中的块进行比较，这进一步减少了在发射机处引入的误差。当找到最佳匹配块时，将其与当前块进行比较，当前块与匹配块之间有误差，将残余误差进行编码并与相应的运动矢量一起发送。根据绝对差值和（SAD）准则或者均方误差（MSE）准则[2]来评估最佳匹配块，即遵守的匹配准则。在本文中，SAD用于计算块失真。对于一个NxN的块，将SAD定义为
Cij是当前帧的块，Rij是一个参考区域的块，C00和R00分别是当前区域和参考区域中的左上角样本。因此，使用SAD匹配准则找出最佳匹配块，并且将最佳匹配块的位移确定为所需的运动矢量（MV）。计算搜索窗口中所有点的全搜索（FS）算法[1]是一种计算密集型算法。为了降低与FS类似的失真度量的计算复杂度，已经提出了许多搜索模式算法（即俗称的快速搜索算法）。对数搜索（LS）算法[2]，三步搜索（TSS）算法[1]，新三步搜索（NTSS）算法[1]，四步搜索（FSS）算法[1]，菱形搜索（DS）算法[3] ]，风筝交叉菱形搜索（KCDS）算法[4]，六边形搜索（HEXS）算法[5]等就是常见的快速搜索算法。中心偏置运动矢量分布的特性被发现并且用于大多数搜索算法当中，因为在连续帧中几乎80％的块都是静止的或者准静止的。在NTSS中使用额外的搜索点来利用中心偏置运动矢量分布的特性，并在中心附近的3x3的搜索块提前终止。FSS在中心附近的5x5搜索块使用方形搜索模式。DS在中心周围使用菱形搜索模式，但它需要至少13个搜索点来决定块是否静止。风筝交叉菱形搜索（KCDS）算法的思想更加的领先。它在第一步中使用小十字菱形图案，这便是在静止块中进行快速运动估计。然后在第二步中使用不对称的风筝形状图案来提高搜索准静止块的速度。然后它再使用DS进行进一步遍历。六边形搜索（HEXS）算法使用六边形图案，这个六边形图案是仅具有7个搜索点的图案，它与理想圆形图案很相似，它对于遍历大型运动块非常地有效。
基于峰值信噪比（PSNR）和结构相似性指数（SSIM）两个参数来判断视频质量的优劣[6]。其中PSNR可以由此计算：
I (i, j)是原始框架和Icirc;(i, j)表示解码器处的重建帧。SSIM是一种比较两幅图像的质量测量方法。两个图像x和y的SSIM由公式确定：
mu;=mean（均值），sigma;2=variance（方差），C1=（K1L）2和 C2=（K2L）2，其中L是像素值的动态范围（对于8位灰度图像为255），K1和 K2是接近于零的非常小的值（Klt;lt;1）。
本文的贡献是提出一种良好的运动估计ME算法，该算法可以在保持视频质量的条件下，通过对块的运动类型进行分类，来自适应地切换搜索模式，以适应不同的图像，获得更有效的最佳匹配块。本文所提出的算法首先使用空间相关性和时间相关性来预测运动矢量，然后对块是静止的，准静止的还是大的运动块进行分类，再然后根据块的运动类型相应地自适应地选择搜索模式。
在进行匹配块搜索时，可以使用每个宏块非常少的搜索点，来适当地进行运动估计得到重建帧而不损害视频的质量。也就是说，在保证视频质量的情况下，利用比其他算法少的搜索点进行运动估计获得重建帧。
本论文的组织结构如下：第二节解释了运动矢量预测，第三节讨论了所提出的HYBHKS（混合六边形风筝交叉菱形搜索算法）算法，第四节描述了运用提出的算法得出的结果，第五节得出了最终的结论，评价了算法的优劣。
- 运动矢量预测
块的运动矢量与其空间域中的相邻块和时间域中的相邻块高度相关，在图1中描述了空间相关性[7]，在图2中描绘了时间相关性[7]。在HYBHK（混合六边形风筝十字菱形搜索运动估计算法）中，通过基于最小SAD（绝对差值和）值考虑上块（UB），左块（LB），当前帧的零运动矢量和前一帧中的并置块的运动矢量来完成当前块（CB）的运动矢量预测，获得的位置将是我们搜索的良好起点。此位置的SAD值用于对块进行分类，然后使用对数搜索（LS）算法[2]，三步搜索（TSS）算法[1]，新三步搜索（NTSS）算法[1]，四步搜索（FSS）算法[1]，菱形搜索（DS）算法[3] ]，风筝交叉菱形搜索（KCDS）算法[4]，六边形搜索（HEXS）算法[5]等算法进行进一步细化。
图1 空间相关性
图2 时间相关性
第三节 混合六边形风筝十字菱形搜索（HYBHKS）运动估计算法
A.搜索模式
HYBHKS算法使用五种搜索模式-小菱形搜索模式（SDSP），大菱形搜索模式（LDSP）[3]，风筝搜索模式（KSP）[4]，六边形搜索模式（HSP）[5]和高效六边形内部搜索模式（EHISP）[8]。
小菱形搜索模式（SDSP）和大菱形搜索模式（LDSP）如图3所示。风筝搜索模式（KSP）由两种类型的图案组成 - 垂直对称如图4（a），4（c）所示，和水平对称如图4（b），4（d）所示。六边形搜索模式（HSP）如图5所示，六边形内部搜索的使用方法展示在图6的图案中，高效六边形内部搜索（EHIS）被有效地完成。
图3 菱形搜索模式
图4 风筝搜索模式（a）上风筝（b）左风筝（c）下风筝（d）右风筝
图5 六边形搜索模式
图6 高效六边形内部搜索模式
B. Hybhks算法
HYBHKS（混合六边形风筝交叉菱形搜索算法）算法在初始步骤中使用运动矢量预测来对块的运动类型进行初始分类。然后将最小SAD（绝对差值和）值与阈值T1进行比较来判断它是否归类为准静止。经过比较判断后，如果不是小菱形搜索模式，则在5点使用和搜索。如果最小SAD位于中心，则终止搜索。否则，基于最小SAD值，将运动分类为小运动或大运动，并且分别执行不同的搜索模式，如KCDS（六边形搜索）和HEXS（风筝交叉菱形搜索）。HYBHKS的流程图被展示在图7。
算法描述如下：
第1步（MV预测）
利用从上块（UB），左块（LB），当前帧的零运动矢量和前一帧中的并置块的运动矢量获得的四个搜索点来计算SAD（绝对差值和）。计算最小SAD的位置并将搜索原点更新到该位置。之后进行最小SAD值与阈值T1的比较，如果最小SAD值小于阈值T1，则把该块分类为准静止块并且终止当前的搜索。如果最小SAD值大于阈值T1，请转到步骤2。
图 7 Hybhks算法
第2步（SDS）
利用搜索窗口中的5个搜索点进行计算SAD（绝对差值和）值，这五个搜索点是以更新位置为中心的搜索点，按照SDSP模式来计算最小的SAD点。如果最小的SAD点在中心找到，则停止当前的搜索，否则将搜索中心更新为新的最小SAD点并继续下一步。
第3步（运动类型判断）
将步骤2中的最小SAD值与阈值T2进行比较。如果小于阈值T2，则块的运动被判断为慢动作，搜索进入步骤4。如果大于阈值T2将其分类为大运动并执行步骤5。
第4步（KDS）[4]：-
（a）。风筝搜索：-
基于SDSP中最小SAD位置的方向，从图5中所示的KSP中选择相应的定向风筝，并在6个位置搜索。如果在定向风筝的中心获得最小SAD，则终止当前的搜索，否则在将最小SAD值的点更新为搜索中心，之后进入步骤4（b）。
（b）。菱形搜索：-
利用图3中所示的LDSP的九个点来计算SAD值。计算最小SAD并将中心更新到最小SAD位置。重复这一过程，直到在中心找到最小位置。然后执行SDSP以进行菱形内部搜索。
第5步（HEXS）[5]：-
（a）。六角搜索:-
利用在图6中所示的HSP的七个点来计算SAD值。计算后，将中心更新到最小SAD位置。重复该步骤，直到最小SAD位置在中心被找到。然后执行步骤5（b）。
（b）。EHIS：-
六边形被分为六组，如图6所示。如果group1，group2，group4或者group5中的其中一个具有第二个最小SAD点，则只搜索靠近该组的两个内部点。这个过程被展示在图6（a）中。如果group3或group6获胜，则只搜索一个点，这个过程被展示在图6（b）中。
C.压缩比的计算
通过使用H.262格式[9]的运动估计ME算法对当前帧和预测帧的误差系数进行编码来获得比特流，进行传输由接收机接收。通过将原本的测试视频的实际大小除以重建以后的视频的新大小来确定压缩比，并比较各种算法的压缩比，得出结论。
第四节 实验结果
进行各种实验以验证所提出方法的性能，使用不同的测试视频进行算法测试，并且将本文提出的算法与经典算法进行对比，得出优劣。将CIF（352 times; 288 ）视频序列akiyo作为测试视频，将领班和移动作为所需要的测试向量。所有实验使用的MATLAB版本均为7.0.10.499（R2010a），并在CPU类型为Intelreg;core（TM）i5-2400 CPU @ 3.10GHz的电脑上进行。
在本文中，使用#39;IPPP#39;格式代替#39;IPPPP ...#39;格式，以便与#39;IPPPP ...#39;格式相比减少错误的传播，减少压缩算法带来的误差。量化参数设置为24，帧速率设置为25fps。在SSIM计算中将常数K1和 K2均设置为0.05。将阈值T1设置为300并且将在广泛观察后将阈值T2设为600。针对测试视频foreman_cif和mobile_cif来计算平均各种参数，比如：PSNR，SSIM，计算复杂度，编码比特率和压缩比，并且将实验测得的数据分别在表I和表II中列出，并且注意区分不同的算法数据。以每个宏块所检查的平均搜索点数表示计算复杂度，输入视频以4：2：0 的YUV格式表示。将实验结果分别与经典的FS（全搜索）算法，HEXS（六边形搜索）算法和KCDS（风筝交叉菱形搜索）算法进行比较。通过仔细比较后，发现所提出的HYBHKS算法在降低计算复杂度上表现良好，相比全搜索算法等经典算法，可以明显降低计算复杂度，提高计算效率。并且在维持低编码比特率的情况下，保持了与传统快速搜索算法相似的PSNR，SSIM和压缩比值，使图像与视频质量没有明显改变，即没有明显的失真。
该算法可以在保持视频质量的条件下，通过对块的运动类型进行分类，来自适应地切换搜索模式，以适应不同的图像，获得更有效的最佳匹配块。本文所提出的算法首先使用空间相关性和时间相关性来预测运动矢量，然后对块是静止的，准静止的还是大的运动块进行分类，再然后根据块的运动类型相应地自适应地选择搜索模式。
对于各种Q值，比如Q = 24,30,36和42，确定发光（Y）分量的PSNR和编码比特率，并且在图8和图9中绘制速率失真曲线。从这些速率失真曲线图中可以明显看出，所提出的HYBHKS算法在高PSNR和低编码比特率的情况下表现良好。在图10中展示了对测试视频Akiyo_cif分别使用全搜索算法，菱形搜索算法，风筝交叉菱形搜索算法，六边形搜索算法和我们提出的混合六边形 - 风筝交叉菱形搜索算法进行处理，图片内容是视频图像的原始帧和重建帧（所重建的帧的编号是23）。根据图片所展示的多种算法实验结果，观察到利用我们所提出的混合六边形 - 风筝交叉菱形搜索算法，在进行匹配块搜索时，可以使用每个宏块非常少的搜索点，来适当地进行运动估计得到重建帧而不损害视频的质量。也就是说，在保证视频质量的情况下，利用比其他算法少的搜索点进行运动估计获得重建帧。
图8 Foreman_cif视频的速率失真曲线
图9 Mobile _ cif视频的速率失真曲线
表格1:利用FS（全搜索算法）, KCDS（风筝交叉菱形搜索算法） 和HEXS搜
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
