講義用スタイル
印刷用スタイル

JPEG の要素技術たち
(23/Jan/2002 版)

JPEG はいろんな要素技術の積み重ねで見映えをあまりそこなうことなく圧縮率 をあげています。その要素技術の直感的な説明を試みます。詳細については参考 文献＝前田：「JPEGコーデック」,日本ファジィ学会誌, vol.11, No.2, pp.259-262 (1999) を参照のこと、と言いつつ、この文書のかなりの部分は、こ こであげている解説記事のパクリです(?!)

JPEG の特徴

JPEG コーデックは多くの場合「非可逆」です。すなわち、元画像と展開画像 が全く同一ではありません。ここでは人間が見る上での自然画の特徴を利用し て、 という原理で情報を削り落すことにより高い情報圧縮を実現しています。この削 り落す程度をユーザが調整できるので画像品質と圧縮率を調整することも可能で す。

画像の色空間の変換

カラー画像について、元データが RGB (Red /Green /Blue 各２５６階調）で 表されていた場合は輝度/色差 色空間(YCbCr)に変換します。変換式は以下の 通りです。 
    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
グレースケールでは画像成分が１なのでこのステップは省略します。Yは輝度 成分でグレースケールと同様で、また他の2つの軸は色情報になります。この 変換を行う理由は、輝度成分と色差成分では人間にとって感じ方が異な るため情報の削り方（後述の量子化テーブル、等）を変えることで効果 的な圧縮が期待できるためです。

ちなみに MPEG ではさらに進めて色差信号は画素数まで落したりします。たとえ ば輝度成分４（四角の四方）に対して色差成分を１つ（四角の中心）づつ、とか。 これが 4:2:0 という情報型式です（詳細略）。

離散コサイン変換(DCT)

そもそも離散コサイン変換とは何か、ですが、対称なデータの離散フーリエ変換 です。では、フーリエ変換というのはどういうものかというと、直交変換の１つ で、時間軸を周波数軸に変換するものです。

…ではわけわかんないかもしんないです。まず、画像も所詮はコンピュータ内で はビットの列なわけで、それをずらずらっと並べたら波とかと同じデータ列です。 そして、それを波として取り扱うといろいろ嬉しいことがあるわけです。

それで、時間軸を周波数軸に変換する、ということを直感的に説明すると；例え ば、音というのは波なわけで、単音の場合はきれいなサインカーブを描いている はずです。で、その場合は、周波数と振幅さえわかれば、わざわざプロットした グラフ（コンピュータの中では点の集まり）をデータとして保持しておかなくて も、再現可能なわけです。つまり（図はいい加減ですが）； 

  **        **        **        **      
 *  *      *  *      *  *      *  *     
*    *    *    *    *    *    *    *    *
      *  *      *  *      *  *      *  *
       **        **        **        **
のようなデータ（波）は 
                    *
                    *
*********************************************
のようなグラフとは（取り敢えず必要な？）情報としては等しいということです。 そうすると、ある場合には保持すべき情報量がぐっと削減できる、というわけで す。

でも実際には（たいていの周期的情報は）ろいろな周波数の波の重なりとして表 現されているわけで、その場合は周波数変換後 

                    *       *
   *                *     * * *
*********************************************
        *   *
のようになっているわけで、周波数変換すると情報量が減る、という ことは必ずしもあてはまらないわけです。

ところが、画像のように相関性が高い信号は、これを周波数成分に変換した時、 低周波成分にエネルギー（特徴）が集中し、また低周波成分が視覚 的にも重要な役割を果たすことが知られていて、DCT符号化はこの性質をのち の量子化と組み合わせて利用しています。

量子化

量子化とはデータの変化を段階的にしてとりうる値を制限すること です。これにより情報量の削減をはかります。各ブロックでは、個別の「量子 化係数」で、DCT後の64の周波数成分の各々を割ります。これが基本の情報圧 縮（削り取り）のステップです。下図に逆変換とあわせて例を示します。

quantise

ここで、上に述べた人間の視覚の性質を利用しているわけです。量子化によっ て逆変換後の画像には画質の歪みが生じますが、量子化テーブルを適切にえら ぶことで人間の目には気にならない程度に押えることが可能です。 特に自然画像においては高次の周波数成分の係数を切り捨てることで画質を保 持しつつデータサイズを小さくできます。極端な話、すべての値が１の量子化 テーブルを用いれば画質の品質を最高に保てますが JPEG データサイズはかな り大きくなります。つまり、このテーブルをいじることで、圧縮率を調整でき るわけです。

ランレングス圧縮

ランレングスとは同じ数値の並びです。で、並びによっては情報を保持し たままデータ量としての圧縮が期待できます。例えば、
"AAAAAAABBBBBBBBBCCCCCCCCBBBBBB"
という文字列があったとしましょう。これはそのまま持っていると３０文字（バ イト）ですが、よく見るとAが７つ、Bが９つ、Cが８つ、またBが６つ並んでいる ので、
A7B9C8B6
と表しても情報量は同じ（再現可能）です。こうすると８文字で表現できるので 4/15 にデータが圧縮できたことになります。ただし、これは運のいい場合（？） で、同じものが連続してないと圧縮できないことに注意してください。

とはいえ JPEG では前節での量子化の結果高次の周波数成分は０になることが多 いので、これを「０が？？個並んでいる」と記録すればデータ量を減らす、すな わち圧縮できることになります。この時、下図にあるようにジグザグに並びをみ る（ジグザグスキャン）ことにより、表の右下に多いことが期待される高次の成 分の０の並びをまとめてカウントすることができ、より大きな圧縮率が期待でき ます。

zigzag

ハフマン符号化

前節でえられたデータをハフマンあるいは算術符号化のいずれかを使用して、 縮小された係数をエントロピー符号化します。ただし、算術符号化 には特許があったため、オプションとなっていたことが多く、多くの場合はハ フマン符号化のみを考えておけばよいでしょう。いずれにしても、ここでは情 報理論的エントロピーの概念を用いて、可逆な圧縮（伸張）を行うわけで、情 報量的に冗長な部分をそぎ落している、ということになります。

ハフマン符号化とは、出現頻度の多いものに少ないデータ（ビット） 長の符号を割り当てることで、全体のデータ量を少なくすることを試みるもの です。この場合、１文字＝１バイト、のような関係はなりたたないことに注意 してください。ちなみにモールス符号も同じ発想ですが、モールス符号は事前 に調査した一般的な文書における頻度で固定的にアルファベットに符号を割り ふっています。ハフマン符号化は一般的にはその対象となるデータ列をまず調 べて、適した符号化を行います。さらに、単に頻度の高いものに短い符号を割 りふるだけでは、符号の切れ目が区別できない場合もありますが、その問題も 解消できる仕組みを提供しています。

例えば、

AAAAAABBCDDEEEEEF
という文書の中で使われているA〜Fの文字（ここではたまたま同じ文字を連続さ せて並べていますが、ランダムに並んでいても同様です）を「出現頻度の多いも のを少ないビット数の符号で表す」ことを考えます。１つの案としては 以下のようなものが考えられます。

文字 出現頻度 符号案 ビット数
A 6 0 1
E 5 1 1
B 2 10 2
D 2 11 2
C 1 100 3
F 1 101 3

でも、この案の符号体系には問題があって、例えば "100" という ３ビットは、1,0,0 で EAA なのか、10,0 で BA なのか、100 全体で C なのかの区別ができないです。

ハフマン法ではハフマン木というものを使って符号系を作り、上の問題を解決し ています。アルゴリズムは以下の通りです。

  1. まずデータ毎に出現頻度を並べます。 
    出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ

  2. 出現頻度の少ない方から２つを選び絵だを伸ばした上段に 数値の合計を書きます。選択肢が複数ある場合はどれを選んでも構いません。こ のことはつまり、符号系はおなじ元データでも一意には定まらない可能性がある ということです。 
    　　　　　　　　　　　　　　　　　　（２）
　　　　　　　　　　　　　　　　　　／　　＼
出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ

  3. 上の手順を繰り返します。上段に向かって枝が 伸びていない数値ならどの位置にある数値をむすんでも かまわないです。 
    　　　　　　　　　　　　　　　（６）
　　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　　　（４）　　　（２）
　　　　　　　　　　　　／　　＼　　／　　＼
出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ

  4. 最終的に根となる数値が１つになったらハフマン木の完成です、末端の葉に向かっ て根の左は０、右は１とします。根から枝を辿って目的の文字に到達したとき、 通過した枝の０または１を順に上位桁から並べたものがハフマン符号となります。 
    　　　　　　　　　　（１７）
　　　　　　　　　　／　　　＼
　　　　　　　　　／　　　　（６）
　　　　　　　　／　　　　　／　　　＼
　　　　　　（１１）　　（４）　　　（２）
　　　　　　／　　＼　　／　　＼　　／　　＼
出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ
符号　　　００　０１　 100　 101　 110　 111
ビット合計  12    10     6     6     3     3 = 40
    あるいは、以下のようなものでもＯＫです。 
    　　　　　　　　　　　　（１７）
　　　　　　　　　　　　／　　＼
　　　　　　　　　　　／　（１１）
　　　　　　　　　　／　　／　　＼
　　　　　　　　　／　　／　　（６）
　　　　　　　　／　　／　　／　　　＼
　　　　　　　／　　／　（４）　　　（２）
　　　　　　／　　／　　／　　＼　　／　　＼
出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ
符号　　　　０　１０　1100　1101　 1110　1111
ビット合計   6    10     8     8     4     4 = 40
    さらに、以下のようなものでもＯＫです。かなり自由度があることが わかると思います。 
    　　　　　　　　　　　　　（１７）
　　　　　　　　　　　　　　／＼
　　　　　　　　　　　　　／（１１）
　　　　　　　　　　　　／　　／＼
　　　　　　　　　　　／　　／　（６）
　　　　　　　　　　／　　／　　／　＼
　　　　　　　　　／　　／　　／　（４）
　　　　　　　　／　　／　　／　　／　＼
　　　　　　　／　　／　　／　　／　（２）
　　　　　　／　　／　　／　　／　　／　　＼
出現頻度　（６）（５）（２）（２）（１）（１）
データ　　　Ａ　　Ｅ　　Ｂ　　Ｄ　　Ｃ　　Ｆ
符号　　　　０　１０　 110　1110　11110　11111
ビット合計   6    10     6     8     5     5 = 40
上のほうの符号系を採用すると、 "AAAAAABBCDDEEEEEF" という文字列は
00 00 00 00 00 00 100 100 110 101 101 01 01 01 01 01 111
となります。いずれの符号系（テーブル）にしても、符号化後は４０ビット＝５ バイトとなります。もとは１７文字＝１７バイトのデータだったわけで、約３割 に圧縮出来たことになります。

圧縮例

まとめとして、下図に前の例で量子化されたデータに対してジグザグシーケンス、 ランレングス、エントロピー符号化を適用した例をしめします。この一連の処理 は可逆であるので画質に影響せず圧縮を可能とします。

entropy

その他 JPEG 関連の話題

MPEG

MPEG は Motion Picture ということで動画像についての通信方式の標準です。 1,2,4,7 が既に標準化された模様です、が、７は動画像圧縮技術ではなくメタ データ云々なんで、ここではあまり関係ないです。細かい話はさておいて、 JPEG とMPEG(1,2) の根本的な違いは、というと、動画像を静止画像の列と捉 えたときに、その画像と画像の間の差というのは（背景が変わらない場合は特 に）少ないので、動き補償してやることで、さらにデータ量を圧縮している、 ということです。 YCbCr に変換して色差 信号を間引いたり、 P/I/B フレー ムに分けたり、等があるのですが、ここでは詳細は略します。

JPEG2000

2001年1月に International Standard となった、JPEG の新しい規格です。 JPEG2000 では DCT をおこなわず、ウェーブレットを用いることで、ブロック歪 を防ぐほか、ポスト量子化によりレート制御を簡単にすることが出来る、などさ まざまな特徴があるのですが、詳細は略します。

とはいえ、機軸技術である（離散）ウェーブレット変換 (DWT) を非常に簡単に 端折っていうと、画像＝２次元情報を、分離型フィルタの考えに基づく１次元の （高周波／低周波）２分割フィルタバンクを繰り返して使用して２次元DWT を実 行します。つまり、画像を

Low,Low High,Low
Low,High High,High

と４分割します。すると、LL が基本的な画像の特徴（エネルギー）を保持して います（原画の画質を維持している）ので、極端な話、ここだけデータをもって いれば元の画像はだいたい復元できることになります。このLL領域についてさら に２次元 DWT を行って…というステージを繰り返していくと、階層的に画像を 分解して、かつ、重要度の高い部分から先におくることが出来る、というわけで す。JPEG 2000ではデフォルト５ステージです。

おわりに

この文書が、読者のみなさんにとって少しでも役にたてば幸いです（無難なまと め）
講義用スタイル
印刷用スタイル