Comparison of parsing techniques for the syntactic pattern recognition of simple shapes

Abstract: Syntactic Pattern Recognition is a procedure, widely used in Cartography and Remote Sensing, that trusts upon matching of sections of maps and/or images or 3D models with archetypes or objects (parsers). Parsing is a topic proper of Linguistics that can be considered as a basic step (syntax analysis) of the Syntactic Pattern Recognition procedure. Considering a possible application of such technique to the automatic interpretation of imaged shapes, preliminary tests have been carried out onto simple geometric forms. An appropriate test image showing different geometric shapes has therefore been created. Parsing techniques have been applied as decision modules of the whole recognition path which is completed by some preliminary image processing steps. A number of algorithms are available for Parsing, for the needs of specific grammars: although not suited for any grammars, tabular methods help save time, as the Kasami method, remarkably simple to use: it works well in the case of contextfree grammars, as reduced to the so- called Chomsky’s normal form. Languages used to describe noisy and distorted patterns are often ambiguous: one string or pattern can be generated by more than one language, so patterns belonging to different classes may have the same description, but with different probabilities of occurrence. Different approaches have been proposed: when a noisy pattern has two or more structural descriptions, it is proper to use stochastic grammars. For the above said test it has been used a normal context free grammar over simple figures, that is a well designed specimen. We also test a badly designed specimen using from the start a stochastic finite state grammar, which can be assimilated to a finite state Markov process: a final comparison of the results shall try to show the differences between those approaches.