Image and Video Processing chapter2

數字圖像處理 chapter2-Image Compression

圖像為什麼可以被壓縮？

最主要的一個原因就是備援，它包含三個方面

• 編碼備援：比如一個圖中隻有 4 種顔色，對每個顔色卻使用 8bit 進行編碼
• 空間備援：比如圖中有大量重複部分，對于這部分如果重複存儲而不做任何壓縮，圖檔的體積會變得非常大。
• 無關：比如一張純色圖，隻有一個值就足夠了，但其中卻出現了許多類似于噪音的值，這時，這些值純色圖來說就是噪音了。

圖像壓縮的流程

JPEG 壓縮

JPEG 整個壓縮過程基本上是遵循這個步驟：

1. 把資料分為“重要部分”和“不重要部分”
2. 濾掉不重要的部分
3. 儲存

步驟一：圖像分割

JPEG 算法的第一步，圖像被分割成大小為 8X8 的小塊

步驟二：顔色空間轉換 RGB->YCbCr

在 JPEG 壓縮算法中，需要把圖案轉換成為 YCbCr 模型，這裡的 Y 表示亮度 (Luminance)，Cb 和 Cr 分别表示綠色和紅色的“色內插補點”。

“色差”這個概念起源于電視行業，最早的電視都是黑白的，那時候傳輸電視信号隻需要傳輸亮度信号，也就是 Y 信号即可，彩色電視出現之後，人們在 Y 信号之外增加了兩條色差信号以傳輸顔色資訊，這麼做的目的是為了相容黑白電視機，因為黑白電視隻需要處理信号中的 Y 信号即可。

有損壓縮首先要做的事情就是“把重要的資訊和不重要的資訊分開”，YCbCr 恰好能做到這一點。對于人眼來說，圖像中明暗的變化更容易被感覺到，這是由于人眼的構造引起的

步驟四：DCT 變換

K-L變換：将能量集中于左上方，效果好，但依賴于圖像本身

DCT變換：變換有一個固定的矩陣，有固定的系數，是以是通用的

DCT變換的數學原理

變換用連續的圖像表達式 f(x,y) 來解釋，我們有一張圖像，記之為 f(x,y)，新的變換域記為 T(u,v) （T(u，v)為變換系數）

兩個函數 r 和 s ,其中的 r(x,y,u,v)和s(x,y,u,v)也被稱作是基函數或者是基圖像。理想化情況下r和s會使均方誤差極小。對于K-L變換，這些系數r(x,y,u,v)完全依賴于圖像，不僅依賴于所取的位置，還依賴于你圖像上實際的灰階值。是以我們使用DCT來代替，DCT中 r 和 s 為：

我們是在試着将 n×n 大小的小圖像，分解成這些基函數的線性組合。如果是純色圖像，這裡的T(u,v) 隻要 u和v 的值都為0即可。如果圖像中變化頻繁，那麼就需要一些系數，如T(3,3)。這樣，每一個 T(u,v)，都會被描述為有多少這樣的部分組成，現在我們已經用此類圖像的線性組合來表示 n × n 的圖像了。

DCT變換的具體例子

在 JPEG 壓縮過程中，經過顔色空間的轉換，每一個 8X8 的圖像塊，在資料上表現為 3 個 8X8 的矩陣，緊接着我們對這三個矩陣做一個二維的 DCT 轉換，由于圖像本身的連貫性，一個 8X8 的圖像中的數值一般不會出現大的跳躍，經過 DCT 轉換會有類似的效果，左上角的直流分量儲存了一個大的數值，其他分量都接近于 0

可以看到，資料經過 DCT 變化後，被明顯分成了直流分量和交流分量兩部分，為後面的進一步壓縮起到了充分的鋪墊作用，可以說是整個 JPEG 中最重要的一步，後面我們會介紹資料量化。

由于已經明确每次進行離散餘弦變化的矩陣大小為8*8，故這裡不再采用上述方法進行離散餘弦變換，而是利用DCT變換矩陣實作DCT變換以降低運算量。

(使用 Image Processing Toolbox™ 軟體有兩種計算 DCT 的方法。第一種方法是使用 dct2 函數。dct2 使用基于 FFT 的算法對大型輸入實作快速計算。第二種方法是使用 DCT 變換矩陣，該矩陣由函數 dctmtx 傳回，對于小型方陣輸入（如 8×8 或 16×16）可能更高效)

為什麼選擇離散餘弦變換？

第一，其實在一些特定情況下，離散餘弦變換完全等同于卡洛南-洛伊變換。這些特例中的圖像，其像素排列符合馬爾可夫鍊，即每個像素都以一種特殊的形式，依賴于相鄰像素，然後相鄰像素也是如此。 這就是所謂的一階馬爾可夫圖像源（ Markovian）。如果可以假設一張這樣的圖像，就可以證明卡洛南-洛伊變換最終就是離散餘弦變換

第二，為什麼不用傅裡葉變換之類的方法呢？ 因為離散傅裡葉變換對周期性有一個潛在的假設，假設圖像如下圖一樣在自我重複。這個假設适用于每個方向，以及整個二維平面。也就是說，我們需要一個小塊中第一個像素，與下一個小塊中的第一個像素（n個之後的像素）完全相同，這就是潛在的假設。但是這種假設存在的可能性很低。

然而，離散餘弦變換對周期性所作的假設是不同的，離散餘弦變換假設邊界處有鏡面對稱，如下圖，即是說圖像是在重複，但是翻折了。這個假設是說，假定這裡的像素與相鄰的這個像素類似，不是說像素與八個像素之後的那一個相同，而是與緊接着它的那個像素相同。這個假設更合理，這就是我們選用離散餘弦變換的兩個原因。其一是對一類圖像而言，進行離散餘弦變換就是在進行卡洛南-洛伊變換。其二是周期性，在我們從 n × n 或 8 × 8 小塊開始處理圖像時，離散餘弦變換對周期性的假設更為實用。

步驟五:量化

經過顔色空間轉換和離散餘弦變換，每一個8X8的圖像塊都變成了三個8X8的浮點數矩陣，分别表示Y,Cr,Cb資料。 我們的問題是，在可以損失一部分精度的情況下，如何用更少的空間存儲這些浮點數？答案是使用量子化（ Quantization ），簡稱量化

在JPEG中采用的均勻量化的方法，有落在某一區間的數，都可以用這個區間對應的縱坐标來表示，我們之後要開始哈夫曼編碼，我們現在把一個區間上的所有點用一個數來代替，就可以增大這個數出現的機率

其中G是我們需要處理的圖像矩陣，Q稱作量化系數矩陣（Quantization matrices），JPEG算法提供了兩張标準的量化系數矩陣，分别用于處理亮度資料Y和色差資料Cr以及Cb。

比如上面資料，以左上角的-415.38為例，對應的量子化系數是16，那麼round(-415.38/16)=round(-25.96125)=-26。

矩陣的量化還有最後一步要做，就是把量化後的二維矩陣轉變成一個一維數組，以友善後面的霍夫曼壓縮，但在做這個順序轉換時，需要按照一個特定的取值順序。

這麼做的目的隻有一個，就是盡可能把0放在一起，由于0大部分集中在右下角，是以才去這種由左上角到右下角的順序。

後面的工作就是對這個數組進行再一次的哈夫曼壓縮，已得到最終的壓縮資料

無損預測壓縮

這麼做的目的隻有一個，就是盡可能把0放在一起，由于0大部分集中在右下角，是以才去這種由左上角到右下角的順序。

後面的工作就是對這個數組進行再一次的哈夫曼壓縮，已得到最終的壓縮資料

感謝以下部落格的幫助：

JPEG算法解密（二）

數字圖像處理（岡薩雷斯第三版）學習筆記