1、壓縮技術(shù)實(shí)驗(yàn)編碼實(shí)驗(yàn)一統(tǒng)計(jì)編碼實(shí)驗(yàn)?zāi)康? .熟悉統(tǒng)計(jì)編碼的原理2 .掌握r元huffman編碼的方法；3 .了解huffman編碼效率及冗余度的計(jì)算；二、 實(shí)驗(yàn)原理霍夫曼編碼，又稱最佳編碼，根據(jù)字符出現(xiàn)概率來 構(gòu)造平均長度最短的變長編碼。huffman編碼步驟：(1)把信源符號x i(i=1,2,n出現(xiàn)概率的值由 大到小的順序排列；(2)對兩個(gè)概率最小的符號分別分配以“ 0和“ 1 ：然后把這兩個(gè)概率相加作為一個(gè)新的輔助符號的概率；(3)將這個(gè)新的輔助符號與其他符號一起重新按概 率大小順序排列；(4)跳到第2步，直到出現(xiàn)概率相加為1為止；(5)用線將符號連接起來，從而得到一個(gè)碼樹，樹的n個(gè)端點(diǎn)

2、對應(yīng)n個(gè)信源符號；(6)從最后一個(gè)概率為1的節(jié)點(diǎn)開始，沿著到達(dá)信源 的每個(gè)符號，將一路遇到的二進(jìn)制碼 “0或“1順序排列 起來，就是端點(diǎn)所對應(yīng)的信源符號的碼字。以上是二元霍夫曼編碼。如果是 r元霍夫曼編碼， 則應(yīng)該如何做呢？在 huffman 編碼方案中，為出現(xiàn)概率較小的信源輸出分配較長的碼字，而對那些出現(xiàn)可能性較大的信源輸出分配較短的碼字。為此，首先將r 個(gè)最小可能的信源輸出合并成為一個(gè)新的輸出，該輸出的概率就是上述的 r 個(gè)輸出的概率之和。重復(fù)進(jìn)行該過程直到只剩下一個(gè)輸出為止。信源符號的個(gè)數(shù)q 與 r 必須滿足如下的關(guān)系式：q = (r-1) n + r n 為整數(shù)如果不滿足上述關(guān)系式，可

3、通過添加概率為零的信源符號來滿足。這樣就生成了一個(gè)樹，從該樹的根節(jié)點(diǎn)出發(fā)并將0、1分別分配給任何r個(gè)來自于相同節(jié)點(diǎn)的分支，生成編碼。可以證明用這種方法產(chǎn)生的編碼在前向樹類編碼中具有最小的平均長度。舉例：對于取值為 u=u1,u2,u3,u4,u5,u6 其相應(yīng)的概率為 p=0.1 ， 0.3， 0.05， 0.09， 0.21， 0.25的信源，試設(shè)計(jì)一個(gè)3 元 huffman 碼，求出碼子的平均長度與編碼效率。201211212220ulu2u3u iu50. 10.30. 050. 090.21(). 25注：因?yàn)槭?元編碼，所以每次3個(gè)概率值相加。碼字的平均長度l=2 x 0.1+1 x

4、 0.3+3 x 0.05+3 x 0.09+2 x 0.21+1 x0.25=1.59信源的燧h (u) = (0.1 x log2(0.1)+ 0.3x log2(0.3)+ 0.05x log2(0.05)+ 0.09x log2(0.09)+0.21 x log2(0.21)+ 0.25x 10g2(0.25)=2.3549編碼效率q=0.9345用 matlab實(shí)現(xiàn)該編碼的方法可用下面的矩陣來說明：201211212220u1u2u3u4u5u60.10.30.05 0.09 0.21 0.250.0.30.25 0.21 0.10.09 0.05 00.30.25 0.21 0.1

5、0.14 0.30.250.21 0.140.10.30.250.45 0.45 10.30.25注：每次3個(gè)數(shù)加完后，重新按序分配編號，在按概率 值重新排序，再進(jìn)行下次加數(shù)。734*1.5.6.2m= 2 .1 .3, 4.5002o o注：m中每一行為按概率值重新排序后的編號列，一共 三次概率值排序；單箭頭表示兩次排序中的概率值并未 參加加數(shù)，未改變；多箭頭表示箭頭所指向的多項(xiàng)概率 值相加后得到箭頭源的概率值。210 . 211 712.20/2, 01c=20 .222 _011注：c為編碼矩陣，從最后一行開始，因?yàn)槭?3元編碼, 故按0、1、2開始編碼。根據(jù)m中的箭頭，單箭頭不變, 多

6、箭頭根據(jù)箭頭源每上一層則箭頭源編碼后再加一位， 同一層中加的位數(shù)按0、1、2順序添加。m矩陣第i (i1)行中的1記錄了合并后的信源符 號在新信源中的位置。3、 實(shí)驗(yàn)步驟1 .輸入初始概率分布p和碼元數(shù)r;2 .檢查是否滿足q = (n-1)r + r (q為輸入信源的個(gè) 數(shù))，如果不滿足則補(bǔ)零使之滿足；3 .排序得m矩陣4 根據(jù) m 矩陣獲得 c 矩陣5 從 c 矩陣中取出最后的碼字矩陣 h 并計(jì)算平均碼 長和編碼效率。4、 實(shí)驗(yàn)儀器1 計(jì)算機(jī)；2 matlab 程序；3 移動(dòng)式存儲器（軟盤、 u 盤等） ；4 記錄用的筆、紙。5、 實(shí)驗(yàn)報(bào)告內(nèi)容1、實(shí)驗(yàn)?zāi)康?、實(shí)驗(yàn)要求3、實(shí)驗(yàn)環(huán)境4、實(shí)驗(yàn)內(nèi)

7、容（敘述操作過程，提交主要程序段）5、實(shí)驗(yàn)結(jié)論6、實(shí)驗(yàn)總結(jié)六、 思考題1 什么是霍夫曼編碼？在matlab 中如何實(shí)現(xiàn)？2 r 元霍夫曼編碼的原理和過程？實(shí)驗(yàn)二 量化與變換編碼1、 實(shí)驗(yàn)?zāi)康? 理解有損壓縮和無損壓縮的概念；2 理解圖像壓縮的主要原則和目的；3 .掌握dct 編碼的原理4 .了解游程編碼的原理2、 實(shí)驗(yàn)原理1 .圖像壓縮原理圖像壓縮主要目的是為了節(jié)省存儲空間，增加傳輸速度。圖像壓縮的理想標(biāo)準(zhǔn)是信息丟失最少，壓縮比例最大。不損失圖像質(zhì)量的壓縮稱為無損壓縮，無損壓縮不可能達(dá)到很高的壓縮比；損失圖像質(zhì)量的壓縮稱為有損壓縮，高的壓縮比是以犧牲圖像質(zhì)量為代價(jià)的。壓縮的實(shí)現(xiàn)方法是對圖像重新

8、進(jìn)行編碼，希望用更少的數(shù)據(jù)表示圖像。信息的冗余量有許多種，如空間冗余，時(shí)間冗余，結(jié)構(gòu)冗余，知識冗余，視覺冗余等，數(shù)據(jù)壓縮實(shí)質(zhì)上是減少這些冗余量。高效編碼的主要方法是盡可能去除圖像中的冗余成分，從而以最小的碼元包含最大的圖像信廣息。編碼壓縮方法有許多種，從不同的角度出發(fā)有不同的分類方法，從信息論角度出發(fā)可分為兩大類。（ 1） 冗余度壓縮方法， 也稱無損壓縮、 信息保持編碼或嫡編碼。具體說就是解碼圖像和壓縮編碼前的圖像嚴(yán)格相同，沒有失真，從數(shù)學(xué)上講是一種可逆運(yùn)算。（ 2） 信息量壓縮方法， 也稱有損壓縮、 失真度編碼或煙壓縮編碼。也就是說解碼圖像和原始圖像是有差別的，允許有一定的失真。應(yīng)用在多媒體

