QOI - O(n) の可逆画像圧縮
(phoboslab.org)"Quite OK Image"
- PNGに近いサイズでRGB/RGBA圧縮を実行
→ 圧縮は20〜50倍高速で、展開は3〜4倍高速
→ 300行のシングルヘッダーファイルによるCコードのオープンソース
→ SIMDを使わないシンプルなシングルスレッド実装
- 技術的な詳細
→ 単一パスで画像をエンコード/デコード
→ すべてのピクセルに一度だけ触れ、各ピクセルは4つの方法のいずれかでエンコード
⇨ 直前のピクセルと同じなら前のピクセルのrun-lengthを増やし、異なるなら新しいピクセルを次の3つの方法のいずれかでパック
⇨ すでに処理したピクセルと同じならそのピクセルのインデックスを使用。これのために直近64個のピクセルに対する配列を保持
⇨ 前のピクセルとの差が大きくなければ、そのRGBA差分値を保存
⇨ 前の3つの方法が失敗した場合はピクセルのRGBA値を保存。ただし直前のピクセルと異なる部分だけを保存
3件のコメント
少し誇張して言えば、QOIはPNGからzlibを取り外してフィルタリングだけを残し、それを改良したものです。
PNGでも使われているzlib/gzip/DEFLATE圧縮アルゴリズムは広く使われていますが、古くなりすぎて効率が落ちている面もありますし、zlibをはじめとするLZ77系のアルゴリズムは「直近のバイト列の中で同じ連続バイト列が何度も現れる」という基本的な仮定を置いています（例: 入力が "to be or not to be" のとき、"to be" の部分が2回現れることを利用する）。しかし画像はこうした仮定があまり当てはまらないデータなので、PNGはzlibを事実上エントロピー符号化（追加の文脈なしに次のバイトが現れる確率に基づいて圧縮するアプローチ）のためだけに使い、前処理段階として単純なフィルタリングを用いて、zlibに入るデータがその仮定にできるだけ合うようにしていますが、実際にはそれほど効率的とは言えません。
現代的な可逆画像フォーマットでは、これを主に2つの方法で改善しています。1つはPNGのフィルタリングに対応するピクセル予測を改良するアプローチで（フィルタの種類を大幅に増やしたり、画像の別々の部分に異なるフィルタリングを適用したりする）、もう1つはPNGのzlibに対応するエントロピー符号化を改良するアプローチです。QOIのアプローチも似ていますが、単純性のためにピクセル予測で現在位置の上側にあるピクセルをまったく使わないこと、そしてエントロピー符号化を放棄して経験に基づく差分（delta）符号化を複数用意していることが特徴です。特に1つ目の特徴のため、圧縮/展開性能とは別にPNGよりも圧縮率が落ちる傾向がありますが、これは単純性を少し犠牲にすれば改善できるように見えます。
追加説明ありがとうございます。面白いですね。
他のフォーマットを置き換える用途で使うのは難しそうですが、コードがシンプルで実装の説明も丁寧なので、読んでいて面白いコードだと思います。
https://github.com/phoboslab/qoi/blob/master/qoi.h