【VBA×画像処理】ビットマップ画像でテンプレートマッチングを行う

本ページでは、VBAで読み込んだビットマップ（BMP）画像を内部的に処理し、別途用意したテンプレート画像と最も類似した領域を画像内から探索する「テンプレートマッチング」の実装方法を解説していきます。テンプレートマッチングは画像内の特定パターンの検出や位置合わせ、製造業の検査画像処理など幅広い分野で利用される基本的な画像処理手法です。本ページでは代表的な3つのマッチング手法（SSD・SAD・ZNCC）を実装します。

テンプレートマッチング

テンプレートマッチングとは、別途用意したテンプレート画像と最も類似した領域を入力画像内から探索する処理のことを指します。具体的には入力画像上をテンプレート画像と同サイズの「窓」でずらしながら走査し、各位置でテンプレート画像との類似度（あるいは差分）を計算して、最も一致する位置を特定します。式で表すと下記の通りです。(※ここで \( I \) は入力画像、\( T \) はテンプレート画像、\( N, M \) はテンプレート画像の幅と高さ、\( S(x, y) \) は位置 \( (x, y) \) でのスコア)

\[
S(x, y) = f\bigl( I(x+i, y+j),\, T(i, j) \bigr) \quad (i = 0, 1, \dots, N-1,\, j = 0, 1, \dots, M-1)
\]

類似度の計算方法 \( f \) によってマッチング手法が異なります。本ページでは画像処理で広く利用される代表的な3つの手法 SSD・SAD・ZNCC を実装します。なお、計算コストを抑えるためいずれの手法でも入力画像とテンプレート画像はあらかじめグレースケール化した上でマッチングを行います。

SSD (Sum of Squared Difference)

SSDは入力画像の比較領域とテンプレート画像の各ピクセルの輝度値の差を2乗して足し合わせた値です。値が小さいほど両画像が類似しており、最小値となる位置がマッチング箇所となります。

計算が単純で実装が容易な反面、画像全体の明るさが変化するとスコアも大きく変動するため、明るさ変化に弱いのが欠点です。

\[
\text{SSD}(x, y) = \sum_{j=0}^{M-1} \sum_{i=0}^{N-1} \bigl( I(x+i, y+j) – T(i, j) \bigr)^2
\]

SAD (Sum of Absolute Difference)

SADは入力画像の比較領域とテンプレート画像の各ピクセルの輝度値の差の絶対値を足し合わせた値です。SSDと同様に値が小さいほど類似しており、最小値となる位置がマッチング箇所となります。

SSDよりさらに計算が単純で2乗の計算がない分わずかに高速ですが、SSDと同じく明るさ変化には弱い特性があります。

\[
\text{SAD}(x, y) = \sum_{j=0}^{M-1} \sum_{i=0}^{N-1} \bigl| I(x+i, y+j) – T(i, j) \bigr|
\]

ZNCC (Zero-mean Normalized Cross-Correlation)

ZNCCは入力画像の比較領域とテンプレート画像のそれぞれから平均値を引いた上で正規化した相互相関値です。SSDやSADとは異なり、値は -1 〜 1 の範囲をとり 最大値となる位置がマッチング箇所となります。

計算式が複雑な分計算量は多くなりますが、各画像の平均値を引いてから計算するため明るさ変化に強いという大きな利点があります。実用的には最も使われることが多い手法です。

\[
\text{ZNCC}(x, y) = \frac{\displaystyle \sum_{j=0}^{M-1} \sum_{i=0}^{N-1} \bigl( I(x+i, y+j) – \bar{I} \bigr)\bigl( T(i, j) – \bar{T} \bigr)}{\sqrt{\displaystyle \sum_{j=0}^{M-1} \sum_{i=0}^{N-1} \bigl( I(x+i, y+j) – \bar{I} \bigr)^2 \cdot \sum_{j=0}^{M-1} \sum_{i=0}^{N-1} \bigl( T(i, j) – \bar{T} \bigr)^2 }}
\]

(※ここで \( \bar{I}, \bar{T} \) はそれぞれ比較領域・テンプレート画像の輝度平均値)

3手法の比較

3手法の特性をまとめると下表の通りです。基本的には精度を優先する場合はZNCC、速度を優先する場合はSADやSSDを利用します。

手法	判定基準	値域	計算量	明るさ変化耐性
SSD	最小値	0以上	低	×
SAD	最小値	0以上	低	×
ZNCC	最大値	-1〜1	高	○

サンプルコード

