無損數(shù)據(jù)壓縮課件

多媒體圖像編碼分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測編碼DPCM基于頻率變換編碼子帶編碼小波變換編碼基于統(tǒng)計(jì)哈夫曼編碼算術(shù)編碼游程編碼RLE國際標(biāo)準(zhǔn)JPEG標(biāo)準(zhǔn)（靜態(tài)圖像）MPEG標(biāo)準(zhǔn)（電視圖像）H.261（可視通信）MHEG標(biāo)準(zhǔn)（超媒體）多媒體圖像編碼分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測編碼DPC多媒體核心技術(shù)：壓縮數(shù)據(jù)壓縮起源于40年代由ClaudeShannon首創(chuàng)的信息論，其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學(xué)中的名詞“熵”(Entropy)來表示一條信息中真正需要編碼的信息量考慮用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條信息編碼，假設(shè)符號Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)多媒體核心技術(shù)：壓縮數(shù)據(jù)壓縮起源于40年代由Claud考慮用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條信息編碼，假設(shè)符號Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)位為：

En=-log2(Pn)

整條信息的熵也即表示整條信息所需的位數(shù)為：E=∑En

舉個(gè)例子，對下面這條只出現(xiàn)了abc三個(gè)字符的字符串：

aabbaccbaa

字符串長度為10，字符abc分別出現(xiàn)了532次，則abc在信息中出現(xiàn)的概率分別為0.50.30.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位

如果用計(jì)算機(jī)中的ASCII編碼，表示上面的字符串需要整整80位呢！簡單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號，這就是數(shù)據(jù)壓縮的基本準(zhǔn)則?？紤]用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條3無損數(shù)據(jù)壓縮概念方式：無損,有損無損(losslesscompression,redundancyreduction)壓縮后的數(shù)據(jù)能夠完全恢復(fù)，如磁盤上的數(shù)據(jù)文件，壓縮后是原來的1/2—1/4算法有：Huffman,RLE,算術(shù)編碼，詞典編碼有損：lossy,不可逆壓縮。聲音、圖像中的變換編碼，例如，DM,APCM,DPCM(圖3-14）由于存在量化器無損數(shù)據(jù)壓縮概念方式：無損,有損4.1Shannon的信息論與數(shù)據(jù)壓縮1.1948年Shannon香農(nóng)創(chuàng)立的信息論：數(shù)據(jù)壓縮理論極限。數(shù)據(jù)壓縮的技術(shù)途徑。壓縮原理：信源中信息分布不均勻；信源中信息含有冗余（相關(guān)性）4.1Shannon的信息論與數(shù)據(jù)壓縮1.1948年Sh舉例26個(gè)字母和一個(gè)分隔符，共27個(gè)字符組成的英文文件，看成信源，該信源的極限(根據(jù)字符出現(xiàn)的頻率不同)：H(x)=1.4bit/字符原因：27個(gè)字符編碼，5bits分布不均勻：如a,b,c的出現(xiàn)頻率比x,y,z高信源相關(guān)系：er,ture,ed,ing等舉例26個(gè)字母和一個(gè)分隔符，共27個(gè)字符組成的英文文件，看成2.信息熵entropy問題：隨機(jī)變量的一個(gè)取值a，攜帶的信息量是多少？相關(guān)概念：消息：數(shù)據(jù)、電報(bào)、電話。信息：對消息加工，有特定價(jià)值一個(gè)信息帶有一定的信息量，大小不等例子一個(gè)消息：某試驗(yàn)成功試驗(yàn)人員預(yù)計(jì)成功的可能性99%：信息量很小試驗(yàn)人員預(yù)計(jì)成功的可能性1%：信息量很大2.信息熵entropy3.信息量：在收到信息以前，處于某種不確定狀態(tài)中，收到信息之后，消除或部分消除了此不確定性。消除不確定性多少，就可以作為信息的度量。4.Shannon用概率說明這一概念事件出現(xiàn)的概率小，相當(dāng)于不確定性多，反之，則少。Pi為事件ai發(fā)生的概率，則ai出現(xiàn)后的自信息量為I(ai)=-logpi3.信息量：在收到信息以前，處于某種不確定狀態(tài)中，收到信息5.信息熵（Entropy） 表示每出現(xiàn)一個(gè)字符所給出的平均信息量。5.信息熵（Entropy）“底”不同而值不同，因而單位也就不同當(dāng)取底為r的整數(shù)時(shí)，則熵的信息單位稱作r進(jìn)制信息單位r=2,單位為bit（比特）r=e,單位為Nat（奈特）r=10,單位為Hart(哈特)log不特別說明時(shí)，取為2“底”不同而值不同，因而單位也就不同

6.信息熵的理解：處于事件發(fā)生之前，根據(jù)先驗(yàn)概率Pj,就有不同的確定性存在，I(ai)與H(x)都是不確定性度量。當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇性的度量但出于事件發(fā)生之后，不確定性已被解除，則是獲得信息的度量可以認(rèn)為是事件隨機(jī)性的度量，因其僅僅對概率Pj取另個(gè)坐標(biāo)而已。7.H(x)就是對離散信源進(jìn)行無失真編碼時(shí)的碼長極限。6.信息熵的理解：8.舉例信源取4個(gè)符號a1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用編碼(0,10,110,111),則平均碼長=…=1.75考慮以下幾種變長編碼：碼Ｂ唯一可譯

例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碼Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１8.舉例信源字母概率碼A碼B碼Ca1１／２０００a2１／４１12練習(xí)信源X中有16個(gè)隨機(jī)事件，即n=16。每一個(gè)隨機(jī)事件的概率都相等，即P(x1)=P(x2)=P(x3)=…=P(x16)=1/16，計(jì)算信源X的熵。練習(xí)信源X中有16個(gè)隨機(jī)事件，即n=16。每一個(gè)隨機(jī)事件的概13無損數(shù)據(jù)壓縮課件149.Huffman編碼H(S)=(15/39)*log2(39/15)+(7/39)*log2(39/7)+…+(5/39)*log2(39/5)=2.1859

壓縮比1.37:1。9.Huffman編碼練習(xí)信源符號的概率如下，畫出其Huffman編碼的編碼樹并給出各符號的編碼以及碼長，最后求出平均碼長XX1X2X3X4X5X6P(X)0.350.200.150.100.100.10練習(xí)信源符號的概率如下，畫出其Huffman編碼的編碼樹并給哈夫曼編碼X101X210X311X4000X50010X60011平均碼長：=2.45哈夫曼編碼４.2算術(shù)編碼提出Rissanen1976年提出。在JPEG與JBIG（Bi-levelimage)中都有算術(shù)編碼的內(nèi)容。2.思想把信源符號構(gòu)成的串S,唯一地映射到實(shí)數(shù)軸上（0，1）之間的一個(gè)實(shí)數(shù)。前提：知道信源每個(gè)符號的概率。４.2算術(shù)編碼提出3.舉例假設(shè)信源由四個(gè)符號{a1,a2,a3,a4}組成，這些符號的概率分別是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四個(gè)符號的二進(jìn)制編碼分別為00，01，10，11符號序列S=a3a1a4a1a3a4a2的二進(jìn)制序列為10001100101101編碼：把S映射到（0，1）之間的實(shí)數(shù)的過程,見教材譯碼:見教。3.舉例4.3RLE編碼（RunLengthEncoding）是一種使用廣泛的簡單熵編碼，它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于傳真機(jī)。RLE原理：圖像（靜止圖像）的相鄰像素相關(guān)性（灰度、彩色）。用二元組（行程，灰度或彩色值）表示。4.3RLE編碼（RunLengthEncoding）例子假定一幅灰度圖象，第n行的象素值為用RLE編碼方法得到的代碼為：80315084180。代碼中用藍(lán)色數(shù)字是行程長度，藍(lán)字后面的數(shù)字代表象素的顏色值。50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8例子假定一幅灰度圖象，第n行的象素值為50代表有連續(xù)50個(gè)象3.不足：隨機(jī)色彩豐富的圖像，平均碼長增加。不是單獨(dú)使用RLE一種編碼方法，而是和其他壓縮技術(shù)聯(lián)合應(yīng)用。無損數(shù)據(jù)壓縮課件4.4詞典編碼思想Huffman編碼：符號的概率已知，概率大的符號分配較短的碼字。字符間的相關(guān)性信息沒有用上。將長度不同的符號串（短語）編碼成一個(gè)個(gè)新的單詞。每個(gè)符號串分配一個(gè)編碼。編碼等長（如12位二進(jìn)制）。2.提出：以色列J.Ziv與A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中應(yīng)用。LZ系列算法4.4詞典編碼思想應(yīng)用范圍LZ77、LZSS、LZ78、LZW算法以及它們的各種變體幾乎壟斷了整個(gè)通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者，甚至連PGP這樣的加密文件格式也選擇了LZ系列算法作為其數(shù)據(jù)壓縮的標(biāo)準(zhǔn)。應(yīng)用范圍LZ77、LZSS、LZ78、LZW算法以及它詞典編碼舉例LZ77編碼術(shù)語輸入字符流(inputstream):一串字符字符(character)：一個(gè)符號編碼位置(codingposition)：輸出的編碼前向緩沖器(lookaheadbuffer)：單詞編碼窗口(window)指針(pointer)詞典編碼舉例LZ77編碼詞典編碼舉例LZ78編碼術(shù)語字符流:一串字符字符：一個(gè)符號碼字流：輸出的編碼碼字：單詞編碼前綴綴—符串詞典：綴—符串、碼字構(gòu)成的對應(yīng)表詞典編碼舉例LZ78編碼LZ78算法思想：不斷從字符流中形成新的綴—符串綴—符串作為新的詞條存入字典中，并給該詞條分配一個(gè)碼字。對字符流的編碼就用“(綴的編碼,字符)”表示輸出碼字流由“(綴的編碼,字符)”編碼算法譯碼算法LZ78算法思想：LZ78編碼算法

