快速Walsh變換與多視角視頻編碼

于　洋，崔新宇，桑愛軍，陳綿書，陳賀新，李曉妮

(吉林大學 通信工程學院，吉林 長春 130022)

?

快速Walsh變換與多視角視頻編碼

于洋，崔新宇，桑愛軍*，陳綿書，陳賀新，李曉妮

(吉林大學 通信工程學院，吉林 長春 130022)

本文針對多視角視頻編碼提出了一種新的編碼方法。在此方法中，結合四維 Walsh 操作算子，以達到壓縮目的。利用4維n階矩陣Walsh變換，對先前彩色視頻流的編碼加以擴展，將其應用到八個視角的視頻編碼中，包括視頻序列分塊，Walsh正變換及反變換，反分塊。這種方法能夠利用視頻序列之間的相關性并且減少視頻序列之間的冗余。本文以VC++6.0為工具，編程實現了基于快速Walsh變換的多視角視頻編碼，研究了不同壓縮比條件下的壓縮性能。通過對實驗數據的分析，本文提出的方法既保證了視頻質量又具有很好的快速壓縮性能。實驗結果表明：本文方法具有可行性及有效性，且易于在編碼端快速實現，為多視角視頻的進一步研究奠定了基礎。

多視角視頻編碼；快速Walsh變換；多維矢量矩陣理論

1　引　言

隨著信息科學技術的飛速發展，人們對多媒體系統的要求也隨之提高，從原來的2維平面場景發展到任意視角的場景，因此多視角視頻的研究成為發展趨勢。

2維平面場景是由放置在固定位置的攝像機對一幅場景拍攝得到的。目前流行的3D電影則是由放置在2個不同位置的攝像機在同一時間對一幅場景拍攝得到的。多視角視頻是由在同一時間放置在不同角度的一系列攝像機對同一場景拍攝得到的視頻序列，能生動準確的表現場景，在各種多媒體應用中十分有效，例如身臨其境的電視會議、3D電視、自由視角電視等[1-5]。然而，各個視角之間有很強的相關性，數據量非常龐大，且包含了很多冗余信息。在實際應用中，必須對多視角視頻進行壓縮編碼，否則其存儲和傳輸都將非常困難。如何在有限的傳輸帶寬條件限制下，對含有巨大信息量的多視角視頻進行壓縮編碼是亟待解決的問題。目前研究多視角視頻的方法多數是基于MPEG-4或H.264結合運動補償預測(Motion Compensated Prediction,MCP)和差值補償預測(Disparity Compensated Prediction,DCP)的方法。他們均是單通道的視頻編碼，在多視角視頻編碼中，一個是主通道，另一個是輔通道。這種方法能處理2個視角的多視角視頻，但當處理更多視角時具有一定局限性。雖然MPEG-4和H.264是非常高效的編碼方法，但他們計算復雜度高，不能實時實現。一些快速算法利用宏塊(MB)模式的RD特性還有編碼信息的相關性來減少模式判斷的復雜性。還有一些算法利用運動矢量的相關性、視差矢量的特性、運動矢量和視差矢量之間的幾何關系來減少運動估計和視差估計的復雜度。以上算法雖能有效降低復雜度，但多視角視頻編碼的整體復雜度仍然巨大。除此之外，盡管一些算法已經考慮到量化參數變化的影響，但計算性能的穩定性和RD性能仍然有待提高[6-10]。

Walsh變換廣泛應用于數字水印、圖像加密、人臉識別、視頻序列的壓縮編碼中。它既保證了重建視頻質量，也使視頻壓縮速度得到提高，可以應用在實時視頻的場合，而且是一些編碼標準的主要變換方法。Walsh函數有以下特點[11-12]：

(1)Walsh函數構成簡單，只由+1和-1構成。

(2)Walsh函數是完備正交的函數。

(3)Walsh函數可將乘法運算轉換為實數加減法運算，減少計算復雜度，提高運算速度。

(4)隨著階數n的增大，在規定區間內+1與-1交替的次數也增多，這種特性稱為序率遞增特性，類似于頻率遞增特性。

