今までに、
- 2つの信号の類似度を測る尺度の一つに相互相関関数というものがある
- でも信号が似ていなくても片方のデータが極端に大きかったりすると相互相関関数の値も大きくなっちゃって本当に似ている場所を検出できなかったりする
- でも相互相関関数は畳み込みの定理からFFTと組み合わせるとはやく計算できる
みたいなことを説明しました。
正規化相互相関係数は片方のデータが極端に大きかったりしても、それに引きずられたりしない相互相関関数よりもロバストな指標です。
2次元画像fからテンプレートtを探すテンプレートマッチングを考えます
fは、tはとします。fの各座標に対する正規化相互相関係数は以下で計算できます。
これを(特にを)まじめに計算するのはとても時間がかかります。
以下のように工夫することで、いくらかはましになります。
まず分子について考えます。
分子の和の中身を展開すると
となります。
ここで、第1項は以前やった相互相関関数そのものであるのでそれぞれをDFTして掛け合わせて逆DFTでいちころです。
第2項はは問題ないのですが、はの値が変わるたびに計算しなおさなきゃならないので少々厄介です。
とりあえず分子はこの辺にして分母に行きます。
分母に関しても、は一度計算してしまえば、各で同じ値が使えるのでそんなに問題ありません。
問題なのは、です。
もう元気がなくなってきたので適当に進めますが、これは
と変形できます。
ここまでの話をまとめると、
各でとを計算しなおさなきゃならないから大変だ!ということです。
これはあらかじめテーブルを作っておくことで計算を高速化することが出来ます。
めんどくさくなっちゃったのであとは以下のページのintegralについてみてくださいおねがいします。
http://opencv.jp/opencv-2svn/cpp/miscellaneous_image_transformations.html