THE UNIVERSITY OF MICHIGAN COMPUTING RE~,SI1:ARCII IA3BORATORY SIlAPE'l MATCLING IN PYRAMIDS JANUARY 1984 Room 1079, East Engineering Building Ann Arbor. Michigan 48109 USA Trel: (313) 763-000

SIIAI';E MA'I'CH I NG IN 1-'YRAMIDS William I, Grosky Intelligent Systems Laboratory Computer Science Department Wayne State University Detroit, Michigan 48202 and Ramesh Jain Department of Electrical and Computer Engineering University of Michigan Ann Arbor, Michigan 48109 Abstract This paper presents a technique for region matching. An image is represented as a function f(X,Y) and a region in an image is approximated by an ehliptical paraboloid. The coefficients of the elliptical paraboloiid ar'e us(:,d( in rniatchirlg regions. It is shown that the coefficients can be easily computed in a pyramid type architecture using prropos(:d pyramid linking algorithms. Our experiments demonstrate that the proposed approach is more robust than moment-based approaches for region matching. Another feature of the approach is that it can be used for region splitting and merging, if required.

1. INTRODUCTION Matching plays a vital role in many applications of image understanding. At a low level, token matching, commonly called correspondence, is used in stereo and structure from motion; object recognition using structural information uses graph isomorphisrn at a high level. The tracking of objects and change detection are required in many applications. Cross-correlation and statistical techniques have been used for matching regions in such situations. If the segmentation of images has been already performed, then correlation has been suggested as a particularly powerful technique for matching and displacement. A serious limitation of correlation, however, is that it does not work well in the case of rotation. In many applications, object recognition is performed based only on the regions, or borders of regions, representing the mask of the object. Usually, several masks for each object are stored and recognition is achieved utilizing matching of the unknown region -with each model. in tracking, also, a region for an object is given, or obtained in a frame, and then unknown regions are matched to it. Assuming segnmentation has been already accomplished, many of the most wide used techniques for the shape description of regions are moment-based 15,7,10,15,16,21,24,25]. These methods extract features which are invariant with respect to the object's position, size, and orientation. The initial impetus in this area was the work of Hu[ l 6] in which 7 algebraic invariants, calculated from n-th order moments of the image, for O_<.n~3, are described. In this paper, we introduce a least-squares based technique which computes various features, and compare it with that of Hul 16]. We interpret an image as function f (X, Y) which maps X and Y coordinates to graylevels. This allows us to consider an image, or a region representing a sub-image, as a surface Z=f (X, Y). A region in a frame is represented by finding a best-fitting elliptical

3 parabol to the graylevel surface corresponding to the region. It is observed that this representation allows the reclitable matching of regions, and by-products of the matching are the parameters describing the 2-D transformation of the surfaces. We discuss a method to fit the elliptical paraboloid to the regions and demonstrate the efficacy of this representation. We also show how to embed the calculations in a pyramid architecture [1,4,8,9,22,23] so that the representation of each region in an image is at the highest possible level in the pyramid structure. It is shown that the parameters of the best-fit surfaces can be computed in the pyramid structure while forming the connected components. Thus, by using a special architecture, it is possible to compute the parameters of the graylevel surfaces very quickly, so that the matching of the surfaces can be performed without going to the raw images. Our method is more powerful than moment-based approaches for several reasons. Moment-based techniques lose all contact with the underlying graylevel surface. They have no notion of the errors involved in representing a segment by a set of real numbers. Thus, there cannot be any embedded control mechanism which uses the error to invoke numerous possible split-and-merge techniques to compute less errorful features. Our technique, on the other hand, has a built-in notion of error; namely, the difference in volume between the actual graylevel surface and the fitted one. Thus, we may use various split-and-merge techniques to lessen the error if we so desire. This paper discusses just the overall efficacy of our approach, so we do not cover this topic, but in future reports such techniques will beconme extremely irn portant. Our technique also generalizes to 3-dimensions in that we may parametrize coefficients of our quadric surfaces in a similar manner as we are here parametrizing the graylevel values. Many views of a 3-D object will then be representable in a very compact manner as a k-dimensional subspace of an mdimensional space, for k <nL, while a single view would be a point in this m

4 dimensional space. We? may then Use existing techniques to efficiently find the best-match to an arbitrary view of soneic unknown object. Moment-based techniques, on the other hand, cannot be generalized in such a direct fashion to handle this problem. Finally, as we shall later demonstrate, our method produces better results. We have performed numerous experiments where various images were translated, rotated, underwent size changes, had noise introduced, and underwent changes in lighting. These experiments show that our approach produces better overall clusters than the moment-based ones. Fitting a parametrized surface to a graylevel surface has been done by other researchers[11,12,13,19]. They, however, do so for reasons other than ours, which causes their methods to be quite dissimilar to ours. Paton[19] uses Legendre polynomial while HIaralick and his co-workers use planes [11] and bicubic surfaces [12,13]. These fittings are done locally, however. For each pixel p, a fit is done over some small neighborhood of p. These researchers are trying to discover local features such as peaks, pits, ridges, ravines, saddles, flats, and hillsides in order to use them as a means for describing an image. Ostensibly, these features can be used for matching purposes. Their use in such a setting has not been explored, however. Also, their robustness under various levels of noise has not been examined. Our method, on the other hand, works quite well under noise. Since matching is our primary goal, we set out to discover global rather than local features, and global features should be more robust under noise than local features. Thus, we fit a single surface to the entire region, rather than many surfaces locally. An overview of our scheme now follows. We interpret an image as a surface Z=f (X, Y) in 3-space. Erach node of the pyramid will then contain the equation of a second-order surface, an elliptic paraboloid, which is fit through the center

of-mass of the level-i sub-image corresponding to this node and which minimizes the square-error between itself and the surface Z=f (X,Y) over an appropriate area. This will be discussed more fully in Section II. For each region in the image, we now want to find the highest node in the pyramid, that is, that node closest to the apex, whose corresponding level-1 sub-image completely contains this region and contains no other region. If we can find such a node, the equation contained in it will convey information regarding the shape of the region, its position and its orientation. If we cannot find such a node, we change some of the links of the pyramid so that a level-k node, k>1, now deLerrnines a not necessarily square region. This connected region will consist of squares of sizes 2k-1 x 2k-1 2k —2 x 2k- 20 x 20 which are joined together across their edges. This will be discussed in Section III. See [2,14,17,18,20] for other applications of pyramid relinking. The embedding of the above calculations in the pyramid data structure will be discussed in Section IV. In Section V, we will discuss the matching phase of our algorithm. This will consist of constructing pyramids for each frame. In each pyramid, we identify nodes corresponding to each region, as above. Two nodes whose equations are equivalent after a coordinate translation and rotation will correspond to the same region. This translation and rotation will then give information regarding the translational and rotational components of the 2-D orientation, respectively, of this region. Finally, the various experiments we performed, as well as our conclusions, will be discussed in section VI.

2. SECOND-ORDER IMAGE APPROXIMATION For illustration, let us assumre an B x 8 grid of pixels. Our coordinate origin will be placed in the exact center of the grid. Thus, the point (ij) will be in the lower loft-hand corner of the pixel in row 4-j and column i+5, This pixel will also have address (i,j). See Figure 1. L,et us assume that this grid contains only 1 surface (,1-connected region). Now, Z=A (X-Xo)2+ B ( -)2+ C(X-XO) ( Y- Y0)+ D is the equation of an elliptic paraboloid centered at point (Xo,Y0). Let us find the values of A,B,C, and D which minimizes the square-error between this surface and the surface Z=f (X,Y) over a circular region centered at (X0,Yo) and with radius R larger than the diameter of any possible region in our grid. For our example, any R>8F- will suffice. (Note that f(X,Y) is assumed to be O outside the grid.) We have experimented with fixed values of R as well as variable values. In the latter case, R is taken to be the maximal distance from (X0, Y0) to a boundary point. We are going to put Xo=XCM and Yo=Ycm, the coordinates of the center-ofmass of the region. The reason for centering this surface at the center-of-mass and fitting it over a circular region is that when this is done, the position and orientation of the surface in the grid will not affect the final equation after a coordinate transformation is done which puts the origin over (XCM,YcM) and the axes in such an orientation as to eliminate the cross-product term. Letting x =X-Xo and y = Y-Y0, we want to minimize expression (1) e jJfo~!H [A2+fy+'2 +D-(x+X0,y+Y)o2dxdy (1) which is equivalent to expression (2): f+R J IA 2nx4+J32y4+C2x2y2+2AJ x 2y2+ 2ACx3y+ 2f x.y (2) +2A]x2+2C)xy +-2IDy2++ ])2f +2(x +Xo,y + Yo)-2Drf (x +Xo,y + Yo) -2Az2f (x +Xo,y + Yo) -23yZf (x +Xo,y + Yo)-2Cxyf (z +Xo,y + Yo)]dzdy

7 We finally end up minimizing tR 2( X + Y).-(2Ax2+ 2Jy+ 2 Cxy +2D) f (z + Xo. + YO)]dxdy (3) +(R6 rRH R4 + ( )(A2+B2) + ( 24 )(C2+ 2AB) + ( 2 )D(A+B)+ R2D2 Setting the partial derivatives of expression (3) with respect to A,B,C, and D equal to 0, we end up with equations (4a)-(4d): 7TR6 irR irR4 +R + R4-2 )zA+(A + )B+( 2 )D=2fi x (x + X.y + YO)dxdy (4a) rr R A+( R F R4 )D=2 fR, R Y 2f (x +Xo,y + Yo)dxdy (4b) (124 )/+( 4 2 TrR6 +R -, 2 )C = 2 fR rf xyf (x +Xo,y + Yo)dxdy (4c) irR4 irR4R +VR 2 )A+( 2 )B +2rrn 2D 2 +ffa2+ f (X +Xo,y+Yo)dxdy (4d) with solutions (5a)-(b'd): A = 6, (y 2+3f 2_-R2)f ( +Xo,y + Yo) Zdy (5a) = (-R) J6 ] + (x2+3y2-R2)f (z +Xo,J + Yo)dxdy (5b) 24 r4RcC = (- ),R J J+VWz2 (x +Xo,y + Yo)dxdy (5c) -R 6 D =f R_ [ 4 - 6R4 (x2+y2)]f (x +XO,y + Yo)dxdy (5d) From Theorem 7.8 in Apostol[3], it may easily be verified that the above solutions do minimize (1.). Changing back to (X, Y) coordinates, letting W= R2-( Y-YC )2 and putting X0=XCJ and Yo= YcA, where C= r JX C Xf(X, Y)dXdY fC M andc- J- f (X' Y)dXd and

