JPEGLSLOCOI图像编码算法分析和研究Word格式.docx

JPEGLSLOCOI图像编码算法分析和研究Word格式.docx

《JPEGLSLOCOI图像编码算法分析和研究Word格式.docx》由会员分享，可在线阅读，更多相关《JPEGLSLOCOI图像编码算法分析和研究Word格式.docx（21页珍藏版）》请在冰点文库上搜索。

它是JPEG标准中用于无损压缩的一种独立模式，它使用基于空间域的非量化的DPCM预测编码（差分脉冲编码），然后对预测误差进行Huffman编码。

因此，用这种方式压缩的图像经重构以后和原图像完全一样的。

它仅使用周围的几个像素对当前像素进行预测，预测公式如下：

对于a1、a、a3、a4这四个系数，可以从预测表中选择，该表提供了8中不同的系数的线性组合。

显然，这种方法的好处是简单，但其缺点是很难到达较高的压缩比。

FELICS（Fast，Efficient，LosslessImagecompression）：

FELICS是一种和JPEG无损模式的压缩比相当的压缩算法，但是其速度却是JPEG无损模式的将近5倍。

这种算法巧妙的运用的当前像素的两个相邻像素进行预测和误差建模。

它使用单比特，修正的二进制码，以及Golomb-Rice编码。

该编码系统在保持较低的压缩比损失的情况下，大大提高了编码速度。

FELICS使用了光栅扫描顺序，并使用当前像素最邻近的两个像素来直接获取一个近似的误差概率分布，有效的结合了预测和残差建模的相关步骤。

在编码时，它会再一个误差模型集合中选择最适合的一个，最终用该模型对应的前缀码来完成编码。

CALIC（Context-basedAdaptiveLossless/Nearly-LosslessCoding）：

它是一个用于连续色调静态图像的基于上下文的只适应的无损/近无损预测编码体系。

他使用当前像素行的前两行像素作为上下文模板，并使用一个巧妙的非线性上下文预测器。

CALIC有连续色调模式和二进制模式两种。

正常情况下使用连续色调模式，对像素进行预测和误差建模然后使用自适应的算术编码；

而当进入大片的色调变化很平坦的区域时则进入二进制模式，即对当前平坦区域中的两种较单调的色调信息进行编码。

高效的上下文建模和量化技术使得CALIC同时有着较低的时间、空间复杂度。

目前为止，CALIC编码的平均比特最少。

2.JPEG-LS

JPEG-LS是一种新的针对连续色调静态图像的无损/进无损的压缩标准，ISO-14495-1/ITU-T.87。

他的核心算法是LOCO-I（LOwComplexityLosslessCompressionforImages）。

它是一种新颖的压缩算法，它结合了Huffman编码的简单地复杂度和上下文建模的压缩潜力，因此被描述为“enjoyingthebestofbothworlds”。

LOCO-I算法可以获得和目前的诸多基于算术编码的压缩算法相似甚至更好的压缩效率，同时又能保持较低的复杂度。

它的整体编码框图如图1所示。

图1：

JPEG-LS编码框图

无损图像压缩通常由两个独立的部分组成：

建模和编码。

建模部分可以归结为一个归纳推导过程，在这个过程中，按照事先规定的某种顺序（例如光栅扫描顺序）观察每一个像素。

在扫描过前i个像素xi=x1x2…xi之后，我们希望指定一个条件概率分布p（·

|xi）来推断下一个像素xi的值。

在理想情况下，xi+1的平均编码长度为-logp（xi+1|xi）bits，其中对数的基为2。

因此，我们期望得到一个非均匀的概率分布，使得下一个像素有一个坑能性较大的值。

在顺序模式，概率分布p（·

|xi）从过去像素学习而得，由于在解码端同样按顺序解码出以前的像素，所以同样可以得到这个概率分布。

而在双行程方法中，条件概率分布经过第一次扫描从整个图像学习而得，而第二次扫描才开始真正的编码，同时这个概率分布模型必须以头信息的格式被传送到解码端。

因而在这种模式下，总的编码长度包括信息头的长度。

理论上，我们可以通过大规模的条件区域或“上下文”来获得更加歪斜或不均匀的概率分布，但是这无疑会增加统计模型的参数数量，从而导致建模代价抵消了部分编码效率，形成“上下文稀释”效应。

不管在顺序模式还是双行程方法中，建模代价和统计模型中自由参数的个数是成正比的。

在目前的无损图像压缩方法中，概率的分配被分成了三项工作：

—预测，通过先序像素集合xi的一个子集来预测下一个像素xi+1的值xp

—确定xi+1的上下文，通常为过去子列的一个函数

—给定xi+1的上下文预测误差ei+1=xi+1-xp的概率模型

受高复杂度的通用模型的启发，LOCO-I找到了优化这些步骤的方法。

目前大部分编码算法都会使用算术编码来消除冗余熵，尽管这种方法很有效，但是再很多应用场合，实现起来还是比较复杂的，尤其是软件执行的时候。

而又有些算法以低复杂度为主要目标，采用传统的DPCM技术，然后对线性预测后的残差进行Huffman编码，虽然复杂度降低了但却无法达到较高的压缩比。

LOCO-I算法结合了Huffman编码的简单（相对于算术编码）和上下文建模的巨大压缩潜力，因此取了众家之长。

该算法使用了一种具有边缘自检测功能的非线性预测器，并且基于一个非常简单的由量化梯度决定的上下文模型。

该方法用少数几个统计参数实现了复杂的通用模型技术所能实现的效果，而且没有“上下文稀释”作用。

在该方法中，通过一个自适应的Golomb-Rice编码使每个上下文对应一个单参数概率分布，而且在平坦区域使用嵌入式字母表扩展机制。

令一种复杂算法FELICS也是基于Golomb-Rice编码的，单LOCＯ－Ｉ和它的不同之处在于LOCO-I更遵循传统的预测－建模－编码模式，使用一种新颖而简单明确的Golomb-Rice参数估计方法。

在保持同样的低复杂度情况下，LOCO-I比FELICS的压缩效率提高了很多。

同样，LOCO-I比目前很多方法的压缩比都高，而复杂度相对较低。

事实上，ISO/IECJTC1/SC29WG1委员会正在考虑是否用JPEG-LS来代替目前的低复杂度无损压缩标。

在接下来的章节里，我们将对JPEG-LS的编码流程及其核心算法LOCO-I进行详细的讨论。

首先在2.1节，我们将探讨如何对当前像素进行预测以及如何获取周围像素的梯度值用于后续的建模；

接着在2.2节我们将分析LOCO-I巧妙的上下文建模过程；

在2.3节，将会阐述Golomb-Rice编码过程；

紧接着在2.4节将讨论用于游程编码的嵌入式字母表扩展机制；

最后，本文会对JPEG-LS的整个编码流程做一个简洁的概括。

2.1 

预测

JPEG-LS中的预测和建模单元都是基于图2中所显示的因果模板的，其中，x表示当前像素，a、b、c、d和e代表相邻像素。

他们的位置关系见图2。

图2：

JPEG-LS的因果模板

在理性情况下，应该根据像素周围的局部边缘方向特性建立不同的模型，采取自适应的方式预测当前像素x的值。

但是我们为了实现低复杂度，放弃了这种方法，而是使用一个先序的边缘检测机制来实现较好的预测。

其预测公式如下：

（1）

其中Px为x的预测值。

不失一般性，我们假设a≤b，那么预测器

（1）的意义可以这样来理解：

当x的左边存在一个垂直的边缘时，则选像素a作为x的预测值；

若x的上方有一个水平的边缘，则选取像素b作为x的预测值；

如果没有检测到边缘，则用一个平面预测a+b-c来作为x的预测值。

或者还可以这样理解，就是取a、b、a+b-c三个中较大的那一个作为x的预测值。

从上面我们可以看到，这种预测具有边缘自检测功能，而且实现简单。

注意我们没有用到像素e和d，它们将在后面上下文建模中用到。

令E=x-Px，则E即为预测残差。

如果是在近无损模式，则会对残差E进行量化，进一步缩减取值范围。

量化过程将在代码描述中讲到，这里省略。

2.2上下文建模

JPEG-LS有两种编码模式：

常规模式和行程模式。

首先通过上下文信息来确定编码是在那种模式下进行，然后再常规模式下，又通过上下文来指导编码的进行。

2.2.1 

编码分布

我们知道，得到当前像素的预测值之后，我们会用当前像素的实际值减去预测值，得到预测残差E=x-Px，然后对残差E进行编码。

由于Huffman编码或者算术编码等熵编码方案与信源的概率分布有着直接的关系，所以我们总是期望知道残差的概率统计特性，然后根据这种特性来制定合适的编码方案，来达到最佳的压缩效果。

在正常情况下，预测残差大致服从拉普拉斯分部，即以0为中心，向两边成指数衰减的趋势，如图3所示。

