A Semantics-Based Decision Theory Region Analyser

1. THEORY

The underlying theory of our system is Bayesian decision theory. The ideas are quite beautiful and powerful, but have not rece ived as much attention as they should from artificial intelligence workers. Even a brief description would be beyond the scope of this paper: '~lementary Decision Theor y '' and '~ec ision Analysis - Introductory l ecure s on choice under uncer­ tainty" are good introductions and "Optimal Statistical Decisions'' and 'Mathematical Statistics a Dec~sion Analysis Approach" are advanced texts.4 , 20 , 5 , The two central ideas are the use of a utility function t o measure the value of various alternative s and an opti­ mality theor em. This theorem shows that any adequate (admissible ) strategy is equivalent t o a strategy of maximi zing expected utility for some choices of ut ility function and probabilities. The theory provides a com­ ple te world view ( like , e .g. logic ) and has been ap­ plied t o many management probl ems. The difficulty in practice is that it is difficult t o s e l ec t the utility and probability functions and t o actua lly carry ou t the computations. We describe below how we attack these problems.

For r egi on analysis, we can define the utility t o be the pr obability that the analysis is correct, con­ tingent upon two factors: the (a prior i ) context know­ l edge about the picture domain, and the values of measurements on this particular image, i. e . we are t o

maximize:

ABSTRACT

The prob l em of breaking an image into meaningful regions is conside r ed . Bayesian decision theor y is seen t o provide a mechanism for i nc luding problem dependent ( semantic ) information in a general sy stem. Some results are pres ented which make the computation feasible. A -programming system based on these ideas and their application to r oad scene s is described.

INTRODUCTION

The problem of segmentation, breaking a complex image into sections, is a central problem in machine perception. The analogous problem arises in the analysis of speech and, fo~that matter, in any pro­ blem of overwhelming size. We will concentrate on the image segmentation problem, but most of the ideas are of wider applicability. The main idea is t o apply (Bayesian) decision theory techniques and the use of problem-dependent information ( s emanti cs ) t o attack the image segmentation problem.

The segmentation problem for T.V. images is as follows : given a picture of some scene, we have a rectangle composed of some 200 x 300 points and f or each such point some information on the light in­ tensity and perhaps col or. For any further process­ ing 60000 points is far t oo many , so , depending on the perception task that we have in mind, the image should be segmented int o regions. Each of these r egi ons should be meaningfillin the problem domain and the relevant information needed f or the spec i f ic task should be easily obtainable .

There has been a great deal of work on segmenting ima~es and a certain limited success has been achiev­ ed. 1 Some biol ogica l and me t eor ological images can be eff ectively segmented using known techniques. How­ ever, f or images like those arising in road scenes or pres ented t o assembly-line robots, the existing al­ gorithms do not suffice. A maj or problem is that the existing algorithms use absolute criteria such as in­ tensity difference, boundary strength, etc. t o f orm regions. 2 ·3 But the criteria for what is a "region" will surely vary with context. Certain shades of green , yellow and brown might be merged into a single region of grass in a scene, ye t distinguishing the same set of col ors might be crucial f or r egion sep­ aration in another scene or even in another part of the same scene (assume for instance that a yellow car occludes part of the grass ) . Another critical consideration is the goa l of the percepti on. For some problems s eparating the green grass from yellow grass will be essential, in others compl et el y con­ fusing.

The importance of goa l direction and context­ depend ence for e ffective probl em solving is now well understood in artificial inte lligence and scene ana l­ ysis is just another example . One can certainly write a special purpose r egion analyzer for a fixed

class of image s and it will work better than any gen- P(global-interpretation context,values of measurements )

An interpretation will divide the image into re­ gions and attach a type label (meaning ) to each re­ gion. One choice of evaluating the overall interpre­ tation would be obtained by considering each region independ:ntly. If for a .~iven partit~on of the ima~e into reg~ons we have {R ( ~ ) i=l,n} reg~ons then the ~n­ terpretation assigns label INT ( i) to region R( i). The values of INT( i ) will be sky, grass, r oad etc. depend­ ing on context and goals. Then assuming independence we will want to max imize the expression:

over all partitions of the image into regions and assignments of labe ls to r egions. This is quite conventional so far and is, in fact, too simple for our purposes. We want t o account f or two additional considerations. First we must use the mode l to get a good s egmentati on of the image into r egions. For exampl e , we might want t o merge green, yellow and brown patche s t o crea te the whole area that we call grass. Secondly, we want t o use additional s emantic constraints e.g. the grass is below the sky, t o in­ fluence the total probability of an analysis of the

scene.

In an attempt t o enrich the semantic structure t o support more of the probl em knowledge and to provide f or control mechanism on the region growing algoiithm, the semantic structure was allowed to have also "first order struc ture". In addition to the propertie s of each individual region we have , f or each pair of ad­ jacent r egions of some interpretations, expected r e lative properties and some expected features of thcir common boundary line. For instance if we have two adjacent regions, one which is named "sky" and the other "hill" then we expect that the sky is above the hill, is a brighter blue than the hills, and that the boundary is usually a more or l e ss horizontal smooth line. The relative properties are usually mor e signi­ ficant than the absolute properties since they are l ess sensitive t o variation between pictures. This semantic model is t oo limited to describe all that is known o f a scene , but many cl~sses of scenes can be segment ed pr operly with first order methods.

Recall that we want t o get a partition of the in­ put and interpretation for the segments ( regions ) and boundaries s o as to maximize the like lihood of having the right interpre tation. Let R( i ) be the i-th regia~ B(i,j) the boundary between region R(i) and R( j ) ( if it exists) and the label of R( i ) be INT ( i ) . Then with our first order assumption the expression that we want t o max imize is:

. Pfgl obal interpretation I values of measurements} = 7J P(R( i) is INT(i) I values of measurements on R(i)) ~ x1 I PfB(i,j) is between INT(i) and INT(j ) I B(i,j ) 's measurements} B(i,j )

[ 1]

The use of [1] repres ents more than just our be­ lief that properties of individual r egions and bound­ aries will suffice for our semantics. It also entails an assumpti on that the probability can be factored in­ t o the product above. This amounts t o assuming that the probabilities of interpretations of each region (boundary) are dependent on the local properties of the individual region (boundary ) and are independent of all other measurements. Thus boundary B( i,j ) which is the boundary be tween R(i) and R(j) is evaluated as bounda ry between INT (i) and INT( j ), where R(i) is label ed INT ( i ) and R(j) is labe l ed INT( j ) .

For exampl e , if INT(i) is "sky" and INT(j) is "hill", the evaluation will include fact ors involving the expected direction, smoothness, etc. of a bound­ ary be tween sky and hill. Thes e factors are assumed to be independent of the particular color etc. of the sky and hill. If the independence assumption seems t o be unreasonable, consider the f ollowing argument:

Now

Pfvalues of measurements on R( i ) I R( i) is INT ( i ) , context}

and

Pfvalues of measurements on B( i,j ) I R(i ) is INT(i ) and R( j ) is INT(j) ,context}

are plausibly considered independent of each other. A similar argument can be used for the factori zation of the other two t erms in the expression on the right of [l]. Putting the se t erms t ogether give us back what we have in [l]. From all picture models which were described in the literature the model described in r ef­ erence 17 is mos t similar t o ours in the basic metho­ dology aspects.

