通識版 JPEG

為了讓多一點人認為這個 blog 有意義，我來寫一篇簡化的 JPEG 通識介紹好了 XD。

JPEG 是一種允許失真的圖片壓縮格式，但是它捨去的資訊是我們不太注意得到的，所以既能達到很好的壓縮效果（一般可以壓到原本的 1/10 左右），看起來又不會有明顯的差異。壓縮過程就是從電腦習慣的表達形式轉換為另一種「突顯較重要資訊」的形式，然後把不重要的部份丟掉。

一般我們都用 RGB 三個向度表達一個點的顏色，即紅、綠、藍三個顏色的混合。一張圖片就可視為紅、綠、藍三塊色版的疊合。

JPEG 壓縮的第一步是把每個色點的 RGB 值換成另一種形式 YCbCr，其中 Y 是亮度資訊，Cb 和 Cr 是彩度資訊。據說人對於亮度比較敏感，對於彩度就沒那麼敏感，所以對於 Cb 和 Cr 色版我們可以模糊處理，幾個鄰近色點視為同一個顏色就好。例如我們把一個 2x2 的方塊看成同一個顏色（即縮成一個點）的話，Cb 和 Cr 色版的資訊量馬上就減少為 1/4！

接下來這一步更厲害，是傳說中的 discrete cosine transform。我們先把一個色版分割為一堆 8x8 的方塊，然後對每個方塊套用 DCT。

一個 8x8 方塊經過 DCT 之後仍然是一個 8x8 方塊，但每個點的意義就不一樣了：一個點的值是某個對應頻率的振幅，偏左上角的點對應的變化頻率較低，愈往右下角對應的變化頻率較高。上圖顯示各點對應的頻率，最左上角的點會影響整個方塊，其下的點主要影響方塊的上半部，再下面一點主要影響方塊的上緣和下緣，依此類推。其中最左上角的點最為重要，我們稱之為 DC 值，其餘稱為 AC 值。經過 DCT 的 8x8 方塊可以透過 inverse transform 轉回原來的 8x8 方塊。（學過線性代數的人就知道 DCT 是從標準基底換到另外一組基底。）同樣地，據說人對於低頻變化比較敏感（例如變動 DC 就會變動整個方塊），對於高頻變化比較不敏感，所以我們可以模糊處理偏右下角的值。而且因為經過 DCT 之後，振幅會非常顯著地集中到左上角，所以我們往往可以只保留左上角一小部份的值，其餘捨棄，整張圖的大小可以縮減好幾倍。這一步的壓縮效果是最顯著的。

最後一步是用 Huffman coding、predictive coding、和 run-length coding 等無失真編碼技巧進一步壓縮。Huffman coding 根據符號的出現頻率給予不同長度的 bit patterns 加以編碼，能達到接近理論上最佳的壓縮效果。Predictive coding 則是針對「DC 值是整個方塊的平均值」以及「相鄰兩個方塊的平均值應該相差不遠」的特性，改而編碼兩方塊間的差值（cf. FTC!!）。因為差值會集中在絕對值較小的區間，這會使 Huffman coding 的壓縮效果更好。AC 的部份因為被我們模糊處理甚至捨棄，會產生很多 0，而很多 0 接在一起的時候，我們就不要說 0000000000000000，說「16 個 0」就好，這就是 run-length coding 的概念。把這三種手法融合起來，又可以把資料量再壓下一些。

以上是最基本的 JPEG 壓縮簡介，解碼的時候就是反著做回去嘍。

--
JPEG 還有更複雜的版本，不過我就放棄啦…