VLSI Architectures For Syntactic Image Analysis

Y. P. Chiang; K. S. Fu

doi:10.1117/12.936997

9 January 1984 VLSI Architectures For Syntactic Image Analysis

Y. P. Chiang, K. S. Fu

Proceedings Volume 0435, Architectures and Algorithms for Digital Image Processing; (1984) https://doi.org/10.1117/12.936997
Event: 27th Annual Technical Symposium, 1983, San Diego, United States

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(n³). 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.

Citation Download Citation

Y. P. Chiang and K. S. Fu "VLSI Architectures For Syntactic Image Analysis", Proc. SPIE 0435, Architectures and Algorithms for Digital Image Processing, (9 January 1984); https://doi.org/10.1117/12.936997

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available