陳 晨,殷海兵

(中國計量學院 信息工程學院,浙江 杭州 310018)

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

陳 晨,殷海兵

(中國計量學院 信息工程學院,浙江 杭州 310018)

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

降低外存帶寬;塊級預測;分層預測;半定長VLC編碼

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

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

1 算法總體設計

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

圖1 系統(tǒng)結構圖Figure 1 System structure diagram

2 幀內預測

2.1 塊級預測

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

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

2.2 分層預測

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

2.3 預測自適應選擇

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

H=-∑pi·log(pi)

(1)

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

3 半定長VLC編碼

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

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

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

4 實驗結果與分析

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

5 結 語

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

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

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

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

[2] 高新波,路文.視覺信息質量評價方法[M].西安:西安電子科技大學出版社,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在圖像處理中的應用[M].北京:清華大學出版社,2008:219-222.

[9] 殷海兵,夏哲雷,方向忠.數(shù)字媒體處理技術與應用[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 《中國計量學院學報》網(wǎng)址：zgjl.cbpt.cnki.net

浙江省自然科學基金資助項目(No.Y1110114).

TN919.8

A