For a given utility function ( like [ l l) there are standard t echniques in decision theory for finding the maximum utility. Unfor tunately , the general t echniques are t oo sl ow and much of our effort has gone into de ­ vel oping algorithms f or e ffici ently computing an ap­ pr oximately optimal partition. The r egi on growing al­ gorithm starts with many small r egi ons and on each iteration merges two adjacent r egi ons ( r egi ons with a common boundary) . The two basic decisions are which pair of regions t o merge on each iteration and when t o stop the algorithm. Thes e two decisions can be con­ troll ed direc tly by the limited probabilistic semantic

world mode l that we have .

In general, on each iteration of r egi on growing the pair of r egi ons whose common boundary is the weak­ est in the current image partition will be merged . Hence the control of the r egion grow ing algorithm is by evaluation of the boundary strength. We will show how our semantic r epresentation can be used directly to compute the goundary strenth.

The second task of the semantics is t o pr oduce the stopping criterion for the region grower. In our case since we want t o maximize

P(interpretation I measurements' values , context}

the optimal partition will be the one with that inter­ pretation which maximi zes this likelihood estimate over all partitions and all possible interpretations of par~ itions which do not allow false boundaries (boundaries between two r egions which are interpreted as parts of the same final object).

In order t o have an e ffective way t o determine that probability we need a relatively fast way t o ob­ tain or approximate for a given partition the optimal

interpretation and its value.

In the next section, we will describe relatively fast methods for computing upper and lower bounds on the optimal va l ue of the probability of a given parti­ tion.

The bounds on the value of the global interpreta­ tion will be used as follows: The algorithm will col­ lapse regions, and generate a sequence of image parti­ tions. For each partition generated, the bounds on the possible value of the best interpretation will be evaluated. Then when the collapsing has been carried too far (as observed by strong decline of the possible interpretation value ) the system will back-up to the most promising partitions observed while growing the regions (as indicated by the lower and upper bounds estimates of the quality of the partition observed) . Next we will search for the best int erpretation for the partitions observed whose bounds were high enough to make it possible that they are the best partition observed. The current algorithm will simply choose the best of the se , but more sophisticated procedures can be used if necessary.

Althernatively we can use the procedure which assigns meaning t o all regions directly as the stop­ ping criterion. That is, if the best global assign­ ment f ound for the given image partition does not interpret any boundary as an erroneous boundary (e.g . a boundary between r egions of the same interpretation) we stop merging ( see discussion below on l ower bound estimates for the image partition for mor e details ) .

2 . PROGRAM ORGANIZATION

The program has four basic sections: 1) the initialization, 2) initial assignment and boundary strength evaluation, 3) heuristics t o evaluate a part­ ition by approximating its optimal assignment, and 4) a limited interactive l earning system.

The first step is t o take a vector of values of measurements at a set of sample points ( in our system usually 500-1000). The local measurements currently indicate only the dominant gray level around the sample point or if the image is observed through seve~ al color filters the dominant gray level through each of the col or filters.

We employ a preliminary region-merging for init­ ialization. The idea is t o use a very crude algorithm on the reduced problem. The simple merging algorithms considered were:

1. Take an image point and grow a r egion around it consisting of all image points which can be connec~ ed t o the starting point by a path of points which satisfies the following conditions: a) each adjacent pair of points along the path are adjacent geometri­ cally , b) the jump in the value of the measurements vector be tween two adjacent points along the path is less than some threshold. 2 ·3 Note that some modifi­ cations are needed to treat gradual but strong change~
2. This initialization is an extension of 1. It initializes as in 1 and then collapses, independent of order, all boundaries with strength less than some threshold. The advantage here over method 1 is the option t o use more s ophisticated boundary strength evaluation.3

Our initialization method utilizes a sampling technique initialized as in 1 ( taking the connecting path to be a path of sample points ) and then merges regions iteratively by e liminating the globally weak­ est boundary first. That is, on each iteration the pair of regions whose common boundary is weakest in the current image partition is merged into one r egi on.

The boundary strenth in this stage is evalua t ed directly fr om the differences across the boundary and its geometrical structure.28 The stopping crietrion in this case can be a threshold on the weakest boundary, that is the merger is stopped when the weakest boundary · is stronger than a given threshold. This threshold is chosen very conservatively s o as t o stop this simpl e minded region grower be f or e it produces false merges. In our experiments it t urned out that the simple init­ ialization algorithm had to be stopped quite early so that the s emantic control was call ed with about 100 r egions present, see reference 28 f or mor e details.

The main algorithm first computes additional pro­ perties ( like shape) of the r egions and boundaries r e ­ sulting from the initialization. It then assigns prob­ abilities t o the t entative interpretations of the re­ gions, i.e. computes

P(R(i) is X I values of measurement on R(i)}

The boundary strength may be evaluated by two re­ lated methods: 1) the probability that the boundary is a real boundary (a boundary between different obj ects in our semantic world model ) and 2) the change in the value of the interpretation as a result of el iminating the boundary. We will ·describe here the first of these which is the one currently used . The second me thod has some advantages and will be discussed be l ow .

We approximate the probability of the boundary to be real as follows:

INTl,INT2

The next step is t o search f or a partition which yields a good value of (1]. This involves both form­ ing partitions and computing the value attainable f r om a labelling of regions in each partition.

A l owe r bound on the value of an image partition is computed by actually finding a good global inter­ pre tation using a simple fast algorithm. Briefly what we are doing is to take the region of highest confi­ dence interpretation and assign to it its most probable interpretation. This assignment allows the program to updat e the probabilities of adjacent regions of the newly interpre ted region by considering the boundary features of the newly assigned r egion. Then the r egion of highest confidence from all un-interpreted r egions is assigned, etc. This is essentially starting a depth first search of the tree of interpre tations and yields a value for the partition which is the desired lower bound. Extending this search to full tree s earch would yield the optimal interpretation. More details on the sequential assignment process are given below.

