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:plain f:id:kaworu_mk6:20190529193133p:plain f:id:kaworu_mk6:20190529193136p:plain f:id:kaworu_mk6:20190529193139p:plain f:id:kaworu_mk6:20190529193142p:plain f:id:kaworu_mk6:20190529193147p:plain