楊樹媛，紀(jì)朝鳳（新疆農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，烏魯木齊830052）

彩色圖像3D-DCT的熵編碼方法研究

楊樹媛，紀(jì)朝鳳
（新疆農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，烏魯木齊830052）

在彩色圖像的三維離散余弦變換壓縮體系中，交流系數(shù)游程編碼后存在大量的長零游程，傳統(tǒng)的JPEG基于（Run，Level）統(tǒng)計(jì)進(jìn)行熵編碼，壓縮性能較差；通過對(duì)交流系數(shù)分布的研究，提出基于（Run Level，Level）的聯(lián)合概率分布進(jìn)行熵編碼的改進(jìn)方法，該方法碼表簡單，且可直接復(fù)用JPEG碼表，有很大潛力應(yīng)用于更高維的視頻圖像變換壓縮領(lǐng)域。另外，根據(jù)非零系數(shù)的分布特點(diǎn)和編碼效率分析，對(duì)密集區(qū)和疏散區(qū)域采用不同的編碼方法。實(shí)驗(yàn)結(jié)果表明，在相同的PSNR下，較JEPG基線標(biāo)準(zhǔn)有11%的碼流節(jié)省。

游程編碼；熵編碼；3D-DCT；圖像壓縮

0　引言

在彩色圖像壓縮領(lǐng)域，三維離散余弦變換（Three Dimensional Discrete Cosine Transform，3D-DCT）被認(rèn)為是運(yùn)動(dòng)補(bǔ)償?shù)奶娲夹g(shù)[1]，它利用RGB三幀的相關(guān)性（例如相同的紋理和相同的灰度、梯度），采用沿著幀方向的一維DCT的方法，來替代傳統(tǒng)圖像壓縮標(biāo)準(zhǔn)中的色空間轉(zhuǎn)換方法，以此消除色空間冗余。

JPEG對(duì)交流（Alternating Current，AC）系數(shù)編碼的主要方法是：首先進(jìn)行游程編碼（Run Length Coding，RLC），然后將游程編碼后的（Run，Level）數(shù)對(duì)進(jìn)行霍夫曼熵編碼（Entropy Coding，EC），即RL-EC方法，這里Run指的是連續(xù)零系數(shù)的長度，Level是非零系數(shù)幅值的數(shù)量級(jí)。關(guān)于RL-EC的改進(jìn)算法，國內(nèi)外已經(jīng)進(jìn)行了大量研究。針對(duì)連續(xù)的非零系數(shù)進(jìn)行編碼時(shí)，碼流長度將會(huì)增加的問題，Tian提出了將非零AC系數(shù)的密集區(qū)和疏散區(qū)進(jìn)行不同編碼的思路[2]；基于當(dāng)掃描位置不同時(shí)，系數(shù)分布的概率統(tǒng)計(jì)模型也是不同的現(xiàn)象，Lakhani提出了一種建立最優(yōu)霍夫曼碼表的方法[3]。跟傳統(tǒng)的單上下文模型相比，姜提出了一種基于聯(lián)合上下文模型的新方法[4]。

上文中的熵編碼方法都是適用于基于2D-DCT算法編碼器的，在3D-DCT中，存在一個(gè)新問題：游程編碼后，出現(xiàn)更多的長零游程，并且游程長度大于15的非常普遍。針對(duì)這一問題，F(xiàn)ryza[5]將JEPG中的碼表進(jìn)行了擴(kuò)展；對(duì)于游程長度大于15的零游程，鄒[6]創(chuàng)建了一個(gè)額外的碼表對(duì)其進(jìn)行編碼；但是，這兩種方法的碼表都太大了。很顯然，改變編碼模型是解決問題的關(guān)鍵。因此，在彩色圖像的3D-DCT壓縮系統(tǒng)中，本文提出了基于（Run Level，Level）的統(tǒng)計(jì)性進(jìn)行熵編碼的改進(jìn)算法（IRL-EC）。該算法有許多優(yōu)點(diǎn)：易于理解、碼表開銷適中、編碼形式與RL-EC相似。另外，還根據(jù)掃描后非零系數(shù)分布的不均勻性，對(duì)不同區(qū)域的采用不同的編碼方法。

1　彩色圖像的3D-DCT壓縮系統(tǒng)介紹

1.1彩色圖像的三維建模和分塊

一幅大小為M×N的彩色圖像，它是由M×N大小的R、G、B三種顏色分量的灰度圖像組成，則彩色圖像的三維建模如圖1所示，沿著x軸的方向?yàn)楦叨染S，沿y軸方向?yàn)閷挾染S，沿z軸方向?yàn)閹S，則可以得到一個(gè)M×N×3的關(guān)于彩色圖像像素值的三維模型。類似于JPEG，為了減少計(jì)算量，提高編解碼速度，將M×N×3的三維模型統(tǒng)一分割為8×8×3的三維塊依次進(jìn)行3DDCT。

圖1　彩色圖像的三維建模和分塊

1.23D-DCT

M×N×3大小的彩色圖像三維塊的3D-DCT定義為：

相應(yīng)3D-IDCT為：

f（x，y，z）是變換前的第z個(gè)顏色分量幀內(nèi)的灰度值，x=0，1，…，M-1，y=0，1，…，N-1，z=0，1，2；

F（u，v，w）為相應(yīng)變換后的第w個(gè)DCT塊內(nèi)的系數(shù)，u=0，1，…，M-1，v=0，1，…，N-1，w=0，1，2。本文中M=N=8。

1.3量化和掃描

變換后主要能量都集中在低頻區(qū)域，且人眼對(duì)于高頻系數(shù)不敏感，定義三維量化矩陣如下：

其中:

i∈[0，M-1]，j∈[0，N-1]，k∈[0，2]。q是量化因子，改變q的值就得到不同的量化級(jí)數(shù)。量化值在低頻區(qū)域較小，隨著（i，j，k）的增加而增大。掃描采用將JPEG中ZigZag掃描擴(kuò)展到三維的方式。

2　熵編碼

和JEPG一樣，對(duì)DC系數(shù)的熵編碼，首先進(jìn)行無損預(yù)測(cè)編碼，然后進(jìn)行變長編碼。另外，如果當(dāng)前編碼塊左側(cè)或上面塊的直流系數(shù)為0，當(dāng)前塊的直流系數(shù)也很可能為0。由此，本文建立了兩種碼表，來基于上下文進(jìn)行自適應(yīng)編碼。

DC編碼格式：（Level）B（Amplitude）B

其中Level是DC系數(shù)的數(shù)量級(jí)，（Level）B是Level對(duì)應(yīng)的二進(jìn)制碼字，（Amplitude）B是DC的幅值對(duì)應(yīng)碼字，假設(shè)Level是l，幅值為A，當(dāng)A≥0時(shí)，碼字是A對(duì)應(yīng)二進(jìn)制值的最后l位；當(dāng)A＜0時(shí)，碼字是|A|-1對(duì)應(yīng)的二進(jìn)制值的后l位。

2.1IRL-EC

RL-EC和IRL-EC的游程編碼格式對(duì)比如下：

RL-EC：（Run，Level）

IRL-EC：（Run Level，Level）

其中，Run Level表示游程長度的數(shù)量級(jí)。

RL-EC和IRL-EC的熵編碼格式如下：

RL-EC：（Run，Level）B（Amplitude）B

IRL-EC：（Run Level，Level）B（Run Length）B（Amplitude）B

其中，（Run，Level）B和（Run Level，Level）B分別是（Run，Level）和（Run Level，Level）對(duì)應(yīng)的二進(jìn)制碼字，（Run Length）B是零游程長度對(duì)應(yīng)的碼字，假設(shè)Run Level是Rl，Run Length是A，當(dāng)Rl=0或者Rl=1時(shí)，就不需要將游程長度進(jìn)行熵編碼，因?yàn)榇藭r(shí)A=Rl；當(dāng)Rl＞1時(shí)，碼字是A-2Rl-1的二進(jìn)制值的后Rl-1位。一個(gè)8× 8×3三維子塊，Run Length的變化范圍是[0，191]，相應(yīng)Run Level的范圍是[0，8]，而較JPEG碼表，Run的變化范圍為[0，15]，可見本文方法的碼表小得多。

圖2為在量化因子q分別為15、25、35、45時(shí)，經(jīng)IRL-EC編碼所得的（Run Level，Level）數(shù)對(duì)的概率統(tǒng)計(jì)柱狀圖。可以看出無論量化級(jí)是多少，較短的Run和較小數(shù)量級(jí)的Level出現(xiàn)的頻率都更高，該統(tǒng)計(jì)特性和JPEG中RL-EC編碼是類似的，因此本文直接復(fù)用JPEG根據(jù)（Run Level，Level）聯(lián)合概率分布生成的碼表。

圖2　 不同量化級(jí)時(shí)的（Run Level,Level）概率分布圖

2.2碼長分析

根據(jù)游程編碼后（Run，Level）的統(tǒng)計(jì)規(guī)律，Run不變，隨著Level的增大，（Run，Level）出現(xiàn)的概率逐漸降低。假定同一Run，不同Level的（Run，Level）的概率為{Pn}，則（Run Level，Level）具有相似的統(tǒng)計(jì)規(guī)律，因此概率也為{Pn}。如果Run是l，Run Level是k，采用RL-EC的平均碼長（λl）和IRL-EC的的平均碼長（λk）定義如下：

表1　平均碼長對(duì)比

式中，Pn和λn分別是Level為n時(shí)，（l，n）數(shù)對(duì)出現(xiàn)的概率和對(duì)應(yīng)的二進(jìn)制碼長。

式中，Pn'和λn'分別是Level為n時(shí)，（k，n）數(shù)對(duì)出現(xiàn)的概率和對(duì)應(yīng)的二進(jìn)制碼長。