XCM+ W r? WYf (X, Y)iXd Y CMMcm we have A 18 6 A = ( R) Y2MEAN+( R)X2MEAN-( )MEAN (6a)?n R6 ilT R" r R4 B = ( X2MFAN+( YMEAN( -( MEAN (6b) iT RrR612 p MA R4 C ( 24)XYMEAN (6c) T R D = ( R)MFAN-( R4)[X2MEAN+Y2MEAN] (6d) for M,4'AN = JYcrM x W, f (X, Y)dXdY (7a) X2M,-'AN - J Y~M,R JM XCW X2f (X,Y)dXdY (7b) YCM4-R XCM 4.Yr,-m fX: —.m [ Xf (X, Y)dXdy]2 MEAN "YCC R XCM + X W2 YCM + R XCM + W r[ JY —. fx+R, M Yf (X,Y)dXdY]2 ME AN [' Y+R- XCM+ I XYMF:AN = Y-Cm+ _ XYf(XY)dXdY (7d) Y(q R t X I' Y' R XCM 4- W M I? XJ.O YW(X Y)GdXMRY (cm.XcM Yf(X.Y) dXdiY] METhus, to coAN the zero-th, first and second order moments of the image. These moments can easily be calculated in ternms of the graylevel value at, each pixel, since, for i,j integers, f (i,j)=f (i+,j+bh ) for O<ac,b <l. Specifically, it can be shown that, JYCM+e RxcM' W LI. —R ~,..- - f (z, Y)~dXdY' - f~ I(i,; ) (sa)

YCM tR XCMI W j. u RJ Xf(XY)dXdY= (i 2)f(ij) (Bb) fYCR JXC-W Yf (X, Y)dXdY = > (j + )f (ij) (Bc)'iv ~ ~ ~%.j fYCM — J? fXC Cii + Y * R XCM+ 1 1W f -CR fx W x2f (X, Y)dXdY =E (i +)(j + )f (ij) (Bf) fYCMR JRX(,CM- 3 1 1 Thus, to develop the equaition of the best fitting elliptic paraboloid to a region, we need only be abl(e to efficiently calculate >z f(ij) (9a) i., ~>3~ if ~(i~,y) ~(9b) %.J E jf(ij) (9c) )> i2(i,j) (9d) i,j Z j2(ij) (9e) i,j for this region. 3. SIEGMENTING AN IMAGN VIA PYRAMID LINKING Consider the image of 1'igure 2. If one constructs a standard pyramid in which each node above Ilvel 1 has precisely 4 sons, one cannot find any node in this pyramid whose corresponding sub-inlmage contains one and only one region. We thus relax this requirement. I'ach node can have as few as 1 and as many as 16 sons. The way this is done is that, as necessary, nodes are relinked to neighboring fathers. Given the 2 x 2 template of Figure 3, area 1 can be linked to either its own father or to a neighbor of this father to the west, to the north or

10 to the northwest.,inmilar staterrlenls can be made for areas 2, 3, or 4. We first label the regions on level 1. We use the standard recursive labelling scheme, but it may be done in parallel by having each pixel with a graylevel above O pass its address to its northern, southern, eastern and western neighbors. When a pixel with a O graylevel receives inputs, it ignores them. When a pixel with a non-zero graylevel receives inputs, it changes its address to the minimal address received.'Thus, after a time proportional to the diameter of a region, that region is labelled by the smallest address of any pixel in that region. Then, starting at level 1 and continuing as long as necessary we do the following. Each 2 x 2 sub-image is examined to see how many region labels are included among its nodes. If this sub-image contains nodes from at most 1 region, none of its nodes are relinked to another another father, while if it contains nodes from 2, 3, or 4- different regions, these nodes are relinked, if possible. This relinking is done in a disciplined fashion: 1) If 3 nodes are from 1 region, while the 4-th node is from a different region, this latter node is the one to be relinked. 2) If 2 neighboring (4-connected) nodes are from one region, these 2 nodes are relinked to the same father. 3) Relinking is only done to a father all of whose sons are either of graylevel O or from the same region. 4) We first try to relink nodes to a father whose sons contain the same region as the to be relinked node. If this can't be done, we then try to relink them to a father all of whose sons are of graylevel 0. 5) After a[ll the relinking is accomplished, each son of! a given. father has a 0 region label or an equal positive region label. The father inher region label. 6) Relinking is not done to a niode if there is no neighboring node of the same region label. If this is the case, we have found a node in the pyramid whose corre.sponlding sub-inlage completely contains just ] region. The information

