思い立ったが吉日、ということで、ここ数日は可逆画像圧縮フォーマットを作ってました。
用途は吉里吉里なので24bitフルカラーあるいは8bitαチャンネルつき24bitフルカラー画像用です。
吉里吉里にはTLG5という独自のフォーマットがあるのですが、これは展開速度重視型で、展開速度は速いのですが圧縮率がさほどよくありませんでした。
速度も圧縮率も少なくともPNGよりは高速で、PNGの代用になるといいよね、ぐらいの目標で作ってました。
まあ、それだけならばERIがあるので、作ったとしても自己満足で終って、公開するに至らなかったと思うのですが、作ってるうちにいつの間にかJPEG2000の可逆モードの圧縮率をおおむね超えるようになったので、TLG6として採用することにしました。
まだあまり最適化してないですが、展開速度は、最低PNGの2倍以上は出せると思います。展開速度重視のTLG5の展開速度はどうも超えられそうにないです。圧縮率ではTLG5を大幅に上回ります。
アルゴリズムはMED(Median Edge Detector)＋色チャンネル相関フィルタ＋ゴロム・ライス符号です。
MEDで輝度の予測値を算出して、それとの誤差をとります。色チャンネル相関フィルタでチャンネル間の輝度の相関性を利用して情報量を減らします。最終的にそれをゴロム・ライス符号で圧縮するのですが、値0が連続する部分はラン・レングス圧縮します。直行変換系は使っていません。
輝度の予測とかいうと、上、左上、左のピクセルの輝度の平均、とか考えますが、MEDは面白いですね。左のピクセルの輝度をa、上のピクセルの輝度をb、左上のピクセルの輝度をcとすると、
unsigned char do_med(
unsigned char a,
unsigned char b,
unsigned char c) {
unsigned char min_a_b = a>b?b:a;
unsigned char max_a_b = a<b?b:a;
if(c >= max_a_b)
return min_a_b;
else if(c < min_a_b)
return max_a_b;
else
return a + b - c;
}
みたいなコードになります。単純な平均や微分よりもうまく予測できるようです。
MEDは、上記をRGBAに対して行います。一見複雑そうで、しかもすべてのピクセルに対して行うので演算量が多そうですが、MMXおあつらえむけの演算で、(MMXが使用できれば)あまり速度的な問題にはなりません。相関フィルタもMMXおあつらえむけです。
展開速度の鍵となるのは、ゴロム・ライス符号をいかに高速に展開するかです。なんとかガリガリ最適化していきたいです。
