基于冗余小波ＤＴ網格技術的單通道視頻編碼

（1.天津大學 電氣與自動化工程學院， 天津 300072；2.河北工業大學 計算機科學與軟件學院， 天津 300130）

摘要：提出了一種新型的基于冗余小波DT(Delaunay triangle)網格技術的單通道視頻編碼算法，該算法通過冗余小波變換提取視頻流中的運動信息，結合DT和仿射變換算法對單通道視頻流進行壓縮。實驗結果表明，該算法在提高PSNR值的基礎上減少了編碼系統的復雜度，具有一定的應用價值。

關鍵詞：視頻編碼；冗余小波；Delaunay三角網格

中圖分類號：TN9198文獻標志碼：A

文章編號：1001-3695(2008)11-3493-03



Single-channel video coding based on redundant wavelet and DT grid



GAO Tao1，LIU Zheng-guang1，YU Ming2

（1. College of Electrical Engineering Automation， Tianjin University，Tianjin 300072， China；2.College of Computer Science Engineering， Hebei University of Technology， Tianjin 300130， China)

Abstract:This paper proposed a single-channel video coding method based on redundant wavelet and DT(Delaunay triangle) grid.The algorithm extracted the features and potential motion areas in the redundant wavelet transform domain， and then did the motion estimation in the time-domain. Experimental results show that the algorithm can increase the PSNR value and reduce the complexity. It has a certain practical value.

Key words:video coding; redundant wavelet; DT grid



利用人的視覺獲取的信息稱為視頻信息，視頻信息的表現形式是視頻信號。一般而言，視頻信號的信息量大，傳輸網絡所需的帶寬相對較寬。例如一路高清新電視信號，由于其信息量巨大，不壓縮需1 Gbps。可見，視頻信息雖然具有直觀性、確定性等優越特點，但要傳輸包含視頻信息的信號卻需要較高的網絡帶寬，所以視頻信號在傳輸前要先進行壓縮編碼，然后再在網絡上進行傳輸。

目前，視頻編碼的方式一般分為基于波形的編碼和基于內容的編碼^[1]。基于波形的編碼采用了將預測編碼與變換編碼組合起來的基于塊的混合編碼方法。為了減少編碼的復雜性，使視頻編碼的操作易于執行，在采用混合編碼方法時，首先將一幅圖像分成固定大小的塊，然后對塊進行壓縮編碼處理。基于內容的編碼首先將視頻幀分成對應于不同物體的區域，然后分別對其進行編碼。具體來說，即對不同物體的形狀﹑運動和紋理進行編碼。在最簡單的情況下，利用二維輪廓描述物體的形狀，利用運動矢量描述其運動狀態，而紋理則用顏色的波形進行描述。

針對基于內容和基于波形編碼各自的特點，本文提出一種以冗余小波變換為基礎，結合DT網格技術對單通道視頻流進行壓縮的視頻壓縮新算法。

1視頻壓縮關鍵技術——運動估計

在視頻壓縮算法中，運動估計是非常重要的一部分，也是視頻壓縮過程中耗時最長的一部分，約占整個壓縮過程運行時間的50%^[2]。所以在保證估計的準確度基礎上減少運動估計運行時間成為視頻壓縮的研究熱點之一。

目前運動估計通常采用的搜索算法有全搜索算法、二維對數算法、“鉆石”搜索算法。全搜索算法一定能夠找到最優的匹配塊，但是計算復雜度很高，硬件實現全搜索算法非常困難。二維對數和“鉆石”搜索算法能夠有效減少計算的復雜度，但是搜索到的結果可能是局部最優點，而不是全局最優點。這些算法都在時域進行，而在小波變換域進行運動估計則引起了人們的關注。

文獻[3，4]提出了冗余小波變換域運動估計方法，對于搜索窗內的一個向量，計算所有尺度下所有子帶的絕對差，然后全部相加，結果稱為交叉子帶或交叉尺度形變。使交叉子帶形變最小的矢量作為當前點的運動矢量（Δx，Δy）：

