周菲菲，張晶晶，羅曉玲

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

?

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

周菲菲，張晶晶，羅曉玲

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

摘要：

關(guān)鍵詞：

0　引言

算術(shù)編碼廣泛應(yīng)用于圖像和視頻壓縮中［1-2］，是基于統(tǒng)計(jì)的、無損數(shù)據(jù)壓縮效率最高的熵編碼方法［3］。算術(shù)編碼的思想始于1948年Shannon的文章［4］，經(jīng)歷了從無限精度到有限精度實(shí)現(xiàn)的過程，第一個(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á)到對算術(shù)編碼器進(jìn)一步地高效應(yīng)用，本文從算術(shù)編碼的基本原理出發(fā)，詳細(xì)討論影響算術(shù)編碼器性能的各種因素，以CACM87和MQ-coder這兩個(gè)最具代表性也是目前在靜態(tài)圖像壓縮領(lǐng)域最常用的算術(shù)編碼器為對象，對其中最關(guān)鍵的概率估計(jì)方法進(jìn)行實(shí)驗(yàn)分析，就算術(shù)編碼器在使用時(shí)如何設(shè)計(jì)概率估計(jì)方法給出指導(dǎo)準(zhǔn)則。

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

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

從碼流本身的角度來看，包括：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總之，自適應(yīng)算術(shù)編碼取得了很好的編碼效果，在完全沒有先驗(yàn)知識的情況下，甚至可以得到小Shannon熵的結(jié)果，這主要得益于自適應(yīng)概率估計(jì)方法對碼流局部變化的適應(yīng)性強(qiáng)。然而，本質(zhì)上，以上方法都是基于碼流的統(tǒng)計(jì)特性，通過已編碼的符號的先驗(yàn)統(tǒng)計(jì)知識對待編碼符號的概率出現(xiàn)情況進(jìn)行估計(jì)，這是正確解碼的必要條件，因此，如果無法獲得更多的關(guān)于碼流序列特征的先驗(yàn)知識，那么就無法期待編碼結(jié)果會有質(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ì)特性是對一種概率估計(jì)方法的基本要求。早期的估計(jì)方法中，概率先驗(yàn)知識通常是通過對符號序列進(jìn)行預(yù)掃描得到，該概率情況就是碼流序列的一種全局概率情況，利用這個(gè)值就可以通過熵編碼來逼近信源的Shannon熵，目前的概率估計(jì)方法都能達(dá)到這一點(diǎn)的要求。此外，需要注意跟蹤到全局統(tǒng)計(jì)特性的速度總是越快越好。

（2）把握碼流局部變化

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

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

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

4　結(jié)語

本文討論分析了圖像壓縮中典型的兩個(gè)算術(shù)編碼器，在分析了影響算術(shù)編碼性能各因素的基礎(chǔ)上，通過實(shí)驗(yàn)對它們進(jìn)行了比較，總結(jié)了在設(shè)計(jì)概率估計(jì)方法時(shí)應(yīng)當(dāng)注意和遵循的準(zhǔn)則，對算術(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ì)的、無損數(shù)據(jù)壓縮效率最高的熵編碼方法，廣泛應(yīng)用于圖像和視頻壓縮中，其性能往往直接決定算法的壓縮效率。分析影響算術(shù)編碼性能的各種因素，并對其中最關(guān)鍵的概率估計(jì)方法進(jìn)行實(shí)驗(yàn)對比分析，給出設(shè)計(jì)概率估計(jì)方法應(yīng)當(dāng)遵循的準(zhǔn)則，對算術(shù)編碼器的進(jìn)一步高效應(yīng)用具有指導(dǎo)意義。

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

基金項(xiàng)目：

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

文章編號：1007-1423（2016）13-0022-05

DOI：10.3969/j.issn.1007-1423.2016.13.006

作者簡介：

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

張晶晶（1984-），女，河北人，碩士，助教，研究方向?yàn)樾盘柼幚?/p>

羅曉玲（1985-），女，福建省，碩士，講師，研究方向?yàn)樾盘柼幚?/p>

收稿日期：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