基于改进TZsearch的视频快速编码算法研究

Research of Fast Video Coding Algorithm on Improved TZsearch

摘要: 随着网络多媒体技术的高速发展以及H.265/HEVC视频编解码标准的不断运用，如何高效地进行视频编码是值得关注的热点之一。针对高效编码视频序列的问题，基于H.265/HEVC帧间预测过程中的运动估计原理以及对视频图像最优点的概率统计，加入判断提前终止搜索条件，提出一种基于改进TZsearch的快速编码算法，有效降低了视频编码时间。通过对经典视频序列的编码验证和对比，改进TZsearch算法在满足编码质量的同时降低编码时间15.37%，更加准确、高效地实现了视频编码。

Abstract: With the rapid development of network multimedia technology and the continuous application of H.265/HEVC video codec standard, how to encode video efficiently is one of the hotspots worthy of attention. Aiming at the problem of efficient coding of video sequences, based on the motion estimation principle in the process of H.265/HEVC inter prediction and the probability statistics of the best advantage of SS video image, adding the judgment early termination search condition, a fast coding algorithm based on improved TZsearch is proposed, which effectively reduces the video coding time. Through the coding verification and comparison of classical video sequences, the improved TZsearch algorithm not only meets the coding quality, but also reduces the coding time by 15.37%, and realizes video coding more accurately and efficiently.

1. 引言

H.265/HEVC作为目前广泛使用的视频编解码标准，主要采用混合编码框架技术，编码压缩能力相较于H.264提升50% [1]。随着H.265/HEVC编码率的提升，其编码效率也急剧降低 [2]。其中帧间预测是时间复杂度最高的关键技术，同时能直接影响到视频编码后主客观质量，主要采用的方式是运动估计。

运动估计常用的搜索算法有新三步搜索算法 [3]、二维对数搜索算法 [4]、三步搜索算法(Three Step Search, TSS) [5] 及全搜索算法(Full Search, FS) [6] 等。在搜索最佳匹配块的过程中需要使用一定的搜索算法，是编解码过程中时间复杂度最高的模块，搜索的精度与时间决定视频的实时压缩效率，其中包括设置搜索的起点、搜索范围大小的确定、选取搜索模式。针对提升编码效率的需求，国内外学者对编码搜索算法开展了一系列的研究，并进行了算法改进。Li X等人提出一种基于六边形搜索模板的改进TZSearch算法，将六边形搜索模板替代菱形模板，六边形模板仅需要30次搜索，将搜索速度提升1.7~6.5倍，性能损失小于2% [7]。Tang等人提出一种基于运动情况改变搜索模板的改进TZSearch算法，帧内运动剧烈的搜索块采用底数为4的六边形搜索模板，运动缓慢的搜索块采用底数为4的六边形搜索模板，帧间相关性大的搜索块采用光栅扫描模板，这种改进TZSearch算法适用于平行相机拍摄的视频序列 [8]。Purnachand等人提出一种提前设置阈值进行判断的改进TZSearch算法，不再采用TZSearch算法中传统八点钻石搜索模板，而是使用六边形搜索模板进行代替，并且在开始搜索过程前设定步长的阈值，当搜索步长小于设定阈值的情况下采用六边形搜索模板 [9]。Kibeya等人提出一种基于精细化搜索的改进TZSearch算法，不再根据搜索步长进行两点搜索和光栅扫描搜索，直接使用八点钻石搜索模板进行搜索，并提出三种细化搜索模型优化搜索路径来解决精度降低的问题 [10]。上述的算法大多适用于运动平稳的视频序列，针对较为复杂的视频序列会有较大的质量损失，并且上述算法均没有区分视频中物体高速与低速运动时的编码效率，存在搜索次数多、编码效率低等问题。本文提出一种基于改进TZsearch的快速编解码算法，通过对高速与低速视频不同运动状态编码分析和算法改进，在保证编码质量的同时提升了编码效率，减少了编码时间，更加适用于实时视频编码的场景。

2. 运动估计

2.1. 运动估计原理

