一種降低外存訪問帶寬占有率的無損壓縮算法

陳 晨,殷海兵

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

一種降低外存訪問帶寬占有率的無損壓縮算法

陳 晨,殷海兵

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

高清、超高清視頻編解碼芯片結(jié)構(gòu)設(shè)計(jì)中,原始圖像幀和解碼圖像參考幀都存在外部存儲(chǔ)器,外存訪問帶寬是系統(tǒng)設(shè)計(jì)的一大難題.通過圖像壓縮編碼技術(shù)來降低圖像冗余度,從而減小圖像的存儲(chǔ)容量和傳輸帶寬.針對(duì)這一問題,提出了一種改進(jìn)型無損圖像壓縮算法.與已有無損壓縮算法相比,改進(jìn)后算法以宏塊為預(yù)測(cè)編碼的基本單元,支持宏塊隨機(jī)訪問;首先在預(yù)測(cè)部分加入塊級(jí)預(yù)測(cè)與分層預(yù)測(cè)的自適應(yīng)選擇;然后在編碼部分融入兩種預(yù)測(cè)模式的半定長(zhǎng)變長(zhǎng)編碼.實(shí)驗(yàn)結(jié)果表明，可降低帶寬約50%.

降低外存帶寬;塊級(jí)預(yù)測(cè);分層預(yù)測(cè);半定長(zhǎng)VLC編碼

在高清視頻編碼器中,大量的原始圖像和圖像參考幀存儲(chǔ)于外部存儲(chǔ)器SDRAM,視頻處理需要周期性地對(duì)外部存儲(chǔ)器大量的數(shù)據(jù)進(jìn)行存取操作,導(dǎo)致外部存儲(chǔ)器的訪存帶寬非常大[1].因此降低外存訪問帶寬是視頻編碼器架構(gòu)設(shè)計(jì)的一個(gè)重要挑戰(zhàn).然而,視頻存在著很強(qiáng)的結(jié)構(gòu)和統(tǒng)計(jì)上的冗余,根據(jù)這些冗余和人眼的視覺特性,可壓縮視頻以減少處理的數(shù)據(jù)量[2].許多無損圖像壓縮算法應(yīng)運(yùn)而生,主要包括兩個(gè)方面:預(yù)測(cè)和熵編碼.常用的無損壓縮預(yù)測(cè)方法有:線性預(yù)測(cè)、邊緣定向預(yù)測(cè)[3]、分層預(yù)測(cè)[4-7]等.線性預(yù)測(cè)是一種解相關(guān)固定高斯過程的有效工具,但它不能兼顧自然圖像的突然變化;邊緣定向和分層預(yù)測(cè)能夠充分利用圖像的相關(guān)性,而預(yù)測(cè)效率較低.常見的熵編碼有:行程編碼、霍夫曼編碼[8-9]、算術(shù)編碼等.行程編碼技術(shù)相當(dāng)直觀,運(yùn)算簡(jiǎn)單,可是對(duì)復(fù)雜的圖像不僅不能壓縮數(shù)據(jù),反而會(huì)造成更大冗余;霍夫曼編碼根據(jù)信號(hào)出現(xiàn)的概率構(gòu)造出平均長(zhǎng)度最短的碼;算術(shù)編碼比霍夫曼編碼復(fù)雜得多,但是它不需要傳送Huffman編碼的碼表,自適應(yīng)能力強(qiáng).

兩種典型的無損圖像壓縮算法:JPEG-LS和CALIC. JPEG-LS把當(dāng)前像素鄰近的幾個(gè)已編碼像素,作為其上下文進(jìn)行預(yù)測(cè),得到預(yù)測(cè)殘差,并對(duì)這些殘差采用Golomb指數(shù)編碼.該算法的優(yōu)點(diǎn)在于:只用了上下文預(yù)測(cè)與Golomb指數(shù)編碼,而沒有用DCT變換和算術(shù)編碼,算法簡(jiǎn)單,易于硬件實(shí)現(xiàn);但是它的壓縮率會(huì)低一些.CALIC采用GAP(梯度自適應(yīng)預(yù)測(cè)器)對(duì)圖像進(jìn)行預(yù)測(cè).根據(jù)預(yù)測(cè)鄰域水平方向和垂直方向的局部梯度來判斷圖像是否存在邊界以及邊界的強(qiáng)弱,并根據(jù)計(jì)算的結(jié)果動(dòng)態(tài)調(diào)整預(yù)測(cè)函數(shù)從而得到預(yù)測(cè)殘差.對(duì)預(yù)測(cè)殘差采用基于CACM++的自適應(yīng)算術(shù)編碼器進(jìn)行編碼.該算法首次提出了預(yù)測(cè)誤差偏差消除思想來進(jìn)一步提高編碼效率;缺點(diǎn)是它是對(duì)整幅圖像進(jìn)行預(yù)測(cè),預(yù)測(cè)效率較低.根據(jù)已有方法的互補(bǔ)特性,本文提出了一種支持隨機(jī)訪問的改進(jìn)型綜合算法,以宏塊為單元對(duì)整幅圖像進(jìn)行壓縮,支持宏塊隨機(jī)訪問,當(dāng)訪問到任何一個(gè)宏塊,硬件能將該宏塊數(shù)據(jù)重建,也就意味著宏塊之間相鄰像素點(diǎn)的相關(guān)性無法使用,在宏塊之間無數(shù)據(jù)依賴.該方法能夠提高預(yù)測(cè)效率、降低外存訪問帶寬,把信息數(shù)據(jù)量降下來,以壓縮形式存儲(chǔ)、傳輸,既節(jié)約了存儲(chǔ)空間,又提高了通信干線的傳輸效率,同時(shí)也可使計(jì)算機(jī)實(shí)時(shí)處理音頻、視頻信息.實(shí)驗(yàn)結(jié)果表明本文算法準(zhǔn)確有效,大幅提高壓縮比,具有一定的應(yīng)用價(jià)值.

1 算法總體設(shè)計(jì)

本算法采用塊級(jí)/分層自適應(yīng)幀內(nèi)預(yù)測(cè)、殘差系統(tǒng)半定長(zhǎng)變長(zhǎng)編碼(variable-length coding, VLC)、控制字段Huffman變長(zhǎng)編碼的多技術(shù)協(xié)作無損壓縮系統(tǒng)方案;提出的自適應(yīng)高效幀內(nèi)預(yù)測(cè),支持不同區(qū)域不同小塊自適應(yīng)編碼,支持宏塊級(jí)數(shù)據(jù)隨機(jī)訪問;并基于編碼比特消耗最小化的原則,在預(yù)測(cè)效率和預(yù)測(cè)殘差編碼比特效率之間平衡.系統(tǒng)結(jié)構(gòu)圖如圖1.

圖1 系統(tǒng)結(jié)構(gòu)圖Figure 1 System structure diagram

2 幀內(nèi)預(yù)測(cè)

2.1 塊級(jí)預(yù)測(cè)

基于宏塊內(nèi)各相鄰像素間的強(qiáng)相關(guān)性,將16×16大小的宏塊分為如圖2所示的小塊.圖2中第一個(gè)像素不做預(yù)測(cè),其預(yù)測(cè)殘差為零.第一行像素作水平方向預(yù)測(cè),即當(dāng)前像素左邊相鄰像素作為當(dāng)前像素的參考預(yù)測(cè).同理,第一列像素作垂直方向預(yù)測(cè).其他15×15像素,分成5×5個(gè)大小為3×3的像素塊,每個(gè)像素塊支持塊間預(yù)測(cè)和像素級(jí)預(yù)測(cè)兩種預(yù)測(cè)模式.塊間預(yù)測(cè)是利用相鄰塊間的相關(guān)性預(yù)測(cè),像素級(jí)預(yù)測(cè)是利用塊內(nèi)相鄰像素間的強(qiáng)相關(guān)性預(yù)測(cè),它們都支持水平和垂直兩個(gè)方向,通過比較兩種方向預(yù)測(cè)得到的殘差絕對(duì)值,選擇絕對(duì)值小者為最佳預(yù)測(cè)方向.計(jì)算塊間和像素級(jí)兩種預(yù)測(cè)模式的殘差,采用VLC編碼,統(tǒng)計(jì)塊編碼比特?cái)?shù),選擇較小編碼代價(jià)的模式,從而確定塊級(jí)預(yù)測(cè)類型.