步驟1:將詞典和當(dāng)前前綴P都初始化為空.

步驟2:當(dāng)前字符C:=字符流中的下一個(gè)字符.

步驟3:判斷P+C是否在詞典中(1)如果"是",則用C擴(kuò)展P,即讓P:=P+C,返回到步驟2.(2)如果"否",則輸出與當(dāng)前前綴P相對應(yīng)的碼字W和當(dāng)前字符C,即(W,C);將P+C添加到詞典中;令P:=空值,并返回到步驟2（3）判斷字符流中是否還有字符需要編碼：如“是”，返回步驟2，如“否”，若當(dāng)前前綴P不是空，輸出響應(yīng)與當(dāng)前前綴P的碼字，然后結(jié)束LZ78編碼算法

步驟1:將詞典和當(dāng)前前綴P都初始化為空.LZ78編碼舉例字符流為：ABBCBCABA詞典與碼字流（輸出）位置字符1A2B3B4C5B6C7A8B9A序號位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)LZ78編碼舉例字符流為：ABBCBCABA詞典與碼字流（輸LZ78譯碼收到信息（碼字，字符）流：(0,A)(0,B)(2,C)(3,A)(2,A)自動構(gòu)造詞典算法步驟一：開始時(shí)詞典是空的步驟二：當(dāng)前碼字W:=下一個(gè)碼字步驟三：當(dāng)前字符C:=緊隨碼字之后的字符步驟四：把當(dāng)前碼字的綴－符串（string.W）輸出到字符流，然后輸出字符C步驟五：把string.W+C添加到詞典中重復(fù)直到所有（碼字，字符）流結(jié)束重構(gòu)出來的詞典與編碼時(shí)生成的詞典完全一樣LZ78譯碼收到信息（碼字，字符）流：(0,A)(0,B)(2.LZW與LZ78相比，有如下特點(diǎn)所有可能出現(xiàn)的字符都事先放在字典中。輸出的碼字流中僅由詞典中的碼字組成。編碼算法思想Greedyparsingalgorithm:檢查字符流中的字符串，Prefix.C,其中Prefix是字典中最長的字符串，C是一個(gè)字符Prefix.C不在字典中。Prefix.C放入字典中。輸出Prefix.C的編號例ABBABABAC2.LZWLZW編碼算法

步驟1:將詞典初始化為包含所有可能的單字符,當(dāng)前前綴P初始化為空.

步驟2:當(dāng)前字符C:=字符流中的下一個(gè)字符.

步驟3:判斷P+C是否在詞典中(1)如果"是",則用C擴(kuò)展P,即讓P:=P+C,返回到步驟2.(2)如果"否",則輸出與當(dāng)前前綴P相對應(yīng)的碼字W;將P+C添加到詞典中;令P:=C,并返回到步驟2步驟4：判斷碼字流中是否還有碼字要譯，如果“是”，就返回步驟2，如果否，吧代表當(dāng)前前綴P的碼字輸出到碼字流LZW編碼算法

步驟1:將詞典初始化為包含所有可能的單字符,2.LZW譯碼算法（略）詞典中包含所有的前綴根（即每個(gè)字符組成詞典）譯碼時(shí)先記住先前碼字（pW）從碼字流中讀出當(dāng)前的碼字（cW）輸出當(dāng)前的碼字（cW）對應(yīng)的單詞,string(cW)string(pW)與string(cW)的第一個(gè)字符合在一起，放入詞典中。例，ABBABABAC詞典中有A,B,C碼字流：（1，2，2，4，7，3）2.LZW練習(xí)采用LZW算法對下列輸入字符流進(jìn)行壓縮編碼，要求寫出編碼過程以及字典，最后給出編碼結(jié)果。ababcbabababaaa練習(xí)采用LZW算法對下列輸入字符流進(jìn)行壓縮編碼，要求寫出編碼步驟位置詞典輸出碼字(1)a(2)b(3)c11(4)ab(1)22(5)ba(2)34(6)Abc(4)45(7)Cb(3)57(8)Bab(5)610(9)Baba(8)711(10)Aa(1)813(11)Aaa(10)步驟位置詞典輸出碼字(1)a(2)b(3)c1多媒體圖像編碼分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測編碼DPCM基于頻率變換編碼子帶編碼小波變換編碼基于統(tǒng)計(jì)哈夫曼編碼算術(shù)編碼游程編碼RLE國際標(biāo)準(zhǔn)JPEG標(biāo)準(zhǔn)（靜態(tài)圖像）MPEG標(biāo)準(zhǔn)（電視圖像）H.261（可視通信）MHEG標(biāo)準(zhǔn)（超媒體）多媒體圖像編碼分類多媒體數(shù)據(jù)壓縮編碼PCM量化預(yù)測編碼DPC多媒體核心技術(shù)：壓縮數(shù)據(jù)壓縮起源于40年代由ClaudeShannon首創(chuàng)的信息論，其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學(xué)中的名詞“熵”(Entropy)來表示一條信息中真正需要編碼的信息量考慮用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條信息編碼，假設(shè)符號Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)多媒體核心技術(shù)：壓縮數(shù)據(jù)壓縮起源于40年代由Claud考慮用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條信息編碼，假設(shè)符號Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)位為：

