1、多媒體技術基礎及應用第4章 多媒體數(shù)據(jù)壓縮編碼技術4.1 多媒體數(shù)據(jù)壓縮編碼的重要性和分類4.2 量化 4.3 統(tǒng)計編碼4.4 預測編碼4.5 變換編碼4.6 多媒體數(shù)據(jù)壓縮編碼的國際標準2多媒體技術基礎及應用第4章 多媒體數(shù)據(jù)壓縮編碼技術本章講課思路:靜態(tài)圖像壓縮編碼的國際標準(JPEG)變換編碼統(tǒng)計編碼預測編碼數(shù)據(jù)壓縮的基本概念3多媒體技術基礎及應用第二部分（一）統(tǒng)計編碼4多媒體技術基礎及應用信息熵的概念最大信息熵定理 數(shù)據(jù)壓縮的理論極限統(tǒng)計編碼算法的設計 變字長定理哈夫曼編碼、算術編碼 4.3 統(tǒng)計編碼本節(jié)的講課思路：5多媒體技術基礎及應用 1.信息:是用不確定性的量度定義的。 2.信息

2、量:從N個相等可能事件中選出 一個事件所需要的信息度量或含量。 3.熵:如果將信源所有可能事件信息量 進行平均就得到信息的熵(熵就是平 均信息量)。4.3.1 統(tǒng)計編碼原理信息量和信息熵6多媒體技術基礎及應用也就是說信息被假設為由一系列的隨機變量所代表，它們往往用隨機出現(xiàn)的符號來表示。 信息7多媒體技術基礎及應用一般地說，信源發(fā)出的消息是一個隨機過程，它是時間與空間的函數(shù)。例如：語音信號時間函數(shù)X(t)；靜止平面圖像空間函數(shù)X(x,y)；電視信號時空（間）函數(shù)X(x,y,t)；電報信號時間離散信號；書信空間上離散的符號序列文字。8多媒體技術基礎及應用要注意理解這個概念中的“不確定性”、“隨機”

3、性、“度量”性，也就是說當你收到一條消息（一定內容）之前，某一事件處于不確定的狀態(tài)中，當你收到消息后，分解除不確定性，從而獲得信息，因此去除不確定性的多少就成為信息的度量。信息9多媒體技術基礎及應用一個消息的可能性愈小，其信息含量愈大；反之，消息的可能性愈大，其信息含量愈小。信息10多媒體技術基礎及應用 1.信息:是用不確定性的量度定義的。 2.信息量:從N個相等可能事件中選出 一個事件所需要的信息度量或含量。 3.熵:如果將信源所有可能事件信息量 進行平均就得到信息的熵(熵就是平 均信息量)。4.3.1 統(tǒng)計編碼原理信息量和信息熵11多媒體技術基礎及應用例如：從64個數(shù)（1-64的整數(shù)）中選

4、定某一個數(shù)（采用折半查找算法），提問：“是否大于32？”，則不論回答是與否，都消去半數(shù)的可能事件，如此下去，只要問6次這類問題，就可以從64個數(shù)中選定一個數(shù)，則所需的信息量是 =6（bit） 信息量12多媒體技術基礎及應用設從N中選定任一個數(shù)X的概率為P(xi)，假定任選一個數(shù)的概率都相等，即 ，則信息量I(xi)可定義為： 信息量13多媒體技術基礎及應用信息量設底取大于1的整數(shù)， 當 ，相應的信息量單位為比特（bit）；當 ，相應的信息量單位為奈特（Nat）；當 ，相應的信息量單位為哈特（Hart）； 14多媒體技術基礎及應用 1.信息:是用不確定性的量度定義的。 2.信息量:從N個相等可能

5、事件中選出 一個事件所需要的信息度量或含量。 3.熵:如果將信源所有可能事件信息量 進行平均就得到信息的熵(熵就是平 均信息量)。4.3.1 統(tǒng)計編碼原理信息量和信息熵15多媒體技術基礎及應用 在信息論中稱為信源的“熵” (Entropy) ，它的含義是信源發(fā)出任意一個隨機變量的平均信息量。 信息熵16多媒體技術基礎及應用信息熵的概念信息量:信息熵:17多媒體技術基礎及應用信息熵的概念信源X中有16個隨機事件，即n=16。每一個隨機事件的概率分別為：X1-X81/32 ； X9-X121/16；X13-X161/8，請寫出信息熵的計算公式并計算信源X的熵。 18多媒體技術基礎及應用信息熵的概念

