Share Email Print

Proceedings Paper

VLSI Architectures For Syntactic Image Analysis
Author(s): Y. P. Chiang; K. S. Fu
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Earley's algorithm has been commonly used for the parsing of general context-free languages and error-correcting parsing in syntactic pattern recognition. The time complexity for parsing is 0(n3). In this paper we present a parallel Earley's recognition algorithm in terms of "x*" operation. By restricting the input context-free grammar to be X-free, we are able to implement this parallel algorithm on a triangular shape VLSI array. This system has an efficient way of moving data to the right place at the right time. Simulation results show that this system can recognize a string with length n in 2n+1 system time. We also present an error-correcting recognition algorithm. The parallel error-correcting recognition algorithm has also been im-plemented on a triangular VLSI array. This array recognizes an erroneous string length n in time 2n+1 and gives the correct error count. Applications of the proposed VLSI architectures to image analysis are illus-trated by examples.

Paper Details

Date Published: 9 January 1984
PDF: 8 pages
Proc. SPIE 0435, Architectures and Algorithms for Digital Image Processing, (9 January 1984); doi: 10.1117/12.936997
Show Author Affiliations
Y. P. Chiang, Washington State University (United States)
K. S. Fu, Purdue University (United States)

Published in SPIE Proceedings Vol. 0435:
Architectures and Algorithms for Digital Image Processing
Per-Erik Danielsson; Andre J. Oosterlinck, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?