JPG 與離散餘弦轉換

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

JPEG

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

首先我們先從 JPEG 的顏色儲存方式開始。

科學家們發現，人類對亮度的反應比顏色敏感很多，因此在選擇顏色空間時，會使用 YCrCb 來儲存，將亮度。

離散餘弦轉換

如果說 JPEG 有什麼演算法讓圖片可以神奇地被壓縮，那麼背後最重要的功臣就是離散餘弦轉換。為什麼圖片可以被壓縮，又跟離散餘弦轉換有什麼關係？

圖片中的高頻與低頻

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

把圖片當作信號來看有什麼好處？就跟其他訊號一樣，我們可以對它做處理，在數學上，信號可以用多項式。

離散餘弦轉換的公式是這樣的：

X_{k} = \sum_{k=0}^{n-1} x_k \cos \left[\frac{\pi}{n} m \left(k+\frac{1}{2}\right) \right]

直接看看經過處理後會變什麼樣子：

對於這個公式，我們可以把轉換後的訊號可以解讀成

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

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

2-D 離散餘弦轉換

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

Qauntitation Table

如果直接保存 DCT 的係數矩陣，那麼原圖並沒有任何壓縮。在實務上會將 DCT 與一個量化表相乘，會得到一個新的 DCT 係數矩陣，這個係數矩陣大部分高頻的係數為零。JPG 演算法會將圖片拆分為數個 8x8 的小區塊，並在這些小區塊間計算 DCT。

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

Zig-zag

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

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

\begin{bmatrix} 4 & 5 & 6 & 9 \\ 1 & 3 & 5 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}

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

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

這是為了之後的壓縮方便。

霍夫曼編碼

霍夫曼編碼是一個無損數據壓縮的演算法，可以很有效地將字串編碼。在 JPG 編碼的時候，會有一大部分的元素是 0，霍夫曼編碼能夠將出現頻率高的字母使用較短的編碼，頻率低的字母則使用較長的編碼。在 JPG 當中，DCT 矩陣會經過霍夫曼編碼後儲存。

實際解碼 JPEG

解碼 JPEG 的過程如下：

將檔案中的霍夫曼編碼表取出
將檔案中的 DCT 係數矩陣取出
將計算 DCT 逆矩陣後乘上量化表係數，得到圖片該處的像素
將 YCbCr 轉換為 RGB

以下是簡易的 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 scan
0xffdb 為量化表
0xffd8 為 JPG 的檔案開頭標記符
0xffd9 為 JPG 的檔案結尾標記符

先將 binary 轉為對應的資料（霍夫曼編碼表、量化表）後再做對應計算就可以得到矩陣了！

測試之後發現沒辦法成功解碼，應該是程式碼有問題，如果有看實作的話，可以發現計算其實還蠻煩瑣的。由於時間不夠這邊就先丟出來給大家參考～

failture

（上面似乎有渲染到正確的顏色，但剩下的部分都綠綠的）

後記

在實際應用上，GPU 或是 CPU 都有圖片編解碼的電路，通常不用另外寫程式去處理。然而 JPG 背後的演算法結合了離散餘弦轉換、霍夫曼編碼、zig-zag 走訪，成功減少了圖片的儲存空間。我很喜歡這種平時視為理所當然的事情，深入研究之後才發現有很多值得令人學習的知識。

Kalan's Blog