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

jpeg などで使っている2次元DCTの式はこんな感じ。
マクロブロックが 8x8 なら N=2 です。

$\Large S(u,v)=\frac{2}{N}C_uC_v\sum^{N-1}_{x=0}\sum^{N-1}_{y=0}s(x,y)cos{\frac{(2x+1)u\pi}{2N}}cos{\frac{(2y+1)v\pi}{2N}}$
$\Large C_n=\left\{\begin{array}{ll}sqrt{\frac{1}{2}} & n=0 \\1 & n\neq0\end{array}\right.$

ただの掛け算と和の計算なので、分配法則によって、C と cos の位置を並び替えることができます。
で、下の式と等価になります。

$\Large S(u,v)=\sqrt{\frac{2}{N}}\sum^{N-1}_{x=0}C_u\{\sqrt{\frac{2}{N}}\sum^{N-1}_{y=0}C_vs(x,y)cos{\frac{(2y+1)v\pi}{2N}}\}cos{\frac{(2x+1)u\pi}{2N}}$

この式を括弧の中だけ別関数にすると、

$\Large F(x,v)=\sqrt{\frac{2}{N}}\sum^{N-1}_{y=0}C_vs(x,y)cos{\frac{(2y+1)v\pi}{2N}}$
$\Large S(u,v)=\sqrt{\frac{2}{N}}\sum^{N-1}_{x=0}C_uF(x,v)cos{\frac{(2x+1)u\pi}{2N}}$

この2つの式に分解できます。
そしてこの式は1次元DCTの式そのままなんですね！

逆に考えると、2次元DCTは単に、1次元DCTを縦方向・横方向に2重に行ってるわけです。
合成関数な感じですね、はい。

現在書きかけ...続きは夜に。