テンプレートマッチングによる物体検出の原理(SAD, SSD, NCC, ZNCC)

テンプレートマッチングによる物体検出の原理について、計算式や計算例も踏まえて解説します。

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

テンプレートマッチング(Template matching)とは、入力画像中からテンプレート画像(部分画像)と最も類似する箇所を探索する処理です。

■左から順に入力画像、テンプレート画像、出力画像

テンプレートマッチングでは、入力画像の一部分とテンプレート画像の類似度を求めます。
その類似度の計算方法には種類がいくつかあります。
今回は、その代表例である「SSD」「SAD」「NCC」「ZNCC」の4つを解説します。

動画解説版

本ページの内容は以下動画でも解説しています。

SSD(Sum of Squared Difference)

SSD(Sum of Squared Difference)では、「画素値の差分の二乗和(二乗誤差)」で類似度を評価します。
この場合、SSDの値が最小になる場所が類似度が最も高いことになります。

入力画像の画素値をI(x,y)I(x,y)、テンプレート画像の画素値をT(x,y)T(x,y)とします。
また、テンプレート画像の幅をww, 高さをhhとします。
走査位置がdx,dydx,dyの場合、SSDの値は次式で計算できます。

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

例えば、テンプレート画像の幅w=2w=2、高さh=2h=2のとき、SSD(1,0)SSD(1, 0)の計算式は以下になります。
SSD(1,0)=x=01y=01(I(1+x,y)T(x,y))2 SSD(1, 0)={\displaystyle \sum_{x=0}^{1} \sum_{y=0}^{1}}(I(1+x,y)-T(x,y))^2

SSDが最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

計算例

以下の入力画像IIとテンプレート画像TTSSDSSDを計算します。

① 走査位置I(0,0)I(0, 0)で計算すると、以下のとおりSSD=43SSD=43となります。

② 走査位置I(1,0)I(1, 0)で計算すると、以下のとおりSSD=25SSD=25となります。

③ 走査位置I(0,1)I(0, 1)で計算すると、以下のとおりSSD=18SSD=18となります。

④ 走査位置I(1,1)I(1, 1)で計算すると、以下のとおりSSD=1SSD=1となります。

SSDSSDの値が最小となるのは走査位置I(1,1)I(1, 1)なので、このときの探索範囲がテンプレート画像と最も類似していると判断できます。

SAD(Sum of Absolute Difference)

SAD(Sum of Absolute Difference)では、「画素値の差分の絶対値の和」で類似度を評価します。
この場合もSADの値が最小になるときが類似度が最も高いことになります。

入力画像の画素値をI(x,y)I(x,y)、テンプレート画像の画素値をT(x,y)T(x,y)とします。
また、テンプレート画像の幅をww, 高さをhhとします。
走査位置がdx,dydx,dyの場合、SADの値は次式で計算できます。

SAD(dx,dy)=x=0w1y=0h1I(dx+x,dy+y)T(x,y) SAD(d_x, d_y)={\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}}|I(d_x+x,d_y+y)-T(x,y)|

SADが最小となる走査位置が、テンプレート画像に最も類似する部分の左上座標となります。
SADはSSDと比べて以下の特徴があります。

  • 計算量が少ない(メリット)
  • 外れ値の影響を受けにくい(メリット)
  • 照明の影響をかなり受けやすい(デメリット)※SSDもそれなりに影響を受ける

計算例

以下の入力画像IIとテンプレート画像TTSADSADを計算します。
ただし、入力画像IIは、元画像Hが照明変化により全ての画素値が4増加したものと仮定します。

① 走査位置I(0,0)I(0, 0)で計算すると、以下のとおりSAD=6SAD=6となります。

② 走査位置I(1,0)I(1, 0)で計算すると、以下のとおりSAD=9SAD=9となります。

③ 走査位置I(0,1)I(0, 1)で計算すると、以下のとおりSAD=14SAD=14となります。

④ 走査位置I(1,1)I(1, 1)で計算すると、以下のとおりSAD=15SAD=15となります。

SADSADの値が最小となるのは走査位置I(0,0)I(0, 0)なので、このときの探索範囲がテンプレート画像と最も類似していると判断されます。
このように、SADは照明変化の影響を受けやすいことがわかります。

NCC(Normalized Cross Correlation)

NCC(Normalized Cross Correlation)では、「正規化相互相関」で類似度を評価します。

入力画像の画素値をI(x,y)I(x,y)、テンプレート画像の画素値をT(x,y)T(x,y)とします。
また、テンプレート画像の幅をww, 高さをhhとします。
走査位置がdx,dydx,dyの場合、NCCの値は次式で計算できます。

NCC(dx,dy)=[I(dx+x,dy+y)T(x,y)][I(dx+x,dy+y)]2[T(x,y)]2 NCC(d_x, d_y)=\frac{ \sum \sum [ I(d_x+x,d_y+y)T(x,y)] } { \sqrt{\sum \sum [I(d_x+x,d_y+y)]^2} \sqrt{ \sum \sum [T(x,y)]^2} }
ここで、

