多媒體通信圖像壓縮

1、第2章 多媒體數(shù)據(jù)壓縮的基本技術小波變換及其用于圖像編碼壓縮原理寧曉燕2016年秋季學期變換編碼能量的再分配2傅立葉變換與小波變換傅立葉變換的局限性4傅立葉變換是一種整體變換，無法反映信號的局部特征 2ejftF xfx tdt051015202500.511.522.5時間幅度時頻信號分析工具短時傅立葉變換5 *2,ejftSTFT xt fx t wttdt051015202500.511.522.5時間幅度 信號高斯窗函數(shù)矩形窗函數(shù)時頻信號分析工具小波變換6 1, , 0tbWx a bx tdtaaa0510152025-1-0.500.511.522.5時間幅度 信號Mexicanl

2、小波,a=0.6Mexicanl小波,a=1二維圖像的小波變換分解8小 波 變 換 的EZW編 解 碼小 波 變 換 的EZW編 解 碼 可以看出，經(jīng)過小波變換后，信號能量已經(jīng)集中在少數(shù)系數(shù)上，將幅值很小的其他系數(shù)忽略（量化到0），則可達到數(shù)據(jù)壓縮的目的。 量化后的變換系數(shù)矩陣是一個具有少量非零值和大量零值的稀疏矩陣，在將此矩陣轉換為一維序列時，如何有效地如何有效地組織非零系數(shù)和有效地表達零系數(shù)所在的位置，對數(shù)據(jù)壓組織非零系數(shù)和有效地表達零系數(shù)所在的位置，對數(shù)據(jù)壓縮的效率有至關重要的影響?？s的效率有至關重要的影響。 Lewis和和Knowles在在1992年提出了小波零年提出了小波零樹樹編碼算

3、法編碼算法。10首先要介紹一個基本概念：零樹首先要介紹一個基本概念：零樹 一個系數(shù)x的直接后代或稱子節(jié)點有三種情況： （1）最低頻子帶LLn（n為小波變換的級數(shù)），如圖所示LL3的任一個系數(shù)x在HL3、LH3、HH3中的對應位置均有一個子節(jié)點，即LLn子帶的系數(shù)共有3個子節(jié)點或稱直接代； （2）最高頻的三個子帶HL1、LH1、HH1，均無后代； （3）除上述兩種情況外，其它各子帶的一個系數(shù)x在相鄰高頻子帶的相應位置都有4個系數(shù)與之對應，且稱該4個系數(shù)為子節(jié)點或直接后代。11一幅圖像三級小波變換后的系數(shù)結構一幅圖像三級小波變換后的系數(shù)結構LL3HL3HH3LH3HL2HL1HH2LH2LH1HH

4、112 1. 把一個系數(shù)x作為一個樹根考察時，它的后代包括直接后代（也稱子節(jié)點）以及這些子節(jié)點的后代。根據(jù)考察點的位置不同，這棵樹的層次（或高矮）也不一樣， 可以是 中的一種，或者是 或它的擴展。 2重要系數(shù)與不重要系數(shù)。對于一給定的閾值T1，如果系數(shù)x的絕對|x|T1，則稱x為重要系數(shù)，否則，為不重要系數(shù)。 3零樹的概念：對于一給定的閾值T1，如果該系數(shù)x本身和它的所有后代都小于T1，則稱這棵樹為一零樹，該系數(shù)就為零樹根 13 小波零樹編碼算法就是利用小波樹的強相關性，將父節(jié)點的絕對值與門限進行比較，當父節(jié)點絕對值小于門限時，認為該小波樹均不是顯著系數(shù)，因此將該小波樹都以零值編碼，從而減少數(shù)

5、據(jù)。顯然，零樹編碼不是十分完美，譬如，父節(jié)點不顯著時也存在子節(jié)點顯著的情形，此時將造成較大的誤差。 1993年，年，Shapiro在小波零樹編碼算法的基礎上提出了嵌入小在小波零樹編碼算法的基礎上提出了嵌入小波零樹編碼（波零樹編碼（Embedded Zero-tree Wavelet, EZW）算法。）算法。14EZW算法中，用5種符號表示小波系數(shù)：l正符號（Positive Symbol, POS）：絕對值大于門限值，且值為正的小波系數(shù)。l負符號（Negative Symbol, NEG）：絕對值大于門限值，且值為負的小波系數(shù)。l孤立零值(Isolated Zero, IZ)：絕對值小于門限值

