多媒體技術(shù)小波變換與數(shù)據(jù)壓縮

1、小波變換與數(shù)據(jù)壓縮主要內(nèi)容小波變換用于圖像壓縮的理由傅里葉變換窗口傅里葉變換小波變換的原理小波變換實(shí)例小波變換與數(shù)據(jù)壓縮小波變換用于圖像壓縮的理由基于DCT (Discrete Cosine Transform)的壓縮標(biāo)準(zhǔn) JPEG MPEG-1 ,MPEG-2, H.264 DCT壓縮的優(yōu)點(diǎn)簡單、便于硬件實(shí)現(xiàn)圖像是分塊處理，沿塊的邊界方向相關(guān)性被破壞，出現(xiàn) artifacts"小波變換用于圖像壓縮的理由 DCT壓縮的缺點(diǎn)blocking傅里葉變換 信號表示多種方式信號的描述： 例如一個函數(shù)表達(dá)式，這就是信號的時(shí)域表示，傅里葉變換 1822年,傅里葉提出頻率的概念:通過傅里葉正變換將

2、信號在頻 域分解，獲得信號的頻譜，再通過反變換重建原始信號。 頻率仍然是傅里葉變換所定義。F（o）ejcotd（D傅里葉變換的特點(diǎn)具有頻域準(zhǔn)確定位，可分析信號能量在各個頻域成分中的分布 情況，最常用的、最廣泛的信號分析工具， 并且相關(guān)的理論研究已發(fā)展為一個重要的數(shù)學(xué)分支調(diào)和分 析。7傅里葉變換傅里葉變換的特點(diǎn)具有頻域準(zhǔn)確定位，可分析信號能量在各個頻域成分中的分布 情況，最常用的、最廣泛的信號分析工具， 并且相關(guān)的理論研究已發(fā)展為一個重要的數(shù)學(xué)分支調(diào)和分 析。9傅里葉變換傅里葉變換的特點(diǎn)具有頻域準(zhǔn)確定位，可分析信號能量在各個頻域成分中的分布 情況最常用的、最廣泛的信號分析工具 并且相關(guān)的理論研究

3、已發(fā)展為一個重要的數(shù)學(xué)分支調(diào)和分 析#傅里葉變換傅里葉變換的不足缺乏時(shí)間頻率的定位功能不適于非平穩(wěn)信號無法根據(jù)信號的特點(diǎn)自動調(diào)節(jié)時(shí)域和頻域的分辨率傅里葉變換的不足成為了推動尋找新變換的動力11窗口傅里葉變換 窗 口傅里葉變換(short time Fourier transform )1946年Gabor提出了短時(shí)傅里葉變換的概念，從而開始了非平穩(wěn)信號的時(shí)頻聯(lián)合分析G(w，t) = o f g(J t 疋八S#窗口傅里葉變換#窗口傅里葉變換f(0 =G(w,t )g(t- t )eJdwdt13窗口傅里葉變換 窗 口傅里葉變換(short time Fourier transform )Ak7

4、宀rtg(t-u)#窗口傅里葉變換 Gabor變換：時(shí)窗函數(shù)=Gauss函數(shù)時(shí)時(shí)窗函數(shù)的Fourier變換仍然是Gauss函數(shù)，保證了窗口傅立葉 變換在頻域內(nèi)也有局域化的功能。15窗口傅里葉變換 窗 口傅里葉變換(short time Fourier transform ) 時(shí)窗(Time Window) 頻窗(Frequency Window) 時(shí)窗函數(shù)g(t)的傅立葉變換G(0)二0(q) 頻窗屮心co codco / j|G(y)2cfo>R/ R頻窗半徑Ad> =g(q)217窗口傅里葉變換 窗 口傅里葉變換(short time Fourier transform )以上

5、定義知，g(t)和G(co)分別起著時(shí)窗和頻窗的作用，在時(shí)間 頻率坐標(biāo)系中，時(shí)窗和頻窗共同作用的結(jié)果就構(gòu)成了時(shí)頻 窗，這樣就從幾何上直觀地描述了時(shí)頻局部化。盡管窗式傅立葉變換能解決變換函數(shù)的局域化問題，但是，其 窗口的大小和形狀是固定的，即窗口面積不變，窗口沒有自適 應(yīng)性。 對于高頻的信息，時(shí)間間隔要相對的小，更好地確定峰值和斷 點(diǎn)，或者說需要用較窄的時(shí)域窗來反映信息的高頻成分。對于低頻譜的信息，時(shí)間間隔要相對的寬才能給出完整的信號 信息，或者說必須用較寬的時(shí)域窗來反映信息的低頻成分。19小波變換原理 小波變換的(wavelet transfoim )發(fā)展 20世紀(jì)80年代后期發(fā)展起來的小波變

6、換理論它是繼傅里葉(Joseph Fourier)分析后信號處理與分析的強(qiáng)大工 具無論是對古老的自然學(xué)科還是對新興的高新技術(shù)應(yīng)用學(xué)科都產(chǎn) 生了強(qiáng)烈沖擊。 小波理論是應(yīng)用數(shù)學(xué)的一個新領(lǐng)域。要深入理解小波理論需 要用到比較多的數(shù)學(xué)知識。從工程應(yīng)用角度出發(fā)，直觀的方法來介紹小波變換及其應(yīng)用， 為讀者深入研究小波理論和應(yīng)用提供一些背景材料 小波變換的(wavelet transfonn )發(fā)展 哈爾(Alfred Haar)對在函數(shù)空間中尋找一個與傅里葉類似的基非常感 興趣。 1909年他發(fā)現(xiàn)了小波，1910年被命名為Haar wavelets最早發(fā)現(xiàn)和使用了小波的名稱小波變換的(wavelet tr

7、ansfoim )發(fā)展20世紀(jì)70年代，當(dāng)時(shí)在法國石油公司工作的年輕的地球物理學(xué) 家Jean Morlet提出了小波變換CWT (continuous wavelet transform)的概念。法國科學(xué)家Y.Meyer創(chuàng)造性地構(gòu)造出具有一定衰減性的光滑函 數(shù),用縮放(dilations)與平移(translations)均為2的j次幕的倍數(shù)構(gòu)造了平方可積的實(shí)空間I?(R)的規(guī)范正交基，使小波得到真正的發(fā)展.S.Mallat于1988年在構(gòu)造正交小波基時(shí)提出了多分辨率分析 (multiresolution analysis)的概念，從空間上形象地說明了小波的 多分辨率的特性，提出了正交小波的構(gòu)

8、造方法和快速算法，叫 做Mallat算法。Mallat算法地位相當(dāng)于快速傅里葉變換在傅里葉分析中的地位。 小波變換的(wavelet transfonn )發(fā)展 1988年Inrid Daubechies最先揭示了小波變換和濾波器組(filter banks)之間的內(nèi)在關(guān)系 20世紀(jì)90年代中期，Sweldens提出了小波變換提升方案第二代小波變換,用于JPEG2000小波在信號(如聲音信號，圖像信號等)處理中得到極其廣泛的 應(yīng)用。23小波變換原理 小波變換的(wavelet transfonn )發(fā)展小波變換具有在不同尺度下保持時(shí)頻分析窗口面積不變性質(zhì)自動調(diào)節(jié)對信號分析的時(shí)寬和帶寬被譽(yù)為信號

9、分析的顯微鏡25小波變換原理 連續(xù)小波變換(continuous wavelet transform ) 小波(Wavelet (A small wave, a ripple)就是小的波形，所謂小，就是它具有衰減性，是存在于一 個較小區(qū)域的波。Fig.l Waves and Wavelets.#小波變換原理 連續(xù)小波變換變換(continuous wavelet transform )小波基函數(shù)小波變換原理小波變換原理傅立葉變換的幾個基函數(shù)示意(b)短時(shí)傅立葉變換的幾個基函數(shù)示意(c) 小波變換的幾個皐函數(shù)示意Fig. 2 Basic Functions for TouLier indo we

10、d Fouiier and Wavelet Transforms123小波變換原理#小波變換原理連續(xù)小波變換(continuous wavelet transform )小波正變換號（心）=/畑*/+3CJX田）.、一予+<» 4幾)忖f 0 -af 2叫dbda8小波反變換標(biāo)注： a = scale variable b= time shift一縮放因子時(shí)間平移在CWT中，縮放和平移是連續(xù)變化的29小波變換原理n01 連續(xù)小波變換(continuous wavelet transform ) 函數(shù)的伸縮Scale f(t) = sin ；a = I f=sin(2/) ； m

11、 = /(0 = sin(4f) ； a 二 連續(xù)小波變換(continuous wavelet transform )小波函數(shù)的伸縮Nonlinear mapping between scale factor and frequenc* Scaleq = I31小波變換原理小波變換原理 連續(xù)小波變換(continuous wavelet transform )AZ ="汀 l%(f)-GC1/2 /dt/叫(f)二Q叫#小波變換原理#小波變換原理時(shí)窗中心：小波的時(shí)窗中心是其母函數(shù)P的時(shí)窗中心乘刃 倍再平移Q個單位小波的匕)時(shí)窗寬度是其母函數(shù)0ZH時(shí)窗寬度的。倍。 連續(xù)小波變換(co

12、ntinuous wavelet transform )獷=f_QC3怦訂（Q）d/|屮儀60）| =33小波變換原理#小波變換原理1/2=-Dwa0I比血）L：1小波匕b 頻窗中心是其母函數(shù)0的頻窗中心的方倍小波務(wù)頻窗寬度是其母函數(shù)爐的頻窗寬度的1倍a 連續(xù)小波變換(continuous wavelet transform )Fig.3 Hi$senbeig Windows.用較對信號做高頻分析時(shí)，實(shí)際是用高頻小波對信號進(jìn)行 細(xì)致觀察用較大C對信號做低頻分析時(shí)，實(shí)際是用低頻小波對信號進(jìn)行 概貌觀察1S = (a/V) (勁=Az.Az)a連續(xù)小波變換(continuous wavelet t

13、ransform )部分小波波形仏縮披函數(shù)Heyer小波函數(shù)1A10.5I0.5JIA00-0.5-O.SI-505-55Hou縮蝕函數(shù)Hou小浜函數(shù)110.565-0.5-05.1C0.51C0.51 子帶編碼SBC (subband coding)：把信號的頻率分成幾個子帶，然后對每個子帶 分別進(jìn)行編碼，并根據(jù)每個子帶的重要性分配 不同的位數(shù)來表示數(shù)據(jù) 20世紀(jì)70年代，子帶編碼開始用于語音編碼20世紀(jì)80年代中期開始在圖像編碼中使用37小波變換原理離散小波變換垂直分析LL圖中的符號 表示頻帶降低1/2, HH表示頻率最高的子帶, LL表示頻率最低的子帶。這個過程可以重復(fù)，£到符

14、合 應(yīng)用要求為止。這樣的濾波器組稱為分解濾波器樹 (decomposition filter trees)離散小波變換只有離散，小波變換才能應(yīng)用離散的方式有很多離散小波變換的多分辨率分析 Mallat創(chuàng)立了多分辨率分析理論在多分辨率分析基礎(chǔ)上，Mallat提出了基于濾波器組實(shí)現(xiàn)信 號的小波正變換和反變換算法。執(zhí)行離散小波變換的有效 方法 Mallat 算法低通濾波器和高通濾波器構(gòu)成雙通道濾波口原始的輸入信號:S口兩個壬補(bǔ)的濾波器 A表示信號的近似值(approximations)D表示信號的細(xì)節(jié)值(detail)39小波變換原理 Mallat 算法低通濾波器和高通濾波器構(gòu)成小波分解樹口對低頻分

