多视点视频编码的TZSearch算法优化
李跃1，邓联文1, 2，习业勋1，黄生祥1, 2，胡照文1，周克省1
(1. 中南大学 物理与电子学院，湖南 长沙，410083;
2. 中南大学 粉末冶金国家重点实验室，湖南 长沙，410083)
摘 要：
视频编码(MVC)中TZSearch算法的计算复杂度，通过分析相邻宏块运动矢量之间的相关性以及当前编码宏块与相邻宏块的最优率失真(RD)之间的关系，提出一种提前终止策略；并对TZSearch算法中光栅搜索范围和循环钻石搜索的最大步长进行优化。研究结果表明：在编码性能基本不变的前提下，与TZSearch算法相比，本文算法平均节约运动估计时间89.67%。
关键词：
中图分类号：TP371 文献标志码：A 文章编号：1672-7207(2014)10-3450-06
TZSearch algorithm optimization of multiview video coding
LI Yue1, DENG Lianwen1, 2, XI Yexun1, HUANG Shengxiang1, 2, HU Zhaowen1, ZHOU Kesheng1
(1. School of Physics and Electronics, Central South University, Changsha 410083, China;
2. State Key Laboratory of Powder Metallurgy, Central South University, Changsha 410083, China)
Abstract: In order to reduce the computational complexity of the TZSeach algorithm in multiview video coding (MVC), the relationship of the motion vectors in the adjacent macroblocks as well as the sum of absolute distortion in the adjacent and the current encoding macroblock was analyzed. The search range of the raster search algorithm and the maximum step of the loop diamond search were optimized. The results show that compared with the TZSearch algorithm, the proposed algorithm saves the motion estimation time by 89.67% on the average without significant influence on the encoding performance.
Key words: multiview video coding; motion estimation; TZSearch algorithm
多视点视频序列是用多个相机同时对同一个场景进行拍摄得到的，能比单个视频序列提供更丰富的视觉体验[1-2]。然而，由于多视点视频的数据量随相机数目成倍增加，导致编码运算的复杂度也成倍增加[3-5]。目前使用的多视点视频编码参考软件称为联合多视点视频编码(joint multiview video coding, JMVC)，由ISO/IEC MPEG和ITU-T VCEG联合制定[6]。MVC中既有视点内的运动估计又有视点间的视差估计，运动估计和视差估计的时间在整个编码所用时间中占很大比例。因此，多视点视频技术要想获得广泛应用，须解决运动估计和视差估计的运算复杂度问题。许多学者提出了诸多快速算法以减少运动和视差估计的计算复杂度，同时能够保持基本不变的视频质量。文献[7]提出一种基于相机几何关系的视差估计算法，能降低视差估计的复杂度，但并不能降低运动估计的复杂度。文献[8]利用相机的几何参数和视差矢量与运动矢量的关系减少运动和视差估计的搜索范围，但其中的运动和视差搜索采用相同的搜索策略而没有考虑多视点视频固有的视点间相关性，只对特定的视频序列具有较好的编码效果，不具有通用性。文献[9]和[10]提出采用运动和视差矢量的几何约束条件求出估计的运动和视差，但不适用于只进行运动估计的视点。JMVC参考软件中统一采用TZSearch算法进行运动和视差估计，文献[11]提出一种基于统计阈值的提前终止TZSearch算法，文献[12]提出一种增强TZSearch算法，通过改变搜索模式和设置搜索阈值减少搜索范围，但上述2种方法的阈值设定并不适用于所有的视频序列。本文作者采用通过分析当前宏块与相邻宏块的运动矢量相关性以及最优率失真(rate distortion, RD)之间的关系以提前终止运动搜索的策略，并根据中心偏置特性简化光栅搜索的范围[13]，自适应调整循环钻石搜索时的最大步长，可以大大减少搜索范围，在保证视频质量的情况下，有效节约运动估计时间，降低算法的复杂度。
1 MVC的TZSearch算法
用TZSearch算法进行运动和视差估计时，支持的搜索块有16×16，16×8，8×16，8×8，8×4，4×8和4×4；搜索模式包括钻石搜索和光栅搜索，算法包括以下4个步骤。
1) 起始点选择：TZSearch算法起始点的预测包括相邻宏块矢量的左值、上值、右上值、相邻宏块矢量的中值和(0, 0)位置矢量，其中最优点作为搜索的起始点。
2) 钻石搜索：以上一步的起始点为中心，充分利用中心偏置的特性，采用步长为1，2，4，8，16，32和64(如搜索范围为64)的钻石搜索，以起始点为中心进行扩展搜索。通过比较搜索点和中心点之间的RD，确定最小RD的搜索点为最优点，并作为下一步搜索的中心点。图1所示为最大步长为8的钻石搜索。值得注意的是，在选定起始点后进行钻石搜索并没有考虑视频序列中宏块的运动相似性，将会导致本身是最优点的起始点还要进行步骤2)~4)的搜索；这是本文所要解决的问题之一。
3) 光栅搜索：将步骤2)中得到的最优点距上一步中心点的距离与3比较，若小于3，则进入步骤4)。否则将进行以3个像素为步长的最大搜索范围的光栅搜索。图2所示为搜索范围为16的3个像素步长的光栅搜索。小步长的光栅搜索虽然能够在搜索窗口内找到更好的匹配点，但会大大增加搜索点数；这是本文所要解决的问题之二。
4) 循环钻石搜索：若步骤3)的最优点距起始点的距离小于3，则只对相邻两个点进行搜索。否则将上一步的最优点作为中心点重复步骤2)的钻石搜索，直到最优点出现在搜索中心点位置。其中，循环步骤2)的钻石搜索必定会与原钻石搜索有大面积的搜索范围叠加，会大大增加已搜索范围内的搜索点数，有待进一步优化；这是本文将要解决的问题三。
图1 最大步长为8的钻石网格搜索
Fig. 1 Diamond grid search for longest step of 8
图2 搜索范围为16的3个像素步长的光栅搜索
Fig. 2 Raster search with pixel step length of 3 and search range of 16
2 TZSearch算法优化
2.1 提前终止策略
针对TZSearch算法步骤2)中提出的问题一，本文根据已编码的相邻宏块运动矢量的相似性，获取当前编码宏块的运动矢量信息。图3所示为当前编码宏块(D)与相邻宏块(A，B，C)的位置关系。若A，B和C的运动矢量中所有x和y方向的矢量都相等，则用式(1)表示，判定D宏块和A，B和C宏块的运动方向相同。具有上述特征的宏块D再根据RD全小于或等于A，B和C的RD的关系提前终止搜索，可用式(2)表示。
(1)
式中：
为已编码宏块A的x方向矢量；
为已编码宏块A的y方向矢量；
为已编码宏块B的x方向矢量；
为已编码宏块B的y方向矢量；
为已编码宏块C的x方向矢量；
为已编码宏块C的y方向矢量。注意，由于编码帧的边界宏块缺少参考宏块的矢量信息，本文对边界宏块不采取提前终止策略。
≤
(2)
式中：ARD，BRD，CRD和DRD分别表示宏块A，B，C和D的RD。
图3 当前编码宏块与相邻宏块的关系
Fig. 3 Sketch map for relationship of current coded macroblock and adjacent macroblock
2.2 光栅搜索范围改进
针对TZSearch算法步骤3)中提出的问题二，本文提出改进的光栅搜索。在TZSearch算法的运动估计过程，首先预测起始点，然后以起始点为中心进行扩展搜索，充分利用中心偏置的特性。同理，在进行光栅搜索时，可以找出步骤2)中步长大于3的每个步长上钻石搜索的最优点，以这些最优点为中心进行一次步长为3的光栅搜索。TZSearch算法步骤2)中钻石搜索步长大于3时，将每个步长上的最优点进行一次步长为3的光栅搜索，如图4所示。
图4 最优点周围步长为3的光栅搜索
Fig. 4 Grating search of step 3 around optimal point
2.3 循环搜索步长的自适应
针对TZSearch算法步骤4)中提出的问题三，在步骤4)中以新的中心点循环，如图1所示的钻石搜索，直到最优点出现在中心点。根据中心偏置特性，利用自适应钻石搜索最大步长代替固定钻石搜索最大步长，自适应钻石搜索最大步长介于上一步骤中最优点所处的钻石搜索步长与相邻的下一个钻石搜索步长之间，有利于避免重复搜索已搜索过的范围，降低搜索点数。自适应钻石搜索最大步长计算过程如图5所示，其中：SR为配置文件设置的搜索窗口大小；LN为相邻最优点的下一个钻石搜索的步长；L为最优点所在的钻石搜索步长(若最优点在光栅搜索的点上，则它所处的步长为前一步得到的钻石搜索局部最优点的步长)；LM为下一次循环钻石搜索时的动态最大步长，可用下式表示。
(3)
图5 自适应钻石搜索最大步长的计算
Fig. 5 Calculation of the longest step for adaptive diamond search
3 结果和性能分析
为了验证优化算法(Proposed)的有效性，使用JMVC8.3.1进行测试分析，测试序列选用MERL提供的“Exi””、“Ballroom”、“Vassar”多视点视频序列[14]。PC机硬件配置如下：Intel(R) Pentium(R) D CPU 3.2 GHZ，8 GB内存。操作系统为：GhostXP SP3。所有测试序列的分辨率为640×480，每个序列测试8个视点，每个视点测试61帧，参考帧数为4，GOP长度设置为15，QP(quantization parameters, 量化参数)设置为22，27，32和37。
表1所示为在不同的QP比较TZSearch算法和Proposed算法的峰值信噪比(peak signal to noise ratio, RPSN)、码率(bitrate, RB)、运动估计时间(time, t)。从表1可知：Proposed算法与TZSearch算法相比，RPSN减少的最大值为0.08 dB，平均减少0.02 dB，视频序列的客观质量评价几乎没有变化，基本保持了原视频质量；RB增加最大值为3.27%，平均值为1.33%，码率增加较小，编码的码率基本不变；t减少时间在90%左右，平均减少时间为89.67%，在视频质量和码率基本不变的情况下，可以大大减少运动估计的时间，提高编码的效率。
另外，为了更合理地表示在相同BR或者相同PSNR情况下，TZSearch方法和Proposed算法的RD性能对比情况，本文采用Bjontegaard delta峰值信噪比(Bjontegaard delta peak signal-to-noise ratio, BDPSNR)和Bjontegaard delta 比特率(Bjontegaard delta bit rate, BDBR)评估TZSearch算法和Proposed算法的RD性能[15]，结果如图6所示。从图6可以看出：序列exit，ballroom，vassar的TZSearch和Proposed的RD曲线几乎重合，可以说明Proposed算法在大大减少运动估计时间的同时，其他性能与TZSearch算法的几乎一致。
表1 各序列采用TZSearch算法和Proposed算法的性能比较
Table 1 Performances comparison of sequences using TZSearch algorithms and proposed algorithm
图6 TZSearch方法和Proposed方法在不同码率下RPSN对比
Fig. 6 Comparison of RPSN for TZSearch method and proposed method with different bitrates
4 结论
1) 通过对MVC中运动估计使用的TZSearch算法复进行分析，提出了提前终止策略，利用当前编码宏块与相邻宏块的运动矢量在x和y方向上的相关性以及RD之间的关系提前终止运动搜索。
2) 根据中心偏置特性简化光栅搜索的范围，避免了搜索区域的重叠，实现了在局部最优点周围进行小范围的光栅搜索；循环钻石搜索时，根据上一步搜索得到的最优点与相邻的下一个钻石搜索步长的距离，自适应地调整循环钻石搜索时的最大步长范围，进一步减少钻石搜索范围。
3) 通过与TZSearch算法的效能对比，优化的算法在保证视频编码性能前提下，平均节约MVC的运动估计时间89.67%。
参考文献：
[1] Vetro A, Wiegand T, Sullivan G J. Overview of the stereo and multiview video coding extensions of the H.264/MPEG-4 AVC standard[J]. Proceedings of the IEEE, 2011, 99(4): 626-642.
[2] Sullivan G J. Standards-based approaches to 3D and multiview video coding[C]// SPIE Conference on Applications of Digital Image Processing XXXII. Orlando, USA, 2009: 7443-7451.
[3] Florencio D, ZHANG Cha. Multiview video compression and streaming based on predicted viewer position[C]// IEEE International Conference on Acoustics, Speech, Signal Processing (ICASSP). Taiwan, 2009: 657-660.
[4] SHEN Liquang, LIU Zhi, AN Ping, et al. Low-complexity mode decision for MVC[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2011, 21(6): 837-843.
[5] ZHANG Qiuweng, AN Ping, ZHANG Yan, et al. Low complexity multiview video plus depth coding[J]. IEEE Transactions on Consumer Electronics, 2011, 57(4): 1857-1865.
[6] ITU-T and ISO/IEC JTC 1. Advanced video coding for generic audiovisual services, ITU-T Recommendation H.264 and ISO/IEC 14496-10 (MPEG-4 AVC)[S].
[7] LU Jiangbo, CAI Hua, LOU Jianguang, et al. An epipolar geometry-based fast disparity estimation algorithm for multiview image and video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2007, 17(6): 737-750.
[8] Kim Y T, Kim J Y, Sohn K H. Fast disparity and motion estimation for multiview video coding[J]. IEEE Transactions on Consumer Electronics, 2007, 53(2): 712-719.
[9] DENG Zhipin, CHAN Yuilam, JIA Kebin, et al. Fast motion and disparity estimation with adaptive search range adjustment in stereoscopic video coding[J]. IEEE Transactions on Broadcasting, 2012, 58(1): 24-33.
[10] CUI Zhaopeng, JIANG Guang, YANG Shuai, et al. A new fast motion estimation algorithm based on the loop-epipolar constraint for multiview video coding[J]. Signal Processing Image Communication, 2012, 27(2): 172-179.
[11] TANG Xiuli, DAI Shengkui, CAI Canhui. An analysis of TZSearch algorithm in JMVC[C]// 2010 International Conference on Green Circuits and Systems (ICGCS). Shanghai, China, 2010: 516-520.
[12] Purnachand N, Alves L N, Navarro A. Improvements to TZ search motion estimation algorithm for multiview video coding [C]// 2012 19th International Conference on Systems, Signals and Image Processing. Vienna, Austria, 2012: 388-391.
[13] Vassilios C, Jan C. A center-biased adaptive search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2000, 10(3): 423-426.
[14] TANG Xiuli. MERL MVC test sequences—ballroom, exit, Vassar[EB/OL]. [2010-08-22]. http://www.merl.com/pub/avetro/ mvc-testseq/ orig-yuv.
[15] Bjontegaard G. Calculation of average PSNR difference between RD curves[C]// Proceedings of 13th ITU-T VCEG. Porto Seguro, USA, 2001: 1-4.
(编辑 杨幼平)
收稿日期：2013-10-11；修回日期：2013-12-23
基金项目(Foundation item)：湖南省自然科学基金资助项目(10JJ5049)；湖南省科技计划项目(2012SK3232，2011SK3258)；中南大学研究生创新基金资助项目(2013) (Project(10JJ5049) supported by Provincial Natural Science Foundation of Hunan; Projects(2012SK3232, 2011SK3258) supported by Provincial Science and Technology Program of Hunan; Project(2013) supported by Graduate Student Innovation Foundation of Central South University)
通信作者：邓联文(1969-)，男，湖南邵阳人，博士，教授，从事微电子技术研究；电话：13787206916； E-mail: dlw626@163.com
摘要：为了减少多视点视频编码(MVC)中TZSearch算法的计算复杂度，通过分析相邻宏块运动矢量之间的相关性以及当前编码宏块与相邻宏块的最优率失真(RD)之间的关系，提出一种提前终止策略；并对TZSearch算法中光栅搜索范围和循环钻石搜索的最大步长进行优化。研究结果表明：在编码性能基本不变的前提下，与TZSearch算法相比，本文算法平均节约运动估计时间89.67%。
