2次元DCTの高速化(2) - ほっしーの技術ネタ備忘録

夜に…って書いてないわけですが。(苦笑)

もう一段階高速化…というかテーブル化のコツ。

$\Large C(n,m)=\left\{\begin{array}{ll}sqrt{\frac{1}{2}} & n=0 \\cos{\frac{(2m+1)n\pi}{2N}} & n\neq0\end{array}\right.$

こういう2次元なテーブルを用意すると、

$\Large S(u,v)=\frac{2}{N}\sum^{N-1}_{x=0}\sum^{N-1}_{y=0}s(x,y)C(u,x)C(v,y)$

こういう式になって...

$\Large F(x,v)=\sqrt{\frac{2}{N}}\sum^{N-1}_{y=0}s(x,y)C(v,y)$
$\Large S(u,v)=\sqrt{\frac{2}{N}}\sum^{N-1}_{x=0}F(x,v)C(u,x)$

こうなるわけです。

これで、乗算の回数を数えると...

前者は $2N^2$ 回。
後者は $N$ が2回で、 $2N$ 回。

2次元DCTを1次元に分解するだけで乗算の数が $\Large \frac{1}{N}$ になりました。