小波變換與圖像壓縮課件.

1、 周三例會報告周三例會報告 26/11 /2014 上海大學(xué)上海大學(xué) 數(shù)字圖像處理數(shù)字圖像處理圖像壓縮圖像壓縮 OUTLINE:OUTLINE: 圖像壓縮圖像壓縮 1.香農(nóng)信息論香農(nóng)信息論 2.數(shù)據(jù)壓縮原理數(shù)據(jù)壓縮原理 3.數(shù)據(jù)冗余數(shù)據(jù)冗余 4.無損壓縮無損壓縮 5.有損壓縮有損壓縮 Wavelet Exchange圖像壓縮圖像壓縮為什么要圖像壓縮?減少表示數(shù)字圖像時需要的數(shù)據(jù)量目的目的什么是圖像壓縮?24真彩色16色位256色位768kb128kb257kb圖像壓縮基礎(chǔ)-香農(nóng)信息論 說明：一個消息若能傳達(dá)給我們許多原來未知的內(nèi)容，我們就認(rèn)為這個信息很有意義，信息量大；反之，一個消息傳達(dá)給我們

2、的是已知確定的東西，則這個傳達(dá)就失去了意義。 生活實(shí)例生活實(shí)例 第一句話：我有一個師兄叫“*”。 第二句話：我大學(xué)舍友是個男生。直觀的感受一下這兩句話所攜帶的未知信息量。 信息信息圖像壓縮基礎(chǔ)-香農(nóng)信息論-信息量在信息論中：信息使用不確定的度量來確定的，一個消息的可能性越小，其信息含量越大；消息的可能性越大，其信息含量越小。設(shè)某消息 發(fā)生的概率為 ，則該消息攜載的信息量為： 1）當(dāng) 時，則單位為比特（bit）； 2）當(dāng) 時，則單位為奈特（nat）； 3）當(dāng) 時，則單位為哈特（hat）。一般以2為底取對數(shù)，由此定義的信息量等于描述該信息所用的最少比特數(shù)。信息量信息量 logiiaI xp x i

3、p x2a ae10a 圖像壓縮基礎(chǔ)-香農(nóng)信息論-信息量在信息論中：信息使用不確定的度量來確定的，一個消息的可能性越小，其信息含量越大；消息的可能性越大，其信息含量越小。設(shè)某消息 發(fā)生的概率為 ，則該消息攜載的信息量為： 1）當(dāng) 時，則單位為比特（bit）； 2）當(dāng) 時，則單位為奈特（nat）； 3）當(dāng) 時，則單位為哈特（hat）。一般以2為底取對數(shù)，由此定義的信息量等于描述該信息所用的最少比特數(shù)。信息量信息量 logiiaI xp x ip x2a ae10a 圖像壓縮基礎(chǔ)-香農(nóng)信息論-信息熵信息熵信息熵 信息熵信息熵 若信源有 個字符，對應(yīng)字符 的概率為 ，則該信源的平均信息量就稱為信息熵

4、，既： 具體到數(shù)字圖像中，稱 為圖像信息熵。它給出了描述一幅圖像攜載信息量的最少比特數(shù)。112200loglogiLLiiiiinnHpxpxnn nix ip xH圖像壓縮基礎(chǔ)-香農(nóng)信息論-圖像編碼圖像編碼圖像編碼 圖像編碼圖像編碼 碼本：碼本：編碼所用符號的集合稱為碼本。 如 碼字：碼字：對每個碼本的每個符號所賦的符號序列稱為碼字。如 碼字長度：碼字長度：每個碼字里的符號個數(shù)稱為碼字長度。數(shù)字圖像：碼長 = 二進(jìn)制數(shù)長度。0123456A,aaaaaaa001011a圖像壓縮基礎(chǔ)-香農(nóng)信息論-香農(nóng)定理香農(nóng)無失真香農(nóng)無失真編碼定理編碼定理 Shannon Shannon無失真編碼定理無失真編

5、碼定理 基于圖像信息熵，存在一種無失真的編碼方法，使編碼的平均碼長與信息熵?zé)o限的接近。既：但以 為下限，既 。這就是Shannon的無失真編碼定理。 無失真編碼性能的幾個指標(biāo)： 1 1）編碼效率）編碼效率 2 2）冗余度）冗余度 或 3 3）壓縮比）壓縮比 n1：編碼后的大小 n2：編碼前的大小,0avgLHavgLHa v gHL1100%DR12RnCn11DRRC 圖像壓縮基礎(chǔ)-圖像壓縮原理 1）數(shù)據(jù)壓縮的對象是數(shù)據(jù)，大的數(shù)據(jù)量并不代表含有大的信息量。 2）圖像壓縮就是除去圖像中多余的數(shù)據(jù)而對信息沒有本質(zhì)的影響。 3）圖像壓縮是以圖像編碼的形式實(shí)現(xiàn)的，用較少的比特數(shù)表示出現(xiàn)概率較大的灰度

6、級，用較多的比特數(shù)表示出現(xiàn)概率較小的灰度級，從而使平均碼長更接近于信息熵。圖像壓縮基礎(chǔ)-圖像壓縮質(zhì)量評判標(biāo)準(zhǔn)壓縮圖像灰階f(xf(xi i,y,yi i) )均方誤差：均方誤差：nimjjifjifmnMSE112),( ),(1規(guī)范化均方誤差：規(guī)范化均方誤差： , ,2fMSENMSEnimjfjifmn112),(1對數(shù)信噪比：對數(shù)信噪比：)(log10log102dBNMSEMSESNRf圖像壓縮基礎(chǔ)-數(shù)據(jù)冗余 1)1)信息熵冗余：信息熵冗余：也稱編碼冗余，如果圖像中平均比特數(shù)大于該圖像的信息熵，則圖像中存在冗余，這種冗余稱為信息熵冗余。 2)2)空間冗余：空間冗余：也稱為像素間冗余或幾

7、何冗余，是圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性所造成的冗余。 3)3)時間冗余：時間冗余：視頻圖像序列中的不同幀之間的相關(guān)性所造成的冗余。 4)4)視覺冗余：視覺冗余：是指人眼不能感知或不敏感的那部分圖像信息。 5)5)結(jié)構(gòu)冗余：結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。 6) 6)知識冗余：知識冗余：是指有些圖像還包含與某些先驗(yàn)知識有關(guān)的信息。 1)1)信息熵冗余：信息熵冗余：也稱編碼冗余，如果圖像中平均比特數(shù)大于該圖像的信息熵，則圖像中存在冗余，這種冗余稱為信息熵冗余。 2)2)空間冗余：空間冗余：也稱為像素間冗余或幾何冗余，是圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性所造成的冗余。 3

8、)3)時間冗余：時間冗余：視頻圖像序列中的不同幀之間的相關(guān)性所造成的冗余。 4)4)視覺冗余：視覺冗余：是指人眼不能感知或不敏感的那部分圖像信息。 5)5)結(jié)構(gòu)冗余：結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。 6) 6)知識冗余：知識冗余：是指有些圖像還包含與某些先驗(yàn)知識有關(guān)的信息。有損壓縮有損壓縮無損壓縮無損壓縮圖像壓縮基礎(chǔ)-圖像壓縮的類型標(biāo)準(zhǔn)量化和矢量量化編碼預(yù)測編碼行程編碼模型法編碼變換編碼字典編碼香農(nóng)-范諾編碼哈弗曼編碼算術(shù)編碼無損編碼無損編碼n圖像壓縮無損壓縮-行程編碼 行程行程：是指字符序列中各個字符連續(xù)重復(fù)出現(xiàn)而形成字符串的長度。 行程編碼行程編碼（游程編碼）：就是將字符

9、串序列映射成字符串的長度和串的位子的標(biāo)志序列。 例如例如：一個字符串00000000 111 888.888 1111 0000000000000000 111 888.888 1111 00000000 8 8個個 3 3個個 5050個個 4 4個個 8 8個個 行程編碼：0 x08,0 x00,0 x03,0 x01,0 x50,0 x08,0 x04,0 x01,0 x08,0 x00 1020100000222220110201000002222201 行程編碼：0 x01,0 x01,0 x01,0 x00,0 x01,0 x02,0 x01,0 x00, 0 x05,0 x00,

10、0 x05,0 x02,0 x01,0 x00,0 x01,0 x01 改進(jìn)： 0 x01,0 x00,0 x02,0 x01,0 xFF,0 x05, 0 x00,0 xFF,0 x05,0 x02,0 x00,0 x01無損壓縮-字典編碼 基于字典編碼方法是用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分，或者基于字典編碼方法是用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分，或者從輸入的數(shù)據(jù)中創(chuàng)建一個短語字典，表示在編碼過程中再遇到該短語，則用字典中短從輸入的數(shù)據(jù)中創(chuàng)建一個短語字典，表示在編碼過程中再遇到該短語，則用字典中短語的語的“索引號索引號”來表示該短語。字典編碼的算法有來表示該短