一般用8bit来表示一个像素的亮度值，那么取值的最大值MAXVAL=255，取值的动态范围RANGE=MAXVAL+1=256，那么预测残差的取值范围就是-MAXVAL≤E≤MAXVAL，其中E=x-xp。

由于这个范围已经超过了8bit所能表示的范围，我们需要通过某种映射机制，使残差分布在-RANGE/2到RANGE/2的范围内。

因为超过这个范围的残差值是很少的，所以这种映射不会严重影响残差的拉普拉斯分布特性。

具体的映射过程如下式所示：

（2）

图3：

典型的拉普拉斯分布曲线

由于图像明暗变化，纹理信息的不同，得到的残差的差异也是多样的，于是我们可以用某种方法将这些残差进行分类，而分类的标准是使这一类残差具有更好的拉普拉斯分布特性，也就是更尖的分布特性。

然后对于每一种特定的分布，我们可以制定与之相适应的编码方案，来达到最好的效果。

由于LOCO-I是单边方式的，所以事先不可能获得各种分布的详细信息，因而要获得残差的概率分布情况留下两种选择：

一是在编码过程中根据过去的上下文信息自适应的建立起一个最优的分布表，但是这种做法复杂度太高，固不予采用；

LOCO-I选择另一种方法，就是通过离线学习，得到一套有限数目的概率分布模型集合，然后对于每一个上下文环境，自适应的为其制定一个最优的模型。

由于拉普拉斯分布以0为中心，我们用一个参数就可以表示其分布，如用一个衰减参数来表示。

因此我们用一个参数来索引这个模型，而每个模型又会有相应的事先制定好的与这种概率分布模型Huffman码表。

2.2.2 

上下文选择

在图3中，我们可以通过计算得到这样几个参数：

g1=d-b,g2=b-c,g3=c-a,andg4=b-e。

这些差值就代表了当前像素周围的局部梯度特性，能够反映局部像素值的变化强度或者说活跃程度，而这一特性必然能为预测提供指导，我们的上下文模型就是根据这几个梯度值得到的。

我们可以根据g1到g4的不同组合值，来决定不同的上下文模型，但是首先必须先对他们进行量化，否则会有太多的组合，过于复杂，也没有必要。

一般的，将g1到g3这三个值，都量化到以0为中心，正负对称的基数个区间中，如…{-2,-1},{0},{1,2}…等，其区间数目可以记为2R+1；

最后一个梯度g4由于离当前像素较远，所以可以进行更粗糙的量化，其区间数为2T+1，而T往往比R小很多。

量化后g1、g2、g3量化到相同的区间，因而都可以取2R+1个值中的一个，g4可以取2T+1中的一个值，所以总的可能的组合为（（2T+1）（2R+1）3）个上下文，因为这些上下文是根据不同的局部梯度值来分类的，所以我们有理由相信属于不同上下文的预测值，有着自己的分布特性，从而可以根据这种分布特性实现更好的编码。

将量化后的四个梯度值记为Qi={q1，q2，q3，q4}，其中的q1、q2、q3、q4分别是g1、g2、g3、g4量化后的值，Qi就代表了一个上下文。

且然而考虑到对称性，即：

Prob{Ei 

=△|Qi 

={q1，q2，q3，q4}}=Prob{Ei 

=-△|Qi 

={-q1，-q2，-q3，-q4}}

则可以将对称上下文合并。

即将-△变为△，然后合并到上下文Qi={-q1，-q2，-q3，-q4}中去，注意，这样的话，我们在编码一个残差时，如果为了合并上下文而改变了其符号，所以需要维护一个符号标志SIGN，来记录是否变更了符号，以便在解码时能恢复原来的值。

合并了对称的上下文后，总的上下文数目变为（（2T+1）（2R+1）3+1）/2。

在JPEG-LS中，g1、g2、g3的量化区间取{e|e≤-15}，{-7,-8,…,-14}，{-3,-4,-5,-6}，{-1,-2}，{0}，{1,2}，{3,4,5,6}，{7,8,…,14}，{e|e≥15}。

而g4被量化到三个区间，|g4|<

5,g4≥5,andg4≤-5。

这样总的上下文数目就是（9*9*9*3+1）/2等于1094个，事实上，有时直接省略了g4这个梯度值，使得上下文数目减小到365个，在JPEG-LS的官方文件中就是这样做的。

2.3 

编码

2.3.1 

Golomb-Rice 

