數(shù);據(jù)壓縮技術(shù)

數(shù)據(jù)壓縮技術(shù)主講戴永教材DavidSalomon,數(shù)據(jù)壓縮原理與應(yīng)用,北京:電子工業(yè)出版社,20032023/2/6

信息工程學(xué)院戴永2引言總思路通過去掉源文件原始數(shù)據(jù)中的冗余度來壓縮數(shù)據(jù).數(shù)據(jù)壓縮:把輸入數(shù)據(jù)流變換成較小的輸出數(shù)據(jù)流.輸入數(shù)據(jù)流:源流或原始數(shù)據(jù)輸出數(shù)據(jù)流:輸出流或壓縮流流:文件數(shù)據(jù)壓縮的實(shí)現(xiàn):把低效(長的)表達(dá)方式改為高效(短的)表達(dá)方式.人們常用數(shù)據(jù)的低效表達(dá)方式是因?yàn)榉奖闾幚?比如說ASCII碼用7位定長碼表示,人們都遵循同一標(biāo)準(zhǔn)而給工作帶來方便.但實(shí)際上ASCII碼中各字符使用頻度差別很大,因而可采用不同長度的的代碼來表示,即形成變長碼.2023/2/6

信息工程學(xué)院戴永3變長碼:常用的字符用短碼,不常用的用長碼.SP理論:S(simplicity):簡潔P(power):能力即在保證實(shí)現(xiàn)功能的前提下,盡可能地去掉不必要的復(fù)雜度和多余的信息.實(shí)現(xiàn)SP理論的可能性為(1)把各類計(jì)算和形式推理視為用模式匹配、聯(lián)合及搜索來進(jìn)行信息壓縮有助于理解。（2）找到并去除冗余的過程總可以在基礎(chǔ)上理解為搜索互相匹配的模式，把任何模式的重復(fù)實(shí)例合并。2023/2/6

信息工程學(xué)院戴永4數(shù)據(jù)壓縮領(lǐng)域的專業(yè)名詞（1）壓縮器（編碼器）：壓縮輸入流中的原始數(shù)據(jù)，建立由低冗余度數(shù)據(jù)構(gòu)成的輸出流的程序。（2）解壓縮器（解碼器）：進(jìn)行以上相反轉(zhuǎn)換的程序（有時(shí)同時(shí)指編碼器和解碼器）。壓擴(kuò)：壓縮/擴(kuò)展（3）原始輸入流：未編碼、原或原始數(shù)據(jù)（4）輸出流（最末壓縮流）：已編碼或已壓縮的數(shù)據(jù)。（5）位（比特）流：已壓縮的文件。（6）非自適用壓縮：為某種專用傳送而設(shè)計(jì)的壓縮方法，壓縮其他數(shù)據(jù)效果很差。（7）自適用壓縮：通過考察原始數(shù)據(jù)而自動(dòng)修改運(yùn)算方法、參數(shù)和碼表等以完成相應(yīng)的壓縮。（8）半自適用壓縮：按以下兩步進(jìn)行壓縮稱為半自適用壓縮，

STEP1讀輸入流，統(tǒng)計(jì)待壓縮數(shù)據(jù)的信息；

STEP2根據(jù)第一步信息設(shè)定參數(shù)進(jìn)行實(shí)際壓縮。2023/2/6

信息工程學(xué)院戴永5有損壓縮：通過丟失一些信息來得到更好的壓縮。解壓時(shí)結(jié)果與原始的數(shù)據(jù)流不完全相同。此方法多用于圖像、電影、聲音等的信息壓縮。無損壓縮：完全可以恢復(fù)原始流的壓縮。該方法主要用于計(jì)算機(jī)程序文件的壓縮。有的文本文件可視情況進(jìn)行有損壓縮。對(duì)稱壓縮：壓縮器和解壓器使用基本相同的算法，但處理方向相反。該方法適用兩方文件數(shù)相同的的常規(guī)壓縮傳送工作。非對(duì)稱壓縮：壓縮器或解壓縮器承擔(dān)的工作量比另一方大得多。例：當(dāng)需把某文件進(jìn)行壓縮存檔供頻繁解壓、使用時(shí)，則可讓壓縮器的算法復(fù)雜，而讓解壓器運(yùn)行快捷。僅作備份時(shí)更是這樣。通用壓縮方法:壓縮器和解壓縮器不需要輸入流的統(tǒng)計(jì)特性的壓縮方法.兩大類壓縮方法:(1)按流模式工作,即有序輸入一個(gè)或多個(gè)字節(jié)進(jìn)行壓縮,直到遇到文件結(jié)尾標(biāo)志.(2)按塊壓縮,每塊獨(dú)立編碼.此時(shí)塊的長度是影響該方法性能的重要參數(shù),可由用戶控制.物理意義的壓縮:不考慮數(shù)據(jù)含義,只從位的角度進(jìn)行數(shù)據(jù)壓縮,即只是把一個(gè)位流轉(zhuǎn)換成另一個(gè)更短的位流.這種壓縮只要搞清楚輸出流是怎樣被編碼的便可.2023/2/6

信息工程學(xué)院戴永6邏輯壓縮:通過對(duì)源流中的各項(xiàng)數(shù)據(jù)進(jìn)行統(tǒng)計(jì),采用不同長度代碼對(duì)數(shù)據(jù)進(jìn)行編碼.該方法對(duì)特定數(shù)據(jù)類型有好效果.表示壓縮性能參數(shù):(1)壓縮比:壓縮比=輸出流量/輸入流量單位:bpb,bpc,bpp壓縮比>1,為負(fù)壓縮或膨脹或擴(kuò)展;壓縮比=1,壓縮器未起作用;壓縮比<1,壓縮器起到壓縮作用.比特率:主指bpb,bpc.表明壓縮之目的為用低比特率來表示任何給定的數(shù)據(jù).比特預(yù)算:對(duì)一個(gè)壓縮文件規(guī)定其中多少(以百分率計(jì)算)為符號(hào)的變長碼字,多少為用于表格編碼.給符號(hào)之外內(nèi)容留多少長度稱為比特預(yù)算.例留10%長度用于某些表格編碼,則表的比特預(yù)算為10%.(2)壓縮因子:壓縮比的倒數(shù)壓縮因子=輸入流量/輸出流量壓縮因子>1,壓縮器起到壓縮作用;壓縮因子=1,壓縮器未起作用;壓縮因子<1,擴(kuò)展.2023/2/6

信息工程學(xué)院戴永7(3)壓縮空間度量:用100×(1-壓縮比)度量壓縮程度.當(dāng)此值為30,表明壓縮后空間節(jié)省30%.(4)像素壓縮前后的bpp比較:顯示像素壓縮的有效程度.(5)壓縮增益:100Ln(參考大小/壓縮后的大小)參考大小:輸入流的量或某種標(biāo)準(zhǔn)無損壓縮方法所產(chǎn)生的輸出流的量.(6)壓縮速度:每字節(jié)多少周期(CPB).用硬件來壓縮時(shí)此指標(biāo)很重要.(7)均方差(MSE)、峰值信噪比（PSNR）：用于度量有損壓縮圖像、電影所引入的失真。2023/2/6

信息工程學(xué)院戴永8第一章基本技術(shù)1.1直觀壓縮壓縮與可靠性的對(duì)立統(tǒng)一:減少冗余度可實(shí)現(xiàn)數(shù)據(jù)壓縮,但同時(shí)也降低了可靠性.如果為了可靠性增加校驗(yàn)位卻又增加了代碼長度即增加了冗余度.盡管如此,人們更早、更多考慮的是壓縮，不過一般為直觀壓縮。以下是直觀壓縮的幾個(gè)例子。1.1.1盲文中的壓縮圖1.1為26個(gè)盲文字母表.每一個(gè)字母用6點(diǎn)組合表示,每一個(gè)點(diǎn)按兩個(gè)狀態(tài)取值,6個(gè)點(diǎn)可形成64個(gè)組合狀態(tài).而26個(gè)字母僅為其中一部分,另外再加上一些數(shù)字和符號(hào),還多出一些組合狀態(tài).對(duì)此又將多出狀態(tài)對(duì)應(yīng)一些常用單詞和使用頻率很高的字母串,如表1.2.將多出狀態(tài)對(duì)應(yīng)一些常用單詞和使用頻率很高的字母串,是盲文中體現(xiàn)出來的壓縮思想.2023/2/6

