JPEGのハフマン符号 (3) ハフマンテーブルの記述

JPEGの規格の中には、ハフマンテーブルの持ち方とそのデコードをどのように行うかのフローチャートが載っています。
ここではそれについて記します。

まず、ハフマンテーブルの持ち方は以下の図のようになります。

DHTというのは、ここからハフマンテーブルが始まるというマーカーで、 0xFFDE です。
次にLhというのは、ハフマンテーブル定義長で、Lh以下何バイトあるかを示します。
先にその他の意味を説明してからここの計算方を説明します。
Tcは、その直後に来るテーブルがDC成分用かAC成分用かを示すフラグで、0ならDC成分1ならAC成分用であることを示します。
Thは、その直後に来るテーブルにつける番号です。各コンポーネント(Y,Cb,Cr)毎に何番を使うかを別の場所で指定しています。
このTc以下をテーブルの数だけ繰り返します。多くの画像では、YについてAC,DC一つづつ、CbとCr共通でAC,DC一つづつの計4つの場合が多いようです。
L1,L2,....Ln,...L16はそれぞれ、nbitの符号がいくつあるかを示す数です。
AC用では最大152個の符号がありますので、グリーディなアルゴリズムで最適符号を求めた場合、16bitをはるかに超える符号が算出されますが、JPEGではそれを16bitに押し込む方法が規格の中に記述されているようです。詳細はデコードには関係がないのでとばします。符号が最大でも16bitということはハードウェアの仕様に大きく影響します。
その後のV1,1......... が符号に対応する値です。
このようにJPEGのハフマンテーブルには符号そのものは記述されていません。

以上のことから、Lhは 2+Σ(17 + mt) という式で求められることになります。
最初の2はLhそのものが使用する2バイト。 17はTc,Th,L1,....L16までの17バイト。 mtは一つのテーブルに含まれるV1,1.... のバイト数です。　Σはテーブルの数だけ合計します。

以上がJPEGのハフマンテーブルの仕様です。これだけだと符号のつけ方に冗長性があります。JPEG仕様書には、これらのテーブルから実際の値と符号を結びつける真のハフマンテーブルを求めるフローチャートと、そのテーブルを使ってデコードするフローチャートが載っています。
次回以降のエントリでそれを説明します。