ncy of 
Iracy. 
A new 
of CIPA 
qualita' 
iplinare,. 
erritorio, 
onero. 
Metodi di 
. Saluzzo 
walita nei 
Analisi 
mite un 
nferenza 
-Arnold, 
ork,. 
mation — 
SOME EXAMPLES OF TABULAR ALGORITHMS IN SYNTACTIC PATTERN RECOGNITION 
T.Bellone*,E. Borgogno *, G. Comoglio * 
*DIGET, Politecnico di Torino, Torino, Italy 
tamara.bellone@polito.it, enrico.borgogno@polito.it, giuliano.comoglio@polito.it 
Commission VI, Working Group 3 
KEY WORDS: Pattern Recognition, Image understanding, Algorithms 
ABSTRACT: 
Image understanding is a very important step in the course of data analysis in GIS. Syntactic Pattern Recognition of 
models is a process, as used in Cartography and Remote Sensing, which makes possible the matching of parts of maps, 
of images and 3D models with archetypes and patterns (parsers). The main item of the entire process is the so-called 
Parsing, a device used in Linguistics, successively used in Cognition Disciplines. Simply, it must help decide whether a 
data string (a phrase) can be a part of an existing pattern (language). 
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. 
1. Foreword 
The so-called computer science revolution has also taken 
place in the area of geodetic sciences, which eventually 
are playing a key role in it (Geomatics). 
Even common people know that many mental preocesses 
are based upon evaluation of contrast and difference: this 
is, for instance, the art of seeing, and generally a good 
approach in all cognitive sciences, also in Linguistics. 
Language, indeed, is based upon blending of discrete 
parts (phonemes, morphemes). Also, vision and speaking 
are 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 
Logic and Linguistics. Some improvements in GIS and 
Digital Photogrammetry are referred to as Computer 
Vision, Image Processing, Image Understanding, 
Machine Learning, which are linked to developments of 
Artificial Intelligence. 
An easy case of this cultural melting is Syntactic Pattern 
Recognition: 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; Artificial Intelligence in turn is 
based upon Logic and Linguistics (Mathematical Logic 
and Mathematical Linguistics). 
A Syntactic Pattern Recognition system consists with 
three parts: pre-processing, pattern description and syntax 
analysis. 
Pre-processing includes pattern encoding and 
approximation, filtering, restoration and enhancement. 
The pattern representation procedure consists of pattern 
segmentation and feature (primitive) extraction, in order 
to represent a pattern in terms of its sub-patterns and 
43 
pattern primitives: each sub-pattern is identified by a 
given set of pattern primitives. 
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 (Sester, 1990). 
Parsing adaption to the GIS context can be thought for 
selecting reference shapes from numerical cartography or 
raster geocoded images. Phrases are cartographic objects 
and language is the set of rules which define these objects 
satisfy or not selecting criteria. 
A double use of Parsing is possible in the framework of 
GIS: both at the generation stage, and for the process of 
query and data analysis. 
The shape reconnaisance by parsing is of evident interest 
for: 
> map production, implementation and updating 
through automatic extraction of shapes from raster 
data; 
» editing of existing maps (as association of codes to 
not-still-coded shapes or perceiving of difference 
between a closed polygon and an open line in order 
to close it); 
» query purposes, aimed to the extraction of raster 
features or not-coded shapes from the database; an 
ample variety of questions may be posed, as one 
deals with new geometrical features which can be 
classified as recursive shapes according to a 
reference pattern.