SUPP: Understanding Moving Picture Patterns Based on Linguistic Knowledge

1. INTRODUCTION

It is a matter of course that image and natural language understanding are very important aspects of artificial intelligence researches · The research works in both areas have remarka­ bly increased in number in recent years , but the results obtained in one area have not been sufficiently used for the research works in the other area . There is much difference of the present knowledge level between image , espe­ cially real world image , and natural language understanding: the knowledge level for the for­ mer is low while one for the latter is high.

In the last decade or more we have worked at constructing a system named SUPP(System for Un­ derstanding Picture Patterns) in order to raise the level of image-understanding up to the linguistic knowledge level and to fill the gap between the works in the two areas. This paper is an overview of SUPP[l]-[7]. The theory devel­ oped there agrees with much of Minsky's frames idea(B]. SUPP can be viewed as a specialization of frames idea in the domain of linguistic understanding of image sequence · It has the following two characteristics:

1. A systematic and exhaustive investigation of the meaning of image is made from the linguistic viewpoint.
2. A theoretical basis is given for dealing

The research reported herein was part by the Japanese Ministry under Grant in Aid for Scientific supported in of Education Research, No.

320709.

with the structure and the meaning of change, be it motion, deformation or so forth, occuring in image sequences.

2. CONCEPTUAL TAXONOMY OF JAPANESE VERBS

When an image or image sequence is given , in­ finite number of static or dynamic events can generally be observed in it . Suppose that the meaning of each event is described in natural language, the description sentences will amount to infinite number. An ordinary sentence is de­ composed into simple sentences , each of which is governed syntactically and semantically by a verb . Since there are only finite number of verbs in each language , meanings of infinite number of events are roughly divided into mean­ ings of those verbs and their interrelations. An object in the real world which is identified by a verb is called "matter." It arises acompa­ nying things, events and attributes , which are called "constituents," so its concept can be regarded as the concept of dynamic or static relation among constituents.

