无损图像压缩

2024-05-25

无损图像压缩（精选7篇）

无损图像压缩篇1

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

1 无损压缩算法

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

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

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

在正常编码模式下,首先采用简单的边缘检测器初步确定一个预测值[11,12];然后再与上下文自适应的预测校正值相结合得到校正预测值;最后使用当前待编码原始像素值减去校正预测值就能得到预测残差,该预测残差的分布满足双边几何分布,利用上下文模型可求得预测残差的编码参数k,熵编码器采用参数k完成Golomb快速一元编码[13,14,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值判断SIGN值,若Q>0,则SIGN为1,若Q<0,则SIGN为-1;变量Q则成为索引A[Q]、B[Q]、C[Q]、N[Q]的地址值,此次优化降低了算法复杂度,提高了效率。在计算得到预测值,根据预测值通过量化后得到误差值以及量化误差值的过程如下

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

对某一像素编码的最后一步是更新变量A[Q]、B[Q]、C[Q]、N[Q],但该变量更新处理必须在编码过程的最后。为提高编码实时性,使变量的更新周期减少,设计了一种新的变量更新方式,如图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所示,10个流水线阶段分别完成以下步骤:

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

阶段2局部梯度值量化;

阶段3查询变量Q地址;

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

阶段5更新环境变量值;

阶段6~8 3个周期除法器;

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

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

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

3 实验及结果

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

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

4 结束语

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

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

关键词：全流水线,无损图像压缩,大吞吐量,FPGA

无损图像压缩篇2

高光谱遥感技术是20世纪80年代兴起的新型对地观测技术, 它将确定物质或地物性质的光谱与把握其空间和几何关系的图像革命性地结合在一起[1]。光谱连续特点使其获取的数据提供了丰富的地物细节, 在国民经济的各个方面获得了广泛应用。随着谱间和空间分辨率的不断增加, 成像光谱仪获取的高光谱数据越来越大, 限制了它在实际中的应用, 必须采用高效的压缩方法对其进行压缩。高光谱数据的获取非常昂贵, 其后续应用主要集中于特征提取、目标检测与分类等领域, 因而无损压缩则成为首选方案。

高光谱数据可以看作准三维图像, 在二维图像的基础上, 增加一维光谱信息。信息冗余来源于空间和谱间的相关性, 其中空间相关性较低, 而谱间具有较强的相关性。现有去除空间相关性的技术已经比较成熟, 如何有效去除谱间相关性, 已成为提高压缩性能的关键。高光谱图像无损压缩方法可以分为基于预测的方法[2,3,4], 基于整数变换的方法[5,6], 基于矢量量化的方法[7], 或者多种方法结合使用。基于预测的方法应用于有损压缩会产生误码传递[8]。Mielikainen J等人提出了基于聚类DPCM (differential pulse code modulation) 的高光谱图像无损压缩算法, 在使用较多参考波段情况下取得了较好的压缩效果, 但算法的复杂度偏高[7]。Zhang J等人将预测误差反馈机制引入谱间预测中, 提高了预测性能[8]。目前, 较多基于预测的方法都结合了聚类、神经网络等技术, 运算量过大, 并且产生了大量附加信息。本文提出一种基于波段分组的高光谱图像无损压缩算法, 为了减少了波段排序算法的计算量, 它根据相邻波段相关性预先进行分组。通过对波段排序算法性能进行研究, 以及对各组波段进行最佳后向排序, 谱间预测结合了最小二乘准则的最优预测, 仿真结果证明了算法的有效性。

1 波段分组

由于波段的自然顺序无法取得较好的预测性能, 根据高光谱图像的特点对波段重新排序非常必要。直接对全部波段进行整体排序, 计算量较大。实验发现, 若波段之间相距较远, 其相关性一般较差, 若预先进行波段分组GOB (group of bands) , 之后对各组进行排序, 可显著减少波段的搜索范围, 从而降低排序算法的计算量。本文根据相邻波段之间相关性来确定GOB的大小, 相关系数的定义如下:

$R_{i, j} = \frac{\sum_{i, j} (X_{i} - \bar{X}) (Y_{j} - \bar{Y})}{\sqrt{\sum_{i} (X_{i} - \bar{X})^{2} \sum_{j} (Y_{j} - \bar{Y})^{2}}} (1)$

式中:Xi和Yj为两个不同波段数据; $\bar{X}$ 和 $\bar{Y}$ 分别为相应的波段均值。根据式 (1) 计算OMIS-I型高光谱图像相邻波段的相关系数可知, 该型数据的第64波段、第79波段、第98波段和第113波段附近的相关性较差。这些波段与其相邻波段之间不适合进行谱间预测, 采用谱内压缩反而会得到较好的效果。借鉴文献[10]的分组思路, 给出如下波段分组方法:

(1) 计算相邻波段的相关系数Ri, i+1 (0≤i≤D-2) , 其中D为总的波段数;设置阈值T, 若R≥T, 则将该两个波段归为同一GOB, 否则置于不同的GOB;

(2) 若GOB中的波段数大于P, 则将GOB中每P个波段作为一个波段子集SOB (subset of bands) ;若有剩余波段, 则单独作为一个SOB。

2 波段排序

为了提高预测精度, 需要对各个GOB (SOB) 进行波段排序。波段排序是指定义一个波段排列顺序, 指定先编码的波段, 并作为后续待编码波段的参考波段。目前采用较多的排序算法为:单调前向排序、单调后向排序、最佳前向排序、最佳后向排序以及最小生成树排序 (Prim算法) [11]。单调前向 (后向) 排序是指当前波段仅利用与其相邻之前 (或之后) 的波段进行预测;而最佳前向 (后向) 排序指当前波段在其之前 (或之后) 的所有波段中搜索最佳预测波段。若i表示当前要预测的波段, 则σ (i) (0≤i<D) 为排序函数, 上述几种排序算法及运算复杂度的描述如表1所示。

最小生成树排序是将用最小预测误差原则选择最优参考波段问题归结到搜索一个图结构的最小加权生成树的优化问题, 可以获得理论上最优的预测效果。由于需要计算任意两个波段之间的预测误差均方值, 故计算量较大。文献[11]给出的实验结果表明, 后向排序的预测效果优于前向排序的预测效果, 最佳后向排序可以获得接近最小生成树的预测效果。考虑预测性能和复杂度两方面因素, 本文采用最佳后向排序算法对各个GOB (SOB) 进行波段排序, 利用波段之间的互相关系数代替MSE作为搜索原则, 可显著提高搜索速度。对于GOB中存在多个SOB的情况, 除最后一个SOB外, 其他SOB的最后一个波段均在与其相邻的后一个SOB中搜索最佳参考波段, 使得每个GOB中只有一个波段采用谱内压缩方式。对于用特定光谱成像仪获取的高光谱图像, 波段之间的相关性是由遥感器决定的, 与图像内容无关, 因而上述波段的分组和排序结果, 可以应用于大部分用该光谱成像仪获取的高光谱图像。

3 基于最小二乘准则的谱间最优预测

高光谱图像的内容比较丰富, 纹理较为细密, 利用波段内所有像素计算预测系数不可取。通常的做法是先对波段进行聚类, 对各个分类分别计算最佳的预测系数, 但聚类算法计算量较大, 并且会导致较多的附加信息。在当前像素的局部邻域范围内可以认为是平稳的, 利用邻域像素进行预测可以获得较好的效果。本文采用与当前像素具有相同空间位置的参考波段像素进行谱间线性预测, 同时在参考波段和当前波段中选取具有相同空间位置的邻域结构, 在该邻域内利用最小二乘准则求得最优谱间预测系数。具体算法:若pk (i, j) 表示第k个波段中第i行、第j列的像素值; $\hat{p}$ k (i, j) 表示其预测值;ek (i, j) 表示预测误差, 则当前像素pk (i, j) 的谱间线性预测值为:

$\hat{p}_{k} (i, j) = \sum_{m = 1}^{L} α_{m} p_{k - m} (i, j) + β (2)$

式中:L为预测阶数。预测误差ek (i, j) 表示为:

$e_{k} (i, j) = | p_{k} (i, j) - \hat{p}_{k} (i, j) | (3)$

在当前波段中选取与pk (i, j) 相邻的K点局部邻域, 该局部邻域中的像素表示为[qk, 1, …, qk, K]T, 按照下式给出的准则计算预测系数α=[α1, α2, …, αL, β]T

$\arg (\min_{α} (\sum_{n = 1}^{Κ} [q_{k, n} - \hat{q}_{k, n}]^{2})) (4)$

上式可表示为:

$ψ = (Q α - C)^{Τ} (Q α - C) (5)$

式中:

$Q = [\begin{matrix} q_{k - 1, 1} & \dots & q_{k - L, 1} & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ \\ q_{k - 1, Κ} & \dots & q_{k - L, Κ} & 1 \end{matrix}]; C = [\begin{array}{l} q_{k, 1} \\ ⋮ \\ q_{k, Κ} \end{array}] (6)$

预测目标在于使式 (5) 最小化, 由此可以得到最佳预测系数:

$α = (Q^{Τ} Q)^{- 1} (Q^{Τ} C) (7)$

由式 (7) 可知, 求解α的运算量随着K和L的增大而增加。综合考虑压缩性能和运算量两方面因素, 选取K=4, L=1。图1所示为参考波段与当前波段相同位置上的邻域结构。其中, Y为当前波段待预测像素;X与Y具有相同的空间位置;Y1～Y4和X1～X4分别对应qk, 1～qk, 4与qk-1, 1～qk-1, 4。

由于利用当前像素之前的已编码邻点进行预测, 预测系数无需作为附加信息进行传输。采用该邻域结构的另一个优点是可以采用逐行处理方式来降低对变换内存的要求。由于JPEG-LS无损压缩标准具有较高的压缩性能和运算效率, 故采用该标准对参考波段和预测残差进行无损压缩。需要指出的是, 在对预测残差进行JPEG-LS压缩前, 需要将残差图像映射到非负空间。若M表示映射函数, ek表示第k波段的预测残差最小值, 则映射后的数据表示为:

$Μ [e_{k} (i, j)] = {\begin{matrix} e_{k} (i, j) ‚ & e_{k} \geq 0 \\ e_{k} (i, j) - e_{k} ‚ & e_{k} < 0 \end{matrix}$

4 实验结果与讨论

为验证所提算法的有效性, 利用VC++软件对128波段OMIS型高光谱图像进行了仿真实验。实用型模块化成像光谱仪 (OMIS) 是我国自行研制的成像光谱仪, 它覆盖了从可见光到热红外的波段范围。图2给出了压缩后各波段的bpp曲线图。

可以看出, 多波段预测算法压缩后个别波段bpp要高于谱内JPEG-LS压缩。本文算法进行了波段分组, 很好地解决了这一问题。

5 结语

本文提出了一种基于波段分组的无损压缩算法。在波段分组的基础上, 对各组进行最佳后向排序, 谱间预测结合了最小二乘的最优预测, 实验结果表明了算法的有效性。多波段预测较多地应用于无波段排序的压缩算法中, 由于预先进行了波段排序, 采用一个参考波段即可获得较好的压缩效果。此外, 本文对波段排序算法性能的研究对后续相关工作具有参考价值。基于上述实验结果, 算法还可以从以下2个方面进行研究:

(1) 高光谱图像内容比较丰富, 不同地物边界处的像素应该单独进行预测;

(2) 谱间只进行前向预测, 双向谱间预测是一种更具潜力的压缩思路, 这也是下一步的研究内容。

摘要：高光谱图像海量数据给存储和传输带来极大困难, 必须对其进行有效压缩。针对高光谱图像不同频谱波段间相关性不同的特点, 提出一种基于波段分组的高光谱图像无损压缩算法。为了降低波段排序算法的计算量, 根据相邻波段相关性大小预先进行分组, 采用最佳后向排序算法对各组波段进行重新排序。在当前波段和参考波段中选取具有相同空间位置的邻域结构, 在最小二乘准则下, 利用邻域像素对当前预测像素进行最优谱间预测。参考波段和预测残差数据进行JPEG-LS压缩。对OMIS-Ⅰ型高光谱图像进行实验的结果表明, 与基于多波段预测算法相比, 该算法可进一步降低压缩后的平均比特率。

关键词：高光谱图像,无损压缩,波段分组,波段排序

参考文献

[1]浦瑞良, 宫鹏.高光谱遥感及其应用[M].北京:高等教育出版社, 2000.

[2]苏令华, 吕韶昱, 万建伟.基于多预测器的高光谱图像无损压缩[J].国防科技大学学报, 2007, 29 (1) :44-48.

[3]MIELIKAINEN J.Lossless compression of hyperspectralimages using lookup tables[J].IEEE Signal ProcessingLetter, 2006, 13 (3) :157-160.

[4]孙蕾, 谷德峰, 罗建书.最佳递归双向预测的高光谱图像无损压缩[J].光学精密工程, 2009, 17 (11) :2864-2870.

[5]DU Q, FOWLER J E.Hyperspectral image compressionusing JPEG2000 and principle component analysis[J].IEEE Geoscience and Remote Sensing Letters, 2007, 4 (2) :201-205.

[6]粘永健, 辛勤, 孙蕾, 等.基于3D SPIHT的高光谱图像压缩技术[J].光学精密工程, 2008, 16 (6) :1146-1151.

[7]付文秀, 王世刚, 高燕梅, 等.结合矢量量化的SPIHT算法用于多光谱图像压缩[J].通信学报, 2004, 25 (6) :110-114.

[8]孙蕾, 罗建书, 谷德峰.基于谱间预测和码流预分配的高光谱图像压缩算法[J].光学精密工程, 2008, 16 (6) :1146-1151.

[9]MIELIKAINEN J, TOIVANEN P.Clustered DPCM forthe lossless compression of hyperspectral images[J].IEEETransactions on Geoscience and Remote Sensing, 2003, 41 (12) :2943-2946.

[10]ZHANG J, LIU G Z.An efficient reordering prediction-based lossless compression algorithm for hyperspectral im-ages[J].IEEE Geoscience and Remote Sensing Letters, 2007, 4 (2) :283-287.

无损图像压缩篇3

在航天应用中,线阵CCD应用广泛,因为它具有较面阵CCD更多的优点,它的结构简单,单排感光单元数可以做得很多,在同等测量精度下,它的测量范围可以做得较大,而且能够在低照度条件下工作。多通道输出的线阵CCD能够在相对较短的时间内实现图像数据的转移,相对地提高了CCD的感光时间,但是输出的图像数据首先要进行数据整合才能得到一幅完整的图像。

图像压缩在各个领域中应用广泛,通过压缩可以减少图像的存储空间,提高传输线路的利用率,而无损图像压缩在航天、航空侦查以及医学摄像领域中应用广泛,较之于有损图像压缩方法,它能够将原始图像无失真地还原出来。JPEG-LS无损图像压缩算法是一种算法难度低、压缩效率较高的无损压缩算法,它的算法难度低便于硬件实现。采用FPGA来实现该算法,可以实现流水线的工作模式,提高算法的执行效率。

1 系统的总体结构

整个系统的工作原理如图1所示,CCD传感器经过视频处理器处理后的数据分为4个通道输出(如图中的A、B、C、D),在双口静态存储器的协助下,将四个通道输出端的图像数据整合成一副完整的图像数据,紧接着输入到JPEG-LS无损压缩模块[1]中进行图像压缩,源图像以预定模式的输入给编码器,在经过上下文建模的判别后决定采用哪种方式进行压缩:一种是常规(Regular)模式,即对图像进行预测,得到预测残差,然后对预测残差进行哥伦布(Golomb)编码[2];另一种是游程(Run)模式,即对图像直接进行游程编码, 得到的压缩图像通过一个输出端口输出。

2 CCD数据的整合

2.1 四通道的线阵CCD工作原理

四通道输出的12 000像元的线阵CCD,如图2所示,A、C通道为奇像元通道,B、D通道为偶像元通道。A通道输出1～5 999奇数像元的数据,B通道输出2～6 000偶像元通道数据,C通道输出6 001～11 999奇数像元数据,D通道输出6 002～ 12 000偶数像元数据。C、D通道输出的数据是排在后面的像元数据先输出,排在前面的像元数据后输出的,这与A、B通道数据输出的顺序相反。

2.2 CCD数据整合的FPGA实现

本文的FPGA选用Xilinx公司的Spartan3的XC3S200芯片,双口静态存储器选用IDT公司的IDT70V27,它的大小为32 K×16 bit。

图 3所示是系统仿真的时序图,CCDCLK是像元转移时钟(为5 MHz),FRAME是帧转移始终,DataA-DataD是四个通道输出的数据,CLKRam是驱动双口RAM的时钟,WAddr是写RAM的地址,RAddr是从RAM读数据的地址。因为双口RAM能同时进行读写操作,为了保证数据能够不间断地处理,在双口RAM中开辟两块区域,一块用于将CCD数据写入RAM中, 另一块是从RAM中读取数据。在向RAM中写入数据时,要求在一个像元转移时钟内,写入四个通道的数据,并且写A,B的数据从第一个地址递增,写C,D通道的数据是从第12 000个地址开始并且依次递减。从RAM中读取数据时, 初始地址为相对于写操作的另一块地址区域的起始地址并且依次递增,这样就读出了一幅完整的图像,用于图像压缩。

3 FPGA实现JPEG-LS图像压缩

3.1 JPEG-LS压缩方法

JPEG-LS压缩方法有两种工作模式:一种是无损压缩模式;另一种是有损压缩模式。本文用的是它的无损压缩模式,在无损压缩工作模式下,JPEG-LS压缩算法的简化框图如图4所示,源图像按预定的扫描模式依次输入给编码器,编码器采用如图中左边的模板的来预测x的值,并通过a,b,c,d的梯度变化来决定编码器采用常规模式编码还是采用游程编码模式,采用常规编码模式时,预测器通过两个部分来预测x的值,一部分是固定预测,即仅根据a,b,c,d的值来预测出一个值,然后通过自适应修正器来对这个预测值进行修正,用x处的真实图像值减去预测值,得到预测误差,通过上下文建模器,对预测误差进行调整,使得预测误差在自己规定的范围内,然后通过哥伦布编码器来进行编码输出压缩后的图像。在游程模式中,编码器直接跳过预测和误差编码,从x处开始计数其值和a的值相同的一连串像素,即游程的长度。

3.2 JPEG-LS无损压缩实现

3.2.1基于FPGA实现JPEG-LS的结构与原理

实现JPEG-LS算法的流程为:

1)初始化。初始化365个预设的上下文计数值A,B,C和N,初始化游程编码的表以及索引,降抽样值x指向图像的第一个像素;

2)计算模板的梯度值。g1=d-b;g2=b-c;g3=c-b; 判断g1=g2=g3=0 ,若等于零则转向游程编码(第八步),若不等于零则为常规模式,继续下一步;

