0:! L I. ”I. I [IUYHUMf 0: w.” JII . rill. ' I ., .. I , L1H. . l J I..(¢Hvl,ltll c it -IJII....¢ VHWYJ- s , 1"“: ‘IvtllfiiIlJIrIo u’ .2 -I x \ I I fut! «(luff (mm. . .11 Buy. .‘Ml. . - n » . ) A tr U 1 u in: I‘ II?! A." C. b ’ . .. F.... '11 . [1 . .. y . n Id. .III f 1 Bill )vMHm:!l} .9? . ' II? | o ‘ . , .hl. .Hr‘,‘ . 443' L! n .bfllhdvn ‘I. I .. ‘ I I I, g ’ nil . A . ‘f" it‘ll Illa‘ I fill, . 1v- a I L. ll? Ifflvnvi gym” n- .\ Hflngt} (J 0% k, l Lt - b u‘ l I L infirm“; .u'rm M" J mm” f.‘ I, 11'.” I!” till)" I! nl’ll if c I “ IIIIIHHWIIJHJI I II. “[11! Ilfl’ -lhf,‘ IH‘ » -llllll . “unfli. Ema”! ”IT! 1'." I]! . Ill...) » Illa! 0:. all]: - {I’g JIIIII’ .nlllllf lanttl [if niflllf. .. H .I-II‘ ll- .‘.|«,l $.41“ 1!??? IJJI 1).“!!11: I 'Il.» I." .l -y u. H11.fu - gfllglf . t I!” {Hull-II), '4'!) - {I} w u v- I- will! .I’l I 4-H. l? ‘f ‘8 , LIBRARY Michigan State This is to certify that the thesis entitled AUGMENTED RELAXATION LABELING AND DYNAMIC RELAXATION LABELING FOR COMPUTER VISION presented by Stephen Andrew Kuschel has been accepted towards fulfillment of the requirements for Ph.D. Computer Science degree in , . ,7 '7 /. fl [’1‘ ,./ ,l/ _// , (tick C4 /¢/j’/Je ’/ Major professor Date August 13, 1979 0-7639 flwi FINES: 25¢ per day per item RETURNS LIBRARY HAT; Phat in book return chm. from dramatic 0308 03 MAR212003 AUGMENTED RELAXATION LABELING AND DYNAMIC RELAXATION LABELING FOR COMPUTER VISION BY Stephen Andrew Kuschel A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1979 ABSTRACT AUGMENTED RELAXATION LABELING AND DYNAMIC RELAXATION LABELING FOR COMPUTER VISION BY STEPHEN ANDREW KUSCHEL Relaxation labeling is a bottom-up data dependent method of labeling the objects in a picture through local consistency criteria over the assigned labels. The criteria are specified through the use of pairwise label compatabilities. Relaxation is amenable to parallel processing. Only homogeneous relaxation has been studied so far, where information description and flow is restricted to regular patterns for each pixel regardless of label. It is desirable to direct the labeling in a top-down manner without the restrictions of homogeneous relaxation processes while retaining the picture level local consistency criteria. Such direction allows additional information to be brought to bear on hard to label areas of the picture. Augmented Relaxation Labeling is a two stage relaxation labeling process which contains a separate iteration stage with a top—down direction capability for specific pixel labeling. The augmentation is accomplished by a broadcast process which sends pertinent information to specifically chosen areas throughout the picture. The received broadcasts cause a change in the labelings to reflect the new information now available. Thus the broadcast process of the augmented relaxation labeler is a suitable communication construct between the levels of a hierarchical description and aids in the labeling of ambiguous areas of the picture by bringing in top-down information. Augmented Relaxation is demonstrated on simple line drawings. Comparisons show it to be both faster per iteration and more effective per iteration than regular relaxation. Dynamic Relaxation Labeling is a single stage combination of the feature of broadcasting and the relaxation paradigm. It is not bound by the requirements of homogeneity but allows information to flow within the picture based on the labelings of the picture and any other knowledge sources available. Dynamic Relaxation is also demonstrated and compared on simple line drawings. General relaxation processes are modeled by the constructs of Shannon Infonmation Theory. The information flow of the local consistency criteria and the broadcast processes are given an information channel model. The appropriate information measures are described and quantified for the various relaxation processes described here. One result is a method for quantifing the goodness of the compatability specifications and a second result gives a measure for the effectiveness of an iteration. A final section on object position prediction by relaxation in sequences of pictures containing motion is included. TO THE GREATER HONOR AND GLORY OF GOD ii ACKNOWLEDGEMENTS It is my great pleasure to acknowledge the gifts that God has given me. They are not my own, but merely in my stewardship. By this dissertation it is my hope to make productive use of them. I also acknowledge my brothers and sisters in Jesus Christ in The werk of Christ Community who have tirelessly encouraged and supported me. I especially wish to thank Coleen Shireman and Rene McCarty who freely gave of their time to help with typing and to Joann Rzepka who helped with the figures. I further acknowledge Dr. Carl V. Page for his ideas direction and guidance that made this thesis possible and to Drs. Richard Reid, John Eulenberg and Erik Goodman who served on the guidance committee. Finally, I wish to acknowledge Dr. Harry G. Hedges who as department chairman always found a way to provide me with an assistantship or other means of support throughout my stay at Michigan State. iii TABLE OF CONTENTS LIST OF FIGURES Vi LIST OF TABLES vii I. THE LITERATURE ON CONSISTENT LABELING and RELAXATION LABELING METHODS l 1.1. INTRODUCTION and PROBLEM STATEMENT l CONSISTENT LABELING 2 5 I.2. I.3. RELAXATION LABELING II. BASIC DEFINITIONS AND PROBLEM STATEMENT 10 11.1. THE PURPOSE OF THIS THESIS 10 II.2. DEFINITIONS 11 11.3. EXPERIENCE MATRICES AND BROADCAST l3 PATTERNS II.3.l. Broadcasts 13 II.3.2. Broadcast Reception 13 II.4. BROADCASTING THRESHOLDS, TOP DOWN CONTROL 15 II.5. EXAMPLE 15 III. INITIAL TESTING and ALGORITHM DEVELOPMENT 19 111.1. PROBLEM DEFINITION l9 III.2. HOMOGENEOUS UNBIASED RLP 20 III.3. DEFINING THE BROADCAST SYSTEM 25 III.3.l. The Experience Matrices 25 III.3.2. Broadcast Control 29 III.3.3. Broadcast Patterns 30 III.4. TESTING 32 III.4.1. Test Pictures 32 III.4.2. Test Runs 35 III.4.3. Analysis 38 III.5. REDESIGN 42 III.5.l. The New Algorithm 42 III.5.2. Broadcast Strength and Algorithm Behavior 46 III.5.3. Reveiw S4 III.5.4. TANH SS III.6. TEST PROGRAM RESULTS 56 III.6.l. The Original Test Picture 56 III.6.2. Picture 2 58 111.7 CONCLUSIONS 60 iv IV. THEORETICAL ISSUES IV.1. IV. IV. IV. IV.2. IV. IV.2.2. Multiple Label Experience Matrices IV. IV.3. IV. IV. IV. IV. IV. IV.4. IV. IV. ON COMPATABILITY ESTIMATION 1.1. The Relaxation Rule and Local Consistency 1.2. The Broadcast Rule as a Relaxation Processor 1.3. Conclusions ‘ DYNAMIC RELAXATION LABELING 2.1. Definitions 2.3. Results INFORMATION MEASURES 3.1. The Model 3.2. The Measures 3.3. Channel Capacity in the Line Processors 3.4. Measures for the Line Processors 3.5. Conclusions CHARACTERIZATION OF FIXED POINTS IN AN ARLP 4.1. RLP Fixed Points 4.2. Broadcasts and RLP Fixed Points V. MOTION PREDICTION V.1. MOTIVATION v.2. DEFINITIONS V.2.1. Experience Matrices V.2.2. Broadcast Patterns v.3. EXAMPLE V 4. DISCUSSION V.4.l. Occlusion V.4.2. Expanded Label Sets v.4.3. V.4.4. Multiple Label Reception VI. CONCLUSION AND FUTURE PROBLEMS V1.1. V1.2. VI. VI. VI. VI. VI. SUMMARY AND CONCLUSION FUTURE PROBLEMS 2.1. Convergence and Optimality 2.2. On Experience Matrices and Compatabilities 2.3. Broadcast Parameters 2.4. Hierarchies 2.5. Chess by Broadcasting BIBLIOGRAPHY APPENDIX A COMPATABILITY MATRICES APPENDIX EXPERIENCE MATRICES B DRLP PROGRAM 75 75 75 77 83 87 87 89 96 102 102 107 110 113 115 124 124 125 13% 136 130 139 131 132 135 135 135 Motion Prediction and Curve Fittingl36 137 138 138 139 139 140 141 143 143 144 146 149 156 FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE 3.10 3.11 3.12 3.13 3.14 3.15 LIST OF FIGURES RIVER EXAMPLE LINE TEST GRID WITHOUT NOISE RELAXATION EFFECTS FROM THE TEST GRID BROADCASTING PATTERNS TEST PICTURE #1 FAINT LINES OF PICTURE #1 BROADCAST PROCESS RESULTS ORIGINAL BEHAVIOR SPURIOUS LINE EXAMPLE DESIRED BEHAVIOR BEHAVIOR OF THE REVISED BROADCAST ALGORITHM e = .2 \\' BEHAVIOR OF THE REVISED BROADCAST ALGORITHM e = .4 \\' BEHAVIOR OF THE REVISED BROADCAST ALGORITHM e = .8 \\' BOUNDED BEHAVIOR CURVES IN THE NEW ALGORITHM e = .8 \\' TANH FUNCTION UPDATE BEHAVIOR RESULTS OF THE REDESIGNED ALGORITHM RESULTS FROM THE REDESIGNED BROADCAST ALGORITHM e = .8 \\' vi 16 23 31 33 33 4O 41 43 50 51 52 53 56 61 62 FIGURE 3.16 RESULTS OF THE RELAXATION ALGORITHM 63 FIGURE 3.17 AUGMENTED RELAXATION RESULTS 65 FIGURE 3.18 ARLP RESULTS WITH EXTRA BROADCASTS 66 FIGURE 3.19 TEST PICTURE #2 ' 68 FIGURE 3.28 RESULTS OF THE RELAXATION ALGORITHM 69 ON PICTURE #2 FIGURE 3.21 ARLP RESULTS ON PICTURE #2 78 FIGURE 3.22 ARLP RESULTS ON PICTURE #2 71 WITH EXTRA BROADCASTS FIGURE 3.23 BROADCAST BEHAVIOR ONLY ON PICTURE #2 74 FIGURE 4.1 BROADCAST PATTERN FOR NO-LINE LABELS 88 FIGURE 4.2 BROADCAST RESULTS ON PICTURE 81 ALL NODES AND LABELS BROADCASTING 98 FIGURE 4.3 BROADCAST RESULTS ON PICTURE #2 ALL NODES AND LABELS BROADCASTING 92 FIGURE 4.4 DYNAMIC RELAXATION ON PICTURE #2 INTERSECTION THRESHOLD = .75 98 FIGURE 4.5 DYNAMIC RELAXATION ON PICTURE #2 INTERSECTION THRESHOLD = 1.8 181 FIGURE 4.6 BROADCAST CHANNELS 185 FIGURE 4.7 CASCADED CHANNELS 186 FIGURE 4.8 INFORMATION MEASURE NORMS FROM THE ARLP ON PICTURE #2 116 vii FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE FIGURE INFORMATION MEASURES FOR EACH NODE FROM THE ARLP ON PICTURE #2 117 INFORMATION MEASURE NORMS FROM THE DRLP ON PICTURE #2 128 INFORMATION MEASURES FOR EACH NODE FROM THE DRLP ON PICTURE #2 121 INFORMATION MEASURE NORMS FROM THE RLP ON PICTURE #2 123 A SIMPLE SCENE WITH A MOVING OBJECT 133 NODES RECEIVING BROADCASTS 133 EXAMPLE EXPERIENCE MATRICES 134 viii LIST OF TABLES TABLE 3.1 EXPERIENCE MATRIX DEFINITIONS 29 TABLE 4.1 BLANK LABEL EXPERIENCE MATRICES 94 TABLE 4.2 INTERSECTION LABEL EXPERIENCE MATRICES 95 ix I. THE LITERATURE ON CONSISTENT LABELING and RELAXATION LABELING METHODS I.1. INTRODUCTION and PROBLEM STATEMENT The field of computer picture processing and vision systems is very diverse. A Survey by Kuschel [1] presents a review of various picture segmentation, modeling and control techniques, notes on syntax, semantics and representation, mathematical theories and psychological models. This survey sould be consulted for an overview of the field. Picture processing is mainly concerned with enhancement, segmentation, compression and storage of the picture. The problem of Vision differs from picture processing in that vision requires an analysis of a scene to be made so that labels can be applied to each object or region of the scene. Visual models are often employed as data structures to represent the properties and relationships of the objects and regions of the scene. This thesis focuses on the topic of labeling of the items in the picture and consequently the relationships of the items to each other. This work is especially applicable to the picture level or the low level of the data structure representing the scene. Such work is a first approximation to the scene labeling and often uses world knowledge from higher levels of the structure. Pertinent papers on labeling will now be reviewed. I.2. CONSISTENT LABELING The work done by Waltz [2] involved the labeling of line segments and regions of line drawings of polyhedra. The line junctions are the basis on which the lines interact and constrain the possible labelings that each line may take. In other words, two lines joined at a junction cannot have labels which are incompatible with the fact that they are joined together. The labeling process is straightforward. The first lines labeled are the outermost lines of the figure, which form the figure-background boundary. Figure and background regions are also labeled. Secondly, lines that are joined to the already labeled lines are considered and the set of possible labels they can take on is determined. These new labels are checked for consistency with existing labels. Any inconsistent labels are eliminated. The second step is repeated until all existing lines have been considered and each line and the regions it bounds, have been consistently labeled. Waltz's method is inherently serial and dependent on prior knowledge of each line segment, its location and endpoints. The important contribution of the work was the demonstration that compatability information about the (labels and hence the) parts of a picture decreased the set of labelings a picture could take on, even by several orders of magnitude, and hence decreased the complexity of picture processing. Haralick [3,4,5] developed a notation which models Waltz's constraints and labeling process as well as serving as a meta-description for several other classic problems (e.g. graph matching, graph or map coloring such as the famous four color problem and the homomorphism and automata equivalence problems). The notation is as follows: U = {u ,u , ... u } The set of units or objects to (1) 1 2 M be labeled in a domain L = {1 ,1 , ... l } The set of labels for unit u (2) l 2 ki N T c U The unit-constraint relation (3) T is the set of N-tuples of units which mutually constrain each other. N may take on several values depend- ing on the nwmber of units entering into a constraint relationship. For example: N = 3, 4, or 5 lines at one junction. N R c (U x L) The unit-label constraint (4) relation R is a set of 2N-tuples where (l , ... ,l ) is a permitted 1 N labeling of units (u , ... ,u ). l N The consistent labeling problem is to find all labelings (l , l , ... l ) for U which are consistent l 2 M with the constraints expressed by the relations T and R. "One general technique used for this problem is a depth first search. The search procedure fixes labels to units as long as it can find a label for each new unit that is compatable according to the constraint relation R with labels already fixed to previous units" [3]. As in any tree search, one wishes to minimize backtracking and thrashing. This is done by the use of a generalized look—ahead operator § KP where K0) 1 j x ij j Labeling is accomplished by giving each label of each node an initial probability based on the underlying data. Label probabilities are updated by an iteration of the product updating rule. (The K in the rule indicates the iteration index.) Each iteration modifies the label probabilities based on whatever ”world knowledge" resides in the compatability measures: p ()l)‘). After several iterations or when 13 the probabilities converge to a fixed point, the label with the greatest probability is chosen as the label for that node. Thus the RLP operates on two sources of information, the initial probabilities and the compatability estimates. If the fixed point gives a unique interpretation for each label (unique interpretation matrix of p (A) i or a UIM ) where one label of node i has value 1.8 and all other labels of node 1 having value 8; the label choice is certain. However, if the fixed point is ambiguous: where several labels have non-zero probabilities, the neighborhood local consistency contribution has become negligible. In other words ”the picture contains no local information suitable for resolving the ambiguities. In such cases control should be passed to another process..." [9]. The product rule converges to the fixed point faster than its earlier predecessor, the arithmetic update rule. The speed increase is accomplished through a series approximation to the arithmetic updating rule, raised to a power, thus yielding a geometric or product rule. Consequently small changes specified by the local neighborhoods are magnified. The derivation details are given in [9,8]. The topic is discussed further in section IV.l. Eklundh [18] developed a measure of convergence in a picture from the relaxation definition. The residual, R, is computed between the solutions of successive iterations using the Euclidean norms of the solutions. Computations may be stopped when the residual is small enough to indicate that the labelings are reaching a fixed point. Zucker and Mohammed [8] have applied their RLP to the problem of detecting lines in a noisy picture. It has functioned well, separating the lines frOm the noise. Their success is due in part to an extension to a two level RLP where relaxation updates both levels as well as serving as the communication vehicle between levels. The higher level is designed to provide direction to the lower level through inter-level compatability functions. II. BASIC DEFINITIONS AND PROBLEM STATEMENT II.l. THE PURPOSE OF THIS THESIS Relaxation is basically a bottom-up, data dependent operation amenable to parallel processing. The homogeneous RPL updates every label of every node at every iteration using the same compatability functions based on each node's immediate neighbors. Thus each node can be processed identically and in parallel on a lockstep parallel machine (where the same operation is performed by each CPU at each time step). It is desired to update specific node label pairs based on top-down world knowledge direction, apart from and in addition to the homogeneity requirements while preserving the parallel nature of the RLP algorithm. The work of this thesis is to define and implement a basic Augmented Relaxation Labeling ProcessOr (ARLP) which contains the ability for top down direction. This augmentation guides overall picture labeling and aids in hard to label areas of the picture where a unique labeling cannot be arrived at directly. Picture results are given to illustrate ARLP and RLP behaviors and properties. Secondly, attention is focused on the inter-label compatability functions which define the world knowledge and its use. The result is the definition of a Dynamic Relaxation Labeling Processor (DRLP), based on the features of the augmentation. The DRLP is a 18 11 general, non-homogeneous, relaxation labeler with greater speed and discrimination than the RLP or ARLP. II.2. DEFINITIONS Augmented Relaxation Labeling was first described by Carl V. Page in 1978. This thesis presents the first implementation and testing. The following definition is adapted from Page [11] and Page and Kuschel [12]. Augmented relaxation labeling is an RLP with an added information broadcasting and receiving process. The augmentation allows a pixel or node in the data structure to broadcast information about its label set beyond its immediate neighbors. The received broadcast is used to update the label probability distribution of the nodes receiving the broadcast. The top down control mechanism decides which nodes may brOadcast, and when, as well as the direction and pattern of the broadcasts. The decision is made based on structural and statistical information in the picture and through the knowledge sources comprising the controller. The basic structure of the ARLP is an iterative two stage process. In the first stage, information is broadcast and received. Labels are appopriately updated. In the second stage, the local consistency compatabilities are applied Via the RLP. The first stage is then re-initiated using the refined information as a starting point. The iterations 12 continue until either convergence on a consistent picture label set (a fixed point) occurs or a resource bound stops computations. Picture information in both stages is represented by the same construct, namely a probability distribution over the labels. World knowledge is still represented numerically as the interaction of a label pair as was done in the RLP. A formal definition follows. DEFINITION 2.1. An Augmented Relaxation Labeling System (ARLP) is a system defined as: A = < R, B, T > (18) where R is a relaxation labeling process; T is the control process which determines the cycling between relaxation and broadcasting and B is a broadcast: B = < Bu, G, E > (11) where Bu is a set of broadcasting units: picture lines, regions, nodes or other units, or a separate knowledge source; G is the set of grammars which determine the broadcast pattern and E is the set of experience matrices containing the knowledge about the label relationships by which broadcasts update the probabilities of nodes receiving the broadcast. 13 II.3. EXPERIENCE MATRICES and BROADCAST PATTERNS II.3.1. Broadcasts The broadcast from a node contains the identity or present labeling of that node. The most likely label at the node conveys that information and so forms a suitable message for a broadcast. The broadcast reaches those nodes defined in the "broadcasting pattern". The choice of a broadcasting pattern for a node and label is semantically dependent on the label. Other factors such as the node position in the picture description, its relation to other nodes and the certainty of the label for that node may also play a part. In general, these patterns can be specified by the two dimensional grammar G, or any other convenient representation for the elements of the rectangular pixel grid or the nodes in a general graph.i II.3.2. Broadcast Reception The effect of a broadcast on a node is determined by an experience matrix E[) .A ,...,X ,...,X ] where 1 2 i b the A are the broadcast labels received by the node. i E is a square kxk column stochastic matrix where k is the number of labels in the label set. Each row of the matrix gives the "experience” for the updating of one label at the receiving node. Each element of a row describes the ”experience” the system has about the 14 row-column label pair (the A,X' pair in (13) below). The label probabilities of the receiving node i are given as a k x 1 column vector p , and are updated i according to the following equation: p =E[>\ ....pA] P (12) b i l 1 Using e as a general element of E with,X as a row X,>\' index and A' as a column index we can write (12) in the node label form similar to (9) from Zucker [7, 8]. k P (M =2 e P (X) (13) i . kw i 3 3:1 3 We can further define a "broadcast neighborhood" of the receiving node i as being those nodes which have affected node i through the broadcast process. The intention of the definition is to allow an analogous term for the relaxation neighborhood defined in section 1.2 at (8). II.4. BROADCASTING THRESHOLDS, TOP-DOWN CONTROL The decision as to whether a node should broadcast its labeling is made in general in a top-down fashion by the knowledge source or control process, T, in authority. The decision may be made in specific situations where obtaining convergence on a label set for a region is difficult due to noise or picture complexity. In simpler cases the decision is more uniformly applied . An example of the latter would be to allow every node to broadcast its most probable label if the probability exceeds a given threshold. The threshold may be picture wide or dependent on the node, label and/or location. It is possible that behavior similar to a neural net can be obtained by allowing different thresholds at different points, depending on factors such as time, previous broadcast and reception patterns. II.5. EXAMPLE Suppose we have an image containing a river which is crossed by a highway, shown schematically (without a grid) in Figure 2.1. Suppose further that, after several passes of an augmented relaxation algorithm, we arrive at the situation where the region indicated by the circle bordering an island, bridge, riverbank and water is not definitively labeled (with high probability) as "river". The control process, T, will, 15 16 Figure 2.1 RIVER EXAMPLE 17 in effect, broadcast the existence of the river segments to nodes nearby. The reception of the broadcast labels will cause transformation of corresponding probabilities. The broadcast pattern can be modeled by a two dimensional stochastic grammar as in the example below. R rt R -> R R rt rt rt R (14) Notation: The leftmost nonterminal location is occupied by the underlined symbol. Overlapping symbols at the same pixel of the same type are merged into one. Thus a node i in the range of both broadcasts, h horizontal units from the left and k horizontal units from the right receives the broadcast ((R .ph ). (R .qk )) (15) 1f rt where ph and qk describe the grammar rule and the new picture position it is applied at. If ph>t, a threshold, and qk>t, we use this information by transforming the label probability distribution 18 (P (X ),...,p (X )) by an experience matrix E(R ,R ). i 1 i b 1f rt The purpose of this experience matrix E(R ,R ) 1f rt is to move probability from labels which are unlikely to lie along the path of a difficult to perceive river to labels which tend to explain the difficulty. So for our example let us define: a * * R B I D A U F O * * * * l 8 8 1/4 1/4 1/4 1/4 1/4 * * 8 1 8 1/4 1/4 1/4 1/4 1/4 * * 8 8 1 1/4 1/4 1/4 1/4 1/4 * E(R ,R )= * 8 8 8 1/4 1/4 1/4 1/4 1/8 * 1f rt * 8 8 8 8 8 8 8 8 * * 8 8 8 8 8 8 8 8 * * 8 8 8 8 8 8 8 8 * * 8 8 8 8 8 8 8 1/8 * H' I, A H 0‘ V Thus if the distribution at a point i is R B I D A U F O t (8.2, 8.1, 8, 8, 8, 8.2, 8.2, 8.3) p (17) After receiving the broadcast labels R ,R , 1f rt p is updated according to (12) using (16) giving: i R B I D AUF 0t (18) (8.375, 8.275, 8.175, 8.1375, n, 8, 8, 8.8375) = P Thus, the probabilities of labels for "river", "bridge”, "island”, and "dam" are increased at the expense of "urban", "factory” and ”other". III. INITIAL TESTING and ALGORITHM DEVELOPMENT III.1. PROBLEM DEFINITION A problem space is desired that will provide a small and workable class of pictures to test an ARLP program. A set of pictures containing line (or edge) information is chosen following Zucker [8]. Lines are well defined and the relationships of pixels forming a line are easily quantified into compatabilities that encourage line formation and continuation. This domain provides an extension to previously recognized work and a set of non-trivial problems to work on. (see also [8]. [7]. [2]) The purpose of the augmentation is to aid in hard to label areas of the picture, or to enhance a particular label or feature of the picture. Noise, fading, gaps, and spurious information are classic problems in line and edge images. Such problems are an appropriate testing ground to compare the performance of the relaxation labeling algorithm with its augmented counterpart. It will be shown that the augmentation does indeed provide additional resolving power over the RLP. The following sections detail the definition and construction of the RLP and broadcast test programs for pictures containing lines. The results on some simple 16x16 pixel pictures are given. A revision of Page's initial broadcast definitions is undertaken based on the 19 28 test results. Revised results are then presented for each system separately and for the combined ARLP. III.2. HOMOGENEOUS UNBIASED RLP The first task of an initial test is to establish a running program that implements an unbiased homogeneous relaxation labeling algorithm, R, as defined in (8), (9) and (18) from Zucker [7,8] for the picture domain described above. The label set for each node (pixel) is the possible orientation the line may have (as a directional vector). For edge data the orientation gives the relative positions of the light and dark components of the edge. For example, an edge along the X axis with the lighter component of the edge above the axis and the darker component below would be orientation 1. If the darker component is above and the lighter component below, an orientation of 5 is assigned. 0 9 No line information in the node I X Orientation l, 8 to the horizontal | l I o I A OR 2 , 45 to the horizontal | 2 I O O A = I . . l . . (19) I C O I o l A OR 8 , 278 to the horizontal | 8 I | X l | 21 The relaxation neighborhood for the compatability functions (7) was defined as the 8 adjacent neighbor nodes in a regular rectangular grid. The compatabil- ities themselves were chosen as in [8] for node i with label X in relation to neighboring node j with label X'. They are defined by the cosine function in (28) below. This design encourages straight line formation while neighboring lines become less compatable as the angle between them increases. l cos(OR(X)-B) cos(OR(X')-B) (28a) | l r (X,X') = I cos(2[OR(X)-B]) if X' = NO LINE (28b) ij | l | l X,X' both NO LINE labels (28c) |_._ -l < r < 1 (28d) ij ‘ where the r are the compatabilities; OR(X) is the 13' orientation (angle) of label A; and B is the angle of the imaginary vector between nodes i and j. These compatabilities are then converted into conditional probabilities through the normalization below: (r._()\,).') + l) 13 p .(XIX') = w --------------------- (21a) 13 A g (r._()..).') + l) 1) 8< p < 1 (21b) ij 22 ; P (XIX') = l for all A' eg the p are (21c) ij 13‘ column stochastic where p are the conditional probability estimates of ii the compatibilities which sum to one over the A labels for all A' at each i j node pair. The p values for ii each of the 8 neighbors are given in the appendix. The w values are adjusted by iteration for each A label A in (22) subject to (21c) so that the compatabilities will have no bias towards any particular label. The w values are giVen in the appendix for sums that are constant to 7 decimal places. These values were recomputed at Zucker's direction since the original values were not available. In some applications, a bias may be desirable in the compatabilities. In the line domain, all lines are equally probable, a priori, regardless of orientation. Hence, no bias is desired. 2 w p (XIX') = constant (22) X' A 11 The RLP thus described was first tested on a simulated test grid of lines of orientation 1 and of varying probabilities. No noise was present. The picture and label probabilities are given in Figure 3.8. The behavior of the algorithm is given in Figure 3.1. The curve shows the change in p (A) for l i 23 mmHoz HDomHHS QHmo Hmme mzHA o.m ouswfim oacou ccc.— cocoa cocoa cocoa cocoa canon canon ocean ccaou canon cocoa cocoa cocoa ecu-n coo.— coeom one." coco" cocoa caco— cocoa cocoa canon canon 99:.“ one.“ eon-u ocegn can." one.— can.— ceeou ooo.— cocoa cocoa cocoa cocoa cocoa cocoa ocean ocean accon ace-n accou ace-n cocoa canon coo.“ coo-n cocoa cocoa cocoa cocoa cocoa cocoa coo.~ cocoa cocoa ace." eceou eceo— can." acco— oceou new. one. cow. cam. coo. 96w. cam. coo. new. one. can. cow. coo. ecwo coo. ceeon cocoa one." ocean acacu ecu-n ocean oecofi ace-a cocoa coo-u ocea— cBOou cocoa cocoa ace-u acco— can. com. com. can. can. can. cem- como can. can. can. can. can. can. can. ocean coo-u cocoa canon canon occ.~ ocean occou cocoa coo-u coco— eeeou coo-n 9990— cocoa eon.— oowo coo. 9:0. 090. eco- oowo one. cow. coo. acme 99¢. :90. new. new. cow. 96w. cocoa canon cocoa caco— oaao— ace.“ cocoa canon cocoa ocean can.“ can." ocean ocean ace-u cocoa oas- eoho capo can. can. can. cos. can. can. 99h. 99h. echo echo ooh. can. can. ocean can-u cocoa ocean coccu one." canon eeoo— canon coo-u cocoa cocoa cocoa eeoon ocean cauc— oooo com. com. com. com. com. can. can. com. com. coco can. can. occ- eeco can. caeon can-u cocoa cocoa coo.“ cocoa cocoa can." :99.“ cocoa ace-u oeeou aeoou one." 99:." caeou :90. com. 99’. coo. eco- eQOo new. aco- acvo cave acme eco- 990. new. cam. now. aceou coo-n anew" can." ocean cocoa ace-u cocoa cocoa canon ego-n canon caes— eceon ocean ocean .3oaon co>ww mum Hoxfia comm um Henna maoxfia umos msu How mowufiafinmnoum Hmsuom one .umoa um :BOsm mm manuo«a onu a: ome mmwu Iwafinmnoua wcwmum> wo mocfia HmuGONfiuo: mo uom < .mowumauouomumso How>m£on mug onwEumumn ou Hommououa cowumxmamu onu mo wawummu Hmfiuaca ecu Ga com: mm3 pfiuw umoO wash "dd“ "‘0'." u n :CCCCCCCCCOCCCOC. :CCCCCCCCCCCCCOCC — n u u u u n u u u u u n a n u u u u u o a co :0 : “ddflfl : “dud-I C ...-0"!" C a u a a n n u a n u n u u u a u a a u u n n n a u c c c o co co. co «coacocqcoocccccccccoco.on.cccooacccococoocccoccccocccccccccococooeoococcccccoccoccoccoococccccococo coco. \oco—o oocmo \oeoo. ouc- ocwo z o a x—t 2.<»u¢\ux¢p x—t z~¢~uzxux

u4 au>wa u .409 uz~aoz c oaou uuzu—xuaxu mzwxx» uzwxzp uocz >¢u>u zh pw E[x.] j k 3 2. Ignore Blank Labels E[x , X ] for A a blank --> E[X ] j k k j 3. Averaging Of Single Line Label Broadcasts El) . A 1 for j=k --> BIA ] + EIX 1 j k j k III.3.2. Broadcast control The decision as to whether a broadcast is made or not, is generally decided in a top down fashion by the knowledge source or control process T in authority, as given in (18). The broadcasting units, Bu in (11). are defined to be the line pixels themselves. (Throughout the paper the more general term "node" will be retained.) The broadcast is then the most likely line label at that node. The decision to broadcast is made by comparing the most likely line label at each node to a threshold: t. If the threshold is exceeded by a line label, the label is allowed to broadcast. Blank labels are not allowed to broadcast as above. There is more 38 on this topic in section IV.2. The threshold value was arbitrarily chosen at .24 but with an eye to being small enough to allow weak lines to form and yet large enough to exclude most noisy points from broadcasting. It should be noted that the presence and value of a broadcasting threshold is of theoretical importance. A homogeneous relaxation system should have no bias towards any label as discussed above. Thus a picture containing no information (all labels equally likely) should remain unchanged by the ARLP. If the same threshold t is used for each label and t is greater than l/k , where k is the number of labels, then the broadcast control will also be unbiased. Since the test system has 9 labels we need t=.24 > .lll=l/9 . III.3.3. Broadcast Patterns The choice of a broadcasting pattern is semantically dependent on the label and other factors. Line labels are defined as broadcasting directionally along the orientation of the label. Figure 3.2 shows the patterns for two labels. Broadcasts were arbitrarily allowed to extend four pixels from the broadcasting node in each direction as specified by the label. Thus in a 16x16 picture, a broadcast can extend halfway across the picture. This decision is implemented through node positions in the rectangular grid rather than as a more general grammar G over the nodes as given in (11). 31 The broadcasting pattern of a label is semantically dependent on the label. This figure shows the patterns for two line labels, 3 and 8. The broadcast is allowed to extend four pixels from the broadcasting pixel in the direction of the label as indicated by the asterisks (*). Figure 3.2 BROADCASTING PATTERNS 32 An alternate choice to a discrete, set, distance would be to allow broadcasts to extend to the picture boundary. The purpose of the broadcast is to put the information where it is needed most, based on the semantic information available. The choice of a local or global broadcast pattern is chosen on this basis. A more practical consideration is that the computational overhead rises as the broadcast patterns increase. A choice of a distance of one offers no advantage over the RLP. In the small pictures used here, four is a compromise choice. As in radio and TV broadcasts, the signal strength decreases with distance traveled. The strength may be described by a continuous measure such as e**(-distance) or a discrete measure based on the number of pixels or nodes traveled. This topic is not part of the original broadcast algorithm. It is further discussed in section III.5.2. III.4. TESTING III.4.1. Test Pictures The suggested broadcast augmentation to the RLP from Page [11] has now been described for a set of pictures containing line information. This broadcast system will now be tested separately as was the RLP in section 111.1 to establish its behavior characteristics. 33 as mmpaoHE Hams m . m 3&2 on». non. ass.“ ass. smm. mmm. mnm. “as. map. ass." She. as». sea.“ was. as». ago. Sam. gnu. cam. An.. “on. mac. was. nep. sun. use. use.“ one. As». Acs. ”as. gas." amp. was. us». aw». Amp. ens. can." nae. nu». ass. coo. sea. 998.. gnu. use. no». «so. spa. new. a... fine. ass. on”. was. «ma. ass.” Gum. can. can. see." saw. «on. ass.“ ass." as». «me. as.” mans. "up. ass." ace. cum. an». ass. "no. nnm. «so. who. can.” “as. as”. was. games sac. .mo. Am». «no. as». Ana. was. we». moo. soc." sen. ASA. «on. ass." ooh. amp. ago. an.. smo.r an». ape. as». «AA. ass.“ "co. ass.“ no». sea.“ Asa. use. «so. “so. new. «GA. «an. ac». mop. ”mm. «so. was. sup. use.” moo. ass." «on. man. can." ass." moo. sss.~ ado. can. use." a... cum. ass._ ppm. as». mes. can. A... was. ass. ass." cos. ..a. use.“ ocn. sue. who. ass." saw. use.” moo. ass.“ ans. och. «no. asp. sum. was. one. ass." ..n. nus. Ace. mom. can. ass." use." «as. .85. «as. so.. «no. sea. 8AA. use." who. was. ass." Ans. ans. .ssa.u «an. «up. can." Ann. was. .Ns. was. “BA. ass." NSF. ass.» nun. gas. can." gas.“ cap. can. ohm. «no. use.“ moo. ass.“ gas. cap. sum. was. a... sac." use." .AA. ans. ..a. ”As. soc. can. has. ABA. ass.” ass." cam. on. men. an». ac». use." now. so». was. ass.“ an». Ass. nus. ass." can. «c». new. a... «on. sea." use. .on. use.“ ass.“ was. ass.“ ass." amp. ommaflH ”COCOCOCOCOOCOCCCCJCCCCOCOCCCOO...” muHHHnmnopn 30H gnu Ham mugomoua 8.8 gunman .mumaxo n a a A a n .maamwu.ogfia m muons mommO mEom ca mumgwsov Hafiz Henna n m u n onwalog no xgman gnu .uso ovmm seas: mm>ppo can mogaa . o N . magnugoo mupuuan onu macaw .Boaop manna can Ga go>aw u a a m n ma mefia some :a Hman kaoxaa umos gnu mo muHHHpmnoum n m o n mnH .OGHH pmagufiuumg Dana mo goaungmwuo mnu mucomounou n n o a n Loans uwwau megHm a ma wmuogov ma unauufla gnu a“ mafia n u o o n n no oucommpm use .HG oppuoam umou mugomoum m.m gunman n o a n OCCCCCGCCOCOCCCCCCCCOCCOCCCCOCCOCCC ccoccaoccccccacccoca...«cacaaacccccccacccaccccccocccccoucoccccc.acecacao.occccaccccocococcooccocoa-c comm. \ooAOo coco. \cooco can. ecu. z a a comma x~z z~u4 4u>UJ n odcu wzndoz a .490 uuzumzunxu Nxmxxb uzmzxp uocz >¢u>u Zhfiw mum mmauaafinmnous Hoxas woumfiuommm one .mewa song up Hanna sHOxHH umoa gnu can» umnump ugmmmua mamnma OGHH onu.mzo£m q.n gunman . era. ooa. ccc.s ~.4. 8's. 0... cce.. a... mvs. sac. use. eee.. coo. cao. cca.w.oso. csc. my“. ('0. ceo.. sec. cco.r cmo. wee. «as. ens. was. "no. «so. xse. .n.. woo. «so. poo. coo.. oem. .os., .ss. occ.. .... eoe.. may. vvw. ~um. moo. s~s. coc.w use. one. «~e. ccc.. sso. .vs. we». use. occ.s coo. coc.. “on. eoe.. soc. mes. non. ccc.. occ.. .cs. sue. ass. occ.s -u. our. ooc.r 996.. coo...ons. sun. .so. -o. ass. are. 4.9.. nus. cca. cao. moo. ocs. (cs. ooo.« ans. sew. ecc.. ooe.. wmo. coo.. cce.p ans. .C.OC..0000........CCCCCOCCCCCCCOCCC o . o a c N I . u I ~ ~ r v e c C I k r o o s N N o . w c n . o N u m o e N C r o o s p c o m m u a o h A o c a e o s . u o o u a o a s m o o m o o ...CCCCCCCCOCCOOCCOCC.......COOCCCO 35 Several pictures have been generated and tested. Lines are represented in printed output by a single digit which denotes the label direction. The picture output presents the most probable label at each node, be it a line (digit) or a no-line (blank) label. Low intensity lines will not appear in the original picture as the no-line label is often more probable. The first picture used here is given in Figure 3.3. It is designed to contain all of the test cases given in section III.l. The line of orientation 8 starts strong and slowly fades out. The curve slowly changes direction but has gaps in it and also fades at the top. There is also a very weak line of orientation 2. A copy of the test picture showing all the low intensity lines is given in Figure 3.4. Noise was added randomly to 18% of the labels in the picture. A random number was compared to the 18% threshold for each label of each node. If the threshold was met, then a second random number was generated, multiplied by .25 and included in the picture as the probability for that label. Hence the maximum noise probability is .25 (which is greater than the broadcasting threshold t=.24). The sum of the probabilities for each node is then set to 1.8. III.4.2. Test Runs The results of a test run are given below in Figure 3.5. As the broadcast algorithm iterated, the 36 RRRRxxaexaexxR-x-xaex meqammm mmmuomm Hm> Figure 3.6 ORIGINAL BEHAVIOR Figure 3.6 presents the original behavior of Page's Low probability pixels (OLD This 41 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX :k 8 X X ‘ 8 - X X 8 2 X. X 8 X X 8 X X 8 3 X X £3 3 X X 3 X X :3 8 X X- _§ 8 X X 2 [_] 8 X x 2 I . x X 2 pi(3)=0.0 X X 1. 1 l 12 X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Figure 3.7 shows the position of a chosen node i with probability p1(3) ='0.0. There is no initial probability of a line of orientation 3 at this node. The node will however, receive the broadcasts of the line segment of orientation 3 that lies directly above it in the picture. In the originally proposed algorithm, the reception of these broadcasts could establish a positive probability of label 3 at node i. The result is a spurious line segment. Figure 3.7 SPURIOUS LINE EXAMPLE 42 after 2 iterations: P.‘3> p (3) + .4<1-p (3)) (25b) 1 1 , i = .4 + .4 * .6 . = .64 And so on until p (3) 3 l where there was no initial i evidence of a label 3. As Figure 3.6 indicates, the larger e is, the worse the behavior is. 12 The solution is to alter the linear additive-summation nature of the broadcast update algorithm so as to forbid the increase of initially zero probability labels, to allow small increases for small initial values and to quickly map large initial probabilities to 1.8. III.5. REDESIGN III.5.1. The New Algorithm The basic algorithm behavior that is desired is shown in Figure 3.8 as a family of convex curves for varying values of e . One family of curves meeting 12 the design criteria was developed by introducing a p (X) factor to the computation of the Experience 1 values as shown in (26) and (27). It is also desired to have each broadcast accurately represent the amount of knowledge or 43 1.0. NEW pi(A) OLD pi(A) The desired behavior of the broadcast algorithm is shown here in contrast to the original behavior shown in Figure 3.6. Here labels with low initial probability receive a small increase from one broadcast reception regardless of the value of eAA that is used. Initially moderately probable labels receive the largest increase while highly probable labels move quickly to probability one. Figure 3.8 DESIRED BEHAVIOR 44 certainty at the broadcasting node. A broadcast strength factor, str , is introduced at this point to A represent the level of knowledge at the broadcasting node in the calculation of the e. values. The XX' equations are given below for the two label case (26) and the general case (27). P (A) = e P (X) + str 6 P (X)(l-P (X)) (26) i 11 i X 12 i i _—_ for X = X' 1.8 and a broadcast of (27a) label X received I l I I | l p (X)*str *e when a broadcast of (27b) l i X XX' label X received I and X f X' e' =I X,X' : I l-p (X)*str *e A = X' (on the diagonal) l i X XX' unless case 1 applies (27c) l l l | 8.8 elsewhere. (27d) |.__ with 8< e' < l XX' and e' =l.8 for all X' as before. X XX' Equations (12) and (13) then become p = B'IA ....X 1p (28) i 1 b i 45 k P_(X) =.Z e' p_(x ) 1 3:1 A.Aj 1 J (29) J The simplest case of a strength factor, str , is A b p (A) m (30) str = Z ---------------------- X j=l dist(node m to node i) where p (A) is the probability of the broadcasting m label at the broadcasting node m and dist is some measure of the distance from node m to node i. The distance calculation can be appropriately chosen to fit the application. Although (27) looks confusing it is simply chosen so as to allow E' to remain a kxk column stochastic matrix. As an aid to understanding, consider the following example where a broadcast of label 3 from node m reaches node i: Let STR = 2.8 and p (3) = .75 3 i and the e values in the third row are: XX' .6 .5 1.0 .5 .6 .65 .6 .5 .5 E' is then formed as follows: since a broadcast of label 3 was received the third row of E is I9 str * p (3) * e I from (27b) 3 i 3,X' X'll 46 which is: e e e e e e e e e 31 32 33 34 35 36 37 38 39 .9 .75 1.8 .75 .9 .925 .9 .75 .75 with a third element of 1.8 from (27a). The diagonal is then l-row3 by (27c) to retain column stochasticity and zero elsewhere by (27d). Thus we have .25 .25 l l I .1 8.8 8.8 I I8.8 .25 I I .9 .75 1.8 .75 .9 .925 .925 .9 .75 .75 .75 I | .25 l '[X l = l .1 | 3 I .875 8.8 l I .875 I | . l I I 8.8 .25 I I l I I | l I This revised experience matrix formula is used in the broadcst algorithm as described in (28) and (29). All other details of the broadcast operation remain as previously defined. The properties and behavior of the new definitions are now investigated. III.5.2. Broadcast Strength and Algorithm Behavior. III.5.2.1. Bounds for Column Stochasticity in the E' Matrix. In order to retain column stochastic E' matrices it is necessary to bound the values of str and e X XX' for all p (R) values in (27). We can begin with str . 1 Al 47 The test program uses simple Euclidean distance in (38). Hence with a broadcast pattern as in Figure 3.8 we have: 8 < str < 2*[1/1 + 1/2 + 1/3 + 1/4] 3 4.84 (31) X Returning to the two label example of (26), we can differentiate to find a maximum to guide the analysis. d “" P (X) + str *e *P(A)(l-P(X)) = 8 (32) d p i X XX' 1 i i d 2 --—- p (X) + 4.84 e PIA) - 4.84 e p (A) = 8 d p. i M' i )w i l 1 + 4.84 e -2*4.84 e p (A) = 8 AN xx i 1.8 max e = ----------------- XX' (4.84*(1-2 P (X)) i lim max e = -1/[4.84*(l-2)] 3 .287 pom —> 1 )x' 1 Hence the maximum value of e 3 .287 insures that a XX' column stochastic E' matrix results from the definition in (27) for the line test program. This result may also be expressed in general in terms of str as in (33). A max e = --------- XX' max str (33) 48 The result in (33) is of some value in practice even though it is derived from the two label case. Since the experience matrices are column stochastic and this result applies to one column, we can simply apply it to all columns. In practice it is also found that l t. An example of this is given in section III.2.2 As each node receives a broadcast label, it stores the received label and adds the strength of that broadcast to the accumulated strength for that label at that node according to (30). When all broadcasts have been received, the experience matrix for each broadcast label at each node is computed according to (27) or (34) and as in the above example. If more than one label is received by a node the experience matrix for that node is computed by averaging as in (23) or through the use of specially defined multiple label experience matrices. Each node's label probabilities are updated by the experience it receives from the broadcasts using (28) or (29). 55 6. The second stage of homogeneous unbiased relaxation occurs to establish local consistency and to complete the augmented relaxation labeling process. III.5.4. TANH An alternate method for broadcast update does not involve an experience matrix at all but is based on a simple function update. The function TANH is a convex monotonically increasing function asymtotic to 1.0 and so is well suited to our needs. The update equation is I | TANH (s*p (X)) if a broadcast of A (35) P (k) = | 1 was received 1 l I l TANH(p (X)/s) if no broadcast of X I i was received where s = str + 1.6 str defined as in (30) and X p (X) = 1.0 as always. X i The definition involves a small change in the strength factor usage since TANH ( 1.9 ) = 7/4 = .7853... The s strength factor here then shifts the TANH values into the desired range. The behavior of this method is shown in Figure 3.13 again using the two label simplification and enforcing the conditions in (35) (normalizing). The application of the method is straightforward. once all broadcasts are received at a node, (35) is applied to each label x of p . i 56 NORMQLIZED TRNH[PIJ 1 < S < 6 828TR+1 C’0'.00 0'.20 0140 o'.so o'.80 11.00 IN I T IRL PI An alternate method to the experience matrices for broadcast update is to use the TANH function as given in equation (35). The power of the method is given here as a family of curves for various strengths of the received broadcast. The curves are read as given in Figure 3.9. The behavior here should be compared to the behavior of the experience matrix update method given in Figure 3.12. Figure 3.13 TANH FUNCTION UPDATE BEHAVIOR 57 III.6. TEST PROGRAM RESULTS. III.6.1. The Original Test Picture Figures 3.14-3.18 present five results of the redesigned algorithm on the original picture of Figure 3.3. Using exactly the same experience matrix values e that produced Figure 3.5d, the new algorithm of (27) MI and (28) gave the results of Figure 3.14. It is clearly seen by examining the highlighted probabilities that even the faintest line is now clear and strong. There are no noise propagation or line extension problems after four iterations of the broadcast cycle of the algorithm only. The label probabilities converge to a unique interpretation for the labels shown after several more iterations. The picture background remains unchanged, spotted with noise, since only line labels are broadcast at this time by the definitions section III.3.2. Nodes where blank labels are most likely, are affected in the relaxation phase. Figure 3.15 shows the results of a stronger experience matrix, namely that of Figure 3.12. The advantage here is that fewer iterations of the broadcast system alone are required to gain the large change in label probabilities needed for weak lines. The relaxation system alone does not give satisfactory results on picture 1 due to the low 58 initial probabilities of the lines. The results of such an attempt are given in Figure 3.16. Sufficient iterations of the broadcast system are required to build up the label probabilities to the .75 level as detailed in Figure 3.1. Figure 3.17 shows the poor results from the ARLP with only one broadcast cycle. Figure 3.18 gives the more acceptable results from three broadcast cycles before entering the relaxation system. Some effects from noise can be seen in Figure 3.18 from the relaxation phase. The node containing a line intersection (where two lines of orientation 3 and 8 are present) represents the problem of an ambiguous labeling predicted in section 3.3.1, equation (23). The problem is due to the averaging of the separate experience matrices, and thus encouraging both labels. The result is a low maximum label probability (.575 in Figure 3.15) at the node. A solution to the problem is given in chapter IV. III.6.2. Picture 2 Picture 2 shows two rectangles and a triangle. Each of the sides of the figures has a different initial probability. Intersecting lines and overlapping corners provide additional problems. Random noise with a maximum label probability of .25 exist over 5% of the picture. Figure 3.19 gives an output of picture 2 with the associated initial label 59 probabilities (again highlighted). Figure 3.2% shows the effect of the relaxation algorithm only. Only the stongest and longest lines survive. With the augmented system, only a small weak portion of one rectangle and part of the triangle are lost as shown in Figure 3.21. The loss is due in fact to the relaxation cycle and not the broadcast cycle. Hence a doubled broadcast cycle initially can again remedy the problem completely as shown in Figure 3.22. A result from the broadcast cycles only is given in Figure 3.23 for further comparisions. 60 III.7. CONCLUSIONS Let us review the goals of the augmented relaxation labeling process and the design revisions that allowed their achievement. The inclusion of a broadcast process augments the RLP with a separate top-down controllable, label and node specific enhancing vechicle. The RLP local consistency and homogeneity criteria are retained. The ARLP is still amenable to parallel processing. Selectable levels of enhancing power are available for the lines through the use of varying experience matrix values as given in section III.5. Broadcasts reflect the information at the broadcasting node through the strength factor, str, which decreases with the distance the broadcast travels. A full review of the broadcast process is given is section III.5.3. Test picture refinement is better due to the augmented system versus the RLP alone. About the same number of iterations are required in the ARLP versus the RLP. In the current line picture implementations, the broadcast cycle runs in .55-.6O seconds while the RLP cycle consumes 10.7 seconds per cycle. Result: enhancement can be specifically directed to detail low probability or fading lines that the RLP alone misses at very low cost. 61 ZEHHMOOA¢ szonmomm NEH mo mHADmmm «H.m unamgm emu. nan. oao.. mac. 0mm. «.m. “no. «we. was. cos.— ooo. on». one. sac. «an. coo. was. no”.. on». coo. an». «as. on... ”we. ”at. cm». aaa._ cos. n_». n_~. "on. one. nae. as... ~mm. ass. “up. mac. «n». as..— eoo.~ use." ¢_o. ~na. gown» mnc. .np. can." mum. coo. eac.. so”. has. ecu. opuuxsmeo.— .no. has. «no. ”no. sex. can. use.“ a... an”. ouo. ....a «No. cue. gnu. ooe.~ as». no... «as. ”on. ace. «0.. use." a... was. soc.“ one. man. one.“ soc." nao. use.“ can. a... can." use. 9... map. so». sos.— com. ..o. coo.“ new. ....— ano. och. «no. nus. sea. «as. ans. use." one. man. co». “no. oo.. «me. an». app. use." new. own. age." saw. was. ewe. nos. «a». use.. «as. ass.. “no. ago. use._ new. sea." owe. =-. poo. wow. cop. use." coo." can. so”. use.“ use._ owa. who. nuo. on». men. use." ”so. coo.w owe. wen. no». a... one. use." man. .on. .3oHon caonm mum mefim comm um Honma kamxfia umoa gnu pow mofiufiafinmnoua may .m.m gunman :« comm mm anuuuowam Hmcfiwauo onu conuma umcu maoanoum cowumwmaoum mafia cam owfioc may no oomuu 0: Saab wcouum cam umoao mum mmcfia musuowm gnu .maco acufluowam uncommoun man mo mcofiumuouw usom Houw< .3onn co>ww mum mucuoan umou uwuww us» so acuwuowam uncommoun cocwfimovou gnu mo muaswmu may coco H.104?) memo nnnn O O O I tn .0 II II uuuu xxx: ~~H~ hbhh who. amo- oecou Nae. aha. can. cocoa one. an». hcoo nun. 99:.— 0090 one. «on! 000. .00. mar. ouwo Otto one. cocoa eno- «on. cocoa on». «no. nno. than are. fine. woo. woo. mar. cocoa mom. son. ups. canon «to. coo.— nan. who. «on. oooo has. ocean now. «to. sub. cocoa shoe «who now. who. one." eco- oecou moo. one-u ocean mom. can. cocoa one." «on. snag ....a cocoa map. on». oeaou cocoa ocean canon coco opu- «no. cps. one. tea. Coo.— ouoo can. an». oak. as». sso.~ 9.... has. use." ass." own. use." see." new. CCCCCCCCC.CCCCCCCCICCCCCCOCOCOCCCCC on c c a N c . o a m _ a a . . o.~ w . 0 cm W a a we a o . w a n . c u on . a N m c cw mm c c n O c c o c c N m o c N a a c N 0 o c w m o coccccoocccccccc.ccocCCCOOcocccccco c zanhcxuhn h¢ Wnahao zumoxu c zo~b<¢uh~ h< oz-mu ooua msu mo vmmumcfi m:OHumuouw 039 haco Houmm muasmou manmumaaoo mo>ww xauuma .¢H.m muswfim cu woumaaoo on vasonm muasmou .NH.m gunman cw cm>fiw mm uoa>mnon osu nuH3 xauuma oucmfiuomxo osu mafia: onsuofia ummu uwuww mnu co Ecuwuomam uncommoun on» mo maOfiumumuH 039 Scum muaommm 999.9 999. «no. 999. 999. ~99. 999.9 999. 999.9 9 999. 999. 9 999.9 9 999.9 999., 999. 9 999. Nam. soc. ,nuaod 999.9 999. 999. 999. 999. 999. 999.9 999.9 999. 999. 999.9. 999.9 999.9 999.9 999.9. o—o. num- 999.9 999.. cpm. ace.— 999.9 999.9 999. 999. 999.9 mm». ohm. 999. .... ;999. can. ocean I one. won. nan. now. new. ceca— «who ocean «Na. ammo boo. nauoa OCCCCCCCCCCOCCCCCCCGOCOCCCCCCCOCCCC 090. was. 959.9 moo. coo. memo, 090. ,h¢09 coo-9 ops. sno- New. has. «up. «no. «on. «to. own. who. coo. a..." mwm. snwo 989. 999.9 99:. cup. one. moo. ooh. 999.9 ace. 9 o 9 o c c c m C C 9 w c w 9 w c N C O C c C C 000.00... zwwozu w zumozu u N «cameo... zo~m<¢ummbmuwwnn»M¢wmqmnw zcuhtcwhu h N N nnonn N N u a u N COC‘IOCC(ICCO1ICCC Q o cocccoccccccuococ t clupmtuodocm 63 29999999< 2999msop mcu 09 wow m9 mHLH .Emumxm may 09 uwoa m9 oC9H >9m>o umoz .:m>9w mum musuowm ummu mam co %Hco Enufiuowam coaumxmfimu ozu mo cowumuoufi mac «0 muasmom oohc.w nut~h 999.— 999.9 999.9 999.« 99¢. woo. woo. ooo. poo. woo. coo. coo. 999.9 999.— moo. 999.— ooo. woo. woo. uNo. moo. woo. 999. 999. Foo. 999. ooo. one. 999. ooo. 999. 999. 999.« woo. hoo. ooo. 099. 99m. 999.9 999.~ 999.9 999." 999." 999.9 a 999.9 999.— 9 999.9 moo. 999.9 999.9 a weo. 999.— hoo. 999.9 999.9 «to. a can. 999.9 999.9 90o. u 90o. 999.— " "No. 999.9 ooo. ooo. 999.9 999.” hum. nun. ooo. woo. 999.“ woo. 999." two. 999.9 moo. 999.u 999.9 999." ooo. 999." 999.9 999." coo. coo. 999.9 999.9 999.9 999.~ 999.— OCCCCCCCCCOCCCCCCCCOCCCCCCCCCCOCCCO COCCCCCCCCCCCCOCC zumoxu a 0mm. moo. 999.9 one. a u o c COCOOCCCCCOOCOCCCCCCOCCCCCCCCCCCC 9 299999999 99 999999 zo-oua muasmmu zoom umoEHm ouwss ponommu m9 ucwoa pmxam m ousuofia umou o£u so 999." 999.— 999." 999.9 999." 999." 999.— 999.— 999.— 999.9 999.9 999.— 999.9 999.9 999." 999.9 999.— 999.9 999.9 999.9 999." 999.9 999.9 999.“ 999.— 999.« 999.— 999.— 999.— 999.— 999.9 999.9 999.— 999.9 999.9 999.9 999.9 999.u 999.— 999.9 999.9 999.— 999.9 999.9 999.9 999.9 999.9 999.— 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999. 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 .uommououa cowumxmaou voucoewsm onu Mom ommo ummu cw=Ou zaoaouuxm cm .umoa coon mm: coHumEuoucH mafia Ham kaco Emumxm coaummemu onu mo macaumuoufi snow umum< 999 - "NON GNU-0 can 0 o 0 0043 9.9.9.099 99.9 999." 999.9 999.9 999." 999.9 999.9 999.9 999.9 999.n 999." «no. 999.9 999.9 999.9 999.9 999.9 999.9 999.« 999.9 999.9 999.9 999.— 999.u 999.u 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.9 999.— 999.9 999.9 999.9 999." 999.“ 999.9 999." 999.9 999.— 999." 999.9 999." 999.9 999.— 999.9 999.9 999.— 999.9 999.9 999.9 999.9 999.— 999." two. 999.— 999.« 999on 999.— 999.— cc». 999.— 999.9 999.9 999.9 999.— 999.u 999.9 999.« 999.~ 999." 999.— 999.9 999.“ 999.9 999.9 999.— 999.9 999.9 999.9 999.9 999.9 999.~ 999.— 999.— 999.“ 999.9 999.~ 999.9 999.« 999.9 999.— 999cm 999." 999.— can. 999.9 999.— 999.9 999.9 999.— 999.9 999.9 999." 999.9 999.— 999.9 999.9 999." COCICCCCCCCCOCCCOOOCCCCCC.CCC.OCCCC C C C C C C C O O i O C C C O C O... "9299 29992 "9299 2999: "9:99 2999: CCCCCCCCCCCQCCCCC 655 9999999 2999999999 999292999 99.9 999999 can." can." ace.“ cocoa cocoa cocoa ace." eeoou ace-u 9599— cocoa cocoa cocoa ocean ace-u ace.— cooon ace-u cocoa cog-u cocoa 9999— 9999— enac— eoeou ace." can.“ cocoa ace." ace-u ocean ace.— ooe9~ one." ocean cocoa ocean cocoa cocoa aeaon ace-u acco— ooeou cocoa cocoa coo-u cocoa hoo- oooou canon canon one.“ coo.u cocoa eeaou 999.4 :99.— 99°." cocoa canon can." use.“ cocoa one.— aeeou canon canon 99:.— coo." neoc— ooaon canon 9099— one." 9999" ace-u canon canon conga cocoa cocoa 9999— cocoa canon cocoa 9999— ocean aeeou cocoa cocoa ace-u 9999— Queen Bacon 9999‘ one.— aeeou ocean cocoa ace-u cocoa cocoa caco— amm. one." cocoa cocoa ace." coo.— eeaou cocoa caco— oceou canon canon can." ecoou cocoa coo.— oaoou ocean coo-u ocean can." ocean ocean ace-n canon ecoo— ace-u cocoa ace-u cocoa cocoa 9999— 9999‘ «mm. acco— eeoon ace-u aaoo— one." cocoa ace-n coco— 9999— 9994— 9999— can." c°e9u aeaou cocoa cocoa can.“ .999“ one." one. ace.— eeaon cocoa one." 0999— can.“ 9999— cocoa coo-u canon cocoa coo-u cocoa canon :99.— ace-u canon cocoa ace.— ceeou coo-u cocoa cocoa cocoa cocoa cocoa coo-n ocean ago.— 9999— ace.— ooeou canon ace-u cocoa ocean canon canon ocean ocean cocoa cocoa cocoa one." ocean ace-n cocoa cocoa cocoa 99°.“ 99°.— ocoo— cc=.~ cocoa can.“ aaoou :99.“ canon cocoa occo— one-u cocoa cocoa :99.— canon can." one.— coe.~ 9999— cocoa coo.— cooou ocean cocoa canon canon ocean cocoa ocean cocoa ocean cocoa ace.— occo— cocoa coo.“ 9999— can." aaaou coo.— ooo.~ cocoa one." cocoa eac- u hos. coo-u cocoa 99¢ — CCCCCCCCCQOCOCCCCCC¢COCCOCCCCCCCCOC C C C C c a .— u o O C .oH.m muawwm :9 999999mv mm n 9 n uowmmuoua coaumxmamu 9:9 :9 9999 Emanoua 9:9 .kufimmv m9 ” 9 99 n 9923 99% 909 9:3 haco Emuwzm sewumxmamu 959 8099 vwcfimuno u 9 9 n mmonu c959 umuumn maummau mum muasmmu mnH .mc09999999 9509 n 9 9 n 99999 cm>9w mum 9939099 9999 wnu so wauzu coaumxmamu mco 99 u 9 9 n vmsoaaow macho 99996909: 950 £993 mqm< 9:9 Eoum wuasmmm u 9 9” C. O: :0 COCCCCCCCCCCCCCCCC.CCCCCCCCCCC 9 299999999 99 999999 9999.9 "9299 299929 9 299999999 99 2999999999 9999. "9299 299929 9 299999999 99 9299999999W9 9999.9 "9299 299929 9 299999999 99 29999999 9 9999. 99999 299999 9 299999999 99 9299999999w9 9999.9 "9299 2999:9 9 299999999 99 29999999 m ”999. "9:99 2999:9 9 29*999999 99 9299999999“ 999.9 "9299 2999:9 9 29 999999 99 29999999 9 9999. "9:99 2999:9 9 299999999 99 929999999999 66 n0:. cow. was. «to. aoaou ecu.— has. cocoa ocea— cNoo cam. 06». homo cocoa homo non. .Amusuofiq mfiu mo mHuuHH 9 99:0 vamv mmfio: mSu mo umoE mm>oa now. cocoa Now. 999. coo.— 999. 999. 999. 999. 999. 999. 999. 999. 999. nos. can.- 999.9 999. 999.— noe- cum. 999. 999.— can." now. on». 9999 099. one. coo-9 .99.— one. ammo unto nNso canon Nao- ova. coco— Noo- coo.— our. cup. Nae. no». 0N0. coco— Non. mhmmm mumaaoo 9993mmu mmmse .mum: cm>9w ma mmau9o ummuvmoun H9999¢9 mnuxm 039 £993 mam< mnu 809m muasmmm DNOo own. 9909— New. Name one. cocoa Ono. nus. hen. nNOo coo-u coo. can. onao 0999— Queen Nao- o—Oo 9999— nac- aoeou onto ~00. ocean onu- «noo nnoo one. 050. fine. Now. Not. now. .90." non. hos. «up. can.“ «to. cocoa man. «no. Non. 00¢. sNho coo-u now. No.9 Nah. cocoa hsoo no». men. when 9099— acre cocoa n00. cocoa nee-n 000. ammo 0009— cocoa «up. snug cocoa cocoa CNN. ens. ocean canon one." 0909‘ con. aka. NNoo cun- Nno. coo. cocoa 96¢. :00. moo. $05. oak. 9999— cocoa poo. cocoa 9999— who. oeenn ace-n cocoa COO.........CCCOCCOCOCOCCCCOOOCCCCC on o c O N o o o N a N u u u 9 c o N N 9 9 c N N o o N o N 9 o N o n 9 o N o n 9 o N o o c N n o o o n O o O O o a N n o o N o o o N a o 9 N 00 .0000...cocc...«90009009990009.9000 . n zoubtcuh~ pd wam—ao zuwozu n zc—h¢¢u»m 9‘ uz~pw< a<0¢n tumozu N tau—czu— —¢ ozupmguo¢oam zuwozu a zanpdcuh~ pa oz-m¢ua¢o¢m 67 99°99 one.— oeeou acco— 99999 c999“ 9999— one." 99999 99999 09:99 ace.— 9:999 cacou ocea— coo.— eaccu ocean coo-u coo.— ace.— coo.— see.— 06:." coco— ecce— cocoa coco— cocoa ecaou coo.— coo.— 06:9— 099.9 90999 coac— coco— ace-n caco— coo.— caco— caco— coo-9 econ— coco— ace.— cacou cocoa ace.— cocoa mom. cocoa coo.— 99:99 ago.— ocean 99:99 99:99 09°99 ago.— 99999 cocoa 99°99 coo.— 999.9 09999 999.9 eeeou ace.— ace.— 99999 9909‘ ace.— 99999 99699 ace-u cocoa cocoa ace-u 99999 99999 ace-u 9991— 0:999 ocean 9:999 can." cocoa oceou 999.9 99999 ace." canon ace-u 99°99 99°99 Gee-u 99999 99:99 cocoa 9999— 99999 ace-u cocoa ego-u cocoa coo. caco— 99999 9999— can.“ ace.— eeeou oeeou 9999— moo. eaoou cocoa 999.9 0909 999." one." ace-u coco— oooon 999.9 coo. coo-n oecou .9999 9999" our. 0999— can." coo. coo-u 99999 .9999 euca— acou— 90699 Now. @9999 ocean ocumow owono eNocow A.u.ucouV m9.m ocean 9 Now. a ace." 9 cocoa a ace-u a 9999— 9 N009 e 99:99 a 9999" a canon N woo. o 9909— one." acco— accou a 99099 a 9999" a one.“ o ...COOCCCCCCOCCCC can" ecu-u ocean cocoa 9999— ace-u 09.— canon Boo-n cocoa 9399— coo-u can“ canon @000 Geo." ecu-u hwwo :90" canon ocean cocoa cocoa accon econ eon-u cocoa cocoa 9999" ocean ecou ace-u one." cocoa ace-u hoo- oeo— Bacon 9090“ ecu-n cocoa coo.— OOon ace-u cocoa econ— eeeon oaaon 960— ocean Bacon cocoa ocean ecoou 00. cocoa NOD. canon canon bacon on." ace-u ocean been" cocoa cocoa Bacon 0’09 car. 969.— eoou cocoa Bacon Bacon Gee-u canon econ caco— occou cocoa accou Genoa ac." ace-u cocoa ace-u e99." 999.— ceou ocean Choc cocoa ocean aeeou «coococccccocococcccccocoocc0.00.00 ”9 9 c a N u d a o a N N c m N c N Q N c N o n c N G n c N o c N n m o n o m c O o c 9 N D 0 Q coccccccccoccccccococcoacccccooccc o 2°~b<¢Uh~ pd «9¢*mc wwoxu 0 2o h‘Kuh~ h< uc—o m m umczu c 20 pCCUh b< 98 km 0 40¢ wwczu n zo~h. cec.9 999.9 999.9 oco.~.eeo.9 999.9 999.9 eoc.9 cnn. ocm. 999.9 own. 999.9 999.9 #90. cocccccccccccacac...cu¢ac¢.occoaccc n 9 9 9 9 9 u . m 9 9 9 9 9 9 n . . . . 9 9 9 . um>m3on wum=w9aEmm9v 09 9999900 . m 9 9 M m n 0 699939 cam mGO9uummumua9 whoa mum 099:9 .cmw: mum mm:99 .. mm 99 99 M9 99 m9 99 n 9mwa09 vcm .99 9959099 :9 cmzu umwaouuw 999m9wcmw mum mm9u9 n M M m m n I99nmnoua mc99 may .mwoc numm um 9mnm9 999x99 9908 0:9 909 n M 9 99 9“ m n mm9u999nmn09a vmum9oommm wsu 5993 30960 kuammmua 99 maustM n 9 9 u U9uumaomm 999899 wc9c9muaou 9929099 umMu vcoowm < . M 99 99 99 99 99 99 m . "OCCCCCC«COCOOOCCOOCCCCCCOOOOCCCCC” COCO.COC.CCCCCC....CC.COCCCCCCOOCC.CCCCCCCOCCCOCCCCQCCCCCCCI..CCCCCOCCOCCOCCCCC.CCCCCCCCCCCCCCCCCCC. 5990. \c099. och. \9990. can. ocN. z o c Ozocmcmxo x9: z~u4 au>w4 9 .490 92—402 0 .qu uuzu—cuaxu sz¢9b uzmxzp wooz >¢u>u Zh on 4w>ua uaomm »¢ 3 w.N uz~4u¢9w ow.m 09=w99 9 99 99 99 99 9M 9 CCCCCOCCCCCCCCC.CCCOCCCCOICCCCCCC 9 299999999 99 9:99M9 9999.9 "9999 2 9929 9 299999999 99 2999 x99 9 9999.9 "9299 2 9999 9 299999999 99 2999999999 9999.9 "9299 2 9990 9 2999999»9 99 2999999999 9999.9 "9299 z 9999 9 299 999 9 99 2999999999 7O N§ mmaaon zo megammm mgm< Hm.m muawfim coo." coo.— ooo.— coo.~ oco.u eeo.— ace." coo." coe.u one." coo." oNo. eec.~ ooe.« coo." oca.~ 99:." cos.“ oec.n ooo.~ coo." oeo.— oeo.u oee.u can." 99:.“ ece.n who. coo.u oea.« coe.u coo.“ oce.u eco.— coo.« can." coo.“ can." aoa.u ace.~ aea.~ aoe.u ace.“ oee.« eeo.~ one." coo." eoa.u ago.“ occ.n 9:6.” one." 999.. coo." cae.— one." aoe.~ new. aeo.— eoe.u ee°.— eaa.~ coo." oaa.u coo.~ Qua.“ coo.u aoe.~ ooa.u one." eoe.u aca.— can.— one." 9:9.u cec.u ecu." can.“ aoe.— ooe.~ ooa.~ nee.“ eco.~ can.“ can." coo." aee.~ ooa.— oeo.— ace." ooo. oae.~ ace.u coo." aoo.~ 99:.“ can.— :99." coo." acc.— moo. can.“ 99:." eoo.— cec.— ace.n one." can." coe.u eoa.~ 99°." 99:." ooo. pho. ooo.~ oea.u can.— :99." aoa.— coo.u ecu." ecu.“ ace." eoa.« eeo.— coo." coo.n aoa.~ coo.~ coo." one." nco. :99." Geo." aoe.~ one." 999.“ cec.~ cao.u eoe.u can.« can." 99:." Geo." woo. can.“ one.“ eoe.— ace.« ecu." aea.u ooe.u eee.~ coo." aoe.~ coo. eue.~ can." ace." eee.n coo." oec.~ oco. ace." cee.u sec.“ 999.“ can." 999." 9:9." 6:9." 99:." ego.u cco.~ can." can." oec.~ one.“ neo. aeo.u one." can." 999.“ 999." can.“ oec.~ coe.~ ace." oeo.~ eoc.~ coo.“ ace." aoc.~ ooe.— «no. 999." coo.— eoc.— 99¢.u eea.u coo.u aae.« cae.u oeo.~ ace.“ 99°." one." use." coo.— can." can." ace." coc.— can.“ coe.u coo." one." 999.“ can." one." eoa.u can.“ ccc.~ eon.— coo.~ can.“ oao.— eeo.~ eoo.— can." aco.~ eoo.~ ooc.~ ago." cae.~ coo." aoe.— one." coe.n ace." coo.— one." ccc.~ oco.— eoc.— coo." coo.— coo." ooo.~ ecu.“ aoe.n ace." coo. 999." 9:9." ecu.— 0.0.0...COCO.CCCCCCCCCOCOCCCCCCCCCC O C a N mmnm c . n g a u p . . m M n . o o C a muaamwu wmwo: mauuwa mum> ucfioa wmxfim mafiamnma n m M um . C Q m: “a: m um vmcfimumu zauumuuou ma :ofiumEu0mcfi mafia umoz . m mm mm mm mm mm mm m . o C C mcoaumuwufi poem umumm mace coaumxmamu ou uoauwmaw umm mH . s s n n . uasmmu 0:8 .mpw: cm>Hw ma cowumumufi awn macho cowumxmamu n M ~ _~ "u m n 5 mac wcm ummuvmoun mco nufi3 mqm< msu mo muaammu way u p «n u . p g a u u u a u a g . M q . . C C CCCCCCCCCCCCOOCCIC0.0CCC¢CCCCCOCCOC . ze.».¢u»_ ». paapao =_~..o Max.» zumozu . zo-.¢u». p. zo_».x<4u¢ cnmm. mug.» zumoxu . zo.~<¢up. p. cz~»m«ua.o¢o can... "mt—h zumoxu n za_».¢U—_ p. zo_—¢x.du¢ amon. nu:_~ zumozu n zo~h¢¢u»_ ». ¢z_»m.uo.o¢m omc..o nuz_p zumoxu m zc~».¢up. p. zo~»¢x.au¢ c.9m. nut.» zumozu N za.».¢up. ». uzupm¢uoaw mm mqm< umuww ms. Law: vwcfimuno muonu cmsu .muuwa can.“ coo. Oho. coo.— ”no. can.“ ooe.~ .99.— «as. o...— I...“ can.“ .0..— one.— cocoa can.— .oaco mmau>u ammovmoun oec.« .9..u ....q use.— one." one." can." ooo.~ moo. moo. cocoa one." man. co..— ea..— .99.— NN.m muawfih ..... .... .... 9.... ..... ..... 9.... .... .... ..... ..... N... 9.... .... ..... ..... 9.... ..... ..... .... .... .... ..... ..... ..... .... .... ..... ..... .... ..... ..9.. ..... ..... ..... ..... ..... .... ..9.. ..... ..... .... .... ..p.. ..... ..... ..... .... .HN.m muswwh wum muaawmu wcfi .mmwma wmunu uxm: ms. 6. cm>ww mum mHu>u ammuvmoun Hmuuficw muuxm cm saws mqm< cm Bouw muazwmm 9. he "N 0‘ O O .. ll ”U “ ~— P” can.“ awe. oeo.— eac.~ aoe.u 9.9.u 09°.u eon.— ooo.u 00°.u «so. 00°.u «on. .09.“ cocoa Ohm. Ono. cocoa oo..« .09." ooo.— 9.9.u one." 999.“ nno. one.“ who. a...— ceo.n can.“ ONO. cocoa no... 900. oao.u eeo.u coo.u one." ono. wow. cocoa ono. woo. «no. 999.” cuo. ooh. ooo.u hop. can.“ one. coo. 99¢.— ooo.u on..— can." oao.u oa..~ ....— ooaou ....~ .0..— .oo.« oo..~ can." can. on..— 0...“ 09¢.u one." .0..— oac.u coo. a..." can.“ oo..— 99.." non. canon ouc.~ can." «so. moo. coo. now. one.— 9.9.x coo.— cocoa 0..." ....u .9..— o...« .00. nor. «on. OOOCOCCOOOCOCCCOOCOOCOOOICOCOCCOOCC II fl u o hhfihhhfinmnnn D n I'D 00.... Ian; oo4Ioo«-ocmm 9cm umoa mum mamnma mafia mEom .um>m30m .HHmum>o 9mmmmuumv mum mucfiom mmfioz cowumxmamu umufim ms. mo muaammu mcu m3osm £~N.m muswfim .maoxu 9.9... u.:.. 9.9.ucoov NN.m muswwm 999.u moo. 999.~ 999.“ 999.“ 999.— 999.— 999.u 999.“ 999." 999.“ ooo. 999.“ 999." 999.— ooo. 999.u 999.— hoo. 999.u ooo. 999." Noo. 999." 999." 999.u 999.“ 999.u 999.u 999.« 999.— 999.u 999.— 999.— 999.~ 999." coo. 999.~ 999.u ooo. 999.u 999.n 999." 999.9 999.— o—o. 999.u o9h. 999." 999.— 999." 999.u ooo. 999.“ 999.« 999.« 999." 999.— 999.. 999.u 999.u 999.~ 999.n moo. CCOCCCCCCCOCCCCCCCCOCCCCCCCCCOCO... N a n o a o 0" n m m n n thhhhhmnflnnn .CCCCCCCCCCCCCCOC dhfihnhhhhhm 999.~ 999.— 999." 999.“ poo. 999.— 999." 999." 999." 999.« 999.. 999." 999.— 999.— 999." 999." 999.~ 999.~ 999." 999.— 999." 999.— 999.u 999.— 999.~ 999." 99m. 999.~ 999.~ 999.— 999.~ 999." n n n m n n n n n m n n n n h n n n u a a « zumozu N za-o wcfiamnma msowca m muwgz n M M .. .m m n coflumuwufi ummH may mo usmuso may msocm u-.m muswwm n . u n n . M . . . . . . . . . . M . m . C C CC...CCC.CCCCCCCOCCCCCOCCCCCCCOCCOC . z....¢... .. ....99 99.... "9... 29.999 . 29...¢u.. .. 29......ux 9.... u.:.. 29.939 . 29......“ .. .z..m.99..¢9 99.... n.:.. 2...:9 m 29...... .. 29......uz ..... nu... zumozu z....x... .. 92....u9.999 ......53 mm .m 32w... '74 N. mmDHUH. zo wgzo mo.><=mm HmmBon 9mHman 9Hm=chs HHm mum mHman wcHH ~59 n M M m m n .mmuanM maoH>mua mnu cu comHumanu no. mum: cm>Hw mum N9 n M M .. .m m n h c musuu a co 9 co mm 090 ummu mom use 0 mu :mmu m u . n . H H H 9 n m w H :9. . . . . . . . . . . . . . . . . C O COCO.CCOG...OCOtCCCOCCCCCCCCCCCCCOC . zo....... .. w:..:9 9.... "U... zumozu . z....¢... .. .z.... 9.9.. 999.. uwx.. 29.9;9 m 29M..¢..M .. 92M.m.99.9¢9 9.... u ... 29.99. 2. ..... .. .z ......9.. ..9.. n9... zumozu . z....¢9.. .. .z..m.99.9¢9 IV. THEORETICAL ISSUES IV.l. ON COMPATABILITY ESTIMATION IV.1.1. The Relaxation Rule and Local Consistency Local label consistency is achieved through estimation of node-label compatabilities. It is effected through the summation approximation of p (A) i in the relaxation rule (9). This approximation is based on the labels of the single neighbor node j and is given in brackets in (9) reproduced here and again in (36). K I_ K _| p (x) TTI X p (MN) p (x) I K+1 1 j I_>c ij j __ p (M = ---------------------------------------- (9) 1 K K Zp (x) TT 2 p (Mx') p (w) x 1 J A' ij j " K I— K "I p m = p (ME ) = I 2 p mm p (m I (36) i i j I_>\' ij j _| K The estimate p (A) is also denoted as p (XIE ) as the i i j estimate of the label A|at node i based on the evidence E at node j and iteration K. It is risky to estimate p (X) on a single neighbor's labels. A more precise i estimate involves more neighbors in some neighborhood pattern or group around node i. Zucker et a1 [8], chose the neighborhood as the eight adjacent nodes in the rectangular grid as explained in section 1.3, 75 76 equation 8. The simple arithmetic average of the of the estimates on each neighbor is used as in (37), (38): A K K K p (A) = p (ME . .2 ) =2 c 2 p lex'w (m (37) i i 1 j j ij x ij j K p (M Z c 2 p (Mm p (m K+l i j ij x ij j p m = ------------------------------------------- <38) i K 2 p m 2 c I p (MN) p on x i j ij x' ij j The estimate in (37) forms the original arithmetic updating rule given in (38). Each neighbor contribution is individually weighted by a factor C . 13' This estimate is later revised based on the closed form for the series of (37) to form the present product updating rule (9), (39). For a discussion of this derivation see [7]. K K . .B.) =TT Z p”(>\|>.')p.(>\') (39) l J 3 >8 13 3 One of the assumptions behind the approximations " K P. (k) = 19. (ME 1 l in (37) and (38) is that of independence over the neighbors. If it is true that one node's labels are independent of those nodes and labels around itself, it is a strange situation to have in the estimation of local consistency. Each label of each node i is approximated by those nodes and labels independent of the label at node i. Obviously it is a statistical 77 simplification which has succeeded by some measure, but it seems more sensible to attempt to measure local consistency using as much statistical dependency amongst the neighbors as is available. This is further detailed the next section through multiple label compatabilities. IV.l.2. The Broadcast Rule as a Relaxation Processor It is instructive to consider the broadcast process as a relaxation process for comparison purposes. The following Theorem establishes the equivalence. THEOREM 4.1 The revised broadcast process of (28), (29), and (34) can be modeled as a relaxation process with variable compatabilities and variable relaxation neighborhoods. PROOF: We need to work (28), (29), and (34) into the same mathematical form as (9) and (37) - (39). p=E'[>\.....>\]p (28) b 1 i l ' Defining E' as in (34) requires a renormalization so we write (28) in single label form with the added factor for restochasticizing as given below. p (k) = -------------------------- (40a) x* A}* l b 1 p (k) = ----------------------------- (40b) 1 Z Z 6' [>\ I ~00 I >\ ] P (A*) >\ M >03 1 b 1 Here (40a) uses the row vector e' , the kth row of E' >\ 78 in a matrix multiplication form with the column vector p . Equation (40b) is the scalar version of (40a). The i normalization is shown as being computed on the final values of p rather than by forming a column stochastic i E' as is done in practice. There are two tracks of the derivation from this point. The first uses the definition of averaged experience matrices from (23) for multiple label broadcasts. The second retains the original definitions of special multiple broadcast matrices. We shall pursue the first and begin by substituting in the definitions of E' from (23) and (34) into (40a) and (46b) for those labels receiving a broadcast: I b l IZpIM str ethI p |'=1 1 j x x j' I i |_ j ____| p (X) = --------------------------------------- (416) 1 z e' [>\ , ... y). ] p X X l b 1 IT _| I X p (x ) str e [k ] | p (A*) Z l'=l i j x WI 3' I i w |_ j __| p m = ---------------------------------------- (41b) 2 2 e' [k , ... ,X ] P (X*) >\ M M" l 1 Again (41a) presents the vector form and (41b) the scaler form. Bringing in (36) and regrouping we have: ___ p (A I .___ | b ' j I l X P (A ) --------- e [A ] I P (A*) Z Ij=1 1 3 dist(i.jI xx* 3 I 1 I* I___ I P_()) = ----------------------------------------- (42a) 1 Z X 9' [>\ I 00- IX 1 P (A*) A x* ;x* 1 b 1 I“B‘ 1 ___I . I,Z -------:- p (A ) e [K ] p (I II p \) = ----------------------------------------- (42b) 1 Z 2 e' [A . ... .x 1 p Ix*I A A* AA* 1 b 1 l‘B‘ —_—I p (x*I I.) c _ p Ix*Ix ) p,(x I I i |3=1 1) in J J j I * I___ I p (A) = ----------------------------------------- (42C) 1 IT _I pIx*II Z c . p (A*IA I p (A I I Z Z i I=l 11 in j i j I A x* I___ ___I with p. (x*lx ) = p (x ) e [k.] a new compatability 13 j i j AA* 3 estimate for labels receiving a broadcast l/ a neighbor weighting ij / dist(ipj) factor and c Labels not receiving a broadcast simply substitute the e factor from (34) into (40). Since this factor AA' is almost always zero, the derivation is not presented. Form (42c) is a similar form to the arithmetic updating rule as in (38). The neighborhood estimate of 80 p. is again a sum of pair-wise label compatabilities as 1 shown in the brackets above. The major difference is in the computation of the neighborhood contribution. The summation over X' (over all the labels of the neighbor nodes) in (9) and (37) is gone. Instead only the single broadcast label is used. In the line processor of chapter 3 the broadcast label is the most likely label although it can be any label the control, T, chooses. The derivation of the second track for multiple label experience matrices begins from (40b). Again the subtitution of the definitions of E' and the further reorganizations form an equation similar to (41b). The summation over the broadcast labels (over the index j) from averaging is now absent. Substituting (34) we have: X* X XX* 1 b 1 p.(X) = ---------------------------------- (43a) 1 Z Z s e' [X . .X] p (m X X* X XX* 1 b 1 Where 8 is the combined or assigned strength, and S X is the Xth element of the row vector 8. Since these experience matrices are free to encourage any or all of the received labels, or even to encourage different labels, it is difficult to characterize the S values for labels in general. To continue this analysis, we will treat those labels which are encouraged and simply 81 retain the broadcast strengths as defined in (30), (34). Other labels are updated by the e' factor of (34) alone. As above, e' is often zero and the derivation is omitted. Expanding the definitions of S and e' we have 1.9 2 --------- PIX)e pIX)p(X*) X* dist(iyj) i j XX* j j i pOIXI= ----------------------------------------- (43b) 1 Z 2 e' [X . .X] p (X*) X X* XX* 1 b 1 1.0 Again let c = --------- i dist(i,j) and let p (X*|X ) = p (X ) e so we have ij j i j XX* U I I i I113 33 I I p_3 1 i I ij 1 b j ' '__I ll ... LJ The neighborhood estimate of p (X) is the i expression in brackets above and given again in (46). A P (X) = P (X*|X ...X) 19'— P (X) (46) i ij 1 b j=l j j This estimate is the desired N-ary compatability measure desired. ********** The estimate obtained in (46) should be compared to the RLP estimates from (36) and (39). The RLP estimates are sums of products of pairwise compatabil- ities. As such they are estimates of the correct form of the equation as used in (46). The DRLP estimate of (46) is free to exploit the label interdependence information that is available in the multiple label conditionals. IV.l.3. Conclusions The following conclusions can be drawn about the broadcast process as described: 1. The broadcast rule can be viewed as an RLP with dynamic relaxation neighborhood and dynamic compatability measures. This variability is under program control and dependent on the incoming picture 84 and the semantic world knowledge about the labels. It is carried out through the broadcast process and seen mathematically in (42c) and (43). Thus the information in the picture is more efficiently exploited. (see also section IV.3) ' It is also important to note that the dynamic case is closer to the original definition of Waltz [2] and the meta-description of Haralick [3,4,5]. Waltz used particular information about lines and junctions to resolve ambiguity in labeling. The experience matrices are set up to hold information about particular labels as opposed to the RLP compatability matrix which contains information about all the lines and labels. Both Waltz and Haralick use semantically defined N-tuples of nodes in a general graph to desribe these labeling relationships. The RLP has only pairwise label compatabilities. True N-ary relations are possible through the reception of multiple label broadcasts for which special experience matrices exist as shown in corollary 4.1.1. and in (46). Results from a dynamic relaxation system with multiple label experience matrices is given in section IV.2. 2. Dynamic relaxation is computationally quicker to perform due to the absence of the innermost summation. This is born out in practice where the relaxation rule computed straightforwardly as in (9) requires 6.5 to 85 6.6 seconds per iteration while the broadcast rule requires .35 to .6 seconds per iteration. Part of the savings rests on the fact that not all nodes broadcast or receive a broadcast. If every node broadcasts and receives then approximately 1.8 seconds per iteration are required. (These figures are taken from the timing data in the pictures of chapters III.6 and IV.2.) 3. Dynamic relaxation can be seen as a first term approximation to the neighborhood contribution series (36) of the full RLP when the broadcast label is the most likely label. The overhead of finding the most likely label at each node is akin to the ordering of each branch of a tree sort prior to the sorting of the whole list. A faster sort results overall. The same is true here: broadcasting is an improvement over the product rule as the product rule improves the arithmetic rule. The gain is not only in execution time but also in resolving power as shown in the results of chapter 3. It is interesting to note that previous attempts to improve the speed and convergence power of the RLP have centered on homogeneity. The solution is in irregularity instead (just as with the complexity solutions Waltz found). Haralick has shown that general relaxation is an NP complete problem. Dynamic relaxation is also NP complete but faster by a factor of k, the number of 86 labels in the label set. 4. A method for defining the variable compatabilities is given by (42) based on a constant world knowledge factor e and the broadcast strength. The world XX' knowledge here reflects any information available about structure and interrelationships of objects. There is a certain flexibility in the numerical specification of the world knowledge due to the broadcast strength. One need not be exact as suitable scaling is done by the strengths for each broadcast. 5. Averaging single label experience matrices for multiple label broadcasts also requires the assumption of statistical independence over the neighboring nodes, as seen in the resulting similarity of (42) and (37). Hence averaging of single label experience matrices is no worse statistically than the RLP. The importance of the developement of multiple label matrices is highlighted since such matrices embody the multiple label conditional probability information and as such are free to exploit statistical dependencies for consistency approximations. 6. Convergence time and fixed point behavior of the broadcast process is dependent on the definitions of the broadcast patterns. This is further discussed in section IV.4. IV.2. DYNAMIC RELAXATION LABELING IV.2.1. DEFINITIONS The mathematics behind the concept of dynamic relaxation was presented in the preceeding section by the development of equations (42c) (43d) and (45). In dynamic relaxation the broadcast algorithm is used as a stand alone system. Since every node must be processed in such a system, every node must receive a broadcast. To accomplish this, most every node will also send a broadcast. Every label will particpate, including the blank label, and not just the line labels as in the ARLP. The broadcasting pattern for no-line or blank labels is given in Figure 4.1. A broadcast of a blank is sent to the 8 adjacent nodes of the broadcasting node. The experience matrix for the reception of a single blank label is given in the appendix. Experience with blanks shows them to often be either picture background and or boundary nodes for lines. As background, the single label experience matrix for a blank uses a constant value to describe its relation to the different line labels. This allows the experience matrix to control background noise of any label equally. The experience of blanks as line neighbors should encourage the formation of lines. This follows from the character of a line and is easily seen in the 87 88 * * * * .45 * * * * The blank or no-line 1abel’6 has a broadcasting neighborhood as shown in Figure 4.1. The pixels represented by an asterisk (*) can be reached in one broadcast. Figure 4.1 BROADCASTING PATTERN FOR NO-LINE (BLANK) LABELS 89 relationship of lines to blanks in a 3x3 pixel neighborhood. Simple averaging of the blank experience matrix given above with the line label experience martices used previously does not give satisfactory results. One matrix encourages the line while the other treats it as noise to be discouraged. The expectation of such an average is that weak lines would be lost and line ends would be shortened. The results of such a system are given in Figure 4.2 and 4.3 for the test pictures. In picture 1 the low probability lines and line ends are lost to blanks. In both pictures noise is adequately controlled although the convergence rate for lines is slower. Simply adjusting the values of the experience matrix is insufficient to resolve the problem. Too low of a value will not affect the noise. Too large a value removes the lines. The solution is the same solution that was suggested for the line intersection problem as indicated in section III.3.l. IV.2.2. Multiple Label Experience Matrices Multiple label experience matrices are introduced to solve ambiguity problems when multiple labels are received. Matrices for blank and line label combinations and for line intersections are developed. When blanks are present in a received broadcast the experience matrix used is chosen based on two factors: 9() ozHHm15 mocwm van u » w m m u vmnmficaefiu ma wmfioz .mm.m 28 -.m muswflm ou muasmmu 9.55 98980 n M. w a a a m m n .mmUHuumE mucmfiumaxm Hmnma 925:2: usonufiz Enufiuowam coaumxmamm u M m u oHEmcxa wnu Eouu fix «2593 so muaammu mucmmmua m3 muswfim n p u a u u a u a u u u u u « ... 0.00.00.0.00....CCOCCICCCCOOOCCCCOQ CCCCOOOOOOCOCO.COCOOCCOOCOCCOCOCCOCCOCCOC00......0.0.0.0...00.00.00...COCOCOOOOOOCCCCOOCOOCCOCOCO... coon. \coou. gnaw. \aoao. can. cow» » a a oooooea xux z~¢puzxuxu4 4u>u4 u .400 uzuaoz o oacu uuzu~¢uaxu Nxmxx» uxmth uocz >¢u>u z»¢z¢cu2~ oDDUD uuzuaoum 9 c o CCCCCOCCCCCCCC.C...CC...CC.C.CCOCOCICCOOCC.CCCCCCCCCCCCICCICOCCOCCOCCOOCOCCOCOCCCCCCCOCCCCCCCOICOCC. .99.. 99... 999.. 99... 999.. 99... 999.. .99.. 9.9. 9.9. 999.. 999. 999.. 99¢. 999.. 999.. .99.. =9... 99:. 999.. 999.. 999.. 999.. 99.. can. coo. 99¢. .99. 999...999.. 999.. 999.. .99.. 99:. ..9.. 9... o... ‘9'. .99. 999.. 99.. 99.. ,999.. ..a. .99. new. 999.. 999. 9.9.. 99:. 999.. 999. ..9. $.9. 999.. .... 999.. 999.. 999.. 99.. .99. 999.. 999.. 999.. 9:9. .99. 999.. 999.. 99.. .99. 999.. .99. .... 999.. 999.. a... 999.. 999.. 999.. ~99. .99.. .99. 9.9.. «no. 999.. 999.. 999.. .... 999.. 999.. 999.. a... 999.. 999.. 999.. 999.. 999.. .99.. 9:». 999.. 9... 999.. 999.. .99. .99. 99». 9.9. .99. ..o. 999. 999.. 999.. .99. wc.w..m99.. 9.... 999.. .9... ..9.. mrxum 9.9.. ..9.. ..9.. voc.. .9... o... a... 999.. LL... rm...— ooc.~ new. coo.— ncv. 52.. you. :3. row. out. put. one.“ one; on... coco— .9o. 99:.. 999.. 999.. 999.. 999.. .99. 9... 999.. 999.. 999.. a... 999.. 999.. 9... 999.. ..c. a... 9.9. 999.. 999.. 999.. 999.. age. 999.. 999.. 999.. a... 999.. 999.. 99... 999.. .99.. 9.9. a... 999.. 999.. 999.. 999....99.. 999.. a... .9... ..o. 9.9. 999.. 99.. 999.. 999.. 99.. 999. 999.. .99.. 999.. 999. 999.. 999.. 999.. 999. 99... 999.. 999.. 999.. 999.. -99.. a... 999.. 999.. 999.. 999.. 999.. 999.. 999.. .99. 999. 999.. 999.. 9.9. .99.. .9.. 999.. ....W 999..,999.. .9... .99.. .99.. one. 999.. 9.... 99... .99.. 999.. .99.. a... 99.. are. out; .73.— can 30.. 23.— 23; .35.. coo.” aw... 2.... an...“ we... can.“ one; on... COCOOOOCOOOOCOOCOO00.000.000.000... o o . u n ... a .. . . n . . . . o 9 m . . n u 9 n . . m a 9 m . . v .9. p n . . p. ... ... m. . . annnrmumnnmmon . . 9. 9. n . n . . 9 9 n n . . 9 s n n . . 9 u u . q — n . o F r: . o h n o o 9. u u u . — ~ g u ~ ~ g _ a o a o 0.0.0.0...00¢...00.0.00000000000000 ‘ w 2c.999... .9 wam.ao coar.. u.:.. zgmoxu m 2o..¢¢u.. .9 oz..m¢ 09cc; 9.99.. nu;.. z.nozu c zc..<¢... .9 oz..m.uo<=9; 99xa.. u.:.. 2.99:9 m 2c..¢¢u.. .9 9:..m9uo Ele for str *p (X) > 0.0 X i and 6 or fewer blank labels (b) received 2. Noise control E[b, X] => E[b] for str *p (X) = 0.0 X i or when 8 blank labels (b) are received 3. Noise control, default E[b]/3.fl + EIX] for str *p (X) >a.0 E[bl X] => ----------------- x 1 2.0 and 7 or 8 blank (b) labels received The choice of the count of blank label broadcasts received is based on the relationships of the line in a 3x3 pixel neighborhood. The strength factor str*p (X), is simply an existence criteria of label X at the 1 receiving node. Case 3 is in some sense an indeterminant case where iteration must resolve the ambiguity. The strength of the blank broadcast is reduced so as not to completely dominate the line label broadcast even though the label existence may be due to noise. 95 When several different line labels are received, the possibility of.a line intersection exists. To label an intersection, an additional label, I, is added to the system. The label I is encouraged based on the received strength of the labels as given below. Table 4.2 INTERSECTION LABEL EXPERIENCE MATRICES 4. Intersection E[X , X ] => E[I] when str * p (X) > t l 2 Xj i for 2 or more labels j. t a suitable threshold 5. Indeterminant E[X ] + E[X ] for str *p (X) > t E[>\I>\]=> 1 2 xi 1 2 -------------- for less than 2 2.0 labels The choice of a threshold in case 1 is dependent on noise present in the picture. The application of the I label is not appropriate simply when a broadcast for 2 labels is received. Noise may exist at the node to make the received strength non zero. In such a case the intersection label could be inappropriately chosen. If there is a strong presence of several lines at the node then an intersection is likely. In the indeterminant case, iteration must resolve the difficulty. 96 In both tables the definitions of the multiple label matrices is given for a label pair. The definitions should be considered as operators on the received label set where necessary. For example, a received label set of [X,, X , X , blank] can apply 1 2 3 both rule 1 and rule 4 to yield E[I] or perhaps rules 3 and 5 to yield the default case of an average over the single label matrices. IV.2.3. Results The dynamic relaxation labeling process (DRLP) was applied to the second test picture. The results are given in Figures 4.4 and 4.5. The results of Figure 4.4 use a threshold of .75 for cases 4 and 5. After one iteration, most of the noise is overcome, many of the lines are uniquely labeled, and the intersection label has appeared for the line intersections at the sides of the rectangles. In the second iteration, the intersection label is applied to the triangle rectangle intersection. Since so many labels shared this intersection an iteration was needed to build up the broadcast line strength to meet the threshold. By the 5th iteration almost every point is uniquely labeled. These results should be compared to the results of Figures 3.14-3.20. Correct convergence is much more quickly obtained. The rectangle corners are not line intersections as drawn. One line ends and the other begins. In this case the discrimination is correct. 97 Corner labels could likewise be added to reflect the different types of corners that Waltz describes [2]. The results of Figure 4.5 use a threshold of l.@. After 4 iterations, the intersection label was not applied at the triangle rectangle intersection. Almost all other nodes are uniquely and correctly labeled. Hence the choice of threshold value is significant. S)8 mm. H GaommmmmH 999.. 999.. 999.. 999.. 999.. cacou Queen mhmo occou ocean 999.. 9.9. .... .9... 99... cocou 0060' ooo.— noo. wow. 9... ..9.. 999.. 999.. 99.. ecu-n 9'0. accou who. :99.— 999.. .99.. a... 999.. ..o. .... «..99em... 9.... 99... 999.. 999.. 999.. .... 999.. 00$. .090“ 99¢." :90." one." 9.9. ..9... 9... 999.. 999.. caoou .09.“ «mo. Goa-n coo-d ooo." Bacon two. cocoa cocoa 999.. 9.9.. 999.. 999.. 999.. 999.. 9..., 99... 9.... 9.... van. cccon nae-u can." ecu-u ZOHHUmmMMHzH N§ MMDHUHm zo ZOHHoE Imp mH mmfio: nose cofiumumuw mco umum< .mmecmuomu o3u .Ne eunuofia :o mmmooua cofiumxmamm oHEmcza mcu mo muasmmu mnu mucmmmum c.q ouswwm osnoou one." can." cam. cocoa Qua. coo.— cocoa cocoa ace.— cocoa ooo.— cocoa coo." boo. mum. mac. .... 999.. ..... 999.. 9... 999.. 999.. 999.. 999.. 9... 999.. .... .... 9... .99.. age." canon OQO. nnm. coo.” coo-u 999.. 999.. ..... 999.. 999.. 999.. 999.. 999.. .9... 999.. 999.. 999.. ooo. qua. can.» wow. goo. coco. .9... .9... mm.ww ..... ..9.. ..... 9... 9... .... 999.. 999.. 99... eecou one.“ can.U cocoa :99." sec.“ 999.. 999.. .... 999.. 999.. ..9.. .99.. 9.9.. 99... .... 999.. ..9.. 9:9." ooo. ca=.— cocoa age." a...“ hco. aha. ace.“ cocoa son. oaoou .99.. 99... ..9.. 9.9.. 99... 9.... cm0. ammo oce.— mom. can." can.“ COCCOCCOCCCOOCCCOOCCOOCCCOOQCCCOCOC C c m m n m n c n u a u n o s n . n o s n c n m h n c n o h n . n o h n . n m m m m m H n m m ~ 0 o h h n o h h n c h h n . . . . . . . c s . s c h 0 nut—p a u n u a u u u a u u a unnnnnnn CCCCOCCCCCOCCOCC COCO-COCO...CCOCCCOOCOCCCOCCCCCCOCC zuwozu a a zo~h¢¢Ub— p¢ hamhao zo-<¢up~ p4 uznpmcuoccxm 959 ooo.— ooo.. occ.~ aoa.~ moo. ooo.— ooo." 00¢. :95.“ can. mom. ace.“ cee.~ can.“ coo.— www. 99:.“ 999.. out. 960.“ ooo.~ ooo.~ one." we...“ ooo.— eea.u .09.. one.— ea..— .09.— woo. ace.« .9... 999. 999.. 999.. 999.. 999.. «or» 999.. 999.. 999.. 9... 9... .99. 999.. 999.. 999.. aoc.~ ace.— 90°.u 00$. can.“ 00:.— Geo.— ooo.— coo.— ace.— aoo.~ ecu.— ooo.— coo.— coo.— 99:.— 999.. 999.. 9.... «99.. ca..- 999.. 999. no... 999.. 999.. 999.. 999.. 999.. 999.. 9.9.. 999.. can.“ eee.u 999m. 2. 99... 999.. 999.. 999.. 9.... 9... 999.. 999.. 999.. 999.. 999.. 9.9.. 999.. 999.. 999.. .99. .... 999.. 9994.999... .99.. 9.... 9.9.. .99. 9... one." 0.9." 96:." can." 999.. 99... 9... 999.. can.“ ....u aea.~ can." 999.. 999.“ 999. 999.. 9.... m9... 9.... ..9.. .99. .9... 9... 999.. 999.. 9.9.. 999.. 99... 96°." .00." occ.~ can.“ 999.. 99... ..9.. .9... a99.— aeo.~ ace." ace.— eoe.u ee=.~ oec.— ace." 9.... .... .99.. 9.... 99:." 099." eeo.— 0N5. N cmcc.— untup tumoxu N zc~b<¢ 999.. ..... 999.. 999.. 999.. 999.. who. .9... ooo. 999.. 999.. 99... mom. cam. .99.. new. 660. 95:. 999.. 999. ..... .... ..... 9.9. ..9.. 999. ..9.. 999. 999.. 9... .mnnu. 99.. .99.. 999. .9... 999. 9.... 999. 0.01“ omw. coe.— 9:9. 909." ooo. can.« .09.“ co..— eoe.— Ops. COCCCCCCCCCCCCCOCCOCCCOCCCCCCOCCCCC CCCCCCCCCCCCOCCC A.o.ucoov q.q muswwm " d n a o o w o n m m m m Nhhth—nnnfln m h u u a u a q u a u n u u CC...COCOCCCCCC.CCCCCCCCCOOCC u oce.u ooo." ace.— a 6:9.“ ace.~ ace.— cmo. ace." ecu.— oae.u :99." 69°." a canon ooe.« see.— u 99°.u ace.— ace.— occ.u canon ace.“ a one." 0...“ 990." u ouc.— .90.“ ace.— " cue.n ocuou 90:.— n 099.“ .900" one." can." canon oee.~ — 959.“ ....u ace." u 006. ocean mom. a...“ new. ecc.~ coo." an. c m n m n m c h n c h n c h n c h n a h n o u n n 0 ~ 5 m n o h n n c s n n o 9 n n . a n u u u n c n c n c u o . ...... zo~h<¢u u pd hambno Uhu ht Znhmtuocoxm 100 age.— can.— 999.— ooo.. moo. ooo.. 999.9 own. can.— mom. moo. ooo.. can.“ coo.~ 999.. 99.0. oc=.~ ooo.~ mew. eaa.u eoo.~ oea.n coo." wwo. 9:9.— ace.— cog.— can.— 999.— :99.“ now. can.“ coo.~ ooo.“ oce.u :99." can.— cee.~ 00v. can." :99.“ ooo.u arm. can.— ooo.~ 99:.— can.“ ccc.n cae.~ 99:.u can.” 909." bee.— ooo.— Goa.- oee.~ eeo.~ 99:.“ 99:.“ can.“ ecu.— 99:." 99:." can.— cae.~ ecu." cog.— eee.u aeo.~ can.— 99:.“ one.— 90:.— 9:9.— ace." ooo.“ can." one." :99.— ooo." ace." one.— 999.“ can.— 99:.— ooo.— 99°." 99°." onc.u ooo.— eeo.u coo.— coo.~ ooo.u one.“ can.— aeo.n can." a aec.u one.“ :50.“ caa.u acc.u n aca.— eoe.u coo." ace.u 99¢." a one." can." eea.u ooo." 599.. a 999." can." one." cca.— can.“ a aaa.— eca.— nee.— eeo.~ 699.. can." aeo.n cce.~ 5 age." ooe.~ ace.— aea.— 99:." Dee.— aca.— can.“ can." coc.— coo.q 0 cm. mm. 09." no. 00. oe.~ on." one. 999." com. coo." coe.u eeo.u ace." one." aoe.— one." eee.u ace." coe.— ace." cee.~ eoe.— cac.u ooo.u aoc.~ 99°.n ooo." oae.u ea=.n 999." «mu. aoo.u coo." oec.u can." eec.~ eo=.u ooo." ece.u ecu." 993." oee.u oco.~ ecc.— ooe.u ooo.“ eec.~ ooo.— eee.n 000. 999." who. eee.~ cae.n oeo.u coo." coo.n coo." can." 999.— :99." ago." eec.u cee.u acc.— 9:9.u one.— aoe.u ace.— eec.u one." age." ace." can." ace.n coo.— oce.— ecu." sec." eoc.n 999." 999." coo.— eao.~ eeo.u eee.— 9:9." 999." oce.u can.“ :99." eee.— cae.u one." ooo.— eeo.~ ace." ooo." aee.~ use.“ see.“ one.u can." saw. one.“ can." ooc.~ ace." ooo." ace." coo. 0mm. mom. ago.” 990. one.“ an:.— Now. .OCCCOCCC...CCCCCCCCCCCCC’OCOOOCCCC C C . m n m n n . . n 9 a a a m h n . o n o h n a . n w s n . . n m s n . . n o h n . . ~ n n n m n u n n m n n n n . . 9 9 n n . . 9 9 n n . . 9 9 n n . . 9 a u a u n n . c h n c c h n c . 9 n a n u a 9 u a 9 u u m a . C C CC...COGCOCOCCCCCCCCCCCCCCCCOCOCCCC c zc—hczup~ 99 ham—:0 mozu o zo_»<¢u9~ p. oznpmQ 999.. 999.. 9.9uw. 999.. 999.. 999.. 999.. 9.9.. 999.. 999.. 999.. 999.. 999.. 999.. 9.9.. 999.. ace.— ooo.a a.o.~ can.— can." cec.u coo.— cocoa aeo.~ ooo.u aco.~ can." 969." can.— ....u can.— m.q muowfim 90:.“ one. one. 9.... ..9..,9.... .99.. 9... 999.. .99.. 999.. 999.. ..9.. 999.. 999.. .99.. 999.. 999.. ..9.. .... 999.. .99.. .9... ..... one." 990. oe=.~ can." ace.— baa." ..9.. 999.. 999.. .9... .99.. 999... 999.. 999.. 999.. 999.. 999.. 999.. 99... ..9.. .9... coo.— cca.~ woo. .9909999e9 9:. umwuma o 5993 mqma mnu mo madame. ecu wucmmoua m.¢ ouswfim .mmHoc mxwa muoe mummaam .vaonmmunu cowuoomumucH CCCCOCCOCCOCCCCC. ooo." 600. one." 099." cac.n nee.— .O.ou cocoa 969." 999.“ eco.n cec.~ cae.~ ....u 999." eco.n cue." coe.~ ace." 0..." 00’. 09°." ace.— aoo.u aeeou ....“ ace.u can." coo.— one." cocoa cocou can.“ 999." eee.— 99°.g wow. 09..“ who. one." eec.~ ecu.— .o..« 0.00% 0...“ cocoa ...ou eec.~ nee.“ ooo." eac.u can.“ cocoa can.“ can." .09.“ 99:.“ aoc.n .090“ 999." ooo.“ coacn one.“ cocoa cocoa eeo.~ ...Jn 0.9." aoe.~ one." cocoa ooo.u coo.u cea.n eee.« 99°." ecu-u one.“ oeeou coo.“ 60°.u 09°.“ 0..." how. cooon ....u ....d canon cocoa ooo. mcw. cae.— :99. 96°." ooo.~ Noa. occcoocccococcc.ooccccccacccocccccc c o n m m n n c n n n u o h n o n 0 h n c n h n . n o 9 m a n m h n a n n n m n n n n a n ~ 0 m n . 9 9 n n c h h n n . 9 9 n n a h a a u u u n c h n o h n c h u u a u u n n n a u n a n C coccccooaccoccc.«cocacocooocccccoo c 2°~h<¢u»— kc wan»:o Zumczu c zcuhdauhu h¢ czuhwt a¢o¢m ammozu n to b<¢Uh~ b< mauhwtuodozm tumozu N 2° btxuhu pd wz-w<90¢o¢m zwmcxu u 2° pcmwhu pd atahm¢904o¢o IV.3. INFORMATION MEASURES The effect of an iteration of a relaxation or of an broadcast process can be modeled using information theory. This model is presented below. The following sections present interpretations of the common information measures and actual values for the RLP and broadcast systems studied. IV.3.l. The Model The Shannon information communication model [l4],[lS], centers around a channel through which a set of messages pass. A set of source symbols, 8', makes up these messages. Each symbol has an attached probability which describes the probability or frequency with which the symbol is transmitted through the channel. The output message is composed of the symbols in the output symbol set, 8. Again there is a probability distribution over the output symbols describing their probability or frequency of being received. The channel is described by a column stochastic conditional probability matrix which yields the probability of a particular output symbol given the input symbol. In a relaxation labeling process or broadcast process the information used to update the probability distribution of the label set,,X, at a node, i, comes from the probability distribution over the label sets, X', of the neighboring nodes, j, according to the 102 103 relaxation or broadcast neighborhoods. The relaxation systems fit the Shannon model as follows. The input symbol set is the set of labels at a single neighboring node with the associated probabilities. The channel output is the neighbor contribution to the updating of the label set at the receiving node as a set of probabilities over the label set,X. The channel matrix is simply the compatability matrix, p.. or the 13 experience matrix E'. A message is a single label. The existence of a channel between any two nodes is dependent on the relaxation and broadcast neighborhoods. For the RLP, the homogeniety property requires a channel between a node and each of its 8 adjacent neighbors. In the spirit of homogeniety, this channel should have identical properties for each neighbor. In the line processor, the compatabilities depend on the angle between the node and neighbor (see (20)). Hence there are eight separate and distinct channels, one for each neighbor position. In the broadcast system, a channel exists between any two groups of nodes that is desired as specified by the broadcasting patterns. In the line processor, all broadcasts of one label received at a node are pooled together and the strengths summed (see (30)). Hence, a channel exists from a group of nodes with the same broadcast label to the single receiving node. This 104 arrangement is depicted in Figure 4.6. In the process of an iteration, information flows through the channels from the neighbor nodes j to the receiving node i. This information influences the probabilities over the labels at node i as described in IV.1. If on a later iteration, information from i reaches node k, there is the effect of a cascade of channels bringing information about j's labels to k through i. Consider the case where node j is allowed to broadcast directly to node k. A direct channel exists and the information about j reaches k in one iteration of the broadcast system. In the RLP however, two iterations are required and there is the additional loss to noise in cascaded channels as is well known. The situation is illustrated in Figure 4.7. Such cascades are the way local consistency is developed into a more global consistency in an RLP. The cascades in each case are combinations of the eight known channels. The broadcast system, in contrast has as many direct global channels as world knowledge permits. In fact, each channel is custom tuned by the parameters of (29) to carry its particular broadcast directly. Cascades of broadcast channels also exist spanning even greater distances. It is difficult to compare such complex systems in a general mathematical way and will not be attempted here. 105 NODE CHANNEL 1 The single channel used by the four nodes broadcasting label X5 to the receiving node i is depicted.) In the broad- cast process, identical labels arriving at a node all use the same channel. Compare this figure to Figure 3.2. Figure 4.6 BROADCAST CHANNELS 106 ITERATION I ZODE X l J' NODE :9 CHANNEL 1 NODE k ITERATION I + 1 NODE A "-~a-—- j I \ NODE ‘~:::::::::=[> 1 CHANNEL ‘ NODE h __i) k CHANNEL Information about label A at node j is transmitted to node i at iteration I. This information is further transmitted to node k at the next iteration. The resulting cascaded channel from j to k with the attendant losses due to noise models the RLP local consistency process. Figure 4.7 CASCApED CHANNELS 107 IV.3.2. The Measures The standard entropy and channel measures are applied and interpreted below. The source entropy, H(X'), gives the average amount of information in each label of the source alphabet. (47) k 0.0 < H(X') = -2 p (X') 109 p (X') < 109 k X' j 2 j 2 A value of zero for H(X') indicates a unique labeling, where one label has probability 1.0. A value of log k indicates that each label is equally likely or that the picture labeling at that node is completely ambiguous. In the case of a high entropy, it is expected that there would be little information available to the local consistency estimation. The broadcast threshold system of the line processor excludes this case as described in section III.3.l. Output entropy is similarly defined for the neighbor contributions (eg (37)) over the channel output label set‘X. This is different than the final label probabilities from one iteration of the RLP (eg (36)) because of the normalizing process. A second output entropy can be defined over the final label probabilities if desired. To distinguish between the two we will refer to the first as channel output entropy and the second as final output entropy. One very basic measure of the effectiveness of the algorithms is the decrease in entropy from the initial 108 label probabilities, the source entropy, to the final output entropy, over the final label probabilities. To compute the entropy drop, subtract the final output entropy from the source entropy as computed by (47). Two measures of the channel are the dispersion and equivocation. The Dispersion or channel entropy, H(X|X') is a measure of the uncertainty of the received label X when it is known which X' was sent. H(X|X' = - E E P(X'.X) 109 P(X|X') (48) X' X 2 0.0 < H(X|X') < log k 2 The dispersion is a measure of information lost in transmission, dispersed from the input symbol over the output symbols. The higher the value, the more the input is spread out or lost. In a deterministic channel, the dispersion is identically zero as each input is mapped to one output (eg each column of the channel matrix has one value of 1.0). Dispersion is usually desired to be as low as possible. The Equivocation or noise entropy, H(X'|X) is a measure of information lost in transmission due to noise. It is the uncertainty about the received symbol, X', averaged over all received symbols. Again a small value here is prefered. In a lossless channel the equivocation is zero (eg each row of the channel matrix has one value of 1.0). 109 k k H(X'IX)= - g ; pLX'.X) log p(X'|X) (49) ' 2 0.0 < H(X'|X) < log k 2 The equivocation is the measure of loss often used in channel cascades. An ideal channel is both lossless and deterministic. The Mutual Information, I(X',X), is the average amount of information received per symbol transmitted. As such it is a measure of the information transmitted through the channel. In the relaxation model this corresponds to the amount of information received for label updating from the neighbor(s) on the other end of the channel. Obviously the larger this value is, the more effective the iteration can be in the updating process. 0.0 < I(X'.X) = H(X') - H(X'IX) < 109 k (50) I(X'.X) = H(X) - H(XIX') 2 I(X'.X) = I(X.X') The Channel Capacity, C, is the maximum information that can be received per symbol transmitted, using an average symbol. It is a measure of the channel's ability to transfer information clearly, without loss. 0.0 < C = max I(X,X') < log k (51) over p(X') 2 110 The channel capacity is then a measure of the maximum average information received per symbol transmitted. As such, it is a measure of the amount of knowledge in the compatabilities on how to use the neighbor information. As the channel capacity rises, so does the potential information flow from the neighbor nodes to the node being updated. The measure of actual information flow is given by the mutual information as stated above. The difference between the mutual information and the channel capacity reflects how well the capacity is used for a given input. As is seen in (50) above, the capacity is greater when loss due to equivocation and dispersion is low. In a deterministic channel therefore, C is the maximum: log k. The channel capacity is in general very difficult to compute. It can be done for the special channels mentioned above and by a Gauss-Jordan (relaxation) technique if the channel matrix is non—singular. IV.3.3. Channel Capacity in the Line Processors The channel capacity of the RLP compatability matrices cannot be directly computed since they are singular. The experience matrices are also singular in general. An exception where capacity can be computed is the case of the reception of strong label broadcasts. The single label experience matrices and the intersection label matrix become deterministic 111 channels for strong enough broadcasts. This allows at least a partial characterization of DRLP capacity as a function of the broadcast strength parameter: str . X This is seen in the following theorem. THEOREM 4.2. The channel capacity of the single label experience matrices is dependent on the broadcast strength with a maximum of log k. PROOF: We will show that the single label experience matrices approach a deterministic channel for large enough values of str . The channel capacity for the X deterministic channel is then computed. The single label matrix is described in (34) as a row vector for the broadcast label and a diagonal. The elements in the row are monotonically increasing, dependent on str , to a maximum of 1.0. The diagonal A. elements decrease correspondingly to maintain column stochasticity. This behavior is illustrated in Figure 3.12 and in (52). lim e' = 1.0 for the Xth row (52) str -> 00 XX' X lim e' = 0.0 elsewhere str -> 00 XX' X (str need really only approach a small integer as shown in Figure 3.12 rather than infinity.) For sufficiently strong broadcasts, the resultant experience matrix has only a single entry, a 1.0, in 112 each column and is thus a deterministic channel. The particular strength value needed can be deduced from the initial experience matrix values in (34) and as shown in the behavior curves as described in section III.5. In the deterministic channel, the dispersion (48) is zero. Substituting in the experience matrix scalers from (34) and (52) the desired relationship between channel capacity and broadcast strength is established. k k H(XIX')= -Z Z p(X.X') log p oo lim I(X,X') = H(X)-H(XIX') = H(X) str -> oo lim C = lim max I(X,X) = H(X) str -> oo str->00 X' (48) (53a) (53b) (54) (55) (56) In the limit of (54), as e' goes to 1.0 for the Xth row the log e' factor goes to 0.0. In all other terms the factor e' goes to zero and so every term in the series goes to zero and the dispersion becomes 113 zero. Hence the mutual information depends only on the source entropy as given in (55). Since the channel capacity is the maximum mutual information, and the mutual information depends on broadcast strength, for strong enough broadcasts the channel capacity depends only on the source entropy H(X). Hence the channel capacity is log k for strong broadcasts. ********** It is important to note the dependence of the mutual information on the broadcast strength. It is the mutual information that is the measure of the channel effectiveness. Hence the effectiveness of the broadcast system increases as the strength of the broadcasts increase. This is intuitively pleasing since the strength is designed to represent the certainty of the label being broadcast. IV.3.4. Measures for the Line Processors- The information measures defined in section IV.2.2 are computed for each node in the second test picture for the RLP, ARLP and DRLP. A picture wide norm for the entropy drop, mutual information and dispersion is given for each iteration. For the broadcast systems, there is only one channel per node. So computation is straightforward. In the relaxation systems, the mutual information and dispersion are computed for each of the 8 channels and then averaged to get single measures for the node. The norms are averages over the nodes processed by that particular system. 114 The measures are presented in Figures 4.8-4.11 for the ARLP and DRLP systems. Figure 4.8 is a repeat of the ARLP output of Figure 3.21 but including the information norms. Figure 4.9 presents 16x16 entry tables of node measures. For brevity, only the first two iterations are presented. Figures 4.10 and 4.11 present similar results for the DRLP output of Figure 4.4. Figure 4.12 presents the results of Figure 3.20 from the RLP for comparison. Several observations are in order. The dispersion values for the relaxation system is close to the maximum of logzk = 3.1699 while the dispersion for the broadcast systems is close to the minimum as predicted in Theorem 4.2. What is happening is that the RLP is spreading the input information out over the entire label set, then choosing particular portions of the information based on the receiving node probabilities and renormalizing it. The effect is similiar to mashing a potatoe, finding the largest remaining lump and using only the lump. The reason the RLP has any success at all is because the compatabilities are set to make lumps representing compatable labels a little larger than the others. The broadcast systems by contrast, concentrate the input information around the received label as directed by the broadcast reception. This is a far more 115 appealing way to utilize world knowledge. The node entropy drop figures are also intriguing. The broadcast systems have a greater ability to decrease the labeling entropy. As Figure 4.9 shows, the relaxation system actually increases label entropy, increases ambiguity, for some nodes. The mutual information figures, channel effectiveness measures, also are uniformly better for the broadcast systems. In fact for the RLP the mutual information for a particular channel can even be zero. This indicates that on the average label, no information was received from the neighbors at all. IV.3.5. Conclusions The information model provides a well recognized and understood model for the relaxation process. Simple numerical measures result by which the compatability or experience matrices can be evaluated as channels. The channel capacity gives a measure of potential, while the dispersion and equivocation show the nature of the information losses. Mutual informa- tion is the performance measure for an iteration. It can be a useful measure for the stopping of computation which is not worth the cost for the information gained. Such measures give insight into design criteria as well. Matrices can be trained or chosen to meet specific operational or selection criteria. 116 N§ MMDHUHm zo m4m< mmH 20mm mzmoz mmamQouucm 30H pom coHumauom:H Hmauss 30H ucmocmuum wsu bum cofiumxmaou you mo=Hm> cowmuwamfic owuma onu muoz .mEpoc cofiumsuomca mnu pow mEuoc mcfia muauofia mmvsaocfi 3b: as; HN.m muawfim mo bamboo onu mumomwu w.¢ muawfim smmhow 2mxaw—o «coo. acme opzu page. a<3p=t can—owuuuz—h coco. 2m¢am_o among: doze .pzu smoo. acapat undue“ nut—p ommhow meamuo ammo. memo o—zu mcoOo a¢3~=t oocqownuuxuh saga. 2mzdm~o snag-I coco ohzu snug. 4m mum mmuswfiw mmmse .Hmccmco comm pom mocwn vcm musuowm MSu cw moo: comm now mmusmmwe coaumEuowcH msu mucommum m.c muswwm INFORHATION HEASURES BROADCISY 99999999049999999 9999999999999999 9999999999999999. 0 0 0 0 0 0 0 0 0 0 0 99999999 I 9.999999. 999999999NID~NN99 9—00-00-0—0—09NHNVDN‘vN99 9909009097~th~7~99 0000000000000000 9 99 9999999999999999 96.199999999999999 9h9999999~999h99 0000000 00000000 9 99999901 999 99 9m99-0999N9N99—099 emoonooomomcocco 9999999999999999 0000000000000000 9 99'999 9 99 99 999999990099990‘99 99999999N99C9999 9C999999N9999999 0000000000000000 9 999999 I 9 9 99 99999999N999NQ99 99999999519999999 9099999999999999 0000000000000000 9 999999 999 99 9999999999999999 90999999999990-099 9099999999999999 0000000 0 000000 9 999999. 9999 99 90-099U‘N0-00-090d0-u-00-0U'MD9 99999000-00-09-u00-uuo‘ho 9'799999999999999 0000000000000000 9 990-. Ill 9 909961999099999—‘9 owocwocanoccocmo 9999999959999999 0000000000000000 9 99 999 99999 9 C \D #9999019999999990-09 09999999999999999 09.99999909999999 0000000000000000 9 99 999 99999 9 ll :9999N999N99999F9 99999N999N99999C9 99.99999999999999 20000000000000000 I 99 999 99999 9 acoownccoc¢0ncce eooowmconnnwmho 9999Mn9h90‘999'm9 0000000000000000 9999 out 9 "9999999019999999 M9999999N9999999 99999999999999999 0.000000000000000 999999 9999999 99999999909999999 “99999999009999999 “9999999999999999 0000000000000000 U9 999999 9999999 (0 9 9999099999999999 99999909999999999 U9CHNWNNN9999999 “0000000000000000 99 9999999 p 0.9999999999999999 99999999999999999 89999999999999999 #0000000000000000 29999999999999999 u 118 99999999N9999999 9999999999999999 9999999919999999 0 0 0 0 0 0 0 99999999 .9999999 99999999N9N99999 9999999999999999 9999999909999999 0000000000000000 99999999 99 99999999900999.099 9999999999999999 99999999 999990-099 0 00000000000000 99999999 999 99 99999999990199999 99990‘99999999999 9999999999999999 0000000000000000 9999 999 9 99 99 99999999999'09999 9999999999999999 9999999999999999 0000000000000000 99999999 9 9 99 999999999999N999 9999999999990‘N99 9999999999999099 0000000000000000 99999999 999 99 9999999999999999 9999999999999999 9999999999999999 0 000 0000000000 9999999999999 99 999990099999990009 9999N—099—09999nh9 90-0999—0999999990-09 0000000000000000 9 99 99 9999 9 99999999999999999 0-09999999999999999 99999999999999999 90000000000000000 09999 999 99999 9 9999999999999999 ”99999999019999999 :9999999999999999 ¢0000000000000000 99999 999 99999 9 Z ”99999999999990‘9 9999999999999999 “9999999999999'09 0000000000000000 999 999 99999 9 999999019999999'09 99999Nnc9999flh99 U99999N99999990-0H9 90000000000000000 99999 999 9 8 99999999999999999 U9999999999999999 90.999999999999999 00000000 0000000 00-09999999 .9999999 U > ‘9999999999999999 9999999999999999 29999999999999999 00000000000000000 0199999999 9999999 .— 9 t9999999999999999 89999999999999999 99999999999999999 01.0000000000000000 8999 9 9999999 H 99999999999999999 ‘9999999999999999 :9999999999999999 0.0000000000000000 99999999999999999 9 9999999999999999 9999999999999999 9999999999999999 0000000000000000 99999999 9999999 9999999999999999 9999999999999999 9999999999999999 00.0000000000000 99999999 9 99999 9999999999999N99 99999999999990-099 99999999—0N999N99 0000000000000000 99999999 999 99 9999N99999V~99999 9999099999999999 9999999999fl99999 0000000000000... 9999 99999 99999 999999999997-9999 99999999999009999 999999999990-09999 0000000000000000 999999999 9 9999 9999999999999999 9999999999999999 999999999999‘N99 0000000000000000 999999999999 99 9999999999999999 9999999999999999 9999999999999999 0000000000000000 9999999999999 99 oneenhcenneococho 9n990999h99999~9 emcee—99099999019 0000000000000000 9 99 99 9999 9 9999999999999999 9999999999999999 9999999999999999 0 0000000000000 99999999 9999999 9 99999999999999999 97.999999999999999 9999999999999990-‘9 00000000000000000 9999999999999 9 II 999990-09999990‘999 99999999999999999 xcoooano—cmeooonwo 90000000000000000 999999 999 9 ”99999999999999 9999999999999999 9999999999999999 0000000000000000 999999999999999 9999999999999999 99999999999999999 99999999999999999 9000000 000000000. 29999999999999999 9 “9999999999999999 99999999999999999 9999999999999999 10000000000000000 99999999999999999 0-0 ID 99999999999999999 “9999999999999999 99999999999999999 ”0000000000000000 89999999999999999 9999999999999999 99999999N9999999 9999999999999999 0 0 0 0 0 0 0 0 99999999 .9999999 9999999GI~NIONN~99 9040-!0-0040-09NU‘NFNNN99 990999909f~hhhh~99 0000000000000000 9 99 9999999999999099 9N999999lfl9999999 9799999919999999 0 0 0 0 0 0 0 0 0 0 9 .9999990: .9990-099 9n99~999~90~99u99 9N99~D999N9~99999 9D999999f~9h99999 0000000000000000 9 99 999 9 99 99 999999990509990‘99 9Q999999N9999|fl99 9.99999999999999 0000000000000000 9 999999 9 9 99 99999999019990.0099 90999999N999—0Q99 acooeooov~ooov~v~eo 0000000000000000 9 999999 999 99 9999999999999599 9999999999999999 9.99999999999999 0000000000000000 9 999999 9999 99 9099N0~~nmnnm¢9 9999m0~~~m¢40uu7~09 9D9990990‘9999F99 0.00.00.00.00... 9 990- 0-0 9 9999(‘999999999—09 9999N999n9999999 9099999959999999 0000000000000000 9 99 999 99999 9 99990-09999999990-09 9099999999999999 9999999999999999 0000000000000000 99 99 999 99999 9 m 9 99999N999N9999999 .n999N999N999990-09 9.99999999999999 0000000000000000 99 999 9999999 ll 8 39999N¢N0~thtuu99 Ooeeewnooonnn—moa zaooospoommmmobbo 00.0000000000000 999° n 9 99999999019999999 h9999999~9999999 9C999999h9999999 00000000000000 999999 9999999 U 99999999999999999 99m999999~9999999 89999999999999999 0000000000000000 99 999999 9999999 U 0. 9999999999999999 99909909999999999 99.9NNDNNN9999999 ~0000000000000000 0.. 9999999 9 9 99999999999999999 99999999999999999 "9999999999999999 30000000000000000 99999999999999999 U Figure 4.9 (cont'd.) IIFOIHAIION HEASURES RELI‘AYION 09999900999999999 9999909999999999 noonwoo—oomaooo 0.00.00.00.00000 9999 9 99 9999 9999 999999999999 0.0999999999099999 9999 999999999999 000.000.0000.... 99999999 I 99 9999M99P~~999h99 999—09999049990009 ooonuccomooo—ono 000.00000..000.0 999I I 99 999 9 \ 99900999999-09 9999 999—N9999OCNF999 9995099999050‘00999 00.000.00.000... 999 9 I 9 99 99999909904999999 999999—099990—061999 999999999990004999 00....000000.000 9999 9 9 I 9 99 9999999~999NP~9N9 9999999999990‘9‘0‘9 99999999999'ON999 000.00.000.00... 9999999 99 I 9 999N99IDO99999999 9990-0999999999999 9999999099999999 000.000.0000.... 999 99 99999 I 99 99.399099909999059 99999099999999609 9.0999(099999990'009 0.00.00.00.00... 9 99 99 9999I I 9 99999999999-09999 99999999990999, 99999995999N9F9n 00.00.000.000... 999 99I 9 9 n 9 999t999~99999n999 w-OU‘99999c-09\D!~ 9950-09") 0.0909999N9N99nh9—0 0.0.0.000.0.0000 009 9 9 99 0- II 9999009999901999999 ‘999'999090-00‘99999 aoomnooonosocecna x0000 000000000000 I 9 9 I 999 9 9999 9199999913999 9999 99.099999‘990 9999 9999999999 0000 000.000.0000 9999 I I I 999I I 9999 099990999999 00999 9999959991099 “.999 999999991!) N99 Q0000 000.0.0000000 O 999 999 99 2 x9909 9999999990-099 “9999 99999NN99999 ‘9999 999999900009. 0000 00000000000. U99 I cocoa N9 VI 9 509999999999909999 ‘9999 999999999999 99999 999999990999 ”0000000000000... 9999 9 999 p “99009999999900.099 9”".99999999Qm99 ‘M'Iu09 99999990009009 0-0000000000000000 8 9909909900 9 U Atxou'AVE. 1fl19 9‘9999990—9N9999 9N9DflNIVCID—i9—0n999 9999999999999999 000000000000.00. NnD-nc‘fl’OOCON—99wb fluonu‘ON—nwnO—ano 9999999999999999 0......00.0.0.00 9990‘Cd—nflfl‘hm9huvfl oo—nccmcnnnuN—oooo 9999999999999999 0000000000000... 99 99090099961909.09—0 ocwmoonnwnouuncn 9999999999999999 000.000.00..000. 99 999.09000n—0h9909 oo—ucncoo—aowonnoo 9999999999999999 0000.0000000000. 99 99—Onnfihflhhnuc9d oomnnwncuoo—anuoo 9999999999999999 0.000.0..00.0.00 99 aooouonooowhwhnn ddd9NNHFNu9dNNN9 9999999999999999 0.0...00..0....0 «amocooonwanOAnN oonwuocmnno—ann 9999999999999999 0000000000000... 9 “OFOOflNnNOOU‘NO‘flfld O90n99nONan-‘NIDC‘DO N~999999999999999 9.000000000000000 0 NO9CdNNfiN-0Nn9h90‘ unwnonuuvnonmmncu 29999999999999999 «00.000.000.00... 9 8 ”OdONFNNNOdQFdIIVD 9nOdN—00h9fld99h'9 "999999999999999 0000.00...0.0000 999999909unn099h mnccuuwnhnNnA—Ae Ud999999999999999 90000000000000... 9 8 90.40900019000thde U 90-09049N0-00-0 onnc‘noomn L9999999999999999 00.0000...0.0000 moonuoonoo—m00 ONOnNuOOuOCOFOnO 9999999999999999 .00....00000000. 99.901999999009999” ‘90'099999999904'00‘9 9999999999999d999 0—0000000000000000 9 9 FNNN9~99IOO~DFONOIDfl 9~NN~ON99NnCnIflFD I~9990I9903999999I~I~ 00.00. 000000000 NNNNNNNNNNNNNNNN ohNhon—coocnacofl 99999990-00-09'5NU-9‘DID hphthhuoohhhhp~ 0000000000000... ---‘-‘ ‘ ‘..‘.NNN 9999m9¢nn9uflu90 Nastcwnhnwncawon 9999999999999999 “000.00.000.00... A.A.A A A A A. - ‘v-‘v ‘— 99999CI~OFCN9999C ~999M9~999M999 9F9hfih999990‘9999 0000000000000... A.AAAA A AA.A A V—‘--“ euheonhocnnhunou ~me~~n~uu~¢ewh°n DFQDFFFOFOFOONOh 00000000M00000000 «m :1 :. z u - eoooncnooucchc—a unuoo¢ooo~noooom QFOFFFFOFOFFOOON 0000000000000... «wwuwwuwwuwwuwuw knouwhnoaonooonn ewohwowofiownhncn nhohhhoocooooooh 0000000000000... -- w v v w' v v—vv Dmcwono—«noouooo omowhownunaowcom DFDOthnooNh-hamh w0000000.0.0.0000 AA A AA.A A -- v W“ v‘vv v OOFufluOV-ODOOOO'IO ~99u990h99N0-‘009N 9999F099999999h9 00.000.00.000... ‘ vvv v w—v‘v omoohcnmwoouuhoo mowwnnnuowcoouam choohohohohhhnoo W0000000000000000 A A A.A A A.A.A A. “““vv w-v‘vvv O OOnONOODNNQnNOO—ufl Dunn—nonowoccneuw ODFDOFOOOODQDOOQQ ...“...W'°' AA A.A A A.A II humouonaohoeo N—I tdnwdodfiuOuhOOOO—o ‘QFOQFMOOOMFFFQ o...000.0000000.. 8‘ - - v-vvvv nunmov-o—«owccano—c NFHOhmcv-u-«DCOCDO ”OFFOQDOOOOOOFP- 0.000W00.00.0000. A‘A A _ vvv v v v .- vv' ‘ v-v‘v OhNnOflFNOOM99NO UNOanCnhhnCFOQ 9|” 9%99999999MFFNF 000000M00000.000.0 c UOOnuduunfiOOthtn grhnhhhhhhnhhwoon hhohhhhhhhhhhohh 2.00.0000”00000000 on“ ......... - 23.--: :I. CQU‘OQWNVIQU‘NNUIU‘N In“. 90*” ”VWInflv-ONQDQC’WU'IN 999999999999999'5'. “000.00.000.00... 120 ace.— acco— cocoa oecou moo. cccou eao.~ two. :69." Oct. moo. ecu." acco— cocoa coac— woo. acco— cocoa 90°.“ 99°.“ mwmo ecu-n ocean one.— ooo.— acac— Nk MMDHUHm ace." coco— ace.— ooeo— 999-n ace.— 9900« can." cocoa cocoa cocoa ocean one.” cocoa coo.“ con." :99." cue.— cooo cocoa ace.“ can." can." cocoa ecu." cocoa ocea— aecon cocoa cocoa o¢0o canon ocean cocoa cocoa canon canon oooou cocoa cocoa cocoa cocoa can." cocoa cocoa cocoa coco— cocoa ace.— cocoa coco— ocean ooo.— can.“ con.— coco— cocoa coco— use.— see.“ canon coco— acco— cocoa econ— ace-n coo.— coo-u cocoa cocoa eeo.~ coco— cocoa ecu-u canon cocoa ooo." 0&0. cocoa nmho can." cocoa cocoa uhwo ecoou coo. cocoa ace.— ace.— canon caco— can." ago.“ ace-u ago-u ecu-u ecu-n ace.— canon occa— coco— cocoa one." see.“ ace." mom. ace.“ cocoa who. coco— ooo." ooo." use." :99." ace.— coo-u coo-u coo-u ocean e oeoou 99:.— canon ace-u ooo.— cooou a one." 99:." ago.“ 20 mama may mom mzmoz mm=mwvcfi mcu mucmmmua HH.¢ muawfim BROAOCISY INFORHAYION HEASUIES 66666666-06666666 @6666. "666666666 66666—06666666666 00.00.000.000... 6 I 66 6666 60666666$NIDNN|DO6 6h—lfi-«d6NraNrDNN666 6~~D¢~006¢6P~r~r~v~~66 000.000...00000. 6 6 66 666660466606660—‘6 6N6~CO666¢56666~D6 666NNN666N666FO6 ......0......... 6 6 66'! 666 6 omecoommmwoo—oa 6N6~0~66f~fi6|06~666 6D6Fh66~7~6|fl~~666 0000......000... 6 66 606666F6M6nhl‘66 606666—06M6chm66 6'6606666666N666 ......0......... 6 66 6 6 66 6666666U‘N66HNC66 6066666fl~666lfl666 6.666660666036066 0000.. 00.0000... 6 66666 66 6 666666I~M6666666 666—66601166666—066 6C6h66|fl~®6666v~66 ...... ......0... 6 6 66 6666 66 60.6660: ~40~~dcflb¢6 66666.4 Ma‘s-“Dd—law-6 6'36666 amooeoowho ...... ...-...... 6 66.! .IO 6 66600606 6mrF6QOOd-I 666nN6 666'6—‘6N6N 606666634601666—06—0 ...... .....0.... 6 6 66 6066—6 "6666h6u6 066606 *NN66—0666 0.0!)666 ““66666—0 00. NIDOIOON66IDNO 666666 .CO6NN666N6666606 6.06666N6nd66666 00.00.000.000... 666 6 II 8 K6666Nfl¢0~0¢06¢06 66666016600666wa 86666hn6hc~v~c~a~ccmn 0000......000000 6666 d 60666666N066DO66 66666666NN660|D66 “0660666hd66fln66 ..........0..0.. 66 666 66 U 66666666606666N6F 66W~D66666N|DNM6N66 266666666DNNCCO66 000.000.0000.... 66 66666 6 U 6 66.066666666675666 66666606666666666 6606N66m~6660666 ‘00....0000000000 66 66 666 p 66h666666666h-NM6 666.66666m660-0666 66.1666666a66'00—06 h................ z 66666a6 6 U 122 N6666N-06N66C6666 66666~n6666m6666 D6666. 66—‘66-‘6666 66666666N6N66066 6666666606666066 6—0666666. 6666—066 .............0.. 6 666666 66 666066660616660-166 ooomn—ooocooOOhwo 666~dN6666666u66 000.000.00.00... 666 66 666 6 66666666660166666 66666660066666666 6666666666666666 ......0......... 666 6 6 66 66666666666dh666 66666666604603.0666 6666666666666666 0000000000000... 6666 6 6 6 66 66666666666666—06 66666666666NU‘N66 6666666666666666 00.000.000.00... 6666666 66 6 6666666666666666 666666NC66666666 6666666666666666 0......0.....0.. 666 66 66666 66 6666066666666Nn6 6666N—06666666nh6 6d666~66666666d6 ................ 6 66 6666666 6 6 u666—0666u6660‘6fl66 fi666666606|fl6~666fl 66666666N6lfl666¢6~ ................. 666 66 "6666666666666666 66606666d6fl666n6~ 60‘666666666666fl16!~ 6................ z 6 6 6 6 06666666606666.06 666d6666666666ln6 N66d66666fl6666—06 0.0.00.000000000 6 66 666 6 666666N6666666d6 A66666NnC6666Nh6n U66666N6666666‘d—O ’...........00... (6666 6666 v W666V-66666666666 6h66666666n666666 6666666666666N666 z................ 666 666 66 66 U fi66h6666666666~60 66.466666666660066 86666666666666666 6................ ~66 66666 '06 .— ‘ 66666666666666666 66666666666666666 66666666666666666 $000.0.0000000000 8666 6 66 666 F. 66666666666601.6066 CHNP6666666606666 6¢d666666666fl6666 h................ 2 66666666 6 0.666666666666666 66666666666066“ 0.666666666666666 0.00.00.00.00000. 6666 6 66 6666 6.066666666666666 6N666666W6666d66 6666666666666066 0.00.00.00.00... 6 666666 6 66 66 0 66666066666666" 66666666C|n666~0~6 666-«H.466—N666N66 ......0......... 666 66 666 6 6666666666~6N666 666666666666N666 6666666666666666 0000.00.00.00... 6666666 66 6 666 666666666d666666 6666666666666666 6666666666666666 0000.00.00.00... 666666666 6 666 6666666n6666h0—16 66666666666N67~66 6666666N6666—0N66 ..............0. 6666666 666 666666.666666666 666666.666666666 6666666666666666 00.00.000.000... 666666 66666 66 6666666666666666 66666666666666—16 66666666666666016 0.00.00.00.00... 6 66 6666666 6 6666666666666C6V~ 6666666666666666 6666666666666N66 0.00.00.00.00... 666 666 6 6 6 6 6666666660666666 6666666W6N666N6. ”666666666666-06N 000.000.00.00... 6 6666 6 666 6 O “6660-.66666—0666666 CM66N666ID66666666 6660-.0-066666666660-‘6 00000000000000... 6 666 6 6666 6 ”66666d6066660h00 866666n606666666h 66666666.!66666666 o................ 666666 6666 66666666666666” uoocmeooowoocnoo ”666H6666d66d666 000.000.0000.... 666 6666 66 66 660666666V~66666h 666666666666660‘60 66666666666666666 6......00........ 266 666666 666 6 ¢ 66666666666666666 66666666666666666 6666666666666666 2....000000...0.. 66666666666666666 .4 6 666666666666N6N66 U6IDN666666660‘6UI66 6‘666666666666666 ”0000.00.00.00... h. 66666666 6 66 6 123 cue-u cocoa ace.— coco— ocean ooo." once" ceca— ocean cocoa canon ocean eeoon acco— cocoa :59.— can.« cocoa ooo.— cue.“ cocoa cow. ocean wow. wow. ceca— cocoa ecu." ocoou acac— coo-n ocaou .mEuo: coHumEuomcw mcu mmvsfiucfi 3o: usa muswwm mo unmuao wan mummamu NH.¢ muswfim Nflhfl wk MMDHUHL zo mAM mmh mom mzmoz mmsm p (A*) (62¢) a a 128 K+1 K p (A+) < P (A+) (62d) a a now if p (AIA*) = P (AIA+) then we have ia ia ‘ K K+1 n (A) = n (A) and the RLP remains at a fixed point at node i in Spite of the received broadcast at neighbor node a. This is an unlikely event. In the more general case of (61) where there are several A+ in (62) it becomes much more difficult to analyze the linear combinations of (61), yet equality is even more unlikely. In conclusion, to the extent which we can define the behavior of (61) is the extent to which we can say that a broadcast reception by a node moves the RLP away from a case 1 fixed point for the nodes in the relaxation neighborhood. Page [16] has further shown that the change must be sufficient to change the Eigenvectors of the governing matrix to obtain a change in the fixed point behavior. The governing matrix here is the matrix Q of the Q(A) for all labels‘A (contribution of the relaxation neighborhood). Hopefully the movement will be sufficient and towards an unambiguous labeling. If we consider a broadcast received at node i only and not at any neighbors we can write (58) following (59): K+1 q (A) = P (A) Con(A) (63) i A i 129 since there has been no change in any of the neighbors contributions. We are left in an identical position in terms of analyzing the linear combination of (63) as we were for (59). There exists the remote possibility that the broadcast will not change the fixed point. Let us assume there is a change away from the case 1 fixed point. If the change is sufficient, the iterations will move the RLP towards a new, and hopefully unambigious, fixed point. If not, the iterations will simply return the RLP to the same fixed point. The situation of the reception of multiple label broadcasts is even harder to analyze because of the uncertain nature of the experience matrices for these broadcasts. We cannot state (62c) quite so cleanly as there may be several A* s which behave so. This in turn further complicates the analysis of (61). With a no-information fixed point the unbiased RLP should remain at the case 1 fixed point. This is the situation where there is no information in the picture at all, each label being equally probable. In this picture there is no unique labeling in existence since there is nothing to label. It should be noted that the broadcast system will not broadcast any label here, as described in section III.2.l. Thus the "Correct Labeling” will be maintained. V. MOTION PREDICTION v.1. MOTIVATION The behavior of an ARLP noted in section III.3.3 and Figure 3.6 has an unexpected redeeming application. The property that allows an ARLP to create an non-zero probability for a label that had zero probability caused line extensions and noise propagation. When motion is present in a sequence of pictures the ARLP can utilize this property to predict the position of the moving object in the next picture in sequence. In other words, the result of an iteration on picture ”i" can be used to predict the position of objects in, and hence the labeling of, picture 'i+1”. The inverse of the prediction mechanism models the removal of the moving object from its present position. v.2. DEFINITIONS V.2.1. Experience Matrices Two types of experience matrices are required to transform a picture with moving objects into a model for the next picture in sequence. These are the "create" and the ”remove” matrices. The create matrix is used when a node receives a broadcast of a label that describes an object in motion. The matrix restructures the label set at that node so the object will appear at that position in the next iteration. The matrix is a kxk column stochastic matrix as described in section II.3. The row of the matrix 130 131 corresponding to the received label will contain ones in the columns of labels that describe background objects which the moving object will hide from view, and zeroes for foreground objects which hide the moving object. The remove matrix restores the label probability of background objects previously occluded. It is used when a broadcast of a label for a departing object is received at the node presently containing the object. The row of the matrix corresponding to the broadcasting label A is all zeroes, effectively setting P (A) = 0.0. The corresponding column details which 1 background labels will receive the probability mass formerly belonging to the moving object. The diagonal elements are all 1's in the other matrix columns. Again the remove matrix is kxk column stochastic. The restoration of background labels by the remove matrix is by no means a clear cut issue. It is here that the local consistency properties of the RLP are desired. Once an initial labeling of the region is accomplished, the RLP will reconcile small difficulties. V.2.2. Broadcast Patterns Two distinct broadcasts must be made as opposed to the single label broadcast of the previous definition. The first is a broadcast of the label in the direction 132 of the moving object. This broadcast, when received, will use an appropriate create matrix in the update calculations (12) and (13) so as to establish the moving object in its correct position. The second broadcast of the label is to the node containing the object. The remove matrix will be used in this case. The actual broadcasting unit will be a knowledge source concerned with trajectories and curve fitting rather than the node itself. This is necessary due to problems of occlusion which may cause the moving object to temporarily vanish. Under the old definitions such an occluded object could never reappear. (This effect parallels an infant who equates sight with existence.) v.3. EXAMPLE Consider the example of a simple scene involving four labels: an airplane, sky, ground and clouds as pictured in Figure 5.1. For the sake of simplicity, let us assume that the plane is traveling in a horizontal trajectory. The broadcast pattern is given in Figure 5.2. The circles show nodes which receive a type 1 broadcast and using a create matrix. Squares show a type 2 broadcast and remove matrix. Example experience matrices are given in Figure 5.3. The broadcast update procedes as in (12) and (13). The relaxation cycle then restores the local consistency of returning background labels. 133 W A SIMPLE SCENE WITH A MOVING OBJECT A IPLANE 1 AZ-SKY A3'GROUND AA'CLOUD 0 Those nodes receiving a type 1 broadcast D Those nodes receiving a type 2 broadcast Figure 5.2 NODES RECEIVING BROADCASTS 134 P S G C I__ __ l l l l .8 | FIG. 5.3a A create matrix E[p1=laaaa|s l l I 0 0 0 0 IS for a cloud as a background I 0 0 0 .2 I I__ .__| label. P S G C I__ __I I l l l .2 IP FIG. 5.3b A create matrix B[p]=loeoa|s l 2 I 0 0 0 0 IG for a cloud as a foreground I 0 fl 0 .8 IC I__ __I object. P S G C I__ __l _ l 0 0 0 0 IP FIG. 5.3c A remove matrix E[P ] = l.75 l 0 0 IS for sky and ground as the 2 I.25 9 l D IG background objects that I 6 0 a 1 IC regain visibility. I__ __I P = Plane S = Sky G =Ground C = Cloud Figure 5.3 EXAMPLE EXPERIENCE MATRICES 135 v.4. DISCUSSION V.4.l. Occlusion The presence of an object like a cloud raises several interesting issues about the level of world knowledge needed by a motion detection system. Some depth or distance information is needed for each object in order to determine whether the plane will pass in front of or behind (or in) the clouds. Once this is known the correct experience matrix can be chosen. The matrix in Figure 5.3a is an example of the cloud as a background object while allowing for a small possibility that the cloud may occlude the plane (the .2 in row 4 column 4). Figure 5.3b is the example for the cloud as a foreground object, this time with a small possibility of the plane peeking through the clouds. The cloud may completely vanish behind the plane just as the sky does or vice versa. V.4.2. Expanded Label Sets Additional labels with special semantic properties can be of use here. For example: two varieties of cloud labels, one designating an occluding cloud and a second a background cloud. The choice is then in which label to support rather than in how much to support a single label. The same situation exists with the ground label. We can differentiate level ground from occluding 136 mountains and from background mountains. The plane can then fly in front of or behind the mountains and land on the level ground. Landing disables the broadcast function as the plane is no longer moving. In each case the particular experience matrix needed is requested in the broadcast mechanism. V.4.3. Motion Prediction and Curve Fitting Broadcasts are controlled by the knowledge source in charge of the trajectory of the moving object. This trajectory is continuously updated by a curve fitting routine. Actual positions are compared to predicted positions for fit refinements or to reflect a change in course. The knowledge source must have a good understanding of kinematics. Three dimensional trajectories involve more than simple translation. Translational information only positions the broadcast pattern. The broadcasting unit must include rotation and scale information in chosing the size and shape of the broadcast pattern. A plane that curves and flies off into the distance is a perfect example. If there is uncertainty in the prediction mechanism as to the next position, several possible positions may be selected. Multiple type one broadcasts are sent, one to each of the various 137 possible positions. A strength factor is employed to reflect the certainty of the predicted positions. The resulting multiple images are resolved with the labeling of the next picture in the sequence. The new trajectory is then entered into the curve fitting routine. V.4.4. Multiple Label Reception A large, slow moving or partially stationary object may generate type one and type two broadcast patterns which overlap. Hence a node receives contradictory experience which requires both the re-creation and removal of the object. It is intuitively clear that the type one broadcast must take precedence. The object does not vanish but rather just moves along. The type two broadcast may be ignored, or in special cases, modify the type one matrix. Reception of two type one broadcasts of different labels presents a slightly different situation. The solution is semantically dependent on the labels involved. A moving cloud can cause a broadcast as well as a plane. The foreground and background information in this case will be the deciding factor as to which object will remain visible. Both examples are cases where a special multiple label experience matrix is a necessity. Averaging the single case matrices can not be expected to give the desired result. VI. CONCLUSION AND FUTURE PROBLEMS VI.1. SUMMARY AND CONCLUSION This thesis has examined relaxation labeling systems for computer vision. The idea of augmenting the homogeneous relaxation system of Zucker [7,8] with the broadcast processes of Page [11] has been studied. The definitions of the brodcast process have been further revised and tested on a series of simple line drawings. This Augmented Relaxation Labeling Processor, (ARLP), is shown to give a more correct labeling in hard to label or ambiguous areas of the picture. The added power of the ARLP is due to the world knowledge available about the structure and interrelationships of the objects in the picture. This knowledge is embodied in the experience matrices (a form of pairwise label compatability matrices.) The broadcast process is also modeled as a relaxation process over the entire picture. To accomplish this, an experience matrix must be defined for every label in the picture and every node must receive a broadcast. The relaxation process is no longer a homogeneous one since the broadcasts use the label dependent experience matrices and label dependent broadcasting patterns in every neighborhood contribution computation. The resulting processor is termed a Dynamic Relaxation Labeling Processor, (DRLP). The DRLP is likewise tested on simple line drawings and 138 139 shown to be superior to both the ARLP and RLP, as well as significantly faster per iteration. The neighborhood contribution process is modeled using Shannon Information Theory. The neighbor labelings serve as the channel input, the compatability and experience matrices model the channel, and the channel output is the neighborhood contribution. The relaxation methods are the examined in the light of the measures describing the channel model. The RLP is found to have an unacceptably high dispersion while the DRLP becomes a deterministic channel with zero dispersion for strong broadcasts. The other standard measures of mutual information, entropy drop and equivocation also favor the DRLP. A final section on motion prediction by broadcasting was presented. The developement of two types of experience matrices, the create and remove matrices, facilitate this task. VI.2. FUTURE PROBLEMS VI.2.l. Convergence and Optimality One important topic in the study of relaxation systems is the convergence properties of the system. This thesis has only scratched the surface of convergence properties for augmented relaxation systems. The initial direction in section IV.4 can be followed. The convergence to a fixed point depends on the broadcast patterns and strengths and the number of 140 received broadcasts. This further complicates any analysis however. For dynamic relaxation systems, much of the work already done can apply when suitable modifications are made for the variability in the broadcast neighborhoods and compatabilities versus the homogeneous constraints in the relaxation processor. This is not easy as one major reason for the introduction of the homogeneity requirements was to simplify the mathematics of the descriptions. Even if a mathematical model is difficult, several convergence measures are potentially available. A measure of convergence can be directly based on the information measures described in section IV.3, especially the mutual information and entropy drop measures. All that is needed is a method of evaluating the numbers that result across a picture set. Another, more predictive measure can be developed from the broadcast strengths. As the strengths rise, the picture converges more quickly. VI.2.2. On Experience Matrices and Compatabilities VI.2.2.1. Optimality Several avenues exist for the definition of an optimal relaxation system. A useful area to optimize is the compatability and experience matrices. The channel measures of dispersion and equivocation are obvious choices here. An optimal channel has zero 141 dispersion and equivocation. So should an optimal experience or compatability matrix. Whenever the channel capacity can be computed, it also is a useful statistic. Another approach would be to look at labeling error statistics or to look at the convergence statistics above. A experience or compatability matrix producing lowest error or fastest convergence, or both, is describable as optimum. IV.2.2.2. Defining and Training Building experience matricies is only a simple task for simple pictures. One key is to have the experience as concentrated on a single label as possible. The field of artificial intelligence has a wealth of avenues for the specification of knowledge and experience from training samples to rote, statistical or analytical abstractions for learning, to procedure based knowledge sources. Any and all of these can be appropriate. VI.2.3. BroadCast Parameters VI.2.3.l. Language Aspects One area of Page's original definitions that has not been devloped is the use of two dimensional grammars for the specification of broadcasting patterns. The various languages describable and their attendant resolving power is a wide open area for research. For example, is a context sensitive language any more (or less) powerful or optimal or sensitive 142 than a context free language. A second research topic is the description of a label algebra incorporating the broadcast grammars to describe the updating process. The operations of the algebra on the labels describe the interactions from the broadcasts and the resulting labelings. Such a model allows the discussion of algorithm behavior in the abstract. The resulting properties describe the system and may even hold a clue to the convergence question. Such algebras can describe both the regular and motion prediction systems. VI.2.3.2. Thresholds Much work can be done in the area of thresholds for broadcasting and for broadcast reception. The major work is to specify various thresholds and the picture effects that result. Where exactly should the receiving threshold be set is an example. VI.2.3.3. Labels The depth of picture description depends on the breadth of the label set available. For line processors, the label set from Waltz [2] should be included rather than a simple intersection label as was done for the DRLP. Additional labels require additional experience, however and the resulting combinational explosion must be dealt with. Hopefully the simplification that resulted from the label constraints in Waltz's work will carry over here in the number of 143 special purpose experience matrices needed. A different idea is that of having broadcast permeable and broadcast reflective labels. In a sense a high receiving threshold is similar to a permeable label. The broadcast has no effect, or just passes by. A reflective label is interesting but would play havoc with most descriptive models. IV.2.4. Hierarchies A major area for future work is to expand the ARLP and DRLP to a multi-level hierarchy with descriptive abstraction such as Minsky's frames. Such a hierarchical description allows for a greater variety of top down controllable broadcasts. A test of the broadcast algorithm as a inter-level communication device is also testable then. Such a system allows the algorithms to be tested on more complex pictures. VI.2.5. Chess by Broadcasting An interesting application of the broadcast paradigm is the determination of the squares on a chess board which can be attacked by a pawn or piece. To see this, simply consider Figure 3.2 to be the partial broadcast definition of a rook or bishop. The marked (*) squares show those squares to which the piece can move in one turn. These marked squares can the broadcast for position prediction at the next lookahead ply- [l] [2] [3] [4] [5] [6] [7] [8] [9] [10] BIBLIOGRAPHY "Computer Vision: A Literature Survey”, Kuschel, Stephen A. unpublished paper, May 1978 "Generating Semantic Descriptions from Drawings of Scenes with Shadows", Waltz, D. MIT Thesis, 1972, also available in The Psychology of Computer Vision, P. Winston, Ed. pp.l9—9l McGraw Hill, 1976 "The Consistent Labeling Problem", Haralick, R. M. and Shapiro, L. G. unpublished paper, Jan 1978 "Scene Analysis, Homomorphisms and Arrangements" Haralick, R. M. in Machine Vision, Academic Press 1978 "Scene Matching Problems", Haralick, R. M. unpublished paper, May 1978 "Scene Labeling by Relaxation Operation", Rosenfeld, A., Hummel, R. and Zucker, 8. IEEE Transactions on Systems, Man and Cybernetics Vol. SMC-6, No. 6 p. 420-433 (June 1977) "Analysis of Probabilistic Relaxation Processes”, Zucker, 8., Computer Vision and Graphics Laboratory, Department of Electrical Engineereing, McGill Univ. Montreal, Quebec TR78-3R. Also available in Proc. IEEE Conf. on Pattern Recognition and Image Processing, 1978. ‘ "A Hierarchical Relaxation System for Line Labeling and Grouping", Zucker, S. and Mohammed, J., Computer Vision and Graphics Laboratory, Department of Electrical Engineering, McGill University, Montreal, Quebec TR78—llR 1978. Also available in Proc. of the IEEE Conf. on Pattern Recognition and Image Processing, 1978. "Relaxation Processes for Scene Labeling: Convergence Speed and Stability”, Zucker, 5., Krishnamurthy, E.V. and Haar, R., IEEE Trans. on Sys. Man and Cyber. Vol. SMC-B, No. 1. (Jan. 1978) "Convergence Properties of Relaxation", Eklundh, J. and Rosenfeld, A. Computer Science Center, University of Maryland, College Park, MD. TR-70l MSC-76-23763 October 1978. 144 [ll] [12] [l3] [14] [15] [16] 145 ”A Study of Augmented Relaxation Labeling for Image Understanding”, Page, Carl V., Department of Computer Science, Michigan State University, unpublished paper October 1978 "Augmented Relaxation Labeling", Page, Carl V., and Kuschel, Stephen A., Department of Computer Science, "Symbols for the Manipulation of Natural Language", C. D. Paren; Ph.D thesis, Department of Computer Science, Michigan State University, 1852. ”The Mathematical Theory of Computation", Shannon, Claude, E, and Weaver, Warren. University of Illinois press. Urbana. 1949. "Information and Coding Theory", Ingels, Franklin, M. Intext, Scranton PA. 1971. "Strong Stability Problems for Probabalistic Machines" Carl V. Page, Information and Control Vol.15 No.6 1969 APPENDIX A COMPATABILITY MATRICES EXPERIENCE MATRICES The pi‘1 label compatabilities are given below as defined in equation (20) M .1 <1 p. O p. .1 O L) oommmmeahs Dob-DUQJMMO ODHNODHNNO . Q Q 0 0 0 . . O 0 60 H [BLD'OO‘JS JNDD MMfiwNNQHQD dqdocaoofivic’ . g 0 . . . 0 0 0 0 H maommmmmoaov mnomnnmmflc OQOHHHde-U", ........'0 ,4 HHkDCOOO-Jrnm: Q0Qf'NNNOO'3 . . Q 0 0 0 Q 0 0 0 «fleecescaom-‘a ...omOJJ-unoou GOUVCNNNDC’D . 0 0 0 . 0 0 . . . d H NNOO‘OONNNQ 005.4:J-Mavoga ooafldddOflO . . . . . 0 . . .v: ommmonommra oomnmmNNJ” HHHDoooHfiG . 0 0 0 0 0 . . . o r! OR NEIGHBOR “ koodeHJmDD mowN9040°O ALU >oomMHdJIn°o ommNoOJOGO fiNNdODDUq—UOD H . 0 . 0 o 0 0 C 0 0 a. 61-! 146 HHDHAfiOu-IIHO admooohfimo mecmmmmmo ooccpflv-IHHHC 0 . 0 0 . 0 0 . . . QQMDq-OHH\OHO ”Mt‘JcooDmnuO QDDONNNHQD . O . 0 0 . . O O . 33m¢°6mHNO \DOJ’QJ‘J‘NJ'MO Gaoudflfififlo . . . . . . ° . I 0 :JmJ'OcomflND LOQJ'IJJ‘JNJ‘NO ooooaa—aflflfi . . . . 0 ' 0 0 P ' v-i thNNNONO mmfinno©h0 fififiOQDOHo 0 g 0 . 0 0 . .5 .131 HBOR “ 2 mNNNv-Ooooooo z . . . . . . . O O 0 ,4 or O umO‘xDOJJF’J‘TU‘D mecDMOOMN-OO MfiYOHHQOQC’do “1.0.0.0.... :3 d .J < >oooo::n3m° 900900th66 fidflfiHOQDOfiC’ H . g o . 0 o 0 0 0 0 a v4 COL TOTALS 2 2 9 9 6 6 2 4 0 D NNJN‘D ORV-“0C3 .1 .1 .0 .0 .1 .1 .0 .U .1 .0 01036060306 NNNHHflflJHD fifinnflflNNHO . . 0 0 . . 0 . 0 . H QmNmJJMv-IJ'J flHJMDOmUO° ddoodflawoo . O 0 0 O 0 O 0 0‘0 .4 ”MNNMMJ‘DNU oofidooqsaocco fifiHHfis—(apflw . . . . . o 0 0 o . MMNNMMQQNQ uoflfioqmmoa fiddflflflacfio . . . 9 . . 0 . C . mQMov-JH'DU‘IO‘O 71'4Q’JP’JWI’OVGM'J fifiNNfldDOQT’ 0 . . . . 0 0 . . 0 wfififlflHw-COOQO Z..00.'0.0.. H a! D ILMMOO‘Hv-Iflflfl’a ”@00603360": Mdfificdfiflflflu w . Q 0 . 0 0 0 . . . D ...l d >MMQO‘HfiHv-(v46 oODO‘QOxDDO‘C’ fifififiofldflfiflo H . 6 0. 0 .0 0 0 0 O. . COL TOTALS NNQ3NNCHDCJ¢J OQONNNOJOMO HHHucaoNuc-Io 0 . 0 0 0 0 o 0 . 0 v4 NNO‘thLOv-LnMC) DQO‘NMMMHmo NNC'DODV'NCDD . 0 0 0 0 . Q 0 0 0 v-O ID‘DO‘Nmmdeo GOO‘O‘ooooa‘o v-Ov-Jccaocav-{lec 0 . 0 0 . o 0 0 0 . v4 O‘O‘O‘Hmmmnoo J‘JNmQG‘L‘CMNO Oofim'THv-h—(CJQO . 0 0 0 . 0 0 0 g 0 fl momdmnmnsoo J'J'Nmsrnumlsu {JOHHdv-Hcocc . 0 0 O . 0 ' 0 . O H 900mmmm “5'33 3 ¢¢Mwiuraommo GOHNNNHOQO a: 0 . . 0 . o . 0 . . o as I ukkmm'omcmno HnmUv-lv-(v-CO'UI'O'J woodfififidoflc 2......0.00 ,4 mmmqocaarso‘o spammmmcoon flHCDQOCJHv-{Hfi O 0 . 0 0 O . 0 0 . .4 ALUES FOR >mm®mocwu~a~o nummmmmmmo 5 FOR NEIGHBOR ” 5 6 .- .- PIJ VALU 147 TOTALS 3L 1) oCJLDManva-dko oohooc33mroo oOflNDov-‘NNO . 0 . 0 . 0 0 0 0 0 06 mchO‘JJ-fNC-‘D MMHmfsktoy-{QC ddflDOQQHv-{C . 0 0 0 0 0 . Q 0 0 H cmmtnd‘d‘lna‘coo nmomuhmoflo ooofldaaoflo . 0 0 0 0 0 Q . I O H fiH-Dcuoocnmo (Joann: Jae-Doc: (JOQHNNNQDO . . . o 0 . o . O 9 ~ H «flococo’nmo Uuuuu: 3606c.) ooo.-QNNNQDD . O 0 0 0 0 . O 0 . .4 NNC‘O‘OONNND \OxDNsl’J‘mOKDQ ODQHHHHOv-ID . O 0 . . 0 0 0 0 0 H oocomcoommc concmthJQ HHHQOOOdHO . Q o O 0 0 . 0 0 0 v4 commdemoD 6005064000 NNv-NDDDDHDC’ 0 . . . . 0 . . . . 6d ocmnflfiJMOO omd‘lsooJ‘sooC' Nun-466667400 0 g 0 o 0 0 0 0 0 . 6v. COLOTOTALS fidchDLOxOlN-flmo IshmtOMMmmmC’ ODDQdeHv-{O 0 0 g 0 . . . . .5 mmmoaaamao ”noncomnoo aoocNNNHOD 0 . 0 . O . . . . O H JJ'LDJiOQLfiv-INO \D‘DJ QJ‘J'NJ’I‘OO OQQQHT'HflV‘O 0 0 o 0 . 0 g Q 0 0 v4 JJmJQ‘DLfifiNO \OKD-J'uaJ-J'Nd‘mu omomafladdo O . . . 0 . . . . 0 .4 .ID HflNMNNNONu 3 ”MMfiCO‘OO'DND fifiv-(HDOOOHD of . . 0 . 0 . 0 0 .v-‘O co I UflHNy-{v-«Iv-OMKOHO HH“M@U‘[B"‘OHU wNNNv-Ioooouo Z . 0 . . . . . . 0 0 .4 (Z O ILU‘ONOQJ'JMJmD OOQMOOMNQO mfififlaogWODv-CD m . o . . . . . . 0 . D ...! d >O‘O‘IDxOJ-1'M—fmo \OOQMOQMNQO fiHHv-h-cctnaodc H . 0 . . 0 0 0 . g . a_ H COL TOTALS NNO‘O‘LOtoN4foD hrs-:Nxotorsv-AOI: «Acorn-(cacao 0 0 0 O 0 0 0 0 0 0 O‘O‘JOGQO‘JO‘D NNNfiHv-{d4fv46 fidflOHv—(NNUD 0 0 0 . O 0 . o 0 . ouomm.+4tm«—L:o fifi¢moczoomo dfiocdadmco o . 0 . 0 0 0 O . 0 .4 M-‘ONNMMOQNQ OOHniuoc‘ome fifiv-h-h-h-{oofio 0 0 0 0 0 0 0 0 0 0 fl NnNNMMOQNQ DD"! HUHO'HI’MD HHfiHHHODv-GO 0 . . 0 0 0 . 0 0 g d 7 QQM'Oflw-ILDLBCDLJ T‘lH-‘DCJMVJMv-imo fiHNNfiHODoo a: 0 0 . 0 0 0 O O . . H 6 CD I UOQNONNTJNMO mHadcu—tdfiafio w 0 0 0 0 0 0 g 0 0 0 .4 ALU >Mnomfldv4v-lao ooomoaoooo 'Jdaflodde-Ific H O . 0 O 0 0 0 0 0 0 a H 148 COL TOTALS NNmaxomw-komo ocmmmmmramo NNDDCC‘HNQQ 0 O 0 0 0 O 0 0 0 0 vi nonmrulnmNI-nao OOmO‘O‘O‘ooo‘o HHQDODde-JO 0 0 0 0 0 0 0 . o 0 mmmdmmmmmo :meaoompo OOdHHfifiooo 0 O . 0 O . O. 0 . 0 ommdmnmnoc :J'Nowon-Dmho auHflHHHooo . . 0 . . . . 0 . . aommmmo‘ahu J'JMfiGQQNNo OOHNNNHDDO 0 0 0 . O 0 0 0 . 0 «I HBCR ” 5 ushmm-oaoonwm: HmwaHHw-‘Io'o‘oc: UCOflv-{Hfificafio Z . . 0 . . g g . 0 . v4 0: D ammococdhoo NNO‘MmmNcooo MHfl'DQOuv-‘Hv-‘D w . 0 . . 0 o . g . . D (a .J 4 >mm®¢066rfl~mo KNO‘MmmNQoo fidfiaoocfidfio H . . 0 . . 0 0 0 . 0 a a 09839637939 1.0044923346 09938537609 .9509470375 1o009h923346 1.0066812174 1.0086629013 .7.9999996996 7.9999997970 .7.9999999343 8.0000009690 8.0000001920 7.9999995060 709999996996 149 EXPERIENCE MATRICES FOR ARLP IAEMQI 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 IAEHLZ .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 IAEHL3 .250 0.000 .750 0.000 0.000 .0.000 0.000 0.000 0.000 .500' .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0:000 0.000 0.000 0.000 0.000 0.900 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .290 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 .0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 .1.000 0.000 0.000 0.000 '0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.090 .875 0.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 1.000- 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0 0000 0.000 .750 0.000 0.000 0.000 0.000 0.000 .250 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 .750 0.000 0.000 0.000 0.000 0.000 .250 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .125 0.000 .400 0.000 0.000 0.000 0.000 0.000 0.060 0.000 .600 0.000 0400 0.000 0.000 0.000 0.000 0.000 0.000 .600 0.000 0.000 .400 0.000 0.000 0.000 0.000 0.000 .600 IAKHL4 .125 0.000 0.000 .875 '0.000 0.000 0.000 0.000 0.000. LABEL5 0.000 0.000 -0.000 0.000 1.000 0.000 0.000 0.000 0.000 IAEHL6 .125 9.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .8075 0.000 0.000 0.000 150 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750. 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000‘ 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 ..500 .500 0.000 0.000 0.000 0.000 0.000 1.000 0.000 ~0.ooo 0.000 0.000 0.000' 0.000 0.000 0.000 0.000 .975 0.000 0.000 .125 0.000. 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 .400 0.000 0.000 0.000 .600 0.000 0.000 0.000 0.000 .400 0.000 0.000 0.000 O 600 0.000 0.000 0.000 0.000 0.000 .400 0.000 0.000 .600 IAKBL7 .250 0.000 0.000 0.000 0.000 0.000 .750 0.000 0.000 IAKHLB .500 9 .000 0.000 0.000 0.000 0.000 0.000 .500 0.000 IAEML9 .990 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .010 0.000 .125 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 .250 0.000 0.000 0.000 0.000 0.000 .750 0.000 0.000 .990 0.000 0.000 0.000 0.000 0.000 0.000 .010 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 .990 0.000 0.000 0.000 0.000 0.000 .010 151 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 10000 0.000 0.000 0.000 0.000 .990 0.000 0.000 0.000 0.000 5.010 0.000 0.000 0.000 0.000 .250 0.000 .750 o .000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 .990 0.000 0.000 0.000 .010 -0.000 0.000 0.000 0.000 0.000 .500 .500 o .000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 .990 0.000 0.000 .010 0.000 0.000 0.000 ‘0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .990 0.000 .010~ 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .990 .010 0.000 0.000 0.0000 0.000 0.000 0.000 .400 0.000 .600 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .400 .600 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 IABHLI 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 IAEH02 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 IABEL3 .250 0.000 .750 .0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0-000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 o 500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 152 EXPERIENCE MATRICES FROM THE .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000' 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .87 0.000 0.000' .125 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 'o.ooo 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 0.000 IMHI .750 0.000 0.000 0.000 0.000 0.000 .250 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 .750 0.000 0.000 0.000 0.000 0.000 .250 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 .125 '0.000 0.000 .600 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .400 0.000 0.000 .600 0.000 0.000 0.000 0.000 0.000 0.000 .400 0.000 0.000 0.000 .600 0.000 0.000 0.000 0.000 0.000 .400 0.000 .800 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 .800 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 0.000 .800 0.000 0.000 0.000 0.000 0.000 0.000 .200 1AKHQ4 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 IABHLS 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 LMEL 6 .125 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 153 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 O .000 0.000 0.000 0.000 ..750 0.000 .250 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000' 0.000 0,000 0.000 0.000 0.000 0.000 .875 0.000 0.000 .125 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .750 0.000 .250 0.000 0.000 0.000 0.000 0.000 .600 0.000 0.000 0.000 0.000 .400 0.000 0.000 0.000 0.000 0.000 .600 0.000 0.000 0.000 .400 0.000 0.000 0.000 0.000 0.000 0.000 .600 0.000 0.000 .400 0.000 0.000 0.000 0.000 .300 0.000 0.000 0.000 0.000 0.000 .200 0.000 0.000 0.000 0.000 .800 0.000 0.000 0.000 0.000 .200 0.000 0.000 0.000 0.000 0.000 .800 0.000 0.000 0.000 .200 IAEEL .250 0.000 0.000 0.000 0.000 0.000 .750 0.000 0.000 0.000 LMEL .500 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 7 .125 0.000 0.000 0.000 0.000 ;875 0.000 0.000 0.000 8 0.000 .250 0.000 0.000 0.000 0.000 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000.0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 0.000 0.000 .875 0.000 0.000 0.000 .‘25 0.000 0.000 .975 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 LABEL 9 FOR INTERSECTIONS .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 .500 0.000 154 0.000 0.000 00.000 0.000 .250 .750 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .125 0.000 0.000 .875 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 .500 0:00 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .250 0.000 .750 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.060 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 0.000 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .600 0.000 .400 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .600 .400 0.000 0.000 0.000“ 0.000 0.000 0.000 0.000 .390 0.000 0.000 .200 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .900 0.000 .200 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .500 .500 LABEL 10 FOR BLANKS .800 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 .800 0.000. 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 0.000 .390 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 0.000 0.000 .900 0.000 0.000 0.000 0.000 0.000 .700 155 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .200 0.000 0.000 0.000 0.000 0.000 .300 0.000 0.000 0.000 .200' 0.000 0.000 0.000 0.000 0.000 0.000 .800 0.000 0.000 .200 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .800 0.000 .200 . 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 .800 .700 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 APPENDIX B DRLP PROGRAM u7l1317° 11V £.50£!! 156 0r1-1 73/73 ‘k'ICl-l' THESIS . .. . . 0 to C. . 0 ll. (.1 .s . . 0.. .s.. . 1g‘04c ... 3 1.1.‘5578 .5 1 5 i.Ls..q 0.0.. . . 1.32309 9... ....» . ...‘1 L(.A.A.7I:V . 1. .. ..c .47.. G 9 ...1 ‘507FC. 1 11. 111 4 a a 1225.....;).«......¢.:1 31.1.1.1... 1 1.1 L‘LL‘LL..LL‘ .... 5.3.3.351 c r ...1 (30.56.5560; .1101 7771777170.}. 0 u \l O I ... o \o \l \l \l o H ... o o O o o L o 1 C. ..b o .. o o 1. 9. I 7 o ... 1 1 6. 0 R1 P 1 SS 0 o A .1 .1 O ... Q. 1. ... I 0.5 0 \J \l u.- h. 0 I 0 CC I. R S ..r L... 1 o o L R 00 o .1 0 LD H 0 9 Pa. 1. o o. L .U N I ... o ...... 1 L l n. o o I .1 o 1 o .09 O L F. ... 110 U U 0 3 I \l \l 1 o I o ..o .3 ... P ...1 1:1 ... o .3 I. 1 1 P o o a. 7 o 6 tr 3 A I JXN R N7 0 .... . I 1 0 EL... . (v o .KX .1 1. L 1 1.") 1. «.9 o u. o .. o. h L V0.) A. 94.... 0 1.‘ .1 r s S v 1. I. 1‘ .l 5.? .11 .1 ...D. 0 LL .3 h. N 0N... .... SN 0 L N RA 0 I I l a ...... ... .\N N C DNn.G 0 1n. 0 I. 0 S N NL .... ... 11 0 PR U 10 A VA]! A o h V ... 1. 1.! N 5 h. o 0 A L 1. 1 k 19 s an; o I. l R IX V1. 1 '5 G 0 LS A N1 0 N CA 1 R19 0 L. 0 U E 55 1L 2 1A.. 0 o E V 01X 1. I ERQY U Al 0 l. S C U o In..." U. o 0 NS 1.5.... .1 R (1.2.8 .1 FL 9 5 l N u ‘1 V"..- o 0.! 0 c 01. 1 100 5 P NNFI 1 FRO o 0 H ... ... 0L R 1’1. lv H o 1.1 1 1.1V 3.1.0:. U 6". o 1. S P. U NB n 1. o s... o 0 1U 1. s 1. L r. 1 1 o 1. .\. a 'l 1. II 1‘ .1 5’7 (.1 n. c In. L n.” .p. M. £11.“. 11V1 0 .p ..b V .1 [L V0 (1.1 ll 0 0 1.. ILFFL .A F [NLF .1 IUII 0 I C s .1 o 1. 0'). 11 C o A... ...... U... 1 ... FINN DEN-r08 o A ...... 1 N1 ...k 0 U I .... t LU I! ..L.» .1 D 31.01. 1U :09. o L n.. 1 1 1.1 LFKI .11 D 0 .LS .3100. EU... ...U 6.0.1. o I. 1 I. U 0! two 1.5 NH. 3 o P n PRC... R .1 G10 FFNN o .1. P .r L... Ur. A o 1.? N o 1 R 0 D. .1011 Yu 0101. o n. .... 1 x... F 11 (I o a in. FISSS .1 NEDL 1O NNU o r. 0 O U V1 ...... ...-A 5U D 0 1.1.... 1 TUDL C1 335 o 1. .1 0 ... DC 3 o ....r. P o R... ....1 S .5 to... .n. L.) In 0 P L K c L O K I... c I N 0 ON H.912.) ... U NolNrn‘ o o I ... 1. 1. (I ...L...1 0 A. o o .10. 1 U U 5555 1n URSK o N V 51. )L 121.... 0.... 9. o h. 1111 L P .1.th N 91.1. o 1 ... .1 l. ... .. r ....AVA o E? H. 0 P 5.1.1.1.? l A. VVVV P SUB... o h. L n. (at L 7‘ (1.1.1... .10L 5 0 ‘5 ”51.1.1. V 1.1.1.1. 0.}! Q U 0 3. IL VFL 1. 013 R 0 R... 1. Rkk ... 6565 .1...R¢ Q 9 o O 5 L I1 A 1 (I ...! o 1 L H) o G ALCCC 1 H 00 c 1 S U ... 0.. 1 :11 U... I (II..(.I v 0 n. I TESQS 1. 1971 ... GOV-'23 c R 9.. V R.- I... a 0 I O C U IN 1 0 PK “F855 ' 0 C .... I. F. .... P O .- OVL .9. 1. o 4 FLL1 o a .10 fl. 0 .JU U I .1 L o I 1 D L \a ... \IER. \15thK3 ...Kruurb..\1ru o ... (L555 L ... .1. a...“ o h. ... 1K 1 r (a I ...... 1. 1:: ‘31. Au). R s 0 f. P 1 1 U1 .1 12L )LSVN I r... In .11P1o ...... o I. I K I Fr. P (N1 0 9.11.1 (Kn-1H7 67.0 VH 1 a ... R H H NR 0 PS! NRNLIA A...3V.1ECH(' 1.1 A. L a. o .a A H .9 1.1. D. .11... 1 1.1 1.1.0... 1. It. R ..P .1 R ... a .1 S .- SH. (F It). (fill/I LC 0 0.1 5‘ R. ... G o a 0L 0 o N H .1 L11 0 11.0 o 515 1 .651. n. ....n A G ... o o v. I... lb 1. 1 1. .. N1]! 1. 11.001‘50 ... L L .... 1 o .r ... ’V I1 ’1 I 1 1 511. s S IFFEC («0 H1 P 1 \ 0)) 1 )..:..L )(r. \I. )3 .1 \I) ) 00R {.1 1) ... v .13... F 51.. 11 I o N 1. 01.11 S 1L0 311. 1‘9 )1 1. 12 13 all 0 63 H JNKXIU c 1. ...L L 1. ...). o 1 2 o 1. ... o .. a...) S 0. 111 1 . (r 1 L15... ...... SK ..1 r1. .0...) S 3111 O’)189,I.-. 1 1 00 011.1 M. .1 III/I Do In. I... r. t o 1 101 1. N 10.1.2 .s. o I old ([01 1 o u. 91.. J VR L .06.... 1 ...! (N6... 1061 1( 4...... 61.... U6 ‘ NV\~NESO 5‘ I E n. 611-1 s (151111248011C‘Ic 0| 1‘ 1.1.1 c1 R 9:39..» 6.... 1.... P .. V .9 a...“ ... [.51. EL‘GCEit‘fiD U ...... .. IA ... .u unogwnriso <. a. .J E V o11i.nu 1vnPLL1r.EUE16.vr1..v 11. 1.: [1 n. 0"”..1‘ o ...... Jr? R L 1. 01.1.R n- IRILLIRAIDIPLRS 1 1.... IRS L1. 9 .H....h).Lh.N1.O H” I O‘KO F. POEIIPnUEn.r.RCELN U 8...: DUB. IF 1 CCCCCIDQ 11 V obd' P JFRCCbFRFNd'FVI P db €11 CH 1 c c o O O o 9 d o a a t O a 1 2 3 ‘ to. 12 9 . ... 2 Z a. I . . CCCCCCCCLC(LCCCCCCCCCCCCC(Ctr. .7CCC C. 0. C 9 (Cr. 0.9 .l ... 'o o 07/13/79 11N ‘.60533 157 011-1 73/73 PROGRkH 1NESIS 9 7 0000000000000 I .. . - 0000000t00003u900u0123‘56759n12 3 0:0006000000000000000 23656789033057.7790: ... ...... I ... (P111 cl. 3.23730. . 1&3‘56709o123 00008999999999! 1 111. I 1. a u a a W 1.1111111111111111 E .01 0 \I N 0 x E N I‘ \I S 0 X 0 3 F. N l\ H 3 N 0 0 C ‘. 0 C N 9 E o o 6 R S C I . n I .E R 2 0 .1 u .3 0 1. O I f I N S E u o 1 L N z s ) 7 t l E 1 N 1 I B 1 H s 0 2 U R 1 E I I E L. L 1 1 n 1 CI 1 m 0L.) ... o N R o O N 1LH R S 1 .... R N R .0 IO ... 1 l 1 E 0 E l E R 1 1 1 U 1 1 1 1 PM N 0 I 1. 1 1o 0 R11 I. 1 I. S .1 )3 A s I 113 I s o R ‘R s R R 1 N N no N E 5 .E 7 E E R H R 1 I 1 C 1 G 01 1 1 I 00” 1 0 00 N .11. 0 1. ..I Q R... 0 l. R R 11 1 I 1 '7R U P U P 1 o) 1 1 R 10 S I 3 on S .3 O A 8 E ENN 1 N 16 l [N C N 1 RI a 8 n 0 C N1 1 1 C L U51 1 I 1 1. 0’ 0 I. u \I U o )0 0 1R 0 1 O 1 GBRA ‘10 OR? 0 (R A COL I a I A NED 16.! "£1 E (A L l R 9 L 9 I ’11R — 1. I o 11U . CN I PER 9 I 9 R 1.” 71v») 0 \I R... MIL 0 ll ‘1 I! L o N o X 81 o 1 1 0L ... S .... L E E1 1‘). (1‘9 51.)) 9 SN 1CE N00 1 I 1 N0 N5 ’18 IN “6 0‘. N "u 1 I IV 11R 1. I. 1. P . .UXVSN1OC ."XCO’C 1.0 I 6U... 0 R I R ...1 O 91(C00 "CO 91 918 N 1 10L NDC U 1.0 H NU ‘1 100C 1R") 1.1 ’RU)‘ D. R 1...... \1 Ll. . .l 10 .K6(NRC6(11K6(U6(117N 0 6IIL HR 3 090 3 ((1085115 ((1OCOS DU 15 0 SU UCC: UE 1CFAC :FANOCEI E1N09 N(1WC 05. . 0o 1 . R1 KR1HELE1H11R1HL1 1.1 I. IFJI I 050 ... R19 .1 3 PRU ...IR .0 I21 I... 0 N0 (1IRSLH1RC 1IRLI1( 0C . 11 CSRO:IIRCIOSROARHIO(1 7 EIIEO R 0 . 1JCJU . 0 RNU'1C1U'15NU'C1IGEIED I N LDR SC .. 0 In. E... 11. 1 . l! 1001 3 15”, 11.... N19RI1IEL 1H 1 5‘ I\ 1 IIRN 7 1 N L R I. 93.11”! RR 8 1N1 .1 R R010 UNNNE P... V00 RPNNVN RE I 011 I I 9111? 00006 HR! ENOO OIER E1 [0“ R N 00 RHHHE IUN L110 C1LU .... .... .. 0 corn wmmmm sun nun m-..» if I] I!!! 1 C65! SCCCI NIS 1R0 CIRE IF! 5 0 6 3 70 1 0 5 n 1 0 C 0 500 C M 9” CC 1 7. 9 9 S 9 9 791 1 CCCCC 91 E N l 1 U nu R B U S to 85 9a 95 100 105 1 5 1o 15 3o 97/13I79 11H ‘.6‘£33 158 "$1.1 73173 001 SUBRUU‘H’JE 0 co... 0.50 I...) R 00.9130500030000000009 '9 11234.55 (K1 123“.$7P7.123‘5$'.9 1 778-.18988-19999999990 .. n... . . . ...Q 1 11111 1111 11111111111222.5535? H 00. r. uh 9a .100 900... n. 0314 05 \o .. fl €933.15... C0 .10.. .9001 n .....J n. £55719 1734-56739 1714-56739. 12.156739 . 123‘557 3333.1):- $.54.6““£15525§66b666666677777777 1111111111111111111111111 11111 1111111111 07/13/79 , x ' ‘ Q , O 1 D . s ' 0 q C I ~ E v 1 . t .( ) o u ‘ D O 1 . OD x f. 1 I N o 1.... 1 0V 1 3 E P 0 0 ...-"11 on. D .1. S fa ‘ f. o 0119 at u‘ an a V .t o H .19 .1 0 o a l H S 0 FL 03 .l 6 I D U o . E01,: o o E . o E A D a . HIUR on S t H E r c I. 1 AA 0.. o 1 R o r. o [P of u N 1 I H N. 0005 on s 1 V E l 1. ”ORV II. I. 1 o 8 o 1 1 3 ICPl .1 I D J 2 1. R o I l P 1 .I o No PI‘P o o 1 R 0 1 o 5 1o [1‘ .0 E o 1 to 111. 0‘1 o x .1 I. N 1 1 D... ‘f‘ " Okla s K r 0 ll ’ N. RA 1 .[N 1 1 I. II. [B I. Q. ‘11....- ON a 1 0 .L I L I 1 ll l 70 “.1 of» 7. rs D. I. I ”I. u. l o I H. 1.... o c .. o C ... n.- 1 1 1 1. 1 15 .11 01 1 o 1 1 R ‘3 1 o. Illa. a U1 1... c 1 U ... 1" N n.) 1 6c .LNRO oON o J n U N C v. 1 a N 1 Ho 11R1. o D "J (1 J 1 SA W 1 1 1 1o 8 If... on. 6 o 1 r B 1.! k can. u 00 ‘ o N 0”” 1. J. 1 u I. 1 \I la 0 I. “U 3.0 9‘11!- 05 11 ON I- s u (W L o "L U L o H. 09".»1 o I? 12 o M V S 1|. n. 1 11 S n 1 1. ROINU .- Ax1 (a 1 u £ ( RI A P AX1 I u. o. PM R0 41 1 "1|. (2 1 1 A.) 1 u 1 L 0! "£1. a t CI ‘0 "‘p O O 0 RJ( 1‘ s 0 t1) 2 O ’ ...L O \ 1 1 O ’ o c. u. LN] o o N 1 1.5 r... P o (.0 u. 6 a PA 1 ‘1 ... to o l R 10 [C .IE .9 1 l .11 1 o 0 9 [P1 l 1 a N a 8 (l1 0 00 A1 00 ROOM" .0 o P 11" o F 9 On. a I o 9 r.” J 0.! HP: 9 . Cl H61. £1111 o( 1 1| [SC lo 1 11 1 C .11 o A. u .16 o 1 1L. 0 o 11 (r .(1Na 1 R .l 1. Ll! .n .. ON 0 (I l .l-1FD 1 I. ‘ VA 1 0 1L! 1 1 IUV 0 1. 1n "1 o 1 O o Pal“ 01 r? I. 3 1 1 LS1V1 III. s (I. I. "9 R1.) I. 160... )6 3 [A110 .... Lu. nan 1n... ) o n ... . l .. LO!!!" 0... r In a 6 1.1.1: 1 N1Rt 61?. u S as 02 LA! 1lro L! C 06 R 1 QRSELI l5! 5 R L E '2: 1 N o 1.1". 1|. DD .9 (1 l “:11. 0:1 1.. C1 .1 r 1 H R. R H (I. 1 1f 1190 9 (bl/L p.51. [NFN .1 1.. DJC1. 0311 91 1 1.. 1 U 1/I’I’LA U N PH LX1 «(ALQHE OH H 115 "GP no SBERI .3 3 09C 0.. JI-1 (AC 0 o .093 a 3 1S . "L01 n1 11 BE] 101 11 1 "(16(101o flu“ o. 10.11.931.11 1 .OZx . VISRKSCo 3 .c 1 A13 . £9.91 3 01...." 1R". "1.1.1.! or. 9. R11JIALCR1H 1H 9PC¢ f. 11‘EIU II.” .N1 o 0 l1 . 1a l 0’11 . 799.251. C SN .6 1 5P 1:. F VEN1 o o 1 6 3 n SPPI..0 10? EN :15 l1 I III I. [[1101 I. RES 1 o o 1 1Jc15201 1HU1 111 o . 7 11lXEVCr‘19IMa1 HI 1 L1 .01911. tn H lbfilflflg ill." 9 I.1.. I(ncqcl 1M(1 1:11 I va 9.019 cl . .ru 1 :94 t. 0211...? . III, OI. [P .11 0|. N11..A.C0l 1 N1IIEK1Q11L 3 1”!!! V l. D. u l 119IQLIAFOIL 1 991:". .alntfil o.t 01..>H1:u n flv:unn3u nYuUr. 7. 1 H069: nu. Nu Rana to .Inuihul UNNNEESC. BEI ov (10 Rfr D (N1RN(O(1NVN UNNNNNEREVS n In a91NDVIOIR VV‘ fiOOOGnN 0 11B 1 or tlflr OPOIFAFAIIP rflnnbfls FS‘: .(AINII ?0 1:9 aflfiuffflo Ufllsu oL 1R1D (911121H1LU PfififloQIIILKS? DH 1Dfl11l1261 1L0 RHHH11‘10 OPLIO .1 13 N1 198110 PFHNMH111CSKN I1 liq-.11 V110 PunbNNll. of Ron ORDROOIFN L urlnrONAAlpSI E..PEOOEIRfl Olin SCcE15100“ ..A 310‘ .(UDUILEIRr. H .aCrFtlllbiflVNI.-PL DRIEBEJUD (Ins. a o a o 1 . . a u . . ‘- '1 3’0 "‘0 . O I h‘ o ... ... 1... 2.. I. no. can ”(VVJ. (CCCCCCC 9 . 7.9 91 9? 1 (CE 91 O 921. N l .1 w R m ‘. 1 5 n 5 ~ 5 . 5 . 1 5 . 5 5 1 1 7. 2 v. 1 1. 1 1 2. Z 3 C7I1SI7¢ FTN $.69b3! 159 SPY-1 7: 73/ qGDCS1 . h D UbkCUTIS' c .4 00!..flnu.n‘..: .03 a . ... ..rJfl .I.“ h.- .JUCJaa. P..UA-F.fi\rJ» \c.o.r.oo..n \nu'.fo°fl$. or..va...: ....ICCOE . 5‘ 90.1 23556.7..- 0. 1.1345679; .123‘.>57Rkw.n 17.942307 3.0. 1§65A1D:v:.123552lfi¢ 17.173311? 1231:3573 14.1 11 . 112c2¢222521 .331 .31 1.1.31.6 :- 6:- A‘L :- 6‘55155r1155666 96666667777777? 7756! 5850.55 222252 ,-,2LSQ£.5§~“2{-4.1305-‘221. (AI-22.57.27 «0.2.08 ‘37:":3s5.‘ ‘ ) ‘ ( 000000 1 ‘o‘nu‘. 611 5 . a. I 000000 D z“n“l~11 0 a. 1 .000000 In 3.;ih‘ 1 c. q. 50 000000 05 C§J§11 '0 3 02 .000000000 N1 21922.,211’0 0H 0. .. 16 0000000000. UN (52!; C0 2 11 .000000 09 ’1 111 111 n 0 5n. .. .. N6 000000 1 0116.111 F0 11 0000 5C .. 00.“ I. N1 .06... 00. 1 0.9000“ 3.5 ‘55... H0 00... Gr... NCNSG .2 00001.12 11‘... 1F1PQ.)H2,‘¢2J.. .41.! 50 IL P.~.s I... (bl/nu/IIIQR... 0 0 0 0 01:. (12 "(H 0 111. 1 P(1G 0035 5.1 1 . . . EFIU (AACKLU 1 0 8.9 U.Uau1$VS1 111 11 . . . EIIEOEQ \AC H ... a V LDRC G...” “‘0’, .../II [III DD N 1 9 R1Hru UNNVENNNNES1~ ntrn..u.uf0 $009.90.. G~ RV, 0......V‘I luv. I.EOAA a!" ‘1MNQI1V11 UBnLrI .Nr.ns..fi,N1AA SCCCICCCCIFDD 009090099 ......COOIQ‘IOOOOOOOQO DLCE'EER ‘97P .o-oap 0 0 0 0 0 00 0 DITA 0] (90.000.00.00 pncsknr calttew PY $1£FHEN A. :uscutt \CDES L IS EROADt NEH ‘5 D LEE“ ”‘3! ON UNI,“ "10%..10511 $EAL ARRAY 0151 PROBABILITY "051 TE!) FOR UPDA11NG ARRAY 1PR$h2 REAL PEAL THRSH1 PEIL E 215221.223: (22s. (2‘2.;t.§.2.0. (.51.). :15 1M! ENCODING 01 FROADCA$1S 1H 1"! P1 (tr.(cccr (tccccch0-‘(trccccrlcctcr (C((cccccctr (rtr (((rcc OQO 97/13/79 4.6‘AS3 11% 160 3r1=1 " 73l’ ‘ FFDCST ~ FPUTIV sv LA.“- UCO...PJ. 00.... .61. . .a. . . .. ..n I . . .. H... ...J. ..flsUm a. .0 ... 1.5. .\. A .. .J. a... c. .o (0 ...-.0 ...“..UCO A! C.17.1..LSC75:1. . 23‘s ALVA... 1217.30.37 0:1 4 3.52.5.7... .... . 23‘55793. 1.1.5.0075; A 7.1.1....5710; ..--(3‘5 P.0C..CC9QO9C.1Q . . 1.. c. . . 13.2.3.5: 5.1.5.10313331....A‘AAAALAAA0E3&.E§SE.6CA.A 06 7.21.3??? .....i .71. .3. 3313! 13.53333131113131111115111 3... 1.1.3.. 3131.31 5.14.13131333 0 .v. 9. 0 O 9 0 P 0 1 O L 1 I. t 1 E o I o i x 9 r0 1. 1 I i l\ A 1 I a... 1. 0 0 L L a o H 11. o 3 E C 7- 1 R 1 A CA 0 C L . A .- H R EV. 0 E E H. 1 H 1 10 n 1 F o S A G G 1 5 Ac. ... NC :5 0 0 5 N . «IL 0. .1. "I. U 3.... n01. . u 0 J 0.: H A O 1.1 CH 0 .- .K N .J v.8 1 H E0 N 1.! 1 D E F '4 U. 0 '1 1 E “E E 0 M . nVL E 0 C N o o I 1 b R 9.0 L R Ln. C 18v 1... o 1 S E 0 a . ... 1.5 N L1 1 0 PJ 1 o 1 2 1 U 0 9. SS 0 o D. A 5L 1 A 9.1 CA 1.5 E.A O D C o C A3. A E .\ 1 1A LC 0 E s 1.6 0 PD. H R n. s L 10 0 R u ON 5 A R G 5. U0 FA 0 E 1 N1 L 1L E s ".5 KC 0 1 N 1.1 o s o 5 .IL 1 h R 0 N 1 5 I. AM R 1 1 o 10 C... 0 E 0 SA J C1 O S 1 1E o E . AC 01. o A .1 5 Rs 1 DE 0 1 1 0 E. AU C 0‘ A? 1U E NE. 0 S H .50 R?_ O ru 0 V‘. CH A 0 A0 0 C C 0 RA 0 1 Au 0 A C‘ 05 Ms J N o 0 A 1 9 CR 0 L E 0 9 ‘5 AR 1. 0 $1 0 .b E a. Rt... .1 E u E .n r. 9... 9 1 1. 0 O 0- H U B \a o 8 SN .R1 0. HP C 0R 0 0 P G r. ...... Or A 0 2 A o P. 3 U P NC... 0 U N1 0 1R 11AG1 L 0 L 0 0 1 VS 0 A1 - S .1“ 1 1 tie nfL. N 0 c. E E 0k .66 nu 1 1 Y 0 KS 7. NE EE11C R 9 B V EA N 1 1 a K 05A 0 u CR A on. E 885.51 1 C A 1. 0 o 1.0 LJ 0 VER 0 1 EN M. E E8 AA on...) s E L E R1 NE 0 1. 0 L CC? 0 0 H1 R 1 H LLIAI. 0 1 C 0‘ OR to 91 C .51A 0 0 C .LL ‘0 1i. 0¢lL0 vfid 1 o r. t?!) CH. P E R 0 9 h. o E 1 E K\ I AI. R R A E 0|. VS 1 RE 0 51‘ 0 ( YL Ell-b. H 3... 0 0 o a! o 0 A .J ... R1 0 1A 7. .00 1 EA1. 0 C Ff. LA A S 1... 12.nCA R1 1 o L F J1. E H 9.; LL (I. 0 E H .FIL F 0 CCn...‘ . v. 5 ...E nu 5 0 0 ...v S L.\ N FC A h. 0 1 6" RC L H 1“ H“ o .RSCC a 230 E 1.1.“ P .I E 1 A. 1EE 0 1. \5 L1 F I 1 {cu DZLG 0 JE 0AA. C1 15 N LE1! LU CN 0 R E EL: 8 An PNN ..LIOAK .h. EFL 1 L05 A 1 EAARL 05 FNR 0 .0 1.! A 0 3.). 9 C5 N E 11.21 0 ”R I N EV 0 .I AL n. 18 U...U 0 1 LL SH 0 LI!) LL E D. 0O 959.! 55 L o 8 1. UL: CE 10 o L P6081 R11 0 3 0.... A1 . o 0. 0 IXAEE L AE 1 Ll1n. DE 0.. 7. 3 fiLjAcC E E IN L (LE R... c . CC C ... 11AA...R. . n .r .....J .LSG LTV 3 LL F RCLCD E\ L 1ChA .. CU SER 0 E a 0 DE . c ..Cv v. A AE RU EN 1C L E ECthE. 0 0 .IL E1 . ..A1 1" u N It 0 E G 11 AH us LFRRLLU! F1 U .311 LCL UEAFP? H 11AFE SE LEILLSUI .— .)... 0 7. .l t 8 ..1 8 ... C ”\A C .\I. C1. CFC N0- AA C .. .— 1X C A UEC2¢.1 1...... 0 1. LPIJ r ...LL. 1 1|; E1 1.111... .P ISRLLOEE A 1.0-.va a E 1 . ... L.l N 0 L .LE P?- 71:2!11. 19. Ht .1111!) 1..IN YJUU s. .15 .IR .3 r13ELnXU_D a A V109 S AAFB NC 1 N NC MN 09 CL C 3A A50 C 0 o 1 E . 9 Kn: n 0A.... a... K a . 0.... 01.1. K AQKCL Y... ... 01R L 0 1 LL91 1.1. RD LLO C1 PC C0 C1. 011 C ‘93C1A Ca 9. 9.0.3.! fl. 0 1. CL GA VE RN E E1.C E 0U P 1 I K .rArr. .25 EN 00 N clan.” Ha .... C 1. .ACDP 0.. SC 9.0L C DALE C1 0 O Q 0 O «C .V c t . . ... u 9 a 3 a 5 .CCCCCCCCCC CCCC . CCCC? 5... . 3 1 4 ...CCC C CCCC C CCC 2 o . E. :J to ‘4 5 c I or C ..V . 1 1 2 2 3 1. 1. II 5 1 1 1 A. 1 1 1 1 1 O. 1 u7113l79 VIN A.£‘A33 161 DIV-1 73173 SUFRDUIINE HRDCSV 9 7. I 3 . 010. no... I . \On \uOCtOOOI 0!. c 000000000002 3 .0- . . I .v 0.. n. uh. . ... 0 ._n 101.0...9Cza1. 1 0.0 17.....A567RA7 1.1.... ASAAII. 9L1w 3A<.A.7A.9.V123ASC.IOAV o. iASA. Afr-“P1234556, I 7.70.390. FAIRFRQQQOOQ... 999 n 111111. 111??) 3A 1.3. 5.66677’77. . 7 MI. 3131131311.“..11 .31A3AA.AAAAAAAAANAAAAAAAAAAAAAAA 111.311.31.133 1 ... L“ a 0 EN 0 R 0 FE .... L ... N AR H s . .... H L1 1 EC ..II 1 .... s A 1” A 1 N 1 N 1 1 a AI. L E 0 AU 1 K V .5. A 0A NC 0 o C 3 . .IV 0 RL 0. 1N 1 J.\. h. A .- U a 0...... 1 1 u. o o H 3 .IR. .... 10 0 6 O 1 A A s 6" or. C I C . o 16 2 EL 1 .1 R S. E A o AN 0 R S E U 0.. S 0 RE 0 E1 A D 1 1D 0 N 0 RR ... HS C (D 5 1 JV u 1 0 A1 0 1A D. 1A 5 C .. or o S 0 C A I. . nu 1R E A 0 RN DD 0 0 IV E H C I. O V... 1 CA .L p C 1L h. 1 0. 1 . CH SR RD. V P .1. CR n... H V o 1 o R1 :0 0R 1 0.. N 6. C3 .... L1 1n. E A a V1 1 RA 0 N [S 0 N. C 6 1 CA. S \I A A! S 1 H... J. Y .... R 1 A J o 1 1 1R 0 0 SL R N 0 . H 5 s a. 1 1 H. n 19... L5 1 to NE" 1 r. 1 1.. 1 X 0 0 n11 o o .IU <1 1 1R1 .\ f! .l E I R 15 1R 90 L9 U 1 Orv n. H 0 1n. I 6 N A... A1 E1 1 DIN 1 N L urn" P 1 1 1 1“. C 0 LV R...- L L NCE o C CN I 5 o N N 00 .r A o 1 . “BR 1 D 1 0 .be .C 6 ... SA N: ER L1 A 0 .II 1 S M 11.50 a D 1 D 1 0.... No: C .r 1 A... 1....) A A 60 o I. P C N 55 CH 1 K0 A s o h. C o a 0C... 0 1 S E A1 E1 A NV L 5 (L N06 0 L 1r... . 1 .(U L A .I CS 51 to AC L 0 SE ENNR A C N. 05? C . CU 815 E DA 1 NN LR 1 1 HF CE 11 fl U111 n. 15 1A6... 0 MC 1 o 10 3.. U I. NA 5851‘ P 0 DJ". 0 .1 Us LL15 Ch. 9 0 K 1 0 L 15 n N r on O N 8.01 0 I IV 0 RA In... CN 1!. C 1 0C 05910 0 u 1.? 8 1 Pt. RLON R P0 IR EC P. o L C 0 .lA.lv-v U . C C h ”N a 101 o n R 9E1 H1 1 A h. N o H E1 E 109” h. 1 N19 Q.CCAL P D..." 91‘ CA RC C V AR 0 n K N 1 “1‘01 L n. 0 I05... 1 CN 0 .I. [.0 C .0 GL1... o J 1CC1 L C LLC 1 JHVKV C V0 ...-C8 1 PV 0 p o "J A 0 0.? L H LLE .. 0C5... 0 1... 1 .l JA MC V C 1 1L11 o 1 "(1 . A U AA1 1 IRRRL C [V 1D: o URoEoY J1 RES 135 C 5110 CLS (Clo r C C1 RN. 1R N .RI' 6 IBAnCI'J 0 '0‘ F R 0 bill] 1 [E HE" C" 1.3.1 1? OAC1S1 V 010E 1A: 119 NS? 1 RC 151 0 FL. on (r LD L (R VH1S CL A .1 E1DSG R E 5 C V... N901...) 0 o . ALgnuE R1 CSA :1 3 SlAIUD I ER ..u." CC 1A0". V“ 0.2:... 1n. 5 R .0 1L 0 o o 3 HOSBV I N CUE RA L010 8 CE CERF) At... 2.1.") 1:: 11C 7 EIRAEC A 1' BSA F Y A o R. .NEAKhLC 2 N GSA EGLJE 666 I NLBNDR O . 1 US L..1¢1 :l Lac A1 01. . U. oU ... 3 III/I S [.5 P V0.ficJ1L£n LEN J [PJ1E1JLoB N I 1N3}! L 7 1 N o. ‘1 EC "N DC. "A 06:81 ENC... I ".5 (U1 CC' 105C1UU00E UNNNNE E 0N V10 1.! .0101K9A 81E"... 1 1 N11V1 fin 1'3P1NNCFVN rmnfloc 1 ”U EAN f 1 t aClen A P11 YCJ1$CEA0R “1N .111NNER RVVPME 0 C0 LHA F0 NLAEADKLC1 LE 5 E10 10DLH2U D1“ D1111LU PWWMMII N r. CR 0 QUCO1OV C CRSR RPV1NFVCPS10 CCD CNNCCC10 UCOCCN 0 .D .700 .....N :01000C in .IEAO [v.CCOCC'U [N ..r UUFF’FN SCCCC... n ”M. 170' LA KC10 NOR 1r... 1HHI HERSCRRlFoRt. I. CCAI'INF D 0 s1 0 N o .... o 1 a: n. ..J F. 90 s . no. 5 a. P. a. p A. 50\ CCCCCC R. CCCC C CCC1 CZCCC CC.) 1C I 3 33‘ E N . I 1 U nu. R B U S 1 < n 5 p 5 5 u p) t. 1 1 2 .1. l; I. A A 155 16 16 .T‘.31.69 C7l13179 11w 6.¢°L33 162 C€181 ’3173 SUE‘CU1XVE [VPLC A. ..1 .CI. .... . . .u. COR)!- p.r. .... .... .933. n .....u. 3.1. .........0. .r. t... ......0. . r a. a \ 1.3 ....UGhTVA a... .u... ...... . .... . . .\ ...fi.~°..u° 7 1.3.x o 3.170.367.5320 ..1705A76. .7... . 7.31.5575... 1.655557va 4.. .1155719 .1?.t.6597%...1. . 3RA$¢.7A:1.....3 7.7.2313. .. .337 1.1...“AA‘L h bLSSSERJ§C.6¢566C666$77777777750 A. S..- a CPL... 9690 90 3.000. . AA‘AAAAA‘MAAAAAAALtut-“ALA““AALLAAAL6:.“A‘LLAAAALAA‘LCAALALLL‘C‘A‘LL(LLA5555.) “ 1. A n 0 1 L 0 0 s a o 0 . 0 C ADUH 0 0 C .bVovl 0 \l 0 1.... .... OAR. 0 H 0 .Ar. V R A 0 2 C 0 7A 0 P51. 0 n. A 0 DAR LAE 0 9 .t H P 0 NEE .1 CEBH 0 0 r. V. .l 0 A V n H570! 0 .1 U L to 0 LA .IA 0 )8 c C .... N 0 DA .1 . LYG 01.0 N T E 0 VNC C3 .1 BR 0 IV H E A R 0 CI... N 0‘ 1. 01C 7 R T 0 R61 [L EDT 0‘9. .6 G A o 5 0 IE I... vIHEA 00 N V P T 0 V: n. R... NTTD 0 V E n. ... o S K 5 0 10H .tA CONT 0 C0 R R Q S N R N 3 0 .l PL C EU 0R 0 .l .l 0 R ... A I 0 5...... X RPS 0 Cs. .3 s 0 s U .\ ..1 L o 0 .IPR FR C.\¢.R 0 J... .1 0 A K T R . .h H 0 57A 0 PARC 0 (a. 0 EN 0 5 N C U 5 o 0 A £3. .1.v.1 01 o C RU 0 K A R .l K .... ..u 0 Cu. 7 N .... F. 0 00 V AC 0 S L .... N C U 0 CUE. 0|.) H.» R5 0).: .... K L w. n. O R A U C) 0 AR 0.. TN 1 0’0 .... 01 F. K R L D .20 0 n .19 .1. EL 0CD C AN A .t .l \l B .... D a 0 k .L 01. 5'55 00“ ... NI. L 0 R z \I R 06 0 REL .1 NAPU 0 N R 1- C U a. N1 0 CO H IYIR 00'. D a N 7... .1 o o o a o )0 DNN in. A» L 0CA .... S... E A 15 x r, N 0 DC :0 EEA UR 0| H 0... H LV 5 o \l o o V .11 o. 0 VIH R REE? 050 T E] o LC . . ... I. \I C N( (0 1R 0 OPH- 0 0 PC \I CID D L .l \a R? C. L0 ELY EC C TA 0’3 K AC I 3 J C6 E o P L 29 25 E0 CPL N o L 0.. o C L.... T K (0V1 V \a I. . I. S o H (5 L 50 E71 9.... PL E 0a? ... R NA 0 36!. I L C ... A L03 ‘15).) 3 A0 REV n I?" 09.1 H E R5 6 C (.0 E a .0. s L 3.0!, JROK A L0 .... s. R- cl 0 00 C 55 K C .1)C0l \l C A R U 2 C B \I 1N1< L 00 .16.! AL D 090 PK .15 . 7.... RR ... L Y 5 AGL 11:? o )0 ON? PE NYE. 09: 0 HR 11 3 0H9“ ET R C L C 0 L65 0 obN L 0 IL L. CACG 0(5 1. YA N 6. S G VN S ... 0 1 L A A11. 0 0) 1.0 C1... ’A AHh. . 0Cv. L .1 2)AL L I... L S C Q. .6 on. .1)L TNCLLC (0 is EL ETA: 01.. v. :13 C o I (ht): E... o L A n..DA 07!. 3505.! 01050 r.A$ 01.7 AZC CC )0 .TPL)1 CS. .... o L \a CVL S Iner . IV :0 CCIS 0.; PH .1 LV JTJ A390 E F D .... C (I K . LNCSEUbC)0 [D C Y 0 UL PSKU A r o .LATR R .. I A K C o {IFEL 01.. (TIVLRQII. 0 RASI A 0 L s AR... 5 o 10.1.... LNTV L A L rubs (9 XL D 0 I00 RIC R 0).". . NW... N (6(LE KN1K)‘: o r. V (LA .I 0) LII/IIAL 00 CAP... SR 09..er L.. Duly-...! I.) D s .L E(R \LR .1 0.. 0C onwLL A L 812 $1030 H871 EA 0 £3 E V 8 NJ V)S FCLxDAPT r ) T CRTA1(.\1F 79P$GTCC10 0| .I L 0 o A At CTN! 0 a CD. )ACERTLAN .u L L CL'gluvA EA AK U11 3‘0 ... .A 5 0 CPL L RSIU L1 R. ...RT .97 BL... A . U ..x ...- ... SUL 905%: LEO SNXF AL 0 CU o (I N V L( (a 7.1 I N... (( ... 0.... I. A 3391!. ...R a Ail/nu 0 Col... 1A 0 .51. .12 5.17 0.0 1' )N...LLKG.ISS ..r . L \IbF'L YCKS RFFLDL c\0 I I RE 0 s~sL J RAVE FV f.PrC( S H F. P L VLLP C( ”I’ll/.1 «10 A51... IR 0 L01 It It... . QIGUL. C v.CT(C.1 L ... U TR P. .rr-AmuATrl .- 910 YEA V 0....(LCL1UU5 Arc! NR hENSA] .... 01 N n.1- .1 ARK». CSGCI UNKNN NVCSI TR... .V-l I LNN R C I: 01 s .K( IN LAC (- “DOOOAUHJGN0 “URN Ru! I.tAa \l (1.18 CL 0| 0|. .1! (.1 D R c K R (L, L Fv. v.1. 10 v (.50 Lt.A0I out... 0 L! ‘QAVEYY. At... U 6“ R0 LL51. 0| C RC C SEA L FUVIIIOTU0 a. I- 0CR L VNR FBEU UU:TK C .0. vll‘ E C Urvfr.fi:..«.. v.10 XPVF A 0.131....) . COT RACE. 90 Na .1 C H VF H .1 SCCCCCClhu0 [Co-3.. I 0. ...-.950 (CS ULKC 0Krll 0.. .b C v.1 C I 0 0 0 0 0 0 0 0 0 0 0 . 0 0 0 0 5 .0 7 ~. 5 C(CCCCCCCCCCCCCCC 9 31 CCCCCC0 4 C C1 QCCC... CCC C C C... 1. t S . Co . (a S S . t . 5 1. 1 .L .... ... 1. b L 5 ... A 6 7 7 163 07/13/79 11H $.60£33 077.1 73/73 SURRUUIINE 'XBLD fl 000°00\ .1... 1.700300%... 0000 00000390030! 1.91.970... P U0 1. 01.. 0.9.05 0...“... COP .. ‘9.$73.\721‘04A7E9 1356759. 1..3A557l.9ou.1~¢7 1056739 12.1.‘56739 1. .... I . ‘11111‘1‘112.¢q¢~122« .27 31.831.21.15 ‘1 AAAAL CAL L ‘55:)?5566Lu 12.550)" .sggggségéggggg as; (155‘ .52!) o E )) S I \a 2 ‘6 . ' 0 O 0 - 2 L 01R. N 11 n C t' U 0 s K03 D 3| 0 I o o ‘1 '1 r \l 70 U S U D 11 r... V .1 0 V L .3 A C C C lo. 0 I. O R L ‘I D n. R N .0. I...) 0.1. 'l .1 0 n. C RV A 0 O A S0 CI. 5 H s 2 L s 0 1| SE n L I. 0 113 N SC 01 .... A 2 7 I o .t .1... G . 0 L )R 5 CR N L 0 R R7 .1. nu ...... .... A C I R RR R R I. I. 00 .1 PF. .1 A D 0 r" = n s L n .1 OK... 5 NM N .. CH I. ....U K C 2 .1...- r.N I C L S R L 5.1 7 ... R. I. F. to .1 D. o o \l N \I R N N f. R' \I) N 0 L I. [N .... C I. \o 1. .... 7..) '10.. n. L VI. A S ’ ... 5X L . SI. A AA H o n 1 (I :8 I L .... Hr“ D. I. C A )R 11.1 7.0. C C A C) V G S n H I..l L a Q. .\. N '1. \a C A o n... IA (6 00 0 la .0. C1. R 01 R \l '1 s I". C0! 9 l L s "R 0" O f H 0" \I ’ ‘C C I ‘Q N. 01C A.) S K V C In 2 \a "DC 07 O o A S f Fa L n A L 73 L 2 BVC Lh 08 I. R 5" R). I K .LN). F N o L (N. R1..(7 a NO 7C 0C1 R on? . 9) C0 1 a OR! A: [a .I A o N 7 C A 7 1U .1 AH n31 L «1 Y. (I) L.) .10 cl) L0 :.o o.l I. OB "Ii. .1 L( l _( I. JFS . 1: LL 8 55 9L...- 00 .IC 0 N s 0 L... LC 0 I! oL’R RR LR I [L AER) ... 015 C9 AR... N.“ D. 8.... 61.15857 H... IAHC RC .flA1 N 050 NICO 0 A0 A Y'AC: $ ULSR) .19 VAL... I. R .0 GR... ....NL )L L L: 7)... C9 0 ’0 ...C 0L A 0L :5 L .1... En." HKLR . .108 A o ‘20. 9 Cu 1. c SUN—r EL 1. .1 Nru) )VLU R (1.1 .... R 0A 1U :17 r. 5.1.1 X L: '5A R [CO .L K 0" 7NLSOE01'S 3. “UL ..s I? 0°er19( 05 LR .lL ...... )NL L o C l!0r.1...l .2 I. .1 :01. 1|. .1 {I.1.-1:": [6 A!" (.1 UN .lllR 1.1 0175 . CR‘EM. ..U C .1 ll .L...1L C. LSISLEACG o CSGESU I. L17. 1. ..." .11...." D L N I. [0:0 U 01" .91. 'INU .0 S N 5L . .1517 ...uCcULH SONSLRI. .1 C7. ARN9LN (70WIQN 0 L I. V. 1...... L S N .UL..1-19A.l'1 5 .....t oL29U19 (IFLCA u. PHILO .1 .1 NS R ..nU ...)(HI SLR CSN A UN 415.11....IUC7H ‘HFTCI. N AS 77L .IH. 7.1U.IK$A'IUCU 0 R NVROM N NNVIR NV'IN n L... NLLR . H ISNIACSGSD C C I. '1‘ U0. 0.1 UIERU nu DEAR C BC (RAIDE: Un. 0.1 L n. 73.57.50 CD (TL-0.1 n. ....LHU h. (UCSGSKSD CI. .1 .1 NVC NC (RID .IR .1 L s nAfn 0.1 'UCN Inf 1.. .1. ... CS...” Cl. 117R... R 0 G 8 9) 7. 1 ”0101 7) a r r. a) n t r. 0. 9” ..L .. C75..CCCC..JC6 C. 7 f. C9 9CCC1 1 1.? 0, 9339 . P C 9 1'6 11' 11s 12 125 13‘ 135 164 07l13l79 VIN A.¢0A33 01181 73/73 SUBRUU1IVE INFOU1 000000.10800000000036 0.0.. 050... 00800900800800800000000 3.556759 1)..)A56789 1.¢I.A557789.1.11.A56789.J121.L..)6790 1235)... 66666561777777.1738! 1. 88888889 099999999.. .. .. ... 31111111 5.. .5551 .Rggssgxassgsf .55....555 55555.. 5556662....6F565665656 I... \l V X I I C I .1 D a 6 N N .I 1 .u. R A I C n o \I .0 ... N 8 A 1 S \l I \l .1 I C I A I A I 0 .1 u I o X .1 . I .1 s 8 A U n. A 0 I I .l ... 2 .1 1 I ' N O 0 H I \I I I 0 I N g I ... A I I I .1 I 0 H .1 1 1 o s I \I I I N N N A. 7 .1. N ... I H. I O C 1 . .1 R N V .. N I N D I U I U U A H U .1 A I N b .t o S N C. R N .. O_ o O 1 D P A I 0 I 0 1 A C C .1 0 ... I .... N I C I 0 I. C .1 N N A D I I I I 1 S N 1 N 0 U 0 I 0 1 ... I I N U ... N 1 N X 1 .. b. I u C R o 0 I 0 I J 0 ... .1 N N .1 1 1 1. O N 1 O I N U ... I I N U N 1 .... \I I. \I I .... \I 0 \IN \I I1 .I 0 ... A U L .1 L 0 \I 0 II N \I N L... 6 S .1 .1 I N 0 0 0 ... L 0 I S .... L 0 1 11 U N I N N C N C N D 0 N ... ... .r 0 R C... I D N .... X 0 I 0 I 0 0 C C 1.. C ... I” 6 N I .1.) .1 N 1 .1 1 1. N I N .1 P V. I .1 10 1 I .1 I. A N ... .. '1 I 1 1 ... N 0 D. 1 2 .1 C G U U A o 1. P J A I. A N I .1 I. I nu s v. I.N .1 N H ... .7 I H I C ... II 1 1 N J .1 .1. U N N .171 .1 .1 .l R .1 0 .1 I N U N .1 I n \au 0 C I u 5.1 I S 0 II nu 1. V \I 0 P .1 N \I N J) N N LF .1... II A R I .1 I I. N I. 1. . ... I. .1 I1 I I a.) I D. N C 0 1 N I. U 0 I .1 \I .1 I N I. I \I 1 A... INLS D C I. C 0 1. ... A I. U 1 ... ... C9 1.. U? L0 9 AA A v. G .1 ... S C C I .1 U C 19 1)nN IN 9CU.._r 0 .1 N L N N ..110 I. .1 .1 N 1 UC I6HL L I NCN1S RN 0 N A I. D N ... SUV C U N N l. U 0... 61NI.06 RFHUI PA A C U 1 N R 1 IN! N 0 R 1 N 1 N1 1 I I ILCN U1CHO U 1 N) .1 U A U 5 ON" 1. U C .1 I. C6N0... (fl 1IJNI I Q .16N C.) U H 1.1... C. O N D ... I 1U CR N11...1VUC ...R I I (IN... I o N C N .150 N... C N ...N I 00 IN 11CNNCUN NU'I NRN L7 '1 I U .II. (I I A NI.‘ L0 L UN'NILR I )U). C CO 0.1 U. L I. DO LN. L "0 0H. 0) 0’NII’ITL’3H I 11.1. I C: N I 0 5 \IN I "N I 0 1 1N1 CN I C3 .1 1. SUD... N.» I? A I N... C R 3 X C I C U A I X N1123G10C . 5 )I ’09).» .1... H) ... )OU;G.H) nu )IHsCInIH) . CONFUUIH I {)6 1’ .11015. P 1 no .1 00100010.“ N .0/0)010...E 'HF'RHNUCGO I O 11 ‘21 .1 I A? 5 .IA 97..) IR). I. .16 IR; («26 ...N NNE... 0L ...1 91L9G 9 I 0. 9 .1 L90 I99. .0 L91 .99. 9 . N... IIDLNR. 9H I.1..IF1IX IN 1I D .IN1IIH1I 1 .IH1IIM1a 1., I’ll... L 1 71 7.1271 71 :7 71-771z7 U 71:71:7L .1 HROEOC 9C09C19C 9C 1.9 1 09C199Cl9 I.1. 09C199CI9... UN NNNNNCFVC1 (1.1.1.1 C1 C1 C U .1C.1 CC1 C .1C.1 ((1 CVN 00 0000 GNELA EANCA .vEA ....A (1.... n. NCAUFEAB.‘ ... NFAn...t.1A9.1CR ROI HNHHLCILclI. 1N11N11H 1H 21 1H311HA1 .1 1.1".)11H61LU BH HNNNATCCIR IRCIR ....K 1.3.! x .... CIIN ......R .l I. CIR 11R 1.1.10 Unu OUDFNVCRU RUINOUPU RUAON .1 'RUUNROUR N 'ROURRUOR".N SC CCCCRIIIU' 9.119.106} 0.1 0H ... ...UFDUU'DU U ...HVDHU'DJIRC A Q 6 R U 0 1 fl. 0 n. .11 C n. 5 a... Id 1 a). .3. av C A 0 5 fl 6 D 7 0 9 9 9 19C 9. ZCCC 0 3 9 ACCC 9 .... 9 C 1 5 f 5 e .... .1 5 . 5 . .... I. 1 2 .1. .... ... A A 5 5 1655 07/13/79 [1N £.b*433 nf1'1 73/73 SUBRHUIINE BDINIO 90900002690C.8900000)0C08000.00“5306.090990.5 739. 1.7!)“:I507R‘9 .123655739n..1q(1.‘567l.9 1.7.1.1.5573 11‘2222???§:2225331333323““LLLb‘GSSSSSSSSQ 66666656665666666655656665666566656666666566 ’ I x \I I. .) b D \I) 1 V I.) I 0 IL \I 6 C l.( I. 1 E Cl I. ( S I" I r I (n. J S a P? J I 8 (l‘ l\ \I U F. 66 E x I H 00 o ( \I I. Ll. ) D 6 7! I“ I. N 1 0 O I. 0 I o )‘I (I c 6 U ILL Iv) E A! E z 1 s C R 1.! ll I G E AU ( I u N 7. cl 10 P]. N U N (P OJ 5 c H E P0 ‘1‘ cl N N .I 9) Jr! 1. I I N r )J t In \I r I. N J I Irv ..t 6 5 cl I. I]. (0 1 '1 U D S I." PL 0 I D H R. F. (.l SA ..r 6 N I I. NU In N Al I «I B F In D I l. 6 U “U 0 HM" : )_ 0 cl N H s R t = \I I. a ‘1 U N N 'l s!) \I I. I .L U r. I u H _JJ J I I u I H N l. )P ) .t I I 2 I l. ( \I V I I 9 .uS I 1?;.¢NI. ( ’5. I U \1 cl I all. I .l (( NLC P N5), I U ‘u U7.‘L ID a: U “V? .LIY S LIIiJ9 r 1)0N I CN 9 F 1U .../U I. 10 I 6 I (6Hl [)1 I ( .I NO [)0 \I N D I . 11‘ I. 61.017 00 (G F. U ‘1" )JH \IJ n ) ))I\(f. I 1 I I (CI-EN 7 U 0) J I. I. I I. 0 JJPF‘ lR‘bNOE I I [H I. .U ‘1) (I S o I IS"! ('N‘l'VU6)C R D o o I(lv)!‘ R o 1.11.1.9 ONICHNEU1n N U H .0 (1- IJ(G f. o ((019 'KH'NILR all I \I N .l . NU... (IN Dv LL! P'I U) N/IN/Ii/bl‘cll. 3 6'! IU(I.UH 5 BBC SUO H.) I. I. 5‘18 vl L 3b NHN‘UC I. AA 0 10 D 172-361(U0Cl o U B) o . .INHH D Ll.) DHPI o PRUUUUUITUH IJE rr AL) ".19 0 I II. ... S F. YFI'FBH PNUIG N l. ( :H'IG' E 11!. ’17....» EN" NNEl’ 6 o la IJ‘ I 8‘10 “NO N : 2 I 2 JD” 0 NC!- lIDL NNRR 1 1| )I-NUHR .l .1le \I IN" I.” I’ll/nu! III. E :IUF)J (INC! IJJ EEJI. NI. cl XHRNE '- l‘UUJ CJHNNN F. l. UU t: E UNN NNNNNSNEKV U FPN (I(N .. : K .I 0 E NNIF s VN FLU 00300” G F. P 0....(11‘6: .IG .. U 09‘ 11(NP ER RHH ”HUaWHELIAL H SffruptTNNUNP P 1.9.! vI'IPIS-ILU BHH HHI....HH!T.I( n. IlNNUNIOHi H l NVSIIUlsID U00 OCUUUIEHAF C n UIOCHHCN 0 0n UOIUDM .IEN SCC CCCCCDRIDI D CHHHNNN! C 00 CCDFNVIRF O 0 r0 3 9” (CC .3. (cc 91 a! s S 1‘ 1: 2 7 an 35 1. 07/13/79 F7" ‘.66‘33 091:1 73/73 SUBROUYINE NORM 00°.) 0:19.300n5. °.rL ‘123‘593 ? 566666 666665 866655.629LJK.‘ IN,NHOU1,NCHNG,NDXSr,NHUY :YF UNNNV: 2 :NAJN 0.09 :76? .. 2R SCCRNM‘VNNVRF 166 07/13/79 '1! ‘.5“33 0P181 73/73 SUFRHU1INE If!" GKXYOSFREUFQXKJOP. a 17 7.4. 567... 9 11.. ..v, ,Ll7yLITELl7;IBiEHB ‘.662‘I:‘. 4. 65.666 ) 2 S 1 ( I R 1| X r. I \I) J.) 6?) 35 21‘ (1" RN, nlfll/ R? :1 .t014( I; O 1‘00.de a 03701. 0 S EPNN6 I I I "81.1.11 ‘1 1...» 15”,. Bataan I... o 1 61.8.UIO U‘NNII OZON 3‘ n UUD......:1=IJ)R Rn. "‘51). \I'IZIU 9...an 1.1-3" ('0 U0”0Rfl.(((00 "EN SCCCIDRRNCUXRK ‘fl 07/13/79 [1‘ ‘.6’£33 0r1=1 73/73 SUBPOUYINE EPILL .0000030090000000 $567.50. .. 171 l 5573? 989.838.9999? 99999 66665 65666666665 A8EL,LI8EL) ) ) L53 ,LIBEL,S) 1O 10) IL Kill. 0 .l: I 9:... (H l) \l E) E)X0 LII-.1 VII (OER L L “I. rain-l I__ .9 (1098 ((51. I I “Cuttlrl. EFMUIIAILL‘ .LE .t X10 :L((IIUE(U NVEchI‘EE-IGSEN .10” L7 L I. 9": R I E 'l USNNEW NV ONUOGS n9. REMM E ....U 8!.“ n. 10 .IU UIUUND. [N n. .\I (2. 1 1) .\ S 1 1 1.09 C051 A1 R63 15 18 PAGES IRINY. 730 LINES FRINY. $003159 5?:‘9 07/13/79 09