Toward Generation of 3-Dimensional Models of Objects Using 2-Dimensional Figures and Explanations in Language

TOWARD GENERATION OF .3-DIMENTIONAL MODELS OF OBJECTS USING 12-DIMENSIONAL FIGURES AND .EXPLANATIONS IN LANGUAGE

Norihiro Abe, Rumihide Itho and Saburo Tsuji

Department of Control Engineering Faculty of Engineering Science Osaka ~univercity Toyonaka Osaka Japan

ABSTRACT

We propose a system that can build a 3-dimensional model of an object with cylinder-like-body, given several 2-dimensional views and . explanations _on its substructures. The goal of our research - is to build a qualitative' model on- relations ; between the object parts rathetr than a precise -3-D geometrical model. The system needs· to match , linguistic expressions to -, representation obtained from images. Also finding' of ~orrespondence between different views is important. Sometimes, it it difficult to get a complete model from an limited number of observations and explanatibns, the system, can ask the user ambiguous points in terms of 1labelsl attached to the rsubpa:rts. Several · difficulties found in experimentation: are discussed.

INTRODUCTION

There! is the close relation between recognition of objects and learning of .them. We human beings, build the object model by seeing: them. There have been many researches that aim at autonomous building of .2 or 3-dimensional models [1-'3], but most of· them are either unnatural or difficult to use without · much knowledge ·on their representation. In order to deal with a large set of objects, much effort of the user is needed. Oshima and Shirai [ 4] ipropo~>ed a model learning system which uses multiple images observed · from different : positions. But image features ·. ar.e not always s~fficient to get a reasonable; model because the system is difficult to klllow which portions Lof an image are essential to the model creation.

Anotlier way for a computer learn a · model of ran object is to understand the structure· of the object ·given in .natural language [5]. We have built ari experimental system [ 6, 7] which builds a model of a new object using an object model · with similar features. This method was found uset1ul to'rlearning a 2-di.!m.ensional iobject without any rotational movements. ' The method was applied 1to a plot ,understanding r system [8] using ·pictorial rand linguistic knowledges. But .we cannot apply it to imagery in which :rotational movements often occur. For these reasons, a; ·new method is proposed that uses verbal explanations along with several figures : of an object. Explanation makes easier for the system · to judge what portions of the fgiven figures are important to. a model building tiecause named iportions are often impOJitant parts.( fhis also ;serves to resolve uncertainty by ireferring with a name to; a known' part of the object. >However ·With .only . explanation, it· is quite :difficult to specify detailed relation's and shape of the ·object. Figures ;can contribute i to solve this probl~m since image analysis techniques 'have extracted them.

SYSTEM ORGANIZATION

Fig.l Tshows the: organization of this·· system. It consists mainly of rthree parts; : language interpreter, imagei,-language ;. communication part r and model gener;1tor. Image-language communication p~rt ext11acts significant' features like a region or branch m order to find identities. i This feature extraction is done by ' the same program ;·as used in [6-8]. The result of the program are converted into frame structure as that of the linguistic interpreter is a same form. Model generator merges two frame representations into one frame which specifies the detailed model ~f' an object. F?r _the fir~t imagei and: explanation, one stmple hypothetic .model 1s created and then it is modified by giving additional images' and explanations. There are many. ; d.i~fic~lt problems here. First, there may be some ambigmtle~> m corres.pondence between features and their names. Second is difficulty in determining 3-dimensional structure. It is difficult to· decide if a patter in image is of 2-dimension (a kind cif pattern .on a r surface) or 3-dimension (a protrusive rstructure).r To know the precise· shape of such a structure needs several observations from · different view ·points. Then this system, mentioned a.s previously, makes a few hypotheses on a shape of an object body and its subparts; as a first approximation, · it assumes that the object. conJsists of a cylinder-like-body, l an~ that any subfigures _ in the object are patterns on 1ts surface execept substructures. clearly known ·as protrusive from the body. Of cause these assumptions will often fails in building the true model because several patterns may. be really, protrusi\1e struc.tures. These rwrong as&u~ptlo?­ cannot be :' revised until at least one anothen VIew IS given, Fig.! System organization But this cannot be easily . solved even if several other vieWS\ are. shown, as it is ;_ difficult ·to find true correspondences . among parts .in different views of' t~e object. Conventional 'meth(l)ds ~sed in c.omput~r: _ gra~htcs have solved this '. problem by usmg precise 3-dimenstonal geometrical descriptions. i However such ari model building method is too rigorous to ma~e the _t~e. system unavailable. That is, ·the methods lack m f~ex1b1hty; The description method used in this system JUst avails of relations amongr subparts wi~ their rnames. and vario~s properties.: The assumption that ! a m.am body IS cylinder-like is just used only for mfernng a subpart locatibn when another observation of it is given from a . different view point.· Since this inference is based on a very coarse modelin-g, the predicted map of : subparts locatibns may roften be , too vague to find unique correspondence 'among the,m. I~ .i~ an .advant~g~ of the system that it has a posstbthty m ·. deciding . the correspondence by using various parts attnbutes. together with their .predicted relatiens. When some parts are left undecidable or mnknown ·after all input figures ha~e been shown, the . system asks the! user: what they a.re. Thts .man-machine communication method Will be abbreviated in this paper.

An input sentence is converted into a tree Structure. Next the word groups for shapes, colors and positional relations are extracted from the syntactic tree, and. the system regards . these noun groups as labels for some substructures of an object. The internal expression are generated based on the analyzed parsing tree.

LANGNAGE-IMAGE COMMUNICATION PART

The internal representation obtained by the image processing programs ;is also of a frame style. Since · two frame representations, linguistic and pictorial one, describe the same object; they should . be completely matched each other, but differences in several points cause matching to fail in finding correspondence of them. A unique correspondence is not always ' expected even if consistent pairings of slot values are got through so called graph: matching method. There have been studied many matching methods for inductive learning[9] . Our matching method for mating two descriptions is different from them in the points that it at first checks just attributes to look for a clue to get good . correspondences, then excludes contradictory combinations by the test of consistence in locational constraint.

KNOWLEDGE AND REPRESENTA:TION IN FIGURES

This 'system at. first has. no priori knowledge on a structure of an object to be modeled. Any generic model of objects is given, then features and structures of. the object are not obtained until they are taught through learnfng. For example, see Fig.2 and 4. Given ithis .figure, alLregions such as Bl , REI, RAl, LPl, and all relations between them such that RPl is included in REl and that REl is to the left of LPl (from an observer) are extracted. Positional 'relations are described quite corsely as shown in the figure ; . locations of subparts are described In terms of subregion. denoted using U, M~ D, L, C, R symboles. For example REl is located at LU of Bl , and RPl .at RC of REI. Here note that the descriptions of locations are different f rom that in explanations, where the relations are expressed .relatively like ~·A is on .the top of B". A translation from an observer centered framework into an object centered one is necessary to find correspondence between two representations.

MATHCING BETWEEN THE LINGUISTIC AND PICTORIAL FRAME

Let assume that six rsentences in Fig.3 are given along with the figure .' Each sentence is analyzed and converted into an internal form, which is' then stored in the frame structures .. Note that several parts not do not appear, which may, be extracted from figures, or stated later.

Now let consider how we find correspondence between a linguistic and image expression. Given · the sentences shown in Fig.3, the matcher can get complete pairs between labels and parts. If some of sentences are deleted from the explanation, ambiguities .on correspondence between labels and parts are left. For example·, if sentence (16) is deleted, then two possibilities, are left concerning ARMs. When. sentence .· (5) is abbreviated then there · are left 6' ambiguities (note that sentence (5) is told) . As w~. have many knowledges . on shapes or properties of objects, we are apt to forget . to state familiar portions to us, but it causes computer .to fall in serious confusion. When' no unique · labelings are attained, the system retains all of · them and tries to exclude contradictory correspondences by. checking the rest of images and explanations. For example, the ambiguity :can be resolved on ARMs in the first case, if the correspondence between LA2 and LAl in Fig.4 and 5 is found by the graph matcher and an explanation on arms is given :Concerning the figure 5. If nothing is elucidated to the figure , the ambiguity is left ·after the end of learning process unless it is resolved anywhere in learning. In suoh a case the system cannot help asking the user such ambiguous points.

GRAPH MATCHING BETWEEN CONSECUTIVE FIGURES

Let consider a case two figures are given as shown in Fig.4 .and 5. Besides labelihg process,· now assuming that e~ch part has a, label given in FigA, the system must fmd .correspondence · between them in order to make clear uncertain. points concerning identification of r~lationsh.ip among subp~rts. Matching the description of Ftg.4 agamst that of. Ftg.5 requires a partial matching method betweenJ them, because a change in a view point causes visible substructures to be occluded and new substructures not observed so far to appear. This patial match is at first tried by .finding subparts with similar attributes in terms of color, shape and their substructures. General constraints on the graph match are listed in Fig.6. For an example, following correspondences . are found at first stage ( · ~ means a strong correspondence, and #I means a weak.one).

REI ++ LE2 I

LEI ++ LE2

Hl ++ H2 (a)

Hl ++ H2 (b)

Ml # M2

Ml # M2

( 1) OE:AO HAS LEFT-EYE.. UGHT - EYE, tlDSL AI·IO MOUTH HI HI S BO[·Y .

tEXIST<OBAO LEFT-EYEl tEXIST!OBAQ RIGHT- EYE) tEXIST!OBAO HOUTHl IEXIST!OBAG NOSE) tEXIST!OBAG BODY) tPART-OF!LEFT-EYE BODYl tPART-OF<RIGHT-EYE BODYl tPART-OF(HOUTH BODYl tPART-OF (HOSE BODYl Fig . 3 Explanatio·ns and their ·

int e rnal repr e s ent a t i ons

1. OBAO HAS LEFT-ARN AND RIGHT- ARM BESIDE HIS BODY .

tEMIST<DBAO LEFT-ARM ) tEXIST!OBAG RIGHT-ARMl tATTACH!LEFT-ARM BODY)

IATTACH!RIGHT-ARM GGDYl

• !31 OBAO HAS HAIRS ON THE TOP OF HIS BODY .

IEMIST!OBAO HA!RSl tATTACH<HAIRS BODY!

IRELATE<HAIRS OH BODYl

• !4) OBAO'S LEFT-EYE IS TO THE RIGHT OF HIS HOSE. tRELATE!LEFT-EYE TO-RIGHT NOSE)
• !5) OBAO'S RIGHT -EYE IS TO THE LEFT OF HIS NOSE.