3)量化g1,g2,g3的梯度值为q1,q2,q3,并将其映射到范围为[1]其中的一种上下文条件下Q;

4)根据以下公式计算固定预测值 $\hat{x}$ MED,然后自适应修正器对固定预测值进行修正得到 $\hat{x}$ :

$\hat{x}_{Μ E D} ≜ {\begin{cases} \min (a, b) i f c \geq \max (a, b) \\ \max (a, b) i f c \leq \min (a, b) \\ a + b - c o t h e r w i s e \end{cases}} (1)$

5)计算预测误差,即将真实像素值减去预测值 $\hat{x}$ 得到 $\bar{ε}$ ,并将 $\bar{ε}$ 映射到预定范围内;

6)计算哥伦布编码的参数k,将预测误差进行哥伦布编码;

7)更新A,B,C,N的值,并返回第一步进行下次循环;

8)游程扫描,对游程长度进行编码。

在FPGA内采用流水线[3]的方法来实现算法。

将算法分成五个模块,各个模块的工作复杂度几乎相同,流水线工作模式如图5所示。在JPEG-LS算法描述里,变量表的更新是在最后一部完成的,但是下次操作要用到这些变量表,所以在FPGA中,将旧的变量A,B,C,N的值保存,便于后面的操作,而同时更新A,B,C,D的值,为了下一次计算,从而保证了流水线工作模式的完成。在每个模块中尽量采用并行算法的模式,如“计算预测误差,保存旧的A,B…0,更新A,B…的值”这个模块,可以将计算预测误差,保存和更新A,B…两个步骤并行运算,减少每一级的运算时间。

