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.