嵌入式零樹(shù)小波EZW編碼及其算法改進(jìn)

在基于小波變換的圖象壓縮方案中,嵌入式零樹(shù)小波 EZW(Embedded Zerotree Wavelets)[1]編碼很好地利用小波系數的特性使得輸出的碼流具有嵌入特性。近年來(lái),在對EZW改進(jìn)的基礎上，提出了許多新的性能更好的算法,如多級樹(shù)集合分裂算法(SPIHT :Set Partitioning In Hierarchical Trees)[2],集合分裂嵌入塊編碼(SPECK：Set Partitioned Embedded bloCK coder),可逆嵌入小波壓縮算法(CREW:Compression with Reversible Embedded Wavelets)[3] 。本文對這些算法進(jìn)行了原理分析、性能比較,說(shuō)明了嵌入式小波圖象編碼的研究方向。

　　1. 嵌入式零樹(shù)小波編碼算法EZW

　　1. 1算法原理:

　　內嵌編碼[1](embedded coding)就是編碼器將待編碼的比特流按重要性的不同進(jìn)行排序，根據目標碼率或失真度大小要求隨時(shí)結束編碼;同樣，對于給定碼流解碼器也能夠隨時(shí)結束解碼，并可以得到相應碼流截斷處的目標碼率的恢復圖象。內嵌編碼中首先傳輸的是最重要的信息，也就是幅值最大的變換系數的位信息。圖1顯示了一個(gè)幅度值由大到小排序后的變換系數的二進(jìn)制列表。表中每一列代表一個(gè)變換系數的二進(jìn)制表示，每一行代表一層位平面，最上層為符號位，越高層的位平面的信息權重越大，對于編碼也越重要。內嵌編碼的次序是從最重要的位(最高位)到最不重要的位(最低位)逐個(gè)發(fā)送，直到達到所需碼率后停止。

　　由圖1可知內嵌編碼的輸出信息主要包括兩部分：排序信息和重要象素的位信息。其中，位信息是編碼必不可少的有效信息，對應于表中箭頭所劃過(guò)的比特位;而排序信息則是輔助信息，按其重要性從左到右排列，反映了重要象素在原圖上的空間位置，用于恢復原始的數據結構。因此，內嵌算法中排序算法的優(yōu)劣和排序信息的處理決定了整個(gè)編碼算法的效率。

　　一副圖象經(jīng)過(guò)三級小波分解后形成了十個(gè)子帶，如圖2所示。小波系數的分布特點(diǎn)是越往低頻子帶系數值越大，包含的圖象信息越多，如圖2中的LL3子帶。而越往高頻子帶系數值越小，包含的圖象信息越少。就是在數值相同的情況下，由于低頻子帶反映的是圖象的低頻信息，對視覺(jué)比較重要，而高頻子帶反映的是圖象的高頻信息，對視覺(jué)來(lái)說(shuō)不太重要。這樣對相同數值的系數選擇先傳較低頻的系數的重要比特，后傳輸較高頻系數的重要比特。正是由于小波系數具有的這些特點(diǎn)，它非常適合于嵌入式圖象的編碼算法。在JPEG2000標準中以小波變換作為圖象編碼的變換方法。

　　EZW算法利用小波系數的特點(diǎn)較好地實(shí)現了圖象編碼的嵌入功能，主要包括以下三個(gè)過(guò)程：零樹(shù)預測，用零樹(shù)結構編碼重要圖，逐次逼近量化。

　　1) 零樹(shù)預測

　　一副經(jīng)過(guò)小波變換的圖象按其頻帶從低到高形成一個(gè)樹(shù)狀結構，樹(shù)根是最低頻子帶的結點(diǎn)，它有三個(gè)孩子分別位于三個(gè)次低頻子帶的相應位置，見(jiàn)圖2左上角，其余子帶(最高頻子帶除外)的結點(diǎn)都有四個(gè)孩子位于高一級子帶的相應位置(由于高頻子帶分辨率增加，所以一個(gè)低頻子帶結點(diǎn)對應有四個(gè)高頻子帶結點(diǎn)，即相鄰的2×2矩陣，見(jiàn)圖2)。這樣圖2所示的三級小波分解就形成了深度為4的樹(shù)。

