多階自適應(yīng)算術(shù)編碼研究

李 彬，倪桂強(qiáng)，羅健欣

(解放軍理工大學(xué) 指揮自動(dòng)化學(xué)院，江蘇 南京210007)

數(shù)據(jù)壓縮分為有損壓縮和無(wú)損壓縮。其中無(wú)損壓縮編碼是基于信息熵原理的可逆編碼，目前主要有基于統(tǒng)計(jì)模型的哈夫曼編碼和算術(shù)編碼，以及基于字典模型的LZ系列編碼。算術(shù)編碼克服了哈夫曼編碼只能用整數(shù)位的代碼表示一個(gè)信源符號(hào)的缺點(diǎn)，而采用了用一個(gè)浮點(diǎn)數(shù)表示一個(gè)信源符號(hào)流的思想，可以更逼近信源編碼。算術(shù)編碼算法在靜止圖像壓縮編碼標(biāo)準(zhǔn)JPEG2000[1]和視頻編碼標(biāo)準(zhǔn)H.264[2]中已被作為國(guó)際標(biāo)準(zhǔn)廣泛采用。

提高編碼的壓縮率和降低編碼的時(shí)間、空間復(fù)雜度是人們研究壓縮編碼算法的主要目的。基于對(duì)信息中單個(gè)符號(hào)頻率統(tǒng)計(jì)的算術(shù)編碼是一種向極限挑戰(zhàn)的編碼方式。本文研究的多階自適應(yīng)算術(shù)編碼著重通過(guò)研究符號(hào)在某符號(hào)序列之后出現(xiàn)的概率來(lái)獲得高效壓縮。參考文獻(xiàn)[3]介紹了一種基于多階上下文自適應(yīng)的二進(jìn)制算術(shù)編碼的實(shí)現(xiàn)，實(shí)現(xiàn)了3階自適應(yīng)。參考文獻(xiàn)[4]介紹了一種能降低復(fù)雜度和內(nèi)存空間但是略微降低了編碼效率的簡(jiǎn)化編碼模型。本文的多階自適應(yīng)算術(shù)編碼對(duì)參數(shù)進(jìn)行了優(yōu)化，可以進(jìn)行更高階次的編碼（測(cè)試中最高可達(dá)11階），在最大限度降低空間消耗的同時(shí)，獲得更好的壓縮效果。與LZW和WinRAR的性能比較結(jié)果表明，本文的多階自適應(yīng)算術(shù)編碼能獲得更滿意的壓縮效果。

1 算術(shù)編碼

1.1 算術(shù)編碼原理

算術(shù)編碼將被編碼的信源符號(hào)流表示成實(shí)數(shù)半開(kāi)區(qū)間[0，1)中的一個(gè)數(shù)值間隔，這個(gè)間隔隨著信息流中每一個(gè)信源符號(hào)的加入逐步減小，每次減小的程度取決于當(dāng)前加入的信源符號(hào)的概率。概率高者減少的程度低，概率低者減少的程度高。符號(hào)流越長(zhǎng)，代表它的間隔越小，編碼表示這一間隔所需的位數(shù)就越多。從算術(shù)編碼過(guò)程中產(chǎn)生的數(shù)值可以被唯一地解碼，精確地恢復(fù)原始的信源符號(hào)流[3]。

設(shè)信源符號(hào)集由 3個(gè)信源符號(hào){a1，a2，a3}組成，根據(jù)已知的信源符號(hào)概率，在[0，1)區(qū)間上為它們分配相應(yīng)的子區(qū)間，子區(qū)間大小與概率成正比。其概率分布及對(duì)應(yīng)的子區(qū)間如表1所示。

表1 信源符號(hào)及其數(shù)值范圍

用range表示編碼輸出數(shù)值落入的間隔，high為range的上界，low為下界，初始時(shí) high為 1，low為 0。 用high_range表示某符號(hào)子區(qū)間的上界，low_range為下界。每一信源符號(hào)被編碼后，根據(jù)公式(1)計(jì)算 high、low及range的新值，并根據(jù)概率分布重新劃分被編碼符號(hào)的子區(qū)間。最后一個(gè)符號(hào)得到的間隔內(nèi)的任何一個(gè)實(shí)數(shù)代表整個(gè)符號(hào)流。對(duì)符號(hào)流“a1a2a3a2a1”進(jìn)行算術(shù)編碼的過(guò)程如圖1所示，用0.305就可以唯一地代表這個(gè)符號(hào)流。

1.2 多階自適應(yīng)算術(shù)編碼

根據(jù)編碼過(guò)程中信源符號(hào)是否更新概率分布，算術(shù)編碼分為靜態(tài)模型和自適應(yīng)模型。靜態(tài)模型的缺點(diǎn)是：首先需要在編碼前對(duì)信源符號(hào)的分布進(jìn)行統(tǒng)計(jì)，會(huì)消耗大量時(shí)間；其次符號(hào)的概率是該符號(hào)在整個(gè)信息中的概率，根據(jù)信息熵原理，不利于對(duì)信息的壓縮。而自適應(yīng)模型隨著符號(hào)的讀入，實(shí)時(shí)動(dòng)態(tài)更新符號(hào)的概率分布，能統(tǒng)計(jì)出某個(gè)符號(hào)在局部的出現(xiàn)概率或某個(gè)符號(hào)相對(duì)于某一上下文的出現(xiàn)概率，壓縮效果好于靜態(tài)模型。

自適應(yīng)編碼中，初始時(shí)假設(shè)各個(gè)符號(hào)的概率相同，并平均分配區(qū)間[0，1)，隨著符號(hào)的讀入，相應(yīng)地更新其概率值，與之對(duì)應(yīng)的子區(qū)間亦隨之改變。若有新的符號(hào)出現(xiàn)則加入符號(hào)集即可。仍設(shè)信源符號(hào)集由3個(gè)符號(hào){a1，a2，a3}組成，對(duì)于符號(hào)流“a1a2a3a2a1”，各個(gè)符號(hào)概率更新、子區(qū)間比例變化、符號(hào)累計(jì)及間隔變化過(guò)程如表2所示。

最后一個(gè)符號(hào)輸入后不再劃分子區(qū)間，得到讀入a1后的區(qū)間[0.238 9，0.240 4)，即編碼結(jié)果的輸出數(shù)值區(qū)間，如0.24就可以作為符號(hào)流編碼結(jié)果。同樣類(lèi)似的解碼過(guò)程可以唯一地解出原符號(hào)流。

如果編碼時(shí)考慮符號(hào)之間的相關(guān)性，把多個(gè)符號(hào)按照不同的上下文結(jié)構(gòu)組合在一起，當(dāng)作一個(gè)編碼單元進(jìn)行自適應(yīng)算術(shù)編碼，就可以進(jìn)一步提高編碼效率。用“階”表示上下文相關(guān)符號(hào)序列的長(zhǎng)度，那么1階上下文自適應(yīng)統(tǒng)計(jì)的就是符號(hào)在某個(gè)特定的符號(hào)后面出現(xiàn)的概率，同樣2階、3階上下文自適應(yīng)統(tǒng)計(jì)的是符號(hào)在某兩個(gè)、三個(gè)特定符號(hào)后面出現(xiàn)的概率。使用多階算術(shù)編碼，使得同一符號(hào)可以在多個(gè)動(dòng)態(tài)統(tǒng)計(jì)的上下文概率表中取得概率值較大的進(jìn)行編碼，從而使總熵值更小。如在1階自適應(yīng)編碼中，在已經(jīng)編碼的10 000個(gè)符號(hào)后，剛剛編碼的符號(hào)是a1，下一個(gè)要編碼的符號(hào)是a2，在之前的10 000個(gè)符號(hào)中統(tǒng)計(jì)到出現(xiàn)了100個(gè)a1和 a2，a2出現(xiàn)在 a1之后的次數(shù)是 10次，那么 a2在 a1之后的概率是 10/100，這一概率對(duì)應(yīng)的熵值是-log2(10/100)=3.321 9 bit，遠(yuǎn)小于 0階的熵值-log2(100/10000)=6.643 9 bit。采用 2階、3階或更高階次的自適應(yīng)算術(shù)編碼，可以獲得更高的壓縮率。

2 建模與算法實(shí)現(xiàn)

2.1 自適應(yīng)編碼模型

用high_count和low_count表示ai對(duì)應(yīng)的子區(qū)間上下界，用scale表示已讀入符號(hào)總數(shù)。讀入符號(hào)ai時(shí)，scale加1，與該符號(hào)對(duì)應(yīng)的子區(qū)間的上界及后面子區(qū)間的上下界值都加1。high和low表示編碼輸出數(shù)值range的上下界，其初始值分別為0xffff和0，則可以通過(guò)公式(2)確定range的范圍。在編碼過(guò)程中，用二進(jìn)制表示的range的數(shù)值范圍越來(lái)越小，當(dāng)high與low的最高位相同時(shí)，則把最高位二進(jìn)制作為碼流輸出，且使high與low左移一位，high末位補(bǔ) 1，low末位補(bǔ) 0。當(dāng) high與 low十分接近沒(méi)有相同最高位時(shí)，就產(chǎn)生下溢，這時(shí)需要擴(kuò)大range使后面的編碼繼續(xù)進(jìn)行，記錄下溢位數(shù)，并在下次編碼時(shí)作為碼流輸出，用于解碼時(shí)保持一致。圖2顯示了自適應(yīng)編碼的基本過(guò)程。

2.2 多階上下文模型

符號(hào)在某符號(hào)序列后出現(xiàn)的概率往往高于其在整個(gè)信息中的概率，這是多階自適應(yīng)算術(shù)編碼能顯著提高壓縮效果的關(guān)鍵。在1階上下文模型中，使用數(shù)組來(lái)統(tǒng)計(jì)符號(hào)出現(xiàn)的次數(shù)是可行的，但對(duì)于2階、3階或更高階的上下文，數(shù)組大小將按指數(shù)級(jí)增長(zhǎng)（256n+1），采用樹(shù)結(jié)構(gòu)[4]存儲(chǔ)出現(xiàn)過(guò)的上下文可以解決存儲(chǔ)空間問(wèn)題。因此，多階上下文模型是一個(gè)包含多個(gè)鏈表節(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)，如果根的層次為0，那么樹(shù)的層次對(duì)應(yīng)了模型的階，父節(jié)點(diǎn)對(duì)應(yīng)低階上下文，子節(jié)點(diǎn)對(duì)應(yīng)高階上下文，各層鏈表節(jié)點(diǎn)構(gòu)成了該層符號(hào)表，鏈表節(jié)點(diǎn)中指向父節(jié)點(diǎn)和子節(jié)點(diǎn)的指針構(gòu)成了符號(hào)序列的上下文關(guān)系，形成上下文樹(shù)。樹(shù)中只有出現(xiàn)過(guò)的上下文才擁有已分配的節(jié)點(diǎn)，沒(méi)有出現(xiàn)過(guò)的上下文不占用內(nèi)存空間。在每個(gè)上下文表中，也無(wú)需保存所有 256個(gè)字符的計(jì)數(shù)，只有在該上下文后面出現(xiàn)過(guò)的字符才擁有計(jì)數(shù)值。由此，可以最大限度地減少空間消耗。

對(duì)于一個(gè)未知的上下文，需要用到一個(gè)特殊的記號(hào)——轉(zhuǎn)義碼，用來(lái)告知解碼器下一個(gè)上下文在此之前從未出現(xiàn)過(guò)，需要使用低階的上下文進(jìn)行解碼。比如在3階上下文模型中，剛剛編碼過(guò) a1a2a3，現(xiàn)在要編碼a4，而在a1a2a3后面從來(lái)沒(méi)有出現(xiàn)過(guò)a4，這時(shí)需要輸出轉(zhuǎn)義碼，并進(jìn)入2階上下文表查找a4在a2a3后面出現(xiàn)在次數(shù)，如果找到則用2階中的概率為a4編碼，否則輸出轉(zhuǎn)義碼進(jìn)入1階上下文表查找，如仍未找到，則輸出轉(zhuǎn)義碼進(jìn)入最低的0階上下文表，如果a4從未出現(xiàn)過(guò)，則轉(zhuǎn)到一個(gè)特殊的轉(zhuǎn)義表，表內(nèi)包含0～255所有符號(hào)，每個(gè)符號(hào)的計(jì)數(shù)都為1，并且永遠(yuǎn)不會(huì)被更新，任何在高階上下文中沒(méi)有出現(xiàn)的符號(hào)都可以退到這里按照1/256的概率進(jìn)行編碼，隨后將a4加入到各階符號(hào)表中。符號(hào)流“a1a2a3a4…ai…”的上下文環(huán)境處理過(guò)程如圖 3所示，其中節(jié)點(diǎn)是簡(jiǎn)化了的鏈表節(jié)點(diǎn)，實(shí)線箭頭表示指向高一階上下文的指針（葉子節(jié)點(diǎn)指針為空），形成上下文表，虛線箭頭表示指向低一階上下文的指針（根節(jié)點(diǎn)除外）。

