Where is Worry?

画像のデータ解析で最も一番良く行われるのが,テンプレートマッチングです.
テンプレートマッチングとは,大きな画像内における特定の場所をそのdata間の差分から求めるという手法です.

テンプレートマッチングには大きく2パターンあります.

  1. 絶対値差分二乗和
  2. 正規化相互相関

まずは画像を読み込んでテンプレートマッチングの準備をします

  • template : 探す部位にあたる画像
  • target : 検索の対象画像

計算容量を抑えることもあり,今回はGrayscaleに一度変換してテンプレートマッチングを行います
そのため,Grayscale情報で読み込みます.

In [ ]:
#ここは数式を出力するためのおまじないなので,実行しない
from math import *
from sympy import *


init_printing()
In [26]:
import sys
import numpy as np
from skimage import io, color, data, img_as_ubyte
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import cv2

%matplotlib inline

templateImg ='Template.png'
targetImg =  'Baboon.jpg'

templateColor = cv2.imread(templateImg)
templateColor = cv2.cvtColor(templateColor, cv2.COLOR_BGR2RGB)
targetColor = cv2.imread(targetImg)
targetColor = cv2.cvtColor(targetColor, cv2.COLOR_BGR2RGB)
template = cv2.imread(templateImg, 0)
#template = img_as_ubyte(template)
target = cv2.imread(targetImg, 0)
#target = img_as_ubyte(target)


[th, tw] =template.shape
[tarh, tarw] =target.shape

scoreMap = np.zeros( (tarh-th, tarw-tw)) #マッチングの評価を入れておくためのリソース

1. 絶対値差分二乗和

最もシンプルなテンプレートマッチングです.
まったく同じところを探すので,当然,情報が完全に一致する所を見るけるとOKですよね

だったら,距離誤差で求めらたいいよね?という原理です.

だから,式も極めてシンプル \begin{equation} ScoreMap = argmin(Target-template) \end{equation}

ただし,この手法は問題もあります.
情報が完全に一致していること,が前提です.
少しでもずれ,照明のむらなどがあれば精度が下がるなどの問題があります.

以下がサンプルCodeです.
for 文でタテ・ヨコにひとつずつ画素を移動させながら,その差分を求めていることがCodeからも確認できます

  • for文の1行目: 注目ピクセルを中心に,周囲の画素(サイズはテンプレートと一緒)をベクトルとして捉え引き算
  • for文の2行目: 1行目で得られたベクトルについて,各ベクトル要素間の二乗差の総和をとる(これがスコア)
In [2]:
for y in range(scoreMap.shape[0]):
    for x in range(scoreMap.shape[1]):
        diff = target[y:y+th, x:x+tw]-template
        scoreMap[y,x] = np.square(diff).sum()

先に求めたスコアで最も最小の場所を以下から求めます.

  • np.argmin(Data):Dataの中から最小値を見つける
  • np.unravel_index(arg1, arg2): arg2のマトリックス(ベクトル)から,arg1に当てはまる要素の場所を返す.
In [3]:
y, x = np.unravel_index(np.argmin(scoreMap), scoreMap.shape)
scoreMap
plt.imshow(targetColor)
Out[3]:
<matplotlib.image.AxesImage at 0x966e4e0>

結果を出力してみます.
今回,テンプレートとターゲット画像上に見つけたテンプレートの場所をしめしました.

In [4]:
fig,(ax1, ax2, ax3) = plt.subplots(3, figsize=(10,10))
ax1.imshow(templateColor, cmap=cm.Greys_r)
ax1.set_axis_off()
ax1.set_title("Template Image")

ax2.imshow(targetColor, cmap=cm.Greys_r)
ax2.set_axis_off()
ax2.set_title("Target+Template Image")
ax2.add_patch(plt.Rectangle((x, y), tw, th, edgecolor="R", facecolor='none', linewidth=1.5))

ax3.imshow(scoreMap,  cmap=cm.Greys_r)
#ax3.set_axis_off()
ax3.set_title("ScoreMap")
ax3.add_patch(plt.Rectangle((x-tw/2, y-th/2), tw, th, edgecolor="R", facecolor='none', linewidth=1.5))


plt.show()

OpenCVを使うと,なんと,これがこんな感じです.

In [5]:
res = cv2.matchTemplate(target,template,cv2.TM_SQDIFF)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)

top_left = min_loc
bottom_right = (top_left[0] + tw, top_left[1] + th)

cv2.rectangle(target,top_left, bottom_right, 255, 2)
Out[5]:
array([[146,  61,  39, ..., 118, 150, 170],
       [115,  97,  34, ..., 134, 144, 137],
       [ 70, 127,  51, ...,  88,  93,  76],
       ..., 
       [147, 147, 144, ...,  87,  84,  84],
       [149, 142, 131, ...,  80,  77,  75],
       [ 13,   9,   6, ...,   8,   4,   1]], dtype=uint8)

これを出力するのは,以下の通り,OpenCVはこうやって,内部でライブラリを整えているので便利なのです.

