Structuring Domain Knowledge For Visual Perception

STHX'IURING J:X:MI\lN KI'O<IIEOOE FOR VISUAL PEIO:PTIOO

Alan I<. Mackworth

Dept. of Calp.tter Science Univ. of British Columbia Vancouver, B.C.

Canada V6T lWS

I · INI'IOXCI'IOO

Early visual processing is conjectured to be almost entirely domain-independent and data-driven; however, high-level vision must exploit domain and object specific constraints and methods, intermingling data-driven and model-driven recognition. we are concerned with knowledge representation and its use for high-level vision. 'Ibis comnunication is a brief report on the theory underlying Mapsee2, a second program for interpreting sketch maps.

II. WHAT'S WR:Hi WITH MAPSEEl?

'Ibis paper is best read a~ a sequel to an earlier vision paradigm entx:x:lied 1n the program Mapseel [3]. '!bat program interprets sketch maps representing scenes containinq roads, rivers, br id;Jes, towns, rrountains, islands, mainland, lakes and oceans. The paradigm suggests extracting cues fran a lao~er level segmentation which are used to invoke, ambiguously, sets of object rrodels. These models are then made to satisfy internal and external consistency constraints using a generalized network consistency constraint satisfaction algorithm. Here we shall be concerned not with praising Mapseel but with burying it. In our view, Mapseel died of representational inadequacy. It exhibits seven ~taTs of that

disease:

1. Its cue/model structure has but a single level.
2. Each model's domain of interpretation is a finite list of labels with no structure within or between the interpretations.
3. Many of the real world scene domain constraints are represented poorly if at all.

'Ibis work was supported in part by NSF Grant MCS-8004882 and NSERC Grant A9281.

*No.> at Department of COlTp.lter Science, University of British Columia.

William s. Havens*

Dept. of Carp.tter Sciences Univ. of Wisconsin at Madison 1210 West Dayton Street

Madison, Wisconsin 53706

1. Its recognition process is essentially data-driven despite the grafting on of the "cvcle of perception" and interpretation-driven re-seqmentation.
2. '!be network of models is oompletely constructed before any model constrains another.
3. '!be model language is particular, local control of iropover ished. In recognition is not
4. possible.
5. Alternative scene interpretations are not explicitly available to guide the program.

The first three ~toms can be ascribed to descriptive inadequacy while the last four are symptanatic of procedural inadequacy.

III. THE !QOolLEIXiE REPRESEN:rATIOO

In order to rectify these inadequacies we have a schema-based knowledge representation. To have a baseline to evaluate the success or failure of the project and to build on the advances of Mapseel, we

have used the same scene domain.

• At a theoretical level, Mapsee 1' s contributions were to demonstrate the use of network consistency constraint satisfaction and the exploitation of data-driven, conservative segmentation techniques. In Mapsee2, we have concentrated on the interaction of decomposition and ~ialization in schema representat1ons, exploit1ng generalized network consistency techniques and the hoooqeneous use of data-driven and model-driven interpretation strateqies. ---

CX!r scene domain can be structured almost hierarchically, based on the canposition or part-of relation as si'Pwn in Figure l. A downward pointing arc indicates that an instance of the object above is comoosed of zero or more instances of the object belo.v. '!be decanposi tion is not a strict tree in that the same Town (instance), for example, may be part of both a Road-system and a Geo-system.

N. SPFX:IALIZATIOO LABELL!~

When an object is hypothesized to exist in the scene, an undifferentiated instance of its generic schema is created. As new canponents are recognized as part of the instance, its description becanes prCXJressively specialized. At the same time, its possible semantic relationships with other schemata becane further constrained.

Initially each incomplete schema instance must represent all possible final interpretations for that object. The schema is armiluously labelled. In contrast, Mapseel eJTployed exP icit exhaustive label sets associated with each object. Unfortunately these labels must be low-level interpretations of the primitive lines and regions which appear in the scene. Attent>ting to encode high-level abstract relationships in these explicit label sets leads to an unavoidable oombinatorial explosion of possible final interpretations.

