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

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

?

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

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

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

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

多視角視頻編碼；快速Walsh變換；多維矢量矩陣?yán)碚?/p>

1　引　言

隨著信息科學(xué)技術(shù)的飛速發(fā)展，人們對(duì)多媒體系統(tǒng)的要求也隨之提高，從原來的2維平面場(chǎng)景發(fā)展到任意視角的場(chǎng)景，因此多視角視頻的研究成為發(fā)展趨勢(shì)。

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

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

(1)Walsh函數(shù)構(gòu)成簡(jiǎn)單，只由+1和-1構(gòu)成。

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

(3)Walsh函數(shù)可將乘法運(yùn)算轉(zhuǎn)換為實(shí)數(shù)加減法運(yùn)算，減少計(jì)算復(fù)雜度，提高運(yùn)算速度。

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

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

2　離散Walsh變換及正交變換

(1)多維矢量矩陣?yán)碚?/p>

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

定義2-2：如果將多維矩陣的維數(shù)劃分成兩組，且分別用2個(gè)矢量表示，如將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劃分的多維矢量矩陣，簡(jiǎn)稱多維矢量矩陣。顯然，一個(gè)多維矩陣可以對(duì)應(yīng)多個(gè)多維矢量矩陣，而一個(gè)多維矢量矩陣只對(duì)應(yīng)唯一的一個(gè)多維矩陣。

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

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

(3)克羅內(nèi)克乘積

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

(1)

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

(4)一維Walsh變換

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

(2)

不同的序?qū)?yīng)著不同的Walsh變換，其中最常用的是Walsh序。因此，本文中所有變換均是Walsh序的Walsh變換。

(5)二維Walsh變換

(3)

其中，變換核為:

(4)

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

(5)

(6)四維Walsh變換

(6)

其中，變換核為:

(7)

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

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

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

當(dāng)n=2時(shí)，有

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

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

3.1分塊

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

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

設(shè)K幀尺寸為I×J的視頻序列，結(jié)合視頻序列的特點(diǎn)，給出如下四維矩陣表示：

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

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

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

3.2Walsh變換

(8)

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

(9)

(10)

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

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

4　實(shí)驗(yàn)結(jié)果及分析

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

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

大，表明壓縮算法的效果越好。因此，可以針對(duì)不同的要求選取不同的分塊方式及不同的壓縮比，以達(dá)到理想的效果。通過與DCT變換的數(shù)據(jù)對(duì)比發(fā)現(xiàn)，本文所提出方法性能上與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為本文方法所用時(shí)間。從時(shí)間可以看出，本文方法在保證壓縮編碼性能及視頻質(zhì)量前提下，所用時(shí)間較短，具有較快速的特點(diǎn)；在性能與DCT性能相近的前提下速度較快，具有一定的優(yōu)越性，適合用于實(shí)時(shí)場(chǎng)合。

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

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

本文所用方法結(jié)合多維矢量矩陣?yán)碚?，利用Walsh變換核的可分離性，可將四維Walsh變換降維處理，分解成4個(gè)一維Walsh變換，減少復(fù)雜度，提高運(yùn)算效率。

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

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

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

5　結(jié)　論

在信息技術(shù)飛速發(fā)展的今天，圖像通信的數(shù)

字化已成為多媒體技術(shù)領(lǐng)域中的重要組成部分。多視角視頻已成為當(dāng)前多媒體通信研究領(lǐng)域中的研究熱點(diǎn)。

本文在多維矢量矩陣?yán)碚摰幕A(chǔ)上，利用四維n階Walsh變換對(duì)多視角視頻進(jìn)行編碼。創(chuàng)新點(diǎn)在于對(duì)變換后的系數(shù)矩陣取不同大小，得到不同的壓縮比，然后對(duì)取不同大小的系數(shù)矩陣進(jìn)行反變換和反分塊，得到重建多視角視頻?？紤]到視頻序列之間的相關(guān)性，利用多維矢量矩陣模型，本文方法很好地去掉了視頻序列之間的相關(guān)性，消除了冗余，達(dá)到了視頻壓縮的目的，且重建多視角視頻與原始多視角視頻幾乎看不出差別，驗(yàn)證了其可行性。本方法在較好的壓縮質(zhì)量下，得到可接受的壓縮比。其算法只有實(shí)數(shù)的加減法運(yùn)算，易于在攝像頭內(nèi)硬件實(shí)現(xiàn)。

[1]桑愛軍,穆森,王墨林,等.基于多維矢量矩陣的多視角視頻編碼[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),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]程雪岷,談夢(mèng)澤,郝群,等.自由立體顯示效果測(cè)試綜述[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]鄒虹，曾鑫，溫鑫.基于兩視點(diǎn)視頻融合技術(shù)的裸眼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]王曉燕，王世剛，姜秀紅，等.亮度優(yōu)化立體視頻視覺舒適度評(píng)價(jià)[J].中國光學(xué)，2015,8(3):394-400.

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

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

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

[9]王瓊?cè)A,鄧歡.集成成像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顯示效果的評(píng)價(jià)與測(cè)量[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].現(xiàn)代電子技術(shù),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]桑愛軍，孫敏，陳綿書，等.多維矢量矩陣變換域的運(yùn)動(dòng)矢量估計(jì)[J].中國光學(xué)，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

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

2095-1531(2016)02-0234-07

TP919.81

A

10.3788/CO.20160902.0234

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

桑愛軍(1973—),女,山東萊州人,博士,教授,碩士研究生導(dǎo)師,1994年于華中理工大學(xué)獲得學(xué)士學(xué)位,1997年于大連理工大學(xué)獲得碩士學(xué)位,2002年于吉林大學(xué)獲得博士學(xué)位,主要從事視頻圖像壓縮編碼方面的研究。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)