iT邦幫忙

2023 iThome 鐵人賽

DAY 6
0

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

JPEG

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

YCrCb

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

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

其中,

  • Y 為亮度
  • Cr 為紅色通道
  • Cb 為藍色通道

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

從 YCrCb 轉為 RGB 的公式為:

  • Y = 0.29900×R + 0.58700×G + 0.11400×B
  • Cb = −0.16874×R − 0.33126×G + 0.50000×B
  • Cr = 0.50000×R − 0.41869×G − 0.081×B

離散餘弦轉換

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

圖片中的高頻與低頻

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

Yes

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

day6-1

把圖片當作信號來看有什麼好處?就跟其他訊號一樣,我們可以對它做處理。例如,透過線性轉換後,我們可以找到低頻或高頻的信號。

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

Yes

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

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

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

既然可以調整為 0,那麼就不需要額外的空間了!

2-D 離散餘弦轉換

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

img

Qauntitation Table

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

在實務上會將 DCT 與一個量化表相乘,會得到一個新的 DCT 係數矩陣,這個係數矩陣大部分高頻的係數為零。JPG 演算法會將圖片拆分為數個 8x8 的小區塊,並在這些小區塊間計算 DCT。

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

Zig-zag

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

img

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

day6-2

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

[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 走訪,成功減少了圖片的儲存空間。我很喜歡這種平時視為理所當然的事情,深入研究之後才發現有很多值得令人學習的知識。


上一篇
[Day5] Seam Carving – 讓圖片不成比例地縮小
下一篇
[Day7] 與程式有關的遊戲精選 (1) – A=B
系列文
從電子元件到傅立葉轉換 - 那些我有興趣的主題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言