　　定義一個(gè)零樹(shù)的數據結構：一個(gè)小波系數x，對于一個(gè)給定的門(mén)限T，如果|x|

　　2) 用零樹(shù)結構編碼重要圖

　　重要圖包括三種要素：即重要系數、孤立零和零樹(shù)根。其中，對于一個(gè)給定的閾值T，如果系數X本身和它的所有的子孫都小于T，則該點(diǎn)就稱(chēng)為零樹(shù)根;如果系數本身小于T，但其子孫至少有一個(gè)大于或等于T，則該點(diǎn)就稱(chēng)為孤立零點(diǎn)。在編碼時(shí)分別用三種符號與之對應。當編碼到最高分辨率層的系數時(shí)，由于它們沒(méi)有子孫，零樹(shù)根不再存在，只需其余兩種符號即可。為了有利于內嵌編碼，將重要系數的符號與重要圖一起編碼，這樣就要使用四種符號：零樹(shù)根、孤立零、正重要系數、負重要系數。

　　3) 逐次逼近量化(Successive-Approximation Quantization,SAQ)

　　內嵌編碼的核心在于采用了逐次逼近的量化方法(SAQ)。SAQ按順序使用了一系列閾值T0、T1，┄，TN-1來(lái)判決重要性，其中Ti=Ti-1/2，初始閾值T0按如下條件選擇，OXjO2T0,其中Xj表示所有變換系數。

　　在編(譯)碼過(guò)程中，始終保持著(zhù)兩個(gè)分離的列表：主表和輔表。主表對應于編碼中的不重要的集合或系數，其輸出信息起到了恢復各重要值的空間位置結構的作用，而輔表是編碼的有效信息，輸出為各重要系數的二進(jìn)制值。編碼分為主、輔兩個(gè)過(guò)程：在主過(guò)程中，設定閾值為T(mén)i,按上述原理對主表進(jìn)行掃描編碼，若是重要系數，則將其幅值加入輔表中，然后將該系數在數組中置為零，這樣當閾值減小時(shí)，該系數不會(huì )影響新零樹(shù)的出現;在輔過(guò)程中，對輔表中的重要系數進(jìn)行細化，細化過(guò)程類(lèi)似于比特平面編碼。對閾值Ti來(lái)說(shuō)，重要系數的所在區間為[Ti,2Ti]，若輔表中的重要系數位于[Ti，3Ti/2],則用符號“0”表示，否則用符號“1”表示。編碼在兩個(gè)過(guò)程中交替進(jìn)行，在每個(gè)主過(guò)程前將閾值減半。譯碼時(shí)系數的重構值可以位于不確定區間的任意處，如果采用MMSE準則，則重構值應位于不確定區間的質(zhì)心處。實(shí)際中為簡(jiǎn)單起見(jiàn)使用區間的中心作為重構值。

　　1. 2算法分析：

　　研究表明，在圖象的低比特率編碼中，用來(lái)表示非零系數所在位置的開(kāi)銷(xiāo)遠遠大于用來(lái)表示非零系數值的開(kāi)銷(xiāo)。零樹(shù)結構正是一種描述圖象經(jīng)過(guò)小波變換后非零數值位置的有效方法。EZW的編碼思想是不斷掃描變換后的圖象，生成多棵零樹(shù)來(lái)對圖象編碼：一棵零樹(shù)的形成需要對圖象進(jìn)行兩次掃描。在生成第一棵零樹(shù)時(shí)，首先找出變換后圖象的最大絕對值系數，用它對應的T0作初始閾值，對圖象進(jìn)行第一次掃描。將圖象中絕對值小于閾值系數都看作零，然后按前面的符號定義形成零樹(shù)。在第二次掃描中，對那些絕對值大于閾值的結點(diǎn)(POS和NEG)按其絕對值是否大于閾值的1.5倍附加一個(gè)比特1或0來(lái)描述其精度。這樣做的目的是減小非零結點(diǎn)系數值的變化范圍，使其適應下一次閾值減半后的比特附加(具體細節見(jiàn)文[1])。而后將閾值減半，再經(jīng)兩次掃描生成第二棵零樹(shù)，在第一次掃描生成零樹(shù)時(shí)，以前已經(jīng)大于閾值的結點(diǎn)不再考慮，而第二次掃描附加比特時(shí)則要考慮以前數值較大的結點(diǎn)以保證精度。如此重復下去，不斷生成零樹(shù)，直到達到需要的編碼精度為止。

