yunomuのブログ

趣味のこと

JPEGを読む(9) AC係数のデコード(DCT、量子化)

AC係数のデコード

 8×8のDCT係数のうち先頭を除く63個をAC係数と呼ぶ。(3)で後回しにしたAC係数の部分を見る。

JPEGを読む(3) ハフマン符号の復号準備 - yunomuのブログ

 この中のDecode_ZZ(K)の部分はDCと同じで、RECEIVEしてEXTENDしている。DCと異なるのはDECODEで取得したハフマン符号値の扱いになる。

RS = DECODE

SSSS = RS modulo 16
RRRR = SRL RS 4
R = RRRR

 とあるように、DECODEでハフマン符号を読み取り、取得した値を上位と下位の4ビットずつに分けている。SSSS = 0の時は一旦無視して、上位4ビットの表す数RだけZZのインデックスKをスキップしている。そしてDecode_ZZ(K)SSSSの示す値をZZ(K)に格納する。Rは4ビットしかなく15までの値しか表現できないため、ZZの中で0が15以上連続する場合はSSSS = 0とする。

 つまりAC係数は0についてのみのランレングス符号化されている。おそらくほとんどの値が0なんだろう。

DCTとZZと量子化の関係

 ちょっと一旦わかったことまとめ。

DCT(離散コサイン変換)

 ここでちょっとDCTの話。定義はここで紹介されているのがわかりやすい。

離散コサイン変換 - MATLAB & Simulink - MathWorks 日本

 要するに、8×8の値を8×8=64種類の正弦波の和として表現し、それぞれの重みを8×8のDCT係数に変換するということ。8×8行列の値を8×8行列に変換しても情報量は変わっていない気がするけど、画像の場合は8×8の中でそれほど複雑に値が変化しないので、DCT係数のほとんどが0になる。この0が続く部分をランレングス符号で圧縮することができるので、画像の圧縮にはよくDCTが使われるらしい。この段階では情報の欠落は発生していない。

 DCTの定義を見ると、DC成分は周波数0を表していて、他の値のベースになるので確かに必ず値が入っていそうではある。かつ隣の8×8ブロックとの連続性もありそうなので、DCだけを差分符号化するのは理に適っている。コンポーネントのH, Vの値で近隣の8×8ブロックをグループ化していたのも、差分の絶対値を小さくする効果がありそう。絶対値が小さいと値を表現するビット数が少なくなる。ビット長が短い方に偏るので、ビット長を表現するハフマン符号の圧縮効果も高くなる。

ところでもしかしてDCとかACって直流と交流ってこと?

Zig-zag sequence

 8×8=64個のDCT係数はFigure A.6のジグザグ順序で配列ZZに格納する。

 これもどうしてかと思っていたんだけど、DCTの周波数が少なく単純なデータから順に並べることで0が連続する部分を増やし、ランレングス符号の圧縮効果を高めるためなんだろう。

量子化

 最初の方で飛ばしちゃったけど、JPEGファイルの最初の方に量子化表(DQT)という64個の値がある。

 Figure A.5の符号化/復号化の流れを見ると、これは単純に符号化時にDCT係数を量子化表の値で割り、復号化の時に掛けている。

 これにより、DCT係数ぞれぞれの絶対値が小さくなる。

 ただしRoundがかかっているので、情報の欠落がそれなりに発生する。元の成分値が105で量子化係数が50だった場合、符号化後は2、復号後は100になり、元の値と5だけずれてしまう。つまり量子化表が品質とファイルサイズの関係を決定付けているのだろう。

 手元のJPEGファイルをいくつか見たところ、おおむね高周波数の量子化係数が大きくなる傾向があった。量子化係数50の場合は50未満は0になるので、複雑な変化は多少つぶしてしまってもいいということだろう。ジグザグ順序との関連もあるし、0が多いとランレングス符号の効果も高くなる。

 一方で[1, 1, 1, ..., 1]となっているものもあった。最高品質にするとそうなるんだろう。

JPEGを読む(8) RECEIVEとEXTEND

 ハフマン符号の復号はいいけど、その後のデータを読む部分を忘れていた。(3)のRECEIVEとEXTENDについて。

JPEGを読む(3) ハフマン符号の復号準備 - yunomuのブログ

