大家耳熟能詳的 JPG,背後有許多值得令人學習的壓縮技巧,看到前人們用各種聰明的 Engineering 技巧將圖片壓縮,會覺得能活在這個世代實在太棒了。
JPEG 其實嚴格來說並不是一種檔案格式,而是一種演算法。檔案的格式則是由 JFIF 所規範的。
首先我們先從 JPEG 的顏色儲存方式開始。一般來說我們會用光的三原色 R、G、B 來表示各種顏色,但科學家們發現,人類對亮度的變化比顏色變化敏感很多。
為了善用這個人類與生俱來的特色,我們想要盡可能減少顏色的訊息量,多用亮度的變化來表示。在影像處理當中常常採用 YCrCb 來表示顏色。
其中,
Y
為亮度Cr
為紅色通道Cb
為藍色通道那麼 G 到哪去了呢?答案是丟掉了。實際上是丟掉了,然而就算丟失一部分的訊息,由於人眼對顏色變化較為不敏感的特性,即時丟失掉一部分的訊息也不會有太明顯的變化。
從 YCrCb 轉為 RGB 的公式為:
如果說 JPEG 有什麼演算法讓圖片可以神奇地被壓縮,那麼背後最重要的功臣就是離散餘弦轉換。為什麼圖片可以被壓縮,又跟離散餘弦轉換有什麼關係?
為了簡化並讓離散餘弦轉換更容易理解,先用 1D 陣列當作範例。如果我們將圖片當作信號來看,以像素灰階值當作 y 軸高度的話,可以這樣表示:
離散餘弦轉換的公式是這樣的:
把圖片當作信號來看有什麼好處?就跟其他訊號一樣,我們可以對它做處理。例如,透過線性轉換後,我們可以找到低頻或高頻的信號。
直接看看經過處理後會變什麼樣子:
對於這個公式,我們可以把轉換後的訊號可以解讀成
cos 的各個頻率分別在圖片中佔多少比例
或者也可以想成,「任何圖片都可以被當作不同頻率的餘弦波合成」。人類來說低頻才是對組成圖片重要的信號,我們大可以將原信號的高頻係數降低,甚至調整為 0,也不會影響原圖太多。
既然可以調整為 0
,那麼就不需要額外的空間了!
2D 的離散餘弦轉換公式較為複雜,但背後原理仍然相同。圖片會先拆成 8x8 的小區塊並轉換成 DCT 係數。
如果直接保存 DCT 的係數矩陣,那麼原圖並沒有任何壓縮。
在實務上會將 DCT 與一個量化表相乘,會得到一個新的 DCT 係數矩陣,這個係數矩陣大部分高頻的係數為零。JPG 演算法會將圖片拆分為數個 8x8 的小區塊,並在這些小區塊間計算 DCT。
在選擇壓縮率的時候,量化表裡頭的係數也會不同。如果沒有壓縮,那麼量化表裡頭的元素都會是 1
(圖片的每個像素都保留)。
DCT 係數矩陣和量化表相乘之後,高頻的部分大部分的元素都是 0
。矩陣的左上方是低頻、越往右下則越高頻。為了將低頻的數字放到前面,在壓縮圖片檔時會以下圖的方式走訪。
舉例來說,如果和量化表相乘後的矩陣是這樣:
那麼實際在編碼時會把它變成:
[4, 5, 1, 1, 3, 6, 9, 5, 0, 0, 0, 0, 0, 0, 0, 0]
這是為了之後的壓縮方便。
霍夫曼編碼是一個無損數據壓縮的演算法,可以很有效地將字串編碼。在 JPG 編碼的時候,會有一大部分的元素是 0
,霍夫曼編碼能夠將出現頻率高的字母使用較短的編碼,頻率低的字母則使用較長的編碼。在 JPG 當中,DCT 矩陣會經過霍夫曼編碼後儲存。
霍夫曼編解碼的詳細原理,由於篇幅關係就不詳細展開,可以到實作的程式碼參考。
解碼 JPEG 的過程如下:
以下是簡易的 JavaScript 實作,有很多部分是參考這篇文章(Understanding and Decoding a JPEG Image using Python),可以在 Codepen 看到完整程式碼,將解碼後的結果渲染到 canvas。
注意這邊不是用 putImageData
,而是直接讀取 JPG 檔案的內容後一格一格渲染到 canvas 上。(當然,在實際開發中我們不會這麼做)
function parseJPG(data) {
const hfTables = {};
const quantizationTables = {};
let quantMapping;
let d = new Uint8Array(data);
let w;
let h;
while (true) {
const marker = new Uint8Array(d.slice(0, 2));
// console.log(marker[0].toString(16), marker[1].toString(16));
if (marker[0] === 0xff && marker[1] === 0xd8) {
console.log("start of image");
d = d.slice(2);
} else if (marker[0] === 0xff && marker[1] === 0xd9) {
console.log("end of image");
return;
} else {
const lenchunk = d.slice(2, 4);
let len = (lenchunk[0] << 8) + lenchunk[1] + 2;
const chunk = d.slice(4, len);
if (marker[0] === 0xff && marker[1] === 0xc4) {
// console.log(d, chunk);
const { table, header } = decodeHuffman(chunk);
hfTables[header] = table;
} else if (marker[0] === 0xff && marker[1] === 0xdb) {
const { header, table } = buildQuantizationTables(chunk);
quantizationTables[header] = table;
} else if (marker[0] === 0xff && marker[1] === 0xc0) {
// start of frame
const { result, width, height } = baseDCT(chunk);
quantMapping = result;
w = width;
h = height;
} else if (marker[0] === 0xff && marker[1] === 0xda) {
// console.log(quantMapping, quantizationTables);
len = startOfScan({
data: d,
hdrlen: len,
width: w,
height: h,
quantizationTables,
quantMapping,
hfTables,
});
}
d = d.slice(len);
}
if (d.length === 0) {
break;
}
}
JPG 檔案裡有很多區塊,區塊之間以一個 0xff
的標記符來識別:
0xffc4
為霍夫曼編碼表0xffda
為 start of scan0xffdb
為量化表0xffd8
為 JPG 的檔案開頭標記符0xffd9
為 JPG 的檔案結尾標記符先將 binary 轉為對應的資料(霍夫曼編碼表、量化表)後再做對應計算就可以得到矩陣了!
測試之後發現沒辦法成功解碼,應該是程式碼有問題,如果有看實作的話,可以發現計算其實還蠻煩瑣的。由於時間不夠這邊就先丟出來給大家參考~
(上面似乎有渲染到正確的顏色,但剩下的部分都綠綠的)
在實際應用上,GPU 或是 CPU 都有圖片編解碼的電路,通常不用另外寫程式去處理。然而 JPG 背後的演算法結合了離散餘弦轉換、霍夫曼編碼、zig-zag 走訪,成功減少了圖片的儲存空間。我很喜歡這種平時視為理所當然的事情,深入研究之後才發現有很多值得令人學習的知識。