　　研究發(fā)現EZW算法存在的問(wèn)題是：

　　(1).由于編碼時(shí)它形成多棵零樹(shù)，因而要多次掃描圖象，造成效率很低。而且每一棵樹(shù)必須在前一棵樹(shù)形成之后才能形成，所以也很難用并行算法優(yōu)化。

　　(2).對所有的頻域進(jìn)行等同重要度的編碼，不能充分利用小波變換的特點(diǎn)。改進(jìn)辦法之一是把最低頻子圖與其它子圖分開(kāi)處理，對其進(jìn)行單獨的無(wú)失真編碼。

　　(3).在一棵零樹(shù)中包含的元素越多，則越有利于數據壓縮。在EZW算法中存在這樣的樹(shù)間冗余，在SPIHT算法中則進(jìn)一步利用了這種樹(shù)間冗余。

　　(4).通過(guò)對小波系數的分析發(fā)現，在同一子帶中相鄰元素間有一定的相關(guān)性，尤其在高頻子帶存在大量的低值元素，所以可以通過(guò)子帶中的集合把大量的這種低值元素組織到一起，達到數據壓縮的目的。而EZW算法并沒(méi)有充分利用這種相關(guān)性。在SPECK算法中利用這種相關(guān)性達到了數據壓縮的目的。

　　2. 多級樹(shù)集合分裂算法 SPIHT

　　原理分析：

　　EZW算法是一種基于零樹(shù)的嵌入式圖象編碼算法，雖然在小波變換系數中，零樹(shù)是一個(gè)比較有效的表示不重要系數的數據結構，但是，在小波系數中還存在這樣的樹(shù)結構，如圖2，即它的樹(shù)根是重要的，除樹(shù)根以外的其它結點(diǎn)是不重要的。對這樣的系數結構零樹(shù)就不是一種很有效的表示方法。A.Said和W.A.Pearlman根據Shapiro零樹(shù)編碼算法(EZW)的基本思想，提出了一種新的且性能更優(yōu)的實(shí)現方法，即基于分層樹(shù)集合分割排序(Set Partitioning in Hierarchical Trees,SPIHT)的編碼算法。它采用了空間方向樹(shù)(SOT：spatial orientation tree)、集合D(i,j)和L(i,j)更有效地表示這樣的系數結構，從而提高了編碼效率。

　　1)SPIHT算法中用到的概念

　　算法中的一些符號和概念說(shuō)明如下：

　　● H：空間方向樹(shù)所有根結點(diǎn)的坐標集合;

　　● Z(i,j)：點(diǎn)(i,j)及其所有的后代的坐標集合，即指空間方向樹(shù);

　　● D(i,j)：點(diǎn)(i,j)的所有后代(子孫)的坐標集合，不包括(i,j)點(diǎn)本身;

　　● O(i,j)：點(diǎn)(i,j)的直接后代(兒子)的坐標集合，在分層塔形結構的最高層H有O(i,j)={(i+LL,j)，(i，j+LL)，(i+LL,j+LL)},除此之外的結點(diǎn)有O(i,j)={(2i,2j),(2i,2j+1),(2i+1,2j), (2i+1,2j+1)}，這里L(fēng)L為最高層H的尺度。

　　● L(i,j)：點(diǎn)(i,j)除直接后代外所有后代坐標的集合;