« Android 対応必要項目と工数見積もり | メイン | Lanczos3 を組み込んだ »
2014年03月10日
Misc.:: mozjpeg はどのようにして圧縮率を上げているのか？
Tweet @jin1016をフォローざっくりソースコード見たりしただけなので、間違っているかもしれないが書いておく。
一言で書くと「プログレッシブ方式で、DC成分の分割サイズを最適なものにすることで偏りを増やし圧縮率を上げている」ということのようだ。
この説明だと知っている人以外にとっては意味不明だと思うので、どのように圧縮しているのかある程度説明し、なぜ圧縮率が上がるのか説明してみる。
JPEG では、色空間変換 → DCT → 量子化 → ハフマン符号化+ランレングス と言う手順で圧縮している。
この中で実際に圧縮を行っているのは、「ハフマン符号化」と「ランレングス」の部分。
これらはデータの偏りが大きいほど圧縮率が上がる。
わかりやすいランレングスを説明すると、00000000 と8個0が並んでいるとすると、これを0×8と表現することでデータを圧縮している。
ハフマン符号化は、もう少し複雑だが今回の説明を理解する上ではだいたい似たようなものと言う認識で構わない。
実際に圧縮行っている処理から、データの偏りを大きくできれば、圧縮率が上がることがわかる。
このデータの偏りを大きくする処理が JPEG では DCT と 量子化 と呼ばれる処理。
DCT とは、離散コサイン変換の略で、周波数領域に変換する処理。
画像を周波数領域に変換？と言われても意味は分かりづらい。
音だと高い音や低い音に分ける処理に当たるので、音だと直感的に理解しやすい。
画像でも同じように変換すると変化が大きいところは高周波成分に、変化が少ないところは低周波成分に当たる。
JPEG では、高周波成分を荒くすることで圧縮率を上げているので、エッジなど変化の大きいところがぼやけやすい。
圧縮率を高くすると、より荒く記録するので、よりぼやける。
( 高周波成分は画質への影響が少ないので荒く記録する )
荒く記録するというのが、量子化に当たる処理。
量子化と言うたいそうな名前がついているが、JPEG で実際に行うのは単なる割り算。
例えば、元の値 100 を 50 で割り、出てきた値 2 を記録する ( デコード時は逆に 50 をかければ元に戻る )。
ここでは綺麗に割り切れる値を使ったが、実際は小数点以下の値も出る。
この小数点以下の部分は捨てて記録するので劣化が起こる。
ここが荒く記録するという部分。
大きな値で割ると、数値は 0 に近づいていく。
高周波成分ほど大きな値で割るので、高周波成分は 0 が多くなる。
これら DCT と量子化は8x8のブロック単位で行われる。
ここからが mozjpeg に関係する部分。
通常方式はブロックごとに記録していくが、プログレッシブ方式では周波数帯単位などで記録していく。
ブロック単位では8x8=64個の範囲で高周波と低周波成分が繰り返されるが、周波数帯単位で記録していくと、低周波成分、高周波成分が連続して記録される。
高周波成分が連続するということは、0 が多く連続する。
つまり、偏りが大きくなり圧縮率が上がる。
どのように周波数帯を分割して記録するのが最適かを求めて記録するのが mozjpeg が行っている処理のようだ。
ここまでの説明からわかるようにプログレッシブ方式にするだけでも、ある程度圧縮率は向上する様子。
元々プログレッシブ方式は、遅い回線で少しずつ画像が表示できるようにするものだったが、これが圧縮率向上に寄与するというのは興味深い。
----------------------------
2014/03/12 追記
「どのように周波数帯を分割して記録する～」の部分について勘違いしている人がいるようなので補足。
周波数帯を変更するのではなく、DC係数を何個ずつに分けるか、もしくはさらに何ビットずつに分けるかというもの。
プログレッシブが元々そのように分割できたので、その分割方法の中で最適なものを選択するということ。
投稿者 Takenori : 2014年03月10日 23:27
comments powered by Disqus