The ACRONYM Model-Based Vision System

The ACRONYM Model-Based Vision System

Rodney A. Brooks, Russell Greiner and Thomas 0. Binford Stanford Artificial Intelligence Laboratory, Stanford University, Stanford, California, 94305, U.S.A.

ACRONYM Is a model-based image understanding system. It demonstrates mechanisms for interpretation of images with generic object classes and genem viewing conditions. in a way that is generalizable. It incorporates a powerful geometric modeling capability with a high level modeling language for natural communication with the user In terms of object models. A user gives high level descriptions of both generic and specific instances of objects. A rule-based Inference system produces a viewpoint dependent symbolic summary of the predicted appearan~;e of the objects. This geometric reasoning capability enables the system to Incorporate and relate knowledge and information at different levels. This summary drives a powerful syntactic matcher to find Instances of the objects In preprocessed Images.

I. INTRODUCTION

ACRONYM Is a vision system based on powerful geometric modeling capabilities. Its geometric modeling system is of Interest in Itself. ACRONYM is also the basis for research in programming robots from a data base of parts models.

ACRONYM is Intended to deal with key problems of Interpreting scenes:

1. Generalizabllity is a central issue. A photolnterpreter performs a a broad range of ta~ks which involve different object classes, which have different contextual Information, and which vary greatly at the Image level because of varied viewpoint, illumination, sensors, weather, and obscuration and camouflage. Systems for very different tasks should be constructed from a large core of common modules and a small set of task-specific modules. For a single system to map this wide range of task elements onto a common set of modules, It Is convenient that the modules represent a natural decomposition of the problem into physically meaningful elements, for example, those we use in our own human description of the problem. Our basis for generalizabillty Is the use of a tightly structured hierarchy of geometric representations.
2. A variety of InfOrmation and knowledge is available. A photolnterpreter solves a puzzle by piecing together selected and multiple clues from current images, background Information, and previous lm<~ges . In doing so. he rrlies heavi ly on spatial interpretation from stereo imaging and shadows, and spatial knowledge about structures.

This research was sponsored by ARPA contract MDA-903-76-C-0206 and NSF contract DAR-781591-t.

Integrating multiple cues within a single task is a key issue which raises technical questions for representation.

1. It Is Important that the system be generic with respect to objects and generic with respect to viewing conditions. Our approach to generic Interpretation Is to use object models made from generic parts, and to me generic predictions of appearances of generic parts.
2. Users should be able to specify tasks In a natural and simple way. Geometric modtls are natural for both the user and the vision system. Ultimately, users will be able to Instruct systems In natural language. The representation hierarchy of ACRONYM is the b<~sis for a Vi~ion Language which could serve as a bridge bttween natural language and standard programming languages.

We describe capabilities for goal-directed model-ba~ed scene Interpretation ba~ed on mapping from objeCt and part models to predicted appearances to picture structures. A CRONY M Is dcsignl"d to function in a descriptive sense (bottom-up) as well, mapping from picture structures to features of parts to object models. In typical sttuattons, both functions are Involved.

Model-based vis ion has rna Jor applications In photointerpretatton and manufacturing. Consider two typical tasks for the systtm:

1. A photointerprtter programs the system to monitor aircraft at an airfield . A lrcraft models are tntered along with a modtl of the airfield . The system Is told thilt aircr·ilft are found at airfields on runways, taxiways, or storage areas.

2. An engineer programs ACRONYM to Inspect a part, or to pick the part from a bin of identical parts and place it in an assembly. He uses the part model from a CAD system and specifies a model of the workstation.

The diagram in flg. l shows the main modules, data structures and data rlow paths, along with the local environment of ACRONYM. The lnnner enclosed boxes represent data structures, the other boxes are program modules. As of January 1979, implementations of all the modules existed, but not all data paths were in operation.

The user interacts with a high-level modeler to produce both generic and specific models. There will eventually be a library of useful partial models to draw upon. The result of this modeling process is the Ob jcct Graph. This graph drives a graphics module which provides the user with visual feedback of shape and spatial relations during the modeling session. The Predictor and Planner module produces a symbolic summary of the way an object modeled In the ObJect Graph can be expected to appear In an Image. This summary Is called the Observabllity Graph and Is used to program the matcher from above. The Matcher constructs an Interpretation Graph from the Observability Graph and the Picture Graph, which Is a symbolic description computed from the Image by the surface mapper, and the edge mapper. The edge mapper uses techniques of Nevatla and Babu [23) to extract two dimensional shape descriptions from the images. This Is augmented by depth information from the stereo pair of Images (when a pair ls used) in the surface mapper, using techniques developed by Arnold [2).

Also Included In fig I are modules for A L and POINTY (see Goldman [ 13)). A L Is a high level l~nguage for controlling manipulator arms. ACRONYM has been interfaced to the A L compiler, so that Instead of driving the physical arms, A L drives ACRONYM models of arms. ACRONYM can update its display of an arm faster than once per second on a moderately loaded system, giving real time simulation. There is an Interface in the other di rect ion to POINTY. POINTY Is an Interpretive sul>set of AL, originally designed to be used in a lead and teach mode, to easily obtain spatial Information for A L programs. ACRONYM can control the arms via POINTY. So far we have used this Interface only for debugging, but It will eventually be used for fully automated assembly tasks, with model-based vision.

2. PREVIOUS MODEL-BASED SYSTEMS

ACRONYM provides a unified approach to many aspects of goal-d lrected vision, and generalizes the approaches of previous vision systl;ms. It has a richer three dimensional model representation, a rule-based planning system, and makes more extensive use of shape and relational Information than previous systems. We briefly .survey some ex istlng systems to summarize their use of models and their matching processes.

The MSYS system (Barrow and Tenenbaum [i)) models objects ln terms of their height and orientation, and models three dimensional spatial relationships between them in terms of above, below,in front , In back, left and right. Some models (e.g. of a floor) are also constrained to correspond to homogeneous regions within an image. An image is roughly segmented by h~nd . Simulated range data is used to determine three dimensional locations and orientations of regions and their spatial relations. Horizontal surfaces are Identified by height. No shape information is used at all . A matcher matches the data against the model. These simple models are sufficient to identify typical objects in a room scene. This demonstrates that spatial relations can be a strong constraint when identifying regions of an image. However the models used rely on a particula r viewpoint, and the ability to propagate constraints throughout the whole image. If some other viewpoint is used, or if the scene ls cluttered with objects not contained ln the model, the constraint approach will break down. Tenenbaum and Barrow [25) have also used this system to dnve the IGS Interpretation guided segmentation system which produces segmentations constrained to be consistent with the high level model.

Garvey [ 12) developed a system which models objects in terms of their height and orientation, three dimensional spatial relationships with each other and the expected ranges of brightness, hue and saturation of their pixels. ApproxImate Indications of size and shape may also be Included. In InteractIve sessions with sample pictures, the system computes histograms of these features over manually segmented regions. Confidence values are given to the spatial relations by the user. The system is given the task of fi nding a given object in an image. It knows the costs associated with testing pixels for each attribute, and so as an initial coarse !Jass, It tests pixels randomly selected from throughout the Image with tests that will cheaply rule out large areas. These tests are selected by examining the models of known objects for cheap distinguishing features of the desired object. Garvey calls this initial phase acq uisition. In the second phase, validation, the models are used to determine more expensive tests, over this reduced area, which will disambiguate the drsired object from others which might also h;~ve produced the pixels first obtained. Spat ial relationships In the models can be used to drive the system when looking for small objects. Larger objects, expected to be adjacent In the Image (such as a table top when look lng for a trlephone) are found first, reducing the search a rea for the sma II obJeCt. The search for the small object can then be carried out at a much finer level. The planning st;~ge and coarse to fine strategy used improve efficiency but this system too suffers from the inability to use general sh;~pe Information.

