Model Invocation for Three Dimensional Scene Understanding

1 Introduction

One imporiant and difficult taak for a genera.! model baaed vision sys· tem ia invoking the correct model. Because .of the potentially huge number of pouible objede, it ie imperative tha.t only a few serious candidatea are aeleded for detailed coneideration. Visual understand· ing muat alao include a pre-attentive element, because all modele need be considered, yet active, direct comparison ie computationally infea.· eible. Furiher, previoualy unseen objech, flexible objects seen in new configuration·, incompletely visible objects (e.g. occlusion) a.nd object varianh (e.g. flawe, generica, new exemplars, etc.) require selecting modele that are "close· to the da.ta..

Model invocation is not juat a visual problem (e.g. integrating cuea while doing crouword puules or invoking situation schema.s), but here only the visual problem ie considered. Invocation a.uocia.tes cluea that auggeat rather than verify. U may support the "seeing" of nonexistent, but highly plaueible objects, aa in surrealist art.

To date, liU!e work haa been done on sophisticated model invo· cation in the context of 3D viaion. Using eaaily meaaured properties to select potentia.! modele faile in large model baaes, because many objecb ahare eimila.r properties. Further, da.ta. errors, generic objects, object substructure a.nd occlusion complicate indexing.

Arbib [1] proposed a achema-baaed invocation proceu with acti­ vation levele baaed on evidence, competition a.nd cooperation from related activity. Ma.rr (6] considered direct search in a model-baae linked using apecificity, adjunct and parent relations. Hinton a.nd Lang (5] evaluated a connectionist model of invocation for 2D models, treating both model a.nd data. feature evidence identically. Feldman and Ballard (2] proposed a detailed computational model integrating evidence from apatially coincident property pairings.

This paper deacribes a. solution tha.t builds on these, embodying ideaa on parallel networks, object description and representation in the context of 3D modele and 3D visual information. The result is a. pla.uaibility calculation in a network structured according constraints defined by the sttudural, generic and context relationships.

Acknowledgements . . . Portions of this work were supporied by a. Umvemty of Edmburgh studentship. Thanks go toR. Bea.Uie, J . Halla.m, D. Hogg, J. Howe, M. Orr and many others.

2 Problem Context

These resulls a.re from the IMAGINE project (3] which inveatiga.ted recognising 3D objects starting from 3D scene information. Earlier stages of processing include:

1. exploiting 3D feature continuity to overcome occlusion,
2. grouping individual surfaces to form primitive and depth a.ggre· gated surface clusters (4] .
3. deacribing the significant scene features (curves, surfaces a.nd volumes) by their 3D properties.

Model invocation happens a.t this point . After invocation, model­ directed processes orient a.nd verify the hypotheses.

Recognition starts from 2 ! D sketch -like da.ta. segmented into sur· face patches of nearly uniform shape a.nd separated by various shape or obscuring boundaries. As no well-developed proceues produce this da.ta. yet, the program input is from computer augmented, hand­ segmented test images. The paper illustrates the invocation process using a test image of a PUMA robot with its gripper obscured, using the surfa.cea shown in figure 1. The scene ha.s flexibly connected rigid solids, haa a. variety of curved surfaces a.nd the robot is both externally a.nd self-obscured.

Object modele are primarily structural, with features attached by reference frame transformations. The ma.in primitives a.re the sur· face patch (SURFACE), characterized by consistent surface shape a.nd polycurve boundary, and hierarchical groupings of surfaces ( ASSEM­ BLY).

Four additional representations are added for invocation:

1. generic relationships between modele,
2. .2. major featurea of each a.uembly grouped according to viewpoint,
3. relevant properiies with typical values for ea.ch structure, a.nd
4. weighting factors modifying the importances of the properties and relationships.

3 Theory: Evidence and A .. oclatlon

Model invocation is baaed on a plausibility value, in the range [-1,1], measuring how well an object model explains an image structure. Models are invoked when the plausibility is positive and aero is treated as a distinguished value. Plausibility is used because:

• some measure of similarity between objects is needed,
• it allows weak evidence support from associated hypotheses,
• it supports accumulating unrelated evidence types, and
• it degrades gracefully as data descriptions fail because of noise, occlusion or algorithmic limits.

The basic structural unit of invocation is the model instance - a given model in a given image context. Contexts are important because object features are usually connected or nearby. They define where image data can come from and what structures can provide supporting evidence. Here, the two types of contexts are the surface hypothesis and the surface cluster, which localize evidence for SURFACE and ASSEMBLY models respectively.

The inputs to invocation are:

• A set { C;} of image contexts.
• A set {(d;, v;;, C;)} of image descriptions of type (d) with value ( v) for the features in these contexts.
• A database {(t;, M;, M~~;, w;;~~:)} of model-to-model (M) associ­ ations of different types (t) with weights (w).
• A database {(M;,{(d;;,l;;,u;;, w;;)})} of desired description con­ straints for each model, where d is the description type, [l,u] is the range of acceptable values and w is a weight.

The output of invocation is a set {(M;,C;,p;;)} of plausibility mea­ sures for each model instance in each image context.

The plausibility of a hypothesis is a function of direct evidence from observed features and indirect evidence from associated hypothe­ ses. For example, a toroidal shape is direct evidence for a bicycle wheel, whereas a nearby bicycle frame is indirect evidence.

Direct evidence ia acquired from image data (e.g. 3D properties such as surface curvatures, axis orientations, etc.). Indirect evidence comes from associations, of which six types have been analyzed here. The four distinguished types are supertype, subtype, supercomponent and subcomponent, the fifth is the competing identity relation and the sixth ia the default association category. The nature of the influence depends on the type of the relationship. For example, an object nec­ essarily requires most of ita subcomponents to be present, whereas the reverse does not hold. Finally, a computation that integrates the seven evidence types to produce a single plausibility value is given.

When defining the different evidence computations below, a set of constraints and a satisfying function is given. Unfortunately, the constraints are never sufficient to implicate a unique function.

3.1 Direct Evidence

Direct evidence is calculated by comparing data properties (from within the appropriate image context) with model requirements.

Some constraints on this computation are:

• The contribution of a datum should be a function of its salience and the degree to which it meets its requirements.
• Each datum is considered only for the best requirement.
• Not all requirements need data (e.g. because of occlusion).
• Every datum must satisfy a constraint, if any of the appropriate type exiat.

Based on these requirements, the following function evaluates a datum according to a requirement:

Let:

n = nominal value (from model), r =nominal range (from model), w = importance weight (from model), d = data value

A description's evaluation is given by the requirement it fih best. Because many models are likely to share some properties, any negative evidence should seriously reduce the plausibility, when inte­ grating the individual evaluations. However, it should not cause im­ mediate rejection, because the evidence may have arisen from (e.g.) partially obscured structures. Here, integration uSeJ a weighted aver­ age that incorporates negative evidence doubly.

This algorithm defines a network fragment linking observed prop­ erties to model instances. The main processing elements are the prop­ erty match evaluation, "max·, ·sum· and ·weight" · functions, with interconnections as defined by the above algorithm. The other algo­ rithms below also have this property.

3.2 Supereomponent Aaaoclatlona

This association gives indirect evidence for a subcomponent, given the possible existence of an object of which it is a part. It ia only suggestive, because the presence of the supercomponent implies that all subcomponents are present (though not necessarily visible), but not that an image structure is any particular component.

Other constraints on the relation are:

• The more plausible the ·object, the more plausible its subcomponents.
• There is only one true superobject of any subcomponent.
• The object context must contain the subcomponent contexts.

One function meeting these constraints chooSeJ the largest plausibility of any supercomponent in this or any larger context.

3.3 Subcomponent Aaaoclatlona

This association supports the presence of an object, given only the presence of its subcomponents (but not requiring any geometrical re­ lationship). For a 3D object, only some of its subcomponents are typically visible from any particular viewpoint, implicating key fea­ ture groupings for integ~:ating e.vidence.

Some constraints on this computation are:

• The more subcomponents present and the more plausible each subcomponent is, the more plausible the object is.
• Subcomponents are seen in viewpoint dependent groups (listing viaible components according to salient viewpoint).
• The subcomponent context must lie within the object conted.

The subcomponent computation occurs in three stages:

1. Find the most plausible candidate for each subcomponent in the given context and subcontexts.
2. Integrate the plausibilities of all subcomponents seen in each viewpoint grouping (weighted to express relative importance).
3. Pick the viewpoint grouping with the highest plausibility

3.4 Identity Inhibition

A structure seldom haa more than one likely identity, unless the iden­ tities are generically related. Hence, an identity is inhibited by un­ related identities having high plausibilities in the same context. In­ hibition also comes from the same identity in aubcontexts, to force invocation to occur only in the smallest containing context.

Other constraints on the inhibition computation are:

• Only positive evidence for other identities inhibits.
• Inhibition varies with the plausibility of competing identities.

These constraints suggest the following computation:

• pick the largest plausibility of all generically un-related hypothe­ ses in the same context and all hypotheses of the aame type in sub-contexts. Call thia P.
• if P > 0, then the inhibitory plausibility is -P; otherwise no inhibition ia applied.

3.6 Evidence Integration