3.2.2 设计实现

设计采用大量的片内RAM资源,首先是对A,B,C,N变量表的存储,使用片内Distributed Ram资源产生4个730字节的变量表,将梯度量化值q1,q2,q3,归一化为Q值,将其转换成索引存储器的地址,实现对A[Q],B[Q],C[Q],N[Q]的索引。当预测误差(Errval)计算出来之后使用更新A,B…模块更新这个变量表里的值。其次,在计算梯度g1,g2,g3时,模板需要两行图像数据,所以要对前一行数据进行存储,在初始化时由于还没有图像数据,将该行的数据初始化为零,在计算梯度的同时,存储读取的图像数据为正在处理的行,若当前行处理完毕,则将该行的地址作为下一行处理的前一行数据的地址。这里设计采用片内的Block RAM 资源设计一个24 000 bytes的双口RAM。这样设计需要的RAM资源占片内资源的88%。

量化g1,g2,g3为q1,q2,q3这个过程如下(这里用C语言描述,Verilog语言也类似),其中T3,T2,T1,NEAR为梯度阈值:

//JPGE-LS标准 //FPGA中实现qi相应的值

If (gi <=-T3) qi=-4; 0;

Else if(gi <=-T2) qi=-3; 1;

Else if(gi <=-T1) qi=-2; 2;

Else if(gi <-NEAR) qi=-1; 3;

Else if(gi <=NEAR) qi=0; 4;

Else if(gi < T1) qi=1; 5;

Else if(gi < T2) qi=2; 6;

Else if(gi < T3) qi=3; 7;

Else qi=4; 8;

在JPEG-LS标准中量化出来的值按照0对称,在FPGA中为了能够更简单的实现查找A,B,C,N中的表,将量化的qi做了修改,在归一化到Q时采用以下公式:

$Q = q_{1} + q_{2} \times 9 + q_{3} \times 9^{2} (2)$

A,B,C,N的变量表按照所需要的Q的升序来进行安排时,Q就可以作为索引这些变量的存储器地址线了,在算法中当q1为负(即SIGN=-1)时,q1,q2,q3都取反,算法要求有365种上下文(Contexts)情况。这里需要730个地址来索引,其中一半重复的,这样增加了存储数量来减少复杂度和提高效率。

使用公式(1)计算出x的固定预测值(Fixed prediction)px,通过以下公式对px进行调整。其中MAXVAL是算法限定的最大预测值。C[Q]即在Q处的C的值:

$p_{x} = {\begin{cases} p_{x} + S Ι Ν G \times C [Q] \\ Μ A X V A L (p_{x} > Μ A X V A L) \\ 0 (p_{x} < 0) \end{cases}} (3)$

得到预测值之后便可以使用真实的像素值减去预测值,得到预测误差Errval,得到预测误差之后,将A[Q],B[Q],C[Q],N[Q]的值备份,存为A1[Q],B1[Q],C1[Q],N1[Q]。然后更新计算A[Q],B[Q],C[Q],N[Q]的值,并将这四个存储区在Q地址处的值更新。

计算Golomb编码的k值,k值的计算是将N1[Q]值右移k位,当N1[Q]的值小于A[Q]时,这个k值即Golomb编码所需要的k。将预测误差Errval重新映射,使得误差为非负数。

进行Golomb编码,以2k作为Golomb编码的参数。表1所示为k=2时,Golomb编码值。

在FPGA中使用Verilog语言实现q=(Errval-1)〉〉k;r=x-(q〈〈 k)-1;编码值为((((1〈〈q)-1)〈〈1)〈〈k)|r。

游程编码在FPGA中的实现的Verilog HDL语言如下,以RUNval+RUNcnt的编码就是游程编码:

4 仿真与结果

整个设计使用Verilog HDL语言[4]实现,在Xilinx的ISE开发平台下完成,综合后占用8 400个逻辑单元,220 k的RAM资源。结合Modelsim对多幅图像进行了仿真,仿真结果表面,对一个像元输入直到预测误差输出(在系统时钟为20 MHz的条件下)延时约为260 ns,压缩一幅12 000像元的图像为1.2 ms。

5 结论

根据FPGA能并行运算的优势,将JPEG-LS无损压缩的结构,按照流水线的模式进行分割,为设计硬件实现图像的无损压缩提供了较好的解决方案,无损压缩能在使图像不失真的条件下,减少了图像的传输量,为图像的传输系统减轻了负担。

参考文献

[1]Marcelo Weinberger,Gadiel Seroussi,Guillermo Sapiro.TheLOCO-I lossless image compression algorithm:principles andstandardization into JPEG-LS[J].IEEE Trans Image Proc,2000,9(8):1310-1322.

[2]Golomb S W.Run length encoding[J].IEEE Transactions onInformation Theory,1966,12:399-401.

[3]Rafael C Gonzalez,Richard E Woods.Digital Image Proces-sion[M].Second Edition.BEIJING:Publishing House ofElectronics Industry,2002:326-400.

无损图像压缩篇4

关键词：灰度半调图像,2DCT,无损压缩

1 概述

在计算机和多媒体通信技术的快速发展中, 针对图像的压缩问题逐渐引起人们的重视。图像的内容丰富、信息量大、占用很大的存储空间, 当对海量数据传输和存储时, 庞大的数据量就给计算机的处理和存储、通信系统的带宽带来了极大的挑战, 为了有效的存储、传输这些数据, 必须对图像进行压缩, 因此有必要对图像压缩编码进行研究[1,2]。JPEG、MPEG等国际标准委员会提出用2维DCT变换对灰度和连续图像进行压缩的方法[2,3]。

图像存在视觉冗余、时间冗余、空间冗余、像素冗余等冗余信息, 图像的像素在水平方向、垂直方向上都存在着一定的相关性, 二维DCT变换是正交变换, 可以去除这些冗余和相关性[2], 解决图像的压缩问题。近年来国内外学者深入研究2维DCT变换, 提出各种基于二维DCT变换的灰度连续图像的压缩和水印算法。目前二维DCT变换的灰度连续图像的压缩大多是有损的。

数字半调技术是将连续图像转变为半调图像的一种计算机和数字信号处理技术, 它利用人眼的视觉低通特性, 将连续的图像转换成等观感的半调图像。由于人眼具有低通特性, 人眼对亮度变化比对色度变化更敏感, 所以当人站在一定远距离观察半色调图像时, 会产生连续色调图像的视觉错觉效果。它和一般的二值图像不同, 一般的二值图像视觉上只有黑白两种颜色, 而没有连续色调的效果。

针对2维DCT变换在灰度半调图像上的应用很少, 该文介绍灰度半调图像的生成机制, 分析灰度半调图像的特点, 设计针对灰度半调图像的二维DCT变换压缩方法, 最后解压图像是没有损失的, 而一般基于的2维DCT变换的连续图像压缩都是有损的, 这是本文的创新。实验结果压缩比高, 效果明显。

2 灰度半调图像的生成机制

对数字半调技术的分类方法有很多, 根据半调图像调制途径的不同可分为三类:调幅半调 (Amplitude Modulation, 简称AM半调) 、调频半调 (Frequency Modulation, 简称FM半调) 及调幅调频混合半调 (Amplitude Modulation Frequency Modulation, 简称AM-FM半调) 。常用的数字半调方法包括:有序抖动法 (Ordered dither, 简称OD法) 、误差分散法 (Error diffusion, 简称ED法) 、直接二值搜索法 (Direct binary search, 简称DBS法) 、点分散法 (Dot diffusion, 简称D法) 、查找表法 (Look-up table, 简称LUT法) 和蓝噪声模板法 (Blue noise masks, 简称BNM法) 等。该文简单介绍这几种常用的灰度半调图像生成方法。

有序抖动法属于点处理方式, 它的输出值只跟图像中对应的输入元素值有关系, 这种半调方法处理过程简单, 速度非常快, 实用性很高。它规定某一阈值矩阵, 将输入图像对应元素点与阈值矩阵对应位置的数值进行比较, 有比较结果才能确定图像的输出结果, 如果阈值矩阵的元素值大于当前像素点的像素值, 则输出结果为0, 也就是输出图像的像素值为黑色, 如果小于, 那么图像为白色, 像素值为1。采用这种方法的计算复杂度低, 实现过程简单。但缺点是容易丢失图像的细节信息, 出现周期性的纹理, 并且图像的再现效果不理想, 视觉效果不好。其处理过程的数学表达式如式 (1) 和式 (2) 所示, 系统框图如图1所示。其中, bi, j是所生成的半调图像, Q (∙) 是量化函数, xi, j∈[0, g) 是原始连续色调灰度图像, dk, l是抖动模板[1]。

有序抖动模型主要采取了两种形式的模板:聚簇型 (Cluster Dither) 和分散型 (Disperse Dither) , 如图2所示。后来, Ulichney等人分析聚簇型和分散型两种半调模板的优势, 分析有序抖动半调图像的产生机制, 提出了一种局部聚簇整体分散的有序抖动模板。常用的有序抖动模板如下图3所示。

2.1 误差分散法

误差分散法 (Errordiffusion简称E法) 利用误差的思想, 把输入图像与输出半调图像之间的误差扩散到其周围点中, 以减小局部误差, 从而提高了图像的再现质量。这种方法的优点是得到的半调图像色调丰富, 视觉效果好;不足之处在于处理速度相对较慢, 并伴随有龟纹现象出现, 且有连续的过渡现象容易在边缘部位产生, 滞后现象在高光和暗调部位出现。

典型的灰度误差分散半调系统框图如图4所示, 其数学模型如式 (3) 到 (5) , 其中, bi, j是所生成的半调图像, Q (∙) 是量化函数, xi, j∈[0, g) 是原始连续色调灰度图像, hk, l是误差分散核系数, ei, j是量化误差矩阵的系数。对于大多数实际的误差分散系统, 误差分散核系数hk, l满足式 (6) 的条件。

随着人们对误差分散类算法研究的不断深入, 相继出现了不同的误差分散半调核。误差分散核均呈不对称结构, 图5给出了常用的几种误差分散核形式, 其中Stevenson误差核 (如图5 (f) ) 是针对六边形的栅格处理, 其他五种均是针对矩形栅格处理。

2.2 直接二值搜索法

直接二值搜索法 (Direct binary search简称DBS法) 为连续色调图像寻找最优的半调输出, 是一种基于HVS (Human Visual System) 模型的迭代搜索算法。为得到最优结果, 它将二值图像和观察到的连续色调图像的误差最小化, 并不断修正当前像素的二值输出。该方法得到半调图像没有明显的结构性纹理, 视觉效果很好。但其计算复杂度非常高, 在实际中并没有得到广泛应用。

2.3 点分散法

点分散法是由一个参数-等级矩阵对最低等级的所有像素, 先使用阈值处理, 得到其相应像素在半调图像中的值, 然后将量化误差扩散到等级大的相邻像素上。即点分散法对像素的处理顺序是由一个参数-等级矩阵决定的, 其具备抖法动和误差分散法的优点, 但是有相当多的龟纹出现在半调图像中。

2.4 查找表法 (Look-up table)

查找表法 (Look-up table, 简称LUT法) 是将原连续色调图像和半调图像的像素值放在一个表中, 通过查表再现图像。该方法的优点是运算速度快, 与误差分散法中间灰度处产生的效果一样, 但缺点在于所得到的半调图像具有结构性纹理, 低、高亮度区域细节不明显, 且LUT表占据的存储空间大[4]。

2.5 蓝噪声半调法

蓝噪声半调法是由白噪声半调方法发展而来的。因为人眼对低频成分很敏感, 对高频分量不敏感, 也就是对图像的细节信息不太敏感, 只对图像的概貌信息较为敏感。而白噪声包含大量的低频信息, 因此使用这种方法得到的半调图像容易产生变形现象, 而且会产生很多龟纹。白噪声的高频成分也就是蓝噪声信息, 根据人眼是觉得低通滤波特性, 提出了蓝噪声掩模法和蓝噪声半调法相结合的方法。该方法的优点是图像整体效果好, 没有结构性龟纹, 但是这种方法产生的图像对灰度级变化不敏感。

3 2维DCT变换

离散余弦变换 (简称DCT变换) 是一种正交变换, 通过正交变换, 可以把图像从空间域转换到变换的频率域, 在空间域图像的能量分布较为平均, 变换后在空间域图像的能量分布比较集中, 主要集中在一些高频系数上, 低频分量携带能量多[5], 高频分量携带能量少, 低频信息代表图像的概貌信息, 高频分量代表图像的细节信息, 可以对变换系数进行量化, 在视觉效果可以接受的情况下, 舍弃一些小的能量, 编码时舍弃掉一些小的系数, 减少要压缩的编码图像的信源, 从而达到压缩的目的。2维DCT变换是JPEG、MPEG等国际连续灰度和彩色图像压缩标准中长用的方法。今年来, 国内外大量学者围绕2维DCT变换进行了大量研究, 取得了丰硕的成果。

3.1 2维DCT变换原理

二维离散余弦变换 (简称2维DCT变换) 是N.Ahmed等人在1974年提出的正交变换方法, 它将时域信号从空域映射到频域, 使得信号在时域所表现出的能量发散形式变换为频域的能量相对集中形式, 以便与对信号进行各种处理。它是最接近K-L变换的正交变换, 常被认为是对语音和图像信号进行变换的最佳方法。2维DCT变换是与傅里叶变换相关的一种变换, 它于离散傅里叶变换类似, 但只适用于实数。

2维DCT正变换公式为:

或写作:F=CTf C (8)

2DCT反变换公式为:

或写作:f=CFCT (10)

式中:x, u=0, 1, 2, ..., n-1;y, v=0, 1, 2, ..., n-1;其中, C为变换核。

3.2 2维DCT变换的特点

正交变换之所以能够压缩数据, 主要有以下性质:

1) 熵保持性, 即只通过正交变换的正变换和反变换, 图像的还能还原回去, 信息不会丢失。

2) 能量保持性, 而且正交变换可以将图像的能量重新进行分配, 使得大部分能量集中在较少的几个系数上, 但总体的能量不变。这样就可以再图像质量允许的情况下, 舍弃能量较小的一些系数, 对能量较小的系数分配较少的比特, 对能量较大的一些系数分配较多的比特, 从而达到压缩的目的。

3) 去相关性。使空间高度相关的数值变为相关性较弱的系数, 进而降低空间数值之间的冗余。

K-L变换是完全的正交变换, 但由于其复杂度高, 没有快速算法, 而且不适合计算机实现, 因此人们经常用DCT这种近似正交变换来代替K-L变换。因此本章简单介绍二维离散余弦变换的方法、应用, 分析其变换特点, 在此基础上详细介绍三维离散余弦变换原理、运算规则, 阐述三维离散余弦变换的常用方法, 简单分析变换后系数的特点。

2维DCT变换是可逆的, 也就是说只采用DCT变换的图像是无损的。2维DCT变换能将信号的能量集中起来, 所以被广泛应用于图像的编码压缩领域, 例如JPEG、MPEG等国际编码标准都适用了2维DCT变换编码。

图像经过2维DCT变换后, 得到的系数可认为是原始图像信号在频率不断增大的余弦函数上的投影, 也就是说图像的低频系数分布在DCT系数矩阵的左上角, 高频系数分布在右下角。中、低频系数所含有的原始信号的成份较多, 所以只用中低频系数进行反变换, 就能得到图像的近似部分。高频系数所含的信息较少, 反应图像的细节信息, 所以在对图像进行压缩编码时, 可以只保留中低频信息, 去除高频信息。去除的信息越多, 压缩比越高, 解压图像越模糊;反之去除的信息越少, 压缩比越低, 解压图像越清晰。去除信息的多少可以自己调节, 看具体的应用场合而定。

4 基于2维DCT变换的灰度半调图像无损压缩

灰度半调图像是特殊的二值图像, 里面的数据只有0和1, 而连续图像的像素值是在0到255之间均匀分布的, 如果直接对其进行2维DCT变换, 变换系数在-3到5之间, 经过量化表后系数就全部量化为0, 也就是图像的信息全部量化掉了, 不能直接对灰度半调图像进行压缩。所以要结合灰度半调图像的特点设计针对灰度半调图像的压缩方法。压缩流程如下:

1) 图像分块:通常分为4×4、8×8或16×16;对同一幅图像分块越多计算速度越快, 但是图像的块效应越明显, 该文采用8×8分块。

2) 图像块像素值平移, 即所有像素值都减去128:这样可以降低系数范围。

3) 对每个图像块进行2维DCT正变换:2维DCT变换的正交性可以消除块各像素的空间冗余。在DCT系数块中, 直流系数 (每个矩阵左上角元素) 最大, 也就是说能量主要集中在矩阵的左上角 (低频区) , 高频系数较小, 可见DCT变换可以将空域的平均能量汇聚到频域的少数几个系数上。

4) 对变换后的系数矩阵进行量化:量化表采用JPEG标准委员会推荐的量化表, 进行量化除法。在量化表设计时, 综合考虑了人眼的视觉的低通特性, 对代表不同频率成分的系数采用视觉加权的形式产生量化矩阵。保留低频分量, 适当忽略高频分量, 使得人眼的视觉效果最佳。

5) 对量化后的系数进行Zig-Zag扫描:量化后的系数矩阵右下角全都是0, 采用Zig-Zag扫描, 可以有效的增大值为0的游程的长度。

6) 熵编码:利用可变长Huffman编码或算术编码技术进一步消除图像数据间的统计冗余, 计算压缩比, 得出图像的压缩数据码流。

7) 熵解码:与熵编码的过程相反。

8) 解码数据恢复矩阵的原顺序:按照Zig-Zag扫描的次序, 依次逐个恢复元素的顺序。

9) 反量化:利用量化表按位进行量化乘法。

10) 2维DCT反变换:根据式 (3-3) 或者 (3-4) 对反量化后的系数进行2维DCT反变换。

11) 图像块像素平移回去:即图像块的每个像素值都加上128。

12) 图像重组:将分块的多个小图像重新拼接成原图像大小。

5 Matlab仿真实验部分代码

Matlab是由美国mathworks公司开发的针对科学计算工具。它将对于矩阵运算特别方便, 该文采用Matlab进行仿真实验。部分代码设计如下:

6 结果结果及分析

实验结果表明基于2维DCT反变换的灰度半调图像方法简单、方便, 既能保证有较高的压缩比, 又能保证有较好的图像质量, 残插图全是黑的, 也就是原图像和解压后的图像是一样的, 算法是无损的。

参考文献

[1]阮秋奇.数学图象处理学[M].北京:电子工业出版社, 2001.

[2]余青山, 苏宏业, 等.一种基于DCT域的自适应块效应消除算法[J].信息与控制, 2008, 37 (2) .

[3]常环.静态图像压缩标准的发展回顾[J].中国现代教育装备, 2007, 4 (50) .

[4]Murat Mese P P.Vaidyanathan.Look-Up Table (LUT) Method for Inverse Halftoning[J].IEEE transactions on Image Processing, 2001, 10 (10) :566-1578.

无损图像压缩篇5

随着卫星遥感图像技术的发展, 人们对遥感图像的质量要求越来越高, 由于航天图像分辨率的要求, 数据的存储量和传输量也在急剧增加, 而卫星通道带宽有限, 要有效地传输图像信息, 必须对图像进行高效压缩。

JPEG-LS是针对连续图像无损或近无损压缩的ISO/ITU标准, 它是近年来JPEG对于图像无损压缩拟订的标准。目前, 在天文观测、航空航天、以及医学摄像等领域都得到了广泛的应用, 它能将无损图像无失真地还原出来。该算法在无损压缩领域具有高保真度和低复杂度等特点[1], 便于硬件实现的, 同目前流行的JPEG、JPEG2000、CCSDS等无损图像压缩算法相比较, 在硬件实现方面具有明显的优势。随着产业的发展、科技的进步以及图像数据量的“爆炸”似增长, 研究更高效的图像压缩技术已迫在眉睫, 各种先进的压缩技术优化的编码算法层出不穷。本文中对JPEG-LS静态图像压缩算法采用C语言实现, 并对该算法进行了优化, 使所编写的程序更适合于硬件描述语言的实现。

1 JPEG-LS图像数据压缩算法

JPEG-LS无损图像压缩算法采用自适应预测、上下文建模和Golomb编码算法, 对于图像中的平坦区域采用游程模式编码[2,3], 否则采用常规模式编码。在无损压缩模式下, JPEG-LS编码模式与JPEG无失真模式相比较, 区别主要在于JPEG-LS利用了Golomb行程编码, 并且引入了误差可以控制的近无损 (near-lossless) 图像压缩。

JPEG-LS无损图像压缩的主要编码原则[4]如图1所示, 原始图像数据以预定的扫描模式依次输入编码器, 无损图像压缩被看做是一个归纳推理的过程, 在编码当前像素时需先扫描过去的数据, 给当前像素值分配一个条件概率P, 就可以推断出当前的像素值, 这种推断的模式称为建模, 当前取样像素值的平均码长分布为-log2P。对于近无损图像压缩则采用重建值代替原始值作为条件数据。在编码过程中, 越短的码长分配越大的概率值。

2 JPEG-LS图像数据压缩算法的编码过程

2.1 上下文建模

所谓上下文建模就是指利用当前待编码数据的邻居与当前像素之间的相关性对其建模。假设当前像素值为x, 与其相邻的四个像素值分别为a、b、c、d, 利用这四个像素样本来确定x的编码方式, 即是采用常规编码还是游程长度编码。

2.2 样值编码模式的选择

通过对图像数据样本进行从左到右, 从上到下的编码后, 样本x也被编码。x的重建值由a、b、c、d样本先前的重建值Ra、Rb、Rc、Rd来决定, 因为是无损压缩, 重建值与原始值相同。上下文确定的步骤为:梯度计算:上下文确定程序的第一步应该是计算梯度值D1、D2、D3

计算公式如:

模式选择:如果当地梯度值D1、D2、D3全为0时 (对于无损压缩) 或者全小于等于NEAR (近无损压缩的压缩比控制因子) 时, 编码选择游长模式编码, 否则选择常规模式编码。

2.3 常规模式编码

常规模式编码分三个步骤进行:第一步, 预测;第二步, 预测误差编码;第三步, 变量更新。对这三个步骤又可以详细划分, 如图2所示:

预测:在进行预测之前先进行梯度量化和梯度合并预测分为四个部骤进行, 首先是边界检测, 预测值Px由样本重建值Ra、Rb、Rc来确定, 具体计算公式如下:

得出预测值之后, 就要进行预测值的修正, 修正过程取决于SIGN (决定上下文符号的临时变量) 和C[Q]的值, C[Q]的值需要在变量更新这一步骤中计算出来:

新的Px值应该约束在[0…MAXVAL (一幅图像中像素的最大可能值) ]这一范围内, 如果Px>MAXVAL, 则令Px=MAXVAL, 如果Px<0, 则令Px=0。MAXVAL取决于图像的精度, 如果图像的精度P=8, 则MAXVAL=28-1。

预测误差编码:得到预测值Px之后, 要计算预测误差Errval, x像素的的实际值用Ix表示, 则Errval=Ix-Px, 如果SIGN=-1, 则令Errval=-Errval。在无损压缩中 (NEAR=0) , 重建值Rx=Ix, 在近无损压缩中 (NEAR>0) , 要对Errval进行量化, 量化后再重建Rx的值。具体计算公式如下:

计算Rx后, 再对它进行边界修正, 即若Rx<0, 则令Rx=0, 若Rx>MAXVAL, 则令Rx=MAXVAL。修正Rx后, Errval的值也要被约束在相应的范围内, 即:

对Errval进行编码, 首先要求出Golomb编码变量k (k值定义为误差映射值MErrval的最不重要位) , 由变量A[0…364]和N[0…364]来计算k值, 通过k值来决定误差的映射。

误差映射之后, 对MErrval进行编码, 具体编码过程如下, MErrval由重要位和不重要位组成 (如图3) , 如果m<LIMIT-qbpp-1, LIMIT为常规模式编码中glimit的值, qbpp为一个映射误差值需要的比特数, 那么由m所形成的数字的编码应该由m个二进制0和1位二进制1组成 (如图4) ;k位不重要位的编码, 按照原来的比特位依次输出。

对于高位重要位, 如果m≥LIMIT-qbpp-1, 则输出LIMIT-qbpp-1个0和1个1, 对于k位不重要位的编码, 则输出qbpp位二进制码, 具体数字输出为MErrval-1的qbpp位最不重要位, 如图5:

下面是LIMIT和qbpp的计算公式:

bpp:MAXVAL的比特数;RANGE:预测误差的范围。

变量更新:常规编码模式的最后一步就是对变量A[Q]、B[Q]、C[Q]和N[Q]的值进行更新, 更新公式如下:

如果N[Q]=RESET (RESET为A[Q]、B[Q]和N[Q]取一半时的门限值) , A[Q]、B[Q]的更新值都取原值的一半, N[Q]的更新值取一半后再加1。

C[Q]的更新取决于B[Q]和N[Q]的更新值, 如果B[Q]≤-N[Q], 则B[Q]=B[Q]+N[Q], 若此时还满足B[Q]≤-N[Q], 那么B[Q]=1-N[Q];如果B[Q]>0, 则B[Q]=B[Q]-N[Q], 若此时还满足B[Q]>0, 那么B[Q]=0。C[Q]的计算公式如下:

常数MIN_C为C[Q]的最小的允许值, MAX_C为C[Q]的最大允许值, 对于8位精度的图像来说, MIN_C为-128, MAX_C为127。

2.4 游程长度编码

游程长度编码[5]是当信源出现连续相同的符号, 或者连续出现的符号在允许失真的范围内, 常使用的一种有效的编码方法。如果指定a样本作为游程模式的开始, 样本值为Ra, 扫描的下一个值为Ix, 若|Ix-Ra|≤NEAR, 则游程继续, 否则游程中断。游程编码步骤如图6:

游程扫描:游程模式的第一步就是扫描图像数据, 一般是行扫描, 得到x的实际值Ix, 若|Ix-Ra|≤NEAR, 则继续扫描, 游程长度计数变量RUNcnt加1, 令Rx=RUNval (扫描的图像数据值) , 如果行结束, 则中断扫描。

游程长度编码:得到游程长度RUNcnt, 就要对它进行编码。当RUNcnt≥2J[RUNIndex], 输出码字‘1’, 且RUNcnt=RUNcnt-2J[RUNIndex], J[0…31]为显示游程长度代码的32个变量;如果RUNIndex<31, RUNIndex减1, 然后进行下一轮的循环, RUNIndex为游程编码时的指针变量, 指向J[0…31]的数据。

如果游程在一行的结尾被中止, 并且RUNcnt>0, 则输出码字‘1’, 然后取样下一个值再进行梯度判断;否则就输出码字‘0’, 将RUNcnt写成二进制的形式, 接着输出J[RUNIndex]个RUNcnt的量化值, RUNIndex减1, 进行下一轮循环。

游程中断编码:如果游程不是在图像行尾结束, 对于这个新的中断值要进行编码。首先按下面公式得出游程中断标志RItype:

通过RItype的值计算出预测值Px, 以及预测误差Errval:

如果NEAR>0, 采用常规编码模式下Errval的编码方法进行量化并计算出Errval的约束值。同样游程编码也要计算Golomb变量k, 它的计算要用到变量TEMP (游程中断编码中用来计算Golomb变量的辅助变量) 、A[Q]和N[Q] (上、下文出现频率的367个计数器) 的值, 其中Q=RItype+365, TEMP的值由下面公式计算:

然后由表3 (用TEMP的值代替A[Q]的值) 得出k的值。在获得Errval和k的值之后, 再求出Errval的映射值, 首先求出误差映射的映射标志map。

误差映射值的计算:

EMErrval的编码方法与常规模式编码中MErrval的编码方法一样。

以上两种编码方式都采用C语言实现, 并对一些实现流程和算法流程进行表格化, 使所编写的程序适合于硬件描述语言VHDL的实现。

3 测试结果

对于JPEG-LS算法的压缩比, 通过C语言对该算法进行编程实现, 并对几幅图像进行了无损压缩, 得到的压缩比见图7。从图中可以看出, 图像的平滑度对图像的压缩比有较大的影响, 主要因为游程长度编码对图像的平滑度要求较高, 因为是灰度图像的无损压缩, 压缩比并不大, 因此可以通过改变图像平滑滤波的方法来改善压缩比[6]。

摘要：本文针对JPEG-LS无损图像压缩算法展开研究, 算法采用C语言实现, 并进一步优化, 使其适合于硬件实现。分析其中的关键技术, 常规模式编码、预测误差编码和游长模式编码, 并将这些算法以公式和表格的形式详尽表示, 降低了算法的复杂度, 便于硬件描述语言编程实现。最后针对不同的图像进行了测试, 得出了不同的压缩比, 仿真结果表明图像的平滑度对图像的压缩比有较大的影响。

关键词：JPEG-LS无损图像压缩,常规模式编码,游长模式编码

参考文献

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

[2]ISO/ICE FCD 14495.Lossless and near-lossless coding of continuous tone still images (JPEG-LS) [S].

[3]ISO/IEC International standard 15444-1, ITU Recommendation T.88, 2000.Information technology-JPEG2000 image coding system[S].

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

[5]王海荣.JPEG-LS多路并行译码算法的硬件实现[D].海南大学, 2010.

数字影像无损压缩算法研究篇6

随着计算机技术、通讯技术和生物医学工程技术等相关技术的高速发展, 通过对医学影像进行数字化处理, 进行计算机智能化处理, 将使依据医学影像进行的诊断放弃传统的肉眼观察和主观判断, 并可依据同一影像进行多种疾病的诊断和多科疾病的诊断。在应用计算机技术后, 医学影像将从形态图像向功能图像转变, 对医学影像数据库和特征库的内容进行提取分析, 将可以帮助医生进行科学的诊断, 提高诊断的科学性、客观性和准确性。

应用DICOM3标准和网络通讯协议标准TCP/IP可以方便地实现对直接具有数字化接口的影像设备的成像数据的提取;小波分析 (Wavelet Analysis) 在时域和频域同时具有良好的局部化性质, 而且由于对图像信号的高频成分采用转件精细的时域或频域取样补偿, 从而可以聚焦到对象的任何细节, 这一特点在医学影像分析中将得到较好的应用。

1总体方案设计

ACR和NEMA联合组成委员会在1993年发布的医学数字成像与通信 (Digital Imaging and Communication in Medicine, DICOM) 标准3.0, 是医学影像设备间联网的专用数字接口, 是进行网络通信时应满足的标准协议, 是一组具有DICOM兼容性的设备所共同遵循的协议。在DICOM标准中, 医学图像包含了许多如图像获取设备对图像的分析、医生的报告及患者情况等信息, 这种信息与图像的结合方便了图像的检索、图像的分析和诊断。医学影像处理的总体结构如图1所示。

