Crazy*Planet:お絵描き研究室：JPEG(原理編３)

お絵描き研究室：JPEG(原理編３)

エントロピー圧縮、プログレッシブエンコード、JPEG フォーマットの構成とマーカについて解説しています。

6. エントロピー圧縮

　量子化のあとの圧縮では不可逆な操作は行われません。圧縮プロセスについては簡単に解説するにとどめます。
　まず、量子化行列の中で突出している DC 成分(左上)を「直前のブロックの DC 成分からの差分」に変換します。画像全体で急峻な DC 変化が現れることは希なので、こうすることによって量子化行列全体の数値を低く押さえて圧縮しやすくします(一番最初のブロックはどうしようもありませんが)。
　次に 8x8 の量子化行列を左上から右下に向かって「ジグザグ」に走査し、64 要素の一次元数列に変換します。表５－２を見ればわかるように、量子化行列には「０」が右下に集中する傾向があるため、このように並べ替えた数列には後端に「０」が連続する傾向が表れます。そこで、この数列に対して「連長ゼロ圧縮」という操作を行い、連続するゼロの値を「たたみこみ」ます。
　最後に、連長ゼロ圧縮をかけた数列に対して「エントロピー圧縮」を行います。エントロピー圧縮とは要素の出現頻度に合わせて可変ビット長のコードを割り当てデータ全体のサイズを削減する操作で、通常は「ハフマン(Huffman)圧縮」というアルゴリズムが用いられます。
　ハフマン圧縮では出現要素とビットコードの一覧を示す「ハフマンテーブル」を作成し、これに従ってデータとビットコードの置換を行います。JPEG(*1)では画像全体で１つのハフマンテーブルを共有する(*2)ため、実際の圧縮前に画像全体に対する数値の出現頻度を調査しておくことで圧縮率を上げることができます。これを２パス最適化(2-pass optimization)圧縮と呼びます。一方最適化を行わない１パス圧縮はファイルサイズに無駄が発生しますが、少ないメモリと遅い CPU でも効率的に動作するという利点があります。

　JPEG の規格ではハフマン圧縮以外に「算術圧縮」というアルゴリズムも規定しています。算術圧縮はハフマンにくらべやや圧縮率が高いのですが、著作権の問題によるライセンス料の支払いが義務づけられているため、実際にはほとんど使われていません。

*1:ベースラインエンコードの場合。プログレッシブエンコードについては次章を参照してください。
*2:実際には Y, Cb, Cr のそれぞれ DC 成分、AC 成分について別々のハフマンテーブルが生成されますが、重要なのはそれらが全ブロックで共有されるという点です。

7. プログレッシブエンコード

　通常の JPEG 画像は左上から右下に向かって走査され、同じ順序で一つのファイルに格納されます。これを低速回線(ダイヤルアップインターネットなど)でダウンロードしながら表示した時には、画像が 8x8 のブロック単位(*1)で左上→右下の順番に表示されることになります。
　しかし画像サイズが大きい場合にはまず最初に荒い全体像が表示され、ロードが進むにつれ細部が補完されてゆくという形式のほうが便利な場合もあります。JPEG の場合は DCT の性質を利用し画像の走査・格納形式に手を加えることによって実現され、俗に「プログレッシブ(Progressive) JPEG)」として知られています。これに対し左上→右下の通常形式は「ベースライン(Baseline) JPEG」と呼ばれます。

　プログレッシブエンコードの圧縮操作では、画像に DCT 操作を行い 8x8 の量子化行列を作るところまではベースラインと同じです。ただしこれをブロック単位に「ジグザグ」走査して順々に格納するのではなく、まず全ブロックの量子化を済ませてしまい、各ブロックの成分を飛び飛びにつまみ食いし何度かの「スキャン(Scan)」単位に分けて格納します。たとえば、

スキャン１：ＤＣ成分のみ
スキャン２：ＡＣ成分の前半(低周波成分)
スキャン３：ＡＣ成分の後半(高周波成分)

　というような順番です(実際のプログレッシブ JPEG のスキャン順序はもう少し複雑です)。再生側は各スキャンごとに逆 DCT 操作をかけ画像を再生することにより、

スキャン１：モザイク状の画像
スキャン２：ピントのぼけた画像
スキャン３：完全な画像

　という順番で「ロード中」の画像を表示できるわけです。最終的に得られる画像は、同じ Q 行列を使って量子化した場合ベースラインもプログレッシブも同じです。

　プログレッシブエンコードのエントロピー圧縮はスキャンごとに行われ、最適化オプションはありません。スキャン単位での圧縮は要素の出現頻度が集中するので圧縮率が向上しますが、各スキャンごとのハフマンテーブルを個別に書き出す必要があるため、これがファイルサイズを増大させます。最終的なファイルサイズはだいたいベースライン(最適化を行ったもの)と同じくらいになりますが、画像の性質(周波数成分の分布)によって若干の増減があります。

　プログレッシブ JPEG は圧縮・再生に大量のメモリを必要とするので、古い 16bit パソコンなどでは対応できない場合があります。今時の 32bit パソコンではまず問題ありませんが、互換性を重視する場合にはベースラインを使ったほうがいいでしょう。

*1:ダウンサンプルなしの場合。詳しくは次章の MCU に関する記述を参照してください。

8. JPEG フォーマットの構造

　これまでの経緯をまとめると、JPEG の画像情報は

量子化テーブル(Q 行列)
ハフマンテーブル
スキャンデータ(量子化されエントロピー圧縮された DCT 係数行列)

　から構成されることがわかります。これらの情報はマーカ(Marker)と呼ばれる構造で分類され、他の情報とともにファイルに格納されます。ファイルを生成するソフトを JPEG エンコーダ、ファイルを読み取って画像を再生するソフトを JPEG デコーダと呼びます。マーカは 0xff に続く任意のバイト列で表現され、次の種類が定義されています。

表８－１ JPEG マーカの一覧

コード	略称	名称	解説
0x00～0xbf	--	--	無意味
0xc0～0xc3	SOF0～SOF3	Start Of Frame Type0～3	フレーム・タイプ(ハフマン圧縮)
0xc4	DHT	Define Huffman Table(s)	ハフマンテーブル
0xc5～0xc7	SOF5～SOF7	Start Of Frame Type5～7	フレーム・タイプ(ハフマン圧縮、差分形式)
0xc8	JPG	JPEG extension	将来の JPEG 拡張用
0xc9～0xcb	SOF9～SOF11	Start Of Frame Type9～11	フレーム・タイプ(算術圧縮)
0xcc	DAC	Define Arithmetic Tables	算術圧縮テーブル
0xcd～0xcf	SOF13～SOF15	Start Of Frame Type13～15	フレーム・タイプ(算術圧縮、差分形式)
0xd0～0xd7	RST0～RST7	Restart marks	スキャンデータ区切り位置
0xd8	SOI	Start Of Image	イメージデータの開始
0xd9	EOI	End Of Image	イメージデータの終了
0xda	SOS	Start Of Scan	スキャンデータの開始
0xdb	DQT	Define Quantization Tables	量子化行列テーブル
0xdc	DNL	Define Number Of Lines	画像のライン数
0xdd	DRI	Define Restart Interval	MCU リスタート間隔
0xde	DHP	Define Hierarchical Progression	(よくわからない…)
0xdf	EXP	EXPand reference images	(よくわからない…)
0xe0～0xef	APP0～APP15	Application type 0～15	アプリケーション依存のデータを格納
0xf0～0xfd	JPG0～JPG13	JPEG extension 0～13	将来の JPEG 拡張用
0xfe	COM	COMment	コメント
0xff	--	--	0xff のデータ値

　データ本体とマーカが混同しないよう、データ単体に出現した 0xff は二重の 0xff 0xff として格納されます。JPEG のファイルを順次読み込んでもし 0xff に遭遇したら次の一バイトを調べ、0x00～0xbf なら無意味、0xc0～0xfe ならマーカ、0xff ならデータと判断することでマーカを判別できるわけです。
　マーカによって区切られた情報をそれぞれセグメント(Segment)と呼びます。通常セグメントはマーカ＋長さ(2byte)＋セグメント情報として構成されますが、SOI, EOI, RST0～RST7 はマーカ単体で意味を持ち長さとセグメント情報を持ちません。また、SOS セグメントの後にはスキャンデータが続きますが、スキャンデータ本体の長さは SOS の長さには含まれません。

