符号の検討(1)

忙しく、だいぶ間が空いてしまった。まだ忙しい状態は続くが、研究は地味にエンジンをかけていきたい。

Macが故障してpelican環境が壊れたのでブログを刷新。

これまでの動きをまとめる。まず12月下旬〜年明けは符号に突っ込んでいた。

例の卒論の結果から、再帰的Golomb-Rice符号の符号パラメータの最適化ができそうというところに目をつけて、できたのでコーデックに組み込んでいた。圧縮率はわずかに上がったし、何より、指数移動平均による更新処理がなくなりデコード速度が上がったのが大きい。
Flake（FLACの最適化エンコーダ）（公式, GitHub ）に割と衝撃を受けている。最大圧縮設定で当時のTAKに迫っている。やっていることはブロック単位で符号長さが最小になるようにGolomb-Rice符号のパラメータとLPC次数を定めている。
- 次数が意外に重要な要因なのかも。多すぎて悪化要因になっている？
- Partitioned-Rice（ブロックを分けてその範囲でパラメータを設定するアイデア）はいままで懐疑の目で見ていたけど、性能の良さから採用に傾いた。
- また、 32bitのbitioもここに実装がある。 参考にすべき。

その後1月下旬は研究会があったのでその準備。そのあたりで並行してRustのお勉強、とても素晴らしい言語。商業的にも意味があると思うし、是非ともマスターしたい。

引き続き符号に着手。まずは近いと指摘があったblock Gilbert-Mooreの詳細を見ていく。記憶上ではレンジコーダの一種だと思ったが…？

まずGilbert-Mooreはレンジコーダと思ってもらっていいはず。
- Arithmetic coding
CODING OF PREDICTION RESIDUAL IN MPEG-4 STANDARD FOR LOSSLESS AUDIO CODING (MPEG-4 ALS) 再帰的Golomb-Riceに似ている。小さい残差ではblock Gilbert-Moore、大きければ普通のGolomb-Rice。
- これをBGMC(Block Gilbert-Moore Codes)と呼ぶらしい（Data Compresssion - The complete reference本より）
- 論文では、LSB部分を直接送ることもしている。
- MPEG4-ALSの実装も多分この論文のとおりになっている。

公開されているコードを見ると、やはりレンジコーダに見える。 LSB部分を直接送ることで、頻度テーブル s_freq が大きくなりすぎないようにしている。

/*
 * Encode a symbol using Gilbert-Moore code.
 * delta -- step size in the s_freq[] distribution.
 */
static void bgmc_encode (unsigned int symbol, int delta, unsigned short *s_freq, BITIO *p)
{
    register unsigned int high, low, range;

    /* get current range: */
    high = p->high;
    low = p->low;
    range = high - low + 1;

    /* narrow the code region to that allotted to this symbol: */
    /* aiki: ここがまさにレンジコーダ. 下限と上限をテーブル引きで高速に計算できるようにしている */
    high = low + ((range * s_freq [symbol << delta] - (1 << FREQ_BITS)) >> FREQ_BITS);
    low  = low + ((range * s_freq [(symbol+1) << delta]) >> FREQ_BITS);

    /* renormalize interval: */
    for ( ; ; ) {

        if (high < HALF) {
            put_bit_plus_follow (0, p); /* output 0 if in low half  */
        } else
        if (low >= HALF) {              /* output 1 if in high half */
            put_bit_plus_follow (1, p);
            low -= HALF;
            high -= HALF;               /* move down by half        */
        } else
        if (low >= FIRST_QTR && high < THIRD_QTR) { /* middle  */
            p->bits_to_follow += 1;     /* output an opposite bit   */
            low -= FIRST_QTR;           /* move down by a quarter   */
            high -= FIRST_QTR;
        } else
            break;                      /* otherwise exit the loop  */

        /* scale interval up: */
        low = 2 * low;
        high = 2 * high + 1;
    }

    /* update encoder's state: */
    p->high = high;
    p->low = low;
}

s_freq を眺めていると、指数的に減少していく頻度テーブルで（おそらく幾何分布orラプラス分布から来ている）、TAKの xcodes に似ているなと思う。TAKはレンジコーダを使っていたのか？？

Related Posts: