An Algorithm which Automatically Constructs Discrimination Graphs in a Visual Knowledge Base

1 Introduction

If we are to develop a ·general-purpose· vision system which can take as input a digitised picture of any natural scene and which produces as output a meaningful description of such a scene, then we must equip the system with a representation which allows for a quick and smooth access to domain-specific knowledge. Most model-based vision systems obtain access to the knowledge base of a particular domain after a segmentation process has scanned the image in search for particular features. The description of these features imposes constraints on the interpretations possible. Features, constraints, and interpretations can be represented as a graph (or hypergraph) with the features (n) as variables, each with an associated domain of interpretations {d), and the constraints (e) as relations. The problem of finding globally consistent inter­ pretations for the image then becomes the problem of finding all possible n-tuples such that each n-tuple is an instantiation of all n variables satisfying the relations. This problem is equivalent to the constraint satisfaction problem [Sj. The existence of algorithms which can solve this problem in less than exponential time has been questioned. Depth-first backtracking, for instance, is of O{ed") in its worst case performance [Sj. Such an algorithm causes a major problem for a general-purpose vision system in which we can ex­ pect domain sises to be very large, because no advance knowledge exists of the domain of interpretation.

The research for efficient solutions to this "exponentiality· prob­ lem has taken several directions. The search for more efficient algorithms, among other things, has led to algorithms that do "intelligent backtracking" [11 and to so-called network consistency algorithms [3j. The latter is a group of polynomial time algorithms which do not necessarily solve the constraint satisfaction problem, but which eliminate all local inconsistencies that cannot partici­ pate in a global solution. Network consistency algorithms will gen­ erally reduce the overall domain sise. This makes them attractive as pre-processors for algorithms such as depth-first backtracking. Recent research has focused on a more effective organisation of the domain of each variable [7j. A hierarchical organization can be imposed on the domain by means of discrimination graphs.

2 Discrimination graphs

Discrimination graphs are based on the assumption that we can classify image features in one or more dimensions (e.g. shape, by

Jan A. Mulder

Department of Mathematics, Statistics, and Computing Science Dalhousie University Halifax, Nova Scotia Canada B3H 3J5

texture), the result of which is a finite number of categories for each dimension. Discrimination graphs (DG's) are based on a (potentially unnatural) categorization of object classes that be­ long to a particular image feature category. A DG is a directed, acyclic graph. Every source node of the graph is an abstract ob­ ject class which intensionally represents all the elementary object classes that belong to a particular image feature category. The leaves of the graph are elementary object classes. Intermediate nodes represent subsets of the set of objects represented by their ancestor(s).

This paper does not provide an in-depth discussion of DG's. The idea of imposing a hierarchical domain organisation by means of DG's was first presented in [7j, an in-depth discussion is pro­ vided in [8j. Intuitively, DG's are useful because image features can have a wide variety of interpretations for which no hierarchi­ cal organization exists. For instance, a collection of green pixels in an aerial photograph can be farm land, a golf course, or even the astroturf in a stadium. Because no natural categorisation scheme exists for such interpretations we cannot use a specialisation hi­ erarchy as a means of replacing these interpretations by more ab­ stract ones. DG's enable us to impose a hierarchical organization on an arbitrary set of natural objects.

. "·· .

Figure 1: an example of a discrimination graph

Figure 1 shows a DG for a simple character recognition prob­ lem. The image consists of one character which is a letter con­ taining horisontal and vertical line segments only. Each letter is classified in two different ways: by the orientation of strokes and by the number of strokes in a particular orientation (table 1) . Recog­ nition takes place in steps. The strokes are the image features and they are investigated one at a time. The DG constructed for this situation reflects this process. The source nodes of the graph are on the left and they represent the possible set of interpreta­ tions after investigation of one stroke. Their successors represent the (sub)set of interpretations after two strokes have been inves­ tigated. The leaves represent the interpretations possible after all strokes have been looked at. All interpretations (abstract or nat­ ural) are labeled (e.g. d1). The constraints associated with each interpretation are shown as well. For instance, interpretation d6

represents allletten with at least one horisontal and at least one vertical stroke. The )etten E, F, H, L, and T satisfy this constraint.

DG'a have been implemented in Mapaee-3, a sketch map inter­ pretation program [8] . Sketch mapa are a useful domain for study­ ing the theory, design, implementation, and evaluation of different knowledge representation schemes [4,2,8].

DG'a allow ua to replace a large aet of natural interpretations in the domain of each variable by a much smaller aet of abstract in­ terpretations. A network consistency algorithm called hierarchical arc coruutency has been designed and implemented which operates in hierarchical domains [6]. This algorithm testa the consistency between the interpretations of adjacent variables. Inconsistent in­ terpretations are replaced by their succesaon in the graph after which the consistency teat is repeated. This teat-replacement se­ quence continues either until a consistent interpretation is found, or until each variable's domain is empty. Only a very small part of the interpretations in the graph need to be considered in this replacement operation. The worst case complexity of hierarchi­ cal arc consistency is O(ed 3 ) . However, a few simple constraints improve this to O(logd(e + (3n/2))) [6]. The combination of hier­ archical arc consistency with DG'a provides a quick and smooth transition from abstract and domain-independent interpretations near the top of the graph to the more domain-dependent interpre­ tations at the leaves.

3 Constructing discrimination graphs

How do we construct a graph auch as the one in figure 17 The graph ia baaed on 3 premiaea: an explicit representation for each natural interpretation (the leaves), an explicit representation for each possible combination of constraints, and an explicit repre­ sentation for. the addition of a single constraint (the arcs) . This results in the creation of 14 feature categories (F1 , ... . ·· .... · , Fa) each with a aet of possible interpretations. For each one of these seta we create a single abstract interpretation: d1 corresponding to F1 , ~ corresponding to F2 etc. The feature categories are also inter-dependent. For instance, the interpretations of Fe can only result from the interpretations of F2 · For the construction of fig­ ure 1 we therefore need several knowledge sources, among which are an explicit representation of the feature category dependen­ cies and the information represented in table 1. The former tells us which transitions between feature categories are legitimate, the latter informs ua which transitions are meaningful. Based on this information we can construct figure 1.

The presence of ao many abstract interpretations, among other things, requires an algorithm that automatically constructs DG's. Indeed, the value of using DG's would decrease if this could not be done. However, we would like such an algorithm to be domain­ independent, that ia, not dependent on an intimate knowledge of feature categories and their dependencies. The graph in figure 1 is optimal in the sense that all possible combinations of interpreta­ tions are explicitly represented and the addition of a new constraint in the image Jeade to a single transition in the graph. Perhaps, it ill p0111ible to design a domain-independent algorithm which does not neceuarily lead to an optimal graph, but which still constructs a usable one.

For one thing, the graph in figure 1 is redundant in the sense that several feature categories have identical interpretation aets. The graph is constructed such that the relation between offspring and their parents is the subset relation. Subsets represented by dif­ ferent offspring may overlap. The algorithm we propose makes no assumptions about the feature categories. It orders the categories by the aetaise of their interpretations and it merges categories with identical interpretations. An abstract interpretation ia created for each category. The abstract interpretations with the largest setsiae become the source nodes of the DG. The graph created is binary and the subsets represented by the two offspring of each abstract interpretation are disjoint .

The start point for construction ill a given feature dimension

FD consisting of n categories (F) with a total of a (natural) in­ terpretations (S). Each category F; (1 :5 i :5 n) has a aet I; of possible interpretations (I; E S). The aiae of I; may vary from cat­ egory to category and a particular interpretation S; (1 :5 i :5 s} may occur in more than one category.

The construction algorithm operates as follows:

1. Merge the categories with identical interpretation seta. F is now of size m (m :5 n) .
2. For each F; (1 :5 i :5 m) create an abstract interpretation A;. A; intensionally represents the set I; of pouible inter­ pretations for F;.
3. Order the abstract interpretations by the setsiae of their nat­ ural interpretations. The interpretation with the largest set­ aile comes lint. Call this ordered list L. The abstract inter­ pretations form the elements in thill list.
4. Do until L is empty:

Take the first element I from L and delete it from L.

Find the element in L that represents the largest subset of I. Call thill element /t.

H the aetsise of It is leu than the integer part of

H the aetaise of I > 1 then do: half the aise of I then execute step i else execute step ii.

1. Split the set represented by I into two dilljoint sub­ sets of approximately equal aiae, and create two new abstract interpretations Is and 14 · Each of these interpretations represents one of the aubaeta. Establish a link from I to ita two siblings and insert the siblings into L at a location that corresponds to their aetaiae.
2. Find the interpretation l2 representing the exclu­ sion of the seta represented by I and 11 · H this interpretation does not exist then create it and in­ sert it into L at the proper location. Establish a link from I to its siblings It and l2.

Application of the construction algorithm to the character recog­ nition problem results in the graph illustrated in figure 2. Identical interpretation sets cause a reduction in the number of feature cat­ egories. Figure 2 shows the 11 interpretations created with the following correspondences (in parentheses) to figure 1: d1 (d1 ), ~

(d3 }, d3 (~,d5 ), d4 , d5 (d4,d7), de (da), d7 (do), ds (du), do (dt2), d10 (d10,da), and d11 (d13). The interpretation with largest set­ aiae, d1 , becomes the source node. d1 ill linked with d2 and ds, both of which already exist. Actually, the algorithm usee existing interpretations ahnost all the time with the exception of d4 which is newly created. All the aplite are caused by atep 4ii. The set EFHLT could also have been split into the subsets EFH and LT.

Figure 2 is no longer an optimal graph. All possible combi­ nations of interpretations are still explicitly represented, but the addition of a new constraint now sometimes requires more than one transition in the graph. For example, the transition from d1 to d4 in figure 1 now requires 3 transitions from d1 through d3 and d4 to d5 · The trade-off between figure 1 and 2 is the tradi­ tional space-time trade-off. Space-wise figure 2 is more efficient, but accessing the proper interpretation (sometimes) requires more time.

This paper cannot provide an extensive discussion of construc­ tion issues. Many of these are addressed in [8] . Suffice it to say here, that the construction algorithm presented above can also be used in knowledge bases which are organised along composition and specialisation hierarchies. In the Mapsee-3 program, for in­ stance, objects are represented at different levels of composition and specialisation. The natural interpretations for each feature category are the leaves of a composition hierarchy. The construc­ tion algorithm constructs a DG at the composition leaf level. A projection algorithm then iteratively projects this graph from one level of composition onto the next level up, thereby constructing an abstract composition hierarchy and a DG at each level of com­ position. This projection algorithm is also discussed in [8] .

4 Conclusion

Discrimination graphs are a useful tool for imposing a hierarchical organisation on domains which cannot be naturally organised in this way. In combination with a hierarchical arc consistency algo­ rithm, discrimination graphs provide a quick and smooth access to domain-specific knowledge. This paper has presented an algo­ rithm that automatically constructs discrimination graphs from a set of naturally interpretable feature categories.

5 Acknowledgements

Comments on a draft of this paper by Jay Glicksman and Bill Havens are gratefully acknowledged. This research was supported by NSERC operating grant A0948.