anbul 2004 
proper use 
ecimen, or 
1 could be 
preliminary 
a possible 
1 of simple 
nage. 
ving three 
ngle and a 
plemented 
or not an 
ic/spectral 
probably 
d out; 
nt distinct 
id region 
low); 
1e original 
algorithm 
probably 
has to be 
| vertices 
on of the 
sed in the 
to letters 
o transfer 
to decide 
that is if 
the IDL 
y describe 
we care to 
has firstly 
is a static 
r changes 
means to 
| define a 
> different 
y be read 
structured 
per of the 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
generic values A; and with a row number equal to the 
maximum number of values (terminal and not) that each generic 
value A; can assume. Each generic value A; (first line) 
determines its own column with the possible values it can 
assume. Terminal values are listed in the last line. The matrix is 
a sparse one. 
The program reads the string corresponding to the translation of 
the geometric primitives in characters and it automatically 
generates the Kasami table for that string. This table size 
obviously depends on the stringth length. Strings belong to the 
grammar if S can be found in the last row, first column of the 
Kasami table. 
Used grammar is a context-free one and it is suitable for the 
recognition of different size equilateral triangles: 
  
SAAK [Ay AA:C [B5 BB, 
  
A,>b A, — aB;C B,b 
  
A1 aB,C B;— bB, Cc 
  
  
  
  
  
The terminal values a, b and c represent the following 
primitives : 
Such grammar reduced to the Chomsky Normal Form can 
be defined as follows : 
  
  
  
  
  
S>A3A4 A4>A,C A4—A 
À1—A35A5 As>A,C B,—>B,4B, 
B,—b A,>b B3 Ar>Az3A6 
A¢—>B;C B,>b AAA | ABC 
B;—>B4B, CC 
  
  
  
  
  
  
It has been verified that the program can correctly label as 
‘equilateral triangles’ the ones corresponding to the strings 
W — "abc" and y 7 "aabbcc "; while it labels w — “aba” and 
y="aabbca” as ‘not —equilateral triangles’. 
Obviously, images are never perfect: they are regularly noise 
poisoned; thus we shall use a stochastic grammar. The chosen 
one is regular, as it is equivalent to a HMM, so that we can use 
the corresponding algorithms, which are a well known powerful 
tool. 
An appropriate test image has been created showing a distorted 
version of an equilateral triangle 
  
687 
Fig. 2 Test image of a noisy pattern (equilateral triangle). 
A stochastic regular grammar has been introduced in order to 
describe an equilateral triangle and some other distorted 
versions (Fig. 3): 
S — aA, 
A, — biA, , A, > bA, 
As > cy, A > C, 
The object has been subdivided in subpatterns, corresponding to 
the string xX = abc». 
Let’s suppose to know probability to get each string x: 
p(a b; cı) = 0.01 
p(a b, cı) = 0.3 
p(a b; c5) 7 0.19 
p(a bs c;) = 0.5 
From probability theory ensues that the probabilities of the 
production rules are: 
pi 
p» — 0.032 
; 7 0.968 
Pa = 0.31 
ps = 0.69 
The hidden states of the corresponding model are: A,, A; and T. 
The parameters of the corresponding HMM are: 
x (Ai) 7 1l, 5 (A5) 2 0, n (T) 7 0; 
eai(@) = 1, eaa (by) 7 0.032, eA» (b5) = 0.968, er (c:) = 0.31, 
er (c:) = 0.69; 
à aa” la amp =l 
Cy Cy 
  
Fig. 3 An equilateral triangle and some distorted versions. 
The “Forward” algorithm shall give us probability of a sequence 
of observations, for instance of the string x 7 a b; c»: 
f(a b. c5) 70.67. 
Viterbi's algorithm, in the turn, lets associate to such a 
sequence, the related most probable asset of otherwise hidden 
states (the parse of the string): 
A, A» T. 
3. FORECASTS 
The ab,c, string of the previously described example, may 
belong also to the classe of square triangles.