Natural Object Recognition: A Theoretical Framework and Its Implementation

1 Introduction

The key scientific question addressed by our research has been the design of a computer vision system that can approach human-level performance in the interpre­ tation of natural scenes such as that shown in Fig­ ure 1. We offer a new paradigm for the design of computer vision systems that holds promise for achiev­ ing near-human competence, and report the experimen­ tal results of a system implementing that theory which demonstrates its recognition abi lities in a natural do­ main of limited geographic extent. The purpose of this paper is to review the key ideas underlying our ap­ proach (discussed in detail in previous publications [12, 13]) and to focus on the result.s of an ongoing experi­ mental evaluation of these ideas as embodied in an im­ plemented system called Condor.

When examining the reasons why the traditional ap­ proaches to computer vision fail in the interpretation of ground-level scenes of the natural world, four fundamen­ tal problems become apparent:

Universal partitioning - Most scene-understanding systems begin with the segmentation of an image into homogeneous regions using a single partition­ ing algorithm applied to the entire image. If that partitioning is wrong, then the interpretation must also be wrong, no matter how a system assigns se­ mantic labels to those regions. Unfortunately, uni­ versal partitioning algorithms are notoriously poor delineators of natural objects in ground-level scenes.

*Supported by the Defense Advanced Research Projects Agency under Contract.s DACA76-85-C-0004 , DACA 76-90C-0021, and 89F737300.

Shape - Many man-made artifacts can be recognized by matching a. 3D geometric model with features extracted from an image [1, 2, 4, 6, 7, 9, 15], but most natural objects cannot be so recognized. Nat­ ural objects are assigned names on the basis of their setting, appearance, and context, rather than their possession of any particular shape.

Computational complexity - The object recogni­ tion problem is NP-hard [16] . As a result, computa­ tion time must increase exponentially as additional classes are added to the recognition vocabulary, un­ less a strategy to avoid the combinatoric behavior is incorporated. Such provisions are a necessary com­ ponent of any recognition system that can be scaled to embrace a real domain.

Contextual knowledge - Despite general agreement that recognition is an intelligent process requiring the application of stored knowledge [3, 5, 14], computer vision researchers typically use artifi­ cial intelligence techniques only at the highest levels of reasoning. The design of an approach that allows stored knowledge to control the lower levels of image processing has proved elusive.

Except for the continuing work at the University of Massachusetts [3], the understanding of natural scenes has received surprisingly little attention in the last decade.

2 Approach

A new paradigm for computer vision systems has been developed, which addresses all four of the problems de­ scribed above. The key provision of this novel approach is a mechanism for the application of stored knowledge at all levels of visual processing. A context set, which explicitly specifies the conditions and assumptions nec­ essary for successful invocation, is associated with every procedure employed by the recognition system.

The architecture is organized into three modules as de­ picted in Figure 2 and described below (a more complete description is also available [13]) :

Candidate Generation -

Hypotheses concerning the presence in a scene of specific categories of objects are generated by de­ lineating regions in an image using special-purpose operators whose invocation is controlled by context sets, thereby avoiding the need for universal parti­ tioning algorithms. The employment of large num­ bers of operators ensures that quality hypotheses can be generated in nearly every context and pro­ vides redundancy that decreases the reliance on the success of any individual operator .

Candidate Comparison - Hypotheses are accepted only if they are consistent with all other members of a clique (consistent subset). Candidate hypotheses for each label are ranked so that the best candidates for each label can be considered before the oth­ ers . Ranking the candidates ensures that the largest cliques can be found early in the search, thereby limiting the computational complexity of the entire paradigm to a linear growth as the recognition vo­ cabulary is expanded. By constructing only a small number of cliques for each image, the approach loses any guarantee of finding the largest clique, but as­ sures the availability of a credible answer compatible with the computational resources of the system.

Clique Formation - Consistency is enforced by pro­ cedures (controlled by context sets) that detect and reject physically impossible combinations of hy­ potheses. The clique that most completely explains the available data is offered as the interpretation of an image. Thus , individual objects are labeled on the basis of their role in the context of the complete clique, rather than solely on the basis of individual merit .

The invocation of all processing elements throughout the system is governed by context. All processing ac­ tions are controlled by context sets , and are invoked only when their context sets are satisfied. Thus, the actual sequence of computations (and the labeling deci­ sions that are made) are influenced by contextual infor­ mation, which is represented by prior knowledge about the environment and by the computational state of the system.

Definition: A context set, CSk> is a collection of con­ text elements that are sufficient for inferring some relation or carrying out some operation on an image.

Syntactically, a context set is embedded in a context rule denoted by

where L is the name of the class associated with the context set, A is an action to be performed, and the C; comprise a set of conditions that define a context.

Example: The context rule

defines a set of conditions under which it is appropri­ ate to use the operator BLUE-REGIONS to delineate candidate sky hypotheses.

There is a collection of context rules for every class in the recognition vocabulary, and each collection con­ tains rules of three types : candidate generation, candi­ date comparison, and consistency determination. In the­ ory, Condor performs the actions A that are associated with every satisfied context set .

3 The recognition process

For each label in the active recognition vocabulary, all candidate-generation context sets are evaluated. The operators associated with those that are satisfied are executed, producing candidates for each class. The candidate-comparison context sets that are satisfied are then used to evaluate each candidate for a class, and if all such evaluators prefer one candidate over another, a preference ordering is established between them. These preference relations are assembled to form partial or­ ders over the candidates, one partial order for each class. Next , a search for mutually coherent sets of candidates is conducted by incrementally building cliques of consistent candidates, beginning with empty cliques. A candidate is nominated for inclusion into a clique by choosing one of the candidates at the top of one of the partial orders. Consistency-determination context sets that are satisfied are used to test the consistency of a nominee with can­ didates already in the clique. A consistent nominee is added to the clique; an inconsistent one is removed from further consideration with that clique. Further candi­ dates are added to the clique until none remain. Addi­ tional cliques are generated in a similar fashion as com­ putational resources permit . Ultimately, one clique is selected as the best semantic labeling of the image on the basis of the portion of the image that is explained and the reliability of the operators that contributed to the clique.

The interaction among context sets is significant . The addition of a candidate to a clique may provide context that could trigger a previously unsatisfied context set to generate new candidates or establish new preference orderings. For example, once one bush has been recognized, it is a good idea to look specifically for similar bushes in the image. This tactic is implemented by a candidate-generation context set that includes a context element that is satisfied only when a bush is in a clique.

4 Evaluation scenario

The approach has been implemented in the form of a complete end-to-end vision system, known as Condor. Images that are monochromatic or color, monocular or stereo, provide the input to the system, along with a terrain database containing prior knowledge about the environment. Condor produces a 3D model of the envi­ ronment labeled with terms from its recognition vocab­ ulary which is stored in the Core Knowledge Structure (CKS) [10, 11] and can be superimposed on the input im­ age (Figure 3) or viewed from another perspective (Fig­ ure 4). The model is used to update the terrain database for use by Condor during the analysis of subsequent im­ agery.

To evaluate the Condor approach, we selected a two­ square-mile region of foothills immediately south of the Stanford University campus as our site for experimen­ tation. This area contains a mixture of oak forest and widely scattered oak trees distributed across an expanse of gently rolling, grass-covered hills and is criss~crossed by a network of trails.

We chose 14 classes for the recognition vocabulary on the basis of their prevalence in the experimentation site and their importance for navigation. These terms are:

{sky, ground , geometric-horizon, foliage, bush, tree-trunk, tree-crown, trail, skyline, raised-object, complete-sky, complete-ground, grass, tree}

Procedures have been devised to extract, evaluate, and check the consistency of candidates for each of these classes. Context sets have been constructed to control the invocation of each of those procedures. Currently the knowledge base contains 88 procedures whose invo­ cation is governed by 156 context sets. All the results described in this paper have been generated using this knowledge base.

them. No trunk was detectable in the foliage to the left of the image, so Condor labeled it as bush.

linage 6 - The texture in the lower corners of the sixth image was found to more closely resemble foliage than grass, so these regions were erroneously identified as bushes. Beause they are very near the camera, they occupy a significant part of the image, but the 3D model created for them reveals that they are less than 2 feet tall.

Image 7 - Several more trees, grass areas, and part of the trail are recognized in the seventh image.

Image 8 - The primary tree is recognized despite the strong shadows, but the lower portion of the trunk was missed by all the trunk operators. Most of the tree crown operators were unable to provide a de­ cent candidate because of the overhanging branches in the upper-right corner - the only operator that succeeded was the one that predicts the crown based on the size and location of the trunk. The combined effects of the incomplete trunk, the nearness of the tree, and the lack of range data account for poor extraction of the tree crown.

This experiment illustrates how Condor is able to use the results of analyzing one image to assist the analy­ sis of other images. Although some trees and parts of the trail were missed in several images, the 3D model that results is nearly complete. Figure 8 shows an aerial view of the composite model contained in the CKS after processing all eight images. For comparison, Figure 9 portrays a model of the objects actually present on the ground, which was constructed by physically measuring the locations and sizes of the individual objects. Note that all of the trees that were visible in at least one image have been correctly labeled, although some of them were misplaced. Most of the trail has been detected, enough to allow a spatial reasoning process to link the portions into a single continuous trail. Furthermore, everything that was labeled tree actually is a tree.

Figure 9: The ground-truth database.

5.3 Experiment 3

Regardless of the architecture, knowledge-based VJSJon systems are difficult to build. If the programmer needed to specify in advance all the information necessary for successful recognition, his task would be hopeless. Therefore, it is essential that a vision system have the ability to improve its competence autonomously, th,ereby learning through experience how to recognize the objects in its environment.

Assertion 3 Using context allows Condor to learn how to recognize natural objects.

To test the validity of this assertion, we return to the first image of the sequence used in Experiment 2 (Fig­ ure 7). When originally analyzed, Condor recognized the trail and part of the grass, but not the trees.

Condor was tasked to reanalyze the first image, this time making use of the contents of the entire database constructed during the analysis of the sequence of eight images. The resulting interpretation is depicted in Fig­ ure 10.

Two trees that could not be extracted on the first pass are now identified. Condor employed a tree-trunk opera­ tor whose context set requires knowledge of the approxi­ mate location of a tree in the field of view. The operator projects a deformable 3D model of the trunk onto the image, and optimizes its fit to extract the trunk. This operator successfully identified two of the trees without contradicting any of the original recognition results.

This experiment (along with others not described here) illustrates that the ability to use prior recognition results as context while interpreting subsequent images enables Condor to improve its performance as its expo­ sure to its environment increases.

6 Conclusion

In its present embodiment, Condor is still a demonstra­ tion system that should be evaluated primarily in terms of its architectural design and innovative mechanisms, rather than its absolute performance. While Condor has demonstrated a recognition ability approaching human­ level performance on some natural scenes, it is still per­ forming at a level considerably short of its ultimate po­ tential (even for the Stanford experimentation site). The knowledge acquisition mechanisms, which are a. key as­ pect of the architecture, should allow continued improve­ ment in performance with exposure to additional site imagery.

A new paradigm for image understanding has been proposed, and used to recognize natural features in ground-level scenes of a geographically limited environ­ ment. This context-based approach is exciting because it deemphasizes the role of image partitioning and em­ phasizes the recognition context in a way that has not been attempted before. This new focus could lead to the construction of vision systems that are significantly more capable than those available today.

7 Acknowledgment

Condor includes software provided by many present and former members of the Perception Group at SRI. In addition , Marty Tenenbaum, Jean-Claude La.tombe, and Lynn Quam have contributed to the research reported here.