=x=0w1y=0h1 \sum \sum = {\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}}

NCCの値は-1.0~1.0に収まり、最大値1.0に最も近くなった走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

  • 照明の影響を受けにくい(メリット)
  • 計算量が多い(デメリット)

NCCは、テンプレート画像と入力画像の部分領域の輝度値を正規化します。これにより、画像の相対的な輝度パターンを比較することができます。
また、テンプレート画像と入力画像の部分領域の内積を計算します。内積は、ベクトルの方向を比較するものであり、ベクトルの大きさ(輝度の絶対値)には依存しません。これらの理由により、「照明変化に比較的強い」という利点があります。

ZNCC(Zero means Normalized Cross Correlation)

ZNCC(Zero means Normalized Cross Correlation)では、「零平均正規化相互相関」と呼ばれる統計量で類似度を評価します。

入力画像の画素値をI(x,y)I(x,y)、テンプレート画像の画素値をT(x,y)T(x,y)とします。
また、テンプレート画像の幅をww, 高さをhhとします。
走査位置がdx,dydx,dyの場合、ZNCCの値は次式で計算できます。

ZNCC(dx,dy)=[(I(dx+x,dy+y)μI)(T(x,y)μT][I(dx+x,dy+y)μI]2[T(x,y)μT]2 ZNCC(d_x, d_y)=\frac{ \sum \sum [ (I(d_x+x,d_y+y)-\mu_I)(T(x,y)-\mu_T] } { \sqrt{\sum \sum [I(d_x+x,d_y+y)-\mu_I]^2} \sqrt{ \sum \sum [T(x,y)-\mu_T]^2} }

ここで、

=x=0w1y=0h1 \sum \sum = {\displaystyle \sum_{x=0}^{w-1} \sum_{y=0}^{h-1}}

μI,μT\mu_I, \mu_Tは、入力画像とテンプレート画像の平均値です。
ZNCCの値は-1.0~1.0に収まり、最大値1.0に最も近くなった走査位置が、テンプレート画像に最も類似する部分の左上座標となります。

計算過程で平均値を引くため、比較する2つの画像領域の平均値が異なっていても類似度が変化しません。つまり、NCCよりも明るさの変動に対してよりロバストとなります。

お借りした画像:プロ生ちゃん(暮井 慧)

Python版OpenCVによる実装例

【Python/OpenCV】テンプレートマッチングの実装(SSD、SAD、NCC、ZNCC)
PythonとOpenCVで画像のテンプレートマッチング(SSD)を行う方法をソースコード付きで解説します。

関連ページ

画像処理
「画像処理」の記事一覧です。
この記事を書いた人
西住技研

在学中はシステム制御理論や画像処理、機械学習を専攻分野として研究していました。就職後は、プログラミング(Python)を活用したデータ分析や作業自動化に取り組み、現在に至ります。そこで得たノウハウをブログで発信しています。
YoutubeX(旧Twitter)でも情報発信中です

西住技研をフォローする
画像処理

コメント

  1. 加納勝博 より:

    お世話になります。

    【Python/OpenCV】テンプレートマッチングの実装(SSD、SAD、NCC、ZNCC) 

    の方法②を試してみたのですが、

    # 入力画像の読み込み
    img = cv2.imread(“C:/github/sample/python/opencv/template-matching/input.png”)
    temp = cv2.imread(“C:/github/sample/python/opencv/template-matching/temp.png”)

    と、

    # 結果を出力
    cv2.imwrite(“C:/github/sample/python/opencv/template-matching/sad2.png”, img)

    の、( )内のファイルを、そこからダウンロードした暮井慧の絵や手持ちの写真に置き換えて
    runさせたのですが、次のようなエラーが発生しました。

    何か設定しないといけないようなところがあるのでしょうか?
    原因がわからないので教えてください。

  2. 加納勝博 より:

    すみません。エラー内容の記述を忘れました。以下の通りです。
    よろしくお願いします。

    Traceback (most recent call last):
    File “D:/P&Q&A/テンプレートマッチング001.py”, line 33, in
    gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
    cv2.error: OpenCV(4.2.0) C:\projects\opencv-python\opencv\modules\imgproc\src\color.cpp:182: error: (-215:Assertion failed) !_src.empty() in function ‘cv::cvtColor’

    • 西住技研 管理人 より:

      加納様
      コメントありがとうございます。
      入力画像データが空のようですね。
      cv2.imread()の引数には、入力画像のファイルパスを指定しますが、そちらが正しくない可能性が高いと思います。

  3. 匿名 より:

    NCCは照明変化に対して頑健でないといった方向がされている論文があります. 筆者様はどうしてNCCが照明変化に対して頑健であると考えられたのでしょうか.