算術編碼算法在圖像壓縮中的研究?

吳曉云

算術編碼算法在圖像壓縮中的研究?

吳曉云

（商洛學院電子信息與電氣工程學院 商洛 726000）

算術編碼是一種無損的數據壓縮方法，可以極大地減小信號的冗余度，由于其比較高的壓縮效率使得它被廣泛地應用在圖像壓縮中。論文首先對算術編碼算法、編碼過程以及有限精度推導過程進行了研究，最后在Matlab對算術編碼的靜態模型和自適應模型進行了仿真和分析。結果顯示算術編碼壓縮效果良好，能實現圖像數據的無損壓縮，體現了算術編碼圖像壓縮上的優良性。

無損壓縮；算術編碼；靜態模型；自適應模型

AbstractArithmetic coding is a lossless data compression method，which can greatly reduce the redundancy of the signal.Be?cause of its high compression efficiency，it is widely used in image compression.The arithmetic coding algorithm，the coding pro?cess and the finite precision derivation process is studied in this paper.Finally，the static model and the adaptive model of arithme?tic coding are simulated and analyzed in Matlab.The results show that the arithmetic coding has a good compression effect.It can re?alize the lossless compression of image data，and it shows the good performance of arithmetic coding image compression.

Key Wordslossless compression，arithmetic coding，static model，adaptive model

Class NumberTP391

1 引言

在進入信息化時代之后，各種數據量劇增，數據壓縮技術的研究受到越來越多的重視。算術編碼是一種無損壓縮方法，有著非常好的壓縮性能［1］。由于計算機硬件及精度過長等方面的限制，算術編碼在壓縮領域沒有得到很好的應用。但是隨著對算術編碼理論研究的成熟和壓縮技術的改進，算術編碼作為一種優于其它熵編碼方法，將成為圖像數據壓縮方法的主要編碼方法，應用在圖像視頻壓縮領域。

2 算數編碼的基本算法

2.1 算數編碼原理

假設符號序列為［00，01，10，11］，它們的概率分布p（00）=0.1，p（01）=0.4，p（10）=0.2，p（11）=0.3，對輸入10001100101101序列進行編碼，編碼過程可以如下［2］：

1）對信源符號按照概率的大小排列，將最開始的區間設置為當前區間。信源符號在當前區間所占的大小與它的概率成正比。

2）選擇第一個信源符號，找到這個符號在當前區間的比例間隔，將此比例間隔作為新的當前區間。這個區間的上下限就成為新區間的上下限，最后把當前區間的起點指示的數加到編碼輸出數。

3）再次按照信源符號的概率序列在新區間劃分比例間隔。然后選擇下一個信源符號，重復第二步。直到輸入完信源序列，最后的輸出就是其算術編碼。具體如圖1所示。

圖1 算術編碼過程

由圖1可以看出其算術編碼的最后輸出在0.5143876～0.514402之間。可以在此區間內任意選擇一個小數作為編碼的結果，比如0.5143878。

算術編碼的優良性眾所周知，但是算術編碼有一個最大的缺點就是：隨著對信源序列編碼的逐漸進行，小數點后的位數會逐漸增加，而很多計算機的精度不能無限增加［3］。比如16位、32位或者64位，那么溢出就不可避免，精度的限制就成了必不可少的一部分，所以在描述區間的小數上提出了有限精度描述。

2.2 有限精度描述與推導

1）精度描述［4～5］

設X為無記憶平穩隨機過程，Xn表示隨機變量的前n個輸出。每一個這樣的序列對應于實軸［0，1］上的區間［cn，cn+an］。

其中P(xn)表示xn出現的概率。

當p（0）=0.25；p（1）=0.75，對10110編碼時如圖2所示。

圖2 精度描述

最后得出區間為［85/44，367/45］。由此可見越往后其精度越來越大，所以需要有限精度來約束。

2）有限精度推導［6］

有限精度不需要得到長度的精確值，只需滿足式（4）可得到唯一解。

根據以上設區間長度an為

即an=0.00..1xxxx，bn表示 an中1前的0的個數，An為N 位整數1xxx..。

當An＜2n-1時，區間上下界相同，最高位可輸出。用q位整數表示P(xn)=2-qP(xn)。結合式（2）和式（3）可得：

3 算術編碼仿真

3.1 靜態模型的M atlab仿真

算術編碼的流程如3所示。在輸入圖像后首先計算其矩陣大小，再統計各個像素的概率，然后在（0，1）上進行編碼，從而得出編碼的上下限，最后取其中一個元素作為輸出結果。解碼過程與編碼過程相似，利用算術編碼的逆作用來鎖定區間，進行逐一的推導還原［7～8］。

圖3 算術編碼流程圖

圖4 為算術編碼的壓縮圖，左邊為原始的圖像，右邊為解壓圖像，可以看出達到了無損壓縮。其編碼時間為0.094s算術編碼范圍上限為0.248453126740064，下限為0.248453061949268。

圖4 算術編碼壓縮圖

3.2 自適應模型的M atlab仿真

自適應算術編碼在輸入圖像后首先要建立一個對應的編碼模型，也就是上下文建模，對概率進行估計后就可以進行編碼，在編碼的過程中還要根據輸入像素序列來更新概率，直到序列輸入完畢即可［9～10］。它的編碼流程如圖5所示。

圖5 自適應算術編碼流程圖

圖6 是自適應算術編碼的原文件，圖7是對其壓縮后的文件，原件的大小為767字節，而壓縮后的文件為200字節，壓縮率大約為26%，從而在存儲中大大減小了數據量，加快了傳輸速度。圖8是解壓后的文件，可以看出與原文件相同，實現了無損壓縮［11～12］。

圖6 自適應編碼原圖

圖7 自適應編碼壓縮圖

圖8 自適應編碼解壓圖

4 結語

本文在Matlab中對算術編碼的靜態模型和自適應模型進行仿真測試，結果表明算術編碼的靜態模型適合二值圖像的壓縮，自適應模型比較適合不能預知概率和概率變化的情況，都能實現無損壓縮。隨著高新技術和電子產業的飛速發展，超大集成電路和CPU的提升，自適應算術編碼的運算復雜和精度問題將迎刃而解，使得算術編碼將廣泛應用于圖像視頻壓縮中。

［1］車晉.數字電視音視頻壓縮編碼技術分析與研究［J］.廣播電視信息，2013，18（12）：66-69.

CHE Jin.Analysis and Research of Digital Audio and Vid?eo Compression Coding Technology［J］.Radio&Televi?sion Information，2013，18（12）：66-69.

［2］曹燦云，王延求.淺儀圖像壓縮編碼技術的發展與應用［J］.信息與電腦，2013，21（3）：127-129.

CAO Canyun，WANG Yanqiu.Development and Applica?tion of Image Compression Coding Technology［J］.Com?puter&Communication，2013，21（3）：127-129.

［3］鄧關寶，楊士元，汪銳.算術編碼在圖像信號壓縮中的應用［J］.計算機工程，2016，32（6）：234-236.

DENG Guanbao，YANG Shiyuan，WAGN Rui.Applica?tion of Arithmetic Coding in Image Signal Compression［J］.Computer Engineering，2016，32（6）：234-236.

［4］周晶.圖像壓縮技術中新型算術編碼的研究與應用［J］.自動化與應用，2015，35（4）：47-49.

ZHOU Jin.Research and Application of New Arithmetic Coding in Image Compression［J］.Automation and Appli?cation，2015，35（4）：47-49.

［5］張紅軍，董金明.多媒體數據壓縮技術方法研究［J］.忻州師范學院學報，2014，30（2）：20-22.

ZHANG Hongjun，DONG Jinming.Research of Multime?dia Data Compression Technology［J］.Journal of Xinzhou Teachers University，2014，30（2）：20-22.

［6］孫倩，岑峰，余有靈.視頻壓縮中算術編碼的研究與發展［J］.高新技術產業發展，2011，10（1）：9-12.

SUN Qian，CEN Feng，YU Youling.Research and Devel?opment of Arithmetic Coding in Video Compression［J］.High_tech Industry Development，2011，10（1）：9-12.

［7］韋偉，游彬，萬福，等.算術編碼理論及誤差分析研究［J］.艦船電子工程，2011，32（12）：69-71.

WEI Wei，YOU Bin，WAN Fu，et al.Research of Arithme?tic Coding Theory and Error Analysis［J］.Ship Electronic Engineering，2011，32（12）：69-71.

［8］張煒琳，尹聰敏.淺談算術編碼的編解碼過程［J］.民營科技，2013，8（12）：8-10.

ZHANG Weilin，YIN Congmin.Discuss of Encoding and Decoding Process of Arithmetic Coding［J］.Private Sci?ence and Technology，2013，8（12）：8-10.

［9］李瑋，林明.基于自適應算術編碼的字符型報文壓縮技術［J］.科學技術與工程，2013，13（10）：37-38.

LI Wei，LIN Ming.Character Type Message Compression Technology Based on Adaptive Arithmetic Coding［J］.Sci?ence Technology and Engineering，2013，13（10）：37-38.

［10］張丹.基于上下文快速有效的自適應二進制算術編碼實現［J］.微型電腦應用，2010，26（7）：56-58.

ZHANG Dan.Implementation of Adaptive Binary Arith?metic Coding Based on Context［J］.Microcomputer Ap?plications，2010，26（7）：56-58.

［11］韓崢，唐昆，崔慧娟.基于參數模型的自適應二進制算術編碼算法［J］.清華大學學報（自然科學版），2009，49（4）：132-534.

HAN Zheng，TANG Kun，CUI Huijuan.Adaptive binary arithmetic coding algorithm based on parameter model［J］.Journal of Tsinghua University（Science and Tech?nology），2009，49（4）：132-534.

［12］林德立，蔡建立.基于上下文的自適應二進制算術編碼［J］.福建電腦，2009，13（7）：69-70.

LIN Deli，CAI Jianli.Adaptive Binary Arithmetic Coding Based Context［J］.Fujian Computer，2009，13（7）：69-70.

Research of Arithmetic Coding in Image Com pression

WU Xiaoyun
（College of Electronic Information and Electrical Engineering，Shangluo University，Shangluo 726000）

TP391

10.3969/j.issn.1672-9722.2017.09.036

2017年3月9日，

2017年4月20日

商洛學院根植地方專項項目（編號：gz16035）資助。

吳曉云，女，碩士，講師，研究方向：數據采集與處理，圖像處理。