首先介绍一下Golomb编码，它的思想就是，对于一个给定的参数m，那么一个整数n（n>

0）的Golomb码Gm由两部分组成：

的二元码表示，和n 

mod 

m二进制直接表示，中间用一为二进制1来隔开。

其中所谓的二元码表示就是指，所要表示的整数值是多少就用多少个0来表示它。

例如当参数m取为4，整数n是9时，那么n的Golomb码G4为0011，可见使用Golomb编码可以讲很多数用小于8个bit的位数来表示，因而达到了压缩的效果，Golomb编码可以看做Huffman编码的预处理过程，即在Huffman编码前对信源数据的一种科学有效的组织形式，它也属于熵编码的范畴。

Golomb编码对于服从几何分布的非负整数来说是最优的，即分布P（n）=（1-ρ）ρn，这里0<

ρ<

1。

对于每一种几何分布或近似的几何分布，可以找到一个参数m使得其Golomb码Gm占有尽可能少的平均比特数，或者说长度。

而这个最优的m值可以通过下式计算：

. 

（3）

特别的，Rice提出令参数m=2k时，即取2的指数大小时，可以使计算过程大大简化，使用简单的移位遍可以代替复杂的除法，这种方式就叫做Golomb-Rice编码，对于每一个编码结果我们用Rk表示。

前面已经提到，预测残差大致服从拉普拉斯分布，其分布范围是（-RANGE/2,RANGE/2-1），因而会出现大量的负数，所以需要将所有的负值映射为正值，经过映射后残差的取值范围变为（0，RANGE-1）。

映射公式如下：

（4）

其中的ME表示经过映射后的非负值，这是大致映射过程，在实际应用时还稍有出入。

幸运的是，拉普拉斯分布经过这种映射之后会近似的服从几何分布，这正是我们想要的。

实际上，在进行Golomb-Rice编码时，当带编码的整数值远大于2k时，会使码字变得很长，反而导致了比特的浪费，所以JEPG-LS使用的是有限长的哥伦布编码，即当码字超过长度限制LIMIT时，则用LIMIT个0跟当前整数值减一后的二进制表示，中间用二进制1隔开。

这样使得码字不会因参数大小的不适合而变得很长。

2.3.2 

序列参数估计

由上面的分析可知，使用Golomb-Rice编码最重要的步骤就是编码参数k的确定。

在JPEG-LS中，对编码参数k的估计是顺序化的，明确的，它的估计是基于量化后的残差的绝对值（如果是无损模式那么显然量化残差就等于原来的残差，因为没有进行量化）的期望值的，其计算公式如下为k=|log2Eq[|E|]|，其中Eq表示期望。

但是由于准确的计算量化残差绝对值的期望比较困难，我们可以用到目前为止，所得到的量化残差的平均值。

在JPEG-LS编码过程中，维护了两个变量N[Q]，和A[Q]，其中Q表示上下文索引，即表示该变量属于哪个上下文所有。

N[Q]表示到目前为止，出现的残差的数目，而A[Q]则是到目前为止，对量化残差绝对值的累计值。

然后通过下式得到k的估计值[4]：

k[Q]=min{k’|2k’ 

N[Q]≥A[Q]} 

（5）

为了对图像的局部变化进行更好的自适应，因为局部经常会出现不遵循总体统计特性的擦差分布，所以我么会周期性的重置N[Q]和A[Q]的值。

明确的说，对于每一个上下文Q，当N的值达到一个预先设定好的阈值N0后，就将N和A的值同时减半，这样在计算k的值是，离现在最近的那些残差值将会占有更大的权重，或者说更有分量。

2.3.3 

偏差消除

我们知道，Golomb-Rice编码对预测残差的拉普拉斯分布有着很强的依赖性。

但是，在某一个上下文模型中，经常会出现一个独立的，系统的偏差，使得分布不在以0为中心。

这种偏差会严重影响Golomb-Rice的编码效果，进而导致编码效率的下降。

为了减轻系统偏差的影响，JPEG-LS使用一种偏差反馈机制，对预测残差进行修正，其目的是将偏离的中心重新“拉”回到0点。

具体方法是，对于某一个特定的上下文，我们维护一个计数器N[Q],和前面的N[Q]一样，记录残差出现的数目，同时维护一个变量B[Q]，来累计目前为止所有经过修正后的预测残差（注意这里不是经过量化的残差值）的值，以及一个修正变量C[Q]。

