濃淡画像における高速パタンマッチングアルゴリズムに関する研究

点击翻译按钮获取中文摘要

研究代表者は,以前にk個の誤りを許す近似ストリングマッチングに対してサンプリングの手法を用いて高速化に成功した.そのアルゴリズムの平均計算時間は,パタン長をm,テキスト長をnとしてO(kn/m)logm)である.この方法は,2次元に拡張可能であり,パタンの面積をm^2,テキストの面積をn^2とするとき,平均時間はO(kn^2/m^2)logm)である.以上の研究では文字列に対するアルゴリズムを扱っているが,本研究では,濃淡値をとるパタンとテキストを扱った.具体的には濃淡値の値域を〔0,R〕とし,許される誤差,すなわちピクセルにおける絶対値の和をkR以内として1次元で平均O(kn/m)logm)時間,2次元では平均O(kn^2/m^2)logm)時間の高速アルゴリズムを開発した.ここで用いた手法は,濃淡値を3値に量子化し,文字列のマッチングにおけるサンプリング法に帰着させることである.応用例として,ビデオ画像における動く物体の追跡を行なった.毎秒10コマ程度の512×512ピクセルの画像において64×64ピクセルの物体の追跡に成功した.なお,濃淡値域Rを256とした。今後,量子化レベルを上げることによって計算時間がどう変化するか,また、マッチングの信頼度がどのように変化するかを調べることが課題である.また,色彩情報を取り入れることによりマッチングの信頼度を上げることも今後の課題である.この研究は,コンピュータヴィジョンの基礎部分として重要であり,産業応用も期待される.