因此，要提高多視角視頻編碼的效率，選擇Walsh變換是一種較為有效的方法。本文以Walsh變換為基礎，提出了一種針對多視角視頻的編碼方案。它能快速實現，并能得到較好的壓縮效果和初步的壓縮比。

2　離散Walsh變換及正交變換

(1)多維矢量矩陣理論

定義2-1：數域W上的M×N數據排成的M行N列數表(ai1i2)M×N稱為二維矩陣，記為AM×N。W上的數表(ai1i2…in)I1×I2×…×In稱為多維矩陣，記做AI1×I2×…×In。

定義2-2：如果將多維矩陣的維數劃分成兩組，且分別用2個矢量表示，如將AI1×I2×…×In表示為A( I1×I2×…×Im)×(J1×J2…Jn)，其中m+n=r，記做AIJ，其中I，J為矢量，I=(I1×I2×…×In)，J=(J1×J2×…×Jn)，則稱多維矩陣M為按照矢量I，J劃分的多維矢量矩陣，簡稱多維矢量矩陣。顯然，一個多維矩陣可以對應多個多維矢量矩陣，而一個多維矢量矩陣只對應唯一的一個多維矩陣。

(2)多維矢量矩陣乘法及克羅內克乘積

如果兩個多維矢量矩陣AIJ和BUV，其中I=(I1×I2×…×In)，J=(J1×J2×…×Jn)，U=(U1×U2×…×Up)，V=(V1×V2×…×Vq)，且J=U，則稱AIJ和BUV具有可乘性。

(3)克羅內克乘積

設多維矩陣AI1×I2×…×In=(ai1i2…im)I1×I2…Im，BJ1×J2×…×Jm=(gj1j2…jm)J1×J2…Jm，都是m維矩陣，則多維A與B的克羅內克乘積如下：

(1)

克羅內克乘積也成為直積或張量積。顯然A?B仍是m階矩陣。一般A?B≠B?A，即克羅內克乘積不滿足矩陣乘法交換律[13]。

(4)一維Walsh變換

設N=2n，則離散f(x)(x=0,1,2…N-1)的Walsh變換為:

(2)

不同的序對應著不同的Walsh變換，其中最常用的是Walsh序。因此，本文中所有變換均是Walsh序的Walsh變換。

(5)二維Walsh變換

(3)

其中，變換核為:

(4)

根據Walsh變換核的可分離性，二維離散Walsh變換可分解為由兩個一維離散Walsh變換所組成的形式，即:

(5)

(6)四維Walsh變換

(6)

其中，變換核為:

(7)

(7)四維n階矩陣正交變換

四維n階矩陣：對于任意4維矩陣，若I=J=S=T,即AI×J×S×T=(aijst)n×n×n×n，則可稱為四維n

階矩陣并表示為AⅣ,n=(aijst)Ⅳ,n。顯然，四維n階矩陣就是四維n階方陣[14-15]。

當n=2時，有

由于Walsh變換中變換矩陣簡單(只含+1和-1)，占用存儲空間少，產生容易，運算過程中只涉及到實數加減法運算，在需要實時處理大量數據的圖像處理問題中廣泛應用[16]。

3　基于快速Walsh變換的多視角編碼的研究

3.1分塊

本文中多視角視頻編碼、解碼方案如圖1。

圖1　多視角視頻編碼、解碼方案 Fig.1　Multi-view video coding and decoding scheme

設K幀尺寸為I×J的視頻序列，結合視頻序列的特點，給出如下四維矩陣表示：

其中1≤i≤I，1≤j≤J表示視頻中像素的空間位置,1≤k≤K表示視頻的幀數(本文中取K=8)，1≤l≤3表示彩色視頻的3個顏色算法[17]。

對于視頻序列，常見的分塊方式有：4×4、8×8、混合、六邊形等多種分塊方式，本文選取較為常用的8×8、16×16分塊方式[18-19]。將實驗用YUV視頻中Y幀、U幀、V幀分別以8×8、16×16大小進行分塊，將得到的分塊按幀的順序排列好，本實驗中通過隔幀采樣只取前8幀。對8個視角做相同的處理，圖2給出了一個視角的分塊方法。

