Image_compression

**影像壓縮**是資料壓縮技術在數位影像上的應用，目的是減少圖像資料中的冗餘資訊，從而用更加高效的格式儲存和傳輸資料。

## 壓縮的原理

資料越一致，代表統計特性越集中，包括傅立葉轉換域 (Fourier transform domain)、直方圖 (histogram)、特徵值 (eigenvalue)...... 等方面的集中度。壓縮的通則即是利用資料的**一致性**，越一致的資料，越能夠進行壓縮。除此之外，也可利用資料的規則性與可預測性來對其作壓縮。通常而言，若可以用比較**精簡的自然語言**來描述一個東西，那麼也就越能夠對這個東西作壓縮。

### 利用資料的特性作壓縮

* 文章：常用字或字母 (字母多出現 E，少出現 QXZ)。
* 歌曲：重複的旋律、頻率的倍頻關係、節拍內頻率的穩定。
* 聲音：能量多集中在低頻、頻率在短區間內的穩定。
* 卡通：每塊區域的邊緣 (edge) 資訊與顏色 (color)、邊緣 (edge) 資訊可以用較少參數編碼 (如果邊緣 (edge) 是幾何圖案)。

### 資料壓縮範例

* 聲音：MP3 (.mp3)，壓縮率約 1/3。
* 圖片：JPEG (.jpg)，壓縮率約 1/10 (灰階) 或 1/20 (彩色，利用 4：2：0)。
* 影片：MPEG (H.264、H.265)，壓縮率約 1/30 (灰階) 或 1/60 (彩色)。

## 影像的一致性

### 空間上的一致性

影像中每一點的值，會和相鄰的點的值非常接近。

$$
\operatorname {F} [m,n+1]\,\!$ ≈ $\operatorname {F} [m,n]\,\!
$$

$$
\operatorname {F} [m+1,n]\,\!$ ≈ $\operatorname {F} [m,n]\,\!
$$

直方圖 (histogram) 是統計出現次數的一種方法，它會去計算一個向量 (vector) 或一個矩陣 (matrix) 當中，有多少個點會等於某一個值。

舉例來說， $\operatorname {x} [n]=[1,2,3,4,4,5,5,3,5,5,4]\,\!$

則 $\operatorname {x} [n]\,\!$ 的直方圖 (histogram) 為 $\operatorname {h} [1]=1\,\!$ ， $\operatorname {h} [2]=1\,\!$ ， $\operatorname {h} [3]=2\,\!$ ， $\operatorname {h} [4]=3\,\!$ ， $\operatorname {h} [5]=4\,\!$

將影像相臨值的差異，利用直方圖 (histogram) 來統計，會發現值幾乎都落在 0 附近。

### 頻率上的一致性

一張影像的頻譜大多集中在**低頻**的地方。
影像的「頻率」是在空間域 (space domain) 作分析：

* **低頻成分**代表變化較為緩和的地方，對應的是影像的 **「顏色」(color)** 和 **「強度」(intensity)**。
* **高頻成分**代表變化較為劇烈的地方，對應的是影像的 **「邊緣」(edge)** 和 **「雜訊」(noise)**。

 

## 常用影像壓縮技術

壓縮的技術分成兩種：**失真壓縮 (lossy compression)** 的壓縮率較高，但無法重建原來的資料，例如：DFT、DCT、KLT (搭配量化 (quantization) 與截斷 (truncation))、4：2：2 或 4：2：0、多項式曲線的近似 (polynomial approximation)；**無失真壓縮 (lossless compression)** 的壓縮率較低，但可以重建原來的資料，例如：二元編碼 (binary coding)、霍夫曼編碼 (Huffman coding)、算術編碼 (arithmetic coding)、格倫布編碼 (Golomb coding)。

### 4：2：2 或 4：2：0

此技術運用的是**空間上的一致性**。

將像素 (pixel) 的 RGB 值，利用以下的公式轉換成 YCbCr

Y = 0.299 R + 0.578 G + 0.114 B

Cb = -0.169 R - 0.331 G + 0.500 B ( Cb = 0.565 (B - Y) )