B;~llard, Brown and Feldm;~n [3) describe a gener<~l purpose system for progr;~mming knowledge-based vision tasks. The knowledge or model Is In terms of nodes describing expected lm;~ge features. and spatial constraints between them. Templates are used to describe shapes. The user must code <Ill executiV(' m;~tch procedure for the p<~rticular task dom<~in. The system has been used for aerial image interpret<~tion and finding ribs in radiographs of human chest c;~vities. While very general purpose, the system is heavily dependent on using a fixed and known viewpoint, and req uires detailed programming for each new domain. Furthermore the user must model objects in the image

domain rather than the three dimensional domain.

Bolles [9) has a Verification Vision system which relies only on the three dimensional relationships of observables to locate a mechanical part accurately within an automatic assembly work st;~tion. The position of the part Is known in advance to within a few inches, and Its orientation to within about fifteen degrees. Thus the models can be very viewpoint dependent. Rather than use shape descriptors; Bolles relies on very loca I operators such as edge detectors, blob characterizr.rs, and Moravec's [20) Interest operator to characterize the ob~ervables. Due to the highly constrained nature of the t il~k thr.se operators have a reasonable chance of matching the correct feature In the image. The system uses a generalized least squares algorithm, and clique finding to rnatch the model of the known spatial relationships of the obJeCt to the features identified by the operators. The model can be used to drive a further refinement phase, where the location and uncertainty region for further features are predicted. These features can then be searched for in the restricted region, with much reduced probability of incorrect Identification. Notice that the models used here are simply a collection of points on the surface of the object.

Kanade [16) distinguishes the Image domain, the domain of observable facts from viewing the scene In either intensity or range data, and the scene domain, where objects are modeled. l-Ie uses a 2 1/2 D scene domain. Objects are represented as Image regions. Shape and spatial relations describe the regions. Ob jeers have multiple representations for multiple viewpoints, but these must be explicitly described by the user. The matching process tries to match observed patches against modeled patches.

Rubin's [24) ARCOS system stores multiple representations of buildings, in terms of such things as texture, color, orientation t~nd gross shape featurl.'s, all gleaned from training examples. It ;~I so has three dimensional knowledge of the positions of the buildings, which is translated into adJacency Information to guide the search for labellings of pixels. The sr.arch technique is a very local pixel (or segment) b<1sed "Locus" search. This localness means that adjacency Is the -only meaningful relation which can be used.

These systems make valuable contributions to model-based vision, however they do not generalize in significant ways, with respect to viewpoint, With re~pect to object classes, and with respect to very large classes of objects. In almost all cases, data and model are matched at the same level, e.g. surface to surface or point to point. ACRONYM adds the capability to reason between different levels of representation, based on a hierarchy of representations.

3. MODELING

The Object Graph contains three dimensional models. It provides volumetric representations of objects, both specific and generic, and three dimensional spatial relations between volume elements. It also provides for multiple levels of represent<~ lion of objects, from coarse to fine. The basic volume primitive used Is the generalized cone, first introduced by Binford [!i). Spatial relationships of volume elements within an object are defined hierarchically. Both specific and generic volume l.'lements, and relations between them can be modeled. Thus an airplane can be defined to have exactly two wings. while an airport can be described as having from one to four runways.

The Context Graph Is not really distinct from the Object Graph. It is only a convenience to talk about objects such as aircraft and their context, airfields. Both use the same representt~tional rpechanisms.

3.1 Generalized Cones

Our models are part/whole graphs; the models resemble stick figures. Parts h;we subparts, they are subgraphs whose leaves are our primitives, generalized cones. Levels of detail correspond to levels of the part/whole subgraph. A natural and useful part/whole segmentation depends on the primitives used for representation of parts. Design criteria for representation were presented In Thomas and Binford [26).

A generalized cone Is defined by generalized translational lnvarlance. It Is described by three sub-primitives; a spine, a cross section and a sweeping rule. In its most general form, a generalized cone Is the volume swept out by the cross section as It Is translated along the spine, while being deformed according to the sweeping rule. Elongation is not a necessary property of generalized cones; neither is a circular cross section.

Most objects can be segmented In a few ways Into volume elements whose cro~s sections change smoothly along some space curve (~ee [21) or Nevatia and Binford [22)). These volume elements can then be modeled by a single generalized cone, with its spine along that space curve. Generalized cones accurately represent a variety of fabrication proce~ses. Intrinsic properties of a generalized cone can be approx lmiltely Inferred from Its two dimensional Image under a broad range of viewing conditions (Nevatiil [21). M<~rr and Nishihara [18)). For example, the length to width riltio varies approxamately as the sine of the angle between the the cone axis and the ray from the axis to the observer. While generalized cones need not be elong·ated, interpretiltion is much simpler for elongated objects and current techniques rely on elongation. M arr [ 17) has shown that Interpretation of the occluding contour of an image of an object, under certain restrictive assumptions, Is equlvaknt to interpretation as generalized cones. Thus generillized cones correspond to a niltural decomposition of large clas~es of objects, and they are easy to match to a two dimensional Image. Moreover they provide a compact representation for complex volumes. The representation of complex objects requires representation of only a few parts, l'ach of which is about as cornplex as the n·presentation of a cube.

Generalized cones have been used In a number of vision and geometric modeling systems. A gin (I] built generalized cone descriptions from Images of simple ob jecu such as a snake and a hammer. Nevatia (21) recognized images of dolls and toy horses, by indexing Into a library of generalized cone models. Miyamoto and Binford ( 19] built a general modeling and graphics display system based on generalized cones. Hollerbach (I i) modeled and recognized classes of Greek vases. M arr and Nishihara [ 18] described a method to determine the orientation of objects by matching them to generalized cone models. ·

Representation of spherical volumes as spheres is Intuitively better than representation as generalized cones, especially for portions of spheres. We set out to incorporate two primary geometrical constructions; translation and rotation. Generalized cones are based on generalized translational lnvarlance. Spheres are based on rotational invariance. We have a straightforward generalization of rotational lnvariance, however generalized spheres, as we understand them now, do not seem as powerful an extension as generalized cones. and we require more work to include them in our representation. We have also thought it necessary to represent surfaces, obviously to represent cross sections of cones, but also for nonplanar sculptured surfaces such as wings. Generalized translational invariance is useful here, too. Generalized cones specialize to ribbons, which are defined by an axis and a cross section, both of which are space curves not plane curves, and a sweeping rule (see Brooks, Greiner, and Binford [7)). It Is not our intention to Ignore standard surface spline representations, but rather to explore the advantages and cost of an alternative representation.

We use a more general class of generalized cones than previous systems. However there are still major restrictions. The cross sections must have a boundary which can be decomposed into straight line segments and circular arcs. The cross section can be kept at any constant angle while being swept along the spine. The sweeping rule must be piecewise linear, and continuous. The spme must be continuous and made up of straight line segments. Circular arcs can also be used as segments of the spine, so long as the sweeping rule is constant, the cross section has a piecewise linear boundary and Is kept normal to the spine. Fig. 2 shows some examples. This latter class allows for convenient representations of curved roads or taxiways. Analytic work Is being done to formalize a natural and adequate extension of this subclass of generalized cones.

The parameters of a cone can describe ranges of possible values, or provide a predicate to test the validity of a proposed value. For instance a generic runway can be described in terms of allowable ranges of length and width - possibly dependent on each other.

3.2 Model Structure

As in previom modeling systP.ms based on generalized cones (e.g. Miyamoto and Binford ( 19)) there is a local coord inate system for each volume primitive in a model, rather than a viewer centered, or object centered coordinate system. A complex object which is modeled by more than one generalized cone has an arfixment tree (in general a directed graph but multiple affixments can be inconsistent), where the coordinate system of a cone is that of its parent, modified by the coordinate transform attached to the arc joining them. As in previous systems (see Thomas and Binford [26)) our models also have a hierarchy of level of detail. However we have chosen to separate this hierarchy from the attachment hierarchy.

The following two examples indicate how and why this separation c;~n be meful. It is natural to affix the two wings of an airplane to the fuselage, to describe the spatial relation among them. However wings appear almost the same size as the fmelage, and the two of them combined (e~pecially when an airplane on the ground is viewed from above) provide an ;~xis of elongation of the same order as that given by the fmelage. Thus at the first level of decomposition, we model an airplane as the generalized cones of the fmelage and the two wings, rather than as a single cone. Consider now the Stanford robot arm shown in fig. 3 (this Is a drawing produced by ACRONYM from its model of the arm). A natural first level of decomposition of the arm Is the upright b;~~e. the boom and the hand assembly. The point of interest here Is the relation between the boom and the hand. The spatial relation between the l:oom and the wrist is best described by a series of spatial links through subp;uts of the hand.

It Is Important to represent both gr.neric objeCts (loosely classes of objects) a~ well as specific objects. For instance we may want to look for airports In general, not only to count the airplanes at each, but also to count the numbers of particular types of airplanes which can be identified. Thus a DC-10 say, would be recognized H an instance of the Object Graph node airplane, or ;~s a DC-10. An aircraft with special radar would be Identified as a modified form of a prototype. If the Object Graph doesn't include a detailed model of a Boeing 76 7, It might be identified as an airplane, but fail to match prcci~ely any detailr.d model. A specific model may be a more refined version of a generic model and a specific model can be an example included in a generic model. The modeling system provides language constructs for using a node of the object graph as a prototype for the construction of a new node. This can be done at all levels - from an object down to a sweeping rule.

3.3 Geometric Editor

The high level modeler provides a high level language which gives the user the ability to manipulate models with symbolic name~. and provides ways to examine partially built models. There is also a graphics module to help the user with detailed modeling of specific objects. It provides the user with visual fecdb;~clc. of wh;~t is being modeled and where the local coordinate systems are. The class of cones allowed can generate complex curved surfaces, e.g. the surface generated by a circle swept along a spine at some non-normal angle while varying in size. Rather than approximate thrse ~urfaces with planar surfaces, we manipulate Its symbolic description nght up until the time to deposit the visible lines in a raster buffer.

We have fast an;~lytic solutions for the appearances of the occluding contours of thrse wrfacrs, and have implemented them in a hidden back surface algorithm. It works directly from the object graph represrntation~ . Early drtails of that algorithm appe<~red in our p<~prr [7). Work is proceeding on extending this to ;~ full hidden surf<~ce algorithm and the full solutions will appe<~r In a later memo. Figs 2. 3, <f were produced by ACRONYM, requiring approximately 250 milliseconds for the most complex of those figures.

4. PRODUCING TilE OllSERVABILIT\' GRAPH

Given models of objrcts, ACRONYM ;~ttcmpts to find instances of the objects in images. The Observab1hty Graph will tell the matcher how to fmd instances. It is a symbolic summary of the expected <~ppearance of objects m the im;~ge. It contaim gPneric and specific predictions about shape elements and relations b<'lween them, with information about how to fmd them, what conclusions to draw If identified and what to wnchrdc if they are not there. If tnfo.-mation about VIewing angles, d1stance and conditions Is av;~rlilble, it can be used to produce more definite predictions. The Pred1ctor and Pl~nner module is a rule based system wh1ch mes the Object Graph to produce the Observability Graph .

The program mmt choose features of the ob jP.Ct whrch correspond to image and wrface properties which segmentation progr;~ms can fmd . We Will call such feat11res "observ;~bles". The features which we are usrng f1rst include shape and two dimensional spatial relations of shapes within the Image. When dealing with a stereo pair of pictures we t~lso use three dimensional splftial relations and surface Information. We Intend to extend the class of features after our Initial experiments.

4.1 ObserVIIblea

Since the exact disposition of objects in the image is not known In advance, the Observabillty Graph can not contain an exact prediction of what will be seen. Rather, It mu.st consist of predictions which adequately describe a range of possible appearances, generic with respect to both object class and viewpoint. They can best be thought of as supplying constraints on the way the picture can be expected to look. For instance, given that the system will be examining aerial photographs of airplanes on the ground, the Predictor and Planner can tell the matcher that when a candidate fuselagE" Is found, wings should be found adjacent to It, with bilateral symmetry. There will be two possibilities for the relative angle, and once the actual angle has been found, the front and rear of the fuselage will have been distinguished . Then the finer task of locating the rear stabilizers (for positive Identification of airplane type) can be carried out, confined to a small part of the image. How these are Implemented Is descnbed in the next paragraph.

The best sort of observables to put Into the Observabillty Graph are those which are invariant. This is a strong requirement; other predictions will be true under a wide range of viewpoints. We will call these quasi-invariant observables. Some are quasi-invariant with respect to object class, while others are quasi-Invariant with respect to viewing conditions. For example all airplanes have a long cylindrical generalized cone as the fuselage (invariant with respect to object cla~s), and from most viewpoints (especially aerial views of airplanes on the ground) the fuselage will appear as an elongated ribbon (invariant with respect to viewing conditions). Observables which are functions can be viewed as quasi-invariants too. For example, the orientations of the wings within an image are functions of the orientation of the fuselage.

The Observability Graph itself consists of nodes, arcs and relations. The nodes are either direct shape descriptors or recursively complete Observabllity graphs themselves. For Instance an airport Observability Graph will contain nodes for runway ;md taxiway shape descriptors, and a node which Is Itself a complete Observability Graph for the generic class of airplanes. Each node corresponds to something which should be identifiable in an Image. A res are binary relations which should hold between Instantiations of the nodes they link in the Image. For instance an arc might say that any instance of a runway should intersect at least one instance of a taxiway. The Observabillty Graph also allows n-ary relations - called simply relations. These are selected from a library of relations each of which is a function on a list of Observability Graph nodes and their candidate instantiations. Proximity and connected are currently Implemented.

4.2 Control of Rules

The Predictor and Planner is clearly a critical module of the ACRONYM system. ACRONYM is the first vision system to Incorporate a general reasoning system. It Is necessary because we wi$h to predict the appearance of generic objects, from generic viewpoints. This is a difficult task which requires reasoning about a large body of diverse knowledge. We have chosen to use a rule based system to facilitate experimentation, and to provide additivity of new knowledge. We will first describe the control structure we have implemented for our rules, then discuss some of the techniques used in our early sets of rules to produce the Observability Graph .

The basic control strategy we have chosen is to have our rules consequent driven (I .e. goal directed, or backward chained). The rules can be interpreted to mean that the consequents should be a~m· ted if the conjunction of the antecedents can be proved. This simple strategy is not quite sufficient for the task at hand, however. It is possible that once Invoked and "fired" a rule may take control for a while, doing some forward reasoning, and possibly setting up new goals which are attempted before control is handed back to the original invoking mechanism. Davis, Buchanan and Shortliffe [II) use consequent driven rules In the MYCIN medkal diagnosis system. Our first implemtntatlon of the rule based Predictor and Planner closely followed the MYCIN model. However, we are working with more complex, structured data, and have gradually moved to a rather different system.

Our rules have three comppnents; premises (these are the antecedents), side effects and consequents (possibly multiple consequents for a single rule). Rules are indexed on their consequents. The backward chaining strategy fmds all rules which might possibly satisfy the current goal. They are tried in turn until one succeeds. A rule is tried by recursively trying to satisfy its premises, until either one fails (whence the rule ls discarded and the next rule tried), or until all premises have bern satisfied. In this case the side effects are carried out, and then the consequents are asserted - satisfying the original goal. As the name suggrsts, the side effects of a rule have nothing to do with the bas1c goal directed control $tructure.

effects

Figure !i. Producing the Observability Graph.

Fig. !i shows the flow of Information from the ObJeCt Graph to the Observability Graph. The assertion of the consequents places them into Associative Triple Memory (A TM). The general form of a consequent is a triple consisting of an object (not In the Object Graph sense), an attribute and a. value. The attribute Is an $-expression - currently these are used purely syntactically v1a tests for equality, but later semantic information may be explicitly attached; the object mt~ybe a structured fragment of the Object �rt~ph or some entity constructed by the rules. The actual Observability Graph Is produced purely by the side effects of rules firing. The got~ls which direct the control st ructure ue to plt~ce given triples In the ATM. For l n stt~nce the top level got~l for producing the Observability Graph for a model called AIRPORT would be to achieve the triple <AIRPORT,(OBSERV GRAPH), T> in ATM.

In producing the observability graph the Predictor and Planner Is guided by two clt~sses of quasi-invariants. Object class invariants broadly determine the node structure of the Observablllty Graph. The viewing condition invariants determine the detailed contents of the nodes, and the arcs t~ nd relations between nodes. Of course this distinction Is sometimes blurred. For Instance a mixture of the two types of quasi-invariants directs production of the t~rc which st~ys th at runwt~ys should intersect a taxiwt~y in the image. The object model says that they should be connected, and a rule wh ich knows that connectivity Is Invariant under all viewing angles deduces that intersection of the regions corresponding to the nodes will be observable.

5. MATCHING

The M t~tcher uses the Obscrvt~billty �rt~ph generated by the Predictor and Planner to locate an object In a Picture Graph. The Mt~tcher makes an Interpretation Mapping which maps the Observability Graph into the Picture Graph . It uses a goal-directed matching scheme, searching for fet~tures indicated in the Obscrvability Graph . It uses relaxation techniques to resolve constraints iteratively. To improve efficiency, the Matcher works in a coarse to fine order which is directed by the Observability Graph. For ex ample, In Identifying aircraft, the Observability Graph has several levels of detail, first the aircraft context, an airfield , then thl' top level of detail of the aircraft, fuselage ttnd wings. then the finer level of detail which distinguishes ind ividual aircraft, I.e. engine number and placement. The Pred ictor and Planner uses the level of detail of the Object Graph and observabllity criteria to constrain the Matcher's search space.

Nodes of the Picture Graph correspond to ribbons, surfaces, and curves. Its arcs and relations Indicate spatial relations wh ich hold between sets of nodes. We currently use intersection, colinearity, and containment arcs. The classes of nodes and t~rcs tire open-ended to t~ccomodt~te other primitives t~nd relations. Ribbons and curves are obtained from an Edge M ~pper (~cc Brooks [G)) which uses a line finder of Nevatia and Babu [23). Surfaces will be obtained from a Stereo Mapper by Arnold (2).

The Matcher attempts to instantiate each node Qf the Observ abi lity �r~ph by a set of Picture nodes which satisfy propert ies of the Observ~bility Node. These local interpretations map a part of the Observab1lity Graph into a limited pt~rt .of the picture. Context Is expressed as Observability ttrcs and relations among sets of Observability nodes. Local Interpretations consistent with Observability t~rcs form the Initial stage of the Interpretation Graph. For example, a segment of a picture may appear to be t1 runway when it Is considered in isolation. However, this interpretation Is not likely if the proposed runway connects with a freeway syst(m, or has a flow of automobiles upon it . This Information must be encoded In the Observability Graph by the Predictor and Planner.

Each test evt~lut~ted by the Mate her has a pair of procedures, (provided by the Predictor and Planner) one for success a.nd one for failure which t~re invoked appropriately. One possible action of a feature-test Is to cause this match to fail unconditionally - thereby removing the suggested instantiation (e.g. a particular Observability node to Picture node mapping) from consideration. Usual actions simply modify the bookkeeping associated with the "goodness" of the match. Stt~ndt~rd conditions such as Must-Be or Should-Not-Be can be encoded as simple special cases.

The Observability Graph can also specify ways to explain a failed condition. More generally. It ct~n specify consequences of interpretations. For example, an interpretation of a ribbon as a fuselage determines the location of the wings. A conjecture may be made which seems plausible at a preliminary stage of the match. If the conjecture Is later proven to be false, the conclusions it fostered are re-evaluated, a.nd possibly rejected as well. This follows the "Walt and See" philosophy used throughout the matching process.

In the Picture Graph, t1 set of edges may be structured as ribbons In several lncomp~tible ways. An Observability node may map to multiple Picture nod('S and a Picture node may map to multiple Observability nodes. The mechanism for enforcing compatibility is uniform at all levels.

The Mate her has storage and retrieval facilities for finding predesignt~ted common subexpressions. It is probably too costly to automate the find1ng of common subexpressions in the Matcher. The process could be partially automated at the level of the Observability Graph or Object Graph, but is probably ineffective if done in a syntactic way. The problem is NP-complete.

The same basic format and evaluating scheme is used by the Observabllity nodes, arcs and relations as by the full Observability Graph its~lf . An node may further place certain requirements on the arcs and relations in which It participates. This may be used to specify the number of instances of a given arc in which some node may participate - for ex ample, ti Jat a runway should be pa rallel to at most one other runway in a given ai rport. This quanti ficat ion is simple to state and to check. Far more complex conditions could be enforced with this facility. Another feature is the use of a. plethor~ of demons for a variety of cases. There is a growing library or routines, includ ing a transitive closure and a. clique finder, which ct~n be used by the Predictor and Planner as appropriate. The range o( control structures representable in the Observability Graph, and usable by the Matcher currently far outstrips the ability of the Predictor and Planner to produce them.

An Important aspect of the Matcher is its total 1gnorance. It Is a driver function, designed to "ev~luate" the Observablllty Graph In the context of the Picture Graph. A II the specific functions, ordering schemes, demons, etc. are contained within the Observability Graph itself. The only routines in the Matcher, proper, are those which access the relevant data, and which know something about the graph structure used. Extensive revisions are planned for the matcher.

6. CONCLUSIONS

The implementation phase has been underway for approx lmately one year. At the time of writing, ACRONYM had been tested on an example generated by hand from a real lmag·e and is being tested on an example generated completely automatically from real images. The High-level Modeler, the Graphics Generator and the Matcher have been tested extensively and are complete for the full-fledged test without further modification. The Predictor and Planner control scheme is complete - it remains to write more rules encoding the the details of transforming the Object Graph Into an Observability Graph.

The Mate her h01s been tested on a hand coded Observability Graph, matching against a hand coded Picture Graph. This test was used during the debugging phase, and was designed to test all modes of operation of the Matcher. Thm the particular Obsernbility Graph used Is more complex than can be reasonably be expected to be generated by the Predictor and Planner, at least until we have had considerably more experience. The Matcher was programmed to perform scene labeling for a trihedral blocks world . The noclrs of the handcoded observability graph described the possible junctions in a two dimmsional line drawing, following the schemes of Huffman ( 15) and Clowes (I 0). The 01rcs constrained the Interpretations of the two junctions defining a line to give It the same labeling.

The High-level Modeler has been used to construct a large number of models. Figs ~ and 1 show output from the Graphics Generator of two objects modeled Ill the high level language accepted by the Modeler. Many additional models of both industrial parts and airport rrlated scenes have been built with the system. The Modeler and Graphics controll.er are completely interactive, enabling the user to "fly" around airports or manipulate the robot arm.

The Predictor and Planner has been run on both the arm model displayed in fig. ~. and a generic model of an airport. It produced the compltte node structure of the Observabillty Graphs In both cases, and included quantifiers In the airport case. to describe the numbers of allowable numbers of runways and 'taxiways m a valid ilirport Instance.

In April 1979, the ACRONYM system was tested with a simplified model of an LIOII, and iln aerial photograph of an L lOll at St~n Francisco ilirport. It identified an aircraft by locating the fuselage, and two wings without help. Th is wt~s a very preliminary coupling of many of tht. modules of ACRONYM (t~ll were involved except the surface mapper which is not yet implemented). Much more development needs to be done to make the system robust.

Work is proceeding on a smarter geometric editor. It will be a knowledge-based editor, which knows about the sorts of operations a user typically wt~nts to perform. It will thus be able to act <~s an intelligent ;~ssistiltH to a user . So fa r, neither the problems of the intersection of generalized cones, nor a full hidden surface algorithm have been solved bec;~use development of the vision system had higher priority than development of the modeling system. These problems will be tackled in conjunction with the smart editor.

The matcher that Is implemented is very powerful, allowing complex quantifications In Its Input lt~nguag·e . The Predictor ilnd Planner does not yet make full use of Its ct~pt~bilities . We intend to look for a formill descript ion of tile matcher, perhaps modifying It to fit a clean definition of ct~pabilitles . This will give a better handle on the type of rules we should write for the Predictor and Planner and give an estimate on the ultimate capabilities of the ACRONYM system as a whole.