Lossless JPEG

Lossless JPEG是一种无失真的图像压缩标准,在1993年由联合图像专家小组英语Joint Photographic Experts Group组织创建和维护,但是现在也可以用来代表Joint Photographic Experts Group所创建的无失真压缩,包含了JPEG 2000还有JPEG-LS。

Lossless JPEG在1993年被建立并加入了JPEG的标准之中,JPEG的压缩方式通常是破坏性资料压缩(lossy compression),意即在压缩过程中图像的品质会遭受到可见的破坏,Lossless JPEG则是用了与传统的JPEG完全不同的方法来压缩,采用无失真的压缩方式,但并没有受到广泛的支援。

Lossless JPEG使用了一个预测的系统,从与目标最近的三个方格(通常为上方,左方,以及左上方)来预测,并且在预测误差中使用熵编码(entropy coding),Lossless JPEG在医学影像中很受欢迎,也被用在数位负片(Digital Negative)的格式中,以及一些数码相机中用来压缩图片,但是在其他方面并没有广泛的应用。

无失真的操作模式

Lossless JPEG实际上是JPEG的一种操作模式,因为JPEG是使用离散余弦变换(Discrete cosine transform)来压缩图片,而Lossless JPEG的模式会存在是因为离散余弦逆变换(Inverse discrete cosine transform)没有被严谨的规定,所以无法保证编码器(encoder)的输入会刚好与解码器(decoder)的输出相符合,Lossless JPEG跟使用离散余弦变换(Discrete cosine transform)的失真压缩模式不同,无失真的压缩使用了一个简单的预期性编码模型(predictive coding model),称为离散脉冲编码调变(differential pulse code modulation)。

离散脉冲编码调变是一种使用图片中目标样本周围的样本中已经编码完成的样本来预测目标样本的调变,预测通常是取目标样本的上方以及左方的样本进行平均,离散脉冲编码调变会将预测样本的误差编码,而不是将每个样本编码,通常在图片中,一个样本与相邻的样本差异会接近0,传统的离散脉冲编码调变的编码器如图片一所示。

 
图片一:DPCM编码器
 
图片二:无失真模式方块图
 
图片三:样本X预测

无失真的操作模式的步骤如图片二所示,在预测的过程中,使用了图片三的A、B、C三个附近的样本,以做出目标样本X的预测,A、B、C三个样本必须为已经预测且编码过的样本,在下面的表格中,有八个预测值可以用来预测目标样本X[1]

  • 数值1、2以及3是一维的预测
  • 数值4、5、6以及7是二维的预测
  • 数值0只能用在差别编码(differential coding)的分级操作模式

一旦所有的样本都有了预测值,样本间的差值可以使用霍夫曼编码(Huffman coding)或算术编码(arithmetic coding)等等方法得到无失真的编码。

数值 预测值
0
1 A
2 B
3 C
4 A + B – C
5 A + (B – C)/2
6 B + (A – C)/2
7 (A + B)/2

一般来说,使用无失真的操作模式来压缩彩色图片,可以达到2:1左右的压缩比,这个操作模式在医学影像中很受欢迎,也被定义为数位负片(Digital Negative)的标准之一,但是因为复杂度所以不被广泛的使用。

JPEG-LS

JPEG-LS是一个无失真/接近无失真的连续调(continuous-tone)图片压缩标准,这个标准可以被分为两个部分,分别为在1998年获得了ISO 14495-1认定的核心技术,以及在2002年获得了ISO 14495-2认定的扩增技术的部分,JPEG-LS是一个简单且有效率的算法,包含了两个独立且独特的层级,分别为建模(modeling)与编码(encoding),JPEG-LS是为了可以提供比lossless JPEG更有效的无失真/接近无失真的图片压缩而被创建出来,因为当时使用霍夫曼编码的JPEG lossless以及其他的标准压缩效果并没有很好,这些压缩方法并没有办法达成很好的去相关(decorrelation)效果,然而JPEG-LS可以得到很好的去相关(decorrelation)的效果,JPEG-LS的核心技术是LOCO-I算法,此算法使用了对残余项(residuals)的预测、建模、以及前文参考编码(context-based coding),因为将残余项当成双边几何分布(two-sided geometric distribution),又称为离散拉普拉斯分布(discrete Laplace distribution),以及Golomb-like码(Golomb-like codes)的使用,所以能有较低的复杂度,除了无失真压缩,透过控制绝对值误差(maximum absolute)的最大值,JPEG-LS也提供了失真压缩的选择,JPEG-LS的压缩速度也比JPEG 2000以及原本的lossless JPEG标准还要快上许多。

