A Program For Geometrical Pattern Recognition Based On The Linguistic Method Of The Description And Analysis Of Geometrical Structures

Introduction

The program is a part of the software of the industrial pattern recognition sys tem presented by T.Vamos and Z. Vas s y in their papers [1,7J. The program variant running at present on the CDC-3300 comput e r is used for the recognition of two -dimensional patterns, like those shown on r'ig.l.

It is typical f or the patterns that they consist of line segments, arcs and - because of the noise of the perceiving d e vice - s mall indefinite elements. The relations between subpatterns, the econo­ mical construction of grammars and the program implementation.

The terminal symbols of the grammar correspond to the primitives of the patterns, while the non-terminal symbols correspond to the subpatterns. Th e non­ t e rminal symbols like the terminal ones lluv e quantitative characteri s tic s , too. Th e r ewriting rules have th e following form:

Left-side non-terminal symbol-> / ( Fi­ nite set of right-side terminal and non-terminal symbols)(Relations between right-side symbols or betwe e n thei r quantitative attributes)(Definition of the quantitative attributes of the l e ft- s ide non-terminal symbol by the quantitative attributes of the right-side s ymbols)(Indication of the symmetrical quantitative attributes)*j

The geometrical relation s permitted in the system and the operation s to obtain the quantitative attributes of the non­ t e rminal symbols are described separately and interpreted in the sy s t e m ~ b be~~~~tc program segments . Their set can b e conveniently extended as much as the system develops.

Figure 3 describes a characteristic sc rew portion represented in Fig.l. Here the terminal s ymbol s co n si~L o f lower case letters, and th e non-Lr·rrninu1 <> ll t':', o f' c apital letters. Thr~ quuntitut.lvt· attributes of the lcft-sld~ uymbolu ur c den o ted by unsubscripted letter s , those of the right-side symbols by subscripted letters; the subscript indicates the or­ dinal number of the corre s po nding right­ side symbol in the rule. The rul e s are numbered.

·'

The output of the pr ogram in the cou r se o f its ope rat ion as a n indepe nd e nt program (e .g. to test new grammars) is the printing of the name s of the patterns recognized by the program on the input list as well as that of the description of the complete analysi s tree . By using the program in system ClJ only th e end results are transmitted through the common data field for other programs.

H No te: For all terminal symbols the quantitative a ttribut es A and B (co - ordi nates of " ' 1" f the ends) are functionally identical - l e t us call them symmetr1ca . or convenience . By analogy, there can b e d e fined "symmetri ca l" quant i tat1v ': at~ributes for non-t e rminal symbols, too . Th e definition or thP symme tr ic al attribute s enable s u s t o reduc e the nt1mber of the r ewrit in~ r ules a nd allows f' 0 r t h e a r b i t r a r i n e s ,; p r o c e ·~ d i n p: i 11 L II r· t! i ,. ,. c L i n n o f' t II e c o II L o u r ~' ·

Th e pr ogram is written in FORTRAN wit h the use o f the LIDI-72 list proces­ s in g s ystem developed in the Comput er and Automation Institute, Hun!arian Academy of ::c i e nc es [5,6J LIDI-72 is written in FOR'!' HAN.

The System LIDI-72 is applicable for the direct representation of arbitrary directed &raphs in the computer. The node may have a name, with a node of the graph some information can be stored in the form of a linear sequence of any len!th, con­ sisting of inte!er numbers, and the number of branches may be arbitrary. Fig.4 re­ presents the graph node by a LIDI-72 list element.

The LIDI-72 system has an advanced program system to operate on lists: the input of information with a tree structure, described in parentheses and some other specific forms, the modification of any graphs, the conditional or uncondi~ional carrying out of operations specified by the user on a certain sub-graph, etc.

The organization of the grammatical analysis

In working with certain limited class of patterns, the grammar describing these patterns is an always used and unchanging information and is organized as a part of the permanent data structure. Fig.5a shows th e structure of the grammar and Fig.5b details the structure of a rul e . Appe nd i x contains the detailed description of the ~ Destruction of the grammar.

'

a/

LS

i

LSR

LGA

S

- ~eft-side 2lmbol

- number of the rule

- ~ist of right-side ~ymbols and .!!_elations

- 'ist for Generation of the quantitative ~ttributes of the left-side symbol

- §.J mbol

NR

- Name of geometrical Relation

NAO

d.a.p. - description of actu~l parameters i.n.q.a.- indication of number of quantitative attributes

i. s. a.

- Name of Assignment Operation

indication of symmetrical quantitative attributes

Fig.5.

Geometrical relations and operati o n s for assignment of value to quantitative attributes are interpreted as FORTRAN lo­ gical funtions and subroutin e s respe c ti­ vely. The grammatical rules are giving only the names of relations and as s ignment operations, further the descriptio n o f actual parameters. The names of relati o n s and assignment operations are collectei in two lists analogous with each other, belonging to the permanent data structure. Fig.6 shows the organization of one of them. The so-called switching index is used for the activation of the respective program segment at the time of the running of the program.

elements recognized by the program) ~'e written in the ~ist of the Generated quantitative Attribute Sets-(LGAS) branching into sublists~ corresponding to syntactic types (Fig.7). These sublists are created and existing only for the running time of the linguistic analysis program.

LNR - ~ist of !ames of geometrical Relations

NR - !arne of geometrical Relation

i

switching index

Fig.6

The analyzer - the program of linguistic analysis - consists of the following subroutines: subroutine of the analysis according to the given rule, subroutine of the synthesis according to the given rule, subroutines for the or­ ganization of the work of program segments checking the geometrical relations and realizing of assignment operations, strategy subroutine for the organization of the order of the analysis according to grammatical rules and a set of auxiliary subroutines.

The algorithm of analysis can be characterized as analysis by synthesis. The grammatical rules are numbered in an increasing hierarchical order,

"bottom-up" (in the increasing complexity of pattern elements to be described). The algorithm consists of information pro­ cessing concerning the actual object on basis of grammatical rules considered in an increasing order of their numbers,of trials to synthesize the left-side symbol, considering every possible com­ bination of the already synthe~iz~d symbols (the syntactic type of which is identical with the types given on the right-side) and checking the fulfilment of the geometrical relations required by the given rule. In the course of cross -recursion between the rules, such a "linear" way of the algorithm is violated, "loops" appear, its general trend, however, does not change.

It must be noted that the greater part of the algorithm is made of the subroutines of the analysis according to a given grammatical rule on basis of which it is easy to organize any other st rategy of the order of the uses of grammatical rules.

The quantitative attributes of the symbols synthesized during the working of the algorithm (i.e. of the pattern

LGAS - ~ist of ~enerated quantitative Attribute Sets

S ~ymbol (Syntactical type of picture element)

lq - List of quantitative attributes of elements with syntactical type S for actual input picture

Fig.7

The run of the program begins with the permanent data structure putting into the memory followed by the reading of the input list and its preprocessing, involving the location of the quantita­ tive attributes of the primitives in the three basic sublists (line, arc, unde­ fine~ of the List of Generated quantita­ tive Attribute Sets intended for infor­ mation storage about the actual pattern.

Fig.8 shows how the organization of the running of the program is imagined. Here the lists are drawn up by circular blocks and the program parts by rectangular ones. The transmission of in­ formation about the actual object is shown by double directed lines and the transmission of information controlling the analysis is shown by simple directed lines .. By running the program-analyzer no modification ta~es place on the permanent data structure (Grammar, List of Names of geometrical Relations /LNR/, List-of Names of Assignment Operation; /LNAO/), therefore-we call it-permanent; the in­ formation stored in it is used to control the analysis of information about the actual object. During the analysis a lot of consecutive structural transformations are carried out on the List of Generated Attribute Sets.

There are two stages in the use of the program:

1/ Creation of a perman ent data structure (Grammar, LNR, LNAO) and pro­ gramming of geometrical relations and assignment operations. This part of the system can be changed and extended without limit during the definition of the set of tasks to be completed with the help of the program. Meanwhile the ana­ lyzer program i.s left unchanged. 'li1e permanent data structure must be described in LIDI-72 input language (in parenthetical form) on cards. A very short program or­ ganizes the input of the permanent data structure in the memory of the computer with the help of the LIDI-72 input program. Durin~ the testine of the data structure th is s hort program calls at the end of its run Lhu program-analyzer which performs tht· analysis of an input li st. After su rv e y of the r esult s of the carrying out of' the analysis corrections can be mad e in the Jescription of the data s tructure . The cur r ecL data structure is transferred on a Ji s c in the form of binary information .

2/ Use of th e program for pattern rrco~niLion (Fi g .B). Fo r this purpos e the Jata st ructur e i s dir ectl y transferred f'rom the dis c t o the memory o f the computer before the beginning of the run of the program-analyzer.

Appendix

Grammar

The rules o f the grammar can be s ubdivided i nto two groups:

• 1 / Rule s wh e re there are only termi­ nal symbols (e .g . rule 0 ln Fig.3) on the right side;

2/ Rules where there arc only non­ terminal symbo l s on the ri~hL s ide (e.g . r ul es 1-3 in Fig.3).

The rules of the first ~roup are pro ­ p:ramm e d as preprocessinr. of input list bccau s f~ Ltli ~ i~. a commo u bu~is to ull r:rammar·:; intc ro , stint~ u: · .. 'I'll<' rulo· " o f' ttl!'

second group are contained in the Grammar which is a part of the permanent data structure for the actual set of tasks. Such a subdivision simplifies the algo­ rithm to a great extent as it is dealing with non-terminal symbols only.

Numbering of grammatical rul es: th e rul er; ar e numbered such a way that e very s ymbol uppcur s firnt as a l e fL- si d e one. Exceptions are only recursions acros s the rule s (which are ulso permitted in the Grammar). Rules with identical left-side symbols get different numbers and enter the grammar a s separate rule s .

The structure of a rul e is s hown on Fig.5b.

~ac h symbol in the list of right- si de symbols gets a number. The numb e ring is comp letely arbitrary, but nece ss ary for th e unambiguous description of geometric relations b e tween symbols, b e caus e th e same rul e may contain several symbol s o f identi ca l s yntactic type. Fo r e very s ymbol, there i s a list of names o f r e ­ lation:;, whi c h th e s ymbol is bound to s atisfy with r e spect to th e prec ee ding right-side symbols of the rul e . For every relation in th e rul e is given th e d esc ription of actual parameter s o f the r el ation. The following order is accepted for the description of parameters: every parameter is described by a pair of integers th e fir s t of which i s th e order ~umb e r of th~ r~ght-side symbol which mu st sati s fy this relation, whil e th~ second is the number of that quantitative attribute of this symbol, the value of whi ch is th e actual parameter of the r e lati o n.

explained in the introduction, it looks as f :J llows:

In the LI DI-'12 input l·Wf~uage tho· name:.; of the nodes of graph are give n by an alph a bet ic string, ancl their attril>uto: :;, i.e . e l ements of linear li s t by in teger s . The attributes are enclos e d betwe e n the sign s (= =) and are delimited by commas and comme nts.

Le t be defined in th e system the following geometrical relations:

notati o ns in the meta-language: names: = · t EQ, NEQ

and th e following assignme nt operation : n o tation in the me ta-language: name: ASSIGN

All List of right- si d e ~ymbol s and Re l at i o ns -have th e name LSR, and ull .!.!,i s t :; for Generation of quantitat i v e attribute s hav e th e name LGA.

r' i g . 9 shows t h e s t r u c t u r e of th e rule for ARC2. The description of the rule in the input language LlUl Wlll be as follows:

C ARC2( =l=)(LSR ( ARC (=l=), ARC(=2=)

C (EQ(=l,l,2,1=),

C NEQ(=l, 2 , 2 ,2=), NEQ(=l,4, 2 ,4=),

C OBTANG(=l,3,2,3=))),

C LGA(=5, 0=)

C (ASSIGN(=l,l,2,2 2,1,4,2,4,1,1=)))

C is a sign for continuation.