tRELATEIR IGHT -EYE TO-LEFT NOSE)

• 161 OBAQ 'S LEFT -ARM IS ON THE RIGHT OF HIS BODY.

t RELATE(LEFT -ARM ON- RIGHT BODY)

fi g.S A si de view

Where, there are correspondences with regard to subparts Ll L2, LP2 RPl, RP2, but these are .used to support the above correspondence (a), (b), Concerning LAl, RAl, N 1 arid N2, LA2, as they are just one close region with the same color and no substructures, they cannot serve to restrict possibility of correspondence. Next using the above fact : as a clue, relations toward the .horizontal and vertical direction are checked · to see if the object is turned upside down or not. If so, the relation toward right and left direction must be reversed when a matching is attempted for the rest of structures of the object. Note that the assumption that a body is cylinder-like is used here. In either case for (a) or (b), the object is not turned .upside down, then it can be decided that horizontal relations among subparts must be preserved between these two figures. By . the Way when the first figure was given, whereas LAl , IRAl, iHl were clearly recognized as projecting structures, other parts are hypothesized. as patterns on Bl. On the other hand in the second figure, just N2 and H2 are identified as protruding·.. ones. A transformation 'of proje<;ting structures on a · suface between one and· another view point must be taken into consideration so as to decide correspondence 'among the rest of parts of the object. In Fig.4, locations: of Hl, LAl and RAl are not clear, because this figure cannnot specify the precise' location of them. Then their location are assumed to be on the side .or top of the body, which means the first 3D-relational model of the ·object that has ibeen generated by the first figure and explanation. For this description, the description , gained from Fig.5 is checked to see which parts are matched each other.