LOCO-I算法[2]

在编码前,有2个必须要做的步骤:去相关(decorrelation)以及误差建模(error modeling)

去相关(decorrelation)

在LOCO-I算法中,垂直或水平的边界侦测(edge detection)可以透过检查目标像素(pixel)X的周围像素,如图片三所示,像素B是垂直的边界,而像素A是水平的边界,这个简单的预测式称为Median Edge Detection预测式,或称为LOCO-I预测式,像素X透过LOCO-I预测式,像素X透过 In the LOCO-I algorithm, primitive edge可以做出以下假设:

 

所以会有以下三种情况:

  • 当X左边有个垂直的边界,会挑B
  • 当X上面有个水平的边界,会挑A
  • 如果都没有,会挑A+B-C

前文建模(Context modeling)

JEPG-LS的算法估计了预测误差(prediction errors)的条件期望值 ,前文建模(Context modeling)的目的是要利用图片中结构相似的部分来对预测误差做编码,前文(Context)是由已知的邻近样本的差异决定,可以用坡度(gradient)来表示:

 

坡度反映了周围样本的平滑度(smoothness)及锐利度(edginess)等资讯,这些差异对预测误差以及统计特性有相当大的影响,从上面的式子中找出的差值都会被量化,以JPEG-LS来说,差值会被量化成9个不同区域,分别以-4~4代表,量化的目的是要使目前样本的值与前文(Context)的互信息(Mutual Information)最大化,我们可以从以下的假设获得前文:

 

在合并了正号与负号之后,可以得到前文有365个,在LOCO-I算法是一个改进后的算法,加法和减法的次数已经减少很多,division-free bias的计算过程可以从[]得到论证,可以透过这些反馈机制减少预测的偏差,进而得到较为精确的预测

相同的区域可做游程编码(Run-length encoding)

在JPEG-LS的一般模式,使用了Golomb–Rice码(Golomb–Rice codes)来做非负游程(non-negative run lengths)的编码,但Golomb–Rice码做低熵的编码很没有效率,因为编码的速率至少要1位元/符元(one bit per symbol),所以常常会造成许多冗余(redundancy),为了避免产生太多多余的码,可以使用字元扩充(alphabet extension)的方法。

JPEG-LS优点

可选择无失真/接近无失真压缩模式

透过控制绝对值误差可以选择不同模式。

压缩速度较快

JPEG-LS的压缩速度比起JPEG 2000以及原本的lossless JPEG标准还要快上许多。

复杂度较低

JPEG-LS特别适合低复杂度的硬件,因为复杂度不会太高,却可以得到不错的无失真压缩效果。

JPEG 2000

JPEG 2000有一个无失真模式,是基于小波转换的图像压缩,但是JPEG 2000的无失真 模式编码速度较JPEG-LS慢,也常常在人为或合成的图片上有较差的压缩比,但JPEG 2000也是比较可扩展的,更进步的,且较广泛被使用的一种压缩格式。

外部链接

http://www.jpeg.org/jpegls/index.html页面存档备份,存于互联网档案馆

http://www.jpeg.org/jpeg2000/index.html页面存档备份,存于互联网档案馆

参考来源

  1. ^ ITU-T. ISO DIS 10918-1 Digital compression and coding of continuous-tone still images (JPEG). Recommendation T.81
  2. ^ Marcelo J. Weinberger, Senior Member, IEEE, Gadiel Seroussi, Fellow, IEEE, and Guillermo Sapiro, Member, IEEE.The LOCO-I Lossless Image Compression Algorithm:Principles and Standardization into JPEG-LSIEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 8, AUGUST 2000