(Δx，Δy)=arg min-W≤Δx，Δy≤WMAE(x-B/2，y-B/2，Δx，Δy）

其中MAE(x，y，Δx，Δy)=（1/B2）Bk=1

Bl=1AE(x+k，y+l，Δx，Δy)

絕對差（AE）為

AE(x，y，Δx，Δy)=Jj=12-j{|Vcj(x+Δx，y+Δy)-Vrj(x，y)|+|Hcj(x+Δx，y+Δy)-Hrj(x，y)|+|Dcj(x+Δx，y+Δy)-Drj(x，y)|}+2-J|Bcj(x+Δx，y+Δy)-Brj(x，y)|

其中：c、r分別代表當前子帶和參考子帶；Bj、Hj、Vj和Dj分別代表j尺度下近似子帶分量、水平子帶分量、垂直子帶分量和對角線子帶分量。搜索過程中，運動矢量大小在搜索窗范圍內，N大小不固定。該算法利用小波變換的空間方向性提高搜索精度，但是運算復雜度大、精度不穩定。文獻[5]提出的EMRMC方法是規則網格運動估計方法，該方法利用運動圖像極大的空間冗余性，通過提取潛在運動區（PMA）有效地縮小了搜索區域，提高了效率。但是，由于各分解子帶大小不等，需要采用逐層擴散的方法得到潛在運動區，運算量也比較大。

通過以上分析，本文提出了一種冗余小波變換域提取特征點和潛在運動區域，利用冗余小波變換各子帶等大小的性質，并結合時域搜索方法進行運動估計，在給運算過程帶來很大方便的同時提高了編碼的質量。首先通過小波變換的方法提取特征點^[3]，得到Delaunay三角形網格；再根據本文的算法在冗余小波變換域提取PMA，并考慮參考幀內N×N鄰域的搜索區，只對落在兩區域的點進行運動估計。由于運動發生的局部性和連貫性以及小波變換的方向選擇性，使得潛在運動區域在高頻子帶通常只占整個圖像的很小部分，本算法只在很小的搜索區對有效的網格頂點進行運動估計，從而提高了運行效率。

11冗余小波變換理論基礎

設MRA由滿足如下條件的嵌套線性空間…V-1V0V1…組成：

a)嵌套空間的并集在平方可積函數空間中稠密。

b)嵌套空間的交集只包含零向量。

c)如果f(t)Vk，那么f(2t)Vk-1；反之亦然。

d)存在函數(即尺度函數)(t)，使得{(t-k):k int}是V0的基，而(t)被定義為滿足下列條件的函數：

（a）∫+∞-∞(t)dt=1；

(b）‖(t)‖2=∫+∞-∞|(t)|2dt=1；

(c）〈(t)，(t-n)〉=δ(n)。

則存在c(n)，n=0，±1，±2，…，使得(2-kt)=∞n=-∞c(n)(2-(k-1)t-n)，說明VkVk-1，即構成了一個MRA。形象地說，所有子空間的并集（V-∞）在L2（R）中稠密，說明V-∞能夠逼近任意信號f(t)|∈L2|(R)。若令fk(t)為f(t)在子空間Vk上的正交投影，有fk(t)=∞-∞a(k，m)(2-(k-1)t-n)，k=0，±1，±2，…，則可以得到a(k，n)=∞-∞a(k-1，m)c(m-2n)/2。假設ψ(t)是V-1中的函數，且滿足：∫∞-∞ψ(t)dt=0；∫∞-∞|ψ(t)|2dt=1；〈ψ(t)，ψ(t-n)〉=δ(n)；〈ψ(t)，(t-n)〉=0。則ψ(t)就是與上述MRA對應的DWT需要的小波。令W0是以{ψ(t-n):n int}為基的線性向量空間，則Vk-1=Wjj=k，那么V-∞=∞j=-∞Wj，于是f-∞(t)=∞k=-∞∞t=-∞b(k，l)ψ(2-kt-l)。同樣，可以導出b(k，n)=∞-∞a(k-1，m)d(m-2n)/2。令，h(n)≡c(n)/2，g(n)≡d(n)/2，(n)≡h(-n)，(n)≡g(-n)，則a(k，n)=∞-∞a(k-1，m)(2n-m)，b(k，n)=∞-∞a(k-1，m)(2n-m)。可以看做a(k，n)、b(k，n)是由a(k-1，m)經過濾波器濾波后抽樣得到的。如果從頻率域考慮，令H(ω)=nh(n)e-jωn，則有|H(ω)|2+|H(ω+π)|2=1，即H是一個正交鏡像濾波器(QMF)。通過多分辨率分析可以將小波的求解轉換為對數字濾波器的設計問題^[6，7]。

如果二維信號x(n，m)(n=1，2，…，N;m=1，2，…，N)進行二維冗余離散小波變換后的低頻分量、水平細節分量、垂直細節分量、對角細節分量分別為Aj(x，y)、Hj(x，y)、Vj(x，y)和Dj(x，y)，小波濾波器組的分析濾波器和合成濾波器分別為{h(k)，g(k)}和{(k)，(k)}，則二維信號分解過程為

Aj(x，y)=Aj-1(x，y)([h]↑2j-1，[h]↑2j-1)(-x，-y);

Hj(x，y)=Hj-1(x，y)([h]↑2j-1，[g]↑2j-1)(-x，-y);

Vj(x，y)=Vj-1(x，y)([g]↑2j-1，[h]↑2j-1)(-x，-y);

Dj(x，y)=Dj-1(x，y)([g]↑2j-1，[g]↑2j-1)(-x，-y)。

12基于冗余小波變換的運動估計

121冗余小波變換產生網格頂點

信號的奇異點在小波變換下，隨著尺度的增大而增大，相鄰尺度的小波系數直接乘可以增強信號的特征點。冗余小波具有平移不變性，各子帶圖像大小等尺寸相同，便于計算。因此算法采用相鄰尺度子帶系數相乘后求和的方法得到模板，計算所有像素點的模板值，如果大于閾值即確定該點為特征點。這樣整個圖像的特征點就確定下來，從而生成一個基于圖像內容的Delaunay三角形網格。模板如下：

mask(x，y)=|J1j=J0HL(j)(x，y)|+

|J1j=J0LH(j)(x，y)|+|J1j=J0HH(j)(x，y)|

其中：J0和J1代表開始和結束的尺度。因為冗余小波各子帶的大小相同，可以直接作算術運算。閾值T的提取操作可描述為將mask(x，y)歸一化后轉換為256級灰度圖像mask，通過迭代法自動確定閾值。大概步驟如下：首先取圖像灰度范圍的中值作為初始閾值T0（設共有L個灰度），然后按下式進行迭代：

Ti+1=1/2Tik=0hk×k/

Tik=0hk+L-1k=Ti+1hi×k/L-1k=Ti+1hk

其中：hk是灰度為k值的像素個數，迭代一直到Ti+1=Ti結束，取結束時的Ti為分割閾值。

圖1是通過冗余小波變換對Akiyo和mother序列一幀圖像進行特征點提取形成的Delaunay三角形網格。

122 結合PMA和網格頂點的運動估計

通過冗余小波變換提取特征點給后續的運動估計帶來了方便和更高的效率。結合冗余小波變換的各子帶系數高度相關、方向選擇性、各子帶與輸入信號大小相等以及平移不變的性質，提出了在冗余小波變換域進行的PMA模板提取，并結合時域方法的運動估計和補償。模板由多子帶組成，包括近似子帶（LL）、低—高子帶（LH）、高—低子帶（HL）、高—高子帶（HH）。提取的PMA模板如下：

mask(x，y)=J1j=J0|LL(j)C(x，y)-LL(j)R(x，y)|+|LH(j)C(x，y)-LH(j)R(x，y)|+|HL(j)C(x，y)-HL(j)R(x，y)|+|HH(j)C(x，y)-HH(j)R(x，y)|

PMA(x，y)=1mask(x，y)≥Γ0

0mask(x，y)＜Γ0

其中:J0和J1代表開始和結束的尺度。因為冗余小波各子帶的大小相同，可以直接作算術運算。XC、XR分別代表當前圖像和參考圖像，Γ0為閾值。對Akiyo和mother序列相鄰兩幀圖像進行PMA提取的結果如圖2所示。

網格頂點的運動估計是在經典的以該點為中心的宏塊運動估計方法基礎上的改進，即在當前幀以網格頂點為中心取得M×M的宏塊，然后在參考幀以該點位置為中心L×L（對于圖像邊緣的特征點的搜索，會隨著到邊界的距離而調整搜索窗）的范圍內搜索匹配宏塊，位移差即該頂點的運動矢量。本算法結合PMA，在PMA中搜索匹配宏塊，即判斷當前幀和參考幀的網格頂點是否落在PMA內。不在PMA的當前幀和參考幀的網格頂點運動矢量規定為0。值對落在PMA內的網格頂點進行運動估計。這樣做的優點在于：由于連續兩幀圖像是非常相似的，大部分區域是相同的，PMA常常分布稀疏且面積很小，運動矢量的搜索可以在局部高效完成。本文采用的最佳匹配準則為絕對幀間差和準則(SAD)^[8]。其數學表達式為

SAD(i， j)=Mm=1Nn=1|Sk(m，n)-Sk-1(m+i，n+j)|

其中:Sk(m，n)為第k幀(m，n)處的像素值；Sk-1(m+i，n+j)為k-1幀在(m+i，n+j)處的像素值。獲得三角形頂點的運動矢量后，三角形內部點的運動矢量可用六參數仿射變換求得：

Δx=α11y+α12y+α13

Δy=α21x+α22y+α23

其中:Δx、Δy分別為x和y方向的運動矢量。由上式可確定該三角形區域的六個仿射變換系數，那么三角形區域內部各點的運動矢量也可求得。

2單通道視頻編碼方案

本文提出的基于冗余小波的單通道視頻編碼方案框架如圖3所示。視頻序列第一幀作為I幀，可直接通過塊DCT變換、量化、VLC編碼形成最終碼流。后續幀可作為P幀，運動矢量由本文提出的算法得到并進行VLC編碼，當前幀與預測幀的差值編碼與I幀類似。從圖3可以看出，本文提出的算法形成的最終碼流具有兼容性，碼流可在MPEG系列和H26x系列的解碼器上解碼，無須另外設計解碼器。

3實驗結果及討論

本文對兩個標準測試圖像序列Akiyo和mother進行實驗，將本文提出的方法與目前視頻壓縮算法H.264和MPEG-4進行比較。標準測試圖像均為CIF格式，運動估計采用Y-幀（亮度圖像分量），包含了彩色視頻圖像幾乎全部的運動信息。實驗采用Akiyo(352×288，15幀)和mother(352×288，15幀)；都采用第一幀作為I幀，后面幀作為P幀，根據前一幀的預測圖像來估計當前幀。重建圖像PSNR值如圖4、5所示；對于視頻圖像數據的壓縮率比較如表1所示。

表1算法壓縮率比較

視頻序列原始大小/MB本文算法/KBH.264/KBMPEG-4/KB

Akiyo sequence2.1730.922.824.8

mother sequence2.1717.610.68.29

從實驗結果可得出，本文提出的算法得到的重建圖像具有更好的主觀視覺質量，PSNR值要高于H.264、MPEG-4壓縮算法，原因在于通過提取PMA和運動特征點提高了運動估計的準確性。從表1可以看出，本文提出的算法在壓縮比方面要劣于H.264和MPEG-4算法，原因在于后續編碼只是采用簡單的VLC編碼，如果結合EZW或者SPIHT編碼，效果可能會有所提高。

4結束語

本文提出了一種基于冗余小波變換提取Delaunay三角形網格特征點，結合PMA與三角仿射變換的單通道視頻壓縮方法。經實驗結果證明，該方法能夠在降低視頻編碼復雜性的同時提高PSNR值，主觀視覺質量更好，具有一定的應用價值。今后研究重點在于提高算法的編碼效率，減少碼流的冗余度。

參考文獻：

［1］

畢厚杰.新一代視頻壓縮編碼標準——H.264/AVC[M].北京：人民郵電出版社，2005.

[2]李群迎，張曉林，劉榮科，等.基于TMS320C64x DSPs的MPEG-4實時編碼器設計與實現[J].電子技術應用，2005，31(7):43-45.

[3]CUI Su-xia，WANG Yong-hui，FOWLER J E.Mesh-based motion estimation and compensation in the wavelet domain using a redundant transform[C]//Proc of International Conference on Image Processing.Rochester:IEEE Press，2002.

[4]CUI Su-xia，WANG Yong，FOWLER J E.Motion estimation and compensation in the redundant- wavelet domain using triangle meshes[J].Signal Processing: Image Communication，2006，21(7):586-598.

[5]WEI Jie，LI Ze-nian.An enhancement to MRMC scheme in video compression[J].IEEE Trans on Circuits and Systems for Video Technology，1997，7(3):564-568.

[6]DAUBECHIES I，SWELDENS W.Factoring wavelet transforms into lifting steps[J].Journal of Fourier Analysis and Applications，1998，4(3):247-269.

[7]CALDERBANK A R，DAUBECHIES I，SWELDENS W，et al.Wavelet transforms that map integers to integers[J].Journal of Applied and Computational Harmonic Analysis，1998，5(3):332-369.

[8]尹黎明，王玲.運動估計算法及其DSP優化[J].咸寧學院學報，2005，25(3):96-98.