あらかじめ用意した形状（パターン）と類似性の高い形状が探索対象画像の中にあるか、あるいはどこにあるかを検出することをパターンマッチングという[1]。ここで、あらかじめ用意した形状及び探索対象画像を画素単位で表現し、対応する画素間の関係を評価することによって、パターンマッチングを行う場合、特に、テンプレートマッチングと呼ぶ。また、このとき、あらかじめ用意した形状をテンプレートと呼ぶ。テンプレートマッチングは、位置決めや形状の抽出などに利用される基本的な技術である。
濃淡画像のテンプレートマッチングにおける類似性を表す評価尺度としては、Ｌ１ノルムや正規化相関(または相互相関)係数がある。評価尺度としてＬ１ノルムを用いた場合、残差逐次検定法（ＳＳＤＡ法）[2]という計算打切り手法により、計算時間の短縮化を図ることができるが、テンプレートと探索対象画像の明るさが異なる場合、肉眼では類似した画像であっても、類似性を低く判定することがある。
一方、評価尺度として正規化相関係数を用いた場合、テンプレートと探索対象画像との明るさの違いによる影響を受けないという特長がある反面、計算の打切りによる計算時間短縮手法がなかったため、処理時間が掛かるという問題があった[3]。
筆者らは、正規化相関係数の持つ特長を損なわないで、正規化相関係数を求める計算を効率的に打切り、テンプレートマッチングを高速化する手法を開発したので報告する。
あらかじめ用意した標準パターン（テンプレート）と類似性の高いパターンを探索対象画像から検出する操作をテンプレートマッチングという。
テンプレートをT(m,n)
(m=0,…,M-1; n=0,…,N-1)、探索対象画像をf(i,j)
(i=0,…,I-1; j=0,…,J-1)
(但し、M≦I且つN≦J)、探索対象画像における、テンプレートと同サイズとなる始点(u,v)の部分画像をf(u,v)(m,n)
(m=0,…,M-1; n=0,…,N-1)とする。このとき、テンプレートマッチングは、テンプレートT(m,n)と最も類似性の高い部分画像f(u,v)(m,n)を探索することである。f、
T、 f(u,v)を図1に示す。
T(m,n)とf(u,v)(m,n)との類似度を、対応する各画素の差の総和（Ｌ１ノルム）で表す。T(m,n)とf(u,v)(m,n)のＬ１ノルムL1(u,v)は式1で与えることができる。ここで、
L1(u,v)の値が小さいほど類似度が高いと考える。
Ｌ１ノルムを用いた場合、肉眼では同じパターンでも類似度が低くなることがある。例えば、
f(u,v)(m,n) がT(m,n)に比べて明るい画像である場合、式2のように表すことができる。
但し、b>0。
このとき、L1(u,v)=MNbとなり、明るさの差bが大きいほどL1(u,v)は大きくなるため、類似度が低くなる。
上述のように、Ｌ１ノルムを用いたテンプレートマッチングは、テンプレートと探索対象画像の明るさの違いにより、適切な評価をしないという問題があるが、下記に示す手法により、計算時間を短縮できるという特長がある。
T(m,n)とf(u,v)(m,n)のL1(u,v)を求める処理において、対応する画素対に対して差を求め、加算していく手順を考える。このとき、計算が進むにつれて値が増加していき、すべての画素対に対する計算を終えたときL1(u,v)が求まる(図2参照)。
そこで、あらかじめ適当なしきい値THを与えておき、差の累積値がしきい値THを超えた時点で処理を打切るようにすれば、Ｌ１ノルムがしきい値THより大きな値になる処理のみ打切ることができるため、処理を効率化することができる。この手法を残差逐次検定法(SSDA法)[2]と呼ぶ。
T(m,n)とf(u,v)(m,n)との正規化相関係数R(u,v)は式３で与えられる。
但し、
正規化相関係数R(u,v)は−1から1までの値を取る。正規化相関係数が１に近いほどテンプレートT(m,n)と部分画像f(u,v)(m,n)は類似性が高く、正規化相関係数が−１に近いほどテンプレートT(m,n)と部分画像f(u,v)(m,n)の反転画像は類似性が高い。テンプレートT(m,n)と部分画像f(u,v)(m,n)が同一の画像であるとき、R(u,v)=1となる。
また、すべてのm(m=0,…,M-1)、n(n=0,…,N-1)に関して、
f(u,v)(m,n) = a×T(m,n)
+ b (但し、a>0)
が成立するとき、R(u,v)=1となる。このように、部分画像f(u,v)(m,n)がテンプレートと比較して、全般的に明るい画像あるいは暗い画像である場合でも、正規化相関係数を用いることにより、類似性が高いと判定することができる。
Ｌ１ノルムと異なり、正規化相関係数は単調増加あるいは単調減少という性質をもたない。従って、逐次的に計算を行っても、図３に示すように増加や減少を繰り返しながら値が定まる。このため、Ｌ１ノルムのような残差逐次検定法を用いることができなかった。
恒等式
但し、
ここで、N、Mはあらかじめ与えられているとする。A、Bは、探索対象画像のすべての部分画像に対して一度求めればよく、計算の手間は、AがMN回の加算、BがMN回の乗算とMN回の加算である。
C(u,v)は移動平均であり、以下の式が成り立つ。
但し、
ここで、 探索対象画像をラスタスキャンしながらC(u,v)を計算することを考えると、C(u-1,v)及びc(u-1,v)はC(u,v)を求める以前に求めている。そこで、その結果を用いることにより、C(u,v)はc(u+M-1,v)を求める手間と2回の加減算で計算することができる。
また、 c(u+M-1,v)は次式の通り、既に求めたc(u+M,v-1)などを用いることにより、2回の加減算により計算することができる。
c(u+M,v)= c(u+M,v-1)−f(u+M,v-1)＋f(u+M,v+N-1)
従って、すべてのu,vにおけるC(u,v)を求める手間は4IJ回の加減算である。
D(u,v)は、各画素を二乗する以外はC(u,v)と同様に求めることができる。従って、すべてのu,vにおけるD(u,v)を求める手間は、IJ回の乗算と4IJ回の加減算である。
以上をまとめると、A、B、C(u,v)及びD(u,v)を、すべてのu,vに対して求める手間は、8IJ+2MN回の加減算とIJ+
MN回の乗算である。 すべてのu,vに対するK1(u,v)及びK2(u,v)は、A、B、C(u,v)及びD(u,v)を用いれば、3(I-M+1)(J-N+1)回の加減算、4(I-M+1)(J-N+1)回の乗算、
(I-M+1)(J-N+1)回の除算及び(I-M+1)(J-N+1)回の平方根演算で求めることができる。
しかし、X(u,v)を計算する手間は、MN(I-M+1)(J-N+1)回の乗算及び2MN(I-M+1)(J-N+1)回の加減算であり、
式4において支配的な演算となっている。
そこで、K1(u,v)及びK2(u,v)をあらかじめ求めた後、X(u,v)をm、nに対して順次求めることを考える。
m=s、n=t (s=0,…,M-1、t=0,…,N-1)まで演算した正規化相関係数途中結果をRu,v(s+tM)と表す。すなわち、
Ru,v(s+tM)は式５のように表すことができる。
ここで、 Ru,v(0)
= K1(u,v)、
Ru,v(M×N)
= R(u,v)である。
K2(u,v)≧0であるので、
Ru,v(w)は、図３に示すように、wに対して単調減少関数となる。
従って、しきい値Rmaxに対して、Rmax以上の正規化相関係数をもつ(u,v)の組を探索する場合、あるw*に対して、
Ru,v(w*) < Rmaxが成立するならば、必ずR(u,v)
< Rmaxが成り立つ。そこで、最初にRu,v(w*)
< Rmax となるw*で正規化相関係数を求める処理を打切ることにより、無駄な処理のみを削減することができる。
正規化相関係数が最大となる場所を求めるテンプレートマッチングアルゴリズムを図４に示す。
本手法を用いたテンプレートマッチング性能評価実験を行った。対象画像としては、320×256画素の画像(画像A)と800×592画素の画像(画像B)を用意した。テンプレートとしては、各対象画像から切出した部分画像を用いた。また、初期目標値Rmaxを0.7とした。評価結果を表１に示す。
表１において、演算量比率は、全処理に対して本手法によって打切られなかった処理の割合を表す。打切り発生頻度は、打切りが発生した部分画像の割合を示す。
表１より、本手法では、打切りを行わない場合と比べて演算量を2/3〜1/5に低減したことが判る。
テンプレートマッチングにおける正規化相関演算のうち、無駄処理のみを打切る高速化手法を開発した。評価実験により、本手法では、打切りを行わない場合と比べて、2/3から1/5の演算量でマッチング点を求めることができた。
今後の課題としては、演算量を削減するためのテンプレート切出し法などが挙げられる。
…(式1)
…(式3)
、
、
、
。
に対してx=
f(u,v)(m,n)、y=T(m,n)とおいて、式３に代入すれば、R(u,v)は、式４のように表すことができる。
…(式4)
、
、
。
…(式5)