基于FPGA的无损图像压缩算法实现

范文晶，王召利，王惠娟，费聚锋，李萧萧

(1.上海机电工程研究所 6室，上海 201109；2. 上海无线电设备研究所，上海 200090)



基于FPGA的无损图像压缩算法实现

范文晶1，王召利2，王惠娟1，费聚锋2，李萧萧1

(1.上海机电工程研究所 6室，上海 201109；2. 上海无线电设备研究所，上海 200090)

针对采用传统硬件方法实现JPEG-LS无损图像压缩算法时延时较多、实时性较差的问题，文中提出了一种基于FPGA的全流水线结构来实现JPEG-LS算法。该结构以提高最大吞吐量为主要目标，通过多级流水线降低每一级运算的延迟，大幅提高了压缩算法的实时性，硬件电路操作频率可达120MHz。

全流水线；无损图像压缩；大吞吐量；FPGA

传统硬件方法在实现JPEG-LS无损图像压缩算法时延时较多、实时性差，为满足高速图像传感器系统的吞吐量需求[1-2]，选用FPGA来实现无损图像压缩算法，以提高最大吞吐量为主要目标，通过全流水线降低每一级运算的延迟，从而满足严格的时序约束，大幅提高了压缩算法的实时性。

1 无损压缩算法

JPEG-LS无损压缩算法的基本思想为[3-5]：由当前像素的几个已经出现过的近邻，用其作为当前像素的上下文，用上下文来预测误差，从几个这样的概率分布中选择一个，并根据该分布用一个特殊的Golomb码字来编码预测误差。JPEG-LS图像压缩标准规定的无损和近无损编码处理的主要组成部分如图1所示。

图1 JPEG-LS编码器模型

JPEG-LS图像压缩标准采用差分预测编码技术，同时建立了匹配上下文模型，高效地实现了One-pass编码器[6～7]，具体算法实现过程如图2所示。

图2 JPEG-LS 压缩算法框图

该编码器基于光栅扫描顺序，每次对一个像素进行编码。具体的编码方式分为两种，即正常模式和游长模式，且这两种模式之间是自适应切换的[8-10]。

在正常编码模式下，首先采用简单的边缘检测器初步确定一个预测值[11-12]；然后再与上下文自适应的预测校正值相结合得到校正预测值；最后使用当前待编码原始像素值减去校正预测值就能得到预测残差，该预测残差的分布满足双边几何分布，利用上下文模型可求得预测残差的编码参数k，熵编码器采用参数k完成Golomb快速一元编码[13-15]。当编码器进入游长编码模式时，完成游长计数后，熵编码器采用效率更高的游长编码，从而对平滑图像可进行大倍率的压缩[16]。

2 JPEG-LS无损压缩算法的FPGA实现

采用标准JPEG-LS算法进行无损压缩硬件实现时存在一些不足：

(1)在计算上下文Q时，需要多步串行计算才能得到Q值，关键路径较长，难以满足实时处理的要求；

(2)在计算误差以及误差量化时，采用标准算法时用到浮点乘法，计算精度不能保证，计算复杂度较高，难以满足快速处理的要求；

(3)参数变量更新时，标准算法涉及较多的加减运算和逻辑判断，且诸多操作是串行运算，计算复杂度较高，影响了整个系统运行速度的提升。

JPEG-LS算法包括较多顺序运算步骤，如果直接按照算法实现为硬件逻辑，将会产生较大的延迟时间，严重阻碍时钟频率的提高。

针对以上问题，本文提出的JPEG-LS实现结构以提高最大吞吐量为主要目标，通过多级流水线降低每一级运算的延迟，从而满足更严格的时序约束。除流水线机制外，通过在较细的粒度上实现运算的并行，提高了每一级运算的速度。

2.1 并行运算降低硬件资源消耗

设计采用FPGA片内的Block Ram或Rom资源以存储计算所得的变量值，在JPEG-LS标准中，计算量化梯度合并时，若矢量(Q1,Q2,Q3)的第一个非零元素是一个负数，则必须将该矢量的符合反转得到(-Q1,-Q2,-Q3)，此时变量SIGN被设置为-1，反之为+1；在这种可能的合并之后，矢量(Q1,Q2,Q3)以一对一的方式被映射到一个整数Q，其表示采样X的上下文。

然而在JPEG-LS标准中并没有规定此映射过程的具体函数，为了能简单实现查找A[Q]、B[Q]、C[Q]、N[Q]表值，将Qi做了优化修改，根据输入的Ra、Rb、Rc、Rd分别计算Rd-Rb、Rb-Rc和Rc-Ra，根据JPEG-LS标准，以这3个梯度值为索引，查表得到3个梯度的量化梯度值id1、id2、id3，在FPGA中使用量化公式

Q=id1×92+id2×9+id3

(1)

映射后可通过Q值判断SIGN值，若Q>0，则SIGN为1，若Q<0，则SIGN为-1；变量Q则成为索引A[Q]、B[Q]、C[Q]、N[Q]的地址值，此次优化降低了算法复杂度，提高了效率。在计算得到预测值,根据预测值通过量化后得到误差值以及量化误差值的过程如下

if(Errval)>0

Errval=(Errval+NEAR)/(2*NEAR+1)

else

Errval=-(Errval-NEAR)/(2*NEAR+1)

(2)

此过程实现较为复杂，且周期较长，使得整个过程实时性降低。针对此处计算，设计查询表的方式替代原浮点乘法运算，由于误差Errval的范围在-255～+256之间，所以将Errval之间的值通过上述方法提前算好建立一张Table表存储在FPGA内部资源ROM中，每次只需以误差值为地址去ROM中查找对应的量化误差值即可。通过以上方法，将复杂的算法以及耗时的计算变为了一次查表就能完成，大幅降低了计算量，提高了实时性。

对某一像素 编码的最后一步是更新变量A[Q]、B[Q]、C[Q]、N[Q]，但该变量更新处理必须在编码过程的最后。为提高编码实时性，使变量的更新周期减少，设计了一种新的变量更新方式，如图3所示。

图3 变量更新结构图

根据以上变量更新的方法，得到一组新的A[Q]、B[Q]、C[Q]、N[Q]值，并且将其分别存储在FPGA内存双口RAM中，在下一次计算来临时可根据当前计算得到的Q值作为地址，从4个双口RAM中读取上一次更新的A[Q]、B[Q]、C[Q]、N[Q]值，再通过变量更新模块获得新的更新值存入RAM中。

2.2 算法流水线结构

为提高硬件平台操作速率以及考虑到系统的实时性，选用流水线结构是实现此算法的必要途径，如图4所示。为了完全实现此流水线结构，使用了10个时钟周期的流水线阶段。为避免结构图过于复杂，此处仅是正常模式下的流水线结构图，并未给出游程模式结构图。运用此流水线模式可使得硬件电路操作频率达到120 MHz。

图4 JPEG-LS流水线硬件结构图

如图4所示，10个流水线阶段分别完成以下步骤：

阶段1 完成预测值计算以及局部梯度值计算；

阶段2 局部梯度值量化；

阶段3 查询变量Q地址；

阶段4 读取环境变量(上下文)值；

阶段5 更新环境变量值；

阶段6～8 3个周期除法器；

阶段9 以及预测误差值计算；

阶段10 误差映射及产生bit流输出。

在FPGA中利用流水线的方式来实现算法，各模块的计算复杂度基本相同，且几个模块可同时进行计算，减少了每一级的运算时间，提高了系统实时性。

图5 常规编码和带有前向预判机制的上下文参数更新时序图

3 实验及结果

为完成整个编码系统，包括预测器和熵编码器两部分功能，选用Altera公司Stratix 系列FPGA，在Quartus软件环境下使用Verilog HDL语言进行编程实现。将传统硬件实现方法和前流水线的JPEG-LS硬件实现的内存消耗、消耗逻辑门单元和硬件操作频率做对比，对比结果如表1所示。

表1 传统硬件方法实现JPEG-LS和全流水线的JPEG-LS硬件实现比较

由表1可知，采用了全流水线结构来实现JPEG-LS算法，大幅降低了FPGA内存空间占用，内存空间占用被降低了26%。该流水线模式也使得硬件电路操作频率由105 MHz提高到120 MHz，满足严格的时序约束，且提高了压缩算法的实时性。

