Model-Building in the Visions System

II. MODEL-BUILDING IN THE VISIONS SYSTEM!

Thomas 2 Williams, John Lowrance, Allen Hanson , and Edward Riseman Computer and Information Science Department University of Massachusetts Amherst, Massachusetts 01003

Abstract

The semantic interpretation system of VISIONS receives a segmentation containing symbolically encoded regions, boundaries and endpoints. The model-builder consists of four major components: 1) multiple levels of representation for both the image-specific model and long-term general know­ ledge, 2) a set of modular knowledge sources, 3) a hierarchical modular strategy to control application of the knowledge sources, and 4) a tree representing the current state of search through the space of possible models.

Multiple Levels of Representation

A model can be viewed as a set of short-term instantiations of long-term general concepts rela­ tive to the current environment [Williams and Lowrance, 1977). This suggests that visual know­ ledge should be subdivided into a short-term-image­ specific model and long-term general knowledge components. Visual knowledge also includes infor­ mation at many levels of abstraction [Erman and Lesser, 1975; Hanson and Riseman, 1976). The primary levels of representation include frames of stereotypical situations [Minsky, 1975), the objects in those scenes, the volumes and surfaces of those objects, and the regions, boundary seg­ ments and endpoints of those surfaces. An example of an instantiated element (short-term) in the model would be a node (OBJl) representing an association between a region (Rl) and a long-term general concept (TRUNK).

Processes as Modular Sources of Knowledge

The model-building processes are viewed as modular Knowledge Sources [Erman and Lesser, 1975). KS's are- responsible for the generation/verifica­ tion of hypotheses. Typical KS's include attribute matcher, perspective, shadow, occlusion, shape, etc. KS application is controlled by the model­ building strategy in the search for a satisfactory model.

Hierarchical Modular Control Strategy

The complexity of the image interpretation task, in general, necessitates the integrated application of many different processes. A hier­ archical modular control structure (Figure 2) provides a powerful tool for exploring the large number of potentially interesting strategies for using these processes. ·

A model-building strategy is a selected con­ figuration of modules from the model-builder library. The strategy must determine which model in the model search space to expand, which level of representation within the model is to be selected, and which theory (i.e., node) at the selected level will be expanded.

1 This work was supported by NSF grant DCR75-16098 .

2 A. Hanson is affiliated with Hampshire College,

Amherst, Massachusetts 01002.

At each level of this hierarchy the hypothe­ sis-test paradigm is implemented as a sequence of three ~ of control modules: 1) FOCUSing on an appropriate aspect of the task, 2) EXPANDing that aspect by generating new hypotheses,~ 3) VERIFYing those hypotheses. Each control module makes strategic decisions at its level determining which lower level control modules and/ nr KS's to apply. For example, the model search space expander calls: 1) a model focusser (strategy to select a partially developed model from the search space), 2) a model expander (strategy to hypothesize an· incremental change to the partial model), and then 3) a model verifier (strategy to determine the correctness of a hypothesis).

Model Search Space

The current state of the search is represent­ ed as a tree of partially constructed models, where each node contains an incremental change from its parent node. In addition, a sketch of the history of construction for each model will be stored. This history might include an indication of the KS's and the strategy modules primarily responsible for each hypothesis, as well as any portions of the model on which the decision was dependent. This information will be used to· care­ fully analyze and understand the modelconstruction process during system development. Eventually it will be used by the strategy in making its

decisions.

Implementation

The representation and manipulation of both information and processes in the high-level por­ tions of VISIONS is supported by a system of data and procedural primitives. This system currently consists of a library of default control modules, a graph processing language [Lowrance, 1977), and a relational data base [Konolige, 1977). All of these are implemented in ALISP [Konolige, 1975),

the UMass version of LISP.