零樹編碼算法小波系數(shù)

零樹編碼算法一零樹編碼算法的基本思想眾所周知，小波系數(shù)的能量集中程度越高，需要編碼的系數(shù)越少，編碼所需的比特?cái)?shù)就越少，所以小波壓縮都是利用變換分解后的圖象能量分布集中這一特性來編碼的。小波系數(shù)的能量集中程度對圖象編碼非常重要，而不同層次上，相同空間濾波方向上的小波系數(shù)之間的相關(guān)性也非常重要。零樹編碼的基本思想就是基于這種相關(guān)性。經(jīng)過小波變換后的圖象被分解成若干個(gè)子頻帶，其中子帶HH是低頻分量，是原始圖象的平滑版本，子帶HL是水平方向上的高頻，垂直方向上的低頻分量；子帶LH是垂直方向上的高頻，水平方向的低頻分量；子帶HH是高頻分量，揭示了原始圖象在斜方向的邊緣信息。為了提高對小波系數(shù)的壓縮性能，JeromeM.Shapiro提出了一種新的數(shù)據(jù)結(jié)構(gòu)零樹（zerotree），如果小波系數(shù)x的絕對值小于給定的閾值TJ則此系數(shù)是可以忽略的。零樹的方法是基于這樣一個(gè)假設(shè)：如果在較粗的級別上，一個(gè)小波系數(shù)是小于閾值，可以忽略的，則所有在相同方向，相同位置的更高的級別上的系數(shù)也基本上是可以忽略不記的。經(jīng)驗(yàn)證明這個(gè)假設(shè)通常是正確的。更特殊的情況下，在一個(gè)多級的子帶系統(tǒng)里，除了最高頻的子帶之外，在每一級別的每個(gè)系數(shù)都是和該系數(shù)在更高的級別相同方位的系數(shù)集合相對應(yīng)的，我們把在較粗的級別上的系數(shù)叫做父親，而在所有在更高的級別上相應(yīng)位置的系數(shù)都叫做后代，同樣的，對于任一給定的后代，在更粗的級別上相同方位上對應(yīng)的系數(shù)叫做祖先。對于一個(gè)QMF-金字塔算法的子帶分解，如圖所示，除了最低頻的子帶之外,所有的父親結(jié)點(diǎn)都有4個(gè)兒子，而最低頻的結(jié)點(diǎn)是有3個(gè)兒子。對系數(shù)的掃描順序的原則是不可以有一個(gè)兒子結(jié)點(diǎn)是在它的父親結(jié)點(diǎn)之前被掃描。對于一個(gè)N級的變換，掃描是先從最低頻的子帶開始的，這里記作LLn,然后掃描子帶HLn,LHn,和HHn,然后掃描第n-1級的系數(shù)，以此類推。在金字塔分解中這種掃描模式的圖示見下圖，可以看到在一個(gè)給定的子帶每個(gè)系數(shù)都是在下一個(gè)子帶的如果一個(gè)系數(shù)如果一個(gè)系數(shù)x和它的所有后代都小于閾值，則這個(gè)系數(shù)X可以看作是零樹的一個(gè)成員，一個(gè)零樹的根指的是一個(gè)零樹中的結(jié)點(diǎn)，但是它不是任何一個(gè)結(jié)點(diǎn)的后代，實(shí)踐證明對于相同的閾值零樹的根的分布并沒有可預(yù)見性。偶們用一種特殊的記號給一個(gè)零樹的根編碼，則它的所有的后代的結(jié)點(diǎn)就都可以被忽略不記了。于是所有的系數(shù)都可以被歸為3類來編碼：1）零樹的根，2）孤立的零結(jié)點(diǎn)，3）重要的點(diǎn)。當(dāng)給最高級的系數(shù)編碼時(shí)，由于已經(jīng)沒有后代，所以可以不用零樹的記號而直接進(jìn)行編碼。在實(shí)踐中，偶們通常把系數(shù)分成4類：1）零樹的根，2）孤立的零結(jié)點(diǎn)，3）正的重要系數(shù)，4）負(fù)的重要系數(shù)。這個(gè)小改進(jìn)將有利于嵌入。注意可能還存在著其它兩種系數(shù)我們沒有考慮，那就是“正的/負(fù)的重要系數(shù)，但是后代是零樹”，在實(shí)踐中，這種系數(shù)點(diǎn)出現(xiàn)的比率很低，為了減少編碼的數(shù)據(jù)量，通常不與考慮。我的關(guān)于零樹編碼的算法的實(shí)現(xiàn)是用C++語言在VC6.0下實(shí)現(xiàn)的，所以在解釋算法時(shí)，涉及到數(shù)據(jù)結(jié)構(gòu)和算法的流程時(shí)，會一C++語言為例來說明零樹編碼算法的具體實(shí)現(xiàn)方法。二零樹的數(shù)據(jù)結(jié)構(gòu)在小波變換之后，得到的是每個(gè)原始圖象的像素坐標(biāo)對應(yīng)的小波系數(shù)。我們要把這些系數(shù)都定義成零樹的結(jié)點(diǎn)，除了最低頻的和最高頻的結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有四個(gè)子結(jié)點(diǎn)，父結(jié)點(diǎn)和子結(jié)點(diǎn)之間坐標(biāo)的對應(yīng)關(guān)系是：父親（x,y） 兒子（2x2y）,（2x+1,2y）,（2x,2y+1）,（2x+1,2y+1）每個(gè)結(jié)點(diǎn)的內(nèi)容包括該點(diǎn)的小波系數(shù),該點(diǎn)的位置坐標(biāo)，還有指向該結(jié)點(diǎn)四個(gè)兒子的指針。如下圖所示Coeff|(x,y) |Son[4]具體用C++語言定義的數(shù)據(jù)機(jī)構(gòu)如下：typedefstructnode*zerotree_pointer;typedefstructnode{doublecoeff;unsignedlongx,y;zerotree_pointerson[4];};假設(shè)圖象經(jīng)過N次分解，最低頻分量最后只剩下一個(gè)系數(shù)，這個(gè)系數(shù)就被作為零樹的根結(jié)點(diǎn)。零樹的根結(jié)點(diǎn)和上面定義的結(jié)點(diǎn)稍有不同，零樹的根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：系數(shù)值HLsonLHsonHHson具體用C++語言定義的數(shù)據(jù)機(jī)構(gòu)如下：structroot_node{doubleroot_coeff;zerotree_pointerLH_son,HL_son,HH_son;};這樣以來一棵零樹的結(jié)構(gòu)如下圖所示：三．零樹的構(gòu)造定義完基本的數(shù)據(jù)結(jié)構(gòu)之后，要進(jìn)行的是零樹的構(gòu)造。即根據(jù)經(jīng)過小波變換后的系數(shù)值構(gòu)造出一棵零樹來，零樹的構(gòu)造的依據(jù)是父親結(jié)點(diǎn)和兒子結(jié)點(diǎn)之間存在著位置坐標(biāo)的的對應(yīng)關(guān)系：對任何點(diǎn)(x,y){Ovxvlength/2,Ovyvlength/2}父親(x,y) 兒子(2x,2y),(2x+1,2y),(2x,2y+1),(2x+1,2y+1)根據(jù)這種對應(yīng)關(guān)系，我們可以用遞歸的算法來實(shí)現(xiàn)零樹構(gòu)造，我們用類C的語言來描述該算法，Creat_Zerotree(x,y)的功能是構(gòu)造一個(gè)以(x,y)為根結(jié)點(diǎn)的零樹，算法如下：Creat_Zerotree(x,y){1.if(x>length/2||y>length/2)return;2．申請四個(gè)新的結(jié)點(diǎn)；3?分別將坐標(biāo)為(2x,2y),(2x+12y),(2x,2y+1),(2x+1,2y+1)的小波系數(shù)添入新申請的結(jié)點(diǎn)；4.將(x,y)結(jié)點(diǎn)的四個(gè)兒子指針指向新建立的四個(gè)結(jié)點(diǎn)；5．Creat_Zerotree(2x,2y);Creat_Zerotree(2x+1,2y);Creat_Zerotree(2x,2y+1);Creat_Zerotree(2x+1,2y+1);Return;}零樹的遍歷（掃描算法）在圖象編碼中，掃描算法是很重要的，直接影響到編碼和解碼的時(shí)間復(fù)雜度，根據(jù)小波系數(shù)的分布特點(diǎn)，低頻的部分是能量集中的區(qū)域，所以要先給低頻的分量編碼，掃描順序也是應(yīng)該是從低頻到高頻，這個(gè)順序如圖所示，圖的掃描順序?qū)?yīng)于零樹的遍歷順序，因?yàn)檎麄€(gè)編碼解碼過程我們都是在對零樹進(jìn)行操作，如果說要按照先由低頻到高頻的順序掃描的話，對應(yīng)于零樹就是遍歷的時(shí)候，對任何一個(gè)結(jié)點(diǎn)，在它的父結(jié)點(diǎn)被訪問之前，它都不可以被訪問，即要按樹層次從最頂層到最底層的順序，一層層的遍歷，這在數(shù)據(jù)結(jié)構(gòu)里叫做平序遍歷（levelorder），所以對圖象的掃描過程其實(shí)就是對零樹的平序遍歷過程。平序遍歷的是通過一個(gè)隊(duì)列來實(shí)現(xiàn)的，隊(duì)列的特點(diǎn)是先進(jìn)先出。這個(gè)隊(duì)列存放的都是指向結(jié)點(diǎn)的指針。遍歷的時(shí)候最先訪問的是根結(jié)點(diǎn)，然后把根結(jié)點(diǎn)的兒子結(jié)點(diǎn)都壓入隊(duì)列，下一個(gè)要訪問的結(jié)點(diǎn)就是最先進(jìn)入隊(duì)列的那個(gè)結(jié)點(diǎn)，也就是說，從隊(duì)列中取出一個(gè)元素，作為下一個(gè)訪問的對象。訪問之后，仍然是把該結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)都壓入隊(duì)列（如果訪問到最底層的結(jié)點(diǎn)時(shí)就沒有兒子結(jié)點(diǎn)就不需要對隊(duì)列進(jìn)行操作），這樣一直進(jìn)行下去，直到隊(duì)列為空，就證明所有的結(jié)點(diǎn)都被訪問過了一遍。使用這個(gè)隊(duì)列的目的是為了使每個(gè)父親都能在兒子被訪問之前被訪問到。具體的算法如下：1．Add_queue(HL_son); //將HL_son加入隊(duì)列；2．Add_queue(LH_son)； //將LH_son加入隊(duì)列；3 Add_queue(HH_son)；//將HH_son加入隊(duì)列；for(;;){root_node=delete_queue(); //從隊(duì)列中取出一個(gè)結(jié)點(diǎn)；if(!IsEmpty_queue()) //當(dāng)隊(duì)列不為空的時(shí)候{map_code(root_node); //訪問該結(jié)點(diǎn)；for(inti=0;i<4;i++){if(root_node->son[i]) //將該結(jié)點(diǎn)的四個(gè)兒子結(jié)點(diǎn)的指針加入隊(duì)列中Add_queue(root_node->son[i]);}else{map_code(queue[front]);//訪問最后一個(gè)結(jié)點(diǎn)；上述算法不僅在對圖象進(jìn)行掃描的時(shí)候被用到，而且在圖象的解碼，還有判斷一個(gè)結(jié)點(diǎn)是否是零樹的根的時(shí)候都要用到，具體差異會在以后提到。五．零樹的編碼算法在確定了掃描的順序之后，我們就可以開始真正的編碼過程，在零樹的遍歷過程中，就是每訪問到一個(gè)結(jié)點(diǎn)，就對這個(gè)結(jié)點(diǎn)進(jìn)行判斷，是否要進(jìn)行編碼。正像在前面提到的那樣，我們最后要把有用的結(jié)點(diǎn)分成4類：1）正的重要的結(jié)點(diǎn)；2）負(fù)的重要的結(jié)點(diǎn)；3）零樹的根；4）孤立的零結(jié)點(diǎn)。正的和負(fù)的結(jié)點(diǎn)就是指大于設(shè)定的閾值的點(diǎn)，零樹的根是指該點(diǎn)小于閾值，而且它的所有后代也都是小于閾值的，這樣我們就可以只對該點(diǎn)進(jìn)行編碼，而忽略所有它的后代，孤立的零結(jié)點(diǎn)是指，該結(jié)點(diǎn)是小于閾值的，但是它的后代中有大于閾值的重要的結(jié)點(diǎn)存在；為了便于操作，我定義了一個(gè)雙向鏈表來存放編碼后的數(shù)據(jù)，這個(gè)雙向鏈表的數(shù)據(jù)定義如下：#definePOS1#defineNEG2#defineIZ3#defineZTR4typedefstructtable_node*table_pointer;typedefstructtable_node{doubleCoeff_value;//結(jié)點(diǎn)的小波系數(shù)；

