Download presentation
Presentation is loading. Please wait.
1
第八章 小波轉換
2
8.1 前言 8.2 一維小波轉換 8.3 二維小波轉換 8.4 快速二維小波轉換 8.5 植基於快取記憶體的算法 8.7 作業
3
8.2 一維小波轉換 將一維的影像資料以方塊函數(Box Function)來表示 給定一維影像I如圖8.1所示。
8.2 一維小波轉換 將一維的影像資料以方塊函數(Box Function)來表示 給定一維影像I如圖8.1所示。 方塊函數 定義於圖8.2所示。 圖8.2 方塊函數 圖8.1 一維的影像
4
將一維的影像資料以方塊函數(Box Function) 來表示
有失真，但也可達到壓縮的效果。 圖8.3
5
有了 和 之後，I就可以表示成 和 的線性組合。
(a) (b) 圖 和 有了 和 之後，I就可以表示成 和 的線性組合。 圖8.5
6
的基底向量 對 而言，任一區塊函數可定義為 (8.1) 其正交性可利用滿足下式來檢定
7
基底向量為小波集 。以圖8.4為例，其小波集如圖8.6所示。
考慮 ，找一個和 正交且互補的新向量空間 。 形成 的基底向量表示為 、 、 和 。我們稱這些 基底向量為小波集 。以圖8.4為例，其小波集如圖8.6所示。 (a) (b) (a) (b) 圖 和 圖 和 的基底向量 對 而言，其基底向量可定義為 (8.2)
8
將一維的影像資料以 和 的線性組合來表示 給定一維影像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。 所以
9
單位正交基底向量的轉換 由 可得知 、 、 和 並非單位正交基底向量。 若將式(8.1)的 和式(8.2)的 做如下的改變， 即能使其成為單位正交基底，亦可簡化內積的相關計算。 (8.3)
10
已在小波轉換中變為較小的係數，這帶來了壓縮效果。 圖8.7可用來表示這種向量基底層層擴展後的關係。
向量基底的擴展 從 轉換成 ，可以發現 I 中的較大係數 已在小波轉換中變為較小的係數，這帶來了壓縮效果。 圖8.7可用來表示這種向量基底層層擴展後的關係。 圖8.7 不同向量基底的層層擴展
11
一維小波轉換的模擬 (a) 原始I。 (b) 第一步 (c) 第二步 (d) 第三步 圖8.8 一個一維WT模擬例子
12
8.3 二維小波轉換 將一維小波轉換擴展成二維小波轉換 利用張量乘積的概念我們可以將 的基底向量 和 擴展成二維轉換所需的四個基底向量：
13
二維小波基底 (a) (b) (c) (d) 圖 、 、 和
14
二維小波基底 利用函數的表示法， 、 、 和 可表示為 (8.4) 依照前一節的原理，若二維影像為 ，則
15
利用張量乘積的概念可將 的基底向量 、 、 和 建構成 、 、 和 四個基底向量，如圖8.10所示。
在 上利用張量乘積來建構相關的基底向量 利用張量乘積的概念可將 的基底向量 、 、 和 建構成 、 、 和 四個基底向量，如圖8.10所示。 圖8.10 張量乘積建構的四個基底向量
16
二維小波轉換的模擬 圖8.11 輸入的影像 圖8.12 行方向的小波轉換 圖8.13 列方向的小波轉換 圖8.14 L和H二個頻帶
圖8.15 四個頻帶示意圖
17
影像經二間段小波轉換後，可得7個頻帶，如圖8.16所示。
二階段的小波轉換 影像經二間段小波轉換後，可得7個頻帶，如圖8.16所示。 圖8.17和圖8.18為Lena影像及其經二階段小波轉換後的結果。 圖8.16 七個頻帶示意圖 圖8.17 輸入的影像 圖8.18 二階段小波轉換後的結果
18
快速小波轉換 以9/7濾波器及迴積式算法進行小波轉換 令二維影像X表示如下，其中X的大小為 n=2pq 。
19
9/7濾波器所對應的矩陣可表示為 對X進行WT，相當於計算 其中 (8.5)
20
以上昇法(Lifting Method) 進行小波轉換
在上昇法中，我們不直接計算 ，而是計算
21
以SCLA (Spatial Combinative Lifting Algorithm) 進行小波轉換
(8.6) 式(8.6)的計算順序為 、 、 、 和 首先要計算 ，得先算 。假設對 而言，滿足 我們由A矩陣的特殊結構，可得知矩陣的偶數行上的元素和矩陣上同位置的元素具有同樣的值，也就是
22
檢查R矩陣的奇數行上的元素，可得知 已經算出了 ，再來計算 ，我們會得到 (8.7)
23
SCLA 在計算上的複雜度 、 、 和 皆需要 乘法。 存在下列四個等式 使用二個for迴圈，即可以完成 的計算，共需要 個乘法。 綜合 以上分析，SCLA的乘法需求量為 ， 而迴積式算法所需的乘法數量約為 。
24
8.4 植基於快取記憶體的算法 以CSCLA 法進行小波轉換 令S(M)代表矩陣M牽涉的符號，而I(M)代表矩陣的I註標範圍，例如：
25
CSCLA 法的執行步驟(1) 為了配合快取記憶體， 我們將影像切割成許多區塊列而每一個區塊列又可切割成許多區塊。區塊的大小可依據快取記憶體的大小來決定。假設在第一區塊列中的第一區塊之大小定為3737，第i個區塊的大小定為3732，2i n/37，這裏影像的大小為mn。最後一個區塊大小定為3727。 我們接著把X[0…36,0…36]讀入第一個區塊，這時我們有I(M)=[0…36,0…36] 和 從式(8.7)的資料相依關係，計算完部分YA和YB後，我們可得下列組態變化
26
CSCLA 法的執行步驟(2) 利用與前一個步驟相同的方式，計算完部分YC、YD、YE後，可得下列組態變化 。 至此，我們檢查最後組態的左上方，可得知Y[0…31,0…31]已可輸 出 。這時得把最後組態之最後五列資料傳出去，以方便在第二區 塊列使用。
![CSCLA 法的執行步驟(2) 利用與前一個步驟相同的方式，計算完部分YC、YD、YE後，可得下列組態變化 。 至此，我們檢查最後組態的左上方，可得知Y[0…31,0…31]已可輸. 出 。這時得把最後組態之最後五列資料傳出去，以方便在第二區.](http://slidesplayer.com/slide/15960008/88/images/26/CSCLA+%E6%B3%95%E7%9A%84%E5%9F%B7%E8%A1%8C%E6%AD%A5%E9%A9%9F%282%29+%E5%88%A9%E7%94%A8%E8%88%87%E5%89%8D%E4%B8%80%E5%80%8B%E6%AD%A5%E9%A9%9F%E7%9B%B8%E5%90%8C%E7%9A%84%E6%96%B9%E5%BC%8F%EF%BC%8C%E8%A8%88%E7%AE%97%E5%AE%8C%E9%83%A8%E5%88%86YC%E3%80%81YD%E3%80%81YE%E5%BE%8C%EF%BC%8C%E5%8F%AF%E5%BE%97%E4%B8%8B%E5%88%97%E7%B5%84%E6%85%8B%E8%AE%8A%E5%8C%96+%E3%80%82+%E8%87%B3%E6%AD%A4%EF%BC%8C%E6%88%91%E5%80%91%E6%AA%A2%E6%9F%A5%E6%9C%80%E5%BE%8C%E7%B5%84%E6%85%8B%E7%9A%84%E5%B7%A6%E4%B8%8A%E6%96%B9%EF%BC%8C%E5%8F%AF%E5%BE%97%E7%9F%A5Y%5B0%E2%80%A631%2C0%E2%80%A631%5D%E5%B7%B2%E5%8F%AF%E8%BC%B8.+%E5%87%BA+%E3%80%82%E9%80%99%E6%99%82%E5%BE%97%E6%8A%8A%E6%9C%80%E5%BE%8C%E7%B5%84%E6%85%8B%E4%B9%8B%E6%9C%80%E5%BE%8C%E4%BA%94%E5%88%97%E8%B3%87%E6%96%99%E5%82%B3%E5%87%BA%E5%8E%BB%EF%BC%8C%E4%BB%A5%E6%96%B9%E4%BE%BF%E5%9C%A8%E7%AC%AC%E4%BA%8C%E5%8D%80..jpg "塊列使用。")
27
CSCLA 法的執行步驟(3) 將最後組態中最後五行資料移到矩陣M中前五行 ，再讀入 X[0…36,37…68]到M的最後32行中。 於是，我們得到 I(M)=[0…36,32…68]和
![CSCLA 法的執行步驟(3) 將最後組態中最後五行資料移到矩陣M中前五行 ，再讀入 X[0…36,37…68]到M的最後32行中。 於是，我們得到 I(M)=[0…36,32…68]和](http://slidesplayer.com/slide/15960008/88/images/27/CSCLA+%E6%B3%95%E7%9A%84%E5%9F%B7%E8%A1%8C%E6%AD%A5%E9%A9%9F%283%29+%E5%B0%87%E6%9C%80%E5%BE%8C%E7%B5%84%E6%85%8B%E4%B8%AD%E6%9C%80%E5%BE%8C%E4%BA%94%E8%A1%8C%E8%B3%87%E6%96%99%E7%A7%BB%E5%88%B0%E7%9F%A9%E9%99%A3M%E4%B8%AD%E5%89%8D%E4%BA%94%E8%A1%8C+%EF%BC%8C%E5%86%8D%E8%AE%80%E5%85%A5+X%5B0%E2%80%A636%2C37%E2%80%A668%5D%E5%88%B0M%E7%9A%84%E6%9C%80%E5%BE%8C32%E8%A1%8C%E4%B8%AD%E3%80%82+%E6%96%BC%E6%98%AF%EF%BC%8C%E6%88%91%E5%80%91%E5%BE%97%E5%88%B0+I%28M%29%3D%5B0%E2%80%A636%2C32%E2%80%A668%5D%E5%92%8C.jpg "CSCLA 法的執行步驟(3) 將最後組態中最後五行資料移到矩陣M中前五行 ，再讀入 X[0…36,37…68]到M的最後32行中。 於是，我們得到 I(M)=[0…36,32…68]和")
28
CSCLA 法的執行步驟(4) 利用與前一個步驟相同的方式，我們也可得到以下五個組態 這時最終的Y[0…31,32…63]也可輸出。仿照類似的做法，我們可依序得到Y[0…31,32k…32k+31]，2 k n/32-2。
29
CSCLA 法的執行步驟(5) 針對第一區塊列，我們只剩下最後一個3727的區塊待完成。 首先我也是將矩陣M的最後五行移到M的前五行 ， 再將 X[0…36,n-27…n-1]移入M的最後27行。這時，我們有 I(M)=[0…36,n-32…n-1]和
![CSCLA 法的執行步驟(5) 針對第一區塊列，我們只剩下最後一個3727的區塊待完成。 首先我也是將矩陣M的最後五行移到M的前五行 ， 再將. X[0…36,n-27…n-1]移入M的最後27行。這時，我們有.](http://slidesplayer.com/slide/15960008/88/images/29/CSCLA+%E6%B3%95%E7%9A%84%E5%9F%B7%E8%A1%8C%E6%AD%A5%E9%A9%9F%285%29+%E9%87%9D%E5%B0%8D%E7%AC%AC%E4%B8%80%E5%8D%80%E5%A1%8A%E5%88%97%EF%BC%8C%E6%88%91%E5%80%91%E5%8F%AA%E5%89%A9%E4%B8%8B%E6%9C%80%E5%BE%8C%E4%B8%80%E5%80%8B37%EF%82%B427%E7%9A%84%E5%8D%80%E5%A1%8A%E5%BE%85%E5%AE%8C%E6%88%90%E3%80%82+%E9%A6%96%E5%85%88%E6%88%91%E4%B9%9F%E6%98%AF%E5%B0%87%E7%9F%A9%E9%99%A3M%E7%9A%84%E6%9C%80%E5%BE%8C%E4%BA%94%E8%A1%8C%E7%A7%BB%E5%88%B0M%E7%9A%84%E5%89%8D%E4%BA%94%E8%A1%8C+%EF%BC%8C+%E5%86%8D%E5%B0%87.+X%5B0%E2%80%A636%2Cn-27%E2%80%A6n-1%5D%E7%A7%BB%E5%85%A5M%E7%9A%84%E6%9C%80%E5%BE%8C27%E8%A1%8C%E3%80%82%E9%80%99%E6%99%82%EF%BC%8C%E6%88%91%E5%80%91%E6%9C%89..jpg "I(M)=[0…36,n-32…n-1]和.")
30
CSCLA 法的執行步驟(6) 最後，我們可以得到五個組態變化如下所示
31
8.7 作業 習題一： 給定一維影像I=(2,6,1,7)，請將I表示成 、 、 和 的 線性組合。 習題二：
請自行給定一張影像，並利用三階段的Harr小波轉換將該輸入 影像進行小波轉換。
Similar presentations
