1、2002年10月9日,2002秋季學(xué)期網(wǎng)上課程多媒體技術(shù)基礎(chǔ)與應(yīng)用(multimedia fundamentals and applications)(face to face 2 of 4),林 福 宗 智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室 l 2002年10月9日,2002年10月9日,小波變換與應(yīng)用,一、小波變換 1.小波 2.小波變換 3. 離散小波變換 二、haar小波變換 1.哈爾函數(shù) 2.求均值和差值 3. 哈爾變換的特性 4.一維哈爾小波變換 5. 二維哈爾小波變換 三、閱讀和練習(xí)作業(yè),2002年10月9日,一、wavelet transform,小波分析是近十幾年才發(fā)展起來并迅速應(yīng)用

2、到圖像處理和語音分析等眾多領(lǐng)域的一種數(shù)學(xué)工具。它是繼110多年前的傅立葉(joseph fourier)分析之后的一個(gè)重大突破，無論是對(duì)古老的自然學(xué)科還是對(duì)新興的高新技術(shù)應(yīng)用學(xué)科都產(chǎn)生了強(qiáng)烈沖擊。 小波理論是應(yīng)用數(shù)學(xué)的一個(gè)新領(lǐng)域。要深入理解小波理論需要用到比較多的數(shù)學(xué)知識(shí)。本教學(xué)提綱企圖從工程應(yīng)用角度出發(fā)，用比較直觀的方法來介紹小波變換和它的應(yīng)用，為讀者深入研究小波理論和應(yīng)用提供一些背景材料,2002年10月9日,1. what is wavelet,一種函數(shù) 具有有限的持續(xù)時(shí)間、突變的頻率和振幅 波形可以是不規(guī)則的，也可以是不對(duì)稱的 在整個(gè)時(shí)間范圍里的幅度平均值為零 比較正弦波,2002年1

3、0月9日,部分小波波形,2002年10月9日,小波的定義,wavelets are a class of a functions used to localize a given function in both space and scaling. a family of wavelets can be constructed from a function , sometimes known as a mother wavelet, which is confined in a finite interval. daughter wavelets are then formed by tr

4、anslation (b) and contraction (a). wavelets are especially useful for compressing image data, since a wavelet transform has properties which are in some ways superior to a conventional fourier transform.,2002年10月9日,an individual wavelet can be defined by,2002年10月9日,2. wavelet transform,老課題函數(shù)的表示方法 新方

5、法fourier haar wavelet transform,2002年10月9日,(1) 1807: joseph fourier,傅立葉理論指出，一個(gè)信號(hào)可表示成一系列正弦和余弦函數(shù)之和，叫做傅立葉展開式。 用傅立葉表示一個(gè)信號(hào)時(shí)，只有頻率分辨率而沒有時(shí)間分辨率，這就意味我們可以確定信號(hào)中包含的所有頻率，但不能確定具有這些頻率的信號(hào)出現(xiàn)在什么時(shí)候。 為了繼承傅立葉分析的優(yōu)點(diǎn)，同時(shí)又克服它的缺點(diǎn)，人們一直在尋找新的方法。,2002年10月9日,傅立葉變換的定義：a mathematical description of the relationship between functions

6、of time and corresponding functions of frequency; a map for converting from one domain to the other. for example, if we have a signal that is a function of time-an impulse response- then the fourier transform will convert that time domain data into frequency data, for example, a frequency response.