11、語。字典編碼的算法有LZ77,LZSS,LZ78LZ77,LZSS,LZ78和和LZWLZW。無損壓縮-香農(nóng)-范諾編碼 具體步驟如下： a）將信源符號按出現(xiàn)的概率 由大到小排列； b）將信源A分成兩個子集并且保證 成立或差不多成立； c）給兩個子集賦不同的碼元值； d）重復(fù)（2）、（3），既對每個子集再一分為二，并賦予不同的碼元值，直到每個子集僅含一個符號為止。 01k 12120112AAkknkkknaaaaaap ap ap ap ap ap a和01knijij kp ap a ip a 假設(shè)有一個信源為 ，其概率分布為：0123456A,a a a a a a a0a1a2a3a4a

12、5a6a無損壓縮-香農(nóng)-范諾編碼010101111000010010111011101111011111香農(nóng)-費(fèi)諾編碼示意圖計(jì)算香農(nóng)-費(fèi)諾編碼平均碼長為：101 0.430.230.1630.1240.0650.0450.022.380NavgkkkLB P 無損壓縮-霍夫曼（Huffman）編碼 霍夫曼編碼法是消除編碼冗余最常用的方法。 假設(shè)有一個信源為A=A,B,C,D，其組成的字符串為AABCCDA,其概率分布為：無損壓縮-霍夫曼（Huffman）編碼A3/7B1/7C2/7D1/7A3/7C2/72/7BDA3/74/7CBA1A0D1B0C01 AABCCDA001101010111

13、0結(jié)果無損壓縮-算術(shù)編碼算術(shù)編碼法和霍夫曼編碼法都是一種變長變長編碼。但霍夫曼編碼必須分配整數(shù)位碼字，而算數(shù)編碼可以分配帶有小數(shù)的比特數(shù)目信符，并且算術(shù)編碼給整個信源符號序列分配一個單一的算術(shù)碼字。假設(shè)有一信源為A=b,c,a,d,cA=b,c,a,d,c，信源中各符號出現(xiàn)的概率分別為： p(a)=0.2 p(b)=0.3 p(c)=0.4 p(d)=0.1p(a)=0.2 p(b)=0.3 p(c)=0.4 p(d)=0.1步驟 “當(dāng)前區(qū)間”初始化0,1）1將“當(dāng)前區(qū)間”分成子區(qū)間，該子區(qū)間的長度正比于符號的概率2對于輸入信源中的每個符號，依次執(zhí)行如下兩個步驟： 選擇下一個信符對應(yīng)的子區(qū)間，

14、并使它成為新的“當(dāng)前區(qū)間”3 在最后一個“當(dāng)前區(qū)間”中任找一個數(shù)作為算數(shù)編碼的輸入碼4無損壓縮-算術(shù)編碼算術(shù)編碼示意圖 輸出區(qū)間0.3728,0.37376） 0.01011111011,0.01011111101） 取位數(shù)最少的一個數(shù): 0.010111111 不考慮“0.”，則編碼輸出為:010111111 算數(shù)編碼法： 霍夫曼編碼法： 91.8/5avgL比特字符1.9/avgL比特 字符Ab,c,a,d,c有損壓縮-變換編碼變換編碼是采用一種可逆線性變換（正交變換），把圖像從空間域映射到變換域的系數(shù)集合，然后對這些變換系數(shù)進(jìn)行量化和編碼。變換編碼方法編碼、解碼示意圖有損壓縮-變換編碼

15、子圖像分解子圖像分解 將一副大小為MxN的輸入圖像分解成大小為nxn的子圖像。如88 1616 原因： 距離遠(yuǎn)的像素之間的相關(guān)性比較差； 小塊圖像的變換比較容易。 量化量化 系數(shù)選擇（濾波）：區(qū)域法和閾值法 量化：小數(shù)系數(shù)變成整數(shù) 編碼編碼 變長編碼法 正交變換正交變換 將一副圖像從空間域映射到變換域的系數(shù)集合。 正交變換的特點(diǎn)： 不會丟失信息； 去除部分相關(guān)性； 能量（信息）集中大的系數(shù)能量多低頻小的系數(shù)能量小高頻Wavelet Exchange小波變換小波變換小波變換用于圖像壓縮的理由基于DCT (Discrete Cosine TransformDiscrete Cosine Trans

16、form) 的壓縮標(biāo)準(zhǔn)JPEGMPEG-1,MPEG-2, H.264DCT 壓縮的優(yōu)點(diǎn)是簡單、 便于硬件實(shí)現(xiàn)DCT 壓縮的缺點(diǎn)是：圖像是分塊處理沿塊的邊界方向相關(guān)性被破壞，出現(xiàn) “blocking artifacts”小波變換用于圖像壓縮的理由傅里葉變換傅立葉分析是一種將基于時間的信號變換為基于頻率的信號的數(shù)學(xué)方法。傅立葉分析能夠很好的刻畫信號的頻率特性，但不能提供信號在時頻上的任何局部信息。為解決以上問題，在變換中增加了一個用于時間局部化的窗口函數(shù)，稱之為“短時傅里葉變換”。然而由測不準(zhǔn)原則可知，窗口的面積不可能任意小。測不準(zhǔn)原則：如果w（t）是一個窗口函數(shù)，則有：因此短時傅立葉變換是一種

17、恒分辨率分析。21小波變換的發(fā)展20世紀(jì) 80年代后期發(fā)展起來的小波變換理論它是繼傅里葉分析后信號處理與分析的強(qiáng)大工具無論是對古老的自然學(xué)科還是對新興的高新技術(shù)應(yīng)用學(xué)科都產(chǎn)生了強(qiáng)烈沖擊。小波理論是應(yīng)用數(shù)學(xué)的一個新領(lǐng)域。要深入理解小波理論需要用到比較多的數(shù)學(xué)知識。小波變換的發(fā)展哈爾(Alfred Haar)對在函數(shù)空間中尋找一個與傅里葉類似的基非常感興趣。1909年他發(fā)現(xiàn)了小波，1910年被命名為Haar wavelets最早發(fā)現(xiàn)和使用了小波的名稱。小波變換的發(fā)展20世紀(jì)70年代，當(dāng)時在法國石油公司工作的年輕的地球物理學(xué)家Jean Jean MorletMorlet提出了小波變換CWT (con

18、tinuous wavelet transform)的概念。法國科學(xué)家Y.MeyerY.Meyer創(chuàng)造性地構(gòu)造出具有一定衰減性的光滑函數(shù)，用縮放(dilations)與平移(translations)均為 2的j次冪的倍數(shù)構(gòu)造了平方可積的實(shí)空間L2(R)的規(guī)范正交基，使小波得到真正的發(fā)展.S . M a l l a tS . M a l l a t 于 1 9 8 8 年 在 構(gòu) 造 正 交 小 波 基 時 提 出 了 多 分 辨 率 分 析(multiresolution analysis)的概念, 從空間上形象地說明了小波的多分辨率的特性,提出了正交小波的構(gòu)造方法和快速算法，叫做Malla

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

20、all wave, a ripple) 就是小的波形，所謂小，就是它具有衰減性，是存在于一個較小區(qū)域的波。 連續(xù)小波變換 定義a = scale variable縮放因子(尺度參數(shù))b= time shift 時間平移（位移參數(shù)）在CWT中，縮放和平移是連續(xù)變化的定義X(t)是平方可積函數(shù)(t)被稱為基本小波或母小波函數(shù)連續(xù)小波變換連續(xù)小波變換連續(xù)小波變換用較小a對信號做高頻分析時，實(shí)際是用高頻小波對信號進(jìn)行細(xì)致觀察用較大a對信號做低頻分析時，實(shí)際是用低頻小波對信號進(jìn)行概貌觀察小波變換與窗口時域分析時間幅值頻域分析時間頻率短時傅里葉變換時間幅值小波分析時間尺度小波變換的性質(zhì)線性性：一個多分量信

21、號之和的小波變換等于各個分量的小波變換之和。平移不變性：如果f(t)的小波變換為Wf(a,b),那么f(t-)的小波變換為Wf(a,b-)尺度共變形：如果f(t)的小波變換為Wf(a,b),那么f(ct)的小波變換為 （1/c）Wf(ca,cb),其中c0自相似性：對應(yīng)不同尺度參數(shù)a和不同平移參數(shù)b的連續(xù)小波變換之間是 自相似的。子帶編碼SBC (subband coding)把信號的頻率分成幾個子帶，然后對每個子帶分別進(jìn)行編碼，并根據(jù)每個子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù)20世紀(jì)70年代，子帶編碼開始用于語音編碼20世紀(jì)80年代中期開始在圖像編碼中使用離散小波變換只有離散，小波變換才能應(yīng)用離散的方式有很多離散小波變換的多分辨率分析Mallat創(chuàng)立了多分辨率分析理論在多分辨率分析基礎(chǔ)上，Mallat提出了基于濾波器組實(shí)現(xiàn)信號的小波正變換和反變換算法。執(zhí)行離散小波變換的有效方法離散小波變換把連續(xù)小波變換中尺度參數(shù)a和平移參數(shù)b的離散化公式分別取為：a= (a0)m ,b=nb0 (a0)m得：這樣離散小波變換可定義為最