A Structural Method of Scene Analysis

Zdenek Zdr&hal

Czech Technical University, Faculty of E.E., Karlovo n8m.13, 121 35 Prague 2, Czechoslovakia

In this paper a method of scene analysis and pattern recognition is outlined. Relational structures are employed as a tool for describing scones and objects. Des.criptive primitives are extracted from the TV image together with their interrelations and the recognition is defined as a task of matching this structural description against models. The method completely reported in lJ] , has been developed for the vision subsystem of the GOALEM robot ~). For comparison see [1] where another structural techniques are reviewed.

'fhe problem can be split into two parts :

(A) 'fhe image of the scene to be recognized is converted into a relational structure called image structure IS. A model is stored as a model structure MS, Then we construct a function f which assigns to each element of IS an element of MS and evaluate the match. Usually the absolute match cannot be found since the real IS differs from the ideal one. Basically, the match can be assessed either in terms of the number of relations being preserved or in terms of the number of relations being different. Only the former case will be discussed in this paper although also the latter one yields interesting results, If MS is a substructure of the IS i.e. a monomorphism exists from MS to IS then the object described by MS is a part of the scene, All the monomorphism& should be found and indicated,

(U) Let an ensemble of model structures be given, I~ving solved the subproblem (A) we have to find the MS giving the best match over the whole ensemble. Since the essence of all the problem lies in the matching algorithm our attention will be focused on part (A).

Def. 1. A vocabulary Vis a set of ordered pairs (P,~ where p is a predicate name and n is the number of its arguments, c:J

Def. 2. A relational structure S over a given vocabulary V is an ordered pair S=(A,F) where A is a set called the carrier and F is a function which assigns to each n-argument predicate nwne from V a subset of An (n-ary relation). Symbol (~ 1 , ··· ,~ stands for an

ordered n-tuple of elements of A.

c:J

For the sake of transparency we will demonstrate the principles of the method considering only unary relations (properties) and binary ones. Their predicate names will be pi and rj, respectively, i 1 j = 1,2, ··· · In order to quantify how the fUnction f preserves the relations we define the following criterion

Def, J. Let MS "' (A,F) , IS = (B,G) be relational structures over a vocabulary V where A = {a 1 , ··· ,~J· B = { b 1 , ··· ,bN} are carriers, let f : A- B be a bijective function, let w(p ) ) o, w(r ) ) 0 be weights of properties and bin~ relations, respectively. Let us denote :

Criterion C is defined as c:J

We assume both carriers have the same number of elements, If this is not the case we add olements to the smaller carrier which do not participate in any relation, The optimal function t* is to be found which maximizes the criterion C i,e. C(MS,IS,t·) · max C(MS,IS,f) · The value f

of C(MS,IS,t·) is used for solVing the subproblem (B),

There are Nl "Various functions f : A - B. We cannot test all of them because of the combinatorial increase of time. It would be convenient if only the functions promising high values of the criterion C are checked, We will estimate the chances of each function in terms of an auxiliary criterion ~whose evaluation i· a1ch simpler,

Pet. 4. Let the assumptions of Def. ). hold with the exception of the conditions (vii),(x) which are omitted, The auxiliary criterion Cis defined as

where ~ 1 · ~ 2 differs fro· the original due to the conditions (vii),(x).

The expression xst'" [ l!' 2 (as,rj ,f) ,w(rj) + +[ c 1 <as,pi,f>.w<pi> depends only on the partial assignment bt ~ f(as) and thus can be calculated regardless of the rest of the fUnction, Let us arrange the numbers xst into_

a square matrix X, We calculate the value of C as a sum of elements Xst taking just one element from each column and row according to the bijective function f, Each Xst evaluates the local match of elements as and bt without considering the rest of both structures and expresses the highest possible contribution of the partial assignment bt a f(as) to the main criterion C, Hence the following theorem can be proven :

Theorem 1. For any given f the inequality C(MS,IS,f) ~ C(US,IS,f) holds, D

The algorithm for matching the structures is based on this theorem.

An outline of the algorithm· Let us arrange the· functions f 1 , f 2 , ··· , f!fl in accordance with the decreasing values of C i.e. if i;>j then C(MS,IS,fi) ~C(MS,IS,fj). Since the Cis calculated from the matrix X this task is a problem of linear programming (assignment problem) and, therefore, efficient methods are available,

In the i-th step of our algorithm C(MS,IS,fi) is evaluated. A variable qi is defined aa : ~ a C(MS 1 IS 1 f 1 ) 1 qi., max\ C(MS,IS,f 1 ),qi_ 1 ), if. 1. From Theorem 1 follows :

After the i-th step all the functions for which C(MS 1 IS,fj)~qi are eliminated since they cannot become tne op~imal function t* , It follows immedi!tely from the inequality C(MS,IS,fj)~ C(US,IS,fj) <~·The matching process is finished if ~(MS,IS,fi+ 1 )~qi,

Obviously, we do not generate the complete decreasing sequence of C since we need only the next function in each step,

~· Structures IS .. (A,F) , MS · <B,G) are given in Fig,1,

The vocabulary V consists of properties p 1 ,p 2 , p) and binary relations r 1 ,r 2 ,r 3 ,r 4 , Weights w(p 1 ) · w(p 2 ) · w(p 3 ) · w(r 1 ) · 1, w(r 2 ) · w(r 3 ) · w(r 4 ) calculated; a 0,5 are given, The matrix X is

The evaluation of x 21 is shown in Fig.2,

The underlined relations contribute to the value x 21 ·

Step 1 :

Step 2 :

C(MS,IS,f 2 ) · 16, q 2 · 16, C(MS,IS,f 3 )~q 2 , the optimal function f* · t 2 has been found and thus the .atching process is finished· For demonstration all the values of C and the evaluated ones of c are shown in Fig · .).

In our implementation of the algorithm · improvements speeding up the convergence are included. Moreover, monomorphisma can be found by means of the following theorem :

Theorepa 2. Let MS · ( B,G) IS · (A,F), A · fa 1 , .... ,~), B · {b 1 , ····· ,bN) , N~M, be given, let f be an injective function f : A-. B. Let us define the identical function g : B-.B, i.e. g(bj)· bj for each bj. If C(MS,MS,g) · C(MS,IS,f) then f is a 110nomorphism fro· MS to IS. D

It would be very difficult to compare our results with thole of [1) because of the differencies in computers, programming lancuagea etc. Just for brief information, our algorithm waa run on an ICL 290.) and took tens of seconds for structures with aa many aa 20 elements. We expect we can slightly speed it up by !~roving the linear programming subroutine

which is being prepared.