概要
画像中から既知の小画像を探すテンプレートマッチング（Q.56〜59）と、二値画像を領域ごとに 分ける連結成分ラベリング（Q.60）を解説します。どちらも画像中を走査して対応関係を探しますが、 前者は画素値の類似度、後者は前景画素の接続を扱います。
テンプレートマッチング
入力画像上でテンプレートと同じ大きさの窓を移動し、各位置で評価値を計算します。
| 問題 | 評価値 | 選ぶ位置 | 性質 |
|---|---|---|---|
| Q.56 SSD | 差の二乗和 | 最小 | 大きな差へ強いペナルティを与える |
| Q.57 SAD | 差の絶対値和 | 最小 | 計算が単純 |
| Q.58 NCC | 正規化相互相関 | 最大 | 明るさの倍率変化に比較的強い |
| Q.59 ZNCC | 平均を引いた正規化相互相関 | 最大 | 明るさの加算変化にも強い |
for (let y = 0; y <= imageHeight - templateHeight; y++) {
for (let x = 0; x <= imageWidth - templateWidth; x++) {
const score = compareAt(x, y);
// 最良の位置と評価値を更新する
}
}SSDとSADは元画像とテンプレートの明るさが変わると評価が悪化します。NCCはベクトルの長さで 正規化し、ZNCCはさらに平均値を引くことで、模様の対応へ注目します。
連結成分ラベリング（Q.60）
二値画像の前景画素を走査し、上下左右でつながる画素へ同じラベルを付けます。異なる仮ラベルが 同じ領域だと判明した場合は、同値関係を記録して後から統合します。
最終的なラベルを色へ変換すると、独立した領域を視覚的に確認できます。斜め方向も同じ領域として 扱う8近傍版は、後続の実装で扱います。
使い分け
テンプレートマッチングは「この見た目がどこにあるか」、ラベリングは「前景がいくつの領域に 分かれているか」を求めます。前者は対象の見本がある場合、後者は二値化後の物体数や面積を 調べる前処理として利用できます。
類似度指標を選ぶ
テンプレートと切り出し領域の画素差を比較する代表的な方法は次のとおりです。
| 指標 | 特徴 |
|---|---|
| SAD | 絶対差の和。軽量で外れ値の影響がSSDより小さい |
| SSD | 差の二乗和。大きな差を強く罰する |
| NCC | 内積を大きさで正規化し、全体の明るさの尺度差に比較的強い |
| ZNCC | 平均も引くため、明るさの加算変化にも強い |
NCC系では分母が0になる単色領域を処理する必要があります。また、テンプレートが入力画像より大きい 場合を先に拒否すると、走査範囲の負値や配列外参照を防げます。総当たりの計算量は探索位置数と テンプレート面積の積になるため、テンプレートを大きくすると急速に重くなります。
ラベリングを実装する2つの方法
幅優先探索・深さ優先探索では、未訪問の前景画素を見つけるたびに近傍をたどります。理解しやすい 一方、大きな領域ではキューのサイズに注意が必要です。2パス法では仮ラベルを付け、Union-Findで 同値なラベルを統合します。
4近傍と8近傍では斜めに接する画素を同一物体とみなすかが変わります。小さな対角線パターンを テスト画像にすると、意図した接続規則になっているかを確認できます。
