音视频学习–运动估计搜索算法五-TZSearch

内容介绍

运动估计（ME）是视频压缩的关键操作。事实上通过消除时间冗余来极大地提高压缩效率，此过程是视频编码器中最关键的部分，本身会消耗超过 50% 的编码复杂度或计算编码时间。为了减少计算时间，许多快速 ME 算法被提出并实现。各路专家学者通过各种方式进行优化和改进。

运动估计常用的搜索算法有新三步搜索算法、二维对数搜索算法、三步搜索算法(Three Step Search, TSS)及全搜索算法(Full Search, FS) 等。有兴趣的可以参考之前的文章。

音视频学习–运动估计搜索

音视频学习–运动估计搜索算法一

音视频学习–运动估计搜索算法二

音视频学习–运动估计搜索算法三

音视频学习–运动估计搜索算法四

本文重点说明TZSearch算法。

TZSearch是什么？

TZSearch是一种运动估计算法，它用于视频编码中的运动估计步骤。该算法采用了一种快速搜索的策略，可以在保证编码质量的前提下，大幅度减少搜索时间。因为视频序列中物体运动状态不同，很难用单一的模型确定最优匹配块。因此，针对这一问题，TZSearch算法作为一种快速搜索算法，并采用混合搜索模型来解决这一挑战。该算法具有多种不同的搜索模板，包括方形、钻石、光栅等。

与传统算法不同的是，TZSearch算法不再使用原点作为搜索起始点。它综合考虑了视频序列的特性，并采用AMVP技术来预测新的起始搜索点。这种技术利用时域或空域上相邻宏块的MV（运动矢量）对当前块进行预测，并将其作为起始点预测集合中的一个元素。然后从预测集合中选择使得率失真代价J最小的点作为最优起始搜索中心，以节省搜索时间。

另外，在步长为1时，TZSearch算法采用两点搜索算法。它会搜索图像中与当前最优点距离最近的两个点。例如，如果最优点为2，则会搜索a和b两个点；如果最优点为6，则会搜索e和g两个点。这样可以补充搜索最优点尚未搜索的点。而当搜索步长大于设定的阈值时，算法会采用光栅扫描模式来提高搜索的准确性。

TZSearch算法在满足搜索准确性的同时也能减少搜索时间。它的优点在于能够根据视频序列的特性选择最佳起始搜索点，并根据步长灵活调整搜索模式，从而在搜索准确性和计算复杂度方面取得了一定的平衡。

TZSearch原理

具体来说，TZSearch算法采用了以下几个步骤：

1. 确定起始搜索点：根据先验信息（如相邻块的运动矢量），采用 AMVP 技术在五个候选运动矢量 MV 中选择率失真代价最小的候选MV作为起始搜索点。
2. 从起始搜索点以步长1开始，按照8点钻石模板或正方形模板在搜索范围内进行搜索，以 2 的倍数依次增加，选出率失真代价最小的点作为该步骤搜索的结果。
3. 若步骤2中得到的最优点对应的步长为1，则需要在该点的周围进行两点搜索，其主要目的是补充搜索最优点周围尚未搜索的点。
4. 若步骤2中得到的最后点对应的步长大于某个阈值，则以该最优点为中心，在一定范围内做Raster全搜索，即搜索该范围内的所有的点，选择率失真代价最小的作为该步骤的最优点。
5. 以步骤4得到的最优点为新的起始的搜索点，重复步骤2到步骤4，使用同类型搜索模板进行循环细化搜索，直到最佳匹配点出现在搜索中心位置时退出循环，并保存最佳 MV 和 SAD。

钻石搜索模版：

正方形搜索模版

BD-Rate表示PSNR相同时，TZSearch与全搜索算法相比编码比特率的增加量，该值为正表示编码性能有所降低。BD-PSNR表示编码比特率相同时，TZSearch与全搜索算法相比PSNR的增加量，该值为正表示编码性能有所提升。运动搜索时间用下式进行比较：

其中TTZSearch和TFullSearch分别表示TZSearch和全搜索算法耗费的时间。引用《新一代高效视频编码H.265HEVC：原理、标准与实现》表4.4中的数据可以看出，TZSearch算法与全搜索算法相比，性能上略有降低（同PSNR下比特率平均仅增加了0.45%），而运动搜索时间仅为全搜索算法的1/5。

VTM代码走读

由于TZSearch相对比较复杂，我们借用VTM的代码做一下分析，相关官网可以参考如下链接：

https://jvet.hhi.fraunhofer.de/

VTM中支持的搜索类型如下，包括全搜索，钻石搜索，选择搜索，增强钻石搜索等。

基本编码过程如下：

IntTZSearchStruct

IntTZSearchStruct通常用于存储运动估计的结果，包括最优运动矢量、失真值、距离等信息。

根据不同的运动估计模式选择不同的函数，完成快速查找：

InterSearch::xTZSearch() 函数对给定预测单元 (PU) 执行最佳运动矢量 (MV) 的时间和空间搜索。

（1）初始化，并确定起始位置，将中值预测器设置为起始点最佳MV。 

（2）确认查找范围：

（2）该函数使用菱形或方形图案围绕最佳 MV 执行粗略搜索。每轮粗略搜索的搜索范围加倍。

如果启用扩展搜索设置，该功能将使用光栅或星形图案执行更精细的搜索。首先执行光栅搜索，然后执行星形搜索。精细搜索的搜索范围是粗略搜索的搜索范围的一半。

通过以越来越细的粒度检查周围的点来微调在早期搜索阶段找到的最佳运动矢量 (MV)：迭代细化，当最佳距离大于 0 时循环根据当前最佳 MV 设置起始坐标（iStartX、iStartY）；如果最佳距离大于1，将距离减半 (iDist = cStruct.uiBestDistance >>= 1)。使用菱形搜索模式 (xTZ8PointDiamondSearch) 或方形搜索模式 (xTZ8PointSquareSearch)。

如果最佳距离为1，将最佳距离设置为 0 以指示终止。

通过以星形模式扩展周围的搜索区域，潜在地找到在 earlier 阶段可能被遗漏的更好的匹配：

将起始坐标（iStartX、iStartY）设置为当前最佳 MV；重置最佳距离和点数，为星形搜索做准备；

迭代遍历增加的距离（iDist）直到 searchRange：根据配置（bStarRefinementDiamond）使用菱形搜索模式（xTZ8PointDiamondSearch）或正方形搜索模式（xTZ8PointSquareSearch）。

如果满足停止条件（bStarRefinementStop 和 cStruct.uiBestRound >= uiStarRefinementRounds），则退出。

如果最佳距离仍然为 1，则使用 2 点搜索（xTZ2PointSearch）处理最后两个可能的候选者。

这时函数返回找到的最佳 MV 和相应的 SAD。

至此TZSearch介绍完毕。

参考文献

https://vcgit.hhi.fraunhofer.de/jvet/VVCSoftware_VTM

https://vcgit.hhi.fraunhofer.de/jvet/HM/-/releases/HM-16.21

https://blog.csdn.net/BigDream123/article/details/118057801

https://blog.csdn.net/weixin_45615071/article/details/108889262

https://blog.csdn.net/lin453701006/article/details/77089786

我是一枚爱跑步的程序猿，维护公众号和知乎专栏《MediaStack》，有兴趣可以关注，一起学习音视频知识，时不时分享实战经验。