週刊 JPEGデコーダをつくる #3 データ圧縮の基礎(前編)

データ圧縮の基礎

JPEGコーデックを用いると、元のデジタル画像をエンコードしてサイズの小さなJPEGファイルへと変換します。JPEGファイルはデジタル画像ではありませんから、ディスプレイに表示するにはデジタル画像へのデコードが必要です。

具体例として、libjpegライブラリ付属のJPEGエンコーダcjpegで標準テスト画像"Lenna"¹をJPEGファイルに変換すると、元のデジタル画像²とのファイルサイズ比 1:20 (1÷20＝5%) にまで縮みます³。この小さなJPEGファイルをWebブラウザや画像ビューアで表示すると、ちゃんと圧縮前と同じ画像に見えます。改めて考えると不思議ですよね？元ファイルサイズの95%にあたる750Kbyteものデータはどこに消えたの？

$ cjpeg lena_std.ppm > lena_std.jpeg
$ ls -l
-rw-r--r-- user  group   37852  1  1 00:00 lena_std.jpeg
-rw-r--r-- user  group  786447  1  1 00:00 lena_std.ppm

本記事ではこの魔法のような「[データ圧縮(data compression)][wp.datacompress]」の原理について、概念的な理解を目指した解説を行います。退屈な話題かもしれませんが、JPEGコーデックの理解には避けて通れません。

用語の整理

まずはデータ圧縮に関する各用語について整理しておきましょう。JPEGコーデックの説明では次の単語が登場します。

• エンコード(encoding)：デジタル画像（原画像）からJPEGビットストリームへと変換する処理。この変換によりデータサイズは削減、つまりデータが圧縮(compress)される⁴。別名: "符号化"
• デコード(decoding)：JPEGビットストリームからデジタル画像（デコード画像）へと変換する処理。この変換によりデータサイズは増大、つまりデータが伸長／展開(decompress)される。別名: "復号化"
• エンコーダ(encoder)：JPEGエンコード処理を行うソフトウェア実装やハードウェア機器。別名: "符号化器"
• デコーダ(decoder)：JPEGデコード処理を行うソフトウェア実装やハードウェア機器。別名: "復号化器"
• コーデック(codec)：JPEGエンコード／JPEGデコード両機能をそなえたソフトウェア実装やハードウェア機器、もしくはJPEGアルゴリズム仕様そのもの。両方の意で使われます。
• 原画像(げんがぞう; source image)：JPEGエンコーダへ入力されるオリジナルのデジタル画像。
• デコード画像(decoded image)：JPEGデコーダによってJPEGビットストリームから復元されたデジタル画像。別名: "復元画像(reconstructed image)"
• ビットストリーム(bitstream)：JPEGエンコーダが出力するバイナリデータ列⁵。本記事連載で実装するJPEGデコーダにとっては入力データとなる。

可逆(ロスレス)と非可逆(ロッシー)

Webでの利用頻度が高い代表的な画像コーデックとして、JPEG以外にもPNG( /ˈpɪŋ/; ぴんぐ)やGIF(/ˈdʒɪf/; じふ)があります。各種画像コーデックの特徴とその使い分けは、本記事連載を読もうと考える方ならば、経験的にも知識としても既にご存知のことでしょう。

全ての画像コーデックは「可逆圧縮」または「非可逆圧縮」のいずれかに大別されます⁶。［おまけ：音声コーデックでもこの分類は有効です］

• 可逆(lossless; ロスレス)圧縮：原画像とデコード画像が厳密に一致する、つまりエンコード／デコード処理を行っても データが完全に復元される 圧縮方式。PNG, GIFはこちら。
• 非可逆(lossy; ロッシー)圧縮：原画像とデコード画像が必ずしも一致しない、つまりエンコード／デコード処理によって データが変化する／歪(ひず)む 圧縮方式。JPEGはこちら。