圖2　一個視角的分塊 Fig.2　Sub-blocking from one of eight views

3.2Walsh變換

(8)

本文中所用的四維8階Walsh操作算子WⅣ,8可由克羅內克乘積得到，即

(9)

(10)

四維2階操作算子WⅣ,3為：

16×16分塊及Walsh變換與8×8過程類似。解碼過程是全部編碼過程的逆過程，整個編解碼過程已在第一小節給出。

4　實驗結果及分析

本文中選取的是4∶2∶0的8個視角的.yuv(352×288)格式的多視角視頻序列，通過隔幀采樣取前8幀，分別將每個視角的數據進行8×8、16×16的分塊，進行快速Walsh正變換和反變換，對變換系數矩陣取不同大小，得到不同的壓縮比CR，本文中取CR=4及CR=8，最后進行反變換、反分塊，得到經過處理后的多視角視頻序列。在RGB格式下以變換后的峰值信噪比PSNR及壓縮比CR為實驗數據作為評價標準，并給出了第一、第八視角原始多視角視頻與部分重建第一、第八視角多視角視頻的對比。

表1為Walsh變換獲得的不同分塊方式對應的CR及PSNR。表2為DCT變換獲得的不同分塊方式對應的CR及PSNR。從表中數據可以看到，8×8的分塊實驗數據要優于16×16的分塊實驗數據。在相應分塊下壓縮比提高了一倍時，信噪比下降很少。在相同CR情況下，PSNR值越

大，表明壓縮算法的效果越好。因此，可以針對不同的要求選取不同的分塊方式及不同的壓縮比，以達到理想的效果。通過與DCT變換的數據對比發現，本文所提出方法性能上與DCT變換相近。

表1　Walsh變換下不同分塊方式的CR及PSNRTab.1　CR and PSNR corresponding todifferent blockings in Walsh Transform

表2　DCT變換下不同分塊方式的CR及PSNRTab.2　CR and PSNR corresponding todifferent blockings in DCT Transform

表3為本文方法所用時間。從時間可以看出，本文方法在保證壓縮編碼性能及視頻質量前提下，所用時間較短，具有較快速的特點；在性能與DCT性能相近的前提下速度較快，具有一定的優越性，適合用于實時場合。

表3　本文方法所用時間(ms)Tab.3　Time consumed in this method(ms)

圖3為原始多視角視頻，圖4為8×8分塊CR=8時的重建多視角視頻，圖5為16×16分塊CR=16時的重建多視角視頻。從圖3、圖4及圖5可以明顯看出，使用本文方法獲得的重建多視角視頻的視頻質量清晰且與原始多視角視頻幾乎看不出差別，滿足了對視頻質量的要求同時還獲得了較好的CR及PSNR。

本文所用方法結合多維矢量矩陣理論，利用Walsh變換核的可分離性，可將四維Walsh變換降維處理，分解成4個一維Walsh變換，減少復雜度，提高運算效率。

圖3　原始多視角視頻 Fig.3　Original multi-view video

圖4　8×8分塊CR=8時的重建多視角視頻 Fig.4　Reconstructed multi-view video of 8×8 blocking when CR is 8

圖5　16×16分塊CR=16時的重建多視角視頻 Fig.5　Reconstructed multi-view video of 16×16 blocking when CR is 16

5　結　論

在信息技術飛速發展的今天，圖像通信的數

字化已成為多媒體技術領域中的重要組成部分。多視角視頻已成為當前多媒體通信研究領域中的研究熱點。

本文在多維矢量矩陣理論的基礎上，利用四維n階Walsh變換對多視角視頻進行編碼。創新點在于對變換后的系數矩陣取不同大小，得到不同的壓縮比，然后對取不同大小的系數矩陣進行反變換和反分塊，得到重建多視角視頻。考慮到視頻序列之間的相關性，利用多維矢量矩陣模型，本文方法很好地去掉了視頻序列之間的相關性，消除了冗余，達到了視頻壓縮的目的，且重建多視角視頻與原始多視角視頻幾乎看不出差別，驗證了其可行性。本方法在較好的壓縮質量下，得到可接受的壓縮比。其算法只有實數的加減法運算，易于在攝像頭內硬件實現。