H.265/HEVC中采用基于块匹配的运动估计，将一帧视频图片分成多个区域块，运动估计是指为当前图像的像素块在已编码图像中寻找最佳匹配块，从而计算运动矢量 [11]。将相邻两帧图像通过树形编码单元分别分成互相独立的像素块，根据搜索范围在参考帧中按照规定算法搜索误差最小的块，通过块匹配原则计算搜索块与当前帧块之间的匹配度，从而得到当前帧的最佳匹配块并计算出当前帧的运动矢量。在编码当前帧时只需要传输参考图像的位置信息和两者之间计算出来的运动矢量，解码时依旧参考帧与残差数据预测出当前帧。

2.2. 块匹配准则

运动估计需要有一个准则来判定搜索块的匹配度，不同的块匹配标准具有不同的判决精度，并且所产生的残余块的系数也不同，从而导致编码压缩率存在某些差异。这些块匹配准则分别是最小均方差误差MSE [12]、绝对误差和SAD [13] 和最大匹配像素数MPC [14]。

1) MSE准则：

$MSE\left(x,y\right)=\frac{1}{MN}{\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{n=1}{\overset{N}{\sum }}{\left[f_i\left(m,n\right)-f_{i-1}\left(m+x,n+y\right)\right]}^2}}$ (1)

2) SAD准则：

$SAD\left(x,y\right)=\frac{1}{MN}{\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{n=1}{\overset{N}{\sum }}\left|f_i\left(m,n\right)-f_{i-1}\left(m+x,n+y\right)\right|}}$ (2)

3) MPC准则：

$MPC\left(x,y\right)=\frac{1}{MN}{\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{n=1}{\overset{N}{\sum }}T\left(f_i\left(m,n\right),f_{i-1}\left(m+x,n+y\right)\right)}}$ (3)

其中块区域边长M、N，(x, y)表示运动估计， $f_i$ 和 $f_{i-1}$ 表示当前图像像素和参考图像像素。

在这三个匹配准则中，SAD准则不含乘除法运算，使用最为广泛。在本文中也将采用这种准则进行搜索块匹配。本文在运动估计过程中使用拉格朗日率失真优化方法来计算运动矢量，率失真代价J计算如下：

$J=SAD\left(x,y\right)+{\lambda }_m\cdot R_m$ (4)

其中 ${\lambda }_m$ 表示拉格朗日因子， $R_m$ 表示比特数。

3. 改进TZSearch算法

3.1. TZSearch算法原理

视频序列中物体运动状态不同，很难用单一的模型确定最优匹配块，难以用一种单一的搜索模板同时满足性能与计算复杂度最优。TZSearch作为快速搜索算法，它是一种混合搜索模型，搜索模型有八点方形、八点钻石、光栅以及两点等，具体如图1所示。

TZSearch算法不再使用原点作为搜索起始点，综合考虑视频序列特性采用AMVP技术预测新的起始搜索点，利用时域或空域上相邻宏块的MV对当前块进行预测并作为起始点预测集合中元素之一，从预测集合中选择率失真代价J最小的点作为最优起始搜索中心，节省搜索时间。另外，当步长为1时采用两点搜索算法，搜索图像中与当前最优点距离最近的点，例如若最优点为2时会搜索a、b两个点，若最优点为6时会搜索e、g两个点，从而补充搜索最优点尚未搜索的点；当搜索步长大于设定的阈值时采用光栅扫描模式，提高搜索的准确性。综上所述，TZSearch算法满足搜索准确性的同时减少搜索时间，在准确性和计算复杂度方面均有可取之处。

(a) 八点钻石搜索模板 (b) 正方形搜索模板

Figure 1. Schematic diagram of TZSearch algorithm

图1. TZSearch算法示意图

TZSearch算法流程具体描述如下：

Step1：起始搜索点的预测。采用AMVP技术在五个候选运动矢量MV中选择最优作为最优起始点；

Step2：从起始搜索点以搜索步长为1开始，采用八点钻石、方形模板，以2的倍数依次增加，若搜索框大小为64依次进行步长为1、2、4、8、16、32、64的模板搜索，选出J最小的点作为该次步长搜索的最优点；

Step3：若搜索步长等于1，则需要在该步长搜索起点的周围做两点搜索；

