【正文】 編碼的壓縮率更高。當(dāng)然壓縮的程度主要取決于數(shù)據(jù)的語(yǔ)義內(nèi)容，比起平均信息量編碼，它的壓縮比更大。簡(jiǎn)而言之，利用信號(hào)原數(shù)據(jù)在時(shí)間域和頻率域中的相關(guān)性和冗余進(jìn)行壓縮的有語(yǔ)義編碼。如： ?預(yù)測(cè)編碼：、 ?變換編碼：、 ?分層編碼：如子采樣、子帶編碼 ?其他編碼：如矢量量化、運(yùn)動(dòng)補(bǔ)償、音感編碼 壓縮編碼的分類 ?混合編碼 ( ) ?混合編碼 = 熵編碼 + 源編碼 ? 大多數(shù)壓縮標(biāo)準(zhǔn)都采用混合編碼的方法進(jìn)行數(shù)據(jù)壓縮，一般是先利用信源編碼進(jìn)行有損壓縮，再利用熵編碼做進(jìn)一步的無(wú)損壓縮。如 、 、等。 壓縮編碼的分類 此外，也可根據(jù)不同的依據(jù)對(duì)數(shù)據(jù)的壓縮算法 進(jìn)行其它不同的分類，如： 按作用域在空間域或頻率域：空間方法、變換方法、混合方法 按是否自適應(yīng)：自適應(yīng)性編碼和非適應(yīng)性（靜態(tài)）編碼 按碼長(zhǎng)：定長(zhǎng)碼和變長(zhǎng)碼 香農(nóng) 范諾 ?香農(nóng) 范諾編碼 (– ) ?在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量 ?在計(jì)算熵時(shí)，如果對(duì)數(shù)的底數(shù)用 2，熵的單位就用“香農(nóng) ()”，也稱“位 ()” ?！拔弧笔?1948年首次使用的術(shù)語(yǔ)。 ? 最早闡述和實(shí)現(xiàn)“從上到下”的熵編碼方法的人是 (1948年 )和 (1949年 )，因此稱為香農(nóng)范諾 ( )編碼法 香農(nóng) 范諾編碼舉例 ? 有一幅 40個(gè)像素組成的灰度圖像，灰度共有 5級(jí)，分別用符號(hào) A， B， C， D和 E表示。 40個(gè)像素中出現(xiàn)灰度 A的像素?cái)?shù)有 15個(gè)，出現(xiàn)灰度 B的像素?cái)?shù)有 7個(gè)，出現(xiàn)灰度 C的像素?cái)?shù)有 7個(gè)，其余情況見(jiàn)表 21 ? (1) 計(jì)算該圖像可能獲得的壓縮比的理論值 ? (2) 對(duì) 5個(gè)符號(hào)進(jìn)行編碼 ? (3) 計(jì)算該圖像可能獲得的壓縮比的實(shí)際值 符號(hào) A B C D E 出現(xiàn)的次數(shù) 15 7 7 6 5 出現(xiàn)的概率 15/40 7/40 7/40 6/40 5/40 香農(nóng) 范諾編碼舉例 理論值 按照常規(guī)的編碼方法，表示 5個(gè)符號(hào)最少需要 3位，如用 000表示 A， 001表示 B， ? ， 100表示 E，其余 3個(gè)代碼 (101， 110， 111)不用。這就意味每個(gè)像素用 3位，編碼這幅圖像總共需要 120位。按照香農(nóng)理論，這幅圖像的熵為 香農(nóng) 范諾編碼舉例 ? 這個(gè)數(shù)值表明，每個(gè)符號(hào)不需要用 3位構(gòu)成的代碼表示，而用 ，因此 40個(gè)像素只需用 ，因此在理論上，這幅圖像的的壓縮比為 120:≈:1 ，實(shí)際上就是3:≈ 香農(nóng) 范諾編碼舉例 (2) 符號(hào)編碼 對(duì)每個(gè)符號(hào)進(jìn)行編碼時(shí)采用 “ 從上到下 ” 的方法。首先按照符號(hào)出現(xiàn)的頻度或概率排序，然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù) 香農(nóng) 范諾編碼舉例 （ 3）壓縮比的實(shí)際值 按照這種方法進(jìn)行編碼需要的總位數(shù)為30+14+14+18+15＝ 91，實(shí)際的壓縮比為120:91≈ : 1 霍夫曼編碼 ?霍夫曼編碼 ( ) ?霍夫曼 (. )在 1952年提出和描述的“從下到上”的熵編碼方法 ?根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來(lái)壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素 (如字母 )出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少 ?廣泛用在 , , 中 霍夫曼編碼 ?基本原理 ?通過(guò)減少編碼冗余來(lái)達(dá)到壓縮的目的。 ?統(tǒng)計(jì)符號(hào)的出現(xiàn)概率，建立一個(gè)概率統(tǒng)計(jì)表 ?將最常出現(xiàn) (概率大的 )的符號(hào)用最短的編碼， ?最少出現(xiàn)的符號(hào)用最長(zhǎng)的編碼。 霍夫曼編碼 具體步驟： 步驟①：按照符號(hào)出現(xiàn)概率大小的順序?qū)Ψ?hào)進(jìn)行排序 步驟②：把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn) P1 步驟③：重復(fù)步驟②，得到節(jié)點(diǎn) P2， P3，P4， …… ， ，形成一棵樹(shù)，其中的稱為根節(jié)點(diǎn) 步驟④：從根節(jié)點(diǎn)開(kāi)始到每個(gè)符號(hào)的樹(shù)葉，從上到下 標(biāo)上 0(上枝 )和 1(下枝 )，至于哪個(gè)為 1哪個(gè)為 0則 無(wú)關(guān)緊要 步驟⑤：從根節(jié)點(diǎn)開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫(xiě)出 每個(gè)符號(hào)的代碼 霍夫曼編碼舉例 d 4 3 2 1 5 7 （共 22*8=176 ) 霍夫曼編碼舉例 c b d a f e 00 10 11 011 0100 0101 1 0 0 1 0 1 1 0 0 1 編碼形式不唯一 4/22)*2(22/4)+(3/22)*2(22/3)+(2/22)*2(22/2)+(1/22)*2(22/1)+(7/22)*2(22/7)+(5/22)*2(22/5)＝ 霍夫曼編碼舉例 ? d （共 22*8=176 ) ? 4 3 2 1 5 7 ? ?經(jīng)過(guò)編碼之后的數(shù)據(jù)為： ? 11111111011011011010001000101101010101000000000000000 ? (共 7*2+5*2+4*2+3*3+2*4+1*4=53 ) ? 霍夫曼編碼 a1 a2 a3 a4 a5 a6 a7 1 0 1 0 1 0 0 0 1 0 1 1 碼字 碼長(zhǎng) 10 2 11 2 000 3 001 3 010 3 0110 4 0111 4 平均碼長(zhǎng)： 熵： 霍夫曼編碼局限性 ?利用霍夫曼編碼，每個(gè)符號(hào)的編碼長(zhǎng)度只能為整數(shù)，所以如果源符號(hào)集的概率分布不是 2負(fù) n次方的形式，則無(wú)法達(dá)到熵極限。 ?輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸 ?譯碼復(fù)雜 ?需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布 ?沒(méi)有錯(cuò)誤保護(hù)功能 應(yīng)用舉例 在圖像的編碼中 首先計(jì)算頻率并以二叉樹(shù)方式進(jìn)行排序來(lái)獲得編碼值，其次用編碼值取代圖像數(shù)據(jù)進(jìn)入圖像文件中。 編碼值的不唯一性 灰度分布很不均勻和很均勻時(shí)的效率 構(gòu)造性差 常用的且有效的方法是： 將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立的編碼。例如：分成 8 8 的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是 64而不是 256）。 應(yīng)用舉例 8*8分塊的編碼效率為 % 16*16分塊的編碼效率約為 61% 全圖的編碼效率為 % 霍夫曼編碼 ?編碼討論 ?編碼是唯一可譯碼。短的碼不會(huì)成為更長(zhǎng)碼的啟始部分； ?編碼的平均碼長(zhǎng)接近于熵 ?缺點(diǎn)：需要多次排序，耗費(fèi)時(shí)間 算術(shù)編碼 ? 編碼的局限性： ? 編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無(wú)法得到最優(yōu)的壓縮效果。假設(shè)某個(gè)字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 2() = 位編碼，但 編碼一定會(huì)為其分配一位 0或一位 1的編碼?？梢韵胂?，整個(gè)信息的 80% 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的 3倍左右。 算術(shù)編碼 ?例 1： ? 在信源的符號(hào)數(shù)目很小的情況 ? X: a b ? P(X): ? H = 0 a b 1 0, 1 算術(shù)編碼 ?例 2：信源的符號(hào)的概率嚴(yán)重不對(duì)稱： ?A = {a, b, c}, P(a) = , P(b) = , P(c) = ?H = ?編碼： ?a 0 ?b 11 ?c 10 ?l = ?冗余（） = l H = (213%!) 算術(shù)編碼 ? 基本思想： ? 考慮對(duì)兩個(gè)字母序列而不是單個(gè)字母編碼 l = 冗余 = （ 27%） 0 111 100 1101 110011 110001 101 110010 110000 算術(shù)編碼 ?該思想還可以繼續(xù)擴(kuò)展 ?考慮長(zhǎng)度為 n的所有可能的 序列 (已做了 32) ?理論上：考慮更長(zhǎng)的序列能提高編碼性能 ?實(shí)際上： ?字母表的指數(shù)增長(zhǎng)將使得這不現(xiàn)實(shí) ?例如：對(duì)長(zhǎng)度為 3的序列： 2563 = 224 = 16M ?需要對(duì)長(zhǎng)度為 n的所有序列產(chǎn)生碼本 ?很多序列的概率可能為 0 ?分布嚴(yán)重不對(duì)稱是真正的大問(wèn)題： ? A = {a, b, c}, P(a) = , P(b) = , P(c) = ? H = ?l1 = , l2 = , … ?當(dāng) n = 8時(shí)編碼性能才變得可接受 ?但此時(shí) = 38 = 6561 !!! 算術(shù)編碼 ?基本思想：算術(shù)編碼不是將單個(gè)信源符號(hào)映射成一個(gè)碼字，而是把整個(gè)消息表示為實(shí)數(shù)線上的 0到1之間的一個(gè)區(qū)間，其長(zhǎng)度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個(gè)代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實(shí)際的編碼輸出。消息序列中的每個(gè)元素都要用來(lái)縮短這個(gè)區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來(lái)表示這個(gè)區(qū)間。 ?采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù) 算術(shù)編碼 ? 符號(hào)串編碼：將串中使用的符號(hào)表按原編碼（如字符的編碼、數(shù)字的二進(jìn)制編碼）從小到大順序排列成表。計(jì)算表中每種符號(hào)出現(xiàn)的概率，然后依次根據(jù)這些符號(hào)概率大小來(lái)確定其在 [0, 1)期間中對(duì)應(yīng)的小區(qū)間范圍 [, )： ? 其中， p0 = 0，顯然，符號(hào)所對(duì)應(yīng)的小區(qū)間的寬度就是其概率 算術(shù)編碼 ? 輸入串編碼：設(shè)串中第 j個(gè)符號(hào)為符號(hào)表中的第 i個(gè)符號(hào)，則可根據(jù)在符號(hào)表中所對(duì)應(yīng)區(qū)間的上下限和，來(lái)計(jì)算編碼區(qū)間 ? = [)。 ? 其中， = 為區(qū)間的寬度，初值 l0 = 0， r0 = 1， d0 = 1。顯然， ↑而與 ↓。 ? 串的最后一個(gè)符號(hào)所對(duì)應(yīng)區(qū)間的下限就是該符號(hào)串的算術(shù)編碼值 . 算術(shù)編碼 ? 通常，對(duì)任意序列 x = x1x2? 只需知道信源的，即信源的概率模型 算術(shù)編碼：編碼和解碼過(guò)程都只涉及算術(shù)運(yùn)算（加、減、乘、除） 舉例 2 字符 概率 a b 要編的字符串 算術(shù)編碼 0 1 a b a [0,) b [,1) ―‖ 0 a b 第一個(gè)為 a，編碼范圍限制在 0～ 1 算術(shù)編碼 0 a b 0 a b 1 對(duì)已知區(qū)間進(jìn)行再次分割 第二個(gè)為 b，編碼范圍限制在 ～ 0 a b 算術(shù)編碼 a b 0 a b 對(duì)已知區(qū)間進(jìn)行再次分割 第 3個(gè)為 a，編碼范圍限制在 [,)范圍內(nèi) 9 a b 算術(shù)編碼 ?在 [,) 中任選一個(gè)浮點(diǎn)數(shù)來(lái)標(biāo)識(shí)這個(gè)區(qū)間，如 ，即可表示我們要編的消息為“” ?把該浮點(diǎn)數(shù)轉(zhuǎn)變?yōu)槎M(jìn)制編碼 : 0010 ?特性： ? 區(qū)間越窄，說(shuō)明符號(hào)串越長(zhǎng)，二進(jìn)制碼長(zhǎng)越長(zhǎng) 舉例 2 ? 假設(shè)信源符號(hào)為 {00, 01, 10, 11}，它們的 概率分別為 { , , , } ? 對(duì)二進(jìn)制消息序列 10 00 11 00 10 11 01 … 進(jìn)行算術(shù)編碼 算術(shù)編碼 ?初始化：根據(jù)信源符號(hào)的概率把間隔 [0, 1)分成如表 2 4所示的 4個(gè)子間隔： [0, ), [, ), [, ), [, 1)。其中 [x, y)的表示半開(kāi)放間隔， 即包含 x不包含 y， x稱為低邊界或左邊界， y 稱為高邊界或右邊界 符號(hào) 00 01 10 11 概率 初始區(qū)間 [0, ) [, ) [, ) [, 1) 算術(shù)編碼 ? 確定符號(hào)的編碼范圍 ? 編碼時(shí)輸入第 1個(gè)符號(hào)是 10，找到它的編碼范圍是 [, ] ? 消息中第 2個(gè)符號(hào) 00的編碼范圍是 [0, )，它的間隔 就取 [, )的第一個(gè)十分之一作為新間隔 [, ) ? 編碼第 3個(gè)符號(hào) 11時(shí)，取新間隔為 [, ) ? 編碼第 4個(gè)符號(hào) 00時(shí)，取新間隔為 [, ) ? 依此類推 …… ? 消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù) 算術(shù)編碼 算術(shù)編碼 算術(shù)編碼 算術(shù)編碼 ?算術(shù)編碼 ?長(zhǎng)度為 n的序列的算術(shù)編碼的平均碼長(zhǎng)為： 算術(shù)編碼的效率高：當(dāng)信源符號(hào)序列很長(zhǎng)，平均碼長(zhǎng)接近信源的熵 ? ?? ? ? ?()1