TZSearch算法分析和性能改进方法

杨中华，戴声奎②，汤秀丽

(①华侨大学信息科学与工程学院，厦门 361008；②厦门微电子股份有限公司博士后工作站，厦门 361008)

0 引言

多视点视频是由摄像机阵列从不同角度拍摄同一场景得到的一组视频信号，包含了丰富的3D场景信息，它满足了人们对视频场景自然和真实再现的需求，并成为近年来视频和多媒体领域的研究热点之一[1]。传统单视点的编码技术已经很成熟[2]，从三步法、新三步法、四步法、钻石形搜索法、六边形搜索法到 UMHexagons等算法的出现，还有很多混合算法的提出，如：为了进一步提高新三步搜索，提出的一种新的基于混合模板的新三步搜索算法[3]。然而，多视点视频数据量随视点数目的增加而线性增加、巨大的存储容量和信道带宽要求也成为制约其发展与应用的瓶颈。因此，在码率可控与失真度容忍度内，如何充分利用多视点视频中时间/空间相关性和视点间相关性去除冗余提高编码压缩效率[4]，是多视点视频技术研究与应用的关键。JMVC[5]作为多视点视频编码的测试平台，当前采用的TZSearch算法效果一般。以下首先阐述JMVC中TZSearch快速搜索算法的原理、统计结果及阈值设置的方法，然后提出基于TZSearch算法改进方法一、方法二，以较小的失真代价来获得较大的编码时间的降低。

1 TZSearch算法步骤

TZSearch是一种混合搜索模型快速搜索算法，具体搜索步骤如下∶

①起始点预测集合∶中值预测矢量、参考帧对应宏块的左、上、右上位置宏块的矢量以及（0，0）位置矢量。以集合中匹配误差最小值点匹配准则（SAD，Sum Absolute Difference）为下一步搜索中心点；

②在搜索中心依次进行步长为1，2，4，8，16，32，64（若搜索窗大小为64）的八点菱形搜索,一共需要进行7轮的匹配搜索，得到的最优点作为下一步的搜索中心点；

③如果步骤②的搜索中心与步骤①的搜索中心距离大于光栅搜索的步长3，将进行3个像素步长的光栅搜索，得到的最优点作为下一步的搜索中心点。否则，进入步骤④；

④细化搜索阶段，重复步骤②的搜索，直到最优点出现在搜索中心位置退出循环。

2 TZSearch算法分析与改进

2.1 最优匹配点的搜索次数统计

在上述步骤②中，每进行一次钻石搜索变量 i++，若在每次搜索的过程中找到新的最优点，则令i=0，否则i++。因此i只有0，1，2，3，4，5，6，7这八种值，并代表找到最优点后使用钻石搜索的次数。这里对视频序列[6]ballroom、exit和vassar进行实验统计（表1所示），i=7的概率最大，约占60% ～70%，即原点处就是最优点；i=6次之, 约占10%左右，即在X=1的钻石搜索中找到了最优点；i=5较次之，约占5%左右，即在X=2的钻石搜索中找到了最优点。统计结果也符合运动矢量的中心偏置特性。

表1 最优点的概率分布

2.2 搜索阈值设置原理

根据上述的统计结果得出在当前搜索点的周围（即在X≤2的钻石搜索中）找到最优点的概率最大的结论，设置提前终止搜索的阈值T，即当步骤②中的i ＞T，则停止搜索，继续执行步骤③。T理论上取值范围为1到6，根据上述实验统计结果，可令T≤3。并采用视频序列soccer（720×480）和puppy（720×480）进行验证，共编码88帧，其结果如表2所示。其中，TZS1、TZS2和TZS3依次是阈值T=1、2和3的TZSearch算法。实验平台为Intel Pentium M1.6G、1GM内存、Microsoft XP操作系统，并在JMVC4.0上验证提出的算法。量化参数分别采用32、37和42，搜索范围为64，GOP大小为8。平均峰值信噪比PSNR=(Ypsnr×4+Upsnr+Vpsnr)/6（Peak Signal To Noise Ratio）计算得到。测试结果均取自右视点。

2.3 TZSearch算法改进方法一

平行摄像头是几何平推的、摄像机水平平移、像素整体定向移动，因此光栅搜索比较适合平行摄像机配置的视差（视间）搜索，即适用于参考帧是相邻视点的情况。而钻石搜索是比较适合普通帧间运动搜索，即适用于参考帧是该视点的情况。因此，可以动态根据参考帧是该视点的还是相邻视点的来选择采用钻石搜索还是光栅搜索，即根据视点标号ViewId来分别判断参考帧是帧间的还是视点间的。如果参考帧是视点间的，如果参考帧是视点间的，可以采用比较细的光栅搜索和比较粗的钻石搜索。另外，由于光栅搜索很费时，如果参考帧是帧间的，可以不采用光栅搜索而采用比较细的钻石搜索。在细化阶段，最佳匹配点就在当前点附近，因此没必要进行大步长的钻石搜索，只需进行步长为1、2、4、8的钻石搜索。这里实验只对左右视点进行测试，左视点的视点标号为0，右视点的视点标号为1，且右视点参考左视点。