7、(,2002年10月9日,(2) 1910: alfred haar發(fā)現(xiàn)haar小波,哈爾(alfred haar)對(duì)在函數(shù)空間中尋找一個(gè)與傅立葉類似的基非常感興趣。 1909年他發(fā)現(xiàn)了小波，1910年被命名為haar wavelets 他最早發(fā)現(xiàn)和使用了小波。,2002年10月9日,(3) 1945: gabor提出stft,20世紀(jì)40年代gabor開發(fā)了stft (short time fourier transform) stft的時(shí)間-頻率關(guān)系圖,2002年10月9日,(4) 1980: morlet提出了cwt,cwt (continuous wavelet transform)

8、20世紀(jì)70年代，當(dāng)時(shí)在法國(guó)石油公司工作的年輕的地球物理學(xué)家jean morlet提出了小波變換wt(wavelet transform)的概念。 20世紀(jì)80年代,從stft開發(fā)了cwt：,2002年10月9日,definition - basis functions: a set of linearly independent functions that can be used (e.g., as a weighted sum) to construct any given signal.,where: a = scale variable 縮放因子 k = time shift 時(shí)間平

9、移 h* = wavelet function 小波函數(shù) 用y = scaled (dilated) and shifted (translated) mother wavelet function, 在cwt中，scale和position是連續(xù)變化的,2002年10月9日,縮放(scaled)的概念,例1：正弦波的算法,2002年10月9日,縮放(scaled)的概念(續(xù)),例2：小波的縮放,2002年10月9日,平移(translation)的概念,2002年10月9日,(5) cwt的變換過程,可分成如下5個(gè)步驟 步驟1: 把小波 和原始信號(hào) 的開始部分進(jìn)行比較 步驟2: 計(jì)算系數(shù)c

10、。該系數(shù)表示該部分信號(hào)與小波的近似程度。系數(shù) c 的值越高表示信號(hào)與小波越相似，因此系數(shù)c 可以反映這種波形的相關(guān)程度 步驟3: 把小波向右移，距離為 ，得到的小波函數(shù)為 ，然后重復(fù)步驟1和2。再把小波向右移，得到小波 ，重復(fù)步驟1和2。按上述步驟一直進(jìn)行下去，直到信號(hào) 結(jié)束 步驟4: 擴(kuò)展小波 ，例如擴(kuò)展一倍，得到的小波函數(shù)為 步驟5: 重復(fù)步驟14,2002年10月9日,(a) 二維圖,2002年10月9日,(b) 三維圖 連續(xù)小波變換分析圖,2002年10月9日,(6) 三種變換的比較,2002年10月9日,(7) 1984: subband coding (burt and adels

11、on),sbc (subband coding)的基本概念：把信號(hào)的頻率分成幾個(gè)子帶，然后對(duì)每個(gè)子帶分別進(jìn)行編碼，并根據(jù)每個(gè)子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù) 20世紀(jì)70年代，子帶編碼開始用在語音編碼上 20世紀(jì)80年代中期開始在圖像編碼中使用 1986年woods, j. w.等人曾經(jīng)使用一維正交鏡像濾波器組(quadrature mirror filterbanks，qmf)把信號(hào)的頻帶分解成4個(gè)相等的子帶,2002年10月9日,圖(a) 正交鏡像濾波器(qmf),2002年10月9日,圖中的符號(hào) 表示頻帶降低1/2，hh表示頻率最高的子帶，ll表示頻率最低的子帶。這個(gè)過程可以重復(fù)，直

12、到符合應(yīng)用要求為止。這樣的濾波器組稱為分解濾波器樹(decomposition filter trees),圖(b) 表示其相應(yīng)的頻譜,2002年10月9日,(8) 20世紀(jì)80年代,mallat, meyer等人提出multiresolution theory 法國(guó)科學(xué)家y.meyer創(chuàng)造性地構(gòu)造出具有一定衰減性的光滑函數(shù)，他用縮放(dilations)與平移(translations)均為 2的j次冪的倍數(shù)構(gòu)造了平方可積的實(shí)空間l2(r)的規(guī)范正交基，使小波得到真正的發(fā)展 小波變換的主要算法由法國(guó)的科學(xué)家stephane mallat提出 s.mallat于1988年在構(gòu)造正交小波基時(shí)提出

13、了多分辨率分析(multiresolution analysis)的概念, 從空間上形象地說明了小波的多分辨率的特性 提出了正交小波的構(gòu)造方法和快速算法，叫做mallat算法。該算法統(tǒng)一了在此之前構(gòu)造正交小波基的所有方法，它的地位相當(dāng)于快速傅立葉變換在經(jīng)典傅立葉分析中的地位。,2002年10月9日,小波分解得到的圖像,2002年10月9日,(9)著名科學(xué)家,inrid daubechies，ronald coifman和 victor wickerhauser等著名科學(xué)家 把這個(gè)小波理論引入到工程應(yīng)用方面做出了極其重要的貢獻(xiàn) inrid daubechies于1988年最先揭示了小波變換和濾波