圖2 宏塊的分塊模式Figure 2 Block partition in one macroblock

2.2 分層預(yù)測(cè)

幀內(nèi)預(yù)測(cè)中另一重要模塊—分層預(yù)測(cè),文獻(xiàn)[4]給出具體分層結(jié)構(gòu)圖,明確闡述宏塊間分層、預(yù)測(cè)的方法.本設(shè)計(jì)中分層預(yù)測(cè)將16×16大小的宏塊通過兩次降采樣后得到3層不同像素間隔的塊.第三層由第二次降采樣所得,由4個(gè)像素間隔組成的4個(gè)2×2小塊,分別對(duì)這些小塊求均值,將其作為小塊中每一個(gè)像素的值,從而得到第三層4×2×2像素(16系數(shù))預(yù)測(cè).第二層由第一次降采樣所得,是2個(gè)像素間隔組成的3個(gè)4×4小塊,再把4×4小塊分割成2×2塊,參考第三層像素,對(duì)本層像素作復(fù)制和平均預(yù)測(cè),得到第二層3×4×4像素(48系數(shù))預(yù)測(cè).同理,第一層參考其他兩層像素,得到3×8×8像素(192系數(shù))預(yù)測(cè).

2.3 預(yù)測(cè)自適應(yīng)選擇

對(duì)于塊級(jí)預(yù)測(cè)和分層預(yù)測(cè)的選擇,每一宏塊利用1比特控制信息pred_type標(biāo)志優(yōu)先選擇預(yù)測(cè)模式,圖像解碼時(shí)根據(jù)pred_type判斷編碼時(shí)的預(yù)測(cè)模式準(zhǔn)確解碼.每個(gè)宏塊根據(jù)殘差編碼比特和控制信息比特,優(yōu)先選擇預(yù)測(cè)效率高者為最優(yōu)預(yù)測(cè)模式.預(yù)測(cè)效率由熵可得,熵的方程式(1)給出,根據(jù)公式(1)比較熵值小者為最優(yōu)模式.熵值越小,誤差內(nèi)所含的信息量越少,壓縮的冗余越多,說明預(yù)測(cè)效率越高.pred_type=0表示優(yōu)先選擇的是塊級(jí)預(yù)測(cè),pred_type=1表示優(yōu)先選擇的是分層預(yù)測(cè).

H=-∑pi·log(pi)

(1)

式(1)中:pi—通常是圖像中一組不同灰度級(jí)的像素或一組不同的預(yù)測(cè)殘差所占的比重.

3 半定長(zhǎng)VLC編碼

以塊級(jí)預(yù)測(cè)為例,對(duì)于預(yù)測(cè)殘差,采用基于小塊半定長(zhǎng)VLC編碼.統(tǒng)計(jì)塊級(jí)預(yù)測(cè)殘差值的最大值和最小值確定殘差的動(dòng)態(tài)范圍mm,將整個(gè)動(dòng)態(tài)范圍自適應(yīng)劃分為8個(gè)變長(zhǎng)的編碼區(qū)域,這8個(gè)區(qū)域用控制字段M(mode)標(biāo)識(shí).為了降低M字段編碼比特,采用Huffman編碼[9]方法.塊級(jí)預(yù)測(cè)中第一行和第一列共有31個(gè)像素,稱這一動(dòng)態(tài)范圍為31系數(shù),剩余的為225系數(shù),統(tǒng)計(jì)這兩種系數(shù)的M取值,用直方圖繪制出來.根據(jù)大量M值的概率分布,得到M取0～7時(shí)可變長(zhǎng)碼表,實(shí)際數(shù)據(jù)流圖如圖3.圖4給出某一序列Night_1 920×1 080的M分布直方圖,其中(a)為225系數(shù)M分布圖,(b)為31系數(shù)M分布圖.同理在分層預(yù)測(cè)中,根據(jù)每層預(yù)測(cè)像素的個(gè)數(shù),將動(dòng)態(tài)范圍分別定義為第三層的16系數(shù)、第二層的48系數(shù)和第一層的192系數(shù),根據(jù)大量序列16系數(shù)、48系數(shù)和192系數(shù)的統(tǒng)計(jì)信息及各M字段所占的比例,可以得到分層預(yù)測(cè)M字段的Huffman碼表.

圖3 實(shí)際數(shù)據(jù)流圖Figure 3 Actual data flow diagram

圖4 225系數(shù)和31系數(shù)的統(tǒng)計(jì)Figure 4 A total of 225 coefficients and 31 coefficients statistics

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提算法的壓縮效果,測(cè)試大量高清視頻(分辨率為1 920×1 080),序列在預(yù)測(cè)部分自適應(yīng)選擇最佳預(yù)測(cè)方式,然后給出與之相對(duì)應(yīng)的編碼方法.以Night_1 920×1 080為例,圖5所示該視頻序列的仿真結(jié)果.其中,(a)為Night_1 920×1 080的二值圖,(b)為自適應(yīng)預(yù)測(cè)后的預(yù)測(cè)殘差圖,(c)為每個(gè)像素經(jīng)半定長(zhǎng)VLC編碼后的比特消耗,(d)為每個(gè)宏塊經(jīng)半定長(zhǎng)VLC編碼后的比特消耗.通過分析比較部分測(cè)試結(jié)果如表1所示,給出了9個(gè)視頻序列經(jīng)過三種算法編碼前后每個(gè)宏塊的帶寬比特?cái)?shù),實(shí)驗(yàn)數(shù)據(jù)表明本算法不僅在編碼后每個(gè)宏塊帶寬比特?cái)?shù)相對(duì)JPEG-LS和CALIC兩種經(jīng)典算法都有所減少,而且發(fā)現(xiàn)每個(gè)宏塊編碼后平均比特?cái)?shù)是編碼前的50%左右,說明本算法可降低外存帶寬約一半,達(dá)到預(yù)期要求.

5 結(jié) 語

針對(duì)高質(zhì)量網(wǎng)絡(luò)視頻傳輸?shù)膽?yīng)用需求,本文提出了一種能夠提高壓縮技術(shù)的無損圖像壓縮算法.該算法相對(duì)于已有算法而言,既能夠提高預(yù)測(cè)效率、降低帶寬比特?cái)?shù),又彌補(bǔ)了只能對(duì)整幅圖像進(jìn)行處理的缺陷.幀內(nèi)預(yù)測(cè)中充分結(jié)合塊級(jí)預(yù)測(cè)和分層預(yù)測(cè)的優(yōu)點(diǎn).塊級(jí)預(yù)測(cè)只利用到當(dāng)前像素左、上像素的相關(guān)性,但其周邊像素?zé)o法運(yùn)用到;而分層預(yù)測(cè)可以實(shí)現(xiàn)對(duì)圖像中更多相鄰像素的參考.熵編碼部分,統(tǒng)計(jì)出兩種預(yù)測(cè)模式的半定長(zhǎng)VLC編碼,與自適應(yīng)選擇的預(yù)測(cè)模式相匹配.三種算法的外存訪問帶寬進(jìn)行壓縮編碼前后的對(duì)比,形象說明了改進(jìn)算法所達(dá)到的降低帶寬約50%的目標(biāo).但是,本文考慮也有不足,如分層預(yù)測(cè)參考的像素間隔太大,相關(guān)性就會(huì)減小,每層的編碼方法也會(huì)有差異[10-11],這些都是下一階段的研究方向.