11 concerning this region will be kept at this node and a flag will be set indicating that this node is the root node or an individual connected region, but its region label is changed to 0, so that higher level nodes will see it as being of graylevel 0. Thus, higher level nodes will treat this node as background for any future relinking operations, even though there is an entire connected region encompassed by this node. This latter region is called a hidden region, and all nodes with such regions are flagged appropriately. 7) Before the relinking starts on level 1., we place a border of graylevel O around the original image. In our case, Ithe 8 x 8 image is put in the center of a 16 x 16 irmage. This is done as it rrnay be necessary to relink into this border.',et us trace the steps taken using the image of Figure 2. Each of Figures 41-8 illustrates higher levels of the pyrantid. Neighboring nodes with similar cross-hatching have the same father node. Also, nodes an R written in them have their root flag set, while nodes with an H written in them have hidden regions included among their children. 4. EMBEDDING THE NECESSARY CALCULATIONS IN THE PYRAMID We now indicate how to embed the calculations of (9a)-(9f) for each 4connected region in the pyramid. E:ach node of the pyramid'eess' only a single 4-connected region, aside fromnt any hidden regions which mlay occur at various children of the given node. Call this region the node's prirrLnary region. We will develop a method whereby each node of the pyramid calculates (9a)-(9f) for that part of its primary region which it encompasses. We will use,0 recurrence forrmulas. Specifically, each node will calculate its value of (9a)-(9f) in termns of the values of (9a)-(9f) of its children, after all relinking has been done at that level. We will illustrate this rrmethod on level 3 of the pyramid for the calculation of (9f). Figure 9 illustrates our exaniple. We want to calculate (9f) for node N. This