6、，但存在后代節(jié)點的絕對值大于門限值的小波系數(shù)。l小波零樹(Zerotree, ZTR)：絕對值小于門限，且后代節(jié)點的絕對值都小于門限的小波系數(shù)。l零符號(Zero Symbol, Z)：絕對值小于門限的葉節(jié)點。由于小波樹在一定掃描順序下位置能完全確定下來，所以在實際編碼中小波零樹和令符號可以用同一符號來表示。15 （1）門限值的選取 初始門限值： ,其中 表示小波系數(shù)， 表示取不超過該數(shù)的最大整數(shù)值。此后每次的門限值： （2）掃描順序 EZW算法通常對小波系數(shù)矩陣 采用Z形掃描順序，如右圖所示 （3）編碼過程 編碼過程主要分為三個過程：顯著性掃描過程（Dominant Pass），主要確定小波

7、系數(shù)的符號（5種符號之一）；改進掃描過程（Refinement Pass），對小波顯著系數(shù)（正符號和負符號）進行加細量化；符號編碼過程（Symbol Encode），對符號進行熵編碼。2logmax02DWTVTDWTV 1,1,2,.2nnTTn 1615106-7-12 23 13 0 0 00 0 0 00 0 0 00 0 0 0 5 -4-3 23 2-2 1 0 0 0 140 0 0 00 0 0 0 0 0 0 00 3 0 00 0 2 0 0 0 0 0 0 0 0 0一幅一幅88圖像三級小波變換后的系數(shù)矩陣圖像三級小波變換后的系數(shù)矩陣以下圖所示的88圖像三級小波分解系數(shù)矩

8、陣為例說明EZW編碼過程171. 首先計算閾值T1，對例子中的系數(shù)矩陣，Xmax=15: 而 n= T1=23=82. 根據(jù)閾值進行第一輪顯著性掃描：掃描順序為Z字形，從低頻子塊到高頻子塊，在每個子塊里都從左到右從上到下一行一行地掃描。3. XT1的重要系數(shù)放入副表中。 215log3218|x|T符號？是零樹根的后代？該系數(shù)的所有后代還有無重要系數(shù)？YNY 跳過，不予編碼N無用ZTR對x編碼有用IZ對x編碼+用POS對x編碼并把絕對值放入副表中用NEG對x編碼并把絕對值放入副表中對系數(shù)對系數(shù) x x編碼掃描每個系數(shù)編碼掃描每個系數(shù)x時的處理流程時的處理流程規(guī)則：規(guī)則：對大于T的正值編成P，負

9、值編成N; 對小于T的零樹，大小之根都編成ZTR，而對零樹的干枝葉都跳過不編； 對孤立零不論哪級的都編成IZ（即為根）（即為孤零）19顯顯著著性性掃掃描描過過程程20 4. 第一輪改進掃描過程：對T1=8時，其副表中的絕對值肯定處于816之間，為此我們把處于12（即1.5 T1）以下的實際值編為0，處于12及以上的實際值編為1，以對區(qū)間進行細化，其編碼規(guī)則如下圖所示，結果如表（1）所示。21 最后將這些0，1序列排在原已編過碼的四類符號之后，對前例而言，經(jīng)第一輪編碼后的碼字就為PPIZ；NZZZ；ZIZZ；ZZZZ；ZPZZ；1011。即15,10,-7,6；-12,2,3,1；3,2,-2,

10、1；3,0,0,0；0,14,0,0；15,10,-12,14。 為了把更重要的信息放在更前面，在每次副掃描后都要進行副表的重排序工作，為使編、解碼對應，應從解碼方的角度對副表進行重排序。 我們認為系數(shù)絕對值越大的就越重要，把原副表進行重排序，顯然，被編碼成 0的10應排到副表最后。而對于12、14和15，因為都編碼為1，這時從解碼方的角度就還無法辨別其大小，所以它們之間的順序仍保持不變。則經(jīng)重排序后的結果如表（2）所示。22第二輪顯著性掃描過程：這里需要注意的是，對前面掃描過程中已經(jīng)確定的重要系數(shù)就不再掃描，且他的細節(jié)信息在隨副掃描進行而增加。為了與原來的0有所區(qū)別，這里用 表示。設第二輪的

