第9章 小波圖像編碼

1、第第9章章 小波圖像編碼小波圖像編碼 2022-2-31第第9章章 小波圖像編碼小波圖像編碼 第第9章章 小波圖像編碼小波圖像編碼 2022-2-329.1 從子帶編碼到小波編碼從子帶編碼到小波編碼 9.1.1 子帶編碼子帶編碼 子帶編碼子帶編碼(subband coding，SBC) 基本概念是把信號(hào)的頻率分成幾個(gè)子帶，基本概念是把信號(hào)的頻率分成幾個(gè)子帶， 然后對(duì)每個(gè)子帶分別進(jìn)行編碼，然后對(duì)每個(gè)子帶分別進(jìn)行編碼， 根據(jù)每個(gè)子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù)。根據(jù)每個(gè)子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù)。 分解濾波器樹分解濾波器樹(decomposition filter trees) 使用

2、一維正交鏡像濾波器組使用一維正交鏡像濾波器組(quadrature mirror filterbanks，QMF)把信號(hào)的頻帶分解成把信號(hào)的頻帶分解成4個(gè)相等的個(gè)相等的子帶子帶,重復(fù)這個(gè)過程，直到符合應(yīng)用要求為止重復(fù)這個(gè)過程，直到符合應(yīng)用要求為止,這樣的這樣的濾波器組稱為分解濾波器樹濾波器組稱為分解濾波器樹 。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-33圖圖9-01(a)表示分解方法，圖表示分解方法，圖9-01(b)表示其相應(yīng)的頻譜。表示其相應(yīng)的頻譜。 圖中的符號(hào)圖中的符號(hào) 表示頻帶降低表示頻帶降低1/2，HH表示頻率最高的子帶，表示頻率最高的子帶，LL表示頻率最低的子帶。表示頻

3、率最低的子帶。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-34 9.1.2 多分辨率分析多分辨率分析 多分辨率分析多分辨率分析( multiresolution analysis) : 也叫做多級(jí)小波分解，就是在一級(jí)分解之后繼續(xù)進(jìn)也叫做多級(jí)小波分解，就是在一級(jí)分解之后繼續(xù)進(jìn)行分析。行分析。 多分辨率圖像多分辨率圖像( multiresolution images)： 使用多級(jí)小波分解得到的分辨率不同的圖像。使用多級(jí)小波分解得到的分辨率不同的圖像。第第9章章 小波圖像編碼小波圖像編碼 2022-2-35圖圖9-02 用一級(jí)小波分解方法得到的圖像用一級(jí)小波分解方法得到的圖像第第9章章 小

4、波圖像編碼小波圖像編碼 2022-2-36圖圖9-03Lena的多分辨率圖像的多分辨率圖像 第第9章章 小波圖像編碼小波圖像編碼 2022-2-37 9.1.3 濾波器組與多分辨率濾波器組與多分辨率 可逆濾波器組可逆濾波器組(invertible filter bank)： 使用濾波和子采樣使用濾波和子采樣(subsampling)的方法用來把離的方法用來把離散信號(hào)分解成大小相等的兩種信號(hào)，并且使用叫做散信號(hào)分解成大小相等的兩種信號(hào)，并且使用叫做共軛鏡像濾波器共軛鏡像濾波器(conjugate mirror filters)的一種的一種特殊濾波器來取消信號(hào)的混疊特殊濾波器來取消信號(hào)的混疊(al

5、iasing)，這樣可從，這樣可從子采樣的信號(hào)中重構(gòu)原始信號(hào)子采樣的信號(hào)中重構(gòu)原始信號(hào)f(n)。 多分辨率理論多分辨率理論(multiresolution theory) 任何共軛鏡像濾波器都可以用來刻畫一種小波任何共軛鏡像濾波器都可以用來刻畫一種小波(t)，它能夠生成它能夠生成L2(R)實(shí)數(shù)空間中的正交基，而且快速離實(shí)數(shù)空間中的正交基，而且快速離散小波變換可以使用串聯(lián)這些共軛鏡像濾波器來實(shí)散小波變換可以使用串聯(lián)這些共軛鏡像濾波器來實(shí)現(xiàn)。現(xiàn)。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-38 9.1.4 從子帶編碼到小波編碼從子帶編碼到小波編碼 小波變換和濾波器組之間的內(nèi)在關(guān)系：小波變

6、換和濾波器組之間的內(nèi)在關(guān)系： 離散時(shí)間濾波器離散時(shí)間濾波器(discrete-time filters)或者正交鏡象濾或者正交鏡象濾波器波器(quadrature mirror filter,QMF)可以被疊代，并在可以被疊代，并在某一種勻稱某一種勻稱(regularity，可粗略理解為函數(shù)的平滑性，可粗略理解為函數(shù)的平滑性)條條件下可獲得連續(xù)小波。件下可獲得連續(xù)小波。 作用：作用： 可使用有限沖擊響應(yīng)可使用有限沖擊響應(yīng)(finite impulse response，F(xiàn)IR)的的離散時(shí)間濾波器來執(zhí)行小波分解，使用相同的濾波器可重離散時(shí)間濾波器來執(zhí)行小波分解，使用相同的濾波器可重構(gòu)小波分解之后