上記説明だけでは非可逆圧縮のJPEGコーデックにメリットなど無いように聞こえますが、データ圧縮性能つまり出力ファイルサイズが全く異なります。先ほどの画像"Lenna"をPNGファイルに変換すると、原画像(.ppm)とのファイルサイズ比 1:1.6 (1÷1.6＝60%) にしか圧縮されません。我らがJPEGファイルは 1:20 (1÷20＝5%) ですから、両コーデックの圧縮性能差は歴然です。[すごーい！きみはデータ圧縮が得意なフレンズなんだね！][friends]

$ convert lena_std.ppm lena_std.png
$ ls -l
-rw-r--r-- user  group  786447  1  1 00:00 lena_std.ppm
-rw-r--r-- user  group  474630  1  1 00:00 lena_std.png
-rw-r--r-- user  group   37852  1  1 00:00 lena_std.jpeg

非可逆圧縮のトレードオフ

JPEGのように非可逆圧縮を行うエンコーダの特徴として、画品質とファイルサイズのトレードオフ を選択するユーザ向けパラメータが提供されます。ほとんどのJPEGエンコーダでは、品質(Quality; Q)パラメータを数値1〜100で指定できます。値が小さいほど低画品質つまり画像は劣化する／歪むがファイルサイズ小、値が大きいほど高画品質つまり原画像と見分けが付かないがファイルサイズ大という関係です。

$ cjpeg -quality 100 lena_std.ppm > lena_q100.jpeg
$ cjpeg -quality 75 lena_std.ppm > lena_q75.jpeg
$ cjpeg -quality 50 lena_std.ppm > lena_q50.jpeg
$ cjpeg -quality 25 lena_std.ppm > lena_q25.jpeg
$ ls -l
-rw-r--r-- user  group  786447  1  1 00:00 lena_std.ppm
-rw-r--r-- user  group  474630  1  1 00:00 lena_std.png
-rw-r--r-- user  group  230221  1  1 00:00 lena_q100.jpeg
-rw-r--r-- user  group   37852  1  1 00:00 lena_q75.jpeg
-rw-r--r-- user  group   24340  1  1 00:00 lena_q50.jpeg
-rw-r--r-- user  group   15808  1  1 00:00 lena_q25.jpeg

鋭い方は気づいたかもしれませんが、最高画品質(Q=100)のJPEGファイルサイズはPNGファイルサイズの1/2程度に抑えられています。JPEGコーデックはPNGコーデックよりも2倍高性能なのでしょうか？

答えはNO。JPEGコーデックの最高画品質は可逆圧縮を意味せず、たとえ最高画品質でエンコードしようとも（目には見えませんが）データは歪む、つまりは非可逆圧縮なのです⁷。一般に、非可逆圧縮と可逆圧縮は異なるアルゴリズムにより実現されます⁸。両方式は目的に応じて使い分けるべきであり、ある一側面だけからの単純比較は無意味です。