圖5 Night_1 920×1 080的仿真結(jié)果Figure 5 Simulation results of Night_1 920×1 080

視頻序列123456789編碼前每個(gè)宏塊帶寬/bit204820482048204820482048204820482048JPEG-LS/bit10991290126512501200983110912011196CALIC/bit10831206125912061151988106511531158本算法/bit10391183106011371119950103511011123帶寬降低率/%50.7357.7651.8055.4254.6446.3750.5353.7654.83

[1] 畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)—H.264/AVC[M].北京:人民郵電出版社,2005:3-6.

[2] 高新波,路文.視覺信息質(zhì)量評(píng)價(jià)方法[M].西安:西安電子科技大學(xué)出版社,2010:10-30.

[3] XIN Li, MICHAEL T O.Edge-Directed prediction for lossless compression of natural images[J]. IEEE Transactions on Image Processing,2001,10(6):813-815.

[4] KIM J, KYUNG C M. A lossless embedded compression using significant bit truncation for HD video coding[J]. IEEE Transactions on Circuit and Systems for Video Technology,2010,20(6):848-849.

[5] OKANO F, KANAZAWA M, HAMASAKI K, et al. Ultradefinition television system with 4000 scanning lines[R].London,U K:Broadcasters Broadcast,2004.

[6] WEINBERGER M, SEROUSSI G, SAPIRO G. The LOCO-I lossless image compression algorithm :principles and standardization into JPEG-LS[J].IEEE Transaction Image Processing,2000,8(9):130-153.

[7] TUAN J C, CHANG T S, JEN C W. On the data reuse and memory bandwidth analysis for full-search block-matching VLSI architecture[J].IEEE Transactions Circuits Systems Video Technology,2002,12(1):61-72.

[8] 張汗靈.MATLAB在圖像處理中的應(yīng)用[M].北京:清華大學(xué)出版社,2008:219-222.

[9] 殷海兵,夏哲雷,方向忠.數(shù)字媒體處理技術(shù)與應(yīng)用[M].北京:電子工業(yè)出版社,2011:68-73.

[10] MERHAV N, SEROUSSI G, WEINBERGER M.Optimal prefix codes for sources with two-sided geometric distributions[J]. IEEE Transaction Image Processing,2000,46(1):121-135.

[11] NIKARA J, VASSILIADIS S, TAKALA J, et al. Multiple-symbol parallel decoding for variable length codes[J]. IEEE Transactions Very-Large-Scale Integration Systems,2004,12(7):676-685.

A lossless compression algorithm to reduce the possession rate of external memory access bandwidth

CHEN Chen, YIN Haibing

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

In HD and Ultra HD video decode chip design, the original image and the decoded image reference frames are stored in the external memory. The external memory access bandwidth is the major problem in the system design. The image compression technology can be used to reduce image redundancy to compress the saving size. We proposed an improved lossless image compression algorithm. The predictive coding unit of the algorithm was macrolock supporting random access. The adaptive choice of hierarchical and block-level prediction was added to the forecast section; and a hierarchical half-length VLC coding was added to the coding part. The bandwidth can reduce about 50%.

external memory bandwidth reducetion; block-level prediction; hierarchical prediction; half-length VLC coding

1004-1540(2015)01-0123-06

10.3969/j.issn.1004-1540.2015.01.022

2014-10-10 《中國(guó)計(jì)量學(xué)院學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

浙江省自然科學(xué)基金資助項(xiàng)目(No.Y1110114).

TN919.8

A