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 跟使用離散餘弦變換（Discrete cosine transform）的失真壓縮模式不同，無失真的壓縮使用了一個簡單的預期性編碼模型（predictive coding model），稱為離散脈衝編碼調變（differential pulse code modulation）。

離散脈衝編碼調變是一種使用圖片中目標樣本周圍的樣本中已經編碼完成的樣本來預測目標樣本的調變，預測通常是取目標樣本的上方以及左方的樣本進行平均，離散脈衝編碼調變會將預測樣本的誤差編碼，而不是將每個樣本編碼，通常在圖片中，一個樣本與相鄰的樣本差異會接近 0，傳統的離散脈衝編碼調變的編碼器如圖片一所示。

無失真的操作模式的步驟如圖片二所示，在預測的過程中，使用了圖片三的 A、B、C 三個附近的樣本，以做出目標樣本 X 的預測，A、B、C 三個樣本必須為已經預測且編碼過的樣本，在下面的表格中，有八個預測值可以用來預測目標樣本 X。

* 數值 1、2 以及 3 是一維的預測
* 數值 4、5、6 以及 7 是二維的預測
* 數值 0 隻能用在差別編碼（differential coding）的分級操作模式

一旦所有的樣本都有了預測值，樣本間的差值可以使用霍夫曼編碼（Huffman coding）或算術編碼（arithmetic coding）等等方法得到無失真的編碼。

一般來說，使用無失真的操作模式來壓縮彩色圖片，可以達到 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 也是比較可擴展的，更進步的，且較廣泛使用的一種壓縮格式。

## 外部連結

http://www.jpeg.org/jpegls/index.html （頁面存檔備份，存於網際網路檔案館）

http://www.jpeg.org/jpeg2000/index.html （頁面存檔備份，存於網際網路檔案館）

## 參考來源