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

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

shortunsignedSymbol;//結點的分類標記；

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