DMNA 因数分解 - タンタン的思考

訂正

まずは前回の訂正．DMNAは6つぐらい特徴があった模様．全然2つじゃなかった．逆に動き検出や画質制御のヒントが増えたと思う．

試行錯誤

DCTを高速演算するときに，
$\left(\begin{array}{cc}1 & \tan(\pi/16) \\\tan(\pi/16) & 1 \\ \end{array}\right)$
という行列が出てくる．詳しくはAP922を参照のこと．

通常は，
$\left(\begin{array}{cc}1 & \tan(\pi/16) \\ \tan(\pi/16) & 1 \\ \end{array}\right)\propto\frac{1}{2^{16}}\left(\begin{array}{cc}2^{16} & T_1 \\T_1 & 2^{16} \\ \end{array}\right)$
と近似して計算する．ただし，
$T_1=\text{Integer}(\tan(\pi/16)\times2^{16}+\frac{1}{2})$
とする．

ところがこの行列を
$\left(\begin{array}{cc}1 & \tan(\pi/16) \\\tan(\pi/16) & 1 \\ \end{array}\right)\propto\left(\begin{array}{cc}181 & 36 \\36 & 181 \\ \end{array}\right)=\left(\begin{array}{cc}1 & 30 \\30 & 1 \\ \end{array}\right)\left(\begin{array}{cc}1 & 6 \\6 & 1 \\ \end{array}\right)$
のように近似できる．

このとき演算コストはどの程度になるのか．通常は4shift, 2add, 2mulとなる．一方因数分解して乗算をシフト加算演算に還元すると，8shift, 8addとなる．*12回のシフトと3回の加算が乗算1回より速いのかどうか，ということになる．シフト加算演算のほうが多分早いと思う．

近似精度について考えてみる．通常は $10^{-6}$ のオーダーで，分解すると $10^{-5}$ のオーダーになる．ちなみに，定数T1を粗く近似してシフト加算演算にすると $10^{-4}$ になってしまう．

最終的な近似精度がどうなるかや，定数倍されたことによって後々の計算で係数が破綻するかも，ということは未検討です．とはいえ，こんな要領で分解してやればもしかしたら高速になるかもしれません．さらに，乗算器を除去できるのはチップ開発時には大きなアドバンテージになることでしょう．

ここまで書いて，四捨五入を考慮するのを忘れてた．10倍も精度が悪いので，1ビットぐらい変わっても誤差範囲になってしまうかな．なお，同じぐらいの近似精度にするには，
$\left(\begin{array}{cc}1 & 5 \\ 5 & 1 \\ \end{array}\right)\left(\begin{array}{cc}1 & -880 \\ -880 & 1 \\ \end{array}\right)$
という分解もある．ちょっと計算コストが増えるのと，多分適当な正規化を入れないと破綻しそう（そしてさらに計算コストが増える）．

量子化まで含めてトータルな設計をしないと完全高速化は難しそうだな．そしてその道のりは長そうだ．これであってますかね．181という数値をどこかで見たことあるなぁと思ったら，特許にも出てました．アプローチは間違ってないって事でしょうかね．もうちょっと数式を整理できたらオートマチックにはじき出せそうなんですが．

*1:30=32-2=2^5-2^1, 6=2^2+2だから，シフト2回と加算1回でそれぞれ乗算に相当する．