JPEG-LS(LOCO-I)图像编码算法分析和研究

JPEG-LS(LOCO-I)图像编码算法分析和研究(2011-12-1620:00:48)转载▼标签：jpeg-ls分类：图像视频类JPEG-LS图像编码算法分析和研究摘要JPEG-LS是在ISO/ITU的新标准中用于对静态连续色调图像进行无损或进无损压缩的一种算法。该算法具有实现复杂度低，保真度高等特点，因而广泛应用于数字相机、网络传输、无线通讯以及医学成像等领域。本文就JPEG-LS的核心算法LOCO-I以及其编码流程进行详细的分析和研究。1.简介无损压缩就是指经过压缩并重建后的图像和原图像完全一样，没有任何损失。如果重建图像和原图像存在差距，而误差被限制在一定的范围内就称作近无损压缩。近无损压缩虽然有所损失，但对视觉影像却很小，也可以认为是无损的。有很多无损或近无损的图像压缩算法，例如传统的JPEG无损模式、FELICS、CALIC等等。首先，我们来大概了解一下其中一些有名的算法。JPEG无损模式：它是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-LSJPEG-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，-q