JPEG DC成分のハフマン圧縮

再び挑み、ようやく目の前が開けてきました。今 3:30AMです。

そもそもの間違いは、JPEG losslessのDC成分に関するハフマン符号化圧縮についての大きな誤解でした。アルゴリズムの書籍などで紹介されているハフマン符号化では、ハフマン木を用いて符号化します。これによって、効率的に一意瞬時符号化・復号化が可能となるビット列を得ることができます。しかし、これらの書籍で紹介されているものは、その符号に対応するデータが1:1で対応付けられているのです。従って、最終的にはハフマン符号と対応データの対応付けの表が出来上がることになります。

しかし、JPEG Lossless DCではこれをしないのです。そこでのデータ格納形式は、ハフマン符号が表しているものは、データではないのです。データでなく、データを表現するビット数なのです。JPEG規格書では、この「データを表すビット数」のことを、「カテゴリー」と呼んでいます。日本語訳では、「分類」と訳されています。

これは一体何を表すのでしょうか? よく、が出てきます。これを理解できませんでした。しかし、ついに本日理解しました。このビット数、つまりカテゴリーで表されるビット数のデータをビット・ストリームから取り出すのです。例えば

カテゴリ3に属するハフマン符号が “10” だとします そうすると次のビット列は

10110111110100

はどうなるでしょぅか?
これは 1010111110100 という風に判断されます。

つまり、赤字部分がハフマン符号であり、この部分がカテゴリ3に属するものと判断されます。従って、引き続く 3 bitsつまり青字部分がデータということになります。

101を二進数と考えられば、その値は 2x2x1 + 2×0 + 1 = 5ということになり、結果的に10101の 5 bitsで5という数字を表すことができました。もともと5という数字は 通常 8 bitsで表現されますので、この操作によって、 8 -> 5 というように 3 bits節約されたことになります。つまり、(8-5)/8 = 37.5%の圧縮率が達成されたことになります。

ここで、ピクセルのビット数、つまりレベルを8 bitsとします。これは通常用いられているもので、そもそも人間の眼が識別できる濃度差の限界とも言えるものです。もちろん、DICOM XAでも 8 bitsの濃度差しか使用していません。濃度差が 8 bitsということは、0から255までの値が当てはまります。

さっきの方法で圧縮しようとしても、例えば255というデータを表すためには 8 bits必要ですから、8 bitsのデータビットの前に、8 という数字を表すハフマン符号がつけたされることになります。そうすると、今度は逆に余計なビットが付加されることになり、圧縮どころかデータ量の拡大が起こってしまいます。しかしながら、実際の画像ではここで一工夫することにより、データがゼロの周囲に収束するようにしています。それは、ピクセル毎の差分値を用いるのです。自然画像では、濃淡はほとんどの場合滑らかに変化します。ということは、差分を取れば祖値は小さい、ということになります。JPEG輝度DC成分では自然画像のこの性質をうまく利用します。

実際にJPEG 輝度DC成分では、ここでのデータは、隣のピクセルとの差分値を当てることになっていますので、その大部分は一桁の値に集積することになります。さらに、工夫してあり、差分は、左右に隣のピクセルと行うのではなく、ジグザグに隣り合うピクセルとの間で差分を取るのです。

ここまで理解すれば、いかにアルゴリズム本の「ハフマン符号化」とは異なるかが分かります。そして、この違いが JPEGに対する理解を妨げているのです。そもそも何故、このようなややこしいことをしているのか? これは実際にもっと理解を進め、プログラムを書いてテストしなければなりませんが、現段階で言える僕の推測は・・・


JPEG規格制定当時、コンピューターで表される画像のサイズは比較的小さく、せいぜい1,024 x 1,024ぐらいしか無かった。従って、8 bitsの濃度を表す1:1のハフマン符号:データ の対応付け表を画像データの中に持てば、そのハフマン符号表部分が冗長なデータとしてサイズが巨大になってしまった。
結果的に、上で述べた方法、つまり、データとの直接変換表は持たずに、画像データそのものの中に埋め込んだ

このように理解しています。