15、量連續(xù)分解LPF: low pass filterHPF: high pass filter Mallat 算法小波包分解樹口對低頻分量和高頻分量均連續(xù)分解 Mallat 算法下采樣過程口原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道 的數(shù)據(jù)均為1000個，總共為2000個。1000 個樣本1000個樣本1000 個樣本1000 個樣本 Mallat 算法下采樣過程口原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道 的數(shù)據(jù)均為1000個，總共為2000個。1000 個樣本100011個拝本 Mallat 算法下采樣過程口原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道 的數(shù)

16、據(jù)均為1000個，總共為2000個。1000 個樣本100011個拝本 Mallat 算法下采樣過程口原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道 的數(shù)據(jù)均為1000個，總共為2000個?？趫D中的符號 表示下采樣1000 個樣本1000個樣本1000 個樣本1000個拝本45小波變換實(shí)例 一維哈爾小波變換哈爾函數(shù)定義0<%<1其他47小波變換實(shí)例 一維哈爾小波變換哈爾函數(shù)定義其他0（兀）基函數(shù)口 一組線性無關(guān)的函數(shù)，以用來構(gòu)造任意給定 的信號 一維哈爾小波變換 哈爾基函數(shù)最簡單的基函數(shù)0/（兀）= 0（2丿兀一） 一維哈爾小波變換哈爾基函數(shù) 0/（兀）=0（2兀i）0&l

17、t;%<1/4其他1/2<%<3/4 其他1/4<%<1/2 其他 3/4<%<1 其他披形：L尿（對L _仏）1如1-仏）10十0 r un1/2 1<r un1/2 1 «)1/21 01)1/2 i51小波變換實(shí)例 一維哈爾小波變換 尺度函數(shù)口 0（兀）:尺度函數(shù)尺度函數(shù)張成的空間力 口 W的基的個數(shù)為00丿（兀）=0（2丿兀一從i = o,2 -1i =0丄，一1)45小波變換實(shí)例 一維哈爾小波變換小波函數(shù)口 g):與尺度函數(shù)對應(yīng)哈爾小波函數(shù)與哈爾函數(shù)相對應(yīng)1 3 0<%<1/2 i/(x) = < -1 當(dāng)

18、l/25xvl0 其他 一維哈爾小波變換小波函數(shù)口 0（兀）: 與尺度函數(shù)對應(yīng)哈爾小波函數(shù)當(dāng) 0 < x < 1/2當(dāng) 1/2 < x < 1其他與哈爾函數(shù)相對應(yīng)1屮（X）=卜10哈爾小波基函數(shù)i/j(%) =x-i = a、 -1) 一維哈爾小波變換小波函數(shù)口 0（兀）: 與尺度函數(shù)對應(yīng)哈爾小波函數(shù)與哈爾函數(shù)相對應(yīng)當(dāng) 0S<l/2 當(dāng) 1/2K1 其他哈爾小波基函數(shù)i/j (%) = y2Jx - i z =0<-9(27 -1)i49小波變換實(shí)例 一維哈爾小波變換小波基函數(shù)構(gòu)成的空間：WJ51小波變換實(shí)例#小波變換實(shí)例WJ = span#小波變換實(shí)例 一

19、維哈爾小波變換小波基函數(shù)構(gòu)成的空間：WJwj=span 一維哈爾小波變換小波基函數(shù)構(gòu)成的空間：WJ53小波變換實(shí)例WJ = span心0丄21#小波變換實(shí)例#小波變換實(shí)例”2=0 “° 一維哈爾小波變換生成矢量空間的哈爾小波基函數(shù)#小波變換實(shí)例#小波變換實(shí)例1阮(x) = < -101屮認(rèn)X)= V -100<<1/81/8<%<2/8其他4/8K5/85/8<x<6/8其他10;(x) = < _1010；(兀)彳T02/8<x<3/83/8<x<4/8其他6/8<<7/87/8<x<l

20、其他55小波變換實(shí)例#小波變換實(shí)例 一維哈爾小波變換生成矢量空間孫2的哈爾小波基函數(shù)#小波變換實(shí)例#小波變換實(shí)例聽（壬）1c?。︰1/21-11-11-1心）1/2;)11/2157小波變換實(shí)例 一維哈爾小波變換生成矢量空間孫2的哈爾小波基函數(shù)#小波變換實(shí)例#小波變換實(shí)例聽（壬）1c?。︰1/21-11-11-1心）1/2;)11/2159小波變換實(shí)例 一維哈爾小波變換實(shí)例圖像=9 7 3 5口像素個數(shù)：2丿=22=4 W中的哈爾基表示= 9 X I L冷（X）+ 7 x 1 L #（切 + 3 X 匚二I_診（勸+ 5 X 1 號 G）/（X）= 90（X）+ 7才（兀）+ 3°；

21、（兀）+ 5從（兀）小波變換實(shí)例 一維哈爾小波變換實(shí)例口 W中的哈爾基表示的一般形式口其中的系數(shù) 一維哈爾小波變換實(shí)例用卩0, W。和M中的函數(shù)表示圖像生成空間卩。的哈爾基函數(shù)為*（%）口生成空間的哈爾小波基函數(shù)為 必（兀）生成矢量空間M的哈爾小波基函數(shù)為猶（X）和亦（X） /（兀）可表示成/（兀）=cX M + 胡 M + 咖；（兀）+ d；0： （x）V2= W V1v' = v°v2 "。護(hù)川 一維哈爾小波變換實(shí)例/(X)= cfo W+qY)2 0)+<?了 ；(x)+c3 (x)I(x) =9 x I I+7 x I I 一維哈爾小波變換實(shí)例心）=力

22、亦）+審:（勸+俶（力+如3+4+ -XX 一維哈爾小波變換實(shí)例 心）=力亦）+c昇（兀）+陽亦）+苗»任）-XV2= W1 VXX一 2o一 2o o 1-1 1 o o-11 11o 1 - 2 o 一維哈爾小波變換實(shí)例 I（x）=莎；0）+盃山（兀）+必元（兀）+卜；（兀）O 二6 X1 1的）+2 XJ1r唏（對+1 X離G)+-1 XAzzr?。￢1 = wQ V0 V2 =u° w° M 一維哈爾小波變換實(shí)例X X X X6 2 1-1 一一 + + +V1 = W° V° V2 =u° M 一維哈爾小波變換實(shí)例口生成其中

23、，4個系數(shù)4蟲和疋就是原始圖像通過哈爾小 波變換所得到的系數(shù)，用來翁示整幅圖像的平均值和不同分 辨率下的細(xì)節(jié)系數(shù)。4個函數(shù)疏）（兀）必（兀），此（兀）和M（x）就是構(gòu) 成空間V2的基。65 一維哈爾小波變換哈爾小波變換的快速算法計(jì)算哈爾小波變換系數(shù)步驟1：求均值(averaging) o計(jì)算相鄰像素對的平均值，得到一幅分辨率比較 低的新圖像，它的像素?cái)?shù)目變成了2個，即新的圖像的分辨率是原來的1/2, 相應(yīng)的像素值為：8 4步驟2：求差值(differencing)用2個像素表示這幅圖像時(shí)，圖像的信息已經(jīng)部分丟失。為了能夠 從由2個像素組成的圖像重構(gòu)出由4個像素組成的原始圖像，就需要 存儲一些圖

24、像的細(xì)節(jié)系數(shù)(detail coefficient),以便在重構(gòu)時(shí)找 回丟失的信息。原始圖像可用下面的兩個平均值和兩個細(xì)節(jié)系數(shù)表 示，8 4 1 -1步9聚3重復(fù)步驟和'2把由第一步分解得到的圖像進(jìn)一步分解成分辨率更低的圖像和細(xì)節(jié)系數(shù)。 在這個例子中，分解到最后，就用一個像素的平均值6和三個細(xì)節(jié)系數(shù)2,1 和一1表示整幅圖像：6 21 -1#小波變換實(shí)例 一維哈爾小波變換分辨率平均值細(xì)節(jié)系數(shù)49 7 3 528 41 -1162該算法可以推廣到其他小波變換67二維哈爾小波變換圖像的二維變換#block of pixelsN 咽 block oftransform coefficient

