KL 展開による正規化相互相関テンプレートマッチングの高速化

足立 一秀 (9551004)


テンプレートマッチングの高速なアルゴリズムである 残差逐次検定法 (SSDA) は、 これまで限られた類似度評価尺度にしか適用されていなかった。 本研究では、明度変化に対し安定な類似度評価尺度である 正規化相互相関を用いたテンプレートマッチングに対し、 2つの手法を提案する。

まず、正規化相互相関によるテンプレートマッチングを ユークリッド距離での最近点探索に帰着することで、 正規化相互相関に対して SSDA を適用する手法を提案する。 次に、正規直交基底への投影変換が ユークリッド距離を保存することを利用して、 正確に候補削減を行ない、SSDA を効率化する手法を提案する。 この最適な投影軸は部分画像集合の統計的な性質を反映しており、 KL 展開によって求められる。

また、従来の正規化相互相関テンプレートマッチングと 2つの提案手法の計算量を比較考察し、 実験によって高速化の程度を確認した。 その結果、SSDA は正規化相互相関においても高速であること、 また多数のテンプレートが重複した範囲を探索する場合、 2つめの提案手法を組み合わせてさらに高速化できることが確認された。