単調連続2次元ワープ問題のマルコフモデル表現と動的計画法による解法

概要

論文の詳細を見る
筆者らが検討している単調連続2次元ワープは, 2画像間の最適一致を実現する画素単位のマッピングの一種であり, 1)パターンの位相を近似的に保存するワープを構成できる, 2)画像全体での2次元的な最適性が保証される動的計画法(DP)を最適一致の探索法として用いる, という特徴を持つ. 単調連続2次元ワープは多くの画像マッチング問題への有効性が期待されるが, 最適解を求めるための計算量が非常に多いという問題があった. 本報告では, より少ない計算量で最適解を求めるための, 単調連続2次元ワープ問題の新たなモデルを提案する. このモデルはleft-to-rightな有限状態オートマトン(FSA)にコストが付随した, いわゆる単純マルコフ決定過程であり, その最適経路問題として単調連続2次元ワープ問題が表現される. このようなモデルは従来解法でも用いられていたが, 本報告で与えるモデルの方が可能な状態遷移の数が大幅に少ないので, より少ない計算量で最適解が求まるアルゴリズムが構成できる. またこのモデル上での準最適解アルゴリズムについても考察し, 従来の準最適解アルゴリズムよりも最適化能力の点で有利であることを示す.
1997-12-18