第五部分小波圖像壓縮技術(shù)教學(xué)課件

1、第五章第五章 小波圖像壓縮技術(shù)小波圖像壓縮技術(shù) 二維正交多分辨分析二維正交多分辨分析 ezw編碼編碼 spiht編碼編碼小波分析及其工程應(yīng)用小波分析及其工程應(yīng)用-清華大學(xué)計(jì)算機(jī)系清華大學(xué)計(jì)算機(jī)系-孫延奎孫延奎-2005春春二維正交多分辨分析二維正交多分辨分析22l r空間空間222,f x yl rf x ydxdy jj zv正交多分辨分析正交多分辨分析 ,kkkkf x ya fx gy ,kkjfxgyv222jjjvvvlr22,f x yl r若記( , )( ) ( )x yxy, , ,|( , )2(2,2)2(2) (2), ,jjjjjjj k mj k mx yxkymx

2、kym k mz,則構(gòu)成2jv的一個(gè)標(biāo)準(zhǔn)正交基。的一個(gè)標(biāo)準(zhǔn)正交基。 2jj zv22()l r構(gòu)成的一個(gè)多分辨分析。的一個(gè)多分辨分析。 二維正交多分辨分析二維正交多分辨分析由1jjjvvw容易推出：容易推出：2221jjjvvw2()()()jjjjjjjwvwwvww222()j zjl rw 從而,123( , )( ) ( )( , )( ) ( )( , )( ) ( )x yxyx yxyx yxy令令123, , , ,( , ),( , ),( , )| , ,j k mj k mj k mx yx yx yj k mz則則22()l r構(gòu)成的一個(gè)標(biāo)準(zhǔn)正交基。的一個(gè)標(biāo)準(zhǔn)正交基。

3、二維二維mallat算法算法1,11,22,331,1, , , , , ,( , )jjjjjjk mjk mk mj k mk mj k mk mj k mk mj k mk mk mk mk mk mfx yccddd1,22,11,22,21,22,31,22,jjk mlknm l nl njjk mlknm l nl njjk mlknm l nl njjk mlknm l nl nchhcdhgcdghcdggc二維維mallat分解算法分解算法1122,22,1122,2,21122,211,112 , = jjlknm l nlknm l nl nlnjjk lm n l n

4、k llmlnljjk lk ll mlmlljjl ml mjjk mhhchhchhchhchhchccd hchcd hc其中, jk mk mc一維行變換一維行變換一維列變換一維列變換二維二維mallat算法算法 一維行小波變換一維行小波變換 一維列小波變換一維列小波變換 ,1,2,3,jjk mk mjjk mk mcddd可分離的二維小波變換可分離的二維小波變換二維二維mallat算法算法1.確定ll另一種計(jì)算方法另一種計(jì)算方法:12344538671259631.5 3.54.5 74.534.56.75336.754.532. 確定確定hl1234453867

5、1259631.5 3.54.5 74.536.754.550.25111.51.5注意注意: 在在matlab中，可以用函數(shù)中，可以用函數(shù)dwt2()和和idwt2()實(shí)現(xiàn)二維離散小波實(shí)現(xiàn)二維離散小波變換的小波分解與重構(gòu)。變換的小波分解與重構(gòu)。 二維二維mallat算法算法1,1,2,3,22,22,22,22,jjjjjk mklmnl nklmnl nklmnl nklmnl nl nl nl nl nchhchgdghdggd二維重構(gòu)算法二維重構(gòu)算法: 二維二維mallat算法算法 一維行小波變換一維行小波變換 一維列小波變換一維列小波變換雙正交濾

6、波器的情雙正交濾波器的情況況二維小波變換的塔式結(jié)構(gòu)二維小波變換的塔式結(jié)構(gòu) 簡單的壓縮方案簡單的壓縮方案:方案方案1: 只保留低頻部分.方案方案2: 全局閾值 法.方案方案3: 保留絕對(duì)值較大的若干小波系數(shù)二維小波變換的塔式結(jié)構(gòu)圖二維小波變換的塔式結(jié)構(gòu)圖 8 8圖像塊的三級(jí)小波分解系數(shù)圖像塊的三級(jí)小波分解系數(shù) 嵌入式零樹小波圖像壓縮技術(shù)嵌入式零樹小波圖像壓縮技術(shù)-ezw編碼編碼 小波圖象編碼的一般結(jié)構(gòu)小波圖象編碼的一般結(jié)構(gòu) 小波樹狀結(jié)構(gòu)小波樹狀結(jié)構(gòu) （1992，lewis and knowles ）幾個(gè)重要的概念幾個(gè)重要的概念: 重要系數(shù)、不重要系數(shù)、零樹根、孤立點(diǎn)重要系數(shù)、不重要系數(shù)、零樹根、