9、中的圖像壓縮編碼方法，從壓縮編碼算法原理上可以分為以下 3 類：（ 1）無損壓縮編碼種類哈夫曼（ huffman ）編碼，算術(shù)編碼，游程（ rle ） 編碼， lempel zev 編碼。（ 2）有損壓縮編碼種類預(yù)測編碼， dpcm ，運(yùn)動(dòng)補(bǔ)償；頻率域方法：正交變換編碼 （如 dct） ，子帶編碼；空間域方法：統(tǒng)計(jì)分塊編碼；模型方法：分形編碼，模型基編碼；基于重要性： 濾波， 子采樣， 比特分配， 向量量化；（ 3）混合編碼。有 jbig ， h261 ， jpeg ， mpeg 等技術(shù)標(biāo)準(zhǔn)。本實(shí)驗(yàn)主要利用 matlab 程序進(jìn)行離散余弦變換（ dct ）壓縮和游程編碼（ run length

10、 encoding ， rle ） 。1）離散余弦變換（dct） 圖像壓縮原理離散余弦變換dct 在圖像壓縮中具有廣泛的應(yīng)用，它是 jpeg 、 mpeg 等數(shù)據(jù)壓縮標(biāo)準(zhǔn)的重要數(shù)學(xué)基礎(chǔ)。和相同圖像質(zhì)量的其他常用文件格式（如gif（可交 換的圖像文件格式 ） ， tiff（ 標(biāo)簽圖像文件格式 ）， pcx（ 圖 形文件格式 ） 相比， jpeg 是目前靜態(tài)圖像中壓縮比最高的。 jpeg 比其他幾種壓縮比要高得多，而圖像質(zhì)量都差不多 (jpeg 處理的圖像只有真彩圖和灰度圖 ) 。 正是由于其高壓縮比，使得jpeg 被廣泛地應(yīng)用于多媒體和網(wǎng)絡(luò)程序中。 jpeg 有幾種模式， 其中最常用的是基于 d

11、ct變換的順序型模式，又稱為基本系統(tǒng)(baseline)。用 dct 壓縮圖像的過程為：(1)首先將輸入圖像分解為8x8或16x16的塊，然后對每個(gè)子塊進(jìn)行二維 dct變換。(2)將變換后得到的量化的dct 系數(shù)進(jìn)行編碼和傳送，形成壓縮后的圖像格式。用 dct 解壓的過程為：(1)對每個(gè)8x8或16x16塊進(jìn)行二維dct反變換。(2)將反變換的矩陣的塊合成一個(gè)單一的圖像。余弦變換具有把高度相關(guān)數(shù)據(jù)能量集中的趨勢，dct 變換后矩陣的能量集中在矩陣的左上角， 右下的大多數(shù)的 dct 系數(shù)值非常接近于 0。 對于通常的圖像來說，舍棄這些接近于 0 的 dct 的系數(shù)值，并不會(huì)對重構(gòu)圖像的畫面質(zhì)量帶

12、來顯著的下降。所以，利用 dct 變換進(jìn)行圖像壓縮可以節(jié)約大量的存儲空間。壓縮應(yīng)該在最合理地近似原圖像的情況下使用最少的系數(shù)。使用系數(shù)的多少也決定了壓縮比的大小。在壓縮過程的第 2 步中，可以合理地舍棄一些系數(shù)，從而得到壓縮的目的。在壓縮過程的第 2 步，還可以采用 rle 和 huffman 編碼來進(jìn)一步壓縮。2）游程編碼（rld原理：例如如下這幅 的二值圖像，如果采用游程編碼可以按如下格式保存其中 10 和 8 表示圖像的寬和高。在這個(gè)小例子中游程編碼并沒有起到壓縮圖像的作用。這是由于這個(gè)圖的尺寸過小，當(dāng)圖像尺寸較大時(shí)游程編碼還是不錯(cuò)的無損壓縮方法。對于灰度圖像和二值圖像，用游程編碼般都有很高的壓縮率。游程編碼方法實(shí)現(xiàn)起來很容易，對于具有長重復(fù)值的串的壓縮編碼很有效，例如：對于有大面積的陰影或顏色相同的圖像，使用這種方法壓縮效果很好。 很多位圖文件格式都采用游程編碼， 如 tiff ，pcx gem bm陣3、 實(shí)驗(yàn)步驟1 打開計(jì)算機(jī)，啟動(dòng) matlab 程序；2 調(diào)入數(shù)字圖像，并進(jìn)行數(shù)據(jù)的游程（ rle ）編碼壓縮處理；3 將原圖像在photosho