25、s#u = Tuv= (T(u/)r= (T(Tu) ) = TuTr轉(zhuǎn)置后繼續(xù)對列實(shí)施變換相當(dāng)于對行實(shí)施變換69小波變換實(shí)例二維哈爾小波變換57例如64 2 3 61 60 6 764 2 3 61 60 6 7 57JM,02#小波變換實(shí)例02#小波變換實(shí)例= 64 2 3 61 60 6 7 57J-00 2丄0 020-)-020-020丄20 1 020 0 120 0-£2£'1丄2丄運(yùn)20 -20271小波變換實(shí)例02#小波變換實(shí)例= 33 32 33 32 31 -29 27 -25J02#小波變換實(shí)例二維哈爾小波變換例如33 32 33 32 31

26、 -29 27= 33 32 33 32 31 -29 27=32.5 32.5 0.5 0.5 31 -2910 0 0 10一2習(xí)陸2-2習(xí)°00000 0 0 00 0 0 00 0 0 00 0 0 010 0 0#1#127 -25#小波變換實(shí)例二維哈爾小波變換 例女口 32*5 32,5 0,5 0 5 31 -29 27 25陸U 000000=32.5 32.5 0.5 0.5 31 -29 27 -25=32.5 0 0.5 0.5 31 -29 27 一256964 2 3 61 60 6 7 57W = 32.5 0 0.5 0.5 31 -29 27 -25小

27、波變換實(shí)例二維哈爾小波變換針對圖像的小波變換的兩種方法 標(biāo)準(zhǔn)分解(standard decomposition)非標(biāo)準(zhǔn)分解(nonstandard decomposition)#小波變換實(shí)例二維哈爾小波變換標(biāo)準(zhǔn)分解(standard decomposition)口對圖像每一行的進(jìn)行小波變換，然后對這個經(jīng)過行變換的圖 像的每一列進(jìn)行小波變換71小波變換實(shí)例二維哈爾小波變換標(biāo)準(zhǔn)分解(standard decomposition)行變換13二維哈爾小波變換標(biāo)準(zhǔn)分解(standard decomposition)口對圖像每一行的像素值進(jìn)行一維小波變換，在進(jìn)行列變換, 行變換與列變換交替進(jìn)行73小波變換

28、實(shí)例二維哈爾小波變換非標(biāo)準(zhǔn)分解(nonstandard decomposition) 口交替地對圖像的行和列進(jìn)行小波變換75小波變換實(shí)例二維哈爾小波變換非標(biāo)準(zhǔn)分解(nonstandard decomposition)#小波變換實(shí)例#小波變換實(shí)例行變換77小波變換實(shí)例二維哈爾小波變換非標(biāo)準(zhǔn)分解(nonstandard decomposition)5010015020025050100150200250二維哈爾小波變換非標(biāo)準(zhǔn)分解(nonstandard decomposition)50100150200250100150200250二維哈爾小波變換非標(biāo)準(zhǔn)分解(nonstandard decompo

29、sition)81小波變換實(shí)例#小波變換實(shí)例1002002505010050150150200250#小波變換與數(shù)據(jù)壓縮小波變換與數(shù)據(jù)壓縮1)1原是圖像壓縮圖像f(x)= yciUi(x)m/(x) = Y E 力心)/=11. Compute coefficients ci,., cm representing an image in a normalized two-dimensional Haar basis.2. Sort the coefficients in order of decreasing magnitude to produce the sequence Cb(i),Starting with in = in. find the smallest in for which 工:為+1("(')2 & where e is the allowable L2 error.小波變換與數(shù)據(jù)壓縮壓縮算法1 （去除最小的系數(shù)procedure Compress(C: array 1. m of reals: c: real) Tinin J min Ci max|Cf|do#小波變換與數(shù)據(jù)