变量C[Q]被初始化为0，每当B[Q]/N[Q]的值（修正残差平均值）增加0.5或更多时，C[Q]的值将会自增1，反之B[Q]/N[Q]的值减小0.5或更多时，C[Q]的值会自减1。

通过这种方法，可以在不用出发运算的情况下使得预测残差的均值保持在区间[-0.5,0.5]内。

而在此同时，B[Q]的值也将被更新来反应C[Q]的变化。

2.4 

嵌入式字母表扩展（游程模式）

有时后，当残差的分布比较歪斜或者畸形时，如集中分布于某几个值上，将会引起很大的编码冗余。

为了处理这种情况，LOCO-I算法使用了一种嵌入式字母表扩展机制。

明确的说就是，当检测到相邻像素a=b=c=d时，即g1=g2=g3=0时，说明编码进行到了一个很平坦的区域，则会进入游程编码模式。

在游程模式中，会继续检测当前像素x后面的像素是否和x相等（在进无损模式则判断是否和x的差值在一个允许的范围内），如果满足，则继续往后检测，然后将相同值的个数（包括x在内）记录下来，即游程长度，和当前值x一起编码，这样解码端就知道有“游程长度”个值为x的像素，这对于变化平坦，出现大量相同像素值的情况会节省很多比特[3]。

3 

编码过程的代码描述

在阐述了JPEG-LS核心算法LOCO-I的编码流程后，下面本文将用C语言再次大体描述一下整个编码流程中的一些关键步骤，其中斜体字部分为C语言代码内容，其他字体为注释。

在这一节，描述顺序是按照软件实际操作流程进行的，和前面介绍算法原理时稍有不同[]。

3.1 

上下文确定

为了方便，我们再次画出如图2所示的因果模板图，注意图4（a）显示的是无损模式的情况，x周围的像素重构前后都是一样的，而图4（b）显示的是进无损模式的情况，我们要使用重构后的像素Ra、Rb、Rc、Rd、Re来做因果模板，这是预测编码的尝试，是为了保持编码端和解码端的一致。

所以左右两个图分别对应无损模式和进无损模式的因果模板，为了统一，在引用到相邻像素时统一用Ra、Rb等表示以后不再作特别说。

图4（a）：

无损模式因果模板 

图4（b）：

进无损模式因果模板

3.1.1 

局部梯度计算

第一步，是上下文的确定过程，我们先计算局部梯度值，G1、G2、G3（G4在这里忽略），其代描述如代码段C-1所示，其中G1、G2、G3表示局部梯度值。

//--CodesegmentC-1——局部梯度计算--//

G1=Rd-Rb;

G2=Rb-Rc;

G3=Rc-Ra;

3.1.2 

模式选择

如果局部梯度值全为零时，或者在近无损模式他们的绝对值在一个允许的误差范围NEAR（NEAR表示进无损模式下允许的最大误差）内，编码将进入游程模式，否则编码将进入常规模式。

下面代码段C-2和C-3分别描述了进无损和无损方式的模式选择过程,其中RunMode和RegularMode分别表示游程和常规两种编码处理过程。

//--CodesegmentC-2——进无损方式模式选择--//

if（（abs（G1）<

=NEAR）&

&

（abs（G2）<

（abs（G3）<

=NEAR））

gotoRunMode

Else

GotoRegularMode

//--CodesegmentC-3——无损方式模式选择过程--//

If（G1==0&

G2=0&

G3=0）

gotoRegularMode

3.1.3 

局部梯度值量化

局部梯度值会被量化到9个区间，然后得到9个值，下面的代码中T1、T2、T3是为量化区间设置的阈值，Q1、Q2、Q3是量化后的梯度值，（Q1,Q2,Q3）组成一个向量，从而决定一个上下文索引值Q，其量化过程如代码段C-4所描述。

///--CodesegmentC-4——梯度值量化--/

If（Gi）<

=-T3Qi=-4;

elseif（Di<

=-T2）Qi=-3;

=-T1）Qi=-2;

=-NEAR）Qi=-1;

=NEAR）Qi=0；

=T1）Qi=1;

=T2）Qi=2;

=T3）Qi=3;

elseQi=4；

3.1.4 

量化梯度合并

如果量化向量（Q1,Q2,Q3）的第一个非零元素是负值，则将所有元素的值取反，即取为（-Q1,-Q2,-Q3），其目的是进行对称上下文的合并，如果进行了值的反转则一个标志SIGN将会置为-1，否则置为+1，显然这是必要的。

3.2 

预测过程是针对常规模式而言的，游程模式将在后面描述。

3.2.1 

带边缘