7、孤立點(diǎn)如何組織小波系數(shù)及如何組織小波系數(shù)及其位置信息？其位置信息？如何處理小波系數(shù)及如何處理小波系數(shù)及其位置信息？其位置信息？ezw編碼編碼 子帶及小波系數(shù)的掃描順序子帶及小波系數(shù)的掃描順序 通過通過多遍掃描多遍掃描編碼多分辨圖像，其中編碼多分辨圖像，其中每一遍掃描每一遍掃描包含以下的包含以下的處理步驟：處理步驟：1.選擇閾值2. 主掃描3. 輔掃描4. 重新排序5. 輸出編碼信號(hào) ezw編碼編碼 1.選擇閾值選擇閾值0t1t1lt2/1iittiilog|0,22max ci jt對(duì)于對(duì)于l級(jí)小波變換，級(jí)小波變換，ezw算法應(yīng)用一系列的閾值算法應(yīng)用一系列的閾值， 來確定小波系數(shù)的重要性，其中

8、來確定小波系數(shù)的重要性，其中，為掃描次數(shù)，初始閾值的選擇方法如下：初始閾值的選擇方法如下：1，2，.，l1。320tezw編碼編碼 2. 主掃描主掃描 在掃描過程中，用一個(gè)主掃描表記錄這些輸出符號(hào)。當(dāng)一個(gè)系數(shù)的輸出符號(hào)為在掃描過程中，用一個(gè)主掃描表記錄這些輸出符號(hào)。當(dāng)一個(gè)系數(shù)的輸出符號(hào)為t時(shí)，它的所有子孫系數(shù)就不再掃描，并用時(shí)，它的所有子孫系數(shù)就不再掃描，并用表示。表示。第第i次主掃描結(jié)束后，將輸出符號(hào)為次主掃描結(jié)束后，將輸出符號(hào)為p或或n的系數(shù)的相應(yīng)位置加標(biāo)記或?qū)⑦@些系數(shù)的系數(shù)的相應(yīng)位置加標(biāo)記或?qū)⑦@些系數(shù)置為零，以免在下次主掃描時(shí)再對(duì)它們編碼。置為零，以免在下次主掃描時(shí)再對(duì)它們編碼。 1d：

9、pnztpttttzttzzzzzpzz ezw編碼編碼 3. 輔掃描輔掃描對(duì)主掃描表進(jìn)行順序掃描，對(duì)其中輸出符號(hào)為p或n的小波系數(shù)進(jìn)行量化。 量化值5640系數(shù)值32486410表5.1 第一次輔掃描量化表系數(shù)幅值 量化符號(hào) 重構(gòu)幅值 63 1 56 34 0 40 49 1 56 47 0 40量化符號(hào)組成的位流為量化符號(hào)組成的位流為1s：1010 系數(shù)量化器系數(shù)量化器4. 重新排序重新排序?yàn)楸阌谠O(shè)置第1i次掃描所用的量化間隔，以提高解碼的精度，對(duì)輸出符號(hào)為p或n的數(shù)據(jù)重新排序。 ppnp47,49,34,63pnpp47,34,49,63ezw編碼編碼 5. 輸出編碼信息輸出編碼信息編碼

10、器輸出兩類信息：編碼器輸出兩類信息：一類是給解碼器解碼器的信息，包括閾值、主掃描表和輔掃描表；第二類是用于下次掃描下次掃描的信息，包括閾值及第4步中重新排序過的重要系數(shù)序列。320t1d1s，：pnztpttttzttzzzzzpzz；：1010320t，pnpp47,34,49,63，小波圖像數(shù)據(jù)。小波圖像數(shù)據(jù)。 ezw編碼編碼 第二次編碼：第二次編碼：設(shè)置新閾值： 162/01tt主掃描： 4t6t7t9t11t12t17z14z15z16z 8t10t13t3t5t1n2p2d：nptttttttttttzzzz輔掃描： 表5.2 第二次輔掃描量化表系數(shù)幅值 量化符號(hào) 重構(gòu)幅值 63 1

11、 60 49 0 52 34 0 36 47 1 44 31 1 28 23 0 202s：100110 重新排序： pnnppp23,31,34,47,49,63ezw編碼編碼 第二次編碼輸出結(jié)果：第二次編碼輸出結(jié)果：a）為解碼器提供的信息161t2d2s，：nptttttttttttzzzz；：100110b）為下一次掃描的信息161t，pnnppp23,31,34,47,49,63，小波圖像數(shù)據(jù)。 11/sd22/sd表表5.3 二次編碼的輸出結(jié)果二次編碼的輸出結(jié)果t032pnztpttttzttzzzzzpzz/1010nptttttttttttzzzz/100110ezw解碼解碼 解

12、碼過程的主要步驟包括：接收編碼器發(fā)送的解碼信息后，設(shè)置閾值，構(gòu)造逆量化器。解讀位流中包含的位置信息和小波系數(shù)信息。 第一次解碼第一次解碼 解碼器接收到的信息解碼器接收到的信息：32/ pnztpttttzttzzzzzpzz/1010 1dpztpzzzzzzzzttttttpn1s1100重要的小波系數(shù)與其量化符號(hào)有如下的對(duì)應(yīng)關(guān)系：重要的小波系數(shù)與其量化符號(hào)有如下的對(duì)應(yīng)關(guān)系： ezw解碼解碼 第二次解碼第二次解碼 解碼器接收到的信息解碼器接收到的信息：16/nptttttttttttzzzz /100110 其中s2的前4位表示第一次解碼時(shí)得到的s1中的量化符號(hào)，它們的重構(gòu)值依次為 。40,

13、56,40,56 第二次解碼過程由兩步組成：第二次解碼過程由兩步組成：1）應(yīng)用新的量化器，提高第一次解碼得到的重要系數(shù)的重構(gòu)精度。40,56,40,56 60, 36,52,442）求解在第一次解碼時(shí)尚未恢復(fù)的系數(shù)。 2d2s2dnptttttttttttzzzz10中由系數(shù)輸出符號(hào)組成的位流與中后兩位量化符號(hào)間的對(duì)應(yīng)關(guān)系如下：ezw解碼解碼 第二次解碼后的結(jié)果第二次解碼后的結(jié)果 小波零樹算法具有顯著編碼性能的原因：小波零樹算法具有顯著編碼性能的原因：（1）離散小波變換（2）零樹編碼 （3）累進(jìn)逼近 （4）自適應(yīng)算法編碼。ezw編解碼算法的實(shí)現(xiàn): http:/perso.wanadoo.fr/

14、polyvalens/clemens/ezw/ezw.html spiht編碼編碼 spiht算法是算法是ezw算法的改進(jìn)算法算法的改進(jìn)算法.spiht算法采用與算法采用與ezw算法相似的零樹結(jié)構(gòu)，但它在系數(shù)子集的算法相似的零樹結(jié)構(gòu)，但它在系數(shù)子集的分割和重要信息的傳輸方式上采用了獨(dú)特方法，能夠在實(shí)現(xiàn)幅值分割和重要信息的傳輸方式上采用了獨(dú)特方法，能夠在實(shí)現(xiàn)幅值大的系數(shù)優(yōu)先傳輸?shù)耐瑫r(shí)，不顯式傳送系數(shù)的排序信息。其基本大的系數(shù)優(yōu)先傳輸?shù)耐瑫r(shí)，不顯式傳送系數(shù)的排序信息。其基本依據(jù)是：任何排序算法的執(zhí)行路徑都是使用分支點(diǎn)的比較結(jié)果進(jìn)依據(jù)是：任何排序算法的執(zhí)行路徑都是使用分支點(diǎn)的比較結(jié)果進(jìn)行定義的，如果

15、編碼器和解碼器使用相同的排序算法，則對(duì)于編行定義的，如果編碼器和解碼器使用相同的排序算法，則對(duì)于編碼器輸入的系數(shù)比較結(jié)果，解碼器通過執(zhí)行相同的路徑就可獲得碼器輸入的系數(shù)比較結(jié)果，解碼器通過執(zhí)行相同的路徑就可獲得排序信息。排序信息。spiht編碼編碼 分集規(guī)則分集規(guī)則 ,max |2()ni ji jxncsx1 若0 其他()1nsx x是重要的 ()0nsx x是不重要的 ),(jio：節(jié)點(diǎn)(i,j)所有孩子的坐標(biāo)集； ),(jid：節(jié)點(diǎn)(i,j)所有子孫的坐標(biāo)集； h：所有樹根的坐標(biāo)集。 ),(),(),(jiojidjil),(jil：節(jié)點(diǎn)(i,j)所有非直系子孫的坐標(biāo)集； 一般地,)

16、12 , 12(),2 , 12(),12 ,2(),2 ,2(),(jijijijijiospiht編碼編碼 分集規(guī)則分集規(guī)則 1)最初坐標(biāo)集由最初坐標(biāo)集由 ( , )|( , )i ji jh和和 ( , )|( , )d i ji jh且具有非零子孫組成；組成； 2) 若若 ),(jid是重要的，則是重要的，則 ),(jid分成分成 ),(jil及4個(gè)單節(jié)點(diǎn) ),(,jiolk3) 若若 是重要的，則是重要的，則 分成分成 4個(gè)集個(gè)集 ),(jil),(jil),(lkd， ),(,jiolk有序表有序表 lip不重要系數(shù)表；不重要系數(shù)表； lsp重要系數(shù)表；重要系數(shù)表； lis不重要子

17、集表。不重要子集表。 每一個(gè)表項(xiàng)都使用坐標(biāo)每一個(gè)表項(xiàng)都使用坐標(biāo)( , )i j標(biāo)識(shí)標(biāo)識(shí) 在在lis中，坐標(biāo)中，坐標(biāo) ( , )i j代表代表 ),(jid或者或者),(jil分別用分別用(i,j)d和(i,j)l 表示表示spiht編碼的主要步驟編碼的主要步驟 （1）閾值和有序表的初始化）閾值和有序表的初始化設(shè)閾值 nt2，其中 )(maxlog,),(2jijicn lsp為空集為空集 lip,| ( , )lis( , )| ( , )i ji jhi j di jh且具有非零子孫其中其中l(wèi)ip和和lis中小波系數(shù)中小波系數(shù)( , )i j的排列順序的排列順序與零樹的掃描順序相同。與零樹的

18、掃描順序相同。例例: 小波系數(shù)最大幅值為63，故n5，閾值 3225tlip(0,0),(0,1),(1,0),(1,1)lis(0,1) ,(1,0) ,(1,1)ddd lsp spiht編碼的主要步驟編碼的主要步驟 （2）排序掃描）排序掃描由以下兩個(gè)大的步驟構(gòu)成：由以下兩個(gè)大的步驟構(gòu)成：1） 順次檢查順次檢查lip中的所有小波系數(shù)中的所有小波系數(shù) ( , )i j，確定其是否重要，確定其是否重要 如果是重要的系數(shù)，則輸出如果是重要的系數(shù)，則輸出“1”及其符號(hào)位，其中正、負(fù)小波及其符號(hào)位，其中正、負(fù)小波系數(shù)的符號(hào)位分別采用系數(shù)的符號(hào)位分別采用“1”和和“0”表示，然后將該系數(shù)從表示，然后將

19、該系數(shù)從lip中中刪除，并添加到有序表刪除，并添加到有序表lsp的尾部。的尾部。 如果如果 是不重要的系數(shù)，則輸出是不重要的系數(shù)，則輸出“0”。 排序掃描1 輸出t32對(duì)lip中的每個(gè)表項(xiàng)順次進(jìn)行處理 is （0,0） significant？yes： 1 1（符號(hào)位）/將（0，0）從lip中刪除，添加到lsp的尾部/lsp（0,0）lip（0,1）,（1,0）,（1,1）spiht編碼的主要步驟編碼的主要步驟 is （0,1） significant？yes： 1 0（符號(hào)位）lsp（0,0）,（0,1）lip（1,0） ,（1,1）is （1,0） significant？no： 0is

20、（1,1） significant？no： 0（2）排序掃描）排序掃描2) 對(duì)對(duì)lis中的每個(gè)表項(xiàng)順次處理，并對(duì)中的每個(gè)表項(xiàng)順次處理，并對(duì)d型表項(xiàng)和型表項(xiàng)和l型表項(xiàng)分別采用不型表項(xiàng)分別采用不同的處理方法，具體算法如下：同的處理方法，具體算法如下： spiht編碼的主要步驟編碼的主要步驟 check the significance of all trees in the lis according to the type of tree type: for a tree of type d: if it is significant, output 1, and code its childr

21、en: if a child is significant, output 1, then a sign bit and add it to the lsp if a child is insignificant, output 0 and add it to the end of lip. if the children have descendants, move the tree to the end of lis as type l, otherwise remove it from lis. if it is insignificant, output 0. for a tree o

22、f type l: if it is significant, output 1, add each of the children to the end of lis as an entry of type d and remove the parent tree from the lis. if it is insignificant, output 0. spiht編碼的主要步驟編碼的主要步驟 三個(gè)有序表三個(gè)有序表lip,lsp,lis的的當(dāng)前狀態(tài)信息當(dāng)前狀態(tài)信息,即即lsp=（0,0）,（0,1）,（0,2）,（4,3）lip=（1,0）,（1,1）,（0,3）,（1,2）,（1,3）

23、,（2,0）,（2,1）,（3,0）, （3,1）,（4,2）,（5,2）,（5,3）lis=（1,1）d,（0,1）l,（2,0）d,（3,0）d,（3,1）d（3）精細(xì)掃描）精細(xì)掃描對(duì)于lsp中的每個(gè)表項(xiàng) ( , )i j，若 ( , )i j（2）中新添加的， 不是在剛剛進(jìn)行過的掃描過程則輸出 ijc的第n個(gè)最重要的位，其中 nt2過程中設(shè)定的閾值。 是掃描例子例子(續(xù)續(xù)): 由于排序掃描由于排序掃描1進(jìn)行之前，進(jìn)行之前，lis= ,故沒有符號(hào)位輸出。故沒有符號(hào)位輸出。 （4）進(jìn)行下一次排序掃描和精細(xì)掃描）進(jìn)行下一次排序掃描和精細(xì)掃描 例例5.6第一次第一次spiht編碼后輸出的信息編碼

24、后輸出的信息 第一次編碼過程完成后，編碼器輸出兩類信息：第一次編碼過程完成后，編碼器輸出兩類信息： 1) 給解碼器的信息給解碼器的信息，包括域值，包括域值 2n、排序掃描的輸出位流、排序掃描的輸出位流 ns1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0、 ：精細(xì)掃描位流及三個(gè)有序表的精細(xì)掃描位流及三個(gè)有序表的初始化信息初始化信息，即，即lip ,lis和和lsp 2) 用于下次掃描的信息用于下次掃描的信息，包括域值，包括域值 2n lip（0,0）, （0,1）, （1,0）, （1,1）lis=（0,1）d, （1,0）d, （1,1）dlsp= 的的當(dāng)前狀態(tài)信息當(dāng)前狀態(tài)信息. 、三個(gè)有序表三個(gè)有序表lip,lsp,lisspiht解碼過程解碼過程 為獲得為獲得spiht解碼器算法，只需將編碼器輸出的位流、初始值以及三個(gè)解碼器算法，只需將編碼器輸出的位流、初始值以及三個(gè)控制表控制表lis、lip、lsp的初始化信息提供給解碼器，并執(zhí)行編碼器的相的初始化信息提供給解碼器，并執(zhí)行編碼器的相同路徑即可。為此，只需將同路徑即可。為此，只需將spiht編碼器代碼中的輸出（編碼器代碼中的輸出（output）改為）改為輸入（輸入（input）即可。這樣，解碼器可恢復(fù)數(shù)據(jù)的排序信息。）