読者です 読者をやめる 読者になる 読者になる

Tech と Culture

テクノロジーとカルチャー

JPEGのハフマン符号 (4) デコード用 ハフマン符号テーブルの生成

ここでは、ハフマンテーブルセグメントの情報から実際のデコードに使うためのテーブルを生成する方法を記します。
JPEG規格ドキュメントの Annex C に相当します。

例として以下のハフマンテーブルセグメントを持つ場合を考えます。
jpegsnoopの出力ファイルの一部 - samplehufftbl.txt
もちろん、実際のセグメントに含まれる情報は、
Total number of codes: 009
の行までです。それ以降のコードを求めている部分はjpegsnoopが算出しています。
samplehufftbl2.jpg
実際には、このようにハフマンテーブルセグメントは記述されています。
1bit符号0個、2bit符号2個、3bit符号3個、、、、と個数が並び(1)、その後それぞれの対応する値がつめて並んでいます(2)。
JPEG規格ドキュメントの中で、(1)をBITS(I)という配列名で呼び、(2)をHUFFVAL(I)という配列名で呼んでいます。

まず、BITS(I)からHUFFSIZE(K)と呼ばれるサイズテーブルを生成します。        
       gensizetbl.jpg
これは非常に単純なアルゴリズムで以下のようにコードを詰めて並べたときに順番に何ビットのコードが格納されているかを示すHUFFSIZE(K)を生成しています。
huffsizek2.jpg

次にHUFFCODE(K)と呼ばれる、ハフマンコードを左から詰めた配列を生成するフローチャートが載っています。
       genhuffcodetbl.jpg
このアルゴリズムも単純なものです。ここで、SLLというのは、Shift-left-logicalの略です。
ここでJPEGのハフマン符号のつけ方が分かります。nbitの符号すべてをつけ終わったら、符号に1を足して次の符号のビット数に応じて左シフトしたものをハフマン符号とします。

以下が先ほどの例に対応するものです。実際のハフマン符号が格納されている配列HUFFCODE(K)が生成されます。
samplehfcdtbl2.jpg

最初に見たようにJPEGファイルの中には HUFFVAL(I)という、ハフマンコードに対応する値を格納した配列が記録されていますので、HUFFCODE(K)とあわせればデコードできることになります。

JPEG規格ドキュメントの Annex C には、他に EHUFFCO という真の値に対するハフマンコードを格納した配列の生成フローチャートが載っていますが、エンコード時にしか使いませんので、ここでは飛ばします。