第 3 章 Scanning Electron Microscope の解析とビームドリフト低減手法
3.3 テンプレートマッチング
54
55
類似度を求める手法の一般的な例[17][18]を以下に示す。
正規化相互相関（Normalized Cross-Correlation：NCC）を用いて類似度を計算する手法。
この計算式は
𝑅𝑁𝐶𝐶(𝑑𝑥, 𝑑𝑦) = ∑ ∑{𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)𝑓(𝑖, 𝑗)}
√∑ ∑(𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗))2√∑ ∑(𝑓(𝑖, 𝑗))2 ⋯ (3.1) と表される。これはcosを用いた内積の定義
cos(𝜃) = 𝑔⃗ ∙ 𝑓⃗
|𝑔⃗||𝑓⃗| ⋯ (3.2) と同様な形となっており、図3.7（a）で示すようにRNCCが1に近づくほどテンプレート画 像と似ている画像となる。
相互相関係数（Zero-means Normalized Cross-Correlation：ZNCC）を用いる手法はNCCと 非常に似ており、領域内の画像輝度値の平均値をそれぞれから減算する部分が相違点とな っている。NCCでは画像の明るさが変動するとRNCCの値が1にならない。そこでテンプレ ート画像と局所画像の輝度値の平均値をそれぞれから減算することで、明るさの変動を吸 収することで安定的に計算ができ、計算結果も1になる。計算式は以下のように示される。
𝑅𝑍𝑁𝐶𝐶(𝑑𝑥, 𝑑𝑦) = ∑ ∑{(𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) − 𝜇𝑔)(𝑓(𝑖, 𝑗) − 𝜇𝑓)}
√∑ ∑(𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) − 𝜇𝑔)2√∑ ∑(𝑓(𝑖, 𝑗) − 𝜇𝑓)2
⋯ (3.3)
ここでg、fはそれぞれの領域内の輝度値の平均である。
ここで、（3.3）式は輝度値の平均を計算してから、さらに輝度値から平均値を減算するた め2 ループ必要であり、効率の悪い計算式となっている。そこで（3.3）式を変形する。輝 度値の平均は
𝜇𝑔=∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)
𝑀 × 𝑁 ⋯ (3.4)
𝜇𝑓=∑ ∑ 𝑓(𝑖, 𝑗)
𝑀 × 𝑁 ⋯ (3.5) で求まることから、（3.3）式に代入して整理すると
𝑅𝑍𝑁𝐶𝐶(𝑑𝑥, 𝑑𝑦) =𝑀𝑁 ∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)𝑓(𝑖, 𝑗) − ∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) × ∑ ∑ 𝑓(𝑖, 𝑗)
√𝑀𝑁 ∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)2− (∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗))2
× 1
√𝑀𝑁 ∑ ∑ 𝑓(𝑖, 𝑗)2− (∑ ∑ 𝑓(𝑖, 𝑗))2 ⋯ (3.6) となる。これにより1ループで類似度を求めることができる。
なお、一般的にはNCCよりも明るさ変動に強いZNCCがよく使われる。
差の2乗和（Sum of Squared Difference：SSD）では画像の同じ位置の輝度値の差の2乗の 合計が用いられる。上記の 2つの手法では類似度は計算結果が 1に近いほど似ている画像 であったが、SSDは0に近いほど似ている画像となる。計算式は
56
𝑅𝑆𝑆𝐷(𝑑𝑥, 𝑑𝑦)＝∑ ∑ (𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) − 𝑓(𝑖, 𝑗))2
𝑚−1
𝑖=0 𝑛−1
𝑗=0
⋯ (3.7)
と表され、図3.7（b）にRSSDの図を示す。
差の絶対値和（Sum of Absolute Difference：SAD）は画像の同じ位置における輝度値の差 の絶対値の合計で計算をする。その計算式を以下に示す。また、その図を図3.7（c）に示す。
𝑅𝑆𝐴𝐷(𝑑𝑥, 𝑑𝑦) = ∑ ∑ |𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) − 𝑓(𝑖, 𝑗)|
𝑚−1
𝑖=0 𝑛−1
𝑗=0
⋯ (3.8)
RSADも0に近いほど似ている画像となる。
SSDとSADはNCCとZNCCに比べ計算量が少なく、特にSADは乗算を含まないため計 算負荷が最も小さい。ただし、どちらの手法も明るさ変動には弱い傾向がある。
（a） （b） （c）
図3.7 一般的なテンプレートマッチング手法の図
57
3.3.2 実験装置のテンプレートマッチングプログラム
実験装置で用いられているテンプレートマッチングの手法を解析した結果を本項で記す。
プログラムで書かれていた手法を前節のように計算式で示すと以下のようになる。
𝑅 = ∑ ∑ (𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗) − 𝜇𝑔)(𝑓(𝑖, 𝑗) − 𝜇𝑓)
𝑚−1
𝑖=0 𝑛−1
𝑗=0
⋯ (3.9)
ここでn = m = 30である。また、図3.6でM、Nに該当する値はどちらも100となっていた。
Rが最大となる位置がテンプレート画像と似ている位置となる。（3.9）式は各画像の輝度値 の平均を減算しており、ZNCCと同様に明るさ変動に強くなっている。また除算がないため SSDやSADと似た形式であり計算量は少なめとなっている。ただし、（3.3）式と同様に式 中で必要なg、fは事前にもとめておく必要があり、計算量が少なめな手法をとっているに もかかわらず計算にかかる時間が多くかかってしまう。そこで、（3.9）式を変形することで 計算の高速化を考える。（3.9）式に（3.4）、（3.5）式を代入すると
𝑅 = ∑ ∑ {𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)𝑓(𝑖, 𝑗) − 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)∑ ∑ 𝑓(𝑖, 𝑗) 𝑀𝑁
𝑚−1
𝑖=0 𝑛−1
𝑗=0
−𝑓(𝑖, 𝑗)∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)
𝑀𝑁 +∑ ∑ 𝑔(𝑑𝑥 + 𝑖, 𝑑𝑦 + 𝑗)
𝑀𝑁
∑ ∑ 𝑓(𝑖, 𝑗)
𝑀𝑁 } ⋯ (3.10) となる。（3.10）式に変形すれば事前に計算する必要がなくなり、2 ループから 1 ループに なるため計算の高速化が期待できる。
58