表2 TZS1、TZS2、TZS3分别与TZS的编码时间比较

2.4 TZSearch算法改进方法二

在 TZSearch算法改进方法一的基础上，进一步提出改进方法二以再度减少编码处理时间。其基本思想是：在统计好的TZSearch阈值分布使用规律的基础上，即TZS2方法比较适合运动比较平缓的序列和TZS3方法比较适合运动比较剧烈的序列的一般规律，针对序列运动的剧烈和缓慢情况，TZSearch算法改进方法一分别与TZS2、TZS3方法结合起来，以达到进一步优化的目的。New1、New2分别是 TZSearch算法改进方法一、二。部分实验测试结果见表3、表4。

表3 New2、New1分别与TZS的编码时间比较

表4 量化参数QP=32时几种算法的比较

3 实验说明和性能评价

3.1 实验说明

①PC机配置及操作环境∶ Microsoft XP系统；JMVC4.0；

②量化参数QP分别选取32、37及42，搜索范围为64，GOP大小为8。参考帧为2。平均峰值信噪比PSNR=(Ypsnr×4+Upsnr+Vpsnr)/6采用公式计算得到。其中Ypsnr、Upsnr、Vpsnr分别表示Y、U、V分量的峰值信噪比；

③实验测试视点数目为 2，即左右两个视点。其中，左视点为主视点，由于只有运动估计，没有视差估计，实验数据不做统计，采用 TZSearch算法进行编码。右视点参考左视点，采用联合运动估计和视差估计的编码方法，分别采用TZSearch算法与优化算法进行测试实验，得到实验数据。所有的实验数据均来自右采用水平相机阵列视点；

④实验测试序列∶ ballroom(640×480)、exit(640×480)、soccer(720×480)、puppy(720×480)、race1(320×240)[6-8]，其中前四个序列各编码88帧，对KDDI提供的race1序列编码200帧，ballroom和puppy序列属于运动比较缓慢的序列，exit、soccer和race1属于运动比较剧烈的序列。

3.2 性能评价

New1与 TZSearch算法（TZS）相比，在编码时间上有30%左右的减少量，除了puppy和exit序列的编码时间减少量少点，大概在15%左右。而这些实验序列的总体PSNR下降非常小，码率增加不超过2%。另外，New2比TZS在编码时间上有 30%～60%的减少量，（除 exit序列）其它序列基本都有45%～50%左右的编码时间减少量。而这些实验序列的总体PSNR下降均未超过0.1 dB，码率增加不超过2%。综上，New2有50%左右的编码时间减少量，而New1只有30%左右编码时间减少量，两者的失真代价都比较少。

4 结语

在宏块最优匹配点分布特点研究的基础上设置合理的阈值，对多种不同特性序列进行的测试表明提出的改进方法二是最优方法，在 PNSR值减少很少、比特率增加很少的前提下有效地减少了编码时间。但这两种方法都只适用于平行相机配置的视频序列，针对汇聚型的摄像机阵列的效果还有待还进一步的改进和优化，以及编码效率也还有很大的空间。

[1] MPEG Video Subgroup.Introduction to Multi-view VideoCoding[C].USA:[s.n.],2008:12-15.

[2] 毕厚杰.新一代视频压缩编码标准一H.264／AVC[M].北京：人民邮电出版社.

[3] 李白萍, 陈方飞.H.264中一种新型算法的研究[J].通信技术,2009,42(12):159-160,163.

[4] 田华娟.H.264中快速多参考帧选择算法研究[J].通信技术,2009,42(05):92-94.

[5] JMVC software model Version 4.0.2009.Tobias Hinz and Karsten Suehring[S].

[6] TANG X.MERL Has Provided the Ballroom, Exit and Vassar Sequences which Can be Downloaded[EB/OL].(2010-07-22)[2010-08-22] http://ftp.merl.com/pub/avetro/mvc-testseq.

[7] 林志鹏,罗琳.基于双目视觉的立体视频压缩关键技术研究[D].南京:东南大学, 2009:18-19.

[8] VETRO A, PANDIT P.Common Test Conditions for Multiview Video Coding[C].USA:[s.n.],2006.