shortunsignedSymbol;//結(jié)點(diǎn)的分類標(biāo)記；

table_pointerllink; //鏈表的左指針；table_pointerrlink; //鏈表的右指針；}Symbol是該結(jié)點(diǎn)屬于上述四類需要編碼的結(jié)點(diǎn)中的哪一類的標(biāo)記。有了這個(gè)雙向鏈表，我們就可以開始給零樹進(jìn)行掃描編碼，每訪問一點(diǎn)，如果是要編碼的結(jié)點(diǎn)，我們就把它加到雙向鏈表中去。下面是編碼的流程圖如下：■輸入一個(gè)系數(shù). 從上面的流程可以看出，編碼的過程是先對一個(gè)結(jié)點(diǎn)進(jìn)行訪問，判斷它是否大于閾值，如果大于閾值的話，它就是重要的結(jié)點(diǎn)，需要被編碼，根據(jù)它的正負(fù)特性來決定Symbol就可以了，如果它是小于閾值的話，情況要復(fù)雜一些，我們要先來判斷它的后代是否有大于閾值的點(diǎn)，這個(gè)過程是用一個(gè)叫做search_descend(zerotree_pointerroot_node)的函數(shù)來實(shí)現(xiàn)的，它的原理也是遍歷以root_node為根結(jié)點(diǎn)的零樹，如果遇到大于閾值的點(diǎn)就返回ture，如果沒有的話就返回false。通過判斷我們可以直到該結(jié)點(diǎn)是零樹的根，還是孤立的零結(jié)點(diǎn)。然后做好標(biāo)記存到雙向鏈表中。值得注意的是，在對零樹進(jìn)行編碼的過程，其實(shí)也是對零樹進(jìn)行修剪的過程，如果一個(gè)結(jié)點(diǎn)是零樹的根的話，那么它的所有后代都可以忽略不記，我們就可以在這里把該結(jié)點(diǎn)的所有兒子指針置空，零樹就被剪掉了一枝，這樣不斷的修剪整棵樹。需要遍歷的結(jié)點(diǎn)會不斷減少。可以大大提高算法的復(fù)雜程度。讀到雙向鏈表中的數(shù)據(jù)最后是要串行化到磁盤文件中去的，這個(gè)過程不是我們討論的重點(diǎn)，值得注意的是，雙向鏈表中只有coeff和symbol是需要串行化的數(shù)據(jù)，而且必須按照鏈表原來的順序存放，這樣才可以正確的解壓縮，因?yàn)槲覀儾]有保存每個(gè)結(jié)點(diǎn)的位置信息，所以只能靠掃描編碼的順序來解壓縮。這樣做的好處是可以減少存放每個(gè)點(diǎn)位置的信息，使壓縮比更高。六．零樹的解碼算法解碼的過程是編碼的逆過程，我們要把存在磁盤文件中的數(shù)據(jù)按照原來的順序再從新讀到雙向鏈表map_table中去，然后根據(jù)這個(gè)雙向鏈表來重建零樹。再由零樹來恢復(fù)出原來的小波變換后的圖象，再通過小波變換的逆變換來恢復(fù)原圖。在解碼過程中，零樹的重建過程是關(guān)鍵所在，因?yàn)橹灰馨蚜銟渲亟ㄆ饋恚覀兙涂梢园呀Y(jié)點(diǎn)一個(gè)個(gè)添回到原圖像中去，而零樹的重建的關(guān)鍵是要找出各個(gè)結(jié)點(diǎn)的位置坐標(biāo)，因?yàn)橐熏F(xiàn)有的雙向鏈表中的數(shù)據(jù)填充回去，最難的就是不知道每個(gè)結(jié)點(diǎn)的位置，不直到該把哪個(gè)點(diǎn)添到哪里去，所以就必須按找鏈表存放的順序來重建零樹，來恢復(fù)原圖。在圖象的編碼中，我們是用平序來遍歷整棵樹的，所以在零樹的重建中，我們也要按平序來重建這棵樹，也就是說，要從最高層到最低層，一層層的恢復(fù)原來的零樹，并且在恢復(fù)的同時(shí)，根據(jù)零樹的父親和兒子的位置坐標(biāo)的對應(yīng)關(guān)系來把每個(gè)結(jié)點(diǎn)的位置信息也填充進(jìn)去。這個(gè)過程同樣要用到一個(gè)隊(duì)列，來調(diào)度結(jié)點(diǎn)的生成順序。因?yàn)橐謴?fù)的零樹只能是修剪過的零樹，原來完整的零樹已經(jīng)在壓縮時(shí)被修剪了，不可能全部恢復(fù)出來，所以這棵樹并不規(guī)則，因?yàn)榉彩怯龅搅銟涞母Y(jié)點(diǎn)(ZTR)，該結(jié)點(diǎn)的兒子就要置空。具體的過程是這樣的：從鏈表頭開始讀數(shù)據(jù)，第一個(gè)結(jié)點(diǎn)就是零樹的根結(jié)點(diǎn)，它的坐標(biāo)顯然是(0,0),然后第二個(gè)是HL_son,坐標(biāo)是(1,0),然后是LH_son(0,l)和HH_son(1,1)這三個(gè)兒子結(jié)點(diǎn)的數(shù)據(jù)填充到零樹中去之后，再把指向他們的指針壓入隊(duì)列，然后又開始了和解碼過程相反的過程，從隊(duì)列中取出一個(gè)結(jié)點(diǎn)，假設(shè)該結(jié)點(diǎn)的位置坐標(biāo)是(x,y),判斷鏈表當(dāng)前指針(current)指向的結(jié)點(diǎn)的symbol，如果是ZTR的話，就把從隊(duì)列中取出的結(jié)點(diǎn)的四個(gè)兒子指針都置