JPG 與離散餘弦轉換

皆さんがよく知っているJPGの背後には、多くの学ぶべき圧縮技術があります。先人たちが様々な巧妙なEngineering技術を用いて画像を圧縮するのを見ていると、この時代に生きていることが本当に素晴らしいと感じます。

JPEG

JPEGは厳密にはファイル形式ではなく、アルゴリズムです。ファイル形式はJFIFによって規定されています。

まず、JPEGの色の保存方法から始めましょう。

科学者たちは、人間が明度に対して色よりも敏感であることを発見しました。したがって、色空間を選択する際には、YCrCbを使用して明度を保存します。

離散コサイン変換

JPEGに画像を驚くべき方法で圧縮させるアルゴリズムがあるとすれば、最も重要な功労者は離散コサイン変換です。画像がなぜ圧縮できるのか、そしてそれが離散コサイン変換とどのように関連しているのかを見ていきましょう。

画像の高周波と低周波

離散コサイン変換を簡略化し、理解しやすくするために、1D配列を例に考えます。画像を信号と見なすと、ピクセルのグレースケール値をy軸の高さとした場合、次のように表現できます：

画像を信号として見る利点は何でしょうか？他の信号と同様に、信号に対して処理を行うことができます。数学的には、信号は多項式で表現できます。

離散コサイン変換の公式は次のようになります：

処理後にどのようになるかを直接見てみましょう：

この公式に対して、変換後の信号は次のように解釈できます。

cosの各周波数が画像内でどのくらいの割合を占めているか

または「任意の画像は異なる周波数のコサイン波の合成と見なせる」と考えることもできます。人間にとっては低周波が求める信号です。元の信号の高周波係数を下げても、あるいは0に調整しても、元の画像にはあまり影響しません。

2-D 離散コサイン変換

2Dの離散コサイン変換の公式はより複雑ですが、原理は同じです。画像はまず8x8の小さなブロックに分割され、DCT係数に変換されます。

量子化テーブル

DCTの係数行列をそのまま保存すると、元の画像は圧縮されていません。実際にはDCTと量子化表を掛け算して、新しいDCT係数行列を得ます。この係数行列の大部分は高周波の係数がゼロになります。JPGアルゴリズムは画像を複数の8x8の小ブロックに分割し、これらの小ブロック間でDCTを計算します。

圧縮率を選択する際、量子化表の係数も異なります。圧縮しない場合、量子化表の要素はすべて1（画像の各ピクセルを保持）になります。

Zig-zag

DCT係数行列と量子化表を掛け算した後、高周波部分の要素はほとんどが0になります。行列の左上には低周波があり、右下に行くほど高周波になります。低周波の数値を前に持ってくるために、画像ファイルを圧縮する際には次のように走査します。

例えば、量子化表と掛け算した後の行列が次のようであるとします：

実際にエンコードの際には次のようになります：

[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ファイルの内容を直接読み込み、1ピクセルずつ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はスキャンの開始
• 0xffdbは量子化表
• 0xffd8はJPGファイルの開始マーカー
• 0xffd9はJPGファイルの終了マーカー

まずバイナリを対応するデータ（ホフマン符号化表、量子化表）に変換し、その後に計算を行うことで行列を得ることができます！

テストの結果、正常にデコードできないことが分かりました。おそらくコードに問題があると思います。実装を見れば計算がかなり面倒であることがわかります。時間が足りないため、ここで一旦皆さんに参考として提示します～

（上記には正しい色が表示されているようですが、残りの部分は緑色になっています）

後記

実際のアプリケーションでは、GPUやCPUには画像のエンコーディングとデコーディングの回路があり、通常は別途プログラムを書く必要はありません。しかし、JPGの背後にあるアルゴリズムは、離散コサイン変換、ホフマン符号化、Zig-zag走査を組み合わせることで、画像の保存スペースを大幅に削減しています。普段当たり前に思えることを深く研究すると、学ぶべき多くの知識があることに気づきます。