Step4：若搜索步长大于某个设定的步长，以当前起始搜索点为中心，在一定搜索框内使用光栅搜索算法进行搜索，选出J最小的点作为该次步长搜索的最优点；

Step5:：以前面步骤得到的最优点作为最新起始搜索点，重复上述步骤使用同类型搜索模板进行循环搜索，直到最佳匹配点出现在搜索中心位置时退出循环，并保存最佳MV和SAD。

TZSearch算法引入预测初始搜索点的概念，使用可变长的搜索模式降低计算复杂度，减少搜索次数与时间，进一步提高了搜索过程的精准性，搜索流程图如图2所示。

Figure 2. Flow chart of TZSearch algorithm

图2. TZSearch算法流程图

3.2. 最优点的概率分布统计

在TZSearch算法搜索过程中，从起始搜索点以搜索步长为1开始，以2的倍数依次增加，若搜索框大小为64依次进行步长为1~64的模板搜索，搜索次数最大为4 + 6 × 8 = 52。TZSearch算法中搜索步长等于1时搜索次数为4，当步长不等于1时搜索次数为8，设置搜索轮数为k，取值为1~7。若在该次搜索过程中找到最优点时，表明以该点作为该次搜索的最优点也是下次搜索的最优起始点。

通过对六个视频测试序列进行TZSearch算法测验，统计视频图像中各个最优点的概率如表1所示，k = 1表明当搜索起点就是最优点时，概率占54%左右；k = 2表明当搜索步长等于1时找到最优点，概率占30%左右；k = 3表明当搜索步长等于2时找到最优点，概率占9%左右；k = 4表明当搜索步长等于4时找到最优点时，概率占5%左右；k = 5表明当搜索步长等于8时找到最优点，概率占1%左右；当搜索步长大于8时搜索最优点的概率可以忽略不计。

Table 1. The best probability statistics of test video sequence

表1. 测试视频序列中最优点的概率统计

根据表1中的概率统计结果，视频内容运动情况较剧烈时需要多次迭代步长搜索才能找到最优点，运动较缓慢时搜索起点有60%左右的概率就是最优点，不需要进行搜索；当搜索步长小于等于8时找到最优点的概率达98%以上，表明在当前搜索起始点的周围能够找到最优点。

3.3. TZSearch算法改进

通过对视频中最优点的概率统计，当搜索轮数大于等于4 (即搜索步长大于等于8)时已能够找到最优点。在TZSearch算法中匹配搜索固定是七轮，搜索次数设置为4 + 6 × 8 = 52次，在找到最优点后继续后面的搜索会增加编码计算复杂度，增加编码时间。这里提出TZSearch算法改进方法，通过加入判断提前终止搜索条件的方式使得当搜索过程中在找到最优点后及时退出搜索过程，从而降低TZSearch算法搜索次数并减少编码时间。改进的TZSearch算法搜索流程图如图3所示。

加入判断提前终止搜索条件的改进TZSearch算法流程具体描述如下：

Step1：起始搜索点的预测。在五个候选MV中选择最优作为确定最优起始搜索点；

Step2：从起始搜索点以搜索步长为1开始，以2的倍数依次增加，根据最佳匹配法则选出J最小的点作为该次步长搜索的最优点；

Step3：若搜索步长等于1，则需要在该步长搜索起点的周围做两点搜索；若搜索步长大于某个设定的步长，以当前起始搜索点为中心，在一定搜索框内使用光栅扫描模式进行搜索，选择选出J最小的点作为该次步长搜索的最优点；

Step4：根据最佳匹配法则计算当前搜索步长下所有匹配点的SAD值，若所有匹配点的SAD值均大于当前的最优点，则提前停止搜索过程；

Step5：以前面步骤得到的最优点作为最新起始点，重复上述步骤进行循环搜索，直到最优点出现在搜索中心位置时退出循环，并保存最佳MV和SAD值。

Figure 3. Flow chart of TZSearch adding judgment of early termination search

图3. 加入判断提前终止搜索条件的TZSearch算法流程图

4. 试验结果和性能分析

