多媒體技術(shù)-圖像與視頻壓縮(1)

1、數(shù)字圖像處理 第七章第七章 圖像與視頻壓縮（圖像與視頻壓縮（1）數(shù)字圖像處理第七章第七章 圖像與視頻壓縮圖像與視頻壓縮n1 通用數(shù)據(jù)壓縮n2 多媒體數(shù)據(jù)壓縮數(shù)字圖像處理1 通用數(shù)據(jù)壓縮通用數(shù)據(jù)壓縮n1.1 數(shù)據(jù)壓縮概述n1.2 數(shù)據(jù)壓縮主要方法l游程編碼l統(tǒng)計(jì)編碼l字典編碼數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-定義定義 “數(shù)據(jù)壓縮”在漢英詞典中的解釋： data compression (A method of reducing the amount of memory required to store data by encoding it and minimizing redundancy. C

2、ompressed data takes less time to transmit, but more computation time to restore it to its original form when needed for processing.)數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-作用作用 通俗地說，就是用最少的數(shù)碼來表示信號(hào)。其作用是：能較快地傳輸各種信號(hào)，如傳真、Modem通信等；在現(xiàn)有的通信干線并行開通更多的多媒體業(yè)務(wù)，如各種增值業(yè)務(wù)；緊縮數(shù)據(jù)存儲(chǔ)容量，如CDROM、VCD和DVD等；降低發(fā)信機(jī)功率，這對(duì)于多媒體移動(dòng)通信系統(tǒng)尤為重要。由此看來，通信時(shí)間、傳輸帶寬、存儲(chǔ)空間甚

3、至發(fā)射能量，都可能成為數(shù)據(jù)壓縮的目的。 數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-概要概要 在計(jì)算機(jī)科學(xué)和信息論中，數(shù)據(jù)壓縮或者信源編碼是按照特定的編碼機(jī)制用比未經(jīng)編碼少的數(shù)據(jù)位元（或者其它信息相關(guān)的單位）表示信息的過程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數(shù)據(jù)位表示。一種流行的壓縮實(shí)例是許多計(jì)算機(jī)都在使用的ZIP 文件格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具Archive使用，能夠?qū)⒃S多文件存儲(chǔ)到同一個(gè)文件中。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-概要概要 對(duì)于任何形式的通信來說，只有當(dāng)信息的發(fā)送方和接受方都能夠理解編碼機(jī)制的時(shí)候壓縮數(shù)據(jù)通信才能夠工作。

4、例如，只有當(dāng)接受方知道這篇文章需要用英語字符解釋的時(shí)候這篇文章才有意義。同樣，只有當(dāng)接受方知道編碼方法的時(shí)候他才能夠理解壓縮數(shù)據(jù)。一些壓縮算法利用了這個(gè)特性，在壓縮過程中對(duì)數(shù)據(jù)進(jìn)行加密，例如利用密碼加密，以保證只有得到授權(quán)的一方才能正確地得到數(shù)據(jù)。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-概要概要 數(shù)據(jù)壓縮能夠?qū)崿F(xiàn)是因?yàn)槎鄶?shù)現(xiàn)實(shí)世界的數(shù)據(jù)都有各種冗余。例如，字母“e”在英語中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。無損壓縮算法通常利用利用了統(tǒng)計(jì)冗余，這樣就能更加簡(jiǎn)練地、但仍然是完整地表示發(fā)送方的數(shù)據(jù)。 如果允許一定程度的保真度損失，那么還可以實(shí)現(xiàn)進(jìn)一步的壓縮。例如，人們看圖畫或者電視畫