👈 [#2 デジタル画像の基礎][article2] ／ [#4 データ圧縮の基礎(中編)][article4] 👉
[article2]: http://qiita.com/yohhoy/items/c5c72cbb61a2f7c278aa
[article4]: http://qiita.com/yohhoy/items/360dccb09379dc6c7f6e

1. 対象ファイルは http://www.cs.cmu.edu/~chuck/lennapg/lena_std.tif よりTIFF形式で入手可能です。TIFF形式からPPM形式へは[ImageMagick][imagemagick]を用いて変換(convert lena_std.tif lena_std.ppm)しています。512x512ピクセル, RGBカラー画像, 各色成分ごとに8bpp（合計24bpp）
   [imagemagick]: https://www.imagemagick.org/ ↩

2. 非圧縮(uncompressed)画像フォーマットとして、ファイル構造が単純な[PPM(portable pixmal)][netpbm]形式を利用します。最小限のメタ情報しか保持しないため、デジタル画像のデータサイズ(512×512×3＝786432byte)に対して非常に小さなオーバーヘッド(+15byte)で済みます。本記事連載で実装するJPEGデコーダでも、デコード画像を同フォーマットにてファイル出力する予定です。
   [netpbm]: https://ja.wikipedia.org/wiki/Netpbm ↩

3. データサイズ削減の度合いは「圧縮率(compression ratio)」と呼ばれることもあります。しかしその定義は "圧縮後サイズ÷元サイズ[%]"、"圧縮で削減できたサイズ÷元サイズ[%]"、"圧縮後サイズに比べた元サイズ[1:N]" など分野や人によって定義がまちまちなことが多いようです。本文中では曖昧さ回避のため、圧縮率という単語は用いません。
   [wp.datacompress]: https://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E5%9C%A7%E7%B8%AE ↩

4. 本文中の定義では "エンコード" と "データ圧縮" の関係性をあえて緩く説明しています。情報理論におけるエンコード(符号化)には、"情報源符号化" と "通信路符号化" の2種類が存在します。JPEGやMP3などの画像・音声コーデック、ZIPなどのファイル圧縮アルゴリズムは全て前者 "情報源符号化" に区分され、いずれもデータの冗長度削減を目的とするため "エンコード" は "データ圧縮" と同義です。無線通信やデータ記録媒体で用いられる後者 "通信路符号化" は、データ冗長度を増やすことで誤り検知・訂正を可能とするため "エンコード" によってデータサイズは増加します。 ↩

5. データ圧縮を行うプログラムでは一般的なプログラムのようなバイト(byte)列ではなく、文字通り "ビット(0/1)" のストリーム(列)を扱います。JPEGデコーダの場合、JPEGファイルからビット単位でのデータ読込みを行います。例えば4バイトのデータ列01 23 45 67[16進表記]は、32ビットのデータ列00000001 00100011 01000101 01100111[2進表記]です。ここから10, 4, 12, 6ビットづつ読み出すと0000000100, 1000, 110100010101, 100111[2進表記]、符号なし整数型とみなす場合は4つの数値4, 8, 3349, 39[10進表記]に解釈されます。一度は自分の手で計算してみてください。 ↩

6. 基本的には可逆(lossless)／非可逆(lossy)の2種類なのですが、実は「準可逆(near-lossless; ニアロスレス)圧縮」という概念も存在しています。合意の取れた定義があるかは微妙なところですが、文字通り "ほぼロスレスといって差し支えないほど歪みが小さい" データ圧縮を意味します。どこからが "準(near-)" なのかは定義次第ですが、歪みをエンコーダが完全に制御できるアルゴリズムや、歪みが一定量以下になることを保証するアルゴリズムを指すことが多いようです。本文中では混乱を避けるため準可逆圧縮には言及しません。
   [friends]: http://moto-neta.com/anime/friendsnandane/ ↩

7. JPEGコーデックに詳しい方は「JPEGにもLosslessモードがあるぞ！」と反論されるかもしれません。はい、それ自体は正しい指摘です。ITU-T(CCITT) Rec T.81では非可逆圧縮の "DCT-basedモード" と、可逆圧縮の "Losslessモード" の2種類を規定します。しかし両者は同じJPEGの名前を冠しているだけで、そのデータ圧縮アルゴリズムは別コーデックと呼べるほど異なります。JPEGコーデックのLosslessモードはごく限られた場面でしか用いられず、一般には全くと言って良いほど普及していません。 ↩

8. JPEGコーデック後継として開発されたJPEG 2000コーデックは、可逆圧縮と非可逆圧縮をシームレスに統合するアルゴリズムを採用しています。これは スケーラブル・コーデック(scalable codec) と呼ばれる考え方です。JPEG 2000ではビットストリームの一部分のみをデコードすると多少歪んだ画像が復元され（＝非可逆圧縮）、全部をデコードすればデコード画像は原画像に完全一致する（＝可逆圧縮）という仕組みを提供します。ただこの方式は代償も伴います。JPEG 2000は "可逆圧縮はサポートしない非可逆圧縮専用モード" と "可逆・非可逆圧縮をサポートするスケーラブル・モード" の2つを規定しており、非可逆圧縮の範囲においては前者専用モードの方が高性能なのです。これはあらゆるスケラーブル・コーデックに共通する特性（＝分割損失／オーバーヘッド）であり、結局は目的に応じた使い分けが必要となります。 ↩