連載するかどうかはわかりませんが勉強しておもしろかったのでネタにしてみます。今回のネタは「整数精度DCT」というやつです。これはH.264のブロック変換で使用されている変換で、H.264の中では数式的に重要となる項目だと思います。これをどうやって考えているか、が意外とおもしろかったですし。H.264が整数精度DCTを使っていることは書いてあってもどうやって考えているのか？について書いていない物がほとんどだと思うので何となくです。
今回の記事ではH.264で4x4DCTを行うときに必要となる4SamplesでのDCTを整数精度で計算する、ということをやってみます。これができれば4x4DCTは行方向と列方向に演算を行うだけなので難しいことはないですし、式の形で見ることができれば本体のコードを見なくてもSIMDを使った高速化も考えやすいと思います。
ちなみに、H.264について勉強した理由は次にADV用動画フォーマットを拡張するときにたぶん基礎となる考え方になるはず、と思ってやっています。自前のフォーマットはMPEG1を参考にして作っているので今となってはいろいろとまずい点が見えるようになりすぎているということで・・・。
4SamplesDCTを行列形式で書いてみる
まずはおさらい、というわけでこれです。一応前に画像変換を組んだときのDCTに関する記事も参考にするといいかも。
参考の記事にも書いてありますが、まずは基本式から。画像変換ではDCTとしてDCT-Ⅱを使います。その式は
となります。今回は4Samplesですので、N=4となります。また、以降の行列ではcosに関するを係数を簡略化するために
という記述を用いるものとします。(8Samplesではないので分母が違う)。これを使って行列形式で変換を書くと
となります。参考記事と見比べてみればいいですが、形は同じです。なお、逆変換はこの行列が直交行列であることからこの行列を転置した物になることを前提としておいてください。
ここから行列を簡略化していく
変換行列の中身をがんばってきれいにしていきます。ついでに整数精度で計算できる様に一部の近似および計算の簡略化を行っていきます。この場合の「整数精度で計算」とは、整数の加減算、整数定数の乗算(2の乗数なら左シフト)、2の乗数の除算(=右シフト)で構成されるような計算を指します。
まずは√2に関する項目を中に入れてしまいます。するとこうなります。
・・・きれいになったのかどうかよくわからないですね。で、問題は残っている二つの定数です。この定数を実際に計算すると以下の様になります。
さすがにcosを計算しただけなので小数ではどんな関係になっているかよくわからないですね。一応三角関数の値なので関係式を作ろうと思ったら作れなくはないですが今回はそういうことは考えないでもっとストレートにやってしまいます。この二つの定数をある値で近似して、もし以下の様な関係式
が成り立つ様にγの値を決めるとDCTの変換行列は以下の様になります。
これならだいぶきれいですよね。最後にこれを実際の計算の形に直してみると
となって、y1とy3の最後の除算を除けば整数の加減算および2の乗除算だけで構成できることがわかります。
逆行列の行列を見てみる
最後の除算に無理数や定数が一つはいっていますが、これに関しては逆行列と組み合わせると見事に無効化することができます。DCTの変換行列は直交行列であり、逆行列は変換行列の転置で求められる、ということを使って整数精度変換時の逆行列を求めるとやっぱり転置行列になるので、
という行列の計算となります。実際の計算では縦に似た様な定数が並んでいるのでそれをあらかじめ計算することで簡略化することができ、
もしくは
というきれいな形になります。こちらも「あらかじめ計算」が終わってしまえば整数の加減算および2の乗除算だけで構成できることがわかります。ここで注意点としては「あらかじめ計算」されている定数と正変換時に除算している定数を見ればわかりますがここの部分は見事に打ち消すことができます。このことを考慮して除算する定数を変更して計算してもかまいませんし、無理数になる部分を誤差が少なくなるように別の定数に絡めて演算する、というのもあります。
γにはどんな値が入るのか？
最後のお題がこれです。ここまでの議論は近似するγとして適当な値をとってこれたときにこんなことができる、というだけでγとしていい値が取れなければ今までの論議は見事にご破算になります。一応γの近似元となる値の定義から1/3～1/2の値を選ぶとよさそうな気がする、ということがわかります。一次元レベルでであれば多分これ以上進むことはできないでしょうね。本当に「適当な」値をとって考えるのが正しい、という結論になるのでしょうが、今回の場合は二次元、つまりもう一回同じ式を使って変換する、ということになるのであればできる限り簡単な有理数の平方根として取ってくるとその前後の計算が簡単ではないか？という推察ができます。(考え方は間違っていないと思います)
で、実際のH.264での整数精度4x4DCTで使われているγの値ですが、という値が使われます。どうもこの値が近似としても悪くなく、かつ変換の処理がやりやすいようで実際この周辺の計算においてこの値の意味というのが分かるようになっているようです。(次に来るのは量子化の処理ですが、H.264の場合、プロファイルが上位のものでないとき量子化行列は固定かつすべての値が同じ行列なのでこれを踏まえたテーブルを作って処理することが可能になっています)
次回があるなら8SamplesDCTかな・・・
H.264では基本的には16×16のブロックを分解し4x4DCTを行うことでブロックを処理する、というのが基本形なので8x8DCTは考えられていませんでした。が、高忠実度規格というものを考えるときは整数精度8x8DCTが使われています。もし次があるならこちらもやってみたいと思います。発想や式はほぼ同じなのですが展開した時の計算方法が(書くときに)面倒なのが問題点ですか。8x8DCTでAANアルゴリズムでの行列の展開ができれば整数精度8x8DCTは簡単にわかるのですが…。