FFTと積分画像を用いた高速テンプレートマッチング

二年ぶりの投稿となります．

今回はFFTと積分画像を用いた高速テンプレートマッチングについて解説します．
テンプレートマッチングとは，サーチ領域からテンプレート画像に「最も類似」した部分を見つけ出す手法です．

教科書によく載っているオーソドックスな手法ですが，計算量が多いため処理時間が長くなってしまいます．
この膨大な計算をフーリエ変換（FFT）と積分画像を用いて短くしようというのが今回の目的です．

実はすでに，高速化された同手法がOpenCVで実装されています．ですからOpenCVの該当するソースコードを見ればよいのですが，それはかなりの苦行です．精神現象学に比べればちょろいもんですが！
そこで次の論文を参考にしつつ話をすすめることにします．

Lewis著 Fast Template Matching
http://scribblethink.org/Work/nvisionInterface/vi95_lewis.pdf

サーチ領域のサイズをM×M，テンプレート画像のサイズをN×Nとし，座標(x,y)上の輝度値をそれぞれf(x,y)，t(x,y)とします．この時，座標(u,v)における類似度は次の式で求められます：

ただし，

とします．
この計算法はゼロ平均の正規化相互相関と呼ばれ，明るさの変動に強いことが特徴です．（と言われていますが，わたしはあまりその実感はありません．）

まず事前準備として，サーチ領域とテンプレート画像を，１辺の長さが「M以上の最小の2のべき乗」となるように拡張します．この時，拡張されたエリアを輝度値0で埋めます．

フーリエ変換

では類似度の式を分子と分母にわけて考えてみましょう．

まず分子は次のように変形できます：

第一項に注目すると，fとtに関する畳込みが行われています．ここでフーリエ変換が登場します．tが時間反転していることに注意して，第一項はフーリエ変換の畳込み定理より

となります．
したがって，座標(u,v)ごとに和をとらなければならなかった計算が，サーチ領域とテンプレート画像をフーリエ変換し，その積を逆フーリエ変換したデータを参照するだけですむことになります．

積分画像

次に，第二項に注目します．この和は座標(u,v)から(u+N-1,v+N-1)までの輝度値fを参照する必要があり処理時間が長くなってしまいますが，積分画像を使うことによって大幅に短縮できます．

この積分画像については，MetaArt様の記事がとてもわかりやすいのでぜひ御覧ください．

cvMatchTemplateの実装を解読してみた

http://iphone.moo.jp/app/?p=630

さて，同じように分母も変形すると

となります．ただし，

です．こちらはfの積分画像に加えて，fの2乗の積分画像も必要になります．さらにTはテンプレート画像のみに依存しますから定数扱いできます．

Σf(x,y)をs1(u,v)，Σf(x,y)2をs2(u,v)と表せば，最終的に類似度は次のように書き換えられます：

結果

サーチ領域を256x256，テンプレート画像を32x32としたところ，処理時間は18msでした．一方，計算式のとおりに求めた場合，その10倍程度の時間がかかりました．（Win7 32bit, Intel Core i7 3.80GHz）
難点を言えば，周波数領域を保持しなければならないので，大きなバッファメモリが必要だということですね．

備考

○浮動小数点の型を倍精度（double）から単精度（float）にしたところ，類似度が-1～+1を超えてしまうことがあるようです．おそらくフーリエ変換した際に精度が落ちてしまっているためと思われます．

○位相相関（Phase Correlation）
位相相関という計算法がありますが，こちらは今回の相互相関とよく似た具合になります．
http://en.wikipedia.org/wiki/Phase_correlation

○ガウシアンフィルタのような，線形ボックスフィルタも畳み込みの一種ですから，今回の手法で高速化できます．