| 講演名 | 1997/12/18 単調連続2次元ワープ問題のマルコフモデル表現と動的計画法による解法 内田 誠一, 迫江 博昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 筆者らが検討している単調連続2次元ワープは, 2画像間の最適一致を実現する画素単位のマッピングの一種であり, 1)パターンの位相を近似的に保存するワープを構成できる, 2)画像全体での2次元的な最適性が保証される動的計画法(DP)を最適一致の探索法として用いる, という特徴を持つ. 単調連続2次元ワープは多くの画像マッチング問題への有効性が期待されるが, 最適解を求めるための計算量が非常に多いという問題があった. 本報告では, より少ない計算量で最適解を求めるための, 単調連続2次元ワープ問題の新たなモデルを提案する. このモデルはleft-to-rightな有限状態オートマトン(FSA)にコストが付随した, いわゆる単純マルコフ決定過程であり, その最適経路問題として単調連続2次元ワープ問題が表現される. このようなモデルは従来解法でも用いられていたが, 本報告で与えるモデルの方が可能な状態遷移の数が大幅に少ないので, より少ない計算量で最適解が求まるアルゴリズムが構成できる. またこのモデル上での準最適解アルゴリズムについても考察し, 従来の準最適解アルゴリズムよりも最適化能力の点で有利であることを示す. |
| 抄録(英) | The authors have proposed a monotonic and continuous two-dimensional warping method based on dynamic programming (DP). It can achieve the optimal pel-to-pel correspondence between two images with preserving topological features. This is useful property for many pattern matching problems. However, a huge amount of computational resources is required to obtain the optimal warping. In this paper, we propose a new representation of the two-dimensional warping problem. It is described as a Markovian-type decision process based on left-to-right, FSA. The number of allowed transitions is significantly fewer than that of previous representation. Therefore, the complexity of DP-based algorithm is remarkably reduced. An sub-optimal algorithm based on pruning technique is also investigated. |
| キーワード(和) | 単調連続2次元ワープ / パターンマッチング / 動的計画法 / マルコフ決定過程 / 計算量 |
| キーワード(英) | two-dimensional warping / pattern matching / dynamic programming / deformable model |
| 資料番号 | PRMU97-174 |
| 発行日 |
| 研究会情報 | |
| 研究会 | PRMU |
|---|---|
| 開催期間 | 1997/12/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Pattern Recognition and Media Understanding (PRMU) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 単調連続2次元ワープ問題のマルコフモデル表現と動的計画法による解法 |
| サブタイトル（和） | |
| タイトル（英） | A Markov Model Formulation of Two-Dimensional Warping Problem and Its Solution by Dynamic Programming |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 単調連続2次元ワープ / two-dimensional warping |
| キーワード(2)（和/英） | パターンマッチング / pattern matching |
| キーワード(3)（和/英） | 動的計画法 / dynamic programming |
| キーワード(4)（和/英） | マルコフ決定過程 / deformable model |
| キーワード(5)（和/英） | 計算量 |
| 第 1 著者 氏名（和/英） | 内田 誠一 / Seiichi UCHIDA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学研究科 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 迫江 博昭 / Hiroaki SAKOE |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究科 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 1997/12/18 |
| 資料番号 | PRMU97-174 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 458 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |