LandScan: A Natural Language and Computer Vision System for Analyzing Aerial Images

1. Introduction

The aim of our research on LandScan (LANguage Driven SCene ANalysis) is to develop a system capable of dynamically updating and maintaining a model of an urhan world over multiple aerial views. The system will have a natural language front end through which users can query the system about a scene, and interactively assist the vision processing by restricting the analysis to those areas of the scene which are of current interest. A unique contribution of the work is that processing is both data-driven (bottom up, determined by sensor data) and query-driven (top down, determined by user queries). The integration of both methods into one system can help ~wercome the shortcomings of each method employed mdependently. For example, if data-driven processing were able to segment a graph of edges derived from the im_age i~to several different connected components, query­ dnven mformation about what the system should be looking for can help impose structure, a.nd a unique segrnentation, upon the otherwise ambiguous data.

The data-driven processing starts with stereo aerial images and reconstructs the surfaces in the scene. The query-driven processing constructs a logical representation of the scene using the queries to guide analysis. High­ level scene analysis is performed using an Augmented Transition Network (ATN).

Tbis research was supported by the following grants: ARO DAA6-29-84-k-006I AfOSR 82-NM-299 NSF MCS-8219196-CER NSF MCS 82-07294 A VRO DAAB07-84-K-F077 Nll-1 1-R01HL-29985-0 1.

LandScan: A Natu:ral Language and Computer Vis:on System for Analyzing Aerial Images

Ruzena Bajcsy Aravind Joshi Eric Krotkov Amy Zwarico

CIS Dept/D2 University of Pennsylvania Philadelphia, Pennsylvania 1Ql04

As an example, suppose the user asks, ·Is there a car on the street?· The output from this query would be: the objects to be recognized, car and street; th~ r~Iat~on ON which must hold between them; and an md1catlon that this query is responded to by a yesfno answer with some explanation. The vision system would then be called to find a car and a street in the relation ON. The car and street would then be added to the Scene Model (if not there already) and the system would reply with an affirmative response.

This paper will describe some related research, the implementation of the data-driven and query-driven portions of the LandScan system, and our plans for Cuture work. A Iater paper will detail how natural Iangtlage queries will interface with LandScan to guide the scene analysis.

2. Reisted Research

A large corpus of research on aerial image understanding per se exists, and many general VISIOn techniques are applicable to the aerial domain. _Large aerial projects have been undertaken at USC [Nevatla 83], CMU [Herman 83] and SRI [Fischler 83]. However, very few integrated systems have been successfully implemented, and the best system architecture is sti!l.an open question. In particular, the problern of prov1dmg high-level feedback to the vision system has not been adequately addressed.

ATN's have been used primarily in the domain of natural langnage [Bates 81J, [Winograd 83] . A notable exception is the system designed by Tropf and W ~~~er [Tropf 83] which uses an ATN model for the recogn1t10n of 3D objects with known geometries.

The work of Talmy [Talmy 83] and Herskovits [Herskovits 82] influenced the design of bot~ the topological relations in the models a~d the . chmc~ of linguistic attributes which must be assoc1ated w1th obJects in order to ensure a robust and reliable natural language interface.

3. Data-driven System lmplementation and Results

This section will describe the data-driven vision modules, which must be effective in an urban world, seen from above. Urban scenes are characterized by an abundance of straight lines and planar surfaces. Under these constraints, the scene may usefully be approximated as polyhedra.

W e have tested the modules on real, highly complex aerial images; it is very difficult to present these results. We show results derived from imaging a subset of the scale model depicted in Figure 6-2: a nmock up" of an urban scene. One advantage of using the scale model is the clarity of the results, and the ease of verifying their compatibility with reality.

3.1. Vision Modules

A stereo pair of images is acquired. The gradient vr of the images blurred at multiple resolutions is computed, and the Canny operator is used to locally suppress non-maxima in the gradient magnitude II vr II = SQRT(fx2 + f/). We call the surviving pixels ·edgels·. To find comc:rs, the variance 172 in the gradient directions B o:-.-=. tan·'(fy)/(fx)) is computed over a local neighborhood. The cornerness of an edgel is proportional to the product 17 2 II v r II-

Corresponding edgels in the two images are matched using 2-sided correlation at multiple scales. In images of parts of thv scenc in Figure 5-l, 83% of the vertically oriented edgels are matched, and the disparity at each is computed. The resultant sparse depth map is refined by linear interpolation (acceptable under the constraints of this domain), first across columns and then across rows. Figure 5-2 depicts the interpolated depth map (corresponding to only the more distaut objects in Figure ··1).

J.2. Surfac:e Model

A graph is constructed to serve as the surface model [Krotkov 84]. The construction algorithm converts a set of contours into a set of closed contours represented as a graph (a linked Iist of v_ertices, _edge~, and fa~es) by traversing edges and at tnhedral JUnchons choosmg the path making the most acute aDgle with respect to the present path.

Surface attributes and relations are computed in the SurfsUP [Radack, et al 84] geometrical modelling system. Attribute values for each face in the surface graph are computed: compactness, centroid, normal, area, type (building, sidewalk, field, street, and unknown), and number of sides. These values are computed once and stored on an attribute Iist. Computed topological relations are above, adjacent (touching), contiguous (sharing an edge), contains (proper inclusion), looksadjacent, lookscontiguous (respectively adjacent and contiguous under perspective transformations). Relations (and indirectly their complements) are computed once and stored as Boolean arrays.

4. Query-driven System lmplementation and Results

This section describes the design and implementation of the query-driven processes. These include object recognition and scene modelling [Zwarico 84], high Ievel reasoning processes, and query handling.

4.1. Objec:t Rec:ognition

The ATN formalism has been chosen as the paradigm for object recognition in LandScan. It is composed of three parts: the grammar, a dictionary, and an interpreter. The grammar represents the a priori or world knowledge that the system must have in order to recognize objects. The dictionary represents the actual J ata: a Iist of all of the faces which have been segmented by vision and the relations between them. The third component is a Lisp program which provides Hw controi ~tructure for the process. Figun ' 5-3 shows the results of running the recognizer on the scene in Figure 5-l.

4.2. The Sc:ene Model

The Scene Model is composed of two components: a Iist of objects currently known to be in the scene and a set of matrices representing the primitive relations. The objects on the object Iist have already been recogniz~d. Each object has associated with it a Iist of surfaces, 1ts location, and a subtype. The relations which are t~e same as in the surface model, are represented by the1r adjacency matrices because the adjacency matrix is easily updated and makes composition of relations a simple matter of Boolean matrix multiplication.

The Scene Model is dynamic because information can be added to it as further image analysis occurs. A new object is added to the head of the Iist. The relations are updated by calculating the relations between the new entity and the current object Iist.

4.3. Linguistic Analyaer . Given a query, the Linguistic Anal!zer will symbolically represent this utterance so tha~ 1t can be used by the reasoning process to analyze the 1mag~. The Linguistic Analyzer will parse ~he ~~ery, dete~m1~e the query type and categorize all 1mphc1t subquenes m the actual utt~rance. Its output will contain a Iist of the obiects to bc found, the relations which must hold betwecn thesc objects, and the query type .(s~ that an appropriate response can be generated). Th1s IS not yet implemented.

4.4. Reasoning

The Reasoner analyzes the query, determines the strategy for obtaining an answer to the query, and provides feedback to the vision system. In order to obtain the information necessary for the generation of the response the Reasoner must have both runtime data (the current Scene Model and the query) and global knowledge (the World Model and the Object Model).

The World Model describes the features and relations of the objects in the domain, buildings, streets, sidewalks, etc. The world is represented by a Iabelied directed multigraph in which the nodes are the objects in the domain and the arcs are labelled with the relation which can hold between them. The Object Model represents the expected physical features (subparts) and linguistic properties (features which affect the usage and interpretation of a spatial construct) of the objects in the domain.

lf the reasoning processes fail to produce a positive response (the query fails to have an answer), the Reasoner performs two types of query failure analysis. The first type of query failure involves a query violating the global knowledge. In this case, the system will respond with a message indicating why the query is conceptually ill­ formed in this domain. The other type of failure involves not finding the information requested in the scene model. In this case, rather than simply responding "not present", the system may ask the user whether a new view of the scene should be analyzed.

5. Discussion

. This paper has presentcd LandScan, a prototype mtegrated system under development that covers most of the di~ferent Ievels of vision and natural langnage processmg. It may be used both to guide the low-level vision processing, and to provide communication of visual information to a user. While LandScan is not complete in the sense that all of it is successfully implemented it provides a computational model for a vision system guided by natural language.

In s:nnmary, the data-driven subsystem of LandScan takes st.ereo ima~es a!ld builds a surface graph repr.escntmg three-dJmensJonal geometric and topological attnbut~s. The query-driven modules recognize objects and bUJld a Scene Model which represents the user's interest in the image.

The natural langnage interface which uses the scene representation still has to be designed. It must be able to apply locative linguistic constructs to some representation of visual data and reason about this data. When this is operative, the scene analysis will be truly query-driven and the goals of the system will have been reached.

Refere::1ces

[Bates 81] Bates, Madeleine. The Theory and Practice of Augmented Transition Network Grammars. In Leonard Bole (editor), Natural Language Communication with Computers. Springer-Verlag, 1g81.

[Fischler 83] Martin Fischlcr. Image Understanding Research and its Application to Cartography and Computer-Based Analysis of Aerial Imagery. Technical Report, SRI International, September, lg83.

[Herman 83] Herman, Martin, Takeo Kanade, Shigeru Kuroe. The 3D MOSAIC Scene Understanding System. In Procccdings of the 8th International Joint Conference on Arti f icial Intelligence. lg83.

[Herskovits 82] Herskovits, Annette. Space and the Prepositions in English: Regularities and Irregularities in a Complex Domain. PhD thesis, Department of Linguistics, Stanford University, 1g82.

[Krotkov 84] Krotkov, Eric. Construction of a Three Dimensional Sur face Model . Technical Report MS­ CIS-84··10, CIS Department, University of Pennsylvania, lg84.

[Talmy 83] Talmy, Leonard. How Language Structures Space. Technical Report 4, Berkeley Cognitive Science Report, January, lg83.

[Tropf 83] Tropf and W alters. An ATN for 3-D Recognition of Solids in Single Images. In Proceedings of the 8th International Joint Conference on Artificial Intelligence. lg83.

[Winograd 83] Winograd, Terry. Language as a Cognitive Process. Addison-Wesley Publishing Co., lg83.

[Zwarico 84] Amy Zwarico. The Recognition and Representation of 9D Images for A Natural Language Driven Scene Analyzer. Technical Report MS-CIS-84-29, University of Pennsylvania, Hl84.