In order to avoid this problem, we have developed an intensional labelling method for schemata representations called ~ialization Labelling. 'Jlle set . of poss1 le hnal interpretations (labels) · for a schema are represented as a tree. Each rode of the tree represents an ~licit . number of final interpretations. Each descendant rode represents a further specialization of the possible final labels implied l:1f its parent. 'Jlle root rode of the tree is the undifferentiated schema instance . At any time in the recognition of the schema instance, the set of all possible final interpretations for the schema is represented l:1f the union of all the labels ~lied 1:1f the current fringe of the tree.

Figure 2 shows the complete specialization tree for the Geo-system schema. Initially a Geo-system is fully undifferentiated, its labelling represented only ~ the schema instance itself. 'Jlle recognition of the Geo-system involves constructing this tree as new components are added to its description (generally increases armiguity of labelling) and pruning the tree as constraints are applied amonq related schemata (decreases ambiguity of labelling).

Specialization labelling avoids the problem of representing exponentially large numbers of labels for abstract high-level objects. As well, it provides a representation for manipulating semantically related labels as a single group.

V. THE ~ITIOO PRX:ESS

'Jlle recognition process is a search of the oamposition hierarchy for a complete and mutually consistent set of schemata instances. The search is guided 1:1f the procedural methods embedded in each schema. As each schema instance satisfies its own internal criteria for completed recognition, it is used as a cue for the hypothesis of higher schemata in the composition hierarchv. For exanple, ~lhen a '!Own instance has been f<;JUnd it i s used as a cue for invoking the procedural methoc'ls of both the Road-System an0 Geo-Svstem schemata above it in the hierarchy. In this way , appropriate high-level schemata can be hypothesiz~ by the discovery of appropriate hiqh-level cues, thus realizing a recursive cue/ model hierarchy.

The invoked higher schemata mus t find or make instances of themselves that can incorporate t he lower instance or return failure if none can. Spatial adjacency is the usual constraint used to find an existing i nstance. Mutual consis tency is then enforced between the higher and lower instances. M:ldel-consistency mod i f i es the description of the higher instance to conform to the lower. The modification includes possibl e further differentiation of the schema instance down its specialization tree or failure. (M:ldel consistency is a generalization of Waltz-l ike pruning of the corner label lists . ) Object-consistency modifies the lower instance to conform to the upper. (This is a generalization of Mapseel-like pruning of the component object chai n and region label lists) · This consistency process may then be propagated to other schema i nstances related to these under the control of the relevant schema methods.

For example, suppose a Shoreline Sl has been recognized as an interpretation of a chain closinq on itself. Sl requires two Geo-system instances tc be part of, G-Sl, the inside one, and G-S2, the outside one. Suppose G-Sl already exists and is already known to be a Landmass, because it contains a Road-system. M:ldel consistency of G-Sl with respect to Sl requires that G-Sl be further specialized to Island. Object consistency of Sl w.r. t. G-Sl specializes Sl to be Island-shore (as qJpOSed to Lakeshore) · Suppose the outside Geo-system for Sl, G-S2, has to be created as a new undifferentiated Geo-system. Model-consistency of G-S2 w.r.t. the Island-shore Sl specializes G-S2 to be a Waterbody. Object consistency of Sl w.r.t. G-S2 succeeds. All of these specialization constraints may propagate to other related schema instances which may in turn continue to propagate them.

VI. cno..tJSIOO

This model of perception is embcdi ed i n the prCXJram Mapsee2. Mapsee2 is written in MAYA, a multiprocess LISP dialect supporting schemata data and control structures [1,2]. Our experience with it so far has been limited so this carmuni cation should be viewed merely as a br ief progress report with tentative sl.ll111lary conclusions. In the meantime it should be clear that each of the inadequacies in Mapseel has been rectified in Mapsee2. Our rrodel is intended to provide a coherent framework for the desiqn and implementation of high-level, schema-based perceptual systems.