hevc视频编码-搜索窗口和快速搜索

块匹配的搜索策略决定了运动估计收敛速度和匹配块的准确度，一般可以把搜索策略分为两类；全搜索和快速搜索。

全搜索也称为穷尽搜索，遍历搜索区域内的所有位置块，因此精确度最高，但耗费的运算资源也最多。

为了保证搜索的效率，整数运动估计不会在整个参考帧内进行，而是限定于某个搜索范围，这一范围被称为 搜索窗口。在HEVC标准下，搜索窗口的大小一般设置为[-64,64] 换而言之，对于每一个PU都在16384(128x128种可能的运动矢量。显然，对于如此庞大的可能性，遍历是极不可取的搜索方法)。因此，不论是软件还是硬件实现，通常会选择某种快速搜索的策略进行搜索，快速搜索策略在保证一定精度的运动估计前提下，通过减少检索点，从而减少运算复杂度。因此可以根据一定的收敛模型（搜索模版）。 一步步缩小搜索范围逼近最佳匹配点，较为著名的快速搜索 有菱形搜索，六边形搜索，十字形搜索等。图5-4给出了菱形搜索和六边形搜索的图案。

菱形搜素和六边形搜索。

4 HM推荐算法

在HEVC模型HM中，整像素运动估计单元采用了快速预测算法TZSearch ，算法流程如图5-5.

开始->确定搜索起始点->方形/菱形所有步长的8点搜索->两点搜索-> 距离大于 iRaster -> 光栅搜索->优化过程 ->结束。

TZSearch 算法流程。

第一步是确定搜索起始点的位置，比较参考帧中对应位置的PU块的上方，左方，右上方的PU块的MV和原点MV(0,0)作为起始MV的匹配误差，匹配误差，误差最优的候选MV用作起始运动矢量。

第二步 是选用方形或菱形的搜索图形，从起始点开始进行搜索步长葱1～64 的搜索。假如最佳的搜索步长是1，再进行一次两点搜索。

第三步搜索的开始先判断第二步得到的最佳匹配位置与索搜中心之间的距离。若该距离为0，则直接跳过这一步的搜索过程；若该距离比预设值iRaster 要大，则要进行一次以iRaster为步长的光栅搜索。即全搜索；若该距离小于iRaster，则直接进入优化过程。

第三步 搜索的开始先判断第二步 得到的最佳匹配位置与搜索中心之间的距离，若该距离为0，则直接跳过这一步的搜索过程；若该距离比预设值iRaster 要大，则要进行一次以iRaster为步长的光栅搜索，即全搜索；若该距离小于iRaster，则直接进入优化过程。

第四步以第三步得到的最优点作为起点，再进行8点的菱形形成方形 的搜索。这类似于第二步，但不同之处在于第二步是为了初步确定大致的位置，而第四步是在一个大范文内较优秀的位置开始进行运动矢量的优化。因此，第四步的搜索步长是逐步收敛的，从先前的最优步长逐步递减到1（同样以2的指数递减。） 此过程中一旦最优距离为零或者搜索步长为最小值1. 便终止所有搜索。经过四步搜索得到的位置即最终的整像素运动矢量。

表5-1给出了TZSearch 相对全搜索的B-DRate 增量。BD-Rate 是衡量图像编码效率的评判标准，表征的是在相同PSNR 图像质量下，不同编码方法之间的BitRate 的情况，以下实验基于HEVC测试视频系列，在HM 平台完成，采用帧间搜索的默认设置，但仅采用1帧参考帧。

相对于全搜索，TZSearch 的编码效果与全搜索相比损失较小。虽然TZSearch能够节省大量时间，但是计算代价仍然很大，不适合于硬件实现。