5、面的時(shí)候可能并不會(huì)注意到一些細(xì)節(jié)并不完善。同樣，兩個(gè)音頻錄音采樣序列可能聽起來一樣，但實(shí)際上并不完全一樣。有損壓縮算法在帶來微小差別的情況下使用較少的位數(shù)表示圖像、視頻或者音頻。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-概要概要 由于可以幫助減少如硬盤空間與連接帶寬這樣的昂貴資源的消耗，所以壓縮非常重要，然而壓縮需要消耗信息處理資源，這也可能是費(fèi)用昂貴的。所以數(shù)據(jù)壓縮機(jī)制的設(shè)計(jì)需要在壓縮能力、失真度、所需計(jì)算資源以及其它需要考慮的不同因素之間進(jìn)行折衷。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-應(yīng)用應(yīng)用 一種非常簡(jiǎn)單的壓縮方法是行程長(zhǎng)度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長(zhǎng)度這樣簡(jiǎn)單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無損數(shù)據(jù)壓縮的

6、一個(gè)實(shí)例。這種方法經(jīng)常用于辦公計(jì)算機(jī)以更好地利用磁盤空間、或者更好地利用計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬。對(duì)于電子表格、文本、可執(zhí)行文件等這樣的符號(hào)數(shù)據(jù)來說，無損是一個(gè)非常關(guān)鍵的要求，因?yàn)槌艘恍┯邢薜那闆r，大多數(shù)情況下即使是一個(gè)數(shù)據(jù)位的變化都是無法接受的。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-應(yīng)用應(yīng)用 對(duì)于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過利用人類感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲(chǔ)空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)量相比并沒有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失三者之間進(jìn)行折衷。 有損圖像壓縮用于數(shù)碼相機(jī)中，大幅度地提高了存儲(chǔ)能力

7、，同時(shí)圖像質(zhì)量幾乎沒有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實(shí)現(xiàn)了類似的功能。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-應(yīng)用應(yīng)用 在有損音頻壓縮中，心理聲學(xué)的方法用來去除信號(hào)中聽不見或者很難聽見的成分。人類語音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時(shí)也將“語音壓縮”或者“語音編碼”作為一個(gè)獨(dú)立的研究領(lǐng)域與“音頻壓縮”區(qū)分開來。不同的音頻和語音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語音壓縮用于因特網(wǎng)電話，而音頻壓縮被用于CD翻錄并且使用 MP3 播放器解碼。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-理論理論 壓縮的理論基礎(chǔ)是信息論（它與算法信息論密切相關(guān)）以及率失真理論，這個(gè)領(lǐng)域的研究工作主要是由 Claud

8、e Shannon 奠定的，他在二十世紀(jì)四十年代末期及五十年代早期發(fā)表了這方面的基礎(chǔ)性的論文。 Doyle 和 Carlson 在2000年寫道數(shù)據(jù)壓縮“是所有的工程領(lǐng)域最簡(jiǎn)單、最優(yōu)美的設(shè)計(jì)理論之一”。密碼學(xué)與編碼理論也是密切相關(guān)的學(xué)科，數(shù)據(jù)壓縮的思想與統(tǒng)計(jì)推斷也有很深的淵源。數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-理論理論 許多無損數(shù)據(jù)壓縮系統(tǒng)都可以看作是四步模型，有損數(shù)據(jù)壓縮系統(tǒng)通常包含更多的步驟，例如它包括預(yù)測(cè)、頻率變換以及量化。 Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲(chǔ)算法之一。DEFLATE是 LZ 的一個(gè)變體，它針對(duì)解壓速度與壓縮率進(jìn)行了優(yōu)化，雖然它的壓縮速度可能非常緩慢，PK

9、ZIP、gzip 以及 PNG 都在使用EFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用于 GIF 圖像。 數(shù)字圖像處理數(shù)據(jù)壓縮數(shù)據(jù)壓縮-理論理論 最好的壓縮工具將概率模型預(yù)測(cè)結(jié)果用于算術(shù)編碼。算術(shù)編碼由 Jorma Rissanen 發(fā)明，并且由 Witten、Neal 以及 Cleary 將它轉(zhuǎn)變成一個(gè)實(shí)用的方法。這種方法能夠?qū)崿F(xiàn)比眾人皆知的哈夫曼算法更好的壓縮，并且它本身非常適合于自適應(yīng)數(shù)據(jù)壓縮，自適應(yīng)數(shù)據(jù)壓縮的預(yù)測(cè)與上下文密切相關(guān)。算術(shù)編碼已經(jīng)用于二值圖像壓縮標(biāo)準(zhǔn) JBIG、文檔壓縮標(biāo)準(zhǔn) DejaVu。文本 輸