信息工程學(xué)院戴永91.1.2不可逆文本壓縮通過簡單地舍棄一些信息來壓縮文本,解碼時(shí)不能還原,稱之為不可逆文本壓縮或緊縮.1.1.3特定的文本壓縮主要針對(duì)無損壓縮(可恢復(fù)).以下是一些特定壓縮例子.(1)文本中有很多空格的情況:比如Herearesomeideas

用0表示非空格,用1表示空格,該句可進(jìn)行如下的壓縮表示0000100010000100000Herearesomeideas一個(gè)空格占8位,而8個(gè)0,1占一個(gè)字節(jié),總的來說是壓縮了.(2)以7位ASCII碼代替8位ASCII碼,稱之為緊縮,壓縮比為7/8(3)選擇合適的數(shù)據(jù)長度進(jìn)行壓縮如果采用40個(gè)字符集元素(26個(gè)字母,10個(gè)數(shù)字,1個(gè)空格,3個(gè)符號(hào))構(gòu)成文本.為適用壓縮,將文本按3個(gè)字符為一段進(jìn)行分割,則一段字符可能出現(xiàn)的組合狀態(tài)為403=64000.2023/2/6

信息工程學(xué)院戴永10表達(dá)1段3字符需3個(gè)字節(jié)共24BIT.而403<216=65536,即16BIT的組合狀態(tài)多于403的組合狀態(tài),用此方法壓縮,壓縮因子可達(dá)24/16=1.5(4)選用合適的代碼形式進(jìn)行壓縮,將8位ASCII碼的文本根據(jù)其文本中所含字符的范圍可采用少位代碼實(shí)現(xiàn)壓縮如果僅含大寫字母,數(shù)字,及一些標(biāo)點(diǎn)符號(hào)可選用老式6位CDC碼(表1.3),也可采用老式5位Baudot碼(表1.4).(5)根據(jù)數(shù)制壓縮,比如兩個(gè)10進(jìn)制數(shù)可壓縮在一個(gè)字節(jié)中.2023/2/6

信息工程學(xué)院戴永11(6)按字典結(jié)構(gòu)方式壓縮:比較前面單詞,前位有N個(gè)相同的字母,就用N打頭,后跟不同的字母,如aaaardvark1ardvarkabaft1baftabandon3ndonabandoning7ingabated3tedabate5abbot2bot2023/2/6

信息工程學(xué)院戴永121.2游程編碼如果數(shù)據(jù)項(xiàng)d在輸入流中連續(xù)出現(xiàn)n次,則以單個(gè)字符對(duì)nd替換n次出現(xiàn)者.稱n個(gè)連續(xù)出現(xiàn)的數(shù)據(jù)項(xiàng)為游程,這種數(shù)據(jù)壓縮方法稱為游程編碼,常用RLE表示.1.3RLE文本壓縮對(duì)重復(fù)字段采用3符號(hào)標(biāo)識(shí)法:(1)重復(fù)提示符,比如@,#等;(2)游程長度參數(shù)或重復(fù)次數(shù),若用一個(gè)字節(jié)表示,最大長度可為255個(gè)重復(fù)字;(3)重復(fù)字符.以上三部分合稱為重復(fù)因子.可見要獲得壓縮效益,重復(fù)字符應(yīng)在3個(gè)以上.2023/2/6

信息工程學(xué)院戴永13重復(fù)因子替代法有如下缺點(diǎn):(1)普通文本中并沒有多少字符重疊.重復(fù)較多的為空格,點(diǎn)劃線,星號(hào)等.(2)要單獨(dú)占用一個(gè)符號(hào),該符號(hào)在被壓縮的文本中不能出現(xiàn).(3)壓縮長度有限,如255或258個(gè)重復(fù)字符.重復(fù)因子壓縮舉例以@為壓縮標(biāo)識(shí)符,重復(fù)長度從1開始計(jì)數(shù)例1.有如下注釋文本;***************************************;input:no;output:no;***************************************寫成RLE壓縮文本如下;@39*Enter;input:noEnter;output:no

Enter;@39*2023/2/6

信息工程學(xué)院戴永14輸入流為102個(gè)字節(jié),輸出流為30個(gè)字節(jié),壓縮比30/102*%=29.4%即輸出被壓縮70%多,壓縮效率很高.例2.被壓文本為6.allistoowell壓縮輸出的文本為6.A@2list@2o

we@2l輸入文本為18個(gè)字節(jié),輸出文本21個(gè)字節(jié),結(jié)果不但沒有壓縮反而擴(kuò)大.可見重復(fù)次數(shù)少于3時(shí)不適宜采用此壓縮方法.例3.被壓縮文本為25,25,25,25,25,25,30,30,30,30,30,30,30壓縮輸出的文本為@325@430以上表達(dá)方式將長度減3,這是從使用此方法的最低要求出發(fā),因而重復(fù)長度可達(dá)258.2023/2/6

信息工程學(xué)院戴永15RLE文本壓縮算法:設(shè)C為字符數(shù)目計(jì)數(shù)單元,設(shè)R為重復(fù)計(jì)數(shù)單元,C←0,R←0從文本緩沖區(qū)順序讀1個(gè)字符到CH單元是文本結(jié)束符否?結(jié)束YNC

←C+1C=1?YSC←CHCH為當(dāng)前字符存放單元,SC為比較或匹配字符存放單元.NSC=CH?YR←R+1R<4?按R值將SC中字符寫入壓縮文件YNN在壓縮文件中寫壓縮格式內(nèi)容(占3個(gè)字節(jié))R←0,SC←CH2023/2/6

信息工程學(xué)院戴永16RLE文本解壓縮算法流程清壓縮標(biāo)志順序讀文本字符是文本結(jié)束符否?結(jié)束YN壓縮標(biāo)志清除否?NYChar=`@`?置壓縮標(biāo)志Y輸出字符讀入N,輸出N個(gè)N后相同字符以上算法表明當(dāng)輸入流發(fā)現(xiàn)至少3個(gè)連續(xù)相同的字節(jié)時(shí),壓縮器在輸出流中加入3個(gè)字節(jié)的壓縮標(biāo)志段.當(dāng)解壓器讀到壓縮標(biāo)志段特定的標(biāo)志符號(hào)時(shí),將3字節(jié)還原成未壓縮的符號(hào)串.2023/2/6

信息工程學(xué)院戴永17RLE的壓縮比概念設(shè)待壓縮的字符串長度為N,字符中包含M次重復(fù),每次重復(fù)的平均長度為L.M次中的每一次重復(fù)可用3字節(jié)代替(提示字符,計(jì)數(shù)值,數(shù)據(jù)),壓縮后的字符串的長度為

N-M*L+M*3=N-M(L-3)壓縮因子為N/(N-M(L-3))例1.N=1000,M=10,L=4壓縮因子為1000/(1000-10(4-3))=1.01例2.N=1000,M=50,L=10,壓縮因子為1000/(1000-50(10-3))=1.538以上例子表明,當(dāng)重復(fù)的平均長度L越大,壓縮因子就越大,壓縮效果越好.MNP5方法為游程和自適用編碼結(jié)合而成,其標(biāo)識(shí)符占4字節(jié).2023/2/6

信息工程學(xué)院戴永181.1.3相關(guān)編碼當(dāng)數(shù)據(jù)是一串差不多的數(shù),或是由彼此相似的字符串構(gòu)成時(shí),可以用相關(guān)編碼進(jìn)行壓縮.例1.當(dāng)某電機(jī)轉(zhuǎn)速穩(wěn)定在額定速度1000轉(zhuǎn)/分時(shí),假定容許偏差為±3轉(zhuǎn)/分,測(cè)速器一般測(cè)出的速度為1000,999,998,998,999,999,1000,1000,1001,1001,1002,1002,1002,1002,1003,1003,1003,1002······,可以壓縮為如下的相關(guān)編碼1000,-1,-1,0,1,0,1,0,1,0,1,0,1,0,0,0,-1,······,例2.當(dāng)某系統(tǒng)從一個(gè)狀態(tài)突跳到另一種狀態(tài)時(shí),假定檢測(cè)出的參數(shù)為2023/2/6

信息工程學(xué)院戴永19110,115,121,119,117,117,115,115,114,118,122,126,129,130,200,203,205,207,209,211,214,217,220,223,227,228,231,······,壓縮為相關(guān)編碼為110,5,6,-2,-2,0,-2,0,-1,4,4,4,4,3,1,200,3,2,2,2,2,3,3,3,3,4,1,3,······,以上例子表明,當(dāng)系統(tǒng)為某一穩(wěn)定狀態(tài)工作時(shí),采樣子系統(tǒng)只要給出第一個(gè)值或從規(guī)定的額定值開始傳送,后跟差分值,便可對(duì)采樣值進(jìn)行高效壓縮.另外由于差分值常常較小,可以將兩個(gè)差分值合放于1個(gè)字節(jié),可進(jìn)一步提高壓縮效率,如1000,(-1,-1),(0,1),(0,1),(0,1),······2023/2/6

信息工程學(xué)院戴永201.4RLE圖像壓縮RLE是壓縮圖形圖像數(shù)據(jù)的常用方法當(dāng)圖像為黑白圖像時(shí)每個(gè)像素只需一個(gè)二進(jìn)制位表示,當(dāng)前的位狀態(tài)要么表示黑,要么表示白.如果一個(gè)像素用多位2進(jìn)制表示,則可使像素顯現(xiàn)出黑白的灰度或色彩.以下用位圖(像素+灰度)形式討論RLE的壓縮原理圖像按位圖存儲(chǔ)的結(jié)構(gòu)如下圖所示。位圖是圖像輸入流···································································································································································································第1個(gè)位圖像素最后1個(gè)位圖像素圖像輸入流從第一個(gè)位圖像素開始順序進(jìn)入壓縮器2023/2/6

信息工程學(xué)院戴永21用RLE壓縮圖像的基本依據(jù)是：在位圖中隨機(jī)選擇一個(gè)像素，其相鄰像素色彩相同的可能性很大，因此壓縮器逐行掃描位圖，搜索色彩相同像素的游程。壓縮流的大小取決于圖像的復(fù)雜度：細(xì)節(jié)越多，壓縮效果越差。注意如下的兩個(gè)現(xiàn)象（1）一條掃描線從均勻區(qū)域（在此區(qū)域相鄰像素的灰度基本無突變）邊界的一點(diǎn)進(jìn)入，通過另一點(diǎn)出來，并且這兩點(diǎn)未被其他掃描線占用，根據(jù)統(tǒng)計(jì)，橫穿一塊均勻區(qū)域的掃描線數(shù)目粗略等于該區(qū)域周長（以周邊像素?cái)?shù)目計(jì)算）的一半。（2）對(duì)于均勻區(qū)域，每一條掃描線向輸出流提供一個(gè)數(shù)據(jù)，則該塊均勻區(qū)域的壓縮比大致等于：周長的一半/區(qū)域內(nèi)總的點(diǎn)數(shù)。比如壓縮一個(gè)3*3均勻區(qū)域點(diǎn)陣，壓縮比為4/9，其提供的壓縮數(shù)據(jù)為3個(gè)。例1.設(shè)有一幅24*24的2值位圖,其像素分布如圖所示,壓縮器從白像素開始.2023/2/6

信息工程學(xué)院戴永22第1行壓縮結(jié)果為:0,24第2行壓縮結(jié)果為:0,6,1,4,2,11第3行壓縮結(jié)果為:0,1,2,2,2,3,2,3,5,4第4行壓縮結(jié)果為:0,5,3,2,3,7,4第8行壓縮結(jié)果為:2,2,2,3,2,2,9,2第24行壓縮結(jié)果為:0,242023/2/6

信息工程學(xué)院戴永23該圖像文件從壓縮器輸出的結(jié)果為0,24,0,6,1,4,2,11,0,1,2,2,2,3,2,3,5,4,0,5,3,2,3,7,4,········，2,2,2,3,2,2,9,2，········，0,242值位圖輸出流的解壓原理：按約定的首像素顏色開始，依次變色，變色長度由當(dāng)前對(duì)應(yīng)的數(shù)據(jù)確定，每輸出一個(gè)確定顏色的像素序列，像素?cái)?shù)目累加該長度數(shù)據(jù)，當(dāng)累加的像素?cái)?shù)目等于圖域列數(shù)，則此列像素解壓完畢。重復(fù)上一行解壓過程，直到被解壓行數(shù)與圖域行數(shù)相同，則整個(gè)圖域解壓完畢。RLE進(jìn)行灰度壓縮時(shí)，連續(xù)的同一亮度的像素用（游程，像素值）的對(duì)偶參數(shù)表示或編碼。游程通常占一個(gè)字節(jié)，可長達(dá)255個(gè)同一亮度數(shù)據(jù)。像素值的位數(shù)與灰度級(jí)有關(guān)，一般為4~8位。例2.具有灰度圖像的壓縮.一個(gè)8位灰度序列為12,12,12,12,12,12,12,12,12,35,76,112,67,87,87,87,5,5,5,5,5,5,1,······的位圖，經(jīng)壓縮后輸出為9，12，35，76，112，67，3，87，6，5，1，

·······游程參數(shù)與灰度值的區(qū)別方法如下2023/2/6

信息工程學(xué)院戴永241).如果圖像限制為只有128級(jí)灰度,可以用每個(gè)字節(jié)中的1位來表示該字節(jié)是灰度值還是計(jì)數(shù)值,比如說以每字節(jié)的D7來標(biāo)識(shí),令D7=0,該字節(jié)低7位表示計(jì)數(shù)值,=1表示灰度值.按此法上述輸出流可寫為9，12+128，35+128，76+128，112+128，67+128，3，87+128，6，5+128，1+128，

·······2).如果灰度級(jí)為256,可降為255,留出一個(gè)狀態(tài)標(biāo)識(shí)(計(jì)數(shù)值,灰度)對(duì)偶參數(shù).假如以255作標(biāo)識(shí)參數(shù),則上述輸出流可寫為255,9，12，35，76，112，67，255,3，87，255,6，5，1，

·······3).將輸出流按8個(gè)數(shù)據(jù)一組分段,每段前加一個(gè)標(biāo)識(shí)字節(jié),標(biāo)識(shí)字節(jié)中從左到右或從D7到D0分別依此對(duì)應(yīng)標(biāo)識(shí)字節(jié)后的8個(gè)參數(shù),某參數(shù)為計(jì)數(shù)值,其在標(biāo)識(shí)字節(jié)中對(duì)應(yīng)的標(biāo)識(shí)位為1,反之為0.按此法,上述輸出流可寫為10000010,9，12，35，76，112，67，3，87,100······,6，5，1，

·······當(dāng)然也可以反過來標(biāo)識(shí).此方法給輸出流的總長度增加了1/8的長度.2023/2/6

信息工程學(xué)院戴永254).對(duì)完全不同的連續(xù)像素進(jìn)行標(biāo)識(shí).將連續(xù)像素長度用正數(shù)表示,而完全不同的連續(xù)像素則用負(fù)數(shù)表示.如果有M個(gè)完全不同的連續(xù)像素,則用-M置于這M個(gè)完全不同的連續(xù)像素之前.按此方法,上述輸出流可寫為9，12，-4,35，76，112，67，3，87，6，5，?,1，

·······“?”看1的性質(zhì)取值,如果1是完全不同的連續(xù)像素之首,“?”取負(fù),如果是灰度則取正.如果遇到形如(P1,P2,P2)的重復(fù)序列將出現(xiàn)擴(kuò)展的現(xiàn)象,因?yàn)檫@種序列的標(biāo)識(shí)結(jié)果為(-1,P1,2,P2),即由3個(gè)字節(jié)變成了4個(gè)字節(jié).不過如果1個(gè)像素3字節(jié)(彩色),則也略有壓縮效果,即(P1,P2,P2)占9字節(jié),壓縮輸出為(-1,P1,2,P2),占1+3+1+3=8字節(jié).以上各方法使用時(shí)還有三點(diǎn)要注意<1>由于游程不能為0,在輸出流中可寫入“游程-1”,(3,87)表示有4個(gè)87灰度的游程,此方法1個(gè)字節(jié)表示的游程可達(dá)256.<2>對(duì)于彩色圖像,通常將像素存為3字節(jié),依此代表紅綠藍(lán)3基色的強(qiáng)度.2023/2/6

信息工程學(xué)院戴永26假定有如下的彩色像素序列(171,85,34),(172,85,35),(172,85,30),(173,85,33),(173,86,34),····將3色分離形成3基色序列為紅序列：171，172，172，173，173，·········綠序列：85，85，85，85，86，·············藍(lán)序列：34，35，30，33，34，············顯然3基色序列可分別進(jìn)行RLE編碼，表明任何用于灰度圖像壓縮的方法同樣可用于彩色圖像壓縮。<3>位圖圖像最好按行編碼壓縮,每行結(jié)束加上EOL(END-OF-LINE)作標(biāo)志符.采用每行加標(biāo)志符的最大優(yōu)點(diǎn)是可實(shí)現(xiàn)對(duì)圖像有選擇的壓縮和解壓.尤其是解壓,可以根據(jù)用戶的要求進(jìn)行圖像重構(gòu),如圖所示,恢復(fù)一幅圖像可以先解碼和顯示2,6,10,14,········，然后再解碼和顯示3，7，11，15，19，·······2610142023/2/6

信息工程學(xué)院戴永27按行單獨(dú)編碼的主要優(yōu)點(diǎn)（1）可方便實(shí)現(xiàn)較快了解一幅圖像的大致情況，以確定對(duì)該幅圖像的處理方案。（2）可實(shí)現(xiàn)在一幅壓縮的位圖中只抽取其中一部分的目的，如從K行到L行。（3）可方便實(shí)現(xiàn)兩幅壓縮圖像的合并，而不必先將它們先解壓后合并。按行單獨(dú)編碼的主要缺點(diǎn)（1）壓縮流中每一行要增加行的起始信息標(biāo)志字節(jié)（書中為每行增加4字節(jié)的起始信息），從而擴(kuò)大了壓縮流的長度。（2）如果圖像變動(dòng)，則必須重算全部游程，即互動(dòng)性差。（3）對(duì)于復(fù)雜圖像不但不能壓縮還有可能擴(kuò)大。如果僅采用按行掃描壓縮，對(duì)于具有很多垂直線的圖像，則可能產(chǎn)生很多的短游程。短游程越多壓縮效果越差。2023/2/6

信息工程學(xué)院戴永28為獲得較好的RLE壓縮效果，通常的RLE壓縮器包含3個(gè)方向掃描的壓縮環(huán)節(jié)輸出流選擇其中結(jié)果較好的。3個(gè)方向掃描包括按行，按列，按鋸齒形，如圖所示。261014261014261014按行掃描按列掃描按鋸齒掃描2023/2/6

信息工程學(xué)院戴永291.1.4有損圖像壓縮有些圖像并不需要其非常細(xì)致的內(nèi)容,而只需要一個(gè)大概;有些只需知道圖像的輪廓便可等.如一些模式識(shí)別圖案,X射線圖案等,這些圖案壓縮可采用忽略短游程的方法,即可獲得好的壓縮比,其效果也可接受.忽略短游程意味著壓縮過程中要損失一些信息.用此方法壓縮圖像稱為有損圖像壓縮.可以忽略的游程長度,一般由用戶自行指定,比如用戶指定最長可忽略的游程長度為3,則游程為1,2,3的相同像素將與其鄰點(diǎn)合并.例.假定一幅二值圖像經(jīng)無損游程壓縮輸出序列為6,8,9,10,2,3,1,3,4,3,10,2,1，3，·········以用戶指定可忽略游程長度為3，進(jìn)行有損圖像壓縮，相應(yīng)的輸出流為6，8，9，10，6，10，10，6，·········6=2+3+1，10=3+4+3，6=2+1+3除了游程長度為3外,游程數(shù)目也是3,此方法尤其適用高分辨率大圖像壓縮.2023/2/6

信息工程學(xué)院戴永301.4.2有條件的圖像RLERLE的一種改進(jìn)形式:設(shè)有一幅2n級(jí)灰度的圖像,在考慮每一個(gè)像素的灰度時(shí)同時(shí)考慮鄰近像素也用n位代碼表示灰度,然后以鄰近像素灰度的出現(xiàn)而使本像素灰度出現(xiàn)的條件概率為依據(jù),將像素的灰度轉(zhuǎn)換為具有規(guī)定游程的n位代碼.掃描完一行后,將一行中所有列的n位代碼連成一長串,計(jì)算游程,把游程編為前綴碼,寫入壓縮流.條件概率的常見預(yù)測(cè)模式如圖所示XAB以A,B作為條件,X出現(xiàn)的概率為P(X|A,B),X是當(dāng)前像素,A及B是X的兩個(gè)鄰點(diǎn)(不必是最靠近的).A,B,X的灰度到n位具有規(guī)定游程代碼的轉(zhuǎn)換,是通過條件概率表來完成的.下面以n=4為例進(jìn)行討論.4位2進(jìn)制碼的16種組合是0000,0001,0010,0011,··········1110，11112023/2/6

信息工程學(xué)院戴永31將16個(gè)代碼按游程分類：1個(gè)游程有：0000，1111；分別定義為W1，W22個(gè)游程有：0001,0011,0111,1110,1100,1000分別定義為W3,W4,W5,W6,W7,W83個(gè)游程有：0100,0010,0110,1011,1101,1001分別定義為W9,W10,W11,W12,W13,W144個(gè)游程有：0101,1010分別定義為W15,W16以上每一組代碼具有互補(bǔ)性.P(X|A,B)與W1~W16的對(duì)應(yīng)關(guān)系如表1.11.其中“值”對(duì)應(yīng)參數(shù)是X的灰度值,“計(jì)數(shù)”對(duì)應(yīng)的值是指左邊A,B取值的情況下X出現(xiàn)此灰度值的次數(shù),統(tǒng)計(jì)值可以是任何一幅或幾幅圖像2023/2/6

信息工程學(xué)院戴永32

A

BW1W2W3W4W5W6W7···215值計(jì)數(shù)421361050462821······1······30值計(jì)數(shù)04431114375264115641915······12······

31值計(jì)數(shù)11139281735524750555206······8······32值計(jì)數(shù)2790234636142642645646180······6······33值計(jì)數(shù)333972228694251151381936517······18······34值計(jì)數(shù)4285932442524022316537311······13······大小新代碼游程數(shù)目:小大2023/2/6

