画像の可逆圧縮:その2
★ 因みに上の画像はRGB24ビット画像ですが、BMPファイルサイズで 49,202 バイトだったものが、 PNGファイルサイズでは 2,988 バイトになっています。 この画像を8ビットに減色してGIFファイルで保存すると 7,710 バイトになっており、 ここでもPNGファイルの方が有利なことが分かります。 可逆圧縮について ![]() したがって、JPEGで苦手なイラストやドキュメント画像のように色数の少ない画像では、 きわめて有効な画像ファイルと云えます。 或いは、レンダリング処理した3DCG画像のように高周波成分が比較的少なく、 且つ輪郭部分での劣化を嫌う画像ではJPEGより効果的と云えるでしょう。 ![]() つまり、画像の冗長な情報を取り除くために先ずは画像に偏りが出るような何らかの変換を行います。 「画像圧縮:その2」でも出てきた、たとえば画素間の線形予測のような変換をしたとき、 その変換座標軸上で予測値の発生頻度の分布を見るとそこには何らかの偏りが生じているので、 この予測値の分布に最適なハフマン符号を与えてエントロピー符号化を行えば、 それが可逆圧縮と云うことになります。 ★ 画像に冗長度が多いほどこの偏りも大きく圧縮効率もよくなるわけで、 このような画像としてイラスト絵や減色したインデックス画像、或いは3DCG画像が適していると云うことになります。 しかし、劣化を与えないと云う条件下では、線形予測してもその予測がおよそ当たっていれば良いと云うわけにもいかず、 また予測の外れる確率が高いと圧縮にはつながりません。 ★ PNGで使われるLZ77やGIFで使われるLZWでは別の方法で冗長度を除く変換を行っています。 ![]() たとえば、話を簡単にするため2ビットすなわち4色で表現する画像があって、 その4色をABCDの記号で表すとします。 そしてその画像を構成する画素の並びが、 A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B ・・・ のようになっていたとします。 この例を見ると AB 或いは ABA の並びが繰り返し出てきているので、 この辺に何か冗長度がありそうに見えます。 このような画素の並びから画像のもつ冗長度を取り除いて何らかの符号に変換することが、 ここで云う可逆圧縮となります。 ★ この変換方法として、最も分かり易いのが2値画像です。 ここでは画素列が0と1しか無いので、その並びの中で0が何個、1が何個続くか、 つまり変化点までの距離(ランレングス)に変換すれば、かなり冗長度は減らせるような気がします。 ところが、同じ2値画像でも画素の並びが市松模様だったらどうでしょう。 この方法では、冗長度は減るどころかかえって増えてしまうかも知れません。 ★ LZ77では、重複する文字列(たとえば AB とか ABA)を検出する毎にハッシュテーブルを作っておき、 次に一致する文字列がでてくれば、それは前の文字列の位置に置き換える方法を採っています。 つまり一致する距離と重複文字列の長さを対にした符号に変換しています。 そして、この距離と長さそれぞれの発生頻度に適したハフマン符号を別々に与えています。 この距離と長さそれぞれの発生頻度の分布を測定してみると、おそらく何らかの偏りを持っているでしょう。 この分布の偏り方が大きいほど圧縮率も大きく、 逆に一様分布だった場合には圧縮効果は無いことになります。 ★ 「画像圧縮:その2」でJPEGにおけるハフマン符号の割り当て方を説明してきましたが、 ここでも同様にこの分布の偏り方に応じて、その発生頻度の多い値には短い符号を、 発生頻度の少ない値には長い符号を割り当てるようにすれば冗長度の少ない符号化(エントロピー符号化)ができるようになります。 ★ その符号の割り当て方として、距離や長さの値で発生頻度の大きい順に、たとえば [0,10,1100,11010,11011,11100,11101,11110,111110,111111,・・・] を割り当てたとすれば、一番発生頻度の高い値は1ビット、 2番目に発生頻度の高い値は2ビットの符号で表現できてしまうことになります。 上例の符号間では","で区切りを付けていますが、符号化としてはこれも冗長になるので、 実際の符号化では区切りを取り除いて、 [01011001101011011111001110111110111110111111・・・] のように符号化します。 これでは一見、符号間の区別がつかないように見えますが、 同期さえとれておれば復号するときの符号間の区切りは、 JPEGの復号化と同じようにテーブル参照方法で正確に検出できるようになります。 LZ77では、ハッシュテーブルは32KBに、長さは256Bに制限されています。 尚、ここでは"文字"として表現していますが、これはバイト単位のバイナリーでもかまいません。 ![]() − 1999.12.20. − |