>>「真面目」でも「頭がいい人」でもお金持ちになれないたった1つの理由とは

【画像処理に入門してみた】テンプレートマッチングについて理解する


こんにちは,学生エンジニアの迫佑樹(@yuki_99_s)です.

現在私は,ロボットの視覚センサ関係で,画像処理について勉強しています.これがめちゃめちゃ面白いんですよ

今回は,『テンプレートマッチング』と呼ばれるものについて勉強したことをまとめておくことにします!

テンプレートマッチングとは?

テンプレートマッチングとは,「ある画像と同じパターンが画像全体に存在するかを見つけること』です.

f:id:McG:20170712210142p:plain

やり方自体は単純な話で,ちょっとずつテンプレート画像を動かしながら,一致しているかを確認していけば良いという話になります.

f:id:McG:20170712205440p:plain

ここで,テンプレート画像のパターンの類似度を計算するための手法として,SSDとSADという二種類の手法があります.

SSDとは?

SSDとは,『Sum of Squared Difference』の略で,直訳すると『誤差の2乗の和』となります.

名前の通り,各画素値の2乗誤差を合計し,その値を比較することで画像がマッチしているかを判断する手法です

この2乗誤差の和が少ないほど,部分画像のパターンとの類似度が高いといえます.

テンプレート画像内の画素\((i,j)\),各画素の濃度を\(T(i,j)\),探索したい対象画像の濃度を\(I(i,j)\)とした時,誤差は\(I(i,j)-T(i,j)\)とかけるので,誤差の二乗和は\(\displaystyle \sum_{i} \sum_{j} \bigl(I(i,j)-T(i,j)\bigr)^2\)と書くことができますね.

f:id:McG:20170712212644p:plain

SADとは?

次に,SADと呼ばれる手法について説明します.

SADとは,『Sum of Absolute Difference』の略で,直訳すると『誤差の絶対値の和』となります.

SSDよりも単純で,誤差の絶対値の和を求めるという手法です

誤差の絶対値の和が小さいほど,部分画像とのパターンとの類似度が高いということになります.

先程と同様に,テンプレート画像内の画素\((i,j)\),各画素の濃度を\(T(i,j)\),探索したい対象画像の濃度を\(I(i,j)\)とした時,誤差は\(I(i,j)-T(i,j)\)とかけるので,誤差の絶対値の和は\( \displaystyle \sum_{i} \sum_{j} |I(i,j)-T(i,j)|\)となりますね.

f:id:McG:20170712230020p:plain

NCCについて

先ほど紹介したSSD及びSADでは,誤差に注目しました.

テンプレート画像と探索対象画像の類似度を計算するには,他に『相関係数を求める』という手法も思いつきます.

NCCは,『Normalized Cross-Correlation』の略で,直訳すると『正規化相互相関係数』となります.

テンプレート画像内の画素\((i,j)\),各画素の濃度を\(T(i,j)\),探索したい対象画像の濃度を\(I(i,j)\)とした時,とし,それらを2種類のデータとして扱った時に,統計学で習った相関係数を計算してあげると,以下の式で求めることが出来ます.

$$\frac{\displaystyle \sum_{i} \sum_{j} I(i,j)T(i,j)}{\displaystyle \sqrt{\sum_{i} \sum_{j}I(i,j)^2} \sqrt{\sum_{i} \sum_{j}T(i,j)^2}}$$

NCCは相関係数を表しているため,完全に一致した場合は1となります.

f:id:McG:20170712225658p:plain

しかしこれでは,テンプレート画像と対象画像の濃度が異なる場合,画素ごとの濃度誤差が蓄積されて,正確な検出ができなくなってしまいます.

そこで,濃度の平均値を引き,下のように正規化したものを使用することも多いです.

$$ \displaystyle \frac{ \displaystyle \sum_{i} \sum_{j} \bigl(I(i,j)-\mu_i(i,j)\bigr)\bigl(T(i,j)-\mu_t(i,j)\bigr)}{ \displaystyle \sqrt{ \sum_{i} \sum_{j} \bigl(I(i,j)-\mu_i(i,j)\bigr)^2} \sqrt{ \sum_{i} \sum_{j} \bigl(T(i,j)-\mu_t(i,j)\bigr)^2}}$$

 

ここで,\mu_t(i,j)及び\mu_i(i,j)は,テンプレート画像の濃度の平均値です.

平均値を引くことで,濃度変化の影響を受けないため,照明が変わったりしても信頼性が落ちないという点において優れています.

まとめ

他にもマッチング手法に関しては様々な手法がありますが,今回はSSD,SAD,NCCについてまとめました.

シグマ記号が多くて大変に思えたかもしれませんが,よくみると高校生でもわかるとても単純な形です.

Matlabあたりを使うと数十行のプログラムを書くだけでめっちゃ簡単に実験できるので,実際に試してみると良いと思いますよ!

f:id:McG:20170712230611p:plain