JPEGを読む(2) ハフマン表定義(DHT)

JPEG仕様(PDF) https://www.w3.org/Graphics/JPEG/itu-t81.pdf

　Figure B.16, B17あたりにフィールドが並ぶ位置のルールが書いてあるけど、これは真面目にパーサーを書くとして。

　まずはDHT(Define huffman table(s): ハフマン表定義)を読みたい。ハフマン符号そのものや符号化のアルゴリズム自体は知っていても、実際に符号表をどう定義するのかは意外と知らなかったりする。単純に考えると値と符号の組を連ねればいいのだけど、データ量削減のための符号化でそんなナイーヴなことをしているはずはない。

　定義を見ると非常に単純だ。1つのDHTにいくつかの表が含まれていて、それぞれは用途を示すTc, Thで識別されている。1つの表は2つの部分で構成される。それぞれL_iとV_{i, j}で表現される。

L_i (1 ≦ i ≦ 16): 長さがiビットの符号語の数
V_{i, j} (0 ≦ j ＜ L_i): 長さがiビットでj番目の符号語が表現する値

　これだけで用は足りるらしい。言われてみればハフマン符号は極めて規則的なので、L_iさえあれば出現する符号語のリストを作ることができる(と、わかった風に書いたがこれを理解するのに2〜3日かかった)。文書の中ではBITSと呼ばれている。V_{i, j}はそのリストに対して順に値を割り振るためのリストで、文書の中ではHUFFVALと呼ばれている。

　ここからHUFFSIZE/HUFFCODEと最終的な値の表を構築していく。それぞれの意味は

HUFFSIZE: k(0 ≦ k ＜ length(HUFFVAL))番目の符号語の長さを表すリスト
HUFFCODE: k(0 ≦ k ＜ length(HUFFVAL))番目の符号語のリスト

　なので最終的には「符号長」「符号語」「値」の3つ組の表ができることになる。Go言語で表現すると以下のコードで、最終的な目的であるhufftableを作っていくためにsizeやcodeやvalueといったフィールドを順に埋めていく作業をする。Tc, Thも一旦ここに格納しておく。

type huffcode struct {
  size  int
  code  uint16
  value uint8
}

type hufftable struct {
    class uint8 // Tc
    target uint8 // Th
    huffcodes []*huffcode
}

　前提として、JPEGのハフマン符号では符号長の最大は16ビットで、値は8ビットであると定義されている。hufftableの大きさも、valueの数だけエントリがあるわけなので当然length(HUFFVAL)と等しくなる。LとVからこの表を作るプロセスはフローチャートになっている。

　まずはHUFFSIZEから。(これもわかったように書いているが理解に1日かかっている)

　これはつまりBITS(符号長iビットの値の数のリスト)が以下のようだった場合、

BITS=[0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

FUFFSIZE(k番目の値の符号長(size)のリスト)は以下のようになるはずだ。

[2, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9]

　BITS(1)=0なので1ビットの符号は0個、BITS(2)=1なので2ビットの符号は1個、BITS(3)=5なので3ビットの符号は5個、BITS(4)=1なので4ビットの符号は1個、...、というのを表現したのが上のリストになる。

　これをhuffcodeのリストとして表現すると以下のコードになる。

func makeHufftable(class,  target uint8, bits [16]uint8, huffval []uint8) []*huffcode {
    var huffcodes []*huffcode

    // HUFFSIZE
    for i, l := range bits {
        for j := 0; j < int(l); j++ {
            huffcodes = append(huffcodes, &huffcode{
                size: i + 1,
            })
        }
    }

　BITSの値の合計値が12なので、HUFFSIZEの長さも12になる。フローチャートの通りに実装するなら最初にHUFFSIZEの長さを計算するとよさそう。

　次に、hufftableのcodeの値、つまりHUFFCODEを埋めていく。フローチャートはこう。

　これが実装は簡単なんだけど意味の理解が結構難しい。符号語のルールとして「すべて"1"の符号語は他の符号語の接頭辞でなければならない(the codes shall be generated such that the all-1-bits code word of any length is reserved as a prefix for longer code words)」というものがあるので、これのおかげで符号長毎の符号語の数のリストだけで符号語のリストを作ることができる。

　フローチャートを読み解くと以下のようになる。

最初の符号語は0 (ビット長にかかわらず)
符号語C_k-1のビット長とC_kのビット長が同じ場合、C_k=C_k-1+1
符号語C_k-1ビット長とC_kのビット長が異なる場合、C_k=(C_k-1+1)<<1

　これをコードで表現するとこう。1ビットシフトを繰り返す部分はまとめてnビットシフトするようにした。本当はフローチャートのまんま書いた方がいいんだけど(実際は2種類実装してテストしました)。

    // HUFFCODE
    var code uint16
    prev := hufftable[0]
    for _, huffcode := range huffcodes[1:] {
        code++
        if prev.size != huffcode.size {
            code <<= huffcode.size - prev.size
        }
        huffcode.code = code
        prev = huffcode
    }

　最後に出来上がった符号語リストにHUFFVALの値を割り当てていく。

　アルゴリズムはこうだけど、hufftableの値が既にHUFFVALと同じ順序で並んでいるので簡単でいい。

    // Order_codes
    for i, v := range huffval {
        huffcodes[i].value = v
    }   

    return &hufftable {
        class: class,
        target: target,
        huffcodes: huffcodes,
    }
}

　これを並べると以下のような対応表が出来上がる。今回はたまたまvalueがindex値と同じになっているけど、当然出現頻度によってここの順番はバラバラになる。