週刊 JPEGデコーダをつくる #1 創刊号

> Webを席巻し続ける [JPEG(じぇいぺぐ)][wp.jpeg] 画像圧縮。あのJPEGファイルからフルカラー画像へと変換する JPEGデコーダ を、あなたの手で一から作り上げよう！「週刊 JPEGデコーダをつくる」創刊。[創刊号は特製バインダー付きで特別定価290円][uncyclopedia]。

…ごめん。ほとんど冗談です。

週1ペースは無理なので不定期、特製バインダーは付きませんし、そもそもお代は頂きません（あ、貰えるならいつでもウェルカム）。全体構想もぼやーっとしかないので何分割するかも未定ですが、少なくとも実装だけは終わっています（後述）。

[wp.jpeg]: https://ja.wikipedia.org/wiki/JPEG
[uncyclopedia]: http://ja.uncyclopedia.info/wiki/%E5%89%B5%E5%88%8A%E5%8F%B7%E3%81%AF%E7%89%B9%E8%A3%BD%E3%83%90%E3%82%A4%E3%83%B3%E3%83%80%E3%83%BC%E4%BB%98%E3%81%8D%E3%81%A7%E7%89%B9%E5%88%A5%E5%AE%9A%E4%BE%A1290%E5%86%86


# まえがき
本連載記事では、JPEGファイルからRGB画像データへとデコード処理を行うJPEGデコーダを、既存ライブラリ[^libjpeg]を一切使わず **フルスクラッチで実装** していきます。このJPEGデコーダ実装とその解説を通じて、JPEGコーデックが用いる **画像圧縮アルゴリズムの理解** を目指します。

この目的を優先するため、下記はスコープ外とします：

- 最適化された実装：アルゴリズムの分かり易さを最優先し、計算量・メモリ使用量を気にしない[富豪的プログラミング][fugo]を行います。
- デコード画像の表示：圧縮されたJPEGファイルを入力とし、デコード後の非圧縮RGB画像ファイルを出力します。デコード画像の目視確認には外部ツールが必要です。
- Baseline JPEG以外の対応：JPEG仕様では "Baseline" と "Progressive" の2種類が定義されますが、比較的実装が簡単な前者のみに対応します。[^jpeg-type]

JPEGコーデックのアルゴリズムには、モダンな静止画像／動画像コーデック([JPEG 2000][wp.j2k], [JPEG XR][wp.jpegxr], [MPEG-2 Video][wp.m2v], [MPEG-4 Video][wp.m4v], [H.264/AVC][wp.h264], [H.265/HEVC][wp.h265], etc...)にも通じるエッセンスがたくさん詰まっています。これらの高度なアルゴリズムについて調べる際に、JPEGでの基礎知識はきっと役立つことでしょう。

[^libjpeg]: JPEGエンコード／デコードライブラリとしては [libjpeg](http://www.ijg.org/) が最も有名です。また同ライブラリをSIMD最適化した [libjpeg-turbo](http://libjpeg-turbo.virtualgl.org/) も広く普及しています。JPEGエンコード処理だけに特化した [Mozilla/mozjpeg](https://github.com/mozilla/mozjpeg) や [Google/Guetzil](https://github.com/google/guetzli) などの実装も存在します。
[^jpeg-type]: JPEGコーデックの方式は、厳密には"Baseline (sequential)"／"Extended sequential"／"Progressive"／"Lossless"の4種類に分類されます。このうち一般に広く使われるのは、"Baseline"もしくは"Progressive"方式です。名前が表す通り"Baseline(ベースライン)"が最も基本的な方式であり、多くのケースで"Baseline JPEG"が利用されています。
[fugo]: http://www.pitecan.com/fugo.html
[wp.j2k]: https://ja.wikipedia.org/wiki/JPEG_2000
[wp.jpegxr]: https://ja.wikipedia.org/wiki/JPEG_XR
[wp.m2v]: https://ja.wikipedia.org/wiki/MPEG-2
[wp.m4v]: https://ja.wikipedia.org/wiki/MPEG-4
[wp.h264]: https://ja.wikipedia.org/wiki/H.264
[wp.h265]: https://ja.wikipedia.org/wiki/H.265


# JPEGデコーダ picojdec
御託は要らんからさっさとコードを見せろというせっかちな方のために、完成版ソースコードをGithubに置いてあります。MITライセンス。アルゴリズム解説の観点から、実装言語には Python 3.6 を使っています。コメント行や空行を除けば500行もありません。

https://github.com/yohhoy/picojdec

「どうして(<i>ここに任意のプログラミング言語名を入れる</i>)言語で作らないんだ！」と[怒る方が居るかもしれません][u-r-vb]。お好みのプログラミング言語でJPEGデコーダを再実装できるよう、アルゴリズムそれ自体の解説も（なるべく）行う予定です。

キミだけのオリジナルJPEGデコーダをつくろう！

[u-r-vb]: http://yohhoy.tumblr.com/post/41940167709/


## What is "JPEG" ?
この記事をここまで読もうと考えた（そして実際に読んでいる）方ならば、もはや説明不要ですよね？ 次行きます。

...と思ったのですが、さすがに酷すぎるので用語定義を確認しておきます。「JPEG」という単語は、主に次の意味で使われるようです：

- Webブラウザに表示される画像や、デジタルカメラで撮った写真のこと。旨そうな食べ物の写真とか、ちょっとえっちいイラストとか。
- ファイルフォーマットとしてのJPEGファイル。拡張子が`.jpeg`や`.jpg`のファイル。
- 静止画像コーデックとしてのJPEGコーデック。画像データを小さく圧縮する方式。

申し訳ありませんが、この記事は1番目で理解している方向けではありません。でも、その理解でも大丈夫。全てのドライバーがエンジン内部構造を知る必要がないのと同じで、全てのユーザがJPEGの原理を知る必要もありません。お疲れ様でした。

ほとんどの人にとって、2番目と3番目は同じに思えるかもしれません。しかし厳密には両者は区別され、**狭義の JPEG** は3番目「コーデック(codec)＝静止画像(still image)のエンコード(encoding)／デコード(decoding)方式[^enc-dec]」のみを指します。2番目は **JFIF**(JPEG file interchange format) や **EXIF**(Exchangeable image file format) というファイルフォーマット仕様で定義されますが（EXIFの方が有名かな？）、広義に JPEG といえば静止画像コーデックとファイルフォーマットの組を指すのが一般的かと思います。[^jpeg-group]

[^enc-dec]: "エンコード(encoding)／デコード(decoding)"の日本語訳には"符号化／復号化"、"圧縮／伸長(展開)"なども当てられますが、用語揺らぎを防ぐためカタカナ表記を基本とします。本文中では分かりやすさのため一部で「圧縮」と表記しましたが、本来は"compress"に対応する訳語です。JPEGの場合「エンコード処理によって結果的にデータは圧縮される」という解釈が妥当かと思います。このような符号化方式を教科書的には「情報源符号化」と呼びます。
[^jpeg-group]: JPEG は "Joint Photographic Experts Group" の略であり、文字通り「JPEGという標準規格を策定したISO/IECの専門家グループ」という意味もあります。これは豆知識的な話ですし、大した意味もありませんから本文中では言及を避けました。


## JPEGの仕様
ソフトウェア開発では、要求仕様が一番大事ですよね。JPEGデコーダも目的を持ったソフトウェアですから、当然、その仕様書(Specification)が存在します。

ここでは、[ITU-T(国際電気通信連合-電気通信標準化部門)][itu-t][^ccitt] による国際標準勧告に準拠したJPEGデコーダを実装します：

- [ITU-T(CCITT) Rec. T.81: "Digital compression and coding of continuous-tone still images"][itu-t.t81]（W3Cによる[free access版][w3c.t81]）
- [ITU-T Rec. T.871: "Digital compression and coding of continuous-tone still images: JPEG File Interchange Format (JFIF)"][itu-t.t871]

今から作るソフトウェアの仕様書ですから、是非一度目を通してみてください。いかがでしょう？一読して「よしJPEGについて理解した。あとは作るだけだな」となった方には、この記事はもはや必要ありません。むしろ教えてくれ。

多くの方は「なるほどわからん」という感想ではないでしょうか？私が知る限り、ITUやISO/IECによる仕様書は概ねこのような構成で記述されます。たぶん一種のコツがあるので、それを掴んでしまえば読み下すことができますし、この情報だけからソフトウェアをつくることも可能です。実際、picojdecは上記2つのみを参照して実装しました。（動作チェック用のJPEGファイル生成にはlibjpegを利用しています）


[itu-t]: https://ja.wikipedia.org/wiki/ITU-T
[^ccitt]: CCITT(国際電信電話諮問委員会) は ITU-T の前身です。JPEGコーデックを定義するT.81勧告は1992年に発行されており、この当時は名称がCCITTだったため併記となっています。
[itu-t.t81]: https://www.itu.int/rec/T-REC-T.81
[w3c.t81]: https://www.w3.org/Graphics/JPEG/itu-t81.pdf
[itu-t.t871]: https://www.itu.int/rec/T-REC-T.871


[#2 デジタル画像の基礎][article2] 👉
[article2]: http://qiita.com/yohhoy/items/c5c72cbb61a2f7c278aa

---