A Compact Relational Structure Representation

1. INTRODUCTION

The way in which information is represent­ ed is c ritically important to the effectiveness of any system in Artificia l Intelligence. Using a good representation, tasks that would other­ wise be intractable become amenable to solution In machine vision, representations have usually been tailored to specific, small domains. Recog­ nition algorithms have been developed that de­ pend for their effectiveness on specific know­ led~e about the objects in the domain. This paper presents a new representation for describ­ in~ objects. The system is intended to be generally applicable, but was developed primar­ ily for the domain of three-dimensional machine vision. It has also been applied to a second domain, that of spelling co rrection. The pre­ sentation of the system will be in terms of machine vis.lon.

Tlw rl'presl'ntation takPs advantage of similar­ ltil·s In till' descriptions, or models, of ob­ jects. If two parts of an object, or two parts of different objects, have the same description, then these parts are represented by a single description in the representation. The basic idea is to share descriptions that are common within models and across models. vfuen this sharing is accompanied by a comprehensive indexing scheme, it leads to a representation that has many advantages over previous repre­ sentations (e.g. Barrow and Popplestone (1971), Falk (1972), Ambler et al. (1975)) and suffers few disadvantages.

Some constraints were placed on the implement­ ation of the system. The first constraint was that the descriptions of objects should be acquired automatically from visual data. This is a sensible constraint because it allows the domain to be changed easily and confronts the problems of representing objects from the real world, rather than those of representing arti­ ficially-created objects. The second constraint was thatthe representation should not be domain­ dependent. It should be possible to change or expand the domain with as little effort as possible, and the information known about ob­ jects should be acquired entirely from the objects themselves rather than being partly dependent on built-in assumptions about the domain. This constraint would be usL·ful in a robot assembly domain, where different assembly tasks might use widely different parts. Instead of having to re-program the system for each ne~r task, it would be preferable for it to acquire descriptions of the parts visually.

Some of the problems to be confronted when a representation and a recognition system are being designed become amenable to solution in a more natural way using the new representation than using earlier representations. It becomes easier to compare descriptions of objects, the domain of objects may be changed or expanqed with very little effort, and the problems of matching symmetrical objects disappear. There is a great deal of flexibility in the choice of how to describe objects, and the form of the representation makes recognition of objects easier.

A recoenition algorithm based on the represent­ ation has been developed and implemented. It makes use of the form of the representation to enable it to recognize objects in a robust and efficient manner. An earlier version of the algorithm appears in Shneier (1977). It is dis­ cussed in more detail in Shneier (1978), and examples are presented of its use in three­ dimensional vision and in spelling correction.

2. COMPACT MODELS

The approach taken here differs from earlier work in two major respects. The first differ~ ence concerns the nature of models. Those authors who have previously made use of models of objects (e.g. Falk (1972), Barrow and Pop­ plestone (1971), but not Waltz (1975)) have given the term "model" certain implicit char­ acteristics. A model has been defined as a description of an object with a one-to-one relationship between parts of the object (e.g. edges, surfaces, volumes) and parts of the model. For example, the model for a cube con­ sists of a separate description of each of the six sides of the cube, and of relationships between the sides.

There are a number of reasons why this concept of model, while natural, is not the best for machine vision. It means that each model has to be treated as a separate entity because there is no sharing of structure between models or parts of models. Most systems have performed matching separately on each model in turn, with models being rejected one by one until a match was found. It was desired to be able to match with all possible models in parallel, finding the best match in the most efficient manner possible. Grape (1973) attempted to match in this way by compiling a central list of feat­ ures against which to match. He was not en­ tirely successful, however, because he had to match against each element of the feature list in turn.

Another reason for re-examining the notion of model concerns the analysis of models of sym­ metric objects. Underwood and Coates (1972) were unable to deal with symmetric objects because of problems of finding the correct correspondence between parts of the scene and parts of the model. Other authors have had to content themselves with finding all possible correspondences between the scene and a model, and then choosing one of these arbitrarily (e.g. Barrow and Popplestone (1971), Ambler et al. (1975)). The problem arises because the model of a symmetrical object contains several parts that are described in a very similar fashion. When an object model is being con­ structed from several views, it is not clear when to construct a new part in the model and when to assume that all parts have already been seen. Similarly, when trying to recognize an object, it is not clear which of a number of parts of a model should be matched against a scene fragment. If the system is to work in a world of man-made objects, it seems advisable to be able to handle symmetry in a more accept­ able manner.

Our solution to these problems with models is to broaden the concept of a model. A model is defined as a collection of descriptions of the kind of parts that make up an object and the set of the relations between them. There is no requirement of a one-to-one correspondence be­ tween object parts and model parts. Rather, there is one model part for each disti~ish­ ably different object part. This is similar to systems of mathematical logic, where a model is a collection of axioms describing a world, and where no axioms are repeated,

So, for example, a model of a cube consists of only one part description--that of a square plane. Relations are defined between instances of the part, so that a form of relational structure is the basis of the representation.

Figure 1 depicts the difference between the conventional relational structure model of a cube and the model described in this paper. The conventional model has one node for each surface iri the cube, whereas the new model has a single node describing all the surfaces. Similarly, while there are many relations de­ fined between the surfaces in the conventional model, the new model needs only a single rela­ tion to represent them all. There is a great saving in the size of the model.

In fact, the models are even more like those of the logician than has been described so far. A logician describes a whole world with one set of axioms. Similarly, the models in this rep­ resentation all share one structure, instead of the usual separation of models of different objects. The advantages of such a system are manifold. Matching is enormously simplified and matches occur with all possible models at once. Models are compact and are easily comp­ ared. Similarities are evident in shared struc ture, and differences are reflected by structure that is not shared.

The second difference between the new system and earlier work is more specific, and arises as a result of the formulation of the models as relational structures. A relational structure is defined as a set E of elements, together with a set of properties P and a set of rela­ tions Rover E (Ambler et al, 1975)). Scene analysis based on relational structures has been concerned with ithe following kind of matching: Given two relational structures <E 1 ,P,R> and <Ez,P,R> define a match between them as a set T1~1. a set Tz~z, and an isomorphism between T1 and Tz preserving properties and relations. That is, e 1 ~e 2 implies p(el) iff p(ez) for each pEP. Also, e1~ei and ez-ez implies r(el,el) iff r(e2 ,e2) for each rER. A match represents a common substructure in the relat ional structures.

This definition will be changed to allow the two relational structures to have a different relationship. For recognition, the structure of models and the structure obtained from the scene being recognized are described in terms of dif­ ferent basic elements. That is, the structure obtained from the scene (called the scene graph) represents the parts of the scene as they actu­ ally appear, whereas the structure of models (the graph of models) represents a meta-descrip­ tion of the objects possibly in the scene. Several parts of the scene graph may map into a single node of the graph of models. There is an isomorphism from the scene graph t o a struc­ ture derived from the graph of models, but not t o the graph of models itself. The structure derived from the graph of models is a conven~ tiona! relational structure with each part of the object described individually, even if the parts have similar descriptions. Relations between the parts are also made explicit.

Thus it is necessary to distinguish three levels in the representation. There is the represent­ ation of the actual sense data in the scene graph, there is the structure representing the models of the objects known to the system, and in between there is a structure instantiated from the graph of models to aid in the analysis of the pa rticular scene being studied. The relationship described above for matching rela­ tional structures holds between the scene graph and the intermediate structure, but this inter­ mediate structure is only one of many possible such structures that can be instantiated from the graph of models.

Winston (1975), with his TYPICAL-MEMBER labels, went some way towards this position. He did not explore the potential of such a representa­ tion, but relied on the conventional structure representation.

3. REPRESENTATION

A representation has been implemented that is simple to construct and is powerful enough to describe a large class of objects. The repre­ sentation is based on primitives and relations. Ideally, primitives could be descriptions of any scene elements that are easy to extract, have a canonical description, and have sufficient vari­ ation to allow the representation of an inter­ esting class of objects. A small set of easily calculated relations is desired that succinctly describe the relationships between instances of the primitives in an object.

Relations are stored as schemata; their argu­ ments are abbreviated surface descriptions in­ stead of full surface descriptions. The form of the representation is a network whose nodes are primitives, and in which an arc is drawn between nodes if a relation is defined between the primitives at those nodes. Arcs are lab­ elled with the set of relation schemata that justifies them. An object will be described by some set of these nodes and arcs, but many nodes and arcs in the network may be common to several object models. A primitive is repre­ sented by a single node, so should an instance of a primitive occur in-several objects, the models produced from these objects would share that node. In addition, models may share relations, should common primitives occur in similar relationships in both models. The only thing that two models may not share is a name.

The network for the two objects of Figure 2 is given in Figure 3. The objects are a cube (called "cube"), and a ·rectangular parallele­ piped ("rect") whose model shares a side with the cube.

Definitions

The definitions are of the terms used to des­ cribe the representation. They ar.e in terms of labelled graphs.

1. Let P = [pl,p 2 , ... ,pnl be a set of primi~ tives. Each Pl forms one (and only one) node of the graph.
2. Let R =(r1,r2·····rmlbe a set of relation schemata. Each r1 is of the form: <function name, arg 1 ,arg2, ... ,argn,value>. The arguments arg1, arg2, ... ,argn are typed variables which may take as values instances of individual elements of P (possibly repeated). The value FALSE (0) is not con­ sidered legal for a relational schema. The labels on the arcs of the graph are sets of relation schemata, subsets of R, called label sets.
3. Let M .. (n 1 ,n2 , .·. ,nk) be a set of names of models.
4. The graph obtained from modelling objects is called the graph of models.
5. A model in the system is represented by a subgraph of the graph of models. The nodes in the subgraph are those primitives that occur in the model. The arcs in the sub­ graph are those that have relation schemata in their label sets that occur in the model. The label set of an arc in the subgraph consists of the subset of relations that occur in the model.

A rich indexing structure is maintained by the representation. Each primitive indexes the models in which it occurs. If a primitive for~ part of the description of an object, it must index the model for that object.

Re~ation schemata index the models in which they occur and the primitives that form their argu­ ments. To test whether or not a relation is satisfied requires finding instances of its arguments, while to derive any benefit from sum a test requires that the information obtained be available to the models that can use it.

The models index both the primitives that form their parts and the ;relation schemata that describe how the parts are related.

4. THE MODELLING PROCESS

4.1 Extraction of s ur f aces

The i mplementa t ion di s cussed here makes use of range data obtained f rom a triangulation rang­ ing system (Popplestone e t al. (1975)). An ob­ ject to be modelled is placed on a turntable (Figure 4). The object is passed under a plane of light, and scanned a t fixed intervals. When the scan is complete, t he object i s rota ted by a known amount, and scanned aga i n. This pro~ cess is repeated until all desi r ed views of the object have been scanned (Figure 5).

(a)

(c)

(b)

( d )

Figure 5

The result of processing the data obtained in this way is a set S of surfaces, each described by:

1. The surface type (plane or cylinder).
2. The equation of the surface.
3. The three-dimensional coordinates of the centroid of the surface.
4. 4 . The radius of a cylindrical surface.
5. The segments of lines that make up the surface.

Some further proces§ing is done on this infor­ mation before a model is produced. The aim of this processing is to derive simple, non­ coordinate-specific information about the sur­ face, which can be used to form primitives. The information chosen is a measure of the dimen­ sions of the surface.

4 . 2 Primitives and relations

From the set S of surfaces, a list P' of surface descriptions is constructed, one for each sur­ face. Elements of P' may be repeated. The elements of P' will be used to construct the set P of nodes in the graph of models. The descrip­ tions are constructed from the surfaces by ex­ tracting the type of surface and its dimensions. All coordinate-specific information is discarded when forming the descriptions. This information is, however, still available to the rest of the system, and will be used to construct the rela­ tion schemata. At the same time, the set

SP = {<s,p> sES,pEP}

of pairs of surfaces and their associated des­ criptions is constructed. SP links the surfaces in the image with the descriptions in the model world. The three-dimensional positions of the surfaces and their relationships with other sur­ f aces will be used in building the mode l.

The next step is to determine the relationships between the surfaces in the objec t being mod­ elled. In the implementation, relations have been restricted to having at most two arguments, for ease of acquisition and because the number of relation schemat a produced for n-ary rela ~ tions can be very large. In practice , binary relations are adequate for the domains under considera tion, a lthough Shneier (1978) presents an argument t o show that this is not true in general .

The choice of the relations with which to model an object is left to the user, who lists the names of the functions to be applied at the time the model is constructed. The use of a relat ion requires that an executable function exist which can calculate values for instances of its arguments. A number of different func­ tions have been used in experiments. Some of these are:

ADJACENT: If the light plane in some subscan passed over both surfaces at the same time, and the line segments produced by the light plane were touching, then the surfaces are adj acent.

RELDIST: The distance from the centroid of one surface t o that of another.

RELANGLE: The angle between two surfaces, from the viewpoint of the first.

Whereas ADJACENT is a true relation, in that it has values "true" or "false," RELDIST and REL­ ANGLE can have a large number of values, each of which will give rise to a new schema when it is encountered in an object being modelled. (There will not, however, be an infinite number of such values, since a range of values which are sufficiently similar will be grouped into an equivalence class.)

The schemata are constructed as follows. For each pair of surfaces in S, the chosen set of functions is applied. The result of the appli­ ca tion is used as the expected value slot in the schema. The name of the function that was applied is the value of ·the function name slot, while the argument slots are filled by the descriptions tha t correspond to the surfaces used in the evaluation. The correspondence is obtained from the set SP ·of pairs of surfaces and their descriptions. Using abbreviated des­ c riptions, rather than full surface descrip­ tions , generalizes the relations to make th~m valid for all surfaces that match the abbrevi­ ated descriptions. If the value of the func­ tion is FALSE (0), a schema is not constructed.

4.3 Producing the graph of models

At this stage there is

1. A list P' of surface descriptions.
2. 2 . A set of relation schemata.
3. A model name.

This informa t ion must be i ntegrated into the graph of models. Any new information should be retained, but duplication or spurious arcs should not be introduced.

Each of the descriptions in P' is matched against the primitives in P, the set of nodes of the graph of models. Only if there is no match (i.e. if a description is sufficiently different) is a new primitive node created for the description and added to P. Primitives are described in exactly the same way as surface descriptions, but there is only one primitive with a particular description. The result is a set PuP' of primitives. Matching requires that the surface types be the same in the prim­ itives and the surface descriptions, and that the dimensions be within some fixed tolerance of each other (currently, dimensions are allowed to vary by about 20% before the match fails).

When a surface description matches with a prim­ itive already in the graph, the values of the primitive in the graph are updated. The mean of each description in the surface and thE primitive becomes the dimension for the primi­ tive in the graph.

The name of the model is added to the set of names if it is not already a member. The new set of relation schemata is added to the set R of schemata that already exist as follows. If a new schema is not already a member of R, it is added to R, and indexes only the new model. If a relation scheme alneady exists in R, it is not duplicated. Instead, the schema is altered so that it indexes the new model in addition to any others it might already index. The model indexes the primitives and relation schemata that occur in it, and the primitives index the new model.

4.4 Example

Figure 4 shows a picture of a toy car resting on the turntable. The car was scanned by the ranger, rotated through 90 degrees, and scanned again. This process was repeated four times , giving four views, each perpendicular to its predecessor. The four views cover all sur­ faces of the car except its base (Figure 5).

After scanning the car, the range map produced from the scans is processed to find the sur­ faces of the car. There are seven of these, corresponding to the roof, two sides, back, front, windshield, and bonnet of the car. Some of these surfaces were visible in more than one view of the car. The r oof appeared in all four scans, and the bonnet in three (Figure 5). Notice that the sides of the car appear smooth because the axle holes were not large enough to be perceived by the ranger.

From the set of surfaces, the program must pro­ duce a description of the car. To be able to do this, three pieces of information are nec­ essary. The first is a name for the object-­ it will be called "CAR". The second require­ ment is a file containing the surface data, and the third requirement is a list of functions to be applied to pairs of surfaces to produce the relation schemata. In this example, a single function that finds ADJACENT relationships between surfaces will be used.

The first thing that the program does is to work out descriptions for each surface. It finds the type of the surface (in this example, all surfaces are planes) and two numbers that describe the dimensions of the surface.

When the program tries to find the dimensions of the roof of the car, it ~iscovers that there are several views of the surface, that is, the roof was scanned more than once by the ranger. Each of these views is processed separately, and the results are merged. The bonnet of the car is treated similarly.

Having described the surfaces, the next stage is to construct the relational structure to descr i be the object. First, the program exam­ ines the surface description. If two descrip­ tions are similar, they are represented by a single primitive node (PRIMITIVE) in the graph of models. In the example, three primitives are found to be sufficient to describe the seven surfaces. This is less than half the number that would be required by a conventional representation, illustrating the compactness of the representation. The three primitives des­ cribe the following surfaces:

Primitive Pl describes the roof and back of the car.

Primitive P2 describes the windshield, bonnet, and front of the car.

Primitive P3 describes the two sides of the carM

The dimensions stored for each of the primitives are the means of the dimensions of each surface that matched with the primitive. In addition to describing the surfaces, the primitives also index the model CAR of which they are parts.

The next step in building the model is to link the primitive nodes by means of ADJACENT rela­ tion schemata. An arc is constructed between two nodes if any of the surfaces described by one of the nodes is adjacent to any of the surfaces described by the other node. Thus, the side of the car is adjacent to the back of the car, giving rise to the schema <ADJACENT Pl P3 ]>. The side of the car is also adjacent to the roof of the car, but this gives rise to the same schema, because the roof and the back are des~ cribed by the same primitive and one schema is used to represent both relationships. All pairs of surfaces are examined, and five relation schemata are found sufficient to describe the relationships between the surfaces in the car.

The three primitives and five relation schemata, together with the name of the car, are all the information needed to model the car (Figure 6).

Note that the bottom of the car was not scanned, and so does not appear in the model. To incor­ porate it, two sets of scans would be necessary. The model as shown would first be constructed, and then another set of views of the car, this time on its side or its roof, would be produced. Presenting the modeller with the new set of views and the old object name would result in the model for CAR being updated to include the new surface and any new relations that were discovered.

The situation is more complex when several ob­ jects are modelled. If the descriptions of some of the surfaces of an object being modelled match with primitives already in the graph of models, the new model will share that primitive in the graph. The node is made to index the new model in addition to any others it already indexes. Similarly, relation schemata may be shared by several models, and must be indexed accordingly.

5. DISCUSSION

The advantages of the representation are as follows. The representation is compact because nodes are shared by parts of several objects . This allows the space required to store models to be reduced, and has valuable implications for recognition. Models can be constructed easily from visual data, and new models can be inte­ grated into the network without affecting those models already in existence.

Because of the sharing in the structure, all models that are described by a part of the structure are made available simultaneously when that part of the structure is accessed. Instead of matching with each model individual­ ly, all of them are available at once and the work that is done to discriminate between mod­ els can be tailored by the context. This allows less work to be done when a scene is analyzed.

The representation is flexible. It was easy to change the domain to which the system was ap­ plied from three-dimensional vision to one­ dimensional spelling correction without chang­ ing the form of the representation. It is also possible to describe objects within a domain in different terms.

The ability to compare descriptions is one of the criteria for a useful recognition. In the past, objects have each been described separ­ ately and compared by finding correspondences between two structures. In the representation presented here, a single structure is shared by all models, with parts of models that are sim­ ilar being represented by the same part of the structure. Thus, instead of painfully comparing two structures and finding points of corre­ spondence, the single structure can be examined and similarities and differences between object models can be found immediately. Similarities are indicated by shared structure, and differ­ ences are indicated by structure that is not shared.

An important requirement for a representation and recognition system, especially one that is to work with man-made objects, is an ability to deal with symmetry. Many objects have some degree of symmetry, and this has led to prob­ lems in previous systems. The difficulty arises when a symmetrical object is matched with its model description. It is not clear what parts of the object should be matched with what parts of the model because there is no:unique way of matching when several parts have the same description. This problem has either been avoided by not allowing symmetric objects in the domain (Underwood and Coates (1972)), or it has been solved by resorting to finding all possible correspondences between the object and its model and choosing one of them (e.g., Barrow et al. (1972)). When there is a large amount of symmetry, as in a cube, this method can be very expensive. Using the representation in this paper, the problem of symmetry disap­ pears. There is a single description for all the similar parts, so that there is no confusion when matching. Symmetric objects can thus be recognized with the same effort as non-symmetric objects.

The representation has been successfully applied to two domains. The first, machine vision, used surface descriptions as primitives, and rela­ tions like adjacency. The second, spelling cor­ rection, used letters as primitives and ordering relations like "precedes" and "follows". Shneier (1978) provides a full discussion of each domain. He also discusses an elegant recognition algorithm that takes advantage of the form of the representation in its analysis. The modelling and recognition systems have been fully implemented and tested. Their performance underlines the advantages of the compact repre­ sentation.

6. CONCLUSIONS

This paper has presented a new representation that takes advantage of similarities in the descriptions of objects. By sharing descrip­ tions that are common within models and across models, a compact representation was obtained that had numerous advantages over other repre­ sentations. The system was implemented and applied to two domains, those of machine vision and spelling correction. In both cases, it proved possible to represent. the objects in the domain in a compact manner that was especially useful for recognition. The simplification of the representat~on is a direct result of a generalized concept of model.

ACKNOWLEDGEMENTS

I am grateful to my colleagues in the Department of Artificial Intelligence at the University of Edinburgh for their assistance in this work, to Azriel Rosenfeld for his comments and suggest­ ions ori the form of this paper, and to the University of Witwatersrand who provided finan­ cial support.