RECEIVE(SSSS)

 SSSSビットを読み取る処理。自明かと思ったけどちゃんと説明されていたので一応読む。SSSSというのは4ビットの数値というだけで特に意味があるわけではない。

 1ビット読み取る関数NEXTBITがあって、特筆することはない。コードは以下。

func (d *Decoder) receive(l int) (uint8, error) {
    var ret uint8
    for i := 0; i < l; i++ {
        b, err := d.nextBit()
        if err != nil {
            return 0, err
        }

        ret = ret<<1 + uint8(b)
    }

    return ret, nil
}

NEXTBIT

 NEXTBITも細かい解説がある。

 変数CNTBに状態を保存してある。基本的には1バイトずつ読み取ってBに保存しておき、そこからNEXTBITを呼び出される度に1ビットずつシフトして取り出していく。8回読み終えると次の1バイトを読む。読んだ1バイトがDNLマーカーだった場合はスキャンを終了する。ついでなのでDNLの読み取りも実装するとこうなる。

type Decoder struct {
// ...

    bitMask uint8
    bits    uint8 
    numLine uint16
}

import "errors"

var (
    EOS = errors.New("end of scan")
)

func (d *Decoder) readDNL() (uint16, error) {
    ld, err := d.readUint16()
    if err != nil {
        return 0, err 
    }   

    if ld != 4 { 
        return 0, errors.New("Unexpected NDL length")
    }   

    return d.readUint16()
}

func (d *Decoder) nextBit() (uint16, error) {
    if d.bitMask == 0 { 
        b, err := d.readUint8()
        if err == ErrUnexpectedMarker {
            d.unread()
            m, err := d.readMarker()
            if err != nil {
                return 0, err 
            }

            if m == Marker_DNL {
                l, err := d.readDNL()
                if err != nil {
                    return 0, err 
                }

                d.numLine = l 

                return 0, EOS 
            }

            return 0, ErrUnexpectedMarker
        } else if err != nil {
            return 0, err
        }

        d.bits = b
        d.bitMask = 0b1000_0000
    }

    bitMask := d.bitMask
    d.bitMask >>= 1
    if d.bits&bitMask == 0 {
        return 0b0, nil
    } else {
        return 0b1, nil
    }
}

 CNTだとピンとこなかったのでビットマスクで表現した。スキャンの終了はエラー値を定義して表現することにした。あとは以前に実装したDecoder#readUint8Decoder#readMarker, Decoder#unreadで簡単に実装できる。

 DNLの意味は一旦置いておく。

EXTEND(V, T)

 EXTENDは、RECEIVEで読み取った値を符号つき整数に変換する処理となる。VRECEIVEの戻り値で、TRECEIVEの引数となっている。

 フローチャートの通りに実装することは簡単だけど、このフローチャートの意味がよくわからない。というのはつまり正負の符号を含む値の表現方法を理解していないということになる。説明はF.1.2.1節とTable F.1にある。

 ここでSSSSRECEIVEの引数で、読み取ったビット数Tのこと。DIFFRECEIVEで読み取った値Vのこととなる。

 SSSS = 0の場合、ストリームを読み取ることなくそのまま0となる。

 SSSS = 1 の場合、つまり1ビット読み取った場合、1ビットには -1, 1 という2つの値が割り当てられている。これを小さい順に符号に割り当てる。

T V value
1 02 -1
1 12 1

 SSSS = 2 の場合、2ビットには -3, -2, 2, 3 という4つの値が割り当てられているので、これを小さい順に符号に割り当てる。

T V value
2 002 -3
2 012 -2
2 102 2
2 112 3

 以下同じ。

 これをアルゴリズムで表すとFigure F.12のフローチャートになる。表を見ると正の数の時 = 最上位ビットが1の時 = V < 2T-1でない時、戻り値はVの値そのままになっていることがわかる。

 このように数値をコード化している理由は、0もしくは絶対値が小さい値の出現確率が極端に多く、かつ表現する値域が広いためハフマン符号化するとテーブルが大きくなりすぎるためだと思われる。差分符号化なので絶対値が小さい値が多いのだろう。

 実装は以下のようにした。ほぼフローチャートのまま。

func extend(v_ uint8, t int) int16 {
    var v int16 = int16(v_)
    var vt int16 = 1 << (t - 1)
    if v < vt {
        return v + (-1 << t) + 1 
    }   
    return v
}

JPEGを読む(7) コンポーネント、サンプリング係数、MCUなど

 Annex Aの数学的定義を読んで実際のところ何をやっているのかを掴む。