En=-log2(Pn)

整條信息的熵也即表示整條信息所需的位數(shù)為：E=∑En

舉個(gè)例子，對下面這條只出現(xiàn)了abc三個(gè)字符的字符串：

aabbaccbaa

字符串長度為10，字符abc分別出現(xiàn)了532次，則abc在信息中出現(xiàn)的概率分別為0.50.30.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位

如果用計(jì)算機(jī)中的ASCII編碼，表示上面的字符串需要整整80位呢！簡單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號，這就是數(shù)據(jù)壓縮的基本準(zhǔn)則?？紤]用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條38無損數(shù)據(jù)壓縮概念方式：無損,有損無損(losslesscompression,redundancyreduction)壓縮后的數(shù)據(jù)能夠完全恢復(fù)，如磁盤上的數(shù)據(jù)文件，壓縮后是原來的1/2—1/4算法有：Huffman,RLE,算術(shù)編碼，詞典編碼有損：lossy,不可逆壓縮。聲音、圖像中的變換編碼，例如，DM,APCM,DPCM(圖3-14）由于存在量化器無損數(shù)據(jù)壓縮概念方式：無損,有損4.1Shannon的信息論與數(shù)據(jù)壓縮1.1948年Shannon香農(nóng)創(chuàng)立的信息論：數(shù)據(jù)壓縮理論極限。數(shù)據(jù)壓縮的技術(shù)途徑。壓縮原理：信源中信息分布不均勻；信源中信息含有冗余（相關(guān)性）4.1Shannon的信息論與數(shù)據(jù)壓縮1.1948年Sh舉例26個(gè)字母和一個(gè)分隔符，共27個(gè)字符組成的英文文件，看成信源，該信源的極限(根據(jù)字符出現(xiàn)的頻率不同)：H(x)=1.4bit/字符原因：27個(gè)字符編碼，5bits分布不均勻：如a,b,c的出現(xiàn)頻率比x,y,z高信源相關(guān)系：er,ture,ed,ing等舉例26個(gè)字母和一個(gè)分隔符，共27個(gè)字符組成的英文文件，看成2.信息熵entropy問題：隨機(jī)變量的一個(gè)取值a，攜帶的信息量是多少？相關(guān)概念：消息：數(shù)據(jù)、電報(bào)、電話。信息：對消息加工，有特定價(jià)值一個(gè)信息帶有一定的信息量，大小不等例子一個(gè)消息：某試驗(yàn)成功試驗(yàn)人員預(yù)計(jì)成功的可能性99%：信息量很小試驗(yàn)人員預(yù)計(jì)成功的可能性1%：信息量很大2.信息熵entropy3.信息量：在收到信息以前，處于某種不確定狀態(tài)中，收到信息之后，消除或部分消除了此不確定性。消除不確定性多少，就可以作為信息的度量。4.Shannon用概率說明這一概念事件出現(xiàn)的概率小，相當(dāng)于不確定性多，反之，則少。Pi為事件ai發(fā)生的概率，則ai出現(xiàn)后的自信息量為I(ai)=-logpi3.信息量：在收到信息以前，處于某種不確定狀態(tài)中，收到信息5.信息熵（Entropy） 表示每出現(xiàn)一個(gè)字符所給出的平均信息量。5.信息熵（Entropy）“底”不同而值不同，因而單位也就不同當(dāng)取底為r的整數(shù)時(shí)，則熵的信息單位稱作r進(jìn)制信息單位r=2,單位為bit（比特）r=e,單位為Nat（奈特）r=10,單位為Hart(哈特)log不特別說明時(shí)，取為2“底”不同而值不同，因而單位也就不同

6.信息熵的理解：處于事件發(fā)生之前，根據(jù)先驗(yàn)概率Pj,就有不同的確定性存在，I(ai)與H(x)都是不確定性度量。當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇性的度量但出于事件發(fā)生之后，不確定性已被解除，則是獲得信息的度量可以認(rèn)為是事件隨機(jī)性的度量，因其僅僅對概率Pj取另個(gè)坐標(biāo)而已。7.H(x)就是對離散信源進(jìn)行無失真編碼時(shí)的碼長極限。6.信息熵的理解：8.舉例信源取4個(gè)符號a1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用編碼(0,10,110,111),則平均碼長=…=1.75考慮以下幾種變長編碼：碼Ｂ唯一可譯

例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碼Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１8.舉例信源字母概率碼A碼B碼Ca1１／２０００a2１／４１47練習(xí)信源X中有16個(gè)隨機(jī)事件，即n=16。每一個(gè)隨機(jī)事件的概率都相等，即P(x1)=P(x2)=P(x3)=…=P(x16)=1/16，計(jì)算信源X的熵。練習(xí)信源X中有16個(gè)隨機(jī)事件，即n=16。每一個(gè)隨機(jī)事件的概48無損數(shù)據(jù)壓縮課件499.Huffman編碼H(S)=(15/39)*log2(39/15)+(7/39)*log2(39/7)+…+(5/39)*log2(39/5)=2.1859

壓縮比1.37:1。9.Huffman編碼練習(xí)信源符號的概率如下，畫出其Huffman編碼的編碼樹并給出各符號的編碼以及碼長，最后求出平均碼長XX1X2X3X4X5X6P(X)0.350.200.150.100.100.10練習(xí)信源符號的概率如下，畫出其Huffman編碼的編碼樹并給哈夫曼編碼X101X210X311X4000X50010X60011平均碼長：=2.45哈夫曼編碼４.2算術(shù)編碼提出Rissanen1976年提出。在JPEG與JBIG（Bi-levelimage)中都有算術(shù)編碼的內(nèi)容。2.思想把信源符號構(gòu)成的串S,唯一地映射到實(shí)數(shù)軸上（0，1）之間的一個(gè)實(shí)數(shù)。前提：知道信源每個(gè)符號的概率。４.2算術(shù)編碼提出3.舉例假設(shè)信源由四個(gè)符號{a1,a2,a3,a4}組成，這些符號的概率分別是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四個(gè)符號的二進(jìn)制編碼分別為00，01，10，11符號序列S=a3a1a4a1a3a4a2的二進(jìn)制序列為10001100101101編碼：把S映射到（0，1）之間的實(shí)數(shù)的過程,見教材譯碼:見教。3.舉例4.3RLE編碼（RunLengthEncoding）是一種使用廣泛的簡單熵編碼，它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于傳真機(jī)。RLE原理：圖像（靜止圖像）的相鄰像素相關(guān)性（灰度、彩色）。用二元組（行程，灰度或彩色值）表示。4.3RLE編碼（RunLengthEncoding）例子假定一幅灰度圖象，第n行的象素值為用RLE編碼方法得到的代碼為：80315084180。代碼中用藍(lán)色數(shù)字是行程長度，藍(lán)字后面的數(shù)字代表象素的顏色值。50代表有連續(xù)50個(gè)象素具有相同的顏色值，它的顏色值是8例子假定一幅灰度圖象，第n行的象素值為50代表有連續(xù)50個(gè)象3.不足：隨機(jī)色彩豐富的圖像，平均碼長增加。不是單獨(dú)使用RLE一種編碼方法，而是和其他壓縮技術(shù)聯(lián)合應(yīng)用。無損數(shù)據(jù)壓縮課件4.4詞典編碼思想Huffman編碼：符號的概率已知，概率大的符號分配較短的碼字。字符間的相關(guān)性信息沒有用上。將長度不同的符號串（短語）編碼成一個(gè)個(gè)新的單詞。每個(gè)符號串分配一個(gè)編碼。編碼等長（如12位二進(jìn)制）。2.提出：以色列J.Ziv與A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中應(yīng)用。LZ系列算法4.4詞典編碼思想應(yīng)用范圍LZ77、LZSS、LZ78、LZW算法以及它們的各種變體幾乎壟斷了整個(gè)通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者，甚至連PGP這樣的加密文件格式也選擇了LZ系列算法作為其數(shù)據(jù)壓縮的標(biāo)準(zhǔn)。應(yīng)用范圍LZ77、LZSS、LZ78、LZW算法以及它詞典編碼舉例LZ77編碼術(shù)語輸入字符流(inputstream):一串字符字符(character)：一個(gè)符號編碼位置(codingposition)：輸出的編碼前向緩沖器(lookaheadbuffer)：單詞編碼窗口(window)指針(pointer)詞典編碼舉例LZ77編碼詞典編碼舉例LZ78編碼術(shù)語字符流:一串字符字符：一個(gè)符號碼字流：輸出的編碼碼字：單詞編碼前綴綴—符串詞典：綴—符串、碼字構(gòu)成的對應(yīng)表詞典編碼舉例LZ78編碼LZ78算法思想：不斷從字符流中形成新的綴—符串綴—符串作為新的詞條存入字典中，并給該詞條分配一個(gè)碼字。對字符流的編碼就用“(綴的編碼,字符)”表示輸出碼字流由“(綴的編碼,字符)”編碼算法譯碼算法LZ78算法思想：LZ78編碼算法

步驟1:將詞典和當(dāng)前前綴P都初始化為空.

步驟2:當(dāng)前字符C:=字符流中的下一個(gè)字符.

步驟3:判斷P+C是否在詞典中(1)如果"是",則用C擴(kuò)展P,即讓P:=P+C,返回到步驟2.(2)如果"否",則輸出與當(dāng)前前綴P相對應(yīng)的碼字W和當(dāng)前字符C,即(W,C);將P+C添加到詞典中;令P:=空值,并返回到步驟2（3）判斷字符流中是否還有字符需要編碼：如“是”，返回步驟2，如“否”，若當(dāng)前前綴P不是空，輸出響應(yīng)與當(dāng)前前綴P的碼字，然后結(jié)束LZ78編碼算法

步驟1:將詞典和當(dāng)前前綴P都初始化為空.LZ78編碼舉例字符流為：ABBCBCABA詞典與碼字流（輸出）位置字符1A2B3B4C5B6C7A8B9A序號位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)LZ78編碼舉例字符流為：A