テンプレートマッチング

テンプレートマッチング^[1]は、デジタル画像処理において、テンプレート画像と一致する画像の小さな部分を見つける技術です。これは、製造における品質管理、 ^[2]、 移動ロボットのナビゲーション、^[3]、または画像のエッジ検出に使用できます。^[4]

テンプレートマッチングタスクにおける主な課題は、画像内で目的の物体が部分的に隠れている場合のオクルージョンの検出、物体が歪んでいたり異なる角度から撮影されている場合の非剛体変換の検出、照明や背景の変化に対する感度、背景の乱雑さ、スケールの変化などである。^[5]

テンプレート マッチングに対する特徴ベースのアプローチは、ターゲット画像またはフレームに一致する形状、テクスチャ、色などの画像特徴の抽出に依存しています。このアプローチは通常、ニューラル ネットワークと、 VGG、 AlexNet、ResNetなどのディープラーニング 分類器を使用して実現されます。^[要出典]多くの最新の分類器が基づいている畳み込みニューラル ネットワーク(CNN) は、画像をさまざまな隠し層に渡すことで処理し、各層で画像に関する分類情報を含むベクトルを生成します。これらのベクトルはネットワークから抽出され、画像の特徴として使用されます。CNN などのディープ ニューラル ネットワークを使用した特徴抽出は非常に効果的であることが証明されており、最先端のテンプレート マッチング アルゴリズムの標準となっています。^[6]

この特徴ベースのアプローチは、後述するテンプレートベースのアプローチよりも堅牢であることが多い。そのため、非剛体や平面外の変換、背景の乱雑さや照明の変化が大きいテンプレートをマッチングできるため、テンプレートマッチングの最先端の方法となっている。^{[7] [8] [9]}

強い特徴のないテンプレートの場合、またはテンプレート画像の大部分がマッチング画像全体を構成する場合、テンプレートベースのアプローチが効果的である可能性があります。テンプレートベースのマッチングでは多数のデータポイントのサンプリングが必要になる場合があるため、結果として得られる縮小画像に対して操作を実行する前に、検索画像とテンプレート画像の解像度を同じ係数で下げてサンプリングポイントの数を減らすことが望ましいことがよくあります。この前処理方法では、画像のマルチスケール、つまりピラミッド表現が作成され、検索画像内のデータポイントの検索ウィンドウが縮小されるため、テンプレートをすべての実行可能なデータポイントと比較する必要がなくなります。ピラミッド表現は次元削減の手法であり、次元の呪いに悩まされているデータセットでの機械学習の一般的な目的です。

テンプレートが直接一致するものを提供しない場合は、さまざまな条件下で一致するオブジェクトの詳細を示すテンプレートを作成するために固有空間を実装すると便利な場合があります。たとえば、さまざまな視点、照明、色のコントラスト、オブジェクトのポーズなどです。^[10] たとえば、アルゴリズムが顔を探している場合、そのテンプレートの固有空間は、カメラに対してさまざまな位置、さまざまな照明条件、またはさまざまな表情（つまり、ポーズ）の顔の画像（つまり、テンプレート）で構成される場合があります。

マッチング画像が物体によって隠されていたり、遮蔽されていたりする可能性もあります。このような場合、考えられるすべての遮蔽をカバーするために多数のテンプレートを用意するのは不合理です。たとえば、検索対象がトランプである場合、検索画像の中には、カードを持っている人の指や、その上に置かれた別のカード、またはカメラの前にある他の物体によってカードが隠されているものがあります。物体が柔軟であったり、ポーズをとったりできる場合、動きが追加の問題となり、動きと遮蔽の両方を含む問題があいまいになります。^[11]このような場合、1つの解決策として、テンプレート画像を複数のサブ画像に分割し、各サブ画像に対してマッチングを実行することが考えられます。

テンプレートマッチングは計算解剖学（CA）の中心的なツールです。この分野では、変形可能なテンプレートモデルを使用して、微分同相写像群（物体を滑らかに変形する関数）の下で人間の解剖学的構造とその軌道の空間をモデル化します。 ^[12]テンプレートマッチングは、テンプレート画像に作用してターゲット画像と一致する未知の微分同相写像を見つけるためのアプローチとして生まれました。

CA のテンプレート マッチング アルゴリズムは、大変形微分同相距離マッピング(LDDMM)と呼ばれるようになりました。現在、解剖学的ランドマーク ポイント、曲線、表面、ボリュームをマッチングするための LDDMM テンプレート マッチング アルゴリズムがあります。

テンプレート マッチングの基本的な方法は、「線形空間フィルタリング」と呼ばれることもあり、検出する検索画像の特定の特徴に合わせて調整された画像パッチ (つまり、「テンプレート画像」または「フィルタ マスク」) を使用します。 ^{[引用が必要]}この手法は、追加の色変数が存在しない、または関連しないグレー画像またはエッジ画像で簡単に実行できます。相互相関手法は、検索画像とテンプレート画像の類似性を比較します。その出力は、画像構造がテンプレート構造と一致する場所、つまり、大きな検索画像値に大きなテンプレート画像値が乗算される場所で最大になります。

この方法は、通常、テンプレートとして使用する検索画像の一部を最初に選択することによって実装されます。 が検索画像ピクセルの値を表すものとします。ここで、 は検索画像内のピクセルの座標を表します。簡単にするために、ピクセル値はグレースケール画像のようにスカラーであると仮定します。同様に、がテンプレート ピクセルの値を表すものとします。ここで、 はテンプレート画像内のピクセルの座標を表します。フィルタを適用するには、テンプレート画像の中心 (または原点) を検索画像内の各ポイントに移動して、テンプレートが及ぶ領域全体にわたって、検索画像とテンプレート画像のピクセル値の間の積の合計 (ドット積に類似) を計算します。より正式には、 がテンプレート画像の中心 (または原点) である場合、検索画像内の各ポイントでの相互相関は次のように計算できます。便宜上、はテンプレート画像のピクセル値とそのドメイン (テンプレートの境界) の両方を表します。検索画像に対するテンプレートのすべての可能な位置が考慮されることに注意してください。相互相関値は、検索ピクセルとテンプレート ピクセルの値が一致したときに最大になるため、最適な一致位置はを超える最大値に対応します。 ${\displaystyle S(x,y)}$${\displaystyle (x,y)}$${\textstyle T(x_{t},y_{t})}$${\textstyle (x_{t},y_{t})}$${\displaystyle (0,0)}$${\displaystyle T\star S}$${\displaystyle (x,y)}$$${\displaystyle (T\star S)(x,y)=\sum _{(x_{t},y_{t})\in T}T(x_{t},y_{t})\cdot S(x_{t}+x,y_{t}+y)}$$${\displaystyle T}$${\displaystyle (x_{m},y_{m})}$${\displaystyle T\star S}$${\displaystyle S}$

テンプレート マッチングを使用して画像の移動問題を処理する別の方法は、絶対差の合計(SAD) 測定を使用してピクセルの強度を比較することです。これを定式化するには、検索画像とテンプレート画像のピクセルの光強度をそれぞれ座標とで表します。次に、テンプレートの中心 (または原点) を検索画像内のある点に移動すると、前と同じように、その点におけるテンプレートと検索ピクセル強度の絶対差の合計は次のようになります。この測定では、相互相関の場合のように SAD が最大になるのではなく、SAD が最小になるとテンプレートの最適な位置が示されます。SAD は実装と理解が比較的簡単ですが、実行が比較的遅くなる傾向があります。SAD テンプレート マッチングの簡単なC++実装を以下に示します。 ${\displaystyle I_{S}(x_{s},y_{s})}$${\displaystyle I_{T}(x_{t},y_{t})}$${\displaystyle (x_{s},y_{s})}$${\displaystyle (x_{t},y_{t})}$${\displaystyle (x,y)}$$${\displaystyle SAD(x,y)=\sum _{(x_{t},y_{t})\in T}\left\vert I_{T}(x_{t},y_{t})-I_{S}(x_{t}+x,y_{t}+y)\right\vert }$$

