初心者プログラマのデバッグ日常

プログラミング歴2年の初心者が勉強したことなどについて記す

JPEGエンコードの手順

大学が忙しく随分間が空いてしまいましたがJPEGについて続きを書いていこうと思います。

今回は具体的なエンコード時の手順についてザックリと説明したいと思います。

それぞれの詳細はまた次の記事で触れます。

手順

  1. RGB形式の画像であればYCbCr形式に変換する
  2. 画像の縦横のピクセル数を16の倍数になるように端を処理する
  3. サンプリング
  4. 8*8のブロックごとにDCT変換を行う
  5. 量子化する
  6. ランレングス+ハフマン符号化

以上のようにエンコードでは大きく分けて6つの手順があります。

実際にはファイル出力のためにヘッダを作成したりする部分もありますが、JPEGの本質的なアルゴリズムではないので今回は省き、またデータ構造の部分で説明します。

 

それでは順に軽く見ていきましょう。

 

1.YCbCr形式

一般的な画像ファイルの場合各ピクセルの赤・緑・青の値を0~255で表現するRGB形式が多いと思います。しかしJPEGではYCbCrと呼ばれる形式を使います。これはY:輝度・Cb:青方向の色相・Cr:赤方向の色相で表現する形式です。具体的な変換方法は以下の式を用います。

 

{ \displaystyle Y = 0.2990 * R + 0.5870 * G + 0.1140 * B - 128 } { \displaystyle C_b = - 0.1687 * R - 0.3313 * G + 0.5000 * B } { \displaystyle C_r = 0.5000 * R - 0.4187 * G - 0.0813 * B }

 この式の詳細はおそらく情報科学の範疇ではないと思われるので僕は調べていません。気になる方は是非調べてみてください。

 

2.画像の端を処理する

今回は次で説明するサンプリングで4:2:0というサンプリングを行うつもりなので、16*16のピクセルを1ブロックとしてエンコード処理で使います。しかしエンコード前の画像の縦横のピクセル数はバラバラ。16の倍数になってないこともあります。その場合16*16のブロックから漏れてしまった部分はエンコードできません。そこで16の倍数になるように画像の右と下にピクセルを拡張します。この時の拡張したピクセルのYCbCrの数値は特に規定はありませんが、DCT変換の都合で拡張する前に画像の端だった部分の数値を引き継ぐと良いようです。

f:id:gaise:20170719123142p:plain

この図では3*3を5*5に拡張する際の端の処理について説明しています。左ではなかった赤い文字の部分が拡張されたピクセルです。

3.サンプリング

サンプリングでは各ピクセルの情報を間引きます。この時に人間が輝度の劣化に比べ色相の劣化に鈍感であるという特徴を利用します。具体的には輝度の情報はそのまま全ピクセルで保持し、色相は1ピクセルごとに捨てます。

f:id:gaise:20170719123937p:plain

上の図の左が元のピクセルのCbもしくはCrの情報だとすると、サンプリングで真ん中のように1ピクセルごとに情報を捨てます。これを右だと解釈することで4分の1の情報量で全ピクセルの数値を表現することができます。

このサンプリングはJPEGがターゲットとしている自然画像では、近いピクセルでは色の変化が少なくなるという仮定に基づいています。一般的に1ピクセルごとに色が大きく変化する写真は少ないだろうということです。逆に漫画などでは線を引いた場所と引いてない場所では色が急激に変化するのでサンプリングは適していないというわけです。

このサンプリングは今回の4:2:0という方法以外にもあるので興味のある方はこちらのサイトをご覧ください。詳しくまとめてあります。

JPEG のクロマサブサンプリングと YUVabc - awm-Tech

今回の4:2:0のサンプリングを行うと16*16のピクセルからY成分は16*16の数値が、Cb,Cr成分は8*8の数値が取れます。これらのセットをMCUと呼びこの後のDCT変換の処理単位になります。

4.DCT変換

DCT変換とはフーリエ変換の一種で、任意の波を様々な周波数のコサイン波の重ね合わせで表現するというものです。JPEGでは8*8ピクセルでの数値を2次元の波として捉え、これをコサイン波の重ね合わせで表現します。先のサンプリングによってMCUに分解されている状態でY成分についてはこのMCUをさらに4つの8*8に分割しそれぞれにDCT変換を施します。この時の変換式は次のようになります。

{ \displaystyle t(u,v) = \frac{1}{4} C(u)C(v)\sum^{7}_{x=0}\sum^{7}_{y=0}(s(x,y)cos\frac{(2x+1)u\pi}{16}cos\frac{(2y+1)v\pi}{16}) }

{ \displaystyle C(n) = \frac{1}{\sqrt{2}} (n = 0) }

{ \displaystyle C(n) = 1 (else) }

s(x,y)は変換前の(x, y)のピクセルの数値、t(u, v)は変換後のピクセルの数値になっています。

5.量子化

DCT変換によって得られた8*8の数値を、量子化テーブルと呼ばれる8*8の数値で割ります。このとき割り切れない数値は切り捨てます。ここで切り捨てられた情報は二度と復元できません。例えば15という数値を4で割ったとすると3になります。15を表現するには4bit必要ですが、3は2bitで表現できるので2bit分短くなって嬉しいのです。

この量子化テーブルは自分で自由に決めることができますが、t(u, v)ではu, vが小さいピクセルに周波数の低いコサイン波の係数が入っているため、そのブロックの基本的な色・輝度の情報を持っています。できれば切り捨てる数値は小さくしたいです。そこでu, vが小さいピクセルでは小さな数値で割り、大きいピクセルでは逆に大きな数値で割るというのが一般的です。

6.ランレングス+ハフマン符号化

量子化した2次元の配列をジグザグスキャンという方法で1次元の配列に直します。

f:id:gaise:20170719131446p:plain

この図の数字を順に辿るように1次元の配列に数値を入れていきます。

この配列に対してランレングス+ハフマン符号化を行うのですがこの説明はかなり長くなってしまうのでまた個別の記事で行います。

 

 

以上が具体的な手順のざっくりした説明になります。

また個別の説明記事を書きたいと思います。