編碼之統(tǒng)計(jì)編碼與信息熵

1.統(tǒng)計(jì)編碼原理——信息量和信息熵根據(jù)香農(nóng)信息論的原理，最佳的數(shù)據(jù)壓縮方法的理論極限是信息熵。如果要求在編碼過程中不丟失信息量，即要求保存信息熵，這種信息保持的編碼又叫熵保存編碼，或叫熵編碼。熵編碼是無失真壓縮。當(dāng)然在考慮人眼失真不易察覺的生理特性時(shí)，有些圖像編碼不嚴(yán)格要求熵保存，信息允許通過部分損失來換取高的數(shù)據(jù)壓縮比。這種編碼屬于有失真數(shù)據(jù)壓縮。信息是用不確定性的量度定義的，也就是說信息被假設(shè)為由一系列的隨機(jī)變量所代表，它們往往用隨機(jī)出現(xiàn)的符號來表示。我們稱輸出這些符號的源為“信源”。也就是要進(jìn)行研究與壓縮的對象。信息量信息量指從N個(gè)相等可能事件中選出一個(gè)事件所需要的信息度量或含量，也可以說是辨別N個(gè)事件中特定事件過程中所需提問“是”或“否”的最小次數(shù)。例如：從64個(gè)數(shù)(1?64的整數(shù))中選定某一個(gè)數(shù)(采用折半查找算法)，提問：“是否大于32?”，則不論回答是與否，都消去半數(shù)的可能事件，如此下去，只要問6次這類問題，就可以從64個(gè)數(shù)中選定一個(gè)數(shù)，則所需的信息量是=6(bit)。我們現(xiàn)在可以換一種方式定義信息量，也就是信息論中信息量的定義。設(shè)從N中選定任一個(gè)數(shù)X的概率為P(x)，假定任選一個(gè)數(shù)的概率都相等，即P(x)=1/N，則信息量I(x)可定義為：上式可隨對數(shù)所用“底”的不同而取不同的值，因而其單位也就不同。設(shè)底取大于1的整數(shù)a，考慮一般物理器件的二態(tài)性，通常a取2,相應(yīng)的信息量單位為比特(bit)；當(dāng)a=e，相應(yīng)的信息量單位為奈特(Nat)；當(dāng)a=10，相應(yīng)的信息量單位為哈特(Hart)。顯然，當(dāng)隨機(jī)事件x發(fā)生的先驗(yàn)概率P(x)大時(shí)，算出的I(x)小，那么這個(gè)事件發(fā)生的可能性大，不確定性小，事件一旦發(fā)生后提供的信息量也少。必然事件的P(x)等于1，I(x)等于0，所以必然事件的消息報(bào)導(dǎo)，不含任何信息量;但是一件人們都沒有估計(jì)到的事件(P(x)極小)，一旦發(fā)生后，I(x)大，包含的信息量很大。所以隨機(jī)事件的先驗(yàn)概率，與事件發(fā)生后所產(chǎn)生的信息量，有密切關(guān)系。I(x)稱x發(fā)生后的自信息量，它也是一個(gè)隨機(jī)變量。P(x)大時(shí)，算出的I(x)小必然事件的P(x)等于1，I(x)等于0。P(x)小時(shí)，算出的I(x)大必然事件的P(x)等于0，I(x)等于1。I(x)稱x發(fā)生后的自信息量，它也是一個(gè)隨機(jī)變量。信息熵現(xiàn)在可以給“熵”下個(gè)定義了。信息量計(jì)算的是一個(gè)信源的某一個(gè)事件叫)的自信息量，而一個(gè)信源若由n個(gè)隨機(jī)事件組成，n個(gè)隨機(jī)事件的平均信息量就定義為熵(Entropy)。熵的準(zhǔn)確定義是:信源X發(fā)出的xj(j=1,2,……n),共n個(gè)隨機(jī)事件的自信息統(tǒng)計(jì)平均(求數(shù)學(xué)期望)，即H(X)在信息論中稱為信源X的“熵(Entropy)”，它的含義是信源X發(fā)出任意一個(gè)隨機(jī)變量的平均信息量。更詳細(xì)的說，一般在解釋和理解信息熵有4種樣式當(dāng)處于事件發(fā)生之前，H(X)是不確定性的度量；當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇性的度量；當(dāng)處于事件發(fā)生之后，是獲得信息的度量；還可以理解為是事件隨機(jī)性的度量.下面為了掌握信息熵的概念，我們來做一道計(jì)算題。例如：以信源X中有8個(gè)隨機(jī)事件，即n=8。每一個(gè)隨機(jī)事件的概率都相等，即P(x1)=P(x2)=P(x3)……P(x8)=1/8，計(jì)算信源X的熵。應(yīng)用“熵”的定義可得其平均信息量為3比特再例：信源X中有17個(gè)隨機(jī)事件，即n=17。每一個(gè)隨機(jī)事件的概率分別為：計(jì)算信源X的熵。信息熵的計(jì)算公式：信源X的熵：定長碼與變長碼定長碼(fixed-lengthcode)即采用相同的位數(shù)(bit)對數(shù)據(jù)進(jìn)行編碼。大多數(shù)存儲數(shù)字信息的編碼系統(tǒng)都采用定長碼。如我們常用的ASCII碼就是定長碼，其碼長為1字節(jié)(Byte)。漢字國標(biāo)碼也是定長碼，其碼長為2字節(jié)(Byte)。變長碼(variable-lengthcode)即采用不相同的位數(shù)(bit)對數(shù)據(jù)進(jìn)行編碼，以節(jié)省存儲空間。例如，不同的字符或漢字出現(xiàn)的概率是不同的，有的字符出現(xiàn)的概率非常高，有的則非常低。根據(jù)統(tǒng)計(jì)，英文字母中“E”的使用概率約為13%，而字母“Z”的使用概率則為0.08%。又如大多數(shù)圖像常含有單色的大面積圖塊，而且某些顏色比其他顏色出現(xiàn)更頻繁。為了節(jié)省空間，在對數(shù)據(jù)進(jìn)行編碼時(shí)，就有可能對那些經(jīng)常出現(xiàn)的數(shù)據(jù)指定較少的位數(shù)表示，而那些不常出現(xiàn)的數(shù)據(jù)指定較多的位數(shù)表示。這樣從總的效果看還是節(jié)省了存儲空間。用這種方法得到的代碼，其碼的位數(shù)，也即碼長就是不固定的，故稱為變長碼。香農(nóng)-范諾編碼，以及霍夫曼編碼，都是變長碼。2.赫夫曼(Huffman)編碼基本原理：按信源符號出現(xiàn)的概率大小進(jìn)行排序，出現(xiàn)概率大的分配短碼，出現(xiàn)概率小的則分配長碼。(定長碼采用相同的碼長對數(shù)據(jù)進(jìn)行編碼，如ASCII碼是定長碼，其碼長為1字節(jié)。)定理：在變長碼中，對于出現(xiàn)概率在的信息符號編以短字長的碼，對于出現(xiàn)概率小的信息符號以長字長的碼，如果碼字長度嚴(yán)格按照符號概率的大小的相反順序排列，則平均碼字長度一定小于按任何其他符號順序排列方式得到的碼字長度。定理證明設(shè)最佳排列方式的碼字平均長度為，則有：式中為信源符號出現(xiàn)的概率，是符號的編碼長度。規(guī)定，。如果將的碼字與的碼字互換，其余碼字不變，經(jīng)過這樣的互換以后，平均碼字長度變成，即因?yàn)椋?，也就是說最短。證畢。Huffman編碼的編碼步驟概率統(tǒng)計(jì)(如對一幅圖像，或m幅同種類型圖像作灰度信號統(tǒng)計(jì))，得到n個(gè)不同概率的信息符號。將n個(gè)信源信息符號的n個(gè)概率，按概率大小排序。將n個(gè)概率中，最后兩個(gè)小概率相加，這時(shí)概率個(gè)數(shù)減為n-1個(gè)。將n-1個(gè)概率，按大小重新排序。重復(fù)③，將新排序后的最后兩個(gè)小概率再相加，相加和與其余概率再排序。如此反復(fù)重復(fù)n-2次，得到只剩兩個(gè)概率序列。以二進(jìn)制碼元(0.1)賦值，構(gòu)成霍夫曼碼字。編碼結(jié)束。利用Huffman編碼方式對信源進(jìn)行編碼已知信源:編碼結(jié)果：X1X2X3X4X5X6X7001001001111011101111平均碼長：=(0.35+0.20)X2+(0.15+0.10+0.10)X3+(0.06+0.04)X4=2.55(bit)(對于等長碼則需要3比特)。Huffman編碼的特點(diǎn)（1）平均碼長（熵）；（2）平均碼長bits（等長碼需要的比特?cái)?shù)）；（3）保證解碼的唯一性，短碼字不構(gòu)成長碼字的前綴；（4）在接收端需保存一個(gè)與發(fā)送端相同的赫夫曼碼表。Huffman不足方面：（1）構(gòu)造出的碼不唯一，其原因是：一是在給兩個(gè)分支賦值時(shí)，可以是左支（或上支）為0，也可以是右支（或下支）為0，造成編碼的不唯一；二是當(dāng)兩個(gè)消息的概率相等時(shí)，誰前誰后也是隨機(jī)的，構(gòu)造出來的碼字也不唯一。（2）編碼碼字字長參差不齊，因此硬件實(shí)現(xiàn)起來不大方便。（3）編碼對不同信編碼效率是不同的。在概率頒很不均勻時(shí)，Huffman編碼才會有顯著的效果，在信源頒均勻的情況下，一般不使用Huffman編碼。3.算術(shù)編碼（ArithmeticCoding）算術(shù)編碼方法也是利用信源概率分布特性、能夠趨近熵極限的編碼的方法。算術(shù)編碼不按符號編碼，即不是用一個(gè)特定的碼字與輸入符號之間建立一一對應(yīng)的關(guān)系，而是從整個(gè)符號序列出發(fā)，采用遞推形式進(jìn)行連續(xù)編碼，用一個(gè)單獨(dú)的浮點(diǎn)數(shù)來表示一串輸入符號。算術(shù)編碼是將被編碼的信息表示成實(shí)數(shù)0和1之間的一個(gè)間隔。信息越長編碼表示它的間隙就越小，表示這一間隙所須二進(jìn)位就越多，大概率符號出現(xiàn)的概率越大對應(yīng)于區(qū)間愈寬，可用長度較短的碼字表示；小概率符號出現(xiàn)概率越小層間愈窄，需要較長碼字表示。它的編碼方法比Huffman編碼方式要復(fù)雜，但它不需要傳送像Huffman編碼中的Huffman碼表，同時(shí)算術(shù)編碼還有自適應(yīng)的優(yōu)點(diǎn)，所以算術(shù)編碼是實(shí)現(xiàn)高效壓縮數(shù)據(jù)中很有前途的編碼方法。特點(diǎn)：方法比較復(fù)雜，具有自適應(yīng)能力（隨著編碼符號流中01出現(xiàn)的概率的變化將自適應(yīng)的改變）。在信源符號概率接近時(shí)，算術(shù)編碼比Huffman編碼效率要高。算術(shù)編碼與解碼舉例假設(shè)信源符號為｛00,01,10,11｝，這些符號的概率分別為｛0.1,0.4,0.2,0.3｝，根據(jù)這些概率可把間隔[0,1）分成4個(gè)子間隔：[0,0.1）,[0.1,0.5）,[0.5,0.7）,[0.7,1），其中[x,y）表示半開放間隔，即包含x不包含y。上面的信息可綜合在下表中。表信源符號，概率和初始編碼間隔符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1）[0.1,0.5）[0.5,0.7）[0.7,1）如果二進(jìn)制消息序列的輸入為：10001100101101。編碼時(shí)首先輸入的符號是10，找到它的編碼范圍是[0.5,0.7）。由于消息中第二個(gè)符號00的編碼范圍是[0,0.1），因此它的間隔就?。?.5,0.7）的第一個(gè)十分之一作為新間隔［0.5,0.52）。依此類推，編碼第3個(gè)符號11時(shí)取新間隔為［0.514,0.52），編碼第4個(gè)符號00時(shí)，取新間隔為［0.514,0.5146），…。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。整個(gè)編碼過程如下圖示：表：編碼過程步驟輸入符號編碼間隔編碼判決10[0.5,0.7)符號的間隔范圍[0.5,0.7)00[0.5,0.52)[0.5,0.7)間隔的第一個(gè)1/1011[0.514,0.52)[0.5,0.52)間隔的最后三個(gè)1/1000[0.514,0.5146)[0.514,0.52)間隔的第一個(gè)1/1010[0.5143,0.51442)[0.514,0.5146)間隔的第六個(gè)1/10開始的兩個(gè)1/1011[0.514384,0.51442)[0.5143,0.51442)間隔的最后三個(gè)1/1001[0.5143836,0.514402)[0.514384,0.51442)間隔的從第二個(gè)1/10開始的四個(gè)1/108從[0.5143876,0.514402中選擇一個(gè)數(shù)作為輸出：0.51439表：譯碼過程步驟間隔譯碼符號譯碼判決[0.5,0.7)100.51439在間隔[0,1)第六個(gè)1/10[0.5,0.52)000.51439在間隔[0.5,0.7)的第一個(gè)1/10[0.514,0.52)110.51439在間隔[0.5,0.52)的第八個(gè)1/10[0.514,0.5146)000.51439在間隔[0.514,0.52)的第一個(gè)1/10[0.5143,0.51442)100.51439在間隔[0.514,0.5146)的第七個(gè)1/10[0.514384,0.51442)110.51439在間隔[0.5143,0.51442)的第八個(gè)1/10[0.5143876,0.514402)010.51439在間隔[0.5143876,0.514402)的第二個(gè)1/10譯碼的消息：10001100101101譯碼器的譯碼過程應(yīng)無限制地運(yùn)行下去。在譯碼器中需要添加一個(gè)專門的終止符，當(dāng)譯碼器看到終止符時(shí)就停止譯碼。在算術(shù)編碼中需要注意的幾個(gè)問題：由于實(shí)際的計(jì)算機(jī)的精度不可能無限長，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(gè)問題可使用比例縮放方法解決。算術(shù)編碼器對整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔［0,1）中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會導(dǎo)致整個(gè)消息譯錯(cuò)。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號的概率根據(jù)編碼時(shí)符號出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號概率的過程叫做建模。需要開發(fā)自適應(yīng)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。因此動(dòng)態(tài)建模就成為確定編碼器壓縮效率的關(guān)鍵。算術(shù)編碼的實(shí)現(xiàn)相應(yīng)地比Huffman編碼復(fù)雜，但當(dāng)與信號源符號的出現(xiàn)概率接近時(shí)，算術(shù)編碼的效率高于Huffman編碼。在圖像測試中表明，算術(shù)編碼效率比Huffman效率高5%左右。分形編碼的思路1988年1月，美國Georgia理工學(xué)院的M.F.Barnsley在BYTE發(fā)表了分形壓縮方法。分形編碼法（FractalCoding）的目的是發(fā)掘自然物體（比如天空、云霧、森林等）在結(jié)構(gòu)上的自相似形，這種自相似形是圖像整體與局部相關(guān)性的表現(xiàn)。分形壓縮正是利用了分形幾何中的自相似的原理來實(shí)現(xiàn)的。首先對圖像進(jìn)行分塊，然后再去尋找各塊之間的相似形，這里相似形的描述主要是依靠仿射變換確定的。一旦找到了每塊的仿射變換，就保存下這個(gè)仿射變換的系數(shù)，由于每塊的數(shù)據(jù)量遠(yuǎn)大于仿射變換的系數(shù)，因而圖像得以大幅度的壓縮。分形編碼以其獨(dú)特新穎的思想，成為目前數(shù)據(jù)壓縮領(lǐng)域的研究熱點(diǎn)之一。分形編碼、基于模型編碼與經(jīng)典圖像編碼方法相比，在思想和思維上有了很大的突破，理論上的壓縮比可超出經(jīng)典編碼方法兩三個(gè)數(shù)量級。分形編碼方法和步驟以平面點(diǎn)集合與圖像為例，迭代函數(shù)系統(tǒng)壓縮編碼大致步驟為：圖像分割首先將原圖（集合X或圖像）預(yù)分割（或預(yù)分解）為若干分形子圖X（m）（m=1，2,…，M），使得每一個(gè)子圖X（m）具有一定的分形結(jié)構(gòu)，及其局部與整體之間保持某種相似特征。而這種子圖分割可以是空間域分割，也可以是頻率域或其他空間域分割。在總圖像的分割中，常常把同類或者相近的物體放在同一子圖中，而把不同的景物，如山脈、河流、沙漠、云霧、森林、草地等，分別置于不同的子圖中。提