信息工程學(xué)院戴永33表中紅線標(biāo)注的是，當(dāng)A=B時(shí)使得X=A=B的現(xiàn)象最多，因此將其對(duì)應(yīng)單游程。對(duì)應(yīng)什么結(jié)構(gòu)的單游程無硬性規(guī)定。當(dāng)A與B大不相同時(shí)，X成為各種灰度的概率都很小，一旦遇到只能根據(jù)預(yù)測(cè)賦予W，但多為多游程W。表中計(jì)數(shù)值左起從高到低排列，與此對(duì)應(yīng)是W1~W16從少游程到多游程順序排列。這樣一來由W構(gòu)成的新圖像碼串的游程數(shù)目會(huì)有效減少，從而實(shí)現(xiàn)壓縮。此方法的工作過程為圖像以光柵順序掃描。對(duì)每一像素X，其鄰點(diǎn)A和B已定位。在條件概率表中查找A，B及X。如果在第i列發(fā)現(xiàn)，則選中相應(yīng)Wi。如圖若X位于圖像頂行，則X按只有鄰點(diǎn)A而無B（但并不按B=0處理）,處理原則是選擇A=3,X=2對(duì)應(yīng)的計(jì)數(shù)值最大的那個(gè)W,本例為7902對(duì)應(yīng)的W1.XA2023/2/6

信息工程學(xué)院戴永34其它類型邊界點(diǎn)可類同處理.互補(bǔ)規(guī)則:選中對(duì)應(yīng)于X的代碼后,將其與前面一個(gè)代碼相比較.若前者最低位是1,則當(dāng)前代碼取為補(bǔ)碼(反碼或互補(bǔ)碼),以此減少游程數(shù).例1.假定壓縮器按前述安排獲得如下序列W2,W4,W1,W6,W3,W2,W1:1111,0011,0000,1110,0001,1111,0000:8個(gè)游程1111,1100,0000,1110,0001,1111,0000:6個(gè)游程1111,1100,0000,1110,0001,0000,0000:6個(gè)游程2023/2/6

信息工程學(xué)院戴永351.4.3BinHex4.0格式文本文件傳送比2進(jìn)制文件傳送安全一些,因?yàn)?進(jìn)制文件傳送是任何位都不能丟失的.BinHex的思想是企圖將任何文件都譯成文本文件傳送,或者說用一個(gè)新的文本文件代替原來的任何一種形式的文件.BinHex4.0是一個(gè)用于文件安全傳輸?shù)奈募袷?傳輸文件進(jìn)入BinHex后,輸出的BinHex4.0文件格式如下1.注釋:(ThisfilemustbeconvertedwithBinhex4.0)2.文件頭2023/2/6

信息工程學(xué)院戴永36包括表1.13所列各項(xiàng)3.讀入輸入文件,第一步進(jìn)行RLE.RLE的標(biāo)志字符為90H例1.90H既作標(biāo)志又作數(shù)據(jù).作數(shù)據(jù)時(shí)后跟00H,表示游程長度為0,以示該90H為數(shù)據(jù).源串和壓縮串的關(guān)系如下表所示.源串壓縮串001122334455667700112233445566771122222222222233119006223311229033441122900033442023/2/6

信息工程學(xué)院戴永374.編寫7位ASCII碼字符(該步驟是此方法的核心).將輸入文件看成是位流,把正讀入的文件分成6位1塊(或6位1段),并把每個(gè)6位代碼當(dāng)作指針,從給定的字庫中讀取字符,將讀出的字符對(duì)應(yīng)的7位ASCII代碼寫入輸出流,構(gòu)成新的文本文件流.例1.將2進(jìn)制文件“7401F590··········”轉(zhuǎn)換成新的文本文件(此例未考慮先進(jìn)行RLE).原文本文件:7401MOVA,#01HF590MOVP1,A

··········設(shè)定6位指針字庫如表2所示.000000!010000100110100110000000001“01000100011101011000100111120110010010110901110010100003011001101000140110100010010501101012023/2/6