以下はSSD・SAD・ZNCCの3手法によるテンプレートマッチングを行うためのコードです。事前に用意しておいたclsBitmap内に下記コードをコピペすることで利用可能になります。各手法のPublic関数は内部の共通処理関数 TemplateMatching をアルゴリズム名付きで呼び出すラッパー方式となっており、共通処理関数内では指定アルゴリズムに応じてスコア計算とベストスコア判定を行います。

クラスモジュール (clsBitmapに追記)

'============================================================================
'=  テンプレートマッチング (SSD / SAD / ZNCC)
'=
'=  【依存関数】下記の処理を事前に実装しておく必要があります
'=    ・ Grayscale                : グレースケール変換
'=        https://liclog.net/vba-bitmap-image-processing-grayscale
'=    ・ Rectangle (任意)         : 検出箇所の枠描画 (結果可視化に利用)
'=        https://liclog.net/vba-bitmap-image-processing-draw-rectangle
'============================================================================

'****************************************************************************
'*  SSD(Sum of Squared Difference)によるテンプレートマッチング
'*
'*      sPathTmp    ：テンプレート画像ファイルパス(.bmp)
'*      (lStride)   ：探索ストライド[px] (省略時は1)
'*      (lMethod)   ：グレースケール変換手法
'*                    0 = 平均法 / 1 = 加重平均法 / 2 = 輝度法
'*      戻り値      ：判定結果エリア座標(左上X,Y座標,右下X,Y座標)
'****************************************************************************
Public Function SSD(ByVal sPathTmp As String, _
                    Optional lStride As Long = 1, _
                    Optional lMethod As Long = 2) As Long()
                    
    SSD = TemplateMatching("SSD", sPathTmp, lStride, lMethod)

End Function

'****************************************************************************
'*  SAD(Sum of Absolute Difference)によるテンプレートマッチング
'*
'*      sPathTmp    ：テンプレート画像ファイルパス(.bmp)
'*      (lStride)   ：探索ストライド[px] (省略時は1)
'*      (lMethod)   ：グレースケール変換手法
'*                    0 = 平均法 / 1 = 加重平均法 / 2 = 輝度法
'*      戻り値      ：判定結果エリア座標(左上X,Y座標,右下X,Y座標)
'****************************************************************************
Public Function SAD(ByVal sPathTmp As String, _
                    Optional lStride As Long = 1, _
                    Optional lMethod As Long = 2) As Long()
                    
    SAD = TemplateMatching("SAD", sPathTmp, lStride, lMethod)

End Function

'****************************************************************************
'*  ZNCC(Zero-mean Normalized Cross-Correlation)によるテンプレートマッチング
'*
'*      sPathTmp    ：テンプレート画像ファイルパス(.bmp)
'*      (lStride)   ：探索ストライド[px] (省略時は1)
'*      (lMethod)   ：グレースケール変換手法
'*                    0 = 平均法 / 1 = 加重平均法 / 2 = 輝度法
'*      戻り値      ：判定結果エリア座標(左上X,Y座標,右下X,Y座標)
'****************************************************************************
Public Function ZNCC(ByVal sPathTmp As String, _
                     Optional lStride As Long = 1, _
                     Optional lMethod As Long = 2) As Long()
                    
    ZNCC = TemplateMatching("ZNCC", sPathTmp, lStride, lMethod)

End Function

