16 テンプレートマッチング
「この物体は画像のどこにあるか？」——これは産業用マシンビジョンに最も多く寄せられる質問である。マニピュレータが把持する部品はトレイのどの位置にあるか？実装ヘッドが位置合わせするパッドはどれだけずれているか？測定プログラムの基準点はこのフレームのどこにあるか？この問いに対する最も直接的な回答は、対象の「写真」1枚を用意し、画像内を1箇所ずつ比較して最も類似した場所を探すことである。これがテンプレートマッチング（template matching）である：小さな参照画像をテンプレート（template）とし、検索画像上を走査して比較し、類似度が最も高い位置（および角度）を出力する。モデリングも訓練サンプルも不要で、任意のテクスチャに適用できるため、産業用位置決めの主力として当然の地位を占めている。
本章では一連の実際のサンプル画像を通して解説する。黒色背景上に散在する面実装用アルミ電解コンデンサ（定格 470 µF、35 V、RVT シリーズ）で、Smart3 グレースケールマッチング例題プログラムから提供されたものである（\(1280\times 960\) 単チャネルグレースケール）。各コンデンサは反射性の金属製円頂部を持ち、上面には「470 / 35V / RVT」の3行のシルク印刷があり、左側には暗色の極性ストライプがある——ストライプと文字が共同で円の回転対称性を崩しているため、角度は一意に定まる。テンプレートはサンプル画像 001 の左上にある1個のコンデンサから切り出したもので（図 16.1 (a)）、円頂部の外接枠で \(230\times 230\) に裁断されている（円頂部の直径は約 214 px）。検索画像はサンプル画像 003（図 16.1 (b)）で、同じ型の5個のコンデンサがそれぞれ異なる位置と姿勢で散在している。正立しているもの、小角度回転しているもの、さらにほぼ \(180^\circ\) 反転しているものもある——これはまさにラインに部品が供給された後の実際の姿である。後述の セクション 16.5 ではサンプル画像 004、005 でも同じモデルの検証を行う。
16.1 類似度指標
テンプレート \(t(u,v)\) の左上角を検索画像 \(f\) の \((x,y)\) 位置に合わせたとき、「どれだけ似ているか」を表す数値が必要である——これが類似度指標（similarity measure）である。最も単純な2種類は、各画素の差の累積である絶対差和（sum of absolute differences, SAD）と二乗差和（sum of squared differences, SSD）である：
\[ D_{\mathrm{SAD}}(x,y)=\sum_{u,v}\bigl|f(x{+}u,\,y{+}v)-t(u,v)\bigr|, \qquad D_{\mathrm{SSD}}(x,y)=\sum_{u,v}\bigl(f(x{+}u,\,y{+}v)-t(u,v)\bigr)^2 . \]
両者とも値が小さいほど類似しており、計算コストが低く意味合いも単純であるが、生産ラインで致命的な欠点が1つある：輝度変化に敏感であることである。あるウィンドウの内容がちょうどテンプレートに照度ゲイン \(g\) を乗じたものであるとする（照明の強弱、ワーク表面の反射率のロット間差などがこのような線形変化を引き起こす）、その場合
\[ D_{\mathrm{SSD}}=\sum_{u,v}\bigl(g\,t(u,v)-t(u,v)\bigr)^2=(g-1)^2\sum_{u,v}t(u,v)^2 . \]
形状は完全に一致しているのに、残差はゲインのずれに対し二乗で増大する——照明が変化すると、SSD の目からは「完全な一致」が「大きく異なる」ものに見えてしまう。
解決策は、ウィンドウとテンプレートをそれぞれ「標準化」してから比較することである。平均を減じ（輝度オフセットを除去）、標準偏差で除し（ゲインを除去）すると、残るのは純粋な「形状」だけになる。これが正規化相互相関（normalized cross-correlation, NCC）である：
\[ \rho(x,y)=\frac{\displaystyle\sum_{u,v}\bigl(f(x{+}u,\,y{+}v)-\bar f_{x,y}\bigr)\bigl(t(u,v)-\bar t\,\bigr)} {\sqrt{\displaystyle\sum_{u,v}\bigl(f(x{+}u,\,y{+}v)-\bar f_{x,y}\bigr)^2}\;\sqrt{\displaystyle\sum_{u,v}\bigl(t(u,v)-\bar t\,\bigr)^2}}, \]
ここで \(\bar f_{x,y}\) は現在のウィンドウの平均、\(\bar t\) はテンプレートの平均である。線形な照明変化に対する不変性は一目で理解できる：ウィンドウの内容を \(a f + b\)（\(a>0\)）に置き換えると、平均減算でオフセット \(b\) が除去され、ゲイン \(a\) は分子と分母の公約因子として約分されるため——\(\rho\) は全く変化しない。
幾何学的な視点：平均を減じたウィンドウとテンプレートをそれぞれ高次元ベクトルと見なすと、NCC は2つのベクトルのなす角の余弦に相当するため、常に \(|\rho|\le 1\) が成り立つ。\(\rho=1\) はウィンドウがテンプレートの正の線形変換である場合に限り成立し、\(\rho=-1\) は白黒反転（極性が反対）に対応する——これはまさに SDK の polarity パラメータで区別される状況である。
実験は導出を完全に裏付けている。サンプル画像 001 から切り出した固定 \(0^\circ\) テンプレートでサンプル画像 003 を画素ごとに走査すると、最も高い応答は左上のほぼ正立したインスタンスに現れ、NCC は 0.827 となる。この値が 1 に近づかないのは、当該インスタンス自体がテンプレートに対して約 \(12^\circ\) の回転ずれを残しているためである（セクション 16.5 の角度探索結果を参照）——角度固定のテンプレートでは「最も良い」インスタンスですら位置を合わせられない。この伏線は セクション 16.3 で回収する。NCC の照明不変性を単独で検証するため、実画像に制御され公開された摂動を加える：このインスタンスの近傍領域のグレースケール値を全体的に 0.5 倍し、当該ステーションの照度が半分に低下した状況を模擬する。結果は一目瞭然で——NCC は 0.827 から 0.827（変化量 0.0001）へと全く変化しなかったのに対し、同じ位置の SSD の二乗平均平方根残差（rms）は 41.2 から 62.3 へと約 1.5 倍に上昇した。明るいインスタンスで 40% の余裕を持たせて検出閾値を較正した場合、判定結果は以下のようになる：
| 指標と閾値 | 明るいインスタンス | 照度 50% のインスタンス |
|---|---|---|
| SSD（rms \(\le 58\)） | 検出（41.2） | 未検出（62.3） |
| NCC（\(\rho \ge 0.80\)） | 検出（0.827） | 検出（0.827） |
ごく普通の照明の減衰でさえ、SSD は良好な部品を「存在しない」と判定してしまう。NCC にはさらに工学的な利点がある：スコアは本来 \([-1,1]\) の範囲に収まり（SDK では百分率に換算される）、「合格点」となる閾値はステーションやカメラが異なってもそのまま流用できる。これに対し SSD の閾値はグレースケールのスケールとノイズレベルに依存するため、カメラを交換するたびに再較正しなければならない。これが産業用マッチングでほぼ例外なく NCC（または次章の形状マッチング）が使用される理由である。
16.2 スコアマップとピーク
各位置の類似度を画像として並べると、スコアマップ（score map）が得られる。図 16.2 は同じシーンの NCC スコアマップと SSD スコアマップである（後者は「明るい = 残差が小さい」として表示）。全解像度で全画像を走査するコストを実演可能な範囲に抑えるため、両方のマップは \(1/2\) 解像度（\(640\times 480\)）で \(115\times 115\) のテンプレートを用いて計算されている（理由は セクション 16.4 で説明する）。
NCC スコアマップ上では5個のコンデンサがそれぞれ円形の応答を生じるが、ピークの高低は明確に分かれる：固定 \(0^\circ\) テンプレートの下で、5つのインスタンスのピーク値は 0.827（正立）から順に 0.750、0.656、0.622、0.516 へと低下する——テンプレートの姿勢からのずれが大きいほど相関は低くなり、ほぼ \(180^\circ\) 反転したインスタンスは 0.5 強の弱い応答しか残さない。これがまさに次節の導入となる：NCC は回転に対処できないのである。SSD マップは同じ話を「残差版」で語っている：正立インスタンスが最も明るい塊であり、残りのインスタンスの輝度は急速に低下する。
スコアマップはさらに深い事実を明らかにする：ピークの鋭さが位置決め能力である。ピークが鋭いほど最適位置の周囲でスコアが速く減衰するため、ノイズがピークの頂点を押しのける余地が小さくなる。逆になだらかな尾根状の応答は、一連の位置が「ほぼ同程度に似ている」ことを意味するため、位置決めは必然的にばらつく。テンプレート内の高周波構造（円頂部のエッジ、極性ストライプ、シルク印刷文字）が豊富なほど、ピークは鋭くなる。最後に、整数画素のピーク頂点は出発点に過ぎない：ピークの近傍領域で、\(x\) 方向と \(y\) 方向のそれぞれについてスコアに3点放線頂点補間（チャプター 2 で導出した \(\delta=(g_{-1}-g_{+1})/(2(g_{-1}-2g_0+g_{+1}))\)）を適用することで、位置をサブ画素まで精密化できる——市販のマッチング処理系が出力する \((404.07, 204.06)\) のような小数座標は、まさにこれによって得られるものである。
16.3 回転と姿勢探索
NCC は照明の問題を解決したが、回転には対処できない。サンプル画像 003 上で固定 \(0^\circ\) テンプレートは、最もよく位置が合っているインスタンスでさえスコアは 0.827 しかなく（そのインスタンス自体が約 \(12^\circ\) 回転している）、ほぼ \(180^\circ\) 反転したインスタンスに至っては 0.5 強しかない——閾値を 0.80 とすると、同じコンデンサが向きを変えただけで存在しないと判定されてしまう。NCC は画素ごとに位置を合わせて比較するため、テンプレートが回転するとエッジの位置がずれ、相関は急速に崩れる。そのため実用的なマッチング処理系は、角度（必要に応じてスケールも）を明示的な探索次元としなければならない：各候補角度ごとに回転させたテンプレートを用意し、逐一比較して最もスコアの高い姿勢を選ぶのである。
SciVision の手法はこのコストを訓練時に移すものである：CreateGreyImageModel が startAngle（開始角度）、angleExtent（角度範囲）、angleStep（刻み幅）に従ってテンプレートを一連のサンプリング姿勢に事前に回転させ、モデルに格納する。コンデンサは供給後に任意の向きを取り得る（サンプル画像にもほぼ \(180^\circ\) 反転したインスタンスが含まれる）ため、本例では全円探索を用いる：\(-180^\circ\) から開始し、範囲 \(360^\circ\)、刻み幅 \(1^\circ\) で、計 360 の姿勢を用意する。探索時には各姿勢ごとにスコアを付け、最適な姿勢の近傍で補間により角度を精密化する。コストは角度の数に比例する——範囲が広く刻み幅が細かいほど、訓練は遅くモデルは大きくなり、マッチングにも時間がかかる。即効性のある見返りとして、固定テンプレート下では 0.827 だった正立インスタンスのスコアは、角度探索を有効にすると 97.58（百分率）まで上昇する——角度が一致すると、相関はすぐに最大値に回復する。
刻み幅はどのように選べばよいか？粗すぎると、真の角度が2つのサンプリング刻みの間にある場合にスコアが低下し位置決めがずれる。細かすぎるのは単なる無駄である。実用的な推定として：回転角 \(\Delta\theta\)（ラジアン）により半径 \(r\) の位置の点が移動する量は約 \(r\,\Delta\theta\) である。テンプレートの最外周での移動量が 1 px を超えないようにすると、\(\Delta\theta \approx 57.3^\circ/r\) となる——本例の円頂部の半径は約 107 px であるため、\(1^\circ\) の刻み幅は外周での移動量約 1.9 px に相当し、「1 px 基準」よりはやや粗いが、探索時のサブ画素角度補間で補われる。
16.4 ピラミッド加速
全解像度での画素ごとの走査コストは膨大である：本例では\((1280-230+1)\times(960-230+1)\)個のウィンドウが存在し、各ウィンドウあたり約\(5.3\times 10^4\)回の乗加算を要するため、合計で約\(4\times 10^{13}\)回の演算となる——単一の角度でさえ許容できない値であり、これがまさにピラミッドと商用マッチャーが存在する理由（前節のスコアマップを\(1/2\)解像度で計算した理由）でもある。解決策は画像ピラミッド（image pyramid）と粗から精への（coarse-to-fine）戦略である：シーンとテンプレートを\(2\times 2\)の平均値で繰り返しダウンサンプリングし（ボックスプレフィルタを適用してから間引く——これは チャプター 10 で強調されたエイリアシング防止ダウンサンプリングである）、最小の最上位層で全画像走査を行う——これはほぼ無料に近い。少数の粗い候補を抽出し、層ごとに高解像度へマッピングして、候補周辺の小さなウィンドウ内でのみ高精度化を行う。
コスト試算：1層下がるごとに、シーンの画素数とテンプレートの面積はそれぞれ\(1/4\)に縮小するため、単層の走査コストは\(1/16\)に縮小する。2層下げた後の最上位層での全走査は、元の作業量の\(1/256\)に過ぎず、候補の高精度化ウィンドウ（本例では\(\pm 8\) px）のコストは九牛一毛である。層を1つ追加するごとに、オーダー単位で性能が向上する。
実験では\(1/2\)解像度（\(640\times 480\)、テンプレートは\(115\times 115\)）を基準として比較した：基準での全画像NCC走査は約\(2.5\times 10^9\)回の演算であり、実測で約10.6 s（最適化されていない/Odビルドであるため、絶対値は大きくマシンの負荷によって変動するが、比率は代表的である）。この基準上に手書きで2段ピラミッドを実装した：最上位層でシーンとテンプレートをさらに2層ダウンサンプリングし（最上位は\(160\times 120\)、テンプレートは\(28\times 28\)）全走査を行い、3つの候補を保持し、それぞれ基準解像度に戻して\(\pm 8\) pxのウィンドウ内で高精度化した。結果：全走査の10.6 sに対して約0.11 s、約100倍の高速化が達成され、見つかったピーク位置は基準の全解像度走査と画素単位で一致——精度は一切損なわれなかった。
層を無限に追加できるだろうか？否。制約は最上位層のテンプレートが依然として識別可能であることである：\(230\times 230\)のコンデンサ円板が数十画素に縮小されても、円形の輪郭と極性のストライプは残るが、それ以上縮小するとストライプとシルク印刷が完全にぼやけてしまい、最上位層から得られる候補は信頼できなくなる。SDKのGetGreyAutoPyramidLevelがこのトレードオフを行ってくれる——本テンプレートに対しては（原画像層を含めて）自動的に5層を提案し、最上位層のテンプレートは約\(14\times 14\)で、円板とストライプは依然として識別可能である。
16.5 SciVisionによる実装
SciVisionのグレースケールマッチングはSCIMV::SciSvGreyMatchが担当し、学習と探索の2段階で行われる：
SCIMV::SciSvGreyMatch gm;
int level = -1;
gm.GetGreyAutoPyramidLevel(tmplImg, mask, &level); // 本例では自動的に5層が提案される
SciMatchModel model;
gm.CreateGreyImageModel(tmplImg, mask, /*pyramidLevel 自動*/ -1,
/*startAngle*/ -180, /*angleExtent*/ 360, /*angleStep*/ 1, &model);
SciPointArray centers; SciVarArray angles, scores;
gm.FindGreyImageModel(sceneImg, searchROI, model,
/*minScore*/ 60, /*matchCount*/ 5, /*overLapRatio*/ 50,
/*startAngle*/ -180, /*angleExtent*/ 360,
/*interpMethod 双線形*/ 1, /*polarity 極性を区別*/ 0,
/*endLevel 原画像層まで高精度化*/ 0, /*clutter*/ 0.0f,
¢ers, &angles, &scores);学習側：pyramidLevelに\(-1\)を渡すとSDKが自動的に層数を選択する（つまりGetGreyAutoPyramidLevelの結果）。startAngle/angleExtent/angleStepは セクション 16.3 で議論した角度サンプリングの3パラメータであり、本例では全周をカバーする。探索側：minScoreは百分制の受け入れ閾値（60点未満の候補は直ちに棄却される）。matchCountは返されるインスタンスの最大数を制限する（本例では5、5つのコンデンサに対応する）。overLapRatioは2つの結果に許容される重複の割合を制御し、多インスタンスの重複除去に使用される。角度区間は学習時と一致する。interpMethod=1は双線形補間を用いてテンプレートを回転させる。polarity=0は明暗の極性が一致することを要求する（白黒反転した「部品」はマッチしない）。endLevel=0は原画像層まで一路高精度化することを意味する——位置決め精度の要求が緩い場合、より高い層で停止すればさらに時間を節約できる。clutterはテンプレート領域外の背景の乱れをペナルティとして課すもので、0は無効を意味する。
実測で遭遇した2つの落とし穴を正直に記録しておく価値がある。1つ目はmaskのROIセマンティクスである。マッチングファミリーはmaskパラメータに対する要求が統一されていない：特徴マッチング、カラーマッチング、輪郭マッチング（SciSvFeatureMatch/SciSvColorMatch/SciSvScaleShapeMatch）のCreate*Modelにはデフォルト構築されたUNDEF ROIを渡さなければならない——全画像をカバーする矩形を渡すと「特徴点が不足している」などのエラーが発生する。グレースケールマッチングは、テンプレート全体をカバーするGenRect1矩形を受け入れることが実測で確認されているが、GenRect1の右下隅は排他端点であることを忘れてはならない——テンプレート全体には\((T,T)\)を渡し、\((T{-}1,T{-}1)\)ではない。同じファミリーの別のマッチャーに切り替えるときは、それがどの種類のmaskを期待しているかをまず確認されたい。2つ目は角度の約束事である。SDKが返す角度は数学的な正方向（反時計回りを正とする）である：サンプル003の正立インスタンスは\(+12.00^\circ\)と報告されるが、これをy軸下向きの画像系の回転描画に直接渡すと向きが誤ってしまうため、符号を反転させて換算する必要がある。本章のmatches.png（図 16.3）で向きが正しい姿勢枠は、まさにこの符号反転後に描画されたものである。
FindGreyImageModelによるサンプル003での探索結果：5つのコンデンサがすべて検出され、十字がサブピクセル中心を、白い枠がそれぞれのマッチ姿勢を示している——ほぼ\(180^\circ\)反転したインスタンスや大角度回転したインスタンスも含まれる。黒い背景上に誤検出はない。
サンプル003でのSDKの実測結果は以下の通りである（角度はSDKの反時計回り正方向）：
| インスタンス | 位置 \((x, y)\) | SDK角度 | スコア |
|---|---|---|---|
| 0（正立） | \((404.07, 204.06)\) | \(+12.00^\circ\) | 97.58 |
| 1 | \((621.79, 714.39)\) | \(-35.26^\circ\) | 92.87 |
| 2（反転） | \((878.39, 241.39)\) | \(+163.00^\circ\) | 91.15 |
| 3 | \((914.14, 794.30)\) | \(+49.00^\circ\) | 90.70 |
| 4 | \((321.08, 649.11)\) | \(-107.66^\circ\) | 89.59 |
5つのコンデンサのスコアはすべて89点以上であり、角度は全周にわたり（\(+163^\circ\)の反転インスタンスを含む）、位置はサブピクセルまで高精度化されている。2つの相互検証が注目に値する。1つ目は、手書きの固定\(0^\circ\)テンプレートを\(1/2\)解像度で走査して得られた最高ピーク（\((404,204)\)にアップサンプリング）が、SDKのインスタンス0の\((404.07,204.06)\)と画素単位で一致——2つの独立した実装が同じ位置を指していることである。2つ目は、同じ正立インスタンスに対して固定角度のNCCは0.827に過ぎなかったのに対し、角度探索を有効にするとSDKは97.58を出力——角度探索によってスコアが回復したことであり、これはまさに セクション 16.3 の論点通りである。同じモデルはサンプル004、005でもそれぞれの5つのコンデンサをすべて検出し（最低スコアはそれぞれ88.9と91.2）、位置と姿勢の変化に対するモデルのロバスト性が確認された。完全な実行可能プロジェクトはcode/template_matching/にある。
産業事例：部品の偏りが角度探索範囲を超えた
ある組立ラインのグレースケールマッチングモデルは、学習時に当時の来料状況に合わせてangleExtentを\(\pm 20^\circ\)に設定し、数ヶ月間安定して稼働していた。その後供給方式が変更され、ワークの実際の偏りが\(\pm 35^\circ\)に達した——探索範囲を超えたインスタンスには一致するテンプレート姿勢が存在せず、マッチスコアは閾値以下に急落し、バッチ全体が見落とされた。最初の対応は「安全のため」範囲を直接全周に拡大することだったが、その結果、学習時間と1回あたりのマッチング時間が明らかに上昇し、さらに悪いことに、姿勢数が倍増したことで類似形状が何らかの角度に衝突する機会が増え、誤検出率が上昇してしまった。最終的な解決策は、上流機構の実際の偏り分布を測定し、その包絡線に余裕を加えて範囲を設定すると同時に、搬送路にガイドを追加して物理的な偏りを範囲内に抑えることであった。教訓：角度探索範囲の役割は物理的な現実をカバーすること——本章のサンプルではコンデンサが反転するため全周を設定するのが妥当であるが、姿勢が制限されるステーションでは、来料の実際の偏りより小さくすることはできず、また「大きければ大きいほど安全」というものでも決してない。
16.6 まとめ
- テンプレートマッチング = 類似度尺度 + 姿勢探索：尺度はどのような外乱にロバストかを決め、探索の次元はどのような姿勢変化を許容できるかを決める。両者は不可欠である。
- SSD/SADは明るさの変化に敏感（ゲイン\(g\)によって\((g-1)^2\)の残差項が生じる）。NCCは平均値を減じて標準偏差で除するため、線形照明に対して厳密に不変——実測で、1つのコンデンサの局所照度を50%に低下させてもNCCは0.827から0.827のままであったのに対し、SSDの残差は1.5倍に増加して見落としが発生した。
- スコアマップのピークの鋭さが位置決め能力である；整数画素の頂点を放物線の頂点補間によりサブピクセルまで高精度化——本例ではSDKが5つのコンデンサをすべてサブピクセルで位置決めし、スコアは89点以上であった。
- NCCには回転不変性がない（固定\(0^\circ\)テンプレートの下で正立インスタンスは0.827に過ぎず、反転インスタンスは0.5強まで低下する）ため、角度を明示的に探索する必要がある。本例では全周を設定してコンデンサの任意の向きをカバーし、探索を有効にすることでスコアが0.827から97.58に上昇した。
- 粗から精へのピラミッドはマッチングを高速化する標準的な手段：最上位層での粗い走査 + 候補の高精度化により、実測で約100倍の高速化が達成され、ピーク位置は全走査と完全に一致した。層数の上限は最上位層のテンプレートが依然として識別可能であること（本例では自動的に5層）。
NCCのロバスト性の境界は線形照明までである：鏡面反射や局所的な影などの非線形な変化、部品が部分的に遮蔽されたりスケールが変化したりする場合、グレースケールマッチングのスコアはすべて低下する——これらのシナリオはエッジベースの形状マッチングで解決される（チャプター 17 参照）。本章の正規化相互相関を積分画像を用いて効率的に計算する方法については、Lewisの古典的な短報(Lewis 1995)を参照されたい。テンプレートマッチングを画像位置合わせというより大きな枠組みで捉えるには、Brownのサーベイ(Brown 1992)を参照されたい。グレースケールマッチングとその高速化戦略についてより体系的な記述は、Stegerらの著作(Steger, Ulrich, と Wiedemann 2018)をさらに参照されたい。