Recall that we want to approximate the maximum possible value of the expression in [3] over all possi­ ble values of INT ( i ) for a given picture partition.

The assignment procedure we use to estimate the best possible assignement of INT( i ) for all R( i ) for a given image partition is as follows:

1. Compute for each region the ratio (based ju~ on local measurements of the region) be tween the most likely interpretation and the next most likely inter­ pretation. This ratio will be called the CONFI (REG) . Let xl be such that P(R is xl values of measurements on R) is max imized f or R and let x2 be such that PfR( i ) is x2 values of measurements on R( i ) } is the next highest. Then

P(R( i ) is xl measurements of R(i )

1. Sort the regions by their confidence ratio.
2. Assign the region with highest confidence ( the one wi.th highest ratio) its most likely inter­ pretation.
3. Update probabilities of different assignment t o regions that were not assigned already, assuming that the last assignment is true. Let the region assigned most recently be R( l ) and its interpretation be INT( l ) . Now if R(i) has boundary B(l,i ) with R( l), then f or any interpretation x of R( i ) in evaluating equation 1 above, there will be a term of the form

from the first product and one of the form

from the second product. There fore a better approxi­ mation of the probability of R(i) being x, assuming that R( l ) is INT ( l ) , is

Thus we use the new information t o find a more accurate pr obability f or the different possible assig~ ments for R(i), by counting the newly int erpreted r e ­ gion R(l).

We do that updating t o all possible interpre ta­ tions for all adjacent r egions of R(l) .

1. Compute the new confidence ratio and r esort the r egi ons by the new confidence ratios .
2. If any region is still unassigned go t o step 3 else exit.

This process of assigning interpretations itera­ tively .provides a good guess on the possible best in­ terpretation, but it does not guarantee the total maximization of our product. We can extend the current algorithm into a full tree search (undoing some assig~ ments and trying alternative ones) to get the best in­ t erpretation. This will be a depth first search in the tree of all possible assignments, where each node will stand for the assignment of a meaning to a regio~ For efficiency purpos e s we can use vari ous pruning techniques t o reduce the search effort required to secure optimality.l6 Our current algorithm is the portion of the tree search up t o the point where we get t o the first terminal node ( first global assign­ ment ) . One should also note that the same sequential assignment and extension into tree search can be applied to an extended first order world model, where we allow relations between any two r egions (not ne ­ cessarily adjacent ) if we continue to assume indepen­ dence . The only difference is that we will have to update the probabilities and confidence of all regions not just those r egi ons adjacent t o the newl y inter­ preted region.

We have the option t o use this assignment pro­ cedure as a region grower by taking all pairs of ad ­ jacent r egions that were assigned the same meaning and merging them. To avoid false merging we consider all regions which were assigned meaning with a low confi­ dence level not mergable into other regions. This approach may be extended by adding it t o the meaning assignment algorithm as a new step 3·5· If any ad­ jacent region of the newly interpre ted r egion is al ­ ready assigned a meaning and it is identical with the meaning of the newly interpreted r egion, then merge the two together. From that point on the unified region will be consider ed in updating probabilities of other, not yet interpreted r egions.

We can use the two extensions (merging on the run, and full tree search) together. This will generate a very reliable meaning assignment concurrent with a re­ gion grow ing procedure which has backup capabilities. It will b~ however, r e latively slow.

Upper Bound

The upper bound is computed by r elaxing the con­ sistency constraint. This condition means that a boundary between two regi ons of known interpretation has to be counted in as a boundary between those two interpretations. We r e lax this condition by breaking the product (1) into local sub-products and finding the best local interpretation for the t erms involved in this subproduct. We take the best possible value for each sub-product separately, and, multiplying them, obtain in an upper bound on the value of the best gl obal interpretation. One such relaxation is to con­ sider all regions and boundaries independently and to assign for each the best possible interpretation con­ sidering only its own properties. The product of all these probabilities is an upper bound on the value of equation 1. It is this sort of estimate which would be used t o approximate the single step impr ovement in the second method of boundary evaluation mentioned above. An exact computation of the change in interpretation value would be t oo time consuming. We do not ye t know which boundary strength computation will be bette r.

Given the lower and upper bounds of the value of the best possible interpretation for a given picture partition, a variety of graph searching techniques can be applied t o find a suitable interpretation and t o pick out the best partitions observed f or more detail ed investigation using the full semantic knowledge .

3 . LEARNING

One of the basic problems with any recognition sy stem is the deve l opment of sharp classification cap­ abilities for objects ( in our case interpreting r egions and boundaries ) . Our case is especially complicated since we need t o recognize portions of objects, spur­ ious boundaries and to overcome partial occlusions. To make the game of developing these capabilitie s easier we developed an interactive learning system. Its main task is t o carry out bookkeeping j obs, t o estimate pro­ babilities, and t o point out pitfalls and options for impr ovement in the classification scheme.

The non-parametric approximation of the probabi­ lity density function works as follows: Given a set of measure functions on some class of objects, we break the space of all possible combinations of values of those measurements into cells (not necessarily cartesian), trying to get an effective classification. That is, given that the values of the measurements of an object fall into some cell, we want that often the probability estimate of the real meaning of the object t o be high. Given a fixed partition of the measurement vector space into cells we want t o learn the probabil­ ities of different interpretations of objects whose measurements' values fall into a cell. This is done by keeping, for each cell and for each possible inter­ pretation, the count of how many times in the past the value of the measurements of objects of that inter­ pretation fell into this cell. The probability of that interpretation is just the number of times the measurements of an object of that interpretation fell into the cell, divided by the t otal number of objects which fell into that cell.

This brings us to the second learning system which would try to create a cell structure with as few cells as possible while attaining a good classifica­ tion among the possible interpretations. For this purpose we sould utilize an augmented classification tree whose leaves correspond to the cells. The aug­ mented tree also allows representation of the fact that two measurements are independent.

Currently this tree is generated interactively. To generate a sub-optimal classification tree auto­ matically the system would keep a whole history list containing objects observed in the past, their prop­ erties and their real meaning. Based on this history the system could try to order the application of measurements so as to get good and cheap classifica~ tion, creating as few as possible cells (leaves ) , while still keeping the good classification probabil­ ity high. It also has the ability t o point out cells that are not sufficiently discriminating so that they may be worked on interactively or automatically (primarily by breaking each such cell into finer sub­ cells, so that for each subcell the classification is more reliable ). A detailed description of this learn­ ing and classification system is given in reference 28 . Techniques for organizing the classification tree so as t o get near optimal sequential classification is described in Slagle and Lee, where game (a-b) type . tree search is utilized in creating the decision tree .23

Such learning techniques are common to many pat­ tern recogni tion and sequential dec ision problems. A vast amount of research, both theoretical and experi­ mental, has been done in this area. Reference 10 is a good description of the theory and Reference 6 is a good introduction to various applicable t echniques. It is interesting t o comment that a l earning scheme similar to the first ( empha~~zing correlations ) was developed by Arthur Samuel. Attempts are now be­ ing made to apply this learning scheme t o speech seg­ mentation and r ecogniti on. 2 5

It is interesting to compare our technique with the nearest neighbor classification which is investi­ gated in various- papers. 29 This principle is to tak~ for a new unknown occurence of an obj ect, the inter­ pr e tation of the object obs erved in the past whose features of the new object. There are two deficiencies in this approach. First, only rar ely is there an ob­ vious metric on the space of values of measurements, and hence only rarely is it clear exactly how to mea­ sure distance in the features of two objects . Second­ ly, it is very hard to search f or the nearest object observed in the past (unless we are in one dimension) since we have to compute the distance from many ex­ ampl es observed in the past to get the minimal dis­ tance. An effective way of reducing the search time will call for breaking the space into cells the way we do. That is, locating first the cell into which the measurements of the new object fall aqd then searching only among known objects whose measurements fall into that cell for the nearest one, ignoring objects which fall into other cells. Thirdly, the answer returned is just one possible interpretation and not a list of different possible interpretations with various prob­ abilities. Extending the nearest neighbor principle to find the n- nearest objects and computing the pro­ babilities of different interpretations based on them will make the computation even less efficient because of search time and will force even more reliance on space partitioning than the method we currently use.

4 . RESULTS AND CONCLUSIONS

As a first experiment, the program was applied to the problem of segmenting images which might be seen driving on a road in the vicinity of the laboratory. The analysis was simplified by assuming the camera was in an upright position. There were six possible labels for a region: sky, road, roadside vegetation, car, shadow of car and tree. The non-terminal nodes in the classification tree are calls on integer valued func­ tions. Some properties and the number of possible values for each are: light intensity (4) , color hue (8l color saturation (4) , size (5 , logarithmic), vertical position (4) , horizontal position (4) , position on edge of image (4) and some crude shape descriptors.

With six types of region, we get 18 (6x6/2) types of boundary. Some boundary properties used, with the number of values for each are : r~lative size (6 log­ arithmic ) , relative intensity (6, logarithmic ) , rel­ ative color (3 green relation x 3 red x 3 blue), boundary shape and orientation (21 classes ) , relative position (4 right extremes x 4 left extremes x 4 above extremes x 4 below extremes), boundary length (5) and position of boundary in frame (5x5) . The algorithms for computing the various properties and the discrim­ ination in each were chosen intuitively.

Initial values for the counts in cells were also set intuitively, and the learning routine was used interactively to refine them (approximating the pro­ babilities and breaking cells to finer cells if desir­ ed for better classification) .

The program was able t o segment the scenes cor­ r ectly using only region properties except that it had difficulty isolating the image on the car on the road. Since a car can be of any color, the program either needs to make use of boundary relations, (e .g. the car is on the road ) or perhaps shape discrimination should be made more sophisticated.

A region growing algorithm based on absolute pro­ pertie s would not work in these scenes mainly for the following reasons: 1) The trees and sky generated very many regions that were more varied in the values of their measurements than any other thing in the picture. 2) The sides of the road are patches of brown, green and yellow . 3) Strong shadows appear frequently on the road.

The second domain to which the system was applied was left ventricular angiograms (x-ray images of the left ventricular made visible by injection of a radio­ opaque dye). These angiograms are useful for various cardiologic applications since they allow observation of myocardial movement. The semantics used for this application described the heart interior, chest cavity background and the dark frame border. No color was available here, and as a result light intensity, posi­ tion and shape was the major recognition tools. In addition the non-semantic region grower had to stop at a relatively early stage because of noise and lack of high contrast border. The number of regions on term­ ination of the non-semantic region grower was two hundred. It is encouraging that the adjustment to the second domain was very easy. We hope that in the fu­ ture a general and rich library of feature extracting routines with the capability of working on many mode ls will be achieved.

Shown below are illustrations of the results of experiments . All pictures are taken from a graphics terminal with gray level capabilities. There are six bits available per image point. Five are used for displaying the original picture, while the high order bit is used for the overlay of displaying the boundary lines.

This is a preliminary version of a general system for utilizing decision theory in scene analysis. There are a number of ideas from both areas that have yet to be tried and many experiments yet to be run. However, there are already some additional considera­ tions which should be mentioned.

The most restrictive assumption in the current program is assumption that the interpretation of a region depends only upon adjacent regions. There are ways of selectively relaxing this rule so that oc­ cluded objects can be understood without having each region depend on all others. In fact, the entire approach wil l stand or fall on the question of whether there is sufficient independence to allow for good performance without prohibitive calculation cost.

