o . . " ‘ "' ' "I . .q n. o .u u 5- . not- .I... , . . . W‘"\I\Ififl.l"‘;t\ \" f“§'|!0.."‘ I_\I;'\"A.’II||\II.-.'..3...I .\».\ .. . ‘I‘ II-‘¢ -\c ' ‘5 .,‘v.',.'.......‘ .. . ‘—".- .' ....qJ‘.....(“-.-.I..‘-.o...A'~I.‘.\v I . ': o- - “- wo c-H‘v "-0-'-‘* - ""0. l.‘ . v ...‘A'. "'.“"'-I"“"" " " ‘ “ .. . . ..-b.-0‘ I ... ‘.'|n.' ... . '——— wry-".quv ...—cs... AN ALGORITHM FOR SEPARAI'ING UNIMODAL FUZZY SETS ON A GRID AND ITS APPLICATION TO OBJECT ISOLATION AND CLUSTERING Thesis for the Degree of M. S. MICHIGAN STATE UNIVERSITY ROBERT LEWIS WALTON 197 3- ‘1 Mithigm $153.6: W, University ,.. 9 Marianna-n. ' ' m a saw I BUUK amnm um. I LIBRARY BINDERS ' GPO‘IIL unsung ABSTRA CT AN ALGORITHM FOR SEPARATING UNIMODAL FUZZY SETS ON A GRID AND ITS APPLICATION TO OBJECT ISOLATION AND CLUSTERING BY Robert Lewis Walton The goal of object isolation is to separate a scene into ”regions of interest", each of which corresponds to an object or a portion of an ob- ject. The objective of this thesis is to develop a machine algorithm capable of isolating objects in an image plane. Such an algorithm can also be applied to the problem of clustering points in a feature space by treating a ”density function" of the points as the intensity function of a scene and then finding the "objects" present. These objects correspond to clusters. A basic approach to the object isolation problem was presented in terms of a clustering algorithm developed by Gitman and Levine[ 1]. Their algorithm is capable of separating a fuzzy set into unimodal re- gions and is capable of performing object isolation, provided each ob- ject can be made to correspond to a unimodal fuzzy set. Usually, if the input scene is preprocessed by low-pass filtering, each object can be made to correspond to one (or perhaps several) unimodal sets. Nor- mally, at least several hundred data points are required to represent Robert Lewis Walton the objects in a scene. If the assumption of a constant number of points per symmetric subset [l] is made, the computational requirements increase at least as rapidly as n2, where n is the number of data points. For a typical number of data points, the computational require- ments are too large to base a practical object isolation scheme on this algorithm. In addition, the algorithm has deficiencies related to equal- ly spaced points and points of equal magnitude. Several attempts are presented in this thesis for overcoming these deficiencies. As a result of these attempts, a new algorithm, the Uni- modal Tree Algorithm, was developed. This algorithm assumes that the data points lie on a uniform grid, which is usually the case when a scene is scanned. It has computational and storage requirements which increase linearly with the number of grid points. The regions the algor- ithm generates are proven to be unimodal, and the union of any two regions is shown to be non-unimodal. Furthermore, these unimodal regions may be of any shape. There is no dependence upon spherical or elliptical regions. Several experiments involving the Unimodal Tree Algorithm were performed. A scene containing three spheres and three ellipsoids was scanned and processed using the algorithm. The result was six regions, each of which contained one object. Another scene which was processed contained two touching ellipsoids. These objects were also separated. A third scene containing two mites in contact was run; three regions resulted. (One mite was light at both ends and darker in the center. I Robert Lewis Walton Several bivariate Gaussian point sets were run using the Unimodal Tree Algorithm as a clustering scheme (in conjunction with a routine to form a density function on a grid). Even severely overlapping Gaus- sian clusters were separated. A crescent-shaped cluster with a Gaus- sian cluster in its center was run to demonstrate the independence of the algorithm with respect to cluster shape. These examples were all run on a "mini-computer" (IBM 1800). Separation of a 25 x 25 scene into unimodal regions required about one minute of IBM 1800 time. A CDC 6500 (large computer) separated these same scenes in approxi- mately 1. 5 CPU seconds per scene. [ 1] Israel Gitman and Martin D. Levine, "An Algorithm for Detecting Unimodal Fuzzy Sets and Its Application as a Clustering Technique, ” IEEE Transactions on Computers, Vol. C-19, No. 7, pp. 583-593, July 1970. AN ALGORITHM FOR SEPARATING UNIMODAL FUZZY SETS ON A GRID AND ITS APPLICATION TO OBJECT ISOLATION AND CLUSTERING BY Robert Lewis Walton A. THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Electrical Engineering and Systems Science 1973 £21“ ACKNOWLEDGEMENTS I thank Dr. P. David Fisher for his invaluable help and suggestions during the writing of this thesis. The large amount of time he devoted to my instruction is greatly appreciated. The help of Dr. R. C. Dubes and Dr. John Kreer in proof reading the document is also greatly appre- ciated. I also thank my working wife, Marsha, for her help and support during the preparation of this thesis. Her understanding and sacrifices have been of great help. Finally, I thank Linda Swan for doing a fine job of typing the manu- script. ii TABLE OF CONTENTS ABSTRACT ACKNOWLEDGMENTS . LIST OF TABLES . LIST OF FIGURES I. II. III. IV. INTRODUCTION. . l.l Object Isolation Problem 1. 2 Machine Algorithm. . . l. 3 Objectives and Accomplishments of the Thesis. GITMAN AND LEVINE'S FUZZY SET SEPARATION ALGORITHM 2.1 Definitions. . . . . . . . . . 2 Gitman and Levine' 3 Algorithm 2. 1 Part One of Procedure F . . Z. 2 Part Two of Procedure F . 2. 3 Procedure 5. . . 3 The Subset Uniting Procedure PPNPP TWO APPROACHES TO THE UNIMODAL SUBSET SEPARATION PROBLEM FOR USE ON AN INTEGER GRID IN TWO DIMENSIONS . 3.1 Introduction . . The Diamond- Function Procedure The Potential Local Maxima Procedure . Conclusion and Maximal Unimodal Partitions www $00M THE UNIMODAL TREE ALGORITHM. . . . . . . . . . 1 Introduction . . . 2 Mathematical Preliminaries . 3 The Unimodal Tree Algorithm . . . . 4 Implementation of the Unimodal Tree Algorithm . 9‘??? APPLICATIONS OF THE UNIMODAL TREE ALGORITHM 5.1 ObjectIsolation. . . . . . . . . . . . . . . . iii ii l3 16 23 28 30 41 41 41 47 51 53 53 54 57 63 67 67 Object Isolation Examples . . . . . . . . . . . . 69 Clustering . . . . . . . . . . . . . . . . . . . 82 Experiments with Clustering . . . . . . . . . . 86 Application to Optimization . . . . . . . . . . . 99 U'lU1U'IU1 WIFUON VI. CONCLUSION....................lOO REFERENCES........................103 APPENDIX: FORTRAN LISTING OF THE UNIMODAL TREE ALGORITHM..................104 iv LIST OF TABLES Table Page 1: Distance to the Next Point Which Can be Added to a Symmetric FuzzySet........................43 Figure 10: ll: 12: l3: 14: 15: l6: 17: 18: LIST OF FIGURES Object Isolation in an Object Classification Scheme . Two Touching Ellipsoids . Symmetric and Non-Symmetric Fuzzy Sets Unimodal Fuzzy Sets Interior Points . Ambiguity in Definition of Interior Points Flowchart of Gitman and Levine's Algorithm . Flowchart of Part One of Procedure F. The Problem with Equal Distance Points The Problem with Equal-Magnitude Points Flowchart of Part Two of Procedure F. . Flat Regions Which are not Local Maxima . An Elliptical Flat Region Surrounded by Lower-Valued Points . . I Flowchart of Procedure S Illustration of Adj acency . Illustration of the Conditions of the Subset Uniting Procedure . . . . . Examples of Intensity Functions Mite Scene . . vi Page ll 12 l4 14 15 17 20 22 24 26 27 29 32 34 38 39 Figure 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: Symmetric Subsets on an Integer Grid . Contours of Constant Distance Using the Manhattan Metric . Crossing Connected Subsets Using an Extended Definition of Connectedness Flowchart of the Unimodal Tree Algorithm . Mite Scene Scanned Mite Scene 25 x 25 Grid of the Mite Scene Ellipsoid and Sphere Scenes. Two Touching Ellipsoids After Averaging Two Touching Ellipsoids as Separated by the Unimodal TreeAlgorithm.............. Six-Object Scene After Averaging . Six Objects Isolated by the Unimodal Tree Algorithm Mite Scene After Averaging . Mite Scene as Separated by the Unimodal Tree Algorithm Enhanced Mite Scene Input and Output A. "Smoothed" Mite Scene . B. Separation of "Smoothed" Mite Scene by the Unimodal Tree Algorithm. Bivariate Gaussian Clusters A. Four Well- Separated Gaussian Clusters, Unseparated. . . . . . . . . . Four Clusters of A, as generated . . Four Clusters of A, as separated by the Unimodal Tree Algorithm. . . . . . Two Overlapping Gaussian Clusters, Unseparated . Two Clusters of D, as Generated . Two Clusters of D, as Separated by the Unimodal Tree Algorithm . pun SPF vii Page 42 45 45 58 68 7O 71 72 74 75 76 77 78 79 80 81 87 88 89 90 91 92 Figure Page G. Two Elliptical Gaussian Clusters, Unseparated . . . 93 H. Two Elliptical Gaussian Clusters, as Generated . . . 94 I Two Elliptical Gaussian Clusters, as Separated by the Unimodal Tree Algorithm . . . . . . . . . . . 95 35: Gaussian "Ring-Type" Cluster A. Gaussian and Ring-Type Cluster, Unseparated . . . 96 B. Gaussian and Ring-Type Cluster, as Generated . . . 97 C. Gaussian and Ring-Type Cluster, as Separated by the Unimodal Tree Algorithm . . . . . . . . . . . 98 viii CHAPTER I INTRODUCTION 1. 1 Object Isolation Problem The process of classifying objects in an image using a machine may be divided into four steps (Nagy [8]): image enhancement, object isolation, feature extraction, and, finally, application of a decision scheme. Image enhancement is normally necessary as a pre-proces- sing step to put the raw input data into a suitable form for the steps which follow. Object isolation separates the image into regions con- taining one object or a portion of an object. This step will allow the “background" to be discarded, thus potentially saving much computer storage and computation later in the object classification procedure. The feature extraction procedure extracts information useful in classi- fying the objects, and the decision scheme determines the classification of each object. This object classification procedure is illustrated in Figure 1. Separating objects in a picture is a relatively simple procedure for the human mind. An example of such a problem is the separation of ellipsoids resting on a dark flat surface, as shown in Figure 2. A 'simple'machine algorithm to separate ellipsoids might not work pro- perly if the ellipsoids are of different size and orientations, or if some of them are touching. Complex algorithms to accomplish object 1 2 Figure 1: Object Isolation in an Object Classification Scheme START ) _L INPUT THE SCENE LL IMAGE ENHANCE- MENT LL OBJECT ISOLATION KW FEATURE XTRACTION _.L_ DECISION SCHEME Figure 2. Two Touching Ellipsoids. isolation under such adverse conditions may be very costly to Operate in terms of computational requirements and/ or storage requirements. 1. 2 Machine Algorithms A machine method applicable to object isolation has been suggested by Gitman and Levine [5] . The method they discuss is capable of sepa- rating touching ellipsoids, and is virtually unaffected by the size, shape, or orientation of the ellipsoids. Their algorithm separates an image into regions having only one "hill" in the intensity function (brightness level) of the wage. Such a partitioning yields the separation required for object isolation. Separating a scene into "unimodal" regions is useful in object iso- lation, but Gitman and Levine's algorithm has some deficiencies. The first deficiency is that special processing is required for equally- spaced sample points. When images are sampled on a grid of some sort, all the data requires special processing in the algorithm. The second deficiency is the special handling required by points of equal intensity- function value. If many such points occur, a large increase in compu- tation time will result. Equal-intensity points will occur many times in an image having only a few brightness quantization levels. 1. 3 Objectives and Accomplishments of the Thesis The primary objective of this thesis is to present an algorithm capable of partitioning a rectangular grid into regions which are uni- modal with reSpect to a function defined at each grid point, and to demon- strate its utility by performing several object isolation experiments 5 using the algorithm. Several pr0perties which are desirable for an ob- ject isolation algorithm to possess are the following: 1. The algorithm should be capable of detecting objects of gen- eral shape. 2. Objects should not be skipped or missed. 3. Each object should generate one region, with no spurious ”extra” regions due to quantization of the intensity function. 4. Computation and storage requirements should increase at most linearly with the number of grid points since a large number of points (500 or more) are usually needed to repre- sent the objects. The algorithm suggested by Gitman and Levine [5] is capable of generating the type of separation necessary for object isolation, but objects may be missed by the algorithm if they have a “flat peak” in intensity value. Also, the computation time required by Gitman and Levine's algorithm increases at least as fast as n2, where n is the num- ber of data points (assuming a constant number of points per symmetric subset). The amount of storage required for Gitman and Levine's algor- ithm is not fixed with respect to the number of data points due to a num- ber of variable-length lists which are formed. Storage requirements for these lists may be several times the number of grid points. Several modifications of this algorithm and some new ideas were introduced in an effort to obtain an algorithm possessing the above properties. The Subset Uniting Procedure was developed to eliminate the prob- lem of skipping objects with a "flat peak". This procedure replaces the last two steps of Gitman and Levine's algorithm, retaining only the first step. This procedure did eliminate the skipping of objects, but the com- putational requirements were still increasing rapidly with the number of points. Gitman and Levine's algorithm and the Subset Uniting Procedure are discussed in Chapter 11. Some simplifications of Gitman and Levine's algorithm as well as the Subset Uniting Procedure are possible when working on a grid, as is the case in object isolation. A simplification of the first part of Gitman and Levine's algorithm, called the Diamond-Function Procedure, was developed. The Subset Uniting Procedure simplifies very easily in the case of a grid, so it was not re-named. The Diamond-Function Proce- dure eliminates the need to compute and store the lists which are re- quired by Gitman and Levine's algorithm, which gives the Diamond- Function Procedure the property of having fixed storage requirements for a given number of data points. The problem Gitman and Levine's algorithm had with equal-distance points is also eliminated, but the problem of handling points of equal magnitude remains. Equal-magni- tude points are handled the same way in both procedures, so the Diamond- Function Procedure inherited the large amount of computation associated with the occurrence of significant numbers of equal-magnitude points in Gitman and Levine's algorithm. Another procedure, called the Potential Local Maxima Procedure, was developed. This procedure replaces the first part of Gitman and Levine's algorithm, and is applicable to a grid of data points. The second procedure of Gitman and Levine's algorithm is retained, but in a version which is simplified considerably because the data points lie on a grid. The Potential Local Maxima Procedure has storage requirements which are linear with the number of data points and computational re- quirements which increase at a rate slightly greater than a linear rate with the number of data points. This procedure, however, generates spurious regions when ”flat spots" occur in a scene, and is thus un- suitable for object isolation. The Diamond-Function Procedure and the Potential Local Maxima Procedure are described in Chapter 111. An algorithm which satisfied all four of the above criteria was develOped after a similarity between the Subset Uniting Procedure and the Potential Local Maxima Procedure was noticed. This algorithm is called the Unimodal Tree Algorithm. If each object can be made into a unimodal subset by properly enhancing the image, the Unimodal Tree Algorithm will generate one region for each object. The algorithm operates only on data in a grid. Both computational and storage require- ments are linear with the number of data points. Points of equal mag- nitude have no adverse affect on the performance of the algorithm. The Unimodal Tree Algorithm along with some statements about its perfor- mance will be presented in Chapter IV. Experiments using the Unimodal Tree Algorithm are presented in Chapter V. Object isolation was performed on three scenes, two of which contained ellipsoids and spheres in various orientations. One of these scenes contained two touching ellipsoids. The third scene was of two mites. The Unimodal Tree Algorithm was also applied to the prob— lem of clustering points in a space. Clustering experiments include the Fisher Iris Data [3], bivariate Gaussian clusters, and "ring"-type Gaussian clusters. The Unimodal Tree Algorithm provides a "fast" (computation and storage requirements are linear with the number of data and grid points) method of clustering large numbers of points into clusters of very general shape. Mention is also made of a possible app- lication in optimization of a function of several variables, but no experi- ments have been carried out in this area. CHAPTER 11 GITMAN AND LEVINE'S FUZZY SET SEPARATION ALGORITHNI 2. 1 Definitions Before describing Gitman and Levine's [5] algorithm, it is neces- sary to define several important terms required to properly understand the algorithm. The first concept needed is that of a fuzzy set. If X is a space of points with elements x eX, then "a fuzzy set A in X is char- acterized by a membership (characteristic) function fA(x) which associ- ates with each point in X a real number in the interval [0, 1], with the value fA(x) representing the 'grade of membership' of x in A". (Zadeh, [9]). There is no need to restrict the value of fA (x) to the unit interval in either Gitman and Levine's algorithm or in any of the algorithms pre- sented in this thesis. A finite interval of either the real or the integer line may be used instead. All the computer examples done in this the- sis use positive integers as the range of the function. Gitman and Levine denote by p a point where the maximum function Sup[fA(x)]. xGX value occurs in A; that is, fAm) = A point p, is called the mode of A. In order to define a symmetric fuzzy set and a unimodal fuzzy set, the following two subsets of X are defined: I‘xi = {x 3fA(x) .>_ fA(xi)} and I|xi,d = {x 3d(p,x) S d(p,, xi)}’ where 10 xi 55X and d(u, v) is a metric, or distance measure, between points u and v; TX is the set of points in X each of which have a function value i greater than the function value of xi; F is the set of points in X xi,d having distance from p. not greater than the distance from p, to xi. Note that the terms ”symmetric set" and "unimodal set" will be us ed instead of "symmetric fuzzy set" and "unimodal fuzzy set" when the context is clear. Definition: A fuzzy set A is symmetric if and only if, for every point xi 4X, I‘x. : Fx,, d' This definition says that moving closer to the mode and inc reasinlg in function value are synonymous in a sym- metric fuzzy set. (See Figure 3) Definition: A fuzzy set A is unimodal if and only if the set Fx. is connected for all xi 6 X. If a fuzzy set is split up into region(s) having a function value greater than u and at most one region results for all a in the range of the function associated with the fuzzy set, then the fuzzy set is unimodal, and visa-versa. (See Figure 4) When working with a computational algorithm, it is necessary to have a finite number of points in a discrete Space. Gitman and Levine denote a sample of N points from A by S 2 {(xi, fi)N}, where xi; X and fi is the function value corresponding to xi. A partition of S into m subsets, each with maximum function value pi, is denoted by {(Si, pi)m}. For a point xk 6 Si' let xt be defined by d(x , x = min [d(xk, xj )]; x is the closest point to xk not in Si. ) k xje(S- S) t 11 Figure 3: Symmetric Fuzzy Sets fA(X) A l I I I 9 I I I I I T ' I I ’ I 1 .1111 --—.-1I---Ir'--II-dr-I--I--'-1—- ' o I I I x xi .1 < I“Kiwi 9 fAIXI Figure 3A. ASymmetric Set. 1"x = x d i i, I: O f I I II? 1 I 9 l I l d I in —hpT—r_pi-—~-Tnhhg—p.T-p— -1.— I I I I I I I x x 1* 1 S rx,d > Figure 3B. Non-Symmetric Set. Fx { Tx- (1' because the "boxed" 19 points are in in but noti in 1"», d 1 12 Figure 4. Unimodal Fuzzy Sets a... O I“ o 1‘. ___..___ --.. 1.1_.__ o I0 0 I o o | o . C I x Figure 4A. A Unimodal Fuzzy Set. TX is connected. i 0.. a... 9 1" ___._o__ _.._. '-___I‘fiil:._ “...-1......1113 _____ :71.le o : :.' I 1 xi xj Figure 4B. Non- Unimodal Fuzzy Set. I‘xi is in two "pieces". Note the necessity for checking the connectedness of I‘Xi for every xi. I‘xj is connected, but the set is not unimodal. Figure 4 . A Unimodal (Left) and a Non -Unimodal Set in two dimen- sions shown by contour lines. The small arrows indicate the contour at the head of the arrow has a higher value than the contour at the tail of the arrow. 13 Definition: xk is an interior point of Si if the set {x3d(xt, x) < d(xt, xk)} includes at least one element of Si' In other words, 1% is an interior point of Si if there is another point in Si closer to Kt , the point closest to xk but not in 51' (See Figure 5) Note that there is an element of ambiguity in this definition of interior point. If two or more points outside Si are found to have the same minimum distance to xk, one of them might satisfy the criterion to make xk an interior point and the other one not. For example, con- sider the four points shown in Figure 6 with the indicated partition into S1 and 52' The distance between xt1 and xk is the same as the distance between xt and x , and is the minimum distance to xk for x f S 2 x is closer to x than xk is to xt , making xk an interior point by l k 1° 1 t1 x1 is not closer to xt than xk is, however, which makes 2 xk not an interior point of 51. Since a scene is ordinarily scanned on definitio n . some sort of a uniformly-spaced grid, some method of deciding if a point is to be considered interior or not interior in such a situation will be needed. This problem will be discussed later. Gitman and Levine do not treat this situation. 2. 2 Gitman and Levine's Algorithm The algorithm developed by Gitman and Levine consists of two parts: procedure F and procedure S. (See Figure 7) In procedure F, the local maxima of the fuzzy set are found. A local maximum in the continuum becomes a mode "1 of subset Si’ subject to certain criteria l4 Figure 5. Interior Points The interior points of S are ”barred". The nearest point in S to each "barred" point has anogher point in S closer to it than the "barred" point. The "unbarred" points in S are no interior points because they do not satisfy the definition of interior point. Figure 6. Ambiguity in Definition of Interior Points.- Is xk interior? 15 Figure 7. Flowchart of Gitman and Levine's Algorithm C START) __I__ Part 1 of Procedure F. Symmetric Partition is formed. L Part 2 of Proc. F Determine the local maxima L Procedure S Assign Data Points to groups. EXIT 16 on the sampling used (theorem 1 in Gitman and Levine). All of the 51's generated by procedure F are symmetric; pi is a local maximum if Iii is an interior point of 51' The criteria on the sampling reflect the fact that there must be a symmetric subset of radius 5 about each local max- imum in the continuum, that the points in the sampling must be spaced no further apart than c, and that local maxima must be sample points. In general, none of these conditions are known to hold, but they should be fairly well approximated for reasonable samples. Procedure S will be discus sed later. 2. 2.1 Part One of Procedure F Part one of procedure F requires generating a sequence A0 = (YI' yg, . . . ) of the points of the sample S in decreasing order of magnitude (assume for now that there are no points of equal magnitude). (See Figure 8). y? is the global maximum of the sample, y: is the next 1 l 2: Y3aoooIOf higher point, and so forth. Another sequence A1 = (yi, y points in S ordered by increasing distance from y? is generated (assume for now that no pair of points is the same distance apart as any other pair). The points in AC) shall all be inapected one at a time, in order, and assigned to a symmetric subset, or group. Assign the points of A0, in order, to group 1 until some r is found such that y: 7! yi, and y? '2' yil for 0 < i < r. (The notation "E" means here "is identically the same point”). When this situation occurs, the next point down in mag- . 0 . . . . n1tude (yr) 13 not the same as the next pomt out 1n distance (yi). Group one might not remain symmetric if y: was assigned to it, since there 17 - 0 0 0 FormlistA A0 : (Y11Y2.oo-.Yno) ordered by decreasing ma nitude 'r—‘———f Form list Ag of points by increasing distance from y?. Setj =1 A 8 % Set 1 to the group to which For noji the nearest é assigned neighbor of yCl has been _ assi ned. For one ii 4__j Assign y: to group i I Set Ji=Ji+l Set q=q+l No X Continue with part 2 of procedure F Figure 8. Flowchart of Part 1 of procedure F. There are N data points. This flowchart does not contain provision for equal-magnitude and equal-distance points. 18 is a closer point of lower magnitude. At this point group two is initiated by setting y: = y: and forming the sequence A of points ordered by 2 increasing distance from yf. The list A2 may be terminated when a point already assigned (Y?) 0 < i < r) is encountered. Future as sign- ment to group two would halt there anyway since the point can never be found in list Ao again. Now suppose that g groups have been initiated in the same manner as groups one and two were initiated above. There are g sequences Al’ A2, . . . , Ag, each of which has a candidate for assignment. These candidates are each denoted by yid where i is the group number, 0 < i S g. Suppose y: is the current point to be assigned in the A0 list (points y? for 0 < i < q have already been assigned). There are three cases: i) No identity between y: and y: for any group. ii) Equality between y: and y: for exactly one group. iii) Equality for more than one group. The action to be taken for each of these cases is as follows: Case i): Form group g + l with mode y?“ = y: and the sequence A . A consists of the points of the sample S in increasing dis- g+l g+l tance order from y?“ Increment g and q, determine which case (i, ii, or iii) is present, and continue. Case ii): Assign y: to the matching group, increment q, and con- tinue. Case iii): Assign y: to the matching group containing theassigned point closest to yg. 19 For an example of procedure F on a simple one-dimensional data set, see Gitman and Levine [5] . This procedure will always generate symmetric subsets. If, however, ambiguity enters into either the ordering of the points by magnitude or by distance, or by both, the procedure may generate many more symmetric subsets than are really necessary. To see why this happens, consider the case of three equally- spaced points of different magnitude. (See Figure 9). The points will be ordered by magnitude correctly, but when the points are subsequently ordered by distance, the second and third points could be placed either way. One way will match up with the ordering in A0 and the other way will not. If the lists do not match, another group will be formed, and the distance ordering for this group will also be ambiguous. If one choice is made, the mode of group one will be found, and the AZ list will be terminated. If the other choice is made, the remaining point will become the next candidate for group two. This point will be as sign- able to either group one or two, but the rule for case iii) will not tell which. In such a case, assignment is arbitrary. Part one of procedure F may generate either one or two symmetric subsets in this simple example. In addition the procedure will enable the generation of a minimum number of symmetric subsets in the case of distance equality. Simply re-order all the equal-distance points in each of the lists Al' A2, . . . , so that the order of these points is the same as their order in the A0 list. Points having equal magnitude also cause the generation of more 20 Figure 9. The Problem With Equal-Distance Points = 2 A0 (1. .3) I Al may be arbitrarily formed in either of two ways: A1 = (1, 2, 3) l l y = l»group l y: = 2»group l y; = 3->group l 15' = (1.3.2) 1 = yl=1»group l f y; :5 form group 2. A may now be formed as either: 2 : I : A2 (2,1, 3) or A2 (2, 3,1) 2 0 = y1 ._..., 2+group 2 y2 = y; :9 2->group 2 l 0 l 0 Z . = y2 = 3+group l y3 = y2 and y3 = y2 g 3+e1ther group 1 or group 2. (Assignment to group 1 or group 2 is arbitrary since the distance to the nearest assigned neighbor is a tie. ) 21 symmetric subsets than necessary. For example, consider three points having the same function value, but separated by different dis- tances. (See Figure 10) An arbitrary ordering is selected for the Ao list, and the A list is generated unambiguously. The second element 1 of the two lists may match or not match, arbitrarily. Either one or two symmetric subsets may result. It is desirable to generate a small number of symmetric subsets for three reasons. First, the initiation of each subset requires the compu- tation and ordering of distances between the mode of the new subset and some of the data points (data points at a distance further than the mini- mum distance from the mode to points already assigned need not be con- sidered). Minimizing the number of subsets will reduce this computation. Secondly, each time a point is assigned to a group, all the groups must be searched for a candidate point identical to the point being assigned. Reduction of the number of groups will also reduce the computation for this search. A third reason is that a local maximum may be missed if the symmetric set around it is terminated prematurely. A modification of case i) may be made which enables the procedure to generate a smaller number of symmetric subsets in the case of equality in function values. If no matching points are formed as in case i), continue the search using the points which have the same mag- nitude as the first point. Initiate a new group only when none of these equal-magnitude points satisfy either case ii) or case iii). Note that if equal distance points are present, the equal-distance points in each of 22 2 = y 2 O 1=y 3=y3 O l .4 4 Figure 10. The Problem with Equal-Magnitude Points. Six cases exist for the possible orderings of A A0 = (l. 2. 3) A1 = (l, 2, 3) l->g roup 1 2->g roup 1 3+g roup 1 A0 A1 2»g roup 1 A2 = (3. 2. 1) 3->group 2 l->group 1 (2.3.1) (2.1. 3) A0 = (l, 3, 2) A1 = (l, 2, 3) l ->g roup 1 A2 = (3, 2,1) 3»group 2 Z-rg roup 1 A0 A1 3->g roup 1 A2 = (1: z: 3) l-g roup 2 2->g roup 2 (3.1. 2) (3. 2.1) 0. A0 = (2.1. 3) A1 = (2,1,3) 2»group l l-egroup l 3->group 1 A0 = (3, 2,1) A1 = (3, 2,1) 3->group l 2»group 1 l-vgroup l 23 the Ai lists will have to be either re-ordered or searched for equality during this procedure. 2. 2. 2 Part Two of Procedure F Part two of Procedure F uses the symmetric partition generated by part one as input and determines the local maxima of the sample function. (See Figure 11). The procedure is as follows: if “i is an interior point of Si' then pi is a local maximum; otherwise, it is not. This test is performed for each Si in the symmetric partition. In other words, determine the minimum distance from pi to the points not in 81' Call the point where this minimum distance occurs xt , and assume xt is i i unique for now. pi is a local maximum if there is a point in Si which has distance from Kt less than the distance from “'1 to xt . Otherwise, i i pi is not an interior point of Si’ and hence is not a local maximum. Note that part two of Procedure F has two inherent problems. First is the problem in the definition of interior point which was men- tioned earlier. The problem of a non-unique xt may be resolved three 1 ways: 1) the mode is interior only if all xt satisfy the condition, 1 2) the mode is interior if any x satisfies the condition, or 3) the t. 1 mode is interior if an arbitrary one of the xt satisfies the condition i for the mode to be an interior point. The third scheme was used in the implementation of Gitman and Levine's algorithm which was used for this thesis. The second problem associated with part two of Procedure F is the occurrence of non-unique p, in S, for one or more groups. The problem 1 1 24 Figure 11. Part 2 of Procedure F. Part 1 of Procedure F I Xt = point having minimum distance between pi and xsx C S - Si there any x q Sin (x, xt)< A Continue with procedure S 25 arises because an arbitrary one of these equal-magnitude points was selected as the mode of the symmetric set. If this mode is surrounded by points of equal magnitude, it will be classified as a local maximum even if this flat region is not a local maximum at all. An example of such a flat spot is a level region on the side of a hill, as shown in Figure 12. To prevent such a flat region from generating any local maxima Gitman and Levine offered the following suggestion: "To solve this problem, we have modified part two of procedure F (in which a search for the local maxima is performed) in the following way. Let 811 be the subset of points in Si which have the same (maximal) grade of membership as pi; then every point in Sii is examined as the mode of Si' If at least one of these points is on the boundary of Si’ then I‘I’i is not considered as a local maximum. " Many counter-examples exist to this solution. Consider the case of an elliptical flat region in two- dimensional Euclidean space surrounded by lower values decreasing with increasing distance from the edge of the flat region, (See Figure 13) Part one of procedure F will pick an arbitrary one of these points in the flat spot as the global maximum and start the first symmetric group with it. The first group will be extended until a point in the distance list Al but not in the flat region is encountered. Another group will start on the flat region at a point of the flat region not in the first group. Such a point will exist because there will be points in the ellipse not included in the disk-shaped symmetric first group. This group will grow until it hits either the edge of the flat region or the first group, 26 Figure 12. Flat Regions Which are not Local Maxima 27 // M Figure 13. An Elliptical Flat Region Surrounded by Lower-valued Points. I 28 whereupon another group will be started. This process will continue until the flat region is covered by symmetric groups. Group one and other groups which hit the edge of the flat spot may be extended by a point or two, and new groups will be initiated to cover the sides of the ”butte". Now consider the first subset. There will be points along its edge which are in the flat spot but are not interior points. The same observation will hold for boundary points in each group having points in the flat region. The result is that this region will be missed as a local maximum. The only way this flat region could be kept as a local maximum would be to include the entire flat region and some of the sur- rounding area in a symmetric subset. In object isolation the problem with missing flat local maxima described above is intolerable. The intensity function is normally quan- tized, perhaps into only a few levels. Occurrences of flat regions which are local maxima will be a common situation in such images. A pro- cedure for correctly handling the case of non-unique modal values is mandatory if object isolation is to be performed. Such a procedure will be discussed after procedure S is described. 2. 2. 3 ProceduregS Using the local maxima generated by procedure F as input, proce- dure S partitions the sample S into unimodal regions. Points which are not local maxima are assigned in the order in which they appear in se- quence A0. (See Figure 14). Each local maximum will start a new uni- modal group. The procedure is as follows: Assign the point y? (in 29 Figure 14. Flowchart of Procedure S. Mj is the jth local maximum. Part two of procedure F Start group j. Assign y? to group j. Set j=j+1 Assign y? to the group to which the nearest higher A neighbor of yio belongs S. 30 location j of sequence A0) to the group in which its nearest neighbor with a higher function value has been assigned, except for the local maxima. When a local maximum is encountered, start a new group. "Higher function value" and "previously assigned” are synonymous in this pro- cedure because of the decreasing-magnitude order of assignment. Gitman and Levine prove a theorem which states that procedure S may be replaced by a procedure which unites the symmetric subsets to form unimodal groups if the maximum diameter of a disk in the contin- uum containing no sample points shrinks to zero. (Theorem three in Gitman and Levine). Furthermore, they point out that if this uniting procedure is used, procedure S reduces to an automatic classification of the points, providing that for each mode the nearest point with a higher grade of membership is recorded during part one of procedure F. The procedure involved is to assign all the points in each subset whose mode is not a local maxima to the group to which the nearest higher neighbor to the mode of this subset was assigned. Assignment is done by decreasing order of modal value for all the subsets. The points in each subset containing a local maximum start a new group. This pro- cedure suggests a similar procedure which replaces part two of proce- dure F and procedure S. 2. 3 The Subset UnitinngroEedureg Since the data points can be assigned by selectively uniting symmet- ric subsets, it should be possible to obtain a similar assignment of the points by using a different rule for uniting these subsets. A requirement 31 for uniting two subsets is that the subsets be "adjacent" to one another. A definition of adjacent symmetric subsets which satisfies the idea of adjacency follows. Definition: Let zij be the closest point (in case of ties in close- ness, the highest of the closest points) in Si to any point in Si, and let zji be the closest point (or the highest of the closest points) in Sj to any point in Si’ where Si and Sj are symmetric subsets. Si and Sj are adjacent if d(z, , 2,.) 5 max [d(zij' w), d(zji' w)], where d(u, v) is a w ES - (S,US,) 1 J metric function between points u and v. (See Figure 15). This inequality has been termed the ultrametric inequality (Johnson [7]). Assume i < j. Then pi 2 “j from part one of procedure F. The following conditions must hold for Si and Sj to be united in order to maintain a unimodal set as the result of this union and of previous unions which may have been made using Si and Sj' and the subsets united to them: a) Si and Sj must be adjacent. b) zji and “j must have the same value. c) The value of zij must be no less than that of zji' d) pi and ”j must have magnitude not less than the magnitude of the mode of any of the subsets with which Si or Sj' respectively, has been united with in the past. The order in which these subset pairs are checked to see if they 32 m Figure 15. Illustration of Adjacency The circled points are the points in each symmetric subset S and S2 closest to the mode of the other subset of the pair. If no points in S - (S US )fall in the shaded region, S and S are adjacent. Other- wise, S1 and S2 are not adjacent. l 2 33 can be united is as follows: First try the pair (51’ SZ)’ then (51’ S3), (81' S4), and so forth to (SI, Sg). Then (52, S3) are checked, then (S S4), and so forth, until the pair (Sg Sg) has been checked. The 2' -l' fact that checks b), c), and d) above are needed is verified in Figure 16. When groups are united, it is not necessary to recall all the previous unions these groups have experienced, as requirement d) would indi- cate. Rather, a flag may be associated with each subset, and set if its subset is united with another subset having a higher modal value. Two subsets may not be united if both flags are set. The above procedure will be termed the "Subset Uniting Procedure". Note that since a single point is a symmetric subset, the Subset Uniting Procedure is applicable to the data points individually before part one of procedure F separates them into symmetric subsets. The Subset Uniting Procedure requires Mi)- adjacency tests for g subsets. If each point 2 is considered as a subset in this procedure, and there are n points, n(n-l) 2 adjacency tests are performed. If each symmetric subset re- sulting from part one of procedure F has about k points in it, then g g n/k. The ratio of the number of adjacency tests necessary if pro- cedure F is not used to the number required if procedure F is used is .. Z - then about AIL-L) r k 11—1-2, or approximately k2 for n much larger 2(2 - 1) (“'k' k k than k. Use of part one of procedure F will thus reduce the number of adjacency tests required for the Subset Uniting Procedure. Each adja- cency test requires substituting each of the points not in either subset 34 Figure 16. Illustration of the Conditions of the Subset Uniting Procedure Each connected set of dots is a symmetric subset. Subsets are num- bered by decreasing value of their mode. Dashed lines indicate previously united subsets. A “:x. A z 31 Case a). l and 2 may not be united because they are not adjacent. If they were united, the result would not be unimodal because the union of l and Z is not connected. Case b). l and 3 may not be united because the value of z is not the same as the value of 113. 2 and 3 may not be united for the same reason. I Z 245 54 Case c). 4 and 5 may not be united because 245 < 254. Case d). 6 is united with 9 and 7 is united with 8. If 8 and 9 are united (they satisfy conditions a), b), and c)), the result is not unimodal. 35 being tested into the ultrametric inequality until either a violation of adjacency is found or all the points are checked. The amount of com- putation involved in an adjacency test is relatively independent of the size of the two subsets. About 11 -2k substitutions into the ultra-metric inequality are required if procedure F is used, and n-2 are required if procedure F is not used, in the ”worst case" where the subsets are adjacent. In the case of a pair of subsets, each of size k, the closest point in each subset to the mode of the other must be found. This oper- ation will require 2k comparisons. These 2k comparisons may be con- sidered to roughly "make up for" the Zk-Z substitutions into the ultra- metric inequality saved when the two k-point subsets are tested for adjacency. Thus, using part one of procedure F to generate subsets containing about k points apiece will reduce the computation involved in the Subset Uniting Procedure by about a factor of k2. The amount of computation involved in part one of procedure F can vary quite a bit depending upon the number of points of equal magnitude which occur. Two major computational operations are involved. First is the ordering of points by magnitude, which occurs only once, and the ordering of points by distance from each mode, which occurs g times. An ordering algorithm called TREEUP was used [2, 4]. Bertziss [2] claims the worst case computation requirements for TREEUP are ap- proximately 2N(logzN - l) comparisons and N(logzN - 1) interchanges. g + 1 orderings must be made, but not all of them involve all 11 data points. Additional ordering is necessary if points of equal distance to 36 some modes are present. The second computational operation involved in part one of proce- dure F is the actual assignment of points. If points of equal magnitude are not present, g comparisons of yq (the point to be assigned) and y: (the current candidate point for each group) must be made. Furthermore, the closest neighbor point which has already been assigned must be found if more than one match exists between yq and the y:. In the case of equal-magnitude function values, many successive points may have to be checked before assignment can be made or a new group can be initiated. For example, consider thirty points of equal magnitude and twenty groups. If yq is the first of these thirty points and yq cannot be assigned to any of the twenty groups, then 600 comparisons will have to be made. If the next point cannot be assigned to any of the twenty old groups or the group just formed from the first of the equal-magnitude points, 609 more comparisons will be made, and so forth. The storage requirements of part one of procedure F are not fixed for a given number of points. In addition to the storage required for the A . 1,..., g 9 ABIo-ooAg function value of each point is the storage for lists A0, A The lengths of A0 and A1 are fixed at 11, but the lengths of A2 vary depending upon the number of points which can possibly be included in each subset. Gitman and Levine state that 5n storage locations were usually sufficient for the lists A0, A , 1 2. . . . , and A in their work. In addition, auxiliary working storage arrays are required during ordering and to hold computed distances. 7n locations were found to be 37 sufficient for these arrays. The computational requirements of part two of procedure F and of procedure S will not be discussed because local maxima may be missed using these procedures. The use of part one of ProcedureF and the Subset Uniting Procedure requires so much computation for the large number of points encountered in an object isolation problem that the use of these procedures for object isolation is impractical on even the fastest computers. Several special functions defined on a 10 x 10 grid were run on the M.S. U. CDC 6500 computer using FORTRAN EXTENDED for a pro- gramming language. These 10 x 10 functions included a crescent- shaped unimodal region and several simpler cases (see Figure 17). The average execution time for these 10 x 10 scenes was about 5 central- processor seconds. When the number of data points was expanded to 484 (a 22 x 22 scene of two mites: see Figure 18), the central processor time increased to 197 seconds. All the groups generated in each trial case were unimodal. The cost associated with using part one of procedure F and the Subset Uniting Procedure in an object isolation scheme is rather high, eSpecially when the object isolation scheme is viewed as part of a pro- cedure to identify objects in a scene, as discussed in Chapter 1. Even when using a computer as powerful as the CDC 6500, only about 20 scenes per central-processor hour can be processed (assuming the rate of one scene every three minutes is valid). Two attempts at obtaining 9 IT.) 6 5 2 9 I I 3’ 9 ‘1 t 7 9 9 II 6 9 I) 7 n 7 .9 9 0 9 9 9 8 I 7 II 3 7 6 6 l f t, 7 7 6 7 7 6 I 7 7 I 8 8 7 8 8 7 7 7 C 6 G 6 6 6 Figure 17. L4 7‘.) 6 6 Examples of Intensity Functions 1‘s) 1“; \7 38 f-J I“) LO L0 03 e0 9 U4 £31 VJ b1 10 \4'1 L1 \1 (I L) 7‘.) OJ :3 7‘0 C3 1! U4 U1 l5] (’3 \N ‘4 pa UJ PO {“3 39 Figure 18. Mite Scene. 40 a faster method for object isolation in a scene sampled on a rectangular grid are discussed in Chapter III. Each of these algorithms has serious drawbacks. An algorithm which effectively overcomes the deficiency of large computational requirements and still exhibits the properties re— quired for object isolation will be discussed in Chapter IV. CHAPTER III TWO APPROACHES TO THE UNIMODAL SUBSET SEPARATION PROBLEM FOR USE ON AN INTEGER GRID IN TWO DIMENSIONS 3 . 1 Int rod uction Part one of procedure F with the Subset Uniting Procedure provides the type of separation required for object isolation. As discussed at the end of the last chapter, this method of separating unimodal subsets defined on an integer grid is not practical for object isolation problems because of the method's computational requirements. Two approaches to the problem of obtaining an algorithm which accomplishes the same results but requires less computation are presented in this chapter. Both approaches make use of the known location and ordering of points in a grid. 3. 2 The Diamond—Function Procedure The first approach is to replace part one of procedure F by another procedure which utilizes the information contained in the location and order of points on a grid. It was noted that on an integer grid, the dis- tance from the mode of a symmetric subset to the next point which can be added to that subset is a function of the number of points already in the symmetric subset, as illustrated in Figure 19 and tabulated in Table 1. Furthermore, note that if the Manhattan metric is used, this 41 42 XEX x x o o e o g e o e e 0 e e e o . e e e e o O Figure 19. Symmetric Subsets on an Integer Grid There are 10 points in the x-ed symmetric set. The next point which can be added is at distance 2 (using the Manhattan metric). There are three such points. This distance may be determined from the in- equality 2d(d +1): n > 2d(d -1). 2d(d +1)?- 10 > 2d(d - 1) implies d = 2, giving 12 210 > 4. 43 Table 1. Distance to the Next Point Which Can be Added to a Symmetric Fuzzy Set. EUCLIDEAN MANHATTAN DISTANCE DISTANCE lWUNflIERJDF TOWTHIINIDCT NTHABEEICH? TC>THE3NEDFT POINTS IN ADDABLE POINTS IN ADDABLE SUBSET POIN T SUBSET POIN T 0- 0 0.000 0- 0 0 1- 0 1.000 1- k 1 5- 8 1.910 5- 12 2 9- 12 2.000 13- 2h 3 13- 20 2.236 25- 00 h 21- 2h 2.828 MI- 60 5 25- 28 3.000 61- 80 C 29- 36 3.162 85- 112 7 37- hh 3.605 113- lhh 6 b5- h8 h.000 1h5- 180 9 09- 56 0.123 181- 220 10 57- 60 h.2h2 221- 26h 11 61- 68 h.h72 265- 312 12 69- 80 5.000 313- 36h 13 81- 88 5.099 365- #20 1h 89- 96 5.385 h21- N80 15 97-100 5.656 681- Shh 16 101-108 5.830 ShS- 612 17 109-112 6.000 613- 68h 18 113-120 6.082 685- 760 19 121-128 6.32“ 761- 890 20 129-136 6.003 3&1- 92k 21 137-1hh 6.708 925-1012 22 195-108 7.000 1013-110h 23 1&9-160 7.071 1165-1200 20 161-168 7.211 1201-1300 2 169-176 7.280 1301-1h0h 26 177-18h 7.615 1&05-1512 27 185-192 7.810 1513-162h 28 193-196 8.000 1625-17h0 29 197-212 8.062 1791-1860 30 213-220 3.206 1861-1980 31 221-22h 8.h85 1985-2112 32 225-232 8.5hh 2113-2290 33 233-2h0 8.602 22h5-2380 3h 44 functional relationship between the number of points in a subset and the distance from the mode of the subset to the next addable point is par-. ticularly simple. This relationship may be derived by noting that the number of points at distance d from the mode of a subset is 4d using the Manhattan metric, for d greater than zero and d an integer (only integer distances occur), as shown in Figure 20. The number of points at a distance not greater than d from a mode (excluding the mode itself) is then 2634i = 2d(d + 1). Thus, for a subset having 11 points (including the rriSde), the distance from the mode to the next addable point is a number (1 such that 2d(d +1) 2 n > 2d(d - 1). This relationship may be used in part one of procedure F to deter- mine if the point to be assigned from the A list, yg, is assignable to 0 any of the existing groups by simply seeing if the distance from yq to the mode of each subset is the same as the distance to the next addable point of the subset. It is known that n :5 2d(d + 1) because yq has not been assigned, and it is necessary only to test if d, the distance between yq and the mode of the subset, satisfies the inequality n > 2d (d - 1). If so, yq may be assigned to this subset; otherwise, it may not. This pro- cedure is called the Diamond—function Procedure. The Diamond-function Procedure eliminates the need to compute and store the lists A , A 1 2, A3, etc. , which gives the Diamond-function Pro- cedure the property of having fixed storage requirements for a given number of data points. The problem Gitman and Levine's algorithm had with equal-distance points is also eliminated, but the problem of handling 45 Figure 20. Contours of Constant Distance Using the Manhattan Metric. Figure 21. Crossing Connected Subsets Using an Extended Definition of Connectedness. x x x + + + x X x + + + x x X + + + + + + X X X + + + x X x + + + x x x Both the x-ed and the +-ed sets are connected using an extended definition of connectedness. 46 points of equal magnitude remains. The method of processing these points is the same as in part one of procedure F. The computational considerations are also the same, except that a simple comparison of two points to see if they are identical is replaced by a distance compu- tation, the computation of 2d(d - l), and a numerical comparison to 11. Since the Diamond-function Procedure replaces part one of pro- cedure F, either part two of procedure F followed by procedure 5 or the Subset Uniting Procedure may be used to complete the separation into unimodal subsets. The use of part two of procedure F and procedure S will not be discussed at length because flat regions which are local maxi- ma may be missed by part two of procedure F. It should be noted that both part two of procedure F and procedure S can be simplified if the data points lie on a grid. The Subset Uniting Procedure may also be simplified when the data points form a grid. The simplification is accomplished by noting that two subsets on a grid are adjacent if there is a point in one subset at a distance of one from some point in the other subset. This simplification in the Subset Uniting Procedure results in reduced computational re- quirements for each adjacency test, because it is no longer necessary to check all the points not in either subset for each adjacency test. The amount of computation still increases rapidly with an increasing number of symmetric subsets, however, because the required number of adja- cency tests (gig—5:12) remains the same. Doubling the number of sub- sets increases the number of adjacency tests by almost a factor of four, 47 an increase which leads to an unacceptable amount of computation for large numbers of subsets. 3. 3 The Potential Local MaximaProcedure The second approach taken toward the problem of reducing the amount of computation while maintaining the ability to separate a fuzzy set into unimodal subsets is described here. This procedure replaces procedure F while Procedure S is retained intact. The neighbor points, or simply neighbors, of a point are all those points at a distance of one from a particular point, using either the Euclidean or the Manhattan metric. Note that if the case of equal-magnitude points is excluded, a local maximum occurs at every point which has lower values at all four neighbor points. All the local maxima can be found by comparing each point with its neighbor points. If all the neighbor points have a lower value, a point is a local maximum. Otherwise, it is not. This proce- dure can replace procedure F, because both procedures do nothing more than find the local maxima. The computation requirements for the above procedure are fixed and are very low compared to the requirements for procedure F. Less than 4n magnitude comparisons need be performed to determine the local maxima, since the checking of the neighbors of each point which is not a local maximum can be terminated as soon as a higher neighbor is found. Also, the points on the edges of the grid will have fewer than four neighbor points. Doubling the number of points will roughly double the amount of computation. Procedure S simplifies considerably in the case of a grid. Each 48 point is either a local maximum, which causes a new group to be gen- erated, or it has a higher neighbor which has already been assigned to a group, due to the decreasing-magnitude order of assignment used in procedure 5. Each point with a higher neighbor is assigned to the same group as was the highest of these neighbors. This local-maxima procedure must be modified to handle the case of equal-magnitude points, because flat regions which are local maxima will be missed. The modification required is not as simple as requiring that a point is a local maxima only if none of its neighbors are higher, because that would generate many local maxima from each flat region. Many more unimodal groups than necessary would result. The interior points of each flat Spot would each become a one-point unimodal region, and the property of generating one unimodal subset for each local maxi- mum would be lost. To avoid this, it is necessary to label each point having no higher neighbor as a "potential" local maxima. Once all the potential local maxima have been found, a search for flat regions can be initiated with an arbitrary one of these potential local maximum points. Two potential local maximum points are M if it is possible to step from one to the other through pairs of potential maximum points which are neighbors of each other. All the potential local maxima which are linked to the starting point are invalidated as local maxima and assigned to the same group as the starting point. The starting point is considered to be the mode of the group. This procedure is repeated using an unassigned local maximum point as the starting point each time until 49 all the potential local maxima have been assigned. Each flat region will generate only one mode in this procedure, since the potential max- ima in a flat region will all be linked to each other. Procedure S will remain the same as it was for the case of no equal-magnitude points. Ties in the case of the highest-magnitude neighbor of each unassigned point may be resolved arbitrarily. The procedure described here, in- cluding procedure S, will be called the Potential Local Maxima Pro- cedure. Note that not all of the unimodal subsets gene rated by the Potential Local Maxima Procedure actually correspond to local maxima, since a flat region on the side of a "hill" (or at the bottom of a ”valley") will generate potential local maximum points. One of these potential local maxima will become the mode of a group which does not contain a local maximum. The potential Local Maxima Procedure is thus not appli- cable to object isolation problems. A scene which is quantized into only a few intensity levels will contain "bands" of equal-intensity points. Each band will generate extra unimodal regions. This will decimate each object into small meaningless regions, instead of isolating each object as desired. Before leaving the Potential Maxima Procedure, an interesting extension of this procedure will be discussed. It was noted that occa- sionally three equal—magnitude diagonally-positioned grid points with lower-valued points around them would cause the generation of three unimodal subsets, with any of the procedures previously discussed. A 50 question arises as to whether each of these three points generate their own unimodal set or "hill", or if they form a "ridge" as one unimodal subset. If no information is available about the continuous function from which the grid sample was made (or if there is no such function), this question would appear to be mostly a matter of individual preference and which result is desired. If the function values are sample points from a continuum, an increase in the resolution of the sample is probably indi- cated. The manner in which the above question is interpreted is that the formation of symmetric subsets indirectly reflects upon the definition of connectedness in the definition of unimodal set. Gitman and Levine never directly mention anything about their concept of connectedness in a discrete point set. If the concept of "neighbor" point is extended to include the eight points closest to a particular point using the Euclidean metric, then the above would classify the three equal-magnitude diagonally-positioned points as one unimodal subs et, providing that the definition of connectedness of the discrete grid is modified to accomodate such sets as being unimodal. Such a definition of connectedness is not particularly intuitively appealing because two connected subsets can cross each other, as shown in Figure 21. If the above idea is used, another problem has been created. Sup- pose three points are diagonally situated as above and that all three are potential local maxima, but not of the same function value. Three cases exist: when the center point is highest, when it is lowest, and when it 51 is in-between the value of the end two points. In the first and last cases, one unimodal subset should be created, but in the second case, two sub- sets must be generated. This suggests the necessity of adding a little to the algorithm to prevent all three points from being included in one subset in the second case. By using somewhat the same idea as was used in the Subset Uniting Procedure, the following additions will accomplish the desired result: Consider all the points having no higher neighbor (including diagonal neighbors) as potential local maximm Start each group with the highest unassigned potential local maximum point. A link from one local maxi- mum to another may be performed only if the value of the second is not greater than the value of the first. A slightly more general procedure may be started from an arbitrary unassigned potential local maximum point by specifying that the second point of a link may be greater than the first point only if the magnitude of the first point is the maximum magnitude which has been encountered so far in the formation of the cur- rent group. 3. 4 Conclusion and Maximal Unimodal Partitions The Diamond-function Procedure is theoretically applicable to ob- ject isolation, but in practice, the large amount of computation required when many points of equal magnitude exist (which was inherited from part one of Procedure F) makes the algorithm impractical. The P0- tential Local Maximum Procedure reduces the computational require- ments to slightly more than linear with the number of data points 52 (N log (N - 1) operations are required for the initial magnitude ordering, and the rest of the procedure is linear), thus basically satisfying the linear computational requirement for an object isolation algorithm. The Potential Local Maxima procedure and the extension of it discussed above have not accomplished anything of interest to object isolation since they cause the separation of flat regions when they should not be separated. A procedure very similar to the procedure used in the ex- tension will be the subject of Chapter IV. Before proceeding to Chapter IV, the concept of a maximal unimodal partition will be discussed. An obvious unimodal partition for any dis- crete set is to consider each point as a unimodal subset. It is equally obvious that there is a ”better" partition; that is, a partition with fewer subsets. By combining two of the closest points into one two-element subset, one less unimodal subset will result. In this sense, there should be a ”best" unimodal partition in which the union of any two of the unimodal subsets of the partition is not unimodal. In most discrete fuzzy sets, there will be many such partitions, any of which shall be termed a "maximal unimodal partition". One unimodal subset will exist for each local maximum in the data set. The number of subsets in any maximal unimodal partition is fixed for a given data set. The property of always generating a maximal unimodal partition is a desir- able property for a unimodal subset separation algorithm to possess. The lack of this property was seen to make the Potential Local Maxima Procedure unusable for object isolation. CHAPTER IV THE UNIMODAL TREE ALGORITHM 4. 1 Introduction Part one of procedure F, the Diamond-function Procedure and the Subset Uniting Procedure all exhibit computational requirements which increase at a rate significantly greater than a linear rate with the num- ber of data points, as discussed previously. For this reason, these procedures are not particularly applicable to the object isolation prob- lem. The Potential Local Maximum Procedure generates spurious separations when equal-magnitude points are present, and is therefore not applicable to object isolation. Part two of procedure F will miss most local maxima which consist of more than one equal-magnitude point, and two objects may not be separated. For this reason, any algorithm which uses part two of procedure F will not be well suited to object isolation. In this chapter, an algorithm which is applicable to object isolation will be presented. This algorithm was developed after a similarity between the Subset Uniting Procedure and the extension of the Potential Local Maxima Procedure was noted. Several definitions and a theorem which are needed to properly understand this algorithm will now be presented. 53 54 4. 2 Mathematical Preliminaries Consider a finite n-dimensional grid of points S with integer grid coordinates and a fuzzy set F in S with function value f. (5 together with F may be considered to be a sample from a continuum if desired. If so, the integer grid points need not match with the coordinate system of the continuum. The entire grid may be rotated, scaled, translated, or otherwise transformed with respect to the coordinate system of the continuum. The origin of the integer grid is immaterial to the algorithm. ) Let G be a graph having the set of all points in S as its vertex set and having one edge between points in each pair (ai, bi) satisfying 0 < d(ai, bi) S R, where d(ai, bi) is a metric, R is a constant, and ai and bi are points in S. Definition: Two disjoint subsets Si and Sj of S are said to be connected if there is exactly one edge of G between some element of Si and some element of Si. If R = l and a Euclidean metric is used in the definition of G, this definition corresponds to the intuitive notion of connectedness. If R 2 42, this intuitive idea of connectedness may be violated by al- lowing connected subsets to cross each other in two dimensions. (See Figure 21). Let Sij be a subset of Si' Sij : {x3f(x) Z f(xj)} for any xj in Si° Definition: A unimodal fuzzy subset Fi exists in Si if and only if the set 81’ is connected for all xj in Si' (Fi has the same function value, f, as did F). Definition: A partition of a set S is an assignment of each element 55 k ofSto one of thek subsets Si inamanner such that kJSi = Sand i=1 SmSj = ¢foralli,j=1,2,...,k, i 7! j. 1 Definition: A partition of S is a maximal unimodal Rartition of S if the partition separates S into k subsets 81’ i = 1, 2, . . . , k, each of which is unimodal, and if SiU Sj is not a unimodal subset for any i 7’ j, i, j=1, 2, . . . , k. An endpoint of a graph is a vertex incident to at most one edge of the graph. A SEES. is a connected. graph containing no subgraph having no endpoints. A path is a tree with two endpoints. In a connected graph, the graphical distance between vertices v1 and v2, denoted by dg(vl, v2), is the number of edges in the shortest subpath of the graph having v1 and v2 as its end-points. (For a treatment of graph theory, see Behzad and Chartrand [1].) Definition: A path P in G is called a descending path if dg(a, h) > dg(b, h) implies that f(a) S f(b) for all a and b which are ver- tices of P and where h is one of the endpoints of P, termed the high endpoint of P. The direction of the descending path is away from h. Definition: A tree T in G is a unimodal tree if there exists a ver- tex h of T such that every vertex of T is a vertex of a descending path in T having h as its high endpoint. I Theorem: A unimodal fuzzy subset Fi exists in Si if and only if G contains a unimodal tree spanning Si' (Fi has; the same function value, f, as does F). Proof: The proof proceeds as follows: It is first shown that if 56 Gij’ the largest subgraph of G in Sij(Sij = {x3f(x) 2 f(xj)} for any xj in Si) is connected for all xj in Si (i. e. , Si is unimodal, from the definition), then Gi’ the largest subgraph of G in Si’ has a spanning subgraph which is a unimodal tree. (By the largest subgraph is meant the subgraph having the greatest number of edges. ) Second, it will be shown that if. G1 is spanned by a unimodal tree, then 61' is connected for all x, in 51' which means that Si is a unimodal subset by definition. 1. If Gij is connected for all xj in Si' then there is a path in each G'j from every point to every other point in Ci" Since every connected 1 graph has a spanning subtree, it must be shown that at least one such spanning subtree of Gi exists which is a unimodal tree. Order the ver- tices in G1 by decreasing value of f. Put a spanning tree through the point(s) in G1 This can be done because of the assumption that each 1' Gij is connected (from the assumption that Si is unimodal). This tree is unimodal since all the vertices have the same ’value of f. Next, add the point(s), if any, which are in Gi and not in Gil' (By definition all points 2 in Gij are in Gil ifj < I). The tree which was put through Gil is extended (edges and vertices added) to include the points in 012' This can be done because Gi is connected and includes Gi . The tree is still uni- 2 l modal because only points of non-higher function value were added to the tree. Continue this extension of the tree to include G, , then G, G 13 1 4’ i5' and so forth, until all the points in Gi have been included in the tree. The tree is still unimodal, and it can be formed since each Gi' is connected and, for j > 1, contains G. 1 j 1' Thus if Si is unimodal in the sense of 57 the definition, Gi contains a unimodal tree. 2. The fact G1 is spanned by a unimodal tree means that Gi is con- nected. If one of the lowest-magnitude points (there may be more than one in the case of equality in function values between points) which is also an endpoint of the tree (there must be such an endpoint since the tree is unimodal) is stripped from the unimodal tree, a unimodal tree is left. Lowest—magnitude points may continue to be stripped from the tree one by one until there are no points left in the tree. At some time during this process, it will have been demonstrated that each Gi' is a unimodal tree, and is therefore connected. Therefore, Si is unimodal by defini- tion. Q. E.D. 4. 3 The UnimodaleLee Algorithm An algorithm which generates unimodal trees on an integer grid will now be described. For each subset the algorithm starts with an arbi- tra ry point which has not been assigned to a previously-formed group and determines the largest possible unimodal tree which can be put through the currently unassigned points. The first subset will have as many points as possible, the second will be as large as it can be without using points from the first subset, and so forth. The procedure is sum- marized below, and a flow chart is shown in Figure 22. Several arrays, pointers, a flag array, and a variable are needed. It is assumed that the function value of each point is in one array. 58 Figure 22. Flowchart of the Unimodal Tree Algorithm. (START) 1.1 IG=0 Set all points as unassigned 2. IG=IG +1 I Are there any unassigned o oint : EXIT I YES Set CBT to an unassigned point. MODE=value(CBT) NEXTC=NEXTO=O GROUP(CBT):IG 4" NEXTOzNEXTOH‘ GROUP(NBT)=IG NEXTC=NEXTC+1 NEXT(NEXTC)=CBT YES NO YES MODE=value(NBT)J ‘CBT=NEXT(NEXTO) 59 Another array, called NEXT, is needed to record branching points so that other branches from each point not an endpoint of the unimodal tree being formed may be found later. The array NEXT functions as a stack. A first-in first-out stack was used here, but the order of removing points which need to be checked for further branching is immaterial. Pointer NEXTC points to the last entry in NEXT and pointer NEXTO points to the last element removed from NEXT. Another array GROUP is needed to hold the group number of each point as it is assigned. An array of flags is necessary to tell which points have been assigned. Two points which are linked by exactly one edge of G are said to be neighbor points. It is assumed that a means exists for determining all of the neighbors of a given point. A group counter IG is needed to count the number of groups formed. A variable MODE which has the same value as the highest point found in each group as it is being formed is required. A pointer CBT, standing for Current Branch poinT, is needed to point to the place at which the unimodal tree is currently being expanded, and another pointer NBT, for Next Branch poinT, is needed to point to an assignable neighbor of CBT. The steps of the Unimodal Tree Algorithm follow. 1. (Initialization of the algorithm). Set IG to zero to indicate that no groups currently exist. Set the assignment flag for all points to in- dicate that every point is currently unassigned. Continue with step 2. 2. (Initialization of a new group). Set IG to IG + 1 in order to start the next group. If possible, find an arbitrary unassigned point and set 1 /—;. 60 CBT to point to it. (This will be the starting point for the new group). If it was not possible to find an unassigned point, go to step 5. If it was possible, set MODE to the value of CBT. (This is the highest value which has occurred in this group). Set NEXTC to zero to indicate that no points have been entered into stack NEXT. Set NEXTO to zero to indicate that no points have been removed from NEXT. Set GROUP(CBT) to IG (this assigns CBT to group IG). Continue with step 3. 3. (Linkage to an assignable neighbor). If possible, find a point NBT such that NET is unassigned and a neighbor of CBT and, if the value of CBT is less than MODE, such that the value of NET is not greater than the value of CBT. (These conditions on NET are necessary to preserve unimodality in the unimodal tree, as discussed below). If this is not pos- sible, go to 4. If it is possible, set GROUP(NBT) to 1G. Set NEXTC to NEXTC+1 and set NEXT(NEXTC) to CBT. (This enters CBT into stack NEXT so that the point can be checked later for additional assignable neighbors). If the value of NET is greater than MODE, set MODE to the value of NET. (This maintains MODE as the highest value yet found in the current group). Set CBT to NET and repeat 3. (This accomplishes a linkage to NET). 4. (An old point which was branched from in step 3 is obtained from stack NEXT and rechecked). Set NEXTO to NEXTO+1. If NEXTO > NEXTC go to 2. (This gets the next old branch point location in stack NEXT. If there is no such point left in NEXT, a new group is started in step 2). Otherwise, set CBT to NEXT(NEXTO) and go to 3. 61 5. (Exit). The data is now partitioned into a maximal unimodal partition. To verify that this algorithm generates a unimodal partition, an inductive argument is presented which shows that each group must be a unimodal tree. If each group is a unimodal tree, it is then a unimodal subset, using the theorem. The inductive argument proceeds by stating that the starting point of each group is a unimodal tree and then showing that whenever step 3 of the procedure is applied to one of the endpoints of a unimodal tree (as CBT), a unimodal tree will result. Given a uni- modal tree, each endpoint of the tree has either the highest magnitude in the tree or it does not. If the particular endpoint in question, CBT, has the highest magnitude in the tree, step 3 will allow any unassigned neighbor point of CBT to extend the tree. Regardless of whether this point is higher, the same, or lower in magnitude, the resulting tree is unimodal. If it is higher, all the descending paths from point H ((one of) the largest magnitude point(s) of the tree) to all the other points of the tree may be extended to include the new point as a highest point of the extended tree, which means the tree is unimodal. If the point is equal to or lower than the mode of the original tree in value, the descending path from H to CBT is extended by one edge to include the new point. Thus all points in the extended tree are included in descending paths each having (one of) the largest magnitude point(s) of the extended tree as its high endpoint, and the extended tree is therefore unimodal. In the case where CBT does not have the largest magnitude in the original 62 tree, step 3 allows extension of the tree only to points having value less than or equal to the value of CBT. Since CBT resides on the low end- point of a descending path from point H, this descending path may be extended to include the new point. Thus the application of step 3 will always generate a unimodal tree, providing the tree given to step 3 is a unimodal tree. Since the starting point by itself is a unimodal tree, as given to step 3 by step 2, the algorithm will always generate unimodal trees, and consequently (by the theorem) unimodal subsets. To verify that this algorithm generates a maximal unimodal pa rti- tion, it is necessary to show that all the subsets are unimodal, which has been done, and that the union of any two subsets genela ted is not uni- modal. Note that the algorithm always follows descending paths as far as they can possibly be extended, in either the ascending or descending direction. This is ensured by saving each point along each descending path as the path is extended, and rechecking the points later for further branches. If further branches are found, the point is again saved and later restored for further checking. Therefore, the particular unimodal tree being formed is extended as far as possible. EXpansion of a uni- modal tree stops only when every unassigned neighbor of every endpoint of the tree violates the condition that the addition of that neighbor would maintain a descending path from the mode of the tree to that neighbor. Suppose Si and Sj are two unimodal subsets generated by the algorithm and that SiUsj is also unimodal. Either Si or Sj must be generated first. Suppose Si was generated first. Because SiUSj is unimodal, there must 63 be endpoints of the unimodal tree generated in Si which are neighbors of some points in Sj. Furthermore, a descending path exists between the mode of Si and Si, in the direction of the higher to the lower (or in either direction if the modes are equal). The part of this path in Si may be re- placed by a path between the mode and the boundary which was generated by the algorithm, since the direction of a descending path is defined by the relative magnitudes of its endpoints. At the crossover between the two subsets, the path generated by the algorithm has a continuation into Sj. The algorithm will then assign a point of Sj to 51' But the point is in 5., so the assumption that the algorithm can generate two unimodal subsets the union of of which is also unimodal has been contradicted. The algorithm, therefore, always generates a maximal unimodal partition. 4. 4 Implementation of the Unimodal Tree Algorithm The Unimodal Tree Algorithm has been implemented in FORTRAN II, in machine-independent code. The implementation described here is for R=l in the definition of graph G, using the Euclidean metric. The starting point for each group is the highest unassigned point. After a group has been completely assigned, there is no further use for the magnitude of the points in that group; therefore, the number of the group may be stored in place of the magnitude value. This technique enables the GROUP array to be the same as the array which holds the function values, and reduces the storage requirements by N, if there are N data points. The magnitude value of each point cannot be discarded until the point is observed not to have any assignable neighbors. Thus 64 the assignment flag for each point is turned on immediately when the point is assigned, but the group number is not inserted until the point is found to have no assignable neighbors; that is, the setting of GROUP(CBT) to IG is removed from step 3 and inserted as the first thing in step 4. This may be done since each point is rechecked through being entered and re—entered in the stack NEXT until all assignable neighbors are assigned. The assignment flag procedure was implemented by requiring that the data be positive. All the data points were changed in sign be- fore execution of the algorithm. A negative value for a point indicates the point has not been assigned. When the assignment flag is set, the data value is changed back to its original positive value. Then when the necessarily positive group number is inserted into the data value location, the assignment flag, which is the sign of the data value, remains positive, indicating assignment of that point. The storage requirement of the UnimodaliTree Algorithm as imple- mented is 2N storage locations for N grid points, plus 3*NDIM locations for an NDIM-dimensional grid, plus the program requirements. N of these locations are needed to store the input data values and the output group numbers. N more locations are used for stack NEXT. Note that while some points may be entered more than once in stack NEXT, there is a point for each extra entry into NEXT which does not get entered into NEXT at all. This point is the last point assigned before the next entry is taken from the stack. NDIM locations are required to store the number of grid increments in each dimension, and NDIM more locations 65 are required apiece for two coordinate vectors, one for CBT and one for NET. The number of computations involved in this algorithm varies slightly from scene to scene because of the variable length of searches for an assignable neighbor for various points. All the points are searched at least once and most of them twice. Each time a point is entered into the NEXT table, it will be searched again in the future. The total num- ber of searches performed is ZN-g where there are N points input and g groups formed. This may be verified by noting that each duplicate entry into stack NEXT is offset by a point which is not entered at all. In addition, the point which was assigned just before the first point was taken from the NEXT array is not entered into the NEXT array and is not checked again. This happens g times so 2N-g checks are performed. In the current implementation, all the neighbors of each point are checked until an assignable neighbor is found, so the tests are of different lengths depending upon which, if any, of the neighbors are assignable. If addi- tional storage is available, the number of the next neighbor to be checked for each point in stack NEXT could be recorded. Then each neighbor position of each point would be checked exactly once and the number of computations would be fixed. The added complexity and storage require- ments to do this were prejudged as not justifiable, so no implementation of this scheme was attempted. A savings in computation time may be obtained at the expense of additional storage requirements. Note that only a few bits are required to store the number of the next neighbor 66 (4 bits will accomodate up to 8 dimensions). A few bits of each data word may be used to store this information, if a degradation in the reso- lution of the data can be tolerated. If a large number of bits per word are available, the data value, the assignment flag, an entry in the NEXT stack, and the number of the next neighbor to be checked may all be stored in one word, reducing the core requirements to N locations. The principal feature of the Unimodal Tree Algorithm is the approx— imately linear amount of computation and storage required by the algor- ithm. In addition, the Unimodal Tree Algorithm is not adversely affected by points of equal magnitude. The Unimodal Tree Algorithm generates a maximal unimodal partition, which provides a great advantage over the Potential Local Maxima Procedure followed by procedure S. The Uni- modal Tree Algorithm thus appears to fulfill the requirements needed for an object isolation scheme. Application of the Unimodal Tree Al- gorithm to object isolation and to clustering of points will be discussed in the next chapter. CHAPTER V APPLICATIONS OF THE UNIMODAL TREE ALGORITHM 5. 1 Object Isolation Two applications of the Unimodal Tree Algorithm are presented in this chapter. The first application is object isolation and the second is clustering of points in a space. Object isolation means defining "regions of interest" in a two-dimensional image. These "regions" of interest" could correSpond to actual objects in a sampled scene or to portions of the objects. Objects in a scene can be separated by this algorithm only if each object corresponds to a unimodal set. Most images contain far more data points than are needed, and they also contain noise and many fluctuations in intensity which are meaningless for object isolation. (See Figure 23.) Direct application of a sampled image to the Unimodal Tree Algorithm would result in a myriad of small meaningless unimodal subsets being generated. A procedure to "enhance" the image for object isolation is thus necessary. Sucha procedure is termed preprocessing of the image. The intent of pre- processing an image before object isolation is to reduce the number of data points so that the objects can still be distinguished but the de- tails of each object, which are meaningless in object isolation, are lost. If the resolution cannot be reduced so that the objects are dis- 67 68 Figure 23. Mite Scene. 69 tinguishable but object detail is lost, further "smoothing" of the reduced image may be required. 5. 2 Object Isolation Examples The scenes which were scanned and processed for this thesis were scanned on a 100 x 100 grid, giving 10, 000 data points per scene. The scanned scenes were reproduced on a line printer with eight distinct brightness levels. (See Figure 24.) All scenes were then reduced to a 25 x 25 grid by averaging square blocks of sixteen points each. (See Figure 25.) Two photos other than the mite photo of Figure 23 were also processed in this manner. They are shown in Figure 2 and Figure 26. Figure 2 shows two eggs touching each other and Figure 26 shows three eggs and three ping-pong balls, none touching each other. The original resolution of each of the 10, 000 data points in one of these scenes was estimated to be eight bits (256 levels). This was reduced to approximately 16 levels of brightness. This reduction of the number of quantization levels of the image resulted in some "smoothing" of the undesirable fluctuations in the scene. The three scenes were then run through the Unimodal Tree Algor- ithm. If the dark background level was suppressed, the two eggs of Figure 2 and the six objects of Figure 26 were isolated. Two and six unimodal groups were generated, respectively, and each group corres- ponded to an object. The mite scene, which still retained some detail of the mites, was separated into 21 unimodal regions. (This is the 70 [I s/ In A - 0”] O C e n I n e o/ c/X/I/I/l/I . n/I/l/ll .///lXXle/////XX///l . o.I)lll.nIIISI/lrl‘uTI/ICIX .oIXXvuIII/ll l A k h I X I I [XXXKXIIXX mnx/l/sxxm. l/II III/ III "I X» XX 1 I’ll/XII - Scanned Mit e Scene . Figure 24. 71 u o o o e e C O o e I 0 e e I, I o I e o”’/”’/ s//’/ s e 0 I’ll] I I O x o//// o a - o/// X ell/I’lllli’llllil‘ I uI/I’llll’lll’lllxx ’/ u/l/l/I/l/I/lilillx’xl/l o/ l/l/l/l/I/l’l/xIXXIII x/l/IIIIIXNxXl‘X ll]”’//’IXX‘II I’ll/l e e . o e e . o o e O o l I x x l x X K II IBINVEI IIKI'U? IIIIIH 25 x 25 Grid of the Mite Scene Figure 25. '72 , . .. .. . . ... . a . .... «a» o u .“L ...... ..e o..:.