14、器組(filter banks)之間的內(nèi)在關(guān)系，使離散小波分析變成為現(xiàn)實(shí) 在信號(hào)處理中，自從s.mallat和inrid daubechies發(fā)現(xiàn)濾波器組與小波基函數(shù)有密切關(guān)系之后，小波在信號(hào)(如聲音信號(hào)，圖像信號(hào)等)處理中得到極其廣泛的應(yīng)用。 ,2002年10月9日,經(jīng)過十幾年的努力，這門學(xué)科的理論基礎(chǔ)已經(jīng)基本建立，并成為應(yīng)用數(shù)學(xué)的一個(gè)新領(lǐng)域。這門新興學(xué)科的出現(xiàn)引起了許多數(shù)學(xué)家和工程技術(shù)人員的極大關(guān)注，是國(guó)際科技界和眾多學(xué)術(shù)團(tuán)體高度關(guān)注的前沿領(lǐng)域。,小波變換,2002年10月9日,3. 離散小波變換,在計(jì)算連續(xù)小波變換時(shí)，實(shí)際上也是用離散的數(shù)據(jù)進(jìn)行計(jì)算的，只是所用的縮放因子和平移參數(shù)比較小而

15、已。不難想象，連續(xù)小波變換的計(jì)算量是驚人的。 為了解決計(jì)算量的問題，縮放因子和平移參數(shù)都選擇 ( j.0的整數(shù))的倍數(shù)。使用這樣的縮放因子和平移參數(shù)的小波變換叫做雙尺度小波變換(dyadic wavelet transform)，它是離散小波變換(discrete wavelet transform，dwt)的一種形式。,2002年10月9日,使用離散小波分析得到的小波系數(shù)、縮放因子和時(shí)間關(guān)系如圖所示。 圖(a)是20世紀(jì)40年代使用gabor開發(fā)的短時(shí)傅立葉變換(short time fourier transform，stft)得到的時(shí)間-頻率關(guān)系圖 圖(b)是20世紀(jì)80年代使用morl

16、et開發(fā)的小波變換得到的時(shí)間-縮放因子(反映頻率)關(guān)系圖。,3. 離散小波變換(續(xù)),2002年10月9日,離散小波變換分析圖,2002年10月9日,dwt變換方法,執(zhí)行離散小波變換的有效方法是使用濾波器 該方法是mallat在1988年開發(fā)的，叫做mallat算法 這種方法實(shí)際上是一種信號(hào)的分解方法，在數(shù)字信號(hào)處理中稱為雙通道子帶編碼 用濾波器執(zhí)行離散小波變換的概念如圖所示 s表示原始的輸入信號(hào)，通過兩個(gè)互補(bǔ)的濾波器產(chǎn)生a和d兩個(gè)信號(hào) a表示信號(hào)的近似值(approximations) d表示信號(hào)的細(xì)節(jié)值(detail),2002年10月9日,在許多應(yīng)用中，信號(hào)的低頻部分是最重要的，而高頻部

17、分起一個(gè)“添加劑”的作用。猶如聲音那樣，把高頻分量去掉之后，聽起來聲音確實(shí)是變了，但還能夠聽清楚說的是什么內(nèi)容。相反，如果把低頻部分去掉，聽起來就莫名其妙。在小波分析中，近似值是大的縮放因子產(chǎn)生的系數(shù)，表示信號(hào)的低頻分量。而細(xì)節(jié)值是小的縮放因子產(chǎn)生的系數(shù)，表示信號(hào)的高頻分量。,雙通道濾波過程,2002年10月9日,離散小波變換可以被表示成由低通濾波器和高通濾波器組成的一棵樹 原始信號(hào)通過這樣的一對(duì)濾波器進(jìn)行的分解叫做一級(jí)分解 信號(hào)的分解過程可以疊代，也就是說可進(jìn)行多級(jí)分解。 如果對(duì)信號(hào)的高頻分量不再分解，而對(duì)低頻分量連續(xù)進(jìn)行分解，就得到許多分辨率較低的低頻分量，形成如圖所示的一棵比較大的樹。這

18、種樹叫做小波分解樹(wavelet decomposition tree) 分解級(jí)數(shù)的多少取決于要被分析的數(shù)據(jù)和用戶的需要,小波分解樹,2002年10月9日,(a)信號(hào)分解 (b)系數(shù)結(jié)構(gòu) (c)小波分解樹 小波分解樹,2002年10月9日,小波包分解樹,小波分解樹表示只對(duì)信號(hào)的低頻分量進(jìn)行連續(xù)分解。如果不僅對(duì)信號(hào)的低頻分量連續(xù)進(jìn)行分解，而且對(duì)高頻分量也進(jìn)行連續(xù)分解，這樣不僅可得到許多分辨率較低的低頻分量，而且也可得到許多分辨率較低的高頻分量。這樣分解得到的樹叫做小波包分解樹(wavelet packet decomposition tree)，這種樹是一個(gè)完整的二進(jìn)制樹。,2002年10月9

19、日,三級(jí)小波包分解樹,圖表示的是一棵三級(jí)小波包分解樹。小波包分解方法是小波分解的一般化，可為信號(hào)分析提供更豐富和更詳細(xì)的信息。例如，小波包分解樹允許信號(hào)s表示為,2002年10月9日,降采樣過程,在使用濾波器對(duì)真實(shí)的數(shù)字信號(hào)進(jìn)行變換時(shí)，得到的數(shù)據(jù)將是原始數(shù)據(jù)的兩倍。例如，如果原始信號(hào)的數(shù)據(jù)樣本為1000個(gè)，通過濾波之后每一個(gè)通道的數(shù)據(jù)均為1000個(gè)，總共為2000個(gè)。 根據(jù)尼奎斯特(nyquist)采樣定理就提出了降采樣(downsampling)的方法，即在每個(gè)通道中每?jī)蓚€(gè)樣本數(shù)據(jù)取一個(gè)，得到的離散小波變換的系數(shù)(coefficient)分別用cd和ca表示,2002年10月9日,降采樣過程

20、,如圖所示。圖中的符號(hào) 表示降采樣。,2002年10月9日,小波變換的定義,a transform which localizes a function both in space and scaling and has some desirable properties compared to the fourier transform. the transform is based on a wavelet matrix, which can be computed more quickly than the analogous fourier matrix. an alternative

21、 to the discrete cosine transform (dct), the wavelet transform changes data, such as video data, into the sum of varying frequency wavelets. wavelets are sometimes used instead of the dct because they are more versatile and dont slow down as much with larger images as the dct does. intels indeo tech

22、nology makes use of wavelets. ,2002年10月9日,haar transform a one-dimensional transform which makes use of the haar functions. h- transform, haar function references haar, a. 1999-2003 wolfram research, inc. header. h-transform a two-dimensional generalization of the haar transform which is used for th

23、e compression of astronomical images. the algorithm consists of dividing the image into blocks of pixels, calling the pixels in the block , , , and . for each block, compute the four coefficients construct.,二、haar小波變換,2002年10月9日,1.哈爾函數(shù),哈爾基函數(shù)基函數(shù)是生成矢量空間v j 而定義的一組線性無關(guān)的函數(shù)，可以用來構(gòu)造任意給定的信號(hào)。也稱尺度函數(shù)(scaling fu

24、nction)，用符號(hào)v j 表示。 哈爾小波函數(shù)哈爾小波函數(shù)是生成矢量 的一組線性無關(guān)的函數(shù) ，用符號(hào)w j表示。矢量空間w j中的小波可用來表示一個(gè)函數(shù)在矢量空間 中不能表示的部分。 見多媒體技術(shù)基礎(chǔ)第2版，8.2,2002年10月9日,2. 哈爾變換原理,假設(shè)兩個(gè)信號(hào)的數(shù)值分別為a和b，計(jì)算它們的和與差，,從s和d重新獲得a和b，,2002年10月9日,哈爾變換舉例,【例】假設(shè)有一幅分辨率只有4個(gè)像素 的一維圖像，對(duì)應(yīng)的像素值或者叫做圖像位置的系數(shù)分別為： 9 7 3 5計(jì)算它的哈爾小波變換系數(shù) 步驟1：求均值(averaging)。計(jì)算相鄰像素對(duì)的平均值，得到一幅分辨率比較低的新圖像，

25、它的像素?cái)?shù)目變成了2個(gè)，即新的圖像的分辨率是原來的1/2，相應(yīng)的像素值為：8 4,2002年10月9日,哈爾變換舉例(續(xù)),步驟2：求差值(differencing)用2個(gè)像素表示這幅圖像時(shí)，圖像的信息已經(jīng)部分丟失。為了能夠從由2個(gè)像素組成的圖像重構(gòu)出由4個(gè)像素組成的原始圖像，就需要存儲(chǔ)一些圖像的細(xì)節(jié)系數(shù)(detail coefficient)，以便在重構(gòu)時(shí)找回丟失的信息。原始圖像可用下面的兩個(gè)平均值和兩個(gè)細(xì)節(jié)系數(shù)表示，8 4 1 -1 步驟3：重復(fù)步驟1和2把由第一步分解得到的圖像進(jìn)一步分解成分辨率更低的圖像和細(xì)節(jié)系數(shù)。在這個(gè)例子中，分解到最后，就用一個(gè)像素的平均值6和三個(gè)細(xì)節(jié)系數(shù)2,1和1

26、表示整幅圖像：6 2 1 -1,2002年10月9日,哈爾變換過程,把由4像素組成的一幅圖像用一個(gè)平均像素值和三個(gè)細(xì)節(jié)系數(shù)表示 這個(gè)過程就叫做哈爾小波變換(haar wavelet transform)，也稱哈爾小波分解(haar wavelet decomposition) 這個(gè)概念可以推廣到使用其他小波基的變換,2002年10月9日,3. 哈爾變換的特性,從這個(gè)例子中我們可以看到： 變換過程中沒有丟失信息，因?yàn)槟軌驈乃涗浀臄?shù)據(jù)中重構(gòu)出原始圖像。 對(duì)這個(gè)給定的變換，我們可以從所記錄的數(shù)據(jù)中重構(gòu)出各種分辨率的圖像。例如，在分辨率為1的圖像基礎(chǔ)上重構(gòu)出分辨率為2的圖像，在分辨率為2的圖像基礎(chǔ)上

27、重構(gòu)出分辨率為4的圖像 通過變換之后產(chǎn)生的細(xì)節(jié)系數(shù)的幅度值比較小，這就為圖像壓縮提供了一種途徑。例如，去掉一些微不足道的細(xì)節(jié)系數(shù)并不影響對(duì)重構(gòu)圖像的理解,2002年10月9日,4. 一維哈爾小波變換,求均值和差值的過程實(shí)際上就是一維小波變換的過程，現(xiàn)在用數(shù)學(xué)方法重新描述小波變換的過程,2002年10月9日,(1) 哈爾基函數(shù),基函數(shù)是一組線性無關(guān)的函數(shù)，可以用來構(gòu)造任意給定的信號(hào), 如用基函數(shù)的加權(quán)和表示。定義了基和矢量空間，就可以把由2j 個(gè)像素組成的一維圖像看成為矢量空間 中的一個(gè)矢量。 最簡(jiǎn)單的基函數(shù)是哈爾基函數(shù)(haar basis function)。哈爾基函數(shù)在1909年提出，它是

28、由一組分段常值函數(shù)(piecewise-constant function)組成的函數(shù)集。這個(gè)函數(shù)集定義在半開區(qū)間 上，每一個(gè)分段常值函數(shù)的數(shù)值在一個(gè)小范圍里是“1”，其他地方為“0” 以圖像為例并使用線性代數(shù)中的矢量空間來說明哈爾基函數(shù)。,2002年10月9日,這4個(gè)常值函數(shù)就是構(gòu)成矢量空間v 2的基,哈爾基函數(shù)(續(xù)1),2002年10月9日,哈爾基函數(shù)(續(xù)2),為了表示矢量空間中的矢量，每一個(gè)矢量空間v j 都需要定義一個(gè)基(basis) 為生成矢量空間 而定義的基函數(shù)也叫做尺度函數(shù)(scaling function)，這種函數(shù)通常用符號(hào) 表示。 哈爾基函數(shù)定義為,2002年10月9日,哈

29、爾基函數(shù)(續(xù)3),哈爾基尺度函數(shù) 定義為,其中，j 為尺度因子，改變j 使函數(shù)圖形縮小或者放大；i為平移參數(shù)，改變i使函數(shù)沿軸方向平移。,空間矢量v j定義為,其中，表示線性生成(linear span),2002年10月9日,(2) 哈爾小波函數(shù),小波函數(shù)通常用 表示。與框函數(shù)相對(duì)應(yīng)的小波稱為基本哈爾小波函數(shù)(haar wavelet functions)，并由下式定義，,哈爾小波尺度函數(shù) 定義為，,2002年10月9日,哈爾小波函數(shù)(續(xù)1),用小波函數(shù)構(gòu)成的矢量空間用w j表示為，,根據(jù)哈爾小波函數(shù)的定義，可以寫出生成，w 0,w 1和w 2 等矢量空間的小波函數(shù),其中，sp表示線性生成；

30、j為尺度因子，改變j 使函數(shù)圖形縮小或者放大；i為平移參數(shù)，改變i 使函數(shù)沿軸方向平移,2002年10月9日,哈爾小波函數(shù)(續(xù)2),生成矢量空間w 2 的哈爾小波：,2002年10月9日,哈爾小波函數(shù)(續(xù)3),生成矢量空間w 2 的哈爾小波,2002年10月9日,(3) 哈爾小波變換過程,(1) 用v2 中的哈爾基表示 圖像9 7 3 5有2j =22=4個(gè)像素，因此可以用生成矢量空間中的框基函數(shù)的線性組合表示，,其中的系數(shù) 是4個(gè)正交的像素值9 7 3 5，因此，,2002年10月9日,哈爾小波變換過程(續(xù)1),圖i(x)用v2中的哈爾基表示,2002年10月9日,用v 0, w 0和w1中

31、的函數(shù)表示圖像 生成矢量空間v 0的基函數(shù)為 ，生成矢量空間w 0的小波函數(shù)為 ，生成矢量空間w1的小波函數(shù)為 和 ，根據(jù),哈爾小波變換過程(續(xù)2),i(x)可表示成,2002年10月9日,其中，4個(gè)系數(shù) ， ， 和 就是原始圖像通過哈爾小波變換所得到的系數(shù)，用來表示整幅圖像的平均值和不同分辨率下的細(xì)節(jié)系數(shù)。4個(gè)函數(shù) , , 和 就是構(gòu)成空間v2的基。,哈爾小波變換過程(續(xù)3),用圖表示為,2002年10月9日,一幅圖像是一個(gè)二維的數(shù)據(jù)陣列，進(jìn)行小波變換時(shí)可以對(duì)陣列的每一行進(jìn)行變換，然后對(duì)行變換之后的陣列的每一列進(jìn)行變換，最后對(duì)經(jīng)過變換之后的圖像數(shù)據(jù)陣列進(jìn)行編碼 1. 求均值與求差值使用求均值

32、和求差值的方法，對(duì)矩陣的每一行進(jìn)行計(jì)算 3. 使用線性代數(shù)由于圖像可用矩陣表示，使用n個(gè)矩陣m1, m2，和mn 同樣可以對(duì)圖像矩陣進(jìn)行求平均值和求差值。這n個(gè)矩陣分別是第一、第二和第n次分解圖像時(shí)所構(gòu)成的矩陣,5. 二維哈爾小波變換,2002年10月9日,二維哈爾小波變換(續(xù)1),用小波對(duì)圖像進(jìn)行變換有兩種方法，一種叫做標(biāo)準(zhǔn)分解(standard decomposition)，另一種叫做非標(biāo)準(zhǔn)分解(nonstandard decomposition)。標(biāo)準(zhǔn)分解方法是指首先使用一維小波對(duì)圖像每一行的像素值進(jìn)行變換，產(chǎn)生每一行像素的平均值和細(xì)節(jié)系數(shù)，然后使用一維小波對(duì)這個(gè)經(jīng)過行變換的圖像的列進(jìn)行變換，產(chǎn)生這個(gè)圖像的平均值和細(xì)節(jié)系數(shù)。標(biāo)準(zhǔn)分解的過程如下，,2002年10月9日,procedure standarddecomposition(c: array 1. .