为了验证上述改进TZSearch算法的有效性，与全搜索(FS)算法、TZSearch算法做对比试验。以HM16.19为测试平台，基于Visual Studio 2015在Intel(R) Core(TM) i5-4590主频3.30 GHz和64位操作系统的计算机上采用六个经典视频测试序列进行验证。

六个经典视频测试序列分别选取前30帧图像进行编码，并将六个视频分成两组，分别对高速与低速两种运动物体视频进行对比，三种算法通过对不同视频的编码时间、峰值信噪比PSNR、比特率RATE等指标进行运算。三种算法的编码运算对比结果表2所示。

Table 2. Comparison results of coding operation on three algorithms

表2. 三种算法编码运算对比结果表

根据对六个视频测试序列验证结果的统计，可以看出TZsearch算法编码时间相比全搜索算法减少了18.6%，而改进TZsearch算法编码时间又有进一步减少，相比全搜索算法减少了26.3%，说明改进TZsearch对于运动物体的编码效率优化比较明显。从Rate和PSNR来看，全搜索、TZsearch和改进TZsearch算法三者的性能参数差距不大。PSNR越大说明图像编码质量越好，从中可以看出FS算法的编码性能略优于TZSearch算法和改进TZsearch算法。

为了更直观对比TZSearch和改进TZSearch算法的区别，计算出视频编码过程中的编码性能指标BD-Rate [15]、BD-PSNR [16] 以及两种算法编码时间的百分比，并将不同速度状态下视频编码结果分别表示如表3和表4所示。BD-Rate表示当改进TZSearch算法与TZSearch算法的平均PSNR相同时编码比特率的增加量，数值为正表示改进TZSearch算法的编码性能降低；BD-PSNR表示当改进TZSearch算法与TZSearch算法的平均Rate相同时PNSR的增加量，数值为正表示改进TZSearch算法的编码性能提升 [17] [18]。运动时间用公式(5)进行比较：

$\Delta T=\frac{T_{\text{TZsearch-imp}}-T_{\text{TZsearch}}}{T_{\text{TZsearch-imp}}}\times 100\%$ (5)

其中分式的分母表示改进TZsearch算法运动估计搜索过程所耗费的时间，分子表示改进TZSearch算法与TZsearch算法运动估计搜索过程所耗费时间的差值。

从表3和表4可以看出，TZSearch算法的平均PSNR值比改进TZSearch算法高0.2218 dB，说明TZSearch算法的编码性能略优于加入判断提前终止搜索条件的改进TZSearch算法。改进后的TZSearch算法同PSNR下比特率增加了0.52%，但编码时间与TZSearch算法相比减少了15.37%左右，计算复杂度远远低于TZSearch算法。此外，不同速度状态下视频编码效率是不同的，对于低速运动物体的视频TZSearch算法编码时间相较于TZSearch算法编码时间减少18.41%，对于高速运动物体的视频TZSearch算法编码时间相较于TZSearch算法编码时间减少12.34%，改进后的TZSearch对于低速运动物体的编码效率优化更加明显。尤其是对于RaceHorses.yuv这个视频序列，背景不变，视频内容运动较缓慢，搜索过程中检测到最优点时提前终止搜索，编码时间减少29.34%，而编码效果并没有因此降低。改进后的TZSearch算法可以准确、高效地实现视频编解码，更有利于视频格式转换、视频帧率提升，从而满足基于实时视频传输系统的需求。

Table 3. Comparison of motion estimation on TZSearch and improved TZSearch for low speed video

表3. 低速物体视频情况下TZSearch与改进TZSearch算法运动估计运算对比结果表

Table 4. Comparison of high speed video motion estimation on TZSearch and improved TZSearch

表4. 高速物体视频情况下TZSearch与改进TZSearch算法运动估计运算对比结果表

5. 结论

针对高效编码视频序列的问题，基于帧间预测过程中的运动估计和快速搜索算法编码原理，提出一种基于改进TZSearch的快速编解码算法。在算法中通过对视频图像最优点的概率统计，加入判断提前终止搜索条件，使得视频编码时间大大降低。经过六组经典视频序列编码验证，改进TZSearch算法在满足编码质量的同时使得编码时间降低了15.37%，更加准确、高效地实现视频编码。