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

Tech と Culture

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

JPEGのハフマン符号 (5) デコードフローチャート

次に、JPEG規格ドキュメントの Annex F.2 にデコードフローチャートが載っていますので、そこを見ていきます。
AC成分のデコードの全体フローは以下のようなものです。
ACdecode.jpg
この中の DECODE というプロシージャが実際にハフマン符号から値を取り出すものです。
この部分は基本的にはDC成分でも同じ動作になります。

まず最初にデコードで使用する内部テーブルを生成します。
以下の図に、MINCODE(K), MAXCODE(K), VALPTR(K)という3つの内部テーブルの生成方法が載っています。
      gendcdtbl2.jpg
前回のエントリーのハフマンテーブルセグメントの例で実行すると以下のような結果が得られます。
minmaxcode.jpg
ここで得られた3つの配列と、jpegファイルのハフマン符号セグメントに記述されている HUFFVAL(I) を用いてデコードを行います。

decodeflow.jpg
1bitづつ順番にフェッチします。それが該当するビット数のMaxcode(k)より小さかったらマッチです。実際の値が入っているHUFFVAL(I)のインデックスは VALPTR(K) より求めることができます。 ここで、そのまま VALPTR(K) の値をインデックスに使うと、該当ビット数でもっとも小さい符号に対応する値が取得されてしまいます。JPEGの符号のつけ方は以前のエントリで理解しましたが、同じビット数の符号は順番に1インクリメントすることによって生成されています。
よって、今フェッチしたビット列とmincode(k)との差をVALPTR(K)に足すことにより対応する値が配置されているインデックスを得ることができます。インデックスが分かれば、ただ単に対応するHUFFVAL(I)の値が求める値となります。

デコードの実装はいろいろな方法が考えられます。ハードウェアにする際には1ビットづつシフトしてフェッチしていく方法をとるか、又はまとめて16ビットフェッチして並列に比較演算するか等の検討が必要になります。しかし、JPEG規格ドキュメントのフローチャートを理解しておいて損はありません。