最近は画像圧縮に思いを馳せておりました。
という日記を書きかけていたところ一向に成果が上がらず何週間も経ってしまったので、この辺で一旦現状をまとめてみたいと思います。
TL;DR
現時点では、当初の目標に到達できる見込みがたっていません。
deflate が意外とバランスよく優秀だったとわからされているところです。
MPIC2
去年開発した非可逆圧縮画像形式の MPIC は、以下のコンセプトにおいて写真等では PNG よりも高い圧縮率を実現し、一定の成果を出せていると思います。
課題が全くないわけではないですが、このコンセプトを維持したままこれ以上の改良の余地はあまりないと思うので、今後 MPIC2 を開発する可能性はおそらく低いと思います。
一方で、 MPIC には苦手な分野やカバーできない分野があるため、新しい圧縮方式を考えていました。
ライバルは PNG ？
新しい画像形式に必要な要素をまとめていくと PNG がカバーしている領域と重なるので、主に PNG と比較して性能を評価することにします。
PNG 形式をおおざっぱに説明すると、画像を圧縮しやすいように簡単なフィルタリングをかけた後、 deflate というアルゴリズムで圧縮しています。
deflate について
PNG に使われている deflate という圧縮アルゴリズムは現在広く使われているものの設計が古く、エッジケースではありますが単色で塗り潰すと圧縮されてるのに0が続くという俄かに信じ難い出力をすることがあります。
このファイルを同じく deflate を使っていることで有名な ZIP で再圧縮するとかなり小さくなります。
同じアルゴリズムで２回も圧縮できるということは、１回目の圧縮が十分ではなく改良の余地があるということになります。 また、エントロピーの観点から 0 がずっと続くような極端に偏った値は圧縮可能であるため、このような値を出力する圧縮は一般にあまり良くないとされています。
さて、 deflate は LZ とハフマンという２種類の圧縮方式を組み合わせています。 LZ は辞書圧縮、ハフマンはエントロピー圧縮に分類されます。
辞書圧縮
辞書圧縮は出現したパターン(通常3バイト以上のバイト列)を辞書に記録していき、辞書に記録されたパターンが再度出現した場合に辞書上のインデックスに置き換えることで圧縮します。
辞書圧縮で最もメジャーな方式は LZ と呼ばれる Lempel さんと Ziv さんが開発したアルゴリズムで、簡単な原理で圧縮性能が高いため多くの可逆圧縮で LZ をもとにしたアルゴリズムが利用されています。
LZ の中でも圧縮前のバイト列をそのまま辞書として使い、辞書のインデックスを現在のアドレスからの相対距離とパターンの長さで表現する方式 (LZ77/LZSS) が主流で、辞書(圧縮前のバイト列)上をスライド移動しながら処理するのでスライド辞書法とも呼ばれます。
LZ 圧縮にはトレードオフがあり、距離が最も短くかつ長さが最も長くなるパターンを探すのが理想ですが、全てのパターンを精査すると検索のためにメモリや処理時間が指数関数的に増えるので、検索を打ち切る閾値を調整することで速度優先か圧縮率優先か選択できます。 なお、検索範囲をあまり広げすぎても圧縮率はそれほど向上しません。
エントロピー圧縮
エントロピー圧縮は値の出現頻度によって符号の長さを変えることで圧縮します。
エントロピー圧縮の中でメジャーなものにハフマン符号があります。 ハフマン符号では出現頻度の差をビットの長さで表現し、正しくデコードできるようにするために CHC (Canonical Huffman Coding) というアルゴリズムで符号化する必要があります。
CHC では出現頻度を整数ビットで表現するため最頻値でも 1/8 (1bit) までしか圧縮できないなど偏りを細かく表現できない弱点があり、同じくエントロピーを使って圧縮する算術符号、レンジコーダー等ではそれらの弱点が改善されています。
エントロピー圧縮で圧縮するには値の出現頻度の極端な偏りが必要で符号の変換表も必要になるため実際には単体ではあまり圧縮できません。 しかし、 LZ 後にエントロピー圧縮を組み合わせるとより小さく圧縮可能なために組み合わせて使われることが多いです。
CHC と ANS
先述の通り CHC はデータの出現頻度の偏りをビット数の整数比で表現するために課題があります。 また、ビットの長さで圧縮する原理上ビット処理が避けて通れません。
現代の計算機は内部的には２進数で動作していますが、その上で動くプログラムはビット処理がそれほど得意ではないのであまり使いたくありません。
別のエントロピー符号として算術符号が有名ですが、いろいろあって実際にはあまり使われていません。
最近は算術符号に代わるエントロピー符号として ANS (Asymmetric numeral systems) というものが注目されているようです。
原理が難しくてまだよくわかっていませんが、簡単な整数演算だけで CHC と同等以上に圧縮できることがわかりました。
なお、 ANS は原理上 CHC に比べて符号変換表が大きくなってしまいます。
CHC はビット数がわかれば符号が復元できるため変換表の値は1〜15程度の小さな数値で済み、さらにdeflateでは変換表自体も圧縮されているのでおそらく100バイト以下になります。
一方、 ANS では変換表が通常10bit以上の大きな値になり、バイト値をANSで圧縮した場合の変換表は8bitでも256バイト〜16bitなら512バイト程度必要になり、 CHC に比べると個々の値が大きく一様な値になるためこの表自体ほとんど圧縮が見込めません。
元々サイズの大きいデータであればこの差は誤差の範囲になりますが、サイズが小さいデータを圧縮する場合は変換表のサイズで圧縮率が逆転する場合があるので注意が必要です。
今風の画像圧縮技術
まずは、自作のフィルタをいくつかの画像に適用して deflate で圧縮するプログラムを作って検証してみました。 写真等では PNG の半分くらいに圧縮できそうなことがわかりました。
写真の場合は YUV 圧縮や多くの非可逆圧縮技術が有効なため、可逆圧縮では圧縮率で太刀打ちできません。 *1
実際のところ、ぼく自身も写真の可逆圧縮にはそれほど関心がないので、こちらの方向性を今後どうするかは検討中です。
いくつかのフィルタリングを試しましたが、いわゆるドット絵やピクセルアートといわれる種類の画像については圧縮率がむしろ悪化する傾向が多いこともわかりました。 ドット絵は写真とはピクセルの偏り方の傾向が違うので、別のアプローチで検証します。
古代の画像圧縮技術
ドット絵はドット絵が主流だった古代のアルゴリズムで圧縮できるやろ！
ということで、古代によく使われたアルゴリズムを参考に作ったアルゴリズムで圧縮できるか検証してみました。
難しくない原理でそこそこの圧縮は可能ですが、 PNG には到底敵いませんでした。
さらに、圧縮後に deflate するより元のデータをそのまま deflate した方がマシな結果になることが多いという微妙な結果になってしまいました。
故きを温ねて新しきを知る
元の画像をそのまま deflate するのは芸がない（というか PNG で良い）ので、もっといい圧縮できないか考えました。
通常のLZ圧縮では一次元方向に圧縮しますが、画像は二次元データなので二次元方向もスキャンするようにした方が圧縮が期待できる場合があります。 そこで検索方法を２次元に改良したLZを実装してみました。
PNG より圧縮できることもありましたが、正直思ったほど劇的な効果もありませんでした。
２次元に改良された deflate ライクな画像圧縮といえば WebP があります。 今まではWebPは写真や動画向けの画像圧縮だと思っていましたが、調べてみるとロスレスモードならドット絵を PNG と同等以上に圧縮可能なことがわかりました。
この分野で開発を続けるのは分が悪いかもしれません…
To be concluded？
現時点では、当初の目標に到達できる見込みがたっていません。
これ以外にも色々変換して実験しましたが、ほとんどのケースで思ったほどの効果が得られないか、フィルタの存在がノイズになって圧縮率が低下するという結果になり、 人間の目には圧縮できそうなデータも実際に圧縮しようとするのは思ったより大変なことがわかりました。
deflate が意外とバランスが良く、 WebP という強力なライバルもいるのでなかなか道は険しいようです。
