JPGと離散コサイン変換

誰もがよく知るJPGだが、その裏には学ぶべき圧縮の技術が数多く隠されている。先人たちが賢明なエンジニアリングの工夫を凝らして画像を圧縮してきたのを見ると、この時代に生きられて本当によかったと思えてくる。

JPEG

厳密に言えば、JPEGはファイル形式ではなく、アルゴリズムの一種である。ファイル形式そのものはJFIFによって規定されている。

まずはJPEGにおける色の保存方法から見ていこう。

科学者たちは、人間が色よりも輝度の変化に対してはるかに敏感であることを発見した。そのため、色空間を選択する際には輝度を分離して保存できるYCrCb（YCbCr）が用いられる。

離散コサイン変換

JPEGにおいて画像を魔法のように圧縮できるアルゴリズムがあるとしたら、その最大の立役者は離散コサイン変換（DCT）である。なぜ画像は圧縮できるのか、そしてそれは離散コサイン変換とどう関係しているのだろうか？

画像における高周波と低周波

離散コサイン変換を単純化して理解しやすくするために、まずは1次元配列を例として考えてみよう。画像を信号として捉え、ピクセルのグレースケール値を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次元離散コサイン変換

2次元の離散コサイン変換の公式はさらに複雑になるが、基本的な原理は同じである。画像はまず8×8の小さなブロックに分割され、DCT係数へと変換される。

Quantization Table（量子化テーブル）

DCTの係数行列をそのまま保存しただけでは、元の画像は一切圧縮されない。実際には、DCT係数行列と量子化テーブルを掛け合わせる（要素ごとに除算する）ことで新しいDCT係数行列が得られ、この係数行列の高周波成分の多くはゼロになる。JPGアルゴリズムは画像を複数の8×8のブロックに分割し、それぞれのブロックに対して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上に1マスずつレンダリングしている（当然ながら、実際の開発でこのような方法は取らない）。

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ファイルの開始マーカー（SOI）
0xffd9 はJPGファイルの終了マーカー（EOI）

バイナリを対応するデータ（ハフマンテーブル、量子化テーブル）に変換した上で計算を行えば、行列が得られる。

テストしてみたところ正常にデコードできなかったため、コードに問題があるようだ。実装を見てもらえればわかるが、計算処理はかなり煩雑である。時間が足りなかったため、ここでは参考用としてひとまず公開しておく。

failture

（上部は正しい色でレンダリングされているようだが、残りの部分が全体的に緑がかってしまっている）

あとがき

実際のアプリケーションでは、GPUやCPUに画像エンコード・デコード用の専用回路が備わっており、通常はわざわざ自前で処理コードを書く必要はない。しかし、JPGの裏にあるアルゴリズムは離散コサイン変換、ハフマン符号化、ジグザグ走査を組み合わせることで、画像の保存容量を見事に削減している。普段当たり前のように使っている技術でも、深く掘り下げてみると学べる知識がたくさんある。僕にとって、そうした探求はとても楽しいものだ。

カテゴリー

ページ

その他