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

　　基于以上概念，在SPIHT算法中，集合的分割策略如下式所示：

　　2)排序過(guò)程

　　編碼中使用了三個(gè)表：不重要系數(shù)表LIP(the list of insignificant pixels)、重要系數(shù)表LSP(the list of significant pixels)和不重要集合表LIS(the list of insiginificant sets)。LSP初始化為空表，LIP用最低頻子帶系數(shù)(如三級(jí)分解中的LL3、LH3、HL3、HH3中的系數(shù))初始化，LIS用每一個(gè)空間方向樹(shù)的根結(jié)點(diǎn)(如三級(jí)分解中的LH3、HL3、HH3中的系數(shù)位置)來(lái)初始化。

　　對(duì)重要圖的確定主要是通過(guò)空間方向樹(shù)的多次分裂來(lái)實(shí)現(xiàn)的。一個(gè)三級(jí)空間方向樹(shù)T(i,j)在初始化時(shí)分裂成樹(shù)頭結(jié)點(diǎn)c(i,j)和剩余集合D(i,j)，見(jiàn)公式(1)。對(duì)c(i,j)判斷其重要性，若重要?jiǎng)t轉(zhuǎn)到LSP中。對(duì)集合D(i,j) 進(jìn)行重要性測(cè)試，若D(i,j)是不重要的，則D(i,j)用一個(gè)符號(hào)就可以表示出來(lái)。若D(i,j)是重要的，則D(i,j)繼續(xù)分裂為兩個(gè)集合O(i,j)和L(ij),如公式(2)。對(duì)O(i,j)中的每個(gè)元素分別進(jìn)行重要性測(cè)試，把重要元素轉(zhuǎn)到LSP中。對(duì)L(i,j)集合進(jìn)行重要性測(cè)試，若L(i,j)不重要，則用一個(gè)符號(hào)就可以表示該集合，若L(i,j)重要，則L(i,j)分裂為四部分，每部分由相應(yīng)空間方向樹(shù)的位置上的元素構(gòu)成，每一部分與O(i,j)中的四個(gè)元素分別構(gòu)成四棵新樹(shù)，由于每棵新樹(shù)的頭結(jié)點(diǎn)已經(jīng)判斷，只對(duì)新樹(shù)的剩余部分也就是L(i,j)分裂出的四個(gè)集合即進(jìn)行判斷，見(jiàn)公式(3) 。如此重復(fù)對(duì)每棵樹(shù)進(jìn)行分裂和判斷直到找出每棵樹(shù)中的所有重要元素，把它們轉(zhuǎn)到LSP中。可以看到SPIHT算法對(duì)重要圖的排序是通過(guò)一系列的集合分裂完成的，即一棵樹(shù)T(i,j)分裂成頭結(jié)點(diǎn)元素c(i,j)和剩余部分D(i,j),對(duì)重要的D(i,j)繼續(xù)分裂成頭結(jié)點(diǎn)的直接四個(gè)孩子O(i,j)和剩余部分L(i,j),對(duì)重要的集合L(i,j)再繼續(xù)分裂為四棵新樹(shù)的剩余部分。

　　對(duì)每棵樹(shù)的分裂不是一次進(jìn)行到底的，而是要按照一定的掃描順序進(jìn)行。對(duì)各個(gè)子帶的掃描順序與EZW算法的掃描順序相同。對(duì)由最低頻子帶(如LL3)和頭結(jié)點(diǎn)構(gòu)成的LIP中的元素是按從上到下、從左到右的順序進(jìn)行掃描的。而對(duì)其它子帶則是按2×2的塊為單位從上到下、從左到右依次掃描。對(duì)每個(gè)2×2塊中元素還是按從上到下、對(duì)每個(gè)2×2塊中元素還是按從上到下、從左到右順序掃描。

　　3) 量化過(guò)程：

　　SPIHT采用與EZW算法相同的逐次逼近量化。

　　與EZW算法的比較：

　　SPIHT算法繼承了EZW算法中的小波系數(shù)的零樹(shù)結(jié)構(gòu)，這里稱(chēng)為“空間方向樹(shù)結(jié)構(gòu)”。該算法不但把零樹(shù)作為一個(gè)集合，而且把剩余樹(shù)(即除去頭結(jié)點(diǎn)的零樹(shù))也作為一個(gè)集合處理。如圖2，假設(shè)在HH3中的某個(gè)元素C(i,j)是重要的，而其后所對(duì)應(yīng)的HH2、HH1中的元素是不重要的，則在EZW算法中第一次掃描把C(i,j)賦予符號(hào)P，對(duì)其后的所有元素形成四棵零樹(shù)ZTR(2i,2j)、ZTR(2i,2j+1)、ZTR(2i+1，2j)、ZTR(2i+1,2j+1)。共用PZZZZ五個(gè)符號(hào)表示這樣的一個(gè)結(jié)構(gòu)。在SPIHT中C(i,j)即放在LIP中，又放在LIS中。對(duì)LIP中元素的比較之后把C(i,j)轉(zhuǎn)到LSP中。而對(duì)LIS比較之后發(fā)現(xiàn)D(i,j)是不重要的(D(i,j_)是指以(i,j)為樹(shù)根的樹(shù)除去根結(jié)點(diǎn)外所有的結(jié)點(diǎn))，可用一個(gè)符號(hào)來(lái)表示。整個(gè)結(jié)構(gòu)可用兩個(gè)符號(hào)表示出來(lái)。所以該算法比EZW算法提高了壓縮率。

