多媒體圖像編碼分類ppt課件

1、Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.1多媒體圖像編碼分類多媒體圖像編碼分類多媒體數(shù)據(jù)緊縮編碼PCM 量化預(yù)測(cè)編碼DPCM基于頻率變換編碼子帶編碼小波變換編碼基于統(tǒng)計(jì)哈夫曼編碼算術(shù)編碼游程編碼RLE國(guó)際規(guī)范JPEG規(guī)范規(guī)范靜態(tài)圖像靜態(tài)圖像MPEG規(guī)范電視圖像H.261可視通訊MHEG規(guī)范超媒體Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.2多媒體中心技術(shù)：緊縮多媒體中心技術(shù)：緊縮數(shù)據(jù)緊縮來源于

2、 40 年代由 Claude Shannon 首創(chuàng)的信息論，其根本原理即信息終究能被緊縮到多小，至今依然遵照信息論中的一條定理，這條定理借用了熱力學(xué)中的名詞“熵( Entropy )來表示一條信息中真正需求編碼的信息量思索用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個(gè)符號(hào)的某條信息編碼，假設(shè)符號(hào) Fn 在整條信息中反復(fù)出現(xiàn)的概率為 Pn，那么該符號(hào)的熵也即表示該符號(hào)所需的位數(shù) 思索用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個(gè)符號(hào)的某條信息編碼，假設(shè)符號(hào) Fn 在整條信息中反復(fù)出現(xiàn)的概率為 Pn，那么該符號(hào)的熵也即表示該符號(hào)所需的位數(shù)位為： En = - log2( Pn ) 整條信息的熵也即

3、表示整條信息所需的位數(shù)為：E = En 舉個(gè)例子，對(duì)下面這條只出現(xiàn)了 a b c 三個(gè)字符的字符串： aabbaccbaa 字符串長(zhǎng)度為 10，字符 a b c 分別出現(xiàn)了 5 3 2 次，那么 a b c 在信息中出現(xiàn)的概率分別為 0.5 0.3 0.2，他們的熵分別為： Ea = -log2(0.5) = 1 Eb = -log2(0.3) = 1.737 Ec = -log2(0.2) = 2.322 整條信息的熵也即表達(dá)整個(gè)字符串需求的位數(shù)為： E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位 假設(shè)用計(jì)算機(jī)中的 ASCII 編碼，表示上面的字符串需求整整

4、80 位呢！簡(jiǎn)單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號(hào)，這就是數(shù)據(jù)緊縮的根本準(zhǔn)那么。Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.4無損數(shù)據(jù)緊縮概念無損數(shù)據(jù)緊縮概念方式：無損,有損無損(lossless compression,redundancy reduction)緊縮后的數(shù)據(jù)可以完全恢復(fù)，如磁盤上的數(shù)據(jù)文件， 緊縮后是原來的1/21/4算法有：Huffman, RLE,算術(shù)編碼，詞典編碼有損：lossy,不可逆緊縮。聲音、圖像中的變換編碼，例如，DM, APCM, DPCM(圖3-14由于存

5、在量化器Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.54.1 Shannon4.1 Shannon的信息論與數(shù)據(jù)緊縮的信息論與數(shù)據(jù)緊縮1. 1948年Shannon香農(nóng)創(chuàng)建的信息論：數(shù)據(jù)緊縮實(shí)際極限。數(shù)據(jù)緊縮的技術(shù)途徑。緊縮原理：信源中信息分布不均勻；信源中信息含有冗余相關(guān)性Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.6舉例舉例26個(gè)字母和一個(gè)分隔符，共27個(gè)字符組成的英文文件，看成信源，該信源的

6、極限(根據(jù)字符出現(xiàn)的頻率不同)： H(x)=1.4bit/字符緣由：27個(gè)字符編碼，5bits分布不均勻：如a,b,c的出現(xiàn)頻率比x,y,z高信源相關(guān)系：er,ture,ed,ing等Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.72. 信息熵entropy問題：隨機(jī)變量的一個(gè)取值a，攜帶的信息量是多少？相關(guān)概念：音訊：數(shù)據(jù)、電報(bào)、。信息：對(duì)音訊加工，有特定價(jià)值一個(gè)信息帶有一定的信息量，大小不等例子一個(gè)音訊：某實(shí)驗(yàn)勝利實(shí)驗(yàn)人員估計(jì)勝利的能夠性99%：信息量很小實(shí)驗(yàn)人員估計(jì)勝利的能夠性1%：信息量很

7、大Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.83. 信息量：在收到信息以前，處于某種不確定形狀中，收到信息之后，消除或部分消除了此不確定性。消除不確定性多少，就可以作為信息的度量。4. Shannon 用概率闡明這一概念事件出現(xiàn)的概率小，相當(dāng)于不確定性多，反之，那么少。Pi為事件ai發(fā)生的概率，那么ai出現(xiàn)后的自信息量為 I(ai)=-log piDistributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.95

8、.信息熵Entropy表示每出現(xiàn)一個(gè)字符所給出的平均信息量。jjn21n21p logp-H(x)p,.,p,p,a,.,a,aX。信息熵為概率分別是的取值為某隨機(jī)變量Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.10“底不同而值不同，因此單位也就不同當(dāng)取底為r的整數(shù)時(shí)，那么熵的信息單位稱作r進(jìn)制信息單位r=2, 單位為bit比特r=e, 單位為Nat奈特r=10, 單位為Hart(哈特)log不特別闡明時(shí)，取為2Distributed DBMSUniversity of Shanghai for

9、 Science and TechnologyPage 1.11 6. 信息熵的了解：處于事件發(fā)生之前，根據(jù)先驗(yàn)概率Pj, 就有 不同確實(shí)定性存在，I(ai)與H(x)都是不確定性度量。當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇性的度量但出于事件發(fā)生之后，不確定性已被解除，那么是獲得信息的度量可以以為是事件隨機(jī)性的度量，因其僅僅對(duì)概率Pj取另個(gè)坐標(biāo)而已。7. H(x)就是對(duì)離散信源進(jìn)展無失真編碼時(shí)的碼長(zhǎng)極限。8.舉例信源取4個(gè)符號(hào)a1,a2,a3,a4,概率1/2，1/4，1/8，1/8 信源的熵H(x)=1.75 bit/字符 假設(shè)用編碼(0, 10, 110, 111), 那么平均碼長(zhǎng)=1.75思索以

10、下幾種變長(zhǎng)編碼：碼獨(dú)一可譯 例1：例4.1例2：8個(gè)字符具有等能夠性例3：字符的分布知： P=(0.9,0.02,0.02,0.02,0.01,0.01,0.01,0.01) H(p)=0.74bit/字符信源字母概率碼A碼B碼Ca1a2a3a4練習(xí)信源X中有16個(gè)隨機(jī)事件，即n=16。每一個(gè)隨機(jī)事件的概率都相等，即P(x1)=P(x2)=P(x3) =P(x16)=1/16，計(jì)算信源X的熵。H Xbitsj()log 11621161164=Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.159.

11、 Huffman 9. Huffman 編碼編碼H(S) = (15/39) * log2 (39/15) + (7/39) * log2 (39/7) + + (5/39) * log2 (39/5) = 2.1859緊縮比1.37:1。Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.16練習(xí)練習(xí)信源符號(hào)的概率如下，畫出其Huffman編碼的編碼樹并給出各符號(hào)的編碼以及碼長(zhǎng)，最后求出平均碼長(zhǎng) XX1X2X3X4X5X6P(X)0.350.200.150.100.100.10Distributed

12、DBMSUniversity of Shanghai for Science and TechnologyPage 1.17哈夫曼編碼 X1 01X2 10X3 11X4 000X5 0010X6 0011 平均碼長(zhǎng)：= 2.45 Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.18.2 .2 算術(shù)編碼算術(shù)編碼提出Rissanen1976年提出。在JPEG與JBIGBi-level image)中都有算術(shù)編碼的內(nèi)容。2. 思想把信源符號(hào)構(gòu)成的串S, 獨(dú)一地映射到實(shí)數(shù)軸上0，1之間的一個(gè)實(shí)數(shù)。前提：知

13、道信源每個(gè)符號(hào)的概率。Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.193. 舉例假設(shè)信源由四個(gè)符號(hào)a1,a2,a3,a4組成，這些符號(hào)的概率分別是0.1,0.4,0.2,0.3).a1,a2,a3,a4四個(gè)符號(hào)的二進(jìn)制編碼分別為00，01，10，11符號(hào)序列S=a3 a1 a4 a1 a3 a4 a2的二進(jìn)制序列為10 00 11 00 10 11 01編碼：把S映射到0，1之間的實(shí)數(shù)的 過程, 見教材譯碼:見教。Distributed DBMSUniversity of Shanghai fo

14、r Science and TechnologyPage 1.204.3 RLE4.3 RLE編碼編碼Run Length EncodingRun Length Encoding是一種運(yùn)用廣泛的簡(jiǎn)單熵編碼，它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于機(jī)。 RLE原理：圖像靜止圖像的相鄰像素相關(guān)性灰度、彩色。用二元組行程，灰度或彩色值表示。Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.21例子例子假定一幅灰度圖象，第n行的象素值為用RLE編碼方法得到的代碼為：803150

15、84180。代碼中用藍(lán)色數(shù)字是行程長(zhǎng)度，藍(lán)字后面的數(shù)字代表象素的顏色值。50代表有延續(xù)代表有延續(xù)50個(gè)象素具有一樣的顏色值，它的顏色值是個(gè)象素具有一樣的顏色值，它的顏色值是8Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.223.缺乏：隨機(jī)顏色豐富的圖像，平均碼長(zhǎng)添加。不是單獨(dú)運(yùn)用RLE一種編碼方法，而是和其他緊縮技術(shù)結(jié)合運(yùn)用。Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.234.4 4.4 詞典編碼詞

