JPEG 壓縮背後的秘密 — 離散餘弦轉換

（本篇文章源自2023 iThome 鐵人賽）

大家耳熟能詳的 JPG，背後有許多值得令人學習的壓縮技巧，看到前人們用各種聰明的 Engineering 技巧將圖片壓縮，會覺得能活在這個世代實在太棒了。

JPEG

JPEG 其實嚴格來說並不是一種檔案格式，而是一種演算法。檔案的格式則是由 JFIF（JPEG File Interchange Format）所規範的。

YCbCr

首先我們先從 JPEG 的顏色儲存方式開始。一般來說我們會用光的三原色 R、G、B 來表示各種顏色，但科學家們發現，人類對亮度的變化比顏色變化敏感很多。

為了善用這個人類與生俱來的特色，我們想要盡可能減少顏色的訊息量，多用亮度的變化來表示。在影像處理當中常常採用 YCbCr 來表示顏色。

其中：

• Y 為亮度（Luminance）
• Cr 為紅色色度通道（Chrominance Red）
• Cb 為藍色色度通道（Chrominance Blue）

那麼 G 到哪去了呢？答案是丟掉了。然而就算丟失一部分的訊息，由於人眼對顏色變化較為不敏感的特性，即使丟失掉一部分的訊息也不會有太明顯的變化。

從 RGB 轉為 YCbCr 的公式為：

$$Y = 0.299R + 0.587G + 0.114B$$ $$Cb = -0.169R - 0.331G + 0.500B$$ $$Cr = 0.500R - 0.419G - 0.081B$$

離散餘弦轉換（DCT）

如果說 JPEG 有什麼演算法讓圖片可以神奇地被壓縮，背後最重要的功臣就是離散餘弦轉換（Discrete Cosine Transform）。

圖片中的高頻與低頻

為了簡化並讓離散餘弦轉換更容易理解，先用 1D 陣列當作範例。如果我們將圖片當作信號來看，以像素灰階值當作 y 軸高度的話，可以把每一行像素視為一段訊號。

把圖片當作信號來看有什麼好處？就跟其他訊號一樣，我們可以對它做頻域分析。透過線性轉換後，我們可以找到低頻或高頻的成分。

對於轉換後的訊號，我們可以解讀成：

cos 的各個頻率分別在圖片中佔多少比例

或者也可以想成，「任何圖片都可以被當作不同頻率的餘弦波合成」。對人類來說低頻才是組成圖片的重要信號，我們大可以將原信號的高頻係數降低，甚至調整為 0，也不會影響原圖太多。

既然可以調整為 0，那麼就不需要額外的空間了！這就是 JPEG 壓縮的核心概念。

2D 離散餘弦轉換

2D 的離散餘弦轉換公式較為複雜，但背後原理仍然相同。圖片會先拆成 8×8 的小區塊並轉換成 DCT 係數。

2D DCT 的公式為：

$$F(u,v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x,y) \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16}$$

其中 $C(k) = \frac{1}{\sqrt{2}}$ 當 $k = 0$，否則 $C(k) = 1$。

公式看起來蠻可怕的，但原理是在問：「這個 8×8 的圖塊，長得像哪些基底圖案？像多少？」

DCT 係數 F(u,v) 就是把原圖和這張基底圖案做內積（dot product）——「這張圖跟這個花紋有多像？」像的程度越高，係數越大，權重更高。

互動：DCT 視覺化

下面的互動工具包含了 64 個 DCT 基底圖案的視覺化——每個 (u, v) 對應一種頻率組合。左上角 (0,0) 是 DC 分量（平均亮度），越往右下角頻率越高。

可以看到哪些基底圖案在壓縮時會被保留（亮的）或丟棄（暗的），數字代表 zig-zag 掃描的順序。

上傳一張圖片後，可以實際看到 DCT 轉換的結果，以及在不同壓縮程度下重建的圖片。

量化表（Quantization Table）

如果直接保存 DCT 的係數矩陣，那麼原圖並沒有任何壓縮。

在實務上會將 DCT 係數除以一個量化表的值，再四捨五入到最近的整數。這個過程會得到一個新的 DCT 係數矩陣，大部分高頻的係數會因為量化而歸零。JPG 演算法會將圖片拆分為數個 8×8 的小區塊，並在這些小區塊間計算 DCT。

在選擇壓縮率的時候，量化表裡頭的係數也會不同。如果沒有壓縮，那麼量化表裡頭的元素都會是 1（圖片的每個像素都保留）。

Zig-zag 走訪

DCT 係數矩陣和量化表相除之後，高頻的部分大部分的元素都是 0。矩陣的左上方是低頻、越往右下則越高頻。為了將低頻的數字放到前面，在壓縮圖片檔時會以 zig-zag 的方式走訪矩陣。

舉例來說，如果量化後的矩陣是這樣：

4 5 1 0
1 3 0 0
6 0 0 0
0 0 0 0

那麼實際在編碼時會把它變成：

[4, 5, 1, 1, 3, 6, 9, 5, 0, 0, 0, 0, 0, 0, 0, 0]

後面連續的零就可以被高效地壓縮。

霍夫曼編碼（Huffman Coding）

霍夫曼編碼是一個無損數據壓縮的演算法，可以很有效地將資料編碼。在 JPG 編碼的時候，會有一大部分的元素是 0，霍夫曼編碼能夠將出現頻率高的符號使用較短的編碼，頻率低的符號則使用較長的編碼。在 JPG 當中，DCT 矩陣經過量化和 zig-zag 走訪後，會再經過霍夫曼編碼儲存。

實際解碼 JPEG

解碼 JPEG 的過程基本上就是把上面的步驟倒過來：

1. 將檔案中的霍夫曼編碼表取出，解碼資料
2. 將 zig-zag 排列還原為 8×8 矩陣
3. 將 DCT 係數乘上量化表，得到近似的 DCT 係數
4. 計算逆 DCT（IDCT），還原出像素值
5. 將 YCbCr 轉換為 RGB

JPG 檔案裡有很多區塊，區塊之間以 0xff 的標記符來識別：

• 0xffd8 — JPG 的檔案開頭標記符（SOI）
• 0xffc0 — Start of Frame，包含圖片寬高等資訊
• 0xffc4 — 霍夫曼編碼表（DHT）
• 0xffdb — 量化表（DQT）
• 0xffda — Start of Scan，實際的影像資料
• 0xffd9 — JPG 的檔案結尾標記符（EOI）

以下是解析 JPG marker 的簡易 JavaScript 實作：

function parseJPG(data) {
  const hfTables = {}
  const quantizationTables = {}
  let quantMapping
  let d = new Uint8Array(data)
  let w, h

  while (d.length > 0) {
    const marker = d.slice(0, 2)

    if (marker[0] === 0xff && marker[1] === 0xd8) {
      d = d.slice(2) // SOI
      continue
    }

    if (marker[0] === 0xff && marker[1] === 0xd9) {
      break // EOI
    }

    const len = (d[2] << 8) + d[3] + 2
    const chunk = d.slice(4, len)

    switch (marker[1]) {
      case 0xc4: { // DHT
        const { table, header } = decodeHuffman(chunk)
        hfTables[header] = table
        break
      }
      case 0xdb: { // DQT
        const { header, table } = buildQuantizationTables(chunk)
        quantizationTables[header] = table
        break
      }
      case 0xc0: { // SOF
        const { result, width, height } = baseDCT(chunk)
        quantMapping = result
        w = width
        h = height
        break
      }
      case 0xda: { // SOS
        startOfScan({ data: d, hdrlen: len, width: w, height: h,
          quantizationTables, quantMapping, hfTables })
        break
      }
    }

    d = d.slice(len)
  }
}

後記

在實際應用上，GPU 或是 CPU 都有圖片編解碼的電路，通常不用另外寫程式去處理。然而 JPG 背後的演算法結合了離散餘弦轉換、霍夫曼編碼、zig-zag 走訪，成功減少了圖片的儲存空間。

我很喜歡這種平時視為理所當然的事情，深入研究之後才發現有很多值得令人學習的知識。JPEG 壓縮讓我們每天可以在網路上傳送數以億計的圖片，而這一切背後是數學、資訊理論和人類視覺特性的完美結合。