1.1符合DICOM标准中间件实现方案

DICOM3消息交换的网络支持对应于ISO/OSI定义的网络传输中的会话层、表示层及联接控制服务单元, 这部分底层 (传输控制层、网络层) 的信息交换定义为通用的网络传输协议。在设计实现中将采用智能Agent中间件技术。当设备采集影像数据后, Agent中间件自动将数据传送到医学影像数据库中, 减少不必要操作的处理, 并能保证数据传输的一致性和同步性。

1.2压缩存储中间件实现方案

影像图片大约需要8～15 MHz的存储空间, 为了缩小存储成本和便于网络传输, 必须对图像进行压缩。现阶段常用的压缩存储方案有4种:① 基于JPEG标准下的无损压缩算法JPEG-LS, 这是DICOM标准支持的一种成熟的无损压缩算法;② 基于整数小波变换的单帧图像无损压缩算法, 它利用了医学图像象素之间存在高度的相关性和整数小波的特性;③ 基于三维整数小波的序列图像无损压缩算法, 对整个序列进行无损压缩, 可以有效地提高图像的压缩率;④ 利用JPEG2000标准支持ROI (Region Of Interest 感兴趣区域) 编码的特性, 对图像的ROI进行无损压缩编码, 对次要信息区域 (如背景) 采用高压缩比的有损压缩方法。

本文在综合分析以上4种方案的基础上, 提出了基于适形离散小波变换 (SA-DWT) [1]与整数小波变换相结合的影像无损压缩算法。并应用该方案构件了智能Agent中间件。

1.3检索诊断中间件实现方案

在应用存储的数字化医学影像和影像特征进行诊断时, 需要完成大量的检索和比对处理, 为了减少网络流量, 提高检索速度, 应用了基于小波模极大值及多尺度不变矩相结合的检索算法, 并建立了算法实现的中间件, 运行效果明显, 能够较好地完成影像的检索和诊断作用。

2无损压缩算法研究

无损图像压缩是指解压缩后的图像与原来图像完全相同, 没有任何信息的损失。医学图像是医学诊断和疾病治疗的重要根据, 在临床上具有重要的应用价值。确保医学影像压缩后的高保真度是医学图像压缩首要考虑的因素。现在医学图像常采用无损压缩, 因为它能够精确地还原图像。但是无损图像压缩的缺点是压缩比低, 仅为2～4;而有损图像压缩的压缩比可高达50, 甚至更高。所以将这2种压缩法方法在保证使用要求的基础上结合起来, 在获取高的压缩质量的前提下提高压缩比。本文提出的基于SA-DWT与整数小波变换相结合的压缩算法, 就是应用SA-DWT算法确定感兴趣区域, 对该区域进行无损压缩, 其他区域进行有损压缩, 大大提高了压缩效率, 并不损失影像的医学作用。

2.1SA-DWT算法

传统的二维小波变换都是针对矩形区域进行的, 得到的变换系数个数一般会大于原始区域像素点个数, 而且由于填充, 变换后区域的边界会出现钝化, 所以限制了任意形状区域的编码效率。

现代的患者同一部位的医学影像可以应用到相关的不同的多个诊断过程中, 因此, 整幅影像中可能存在多个特征区域, 而每个区域的形状都不是规则的图形, 不适合采用传统的二维小波变换。本文采用了Li等提出的适形离散小波变换 (SA-DWT) , 该变换可以用于对任意形状的图像对象进行变换, 因此适合与对医学影像中的感兴趣区域进行编码。测试结果表明:

① 变换域的变换系数同像素域的相同;

② 只要采用的L阶小波滤波器具有完全重构特征, 并且下采样的位置已知, 就存在一个唯一的反变换, 可用于完全重构原始的影像;

③ 长度自适应的小波变换保留了分段采样点的位置, 不会产生超出边界的系数。

由于对奇数长度图像信号的剩余采样点进行了缩放, 因此这种任意长度的小波变换得到的低通系数具有相同的尺度, 这就避免了边界处小波系数的突变。

2.2提升算法原理

由Sweldens等提出来的提升方案 (Lift Scheme) 是构造紧支集双正交小波的一种新方法, 被称为“第二代小波”[2], 也叫做整数小波变换。该方法可以将整数映射到整数, 可以实现由SA-DWT算法分割的不同区域内影像的无损压缩。

对于原始信号sj, 经小波分解成为低频信号sj-1和高频细节信号dj-1两部分。有提升方法构成的小波变换包括:分裂 (Split) 、预测 (Predict) 和更新 (Update) 3个步骤。

2.2.1 分裂

此过程是将原始信号sj分裂成2个互不相交的子集sj-1和dj-1, 通常是将这个信号序列分解成偶数序列和奇数序列, 即

split (sj) = (evenj-1, oddj-1) = (sj-1, dj-1) 。

2.2.2 预测

针对数据间的相关性, 可用sj-1去预测dj-1, 故可以采用一个与数据集结构无关的预测算子P, 使得dj-1=p (sj-1) , 这样就可以用子数据集sj-1代替原始数据集sj。若再用子集dj-1与预测值p (sj-1) 之间的差值去代替dj-1, 则此差值反映了二者的逼近程度。如果预测是合理的, 则差值所包含的信息就比原始子集dj-1包含的信息要少得多。预测表达式为:

$\hat{d}_{j - 1} = o d d_{j - 1} - p (e v e n_{j - 1}) = d_{j - 1} - p (s_{j - 1})$ 。

将数据集合分成偶数集合和奇数集合后, 最简单的一个预测算子就是用相邻2个偶数的均值来作为它们之间的奇数的预测值, 即

p (sj-1) =s (j, 2k+sj, 2k+2) /2。

由此可得预测表达式为:

$\hat{d}_{j - 1, k} = d_{j - 1, k} - p (s_{j - 1}) = s_{j, 2 k + 1} - (s_{j, 2 k} + s_{j, 2 k + 2} / 2)$ 。

2.2.3 更新

经过上述2个步骤后, 所产生的系数系数子集sj-1的某些整体性质 (如均值) 并不和原始数据中的性质一致, 因此需要采用更新过程。其目的是通过算子U产生一个更好的子数据集合 $\hat{s}_{j - 1}$ , 使之保持与原始数据集一致的特征。 $\hat{s}_{j - 1}$ 定义如下:

$\hat{s}_{j - 1} = e v e n_{j - 1} + U (\hat{d}_{j - 1}) = s_{j - 1} + U (\hat{d}_{j - 1})$ 。

具体的更新计算的过程为:

$\hat{s}_{j - 1, k} = s_{j, 2 k} + (\hat{d}_{j - 1} + \hat{d}_{j - 1, k - 1})$ 。

对于数据子集 $\hat{s}_{j - 1}$ 重复进行上述相同的3个步骤, 即将 $\hat{s}_{j - 1}$ 分解成 $\hat{s}_{j - 2}$ 和dj-2, 经过n次分解后, 原始数据sj的小波表示为:

${\hat{s}_{j - n}, \hat{d}_{j - n}, \hat{d}_{j - n + 1}, \dots, \hat{d}_{j - 2} ‚ \hat{d}_{j - 1}}$ 。

式中, $\hat{s}_{j - n}$ 代表了信号的低频部分; ${\hat{d}_{j - n}, \hat{d}_{j - n + 1}, \dots, \hat{d}_{j - 2}, \hat{d}_{j - 1}}$ 代表了信号的高频部分。

重构数据时的提升为:

$\begin{array}{l} s_{j - 1} = \hat{s}_{j - 1} - U (\hat{d}_{j - 1}) ‚ \\ d_{j - 1, l} = d_{j - 1, l}^{(1)} + a_{- 1} (s_{j - 1, l - 2} - s_{j - 1, l - 1}) ‚ \\ s_{j} = Μ e r g e (s_{j - 1}, d_{j - 1}) 。 \end{array}$

2.3整数小波变换

Sweldens已经证明在提升的基础上可以进行整数集到整数集的小波变换。一个整数集合通过小波变换得到的仍然是整数集合。在进行影像压缩编码处理过程中, 不需要对变换后的系数进行量化, 因此可以实现影像的无损压缩。

在进行影像的无损压缩时, 主要采用了S变换和S+P变换。针对影像的特点并结合Haar变换的整型表示方法, 提出如下形式:

S变换之后, 在低通系数sj-1, l的基础上进行线性预测, 以产生新的高通系数dj-1, l, 这就是S+P变换。

2.4实验与分析

在验证算法中, 主要选取了3组MR图像 (256*256*16 bits, 每组30幅) 和2组CT图像 (512*512*16 bits, 每组30幅) , 分别采用了本文提出的算法进行压缩处理, 同时用预测整数小波变换 (简称:PIWT) 、整数小波变换 (IWT) 和差分脉冲编码调制 (DPCM) 等算法对这5组序列影像进行压缩编码, 得到平均压缩率如表1所示。对其中的数据进行分析可知:本算法的压缩率分别比PIWT算法、IWT算法和DPCM算法平均提高81.15%、100.73%和67.61%。表1中的二维算法的压缩率是序列图像中个图像压缩率的平均值。

应用SA-DWT变换可以方便地找到影像中的多个感兴趣区域, 应用整型小波变换对影像象素本身灰度值进行变换, 且保持了变换前后的整数的一致性, 可以实现对感兴趣区域的无损压缩。

在进行若干次提升变换后, 再利用哈夫曼编码对变换后的系数进行编码, 将较好地去除像素间的相关性, 极大地减低了原始图像的信息量。

3结论语

DICOM标准可以方便地将医学影像处理的数据传到计算机中进行处理, HL7标准可以提高医院不同应用软件间的通信能力。根据多媒体技术和关系数据库理论, 建立医学影像数据库。在构建影像数据库和影响特征库时, 为了减少数据存储量, 提高影像传输速率, 而不影响影像的诊断效果的基础上, 本文提出了基于适形离散小波变换 (SA-DWT) 与整数小波变换相结合的影像无损压缩算法, 并构建了该算法的中间件, 在实际的验证测试中, 该算法可以较好地完成影像的压缩存储, 效果良好。

下一步的研究工作将针对目前影像压缩存储算法和影像检索的算法进行深入研究和比较, 进一步发展各种医学影像内容分析的理论和技术, 深入研究能够充分表示医学图像内容的各种特征, 进一步发展系统架构、性能评价、相似性度量方法、人机交互方式、高维度检索和智能诊断等技术。

参考文献

[1]CINKLER K.Very Low Bit-rate Wavelet Video Coding[J].IEEE Journal on Selected Areas in Communication, 1998, 16 (1) :4-11.

无损图像压缩篇7

在水声探测与通信中,常需要对换能器阵列接收到的信号进行存储,因而无损压缩技术得到了更多的关注[1]。常见的无损压缩算法分为两大类:基于统计模型的无损压缩和基于字典模型的无损压缩[2,3,4]。基于统计模型的无损压缩算法有:Huffman压缩算法、算术压缩算法[5]、游程压缩算法[6]等,基于字典模型的算法有LZ77压缩算法、LZ78压缩算法、LZW压缩算法[7,8]等。无损压缩利用数据的统计冗余进行压缩,压缩率受到数据统计冗余度的理论限制,广泛应用于文本数据、程序和特殊场合的图像数据(如指纹图像、医学图像等)的压缩[9]。

1Huffman和LZ77压缩算法原理

1.1 Huffman算法原理

Huffman编码[10]是一种基于二叉树结构的编码方式,编码的核心是Huffman树的建立。

二叉树可以利用来设计前缀编码。假设有一棵如图1所示的二叉树,其四个叶子结点分别表示A,B,C,D四个字符,且约定左分支表示字符‘0’,右分支表示字符‘1’,则可以从根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。则所得A,B,C,D的二进制前缀编码分别为0,10,110和111。

假设每种字符在信息中出现的次数为wi,其编码长度为li,信息中只有n种字符,则信息总长为:

$L = \sum_{i = 1}^{n} w_{i} l_{i} (1)$

对应到二叉树上,若置wi为叶子结点的权,li恰为从根到叶子的路径长度,则L恰好为二叉树上带权路径长度。由此可见,设计信息长度最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵Huffman树的问题,由此得到的二进制前缀编码称之为Huffman编码。

1.2 LZ77压缩算法原理

LZ77[11,12]是一种基于字典的压缩算法,其主要思想是把已输入的数据流的一部分作为字典,编码器为输入流开一个窗口,并随着字符串的编码而把窗口中的数据从右移动到左,因而这种方法是基于一个滑动窗口。LZ77的基本思想可以借助图2表示。

从图2中可以得出LZ77算法的最简单步骤:

(1) 从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤(2),否则进行步骤(3);

(2) 边界的偏移,len为可匹配的长度,C为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤(1);

(3) 输出三元符号组(0,0,C)。其中C为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤(1);

解压缩的过程十分简单,只要像压缩时一样维护好滑动的窗口,随着三元组的不断输入,在窗口中找到相应的匹配串,缀上后继字符C输出(如果off和len都为0则只输出后继字符C)即可还原出原始数据。

2Huffman和LZ77算法的压缩效果对比

2.1 水声通信数据压缩率对比

Huffman算法编程实现之后,为了试验针对不同文件类型的压缩效果,分别使用TXT文档和WAV音频进行压缩对比。为了得到正确的压缩结果,对每种类型各取10个样本进行压缩。其中TXT文档内容为水声通信解码的数据, WAV音频则为接收到的水声信号。压缩时所使用的机器配置为:酷睿T2050(1.6 GHz),1G内存,120G硬盘,x1450(128M)独显。使用Huffman算法和LZ77算法进行压缩之后的结果对比如表1和表2所示,对TXT文档和WAV音频的压缩率对比如图3～图4所示。

从表1和图3可以看出,Huffman算法对所选文本文档的压缩率稳定在20%～30%之间,LZ77算法对所选文本文档的压缩率稳定在50%～60%之间。同时压缩时间和解压时间随着文件的大小而变化,文件越大,压缩时间越长,解压时间也越长。

通过表2和图4可以看出,Huffman算法对所选WAV音频的压缩率大约为3%左右,压缩效果较差,而LZ77算法对WAV音频的压缩率大约在1.4%左右,压缩效果比Huffman更差。

2.2 水声信号WAV文件压缩速率对比

一般来说,可以用算法的复杂性来衡量一个算法的效率,而算法的复杂性分为算法的时间复杂性和空间复杂性。算法的时间复杂性越高,算法的执行时间越长;反之,执行时间越短。算法的空间复杂性越高,算法所需的存储空间越多;反之越少。在算法的复杂性分析中,对时间复杂性的分析考虑的更多[13]。

针对本文的两个程序,考虑当输入规模为n时,Huffman算法内部的循环体执行了n2次,这个次数再乘以一个常数因子,便决定了Huffman算法的执行时间。因此Huffman算法的时间复杂性是O(n2)。LZ77算法内部的循环体也执行了n2次,所以LZ77算法的时间复杂性同样是O(n2)。

但是根据测试结果,同样压缩1.67 MB的文本文档,Huffman算法仅仅需要0.312 s,而LZ77却需要4.671 s。其实,这是常数因子所起的作用,可以推测LZ77算法的常数因子较大。按照这一思路,在源文件不断增大的过程中,两种算法运行时间的增加速度将会大致相同。为了验证这一点,选用不同大小的水声信号WAV文件进行了测试。测试时所使用的机器配置为:酷睿T2050(1.6 GHz),1G内存,120G硬盘,x1450(128M)独显。测试结果如表3所示。

通过表3可以看出,在压缩源文件不断增大的过程中,LZ77压缩算法的压缩时间T2和Huffman算法的压缩时间T1的增长速度基本持平。由此,以下猜测得以验证:LZ77和Huffman算法的时间复杂性都是O(n2),所不同的是常数因子。可以预测,在压缩更大的水声WAV文件的时候,LZ77算法的执行时间将依然保持在Huffman算法执行时间的4倍左右。

3结语

在本文中,重点介绍了Huffman算法和LZ77算法的基本原理。在编程实现两种算法之后,通过对不同类型文件的压缩对比,可以看出,针对水声领域解码之后的TXT文件数据,LZ77的压缩率优于Huffman,而针对接受到的水声信号WAV文件,Huffman则要优于LZ77。此外,对于要求压缩速率的场合,Huffman算法要远远优于LZ77算法。

摘要：为了选择适合水声通信数据无损压缩的算法,对哈夫曼压缩算法和LZ77压缩算法进行了对比研究。通过C语言编程实现两种算法的压缩,并利用水声通信数据获得压缩结果。对两种算法的压缩率和压缩效率对比分析之后,得出结论:对于水声信号,使用哈夫曼算法将获得更好的压缩率和压缩速率。尤其是哈夫曼算法的压缩速率远远优于LZ77算法。

【无损图像压缩】推荐阅读：

无损压缩算法10-05

无损数据压缩10-11

图像压缩编码05-08

遥感图像压缩06-07

指纹图像压缩11-19