　　SPIHT算法初始化過(guò)程、細(xì)化過(guò)程類(lèi)似與EZW算法，它改進(jìn)了EZW 重要圖的表示方法，也就是重要系數(shù)在表中的排序信息，使得集合的表示更為精簡(jiǎn)，從而提高了編碼效率。SPIHT算法在不同的比特率下比EZW算法的峰值信噪比都有所提高[2]。

3.集合分裂嵌入塊編碼器SPECK

　　3.1原理分析：

　　對(duì)小波變換系數(shù)的分析可以看出，在系數(shù)中存在許多的不重要系數(shù)，尤其對(duì)于高頻子帶更是如此。在EZW算法和SPIHT算法中，主要是利用樹(shù)結(jié)構(gòu)來(lái)表示這些不重要系數(shù)。這兩種方法雖然利用了子帶間不重要系數(shù)的相關(guān)性，但是沒(méi)有充分利用同一子帶中不重要系數(shù)的相關(guān)性。為此 Asad 和 Pearlman提出了SPECK算法，該算法是近期嵌入式分級(jí)圖象編碼算法中性能較好的一種。

　　1)算法中用到的概念和定義

　　集合定義：LIS——不重要系數(shù)集合列表 ，用最低頻子帶系數(shù)初始化(如三級(jí)分解中的LL3)。

　　LSP——重要系數(shù)列表，存放重要系數(shù)以便進(jìn)一步量化。

　　集合S——放置待處理的塊，用最低頻子帶系數(shù)初始化(如三級(jí)分解中的LL3)。

　　集合I——放置除了S之外的剩余塊集合，I=X-S,X是所有塊的集合。

　　塊：相應(yīng)小波分解的每一個(gè)子帶定義一個(gè)相應(yīng)的塊。塊可以是只包含單個(gè)元素，如8×8系數(shù)陣經(jīng)過(guò)三級(jí)分解后對(duì)應(yīng)的LL3、HL3、LH3和HH3都只包含一個(gè)元素。一般一個(gè)塊中包含22N(N=0,1,2,…,n)個(gè)元素，其中，n-1是小波分解的層數(shù)。

　　2)排序過(guò)程

　　對(duì)于只包含一個(gè)元素的塊，若重要?jiǎng)t把它轉(zhuǎn)到LSP中，以便進(jìn)行進(jìn)一步量化。對(duì)于包含2N×2N個(gè)元素的塊，如果是不重要的，可以只用一個(gè)符號(hào)表示它。對(duì)于重要的塊，則要等分為四個(gè)子塊，然后從上到下、從左到右對(duì)各個(gè)子塊進(jìn)行重要性判斷，對(duì)重要的子塊繼續(xù)分解，如此重復(fù)直到找出塊中所有的重要系數(shù)，并把它轉(zhuǎn)到LSP表中，以便進(jìn)一步量化。

　　對(duì)各個(gè)塊的處理順序是與EZW算法對(duì)子帶的掃描順序是相同的，即從低頻塊(子帶)依次到高頻塊(子帶)。具體在SPECK算法中，采用一種稱(chēng)為倍頻程分裂的方法，來(lái)決定各塊掃描順序。初始化時(shí)集合X由所有塊構(gòu)成，集合S是由最低頻塊(如LL3)來(lái)初始化，而剩余集合I=X-S。集合I依次分解出三個(gè)最低頻的塊(如HL3,LH3,HH3)和剩余集合I。然后對(duì)剩余集合I再進(jìn)行一次分裂，分解出三個(gè)次最低頻的塊(如HL2,LH2,HH2)，如此重復(fù)直到把所有的塊分裂出來(lái)，直到剩余集合I變?yōu)榭占＿@樣就可以把各個(gè)塊依次排列，重要圖掃描就是以此順序來(lái)進(jìn)行。

　　通過(guò)以上兩步，就可以把重要系數(shù)重要性放到表LSP中，以便下一步的逐次量化。

　　3)量化過(guò)程

　　SPECK算法的量化、求初始閾值與EZW算法相同。

　　SPECK算法的特點(diǎn)如下：①以上三種算法在掃描順序和量化過(guò)程是一樣的，差別在于對(duì)不重要系數(shù)的表示方法，EZW采用零樹(shù)結(jié)構(gòu)，SPIHT采用空間方向樹(shù)，SPECK采用塊結(jié)構(gòu)。SPIHT算法在一個(gè)集合中包含了更多的不重要系數(shù)，提高了壓縮率，而SPECK算法采用易于計(jì)算和并行處理的塊結(jié)構(gòu)，提高了編碼速度。 ②另外，SPECK算法還有其它一些特點(diǎn)。需要小的動(dòng)態(tài)存儲(chǔ)，有強(qiáng)的容錯(cuò)性。因?yàn)閴K間是獨(dú)立編碼的，在傳輸發(fā)生誤碼時(shí)，只有誤碼所在的塊受到影響。而在EZW和SPIHT中誤碼將影響到整個(gè)樹(shù)結(jié)構(gòu)，對(duì)圖象的破壞較大。