第八章 小波轉換

8.1 前言 8.2 一維小波轉換 8.3 二維小波轉換 8.4 快速二維小波轉換 8.5 植基於快取記憶體的算法 8.7 作業

8.2 一維小波轉換 將一維的影像資料以方塊函數(Box Function)來表示 給定一維影像I如圖8.1所示。 8.2 一維小波轉換 將一維的影像資料以方塊函數(Box Function)來表示 給定一維影像I如圖8.1所示。 方塊函數 定義於圖8.2所示。 圖8.2 方塊函數 圖8.1 一維的影像

將一維的影像資料以方塊函數(Box Function) 來表示 有失真，但也可達到壓縮的效果。 圖8.3

有了 和 之後，I就可以表示成 和 的線性組合。 (a) (b) 圖8.4 和 有了 和 之後，I就可以表示成 和 的線性組合。 圖8.5

的基底向量 對 而言，任一區塊函數可定義為 (8.1) 其正交性可利用滿足下式來檢定

基底向量為小波集 。以圖8.4為例，其小波集如圖8.6所示。 考慮 ，找一個和 正交且互補的新向量空間 。 形成 的基底向量表示為 、 、 和 。我們稱這些 基底向量為小波集 。以圖8.4為例，其小波集如圖8.6所示。 (a) (b) (a) (b) 圖8.4 和 圖8.6 和 的基底向量 對 而言，其基底向量可定義為 (8.2)

將一維的影像資料以 和 的線性組合來表示 給定一維影像I=(3,5,2,8)，利用 、 、 和 的線性組合可表示為 使用 、 、 和 的 線性組合則得到 其中a、b、c和d需滿足下式 解得a=(3+5)/2=4，b=(2+8)/2=5，c=(3-5)/2=-1，d=(2-8)/2=-3。 所以

單位正交基底向量的轉換 由 可得知 、 、 和 並非單位正交基底向量。 若將式(8.1)的 和式(8.2)的 做如下的改變， 即能使其成為單位正交基底，亦可簡化內積的相關計算。 (8.3)

已在小波轉換中變為較小的係數，這帶來了壓縮效果。 圖8.7可用來表示這種向量基底層層擴展後的關係。 向量基底的擴展 從 轉換成 ，可以發現 I 中的較大係數 已在小波轉換中變為較小的係數，這帶來了壓縮效果。 圖8.7可用來表示這種向量基底層層擴展後的關係。 圖8.7 不同向量基底的層層擴展

一維小波轉換的模擬 (a) 原始I。 (b) 第一步 (c) 第二步 (d) 第三步 圖8.8 一個一維WT模擬例子

8.3 二維小波轉換 將一維小波轉換擴展成二維小波轉換 利用張量乘積的概念我們可以將 的基底向量 和 擴展成二維轉換所需的四個基底向量：

二維小波基底 (a) (b) (c) (d) 圖8.9 、 、 和

二維小波基底 利用函數的表示法， 、 、 和 可表示為 (8.4) 依照前一節的原理，若二維影像為 ，則

利用張量乘積的概念可將 的基底向量 、 、 和 建構成 、 、 和 四個基底向量，如圖8.10所示。 在 上利用張量乘積來建構相關的基底向量 利用張量乘積的概念可將 的基底向量 、 、 和 建構成 、 、 和 四個基底向量，如圖8.10所示。 圖8.10 張量乘積建構的四個基底向量

二維小波轉換的模擬 圖8.11 輸入的影像 圖8.12 行方向的小波轉換 圖8.13 列方向的小波轉換 圖8.14 L和H二個頻帶 圖8.15 四個頻帶示意圖

影像經二間段小波轉換後，可得7個頻帶，如圖8.16所示。 二階段的小波轉換 影像經二間段小波轉換後，可得7個頻帶，如圖8.16所示。 圖8.17和圖8.18為Lena影像及其經二階段小波轉換後的結果。 圖8.16 七個頻帶示意圖 圖8.17 輸入的影像 圖8.18 二階段小波轉換後的結果

8.4 快速小波轉換 以9/7濾波器及迴積式算法進行小波轉換 令二維影像X表示如下，其中X的大小為 n=2pq 。

9/7濾波器所對應的矩陣可表示為 對X進行WT，相當於計算 其中 (8.5)

以上昇法(Lifting Method) 進行小波轉換 在上昇法中，我們不直接計算 ，而是計算

以SCLA (Spatial Combinative Lifting Algorithm) 進行小波轉換 (8.6) 式(8.6)的計算順序為 、 、 、 和 首先要計算 ，得先算 。假設對 而言，滿足 我們由A矩陣的特殊結構，可得知矩陣的偶數行上的元素和矩陣上同位置的元素具有同樣的值，也就是

檢查R矩陣的奇數行上的元素，可得知 已經算出了 ，再來計算 ，我們會得到 (8.7)

SCLA 在計算上的複雜度 、 、 和 皆需要 乘法。 存在下列四個等式 使用二個for迴圈，即可以完成 的計算，共需要 個乘法。 綜合 以上分析，SCLA的乘法需求量為 ， 而迴積式算法所需的乘法數量約為 。

8.4 植基於快取記憶體的算法 以CSCLA 法進行小波轉換 令S(M)代表矩陣M牽涉的符號，而I(M)代表矩陣的I註標範圍，例如：

CSCLA 法的執行步驟(1) 為了配合快取記憶體， 我們將影像切割成許多區塊列而每一個區塊列又可切割成許多區塊。區塊的大小可依據快取記憶體的大小來決定。假設在第一區塊列中的第一區塊之大小定為3737，第i個區塊的大小定為3732，2i n/37，這裏影像的大小為mn。最後一個區塊大小定為3727。 我們接著把X[0…36,0…36]讀入第一個區塊，這時我們有I(M)=[0…36,0…36] 和 從式(8.7)的資料相依關係，計算完部分YA和YB後，我們可得下列組態變化

CSCLA 法的執行步驟(2) 利用與前一個步驟相同的方式，計算完部分YC、YD、YE後，可得下列組態變化 。 至此，我們檢查最後組態的左上方，可得知Y[0…31,0…31]已可輸 出 。這時得把最後組態之最後五列資料傳出去，以方便在第二區 塊列使用。

CSCLA 法的執行步驟(3) 將最後組態中最後五行資料移到矩陣M中前五行 ，再讀入 X[0…36,37…68]到M的最後32行中。 於是，我們得到 I(M)=[0…36,32…68]和

CSCLA 法的執行步驟(4) 利用與前一個步驟相同的方式，我們也可得到以下五個組態 這時最終的Y[0…31,32…63]也可輸出。仿照類似的做法，我們可依序得到Y[0…31,32k…32k+31]，2  k  n/32-2。

CSCLA 法的執行步驟(5) 針對第一區塊列，我們只剩下最後一個3727的區塊待完成。 首先我也是將矩陣M的最後五行移到M的前五行 ， 再將 X[0…36,n-27…n-1]移入M的最後27行。這時，我們有 I(M)=[0…36,n-32…n-1]和

CSCLA 法的執行步驟(6) 最後，我們可以得到五個組態變化如下所示

8.7 作業 習題一： 給定一維影像I=(2,6,1,7)，請將I表示成 、 、 和 的 線性組合。 習題二： 請自行給定一張影像，並利用三階段的Harr小波轉換將該輸入 影像進行小波轉換。