チュートリアル
●マッチング
画像のマッチングとは，２枚の画像の照合，あるいは１枚の画像とそのモデルの間の
照合を行なうことである．照合をとるレベルにより，画素データレベルの
マッチングと，画像から抽出した特徴のレベルにおけるマッチングに分けられる．
後者では，特徴記述間の関係を照合する必要があり，画像理解の方法にも
関連している．
◎画素データレベルでのマッチング
画像の位置合わせ(registration)問題では，２枚の画像が平行移動で重なる関係にある
場合には，画素データレベルでのマッチングを行える．主な方法には，相関法，
残差逐次検定法がある．
(１)相関法
図のように，Ｗ（ｉ，ｊ） を大きさ Ｌ×Ｌ の画像とし
Ｓ（ｉ，ｊ）を大きさＭ×Ｍの画像とする．画像Ｗが画像Ｓのある部分に対応
していることを知るために，
を，１≦ｍ≦Ｌ−Ｍ＋１，１≦ｎ≦Ｌ−Ｍ＋１ の範囲で計算する．このＲ（ｍ，ｎ）
が最大値を取る（ｍ，ｎ）により画像ＳとＷの関係が得られる．この計算は直接
計算せずにフーリエ変換を用いることもできる．相関法の問題点は
(α)ノイズに敏感で，ノイズがあるとピークが不鮮明になること，
(β)計算コストが大きいこと
である．ノイズの対策には，信号理論的立場から改善を行なう方法が提案されている．
(２)残差逐次検定法
この方法は，Barnea and Silverman により提案され，ＳＳＤＡ(Sequential Similarity
Detection Algorithm)と呼ばれている．誤差の累積である残差には，
を用いる．このとき，ウィンドウ内の全画素について残差を計算してしまわず，
一定の順序でサンプリングを行ない，残差の中間結果を調べる．
残差が早く増加していれば．閾値Ｔを越えた時点で
処理を打ち切る．Ｃのように残差の増加が遅い場合にはマッチングの可能性が高い．
この方法は，相関法に比べて計算時間を大幅に改善することができる．
閾値の与え方には固定閾値を与える方法と，調べるサンプル点数の
増加に従って単調増加関数を与える方法がある．また，ウィンドウ内で最後まで誤差を
加算した場合の残差に基づいて，閾値を自動的に決める方法も提案されている．
このほかに，始めから全テンプレートを適用せずに部分テンプレートを適用し，
その結果に基づいて全テンプレートを用いる２段階テンプレートマッチング法や，
最も解像度の高い画像上でマッチングをせず，あらかじめ粗い画像を用意して
探索効率を改善する方法などがある．
今回の応募に関してはテンプレートの背景部分は相関演算，残差計算から除外
する必要があることにご留意下さい．
またカラー画像であることから色ヒストグラムを利用した粗密探索を適用する
など上記の相関演算，残差計算以外に様々な手法が適用できます．皆様の
面白いアイデアを期待しています．
コンテストのホームページに戻る
問い合わせ先
prmucont@cs.titech.ac.jp