Using Discrimination Graphs to Represent Visual Knowledge

This dissertation is concerned with the representation of visual knowledge. Image features often havee many different local interpretalions. As a result, visual interpretations are often ambiguous and hypothetical. In many model-based vision systems the problem of representing ambiguous and hypothelical interpretations is not very specifically addressed. Generally specialization hierarchies are used to suppress a potential explosion in local interpretations. Such a solution has problems, as many local interpretalions cannot be represented by a single hierarchy. As well, ambiguous and hypothetical interpretations tend to be represented along more than one knowledge representation dimension limiting modularity in representation and control. In this dissertation a better solution is proposed. Classes of objects which have local features with similar appearance in the image are represented by discrimination graphs. Such graphs are directed and acyclic. Their leaves represent classes of elementary objects. All other nodes represent abstract (and sometimes unnatural) classes of objects which intensionally represent the set of elementary object classes that descend from them Rather than interpreting each image feature as an elementary object we use the abstract class that represents the complete set of possible (elementary) objects. Following the principle of least commitment the interpretation of each image feature is repeatedly forced into more restrictive classes as the context for the image feature is expanded until the image no longer provides subclassification information. This approach is called discrimination vision and it has several attractive features. First, hypothetical and ambiguous interpretations can be represented along one knowledge representation dimension. Second the number of hypotheses represented for a single image feature can be kept small. Third in an interpretation graph competing hypotheses can he represented in the domain of a single variable. This often eliminates the need for restructuring the graph when a hypothesis is invalidated. Fourth, the problem of resolving ambiguity can be treated as a constraint satisfaction problem which is a well researched problem in Computational Vision. Our system has been implemented as Mapsee-3, a program for interpreting sketch maps. A hierarchical arc consistency algorithm has been used to deal with the inherently hierarchical discrimination graphs. Experimental data show that, for the domain implemented, this algorithm is more efficient than standard arc consislency algorithm.