Cr = 0.500 R - 0.419 G - 0.081 B ( Cr = 0.713 (R - Y) )

其中 Y 是亮度 (Luminance)，Cb 是藍色色差 (chrominance) ，Cr 是紅色色差 (chrominance)。

人類的視覺系統，對於亮度比較敏感，而對於彩度比較不敏感。
因此我們可以利用人類視覺的特性，減少 Cb、Cr 的取樣個數，取樣格式有 4：2：2 與 4：2：0 兩種。

假設一張圖片原本壓縮前 (即 4：4：4) 的 Y、Cb、Cr 各有 M×N 個值，4：2：2 的壓縮 Y 保留為 M×N 個值、Cb、Cr 則取樣到各剩下 M/2×N 個值；4：2：0 的壓縮 Y 同樣保留為 M×N 個值、Cb、Cr 則進一步取樣到各剩下 M/2×N/2 個值。
從 4：4：4 到 4：2：2，壓縮率約為 2/3；從 4：4：4 到 4：2：0，壓縮率約為 1/2。
從 4：4：4 壓縮到 4：2：2，再壓縮到 4：2：0，單一像素 (pixel) 儲存的 bit 數可以等效為：24 bits/pixel → 16 bits/pixel → 12 bits/pixel。

還原時，則是利用插值 (interpolation) 的方式：

 $\operatorname {C_{\text{b}}} [2m+1,2n]\,\!$ = 1/2 ×( $\operatorname {C_{\text{b}}} [2m,2n]\,\!$ + $\operatorname {C_{\text{b}}} [2m+2,2n]\,\!$ )

 

### 8×8 離散餘弦轉換 (DCT)

此技術運用的是**頻率上的一致性**。

通常我們會將影像切成 8×8 的方格作離散餘弦轉換 (DCT)，原因如下：

* 一張影像的每個區塊，其高低頻成分都不一樣，對整張影像直接作離散餘弦轉換 (DCT)，多少會有高頻成分的出現。如果切成 8×8 的方格，則對大部分的方格幾乎都沒有高頻成分。
* 降低記憶體的需要量
* 降低運算量

經過離散餘弦轉換 (DCT) 後的 8×8 矩陣稱為 DCT 矩陣。DCT 矩陣最左上角的係數稱為**直流 (DC) 成分**，而其他 63 個係數則稱為**交流 (AC) 成分**。越靠近 DC 值的 AC 值係數表示頻率較低的部分，而越往右下角方向的 AC 值代表的頻率則越高。

2D 的 8×8 DCT 的輸出通常會按照 "zigzag" 的順序，將 2D 轉為 1D 的型態。按照此順序排列，能量可能較大的會被擺在前面，而後面的高頻成分從某個值開始後幾乎為零，以符號 EOB (end of block) 表示，指後面的高頻的部分經過量化 (quantization) 之後皆為 0。

### 差分編碼 (Differential coding)

此技術運用的是**空間上的一致性**。

差分編碼指的是，除第一個元素外，將其中各元素都表示為各該元素與其前一元素的差的編碼。

對 $\operatorname {DC} [i,j]\,\!$ ，是針對 $\operatorname {DC} [i,j]\,\!$ - $\operatorname {DC} [i,j-1]\,\!$ 去編碼，
而不是直接對 $\operatorname {DC} [i,j]\,\!$ 作編碼。

### 霍夫曼編碼 (Huffman coding)

霍夫曼編碼 (Huffman coding) 的編碼原則：(Greedy Algorithm)

* 所有的碼皆在編碼樹 (coding tree) 的端點，再下去沒有分枝。滿足**唯一可解譯碼 (uniquely decodable code)** 與**即時可解碼 (instantaneous decodable code)**。
* 機率越大的，編碼長度 (code length) 越短；機率越小的，編碼長度 (code length) 越長。
* 假設 $S_{\text{a}}\,\!$ 是第 L 層的節點 (node)， $S_{\text{b}}\,\!$ 是第 L+1 層的節點 (node)，則 $\operatorname {P} (S_{\text{a}})\,\!$ >= $\operatorname {P} (S_{\text{b}})\,\!$ 必須滿足。