6、19多媒體技術基礎及應用(1)當處于事件發(fā)生之前，是不確定性的度量；(2)當處于事件發(fā)生之時，是一種驚奇性的度量；(3)當處于事件發(fā)生之后，是獲得信息的度量；(4)還可以理解為是事件隨機性的度量。解釋和理解信息熵有4種樣式：20多媒體技術基礎及應用最大離散熵定理：所有概率分布P（Xi）所構成的熵，以等概率時為最大。統(tǒng)計編碼的理論基礎21多媒體技術基礎及應用最大離散熵定理以信源X中有8個隨機事件，即n=8。每一個隨機事件的概率都相等，信源X的熵為： 即當 時，信源X的熵 22多媒體技術基礎及應用 熵的范圍： 只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。這就是統(tǒng)計編碼的理論基礎。 統(tǒng)計編碼的

7、理論基礎23多媒體技術基礎及應用如果要求在編碼過程中不丟失信息量，即要求保存信息熵，這種信息保持編碼又叫做熵保存編碼，或者叫熵編碼。特性：熵編碼是無失真數(shù)據(jù)壓縮，用這種編碼結果經解碼后可無失真地恢復出原圖像。 熵編碼24多媒體技術基礎及應用 熵的范圍： 只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。這就是統(tǒng)計編碼的理論基礎。 統(tǒng)計編碼的理論基礎25多媒體技術基礎及應用Huffman編碼方法于1952年問世, 是在他的論文“最小冗余度代碼的構造方法（A Method for the Construnction of Minimum Redundancy Codes）”中提出來的。迄今為止,

8、仍經久不衰, 廣泛應用于各種數(shù)據(jù)壓縮技術中, 且仍不失為熵編碼中的最佳編碼方法。4.3.2 赫夫曼（Huffman）編碼26多媒體技術基礎及應用1、變字長編碼定理 在變字長編碼中，對于出現(xiàn)概率大的信息符號，編以短字長的碼,對于出現(xiàn)概率小的信息符號編以長字長的碼，如果碼字長度嚴格按照符號概率的大小的相反順序排列，則平均碼字長一定小于按任何其他符號順序排列方式得到的碼字長度。27多媒體技術基礎及應用英文字母出現(xiàn)的概率按大小排列該英文字母編碼的碼長按大小排列概率大碼長短28多媒體技術基礎及應用證明: 最佳的平均碼字長度: 其中：P(ai)是信源符號ai出現(xiàn)的概率；ni是符號ai的編碼長度。29多媒體

9、技術基礎及應用根據(jù)編碼方法定義規(guī)定： P(ai)=P(as) nins 如果將ai 的碼字與as的碼字互換，則: 30多媒體技術基礎及應用2、哈夫曼編碼 Huffman 編碼就是利用變字長最佳編碼，實現(xiàn)信源符號按概率大小順序排列。31多媒體技術基礎及應用信源符號按概率大小順序排列 (1) 出現(xiàn)概率最小的兩個符號概率相加合成一個概率。32多媒體技術基礎及應用 (2) 將合成概率看成一個新組合符號概率，重復上述做法，直到最后只剩下兩個符號概率為止。33多媒體技術基礎及應用 (3) 反過來逐步向前編碼，每一步有兩個分支各賦予一個二進制碼，可以對概率大的編碼為1。34多媒體技術基礎及應用 例如：a1

10、0.20 01a2 0.19 00a3 0.18 111a4 0.17 110a5 0.15 101a6 0.10 1001a7 0.01 1000 10111000100135多媒體技術基礎及應用 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 36多媒體技術基礎及應用 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 10111000100137多媒體技術基礎及應用 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7

11、 0.01 1011100010010138多媒體技術基礎及應用 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 101110001001010039多媒體技術基礎及應用a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 101110001001010011140多媒體技術基礎及應用a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 101110001001010011111041多媒體技術基礎及應用a1 0.2

12、0 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 101110001001010011111010142多媒體技術基礎及應用 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 1011100010010100111110101100143多媒體技術基礎及應用a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 10111000100101001111101011001100044多媒體技術基礎及應用需要討論的問題：(1)霍夫曼

13、編碼方法構造程序是一致的，但構造出來的碼顯然是不唯一的。(2)霍夫曼編碼的碼字字長參差不齊，硬件實現(xiàn)不易，譯碼電路復雜。 (3)需要知道信源符號的概率分布。在信源概率分布不均勻時，霍夫曼編碼效率高。 (4)霍夫曼編碼表缺省 45多媒體技術基礎及應用解決的辦法是雙字長編碼。 雙字長是只采用兩種字長（短碼字和長碼字）的碼字。出現(xiàn)概率值高的符號用短碼字，出現(xiàn)概率值低的符號用長碼字，短碼字中的一個碼不用，用來做長碼字的前綴。例如：短碼字長為2位（00 01 10 11）其中的“11”可以不用來做短碼字，而是用來做長碼字的前綴 。46多媒體技術基礎及應用 信源為x1 x2 x3 x4 x5 x6 x7七

14、個符號，編碼如下：x1 x2 x3 x4 x5 x6 x7 00 10 01 1100 1101 1110 1111 這種方法稱為2/4編碼法，最多只對應7個符號。還有3/6編碼法，最多只對應15個符號；4/8編碼法，最多只對應31個符號47多媒體技術基礎及應用 多媒體技術基礎及應用呂小星 副教授北京廣播電視大學理工教學部E-Mail: Tel: 6212364848多媒體技術基礎及應用4.3.3 算術編碼原理： 算術編碼方法是將被編碼的信息表示成實數(shù)0和1之間的一個間隔。信息越長編碼表示它的間隙就越小，表示這一間隙所須二進位就越多，大概率符號出現(xiàn)的概率越大對應于區(qū)間愈寬，可用長度較短的碼字表

15、示；小概率符號出現(xiàn)概率越小層間愈窄，需要較長碼字表示。49多媒體技術基礎及應用 初始化子區(qū)間為0，1 MPS為大概率符號, LPS為小概率符號 設 大概率:Pe 小概率: Qe 設置兩個專用寄存器（C，A） C 寄存器的值為子區(qū)域的起始位置 A 寄存器的值為子區(qū)域的寬度QePe50多媒體技術基礎及應用算術編碼實現(xiàn)步驟 第一步：跟據(jù)概率Qe和Pe值，將半開區(qū)間0, 1分割成兩個子區(qū)間。如圖 QePe0 151多媒體技術基礎及應用第二步：當編碼輸入符號流中，第一個來的是“LPS”其輸出碼字應落在0-Qe子區(qū)間內；第一個符號來的是“MPS”，其輸出碼字應落在Qe-1子區(qū)間內QePe0 152多媒體技

16、術基礎及應用 第三步：當?shù)诙杹砼R后，這時相當于對兩個符號編碼。對第一次分割結果的兩個子區(qū)間，依Qe和Pe概率進行再分割，得到四個子區(qū)間。第一個子區(qū)間是0-QeQe，第二個子區(qū)間是QeQe-Qe，第三個子區(qū)間是Qe-Qe+QePe，第四個子區(qū)間是(Qe+QePe)-1。0 1QeQeQeQe+QePe53多媒體技術基礎及應用 第四步：第三個符號來臨后，要區(qū)別以下情況， 當?shù)诙€符號為“LPS”第三個符號也是“LPS”，則對0-QeQe段依概率Qe、Pe分割， 當?shù)诙€符號為“LPS”第三個符號為“MPS ”，則對QeQe-Qe段分割； 當?shù)诙€符號為“MPS”第三個符號為“LPS”，則對Qe

17、-(Qe+QePe)段分割， 當?shù)诙€符號為“MPS”第三個符號為“MPS”，則對(Qe+QePe)-1最后一段分割。 54多媒體技術基礎及應用第五步：以此類推，直到一組符號結束為止。第六步：在最后分割得到的區(qū)間內，找一個最小的二進制小數(shù)，小數(shù)點后的二進制碼字就是所得到的算術編碼。55多媒體技術基礎及應用初始化時：C=0 A=1當小概率符號LPS到來時： C=C A=AQe當大概率符號MPS到來時： C=C+AQe A=APe=A（1-Qe）56多媒體技術基礎及應用例題：已知信源符號為1011，對其進行算術編碼。解：符號“0”為小概率符號,其概率Qe=1/4符號“1”為大概率符號,其概率Pe=

18、3/457多媒體技術基礎及應用初始化： C=0， A=1 Qe=1/4 Pe=3/4“1”， C=C+AQe=0+11/4=1/4 A=APe=13/4=3/4 C=0A=1Qe=1/4Pe=3/458多媒體技術基礎及應用“10”， C=C=1/4 A=A Qe=3/41/4=3/16” CA=3/4Qe=1/4Pe=3/4“10”59多媒體技術基礎及應用“101”， C=C+AQe=1/4+3/161/4=19/64A=APe=3/163/4=9/64” 10160多媒體技術基礎及應用“1011”， C=C+AQe=19/64+9/641/4=85/256A=APe=9/643/4=27/256C=19/64A=9/64Qe=1/4101161多媒體技術基礎及應用C = 85/256 =（）bA = 27/256 = （）b子區(qū)間的尾 =C+A = （）b在子區(qū)間中取一個最小的數(shù)為：（）b取小數(shù)點后面的數(shù)為：“011”，“011”就是所得的算術編碼。 62多媒體技術基礎及應用 0 為LPS Qe= 1/8 =（