In [6]:
plt.subplot(121),plt.imshow(res,cmap = 'gray')
plt.title('Matching Result'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(target,cmap = 'gray')
plt.title('Detected Point'), plt.xticks([]), plt.yticks([])
Out[6]:
(<matplotlib.text.Text at 0xa0e1dd8>,
 ([], <a list of 0 Text xticklabel objects>),
 ([], <a list of 0 Text yticklabel objects>))

1. 正規化相互相関

絶対値差分和では,画像がずれたり,照明のむらがあれば精度に影響が出ました
ということで,単純な差分だけではうまくいかないということが言えるわけです.

画像ってベクトルだから,ベクトルの内積を用いて考えたらいいよね?これが正規化相関の根本的なアイデアです

ということで,式が少しややこしくなります.

ベクトルの内積を考えるわけなので,ベクトルの距離と$\cos(\bf x)$から類似度を求めることになります.
入力画像,テンプレート画像をそれぞれ,$I(x, y), T(i,j)$とすると下式が導かれる. $$ ScoreMap(x, y) = \frac{\sum_{y=0}^{N-1}\sum_{x=0}^{M-1}I(x,y)T(x, y)}{\sqrt{\sum_{y=0}^{N-1}\sum_{x=0}^{M-1}I(x,y)^2\times \sum_{y=0}^{N-1}\sum_{x=0}^{M-1}T(x,y)^2}} $$ この式では,分子が内積になっている,そして,分母が各ベクトル間の距離で演算されています.
ということで,$\cos(\bf x)$と同じ意味を持ってます.これが類似度というものです.
類似度は$\cos(\bf x)$の考慮なので,その値は.$-1 \leq ScoreMap(x, y) \leq 1$をとります

しかし,いくら類似度を考慮していると言えど,やはり差分を検討しているのがこの手法.
画素間の照明むらにも影響をできるだけ抑えるため,画像の平均的な輝度を差し引き,類似度を以下の様に求めます.
$$ ScoreMap(x, y) = \frac{\sum_{y=0}^{N-1}\sum_{x=0}^{M-1}(I(x,y)-\overline{I})(T(x, y)-\overline{T})}{\sqrt{\sum_{y=0}^{N-1}\sum_{x=0}^{M-1}(I(x,y)-)-\overline{I})^2\times \sum_{y=0}^{N-1}\sum_{x=0}^{M-1}(T(x,y)-)-\overline{T})^2}} $$

OpenCVの便利さを覚えてしまったので,OpenCVで使い倒します.
正規化相互相関のライブラリはcv2.TM_CCOEFF,と,照明につよいcv2.TM_CCOEFF_NORMEDです.

In [25]:
%reset
Once deleted, variables cannot be recovered. Proceed (y/[n])? y
In [10]:
res = cv2.matchTemplate(target, template, cv2.TM_CCOEFF)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)
print(min_val, max_val, min_loc, max_loc)

top_left = max_loc
bottom_right = (top_left[0] + th, top_left[1] + tw)

cv2.rectangle(target,top_left, bottom_right, 255, 2)
-3426174.0 19324136.0 (36, 140) (123, 22)
Out[10]:
array([[146,  61,  39, ..., 118, 150, 170],
       [115,  97,  34, ..., 134, 144, 137],
       [ 70, 127,  51, ...,  88,  93,  76],
       ..., 
       [147, 147, 144, ...,  87,  84,  84],
       [149, 142, 131, ...,  80,  77,  75],
       [ 13,   9,   6, ...,   8,   4,   1]], dtype=uint8)
In [13]:
plt.subplot(121),plt.imshow(res,cmap = 'gray')
plt.title('Matching Result'), plt.xticks([]), plt.yticks([])
#plt.subplot(122),plt.imshow(target,cmap = 'gray')
plt.subplot(122),plt.imshow(target,cmap = 'gray')
plt.title('Detected Point'), plt.xticks([]), plt.yticks([])
Out[13]:
(<matplotlib.text.Text at 0xa0a5198>,
 ([], <a list of 0 Text xticklabel objects>),
 ([], <a list of 0 Text yticklabel objects>))
In [21]:
res = cv2.matchTemplate(target,template,cv2.TM_CCOEFF_NORMED)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)

top_left = max_loc
bottom_right = (top_left[0] + tw, top_left[1] + th)

cv2.rectangle(target,top_left, bottom_right, 255, 2)
Out[21]:
array([[146,  61,  39, ..., 118, 150, 170],
       [115,  97,  34, ..., 134, 144, 137],
       [ 70, 127,  51, ...,  88,  93,  76],
       ..., 
       [147, 147, 144, ...,  87,  84,  84],
       [149, 142, 131, ...,  80,  77,  75],
       [ 13,   9,   6, ...,   8,   4,   1]], dtype=uint8)
In [22]:
plt.subplot(121),plt.imshow(res,cmap = 'gray')
plt.title('Matching Result'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(target, cmap = 'gray')
plt.title('Detected Point'), plt.xticks([]), plt.yticks([])
Out[22]:
(<matplotlib.text.Text at 0x92b31d0>,
 ([], <a list of 0 Text xticklabel objects>),
 ([], <a list of 0 Text yticklabel objects>))

ところで,正規化相関のひとつの手法,TM_CCORRを使ってみました.
結果としては,違う所を認識しました.

この原因については,今のところ調査中です.
ただし,同じような相関性をとっているのに,このように違う値を出すのは非常に興味があります.

In [27]:
res = cv2.matchTemplate(target,template,cv2.TM_CCORR)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)

top_left = max_loc
bottom_right = (top_left[0] + tw, top_left[1] + th)

cv2.rectangle(target,top_left, bottom_right, 255, 2)
Out[27]:
array([[146,  61,  39, ..., 118, 150, 170],
       [115,  97,  34, ..., 134, 144, 137],
       [ 70, 127,  51, ...,  88,  93,  76],
       ..., 
       [147, 147, 144, ...,  87,  84,  84],
       [149, 142, 131, ...,  80,  77,  75],
       [ 13,   9,   6, ...,   8,   4,   1]], dtype=uint8)
In [28]:
plt.subplot(121),plt.imshow(res,cmap = 'gray')
plt.title('Matching Result'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(target,cmap = 'gray')
plt.title('Detected Point'), plt.xticks([]), plt.yticks([])
Out[28]:
(<matplotlib.text.Text at 0x96e2e48>,
 ([], <a list of 0 Text xticklabel objects>),
 ([], <a list of 0 Text yticklabel objects>))