yunomuのブログ

趣味のこと

JPEGを読む(3) ハフマン符号の復号準備

JPEGを読む

JPEGを読む(2) ハフマン表定義(DHT) - yunomuのブログ これのつづき

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

　ハフマン符号表があればscanのペイロードをデコードできる。復号手順はAnnex FのF.2に書いてある。

　JPEGでは8×8のブロックごとにDCTをかけて64個のDCT係数を計算する。DCT係数は本文ではZZ(k) (0 ≦ k ≦ 63)と表現されている。8×8=64のブロックをジグザグ(Zig-zag)に走査しているのでZZらしい。

　ZZのうち最初の係数ZZ(0)をDC、以降の63個(ZZ(k) (1 ≦ k ≦ 63))をACと呼ぶ。DCとACでは符号化/復号化の手順と内容が少し違っている。

　DCはDCT係数のリストの中で直前のブロックのDCとの差分が記録されている。つまりi番目のブロックのDCの値DIFFiは以下のようになる。

  • DIFF0 = DC0
  • DIFFi = DCi - DCi-1

　ビット列からDIFFを取り出す手順はF 2.2に書かれている。

T = DECODE
DIFF = RECEIVE(T)
DIFF = EXTEND(DIFF, T)

　この中のDECODE, RECEIVE, EXTENDは以下の通り。

  • DECODE: ハフマン符号の復号処理
  • RECEIVE: 指定したビット数のビット列を読み取る処理
  • EXTEND: ビット列を正負符号を考慮して差分値に戻す処理

　ここでわかる通り、JPEGでハフマン符号化する値は値そのものではなく、値を表現するために必要なビット数だったということになる。値を直接符号化するとハフマン符号表が大きくなりすぎるので、読むべきビット数を符号化してヘッダみたいに付加した方が全体としての圧縮率は上がるということなんだろう。

　具体的には、前回の表に照らし合わせると、例えば1を表現しようとすると、1は0b1なのでビット長は1。ビット長1を表すハフマン符号語は0b010なので、1は0b010と0b1を合わせて0b0101と表現されることになる。同様に18は0b10010で5ビットなので、5ビットを表わす符号語0b110を付加して0b11010010となる。冗長な気がしなくもないけど、差分符号化で0付近へのデータの偏りを高めた状態で適用すると値部分のビット長が短くなるので、最終的に圧縮効率を上げることができるのだろう。

　ACの方はFigure F.13, F14にある通り少しだけ複雑になっているけどおおむねDCと同じ。つまりまずはDECODE, RECEIVE, EXTENDあたりを読み解いていこう。

　まずDECODEに先立ってDecoder_tablesというMAXCODE, MINCODE, VALPTRの3つのテーブルを作る。

　これを前回のHUFFCODEテーブルに適用すると以下の3つの表ができあがる。書くのが面倒なのでひとつにまとめた。

ビット長 MAXCODE MINCODE VALPTR
1 -1
2 0 0 0
3 6 2 1
4 14 14 6
5 30 30 7
6 62 62 8
7 126 126 9
8 254 254 10
9 510 510 11
10 -1
11 -1
12 -1
13 -1
14 -1
15 -1
16 -1

　この表はそれぞれ以下のものを表している。

  • MAXCODE: そのビット長の符号語の中で、符号語を数値として見た時に最大値のもの
  • MINCODE: そのビット長の符号語の中で、符号語を数値として見た時に最小値のもの
  • VALPTR: HUFFCODEテーブルの中で、そのビット長の符号語が始まる位置のインデックス

　言われてみれば、切れ目無く符号語と数値が連続したビット列を解読するにあたり、このような補助テーブルがあると便利かもしれない。

　これらの表を格納するにあたり、前回作ったhufftable構造体を拡張する。

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

    maxcode map[int]int
    mincode map[int]int
    valptr  map[int]int
}

　あとはアルゴリズムを整理して実装。前回のmakeHufftableも拡張して補助テーブルも生成するようにする。

func makeDecoderTables(bits [16]uint8, huffcodes []*huffcode) (map[int]int, map[int]int, map[int]int) {
    maxcodes := make(map[int]int)
    mincodes := make(map[int]int)
    valptr := make(map[int]int)
    var j int 
    for i := 0; i < 16; i++ {
        if bits[i] == 0 { 
            maxcodes[i+1] = -1
            continue
        }

        valptr[i+1] = j 
        mincodes[i+1] = int(hufftable[j].code)
        j += int(bits[i]) - 1
        maxcodes[i+1] = int(hufftable[j].code)
        j++
    }

    return maxcodes, mincodes, valptr
}

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

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

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

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

    maxcode, mincode, valptr := makeDecoderTables(bits, huffcodes)

    return &hufftable{
        class:     class,
        target:    target,
        huffcodes: huffcodes,
        maxcode:   maxcode,
        mincode:   mincode,
        valptr:    valptr,
    }
}

　これでハフマン符号デコードの準備はできた。けどいくつかある符号表のどれをどのscanブロックで使うのかがまだわからないので次からは全体の構造を読まなければならない気がする。順序がめちゃくちゃだけど。