多階上下文模型在初始化時(shí)，需要?jiǎng)?chuàng)建轉(zhuǎn)義表及初始上下文表，上下文表中各階鏈表節(jié)點(diǎn)中設(shè)置符號(hào)表、符號(hào)計(jì)數(shù)器、符號(hào)表大小計(jì)數(shù)器以及上下文指針。讀入符號(hào)后，在當(dāng)前上下文表中從高階到低階查找符號(hào)表，找到后輸出其在符號(hào)表的累計(jì)次數(shù)，進(jìn)而計(jì)算其概率區(qū)間，否則進(jìn)入轉(zhuǎn)義表，輸出固定的概率值1/256，然后進(jìn)入編碼器編碼，編碼完成后，更新上下文表，將符號(hào)加入到當(dāng)前上下文各階節(jié)點(diǎn)的符號(hào)表中，并更新符號(hào)計(jì)數(shù)器。多階上下文自適應(yīng)算術(shù)編碼流程如圖4所示。

3 性能測(cè)試與比較

壓縮率是反應(yīng)壓縮效果的重要指標(biāo)，其計(jì)算式為：（1-輸出文件大小/輸入文件大?。?00%，其值越大，壓縮效果越好。為測(cè)試程序性能，選取了不同大小和不同類(lèi)型的文件進(jìn)行壓縮，試驗(yàn)結(jié)果如圖5所示，其中文本文件是大小為137 979 B的歷史文獻(xiàn)節(jié)選，位圖文件是分辨率為1 680×1 050、大小為 5 292 054 B的電腦桌面文件。從結(jié)果中可以看出，多階自適應(yīng)算術(shù)編碼能達(dá)到很好的壓縮效果，壓縮率隨著階次的升高而提高，但提高幅度逐漸降低，3階和4階就能達(dá)到比較顯著的壓縮效果。與參考文獻(xiàn)[5]中改進(jìn)的LZW算法比較發(fā)現(xiàn)，0～2階的壓縮效果要差于LZW，但從3階開(kāi)始，壓縮效果就要優(yōu)于LZW。

考慮到多階自適應(yīng)算術(shù)編碼的特征，其對(duì)上下文相關(guān)性強(qiáng)的文件壓縮可以達(dá)到更高的壓縮率。為此，選取了一個(gè)內(nèi)容相關(guān)性強(qiáng)的文本文件和一個(gè)背景變化不太大的位圖文件，如表3和表4所示顯示了多階自適應(yīng)算術(shù)編碼與LZW以及WinRAR的比較結(jié)果?？煽闯?，多階自適應(yīng)算術(shù)編碼對(duì)上下文相關(guān)性強(qiáng)的文件壓縮效果從2階開(kāi)始就優(yōu)于LZW，而3、4階就能較明顯的好于WinRAR。

表5記錄了多階自適應(yīng)算術(shù)編碼和LZW算法對(duì)上述4個(gè)文件壓縮所需要的時(shí)間，從表中可以看出，低階編碼消耗的時(shí)間最多，3階、4階左右消耗的時(shí)間最少，再高階次消耗的時(shí)間反而上升。 另外，對(duì)于一般性文件，LZW消耗的時(shí)間明顯少于本文多階算法，但是對(duì)于上下文相關(guān)性強(qiáng)的文件，本文多階算法可以明顯少于LZW。

表3 壓縮比較(原文件：110 522 B)

表4 壓縮比較(原文件：3 932 214 B)

表5 多階自適應(yīng)算術(shù)編碼與LZW算法時(shí)間消耗比較（單位：s）

從以上性能測(cè)試與比較中可以得出，本文研究的多階自適應(yīng)算術(shù)編碼在3階、4階時(shí)可以獲得滿意的壓縮率，而且消耗的時(shí)間最少，在整體上壓縮效果最佳。

[1]陳瑋，楊名利.基于 FPGA的 JPEG2000自適應(yīng)算術(shù)編碼器設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(10)：211-213.

[2]DAMIAN K，MAREK D.Improved context-adaptive arithmetic coding in H.264/avc[C].Glasgow：EUSIPCO，2009：2216-2220.

[3]楊文濤，劉衛(wèi)忠，鄭立新.多階上下文自適應(yīng)二進(jìn)制算術(shù)編碼實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，35(3)：42-45.

[4]謝林，虞露，仇佩亮.基于上下文的自適應(yīng)二進(jìn)制算術(shù)編碼研究[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2005，39(6)：910-914.

[5]張鳳林，劉思峰.LZW*：一個(gè)改進(jìn)的LZW數(shù)據(jù)壓縮算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(10)：1897-1899.