Visual Routines and Visual Search: A Real-Time Implementation and an Automata-Theoretic Analysis

1 Introduction

Shimon Ullman proposed the visual routines theory of in­ termediate vision as a way of explaining how the human visual system might solve certain visual tasks (such as computing spatial relations) that seem to require serial processing [Ullman, 1984]. At a gross level, the theory proposes that the visual system contains a set of registers that can contain different types of visual data, a means of focusing visual attention on task-relevant portions of the image, and a set of primitive "instructions," such as coloring and line drawing, that can be combined like instructions in a computer program to compute useful properties of an image. These resources are collectively referred to as the vi&ual routine proceuor or VRP.

1 Support for this research was provided in part by the University Research Initiative under Office of Naval Research contract N00014-86-K-0685, and in part by the Advanced Research Projects Agency under Office of Naval Research contract N00014-85-K-0124, and in part by the National Sci­ ence Foundation under grant number IRI-9407273. Joanna Bryson kindly read drafts of this paper and provided useful comments.

The visual routines theory have received increasing at­ tention from the AI community in recent years {[Agre and Chapman, 1987][Chapman, 1990][Reece and Shafer, 1991][Romanycia, 1987][Whitehead and Ballard, 1990]). Much of this attention has come from the reactive rea­ soning and planning community, in part because Agre and Chapman's implementation of the visual routines model provides an alternative interface between reason­ ing and perception, which is both easier to implement and more biologically plausible than standard database­ like interfaces.

. Despite the level of interest, there has yet to be a VRP implementation that runs on real camera images. To date, VRP systems have run either off of hand-drawn bitmaps [Romanycia, 1987] or have been directly inter­ faced to the world model of a world simulator, thus bypassing low-level vision entirely [Agre and Chapman, 1987][Chapman, 1990][Reece and Shafer, 1991].

In this paper, I describe Jeeves , a working visual rou­ tine processor that runs off of color video at approxi­ mately 10Hz using only relatively simple hardware. This is work in progress. As of this writing, J eeves imple­ ments the visual search portion of the theory, the part which is presently best worked out. I will also present a formal analysis of the amount of control machinery required to solve arbitrary-length Horn clauses, discuss the effect of resource limitations on visual search, and give an example of a simple Horn clause for which most current biological theories of visual search cannot ac­ count. Finally, I will describe Bertrand, a novel logic programming system that answers Horn Clause queries about scenes without the use of an internal proposition database.

2 Overview of the VRP model

2.1 Early vision and attention

Virtually all theories of vision presuppose a stage of early or low level processing that extracts local features from the image such as edges, color information, or depth. It is generally believed that early vision computes a set of low level map& each displaying the strength or value of a specific feature for all points in the image. These maps are believed to be computed bottom-up and in parallel.

In the last decade, covert visual attention, the prob­ lem of selecting image-plane regions for processing, has been widely studied in the psychophysical and neuro­ physiological communities. A wide range of neural mod­ els of covert attention have been proposed (see [Tsotsos et al. , 1994) for a detailed survey) . These models assume image regions are selected based on their low level fea­ tures (see above). Most use a pyramid structure, and so are referred to as "attention-" or "addressing-pyramids". Models differ on what the attention mechanism reports to the next level about the region. Some models such as [Koch and Ullman, 1985) route aggregate feature val­ ues of the attended region to their outputs, while other models, such as [Olshausen et al., 1992), route resam­ pled images to their outputs. Jeeves , is patterned after [Koch and Ullman, 1985), although dynamic resampling would be easy to add.

For the purposes of this paper, the most important data on covert attention are the experiments of Treisman et al. [Treisman and Gelade, 1980), which suggest the vision system can search all points in the image in par­ allel for many low level features (called "pop-up" proper­ ties) but must handle conjunctions offeatures by serially enumerating regions satisfying one of the conjuncts and then testing them for the other(s). Most neural models of attention have image-parallel hardware for matching pop-up properties to handle the simple cases, and pro­ vide some return-inhibition mechanism to support region enumeration for conjunctions. Return-inhibition stores the locations of previously attended regions and prevents them from being selected in the future. All regions sat­ isfying a given pop-up feature can then be enumerated by repeatedly selecting a region and inhibiting it.

It is outside the scope of this paper to debate the va­ lidity of Treisman's experiments or the various neural models of covert attention. The interested reader is di­ rected to [Tsotsos et al., 1994].

2.2 Visual routines

The visual routine model [Ulhnan, 1984] claims that cer­ tain kinds of visual work are done by selecting relevant regions of the image and applying simple geometric op­ erations to them such as drawing lines to connect them, searching along the lines for other regions, or checking whether a point lies within a closed curve using flood-fill operations. The essential claims are that (1) there ex­ ists a vi6ual routine proceuor (VRP) that consists of a set of discrete functional units, each capable of perform­ ing a specific operation such as line drawing or flood filling and (2) these operations can be combined in task­ specific manners to do useful visual work in the same way subroutines are built up from primitive machine instruc­ tions (hence the name "VRP") . The model presupposes a number of basic architectural features of the visual system:

• An early vision system to compute primitive fea­ tures,
• An attention system to select task-relevant regions based on those features and route them to the VRP,
• A set of functional units for executing primitive in­ structions, and
• A set of specialized state elements for holding intermediate values (registers) .

The details of the registers and functional units are un­ known. Chapman's system [Chapman, 1990] contained four types of state elements: markers, which held image locations; lines and rays; activation planes, which were general registers that could hold arbitrary binary images; and a return inhibition map. All state elements. except the return inhibition map could be directly named and manipulated. The return inhibition map had its own specialized operations. In Chapman's system, a blocks­ world visual routine for finding the first block under­ neath some blue block would consist of the following op­ erations:

1. clear the return inhibition buffer
2. select a blue block and inhibit it
3. set marker 0 to the location of the selected region
4. set ray 0 to project downward from marker 0
5. set marker 1 to the first object along ray 0
6. if the previous operation failed, go to step 2.

If this routine succeeds, then marker 0 will designate the blue block and marker 1 the block underneath it.

3 Jeeves implementation

Jeeves is the first system to implement the VRP model on real camera data using a real low level vision sys­ tem. It implements the necessary extensions to allow operation on scenes in which objects have non-trivial spatial extent and/or occlude one another. It imple­ ments marker and line operations, but presently does not implement activation plane operations (the current do­ main doesn't exercise them adequately). It implements queries on 2D spatial relations and simple feature values and has been tested on children's blocks (real ones, with differing shapes), books, and brightly colored kitchen utensils. The architecture of Jeeves is shown in figure 1. I hope to apply it to other domains and to extend its repertoire of computations soon.

Jeeves runs on 64 x 29 images at approximately 10Hz. It is written in C and presently runs on color vision hard­ ware designed at MIT by Chris Barnhart. The hardware consists of roughly $1000US worth of components, in­ cluding a Texas Instruments C31 floating-point DSP and an NTSC color digitizer. It is controlled from a Sparc-1 running Scheme over a 38K-baud serial port.

The process of building a low-level vision system and VRP that can run at 10Hz required a great many com­ promises, most importantly, the use of low resolution im­ ages and the lack of a shape-matching system. In some cases, these compromises limited the tasks that could be solved by the system. I have tried to restrict my at­ tention to claims and tasks that are unaffected by these limitations.

3.1 Low-level maps

After grabbing the image and averaging it down to low resolution, the system computes a number of low level retinotopic maps. As of this writing, it computes various color maps (R, G, B, R/I, G/I, B/I), intensity, temporal and spatial derivatives, including Laplacian, V 2 G edges, and a grey-scale symmetry operator. An optic flow de­ tector has also been implemented but is not presently used.

3.2 Preattentive segmentation

Chapman's SIVS system ignored the issue of dividing the image into regions corresponding to distinct objects, ef­ fectively assuming that objects were single points. Chap­ man argued from psychophysical evidence that the vision system might perform a first-pass segmentation before the attention pyramid. The attention pyramid would then select among segments rather than points. Other models assume that the attention pyramid can select among different scales, but does not use segmented in­ put. As much for engineering reasons as for theoretical ones, I choose to use a preattentive color segmentation system as a preprocessing stage for the attention pyra­ mid. The system finds color boundaries in the image and uses a connected-components algorithm to label regions of homogeneous color. The segmentation system also al­ lows the higher level to specify minimum and maximum segment sizes. Minimum sizes allow the suppression of "noise" segments and maximum sizes act as a crude form of figure/ground separation.

I do not propose the simple color segmentation system as any kind of theory of human preattentive segmenta­ tion. However, the use of segmentation is logically inde­ pendent of other design decisions; one could change or remove the segmentation system and still have a usable vision system.

3.3 The saliency map and visual attention

The VRP selects task-relevant image regions by comput­ ing a pixel-by-pixel weighted sum of the low level maps [Clark and Ferrier, 1988][Ahmad and Omohundro, 1991]. The weights are one of the input parameters of the sys­ tem and can be changed continuously by the higher lev­ els (see figure 2). Weighted sums may be more powerful than the human system. One can adjust the weights to select for conjunctions, for example. However, this would presuppose something like a perceptron learning algorithm running to learn the proper weights for the proper conjunctions. Since this would require consider­ able training, the human system might use the weighted combinations and still be unable to do parallel search for conjunctions. In point of fact, more recent psychophys­ ical results do indicate that at least some conjunctions can be learned with sufficient training (see [Weismeyer, 1992] and [Tsotsos et al., 1994] for surveys of recent re­ sults).

The attention system computes the region with the maximum integral of salience. This differs from previ­ ous systems which have either found the image point with maximal salience or the image point with maximal smoothed salience, perhaps over several different scales. Finally, the attention system computes the bounding box, area, centroid, and average low level map values for the winning segment.

3.4 Visual markers

The only directly-addressable memory in J eeves is a small collection (10) of registers called "markers" [Chap­ man, 1990] which can hold the centroid and bounding box of a segment. Markers can be loaded with the spec­ ifications of the currently attended region, compared to one another, or used to focus attention (see below).

3.5 Return-inhibition and spatial · constraint

In many biological attention models and also in many computer implementations, return inhibition is imple­ mented as a function internal to the attention pyramid itself. Indeed, most biological models provide only very limited control over return inhibition, if any. Chapman's model provides control lines to enable and disable the ad­ dition of the current point to the set of inhibited points and to clear the set of inhibited points. It does not pro­ vide the capability to suppress return-inhibition without permanently clearing the set of inhibited points.

Jeeves implements return inhibition through a sepa­ rate return-inhibition map (RIM) that is summed into the saliency map (see figure 2). Jeeves provides sepa­ rate control lines for adding the current region to the RIM, clearing the RIM, and including the RIM in the the saliency measure. The latter is controlled through the same weighting mechanism used for other maps.

Both Chapman and Ullman propose that the VRP can search for objects along specified rays. In Chapman's system, this is implemented though a separate attention mechanism. As with return inhibition, spatial constraint of search is implemented in Jeeves through the saliency mechanism. A separate low level map, with its own inde­ pendent weight, computes a "position salience" for each point in the image. Position salience is ta&k dependent but image independent. It is computed as a sum ofterms that fall off quadratically with distance from a marker and from a ray emanating from the marker. If either term is zero, the position salience is zero. The marker, ray direction, and rates of decay are inputs to the atten­ tion mechanism.

4 Automata-theoretic analysis

Most computational work on covert attention and visual search (e .g. [Chapman, 1990][Tsotsos et al., 1994][Weis­ meyer, 1992]) has been designed specifically to fit psy­ chophysical timing data on very specific tasks, such as Triesman's. Relatively little attention has been given to the computational power of these models in the abstract. In effect, these models treat the visual search system as a very simple Prolog engine: they search for image regions satisfying a conjunction of primitive features. They se­ rially enumerate regions satisfying the first feature and test each for the other features. A failure of the test causes backtracking, which is implemented by the return inhibition mechanism. The essential differences between these systems and a Prolog engine are that:

• The propositional database is replaced by the image.
• Logic variables are replaced by markers or the at­ tention output.
• Backtracking state is stored in the return inhibition mechanism, and
• Only very simple queries are examined.

The last two of these are particularly important for our purposes: the Treisman experiments amount to Horn clause queries containing exactly one variable. The vi­ sual attention mechanisms can only handle queries in­ volving one variable, because they only have one state element in which to record backtracking information: the return inhibition mechanism. Multiple-variable queries require either multiple return-inhibition maps or ad-hoc query restrictions to limit backtracking.

4.1 Enumeration oracles

We can make these observations more precise by intro­ ducing an abstract VRP with infinite resources. First, some definitions. Consider a conjunction of literals in Prolog notation:

We define the &ignature P(h, ... , f.,.) , fi E {0, 1} of a predicate application P(Xlt ... , X.,.) to be the application with its arguments replaced by 1 if the application is the leftmost occurrence of the variable in the clause, else 0:

The signature specifies whether the search engine needs to enumerate values for the variable (1) or to filter them (0).

We will define an enumeration oracle over a domain D to be a machine with an input (to be described mo­ mentarily), a binary output, and infinite collections of numbered object regi&ter& Dlt D2 , ... ranging over D and contezt regi&ter& cl, c2, ... ranging over sequences of tu­ ples over D, i.e. (D*)*. Note that these machines are oracle&: idealizations not intended to be physically in­ stantiable.

The input to the oracle is a tuple (S, (o1 , ... , o.,.), c, r) where S is a predicate signature, ( olt ... , o.,.) is a list of object register numbers (one for each argument of the predicate), c is a context register number, and r is a binary restart flag.

Upon rece1vmg an input, (P(/1, ... , f.,.), (olt ... , o.,.), c, r), the oracle tests whether P(Do, ... , Do,.) is satisfiable, updates context register Cc and those object registers specified by the fi, and returns true if the predicate was indeed satisfiable.

More formally, let v be the number of registers to be instantiated, i.e . .E fi· If v = 0, the oracle simply tests whether P( D 01 , ... , Do,.) is true. If v::f:O, the oracle must determine if there is another set of variable values that will make P( Do, ... , Do,.) satisfiable. To do this, it main­ tains the set of untried variable values in context register Cc. If r is true, we are restarting an enumeration so the oracle chooses an arbitrary ordering on D" and stores it in Cc. Regardless of r, it finds the first tuple in Cc that can be substituted into the unbound variables in the lit­ eral so as to make it true. If such a tuple exists, the Do, for which fi = 1 are updated from the tuple, Cc is set to the remaining tuples, and the oracle returns true. Otherwise it returns false.

4.2 Solving Horn clauses

The enumeration oracle is essentially a VRP with infinite markers (object registers) and return inhibition buffers (context registers). It can be shown that such a system can answer arbitrarily long Horn clauses, given surpris­ ingly little external control logic: a flip flop and a shift register (see figure 3) . Because of space limitations, I will only sketch the proof.

The system requires an external "compilation" phase to translate from the external representation of the Horn clause to a suitable shift-register tape. For convenience, we will assume that variables are drawn from a numbered set Xi, which we will put in correspondence with the object registers Di. Given a conjunction of literals over variables,

we create a shift register tape whose cells are oracle in­ puts that enumerate the respective literals of the con­ junction. Thus cell i, is the tuple giving the signature of the ith literal, the registers for the literal's argument variables, and a context register to use. We will use con­ text register C1 for literal i. The restart flag must be generated at run time, so it will not be included in the cell. The shift register tape is then:

and the tape for the clause in (1) would be (using X as variable 1 and Y as variable 2):

The only non-trivial part of this compilation process is computing the signature. It is easily done by keeping track of which variables have appeared so far in a left­ to-right reading of the clause.

Given this tape, we can enumerate all satisfying vari­ able assignments of the clause by adjoining a simple au­ tomaton to the oracle. The tape is augmented with left­ and right- end-of-tape markers, and the shift register is started at the left end of tape. The automaton has a single flip-flop, called restart, which is initialized to 1. It follows the rules:

• If restart, then shift to the next cell to the right, else to the left.
• If not at end of tape, take current cell's tuple, ap­ pend restart to it, and feed it to the oracle, storing the result in restart.
• If at the right end of tape, signal success and clear restart.
• If at the left end of tape and restart is clear, termi­ nate.

These rules are easily implemented in a few gates.

In effect the tape acts as the backtracking stack, one cell per frame, and the context registers named on the tape hold the backtracking history of their respective frames. Each time the automaton reaches the right EOT and signals success, it has found a complete satisfying variable assignment for the clause. It can be shown that:

Claim 1 The automaton above signals success once for each satisfying variable assignment of the clause.

Sketch of proof: By induction, the number of right­ ward tape crossings out of the ith cell is equal to the number of satisfying variable assignments for the first i literals in the clause. Rightward crossings out of the last cell enter the right EOT and so signal success.

This allows us to quantify the amount of control state needed to satisfy arbitrary length Horn clauses with an enumeration oracle.

We have assumed the enumeration oracle handles arbitrary signatures of arbitrary literals. We can weaken these assumptions somewhat through compile­ time transformations by forcing variables to be enumer­ ated one at a time using weaker predicates or by evaluat­ ing the literals in a different order. Such transformations are outside the scope of this paper.

4.3 Resource constraints

Current biological theories of covert visual attention tac­ itly assume only a single "context register," the return­ inhibition state. The return-inhibition state can only track the enumeration of a single variable. Thus, it would seem that the VRP can only handle clauses con­ taining a single variable. In point of fact, this can be optimized somewhat.

Backtracking with markers

The predicate on( X, Y) be solved in the VRP by project­ ing a short ray downward from a known X and placing Y on the first object found along the ray (or by project­ ing upward from a known Y). The same procedure also works for the immediately-above ( iabove) relation 2 if we use an infinitely long ray. A solution to iabove(X, Y) is also a solution to above(X, Y). To find any other solutions to above(X, Y), we can inhibit return to the previous solution and resolve. This requires an extra return-inhibition map, however. If we adopt the ideal­ ization that an object can only immediately above one other object, then we can solve above( X, Y) without an extra return-inhibitionmap. The reasin is that aboveness is the transitive closure of immediately aboveness:

which gives us the following procedure for enumerating values of Y given X: to restart an enumeration, project a ray down from X and bind Y to the first object found along the ray; to backtrack the enumeration, project a ray down from the current value of Y and rebind Y to the first object found along the ray.

In effect, this technique causes the object registers to do double-duty as context registers. The technique is applicable to any right-unique relation: 3

Claim 2 Let r(X, Y) be right-unique and r*(X, Y) be its transitive closure. An enumeration oracle can enu­ merate the signature r* ( 0, 1) without using a contezt reg­ ister, provided that it can enumerate r(O, 1).

Method:

Given the input (r*(0,1),(o,,oj),c,1), the oracle com­ putes (r(O, 1), (o,, Oj), c, 1). Given (r*(O, 1), (o,, Oj), c, 0), it computes (r*(O, 1), (o1, Oj ), c, 1). Neither operation re­ quires changing the context register c, so the oracle can safely ignore it.

Although useful, the technique does not obviate the need for context registers. Arches, a favorite topic in the blocks world, presuppose the on predicate is non-right­ unique. An arch query such as:

simply cannot be processed by a VRP unless it has mul­ tiple return-inhibition maps! Of course, arches might be recognizable via a different query, depending on the particular capabilities of the VRP.

l X is immediately above Y iff X is above Y and for all Z above Y either Z is above X or Z = X.

3 r is right-unique if for all :z:, y, z, r(:z:,y) 1\ r(:z:,z) => r(:z:, z) .

Down to 0 ; (blue x): x set to block 1

Down to 1 ; (above x y): y set to block 2

Down to 2 ; (above y z): query fails

Up to 1

; (above x y): query fails

Up to 0

; (blue x): x set to block 3

Down to 1 ; (above x y): y set to block 4

Down to 2 ; (above y z): z set to block 5

7 VRP operations; The formula is satisfied.

Figure 4: An image (above left), its subsampled version (above right), and an example query and execution trace (below). Semicolons mark annotations. Note that the system assumes any uniformly colored region is a block. It does not recognize the other objects, although it can tolerate their presence.

5 A database-free logic programming system

Bertrand is logic programming system built to experi­ ment with the search capabilities of the VRP. It is essen­ tially a direct implementation of the Horn-clause satisfier discussed above. It has a compilation phase that trans­ lates clauses into shift-register tapes and an execution phase in which VRP markers are set to a satisfying vari­ able assignment for the clause using backtracking search. Marker positions are overlaid as colored X's on the live video image. An example execution trace is shown in figure 4.

At present, Bertrand runs with only one return­ inhibition map, although this could be easily changed.

6 Answering natural language queries

The above results suggest a natural extention to the pro­ cessing of simple natural language utterances: we add a simple parsing front end and a semantics system that defines the semantics of visual words in terms of VRP instructions that find their referrents. We can then an­ swer the sort of natural language queries whose logical forms are simple Horn clauses of the form that Bertrand can solve: ·

• Is there a green block?
• Is the green block on another block?
• Show me the blue block on the red block.
• Is it on a red block?
• Is there a green block on a blue block on a red block on an orange block under a green block?

Ludwig is a natural language system that can answer simple questions using the VRP. Although quite limited, it is novel in that it uses not only no world-model, but no tree-structured representations whatsoever! Ludwig is implemented entirely as a set of piplined parallel pro­ cesses, each finite state, with fixed connections between them. Connections are simple activation levels, binary values, or narrow busses. 4 In this sense, it is compatible with connectionist ideas. To my knowledge, Ludwig is the most sophisticated system to date based on the no­ tion of using the world as its own best model. It is also the only such system that supports fully compositional representation and recursive structures.

7 Motor control

We have mounted the vision system on a mobile robot base and used it for simple visuo-motor experiments. Al­ though designed for visual search, the visual routine pro­ cessor already contains much of the machinery necessary for the visual system of the Polly robot [Horswill, 1993j. For example, the Polly system performs collision avoid­ ance by steering to avoid texture in the image. Since the floor of Polly's environment has no surface markings, the presence of an edge necessarily indicates the presence of an obstacle and so an edge detector is sufficient to act as an obstacle detector. Polly computes the depths of edges using image-plane height. In particular, Polly steers by computing three distances, d,, de, and dr, which are de­ fined as the image plane heights of the lowest edge pixels in the left, center and right thirds of the image, respec­ tively. Polly then turns at a rate proportional to d, - dr and advances at a rate proportional to de.

Such a control regime is easily added to the VRP. The output of the saliency map is fed to a motor control unit that computes d,, de, and dr, defined to be the image plane heights of the lowest &alient pixels in their respec­ tive image areas. The motor control unit also computes :Z:min> the :z: coordinate of the lowest salient pixel in the whole image. A motor control in&truction then consists of a VRP instruction to determine the settings of the salience parameters and a matrix A and a vector b used to compute the motor velocities as:

For example, using a VRP instruction spatial derivatives and specifying to attend to

where d.top is the desired stopping distance for the robot, yeilds the standard Polly collision avoidance algorithm, while the values

where dw is the desired dista¥ce reading for the left wall, yeilds Polly's left-wall following algorithm. Finally,

4 In fact, Ludwig is implemented directly in a register­ transfer-level hardware language.

yields a primitive following algorithm that steers toward and approaches the nearest object.

The motor control unit is also able to make ballistic turns to face in the direction of a given marker. After a ballistic turn of the robot's body, marker positions are automatically updated to compensate for the motion.

Finally, the motor control unit has been integrated into Bertrand to allow motor control operations to be mixed with visual search operations. Thus the program:

will cause the robot to find a red block on a blue block and drive up to it.

8 Conclusions

This paper provides the first VRP implementation that runs on real camera data and one of the few implemen­ tations of biological theories of covert visual attention that runs on real data. It also provides a formal study of the VRP's visual search capabilities and the effects of the resource limitations in biological attention theories (for a study of visual search independent of the VRP architecture, see [Tsotsos, 1990]).

One of the outcomes of the formal analysis is that some surprisingly simple queries cannot be solved without as­ suming more machinery than current biological theories provide. This is not fatal to the theories, it simply means that must either (1) we revise the theory, (2) assume that some other system is in charge of finding arches, or (3) assume the problematic queries aren't important in ev­ eryday life. (1) is simple: just assume there are multiple return-inhibition maps and that their effects on the at­ tention pyramid can be gated by higher level processes. This may not be true, but it suggests a whole range of interesting psychophysical experiments. (2) is more tricky. Many computer models of recognition tacitly as­ sume the ability to perform complicated backtracking searches. Explaining one system's inability to backtrack by assuming another's ability to backtrack simply begs the question. If psychophysical experiments should show that the human visual system really is limited in its abil­ ity to backtrack in visual search, this would lend support to view-based models of recognition.

Bertrand and Ludwig are interesting because they have no internal world model: database operations on the model are translated directly into image-plane op­ erations, yielding a high performance interface that is plug-compatible with a database. An existing problem solver could be modified to do the same. The result would be a system that seamlessly alternated between image operations and world-model operations, depend­ ing on the type of query.