After due consideration about correspondence with the real world , the concepts of approxi­ mately 5,000 Japanese verbs were classified according to an algorithm . The concepts are divided into two large classes : "e.imple matter concept" and "non-simple matter concept." The former can not be decomposed into elementary matter concepts while the latter can be decom­ posed. Th~y can further be classified according to their structural patterns and semantic con­ tents. The results are described in (21 and [~.

3. THE KNOWLEDGE SYSTEM

The knowledge system contains a visual , a con­ ceptual, a linguistic and a thesaurus component.

3.1 T_h.~ _ _v_~s~-~ !_lnd_ the Conceptual Component

The visual component contains models of primi­ tive pictures and syntactic rules among them · An example of model is shown in Fig. 4-(b). The rules are applied to picture pattern pairs , which Minsky called "before-after" frame-pairs. The conceptual component contains conceptual features, concepts and networks of concepts · A matter concept is expressed by [ V : c1c2 · · ·c1 d1(E1)d 2(E2)···dm(Em)l where each ci denotes a feature of matter itself and corresponds to a syntactic rule mentioned above · Each dj( ) denotes the case or role of a constituent and must be filled by specific instance or concept of constituent. Features Ej ( = ej 1ej 2···ejn ) specify the conditions its ass1gnment must meet . Networks are constructed among similar matter concepts.

3.2 Jhe Linguistic and the Thesaurus Component

The linguistic component consists of diction­ aries for the production of Japanese and English sentences. The thesaurus component con­ tains all the classified concepts in Chap. 2 and supports to develop other components.

The knowledge system is discussed in detail in [1] , [ 5 J, [ 6] and [ 7).

4. THE UNDERSTANDING PROCESS

The process of understanding a sequence of two­ dimensional line drawings ( handwriting is allowed) is described · The overall system is indicated in Fig. 1.

Fig.'3 Organization of the system

4.1 Primitive Picture Recognition and Syntactic Analysis

The picture pattern reader is a curve follower that traces line segments by octagonal scanning. The recognizer is based on Evans's matching program[9] for graph-like line drawings but is improved to handle noisy ones.

The syntactic analyzer A decomposes the complex picture , in which two or more primitive pic­ tures may intersect or touch each other , and recognizes them according to Gestalt criteria. The syntactic analyzer B performs Boolean oper­ ations on quantized primitive pictures to check such a relation as "MAN INSIDE HOUSE." The syn­ tactic analyzer C performs numerical operations on the data such as coordinates and transfor­ mational coefficients of primitive pictures. The programs mentioned above are described in detail in [4] and [5].

4.2 Semantic Analyzer and Inference

The semantic analyzer detects the meaning of matter-centred change in picture pattern pairs by top-down analysis · Suppose that matter [ V(s,oa):clc2···Clds(es)d0 a(e0 a)] is directed by the Inference. The analyzer assigns the role of s to one of the primitive pictures , say Ps after checking whether Ps meets es· It assigns the role of oa to another primitive picture P 0 a in the same way. Then it analyzes each ci by calling a correspondent sub-program in the syn­ tactic analyzer B or C. If all the analyses end in success, the meaning of V(s,oa) is detected. The present Inference makes inferences about all the similar concepts in the network in depth-first order , directing each matter concept at a node to the semantic analyzer. Finally , the synthesizer produces Japanese and English simple sentences.

5. EXPERIMENTS

Almost all the programs were written in FORTRAN to run under the OSII/VS of the FACOM 230-38S medium scale computer at the Department of Information Science and Systems Engineering at Oita University. Experimental results [4]-[7] are shown in Fig. 2-5.

(a) Preprocessed

1. Pattern matching

input picture

[p7:q 5],[p9:ql4),[pl9:q6],(p8: q4),[p6:ql5),

(plO:ql~), (pl8: q7 ' (p5 : q2) ' (pll:ql2),

[pl 7:qeJ,[pl2:q9]

(pl6:qlO),(pl2:q9),(pl5:qll)

2. Transformation and similarity Translation: (524.4, 483.7)! scaling : 2.173 times, rotation : 2.290 rad an, reflection : in Y-axis. Similarity : 0. 718(~1 )

Fig. 4-Recognition of iibird[l)"

t=t 4

t=t 5

(a) Input sequence t=to * OT0K0(4) GA IE NO UCHI NI ITA.

------- t=tl * OTOK0(4) GA IE KARA DETA.

*THE MAN[4) WAS IN THE HOUSE.

* THE MAN[4) WENT OUT OF THE HOUSE.

t=t2 * OTOK0(4) GA KURUMA NI NOTTA.

-------

* THE MAN[4) RODE INTO THE CAR.

t=t 3 * KURUMA GA HASHITTA.

* THE CAR RAN.

t=t4 * KURUMA GA KI NI BUTSUKATTA.

* THE CAR COLLIDED AGAINST THE TREE.

t=t5 TORI(l) GA KI KARA SATTA.

• THE BIRD[l) LEFT THE TREE. * OTOK0(3) GA KURUMA KARA ORITA.

• THE MAN[3) ALIGHTED FROM THE CAR.

(b) Output sentences 1. Description of t=t 0 is for the picture pattern at t=t 0 · 2. Description of t=ti (i~l) is for the picture pattern pair at t=ti and ti-l· 3. The * marks were assigned by man.

Fig. 5-Understanding of a picture pattern sequence

(b) The model of "bird[l)"

6. CONCLUSIONS

A system has been surveyed that understands moving picture patterns linguistically. Badler's approach[lO) basically agrees with ours in handling verb-centred events but differs in that SUPP is based on a systematic analysis of almost all the verbs used for everyday Japanese while he notes only motion verbs in English. By SUPP image understanding research has come clos­ er to natural language understanding research.

ACKNOWLEDGEMENT

The author started to develop SUPP some ten years ago when he was at Kyushu University. The author wishes to express his gratitude co Prof. T.Tamati of Kyushu University for kind guidance and material support.