JPEG

符号化の手順

JPEG のベースライン方式は、画像を色の成分に分け、8×8 画素のブロックごとに周波数の成分に変え、細かい情報を捨ててから、残った値をハフマン符号で詰めます。

1. 色の変換RGB から輝度と色差へ
2. 色差の間引き4:2:2・4:2:0
3. DCT8×8 画素のブロックごと
4. 量子化周波数ごとの刻みで丸める
5. 記号化ジグザグ順、DC の差分、AC のランレングス
6. ハフマン符号記号を詰める

情報が失われるのは、色差の間引きと量子化、それに途中の丸めだけです。そのあとの記号化とハフマン符号は可逆です。

色の変換と間引き

色は JFIF の式で、RGB から輝度 $Y$ と色差 $C_b$・$C_r$ に変えます[1]。人の目は明るさに比べて色の細かさに鈍いため、色差の標本は次のどちらかで 1/2 に間引きます。

• 4:2:2: 横に 1/2
• 4:2:0: 縦横に 1/2

間引いた標本は受け持つ画素の平均で、その中心にあるとみなします[1]。

輝度のブロックと、同じ範囲の色差のブロックをまとめたものを MCU（最小符号化単位）といいます。画像の端は、MCU の大きさまで端の画素を繰り返して埋めます。

DCT

DCT（離散コサイン変換）は、ブロックの 64 個の標本を、64 個の基底の模様の重み $F(u,v)$ に置き換えます[2]。

• DC 係数: 左上の係数。平均の明るさから 128 を引いたものの 8 倍
• AC 係数: ほかの係数

なめらかな画像では、エネルギーが低い周波数の少数の係数に集まります。DCT と逆 DCT は、丸めを除けば元に戻る変換です。

量子化

量子化は、係数を量子化テーブルの値 $Q(u,v)$ で割って丸めます[2]。高い周波数ほど $Q(u,v)$ が大きく、細かい模様の小さな係数の多くが 0 になります。

品質は IJG（libjpeg）の決め方で、基準の表[2]を倍率 $s$ [%] で拡大縮小し、1〜255 に収めます[3]。品質 50 で基準の表のまま、100 ですべて 1 です。

量子化テーブルはファイルに入れて送るため、復号器は同じ値を掛けて係数を戻せます。

記号化

量子化した係数は、低い周波数から高い周波数へジグザグに並べます[2]。

DC 係数

走査の順で 1 つ前の同じ成分のブロックとの差分を、次の 2 つで表します。

• 大きさの区分 $\mathrm{SSSS}$ の符号
• $\mathrm{SSSS}$ ビットの付加ビット。負の値は 1 を引いた値の下位ビット

AC 係数

0 の続く数 $\mathrm{RRRR}$ と、次の 0 でない係数の $\mathrm{SSSS}$ を 1 バイトの記号 $\mathrm{RRRRSSSS}$ にまとめ、付加ビットを続けます。

• ZRL（F/0）: 16 個以上続く 0 を 16 個ずつ送る
• EOB（0/0）: 最後の 0 でない係数の後を打ち切る

ハフマン符号

記号はハフマン符号にします。輝度と色差に別の表を使います[2]。

• 標準の表: Annex K の K.3〜K.6
• 最適化: この画像の記号の出現回数から、長さ 16 ビット以下という制限つきでハフマン木を作る。K.2 の手順[2][4]

符号化したデータの中に 0xFF のバイトが現れたら、マーカーと区別するため後に 0x00 を挟みます。最後のバイトの余りは 1 で埋めます。

ファイルの構成

ファイルは次の並びです[1][2]。

1. SOI始まり
2. APP0JFIF
3. DQT量子化テーブル、ジグザグ順
4. SOF0画像の大きさと成分
5. DHTハフマン表
6. SOSスキャンの開始
7. データ符号化したデータ
8. EOI終わり

このツールはこの並びのファイルを自前の符号器で作り、自前の復号器で画素に戻して表示します。復号では、色差を最近傍か線形の補間で画素の数に戻します[5]。

PSNR

PSNR は、元の画像と復号した画像の平均二乗誤差 $\mathrm{MSE}$ から求めます[6]。$Y$ は、両方の画像の RGB から JFIF の式で求めた輝度で比べます。

出典

1. 色の変換、色差の標本の位置、APP0E. Hamilton, JPEG File Interchange Format, Version 1.02, C-Cube Microsystems, 1992
2. DCT・逆 DCT・量子化・ジグザグ順・DC の差分と AC のランレングス・ハフマン符号・マーカー（A.3.3・A.3.4・図 A.6・F.1.2・Annex B・Annex C）、量子化テーブルとハフマン表の標準（Annex K の表 K.1〜K.6）、最適なハフマン表の作り方（K.2）ITU-T Recommendation T.81 | ISO/IEC 10918-1, Digital compression and coding of continuous-tone still images – Requirements and guidelines, 1992
3. 品質の式Independent JPEG Group, libjpeg, jcparam.c の jpeg_quality_scaling と jpeg_add_quant_table
4. 最適なハフマン表Independent JPEG Group, libjpeg 版 6b, jchuff.c の jpeg_gen_optimal_table
5. 色差の線形補間Independent JPEG Group, libjpeg 版 6b, jdsample.c の fancy upsampling。版 7 で DCT による拡大に替わった
6. PSNRQ. Huynh-Thu, M. Ghanbari, “Scope of validity of PSNR in image/video quality assessment,” Electronics Letters, vol. 44, no. 13, pp. 800–801, 2008

このツールで決めたこと

• 浮動小数点で行列の積として計算する DCT
• 色差の間引きの丸め
• ビット数の地図の配分