版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
霍夫曼編碼(biānmǎ)HuffmanCoding長(zhǎng)春(chánɡchūn)理工大學(xué)080212418高延邦圖像(túxiànɡ)無損壓縮第一頁,共14頁。目錄(mùlù)
一、什么(shénme)是編碼二、霍夫曼編碼簡(jiǎn)介三、霍夫曼編碼的熵四、霍夫曼編碼(一)霍夫曼編碼過程(二)霍夫曼樹的構(gòu)建(三)霍夫曼表五、霍夫曼編碼特點(diǎn)第二頁,共14頁。一.什么(shénme)是編碼編碼是將源對(duì)象內(nèi)容按照一種標(biāo)準(zhǔn)轉(zhuǎn)換(zhuǎnhuàn)為一種標(biāo)準(zhǔn)格式內(nèi)容。源對(duì)象標(biāo)準(zhǔn)編碼后GooddayG112237456o2d3d4a5y6
7第三頁,共14頁。二.霍夫曼編碼(biānmǎ)簡(jiǎn)介
霍夫曼編碼是不定長(zhǎng)編碼,即代表各元素的碼字長(zhǎng)度不等。該方法完全依據(jù)(yījù)字符出現(xiàn)概率來構(gòu)造平均長(zhǎng)度最短的碼字,有時(shí)稱之為最佳編碼。該編碼是基于不同符號(hào)的概率分布,在信息源中出現(xiàn)概率越大的符號(hào),相應(yīng)的碼越短;出現(xiàn)概率越小的符號(hào),其碼越長(zhǎng),從而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。它在變長(zhǎng)編碼中是最佳的。在計(jì)算機(jī)信息處理中,“霍夫曼編碼”是一種一致性編碼法(又稱"熵編碼法")。DavidAlbertHuffman戴維·霍夫曼第四頁,共14頁。三、霍夫曼編碼(biānmǎ)的熵
一個(gè)事件集合x1,x2,……xn,處于一個(gè)基本概率空間,其相應(yīng)概率為p1,p2,……pn,且p1,p2,……pn之和為1,每一個(gè)事件的信息量為I(xk)=-logn(pk),如定義在空間中的每一事件的概率不相等的平均不肯定程度或平均信息量叫做熵H,則H=E{I(xk)}=∑pkI(xk)=-∑pkloga(pk)。對(duì)于圖像來說,n=2m個(gè)灰度級(jí)xi,則p(xi)為各灰度級(jí)出現(xiàn)的概率,熵即表示平均信息量為多少比特,換句話說,熵是編碼所需比特?cái)?shù)的下限,即編碼所需的最少比特。編碼一定要用不比熵少的比特?cái)?shù)編碼才能完全保持(bǎochí)原圖像的信息,這是圖像壓縮的下限。當(dāng)a=2是,H的單位是比特。第五頁,共14頁。四、霍夫曼編碼(biānmǎ)
設(shè)信息源空間為[A*P]:{A:a1a2……an}{P(A):P(a1)P(a2)P(a3)……P(an)}其中∑P(ak)=1,先用r個(gè)碼的號(hào)碼(hàomǎ)符號(hào)集X:{x1,x2,……xr}對(duì)信源A中的每一個(gè)符號(hào)ak進(jìn)行編碼。編碼過程如下:把信源符號(hào)ai按其出現(xiàn)的概率的大小順序排列起來;把最末兩個(gè)具有最小概率的元素之概率加起來;把該概率之和同其余概率由大到小排隊(duì),然后再把兩個(gè)最小概率加起來,再排隊(duì);重復(fù)步驟(2)、(3),直到概率和達(dá)到1為止;在每次合并消息時(shí),將被合并的消息賦以1和0或0和1;尋找從每個(gè)信源符號(hào)到概率為1處的路徑,記錄下路徑上的1和0;對(duì)每個(gè)符號(hào)寫出"1"、"0"序列(從碼數(shù)的根到終節(jié)點(diǎn))。創(chuàng)建霍夫曼表。壓縮編碼時(shí),將碼值用碼字代替。(一)霍夫曼編碼(biānmǎ)過程第六頁,共14頁。(二)霍夫曼樹的構(gòu)建(ɡòujiàn)
霍夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹,碼樹從最上層的端點(diǎn)開始構(gòu)造,直到樹根結(jié)束。這里舉個(gè)例子說明如何生成霍夫曼樹。假設(shè)對(duì)由a1、a2、a3、a4、a5、a6、a7、a8八個(gè)信源符號(hào)組成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進(jìn)行霍夫曼編碼。首先應(yīng)對(duì)信息中各數(shù)字出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)(tǒngjì)如下:
碼值
a1a2a3a4a5a6a7a8次數(shù)
22343331概率0.10.10.150.20.150.150.10.05熵H=-0.1*log2(0.1)-0.1*log2(0.1)-0.15*log2(0.15)-0.2*log2(0.2)-0.15*log2(0.15)-0.15*log2(0.15)-0.1*log2(0.1)-0.05*log2(0.05)=2.9087(bit)第七頁,共14頁。具體過程是這樣的,先將所有符號(hào)排成一行,構(gòu)成8個(gè)最底層節(jié)點(diǎn)。首先(shǒuxiān)將這些節(jié)點(diǎn)中最小兩個(gè)概率值相加:0.05+0.1=0.15,得到新的節(jié)點(diǎn)這時(shí)擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。第八頁,共14頁。再將兩個(gè)最小的概率(gàilǜ)值相加得到新的節(jié)點(diǎn)......直到得到根節(jié)點(diǎn)概率(gàilǜ)為1.0為止。相加時(shí),對(duì)于概率(gàilǜ)值相等的多個(gè)節(jié)點(diǎn),可以任意選取。除根節(jié)點(diǎn)外,設(shè)節(jié)點(diǎn)左邊分支為0,右邊分支為1(也可以反過來)。這樣,生成的霍夫曼樹如下圖所示:第九頁,共14頁。對(duì)于各值(碼值)的代碼(碼字)就是從根節(jié)點(diǎn)出發(fā)到底層節(jié)點(diǎn)所經(jīng)歷的分支序列。如a4的代碼(碼字)為00,a6的碼字為111......通常a4和a6等稱為(chēnɡwéi)碼值,00和111等稱為(chēnɡwéi)碼字。所有碼值和碼字對(duì)應(yīng)關(guān)系如下表所示:第十頁,共14頁。(三)霍夫曼表
將所有碼值和碼字的關(guān)系整理成一張表,為了整字節(jié)輸出碼字,表中還含有各碼字的長(zhǎng)度(chángdù)。這種表就稱為霍夫曼表。本例霍夫曼表如表所示:
第十一頁,共14頁。進(jìn)行壓縮編碼時(shí),只要(zhǐyào)將碼值用碼字代替即可。所以源符a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8編碼為:0100100110111011011010000000011011011010000100001001。平均碼長(zhǎng)B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*3+0.15*3+0.1*4+0.05*4=2.95(b)熵H=2.9087編碼效率N=H/B=2.9087/2.95=98.6%第十二頁,共14頁。五、霍夫曼編碼(biānmǎ)的特點(diǎn)
1.霍夫曼方法構(gòu)造出來的碼不是唯一的。原因:在給兩個(gè)分支賦值時(shí),可以是左支(或上支)為0,也可以是右支(或下支)為0,造成編碼的不唯一。當(dāng)兩個(gè)消息的概率相等時(shí),誰前誰后也是隨機(jī)的,構(gòu)造出來的碼字就不是唯一的。2.霍夫曼編碼碼字字長(zhǎng)參差不齊。3.霍夫曼編碼對(duì)不同的信源的編碼效率是不同的。當(dāng)信源概率相等時(shí),其編碼效率最低。只有在概率分布很不均勻時(shí),霍夫曼編碼才會(huì)收到顯著的效果。4.解碼時(shí),必須參照霍夫曼編碼表才能正確譯碼。在信源的存儲(chǔ)與傳輸過程中必須首先存儲(chǔ)或傳輸這一霍夫曼編碼表,在實(shí)際計(jì)算壓縮效果時(shí),必須考慮霍夫曼編
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 工作總結(jié)之互聯(lián)網(wǎng)實(shí)習(xí)總結(jié)
- 2024年無機(jī)械動(dòng)力飛機(jī)項(xiàng)目資金申請(qǐng)報(bào)告代可行性研究報(bào)告
- 《侵犯人身權(quán)利罪》課件
- 銀行員工績(jī)效評(píng)估制度
- 酒店餐飲服務(wù)流程優(yōu)化與提升制度
- 【大學(xué)課件】學(xué)習(xí)科學(xué)與技術(shù)
- 《保險(xiǎn)業(yè)務(wù)需求分析》課件
- 學(xué)生關(guān)于珍愛生命的演講稿(34篇)
- 陜西省咸陽市武功縣2024屆九年級(jí)上學(xué)期期末考試數(shù)學(xué)試卷(含答案)
- 2024數(shù)字醫(yī)療年度創(chuàng)新白皮書 醫(yī)療大模型開啟“百模大戰(zhàn)”數(shù)字醫(yī)療單筆融資創(chuàng)紀(jì)錄
- COPD教學(xué)講解課件
- (完整版)國(guó)際法期末考試習(xí)題
- 2萬噸/年燃料丁醇發(fā)酵工段工藝設(shè)計(jì)- 倒數(shù)第二版
- 2021-2022學(xué)年六年級(jí)上冊(cè)世界少年奧林匹克思維能力測(cè)評(píng)地方選拔活動(dòng)(含答案解析)
- 《生物力學(xué)》配套教學(xué)課件
- 湘科版五年級(jí)(上冊(cè))科學(xué)期末質(zhì)量測(cè)試題(含答案)
- 腦積水(實(shí)用課件)
- 《企業(yè)會(huì)計(jì)模擬實(shí)驗(yàn)教程》答案
- 攝影技巧構(gòu)圖(共52張PPT)
- 廢氣治理設(shè)施運(yùn)行管理規(guī)程
- 監(jiān)控中心報(bào)警記錄表
評(píng)論
0/150
提交評(píng)論