たくさん寝太郎の寝床

大阪在住大学生オタクのブログ

Template Matchingの話

こんにちは、たくさん寝太郎です。

昨日はゼミの論文紹介でした。
準備が大変でした(KONAMI感)


紹介した論文にTemplate Matchingの話が出てきたので折角ですしブログでも紹介しようと思います。

Template Matching(T-M)

テンプレートマッチングとは、画像を与えた時にその画像より小さいサイズのテンプレート画像を画像内から見つける手法です。

例えばたくさん寝太郎のヘッダーからこのクラゲを見つけたいとします。
f:id:kaworu_mk6:20190529192328j:plain

このテンプレートを画像内でスライドし類似度を計算する事で、どの位置がこのテンプレート画像に最も近いかを求めることができます。

類似度指標

  • SSD(Sum of Squared Difference): 画素値の差分の二乗和です。

 入力画像の画素値をI(x,y), テンプレート画像の画素値をT(x,y)、走査位置を(dx,dy)とした時SSD(dx,dy)は以下のようになります。

 SSD(d_x,d_y)=\sum_{x=0}^{w-1}\sum_{y=0}^{h-1}(I(d_x+x,d_y+y)-T(x,y))^2

ここでw,hはテンプレート画像の幅(wide)、高さ(high)です。

  • SAD(Sum of Absolute Difference): 画素値の差分の絶対値の和です。

 SAD(dx,dy)は以下のようになります。

 SSD(d_x,d_y)=\sum_{x=0}^{w-1}\sum_{y=0}^{h-1}|I(d_x+x,d_y+y)-T(x,y)|

SSDに比べて計算量が少ないです。また、外れ値の影響を受けにくいというデメリットがあります。


SSD,SADは計算量は多くないが照明の影響を受けやすいというデメリットがあります。

照明の影響を考慮した指標としてNCC(Normalized Cross Correlation)やZNCC(Zero-NCC)などがあるのですが、式が長くなるのでここでは詳しくは述べません。(以下のサイトが分かりやすく説明しています: http://isl.sist.chukyo-u.ac.jp/Archives/tm.html)


では実際にテンプレートマッチングを使ってみましょう。
自分で実装しても良かったのですが、OpenCVにあるらしいのでそれを使ってみます。

labs.eecs.tottori-u.ac.jp

ここでは6つの指標(SQDIFF,SQDIFF_NORMED,CCORR,CCORR_NORMED,CCOEFF,CCOEFF_NORMED)を使って判別しています。
それぞれの計算式はコレに載っています。

opencv.jp

実際に行ってみた結果が次の6枚です。
f:id:kaworu_mk6:20190529193130p:plainf:id:kaworu_mk6:20190529193133p:plainf:id:kaworu_mk6:20190529193136p:plainf:id:kaworu_mk6:20190529193139p:plainf:id:kaworu_mk6:20190529193142p:plainf:id:kaworu_mk6:20190529193147p:plain

SQDIFF以外はちゃんと正解を出していました。


私が紹介した論文では単一の加速度センサーによる活動認識において、Template Matchingを使う事で他の統計的学習法よりも良い精度を出す場合があるなどの話をしていました。T-Mを使う利点としてはtraining setの数が少ない場合でも高い認識率を出す事らしいです。


今回読んだ論文の中にはDynamic Time Warpingなどの話も出てきていたので、それについてもまた今度ブログで紹介できればと思います。