The choice of l ocal measurements around each point is, of course, another crucial factor. The idea of relatively coarse sampling allow us to apply more operators, including ones like Hueckel's, or l4 texture finders which inherently involve many points. There is the additional important potential f or vari­ able density sampling, possibly using planning in the manner of Kelly.l5

A more difficult task would be to effectively in­ corporate 3-D constraints, as done so successfully for blocks by, i.e., Falk and Waltz ( this would call for the addition of vertex properties ) .7 , 27 There are many possible refinements to the l earning procedure, especially on the question of what measurements are important.

BIBLIOGRAPHY

1. Barrow, H.G., Ambler, A.P. and Burstal, R.M . "Some techniques for recognition structures in pictures" Department of Machine Intelligence and Perception, University of Edinburgh, 1972 .
2. 2 . Barrow, H.G. and Popplestone, R.J. ''Relational Description in Picture Processing" Machine In­ telligence, 6 , 377- 396 , 1971 .
3. 3 · Brice, C.R. and Fennema, C.L. "Scene Analysis Us­ ing Regions" Journal of Artificial Intelligence, 1, 205-226, 1970 .
4. 4 . Chernoff, H. and Moses, L. "Elementary Decision Theory" Wiley Publishing Company, N.Y., 1959 .
5. 5 . De -Groot, M.H. "Optimal Statistical Decisions" McGraw-Hill, N.Y ., 1970 .
6. 6 . Dud a, R .D. and Hart, P .E. "Pattern Classification and Scene Analysis" Wiley, 1973 ·
7. 7 · Falk, G. "Computer Interpretation of Imperfect Line Data as a Three Dimensional Scene" Arti­ ficial Intelligence Memo 139 , Stanford Univer­ sity, 1970 .
8. 8 . Ferguson, T.S. 'Mathematical Statistics, A Decision Analysis Approach" Academic Press, 1967.
9. 9 · Feldman, J .A. "A Way of Looking at Things " Dept. of Computer Science, Hebrew University, Jeru­ salem, January 1971.
10. 10 . Fu, K.S. "Sequential Met hods in Pattern Recogni­ tion and Machine Learning" Academic Press, N.Y ., 1968.
11. Griffith, A.K. 'Mathematical Models for Automatic Line Detection" JACM, 62- 8o , 1973 .
12. 12 . Guzman, A. "Computer Recognition of Visual Object in a Three-Dimensional Scene" M.I.T., 1969 .
13. 13 . Harlow, C.A. and Eisenbeis, S.E. "The Analysis of Radiographic Images" Technical Report, Dept. of Electrical Engineering, University of Missouri­ Columbia.
14. 14 . Hueckel, M.H. "An Operator Which Locate Edges in Digitize Pictures" Artificial Intelligence Memo ~. Stanford University, 1969.
15. 15 . Kelly, M.D. "Visual Identification of People by Computer" Artificial Intelligence Memo 30, Stan­ ford University, 1969·
16. Nilsson, N.J. "Problem Solving Methods in Arti­ ficial Intelligence", McGraw-Hill.
17. 17 . Preparata, Franco P. and Ray, S .R. "An Approach to Artificial Nonsymoblic Cognition" Information Science, 4 , 65 - 86 , 1972 .
18. 18 . Pingle, K.K. and Tenenbaum, J .M. "An Accomodation Edge Follower", IJCAI-2 .
19. 19 . Quam, L.H. "Computer Comparison of Pictures" Stanford Artificial Intelligence Memo 44 , Stan­ ford University, 1968 .
20. 20 . Raiffa, H. "Dicision Analysis - Introductory Lectures on Choice Under Uncertainty" Addison Wesley, July 1970 .
21. Rosenfeld, A. "Picture Processing by Computer" Academic Press, N.Y. 1969 ·
22. 22 . Samuel, A.L. "Some Studies in Machine Learning Using the Game of Checkers II - Recent Progress" IBM Journal of Research and Development, 11, 601617, 1967 ·
23. 23 . Slagle, J .R. and Lee, R.T.C. "Application of Game Tree Searching Techniques to Sequential Pattern Recognition" CACM, 103-110 , Feb. 1971.
24. 24 . Thomas, A. "Color Perception" Stanford University 1973·
25. Thosar, R.B. and Samuel, A.L. "Some Preliminary Experiments in Speech Recognition Using Signa-

• ture Table Learning" Artificial Intelligence Memo, Stanford University, ( to appear ) .
• 26 . Vicens, P. "Aspects of Speech Recognition by Computer" Artificial Intelligence Memo 85 , Stan­ ford University.
• Waltz, D.L. "Generating Semantic Description from Drawing of Scenes with Shadows" M.I.T. TR-271.
• 28 . Yakimovsky, Y. "Picture Processing, Use of Prob­ abilistic Semantics for Region Growing and Rec­ ognition~' Stanford University. (Forthcoming dissertation) .
• 29 . Cover, T.M. and Hart, P.E. ''Newest Neighbor Pattem Classification" IEEE Trans. Information Theory, Vol. II-13 , 21-27 , 1967 .

(8-4! Result of grouping regions by their assigned meaning. Taking only regions ~hich ~ere assigned meaning ~i th confidence over 18 to be mergable.

!F -2-3-4) Iterations of semantic region.gro~er. The region gro~er used IS grouping of alI adjacent regions ~hich are assigned the same meaning by the sequential assignment procedure, before the first ass i gnmen·t ~ i th I o~ confidence I eve I occurs. On each iteration the confidence threshold is lo~ered.