　スキャンデータの実際の長さはエントロピー圧縮されたデータを展開してみなければわかりませんが、スキャンデータが１ビットでも狂っていると展開した長さが狂い、以降のスキャンデータ読み取り開始位置が全て狂ってしまう可能性があります。RST0～RST7 はこの現象を防ぐ目的で定義されており、RST マーカが出現したタイミングでスキャンデータの解読位置をリセットします。
　RST の出現間隔は DRI セグメントに格納されており、これは MCU(Minimum Coded Unit) という単位で定義されています。MCU は１ブロックを再生するのに必要なデータ量で、例えばダウンサンプルなしの場合 MCU=Y+Cb+Cr(8x8)、ダウンサンプル比 4:1 のときは MCU=4Y+1Cb+1Cr(16x16) といった値になります。画像が 128x128 でダウンサンプル比 4:1 の場合、DRI=8 MCU として定義されていれば画像の縦 16 ラインごとに RST0～RST7 が交互に現われ、万が一途中でスキャンデータが狂っても 16 ラインごとに読み取り位置がリセットされることを保証します。
　なお、一部の JPEG デコーダでは画像の幅が MCU の整数倍でない時、RST マーカが入っていなければ展開が狂うこともあるようです。また、DRI および RST が使用されるのは通常ベースラインエンコードの場合だけです。プログレッシブ画像に RST を含めると、各スキャンごとに反復して RST が挿入されるのでサイズ効率が悪化します。

　一般的な JPEG(JFIF) で使わるマーカは SOF0(ベースライン) または SOF2(プログレッシブ), DHT, SOI, EOI, SOS, DQT, APP0 だけで、場合によって RST0～RST7, DRI, DNL, APP1～APP15, COM が混ざることもあります。JFIF フォーマットの構成を表８－２に示します。マーカは上から下に向かって一般的な出現順序(ファイル先頭～終端)順に並べてあります。

表８－２ JFIF フォーマットの構造

マーカ	必須	反復	解説
SOI	Yes	No	JFIF ファイルの開始を意味
APP0	Yes	No	JFIF のバージョン等を格納 (JFIF ヘッダ)
APP0～15	No	Yes	アプリケーション独自の拡張情報、サムネール等を格納 (JFXX ヘッダ等)
COM	No	No	コメント文字列を格納
DNL	No	No	画像のライン数を格納(*1)
DQT	Yes	No or Yes(*2)	量子化テーブルを格納
SOF	Yes	No	SOF0 または SOF2 で画像形式を格納
DRI	No	No	MCU リスタート間隔を格納
DHT	Yes	No or Yes(*3)	ハフマンテーブルを格納
SOS	Yes	No or Yes(*4)	スキャンデータの開始
RST0～7	No	Yes	スキャンデータ区切り位置を意味
EOI	Yes	No	JFIF ファイルの終端を意味

*1:一応オプションとして定義されていますが、DNL の入った JFIF ファイルにお目にかかったことはありません。
*2:カラー画像の場合 Y と CbCr の DQT が別テーブルになりますが、これを一つのセグメントにまとめても、二つのセグメントに分割しても構いません。
*3:AC 成分と DC 成分の DHT が別テーブルになり、カラー画像の場合更に Y と CbCr が別テーブルになりますが、これを一つのセグメントにまとめても、複数のセグメントに分割しても構いません。プログレッシブエンコードの場合はスキャンごとの DHT が生成されますが、これも統合・分割のどちらにでも格納できます。
*4:カラー画像の場合 Y, Cb, Cr が別スキャンになりますが、これを一つのセグメントにまとめても複数のセグメントに分割しても構いません。しかしプログレッシブエンコードの場合は必ず複数回スキャンとなりますので、スキャン回数だけ SOS も反復されます。

　JFIF ヘッダ、JFXX ヘッダなどの詳細については割愛します。詳しくは規格書や参考書を参照してください。

　オプションのマーカを含めるかどうか、DHT や DQT を統合するか分割するか、この辺りの実装は JPEG エンコーダごとに微妙に異なっており、マーカの出現順序も実装によって少しづつ異なります。これらは言わば JPEG エンコーダの「癖」あるいは「指紋」のようなものです。実際どのような相違が発生するのかは[お絵描き研究室：JPEG(実験編)]を参照してみてください。

9. JPEG についてのまとめ

　最後に、世間に流布している JPEG の「常識」を検証することで、今まで述べてきた JPEG/JFIF の特を簡単にまとめておきます。

JPEG とは画像フォーマットの名前である…しかし？: JPEG とは画像フォーマット標準化委員会と、JPEG 委員会によって決められたフォーマット形式の名前を指します。しかし一般に使われている「JPEG」とは、JPEG フォーマットの一形式である JFIF を指す場合が多いです。
JPEG はフルカラーの画像フォーマットである…とは限らない: JFIF には YCbCr(フルカラー)とグレイスケール(白黒)の二種類がありますので、必ずしもフルカラーには限定されません。ただし、GIF や PNG のような 16 色、256 色という形式は持ちません。
JPEG の圧縮は離散コサイン変換(DCT)という手法による…DCT は圧縮そのものではない: DCT は画素行列→周波数行列の変換操作であり、圧縮そのものではありません。JPEG の圧縮は主に量子化によるデータの切り捨てとハフマン法によるエントロピー圧縮によって実現されます。
JPEG は保存時に細部情報を失う…その通り: 主な情報欠落は量子化とダウンサンプリング時に発生しますが、RGB←→YCbCr 変換および DCT/逆 DCT 演算の桁落ちによっても情報欠落が発生しますので、同じ画質パラメータで保存→再生を繰り返しても少しずつ画質が劣化してゆきます。
JPEG 圧縮率を上げすぎると極端に画質が劣化する…その通り: JPEG の圧縮は情報の切り捨て(量子化)による効果が大きいですが、圧縮率を上げすぎると必要な情報まで切り捨ててしまうため、使用に耐えないほど画質が劣化します。
JPEG 画像は色むらを起こしやすい…使い方次第: 色むら(特に赤系・青系)の原因は圧縮率の上げすぎかダウンサンプリングの不適切な使用です。ダウンサンプル比を 1:1 に設定し、高画質で保存すれば色むらはほとんど発生しません(ただしファイルサイズは多少肥大化します)。
JPEG は自然画に向く…場合が多い: JPEG でもダウンサンプル比と画質を適切な妥協点に設定して使えば、必ずしもベタ塗り画像を苦手とする訳ではありません。ただし原画の色数が少ない場合は GIF/PNG のほうが小ファイルサイズになる場合が多いです。また、JPEG では圧縮に DCT を使用している関係上、色変化・輝度変化がなめらか(高周波成分を含まない)な画像のほうが圧縮率が上がります。
WEB 画像にはなるべくプログレッシブ JPEG を使うべきだ…目的による: プログレッシブ形式はベースライン形式とのファイルサイズ差もあまりなく、ロード中の全体像が見えることが利点です。しかし展開に大量のメモリを必要とするため、古いパソコンや組み込み端末では表示できない、あるいは展開がひどく遅い場合もあります。どんなユーザー環境を対象にしているのか、その目的に応じて使い分けましょう。
JPEG にはサムネール画像が内蔵されている…時もある: JFIF 規格にはサムネールの規定がありますが、形式には JFIF-RGB, JFXX-PALETTE, JFXX-RGB の三種類があり、他に Adobe PhotoShop の APP13 など独自形式のものもあります。種類ばかり多くてサポートソフトが少ないため、現状ではあまり活用されていません。特にファイルサイズ優先の WEB 画像では、内蔵サムネールは使わない方が無難でしょう。

10. 参考文献など

「JPEG 研究室：原理編」を書くにあたって下記の書籍・情報を参考にしました。なお、勝手ながら敬称等は略させて頂いております。

"データ圧縮ハンドブック"
M.Nelson, J.L.Gailly, 荻原剛志・山口英訳
Prentice Hall/トッパン (ISBN 4-8101-8605-9)
"Graphic File Format" 2nd edition
David C.Kay, John R.Leveine
McGraw-Hill (ISBN 0-07-034025-0)
"EJX" ver 1.3.22 および添付ドキュメント
阿部　昇(あべべ)
"Encyclopedia of Graphics File Formats" Second edition
J.D.Murray, William Vanryper
O'Reilley&Associates (ISBN 1-56592-161-5)
"JPEG File Interchange Format Version 1.02"
Eric Hamilton
C-Cube Microsystems
"JPEGLIB2" Release 6b ソースおよび添付ドキュメント
Independent JPEG Group(IJG)

[研究室] [目次]

Copyright by 'Crazy' Y.Sasaki