この単純な実装では、上記の方法がグレー画像に適用されていると想定されています。これが、ピクセル強度としてグレーが使用される理由です。この実装の最終的な位置は、テンプレート画像が検索画像と最も一致する左上の位置を示します。

最小SAD = VALUE_MAX ;  

// 検索画像をループします
for ( size_t x = 0 ; x <= S_cols - T_cols ; x ++ ) { for ( size_t y = 0 ; y <= S_rows - T_rows ; y ++ ) { SAD = 0.0 ;             
                 
          

        // テンプレート画像をループします
for ( size_t j = 0 ; j < T_cols ; j ++ ) for ( size_t i = 0 ; i < T_rows ; i ++ ) {                  
                       

                ピクセルp_SearchIMG = S [ y + i ][ x + j ];ピクセルp_TemplateIMG = T [ i ][ j ]; SAD += abs ( p_SearchIMG . Grey - p_TemplateIMG . Grey ); }   
                   
		
                      
            

        // 見つかった最適な位置を保存します
if ( minSAD > SAD ) { minSAD = SAD ; // 最小 SAD を返しますposition . bestRow = y ; position . bestCol = x ; position . bestSAD = SAD ; } } }               
              
            
              
              
              
        
    
    

カラー画像に対してテンプレート マッチングを実行する 1 つの方法は、ピクセルをカラー コンポーネントに分解し、各色ごとに個別に計算された SAD の合計を使用して、カラー テンプレートと検索画像間の一致の品質を測定することです。

過去には、このタイプの空間フィルタリングは、演算の計算が複雑なため、通常は専用のハードウェアソリューションでのみ使用されていましたが、^{[13]画像の周波数領域でフィルタリングすることでこの複雑さを軽減することができます。これは「周波数領域フィルタリング」と呼ばれ、}畳み込み定理を使用して行われます。

マッチング処理を高速化するもう 1 つの方法は、画像ピラミッドを使用することです。これは、異なるスケールの一連の画像であり、元の画像を繰り返しフィルタリングしてサブサンプリングすることで、解像度を下げた一連の画像を生成します。^[14]これらの低解像度の画像は、テンプレート (同様に解像度を下げた) を検索して、より大きなスケールで検索するための開始位置を得ることができます。その後、より大きな画像を開始位置の周りの小さなウィンドウで検索して、最適なテンプレートの位置を見つけることができます。

他の方法では、変換、スケール、画像の回転、さらにはすべてのアフィン変換などの問題も処理できます。^{[15] [16] [17]}

複数のテンプレート (固有空間) を使用することでマッチング方法を改善できます。これらの他のテンプレートは、異なるスケールと回転を持つことができます。

特徴ベースとテンプレートベースのアプローチをハイブリッド化することで、マッチング方法の精度を向上させることも可能です。^[18] 当然、これには検索画像とテンプレート画像に特徴マッチングをサポートするのに十分な特徴があることが必要です。

同様の他の方法には、「ステレオマッチング」、「画像登録」、「スケール不変特徴変換」などがあります。

テンプレートマッチングにはさまざまな用途があり、顔認識（顔認識システムを参照）や医療画像処理などの分野で使用されています。過去には、一定時間内に橋の一部を横切る顔の数を数えるシステムが開発され、使用されていました。他のシステムには、デジタル胸部X線内の石灰化結節の自動検出などがあります。^[19] 最近、この方法は地統計シミュレーションに実装され、高速アルゴリズムを提供できるようになりました。^[20]

• 顔認識システム
• パターン認識
• コンピュータービジョン
• 弾性マッチング

• OpenCV でのテンプレートマッチング
• テンプレートマッチングを使用した視覚的物体認識
• 回転、スケール、平行移動不変のテンプレートマッチングのデモプログラム
• 視点不変テンプレートマッチング
• 2009年までの広範なテンプレートマッチング参考文献