Lossless JPEG

Lossless JPEG是一种无失真的图像压缩标准，在1993年由联合图像专家小组组织创建，并由该小组负责后续维护，但这一词语即使是现在也可用于代表由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与使用离散余弦变换的失真压缩模式不同，无失真的压缩使用了一个简单的预期性编码模型（predictive coding model），称为脉波差量编码调变（differential pulse code modulation，DPCM）。

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

<image>

<image>

<image>

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

- 数值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个必须要做的步骤：去相关（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 = \begin{cases} min(A,B), & \mbox{if } \mbox{ C≥max(A,B)} \\ max(A,B), & \mbox{if } \mbox{ C≤min(A,B)} \\ A+B-C, & \mbox{otherwise } \end{cases}$$

所以会有以下三种情况：

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

#### 前文建模（Context modeling）

JEPG-LS的算法估计了预测误差（prediction errors）的条件期望值$E\left\{\ e|Ctx \right\}$，前文建模（Context modeling）的目的是要利用图片中结构相似的部分来对预测误差做编码，前文（Context）是由已知的邻近样本的差异决定，可以用坡度（gradient）来表示：

$$\begin{array}{lcl} g_1 & = & D-B \\ g_2 & = & B-C \\ g_3 & = & C-A \end{array}$$

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

$$P(e|Ctx=[q_1,q_2,q_3])=P(-e|Ctx=[-q_1,-q_2,-q_3])$$

在合并了正号与负号之后，可以得到前文有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也是比较可扩展的，更进步的，且较广泛使用的一种压缩格式。