ul 2004 
ices by 
jection 
ng the 
by the 
got the 
ate and 
hat the 
  
  
COMPARISON OF PARSING TECHNIQUES FOR THE SYNTACTIC PATTERN 
RECOGNITION OF SIMPLE SHAPES 
T.Bellone, E. Borgogno, G. Comoglio 
DIGET, Politecnico, Corso Duca degli Abruzzi, 24, Torino, Italy 
tamara.bellone, enrico.borgogno, giuliano.comoglio@polito.it 
Commission II, WG III/8 
KEY WORDS: algorithms, vision, pattern, recognition, understanding 
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 context- 
free 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. 
1. INTRODUCTION 
Language is based upon blending of discrete parts (phonemes, 
morphemes) we may suppose what really happens as one 
speaks, that is a passage from a starting point to a universe in 
progress of more and more complicated structures, and this 
process may be thought of as unique. However, as Minsky says, 
the same kind of process takes place when we try to understand 
a visual experience. 
The meaning of a sentence relies upon the single words and 
upon their position. A sequence of words is seen as 
grammatically correct only when words appear in the 
framework of a certain scheme, however bias between sense and 
non-sense is only partially grammatical (grammar does not 
entirely control language). 
Linguistic assemblages are shaped upon forms and rules. For a 
number of scholars, linguistic forms, at least the most common 
types, arise less from a sort of inner device proper to the 
language, than from the very way one thinks: in other words the 
special way our brain works must be taken into account. So 
vision and speaking are both based upon principles not quite 
different. 
This is why some present procedures of Geomatics may be 
referred to logical and symbolic structures proper for 
Mathematical Logics and for Linguistics. Some improvements 
in GIS, Digital Photogrammetry and Remote Sensing are 
referred to as Computer Vision, Image Processing, Machine 
Learning, which are also linked to developments of Artificial 
Intelligence, which in turn is based upon Logics, Mathematical 
logics, Linguistics and Mathematical Linguistics. 
683 
An easy case of this cultural melting is Pattern Recognition, as 
used in the framework of Image Processing: it 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). Also, parsing is a topic 
proper of Linguistics, which has been borrowed from cognitive 
sciences. 
Syntactic Pattern Recognition consists of three major steps: 
® preprocessing, which improves the quality of an image, 
e.g. filtering, enhancement, etc. 
e pattern representation, which segments the picture and 
assigns the segments to the parts in the model 
® syntax analysis, which recognizes the picture according to 
the syntactic model: once a grammar has been defined, some 
type of recognition device is required, the application of such a 
recognizer is called Parsing. 
The decision whether or not the representation belongs to the 
class of patterns described by the given grammar or syntax (is 
syntactically correct) is made by a “parser”. 
Parsing is then the syntax analysis: this is an analogy between 
the hierarchical (treelike) structure of patterns and the syntax of 
language. 
Patterns are built up by sub-patterns in various ways of 
composition, just sentences are built up by words and sub- 
patterns are built up by concatenating primitives (features) just 
words by concatenating characters. 
Also, a texture is considered to be defined by subpatterns that 
occur repeteadly according to a set of rules.