| 講演名 | 1998/2/19 2次元CYK法による線図形画像の直接構造解析アルゴリズムの改良 川下 直人, 片山 喜規, 迫江 博昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 2次元CYK法とは, 文脈自由文法(CFG)でモデル化された線図形を画像中から前処理無しに直接検出し, 接続統合するCYK型の解析手法である.その基本構造はΝ×Ν入力画像に対してΜ個の記号でモデル化された線図形を検出する際にΟ(Ν^6)の計算量とΟ(ΜΝ^4)の記憶量を必要とする.本稿では, 記号駆動型の終点位置制約や書換え規則の右辺進行度を状態変数表現する事による書換え規則適用判定の効率化, 背景領域の分離, 削除と前景領域のリスト化, CYK解析ケーブルの記号間共有化等のアルゴリズム改良によって, 計算量・記憶量の低減を図る.アルゴリズムの高速化比較実験により上記のアルゴリズム改良の有効性を検討する. |
| 抄録(英) | We proposed a CYK based two-dimensional parsing method for directly detecting a line pattern in a noisy picture according to a context free grammar (CFG) model. The time and spatial complexities of its basic algorithm amount to Ο(Ν^6) and Ο(ΜΝ^4), respectively, for Ν×Ν input image and Μ symbols Model. In this paper we investigate several improvements for efficiency enhancements. They include (1) the analyzed data limitation by removing background area from the image, (2) the symbol driven limitations for line tracing and rule application, (3) the shared parsing table among symbols. Significant efficiency improvement of the proposed algorithm was observed through experiments. |
| キーワード(和) | 線図形解析 / CFGモデル / 2次元CYK法 |
| キーワード(英) | Line pattern analysis / CFG modeling / Two-dimensional CYK parsing |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | PRMU |
|---|---|
| 開催期間 | 1998/2/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Pattern Recognition and Media Understanding (PRMU) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2次元CYK法による線図形画像の直接構造解析アルゴリズムの改良 |
| サブタイトル（和） | |
| タイトル（英） | An Efficiency Improvement of the Line Pattern Parsing Algorithm Based on Two-dimensional CYK Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 線図形解析 / Line pattern analysis |
| キーワード(2)（和/英） | CFGモデル / CFG modeling |
| キーワード(3)（和/英） | 2次元CYK法 / Two-dimensional CYK parsing |
| 第 1 著者 氏名（和/英） | 川下 直人 / Naoto KAWASHITA |
| 第 1 著者 所属（和/英） | 西日本新聞社 Nishinippon Shimbun |
| 第 2 著者 氏名（和/英） | 片山 喜規 / Yoshinori KATAYAMA |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究科 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 迫江 博昭 / Hiroaki SAKOE |
| 第 3 著者 所属（和/英） | 九州大学大学院システム情報科学研究科 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 1998/2/19 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 558 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |