周菲菲，張晶晶，羅曉玲

（裝甲兵工程學(xué)院信息工程系，北京100072）

?

圖像壓縮中算術(shù)編碼器的比較研究

周菲菲，張晶晶，羅曉玲

（裝甲兵工程學(xué)院信息工程系，北京100072）

摘要：

關(guān)鍵詞：

0　引言

算術(shù)編碼廣泛應(yīng)用于圖像和視頻壓縮中［1-2］，是基于統(tǒng)計(jì)的、無(wú)損數(shù)據(jù)壓縮效率最高的熵編碼方法［3］。算術(shù)編碼的思想始于1948年Shannon的文章［4］，經(jīng)歷了從無(wú)限精度到有限精度實(shí)現(xiàn)的過(guò)程，第一個(gè)真正意義上的二進(jìn)制算術(shù)編碼器于上世紀(jì)80年代初由Rissanen和Langdon給出，而把算術(shù)編碼器推向?qū)嵱脛t要?dú)w功于1987年Witten等人發(fā)表的一個(gè)實(shí)用算術(shù)編碼器程序，即CACM87［5］。現(xiàn)在，算術(shù)編碼器已經(jīng)獲得了一些重要應(yīng)用，如IBM的QM-coder被用作靜止圖像壓縮標(biāo)準(zhǔn)JPEG的一部分，而IBM的MQ-coder［6］則被新的靜止圖像壓縮標(biāo)準(zhǔn)JPEG2000和二值圖像壓縮標(biāo)準(zhǔn)JBIG2所采用；另外，算術(shù)編碼器CACM87和CABAC分別是視頻圖像壓縮標(biāo)準(zhǔn)H.263和H.264、AVS+的可選項(xiàng)。總之，算術(shù)編碼器已經(jīng)成為高效壓縮不可或缺的組成部分。

為了達(dá)到對(duì)算術(shù)編碼器進(jìn)一步地高效應(yīng)用，本文從算術(shù)編碼的基本原理出發(fā)，詳細(xì)討論影響算術(shù)編碼器性能的各種因素，以CACM87和MQ-coder這兩個(gè)最具代表性也是目前在靜態(tài)圖像壓縮領(lǐng)域最常用的算術(shù)編碼器為對(duì)象，對(duì)其中最關(guān)鍵的概率估計(jì)方法進(jìn)行實(shí)驗(yàn)分析，就算術(shù)編碼器在使用時(shí)如何設(shè)計(jì)概率估計(jì)方法給出指導(dǎo)準(zhǔn)則。

1　影響算術(shù)編碼性能的因素分析

算術(shù)編碼按照信源輸出符號(hào)的概率對(duì)碼區(qū)間進(jìn)行遞歸分割，將整個(gè)符號(hào)序列映射為［0，1）區(qū)間的一個(gè)子區(qū)間，不同的符號(hào)序列最終對(duì)應(yīng)互不重疊的子區(qū)間，因此可以取區(qū)間內(nèi)的一點(diǎn)作為對(duì)應(yīng)序列的編碼，用于表示該點(diǎn)的新的符號(hào)序列即為壓縮碼流。原序列中符號(hào)的概率越大，對(duì)應(yīng)的碼區(qū)間就越長(zhǎng)，表示該碼區(qū)間所需要的編碼位數(shù)就越少。如果信源是平穩(wěn)的且發(fā)出的符號(hào)之間是統(tǒng)計(jì)獨(dú)立的，并且能夠獲得信源的先驗(yàn)統(tǒng)計(jì)知識(shí)，那么由Shannon的信息論可知，算術(shù)編碼能夠使壓縮達(dá)到理論的下界Shannon熵，其中先驗(yàn)知識(shí)通常需要對(duì)符號(hào)序列進(jìn)行預(yù)掃描得到，然而這并不是任何情況都允許的。此外，如果信源的統(tǒng)計(jì)規(guī)律是時(shí)變的，也即信源是非平穩(wěn)的，如圖像、視頻等都屬于非平穩(wěn)信源，就需要自適應(yīng)地、在線地對(duì)符號(hào)的概率進(jìn)行估計(jì)，才能得到更好的壓縮結(jié)果，也就是所謂的自適應(yīng)算術(shù)編碼。基于以上基本原理，分析影響算術(shù)編碼壓縮效率的因素如下：

從碼流本身的角度來(lái)看，包括：

（1）信源（碼流）的Shannon熵：熵值越小表示包含的信息量就越少，壓縮的潛力就越大，就可能得到越高的編碼效率，符號(hào)概率分布差異大的碼流其香農(nóng)熵小。

（2）碼流的概率分布特性：對(duì)于符號(hào)概率比值相同的兩段碼流，其局部也可以有不同的變化特性，會(huì)對(duì)自適應(yīng)算術(shù)編碼的壓縮效率產(chǎn)生一定的影響。然而，碼流本身的特性是很難改變的，只能在分析的基礎(chǔ)上加以利用，把握碼流特性對(duì)提高編碼性能也是至關(guān)重要的。

從編碼方法的角度來(lái)看，算術(shù)編碼是一類基于統(tǒng)計(jì)的熵編碼方法，它利用符號(hào)的概率差異來(lái)實(shí)現(xiàn)壓縮，符號(hào)的概率值直接決定了算術(shù)編碼的壓縮效果，所以對(duì)符號(hào)的概率估計(jì)是算術(shù)編碼研究領(lǐng)域最關(guān)鍵問(wèn)題。對(duì)符號(hào)概率估計(jì)的準(zhǔn)確程度直接決定了編碼效率，當(dāng)選定一種算術(shù)編碼實(shí)現(xiàn)方式時(shí)，這一精度主要取決于：

（1）初始值的設(shè)定：一般來(lái)說(shuō)，初始值的設(shè)定僅僅影響了編碼的初始階段，對(duì)于長(zhǎng)度較短的碼流序列來(lái)說(shuō)壓縮效率會(huì)有一定改變；如果編碼序列足夠長(zhǎng)時(shí)，初始值設(shè)定的影響就非常小了。但是，如果在編碼的過(guò)程中，利用已獲得的先驗(yàn)知識(shí)頻繁地干預(yù)并設(shè)定碼流的概率值，還是會(huì)對(duì)編碼效率產(chǎn)生積極的影響。

（2）符號(hào)的概率估計(jì)：這一因素始終作用于編碼的整個(gè)階段，一直對(duì)編碼的效果產(chǎn)生影響，因此，可以說(shuō)概率估計(jì)是決定壓縮效率最主要因素。高效的概率估計(jì)方法應(yīng)當(dāng)在把握碼流整體特性的基礎(chǔ)上，較好地跟蹤并反映碼流的局部變化，從而實(shí)現(xiàn)合理的區(qū)間分配。

2　典型的概率估計(jì)方法

下面介紹圖像壓縮領(lǐng)域常用的自適應(yīng)概率估計(jì)方法，由于在圖像壓縮中算術(shù)編碼常用于上下文預(yù)測(cè)分類后的二元碼流序列的壓縮，所以以下概率估計(jì)模型的給出都是針對(duì)二符號(hào)集的情況，很容易將這些方法擴(kuò)展到多符號(hào)的情況。

（1）比值計(jì)數(shù)估計(jì)法

概率估計(jì)最直觀、簡(jiǎn)單的方法是對(duì)已經(jīng)出現(xiàn)的符號(hào)進(jìn)行計(jì)數(shù)，用該符號(hào)出現(xiàn)的頻率值作為概率估計(jì)值，比值計(jì)數(shù)（Scaled-Count，SC）估計(jì)法的思想就是這樣。事實(shí)上，這是在假設(shè)信源序列中各隨機(jī)變量是獨(dú)立、同分布的前提下，對(duì)先驗(yàn)概率密度為均勻分布的情況用貝葉斯估計(jì)得到的，不過(guò)，大量實(shí)驗(yàn)說(shuō)明，對(duì)很多信源來(lái)說(shuō)，得到的模型均適用。設(shè)C0、C1分別為已編碼的“0”和“1”的個(gè)數(shù)，則下一位為“0”的概率為：

其中，Δ的取值影響了概率估計(jì)的變化快慢。當(dāng)Δ取較大的值時(shí)，估計(jì)變化慢，且估計(jì)的偏斜量較小，傾向于認(rèn)為概率分布是均勻的，是比較保守的方法，反之較小的值對(duì)應(yīng)更激進(jìn)的方法，適用于高度偏斜概率發(fā)生可能性大的情況。該方法是從整體統(tǒng)計(jì)意義上對(duì)符號(hào)進(jìn)行概率估計(jì)，能反映碼流的總體概率變化趨勢(shì)，CACM87算術(shù)編碼器采用的就是此概率估計(jì)方法。

此外，為了能及時(shí)跟蹤非平穩(wěn)碼流的概率變化，可設(shè)置閾值Cmin和Cmax，當(dāng)min｛C0，C1｝〉Cmin或者max｛C0，C1｝〈Cmax，就對(duì)C0和C1進(jìn)行收縮操作，通常是減半（除以2）。

（2）概率狀態(tài)表法

上述比值計(jì)數(shù)估計(jì)器是一個(gè)有限狀態(tài)機(jī)，最終可以通過(guò)建立概率狀態(tài)轉(zhuǎn)移表實(shí)現(xiàn)。表的建立是基于理論分析和大量的統(tǒng)計(jì)實(shí)驗(yàn)，并利用當(dāng)前狀態(tài)所對(duì)應(yīng)的概率值對(duì)當(dāng)前符號(hào)進(jìn)行編碼，然后按照預(yù)先定義的規(guī)則，從轉(zhuǎn)移表的一個(gè)狀態(tài)跳入另一個(gè)狀態(tài)，由于不同的狀態(tài)對(duì)應(yīng)不同的概率估計(jì)值，從而實(shí)現(xiàn)對(duì)概率估計(jì)值的更新。

JPEG2000中采用的MQ-coder就是其中的典型代表，其概率狀態(tài)轉(zhuǎn)移表如表1所示。狀態(tài)0～13與轉(zhuǎn)移表的“啟動(dòng)”部分相對(duì)應(yīng)，采用貝葉斯學(xué)習(xí)過(guò)程，利用較少的符號(hào)實(shí)現(xiàn)對(duì)碼流概率的初步估計(jì)；最后的狀態(tài)46是非自適應(yīng)的，一旦進(jìn)入這個(gè)狀態(tài)就不可能離開(kāi)它；剩余的狀態(tài)14～45表示表的非暫態(tài)部分，一旦從一個(gè)啟動(dòng)狀態(tài)進(jìn)入，狀態(tài)機(jī)就永遠(yuǎn)無(wú)法離開(kāi)非暫態(tài)部分。概率估計(jì)采用重歸一化驅(qū)動(dòng)，符合實(shí)際應(yīng)用的需求。由于表的規(guī)模有限，所以必須使用近似操作，這會(huì)損失編碼效率。但是，相較于比值估計(jì)法，它用查表操作代替算術(shù)運(yùn)算來(lái)進(jìn)行概率估計(jì)，從而擁有更快的編碼速度，因此，在實(shí)際中使用廣泛。

3　實(shí)驗(yàn)結(jié)果及分析

這兩種典型的概率估計(jì)方法對(duì)應(yīng)了不同算術(shù)編碼的實(shí)現(xiàn)方式，在實(shí)際中都有應(yīng)用。下面，通過(guò)實(shí)驗(yàn)來(lái)分析一下它們概率估計(jì)的效果，本文選取了一段真實(shí)的圖像壓縮中待編碼的碼流，采用各種概率估計(jì)方法得到的概率估計(jì)變化曲線圖，如圖1所示。為了便于比較，本文設(shè)計(jì)了滑動(dòng)窗口概率估計(jì)法（SW）（實(shí)際中，由于存儲(chǔ)開(kāi)銷等問(wèn)題，一般無(wú)法真正使用），窗口內(nèi)始終存放與當(dāng)前待編碼位最靠近的若干位數(shù)據(jù)，并利用實(shí)際窗口中0、1的真實(shí)頻率值作為對(duì)0、1符號(hào)的概率估計(jì)值，可以認(rèn)為是對(duì)碼流序列局部變化最準(zhǔn)確的刻畫，圖1（a）是窗口大小為100時(shí)概率估計(jì)值變化情況。圖1（b）對(duì)應(yīng)不帶收縮操作的SC概率估計(jì)方法，隨著編碼的進(jìn)行曲線圖逐漸趨于平緩，對(duì)應(yīng)碼流序列的總體統(tǒng)計(jì)特性，適用于變化平緩的信源，對(duì)碼流的局部變化不敏感。圖1（c）為帶收縮操作的SC概率估計(jì)方法，該方法能及時(shí)地根據(jù)碼流序列的變化情況調(diào)整其概率估計(jì)，因此從圖中可以看出，它很好地跟蹤到了碼流的局部變化，曲線的整體走勢(shì)與SW極其相似，只是該方法計(jì)算復(fù)雜度高。圖1（d）是采用MQ概率狀態(tài)轉(zhuǎn)移表得到的概率估計(jì)值，該方法通過(guò)頻繁的狀態(tài)跳轉(zhuǎn)來(lái)跟蹤碼流的變化，能夠反映出碼流的變化走勢(shì)，但與圖1（a）相比變化相對(duì)劇烈，對(duì)碼流的局部變化非常敏感，實(shí)驗(yàn)表明，這種過(guò)度的敏感性很多時(shí)候會(huì)帶來(lái)編碼效果的降低，不過(guò)該方法的計(jì)算復(fù)雜度較低。不同的概率估計(jì)方法可能會(huì)帶來(lái)上百bit的編碼差異。

表1　MQ編碼器概率狀態(tài)轉(zhuǎn)移表

圖1　各方法概率估計(jì)曲線圖

采用以上概率方法，對(duì)9段真實(shí)待壓縮碼流進(jìn)行算術(shù)編碼，結(jié)果如表2所示，其中，最好的結(jié)果用粗體表示。其中，SW和SC（帶收縮）效果相當(dāng)，這與圖1的結(jié)果是吻合的，甚至在很多情況下，SC會(huì)取得優(yōu)于采用碼流局部真實(shí)頻率值的SW的效果，分析可能的原因是，SW僅僅參考與當(dāng)前待編碼位相鄰的若干位數(shù)據(jù)來(lái)估計(jì)當(dāng)前位的概率值，而另兩種方法相當(dāng)于為最近看到的符號(hào)賦以更大的權(quán)重，概率估計(jì)時(shí)是以前面看到的所有符號(hào)作為參考基礎(chǔ)的，所以從統(tǒng)計(jì)意義上可能獲得比SW更好的效果，但是三者沒(méi)有質(zhì)的差別。特別指出的是，雖然免乘法的MQ在大多數(shù)情況下都不如其他方法，但是對(duì)于概率分布差異極大，也即“0”符號(hào)出現(xiàn)頻率極高的碼流序列，該方法卻取得了最好的效果，究其可能的原因，由于該方法的靈敏性高，當(dāng)出現(xiàn)連續(xù)0很多的情況下，某些局部對(duì)0的概率估計(jì)值可能達(dá)到很大，所以對(duì)大量出現(xiàn)的0符號(hào)取得了很好的編碼效果，此時(shí)若有1出現(xiàn)，則需要付出額外的編碼代價(jià)，結(jié)果說(shuō)明獲得的增益比損失大。

表2　算術(shù)編碼器性能比較

總之，自適應(yīng)算術(shù)編碼取得了很好的編碼效果，在完全沒(méi)有先驗(yàn)知識(shí)的情況下，甚至可以得到小Shannon熵的結(jié)果，這主要得益于自適應(yīng)概率估計(jì)方法對(duì)碼流局部變化的適應(yīng)性強(qiáng)。然而，本質(zhì)上，以上方法都是基于碼流的統(tǒng)計(jì)特性，通過(guò)已編碼的符號(hào)的先驗(yàn)統(tǒng)計(jì)知識(shí)對(duì)待編碼符號(hào)的概率出現(xiàn)情況進(jìn)行估計(jì)，這是正確解碼的必要條件，因此，如果無(wú)法獲得更多的關(guān)于碼流序列特征的先驗(yàn)知識(shí)，那么就無(wú)法期待編碼結(jié)果會(huì)有質(zhì)的提高，這符合熵編碼基于統(tǒng)計(jì)特性的初衷。

基于以上統(tǒng)計(jì)實(shí)驗(yàn)及結(jié)果分析，本文總結(jié)出以下幾點(diǎn)適用于概率估計(jì)方法設(shè)計(jì)的準(zhǔn)則，包括：

（1）描述全局統(tǒng)計(jì)特性

反映出碼流的全局概率統(tǒng)計(jì)特性是對(duì)一種概率估計(jì)方法的基本要求。早期的估計(jì)方法中，概率先驗(yàn)知識(shí)通常是通過(guò)對(duì)符號(hào)序列進(jìn)行預(yù)掃描得到，該概率情況就是碼流序列的一種全局概率情況，利用這個(gè)值就可以通過(guò)熵編碼來(lái)逼近信源的Shannon熵，目前的概率估計(jì)方法都能達(dá)到這一點(diǎn)的要求。此外，需要注意跟蹤到全局統(tǒng)計(jì)特性的速度總是越快越好。

（2）把握碼流局部變化

如果期望在Shannon熵的基礎(chǔ)上進(jìn)一步提高編碼效率，逼近一種更高階的熵值，則概率估計(jì)方法還必須能夠把握碼流的局部變化，隨著編碼的進(jìn)行不斷地對(duì)概率估計(jì)值做出調(diào)整和更新?；谝陨蠈?shí)驗(yàn)可知，好的概率估計(jì)既要反映出碼流的局部概率變化，又不能對(duì)這種變化過(guò)于敏感，使得概率估計(jì)值的變化過(guò)于劇烈，需在碼流總體特性的基礎(chǔ)上進(jìn)行調(diào)整，否則懲罰的代價(jià)總是大于收益的。

（3）計(jì)算復(fù)雜度權(quán)衡

通常來(lái)講，更好的概率估計(jì)方法總是對(duì)應(yīng)了更高的計(jì)算復(fù)雜度，若想要提高編碼速度，必然要犧牲一部分編碼性能，因此，通常需要的編碼效率和編碼速度之間進(jìn)行權(quán)衡，根據(jù)實(shí)際需要選擇一種折中的方式。

4　結(jié)語(yǔ)

本文討論分析了圖像壓縮中典型的兩個(gè)算術(shù)編碼器，在分析了影響算術(shù)編碼性能各因素的基礎(chǔ)上，通過(guò)實(shí)驗(yàn)對(duì)它們進(jìn)行了比較，總結(jié)了在設(shè)計(jì)概率估計(jì)方法時(shí)應(yīng)當(dāng)注意和遵循的準(zhǔn)則，對(duì)算術(shù)編碼器在圖像、視頻壓縮中的進(jìn)一步高效利用具有指導(dǎo)意義。

參考文獻(xiàn)：

［1］王玉晶，莫建麟．DCT算術(shù)編碼在圖像壓縮中的應(yīng)用［J］．西南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，41（1）：107-109.

［2］王佳，張剛，常青等．AVS+中熵編碼算法的研究與實(shí)現(xiàn)［J］．科學(xué)技術(shù)與工程，2015，15（2）：231-235.

［3］傅祖蕓．信息論基礎(chǔ)理論與應(yīng)用（第4版）［M］．北京：電子工業(yè)出版社，2015.

［4］C. E. Shannon. A Mathematical Theory of Communication［J］. Bell System Technical Journal，1948，27: 379-423、623-656.

［5］Cleary J. G.，Witten I. H.，Neal R. M.. Arithmetic Coding for Data Compression［J］. IBM Journal of Research and Development，Commun of the ACM. 1987，30（6）: 520～541

［6］Taubman D.，Marcellin M. W.. JPEG2000: Image Compression Fundamentals，Standards and Practice［M］. Kluwer Academic Publishers，2002

Comparative Study of Arithmetic Encoder in Image Compression

ZHOU Fei-fei，ZHANG Jing-jing，LUO Xiao-ling
（Department of Information Engineering，Academy of Armored Forces Engineering，Beijing 100072）

Abstract：

Keywords：

算術(shù)編碼是基于統(tǒng)計(jì)的、無(wú)損數(shù)據(jù)壓縮效率最高的熵編碼方法，廣泛應(yīng)用于圖像和視頻壓縮中，其性能往往直接決定算法的壓縮效率。分析影響算術(shù)編碼性能的各種因素，并對(duì)其中最關(guān)鍵的概率估計(jì)方法進(jìn)行實(shí)驗(yàn)對(duì)比分析，給出設(shè)計(jì)概率估計(jì)方法應(yīng)當(dāng)遵循的準(zhǔn)則，對(duì)算術(shù)編碼器的進(jìn)一步高效應(yīng)用具有指導(dǎo)意義。

算術(shù)編碼；概率估計(jì)；圖像壓縮

基金項(xiàng)目：

學(xué)院創(chuàng)新基金項(xiàng)目（No.2013XX029）

文章編號(hào)：1007-1423（2016）13-0022-05

DOI：10.3969/j.issn.1007-1423.2016.13.006

作者簡(jiǎn)介：

周菲菲（1982-），女，山西太原人，講師，博士，研究方向?yàn)閳D像處理、熵編碼

張晶晶（1984-），女，河北人，碩士，助教，研究方向?yàn)樾盘?hào)處理

羅曉玲（1985-），女，福建省，碩士，講師，研究方向?yàn)樾盘?hào)處理

收稿日期：2016-03-15修稿日期：2016-04-10

Arithmetic coding is the most efficient entropy coding method based on statistical and lossless data compression. It is widely used in image and video compression，and its performance directly determines the efficiency of the algorithm. Various factors influencing the performance of arithmetic coding is analyzed. And the most critical probability estimation method to carry on the comparative analysis of the experiment，and gives the design probability estimation methods should follow the guidelines，the arithmetic coder further，application has guiding significance.

Arithmetic Coding；Probability Estimation；Image Compression