International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
  
A stochastic finite state automaton is a five tuple SA- (X, Q, M, 
T , F) where Z is a finite set of input symbols for the strings 
(the alphabet) , Q is a finite set of internal states, M is a 
mapping of £X into the set of nxn stochastic state transition 
matrices, 77 is the n-dimensional initial state distribution vector 
and F is a finite set of final states. 
Indeed the generation process from a stochastic finite state 
grammar can be assimilated to a finite state Markov process. 
Let Gs = (Vn, Vr, Ps, S) be a stochastic grammar, we can 
construct a stochastic automaton SA = (Z, Q, M, % ), accepting 
languages generated by Gg : T(SA) 
The alphabet 2 is equal to the set of terminal symbols V ; the 
state set Q is the union of the set of non terminals Vy and the 
states T and R, state of termination and of rejection 
respectively; T is a row vector with the component equal to 1 
in the position of state S, the other components equal to 0; the 
state transition. matrices M are formed on the basis of the 
stochastic productions; finally a n vector m; represents the final 
state. 
Let's consider the stochastic finite state grammar G = (Vy, Vy, 
Ps , S), where: 
Vu =(S, A), V1 = (a, b) and Ps : 
S aA pl 
A -»aA p-70.8 
A b pz02 
We have, according to the above described procedure: E = (a, 
b), Q = (S, A, T, R), m =(1000),andF=T. 
We can construct the transition state matrices M(a) and M(b): 
S-A T S A R 
S 01 0 0 S 0 0 l 
M(a)=A 0 08 0 0.2 M(b)=A 0 0 0.2 0.8 
T.0: 050 1 T. 10 .0..0 1 
KO 070 1 RO 00 I 
According to the Markov chains theory, we can calculate for 
example the probability of the string x = aab. 
M (aab) =m, M? (a) M (b) Tt; 
0.08 0 02710 0. 0 ] 0 
0 0.664 0 036 0 O 02 O8 |0 
M(aab)-|]| 0 0 0 - 0.16 
0 099 11pe 0 1 | 
Qo o o IT» o o 1 0 
If we calculate the probability of the string by means of forward 
algorithm of HMMS, we obtain the same result. 
Indeed, we can consider the hidden states: A and T and the 
following parameters: 
n(A)7 l, (T) 2 0; 
ea(@)=1,er(b)=1; 
aya = 0.8, apr = 0.2, arr = 0.8; 
fa (a) = (A) ea(a) = 1; 
fr (a) = X(T) er (a ) =0; 
fa (a,a) = 0.8, fr (a,a) = 0; 
fa (a,a,b) = 0, fr (a,a,b) = 0.16; 
f (a,a,b) = fa (a,a,b) + f; (a,a,b) = 0.16. 
If we calculate the probability of the string x= aab taking into 
account how it is generated: 
686 
S — aA — aaA aab 
we obtain the same result: 
p(x) = p(aab) = 1x 0.8 x 0.2 = 0.16. 
2.3 Application test 
We mean to test a badly designed specimen either by proper use 
of a normal grammar after a pre-treatment of the specimen, or 
using from the start a stochastic grammar. 
First, in order to evaluate how well such approach could be 
applied to the automatic interpretation of images preliminary 
tests have been carried onto simple geometric images. 
It is here shown an example addressed to draft a possible 
operational path for Parsing based pattern recognition of simple 
geometric entities. 
   
Fig. 1 Test image and polygon grouped pixels image. 
An appropriate test image has been created showing three 
different geometric figures: a rectangle, a scalene triangle and a 
equilateral triangle. The goal is to verify if the implemented 
grammar could correctly decide if one figure is or not an 
equilateral triangle. 
The recognition process goes on in the following way: 
> a preliminary identification, based on radiometric/spectral 
discriminants, of the pixels of the image probably 
belonging to the searched objects is firstly carried out; 
> the selected pixels are then grouped in different distinct 
geometric entities using neighbourhood and region 
growing criteria (different colors in the image below); 
> foreach entity a frame window is clipped from the original 
image and a Fórstner filtering and thresholding algorithm 
is applied in order to select pixels most probably 
representing the vertices of the figure which has to be 
recognized; 
> assuming that figures are closed polygons vertices 
coordinates are used to define length and direction of the 
connecting lines. These are the geometric primitives used in the 
parsing grammar. A simple translation from numbers to letters 
(defined when grammar has been defined) allow to transfer 
information to the parsing engine algorithm which has to decide 
if the object belongs or not to the defined grammar, that is if 
that polygon is or not an equilateral triangle. 
All these steps have been implemented using the IDL 
programming language. We do not intended to deeply describe 
well known image processing algorithms. Otherwise, we care to 
briefly describe how the parsing algorithm works. It has firstly 
to be structured, defining the deciding grammar. This is a static 
part of the program; in fact, once defined, it never changes 
during the recognizing process. Changing grammar means to 
change the program text. In the future we intend to define a 
standard text file the user can fill off-line to define the different 
grammars he wants to use. Such file could be directly be read 
by the program while executing. Grammar has been structured 
as a matrix, with a column number equal to the number of the 
Interna. 
generic 
maximt 
value . 
determi 
assume. 
a sparse 
The pro 
the gec 
generat 
obvious 
gramme 
Kasami 
Used g 
recogni 
The te 
primitiv 
Such gr: 
be defin 
S>A;A 
A, A3 
B,b 
A,B4C 
B,—>B,F 
  
It has b 
‘equilate 
w= "ab 
y 7 "aab 
Obvious 
poisonec 
one is re 
the corre 
tool. 
An appr 
version (