離散フーリエ変換(6) - 正規化相互相関係数

今までに、
- ２つの信号の類似度を測る尺度の一つに相互相関関数というものがある
- でも信号が似ていなくても片方のデータが極端に大きかったりすると相互相関関数の値も大きくなっちゃって本当に似ている場所を検出できなかったりする
- でも相互相関関数は畳み込みの定理からFFTと組み合わせるとはやく計算できる

みたいなことを説明しました。

正規化相互相関係数は片方のデータが極端に大きかったりしても、それに引きずられたりしない相互相関関数よりもロバストな指標です。

2次元画像fからテンプレートtを探すテンプレートマッチングを考えます

fは $M_x \times M_y$ 、tは $N_x \times N_y$ とします。fの各座標 $(u, v)$ に対する正規化相互相関係数は以下で計算できます。

$c_{u, v} = \frac{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} \left( f_{x,y} - \overline{f}_{u,v} \right) \left( t_{x - u, y - v} - \overline{t}\right) }{\sqrt{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} \left( f_{x,y} - \overline{f}_{u,v} \right)^2} \sqrt{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v}\left( t_{x - u, y - v} - \overline{t}\right)^2}}$

$\overline{f}_{u, v} = \frac{1}{N_x N_y}\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v}f_{x,y}$

$\overline{t} = \frac{1}{N_x N_y}\sum^{N_x - 1}_{x = 0} \sum^{N_y - 1}_{y = 0} t_{x, y}$

これを(特に $\overline{f}_{u, v}$ を)まじめに計算するのはとても時間がかかります。

以下のように工夫することで、いくらかはましになります。

まず分子について考えます。

分子の和の中身を展開すると
$\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} \left( f_{x, y}t_{x - u, y - v} \right) - \overline{t} \sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y} - \overline{f}_{u, v} \sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v}t_{x - u, y - v} + N_x N_y \overline{t} \overline{f}_{u, v}$
$= \sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} \left( f_{x, y}t_{x - u, y - v} \right)- \overline{t} \sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y}$

となります。

ここで、第1項は以前やった相互相関関数そのものであるのでそれぞれをDFTして掛け合わせて逆DFTでいちころです。
第2項は $\overline{t}$ は問題ないのですが、 $\sum^{u + N_x -1}_{x=u}\sum^{v + N_y - 1}_{y = v} f_{x, y}$ は $(u, v)$ の値が変わるたびに計算しなおさなきゃならないので少々厄介です。

とりあえず分子はこの辺にして分母に行きます。

分母に関しても、 $\sqrt{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v}\left( t_{x - u, y - v} - \overline{t}\right)^2}$ は一度計算してしまえば、各 $(u, v)$ で同じ値が使えるのでそんなに問題ありません。

問題なのは、 $\sqrt{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} \left( f_{x,y} - \overline{f}_{u,v} \right)^2}$ です。

もう元気がなくなってきたので適当に進めますが、これは
$\sqrt{\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y}^2 - \frac{1}{N_x N_y}\left( \sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y} \right)^2$
と変形できます。

ここまでの話をまとめると、
各 $(u, v)$ で $\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y}$ と $\sum^{u + N_x -1}_{x=u} \sum^{v + N_y - 1}_{y = v} f_{x, y}^2$ を計算しなおさなきゃならないから大変だ！ということです。

これはあらかじめテーブルを作っておくことで計算を高速化することが出来ます。

めんどくさくなっちゃったのであとは以下のページのintegralについてみてくださいおねがいします。
http://opencv.jp/opencv-2svn/cpp/miscellaneous_image_transformations.html