算術(shù)編碼算法在圖像壓縮中的研究?

吳曉云

算術(shù)編碼算法在圖像壓縮中的研究?

吳曉云

（商洛學(xué)院電子信息與電氣工程學(xué)院 商洛 726000）

算術(shù)編碼是一種無(wú)損的數(shù)據(jù)壓縮方法，可以極大地減小信號(hào)的冗余度，由于其比較高的壓縮效率使得它被廣泛地應(yīng)用在圖像壓縮中。論文首先對(duì)算術(shù)編碼算法、編碼過(guò)程以及有限精度推導(dǎo)過(guò)程進(jìn)行了研究，最后在Matlab對(duì)算術(shù)編碼的靜態(tài)模型和自適應(yīng)模型進(jìn)行了仿真和分析。結(jié)果顯示算術(shù)編碼壓縮效果良好，能實(shí)現(xiàn)圖像數(shù)據(jù)的無(wú)損壓縮，體現(xiàn)了算術(shù)編碼圖像壓縮上的優(yōu)良性。

無(wú)損壓縮；算術(shù)編碼；靜態(tài)模型；自適應(yīng)模型

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 引言

在進(jìn)入信息化時(shí)代之后，各種數(shù)據(jù)量劇增，數(shù)據(jù)壓縮技術(shù)的研究受到越來(lái)越多的重視。算術(shù)編碼是一種無(wú)損壓縮方法，有著非常好的壓縮性能［1］。由于計(jì)算機(jī)硬件及精度過(guò)長(zhǎng)等方面的限制，算術(shù)編碼在壓縮領(lǐng)域沒(méi)有得到很好的應(yīng)用。但是隨著對(duì)算術(shù)編碼理論研究的成熟和壓縮技術(shù)的改進(jìn)，算術(shù)編碼作為一種優(yōu)于其它熵編碼方法，將成為圖像數(shù)據(jù)壓縮方法的主要編碼方法，應(yīng)用在圖像視頻壓縮領(lǐng)域。

2 算數(shù)編碼的基本算法

2.1 算數(shù)編碼原理

假設(shè)符號(hào)序列為［00，01，10，11］，它們的概率分布p（00）=0.1，p（01）=0.4，p（10）=0.2，p（11）=0.3，對(duì)輸入10001100101101序列進(jìn)行編碼，編碼過(guò)程可以如下［2］：

1）對(duì)信源符號(hào)按照概率的大小排列，將最開(kāi)始的區(qū)間設(shè)置為當(dāng)前區(qū)間。信源符號(hào)在當(dāng)前區(qū)間所占的大小與它的概率成正比。

2）選擇第一個(gè)信源符號(hào)，找到這個(gè)符號(hào)在當(dāng)前區(qū)間的比例間隔，將此比例間隔作為新的當(dāng)前區(qū)間。這個(gè)區(qū)間的上下限就成為新區(qū)間的上下限，最后把當(dāng)前區(qū)間的起點(diǎn)指示的數(shù)加到編碼輸出數(shù)。

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

圖1 算術(shù)編碼過(guò)程

由圖1可以看出其算術(shù)編碼的最后輸出在0.5143876～0.514402之間。可以在此區(qū)間內(nèi)任意選擇一個(gè)小數(shù)作為編碼的結(jié)果，比如0.5143878。

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

2.2 有限精度描述與推導(dǎo)

1）精度描述［4～5］

設(shè)X為無(wú)記憶平穩(wěn)隨機(jī)過(guò)程，Xn表示隨機(jī)變量的前n個(gè)輸出。每一個(gè)這樣的序列對(duì)應(yīng)于實(shí)軸［0，1］上的區(qū)間［cn，cn+an］。

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

當(dāng)p（0）=0.25；p（1）=0.75，對(duì)10110編碼時(shí)如圖2所示。

圖2 精度描述

最后得出區(qū)間為［85/44，367/45］。由此可見(jiàn)越往后其精度越來(lái)越大，所以需要有限精度來(lái)約束。

2）有限精度推導(dǎo)［6］

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

根據(jù)以上設(shè)區(qū)間長(zhǎng)度an為

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

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

3 算術(shù)編碼仿真

3.1 靜態(tài)模型的M atlab仿真

算術(shù)編碼的流程如3所示。在輸入圖像后首先計(jì)算其矩陣大小，再統(tǒng)計(jì)各個(gè)像素的概率，然后在（0，1）上進(jìn)行編碼，從而得出編碼的上下限，最后取其中一個(gè)元素作為輸出結(jié)果。解碼過(guò)程與編碼過(guò)程相似，利用算術(shù)編碼的逆作用來(lái)鎖定區(qū)間，進(jìn)行逐一的推導(dǎo)還原［7～8］。

圖3 算術(shù)編碼流程圖

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

圖4 算術(shù)編碼壓縮圖

3.2 自適應(yīng)模型的M atlab仿真

自適應(yīng)算術(shù)編碼在輸入圖像后首先要建立一個(gè)對(duì)應(yīng)的編碼模型，也就是上下文建模，對(duì)概率進(jìn)行估計(jì)后就可以進(jìn)行編碼，在編碼的過(guò)程中還要根據(jù)輸入像素序列來(lái)更新概率，直到序列輸入完畢即可［9～10］。它的編碼流程如圖5所示。

圖5 自適應(yīng)算術(shù)編碼流程圖

圖6 是自適應(yīng)算術(shù)編碼的原文件，圖7是對(duì)其壓縮后的文件，原件的大小為767字節(jié)，而壓縮后的文件為200字節(jié)，壓縮率大約為26%，從而在存儲(chǔ)中大大減小了數(shù)據(jù)量，加快了傳輸速度。圖8是解壓后的文件，可以看出與原文件相同，實(shí)現(xiàn)了無(wú)損壓縮［11～12］。

圖6 自適應(yīng)編碼原圖

圖7 自適應(yīng)編碼壓縮圖

圖8 自適應(yīng)編碼解壓圖

4 結(jié)語(yǔ)

本文在Matlab中對(duì)算術(shù)編碼的靜態(tài)模型和自適應(yīng)模型進(jìn)行仿真測(cè)試，結(jié)果表明算術(shù)編碼的靜態(tài)模型適合二值圖像的壓縮，自適應(yīng)模型比較適合不能預(yù)知概率和概率變化的情況，都能實(shí)現(xiàn)無(wú)損壓縮。隨著高新技術(shù)和電子產(chǎn)業(yè)的飛速發(fā)展，超大集成電路和CPU的提升，自適應(yīng)算術(shù)編碼的運(yùn)算復(fù)雜和精度問(wèn)題將迎刃而解，使得算術(shù)編碼將廣泛應(yīng)用于圖像視頻壓縮中。

［1］車(chē)晉.數(shù)字電視音視頻壓縮編碼技術(shù)分析與研究［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］曹燦云，王延求.淺儀圖像壓縮編碼技術(shù)的發(fā)展與應(yīng)用［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］鄧關(guān)寶，楊士元，汪銳.算術(shù)編碼在圖像信號(hào)壓縮中的應(yīng)用［J］.計(jì)算機(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］周晶.圖像壓縮技術(shù)中新型算術(shù)編碼的研究與應(yīng)用［J］.自動(dòng)化與應(yīng)用，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］張紅軍，董金明.多媒體數(shù)據(jù)壓縮技術(shù)方法研究［J］.忻州師范學(xué)院學(xué)報(bào)，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］孫倩，岑峰，余有靈.視頻壓縮中算術(shù)編碼的研究與發(fā)展［J］.高新技術(shù)產(chǎn)業(yè)發(fā)展，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］韋偉，游彬，萬(wàn)福，等.算術(shù)編碼理論及誤差分析研究［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］張煒琳，尹聰敏.淺談算術(shù)編碼的編解碼過(guò)程［J］.民營(yíng)科技，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］李瑋，林明.基于自適應(yīng)算術(shù)編碼的字符型報(bào)文壓縮技術(shù)［J］.科學(xué)技術(shù)與工程，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］張丹.基于上下文快速有效的自適應(yīng)二進(jìn)制算術(shù)編碼實(shí)現(xiàn)［J］.微型電腦應(yīng)用，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］韓崢，唐昆，崔慧娟.基于參數(shù)模型的自適應(yīng)二進(jìn)制算術(shù)編碼算法［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），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］林德立，蔡建立.基于上下文的自適應(yīng)二進(jìn)制算術(shù)編碼［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日

商洛學(xué)院根植地方專項(xiàng)項(xiàng)目（編號(hào)：gz16035）資助。

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