11、閾值128422TT232425第二輪改進掃描過程，此時副表中的絕對值已變?yōu)?5, 12, 14, 10, 7, 6, 5, 4，已知它們分別處于區(qū)間4，8) 、8，12) 、12，16) ，我們判斷它們是處于每個區(qū)間的上半部分6，8) 、10，12) 、14，16)，還是下半部分4，6) 、8，10) 、12，14)，并分別用1和0進行編碼，有10111100，見表（3）。最后將這個二進制序列排在第二輪已編過的四類符號之后則本次編碼輸出為：N P；Z Z Z；Z Z Z Z；P N Z Z；Z Z Z Z；Z Z Z Z；Z Z Z Z；10111100。即，-7,6；2,3,1；3,2,-

12、2,1；5,-4,-3,2；3,0,0,0；0,3,0,0；0,0,2,0；15,-12,14,10,-7,6,5,-4。 26這時，從解碼方的角度已能分辨1412，所以重排序為15，14，12，10，7，6，5，4。 1 1 0 1 1 1 0 0 自自 然然 碼碼 字字27EZW算法的解碼步驟算法的解碼步驟（一）在未獲得小波系數(shù)的編碼碼流前，解碼方應先獲得： 圖像大?。盒〔ㄗ儞Q級數(shù)；初始閾值T1。 本例的圖像大小為88；小波級數(shù)為3 ；初始閥值為T1 = 8。 解碼方在獲得這些信息以后，會開辟一個88的存儲空間，并把系數(shù)的值賦為028 按照與編碼一樣的掃描順序，邊掃描這個初始化為0的系數(shù)矩

13、陣，邊讀取碼流：PPIZ；NZZZ；ZIZZ；ZZZZ；ZPZZ 在讀到POS時 用1.5 T1重建=12，并把坐標也放入一個解碼方維持的副表。 在讀到NEG時 用1.5 T1重建= -12，并把坐標也放入一個解碼方維持的副表。 在讀到IZ和ZTR時，不用對該系數(shù)賦新值，但對于ZTR的后代，以后就跳過，不掃描。29按照上述規(guī)則，當做完第一次顯著性掃描時，解碼出的系數(shù)矩陣如上圖所示。這時，解碼方副表的情況如表（4）所示，繼續(xù)讀副表中的原始碼流：1011，并分別對應。解碼方經(jīng)過第一輪顯著性掃描后的重建值解碼方經(jīng)過第一輪顯著性掃描后的重建值30表（表（4）：解碼方第一輪改進掃描未重排的示意圖）：解碼

14、方第一輪改進掃描未重排的示意圖31 所以，在解碼方進行了一次顯著掃描和改進掃描后，解碼出的系數(shù)矩陣為圖（8）。與編碼對應，這時也要進行一個副表的重排序，重排序后的副表如表（5）所示圖（圖（8）：解碼方經(jīng)過第一輪副掃描后的重建值）：解碼方經(jīng)過第一輪副掃描后的重建值X表（表（5）：解碼方第一輪）：解碼方第一輪副掃描重排序后的副表副掃描重排序后的副表32 （二）接著進行第二遍的掃描，這時，與編碼一樣，對在第一輪中已發(fā)現(xiàn)是重要的系數(shù)，在第二輪的顯著性掃描中，就不對其進行掃描。 另外，解碼重構規(guī)則與第一遍解碼掃描時一樣，只是把T1換成了T2=4，即： 讀到POS時 用1.5 T2=6重建，并把坐標也放入

15、解碼方的副表中。 在讀到NEG時 用1.5 T2=-6重建，并把坐標也放入解碼方的副表中。33 在讀到IZ和ZTR時，不用對該系數(shù)賦新值，但對于ZTR的后代，以后就跳過，不掃描。圖圖(9)： 解碼方經(jīng)過第二輪主掃描后的重建值解碼方經(jīng)過第二輪主掃描后的重建值34讀到的第二輪原始碼流是：N P；Z Z Z；Z Z Z Z；P N Z Z；Z Z Z Z；Z Z Z Z；Z Z Z Z和第一輪經(jīng)重排后的副表之自然碼字。則第二遍顯著性掃描解碼后的結果見圖（9）。顯然是按1.5T2=6進行重建。這時副表的情況見表（6）：表（表（6）：解碼方第二輪）：解碼方第二輪 改進掃描的示意圖改進掃描的示意圖35 接著進行第二輪副掃描的解碼，這時讀到的碼流是：經(jīng)第一輪重排后的第二輪自然碼字10111100，與現(xiàn)在副表中的數(shù)據(jù)相對應，進行解碼。按前面所述的副掃描解碼規(guī)則，這時把T1變成了T2即：1對應系數(shù)的絕對值0.25 T