'----------------------------------------------------------------------------
'-  テンプレートマッチング共通処理
'----------------------------------------------------------------------------
Private Function TemplateMatching(ByVal sAlgorithm As String, _
                                  ByVal sPathTmp As String, _
                                  Optional lStride As Long = 1, _
                                  Optional lMethod As Long = 2) As Long()
 
    Dim rgbDataOrg()      As RGBTRIPLE '元画像RGBデータ
    Dim rgbDataTmp()      As RGBTRIPLE 'テンプレート画像RGBデータ
    Dim rgbDataOrgGray()  As RGBTRIPLE '元画像RGBデータ(グレースケール)
    Dim rgbDataTmpGray()  As RGBTRIPLE 'テンプレート画像RGBデータ(グレースケール)
    Dim rgbDataCompArea() As RGBTRIPLE '比較エリア
    
    Dim lCoord(3)       As Long
    Dim lHeight         As Long
    Dim lWidth          As Long
    Dim lHeightTmp      As Long
    Dim lWidthTmp       As Long
    Dim lX              As Long
    Dim lY              As Long
    
    Dim dScore          As Double
    Dim dScoreBest      As Double
    Dim bIsLargerBetter As Boolean
    
    Dim lMinX As Long
    Dim lMinY As Long
    Dim lMaxX As Long
    Dim lMaxY As Long
    
    'アルゴリズム別の初期値設定 (SSD/SADは最小値探索、ZNCCは最大値探索)
    Select Case sAlgorithm
        Case "SSD", "SAD"
            bIsLargerBetter = False
            dScoreBest = 1E+30  '最小値を探すので大きな値で初期化
        Case "ZNCC"
            bIsLargerBetter = True
            dScoreBest = -1E+30 '最大値を探すので小さな値で初期化
    End Select

    '元画像 & テンプレート画像を読込
    rgbDataOrg = m_rgbImageData
    rgbDataTmp = ImportDataFromBitmapFile(sPathTmp)
    
    '元画像 & テンプレート画像をグレースケール変換
    rgbDataOrgGray = Grayscale(rgbDataOrg, lMethod)
    rgbDataTmpGray = Grayscale(rgbDataTmp, lMethod)
    
    lHeight = UBound(rgbDataOrg, 1) + 1
    lWidth = UBound(rgbDataOrg, 2) + 1
    lHeightTmp = UBound(rgbDataTmp, 1) + 1
    lWidthTmp = UBound(rgbDataTmp, 2) + 1
    
    '元画像をテンプレートサイズの窓で走査
    For lY = 0 To lHeight - lHeightTmp Step lStride
        For lX = 0 To lWidth - lWidthTmp Step lStride
          
            '比較領域を抽出
            rgbDataCompArea = ExtractCompareArea(rgbDataOrgGray, lX, lY, lWidthTmp, lHeightTmp)
          
            'アルゴリズム別にスコアを計算
            Select Case sAlgorithm
                Case "SSD"
                    dScore = SumOfSquaredDifference(rgbDataCompArea, rgbDataTmpGray)
                Case "SAD"
                    dScore = SumOfAbsoluteDifference(rgbDataCompArea, rgbDataTmpGray)
                Case "ZNCC"
                    dScore = ZeroMeanNCC(rgbDataCompArea, rgbDataTmpGray)
            End Select

            '最良スコアを更新
            If (bIsLargerBetter And dScore > dScoreBest) Or _
               (Not bIsLargerBetter And dScore < dScoreBest) Then
                dScoreBest = dScore
                lMinX = lX
                lMinY = lY
                lMaxX = lX + lWidthTmp - 1
                lMaxY = lY + lHeightTmp - 1
            End If
            
        Next
    Next
    
    lCoord(0) = lMinX
    lCoord(1) = lMinY
    lCoord(2) = lMaxX
    lCoord(3) = lMaxY
    
    TemplateMatching = lCoord
    
End Function

'----------------------------------------------------------------------------
'-  比較領域を抽出
'----------------------------------------------------------------------------
Private Function ExtractCompareArea(rgbDataOrg() As RGBTRIPLE, _
                                    ByVal lStartX As Long, ByVal lStartY As Long, _
                                    ByVal lAreaWidth As Long, ByVal lAreaHeight As Long) As RGBTRIPLE()
    
    Dim rgbDataArea() As RGBTRIPLE
    Dim lX As Long
    Dim lY As Long

    ReDim rgbDataArea(lAreaHeight - 1, lAreaWidth - 1)

    For lY = 0 To lAreaHeight - 1
        For lX = 0 To lAreaWidth - 1
            rgbDataArea(lY, lX) = rgbDataOrg(lStartY + lY, lStartX + lX)
        Next
    Next

    ExtractCompareArea = rgbDataArea
    
End Function

'----------------------------------------------------------------------------
'-  SSD : 輝度値の差の2乗和
'----------------------------------------------------------------------------
Private Function SumOfSquaredDifference(rgbDataA() As RGBTRIPLE, _
                                        rgbDataB() As RGBTRIPLE) As Double
    
    Dim dSum  As Double
    Dim lDiff As Long
    Dim lX    As Long
    Dim lY    As Long
    Dim lH    As Long
    Dim lW    As Long

    lH = UBound(rgbDataA, 1)
    lW = UBound(rgbDataA, 2)
    
    dSum = 0
    For lY = 0 To lH
        For lX = 0 To lW
            lDiff = CLng(rgbDataA(lY, lX).rgbRed) - CLng(rgbDataB(lY, lX).rgbRed)
            dSum = dSum + lDiff * lDiff
        Next
    Next

    SumOfSquaredDifference = dSum
    
End Function