コンポーネント(component)

 まずコンポーネントについて。コンポーネントは仕様のどこを読んでも「画像に含まれる2次元配列」という以上の情報が出てこない。

 実のところJPEG規格は2次元配列のリストを符号化する方法を規定しているだけであり、その2次元配列のデータが何を表現しているのか、画像なのかどうかすらも問題にしていない。なので原理的にはこの2次元配列のリストというデータはRGBのビットマップ値でもいいし、YCbCrでもいいし、CMYKでもいいし、他の何かでもいい。ただしJPEGには「コンポーネントのリストが何を表現しているのか」を表現するフィールドは存在しないので、JPEG形式のデータをデコードできたとしても元の画像を再現することはできない。

 そのためJPEGファイルの仕様を定めたJFIF(JPEG File Interchange Format)という仕様がある。JFIF形式では、JPEGに色空間などの情報を付加して元画像を復元できるようにしたものらしいけど、妙に複雑になってしまったし、なんやかんやあってJPEGにも規格が取り込まれていて、MIMEタイプも"image/jpeg"のままだし、だいたいJPEGと似たようなものだよ。みたいな事がWikipediaに書かれている。

JPEG File Interchange Format - Wikipedia

 JFIFでは色空間は標準ではY(グレースケール)またはYCbCrと定義されていて、このあたりが取り込まれてJPEGの色空間もYCbCrで表現するということになっているらしい。

 つまり、テスト用の画像に含まれていた3つのコンポーネントはそれぞれY, Cb, Crの成分を表現した2次元配列だったということになる。これでコンポーネントの事は完全に理解した。

サンプルと精度(sample and sample precision)

 コンポーネントが成分のことなので、サンプルというのはそのままその標本値、つまりYCbCrの値ということになる。ということは精度Pはビット数で、前回使ったファイルではP=8, X=400, Y=400だったので、このファイルはそれぞれの成分が0〜255の値をとる大きさ400x400の画像だということになる。

水平/垂直サンプリング係数(Horizontal/Vertical sampling factor)

 いろいろ書いてあるのを読み解くと、元画像の要素数X×Yだけど、コンポーネントの要素数はそこから割り引いていくということらしい。その比率はフレームヘッダのコンポーネントパラメータで示されている。

 例として、X = 512, Y = 512 の画像で、3つのコンポーネントのサンプリング係数が以下の場合、

  • Component 0: H0 = 4, V0 = 1
  • Component 1: H1 = 2, V1 = 2
  • Component 2: H2 = 1, V2 = 1

それぞれのコンポーネントCiの縦横のサンプル数xi, yiは以下のようになる。

  • Componennt 0: x0 = 512, y0 = 256
  • Componennt 1: x1 = 256, y1 = 512
  • Componennt 2: x2 = 128, y2 = 256

 つまりこの場合、コンポーネント0は水平方向の圧縮は無し、垂直方向は1/2になる。コンポーネント1は水平方向に1/2、垂直方向はそのまま。コンポーネント2は水平方向に1/4、垂直方向に1/2に圧縮されている。

 前回利用したデータでは以下のようになっていた。

  • C0: H0 = 2, V0 = 2
  • C1: H1 = 1, V1 = 1
  • C2: H1 = 1, V1 = 1

 この場合は、C0は圧縮せず、C1, C2では縦横に1/2ずつ圧縮されているということになる。C0はYなので、輝度に敏感な人の目の特性に合わせてYだけは細かく表現できるようにしようということだろう。手持ちの画像のほとんどのサンプリング係数はこのようになっていた。

データユニット(unit)

 可逆変換では1つの値を1単位(ユニット)とする。DCTを利用する場合は8×8で64個の値を1単位とする。このユニットは次のMCU(Minimum coded unit)と関わってくる。

MCU(Minimum coded unit)

 最初に出てきたFigure B.2で、Entropy-coded segmentの中に並んでいたデータ。だんだん近付いてきた。

非インターリーブ

 スキャンに含まれるコンポーネント数(Ns)が1の時は1ユニットがそのまま1MCUになる。コンポーネントC0のユニットuj, i (0 ≦ ix0, 0 ≦ jy0)に対して、x0×y0個のMCUが含まれ、

  • MCU0 = u0, 0
  • MCU1 = u0, 1
  • ...
  • MCUx0 = u0, x0-1
  • MCUx0+1 = u0, 1
  • ...
  • ...
  • MCUx0×y0-1 = uy0-1, x0-1

となる。一般化するとMCUi+j×x0 = uj, i となる。

 例として、DCT利用で x = 512, y = 256 だった場合、ユニットは 8 × 8 なので、512 × 256 ÷ (8 × 8) = 2048 となり、このスキャンには2048個のMCUが含まれることになる。

インターリーブ

 Ns > 1 の時は、インターリーブする。つまりコンポーネントをまたいだデータのブロックを1つのMCUとする。コンポーネントCiの横Hiユニット、縦Viユニットをひとつの塊として扱い、ちょっと説明が大変なのでFigure A.3のように並べる。

 水平/垂直サンプリング係数の定義により、この塊の数は各コンポーネントで同一になる。この数=MCUの数になる。そしてインターリーブの場合は1つのMCUの中にΣNsi=0Hi×Vi個のユニットが含まれている。

 例として、Ns = 3の時(スキャンに全てのコンポーネントが含まれる時)、サンプリング係数の節のコンポーネントの場合をそれぞれ計算してみると、こうなる。

  • Component 0: H0 = 4, V0 = 1, x0 = 512, y0 = 256 → (512 ÷ 8 ÷ 4) × (256 ÷ 8 ÷ 1) = 512
  • Componennt 1: H1 = 2, V1 = 2, x1 = 256, y1 = 512 → (256 ÷ 8 ÷ 2) × (512 ÷ 8 ÷ 2) = 512
  • Component 2: H2 = 1, V2 = 1, x2 = 128, y2 = 256 → (128 ÷ 8 ÷ 1) × (256 ÷ 8 ÷ 1) = 512

 つまりスキャンに512個のMCUが含まれることになる。それぞれのMCUに含まれるユニットは 4 × 1 + 2 × 2 + 1 × 1 = 9個になる。

restart interval

 DRI(Define restart interval)マーカーが存在する場合、MCUの列を定期的に区切ってrestart intervalを置くことができる。これがあることによりinterval毎に並列処理したり、ランダムアクセスしたり、差分符号化のエラー伝播を防いだりすることができる。というようなことが4.9節に書いてある。

 実際のところは私が使っているサンプルデータにDRIが無いのでよくわからない。なので一旦置いておくことにする。

 ともあれこれで今のところわからない部分は全部解決したはず。

JPEGを読む(6) フレームヘッダとスキャンヘッダ

Interpret frame header

 Figure E.7の"Interpret frame header"の部分Decoder#readFrameHeaderを作る。ビットフィールドの定義はTable B.2にあって、それぞれのフィールドの意味はこう。

  • Lf: フレームヘッダの長さ
  • P: サンプル精度。フレーム内のコンポーネントのサンプルのビットの精度らしい。コンポーネントもサンプルも精度もわからない。Annex Aに書いてあるらしいけどまだ読んでない。
  • Y, X: 画像のサンプルのライン数と列数。要するに縦横の画素数のこと。
  • Nf: フレーム内のコンポーネントの数
  • Csi: i番目のコンポーネントのIDらしい
  • Hi, Vi: i番目のコンポーネントの水平サンプリング係数と垂直サンプリング係数らしい。これもAnnex Aで説明されている。
  • Tqi: 量子化表のどれを使うか。ハフマン符号表にもあったThみたいなやつが量子化表にもあって、どの表を使うかをこの値で示している。

 これは順に読めばいいだけなのでコードは長いけど簡単。出力のためにDecoder構造体にも値を追加する。

type componentParam struct {
    c, h, v, tq uint8
}

func (p *componentParam) String() string {
    return fmt.Sprintf("(C=%d H=%d V=%d Tq=%d)", p.c, p.h, p.v, p.tq)
}

type frameHeader struct {
    marker uint8
    p      uint8
    y, x   uint16
    params []*componentParam
}

func (h *frameHeader) String() string {
    return fmt.Sprintf("p=%d (x, y)=(%d, %d) params=%v", h.p, h.x, h.y, h.params)
}

type Decoder struct {
    // (略)
    frameHeader *frameHeader
}

// (略)

func (d *Decoder) readFrameHeader() (*frameHeader, error) {
    m, err := d.readMarker()
    if err != nil {
        return nil, err 
    }   

    if !m.isFrameMarker() {
        return nil, ErrUnexpectedMarker
    }   

    lf, err := d.readUint16()
    if err != nil {
        return nil, err 
    }   

    p, err := d.readUint8()
    if err != nil {
        return nil, err
    }

    y, err := d.readUint16()
    if err != nil {
        return nil, err
    }

    x, err := d.readUint16()
    if err != nil {
        return nil, err
    }

    nf, err := d.readUint8()
    if err != nil {
        return nil, err
    }

    var componentParams []*componentParam
    for i := 0; i < int(nf); i++ {
        c, err := d.readUint8()
        if err != nil {
            return nil, err
        }

        hv, err := d.readUint8()
        if err != nil {
            return nil, err
        }
        h := hv >> 4
        v := hv & 0xF

        tq, err := d.readUint8()
        if err != nil {
            return nil, err
        }

        componentParams = append(componentParams, &componentParam{
            c:  c,
            h:  h,
            v:  v,
            tq: tq,
        })
    }

    ret := &frameHeader{
        p:      p,
        y:      y,
        x:      x,
        params: componentParams,
    }

    return ret, nil
}

// (略)

func (d *Decoder) decodeFrame() error {
    header, err := d.readFrameHeader()
    if err != nil {
        return err
    }
    d.frameHeader = header

...

 これで適当な画像を読み込むとこのような表ができる。

Marker Lf P X Y Nf
0xFFC0 17 8 400 400 3

 Nf=3なのでコンポーネントパラメータは3つある。

Csi Hi Vi Tqi
1 2 2 0
2 1 1 1
3 1 1 1

Decode scan

 スキャンをデコードする。スキャンというのは、実際に符号化されたデータが格納されたセグメントのことらしい。

 図の通り、スキャンヘッダーを読んで、あとはintervalの個数だけ繰り返しペイロードを読む。中身や個数は置いておいて、とりあえずスキャンヘッダを読む。定義はFigure B.3, Table B.4にある。

  • Ls: スキャンヘッダの長さ
  • Ns: スキャン内のコンポーネントの数。
  • Csj: コンポーネントセレクター。フレームヘッダのCiと一致して、以降のTdjTajがどのコンポーネントに適用されるかを示す。ひとつのスキャンに対応するコンポーネントのパラメータには制約があるみたいだけど一旦置いておく。
  • Tdj, Taj: このスキャンのデータを、どのエントロピー符号化表で復号するかを指定する識別子。エントロピー符号化表というのは算術符号化表もしくはハフマン符号化表のことで、TdjはDC用、TajはAC用。ここで複数あったハフマン符号化表のどれを使うかを指定している。ちなみに算術符号orハフマン符号はフレームヘッダで指定される。
  • Ss, Se: DCTの場合は1つの要素に含まれるDCT係数の配列の最初と最後の位置。1つの要素は8x8で64個あるので、それぞれSs=0, *Se"=63で固定となる。階層型DCTの時や可逆変換の時は要素の単位が変わってくるので意味のある値になるらしいけどこれも一旦置いておく。
  • Al, Ah: これらも階層型DCTや可逆変換の時以外は0なので保留。移動小数点を規定しているらしい。

 あとはこれを読むだけ。コードはフレームの時とほとんど同じで読むだけなので省略。読むと以下のような表ができる。

Ls Ns Ss Se Ah Al
12 3 0 63 0 0

 ここでもNs=3なのでスキャンコンポーネントのパラメータは3つ。こういう感じになっている。

Csi Tdi Tai
1 0 0
2 1 1
3 1 1

まだわかってないこと

 続いて、スキャンの中身を読み始める前にそろそろ全体的な構造を把握しないとわからないことが増えてきた。

  • intervalの数はどこで決まる?
  • スキャンのペイロードの長さはどこで把握する?
  • コンポーネントって何?
  • サンプルって何?
  • 精度Pって何?

 このあたりがわかっていないのでこのまま読み進めることができない。なのでAnnex Aに戻って定義を読み直す。

 その前に、一旦はペイロードの内容を全部読み飛ばしてファイルを最後まで読めるようにしてもいい。こんな感じで。

func (d *Decoder) decodeResetInterval() error {
    for {
        _, err := d.readByte()
        if err != nil {
            return err 
        }
    }   
}

 これをつなげて動けば一応、読み取ったヘッダなどを出力したりして遊ぶことはできる。

JPEGを読む(5) JPEGファイル全体の構造を読めるようにする

 一旦JPEGファイルの全体の構造に立ち戻る。構造のフローチャートはややこしいので一旦飛ばして。Annex E "Encoder and decoder control procedures"のE.2デコードの章を見ていく。

Decode image

 Decoder_setupと、SOF(start of frame)マーカーが出てくるまでマーカーを読む部分("interpret markers")があるけど、これはどちらも読むマーカーの種類は同じなのでまとめてしまっても良さそうに見える。Figure B.16と話が違うような気がしないでもないけど一旦まとめてしまおう。階層の定義(DHP)がある時が考慮されてないけど、これも一旦無視する。そうするとコードはこういうことになる。Decoder#DecodeはFigure E.6のDecode_imageDecoder#decodeMiscは"interpret markers"に相当する。

 Decoder#decodeMiscDecoder#decodeFrameは後で実装する。一旦すべて返却値は無いものとする。

func (d *Decoder) decodeMisc() error {
    // TODO
    return nil
}

func (d *Decoder) decodeFrame() error {
    // TODO
    return nil
}

func (d *Decoder) readSOI() error {
    m, err := d.readMarker()
    if err != nil {
        return err 
    }   

    if m != Marker_SOI {
        slog.Error("readSOI()", "marker", m)
        return ErrUnexpectedToken
    }   

    return nil 
}

func (d *Decoder) Decode() error {
    if err := d.readSOI(); err != nil {
        return err 
    }

    if err := d.decodeMisc(); err != nil {
        return err 
    }

    if err := d.decodeFrame(); err != nil {
        return err 
    }

    return nil 
}

Interpret markers

 Miscにあたる部分はTable E.1に記載してある。

 "merkers"というのはこのなかのいずれかのフィールドのリストらしい。ちなみにフローチャートの"Decoder_setup"の部分で読むテーブルもこの中のDRIやDACらしいので、「まとめてしまっても良さそう」と書いた理由はここにある。ここに挙がっているフィールドは全てマーカーの直後の16ビットでフィールドの長さを示してくれているので、取りあえず中身は読み飛ばしておく。これを繰り返し、Table E.1に記載されていないマーカーがきた場合は読むのをやめる。Markerの方にもそのマーカーがSOFxかどうかを判別するメソッドを足しておく。

import "log/slog"

var frameMarkers = []Marker{
    Marker_SOF0,
    Marker_SOF1,
    Marker_SOF2,
    Marker_SOF3,
    Marker_SOF5,
    Marker_SOF6,
    Marker_SOF7,
    Marker_SOF9,
    Marker_SOF10,
    Marker_SOF11,
    Marker_SOF13,
    Marker_SOF14,
    Marker_SOF15,
}

func (m Marker) isFrameMarker() bool {
    for _, fm := range frameMarkers {
        if m == fm {
            return true
        }
    }
    return false
}

func (d *Decoder) decodeMisc() error {
    for {
        m, err := d.readMarker()
        if err != nil {
            return err
        }

        if m.isFrameMarker() {
            d.unread()
            return nil
        }

        switch m {
        case Marker_DQT, Marker_DHT, Marker_DAC, Marker_DRI, Marker_COM, Marker_APP_n:
            l, err := d.readUint16()
            if err != nil {
                return err
            }

            slog.Info("other header",
                "marker", m,
                "length", l,
            )

            // skip field
            if _, err := d.readBytes(int(l - 2)); err != nil {
                slog.Error("skip")
                return err
            }
        default:
            d.unread()
            return nil
        }
    }
}

Decode frame

 フレームをデコードする。フローチャートはこう。

 これはこのとおりに実装する。Decoder#decodeFrameHeaderDecoder#decodeScanの中身は後回し。

func (d *Decoder) decodeFrameHeader() error {
    // TODO
    return nil
}

func (d *Decoder) decodeScan() error {
    // TODO
    return nil
}

func (d *Decoder) readEOI() error {
    m, err := d.readMarker()
    if err != nil {
        return err
    }

    if m != Marker_EOI {
        slog.Error("readEOI()", "marker", m)
        return ErrUnexpectedMarker
    }

    return nil
}

func (d *Decoder) decodeFrame() error {
    if err := d.readFrameHeader(); err != nil {
        return err
    }

    for {
        if err := d.decodeMisc(); err != nil {
            return err
        }

        m, err := d.readMarker()
        if err != nil {
            return err
        }

        if m != Marker_SOS {
            return ErrUnexpectedMarker
        }

        if err := d.decodeScan(); err != nil {
            return err
        }

        if err := d.readEOI(); err == ErrUnexpectedMarker {
            d.unread()
            continue
        } else if err != nil {
            return err
        }

        return nil
    }
}

 ここまでで一旦ストリームの終端まできた。

JPEGを読む(4) ストリームを読む準備

 本格的に復号していく前に、デコーダのインタフェースと補助関数を作る。既にちょっとコードに書いているけど。

外部インタフェース

 外部インタフェースは一旦こういう感じで。出力はまだどういう形式にするか考えていないので一旦無し。

import (
    "bufio"
    "io"
)

type Decoder struct {
    r *bufio.Reader
}

func NewDecoder(r io.Reader) *Decoder {
    return &Decoder{
        r: bufio.NewReader(r),
    }
}

func (d *Decoder) Decode() error {
    // TODO

    return nil 
}

 Decoderには*bufio.Readerを持たせている。おそらく入力ストリームをバイト単位で読むことが多くなると思われるので、bufio.Reader#ReadByteを使いたい。

マーカー

 JPEGファイルのマーカーも定義しておく。これはもうTable B.1を根性で書き写す。

import "fmt"

type Marker byte

const (
    Marker_SOF0   Marker = 0xC0
    Marker_SOF1          = 0xC1
    Marker_SOF2          = 0xC2
    Marker_SOF3          = 0xC3
    Marker_SOF5          = 0xC5
    Marker_SOF6          = 0xC6
    Marker_SOF7          = 0xC7
    Marker_JPG           = 0xC8
    Marker_SOF9          = 0xC9
    Marker_SOF10         = 0xCA
    Marker_SOF11         = 0xCB
    Marker_SOF13         = 0xCD
    Marker_SOF14         = 0xCE
    Marker_SOF15         = 0xCF
    Marker_DHT           = 0xC4
    Marker_DAC           = 0xCC
    Marker_RST_n         = 0xD0
    Marker_SOI           = 0xD8
    Marker_EOI           = 0xD9
    Marker_SOS           = 0xDA
    Marker_DQT           = 0xDB
    Marker_DNL           = 0xDC
    Marker_DRI           = 0xDD
    Marker_DHP           = 0xDE
    Marker_EXP           = 0xDF
    Marker_APP_n         = 0xE0
    Marker_JPG_n         = 0xF0
    Marker_COM           = 0xFE
    Marker_TEM           = 0x01

    Marker_FF            = 0x00
    Marker_Prefix        = 0xFF
)

func (m Marker) String() string {
    return fmt.Sprintf("0xFF%02X", int(m))
}

 ここでもおそらく入力ストリームをバイト単位で読むことを想定して、マーカーの値は先頭の0xFFを取り除いた1バイトだけを記録しておく。最後の2つは厳密にはマーカーではないけど、Prefix部分を表すMarker_Prefix = 0xFFと、データの中に出現する0xFFを表現するためのエスケープ用の疑似マーカー0xFF00のための値Marker_FF = 0x00も用意しておく。デバッグやエラー出力に便利なのでMarker#Stringも一応書いておく。というかこれが書きたくてtype Markerを定義した。なにかと便利なので。

マーカーと1バイトのデータを読む

 次はストリームのデータを読む補助メソッドを作る。マーカーの定義により、1バイトのデータを読んだ時の挙動は以下のようになる。

  1. 1バイトを読む
  2. 読んだ値が0xFFでない場合は、値をそのままデータとして返却する
  3. 1バイトを読む
  4. 読んだ値が0x00の場合は、0xFFをデータとして返却する
  5. それ以外の場合は、読んだ値をマーカーとして返却する

 実装するとこうなる。

func (d *Decoder) readByteMarker() (byte, Marker, error) {
    b, err := d.r.ReadByte()
    if err != nil {      
        return 0, 0, err 
    }
    
    if b != Marker_Prefix {
        return b, 0, nil
    }

    m, err := d.r.ReadByte()
    if err != nil {
        return 0, 0, err
    }

    if m == Marker_FF {
        return b, 0, nil
    }

    return 0, Marker(m), nil
}

 返却値が0, 0, nilになる場合が複数あるように見えるが、0xFF00となるマーカーは存在しないのでこれで成立している。最後のマーカーを返却する時にマーカーとして有効な値になっているかどうかをチェックした方が良いかもしれない。しなくても後でありえない位置にありえないマーカーが来るとエラーになるはずなので、特にここでチェックする必要も無いような予感はする。

 マーカーは突然出現するわけではなく、読むべきタイミングというのは予想できる。つまり基本的には「次はマーカーがくるはず」「次はマーカーは来ないはず」と思ってストリームを読む。なので以下の2つのメソッドを用意しておく。

import "errors"

var (
    ErrUnexpectedByte = errors.New("unexpected byte")
    ErrUnexpectedMarker = errors.New("unexpected marker")
)

func (d *Decoder) readByte() (byte, error) {
    b, m, err := d.readByteMarker()
    if err != nil {
        return 0, err
    }

    if m != 0 {
        return 0, ErrUnexpectedMarker
    }

    return b, nil
}

func (d *Decoder) readMarker() (Marker, error) {
    b, m, err := d.readByteMarker()
    if err != nil {
        return 0, err
    }

    if m == 0 {
        return 0, ErrUnexpectedByte
    }

    return m, nil
}

複数のバイト値や数値

 複数のバイトを一気に読むメソッド。io.Reader#Readとかで一気に読みたいところだけど、マーカーや0xFF00が絡んでくる可能性があるので結局1バイトずつ読むことになる。

func (d *Decoder) readBytes(n int) ([]byte, error) {
    var ret []byte

    for i := 0; i < n; i++ {
        b, err := d.readByte()
        if err != nil {
            return nil, err
        }

        ret = append(ret, b)
    }

    return ret, nil
}

 Annex Fを見たところ、テーブルのほとんどのフィールドは8ビットか16ビットの数値として解釈されるようなので、uint8, uint16の単位で読むメソッドも作っておく。さっそくDecoder#readBytesが役に立った。

func (d *Decoder) readUint8() (uint8, error) {
    b, err := d.readByte()
    if err != nil {
        return 0, err
    }

    return uint8(b), nil
}


func (d *Decoder) readUint16() (uint16, error) {
    bs, err := d.readBytes(2)
    if err != nil {
        return 0, err
    }

    return (uint16(bs[0]) << 8) | uint16(bs[1]), nil
}

読み戻す

 こういうパーサを書く時はトークンを1つ読まなかったことにしたり(unread, unget)、ストリームを消費せずに先頭のトークンを読む(peek)処理があると、最終的に必要かどうかはわからないけどデバッグ中とかでは役に立つ。というか実際に後で役に立ったので作ろう。peekはあとでまた読むのが面倒なので一旦unreadにしておこう。最初に書いたDecoderDecoder#readByteMarkerに手を入れる。

 まずDecoderに状態を追加する。

type Decoder struct {
    r *bufio.Reader

    // unread用のフィールド
    prevByte   byte
    prevMarker Marker
    unreaded   bool
}

 Decoder#readByteMarkerでは、値を返す時に返却値をprevByte,prevMarkerに保存し、unreadedtrueの時は保存した値を返すようにする。

func (d *Decoder) readByteMarker() (byte, Marker, error) {
    if d.unreaded {
        d.unreaded = false
        return d.prevByte, d.prevMarker, nil
    }

    b, err := d.r.ReadByte()
    if err != nil {
        return 0, 0, err
    }

    if b != Marker_Prefix {
        d.prevByte = b
        d.prevMarker = 0
        return b, 0, nil
    }

    m, err := d.r.ReadByte()
    if err != nil {
        return 0, 0, err
    }

    if m == Marker_FF {
        d.prevByte = b
        d.prevMarker = 0
        return b, 0, nil
    }

    d.prevByte = 0
    d.prevMarker = Marker(m)
    return 0, Marker(m), nil
}

 unreadの処理本体はこれでいい。

func (d *Decoder) unread() {
    d.unreaded = true
}

 これで今のところ必要な素材は揃ったはず。

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

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を表現しようとすると、10b1なのでビット長は1。ビット長1を表すハフマン符号語は0b010なので、10b0100b1を合わせて0b0101と表現されることになる。同様に180b10010で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ブロックで使うのかがまだわからないので次からは全体の構造を読まなければならない気がする。順序がめちゃくちゃだけど。