一种降低外存访问带宽占有率的无损压缩算法

陈 晨,殷海兵

(中国计量学院 信息工程学院,浙江 杭州 310018)

一种降低外存访问带宽占有率的无损压缩算法

陈 晨,殷海兵

(中国计量学院 信息工程学院,浙江 杭州 310018)

高清、超高清视频编解码芯片结构设计中,原始图像帧和解码图像参考帧都存在外部存储器,外存访问带宽是系统设计的一大难题.通过图像压缩编码技术来降低图像冗余度,从而减小图像的存储容量和传输带宽.针对这一问题,提出了一种改进型无损图像压缩算法.与已有无损压缩算法相比,改进后算法以宏块为预测编码的基本单元,支持宏块随机访问;首先在预测部分加入块级预测与分层预测的自适应选择;然后在编码部分融入两种预测模式的半定长变长编码.实验结果表明，可降低带宽约50%.

降低外存带宽;块级预测;分层预测;半定长VLC编码

在高清视频编码器中,大量的原始图像和图像参考帧存储于外部存储器SDRAM,视频处理需要周期性地对外部存储器大量的数据进行存取操作,导致外部存储器的访存带宽非常大[1].因此降低外存访问带宽是视频编码器架构设计的一个重要挑战.然而,视频存在着很强的结构和统计上的冗余,根据这些冗余和人眼的视觉特性,可压缩视频以减少处理的数据量[2].许多无损图像压缩算法应运而生,主要包括两个方面:预测和熵编码.常用的无损压缩预测方法有:线性预测、边缘定向预测[3]、分层预测[4-7]等.线性预测是一种解相关固定高斯过程的有效工具,但它不能兼顾自然图像的突然变化;边缘定向和分层预测能够充分利用图像的相关性,而预测效率较低.常见的熵编码有:行程编码、霍夫曼编码[8-9]、算术编码等.行程编码技术相当直观,运算简单,可是对复杂的图像不仅不能压缩数据,反而会造成更大冗余;霍夫曼编码根据信号出现的概率构造出平均长度最短的码;算术编码比霍夫曼编码复杂得多,但是它不需要传送Huffman编码的码表,自适应能力强.

两种典型的无损图像压缩算法:JPEG-LS和CALIC. JPEG-LS把当前像素邻近的几个已编码像素,作为其上下文进行预测,得到预测残差,并对这些残差采用Golomb指数编码.该算法的优点在于:只用了上下文预测与Golomb指数编码,而没有用DCT变换和算术编码,算法简单,易于硬件实现;但是它的压缩率会低一些.CALIC采用GAP(梯度自适应预测器)对图像进行预测.根据预测邻域水平方向和垂直方向的局部梯度来判断图像是否存在边界以及边界的强弱,并根据计算的结果动态调整预测函数从而得到预测残差.对预测残差采用基于CACM++的自适应算术编码器进行编码.该算法首次提出了预测误差偏差消除思想来进一步提高编码效率;缺点是它是对整幅图像进行预测,预测效率较低.根据已有方法的互补特性,本文提出了一种支持随机访问的改进型综合算法,以宏块为单元对整幅图像进行压缩,支持宏块随机访问,当访问到任何一个宏块,硬件能将该宏块数据重建,也就意味着宏块之间相邻像素点的相关性无法使用,在宏块之间无数据依赖.该方法能够提高预测效率、降低外存访问带宽,把信息数据量降下来,以压缩形式存储、传输,既节约了存储空间,又提高了通信干线的传输效率,同时也可使计算机实时处理音频、视频信息.实验结果表明本文算法准确有效,大幅提高压缩比,具有一定的应用价值.

1 算法总体设计

本算法采用块级/分层自适应帧内预测、残差系统半定长变长编码(variable-length coding, VLC)、控制字段Huffman变长编码的多技术协作无损压缩系统方案;提出的自适应高效帧内预测,支持不同区域不同小块自适应编码,支持宏块级数据随机访问;并基于编码比特消耗最小化的原则,在预测效率和预测残差编码比特效率之间平衡.系统结构图如图1.

图1 系统结构图Figure 1 System structure diagram

2 帧内预测

2.1 块级预测

基于宏块内各相邻像素间的强相关性,将16×16大小的宏块分为如图2所示的小块.图2中第一个像素不做预测,其预测残差为零.第一行像素作水平方向预测,即当前像素左边相邻像素作为当前像素的参考预测.同理,第一列像素作垂直方向预测.其他15×15像素,分成5×5个大小为3×3的像素块,每个像素块支持块间预测和像素级预测两种预测模式.块间预测是利用相邻块间的相关性预测,像素级预测是利用块内相邻像素间的强相关性预测,它们都支持水平和垂直两个方向,通过比较两种方向预测得到的残差绝对值,选择绝对值小者为最佳预测方向.计算块间和像素级两种预测模式的残差,采用VLC编码,统计块编码比特数,选择较小编码代价的模式,从而确定块级预测类型.

图2 宏块的分块模式Figure 2 Block partition in one macroblock

2.2 分层预测

帧内预测中另一重要模块—分层预测,文献[4]给出具体分层结构图,明确阐述宏块间分层、预测的方法.本设计中分层预测将16×16大小的宏块通过两次降采样后得到3层不同像素间隔的块.第三层由第二次降采样所得,由4个像素间隔组成的4个2×2小块,分别对这些小块求均值,将其作为小块中每一个像素的值,从而得到第三层4×2×2像素(16系数)预测.第二层由第一次降采样所得,是2个像素间隔组成的3个4×4小块,再把4×4小块分割成2×2块,参考第三层像素,对本层像素作复制和平均预测,得到第二层3×4×4像素(48系数)预测.同理,第一层参考其他两层像素,得到3×8×8像素(192系数)预测.

2.3 预测自适应选择

对于块级预测和分层预测的选择,每一宏块利用1比特控制信息pred_type标志优先选择预测模式,图像解码时根据pred_type判断编码时的预测模式准确解码.每个宏块根据残差编码比特和控制信息比特,优先选择预测效率高者为最优预测模式.预测效率由熵可得,熵的方程式(1)给出,根据公式(1)比较熵值小者为最优模式.熵值越小,误差内所含的信息量越少,压缩的冗余越多,说明预测效率越高.pred_type=0表示优先选择的是块级预测,pred_type=1表示优先选择的是分层预测.

H=-∑pi·log(pi)

(1)

式(1)中:pi—通常是图像中一组不同灰度级的像素或一组不同的预测残差所占的比重.

3 半定长VLC编码

以块级预测为例,对于预测残差,采用基于小块半定长VLC编码.统计块级预测残差值的最大值和最小值确定残差的动态范围mm,将整个动态范围自适应划分为8个变长的编码区域,这8个区域用控制字段M(mode)标识.为了降低M字段编码比特,采用Huffman编码[9]方法.块级预测中第一行和第一列共有31个像素,称这一动态范围为31系数,剩余的为225系数,统计这两种系数的M取值,用直方图绘制出来.根据大量M值的概率分布,得到M取0～7时可变长码表,实际数据流图如图3.图4给出某一序列Night_1 920×1 080的M分布直方图,其中(a)为225系数M分布图,(b)为31系数M分布图.同理在分层预测中,根据每层预测像素的个数,将动态范围分别定义为第三层的16系数、第二层的48系数和第一层的192系数,根据大量序列16系数、48系数和192系数的统计信息及各M字段所占的比例,可以得到分层预测M字段的Huffman码表.

图3 实际数据流图Figure 3 Actual data flow diagram

图4 225系数和31系数的统计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)为每个像素经半定长VLC编码后的比特消耗,(d)为每个宏块经半定长VLC编码后的比特消耗.通过分析比较部分测试结果如表1所示,给出了9个视频序列经过三种算法编码前后每个宏块的带宽比特数,实验数据表明本算法不仅在编码后每个宏块带宽比特数相对JPEG-LS和CALIC两种经典算法都有所减少,而且发现每个宏块编码后平均比特数是编码前的50%左右,说明本算法可降低外存带宽约一半,达到预期要求.

5 结 语

针对高质量网络视频传输的应用需求,本文提出了一种能够提高压缩技术的无损图像压缩算法.该算法相对于已有算法而言,既能够提高预测效率、降低带宽比特数,又弥补了只能对整幅图像进行处理的缺陷.帧内预测中充分结合块级预测和分层预测的优点.块级预测只利用到当前像素左、上像素的相关性,但其周边像素无法运用到;而分层预测可以实现对图像中更多相邻像素的参考.熵编码部分,统计出两种预测模式的半定长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] 殷海兵,夏哲雷,方向忠.数字媒体处理技术与应用[M].北京:电子工业出版社,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 《中国计量学院学报》网址：zgjl.cbpt.cnki.net

浙江省自然科学基金资助项目(No.Y1110114).

TN919.8

A