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

Abstract

Model-based vision systems must be capable of dealing with large quantities of hypothetical interpretations. Hypothesise-and-test methods often lead to combinatorial explosions of possible inter-pretations. Discrimination graphs prevent such explosions by im-posing a hierarchical organisation on the domain of interpretation. Such an organisation effectively reduces the number of interpre-tations that the system has to deal with. This paper presents an algorithm which automatically constructs discrimination graphs. 1 In t roduc t i on 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