信息工程學(xué)院戴永387401F590··········的2進(jìn)制代碼為01110100000000011111010110010000按6位一塊分割011101,000000,000111,110101,100100,00··········查新文本轉(zhuǎn)換表得F!(bM··········與此對(duì)應(yīng)的7位ASCII代碼位流為10001100100001010100011000101001101··········1.5前移編碼此方法的基本思想是:建立一張1維位置可變轉(zhuǎn)換表,該表將常用或重復(fù)使用符號(hào)靠前排列,并不斷改變編號(hào).2023/2/6

信息工程學(xué)院戴永39基本原理如下設(shè)A是一張用于轉(zhuǎn)換的1維字母表,表中元素位置編號(hào)不變,元素內(nèi)容根據(jù)輸入流內(nèi)容變化,令A(yù)=(a0,a1,a2,a3,a4········an）A中每個(gè)元素的編號(hào)與A中初始元素符號(hào)的下標(biāo)相同，用FA表示A的元素標(biāo)號(hào)即FA=（0，1，2，3，4,··········n）設(shè)x1x2x3x4x5·········xm為輸入流.如果xi=xi-1,而xi=aj,則A中元素位置作如下調(diào)整2023/2/6

信息工程學(xué)院戴永40A’=(aj,aj-1aj-2,···a4,a3,a2,a1,a0,aj+1,aj+2aj+3,···an）=(a0’,a1’,a2’,a3’,a4’········an’）FA仍不變,即FA=（0，1，2，3，4,··········n）.以上aj=a0’對(duì)應(yīng)0,aj-1=a1’對(duì)應(yīng)1,aj-2=a2’對(duì)應(yīng)2,··········其余類推.例1.設(shè)原始A0=(a,b,c,d,m,n,o,p),FA=（0,1,2,3,4,5,6,7,）,輸入流為“abcddcbamnopponm”.不采用前移編碼C’=(0,1,2,3,3,2,1,0,4,5,6,7,7,6,5,4)采用前移編碼:C1=(0,1,2,3,········），已編完輸入流的abcd，輸入流的下1個(gè)字母與前一個(gè)字母相同，相同字母為d，字母表從d往前翻，元素按新位置重新編號(hào)，即2023/2/6

信息工程學(xué)院戴永41A1=(d,c,b,a,m,n,o,p),仍有FA=（0,1,2,3,4,5,6,7,）,此時(shí)d?0,c?1,其余類推.在A1基礎(chǔ)上往后編,有C2=(0,1,2,3,0,1,2,3,4,5,6,7,········）,已編完輸入流的abcddcbamnop,輸入流的下1個(gè)字母與前一個(gè)字母相同，相同字母為p，字母表從p往前翻，元素按新位置重新編號(hào)，即A2=(p,o,n,m,a,b,c,d),仍有FA=（0,1,2,3,4,5,6,7,）,此時(shí)p?0,o?1,其余類推.在A2基礎(chǔ)上往后編,有C3=(0,1,2,3,0,1,2,3,4,5,6,7,0,1,2,3）.以上方法為集中前移法,結(jié)果使得前移法編碼后的代碼平均值小于不前移編碼代碼平均值.2023/2/6

信息工程學(xué)院戴永42例2.非集中前移現(xiàn)象.其原理是在輸入流中遇到哪個(gè)符號(hào),就將A中相同符號(hào)提到最前面,A中元素重新編號(hào).設(shè)輸入流為Z=(abcdmnopabcdmnop),A、FA仍為例1的A、FA

。不前移的編碼為C’=(0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7);前移的編碼為C=(0,1,2,3,4,5,6,7,7,7,7,7,7,7,7,7)C中第2個(gè)“7”的來源如下A0=(a,b,c,d,m,n,o,p),FA=（0,1,2,3,4,5,6,7,）,遇Z(a)，A1=(a,b,c,d,m,n,o,p),C=(0,········），a?0遇Z(b)

，A2=(b,a,c,d,m,n,o,p),C=(0,1,········),a?0,b?1,遇Z(c)

，A3=(c,b,a,d,m,n,o,p),C=(0,1,2,········),a?0,b?1,c?2,·····························遇Z(p)

，A8=(p,o,n,m,d,c,b,a),C=(0,1,2,···7·····),a?0,·····,p?7,遇Z(a),A9=(a,p,o,n,m,d,c,b),C=(0,1,2,···7,7·····),a?0,···,p?7,a?7,其余類推.顯然這種前移得出的編碼的平均值太大,還不如非前移編碼.2023/2/6

信息工程學(xué)院戴永43兩個(gè)例子的輸入流,編碼及A的變化比較見表1.14.之所以希望以上前移編碼的平均值要小,是為了后面要介紹的高效霍夫曼碼(算術(shù)碼)作準(zhǔn)備.只有編碼的平均值小,整數(shù)代碼就少,隨之霍夫曼碼的碼長就短.實(shí)現(xiàn)高效霍夫曼碼的常見4種辦法為(1)把霍夫曼碼賦給[0,N]范圍的整數(shù),使較小的數(shù)對(duì)應(yīng)較短的碼,如0?0,1?10,2?110,3?1110,4?11110,5?111110,6?1111110,7?1111111.(2)給整數(shù)分配代碼,使整數(shù)i>=1的代碼為她的2進(jìn)制代碼前加Log2i個(gè)0,

i霍夫曼代碼加的0數(shù)霍夫曼碼字長11Log21=012010Log22=133011Log23=13400100Log24=25···················································································150001111Log215=3716000010000Log216=492023/2/6

信息工程學(xué)院戴永44（3）采用自適用霍夫曼編碼（下節(jié)講）（4）為了盡可能地壓縮，對(duì)C掃描兩次，第1次計(jì)算代碼頻度,第2次具體編碼.第1次掃描所統(tǒng)計(jì)的代碼頻度用于計(jì)算概率,第2次掃描根據(jù)第1次掃描形成的概率構(gòu)造霍夫曼代碼(具體在第2章介紹).前移方法的變形1>前移k把A中為當(dāng)前符號(hào)所匹配的元素前移k個(gè)位置,而不是一直移到A的前部.參數(shù)k可由用戶指定,默認(rèn)值為n或1.此舉雖然降低了集中特性的性能,但能根據(jù)需要滿足一些特殊序列的壓縮要求.k=n為原形的前移方法;k=1,只是和前面一個(gè)元素交換位置.2>等c次再移僅當(dāng)A中某元素與輸入流中符號(hào)匹配c次(不必連續(xù)c次)后,才將其移到前面.A中各元素要安排計(jì)數(shù)器計(jì)數(shù)匹配次數(shù).此方法較適用移動(dòng)或重排A的元素速度很慢的情況.3>通常把從輸入中讀入的一個(gè)字(或一個(gè)單詞)作為一個(gè)字節(jié).此方法A必須從空開始,元素內(nèi)容在輸入和編碼時(shí)加入.例有以下文本theboyonmyrightistherightboy輸入第1個(gè)“the”時(shí),A是空的,找不到,在A中添加“the”,編碼器給出0,后跟“the”.2023/2/6

信息工程學(xué)院戴永45解碼器也從空A開始,以0表示在A中選擇第1個(gè)字.但此時(shí)解碼器中的A是空的,解碼器從編碼器中取出0后跟的字(這里是the)添加到A中.下一個(gè)字是“boy”,加到A中,使A=(“the”,“boy”),編碼器發(fā)出“1boy”.加入后作非集中前移處理,即將“boy”移到A的前面,A=(“boy”,“the”).解碼器處理和前面相似.字A(添加前)A(添加后)編碼器輸出the()the0the

boy(the)(the,boy)1boyon(boy,the)(boy,the,on)2onmy(on,boy,the)(on,boy,the,my)3myright(my,on,boy,the)(my,on,boy,the,right)4rightis(right,my,on,boy,the)(right,my,on,boy,the,is)5isthe(is,right,my,on,boy,the)(is,right,my,on,boy,the)5(按添加前的排序)right(the,is,right,my,on,boy)(the,is,right,my,on,boy)2boy(right,the,is,my,on,boy)(right,the,is,my,on,boy)52023/2/6

信息工程學(xué)院戴永461.6標(biāo)量量化從數(shù)據(jù)壓縮的角度出發(fā),量化也是為了有益于數(shù)據(jù)壓縮,包含兩個(gè)方面的內(nèi)容(1)如果被壓縮數(shù)據(jù)是大值,量化用于將其轉(zhuǎn)換為小值.小值比大值占用空間少,這種量化本身就是壓縮,但為有損壓縮,因小值比大值含的信息量少.(2)如果被壓縮數(shù)據(jù)是模擬量,這種量化仍是將其離散后化為小的數(shù)值.數(shù)值越小,壓縮效果越好,但信息損失也越大.方法1.假如輸入流每一個(gè)數(shù)據(jù)都是8位構(gòu)成,可以刪去每項(xiàng)數(shù)據(jù)的低4位,而獲得壓縮因子=2.但此方法使得輸出數(shù)據(jù)由256種符號(hào)變成了16種符號(hào),即16,32,48,64,·······,丟失了256-16個(gè)符號(hào)信息.2023/2/6

信息工程學(xué)院戴永47方法2.仍是一個(gè)8位數(shù),輸入符號(hào)在[0,255]范圍內(nèi).設(shè)置一個(gè)間隔參數(shù)s(也可稱為步長值),以s為均勻間隔的量化值(量化序列)為0,s,2s,3s,4s,······，ks，255，并使(k+1)s>255,而ks<=255.當(dāng)s=3時(shí),均勻間隔的量化值為0,3,6,9,12,······，252，255;當(dāng)s=4時(shí),均勻間隔的量化值為0,4,8,12,16,······，252，255;每一個(gè)輸入符號(hào)在以給定的s均勻間隔序列中尋找最接近的量化值(取小).方法3.選擇合適的量化值,使得[0,255]間任何一個(gè)數(shù),總可以在待量化數(shù)據(jù)中找到一個(gè)不大于d個(gè)單位的數(shù)據(jù)(局部量化法).處理方法:將量化范圍按2d+1長度分段,并置于[0,255]的中心.2023/2/6

信息工程學(xué)院戴永48例.設(shè)d=16,則2d+1=33,256/33=7余25,即[0,255]被分成7段余25個(gè)數(shù).顯然在[0,255]任取一個(gè)序列都能滿足基本結(jié)果.從距區(qū)間25以內(nèi)的數(shù)據(jù)開始都能獲得8個(gè)數(shù)值以內(nèi)的量化序列,如20,53,86,119,152,185,218,251標(biāo)量量化是有損壓縮,它易于控制壓縮比和數(shù)據(jù)損失間的平衡,但實(shí)現(xiàn)簡單,而只適用于可以大失真的情況.標(biāo)量量化壓縮不適合圖像壓縮,因?yàn)闃?biāo)量量化壓縮過于陡峭,會(huì)使本來連續(xù)的灰度變成對(duì)比度很強(qiáng)的雜線條比如一幅幾乎均勻的圖像區(qū)域(像素值為127或128).如果127量化為111,128量化為144,解壓后該圖像會(huì)成為格狀圖案,相鄰像素總在111,144之間跳變.圖像和聲音常采用的有損壓縮為矢量量化法.2023/2/6

信息工程學(xué)院戴永49第2章統(tǒng)計(jì)方法第1章討論的基本技術(shù)各方法采用的編碼主要是定長碼,如RLE,BinHex,前移編碼,量化編碼等.本章主要介紹變長編碼,總的思路是根據(jù)數(shù)據(jù)出現(xiàn)的概率大小賦其長碼或短碼.設(shè)計(jì)和實(shí)現(xiàn)變長碼必須要解決的問題(1)解碼要唯一;(2)平均碼長與其他方法比較要最短.2.1信息論信息是難以理解的不確定量,無法精確定義,捕獲和度量.信息的標(biāo)準(zhǔn)定義:(1)通過學(xué)習(xí),經(jīng)驗(yàn)或教訓(xùn)所獲得的知識(shí);(2)關(guān)于某一特定事件或情景的知識(shí),情報(bào);(3)收集的事實(shí)或數(shù)據(jù);(4)通知的行為或被通知的條件,知識(shí)的交流.2023/2/6

信息工程學(xué)院戴永50信息論在于用量化方法來處理信息,度量信息,使人們能用精確的數(shù)字來描述一個(gè)事件所含的信息信息量化的依據(jù):一條消息的信息含量等于該消息引起人們的驚奇度一種最簡單的量化方法是:將問題數(shù)等于表達(dá)結(jié)果所含信息需用的位數(shù).實(shí)際上是從兩個(gè)方面考慮:(1)表達(dá)考察范圍內(nèi)所有信息所需的位數(shù).比如用2進(jìn)制表達(dá)1~64(其中每一個(gè)作為一個(gè)信息),需要log264=6位,即6位可表達(dá)1~64中所有信息.(2)按“是/否”判斷找到結(jié)果的最多提問次數(shù).比如在1~64中按2分法找到一個(gè)數(shù)的最多次數(shù)為6次.2進(jìn)制和其它進(jìn)制包含信息量的換算以10進(jìn)制為例.給定k位10進(jìn)制數(shù)和x位2進(jìn)制數(shù),使兩個(gè)數(shù)表達(dá)的信息量相等有2023/2/6

信息工程學(xué)院戴永5110k-1=2x-1解之得x=k(Log10/Log2)將底改為2,有x=kLog210~~3.32k,表明1位10進(jìn)制數(shù)所含信息量相當(dāng)與3.32位2進(jìn)制數(shù)所含的信息量.推廣到一般有x=kLog2n,n為n進(jìn)制.n進(jìn)制有n個(gè)符號(hào),以下按n個(gè)符號(hào)出現(xiàn)的概率來表示x對(duì)應(yīng)的信息量.設(shè)n個(gè)符號(hào)分別對(duì)應(yīng)出現(xiàn)的概率為P1,P2,···,Pn,顯然P1+P2+···+Pn=1,在等概率條件下有nP=1,即P=1/n或n=1/P于是x=kLog2n=kLog2(1/P)=-kLog2P(這里的k要理解為流輸送了多少位,與進(jìn)制無關(guān),x為信息量)當(dāng)各符號(hào)出現(xiàn)的概率各不相同時(shí),設(shè)其中第i符號(hào)出現(xiàn)了k次,出現(xiàn)概率記為Pi,那么在單位時(shí)間內(nèi)平均出現(xiàn)的次數(shù)為kPi.2023/2/6

信息工程學(xué)院戴永52僅第i符號(hào)出現(xiàn)的信息量為-kPiLog2Pi.n個(gè)符號(hào)出現(xiàn)而產(chǎn)生的總的信息量為

x=-k∑n1PiLog2Pi改寫為(x/k)=-∑n1PiLog2Pi表明每一位n進(jìn)制符號(hào)對(duì)應(yīng)的2進(jìn)制信息量為-∑n1PiLog2Pi從傳送信息的角度討論,傳送一個(gè)bit需1/k時(shí)間,那么傳送x個(gè)2進(jìn)制代碼需要的時(shí)間x/k,其對(duì)應(yīng)的信息量為-∑n1PiLog2Pi,稱之為被傳送數(shù)據(jù)的“熵”,即一種用概率表示的信息量.對(duì)于單個(gè)符號(hào)的熵定義為-PiLog2Pi.數(shù)據(jù)的熵取決于各符號(hào)的概率Pi,當(dāng)n個(gè)符號(hào)出現(xiàn)的概率相等時(shí),數(shù)據(jù)的熵值達(dá)到最大,即用熵來計(jì)算數(shù)據(jù)冗于度R的方法為

R=x/k-(-∑n1PiLog2Pi)=-Log2(1/P)+∑n1PiLog2Pi

=-Log2(n)+∑n1PiLog2Pi當(dāng)輸入流被壓縮到無冗于度,即R=0時(shí),數(shù)據(jù)熵為∑n1PiLog2Pi=-Log2(n)2023/2/6

信息工程學(xué)院戴永532.1.1算法信息容量算法信息容量也稱計(jì)算機(jī)程序長度.描述計(jì)算機(jī)程序的一個(gè)述語是2進(jìn)制序列的復(fù)雜度.復(fù)雜度(KCC)定義:能生成2進(jìn)制字符串S的最短的計(jì)算機(jī)程序的長度(以位為單位).比如生成將2進(jìn)制字符串S去打印,顯示或?qū)戇M(jìn)文件等的程序.一般如果長度為n的2進(jìn)制字符串是隨機(jī)的,則其KCC也接近于n.從壓縮的角度考慮文本,圖像及聲音的復(fù)雜度多為中等的復(fù)雜度.2023/2/6

信息工程學(xué)院戴永54低等KCC為具有大量重復(fù)內(nèi)容的文件,如書中S1,實(shí)際少見;高等KCC為文件內(nèi)容大量的是隨機(jī)數(shù)據(jù),很不利于壓縮,如書中S2.中等KCC為既有隨機(jī)數(shù)據(jù)也有相當(dāng)數(shù)量便于壓縮的重復(fù)塊.算法信息容量也是對(duì)某消息所含信息的度量.信息論中對(duì)信息量是預(yù)測(cè)形式,而算法信息容量衡量的是已經(jīng)出現(xiàn)的信息,即人們對(duì)已出現(xiàn)信息的驚奇度.比如處理那一段代碼程序很簡單,或很長,或一般等.簡單的,重復(fù)的內(nèi)容不能增加信息量,或信息越來越少,內(nèi)容越新,越多,越復(fù)雜,信息量越多.這就是所謂的香農(nóng)信息論基本思想.2023/2/6

信息工程學(xué)院戴永552.2變長碼例1.設(shè)有4個(gè)字符,a1,a2,a3,a4.<1>若它們?cè)跀?shù)據(jù)串中出現(xiàn)的概率均等于0.25,相應(yīng)的數(shù)據(jù)熵(實(shí)際對(duì)應(yīng)的是2進(jìn)位數(shù))是4(-0.25Log20.25)=2即每個(gè)字符至少需要2位2進(jìn)制碼,這里先給4個(gè)字符分別賦予00,01,10,11.4個(gè)字符概率相等,R=0,所以數(shù)據(jù)不能被再壓縮,即不能被壓縮到低于2位/字符.<2>若出現(xiàn)概率不等,如P1=0.49,P2=0.25,P3=0.25,P4=0.01,對(duì)應(yīng)的數(shù)據(jù)熵為-(0.49Log20.49+0.25Log20.25+0.25Log20.25+0.01Log20.01)≈-(-0.050-0.5-0.5-0.066)=1.57即每字符的平均最少位數(shù)下降到了1.57位.2023/2/6

信息工程學(xué)院戴永56如果仍用個(gè)2位進(jìn)行編碼,則R=2-1.57=0.43.減少R的方法是采用不定長碼或變長碼.具體原理:將概率高的對(duì)應(yīng)短碼,依次增長,如下表所示.符號(hào)概率編碼1編碼2a10.4911a20.250101a30.25010000a40.01001001變長碼計(jì)算平均碼長的方法:因概率是該字符在整個(gè)數(shù)字串中出現(xiàn)的概率,賦予變長碼后,應(yīng)該考慮該字符對(duì)應(yīng)的碼長在數(shù)字串中出現(xiàn)的概率,這里可以把概率看成是比率,即假定輸出的數(shù)字串長度為Z,第i字符出現(xiàn)的次數(shù)為K(累積長度),則第i字符在數(shù)字串中出現(xiàn)的概率為K/Z,也是第i字符在Z中占據(jù)的長度比率.當(dāng)給各符號(hào)賦予不同的碼長時(shí),每個(gè)碼長在字串長度中占有的份額即為平均碼長,計(jì)算公式為:碼長?概率所有符號(hào)占用的代碼長度由下式求得碼長1?概率1+碼長2?概率2+·········+碼長n?概率n對(duì)于上表有1?0.49+2?0.25+3?0.25+3?0.01=1.77

接近最少位數(shù).2023/2/6

信息工程學(xué)院戴永57和等長碼相比,R=1.77-1.57=0.2.值得注意的是平均位短不一定數(shù)字串的編碼長度就短,需看采用何種編碼.例1.用上述表中符號(hào)編一個(gè)20符號(hào)的字符串(見書P32),每個(gè)符號(hào)的出現(xiàn)概率與表中相同.顯然,按等長編碼,1.57位必須用2位,需40位.如果按編碼1進(jìn)行變長碼編碼則只用了37位,每字符平均占用37/20=1.85位,和平均碼長的計(jì)算值很接近.編碼1存在解碼的歧義性.設(shè)從左到右進(jìn)行解碼.a1的編碼與其它3個(gè)有明顯區(qū)別不會(huì)出錯(cuò).a2~a4均以0開始,解碼器遇0后必須再往后查,再查到0肯定可以確定其右必為1,此3位為a4代碼.若查到的是1,則要區(qū)別a2還是a3,再往下查,如果是1,可以判為a2a1序列;如果是0,那么是a3,還是a2,a4,還是a2a3呢?編碼2按上述過程識(shí)別不會(huì)出現(xiàn)歧義,第2,3位都有獨(dú)立碼.2023/2/6

信息工程學(xué)院戴永58設(shè)計(jì)變長碼應(yīng)遵循的兩條規(guī)則:(1)把短碼賦予出現(xiàn)頻率高的字符;(2)遵循前綴性.按上述規(guī)則生成字符代碼可既短又唯一可譯,但未必最佳(未必是平均長度最短的碼字).2.3前綴碼前綴碼就是滿足前綴性(區(qū)別在前面規(guī)定的可變的碼長)的變長碼.前面介紹的整數(shù)2進(jìn)制編碼的碼長是已知的,即事先知道這組整數(shù)的位數(shù)為n,從而決定了碼長為1+Log2n;再者不能在代碼前加碼,即無前綴性.2023/2/6

信息工程學(xué)院戴永592.3.1一元前綴碼基本一元碼定義:設(shè)有正整數(shù)n,用n-1個(gè)1后跟一個(gè)0,或用n-1個(gè)0后跟一個(gè)1構(gòu)成的代碼稱為一元碼.可見一元碼的長度是n位.兩種結(jié)構(gòu)如下n0尾一元碼1尾一元碼101210013110001411100001511110000012023/2/6

信息工程學(xué)院戴永60通用一元碼定義:對(duì)數(shù)據(jù)字符進(jìn)行編碼的第n個(gè)碼字由n個(gè)1后跟一個(gè)0再加上所有的a位碼組成,a=開始數(shù)+n?步長數(shù).設(shè)定一個(gè)結(jié)束數(shù)(STOP),當(dāng)a=STOP時(shí),丟掉n個(gè)1后緊跟的一個(gè)0.可見通用一元碼形成取決于開始數(shù)(START),步長數(shù)(STEP)和結(jié)束數(shù),常用(START,STEP,STOP)三元組的形式表達(dá)通用一元碼.例1.設(shè)有通用一元碼(3,2,9),其對(duì)應(yīng)的碼字如下表

na=3+n?2第n個(gè)碼碼字?jǐn)?shù)目表達(dá)的整數(shù)范圍030xxx23=80~7

1510xxxxx25=328~39(將00000定為8)

27

110xxxxxxx27=128

40~(39+128)

3

9

111xxxxxxxxx29=512

168

~(39+128+512)2023/2/6

信息工程學(xué)院戴永61例2.通用一元碼為(2,1,10)請(qǐng)自閱.注意點(diǎn):(1)STOP通過步長累加是一定能到達(dá)的值.(2)a是符號(hào)可添加代碼的位數(shù).(3)除STOP對(duì)應(yīng)的碼字外,前面符號(hào)的已知代碼排列服從一元碼規(guī)則.(4)通用一元碼由已知碼和待填碼兩部分組成.(5)通用一元碼的數(shù)量=(2stop+step-2start)/(2step-1)例3.通用一元碼(3,2,9)的碼字?jǐn)?shù)=(512?4-8)/3=680=512+128+32+82023/2/6

信息工程學(xué)院戴永622.3.2其他前綴碼用B(n)代表整數(shù)n的2進(jìn)制表示,|B(n)|為這種表示所占用的位數(shù),用/B(n)表示B(n)去掉最高位后的編碼(最高位總是1).以下是基于這種表示的4種前綴碼.C1碼:前面是通用一元碼,后面是/B(n).例如n=16,則B(16)=(10000)2,|B(16)|=5,/B(16)=0000,由于|B(16)|=5,相應(yīng)的通用一元碼選用11110(也可采用00001).相應(yīng)的C1碼表示為11110|0000.|C1(n)|=2Log2n+1C2碼:將C1按如下方法重排既得C2.11110|0000→C2(16)=101010100C3碼:由前后兩部分組成.前部分根據(jù)n的2進(jìn)制位數(shù)進(jìn)行C2編碼,如n=16,則|B(16)|=5,C2(5)=10110(C1(5)=110|01);后部分為/B(n).例C3(16)=10110|00002023/2/6

信息工程學(xué)院戴永63C4:由多個(gè)碼位數(shù)遞減前排構(gòu)成.基本原理為從B(n)開始,以其|B(n)|-1的2進(jìn)制編碼遞歸左排,直到位數(shù)可用兩位代碼表示則停止,為便于識(shí)別在B(n)右邊加一個(gè)0.例.C4(16)=10|100|10000|05|B(4)|-1=2|B(16)|-1=4n等于其它值正整數(shù)的4種前綴碼請(qǐng)參閱P35.表2.6.以下根據(jù)碼長來計(jì)算n的概率對(duì)于一元碼,設(shè)整數(shù)為n,則表示n的2進(jìn)制位數(shù)即碼長L也為n,L=n=Log22n任意n在L位的組合中出現(xiàn)的概率為P(n)=1/2L=2-L=2-nC1(n)的長度L=1+2Log2n=Log2(2n2)如果也按L等于整數(shù)處理,則P(n)=2-L=1/(2n2)C3(n)的碼長L=1+Log2n+2(Log2(1+Log2n))2023/2/6

信息工程學(xué)院戴永64=Log22+2Log2Log22n+Log2n=Log22n+2Log2Log22n=Log2(2n(Log22n)2)因此在L等于整數(shù)的理想狀態(tài)下,有

P(n)=2-L=1/(2n(Log22n)2)P35表2.7給出了一元碼,C1,C3的8個(gè)整數(shù)的理想概率.對(duì)于特定場(chǎng)合正整數(shù)編碼的前綴碼按如下方法設(shè)計(jì)選擇一些相關(guān)的正整數(shù)vi,進(jìn)行有序排列,形成表格.2023/2/6

信息工程學(xué)院戴永65正整數(shù)n按以下步驟確定(1)找一個(gè)k,使其滿足∑k-1i=1vi

<n≤∑ki=1vi

(2)計(jì)算差值d,d=n-∑k-1i=1vi-1nmax=∑ki=1vi

,所以dmax=∑ki=1vi

-∑k-1i=1vi

–1=vk-1dmax是可以用Log2vk位表示的值對(duì)d進(jìn)行標(biāo)準(zhǔn)的2進(jìn)制編碼,有兩種碼長1)與d相等