'----------------------------------------------------------------------------
'-  SAD : 輝度値の差の絶対値の和
'----------------------------------------------------------------------------
Private Function SumOfAbsoluteDifference(rgbDataA() As RGBTRIPLE, _
                                         rgbDataB() As RGBTRIPLE) As Double
    
    Dim dSum  As Double
    Dim lDiff As Long
    Dim lX    As Long
    Dim lY    As Long
    Dim lH    As Long
    Dim lW    As Long

    lH = UBound(rgbDataA, 1)
    lW = UBound(rgbDataA, 2)
    
    dSum = 0
    For lY = 0 To lH
        For lX = 0 To lW
            lDiff = CLng(rgbDataA(lY, lX).rgbRed) - CLng(rgbDataB(lY, lX).rgbRed)
            dSum = dSum + Abs(lDiff)
        Next
    Next

    SumOfAbsoluteDifference = dSum
    
End Function

'----------------------------------------------------------------------------
'-  ZNCC : 平均値を引いた正規化相互相関
'----------------------------------------------------------------------------
Private Function ZeroMeanNCC(rgbDataA() As RGBTRIPLE, _
                             rgbDataB() As RGBTRIPLE) As Double
    
    Dim dMeanA  As Double
    Dim dMeanB  As Double
    Dim dNumer  As Double '分子
    Dim dDenomA As Double '分母項A
    Dim dDenomB As Double '分母項B
    Dim dDevA   As Double
    Dim dDevB   As Double
    Dim lX      As Long
    Dim lY      As Long
    Dim lH      As Long
    Dim lW      As Long
    Dim lN      As Long

    lH = UBound(rgbDataA, 1)
    lW = UBound(rgbDataA, 2)
    lN = (lH + 1) * (lW + 1)
    
    '平均値を計算
    dMeanA = 0
    dMeanB = 0
    For lY = 0 To lH
        For lX = 0 To lW
            dMeanA = dMeanA + rgbDataA(lY, lX).rgbRed
            dMeanB = dMeanB + rgbDataB(lY, lX).rgbRed
        Next
    Next
    dMeanA = dMeanA / lN
    dMeanB = dMeanB / lN
    
    '相関係数を計算
    dNumer = 0
    dDenomA = 0
    dDenomB = 0
    For lY = 0 To lH
        For lX = 0 To lW
            dDevA = rgbDataA(lY, lX).rgbRed - dMeanA
            dDevB = rgbDataB(lY, lX).rgbRed - dMeanB
            dNumer = dNumer + dDevA * dDevB
            dDenomA = dDenomA + dDevA * dDevA
            dDenomB = dDenomB + dDevB * dDevB
        Next
    Next
    
    'ゼロ除算回避
    If dDenomA = 0 Or dDenomB = 0 Then
        ZeroMeanNCC = 0
    Else
        ZeroMeanNCC = dNumer / Sqr(dDenomA * dDenomB)
    End If
    
End Function

　
標準モジュール

Option Explicit
Sub main()

    Dim sPathBmpSrc As String
    Dim sPathBmpTmp As String
    Dim sPathBmpExport As String
    Dim oBitmap As clsBitmap
    Dim lCoord() As Long

    sPathBmpSrc = "C:\...\source.bmp"      '入力画像
    sPathBmpTmp = "C:\...\template.bmp"    'テンプレート画像
    sPathBmpExport = "C:\...\output.bmp"   '出力画像

    Set oBitmap = New clsBitmap
    Call oBitmap.LoadBitmap(sPathBmpSrc)                                          '画像読み込み
    lCoord = oBitmap.SSD(sPathBmpTmp)                                             'SSDによるテンプレートマッチング
    'lCoord = oBitmap.SAD(sPathBmpTmp)                                            'SADによるテンプレートマッチング
    'lCoord = oBitmap.ZNCC(sPathBmpTmp)                                           'ZNCCによるテンプレートマッチング
    Call oBitmap.Rectangle(lCoord(0), lCoord(1), lCoord(2), lCoord(3), _
                           RGB(0, 0, 255), 3)                                     '検出箇所を青枠で可視化
    Call oBitmap.ExportBitmap24(sPathBmpExport)                                   '画像出力

End Sub

使い方は上記コードのように、画像読み込み後にいずれかのマッチング手法を呼び出すだけです。

戻り値として検出された矩形領域の座標 (左上X, 左上Y, 右下X, 右下Y) がLong型配列で返るため、これを長方形の描画処理にそのまま渡すことで、検出箇所を画像上に枠線で可視化することができます。

　

関連情報

VBA×画像処理ページ

次回 >> 画像の平滑化(ガウシアンフィルタ)
前回 >> 画像に長方形を描画
画像処理のメインページへ戻る

参考

外部リンク：Template matching – Wikipedia
　　　　　：Cross-correlation – Wikipedia