さて、今回はいよいよZNCC計算についてお話しましょう！

ZNCCは画像のテンプレートマッチングでよく利用されますが、画像以外のデータにも対応している方法です。なぜそう言われるか、以下の式を見てください。

一般的に相関係数rの定義は

\[r = {xとyの共分散 \over (xの標準偏差)(yの標準偏差)}\]

で表されます。

パターンマッチングの中で比較的よく利用されているZNCCの類似度計算は相互相関係数を示し、入力画像の輝度分布=x、テンプレートの輝度分布=y、走査位置を(dx,dy)、iとjは画像のサイズとしたとき、

\[ R_{ZNCC}(d_x,d_y) = \frac{\sum\sum{\lbrace(x(d_x+i,d_y+j)-\bar{x})(y(i,j)-\bar{y})}\rbrace}{\sqrt{\sum\sum(x(d_x+i,d_y+j)-\bar{x})^2}\sqrt{\sum\sum(y(i,j)-\bar{y})^2}}\]

で表されます。(見直したけど式間違ってたらすいません💦)

大学では実験に対する結果の有効性を示す方法として、モトハシの時代は確か”実験計画法”や”計量生物学”という名目で必修科目となっていました(当時、単位取るのに苦労しましたが･･･)。計算の中身はこれと全く同じ概念です。

つまり画像の類似度は入力画像をx、テンプレートをyとしたとき、構成自体は相関係数rを求めるのと何ら変わりありません。実際の手順では、入力画像x内の左上(0，0)を走査開始位置とする窓とテンプレートyの相関係数をとっていることになります。(dx,dy)は(0，0)を開始地点とし、最後はxの縦横のサイズからyの縦横サイズ( i , j )分差し引いた地点で終わります。

通常、プログラム上では平均の計算を行ってから相関係数を求めるのが流れとしては正しいですが、もう一つの計算パターンとして分散の公式を使用することで計算コストを小さくできるとの情報もありました。

そこで今回モトハシはPythonで２パターンの計算方法を試して結果を比較してみることにしました。すると面白い結果が・・・！

計算方法

1. 入力画像xの各走査位置毎に平均計算を行ってから、\(R_{ZNCC}＝r＝\frac{\sum\lbrace(xの偏差)(yの偏差)\rbrace}{\sqrt{(xの偏差平方和)}\sqrt{(yの偏差平方和)}}\)で解を導く方法
2. \(分散(V) = (二乗和)-(平均の二乗)\)の公式を利用し、平均処理を省きながら直接\(R_{ZNCC}\)の計算をする方法

※1．でrの式が変化している事を疑問に感じた方、共分散と標準偏差の公式を確認してください。分母分子ともにデータ個数で割る工程が存在していますが、実際は約分できるのでこのような式へと変換できます。

例として、丁度図で示しているテンプレートyとピンクの点線で囲まれた走査位置(0，0)地点のZNCCを、上記2つの計算方法を使って導いてみます。

[下準備]．

#下準備
import cv2
import numpy as np

photo='../Choco.jpg'
img = cv2.imread(photo)
h = img.shape[0]
w = img.shape[1]

img = cv2.resize(img,(int(w/4), int(h/4)))
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

#元の入力画像(img)から任意の位置(1/9size)をテンプレート(temp)に指定
temp=gray[195:280,55:168] 

#走査窓(u)
h,w=temp.shape
u=gray[0:0+h,0:0+w]

#計算のためfloat型へ変換
u = np.array(u, dtype="float")
temp = np.array(temp, dtype="float")

[方法1]．

#[方法1]

#センタリング
W=u-np.mean(u)
T=temp-np.mean(temp)

#ZNCC
mol=np.sum(W*T)
den=np.sqrt(np.sum(W**2))*np.sqrt(np.sum(T**2))

ZNCC＝mol/den

>>> ZNCC
0.0510839426117405
>>> 

[方法2].

#[方法2]

#入力画像とテンプレートデータから分散Vを求める
V=np.mean(u**2)-(np.mean(u))**2
V2=np.mean(temp**2)-(np.mean(temp))**2

#ZNCC
#分散V＝標準偏差Sの2乗より
den=np.sqrt(V)*np.sqrt(V2)
#共分散
mol=np.mean((u-np.mean(u))*(temp-np.mean(temp)))

ZNCC=mol/den

>>> ZNCC
0.051083942611739444
>>> 

結果、2つの計算を行いましたがどちらも答えは同じでした。ですが、この計算をベースにプログラム上で走査位置を変えながら結果の集計をすると、[方法2]の相関係数がすべて0になるという異常事態が起こりました。

これについては次回話します。

参考文献

• 中村俊太. 斉藤文彦. ”テンプレート内有効特徴画素選択による高速画像マッチング”. IIEEJ, 2012, 41巻, p.392-397
• 大野広揮. 橋本学. "マルチクラス識別機能を有した高速テンプレートマッチング". Journal of the Japan Society for Precision Engineering Vol82, No.12. 2016