7、的信號(hào)。構(gòu)小波分解之后的信號(hào)。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-39 第二代小波第二代小波(second generation wavelets) 基本思想基本思想: 首先把信號(hào)分成偶數(shù)號(hào)樣本和奇數(shù)號(hào)樣本首先把信號(hào)分成偶數(shù)號(hào)樣本和奇數(shù)號(hào)樣本; 根據(jù)信號(hào)本身的相關(guān)性，奇數(shù)樣本使用偶數(shù)樣本進(jìn)行預(yù)測(cè)，根據(jù)信號(hào)本身的相關(guān)性，奇數(shù)樣本使用偶數(shù)樣本進(jìn)行預(yù)測(cè)，由預(yù)測(cè)丟失的信號(hào)叫做信號(hào)的細(xì)節(jié)信息由預(yù)測(cè)丟失的信號(hào)叫做信號(hào)的細(xì)節(jié)信息; 然后調(diào)整偶數(shù)樣本以保存原始信號(hào)的粗糙信息和細(xì)節(jié)信息。然后調(diào)整偶數(shù)樣本以保存原始信號(hào)的粗糙信息和細(xì)節(jié)信息。 效果：效果： 解決了非無限信號(hào)或者非周期信號(hào)的小波和小

8、波變換問題；解決了非無限信號(hào)或者非周期信號(hào)的小波和小波變換問題； 使計(jì)算速度得到很大的提高使計(jì)算速度得到很大的提高 第第9章章 小波圖像編碼小波圖像編碼 2022-2-310 9.1.5 小波分解圖像方法小波分解圖像方法*第第9章章 小波圖像編碼小波圖像編碼 2022-2-3119.2 失真的度量方法失真的度量方法 失真度量法，失真度量法， 用峰值信號(hào)噪聲比用峰值信號(hào)噪聲比(peak signal to noise ratio, PSNR)來衡量來衡量, 定義為最大像素值與均方差定義為最大像素值與均方差(mean square error，MSE)之比，之比， (db)210()10logPe

9、ak Signal ValuePSNRMSE第第9章章 小波圖像編碼小波圖像編碼 2022-2-312對(duì)對(duì)8位二進(jìn)制圖像，位二進(jìn)制圖像， (db)其中，其中，其中，其中，為原始圖像的像素值，為原始圖像的像素值，為解為解壓縮之后的像素值。壓縮之后的像素值。21025510logPSNRMSE112001(,)(,)MNmnM S Ex mnx mnM N ( , )x m n( , )x m n第第9章章 小波圖像編碼小波圖像編碼 2022-2-313規(guī)格化均方差規(guī)格化均方差(normalized mean square error，NMSE) 1120011200 ( , )( , ) ( ,

10、 )MNmnMNmnx m nx m nNMSEx m n信號(hào)噪聲比信號(hào)噪聲比(signal to noise ratio，SNR) 10110logSNRNMSE平均絕對(duì)誤差平均絕對(duì)誤差(mean absolute error，MAE) 11001 ( , )( , )MNmnMAEx m nx m nMN第第9章章 小波圖像編碼小波圖像編碼 2022-2-3149.3 EZW編碼編碼 9.3.1 介紹介紹 嵌入嵌入(式式)零樹小波零樹小波(embedded zerotree wavelet，EZW)算法算法 : “小波小波” 指該算法以離散小波變換為基礎(chǔ)，以大的小波變換系數(shù)比小的小指該算法

11、以離散小波變換為基礎(chǔ)，以大的小波變換系數(shù)比小的小波變換系數(shù)更重要，以及高頻子帶中的小系數(shù)可以被拋棄的事實(shí)波變換系數(shù)更重要，以及高頻子帶中的小系數(shù)可以被拋棄的事實(shí)為背景。為背景。 “零樹零樹” 指小波變換系數(shù)之間的一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)殡x散小波變換是一種指小波變換系數(shù)之間的一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)殡x散小波變換是一種多分辨率的分解方法，每一級(jí)分解都會(huì)產(chǎn)生表示圖像比較粗糙多分辨率的分解方法，每一級(jí)分解都會(huì)產(chǎn)生表示圖像比較粗糙(低頻圖像低頻圖像)和比較精細(xì)和比較精細(xì)(高頻圖像高頻圖像)的小波系數(shù)，在同一方向和相的小波系數(shù)，在同一方向和相同空間位置上的所有小波系數(shù)之間的關(guān)系可用一棵樹的形式表示，同空間位置上的所有

12、小波系數(shù)之間的關(guān)系可用一棵樹的形式表示，如果樹根和它的子孫的小波系數(shù)的絕對(duì)值小于某個(gè)給定的閾值如果樹根和它的子孫的小波系數(shù)的絕對(duì)值小于某個(gè)給定的閾值T(threshold)，那么這棵樹就叫做零樹。，那么這棵樹就叫做零樹。 “嵌入嵌入” 指漸進(jìn)編碼技術(shù)指漸進(jìn)編碼技術(shù)(progressive encoding) 第第9章章 小波圖像編碼小波圖像編碼 2022-2-315 小波圖像編碼小波圖像編碼(wavelet image coding)的一般的一般結(jié)構(gòu)結(jié)構(gòu) ： 小波變換小波變換(wavelet transform) 不損失數(shù)據(jù)，但它是不損失數(shù)據(jù)，但它是EZW算法具有漸進(jìn)特性的基礎(chǔ)；算法具有漸進(jìn)特

13、性的基礎(chǔ)； 量化量化(quantization) 對(duì)數(shù)據(jù)會(huì)產(chǎn)生損失，數(shù)據(jù)損失的程度取決于量化閾值的大對(duì)數(shù)據(jù)會(huì)產(chǎn)生損失，數(shù)據(jù)損失的程度取決于量化閾值的大小，小，EZW算法指的就是這個(gè)模塊的算法，它的輸出是符號(hào)算法指的就是這個(gè)模塊的算法，它的輸出是符號(hào)集集P, N, T, Z, 0, 1中的一系列符號(hào)；中的一系列符號(hào)； 熵編碼熵編碼(entropy encoding) 對(duì)每個(gè)輸入數(shù)據(jù)值精確地確定它的概率，并根據(jù)這些概率對(duì)每個(gè)輸入數(shù)據(jù)值精確地確定它的概率，并根據(jù)這些概率生成一個(gè)合適的代碼，使輸出的碼流生成一個(gè)合適的代碼，使輸出的碼流(code stream)小于小于輸入的碼流。輸入的碼流。 第第9章

14、章 小波圖像編碼小波圖像編碼 2022-2-316 小波變換 量化 熵編碼 EZW中的 Zerotree, Embedding 圖圖9-05 第第9章章 小波圖像編碼小波圖像編碼 2022-2-317 9.3.2 算法算法 每一遍掃描大致包含三個(gè)步驟：每一遍掃描大致包含三個(gè)步驟： 設(shè)置閾值設(shè)置閾值 每個(gè)小波系數(shù)與閾值進(jìn)行比較每個(gè)小波系數(shù)與閾值進(jìn)行比較 量化系數(shù)和重新排序量化系數(shù)和重新排序 需要維護(hù)兩種表：需要維護(hù)兩種表： 小波系數(shù)的符號(hào)表小波系數(shù)的符號(hào)表 量化表。量化表。 1. 零樹零樹第第9章章 小波圖像編碼小波圖像編碼 2022-2-318圖圖9-06 Lena圖像使用三級(jí)濾波器組做小波變

15、換輸出的子圖像圖像使用三級(jí)濾波器組做小波變換輸出的子圖像(sub image) 第第9章章 小波圖像編碼小波圖像編碼 2022-2-319圖圖9-07 各級(jí)子圖像中的系數(shù)之間的關(guān)系各級(jí)子圖像中的系數(shù)之間的關(guān)系第第9章章 小波圖像編碼小波圖像編碼 2022-2-320圖圖9-08 非零樹與零樹的概念非零樹與零樹的概念 第第9章章 小波圖像編碼小波圖像編碼 2022-2-321 2. 掃描方法掃描方法第第9章章 小波圖像編碼小波圖像編碼 2022-2-322 3. 算法算法 (1) 閾值的選擇閾值的選擇 開始時(shí)的閾值開始時(shí)的閾值T0通常按下式估算，通常按下式估算， 其中，其中，MAX(.)表示最大

16、的系數(shù)值，表示最大的系數(shù)值，Xi表示小波變換分解到表示小波變換分解到第第i級(jí)時(shí)的系數(shù)。以后每掃描一次，閾值減少一半。級(jí)時(shí)的系數(shù)。以后每掃描一次，閾值減少一半。 log (MAX(|)iXT 202第第9章章 小波圖像編碼小波圖像編碼 2022-2-323 (2) 給系數(shù)分配符號(hào)給系數(shù)分配符號(hào) 主掃描主掃描(dominant pass) : 掃描每一個(gè)系數(shù)以產(chǎn)生系數(shù)符號(hào)掃描每一個(gè)系數(shù)以產(chǎn)生系數(shù)符號(hào) 輔掃描輔掃描(subordinate pass) 量化帶符號(hào)量化帶符號(hào)P和和N的系數(shù)的系數(shù)判斷條件判斷條件輸出符號(hào)輸出符號(hào)|X|TX0P(positive)：表示正，重要系數(shù)：表示正，重要系數(shù)X0N(

17、negative)：表示負(fù)，重要系數(shù)：表示負(fù)，重要系數(shù)|X|T所有子孫系數(shù)所有子孫系數(shù)|X|Xi i|T,X|T|TZ：孤立的零，不重要系數(shù)：孤立的零，不重要系數(shù)表表9-1 第第9章章 小波圖像編碼小波圖像編碼 2022-2-324 9.3.3 算法舉例算法舉例 1. 樹結(jié)構(gòu)樹結(jié)構(gòu)圖圖9-10 第第9章章 小波圖像編碼小波圖像編碼 2022-2-325(a) 88子圖像小波變換系數(shù)子圖像小波變換系數(shù) (b) 最低頻帶小波變換系數(shù)樹最低頻帶小波變換系數(shù)樹圖圖9-11 編碼樹的結(jié)構(gòu)編碼樹的結(jié)構(gòu)(1)第第9章章 小波圖像編碼小波圖像編碼 2022-2-326(a) 88子圖像小波變換系數(shù)子圖像小波變

18、換系數(shù) (b) 2級(jí)子圖像小波變換部分系數(shù)樹級(jí)子圖像小波變換部分系數(shù)樹圖圖9-12 編碼樹的結(jié)構(gòu)編碼樹的結(jié)構(gòu)(2) 第第9章章 小波圖像編碼小波圖像編碼 2022-2-327 2. 編碼編碼 (1) 第一次掃描：第一次掃描： 步驟步驟1: 選擇初始閾值。最大的系數(shù)為選擇初始閾值。最大的系數(shù)為63，因此選擇，因此選擇T0=32。 步驟步驟2: 指定系數(shù)的符號(hào)。指定系數(shù)的符號(hào)。 第一次主掃描之后，緩沖存儲(chǔ)器第一次主掃描之后，緩沖存儲(chǔ)器D1中的系數(shù)符號(hào)為：中的系數(shù)符號(hào)為：D1: P N T T P T T Z T T T T T T T P T T第第9章章 小波圖像編碼小波圖像編碼 2022-2-

19、328 步驟步驟3: 量化系數(shù)。量化系數(shù)。 第一次輔掃描之后，第一次輔掃描之后，4個(gè)系數(shù)個(gè)系數(shù)63-P, 34-N, 49-P, 47-P的量化符號(hào)所組成的位流為：的量化符號(hào)所組成的位流為：S1: 1 0 1 0 表9-2 第一次輔掃描量化表系數(shù)幅度系數(shù)幅度量化符號(hào)量化符號(hào)重構(gòu)幅度重構(gòu)幅度63156340404915647040第第9章章 小波圖像編碼小波圖像編碼 2022-2-329 步驟步驟4: 重新排列帶重新排列帶P/N符號(hào)的數(shù)據(jù)。符號(hào)的數(shù)據(jù)。 步驟步驟5：輸出編碼信息。：輸出編碼信息。 給解碼器的信息包含下面三種：給解碼器的信息包含下面三種：HEADER (即即T0=32), D1:

20、P N T T P T T Z T T T T T T T P T T “AND” S1: 1 0 1 0. 給下一次掃描用的信息包含下面三種：給下一次掃描用的信息包含下面三種： T0=32, 63-P, 49-P, 34-N, 47-P “AND”子帶圖像。子帶圖像。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-330 (2) 第二次掃描第二次掃描 步驟步驟1: 設(shè)置新閾值：設(shè)置新閾值：T1=T0/2=16。 步驟步驟2: 指定系數(shù)的符號(hào)。指定系數(shù)的符號(hào)。 步驟步驟3: 量化系數(shù)。量化系數(shù)。 圖圖9-14 第第2次主掃描次主掃描 第第9章章 小波圖像編碼小波圖像編碼 2022-2-3

21、31 步驟步驟4: 重新排列帶重新排列帶P/N符號(hào)的數(shù)據(jù)。符號(hào)的數(shù)據(jù)。 步驟步驟5: 輸出編碼信息。輸出編碼信息。 給解碼器的信息包含下面兩種：給解碼器的信息包含下面兩種：D2: N P T T T T T T T T T T T T T T T “AND” S2: 1 0 0 1 1 0. 給下一次掃描用的信息包含下面三種：給下一次掃描用的信息包含下面三種：T1=16, 63-P, 49-P, 47-P, 34-N, 31-N, 23-P “AND”子帶圖像子帶圖像. (3) 第三次掃描第三次掃描 步驟步驟1: 設(shè)置新閾值：設(shè)置新閾值：T2=T1/2=8。 步驟步驟2: 指定系數(shù)的符號(hào)。指定

22、系數(shù)的符號(hào)。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-332 步驟步驟3: 量化系數(shù)。量化系數(shù)。 圖圖9-15 第第3次主掃描（次主掃描（1） 第第9章章 小波圖像編碼小波圖像編碼 2022-2-333圖圖9-15 第第3次主掃描（次主掃描（2） 第第9章章 小波圖像編碼小波圖像編碼 2022-2-334 步驟步驟4: 重新排列帶重新排列帶P/N符號(hào)的數(shù)據(jù)。符號(hào)的數(shù)據(jù)。 步驟步驟5: 輸出編碼信息。輸出編碼信息。 給解碼器的信息包含下面兩種：給解碼器的信息包含下面兩種：D3: PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT “A

23、ND” S3: 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0. 給下一次掃描用的信息包含下面三種：給下一次掃描用的信息包含下面三種：, 63-P, 49-P, , 47-P, 34-N, 31-N, 23-P, 14-P, 13-N, , 15-P, 14-P, 12-N, 14-N, 13-P, 12-N, 10-P, 9-N, 8-P, 9-P, 9-P, 11-P “AND”子帶圖像子帶圖像.第第9章章 小波圖像編碼小波圖像編碼 2022-2-335表表9-3 三次編碼的輸出三次編碼的輸出名稱名稱內(nèi)容內(nèi)容Header32D1 / S1P N T T P

24、T T Z T T T T T T T P T T / 1 0 1 0D2 / S2N P T T T T T T T T T T T T T T T / 1 0 0 1 1 0D3 / S3PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT/ 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0第第9章章 小波圖像編碼小波圖像編碼 2022-2-336 3. 解碼解碼 解碼分為三個(gè)步驟：解碼分為三個(gè)步驟： 首先設(shè)置閾值首先設(shè)置閾值 構(gòu)造逆量化器構(gòu)造逆量化器 解讀位流中包含的位置和小波系數(shù)值解讀位流中包含的位置和小波系

25、數(shù)值 (1) 第一次解碼第一次解碼 解碼器開始時(shí)的閾值解碼器開始時(shí)的閾值T0=32，它接收到來自編碼器第一次，它接收到來自編碼器第一次掃描輸出的系數(shù)符號(hào)是，掃描輸出的系數(shù)符號(hào)是，P N T T P T T Z T T T T T T T P T T / 1 0 1 0 這個(gè)信息相當(dāng)于量化符號(hào)所組成的位流與系數(shù)符號(hào)之間有這個(gè)信息相當(dāng)于量化符號(hào)所組成的位流與系數(shù)符號(hào)之間有如下的對(duì)應(yīng)關(guān)系，如下的對(duì)應(yīng)關(guān)系，D1PNT T P T T Z T T T T T T T P T TS110 1 0 第第9章章 小波圖像編碼小波圖像編碼 2022-2-337圖9-16 第一次解碼的結(jié)果第第9章章 小波圖像編碼

26、小波圖像編碼 2022-2-338 (2) 第二次解碼第二次解碼 分兩步。分兩步。第一步：提高第一次解碼時(shí)得到的系數(shù)的精度，第一步：提高第一次解碼時(shí)得到的系數(shù)的精度，第二步：求解未解碼的系數(shù)。解碼器將使用編碼器生成第二步：求解未解碼的系數(shù)。解碼器將使用編碼器生成的第二次編碼時(shí)的掃描信息，的第二次編碼時(shí)的掃描信息，D2: N P T T T T T T T T T T T T T T T S2： 1 0 0 1 1 0 解碼器首先修改閾值，使，然后構(gòu)造一個(gè)如圖解碼器首先修改閾值，使，然后構(gòu)造一個(gè)如圖9-17所示的所示的量化器。量化器。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-339如

27、圖如圖9-17 第第2次解碼次解碼 第第9章章 小波圖像編碼小波圖像編碼 2022-2-340(3) 第三次解碼第三次解碼 解碼器將使用編碼器第三次掃描產(chǎn)生的信息，解碼器將使用編碼器第三次掃描產(chǎn)生的信息，D3： PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT S3: 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0S3中用下劃線表示在第二次解碼時(shí)已經(jīng)得到的系數(shù)。中用下劃線表示在第二次解碼時(shí)已經(jīng)得到的系數(shù)。 解碼器首先修改閾值，使新的閾值解碼器首先修改閾值，使新的閾值T2=T1/2=8，然后構(gòu)，然后構(gòu)造如圖造如圖

28、9-18所示的量化器，進(jìn)入第三次解碼。所示的量化器，進(jìn)入第三次解碼。 第第9章章 小波圖像編碼小波圖像編碼 2022-2-341如圖如圖9-18 第第3次解碼次解碼 第第9章章 小波圖像編碼小波圖像編碼 2022-2-3429.4 SPIHT編碼編碼 9.4.1 介紹介紹 SPIHT(set partitioning in hierarchical trees)算法算法 譯成譯成“層樹分集層樹分集”算法。算法。 具有特性具有特性 圖像的漸進(jìn)傳輸，最先傳送幅度大的系數(shù)圖像的漸進(jìn)傳輸，最先傳送幅度大的系數(shù) 比較高的比較高的PSNR 復(fù)雜度比較低復(fù)雜度比較低 計(jì)算量比較少計(jì)算量比較少 位速率容易控制

29、位速率容易控制第第9章章 小波圖像編碼小波圖像編碼 2022-2-343 9.4.2 漸進(jìn)圖像的傳輸漸進(jìn)圖像的傳輸 采用幅度大的系數(shù)先傳送原則的理由：采用幅度大的系數(shù)先傳送原則的理由： 假設(shè)原始圖像由一組像素假設(shè)原始圖像由一組像素pi,j組成，用組成，用ci,j表示經(jīng)過小波變表示經(jīng)過小波變換之后產(chǎn)生的系數(shù)，其中換之后產(chǎn)生的系數(shù)，其中(i,j)為像素的坐標(biāo)，也是小波圖為像素的坐標(biāo)，也是小波圖像系數(shù)的坐標(biāo)。為簡(jiǎn)化符號(hào)，使用字母像系數(shù)的坐標(biāo)。為簡(jiǎn)化符號(hào)，使用字母p表示二維圖像，表示二維圖像，用用c表示小波變換之后的系數(shù)，因此一幅圖像的小波變換表示小波變換之后的系數(shù)，因此一幅圖像的小波變換可表示成，可

30、表示成， 表示單式表示單式(unitary)分層子帶變換，經(jīng)過小波變分層子帶變換，經(jīng)過小波變換之后的二維陣列具有與相同的維數(shù)。換之后的二維陣列具有與相同的維數(shù)。c = ( p )( )第第9章章 小波圖像編碼小波圖像編碼 2022-2-344 在漸進(jìn)圖像傳送中，解碼器開始設(shè)置的重構(gòu)矢量在漸進(jìn)圖像傳送中，解碼器開始設(shè)置的重構(gòu)矢量通常通常為零，然后按照接收到的編碼信息進(jìn)行修改。在接收到系為零，然后按照接收到的編碼信息進(jìn)行修改。在接收到系數(shù)的近似值或者精確值之后，解碼器可以得到重構(gòu)的圖像數(shù)的近似值或者精確值之后，解碼器可以得到重構(gòu)的圖像，其中，其中，表示小波變換的逆變換。表示小波變換的逆變換。 如果

31、用均方差如果用均方差(MSE)指標(biāo)來衡量，則失真程度指標(biāo)來衡量，則失真程度可表示為，可表示為，其中其中N為圖像的像素?cái)?shù)目，為圖像的像素?cái)?shù)目，是由系數(shù)是由系數(shù)重構(gòu)重構(gòu)的像素值。的像素值。 c p1( )mse(p p)D2mse,1(pp)()i ji jijDppN,i jp,i jc第第9章章 小波圖像編碼小波圖像編碼 2022-2-345 由于歐幾里得范數(shù)由于歐幾里得范數(shù)(Euclidean norm)即向量的長(zhǎng)度相對(duì)于即向量的長(zhǎng)度相對(duì)于單式變換單式變換 是不變的，因此可以證明，是不變的，因此可以證明， 該式表明，解碼器開始使用的系數(shù)近似值該式表明，解碼器開始使用的系數(shù)近似值為零為零時(shí)，最

32、大的系數(shù)時(shí)，最大的系數(shù)對(duì)減少均方差最重要，因此幅對(duì)減少均方差最重要，因此幅度比較大的系數(shù)需要先傳送。度比較大的系數(shù)需要先傳送。 ,i jc, i jc第第9章章 小波圖像編碼小波圖像編碼 2022-2-346 9.4.3 分集排序算法分集排序算法 分集排序算法分集排序算法(set partitioning sorting algorithm) 按照一種規(guī)則選擇發(fā)送的系數(shù)按照一種規(guī)則選擇發(fā)送的系數(shù)， 這個(gè)規(guī)則是這個(gè)規(guī)則是其中，其中，2n實(shí)際上就是實(shí)際上就是EZW算法中的閾值。編碼時(shí)每掃算法中的閾值。編碼時(shí)每掃描一遍，新的閾值就設(shè)置為描一遍，新的閾值就設(shè)置為2n-1。對(duì)給定的。對(duì)給定的n，如果，如

33、果|ci,j|2n，就稱系數(shù)，就稱系數(shù)ci,j是重要是重要(significant)的，否則就的，否則就稱系數(shù)是不重要的稱系數(shù)是不重要的(insignificant) 幅度比較和比較結(jié)果之間的關(guān)系幅度比較和比較結(jié)果之間的關(guān)系用用 表示表示。 , i jc1,22nni jc,( , )1max2( )0ni ji jTncS T其他,nSi j( , )nSi j第第9章章 小波圖像編碼小波圖像編碼 2022-2-347 9.4.4 類型和變量類型和變量圖9-19 最低子帶的一個(gè)系數(shù)和最最低子帶的一個(gè)系數(shù)和最高子帶的系數(shù)都沒有子孫高子帶的系數(shù)都沒有子孫(descendant) 第第9章章 小波

34、圖像編碼小波圖像編碼 2022-2-348 三種次序列表變量三種次序列表變量 LIP (List of Insignificant Pixels): 不重要像素表，用于存放單個(gè)不重要的系數(shù)。用低通不重要像素表，用于存放單個(gè)不重要的系數(shù)。用低通(或者叫做或者叫做DC)子帶的系數(shù)初始化。子帶的系數(shù)初始化。 LIS (List of Insignificant Sets)： 不重要子集列表，用于存放不重要的系數(shù)樹。用不重要子集列表，用于存放不重要的系數(shù)樹。用DC子子帶中不重要的系數(shù)集的坐標(biāo)初始化。帶中不重要的系數(shù)集的坐標(biāo)初始化。 LSP (List of Significant Pixels)： 重

35、要像素表，用于存放重要系數(shù)。初始化成空集。重要像素表，用于存放重要系數(shù)。初始化成空集。 A型型(Type A)樹樹 : 也稱也稱D型樹：型樹：LIS代表坐標(biāo)集，編碼時(shí)需要檢查所有的子代表坐標(biāo)集，編碼時(shí)需要檢查所有的子孫系數(shù)以確定是否重要。孫系數(shù)以確定是否重要。 B型型(Type B)樹樹 : 也稱也稱L型樹：型樹：LIS代表坐標(biāo)集，編碼時(shí)需要檢查除子系數(shù)之代表坐標(biāo)集，編碼時(shí)需要檢查除子系數(shù)之外的所有子孫系數(shù)以確定是否重要。外的所有子孫系數(shù)以確定是否重要。第第9章章 小波圖像編碼小波圖像編碼 2022-2-349 9.4.5 算法算法 符號(hào)：符號(hào)：O(I,j)= the 4 offspring

36、of ci,j /系數(shù)系數(shù)ci,j的的4個(gè)子系數(shù)組成的坐標(biāo)集個(gè)子系數(shù)組成的坐標(biāo)集 D(I,j)= all descendants of ci,j /系數(shù)系數(shù)ci,j的所有子孫系數(shù)組成的坐標(biāo)集的所有子孫系數(shù)組成的坐標(biāo)集 /除子節(jié)點(diǎn)之外的所有子孫節(jié)點(diǎn)的坐標(biāo)集除子節(jié)點(diǎn)之外的所有子孫節(jié)點(diǎn)的坐標(biāo)集Sn(X)= 1 if some element of X has magnitude 2n, /在子孫坐標(biāo)集中有幅度大于或者等于閾值的坐標(biāo)集在子孫坐標(biāo)集中有幅度大于或者等于閾值的坐標(biāo)集0 otherwise / 在子孫坐標(biāo)集中沒有幅度大于或等于閾值的坐標(biāo)集在子孫坐標(biāo)集中沒有幅度大于或等于閾值的坐標(biāo)集/ 重要系

37、數(shù)測(cè)試方法：重要系數(shù)測(cè)試方法：( , )( , )( , )L i jD i jO i j,( , )1max2()0ni ji jXncSX其他第第9章章 小波圖像編碼小波圖像編碼 2022-2-350Sn(I,j)=1 if ci,j has magnitude2n,/ 在系數(shù)集在系數(shù)集ci,j中有幅度大于或等于閾值的系數(shù)中有幅度大于或等于閾值的系數(shù)0 otherwise/ 在系數(shù)集在系數(shù)集ci,j中沒有幅度大于或等于閾值的系數(shù)中沒有幅度大于或等于閾值的系數(shù) 變量：變量： LIP (List of Insignificant Pixels) / 存放單個(gè)不重要的系數(shù)存放單個(gè)不重要的系數(shù)LI

38、S (List of Insignificant Sets) / 存放不重要的系數(shù)樹存放不重要的系數(shù)樹Entries are: （i,j) of type A D(i,j)； / 是是A型樹型樹(i,j) of type BL(i,j) / 是是B型樹型樹LSP( List of Significant Pixels) / 存放重要系數(shù)存放重要系數(shù)第第9章章 小波圖像編碼小波圖像編碼 2022-2-351 *1. Initialization: / 初始化output n = log2(largest coefficient) / 確定閾值確定閾值set LSP = / 設(shè)置設(shè)置LSP為空集為

39、空集set LIP = (i,j) | ci,j is a root / 把坐標(biāo)加到把坐標(biāo)加到LIPset LIS = (i,j) of type A | ci,j is a root / 把所有樹指定為類型把所有樹指定為類型A，加到，加到LIS2.Sorting Pass:/ 排序掃描主要是檢查排序掃描主要是檢查L(zhǎng)IP和和LIS中的系數(shù)是否重要，然后把重中的系數(shù)是否重要，然后把重要的系數(shù)移到要的系數(shù)移到LSPfor each entry (i,j) in LIP do/ 檢查檢查L(zhǎng)IP中的所有系數(shù)以確定是否重要中的所有系數(shù)以確定是否重要output Sn(i,j) if Sn(i,j) =

40、1 then move (i,j) to LSP, output sign(ci,j) 2nT 第第9章章 小波圖像編碼小波圖像編碼 2022-2-352for each entry (i,j) in LIS do/ 檢查檢查L(zhǎng)IS中的所有中的所有D型樹以確定是否重要型樹以確定是否重要if entry has type A thenoutput if = 1 then for each in do output if =1 then add (k,l) to LSP and output sign of else add (k,l) to the end of LIP.if L(i,j) is

41、 not empty thenmove (i,j) to end of LIS as entry of type Belsedelete (i,j) from LIS and go around the loop.( ,)nSD i j( ,)nSD i j( , )k l( , )O i j( , )nS k l( , )nSk l第第9章章 小波圖像編碼小波圖像編碼 2022-2-353if entry has type B then/ 檢查檢查L(zhǎng)IS中的所有中的所有L型樹以確定是否重要型樹以確定是否重要output if = 1 thenfor each (k, l) in O (i,

42、j) doadd (k, l) to end of LIS as entry of type Aremove (i, j) from LIS3. Refinement Pass: / 精細(xì)掃描主要是處理精細(xì)掃描主要是處理LSP中的系數(shù)以增加它的精度中的系數(shù)以增加它的精度for each (i, j) in LSP doif (i, j) was not added in the last sorting pass thenoutput the n-th most significant bit of .4. Quantization Step:decrement n, go back to S

43、orting Pass.*( ( , )nSL i j( ( , )nSL i j第第9章章 小波圖像編碼小波圖像編碼 2022-2-354 9.4.6 算法舉例算法舉例 A執(zhí)行執(zhí)行SPIHT算法的步驟：算法的步驟： 1. 計(jì)算閾值和初始化。計(jì)算閾值和初始化。 2. 檢查檢查L(zhǎng)IP中的所有系數(shù)以確定是否重要：中的所有系數(shù)以確定是否重要： 如果重要，輸出如果重要，輸出“1”和符號(hào)位，然后把該系數(shù)移到和符號(hào)位，然后把該系數(shù)移到LSP。 如果不重要，輸出如果不重要，輸出“0” 3. 按照樹的類型，檢查按照樹的類型，檢查L(zhǎng)IS中所有重要的樹：中所有重要的樹： (1) 對(duì)對(duì)D型樹：型樹： 如果該樹是重要

44、的，輸出如果該樹是重要的，輸出“1”，然后對(duì)子節(jié)點(diǎn)的系數(shù)進(jìn)行編，然后對(duì)子節(jié)點(diǎn)的系數(shù)進(jìn)行編碼：碼： 如果該樹不重要，輸出如果該樹不重要，輸出“0” (2) 對(duì)對(duì)L型樹：型樹： 如果該樹是重要的，輸出如果該樹是重要的，輸出“1”，把每一個(gè)子節(jié)點(diǎn)移到，把每一個(gè)子節(jié)點(diǎn)移到LIS的的末端作為末端作為D型樹，然后把父樹從型樹，然后把父樹從LIS中刪除。中刪除。 如果該樹不重要，輸出如果該樹不重要，輸出“0”。 4. 減少閾值，然后返回到減少閾值，然后返回到2。第第9章章 小波圖像編碼小波圖像編碼 2022-2-355 B. 小波圖像系數(shù)的編碼小波圖像系數(shù)的編碼 一幅一幅44圖像經(jīng)過小波變圖像經(jīng)過小波變換的

45、兩次分解后的系數(shù)為：換的兩次分解后的系數(shù)為：創(chuàng)建如圖創(chuàng)建如圖9-20所示所示的一棵編碼系數(shù)樹的一棵編碼系數(shù)樹:第第9章章 小波圖像編碼小波圖像編碼 2022-2-356*計(jì)算初始閾值計(jì)算初始閾值T16。初始化。初始化: LIP = (0,0) , LIS = (0,0)D , LSP = - 主掃描主掃描1:T = 16 輸出輸出Is (0,0) significant? yes: 1 LSP = (0,0) 1 (sign bit) Is D(0,0) significant? no: 0 LIP = , LIS = (0,0)D , LSP = (0,0) 3 bits -輔掃描輔掃描1:

46、沒有符號(hào)要處理沒有符號(hào)要處理 - 第第9章章 小波圖像編碼小波圖像編碼 2022-2-357主掃描主掃描2:T = 8 Is D(0,0) significant? yes: 1 Is (1,0) significant? no: 0 Is (0,1) significant? no: 0 Is (1,1) significant? no: 0 LIP = (1,0), (0,1), (1,1) , LIS = (0,0)L Is L(0,0) significant? yes: 1 LIS = (1,0)D, (0,1)D, (1,1)D Is D(1,0) significant? yes

47、: 1 Is (2,0) significant? yes: 1 第第9章章 小波圖像編碼小波圖像編碼 2022-2-358LSP = (0,0), (2,0) 1(sign bit) Is (2,1) significant? yes: 1 LSP = (0,0), (2,0), (2,1) 1(sign bit) Is (3,0) significant? no: 0 Is (3,1) significant? no:0 LIP = (1,0), (0,1), (1,1), (3,0), (3,1) , LIS = (0,1)D, (1,1)D Is D(0,1) significant?

48、 no: 0 Is D(1,1) significant? no: 0 LIP = (1,0), (0,1), (1,1), (3,0), (3,1) , LIS = (0,1)D, (1,1)D , LSP = (0,0), (2,0), (2,1) 14 bits -輔掃描輔掃描 2:同同EZW算法的輔掃描算法的輔掃描1 bit -第第9章章 小波圖像編碼小波圖像編碼 2022-2-359主掃描主掃描3:T = 4 Is (1,0) significant? yes: 1 LSP = (0,0), (2,0), (2,1) , (1,0) 1 (sign bit) Is (0,1) sig

49、nificant? no: 0 Is (1,1) significant? yes: 1 LSP = (0,0), (2,0), (2,1), (1,0), (1,1) 0 (sign bit) Is (3,0) significant? yes: 1 LSP = (0,0), (2,0), (2,1), (1,0), (1,1), (3,0) 1 (sign bit) Is (3,1) significant? no: 0 LIP = (0,1), (3,1) Is D(0,1) significant? no: 0 Is D(1,1) significant? yes: 1Is (2,2)

50、 significant? yes: 1 第第9章章 小波圖像編碼小波圖像編碼 2022-2-360LSP = (0,0), (2,0), (2,1), (1,0), (1,1), (3,0), (2,2)0(sign bit) Is (2,3) significant? yes: 1LSP = (0,0), (2,0), (2,1), (1,0), (1,1), (3,0), (2,2), (2,3) 1(sign bit) Is (3,2) significant? no: 0 LIP = (0,1), (3,1), (3,2) Is (3,3) significant? no: 0LIP

51、 = (0,1), (3,1), (3,2), (3,3) LIP = (0,1), (3,2), (3,2), (3,3) , LIS = (0,1)D , LSP = (0,0), (2,0), (2,1), (1,0), (1,1), (3,0), (2,2), (2,3) 16 bits -輔掃描輔掃描3: 同同EZW算法的輔掃描算法的輔掃描 3 bits - 第第9章章 小波圖像編碼小波圖像編碼 2022-2-3619.5 EBCOT編碼簡(jiǎn)介編碼簡(jiǎn)介 9.5.1 介紹介紹 最佳截?cái)嗲度氪a塊編碼最佳截?cái)嗲度氪a塊編碼 (embedded block coding with optimiz

52、ed truncation，EBCOT) 是一種對(duì)小波變換產(chǎn)生的子帶系數(shù)進(jìn)行量化和編碼是一種對(duì)小波變換產(chǎn)生的子帶系數(shù)進(jìn)行量化和編碼的方法。的方法。 基本思想是把每一個(gè)子帶的小波變換系數(shù)分成獨(dú)立基本思想是把每一個(gè)子帶的小波變換系數(shù)分成獨(dú)立編碼的碼塊編碼的碼塊(code-block)，并且對(duì)所有的碼塊使用，并且對(duì)所有的碼塊使用完全相同的編碼算法。完全相同的編碼算法。第第9章章 小波圖像編碼小波圖像編碼 2022-2-362 “截?cái)嘟財(cái)唷钡暮x：的含義： 對(duì)每一個(gè)碼塊進(jìn)行編碼時(shí)，編碼器不用其他碼塊的任何信對(duì)每一個(gè)碼塊進(jìn)行編碼時(shí)，編碼器不用其他碼塊的任何信息，只是用碼塊自身的信息產(chǎn)生單獨(dú)的嵌入位流息，

53、只是用碼塊自身的信息產(chǎn)生單獨(dú)的嵌入位流(bitstream)。每一碼塊的嵌入位流可以被截?cái)喑砷L(zhǎng)度不等。每一碼塊的嵌入位流可以被截?cái)喑砷L(zhǎng)度不等的位流，生成不同的位速率。的位流，生成不同的位速率。 “最佳最佳”的含義：的含義： 每一碼塊的嵌入位流應(yīng)該截?cái)嗟绞裁闯潭炔欧咸囟ǖ哪棵恳淮a塊的嵌入位流應(yīng)該截?cái)嗟绞裁闯潭炔欧咸囟ǖ哪繕?biāo)位速率、失真限度或者其他衡量圖像質(zhì)量的指標(biāo)，也就標(biāo)位速率、失真限度或者其他衡量圖像質(zhì)量的指標(biāo)，也就是在給定一個(gè)目標(biāo)位速率的情況下，使重構(gòu)圖像的失真程是在給定一個(gè)目標(biāo)位速率的情況下，使重構(gòu)圖像的失真程度最小，度最小，David Taubman提出了一種認(rèn)為是提出了一種認(rèn)為是“最佳最佳”的的方法來截?cái)嗝恳粋€(gè)