The seven evidence 'ypes are in,egra'ed 'o give 'he plausibili'y value for 'he model hypo,hesis. Some constraints on this compu,ation are:

• DirecUy rela'ed evidence {direc,, subcomponen' and subtype) should have grea,er weigM.
• O'her indirect evidence should be somewhat incremental.
• Only 'ypes wi'h evidence are used.
• If 'here i8 no direct, subtype or subcomponen' evidence, 'hen evidence in,egration produces no result.
• Direc' and subcomponen' evidence are equivalent and 'he weaker of 'he 'wo should be bken.
• S'rong supercomponen' or association evidence supports.
• The plausibility of a 'ype mus' be a' least that of the subtype and a' mos' 'ha' of 'he supertype.
• If o'her identities are competing, 'hey inhibi' 'he plausibility.

One .function meeting 'heae conatrainta is:

~

• E - invocation in exa.c' con,ext
• L - invocation in larger con,ex' 'han neceaaary
• I - invalid invoca,ion

.H.QIES.

• 1 - because 'raahcan ou,er surface very similar
• 2 - aimilari'y with upper arm model
• 3- ASSEMBLY wi'h lingle surface has poor diacrimina,ion
• 4 - no' large enough con'ex' 'o conbin all components

4. Evaluation

Ideally, invocation should select all correct models in only the co.r· rec' contex' and 'he only false invoca,ions are those "similar· to the true ones. Further 'he compubtion should converge. As 'he network struc,ure is scene dependent and non-linear, only minor ma,hematical results have been found so far, concerning:

• rela,ive ranking betwee11, 'he same model in different contexts,
• correct direc,, subcomponent and generic evidence always im· plies invoca,ion, and
• the number of direct evidence properties to use.

So, a performance demonstration is presented, using a network crea,ed from 'he tea' scene, showing tha,, here, invocation is effective.

Table 1 lists all invoked ASSEMBLY models and the associated image regions, ranked by plausibility. (Invoked surface models are not listed.) These were computed in a ne,work con,aining 252 model-data pairing nodes for H ASSEMBLy models in 18 surface clusters, and 425 nodes for 25 SURFACE models in 17 data surfaces.

lnvoca,ion was aelec,ive with 17 ASSEMBLY invocations of a pos· aible 252, where 10 oUhe 17 invocations were correct and 9 were in the smalles' appropria'e contex,. All appropriate invocations occurred. Of 'he incorrect, only 3 were unjustified (notes 2 and 3 in 'able 1). From 'he SURFACE model invocations (no' shown), 24 invocations were made ou' of 425 possible. Of 'hese, 10 were correc,, 10 were jua,ifiably incorrec' because of similarity and 4 were inappropriate invocations. Clearly, invocation worked well here.

The chief causes for improper invocation were:

• not large enough contex' 'o con,ain all subcomponents while having s'rudurea no' contained in 'he successful context, and
• superficial aimilari'y be,ween fea,ures.

li Diacuasion

The invocation process discussed here in,egrates 'he major evidence types and elimina'ea 'he need for exhaustive model-directed 'eating while still maintaining acceaa 'o all models. By basing invocation on propagated plauaibili'y values, the data 'o model comparison compu­ tation has been regularised, and is amenable to parallelism.

To summarise, this paper has:

• defined a formal basis for visual model invocation.
• proposed cons,rainh on the effect of different evidence types.
• proposed surfaces and surface clusters as the contexts in which 'o consider invoca,ion.
• demonstrated a successful implementation of the theory in a simplified 3D contex, .

6 Bibliography

1. Arbib, M. A., LocGl Orgo.nizing Prouuea o.nd Motion Schemo.a in Yiauo.l Perception, in Hayes, et.al., Machine Intelligence 9, pp287-298, 1979.
2. Feldman, J . A., Ballard, D. H., Computing With Connection·, in~ and Machine Vision, Beck, Hope and Rosenfeld (eds) , Academic Preas, pp 107-155, 1983.
3. Fisher, R. B., From Surfo.cu to Object&: Recognizing Object. Ua­ ing Surfo.ce lnformo.tion And Object Model., PhD Thesis, Dept . of Ar,ificial In'elligence, Univ. of Edinburgh, 1986.
4. Fi8her, R. B., Identity Independent Object Segmento.tion in I! 1/tD Sketch Do.to., Proc. 1986 European Conference on Artifi­ cial In'elligence, July 1986.
5. Hinton, G. E., Lang, K. J ., Sho.pe Recognition o.nd nluaory Con­ nectiona, IJCAI 9, pp252-259, 1985.
6. Marr, D., Vision, W.H. Freeman and Co. (pub), 1982.