4 结束语

为满足高速图像传感器系统的吞吐量需求，本文在FPGA中采用全流水线结构，降低了每一级运算的延迟，实现了JPEG-LS无损/近无损图像压缩算法。该算法已在FPGA平台通过验证，实现了大吞吐量的无损图像压缩，可应用于高速图像传输系统中。

[1] 沈洪亮,刘金国.基于JPEG-LS的遥感图像无损压缩技术[J].光电子技术,2009,29(3):206-210.

[2] Marcelo Weinberger, Gadiel Seroussi, Guillermo Sapiro. The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS[J].IEEE Transations on Image Proceeding,2000, 9(8):1310-1322.

[3] 唐垚,曹剑中,李变侠,等.基于FPGA的JPEG-LS无损压缩算法的实现[J].弹箭与制导学报,2006,26(SA):1219-1222.

[4] 刘嘉晗,赵岩,王宇心,等.高性能全流水线可控参数JPEG-LS 编码器实现[J].微电子学与计算机,2010,27(2):34-37.

[5] BeDi S,Edris E.Improvement to the JPEG-LS pre diction scheme[J].Elsevier on Image Vision Computing,2004,22(1):9-14.

[6] Merlino P, Abramo A.A fully pipeline architecture for the LOCOI compression algorithm[J].IEEE Transactions on Very Large Scale Integration (VLSI),2009,17(7):967-971.

[7] 李晓雯,陈新凯,李国林,等.低功耗全流水线JPEG-LS无损图像编码器的VLSI设计[J].清华大学学报:自然科学版,2007,47(10):1654-1658.

[8] 张毅.码率可控的JPEG-LS近无损图像压缩编码器硬件实现[D].西安:西安电子科技大学,2014.

[9] 郝勇峥.基于JPEG-LS算法的星载图像压缩系统设计[D].西安:西安电子科技大学,2011.

[10] 徐燕凌,刘蓓.JPEG-LS图像压缩动态码率控制策略[J].计算机工程,2008,34(7):238-239,271.

[11] 崔倩.JPEG-LS码率控制算法研究[D].西安:西安电子科技大学,2011.

[12] 张芝贤,王玉周,刘筠筠.基于DSP的图像采集及JPEG-LS压缩系统[J].微计算机信息,2009,25(29):139-140,190.

[13] 杨武,董世都,张光建.一种基于小波系数上下文模型的图像压缩方法[J].微电子学与计算机,2006,23(4):153-155,159.

[14] 刘强,彭玉涛.基于流水线技术的无损JPEG-LS编码器实现新方法[J].科技信息,2011(35):120-121,134.

[15] 曹青,吴乐南.静止图像无失真编码的新标准JPEG-LS[J].电子工程师,1999(2):12-14.

[16] 王黎明,赵英亮,韩焱,等.基于JPEG-LS框架的无损压缩技术研究[J].电脑开发与应用,2002,15(4):6-7.

Implementation of Lossless Image Compression Algorithm Based on FPGA

FAN Wenjing1, WANG Zhaoli2, WANG Huijuan1, FEI Jufeng2, LI Xiaoxiao1

(1. Room 6, Shanghai Electro-Mechanical Engineering Institute, Shanghai 201109, China;2. Shanghai Wireless Equipment Institute, Shanghai 200090, China)

The traditional hardware implementation of JPEG-LS lossless image compression algorithm suffers poor real-time performance. This paper presents a fully-pipelined structure based on FPGA to achieve the JPEG-LS algorithm. The structure reduces the delay of every step through Multi-stage pipeline to improve maximum throughput as well as the real-time of the compression algorithm, making hardware circuit operating frequencies up to 120 MHz.

fully-pipeline; lossless image compression; high-throughput; FPGA

2016- 01- 23

范文晶(1985-)，男，硕士，工程师。研究方向：数字信号处理及地面发射技术。王召利(1984-)，女，硕士，工程师。研究方向：数字信号处理技术。

10.16180/j.cnki.issn1007-7820.2016.11.036

TN919.83；TP

A