As mentioned previously there have been two possible correspondences,. but preservation of horizontal relations excludes tl).e case (a) because REl ++ LE2, Hl ++ H2, M 1 # M2 contradicts the assumption that. the body is of cylinder-like structure. On. the other hand the case (a) leads without contradiction to a conclusion that LA2 can be LAl and N2 be Nl.

Then the 3-dimensional structure of Nl is rewritten from pattern to projection and correctness of other structures is augmented as a consequence of this matching.

IMPLEMENTATION AND. DISCUSSION

The examples ~hown above are real results of the implemented the system. Although this system is not completely implemented, we have found many difficulties during the experimation. In this research the image processing programs extract subregions independently flrom 'the rest of this the system, then meaningless co.rrespondences are generated at the first stage. The. top down extraction mechanism concerning image processing is needed so as to reduce meaningless combinations between figures and parts names.

Since the examples used in this study are rather simple, then a reasonable conclusion is obtained. Especially, the examples ~ead to a model of the oljject without asking the user ambiguous points. We have also experimented exsamples with several ambiguities . on both labeling process and matching of figures . .. It is however too difficult to elucidate the case including bot,P, of the ambiguities in a limitted space. We . have not treated a peculiar case where a region or line are observed as a line !Or point, respectively. And also we have not considered precise estimation of a slii.ape transformation except for the relation between ellipses and circles.

Now, we have just experimented a few objects with a cylinder-like-boCiy, consequently we · must extend 1this method soc as to :appl·Y it to more objects not modeled by the first approximation that a , body is , of the cylinder-like. A knowledge organization mechanism must cbe constructed in order to build concept of the learned objects and to use experience in learning of other objects. The implemented system has no such a function .

SAME,~ SHAP E; mu .c;c ,. , .. uJat ch a ·. r eg ion agai nst a br anc h<

SAME-CO ~ - .parto with d ill e r ent r colo r s s houl d no t be pa ired.

• SAME .~INCL ; l or .; ubpar t s A of Band C o f <D, when A- does no t ma tched to C evenc if B and D can be pai r ed, they a r e no t r egarded . as a pa ir .

SAME .- RE~ ; ,if the r e i s an ext r em d i ller ence of loca t ion between t he pr edi c t ed one and t hat of t he model, t he predictibn is no t r ight.

Fig.6 Const r ai n ts on gr ap matc h i ng