16、典編碼思想Huffman編碼：符號(hào)的概率知，概率大的符號(hào)分配較短的碼字。字符間的相關(guān)性信息沒有用上。將長(zhǎng)度不同的符號(hào)串短語編碼成一個(gè)個(gè)新的單詞。每個(gè)符號(hào)串分配一個(gè)編碼。編碼等長(zhǎng)如12位二進(jìn)制。2. 提出：以色列J. Ziv 與A. Lempel,LZ77,LZ78, 1984,T. A. Welch提出LZW,在Unix中運(yùn)用。LZ系列算法Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.24運(yùn)用范圍運(yùn)用范圍LZ77 、LZSS 、LZ78 、LZW算法以及它們的各種變體幾乎壟斷了整個(gè)通用數(shù)據(jù)緊縮領(lǐng)域

17、，我們熟習(xí)的PKZIP、WinZIP、WinRAR、gzip等緊縮工具以及ZIP、 GIF、PNG等文件格式都是LZ系列算法的受害者，甚至連PGP這樣的加密文件格式也選擇了LZ系列算法作為其數(shù)據(jù)緊縮的規(guī)范。 Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.25詞典編碼舉例詞典編碼舉例LZ77編碼術(shù)語輸入字符流(input stream):一串字符字符(character)：一個(gè)符號(hào)編碼位置(coding position)：輸出的編碼前向緩沖器(lookahead buffer)：?jiǎn)卧~編碼窗口(wi

18、ndow)指針(pointer)Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.26詞典編碼舉例詞典編碼舉例LZ78編碼術(shù)語字符流:一串字符字符：一個(gè)符號(hào)碼字流：輸出的編碼碼字：?jiǎn)卧~編碼前綴綴符串詞典：綴符串、碼字 構(gòu)成的對(duì)應(yīng)表Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.27LZ78LZ78算法算法思想：不斷從字符流中構(gòu)成新的綴符串綴符串作為新的詞條存入字典中，并給該詞條分配一個(gè)碼字。對(duì)字符流的編碼就

19、用“(綴的編碼 ,字符)表示輸出碼字流由“(綴的編碼 ,字符)編碼算法譯碼算法Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.28LZ78LZ78編碼算法編碼算法步驟1:將詞典和當(dāng)前前綴P都初始化為空. 步驟2:當(dāng)前字符C:=字符流中的下一個(gè)字符. 步驟3:判別P+C能否在詞典中 (1)假設(shè)是,那么用C擴(kuò)展P,即讓P:=P+C,前往到步驟2. (2)假設(shè)否,那么輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字W和當(dāng)前字符C, 即(W,C); 將P+C添加到詞典中; 令P:=空值,并前往到步驟2 3判別字符流中能否還有字

20、符需求編碼：如“是，前往步驟2，如“否，假設(shè)當(dāng)前前綴P不是空，輸出呼應(yīng)與當(dāng)前前綴P的碼字，然后終了Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.29LZ78LZ78編碼舉例編碼舉例字符流為：ABBCBCABA詞典與碼字流輸出位置字符1A2B3B4C5B6C7A8B9A序號(hào)位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)Distributed DBMSUniversity of Shanghai for Science and Technology

21、Page 1.30LZ78LZ78譯碼譯碼收到信息碼字，字符流：(0,A)(0,B)(2,C)(3,A)(2,A)自動(dòng)構(gòu)造詞典算法步驟一：開場(chǎng)時(shí) 詞典是空的步驟二：當(dāng)前碼字W:=下一個(gè)碼字步驟三：當(dāng)前字符C:=緊隨碼字之后的字符步驟四：把當(dāng)前碼字的綴符串string.W輸出到字符流，然后輸出字符C步驟五：把string.W+C添加到詞典中反復(fù)直到一切碼字，字符流終了重構(gòu)出來的詞典與編碼時(shí)生成的詞典完全一樣Distributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.312.LZW與LZ78相比，有如下特點(diǎn)一切能夠

22、出現(xiàn)的字符都事先放在字典中。輸出的碼字流中僅由詞典中的碼字組成。編碼算法思想Greedy parsing algorithm:檢查字符流中的字符串，Prefix.C, 其中Prefix是字典中最長(zhǎng)的字符串，C是一個(gè)字符Prefix.C不在字典中。Prefix.C放入字典中。輸出 Prefix.C的編號(hào)例 ABBABABACDistributed DBMSUniversity of Shanghai for Science and TechnologyPage 1.32LZWLZW編碼算法編碼算法步驟1:將詞典初始化為包含一切能夠的單字符,當(dāng)前前綴P初始化為空. 步驟2:當(dāng)前字符C:=字符流中的下一個(gè)字符. 步驟3:判別P+C能否在詞典中 (1)假設(shè)是,那么用C擴(kuò)展P,即