12 node has 4 children after all the relinking has been done on level 2: its northwest, southeast and southwest children as well as the southeast child of its western neighbor. Areas p q, r and s are the regions in the image encompassed by these children, respectively. We then have that (9f) for node N is > (i-2~)(j +20)fp(i,)+ >3 (i-3 *2~)(j -2)fq(ij) (10) i,j ep i,j q + (i-2~)(j-2~)fr(i,j)+ > (i+2)(j -20)fs(ij) i j e r i, e s where in each region p, q, r or s the origin of the row, column indices i,j is the respective child. T'hus, what is pixel (0,0) with respect. to the northwest son of node N is pixel (-1 1) with respect, to node N. T'he functions fp, fq, fr and fs are function f with these coordinate transformations. Now, (10) reduces to >S ijfp(i,j)+?jfq(i,j)+ > ijfr(i,j)+ > ijfs(i,j) ij rp.j e q i,j r ij es +20(, ifp(i,j)- >3 ifq(i,j)- >, ifr(i,j)- > ifs(i,j)) i.j ~p i.j cq i,j er i,j es +20( jf"s,(i,j)-, jfp(i,j)- > jfr(i,j)-3 > jfq(i,j) i.j E p itq ij e r ij es +(20)2( Z fr(i,j)- > fp(ij)- >3 fs(i,j)+3 >: fq(i,j) i j c i7.j E yq i.j Er i j e s l'hus, (9f) at. node N is cotrmrputed in Lernms of (9a), (9b), (9c) and (9f) at the children of node N. In general, in computing (9a)-(9f) at a level n node, for nl, we use 2 n-3 instead of 20 in (1 1). Also, the initializations of (9a)-(9f) at. pixel (i,j) of level 1 are f (,j),- ) 2 4 4,and,respectively.' 2 2 4 4 5. SHAPE MATCHING In each node of oeur pyrairltld which cornpletely encoTopasses a region, we have the equation %=AX2+fYy2+CXY+D of a best-fitt.ing elliptical paraboloid through the center-of-maiss of the region. ln order to use this surface for match

13 ing purposes, we find the angle which the major axis of the ellipse which results from the intersection of the elliptic paraboloid with the (X,Y)-plane makes with the positive X-axis. This angle is restricted to be in the first or fourth quadrant, and is found by calculating through what angle to rotate the (X,Y) axis so that the C;XY term is eliminatead. The resultant X2", Y and constant coefficients will be used in matching regions from frame to framrne. The feature we actually use is the eccentricity of the ellipse which results frorn Lhe interesection of the elliptic paraboloid with the (X, Y)-plane. This feature should remain constant under rotation, translation and scale changes as well as under the addition of a constant graylevel. Once we find similar regions in 2 framrnes, we use the center-of-mass and the difference in the above angles to find the 2-1) translational and rotational components of motion, respectively. We assunme that the rotational component is small, as this method does not give unique r-sullts for arbitrary rotations. That is, 2 different rotations nlay lead to the same answer. For example, if in frame 1, the major axis of the above ellipse nmakes an angle of 30 degrees with the positive X-axis, while in frame 2 the angle is 60 degrees, the rotational component could be -150 degrees, 30 degrees, 210 degrees or 330 degrees. It is easily derived that if the axes are rotated by RAD radians, for RAD =.5 *arctan( (A-3))' the (CXY term disappears. Also, the equation of the dY -(2AX+ CY) aforementioned ellipse is AXB2 Y2+C,XY+D=O. Thus, X= (BY+CX) or dY -2A This implies that if s'iJn(A)-sign (C) then its major axis is in the 4-th quadrant, while if sign (A n ( C), its major axis is in the 1-st quadrant. Thus, for RAD =.5 *IrCt( art( ( ), if RA)(<O and sign(A)-/sign n(C), we add to AD, while ifRAO and sig(A)=sg(C), we subtract from RAD

14 6. KXPIRIMENTS ANI) CONCIUSIONS To see how well our- method performed, we generated data on which we tested how our approach compared to that of the standard moment-based approach of Hu[l6]. lThe dat.a was fornmulated as follows: 1. We started out with 19 binary inmages of airplanes. Each of our images was of 64 x 64- resolution. 2. Each of the 19 images was rotated by 0, 15, 30, and 45 degrees, resulting in 76 images. 3. These 76 binary images were transformed to 64-graylevel images by generating random gray-values and smoothing twice with a window size of 3 x 3. 4. 5 ranges of noise were added to each of these'76 images by adding random values to each of the pixel values.'T'hese ranges were plus-n-iinus 0, 5, 10, 15, and 20 graylevels. I. Each graylevel. g>0 of each of the'76 graylevel images was transformed to graylevel min(63,g+1 2). 6. Each of the 76 graylevel regions was reduced to 32 x 32 resolution by averaging once over a 2 x 2 -window. 7. Each of the 76 graylevel regions was reduced to 32 x 32 resolution by averaging once over a 2 x 2 window, and then transformed by changing each graylevel g>O to graylevel max(O,g-4). We thus had a total of 1520 61-graylevel imnages, each of resolution 64 x 64. lor each image, we calculated the eccentricity of the resulting elliptical paraboloid using both a fixed and a variacble radius, as well as the 7 invariants of tlu[16]. Some sample images and their resulting parameters are shown in Figures 1.0-12. In order to corrmpare the variooLus approaches, we formed 1.9 clusters, 1 cluster per airplane, and calculated the cigenvalues of (SW -1) *SB, where SW is