不滿足以上的條件則往上推一層。

### 算術編碼 (Arithmetic coding)

霍夫曼編碼 (Huffman coding) 是將每一筆資料分開編碼，算術編碼 (Arithmetic coding) 則是將**多筆資料一起編碼**，因此壓縮效率比霍夫曼編碼 (Huffman coding) 更高，近年來的壓縮資料大多使用算術編碼 (Arithmetic coding)。

* 範例：

假設要對 X 來作二進位的編碼，且經過事先的估計， $\operatorname {X} [i]=a\,\!$ 的機率為 0.8， $\operatorname {X} [i]=b\,\!$ 的機率為 0.2。

若實際上輸入的資料為 $\operatorname {X} =aaabaa\,\!$

Initial( $\operatorname {X} [1]=a\,\!$ )：lower =0，upper=0.8

When i = 2 ( $\operatorname {X} [2]=a\,\!$ )：lower =0，upper=0.64

When i = 3 ( $\operatorname {X} [3]=a\,\!$ )：lower =0，upper=0.512

When i = 4 ( $\operatorname {X} [4]=b\,\!$ )：lower =0.4096，upper=0.512

When i = 5 ( $\operatorname {X} [5]=a\,\!$ )：lower =0.4096，upper=0.49152

When i = 6 ( $\operatorname {X} [6]=a\,\!$ )：lower =0.4096，upper=0.475136

由於 lower =0.4096，upper=0.475136

lower <= 14\* $2^{-5}\,\!$ < 15\* $2^{-5}\,\!$ <= upper

所以編碼的結果為

$$
14_{\text{(2,5)}}=01110\,\!
$$

## 動態影像之編碼

MPEG (Moving Picture Experts Group) 為動態影像編碼的國際標準。
動態影像編碼的使用原理為：不同時間，同一個像素 (pixel) 之間的相關度通常極高，只需對有移動的物件 (objects) 記錄**移動向量 (motion vector)**。

 $\operatorname {F} [m,n,t]\,\!$ ：時間為 t 的影像

如何由 $\operatorname {F} [m,n,t]\,\!$ ， $\operatorname {F} [m,n,t+delta]\,\!$ 來預測 $\operatorname {F} [m,n,t+2*delta]\,\!$ ？

(1) 移動向量 $\operatorname {V_{\text{x}}} [m,n]\,\!$ ， $\operatorname {V_{\text{y}}} [m,n]\,\!$

(2) 預測 $\operatorname {F} [m,n,t+2*delta]\,\!$ ：

$$
\operatorname {F_{\text{p}}} [m,n,t+2*delta]\,\!$ = $\operatorname {F} [m-{V_{\text{x}}}[m,n],n-{V_{\text{y}}}[m,n],t+delta]\,\!
$$

(3) 計算「預測誤差」

$$
\operatorname {E} [m,n,t+2*delta]\,\!$ = $\operatorname {F} [m,n,t+2*delta]\,\!$ - $\operatorname {F_{\text{p}}} [m,n,t+2*delta]\,\!
$$

對預測誤差 $\operatorname {E} [m,n,t+2*delta]\,\!$ 作編碼。

## 影像檔案的處理 (Matlab)

### 基本概念

* 灰階影像在 Matlab 當中是一個矩陣，彩色影像在 Matlab 當中是三個矩陣，分別代表紅色 (Red)、綠色 (Green)、藍色 (Blue)。

.bmp: 沒有經過任何壓縮處理的圖檔

.jpg: 有經過 JPEG 壓縮的圖檔

* 要對影像做運算時，**要先變成 double 的格式**，否則電腦會預設影像為 integer 的格式，在做浮點運算時會產生誤差。

例如，若要對影像做 2D 離散傅立葉轉換 (Discrete Fourier transform)：

im=imread('C:\Program Files\MATLAB\pic\Pepper.bmp');

im=double(im);

Imf=fft2(im);

### 基本指令

* Image 檔讀取: imread
* Image 檔顯示: imshow, image, imagesc
* Image 檔製作: imwrite
* Video 檔讀取: aviread

### 範例

* 黑白影像

im=double(imread('C:\Program Files\MATLAB\pic\Pepper.bmp'));

(如果 Pepper.bmp 是個灰階圖，im 將是一個矩陣)

size(im);

(用 size 這個指令來看 im 這個矩陣的大小)

image(im);

colormap(gray(256));

* 彩色影像

im2=double(imread('C:\Program Files\MATLAB\pic\Pepper512c.bmp'));

size(im2);

(由於這個圖檔是個彩色的，所以 im2 將由三個矩陣複合而成)

## 壓縮方法

影像壓縮可以是有損資料壓縮也可以是無失真資料壓縮。常見的應用有 raw 和 tiff 格式等。gif 和 jpeg 是失真壓縮。通過 DCT 轉換後選擇性丟掉人眼不敏感的訊號分量，實現高壓縮比率。

### 無失真壓縮

對於如繪製的技術圖、圖表或者漫畫，優先使用無失真壓縮，這是因為失真壓縮方法，尤其是在低的位速條件下，將會帶來壓縮失真，如醫療圖像或者用於存檔的掃描圖像…… 等，這些有價值的內容的壓縮也儘量選擇無失真壓縮方法。

* 遊程編碼
* 熵編碼法
* 如 LZW 這樣的自適應字典演算法

### 失真壓縮

有損方法非常適合於自然的圖像，例如一些應用中圖像的微小損失是可以接受的（有時是無法感知的），這樣就可以大幅度地減小位速。

* 色彩空間：這是化減到圖像中常用的顏色。所選擇的顏色定義在壓縮圖像頭的調色盤中，圖像中的每個像素都用調色盤中顏色索引表示。這種方法可以與抖動一起使用以模糊顏色邊界。
* 色度抽樣：這利用了人眼對於亮度變化的敏感性遠大於顏色變化，這樣就可以將圖像中的顏色資訊減少一半甚至更多。
* 轉換編碼：這是最常用的方法。首先使用如離散餘弦轉換（DCT）或者小波轉換這樣的傅立葉相關轉換，然後進行量化和用熵編碼法壓縮。
* 分形壓縮：

## 特性

影像壓縮的目的就是在給定位速或者壓縮比下實現最好的圖像品質。但是，還有一些其它的影像壓縮機制的重要特性：

* 可延伸編碼 ：又稱漸進編碼、嵌入式位流，通常表示操作位流和檔案產生的品質下降（沒有解壓縮和再壓縮）。儘管具有不同的特性，在無失真編碼中也有可延伸編碼，它通常是使用粗糙到精細像素掃描的格式。尤其是在下載時預覽圖像（如瀏覽器中）或者提供不同的圖像品質存取時（如在資料庫中）可延伸編碼非常有用，有幾種不同類型的可延伸性：
  * 品質漸進：又稱層漸進，位流漸進更新重建的圖像。
  * 解析度漸進：首先在低解析度編碼圖像，然後編碼與高解析度之間的差別。
  * 成分漸進：首先編碼灰度資料，然後編碼彩色資料。
* 感興趣區域編碼：圖像某些部分的編碼品質要高於其它部分，這種方法可以與可延伸編碼組合在一起（首先編碼這些部分，然後編碼其它部分）。
* 元資料資訊：壓縮資料可以包含關於圖像的資訊用來分類、查詢或者瀏覽圖像。這些資訊可以包括顏色、紋理統計資訊、小預覽圖像以及作者和著作權資訊。

壓縮方法的品質經常使用峰值信噪比來衡量，峰值信噪比用來表示圖象失真壓縮帶來的噪聲。但是，觀察者的主觀判斷也認為是一個重要的、或許是最重要的衡量標準。

## 參見

* 數據壓縮
* 圖形檔案格式
* 數位訊號處理
* 圖像處理
* 電腦圖學
* 萊娜圖
* 標準測試圖像
* 圖像品質
  * 峰值信噪比
  * 結構相似度

## 參考文獻

Jian-Jiun Ding, 「Advanced Digital Signal Processing」, NTU, 2021.