A Procedural Model of Recognition

1. Introduction

This work is based on the belief that a comput­ ational theory of perception must encompass dual theories of representation and recognition. We propose a proc~dural model of recognition which 1) provides a mechanism for flexibly integrating top­ down and bottom-up control structures, 2) supports the use of a hierarchy of model driven methods, and 3) defines a deductive process scheduling mechanism.

2. The Chicken and Egg Problem

The top-down recognition model proposed by Minsky(l974), championed by Kuipers(l975), and used by many others exhibits a number of short-comings: 1. A frame must explicitly be made the current hypothesis before its expertise is available to the recognition process.

2. An ordering must be placed on alternative subgoals. The top-down paradigm forces the choice of a single, hypothesis at a time. The mechanism for choosing a next hypothesis is completely failure driven. 3. Identical subgoals must be carried out indepen­ dently. The same subgoal may be attempted and

achieved numerous times by the system.

To avoid this thrashing behaviour, Kuipers(l975) has advocated the use of a similarity network to recommend a replacement candidate frame on failure. This scheme assumes first that a mapping exists between the failing frame and each next candidate frame and secondly that the network is in some sense "complete". Any "surprises" cause the system to revert to blind automatic backtracking.

These difficulties are three manifestations of what Mackworth(l975) has called "the chicken and egg problem". It seems clear that to avoid these problems, an integration of both top-down and bottom­ up techniques are needed. Kaplan(l973) and more recently Bobrow & Winograd(l977) have advocated the use of multiprocessing with priority queue scheduling. We argue that in order to effectively integrate top­ down and bottom-up recognition methods more sophisti­ cated mechanisms than priority queues are needed.

3. Implementation

We define a procedural recognition model which utilizes multiprocessing and a deductive scheduling mechansim to realize an integration of top-down and bottom-up search. The model operates in two mutually recursive modes. The first mode is called matching and incorporates essentially the top-down recognition paradigm. The expectations of a frame are matched by direct observation by recursive use of matching i.e. subgoaling, ·and by recursive calls to the second mode described below.

The second mode implements bottom-up search and consists of two cyclical phases called expectation and completion.

Each frame may have associated with a number of processes called supergoals. Instead of relying entirely on matching to recognize an instance, a frame may suspend its recognition by computing a set of current expectations and suspending super­ goal processes to patterns representing those expectations. Each such process remains suspended until evidence is discovered which satisfies its expectations. The process is then resumed and the recognition of its associated frame continues.

Whereas a subgoal has an explicit caller and must eventually return a success or failure to that caller, a supergoal has no explicit caller. Instead, when a supergoal succeeds it begins the completion phase by resuming in turn one or more suspended supergoals of those higher frames of which its frame may be part. This provides a mechanism for handling non-determinism without resorting to failure driven methods. A particular frame instance need be recog­ nized only once.

Completion also provides a deductive pro·cess scheduling mechanism. Processes are ac tivated when the expectations that they are bound to have been satisfied. The model, as well, supports the use of a hierarchy of model driven methods to guide the recognition process. A frame's method computes a set of expectations, binds supergoals to those expect­ ations, and may relinquish control to a higher method. Alternatively, the method may retain control. This permits a frame to pre-empt a higher but less specific method and impose its own more powerful method to encourage the discovery of evidence sat­ isfying its expectations and propagating its own recognition.

This recognition model has been implemented as an experimental programming language, a dialect of LISP called MAYA (Havens,1976). The language provides primitives for constructing and accessing frames and semantic networks. MAYA provides control structure mechanisms for implementing the recognit­ ion model described. Multiple processes associated with particular frames may be created, suspended to patterns within frames, and resumed again by match­ ing those patterns. Specific control primitives are defined to permit subgoal and supergoal interaction and to support the realization of method hierarchies. We are presently experimenting with the recognition model by applying MAYA to a computer vision task (Havens, 1977).