10、入系統(tǒng) Dasher 是一個(gè)逆算術(shù)編碼器。數(shù)字圖像處理1 通用數(shù)據(jù)壓縮通用數(shù)據(jù)壓縮n1.1 數(shù)據(jù)壓縮概述n1.2 數(shù)據(jù)壓縮主要方法l游程編碼l統(tǒng)計(jì)編碼l字典編碼數(shù)字圖像處理游程編碼（游程編碼（RLE）n思想：如果數(shù)據(jù)項(xiàng)d在輸入流中出現(xiàn)n次，則以單個(gè)字符對(duì)nd替換n次出現(xiàn)者。這個(gè)連續(xù)出現(xiàn)的數(shù)據(jù)項(xiàng)叫做游程n，這種數(shù)據(jù)壓縮方法稱為游程編碼或RLEnRLE文本壓縮nRLE圖像壓縮數(shù)字圖像處理RLE文本壓縮文本壓縮 2. all is too well 2. a2l is t2o we2l一個(gè)解決方法就是在重復(fù)部分前綴一個(gè)特殊的提示字符，我們用作提示，則字符串被替換成: 2. a2l is t2o we

11、2l數(shù)字圖像處理 RLE RLE 文本壓縮的步驟文本壓縮的步驟 讀入第一個(gè)字符后，計(jì)數(shù)值為1，保存該字符。將后續(xù)字符與已保存者相比較，相同則重復(fù)計(jì)數(shù)器加1。如果讀入一個(gè)不同字符，則操作取決于重復(fù)次數(shù)：如果次數(shù)很小，把已保存的字符寫入壓縮文件，保存新讀入的字符；否則先寫一個(gè)，在輸出重復(fù)次數(shù)及被保存的字符。下圖是游程文本壓縮器的流程圖數(shù)字圖像處理 數(shù)字圖像處理 RLE RLE 文本解壓的步驟：文本解壓的步驟：一旦讀入一個(gè)，則立即讀入重復(fù)次數(shù)及實(shí)際字符，并在輸出流中重復(fù)寫該字符n次。數(shù)字圖像處理 數(shù)字圖像處理 RLE RLE 方法存在的問題方法存在的問題普通英文中并沒有多少重復(fù)。有許多雙寫，但是很少

12、有3次重復(fù)的。 在輸入流中，字符可能是文本的一部分，此時(shí)必須選一個(gè)不同的提示字符。由于重復(fù)計(jì)數(shù)值以字節(jié)形式寫在輸出流中，只能計(jì)到255。數(shù)字圖像處理 RLERLE的壓縮比的壓縮比 假設(shè)待壓縮字符長(zhǎng)度為N，字符中包含M次重復(fù)，每次重復(fù)的平均長(zhǎng)度為L(zhǎng)。M次中的每一次重復(fù)可用3字節(jié)代替，因此，壓縮后字符串的長(zhǎng)度為N-M(L-3)，壓縮因子為 N/(N-M(L-3)如果N=1000,M=10,L=4,則壓縮因子1.01， 如果N=1000,M=50,L=10 壓縮因子1.538數(shù)字圖像處理RLE圖像壓縮圖像壓縮n二值圖像n灰度圖像n彩色圖像 RLE圖像壓縮基于這樣的事實(shí)：如果我們?cè)谠搱D像中隨機(jī)選擇一個(gè)

13、像素，其相鄰像素色彩相同的可能性很大，因此壓縮器逐行掃描位圖，搜索色彩相同之像素的游程。數(shù)字圖像處理二值圖像二值圖像n假設(shè)圖像從黑像素或白像素開始，按行掃描位圖，給出黑白像素的游程。n例如：開始17個(gè)白像素，其后跟隨一個(gè)黑像素，再跟55個(gè)白像素等，則把17，1，55，寫入壓縮流。數(shù)字圖像處理灰度圖像灰度圖像n12,12,12,12,12,12,12,12,12,35,76,112,67,87,87,87,5,5,5,5,5,5,1, 被壓縮為n9，12，35，76，112，67，3，87，6，5，1，n我們要區(qū)分是含灰度值的字節(jié)和含計(jì)數(shù)值的字節(jié)，解決方法如下：數(shù)字圖像處理區(qū)分灰度值和游程的方法

14、區(qū)分灰度值和游程的方法n如果圖像限制為只有128級(jí)灰度，我們可以用每個(gè)字節(jié)中的一位來表示該字節(jié)所含的是灰度值還是計(jì)數(shù)值。n如果灰度級(jí)為256，則可降為255，保留一個(gè)值作標(biāo)志，至于每個(gè)游程計(jì)數(shù)字節(jié)之前。n每字節(jié)均加一位，以表示該字節(jié)所含是灰度值還是計(jì)數(shù)值。此時(shí)這些附加位每8個(gè)累計(jì)為一組，每組先于其所屬的8個(gè)字節(jié)寫到輸出流中數(shù)字圖像處理彩色圖像彩色圖像n對(duì)于彩色圖像，通常將每像素存為3個(gè)字節(jié)，代表其紅、綠、藍(lán)3基色的強(qiáng)度，因此把像素分成3個(gè)序列，每一序列分別游程編碼。n（171,85,34）、(172,85,35)、(172,85,30)、(173,85,33)數(shù)字圖像處理各行單獨(dú)編碼的原因各行

15、單獨(dú)編碼的原因n有時(shí)用戶只查看圖像的一般形狀不需要細(xì)節(jié)，各行單獨(dú)編碼可以各行解碼。n逐步重建n可以只抽取圖像的一部分n合并兩幅圖像不必先解碼數(shù)字圖像處理1 通用數(shù)據(jù)壓縮通用數(shù)據(jù)壓縮n1.1 數(shù)據(jù)壓縮概述n1.2 數(shù)據(jù)壓縮主要方法l游程編碼l統(tǒng)計(jì)編碼l字典編碼數(shù)字圖像處理統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼n香農(nóng)-費(fèi)諾編碼n哈夫曼編碼n算術(shù)編碼數(shù)字圖像處理香農(nóng)香農(nóng)-費(fèi)諾編碼費(fèi)諾編碼n信息的度量n變長(zhǎng)碼特性n香農(nóng)費(fèi)諾編碼數(shù)字圖像處理信息的度量信息的度量n給定一個(gè)k位十進(jìn)制數(shù)和一個(gè)k位二進(jìn)制數(shù)，一個(gè)很自然的問題是，這兩個(gè)k數(shù)位包含了多少信息？這可以通過計(jì)算它們?yōu)楸硎就粋€(gè)數(shù)而各自所需的位數(shù)來回答。 2log10logk

16、x 12110 xkkkx32. 310log2數(shù)字圖像處理n給定一個(gè)n進(jìn)制數(shù)，有 ，即1位n進(jìn)制數(shù)所含的信息相當(dāng)于 位二進(jìn)制數(shù)包含的信息。n如果發(fā)射機(jī)傳送一個(gè)符號(hào)需要1/s單位時(shí)間，則其傳送速率是每單位時(shí)間s個(gè)符號(hào)。在一個(gè)單位時(shí)間內(nèi)發(fā)射機(jī)可以發(fā)出s個(gè)符號(hào)，包含的信息量是 位。我們用 表示信息量，單位為位數(shù)/單位時(shí)間。ns2lognsH2lognkx2lognx2log信息的度量信息的度量數(shù)字圖像處理n假設(shè) 在數(shù)據(jù)中出現(xiàn)的概率是 ，自然有 在 的等概率特例下，由 可推出： nppi1ipnP/1121npppPspsnsH222log)/1 (loglogian假定數(shù)據(jù)是由 到 所生成的字符串

17、，這樣一個(gè)集合就是一個(gè)有n個(gè)符號(hào)的字母表。1ana信息的度量信息的度量數(shù)字圖像處理 在數(shù)據(jù)中出現(xiàn)的概率是 ，那么它在單位時(shí)間內(nèi)平均出現(xiàn)了 次，因此它對(duì)H的貢獻(xiàn)是那么n個(gè)符號(hào)對(duì)H的貢獻(xiàn)之和是：ispipiipsp2logiinppsH21logia 這里H表示信息量，是單位時(shí)間傳送的符號(hào)位數(shù)。所以一個(gè)n進(jìn)制符號(hào)所含有的信息量就是H/S（因其需要1/s時(shí)間傳送一個(gè)符號(hào)）或 ，稱為被傳送數(shù)據(jù)的熵（entropy）iinpp21log信息的度量信息的度量數(shù)字圖像處理變長(zhǎng)碼變長(zhǎng)碼 符號(hào) 概率 編碼1 編碼2 0.49 1 1 0.25 01 01 0.25 010 000 0.01 001 0012a1

18、a4a3a數(shù)字圖像處理n因而遵循以下兩條規(guī)則就可以設(shè)計(jì)變長(zhǎng)碼：因而遵循以下兩條規(guī)則就可以設(shè)計(jì)變長(zhǎng)碼：（1）把短碼賦給出現(xiàn)頻率高的字符；）把短碼賦給出現(xiàn)頻率高的字符；（2）遵循前綴性。）遵循前綴性。數(shù)字圖像處理香農(nóng)費(fèi)諾編碼香農(nóng)費(fèi)諾編碼n按概率把符號(hào)從大到小排序n將這些符號(hào)劃分成概率幾乎相同的兩個(gè)子集n一個(gè)子集以開始，另一個(gè)以開始n在按照同樣的步驟劃分這兩個(gè)子集，一直到子集不能被劃分?jǐn)?shù)字圖像處理香農(nóng)-費(fèi)諾編碼 概率 步驟 碼字 1. 0.25 1 1 :11 2. 0.20 1 0 :10 3. 0.15 0 1 1 :011 4. 0.15 0 1 0 :010 5. 0.10 0 0 1 :0

19、01 6. 0.10 0 0 0 1 :0001 7. 0.05 0 0 0 0 :0000數(shù)字圖像處理練習(xí)練習(xí)n首先從第3個(gè)和第4個(gè)符號(hào)中間劃分子集，計(jì)算平均碼長(zhǎng)？數(shù)字圖像處理統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼n香農(nóng)-費(fèi)諾編碼n哈夫曼編碼n算術(shù)編碼數(shù)字圖像處理哈夫曼編碼(Huffman Coding)是可變長(zhǎng)編碼(VLC)的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng) 度最短的碼字，有時(shí)稱之為最佳編碼 在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱熵編碼法），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)

20、）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。 哈夫曼（Huffman）碼數(shù)字圖像處理 例如，在英文中e出現(xiàn)概率很高，而z出現(xiàn)概率則最低。 當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來表示，而z則可能花去25個(gè)位（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)位。 二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率

21、的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。 哈夫曼（Huffman）碼數(shù)字圖像處理 哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。 哈夫曼（Huffman）碼數(shù)字圖像處理一、二進(jìn)制哈夫曼編碼二進(jìn)制哈夫曼編碼1.步驟步驟(1) 信源符號(hào)按概率分布大小，以遞減次序排列； (2) 取兩個(gè)最小的概率，分別賦以“0”,“1”;然后把這兩個(gè)概率值相加，作為新概率值與其他概率重新排序(3) 按重排概率

22、值，重復(fù)(2), 直到概率和達(dá)到1為止(4) 由后向前由后向前排列碼序，即得哈夫曼編碼哈夫曼（Huffman）碼數(shù)字圖像處理2. 例題例題 x1 0.4 x2 0.2 x3 0.2 x4 0.1 x5 0.1平均碼長(zhǎng)碼方差12=E(li-L)2=p(xi) (li-L)2 = 1.36 0.20.40.61.00101010112.2/K 碼符號(hào)信源符號(hào)X:p(x)(0.4,0.2,0.2,0.1,0.1)（合并后概率下放合并后概率下放）哈夫曼（Huffman）碼01100000100011數(shù)字圖像處理n方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面；哈夫曼（Huffman）碼數(shù)字圖像處理

23、3. 上例上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1010.20.40.61.0010101（合并后概率上放）（合并后概率上放）哈夫曼（Huffman）碼數(shù)字圖像處理 3. 上例上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長(zhǎng) 碼方差22 = 0.16 兩法平均碼長(zhǎng)相同，故信息率R、冗余度相同；但碼方差不同，碼方差小要好.010.20.40.61.001010122.2/K 碼符號(hào) 信源符號(hào)（合并后概率上放）（合并后概率上放）哈夫曼（Huffman）碼數(shù)字圖像處理n方法二：合

24、并后的新符號(hào)排在其它相同概率符號(hào)的前面.哈夫曼（Huffman）碼數(shù)字圖像處理兩種編碼的平均碼長(zhǎng)是一樣的，都是2.2，那一種更好呢，我們可以計(jì)算一下平均碼長(zhǎng)的方差。511( )0.4 1 0.2 20.2 30.1 40.1 42.2iiiLP s l 521( )0.4 20.2 20.2 20.1 30.1 32.2iiiLP s l 2221() ( )()qiiiiE lLP slL522111( )()1.36iiiP slL522221( )()0.16iiiP slL定義碼字長(zhǎng)度的方差2：哈夫曼（Huffman）碼數(shù)字圖像處理n可見：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種

25、編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。l第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；l第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；l顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。結(jié)論結(jié)論：在哈夫曼編碼過程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。哈夫曼（Huffman）碼數(shù)字圖像處理 3. 上例上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均碼長(zhǎng) 結(jié)論結(jié)論 碼方差22 = 0.16 兩法平均碼長(zhǎng)相同，故信息率R、冗余度相同；但

26、碼方差不同，碼方差小要好.010.20.40.61.001010122.2/K 碼符號(hào) 信源符號(hào)（合并后概率上放）（合并后概率上放）哈夫曼（Huffman）碼數(shù)字圖像處理定理：定理：在變長(zhǎng)編碼中，若各碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小逆序排列，則其平均長(zhǎng)度為最小。結(jié)論結(jié)論：哈夫曼編碼方法，它完全依據(jù)字符出現(xiàn)概率來構(gòu)造平均長(zhǎng)度最短的異字頭碼字，有時(shí)稱之為最佳編碼。 哈夫曼（Huffman）碼數(shù)字圖像處理 應(yīng)該指出的是，由霍夫曼編碼過程編出的最佳碼不是唯一的，但其平均碼長(zhǎng)是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。 此外，由于碼長(zhǎng)不等，還存在一個(gè)輸入與輸出的速率匹配問題。解決的辦法是設(shè)置一定容

27、量的緩沖寄存器。 而隨著微電子與計(jì)算技術(shù)的發(fā)展，霍夫曼編碼已可做成單片IC，并成為許多國際標(biāo)準(zhǔn)中的主要技術(shù)內(nèi)核之一。能夠用較低的處理代價(jià)，來換取昂貴的通信開銷，是完全值得的。哈夫曼（Huffman）碼方差最小者最佳方差最小者最佳數(shù)字圖像處理0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.04011 x3 0.10000 x4 0.1001 x2 0.18 1 x1 0.4010010110101010000000001000011哈夫曼（Huffman）碼4.4.例

28、題例題X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)數(shù)字圖像處理二、二、D進(jìn)制哈夫曼編碼進(jìn)制哈夫曼編碼1. 編碼步驟同二進(jìn)制，但需注意兩點(diǎn)：每次取最小的D個(gè)概率,分別賦以0,1, D-1；信源符號(hào)個(gè)數(shù)r必須滿足：r=(D-1)+D. 當(dāng)r不滿足時(shí)，在信源符號(hào)集中補(bǔ)充一些對(duì)應(yīng)概率為0的符號(hào).哈夫曼（Huffman）碼數(shù)字圖像處理 2.例題例題某離散無記憶信源符號(hào)集某離散無記憶信源符號(hào)集a1,a2,a3,a4,a5,a6,a7,a8，a9，已知所對(duì)應(yīng)的概率，試對(duì)其進(jìn)行四元編碼！，已知所對(duì)應(yīng)的概率，試對(duì)其進(jìn)行四元編碼！ 哈夫曼（Huffman）碼解：其中D

29、=4. 若取=2可得大于9但與9最接近的正整數(shù)10，因此在編碼時(shí)加入一個(gè)零概率符號(hào).對(duì)其進(jìn)行四元編碼： 數(shù)字圖像處理 0.40.10.20.10.050.070.050.010.0200.080.3201301230123a1a2a3a4a5a6a7a8a9哈夫曼（Huffman）碼數(shù)字圖像處理n哈夫曼碼考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮；n哈夫曼碼的編碼方法都不惟一；n哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求，編碼效率比較高，因此綜合性較優(yōu).哈夫曼（Huffman）碼數(shù)字圖像處理nHuffman碼在具體實(shí)用時(shí)，設(shè)備較復(fù)雜.在編碼

30、器中需要增加緩沖寄存器，因?yàn)槊總€(gè)信源符號(hào)所對(duì)應(yīng)的碼符號(hào)長(zhǎng)度不一，負(fù)責(zé)會(huì)造成輸入和輸出不能保持平衡.優(yōu)點(diǎn)：提高編碼效率；缺點(diǎn)：需要大量緩沖設(shè)備來存儲(chǔ)這些變長(zhǎng)碼，然后再以恒定的碼率進(jìn)行傳送；在傳輸?shù)倪^程中如果出現(xiàn)了誤碼，容易引起錯(cuò)誤擴(kuò)散，所以要求有優(yōu)質(zhì)的信道。哈夫曼（Huffman）碼數(shù)字圖像處理哈夫曼碼也是譯碼的工具：哈夫曼碼也是譯碼的工具：哈夫曼（Huffman）碼數(shù)字圖像處理0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.04011 x3 0.10000 x4 0

31、.1001 x2 0.18 1 x1 0.40哈夫曼（Huffman）碼4.4.例題例題X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)數(shù)字圖像處理10010110101010000000001000011哈夫曼（Huffman）碼4.4.例題例題 X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04)若接收的字符串是：若接收的字符串是：00010100101100011000101001011000110001010010110001100010100101100011數(shù)字圖像處理統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼n香農(nóng)-費(fèi)諾編碼n哈

32、夫曼編碼n算術(shù)編碼數(shù)字圖像處理算術(shù)編碼算術(shù)編碼算法思想HuffmanHuffman編碼中編碼中每個(gè)符號(hào)每個(gè)符號(hào)都用都用整數(shù)個(gè)整數(shù)個(gè)bitsbits來表來表示，影響編碼效率。示，影響編碼效率。若能把若能把一串符號(hào)一串符號(hào)作為編碼單位，則效率還可作為編碼單位，則效率還可提高。提高。符號(hào)串的區(qū)間表示法設(shè)符號(hào)串為：設(shè)符號(hào)串為： bacedbbdea bacedbbdea 則它可以映射成為則它可以映射成為0 0，1 1）中的唯一的一個(gè)子）中的唯一的一個(gè)子區(qū)間。區(qū)間。數(shù)字圖像處理00.20.50.60.81abcdeabcdeabcdeabcde0.2b 0.5a 0.260.2360.20.23字符ab

33、cde概率0.20.30.10.20.2范圍0,0.2) 0.2,0.5)0.5,0.6) 0.6,0.8) 0.8,1.0)數(shù)字圖像處理high為編碼區(qū)間的高端,low為低端,range為區(qū)間長(zhǎng)度, lowrange為字符分配區(qū)間的低端 highrange 為區(qū)間的高端。初始化： high=1,low=0,range=high-low=1 一個(gè)字符編碼后新的low和high為：Low=low+range* lowrangeHigh=low+range* highrange0子區(qū)間1lowlowhighhighrangerangelowlowrangerangehighhigh數(shù)字圖像處理計(jì)算

34、過程： 1）將 0，1）區(qū)間按照概率的比例分配給五個(gè)字符，即（如圖形表示）： a= 0，0.2， b= 0.2，0.5, c= 0.5，0.6 d= 0.6，0.8 e= 0.8，1)high=1,low=0,range=high-low=1 2)輸入第一個(gè)字符 b，得b.high=0.5,b.low=0.2b.range=b.high-b.low=0.3 3)將 0.2，0.5）區(qū)間按照概率的比例分配給五個(gè)字符，如圖形表示。數(shù)字圖像處理 4)輸入第二個(gè)字符 a，得a.high=0.26,a.low=0.2a.range=a.high-a.low=0.06 5)將 0.2，0.26）區(qū)間按照概

35、率的比例分配給五個(gè)字符，如圖形表示。 6)輸入第三個(gè)字符 c，得c.high=0.236,c.low=0.23c.range=c.high-c.low=0.006依次重復(fù)輸入后續(xù)字符，重復(fù)執(zhí)行5)-6）步,直到輸入最后一個(gè)字符。在最后這個(gè)區(qū)間內(nèi)選擇ENDc.low , 將它變成二進(jìn)制 ，去掉前面的 0 和小數(shù)點(diǎn)，我們可以輸出二進(jìn)制數(shù)這就是被壓縮后的結(jié)果。數(shù)字圖像處理 編碼過程首先定義Low和High兩個(gè)變量，并設(shè)置 Low0 High1當(dāng)讀入和處理字符時(shí)，Low和High按照如下方式更新 NewHigh：OldLow+RangeHighRange（X）; NewLow：OldLow+Range

36、LowRange（X）；其中RangeOldHighOldLow， LowRange（X）和HighRange（X）表示符號(hào)X所對(duì)應(yīng)區(qū)間的下限和上限。數(shù)字圖像處理 例：給出對(duì)短串“SWISS MISS”的壓縮步驟。 字符 頻率 概率 范圍 累計(jì)頻率 Total CumFreq 10 S 5 5/10=0.5 0.5,1.0) 5 W 1 0.1 0.4,0.5) 4 I 2 0.2 0.2,0.4) 2 M 1 0.1 0.1,0.2) 1 1 0.1 0.0,0.1) 0 概率和頻率表數(shù)字圖像處理 算法編碼過程 字符 Low和High的計(jì)算 S L 0.0+(1-0.0) 0.5=0.5 H

37、 0.0+(1-0.0) 1.0=1.0 W L 0.5+(1.0-0.5) 0.4=0.7 H 0.5+(1.0-0.5) 0.5=0.75 I L 0.7+(0.75-0.70) 0.2=0.71 H 0.7+(0.75-0.70) 0.4=0.72 S L 0.71+(0.72-0.71) 0.5=0.715 H 0.71+(0.72-0.71) 1.0=0.72數(shù)字圖像處理 S L 0.715+(0.72-0.715) 0.5=0.7175 H 0.715+(0.72-0.715) 1.0=0.72 L 0.7175+(0.72-0.7175) 0.0=0.7175 H 0.7175+(0.72-0.7175) 0.1=0.71775 M L 0.7175+(0.71775-0.7175) 0.1=