Presentation | 1998/2/19 An Efficiency Improvement of the Line Pattern Parsing Algorithm Based on Two-dimensional CYK Method Naoto KAWASHITA, Yoshinori KATAYAMA, Hiroaki SAKOE, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Line pattern analysis / CFG modeling / Two-dimensional CYK parsing |
Paper # | |
Date of Issue |
Conference Information | |
Committee | PRMU |
---|---|
Conference Date | 1998/2/19(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Pattern Recognition and Media Understanding (PRMU) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | An Efficiency Improvement of the Line Pattern Parsing Algorithm Based on Two-dimensional CYK Method |
Sub Title (in English) | |
Keyword(1) | Line pattern analysis |
Keyword(2) | CFG modeling |
Keyword(3) | Two-dimensional CYK parsing |
1st Author's Name | Naoto KAWASHITA |
1st Author's Affiliation | Nishinippon Shimbun() |
2nd Author's Name | Yoshinori KATAYAMA |
2nd Author's Affiliation | Graduate School of Information Science and Electrical Engineering, Kyushu University |
3rd Author's Name | Hiroaki SAKOE |
3rd Author's Affiliation | Graduate School of Information Science and Electrical Engineering, Kyushu University |
Date | 1998/2/19 |
Paper # | |
Volume (vol) | vol.97 |
Number (no) | 558 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |