The LOCUS Model of Search and its Use in Image Interpretation

Introduction

The central problem in image understanding is the represent at ion and use of all the available sources of knowledge in the interpretation and description of an image. The problem of representation is complicated by the di versi ty of the sources of knowledge. Converting knowledge into effective algorithms in the presence of error and uncertainty further complicates lhe issue. In this paper we present a specific framework for representation and use of knowledge which appears to be both sufficient and efficient for a wide variety of image interpretation tasks.

The framewor·k for image interpretation presented here is b<~sed on the Locus model successfully used in speech understanding research (Lowerre and Reddy, 1977). The Locus model is a non-backtracking, non-iterati ve, deterrninistic search technique in which a beam of near-miss altern<~lives around the best path are extended to determine the near-optimal description of the image.

This technique is being applied to several tasks which together exhibit a wide range of image source variability, sensor characteristics, and noise characteristics. The three tasks currently under exploration are: interpretation of uncontrived arbitrary images representing different views of downtown Pittsburgh (3-D world); location of a landmark or identification of an image from satellite and aerial images of the Washington, D.C. area (2-D world); detection of changes in an image using symbolic techniques. The downtown Pittsburgh task involves several interesting subtasks: scene­ type identification (indoor, outdoor, office, ... ), camera position identification (scale, location and orientation aspects of the image}; im<~ge structure understanding (relative positions of buildings}; and image detail understanding (detect cars, bushes, people walking after the l<~rger context of a "road" is established}.

In the following sections we will outline the structure of the model, illustrate its use by a simple but detailed example, <~nd discuss the relationship of the present approach to earlier attempts at image interpretation. A detailed description of the model as applied to the image interpretation tasr, will be given irt Rubin (1977). A more complete discussion of the strengths and limitations of the

This work w<~s supported by the Defense Advanced Research Projects Agency (F44620-73-C-0074) and is monitored by the Air Force Office of Scientific Research.

model and it s relationship to the other approaches to knowledge representation and search are · given in Reddy (1977}.

I ma_p,~_W.!l9~r..!!t9DsliD.g_~ea rch ·

The basic premise underlying the Locus model is that the problem of image inter·pretation can be viewed as a probleh1 of seMch. Given a specific knowledge representation par<~digm and a specific signal-to-symbol transformation paradigm, a hiBhly efficient St~arch can be used to obtain a near -optimal global solution satisfy ing as many of the constraint s of the world model as possible.

The principal requirement of the Locus model is in the are<~ of knowledfle representation. Most approaches to image recognition assume the exi~. tence (ar1d availability) of a world model in terms of some internal . symbolic description. The wor ld model usunlly consists of knowledge which defines the structure and reliltionship among objects in all scenes !hill are interpretable by the world modeL By iteratively redefining higher level structures in terms of simpler objects one c11n generate a hierarchical network (or possibl y a relational semantic networll}.

The particular knowledge representation paradigm we have adopted in Locus is to attempt to represent all images that are adrnissible by the world model in terms of a graph st ructure whose nodes ar·e Primitive Pic.ture Elements (PPEs}. A PPE is chosen so that all pixels belonging to a given PPE class share the silme properties in the feature space (or signal space}. Thus il PPE might sometimes represent an entire object as in the c<~se of sr,y, river, or road, or represent a small subpnr t of <~n object such as a segment with simi lar textur<~l properties. As an exampie, the table below li sts the PPEs that have been identified in a typical scene of downtown Pittsburgh. Note that the PPEs are chosen for their structural uniqueness as well as their visual uniqueness.

Th~ <~bovc set of PPEs <1re prir·>ilri ly intended for use in the detail undcrstandin [~ sub-ta~·k of the downtown Pittsburgh im<1ge intcrp1·et~tion ta ~, k. These are by no means uniC]ue and ue given here purely lo illustrate the type of detail that can be ilpplied. However, at other levels of under sl anding (such as scene underr.landing or viewpoint understandinr,) I he number of PfJEs needed can be substantiillly (; fnaller. For example, on the scene understanding t ;d1, we pliln to use only 5 PPEs: Sky, Mountains, Buildings, River, and Park.

We assume I hat a set of !'PEs am available which can be used to compose any image that is admissible by the world model. Further we assume that most, if not all, of the constraints about object structure, size, shape, location, and orient ;~lion arc expressible in terms of the. graph structure containing only the !'PEs. It is obvious that this type of knowledge representation is likely to be expensive in terms of space for all except the most tri vial problems but it ilppears to be what is needed for iln efficient solution. Baker (1975) and Lowen·e (1 976) show how different types of l1nowledge ilnd constr ilints can be combined into a si ngle graph stn.1clure.

Let us conside1· an exa1nplc. The task is the labeling of a 'h2 scene. We will assume that thi s scene consists of three objects (P~'Es) called A, B, anrl C. Figure I shows the possible relationships that are allowed between A, B, C, and the scene ede,e. The arrows indicate the adjacency relationGhips between the objects and the boundaries. Note that either A 01· El m;;y be ilcljacent to the left, top, and bottom boundaries and that only C is permitted next to the right boundary.

The only relationships used in this network are horizontal and vertical.· It is poss ible to employ more contextual inforrniltion such as diagonal relationships, but this simple network is adequate for our example.

In the abr,cnce of any constraints, the optimal <~ssignrnent of PPEs to pixels can be obtained by selecting the best PPE label in each pixel neighborhood. However, given the semantic, syntactic, 5\ructural, ;;nd segmental properties of scenes that are acceptable within the world model, one wi5hes to' choose those assignments of PPEs to pixels that are both globally optimal and consistent with the model.

In ou'r example, each point in the 4x2 scene can be labeled arbitrarily from the three PPEs, allowing 3 8 possible interpretations. Given the network constraints, this reduces to only 9 possible labelings, shown below in Figure 2:

?: ~iik~B -~

These 9 labelings can be seen graphically in Figure 3 which shows the possible network paths that can be traversed while searching from the initial state to the final state. This is an unpruned recognition tree. II appears as a graph because some of the nodes have been combined to indicate the independence of I he path from the prior context. The nodes at po~dlions (2, 2), (2, 3), and (2, 4) have states arriving from the TOP and LEFT. This is the no1·rnal case for most PPEs in a larger irnae;e since the aver<1ge point is not along the top or left side. Note that for real pictures with real constraints, the comp lexi ty of the networks and the number of legal label ilssignmcnts is significantly higher.

?J.g_nnl-to-Symbol Matching

Matching the symbolic elements of the network to the signal requires il signal-to-symbol transformation technique by means of which one can edimate the likelihood that a given PPE is present at (or <:~round) a pixel location. This basically requires the availability of a pattern template for each PPE and a dis! a nee mcl!·ic for matching the unknown signal with the PPE templates.

Figure 4 shows the values at each posit ion in the sensed image for our example. Our task is to assign a label (A, £3, or C) to each pixel. Suppose the expected value (templates) of PPE objects are: A~4, 8=9, <md C=3. Then the question is which of the 9 possible interpretations given in Figures 2 and 3 best represent the signal. ·

For simplicity, let us assume that the distance metric is: Ail = I - li-il/10, yielding the following statistical matches for 'As, Bs, and Cs:

Th§)_Loc_IJ?_ M<2_®1

Given a PPE graph structure representation of the world model and a signal - to-symbol transformation technique, the problein of interpreting an unknown image can be viewed as finding the optimal path through the graph, i.e., finding a sequence of PPEs which best describe each of the pixel neighborhoods of the unknown image, subject to constraints defined by the knowledge sources represented by the graph. In our example, Figure5 2 and 3 provide two different representations of the constraint and illustrate the power of knowledge sources · in reducing the number of altematives.

Finding the optimal path through the graph is a classical search problem with many possible altemative search strategies (Nil sson, 1971 }. In this paper we propose and use a 5earch strategy called Locus which appears to be effective in perceptual problem solving. Locus is a beam search heuristic · in which all except a beam of ncar-miss alternatives around the best path are pruned from the search tree at each pixel (or segmental} decision point. This contains the exponential growth of nodes in the patl1 without requiring backtracking and non-deterministic search.

The Locus search proceeds as follows: 1) a forward pass calculates path likelihoods and inter-node connections, and 2} a backtrace uses the inter-node connections to determine the components of the ncar-optimal network path. As the forward pass search progres~;es through the network, unpromising alternatives are pruned and the interconnections along the beam are saved until the end of the network is reached. At this point, a backtrace of the connections is made to s~lect a path through the network. Note that this path is expected to lie in the beam that was carved out by the forward pass. By delaying the decision making process until all of the network nodes have been examined, Locus obtains the globally near -optimal path through the network. This is because the calculation of a node's likelihood hinges on all previous nodes that led up to it. Thus, during the backtrace, each node decision is guaranteed against degeneration because its likelihood is supported by all nodes before it. This means that the selection of an object label in one corner of the scene can affect the labeling in the opposite corner. Consideration of all of the near-miss alternati ves removes the need for backtracking, and thus removes the problem of whether to search by depth or breadth.

Before we can define the search strategy for finding the optimal path we need to define the term path likelihood in a PPE network. Path !l.t,elihood is defined incrementally in terms of the nodes it traverses and uses three pieces of information to calculate a likelihood: the statistical match of the signal to the symbol; the likelihoods of previous network nodes; and the tr ansition likelihoods of arriving from those previous network nodes. Formally:

where Pi j is the li kelihood of being in network state i at position j' of the ~en~ed data; Ai j is the slali~;tical match of the PPE symbol repre5ented by state i to the signal at position j; Cl(d) is the ~tnt e adjilcency function which offsets the current stale (j} to the previous sl ate (j·Cl(d)) in direction d; and T kid is the trC~nsition likelihood of traveling from state k to state 'i in direction d. For i1nage processinp_, the position (j} is an (x, ·y} vector . The maximum kin the above equation i5 saved as the best previous state and identifies the best pilth to take during the backtr;;ce. Note that the likelihood values <1re not needed during the bacr,lrace: they accumulate on the forward p<1ss only. The bacl\- pointers are calculated on \he forw<>rd pass usinp, the likelihood information, so they reflect all node transitions to that point. The backtrace uses only the best previous node for each 5\ate as it quickly steps through the network and selects a path. No search is perfoni1ed in this p~ss: it i,; pure look-up.

Going back to our example, Figure 6 shows the stal es that were exami.ned in the forwal'd pas(.. Note that this is simply a pruned ve·r sion of the recognition tree in Figure 3. The numbers above each node arc the lit-,elihoods calculated for that point on the forward pass. The first number is the forward pass likelihood which is calculated for each node at a given position. The second number is the normalized forward pass likelihood which is ca lculated after each node at the position has been exe1mined. The normalization is necessary to keep the likelihoods from degenerating ilS the network is traversed (discussed below}. Note that nodes are pruned from the beam when their un-norrnalized likelihood drops to 0.5 or below.

Let us look at the likelihood calcul<1tions for the point (2, 3} in Figure 6 (the -two squares in the third column}. The bottom point is a C, <1nd it is on the path which selects labelings number 6 through 9 (see Figure 2}. There are two paths from \he top and left that contribute to the likelihood calculations. For sil1lplicity, the transition likelihoods in this exal1lple will always be J .0 when lqj al. Thus, if a transition appears in Figure 3, it's likelihood is 1.0. Looking at the left context, the point <1! (2, 2} has a normillizcd lik.elihood value of 1.0. Since this is \he only node in that direction, it · is the maximum node in that direction (see equation 1} and so the likelihood from the left is 1.0. From \he top, the likelihood of being at point (1, 3} is also 1.0. Tal1ing the average gives 1.0 and multiplying thi s by 0.5 (the statistica l from Figure 5} match yields an un-normalized lil1elihood of 0.5 for thi s state.

The other node at position (2, 3) is a 8 on the path which includes labelings 1 throur,h 5. The statistical match of that point to PPE 8 is 0.6. Since there are two previous nodes to the left, calculation of the likelihood from the left involves finding the best previous ·node in that direction. In thi s case, the 8 in position (2, 2} is st ronger with a likelihood of 1.0. Since the likelihood from the top is 0.75, the average likelihood for that state is 0.87. When multiplied by the statistical match for !hill PPE, the un-normalized likelihood of that node becomes 0.79.

Once all node likelihoods are ca lculated, they are norm11lized so that the largest lil1elihood becomes 1 and the others increase proportionately. For this reason, the lop node expilnds to 1.0. The PPE for · C at position (2, 3} is pruned because it's un-normalized likelihood is 0.5. Note that the back-pointers which are saved here tell which previous node is the best. The ba~k-pointer for the top node at point (2, 3} selects the 8 at point (1, 3} from the top and the 8 at position (2, 2) from the left. The selection of the node to the left is done because that node had the greatest previous node likelihood.

The Cillculation of node likelihoods proceeds in a raster milnner. This means that \he order of calculation is (1,1), (1,2), (1,3), (1,4), (2,1), (?.,?.), (2 3), (2,4). When all of the likelihoods hilve b0en calculilled on the forward p<~ss, the backtrace makes a quick pass of the back-pointers to determine the global pillh. This backtrace proceeds in a rever'se raster milnner and follows the back-pointers left by the forward pass. Refering to Figure 6 again, you can see thilt the C ill point (2, 4) is the first point chosen for the global path. From there, two points are suggested to the top and left: the C nl (1, 4) ilnd the 8 ill (2, 3). The next point in the bilcklr<~ce is the [3 at (2, 3) whirh was indicated from the C to its right. II indicates the B in ( 1, 3) and the 8 in (2, 2). The b<~cktrace looks very simple but occasionally runs into snilg5. In this f'Xilmple, there is a conflict of back-pointers at position ( 1, 3). The state to its ri ght is a C and indicates that ( 1, 3) should be a C. The stflle below it is a 8 and indicates that (1, 3) should be a 13. Although conflict reso lution is very difficult and not fully solved, the solution here is obvious. The network does not allow a C at (1, 3) to exist above a 8 at (?., 3) and the B has illready been chosen. Therefore the 8 at (1, 3) is chosen because it does not contradict any network constr<~ints. Once the H at (1, 3)· is selected, the rest of the back\ race proceeds smoothly and path 4 is identified as the correct labeling.

This example shows an interesting property of the Locus search: error correcting without backtracking. Notice that the strongest path, from \he start, is the one .which leads to labeling 7. This i.s based on the weak assumption that the point (1, 3) is a C. In truth, it could be any PPE, but the network rules out A. Of the remaining.· choices, C is statistically betler than B, so the ·forward pass prefers C. On il globfll basis, however, 8 is better bec<1use path 4 is more globally consistent with the sensed data. This is because the point (2, 3) is strongly fflvored to be a 8 over a C, and it is not until the global path is assembled from the bflck-pointcrs !hill the mista~,e is corrected. If thi s dflta were run through a backtracking system which employed a best-first search, the incorrect pillh would be selected because of the search technique's inability to bring global context to bear on local labeling. If some way of detecting the error were found, the system would have to back up before continuing. In this example, Locus provides a better solution in the same flmOLml of time while in other cases, we can reduce the search time without Silcrificing accuracy.

Discussion

and Fu, 1976). The approach presented in thi s paper principally differs from the above in how the network represt>n\ation is to be used .. It rejects tho:> notion that image recO[lnition is bes t viewed a~; a problem in parsing. Given the error and uncertainty nssociated with the decisions, the problem tends to be not one of deciding whether a given pilttern is pflrsable but rather one of search, i.e., deciding which of the many accept able alternative paths represents the near-optimal interpretation.

The view that the problem of image recognition is one of constraint !;atisfying search has been gaining increasing acceptance (Waltz, 1975; Tenenbilum and Barrow, 1976; Rosenfeld, Hummel and Zucker, 1 976). This paper also subscribes to thi s viewpoint and differs mainly from the other efforts in the represenlfltion of constraints and the method of search.

The refllization that one needs to introduce some measure of the der,rec of lltKert<Jinty into the interpretation process is reflected in the papers by Fischler and Elschlager (1973), Feldman and YakimovsY.y (1975), and the probabilistic relflxfllion methods under development at SRI and Marylflnd. The method proposed here is able to handle search in the presence of error and uncert flinty in a natural and straightforward manner provided all knowledge and constraints are represented in terms of a PPE graph structure.

Constraint satisfying search in the presence of uncertainty is also a central problem in other areas of AI, in particulf\r in speech understanding systems research. Several techniques developed for use in the speech area such as representation of knowledge sources as cooperating independent processes (Reddy et al, 1973; Lesser et al., . 1975; Erman et ill., 1977), island driven search (Woods et al., 1977; Erman et al., 1977), and network representations of knowledge (Baker, 1975; Lowerre, 1976) also appear to be relevant to other knowledge based systems research, including vision. The Locus model presented here wfls first developed for use in the Harpy connected speech recognition system. Though the basic ideas remain the same, the model had to be revised substantially to make it useful in image recognition.

The best-first seat·ch given by the A* algorithm (Nils!·On, 1971) and the breadth-first graph search of the dynamic prograrnrning <~lgorithms (l_evine, 1 977; Bellman, 1962) provide alternative approaches to optimal graph search pt·oblems. The beam sef\rch technique of the · Locus model provides il minimal effort neflr-oplimal solution and appears to be effective in cases where the evaluation function is a

The model presented in this paper . has been used to function of an external signal source and where a large

interpret Ohlander·s city scene, demonstrating the initial number of decisions fire related to each other in that they validity and usefulness of the model. We plan to use the fire all attempting to provide alternative interpretations of model to interpret 11rbilrary views of downtown Pittsburgh (a the same signfll segment. 3-D wo"rld), and different satellite views of the Washington, Occasionally, the heuristics associated with the beam D.C. f\rea (f\ 2-D world). Representat·ion of the knowledge ·search lead to the elimination of the optimal pilth. This need about 3-D and 2-D world models in terms PPE graph not be cause for major concern because a good path will structure requires the development of several preprocessing always be chosen. Since the match likelihoods are less than programs (the PPE graph for Oblander's city scene was accurate, attempting to find the optimal path at great cost generillecl manually). In this section we will discuss the and effort leads to little or no improvement in performance. relationship of this model to other approaches in image The success of beam searching is highly dependent on recognition resef\rch, and our present views of the strengths the choice of the "near miss" .threshold that defines the width and limitations of this approacli. of the beam. If the threshold is too small, the resulting

The graph structure repre!·entation proposed here is a narrow beam of alternatives could lead to the pruning of the

naturf\1 outgrowth of work in languages (Aho and Ullman, correct path. On the other hand, many unproductive paths 1972), graph representations (Harlow, 1972), and syntax will be examined if the threshold is too large. In our present directed pattern recognition (Narasimhan, 1966; Clowes, 1969; system, the threshold is chosen large enough so as to make it

------·--------·--,immune to local errors in the assip,nment of lir,elihood values to symbols fr·om the ~;ignal.

A sir,ni fic ant feature of the Locus model of search is its linearity. Because Locus prunes al l but a narrow beam of al ternati ves, it s ~.earch time is lir1ear wi th respect to the size of the input sicnal and is essentially independent of the symbol spiKe ~·ize. Thus, locus searching controls the cornbinntorial explosion that occurs in most graph searching techniques. Note, however, that the size cit the beam exrilnds and contracts durinc the search as the connectivity between syrnbols ir1 the graph inueases and with the degree of uncertainty of the decisions.

The order of search in Locus is a subtle issue that <!ppeilrs to be a problem but upon closer inspection turns out to be unimport<mt. When using Locus in speech underst<lndins, there is one independent dimension of time which can be used to order the search. In image processing with static pictures, there are two dimensions, so a raster ·SCan is used. This might appear to cause continuity problems especi<llly ill the end of a scan line. However, Locus requires only the IOcil l context for a point and it propagates the global context rC'gilrdlcss of ~.ear·ch ordPr. Thus, any search pattern can be U!·ed as long as it is reversed on the backlrace. Note also that the r<lster scan has the advanlilge of allowing the use of context for horizontally, vertically, and diagonally adjacent sl<~tes.

A main concern with the finite state networks is lh81 not all rel8lional conslr~ints me easily represenl~ble within tllal frameworl\. We have not found this to be a problem in the 3-D ilnd 2-D worlds we hilve con!ddered so far, although the representation~; tend to be expensive in .terms of the space (memory) required. We expect to use a posl-pilss to apply constraints that ure not easily incorporated into the network.

Knowledge such as sh<~pe, size, orientation, and location of objects is different frorn spectral properties of objects such as color and texture infot·mation. This type of knowledge cannot be included directly as part of the signal ­ to-symbol match. Such supra-segmental knowledge can however be incorporated into the network in several different ways (Rubin, 1977).

The example given in this paper shows how the Locus model can be used in the interpretation of the image on a pixel by pixel basis. The technique is equally useful with pre-segmented data. In fact, segment alion improves accuracy ilnd leilds in subs! illltial ~·peed up in miltc.hing Hnd search. While extra segments do not cause any problem, missing segments Ciltmol be ac.comod<1ted within the .present scheme without additional computational effort. This is because the graph representation per·mits self-transi tions in the PPE network but does not (at present) permit skipping PPE nodes.

t;.:..Q,nclu~.9..!:l

This paper provides a framewor l\ for r,nowledge representation and search for· image recognition tasks, leading to an easily implernentable total systems frameworl', within which one can explore the relative merits of different types of knowledge. One still has to decide what knowledge is available, how to acquire and define it, how to select an adequate set of primitive picture elements (PPE) for a given I ask, and how to match symbols (PPEs) to the signal. However, each of these subtasks look much more manageable to us than the original image interpretation task.

Ac_l(_Q.~~Iegg~men~

The authors would lir,e to thank Larry Davis, David McKeown, and John Kender whose comments were. helpful in the preparation of thi s paper·.

6.RJ2.9JlcJi~_/l. _ _i'}(_)<;lLJ~.>5mnple

This 8ppendix shows the Locus n1oclel as it hils actually been programmed at Carnegie-Mellon University. The program which uses Locu~; i~; called ARGOS and this example is direct out put from the system. The scene that we are using is the downtown Pittsburgh image shown in Figure 7: I he most complex image w;cd by Oblander (1975). The image was broken down into 15 f'PEs shown below:

Figure 8 shows the labelings that were generated for the picture in Figure 7. The letters correspond to the PPE letters in the above list. Althotrgh this is not a perfect labeling by any means, it is an improvement over un-guided labeling and shows that Locus is effective for image interpretation.

• Aho, A. V. ilnd Ullman, J. D. (1972). The Theory Qf. P.arsing 1 IIA~_sl!l.L!9J1. ~1.ncJ. Q.QI:DR.iJ.i.~R. Prentice-Hall, Englewood Cliffs, N.J.
• Baker, J. K. (1975). "The DRAGON system--An overview", l.EII Trans. _1\cou ~J., Speech, ~.&llill Processing, vol. ASSP-23, 24-29, Feb.
• Bellman, R. and Dreyfus, S. (1962). ~ Dynamic E'I.9RL!l.D.ll}lillR, Princeton Univ. Press, Princeton, N.J.
• Clowes, M. C. (1976). "Pictorial relationships - A Syntactic Approach", in !0..i!_<J:lj.!.l_Q. )Dtel!ig~lce IV (Meltzer and Michie, eds.), Arnericiln Elsevier, New York.
• Erman, L. D., ct al. (1977). The Hearsay-11 System, (in preparation).
• Feldman, J. A. and Yakirnovsky, Y. (1975). "Decision Theory <~nd Artifi cial Intelligence: I. A Semantics Based Region Analyzer," ~LE!.l.<Jpl !.!.l.Lc:ll!gr;_t}~_Q; vo l 5, pp. 349-371.
• Fischler, M. A. and Eschla::;er, R. A. (1973). "The Representation and Millching of Pictorial Structures," IEEE Tr i!_nsilclions on QQ!:!!J?Jd!QI2.. J<muary.
• Fu, K. S. (1976). "Syntactic Pattern Recognition," in f)igital Piltlern He<:.Q:~!iO.D. (Fu, eel.), Springer Verlag, New York.
• Harlow, C. A. (1972). "Image Analy:ds and Graphs," TR IAL-TR J 7-72, !mace Anillysi(; Laboratory, University of Missouri­ Columbia, Septernber.
• Levine, M. D. (1977). "A Knowledge-Based Computer Vision System," Work5hop on Computer Vision Systems, Vol. II, University of Massachusetts, Amherst, Mass., June, 1977.

Lesser, V. R., Fennell, R D., Enmm, L. D., and Reddy, D. R.( 1975). . "Organization of the Hearsay-11 Speech Unders t<~nding System," II:.EE Trans. Hum. Factors !J~_<:.U.P.!b vol. ASSP-23, 11-23.

Lowerre, B. T. (1976). ''Th(~ HAf~PY Speech Recognition System," (Ph.D. Thesis, Carnegie-Mellon University), Tech. Report, Computer Science Department, Carnegie-Mellon University, Pitlsbu1·gh, PA.

Lowerre, B. T., and Reddy, D. R. (1977). Search in the Harpy Connected Systf'rn,'' pape1· to be publi shed. "Represent at ion and Speech Recognition

Narasimhan, R (1966). "Syntax-OII·ccted Interpretation of Classes of F'iclures," Communications Qi the ACM, vol. 9, no. 3, March.

Nilsson, N. (1971 ). Problcl1l Solvin~ Methods ill. Artificial l.!.l.l~IJlR~l'l<:.Q, McGraw Hill.

Oblander, R. B. (1975). "Analysi~; of Natural Scenes," (Ph.D. Thesis, Carnegie-Mellon UnivNsity), Tech. Report, Computer Science DepartiYoent, Carnegie -Mellon University.

Reddy, D. R. (1977). "Asper!~; of Rcp1·esentation and Search in Perceptual Problem Solving," (in preparation).

Reddy, D. R., Erman, L. D., and Neely, R B. (1973). "A model and a . system for rnachine nxognition of speech," IEEE Tran~~ AudJQ El edc_Q_ilcous_L vol. AU-2 1, 229-238.

Rosenfeld, A., Hummel, R. A. and Zucker, S. W. (1976). "Scene labelling by relaxation ope·rations," IEEE Trans. Syst., McH\ QLQ.~Ilb SMC-6, 420-433.

Rubin, S. M. ( 1977). "The ARGOS Image Understanding System," (Ph.D. Thesis, Dept. of Computer Science, Carnegie -Mellon University), (in preparation).

Tenenb<Jum, J. M. i11ld Barrow, H. G. ( 1976). "Experiments in Interpret at ion-Guided Scgrnent at ion," Technical Note 123, Stanford Research Institute, Menlo Park, CA.

Wnltz, D. ( 1975). Understanding Line Drawings with Shadows, in Thg_ E'.~J'.C.lJQjQgy_ Qi QQ.I}}Q_L!l_e.I_ VisjQn, (P. Winston, Ed.), MIT Press, Cambridge, MA.

Woods, W. W., et al. ( 1977). "Final Report on Speech Understanding Systems," Bolt, Beranek and Newman Inc., Cambridge, MA.

.... ---,- -