JPEG算法與IRL-EC算法的平均碼長對(duì)比結(jié)果如表1所示?？梢钥闯觯?dāng)游程長度大于4時(shí)，本文方法具有明顯優(yōu)勢(shì)。由于編碼后非零系數(shù)密集區(qū)的游程一般較短，疏散區(qū)的游程較長，因此可采用分段混合編碼的方法，對(duì)于密集區(qū)采用JPEG中的RL-EC編碼方法，疏散區(qū)采用本文提出的IRC-EC編碼方法。

將疏散區(qū)和密集區(qū)分割的位置定義為斷點(diǎn)，為了便于解碼，EOB即（0，0）被視為斷點(diǎn)的標(biāo)識(shí)，其表示一種熵編碼方法的結(jié)束和另一種熵編碼方法的開始。由于最佳斷點(diǎn)的選取不是本文的研究重點(diǎn)，本文斷點(diǎn)位置選取為第10個(gè)AC系數(shù)處，即前10個(gè)系數(shù)采用RLEC編碼，其余系數(shù)采用IRL-EC編碼。

3　仿真結(jié)果和分析

實(shí)驗(yàn)選取標(biāo)準(zhǔn)圖像數(shù)據(jù)庫中的彩色圖像，其大小為256×256，峰值信噪比（Peak Signal to Noise Ratio，PSNR）用來作為圖像質(zhì)量的客觀評(píng)價(jià)標(biāo)準(zhǔn)，使用壓縮比（Compression ratio，Cr）表示原圖像和壓縮后文件大小的比值。表2是本文方法和JPEG基線壓縮系統(tǒng)[7]對(duì)比結(jié)果。其中比特率的節(jié)省率Sr計(jì)算定義如下：

表2　本文方法和JPEG的圖像壓縮結(jié)果對(duì)比

其中Cr和Cr'分別表示采用JPEG和IRL-EC所得的壓縮比。

從表2中可以看出，PSNR越大，文中方法的優(yōu)點(diǎn)越明顯，這是因?yàn)榇藭r(shí)量化級(jí)較小，掃描系數(shù)中有較多的非零系數(shù)，長零游程出現(xiàn)的頻率更高。

4　結(jié)語

本文是3D-DCT在圖像壓縮領(lǐng)域的進(jìn)一步研究，基于掃描后系數(shù)中存在大量的長零游程這一特性，本文提出了一種改進(jìn)的熵編碼方法。當(dāng)前，3D TV和3D手機(jī)等技術(shù)的快速發(fā)展應(yīng)用，文中方法有廣闊的發(fā)展空間應(yīng)用于視頻圖像的多維變換壓縮系統(tǒng)中。

[1]Natarajan T，Ahmed N.On Interframe Transform Coding.IEEE Transactions on Communication，1977，25（11）:1323-1329.

[2]Tian D，Chen W H，Chang P S，et al.Hybrid Variable Length Coding for Image and Video Compression.IEEE International Conference on Acoustics，Speech and Signal Processing，2007:I-1133-I-1136

[3]Lakhani G.Optimal Huffman Coding of DCT Blocks.IEEE Transactions on Circuits and Systems for Video Technology，2004，14（4）: 522～527

[4]姜麗麗，趙德斌.基于復(fù)合上下文的自適應(yīng)熵編碼器設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用于軟件，2007，24（6）：98～100

[5]Fryza T.Properties of Entropy Coding for 3D DCT Video Compression Method.17th International Conference on Radioelektronika，2007:1～4

[6]鄒鑫馨.基于3D-DCT的視頻編碼實(shí)現(xiàn)[D].電子科技大學(xué)碩士學(xué)位論文，2009

[7]黎洪松.數(shù)字圖像壓縮編碼技術(shù)及其C語言程序范例[M].學(xué)苑出版社，1994

Run Length Coding;Entropy Coding;3D-DCT;Image Compression

Research on Entropy Coding of Three Dimensional DCT of Color Image

YANG Shu-yuan，JI Chao-feng
（College of Computer and Information Engineering，Xinjiang Agriculture University，Urumqi 830052）

In the compression system of three dimensional discrete cosine transform,there are lots of long zero run-lengths of alternating current coefficients,which are encoded by run length coding,traditional entropy coding method in JPEG based on the statistics of（Run,Level）is not suitable.By path of the study of distribution of AC,proposes the improved entropy coding algorithm based on jointly probability of（Run Level,Level）,the size of code table is moderate,code table in JPEG is multiplexed,and there is great potential in the higher dimensional transform compression field of video image in further.According to the non-uniformity of non-zero coefficient and the analysis of coding efficiency,the scattered and clustered areas of non-zero coefficients are coded with different methods.The experiment results show that,when the peak signal and noise ratio is the same,there is 11%code rate savings compared with the Baseline of JPEG standard.

1007-1423（2015）14-0062-05

10.3969/j.issn.1007-1423.2015.14.015

楊樹媛（1984-），女，甘肅白銀人，碩士研究生，講師，研究方向?yàn)槎嗝襟w信息處理、軟件開發(fā)

紀(jì)朝鳳（1985-），女，新疆塔城人，碩士研究生，講師，研究方向?yàn)殡娮有畔⒓夹g(shù)

2015-03-19

2015-04-29