Chamfer Matching

Last updated： June 7, 2013.

【参考文献】

H. Barrow, J. Tenenbaum, R. Bolles and H. Wolf, “Parametric correspondence and chamfer matching: Two new techniques for image matching”, In Int’l Joint Conf. of Artif. Intel., pp. 659–663, 1977.
J. Canny, “A Computational Approach To Edge Detection”, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 8, no. 6, pp. 679-714, Nov. 1986.
A. Rosenfeld and J.L. Pfaltz, “Sequential Operations in Digital Picture Processing”, J. Assoc. Comput. Mach., vol. 13, pp. 471-494, 1966.

概要
Chamfer Matchingは入力画像とテンプレート画像間のエッジの相違度に基づいてマッチングをおこなう手法です．エッジ情報をもとにマッチングするため，非常に高速な検出が可能です．
アルゴリズムの流れ
まず，入力画像とテンプレート画像からエッジ検出をおこないます．次に，入力画像から生成したエッジ画像に対し距離変換処理をおこない距離変換画像を作成します．このようにして得られた，距離変換画像とテンプレート画像のエッジ画像の相違度に基づいてマッチングをおこないます．
エッジ検出（Canny edge detector）
入力画像とテンプレート画像からのエッジ検出は下記のように5つのStepから構成されます．
■Step1:入力画像fをガウシアンフィルタgで平滑化
　■f * g
■Step2:平滑化画像の縦横の微分値を計算
　■縦方向の微分値fyと横方向の微分値fxを計算
■Step3:勾配強度と勾配方向の算出
　■勾配強度　　　　　　　　　　　　　　　　　　　　　勾配方向

■Step4:勾配強度の極大画素を抽出
　■g(x,y)が勾配方向の画素に対して極大である場合エッジ候補とする
■Step5:しきい値処理
　■g(x,y)>Thigh:エッジ画素とする
　■g(x,y)<Tlow:エッジ画素としない
　■Tlow<=g(x,y)<=Thigh:近傍にエッジ画素があるときのみエッジ画素とする
距離変換画像
距離変換画像とは，エッジ画像の各画素から最近傍のエッジ点までの距離を画素値とした画像です．下の例では，エッジに近くなるほど黒くなり，エッジから遠くなるほど白くなります．
相違度マッチング
■相違度
テンプレート画像TEと入力距離変換画像IDTとの相違度は次式により算出します．h,wは画像の縦と横のサイズです．相違度Sが最小になる位置をテンプレートの位置として決定します．

■探索
Chamfer Matchingでは距離変換画像の画素値がエッジ画素までの距離値になっていることを利用し，全探索することなく効率的に解を探索します．下記のように，相違度の勾配方向と勾配強度を用いて相違度を最小化する方向と変化量を推定します．

■x方向の微分値:

■y方向の微分値:

■勾配強度:

■勾配方向: