Using Discrimination Graphs to Represent Visual Interpretations that are Hypothetical and Ambiguous

1. lntroduction

A key issue in Computational VJSion is the proper mapping from image features to interpretations. Image features are often highly ambiguous with respect to interpretation. As a result, alternative interpretations for a single feature have to be represented as hypotheses. These hypotheses are instantiations of scene objects and they can be represented by means of an interpretation graph in which each variable (node) represents a hypothesis and the arcs represent constraints between different hypotheses. In a computational vision system the number of hypotheses can be quite large. Hence, the propagation of constraints over the interpretation graph can be a complex and cumbersome operation, because the addition of new hypotheses and invalidation of exist­ ing ones requires a continuous restructuring of the graph.

Most model-based vision systems use specialization hierarchies 2 in an attempt to alleviate this problern . These hierarchies can be used to replace sets of elemen· tary interpretations with a similar appearance in the image by a smaller set of more abstract interpretations. These interpretations are not only hypothetical, they are also ambiguous. They reduce the number of hypotheses that the system has to deal with. Unfortunately, speciali­ zation hierarebiet only offer a partial solution to the interpretation explosion problem. They are natural categorization schemes and many image features allow for interpretations that do not fit into such schemes. For example, a grassy area seen from low altitude could be farm land as well as a golf course and there is no special­ ization hierarchy that joins both concepts into one.

1 Tbe reoearcb reported iD tbil pt~per .,.... c:arried out iD tbc Labaratory for Compatalioaal V'W<>n · tbc Univcnily of Briliab Columbia.

2 For a rcvicw of dift:rcot 111a of opecia!jzatJon bicran:blca, occ [I)

hierarchies in at least two respects. An abstract class often represents elementary classes that cannot be joined in a natural specialization hierarchy. As weU, the tangled structure of the graph means that not all memben of a subdass are automatically a member of a superdass as weU (i.e. no universal implication). At the source nodes, discrimination grapbs represent object classes which are unique with respect to a particular image appearance, but highly ambiguous with respect to interpretation. At the leaves, on the other band, we find elementary classes which are unique with respect to interpretation, but am biguous with respect to their physical appearance.

Discrimination grapbs permit the construction an interpretation graph in wbich each image feature is represented by means of a single variable. This variable is an instance of an abstract object class wbich intension­ ally represents the whole range of possible (elementary) interpretations for the feature concemed. The elemen­ tary interpretations can be represented uplicitly as a set of Iabels in the domain of the variable, or, if we use discrimination grapbs, implicitly by an abstract Iabel. As the interpretation progresses, we can expect an invalida­ tion of some of these Iabels. The variables, however, only represent information that is true for all interpreta­ tions. Thus, invalidation of one Iabel only requires its deletion or replacement . This can be done without changing the structure of the interpretation graph. As weU, all interpretations, hypothetical or ambiguous, are now represented as Iabels in the domain of a single vari­

able.

3. Mapsee-3

Mapsee-3, the sequel to Mapsee-2 [2), is a scbema-based program for interpreting sketch maps. lts schema-based format has been inherited from Mapsee-2. Each object class is represented as a Iist of attribute­ value pairs. The attributes determine its intemal struc­ ture and its relations to other object classes. For exam­ ple, each class has a "components" and "super­ components" attribute which determines its location in a composition bierarchy of objects. The object's location in a discrimination graph, on the other band, is determined by its "discriminations" and "generalizations" attri­ butes . An "instances" attribute lists the current instan­ tiations of the object class. Each instance of an object class inherits the attributes of its parent. A special attri­ bute "Iabel" is used to store the current interpretation

of the instance.

Mapsee-3 interprets sketcb maps such as the one in figure 1. Both line segments and regions have meaning. Line segments can be interpreted in terms of elementary object classes such as roads, riven, shores, towns, mountains, and bridges, whereas regions can be land or water. The input consists of a set of plotter commands which indicate the exact location of each line segment in

the image.

The Mapsee-3 control is subdivided into three stages: segmentation, image-to-scene mapping, and interpretation. A segmentation process results in the creation of sets of connected line segments (called cbains) and regions. The chains form the image features

that need interpretation. Mapsee-3 has a fixed number of sbape categories for describing chains. The image-to­ scene process observes the shape of each individual chain and selects a category in which the chain is placed. Different categories are characterized by features such as dosure, mountain-shape, bridge-shape, and blobs.

Discrim ination graphs form a key feature in the Mapsee-3 design. Each shape category allows for many different elementary interpretations. The discrimination graphs are constructed such that there is a single (abstract) object class for the set of elementary classes allowed by each shape category. Figure 2 shows a simplified example of a Mapsee-3 discrimination grapb. This graph would result from the existence of two shape categories. A closed chain depicts a coastline, lakeshore, or road. Any other line segment depicts a road or river. The leaves of the graph are elementary object classes (e.g. lakeshore, road), the other nodes represent more abstract classes, some of which are unnatural (e.g. road/shore) . AU descendents of road/shore can have the same appearance in the image. The nodes in the grapb with more than one parent can have different appearances in the image~ A road, for example, may or may not be depicted by a closed line segment. Thus, not all roads are roadlshores, some may be roadlriven instead.

The image-to-scene process instantiates the appropriate scene object for each chain. Only one instance is created for every chain. A closed chain, for instance, gets represented by an instance of the class road/shore. The interpretation of this chain is represented by the "Iabel" attribute of the instance. This Iabel is also road /shore, which indicates that all of road /shore 's successors in the discrimination graph are valid interpretations. The image-to-scene process also creates the beginning of the interpretation graph. The instances are the variables, their Iabel the domain. Find­ ing the constraints between instances, however, is the responsibility of the interpretation process.

This paper does not address the question of the construction of the interpretation graph. For such a dis­ cussion the reader is refered to [3]. We therefore only discuss the component of the interpretation process that is concemed with constraint propagation. In Mapsee-3 this process is called discrimination, and it uses the discrimination graphs.

Discrimination is an implementation of a network consistency algorithm called hierarchical arc consistency (h.a.c.) . This algorithm is a derivative of arc consistency as described in [4) . lt maintains consistency between Iabels in the domain of adjacent variables in a constraint graph. Two adjacent variables are considered consistent if all Iabels in the domain of one variable are consistent with at least one Iabel in the domain of the other. If this is not the case then the inconsistent Iabel is replaced. In case of replacement the test is repeated for all variables adjacent to the one in the domain of which the replace­ ment took place. H.a.c. assumes a hierarchical organiza­ tion of the domain of each variable as is the case in discrimination graphs. If a Iabel is inconsistent then h.a.c. will recursively replace it by one of its descendents

in the hierarchy until a consistent descendent is found.

As an example, the road /shon Iabel of an instance becomes inconsistent if both regions surrounding the closed eh ain are constrained to be land. R oad I shore is valid only as long as all of its descendents (see figure 2) are valid. The new constraint invalidates the shore interpretation. H.a.c. replaces this Iabel by using the principle of least commitment, introduced to Computa­ tional Vision by Marr and Nishihara [5). First, road/shon is replaced by road and shore. Next, the con­ sistency of each of these Iabels is tested. Consistent Iabels are tept, inconsistent Iabels are replaced by their successors. In this example, shon, Iaiceshore and coast­ line are all inconsistent. Thus road is the only Iabel that remains. A more detailed discussion of b.a.c. is provided in [3) .

Mapsee-3 solves the problern of uniformity and efficiency as described in tbe introduction. Competing interpretations are all represented as Iabels in the domain of a single variable. Efficiency is achieved in several ways. First, invalidation of a particular Iabel does not result in a structural change in the interpretation graph. Second, the number of Iabels in the domain of each variable can be tept very smaU, thanks to the use of discrimination graphs and the principle of least com­ mitment. Specialization hierarcbies do not offer this capability to such an extent. Third, b.a.c. does not main­ tain an explicit administration of the compatibility between the Iabels of adjacent variables. Only if a Iabel change in a neighboring variable toot place, will a vari­ able test its Iabels. lt will stop this test as soon as a com­ patible Iabel is found in the domain of a neigbbor. In interpretation graphs with competing interpretations represented by different variables, the compatibility between the interpretation of adjacent variables is represented explicitly. As mentioned before, most interpretations tend to be eliminated during the course of the interpretation process .

4. Conclusions

We have described the concept of discrimination grapbs as a uniform and efficient way for representing interpretations that are hypothetical and ambiguous. We have also described a hierarchical constraint propagation algorithm that uses discrimination graphs in an efficient manner to propagate constraints in an interpretation graph. Discrimination graphs and hierarcbical constraint propagation have been implemented in Mapsee-3, a schema-based vision system that interprets sketch maps.

References ·

1. RJ. Brach man, "Wbat IS-A is and lsn't", Proc. of the 4th Nat. Conf. of the Can. Soc. for Comp. Studies of lnteUigence, pp. 212-221, Saskatoon, Canada, 1982.
2. (2] W.S. Havens and A.K. Mactworth, "Representing Knowledge of the Visual World", IEEE Computer, vol. 16, no 10, pp. 90-98, 1983.
3. [3) J.A. Mulder, "Representing Ambiguity and Hypotheticality in Visual Knowledge", Forthcoming Pb.D. Thesis, Department of Computer Science, Univer­ sity of British Colum bia.

(4] A.K. Mactworth, "Consistency in Networts of Rela­ tions", Arrificial lntelligence, vol. 8, no 1, pp. 99-118, 1977.

(5] D. Marr and H.K. Nishihara, "Representation of the Spatial Organization of Three Dimensional Sbapes", Report 377, A.I. Lab, M.I.T., 1976.