[1]桑愛軍,穆森,王墨林,等.基于多維矢量矩陣的多視角視頻編碼[J].吉林大學學報(工學版),2013，43(4):1110-1115.

SANGAJ,MUS,WANGML,et al..Multi-viewvideocodingbasedonmulti-dimensionalvectormatrix[J]. J. Jilin University(EngineeringandTechnology),2013,43(4):1110-1115.(inChinese)

[2]YANGY,DAIQH,JIANGGYX,et al..Comparativeinteractivityanalysisinmulti-viewvideocodingschemes[J]. ETRI Journal,2010,32(4).

[3]JUNGJJ,HOYS.Colorcorrectionalgorithmbasedoncameracharacteristicsformulti-viewvideocoding[J]. Signal,Image and Video Processing,2014,8(5):955-966.

[4]張寶龍,李丹,王靖云,等.基于OV9712的串行器解串器視頻編碼方案[J].液晶與顯示,2015,30(6):965-971.

ZHANGBL,LID,WANGJY,et al..ExploringtheprogramofvideocodingbasedontheOV9712SER/DES[J]. Chinese J. Liquid Crystals and Displays,2015,30(6):965-971.(inChinese)

[5]程雪岷,談夢澤,郝群,等.自由立體顯示效果測試綜述[J].液晶與顯示,2014,29(5):830-838.

CHENGXM,TANMZ,HAOQ,et al..Surveyonauto-stereoscopicdisplaymeasuringsystem[J]. Chinese J. Liquid Crystals and Displays,2014,29(5):830-838.(inChinese)

[6]鄒虹，曾鑫，溫鑫.基于兩視點視頻融合技術的裸眼3D顯示的研究[J].液晶與顯示，2014,29(5):824-829.

ZOUH,ZENGX,WENX.Glasses-free3Ddisplaybasedontwo-viewvideosynthesizetechnology[J]. Chinese J. Liquid Crystals and Displays,2014,29(5):824-829.(inChinese)

[7]王曉燕，王世剛，姜秀紅，等.亮度優化立體視頻視覺舒適度評價[J].中國光學，2015,8(3):394-400.

WANGXY,WANGSHG,JIANGXH,et al..Evaluationofstereovideovisualcomfortbasedonluminanceoptimization[J]. Chinese Optics,2015,8(3):394-400.(inChinese)

[8]蔣剛毅，廖義，郁梅，等.基于雙目視覺特性的立體視頻編碼碼率控制算法[J].光學 精密工程，2014,22(2):451-458.

JIANGGY,LIAOY,YUM,et al..Ratecontrolalgorithmforstereoscopicvideocodingbasedonbinocularviusualcharacteristics[J]. Opt. Precision Eng.,2014,22(2):451-458.(inChinese)

[9]王瓊華,鄧歡.集成成像3D拍攝與顯示方法[J].液晶與顯示,2014,29(2):153-158.

WANGQH,DENGH. 3Dpickupanddisplaymethodofintegralimaging[J]. Chinese J. Liquid Crystals and Displays,2014,29(2):153-158.(inChinese)

[10]王嘉輝,鄧玉桃,蘇劍邦,等.全高清裸眼3D顯示效果的評價與測量[J].液晶與顯示,2013,28(5):805-809.

WANGJH,DENGYT,SUJB,et al..Evaluationandmeasurementofdisplayeffectinfullhighresolutionautostereoscopicdisplay[J]. Chinese J. Liquid Crystals and Displays,2013,28(5):805-809.(inChinese)

[11]OUYWL,CHWK.FastalgorithmforWalshHadamardtransformonslidingwindows[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(1):165-171.

[12]PARKCS.RecursivealgorithmforslidingWalshHadamardtransform[J]. IEEE Transactions on Signal Processing,2014,62(11):2827-2836.

[13]龍清.圖像壓縮編碼中Walsh變換與DCT變換及其比較[J].現代電子技術,2011，34(10):12-16,

LONGQ.WalshtransformandDCTtransforminimagecompressioncoding[J]. Modern Electronics Technique,2011,34(1):12-16.(inChinese)

[14]ANADA,PASCALF,FERNANDOP.OptimizedMVCpredictionstructureforinteractivemulti-viewvideostreaming[J]. IEEE Signal Processing Letters,2014,20(6):603-606.

[15]CANB,TRUONGQN.Multi-viewvideoplusdepthcodingwithdepth-basedpredictionmode[J]. IEEE Transactions on Circuit and System for Video Technology,2014,24(6):995-1005.

[16]LIP,WANGYR,LVHL,et al..Walshtransformintransientechorecognition[J]. Advanced Materials Research,2013,694:2865-2869.

[17]桑愛軍，孫敏，陳綿書，等.多維矢量矩陣變換域的運動矢量估計[J].中國光學，2015,8(2):191-197.

SANGAJ,SUNM,CHENMSH,et al..Motionvectorestimationinmulti-dimensionalvectormatrixtransformdomain[J]. Chinese Optics,2015,8(2):191-197.(inChinese)

[18]LIY,CHENHX,SANGAJ,et al..Four-dimensionalmatrixWalshtransformforlosslesscompressionofcolorvideo[J]. The J. China University of Posts and Telecommunication,2010,17(3):123-128.

[19]ZHUW,ZHENGYY,CHENP,et al..Fastmacroblockencodingalgorithmbasedonrate-distortionactivityformulti-viewvideocoding[J]. Signal Processing:Image Communication,2014,29:1063-1078.

Fast Walsh transform and multi-view video coding

YU Yang, CUI Xin-yu, SANG Ai-jun*, CHEN Mian-shu, CHEN He-xin, LI Xiao-ni

(CollegeofCommunicationEngineering,JilinUniversity,Changchun130022,China)

,E-mail:sangaj@jlu.edu.cn

A fast coding method for multi-view video coding has been put forward in this paper. In this method, in order to compress the data, we combined four dimension Walsh operation. Combined with 4D n-order matrix Walsh transform, a series of coding schemes on colorful video stream proposed in previous studies was expanded and applied in eight-view video coding. The coding method includes video sub-blocking, Walsh transform and inverse transform, inverse sub-blocking, which can take advantage of the correlation of the video sequence and reduce the redundancy of the video sequence. We achieved the goal of multi-view video programming based on fast Walsh transform in VC++6.0 environment, and studied the compression performance in different compression conditions. Experiment data shows that the video quality can be guaranteed and the CR and PSNR is good. With good feasibility and effectiveness, this method is easy to achieve in the encoding side and lays a foundation for further study of multi-view video coding.

multi-view coding;fast walsh transform;multi-dimensional vector matrix theory

2015-11-11；

2016-01-12

吉林省自然科學基金資助項目 (No.20130101045JC)；吉林省科技發展計劃國際科技合作資助項目(No.20130413053GH，No.20140414013GH)；國家自然科學基金資助項目 (No.61171078)；吉林省青年科學基金資助項目(No.20130522164JH)

2095-1531(2016)02-0234-07

TP919.81

A

10.3788/CO.20160902.0234

于洋(1990—),男,吉林梅河口人,碩士研究生,2012年于長春大學獲得學士學位,主要從事視頻圖像壓縮編碼制方面的研究。E-mail:yy13@mails.jlu.edu.cn

桑愛軍(1973—),女,山東萊州人,博士,教授,碩士研究生導師,1994年于華中理工大學獲得學士學位,1997年于大連理工大學獲得碩士學位,2002年于吉林大學獲得博士學位,主要從事視頻圖像壓縮編碼方面的研究。E-mail:sangaj@jlu.edu.cn

Supported by Jilin Provincial Natural Science Foundation of China(No.20130101045JC), Jilin Provincial Project of International S&T Cooperation and Exchange of China(No.20130413053GH，No.20140414013GH)， National Natural Science Foundation of China(No.61171078), Jilin Provincial Natural Science Young Foundation of China(No.20130522164JH)