the uAthin-cltLster scaltter rrinarix and SiY is the between-cluster scatter matrix as described in Duda and ltart[6]. The largest eigenvalues were 32.1, 1.3, and 44.0 for Hu's 7 invariants, our method with a fixed radius, and our method with a variable radius, respectively. Note that partitions giving larger eigenvalues. are more favorable. Also, note that our method, using a variable radius and only moments of up to second-order, outperforms Hu's method which uses thirdorder moments. We have thus demonstrated that our least-squares based method is robust and outperforms moment-bascd techniques. We have also introduced a pyramid-based architecture in whic-h the computations are done quite rapidly, especially for images containing ng ultiple regions. We are currently expanding this method to include both general quadric surfaces and error estimation techniques. The latter will be used to control various split-and-merge schemes to be used for images of objects having multiple surfaces. 7. REFERENCES [1] Adelson, lIl.]-[. and l3urt,'P.I.,'image Data Compression with the Laplacian Plyramid,' Proceedirngs of the Conference on Pattern Recognition and Image Processing, Dallas, Texas, 1981, pp. 218-223 12] Antonissc, H.J.,'Inmage Segrr-enlation in Pyramids,' CbmpuLter Graphics and Image Processing, Volume 19 (1982), pp. 367-383 [3] Apostol, T., Mathematical Analysis, Addison-Wesley, Reading, Massac husetts, 1960 [4] Burt, P.J., Tree and;Pyramid Structures for Coding Hexagonally Sampled Hinary Images, Technical Report TR-8 14, University of Maryland, College

16 Park, Maryland, October 1979 15] Casey, R.G.,'Moment Normahlization of Handprinted Characters,' IBM Journal of Research and DevelopnrLent, Volume 14 (1970), pp. 548-557 [61 Duda, fR.0. and lart., )P.E., Pattern Classification and Scene Analysis, Wiley-lnterscience, New York, 1 973 [7] Dudani, S.A., Breeding, K.J., and McGhee, R.B.,'Aircraft Identification by Moment. Invariants,' IElf,';,'E 7TranLs rLctions on (omputers Volume 26 (1977), pp. 3946 181 I)yer, C.IZ. and'{osenel'ld, A., Cellular hyramids for Image Analysis, TR5414, Computer Scitence l)epartrrnenl, Ilnivcrsity of Maryland, Colle May 1977 [9] Dyer, C.R. arind TRosenfeld, A., Cellular t hjram.ids for Image Analysis, 2, TR-596, Computer Science Department, University of Maryland, Co November 13977 [10] Hall, E.L., Crawford, W.O., and Roberts R.E.,'Computer Classification of Pneumrnoconiosis from Radiographs of Coal Workers,' IEEE Transactions on Bioniedical Engineering, Volume 22 (1975), pp. 518-527 II1 Ilaralic k,!.M., K'1,;(d.1 anF] I egion Analysis for l)igi lal Image Data,' CobLmitnler (rap)hie s and/L Imrzge lrocenssring, Volulme 12 (1980), pp. 60-7 1121 Illaralick, Hl.M.,'licdes (and Valleys on I)igital Images,' Computer Vision, (7ra,)phic, and IrLage ILrocf:erSsilg, Volumeil 22', (1 983), pp. 2B-3B 1.3] llaralick, R.M., Wal.son,,.'1'., and Iaffey, 1'.J.,'The Topographic Primal Sketch,' I'he Internat.ion.ral JouLrTLr1l o( Uobotics.T Riesearch, Volume 2 (1983), pp. 50-' 2 11,I tlorlg,'l'.ll., Shncifr, M., and Rt:-;.nfeld, A.,'Border Extraction Using I,inke.l id ge l yr'rilicl s, i 11,'t',l,' l'ra.lreL. cti'i.-t,' on S'!Jst. erLs, Man., q and C(yberneti Volt.lni'l. 12 (1 92), [)[>. (-G' ) — f;f;f

17 [15] Hsia 1'.C.,'A Note on Invariant. Moments in Image Processing,' I'fE'F, 7Thansactior'ns on SyJsterrLs, Man, nrLd (bBVer7Letics, Volume? 1 1 (1980), pp. 831-B34 [16] Hu, M.K.,'Visual Pattern Recognition by Moment Invariants,' IRE Transactions on Information Theory, Volume 8 (1962), pp. 179-187 [1.7] Kasif, S. and Rosenfeld, A.,'Pyramid Linking is a Special Case of ISOD)A'rA,' l'A,'E 7'rarnsrtwL tions on SJystemRrLS, Man, and Uybernetics Volume 13 (1983), pp. 84-85 [18] Narayanan, K.A. and Rosenfeld, A.,'Approximation of Waveforms and Contours by One-Dimensional Pyramid Linking,' Patternt Recognition Volume 15 (1982), pp. 389-396 [19] Paton, K.,'I'icture Description Using Legendre Polynomials,' Computer rkaphics and Image Procerssing, Volume 4 (1975), pp. 40-54 [201 Pietikainen, M. and Rosenfeld, A.,'Image Segmentation by Texture Using Pyramid Node Linking,' LiA'N Transactions on S'ystems, Man and Cybernetics, Volumn-e SM'MC-11 (19j1), pp. t82-82B,; 1'211 Reeves, A.P. and Rostamnlpour, A.,'Shape Analysis of Segmented Objects Using Moments,' 1lroceedi'n. gs of the (onference on Ptattern Recognition and Image Processing, Dallas,'Iexas, 981, pp. 1.71-174 [22] Tanimoto, S.li., T'owards Hlierarchical Cellular Logic: Design Consideration for Pyramid Machines,'TR t81-02-01, Computer Science Department University of Washington, Seattle, Washington, February 1981 [23] Tanimoto, S.I. and Klinger, A., Editors, Structured Computer Vision: Machine Perception'Through I-lierarchical Computation Structures Academic Press, New York, 1.93t30 [24] Wiejak, J.S.,'Momennt Invariants in Theory and Practice,' Image and lVisi.on Computing, Volurnme 1 (13983), pp.'79-83

1B [251 Wong, [.Y. and Hiall, i.','Scene Matching with Invariant Moments,' Computer Graphics and Image tProcessimrg, Volume 8 (197B), pp. 16-24

43 j. (3, ~33) 0~~~~~~~~00 Ow (-4,-4)~~~~~~~-I) (O~~~~~~~~~~~~~~~~~( -1.0 (32 -4) 1,0~ 2. 3,0~~ 3,0~~~.

o Ib~I ~ ~~~~~~~~ 0 so I ~ r 0 I ii C3~~~~~3 a 0~~~~~~~~. 0, 0 0~~~~~~~~~~~~~~~~~~~~~~~3 0~~~~~~~~~~~~~~~~, FIGRE2 ABIAR.0G

;V1',V" L, g x z V - ~E 3lHg19.d ~ v L. II

p ~~~~~~~~03 T' ~~~~~~~~~~~~~~~~' I FIGRE4 EVL O TE MAE YRMI

/INVkmAd 9OVk[I {}L dO 0 IA3~I - g PoflDI{ F'C a vc~~~~~~~~~~~~~ 0'0 O'q. ~~~~l~' / / / ~ —C O'te~~~~~~~~0,. o~~~~~~~0-' o0 II..a ~~ ~ —`f,

Z, Q~~~~~~~~~~~~~101 a a~~~~~~~ aI -- -- CP~~~~~~J. -2.0 ~ ~ ~ ~ ~ ~ ~~, -1.0~ ~ ~ ~ ~ ~~~~~, a -~~~~~

at R 000-100 0 - 0, 0 a cl H 0 R H H O ll —- i -J. 0 H 0

(IIWVHA a)d I)VWI aMI. o40 S 1IaA'li - 8 2MWI9II S'O If H is $

q r S FIGURE 9 - THE PYRAMID CAL.CULATIONS

.......................... v....................................................... k v............................................................ kxvj................................................ fojm1mkkseeirzxt1gbbbd&ije.................... * fspzyDBExpkquwuvvoimqsnpoe........................................ vHECzDCwswzxwABusyEExo.......................................... ittvwwsmswutvvtljotuqe.................................................. uzyxzv.......................................................... rBxxxn.......................................................... mztxtn....................................................... nBtDts........................................ 9dikomklpqpmromdhatwmurxsvsmfachiljoijipnle6.................... envyBAAyzwwsCzBnruyBvvovAMIxolqvrqpytrqxwspd.................... hpwyDCBxvostCAxnqryzAwosCPHxptvtmkqwwtxuytue.................... dkpttAwvlhopvsrqrsuzEDplrDDvwBDzsoszFDEusfJ9........................ pxtwopuxwnmrtyqxyDsmorqouECzvtuuDIKv........................... 7hkplmmosqyCABoxuxqlqlplvCCzqkihqvvk................................... tuxwwxlzxDuouosnrxBw...........................................tFExrspzAAv=AzEywvzr............................................ mBuqkrsvuzvssBCArqsl............................................. drqrjsuxvxvyvFzArnlb.............................................. ioqvuqsyywuAyxog........................'. jmto*AFEBzzsnf8.................................................. wtohvyyvzwph.................................................... joklqvsxywh5...................................................fepqutzs...................................................... gjlnrpph.............................................d.......... cirpul..................................................... Inpotj.......................................................... gmvtCq.......................... ciloyr............................................................ iln t............................................................. dkl f........................................................... horg........................................................... anti................................,,............,.................r.....................,.........., *,,o............................ ~........... I.....................,,................ I.............XX..............................,, *,..............................mm...........o...................,,*,.........................................o..................., o,o........................ I......................................... o.............................................................. *,.........,................................o.................,,,,.,.,,o,.....,,.....,,.........................o...............,,,,.,.......,,........................., I.......,................,..o,,..........................................,................. o,................,...............................................,. e.......,...............,...................................,e qe e......................,..,.................e...............o.. *.......................,..... I..........,..................... o........................................................... Fixed radius eccentricity:.368 x 10 Variable radius eccentricity =.108 x 100 FIGURE 10 -IMAGE #3

.**..1...........G............... qjtf.........3....................................I........ kKog...hs78..................................................GngO89.fshnaG.............................................pzmgh.pxqDv.................................................. d lsrCzto. yzC. o..............................................lajog.hqqEDEChppno2................... * 3.maumEAwokvrluqbc.........7.b428.......................... oAB.ztpCqswAk........... 2hgusmg. 9..........................S9utvKyBtEsgrFDoo$.........5okqms.ouqi6..................... 3ywxba3..rEEqur..... 39dvxAxxrCuy~o.......................... tDCEmbkffhkjomruqs$ryc?7............................evvopDEBywmyrAovkxrxNKE....................................... 5frB.pjstXyzqDFwmqqsHwl.................g9 1................onCvvCyhEvArmCxvtqug2e................... a nnsmwqpxxtzuq qCqxpzuxf*.................... 0............ Obj BBpoyqn uumdxHwwgqxekHtu2................................. 4cfnzxzyyyDFljnl vBAsvAkwxBwvFpj...............................eqvwvFrsxtlzsqjrBqExyAno rGkAnl...................... c q.......... C xyKpvpsBwDu ErABAAusBEpEvHztvl9............................... kmvt tDyCxtxxkCmvuDzzuwxrBAOpH80.................................. 3808rkt l.rloyxwpGxFvmml..................................... ~.t.... gFwBlpvEBEzpEDsx3a.................................... 3wx whnr qr... 3 i.xxru.................................. 299uyvyfAxtsDob................................................... jvaCqnmmCrmGue......................................... 5kmjbjvtAACf....................................... B.bmqqqAg.................................... a w ulxj.......................~..~.r oxuyy5n................................kvty~tx~vu r En............................................lyx..jgfgyo.........................................................47qkfg...................................................................................... 5r'gr5................................................... Ohfkl........................ ~.. o......... o,,................... km b j iA c..................................................b q q g............D1.................................................... 9 I.....u 9.......................~~~~~~~~~.J............., o,......,.,..................I.......,br ~ i.......................,........,........................ 7 g g o......................... ~''*'*''**''''*'*'*'''*'''''''' 7qkf....''', *-..................., o.,.................................... i i O............... I........,...,............................. j..................................,........................... a I.........................,..,.. o.,.....,............................ h S.........................,.a...,.3mam~wkvl...............................................................................*~ s g9..........................Qu...........S.........msoqi,.........................Fixed rad.....us eccentricity.. 348 x 0...........................................~e~H ~ 2........ -2 Variable radius eccentricity =.946 x 10 FIGURE 11 - IMAGE #3 ROTATED 15 DEGREES WITH 10 UNITS OF NOISE

,. 0, 0........................................ j......... I.........., o;....................................... h q................ I.................................. a c.......... v j e u.............................................. tq7........................c7.ue.............................. Dt5......6p%............................................. 7................plwLuvt... t.................... I...p.t..................... isH3.sjkqzb..... DevRTMLs*.................................... ahMfgx4dqso~j......lz.BjJADE3............................ 4BoDrPmora..... 2Fsjigcaj.................... jvAORy3...fs7xGyCB.g....................................... on ye......................................aHsfstel..kagALFxEAr..................................... kZHMmkWSAc.....................................e.hDpmrmwogqNyP nsw MKu...... G................................... cEvCjhAePmouxC. IeupvKhsm..................................... aBKDwHj.femacAcBp dalHApvv3...................................... b7DxnB7..7xiegdHkCmkfpQSDb.g................................... zgoKA3......eChqMpjtrQmmGa2.................................. r.......NFHu!ejxOjFh...................................... C4.....s7x~yCBPA........................................... lHvny KhrcvpBxEFkgzte........................................... mekTAaxACjKKgNrNwmyod......................................... o72 IBgmGG kpznueCwTpRuv........................................ zexhzp jwEh7wFhxo y jsuOJg........................................ EvJrAKjBHNXidhhtCF9zmyn..................................... 6B jvBuCCDAnwdpueffhJHgFFu4.....................................b. D lpCFk.qJH16AevBk.ypHrAyk..................................... u8ck,4qM 0 2s1mAm zct.................................qpq.B Jn6hh................................... 8.4Fsj osEq v...............bjd...................................dopdJur..................g2.p.av4...........................................................AekrB.................. 3.... 7 I g G i z u w p uv.......................~O...................................... B l ~ ~ w h w h g s D g........i..............,............................. E rA J H h d g C zm n...................o....o. o........................... B v u C nw p e f j g u4.....................,,.................. B I p~.q H 6 v k.y r yk...............................,,......o.........., f m u h...i c.4 s s mA z t...................,..............,......,...,...... q q ~ h h.......d..&..h H c b n...............................,......... S......~................ g 7 p......................,................... do J u................. g.p. v................ ~,................... J*........................ A k B.........................................g..................cHbO............. ~..,..,.....,.,.,.........,........................ M...........,..,,..,...................................................-........,.,,,....o...o,................................................... ~........................... I...................................,.,e,,..............................................................,,,..,...,................................................... ~.............................................. I................ Fixed radius eccentricity =.428 x! Variable radius eccentricity =.1.20 x 100 FT~UE 12 I TAGE #3 RQTATED 45 D)EGREES WITH t2O UNITS. OF NOISE UNIVERSITY OF MICHIGAN...........................~~~~III IJI rlJIll lr il I J~l IJIl lI Il I[ I............. IJ...... 39~015 03027 6888................. I................................................................................................. I..................................................................... I......... I~~~~~~~~~~~~~~(~~~~~ ~(~~~~~~Fixed radius eccentricity.428 x 10- (~ll~~~~~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~((~ ~~~~~ ~~~~~~~~~~~~~~1~~~~~ ~Variable radius eccentricity =.1.20 x 10 M,;URE12 T-MGE #3 OTATED45 DEGEES WTII t2OUNTTS F NQIS