単調連続2次元DPアルゴリズムの階層化

勝股 充  鈴木 尚  徳田 恵一  北村 正  

誌名
電子情報通信学会論文誌 D   Vol.J85-D2   No.9   pp.1382-1391
発行日: 2002/09/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: 画像処理,画像パターン認識
キーワード: 
2次元ワープ,  パターンマッチング,  動的計画法,  階層化,  反転防止,  

本文: PDF(2.5MB)>>
論文を購入




あらまし: 
画像マッチングの手法である単調連続2次元DPアルゴリズムの改良手法について述べる.従来の2次元DPによる2次元画像マッチングでは,直接的な探索に比べれば大きく計算量を削減できる.しかし,現実的な時間で計算を終えるためには,ビームサーチを行う必要があり,現実的な計算時間のビーム径では,最適解からのずれが大きくなるという問題があった.本論文では,まず,ワープ時に起こる画素の位置関係の反転を完全に回避することのできる手法を提案した上で,既存のアルゴリズムを階層化することにより,現実的なビーム径で性能改善を図る.階層化は,計算量の増加につながるが,ビーム径を従来法に比べてかなり小さくでき,結果的に計算量の削減を実現できることが実験により示された.また,反転問題では従来法では完全に反転を防止できていなかったが,本手法により完全に反転を防止することができるようになった.