一種分形與小波混合視頻編碼算法ＦＥＺＷ

摘要：將小波變換與分形理論相結合成為一種具有可伸縮性的混合視頻編碼算法FEZW（分形—嵌入式零樹小波編碼），該算法在嵌入式零樹小波編碼的基礎上，應用分形理論進行幀間預測，不需運動估計和補償。實驗結果表明，該算法具有較好的視頻質量可伸縮性，能有效改進圖像碼率下降時視頻質量下降迅速的情況，適合于無線網絡等高差錯網絡的視頻傳輸。

關鍵詞：分形；小波變換；分形—嵌入式零樹小波編碼；視頻編碼

中圖分類號：TP312文獻標志碼：A

文章編號：1001—3695(2007)03—0292—02

0引言

分形編碼以其較高的壓縮率成功應用于圖像壓縮領域，尤其適合于含邊界（高頻成分）較多的圖像；但由于算法復雜度較高，難以應用到實時的視頻編碼上。基于小波的編碼方法算法簡單，特別是它的分級分解的特點，對可伸縮性有很好的支持；但它對高頻部分處理不好，恢復后較模糊。如果將兩者相結合就能取長補短，充分發揮兩者的優勢。

結合的方法大體可以分為兩類：①先使用分形進行圖像編碼，然后對殘差圖像使用小波編碼以提高圖像質量，這種方法會損失一定的壓縮效率；②先將圖像進行小波分解，然后在小波域上進行分形編碼[1—3]，此類方法效果較好。文獻[1]對全部小波系數進行分形壓縮，導致壓縮速度較慢；文獻[2]使用分形對小波系數進行選擇性壓縮，其他沒有使用分形壓縮的小波系數則用SPIHT(SetPartitioningIntegratedHybridTree)算法進行編碼，該方法在高碼率的情況下效果很不理想。另外，這些方法都不具備可伸縮性。本文將EZW(EmbeddedZerotreeWavelet，嵌入式零樹小波編碼)和分形相結合，提出了一種嵌入式、分形和小波混合視頻編碼算法FEZW（FractalEZW），該編碼器的輸出碼流支持可伸縮性，適于在無線網絡等高差錯的網絡中傳輸。

1FEZW算法

1.1小波分解

對每幀圖像進行小波分解。以圖1為例，圖像被分解成4級小波系數，低頻小波系數（即圖中第4級小波分解系數）采用嵌入式零樹小波編碼方法（EZW），其他高頻的小波系數則根據圖像幀的類型進行不同的分形編碼。對于I幀（Intra-Frame）使用幀內分形編碼，P幀(PredictiveFrame)則使用幀間分形編碼。下面對這兩種分形編碼方法分別加以說明。

圖1FEZW編碼方法示意圖

（1）幀內分形編碼

若當前幀是I幀，則進行幀內分形編碼。該方法與圖像分形編碼類似。如圖1所示，對于高頻小波系數，將第n-1級的系數劃分成互不相交的Range塊，第n級的系數形成可重疊的Domain塊。圖1中的正方形塊為Range塊，三角形塊為Domain塊；箭頭則表示了數據之間的關系：它們在原圖像中是相同位置不同頻率的數據。將Domain塊和Range塊進行匹配運算，即用Domain塊預測Range塊。不同級之間的預測關系具有相似性，即如果第4級對第3級有預測關系，那么第3級對第2級在相應的位置也有預測關系，稱之為分形樹預測。為了提高處理速度，將相鄰級的Domain塊和Range塊設為相同大小，而且為了保證圖像質量采取了選擇性編碼，即設定一閾值，如果使用分形方法匹配的數據塊與原數據塊之間的失真不超過該閾值，則采用分形編碼，該Range塊的子樹塊均使用相同方法編碼；反之，如果失真超過該閾值，那么對該塊不采用分形編碼，而使用EZW編碼。

（2）幀間分形編碼

若當前幀是P幀，則進行幀間分形編碼。與幀內分形編碼的主要差別在于，使用該幀的前一幀作為參考幀。將該幀的高頻小波系數分成range塊，而domain塊取自參考幀。如果失真在閾值以內，采用分形編碼，否則使用EZW編碼。由于幀間的相似性較大，可以有許多數據塊使用分形編碼，這種幀間分形編碼方法可以有效提高壓縮率。

1.2解壓過程

幀間分形編碼和幀內分形編碼的解壓過程相似，首先恢復小波編碼的圖像部分，然后再將分形部分應用到恢復的圖像。

1.3相關參數

在本方法中，為了有效提高壓縮比而且保證圖像質量，使用了一些參數在壓縮率與失真之間進行調節。主要參數有分形編碼時的匹配閾值t（Tolerance）和壓縮碼率b（Bitrate）。

（1）匹配閾值t所設定的值為分形匹配時的最大閾值。如果分形匹配的失真小于該閾值，那么進行分形編碼；否則使用EZW編碼。t越大則能使用分形編碼的系數塊越多，而失真則越大。

（2）壓縮碼率b的單位為bpp（bitperpixel），代表每個像素使用的比特數。碼率b越大表示壓縮效率越低；反之，碼率越小則壓縮效率越高。

2實驗結果

本方法對Salesman，MissAmerica等QCIF（QuarterCommonIntermediateFormat）格式（176×144像素）的標準視頻序列進行實驗。因為YUV的數據中UV和Y的相關性比較大，所以只進行Y分量的壓縮，對UV的處理進行擴展即可。實驗中只對前150幀進行壓縮，第一幀為I幀，其余為P幀。統計的性能數據包括壓縮過程中的分形匹配塊個數、每一幀圖像中分形編碼和EZW編碼所占的字節數、各幀的PSNR值。

主要用到的參數包括分形匹配的閾值t、EZW壓縮時的每位像素的碼率b（各參數的意義如上所述）。

表1為FEZW和EZW的實驗結果比較。視頻序列Salesman和MissAmerica在不同碼率b和不同的分形閾值t下，每幀的平均PSNR和平均字節數(B/F)。從表1的比較結果可以看出：

（1）高碼率壓縮（b＝0.3bpp）時，FEZW與EZW相比，視頻恢復質量基本相當。如表1所示，以MissAmerica序列為例，在分形參數t＝1時，FEZW比EZW每幀所需字節數平均增加6.6％，而PSNR值僅由39.49dB下降到39.42dB，基本沒有差別。出現這種情況的主要原因是在進行分形壓縮時，使用分形壓縮的Range塊系數位置設置為0，這樣就可以有效減少小波變換部分的數據。

（2）低碼率情況下（b＝0.1、0.05bpp），FEZW與EZW相比，解壓后圖像的PSNR值有所提高。如表1所示，對Salesman進行壓縮時，在每幀總字節數增加平均不超過20字節的情況下，分形閾值t＝2時FEZW與EZW相比，每幀解壓后的PSNR平均高出0.1～0.2dB。圖2是對Salesman進行碼率為0.05bpp的EZW和FEZW壓縮PSNR的比較。

（3）FEZW有較好的視頻質量可伸縮性。隨著幀圖像碼率的降低，FEZW與EZW相比，在有效降低小波變換部分數據量的同時，解壓后圖像質量（PSNR值）的下降速度較慢。例如對于Salesman序列，當碼率有所下降時，采用FEZW進行編解碼得到的幀圖像的PSNR比EZW方法平均要高。圖3是Salesman在小波系數相同但不同碼率下使用FEZW和EZW進行編解碼時幀序列的平均PSNR趨勢比較圖（數據如表1所示）。

表1FEZW和EZW的實驗結果比較

圖2Salesman序列每幀的PSNR

圖3不同碼率情況下幀平均PSNR比較

上述實驗結果表明，使用分形和小波混合壓縮方法（FEZW）進行壓縮，比單純小波壓縮方法EZW在低碼率的情況下效果好，因為分形保持了圖像塊之間的關系，能夠保持一定的細節。幀間使用分形預測比幀內使用的效果好，因為幀間的相似度更高。另外，在有數據丟失（即碼率降低）時，FEZW方法能夠減緩PSNR的下降。原因是分形信息是由縮放因子和平移因子共同作用的。當幀圖像碼率降低時，EZW細節的數據會丟失，而分形縮放因子作用到EZW數據上以后會對細節數據有適量補充，從而可以有效減緩PSNR的降低。這一點非常適合于無線網絡的傳輸。在無線網絡中，帶寬有限且丟包率較高，FEZW的這種質量可伸縮性的特點使得接收端可以根據實際接收到的數據恢復出視頻幀，而且在大量數據丟失的情況下，圖像恢復質量不至于很差。

本文將分形理論和小波變換相結合，提出了一種混合的視頻編碼方法——FEZW。該算法既克服了分形編碼效率低的缺點，又發展了小波變換的可伸縮特性。實驗結果表明，與EZW相比，在較低碼率下，該方法得到的幀圖像的PSNR值有所提高；高碼率下兩者的PSNR相當；EZW和FEZW均是可截斷編/解碼方法，但是在丟失相同的數據時，FEZW的PSNR下降速度較EZW慢，這種特點非常適合應用于無線網絡的視頻傳輸。我們下一步的工作將致力于無線網絡中FEZW視頻傳輸技術的研究。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。