--- title: "Chain of Circles for Matching and Recognition of Planar Shapes" authors: - "Jae-Moon Chung" - "Noboru Ohnishi" doi: "" url: "https://ijcai.org/proceedings/1997/213" pdf: "https://ijcai.org/proceedings/1997/0213.pdf" venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence" year: 1997 pages: "1482-1486" track: "Vision" keywords: --- # Chain of Circles for Matching and Recognition of Planar Shapes Jae-Moon Chung, Noboru Ohnishi *Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1482-1486. ## Abstract Based on a resulting medial axis co nfiguration of planar shapes, a new s hape descriptor called the c hain of circles (CoCs) is defined herein. The CoCs represe ntation is directly extracted along the boundary contour of silhouette images, and can be co ntr olled in a hierarchical manner which appeals to intuition . The coarseto-fine hierarchy makes matching of shapes possible with less computational complexity and greater robustness to noise , spatial quantization and local deformation of shapes . The dissimilarity vector calculated in the matching , which is executed via the dynamic programming technique , may be used to facilitate the searching process in the digital library. The capability of the proposed method is shown by matching several co mplex shapes such as map images ## Full text ## 1 Introduction Compared to the curvature-based shape descrip­ tions [Mokhtarian and Mackworth , 1986; He and Kundu, 1991; Sederberg et al., 1993; Siddiqi and Kimia, 1995) , the axis-based methods [Blum, 1967; Blum and Nagel, 1978; Brady and Asada, 1984; Rosenfeld, 1986; Leyton , 1988; Saint-Marc et a/., 1993; Rom and Medioni, 1993; Zhu and Yuille, 199.5; Ogniewicz and Ki.ibler, 1995) are known to be capable of describing shapes in terms of the region surrounded by the boundary, as well as the boundary itself, simultaneously. Although this is not dealt with in this paper , we intuitively know that shapes with holes, as shown in Figure 1(a) , also can be rep­ resented directly by the axis-based description without using any other intermediate representation. Several axis-based descriptions [Blum and Nagel, 1978)[Zhu and Yuille , 1995] require the analysis of axis connections to find branch points where shapes are par­ titioned into their parts. However. it is difficult to find stable branch points , as discussed in [Zhu and Yuille, 199,)). in which they used a top-down approach using shape models to solve the problem. which can deal with only the formal shapes, as shown in Figure 1(b) . Blum's medial axis transformation (MAT) [Blum, 1967) and its effective calculation [Lee , 1982) has conventionally been used to calculate the a..xis . However, the use of MAT has been criticized because the axis obtained is very sensi­ tive even to a slight deformation of shapes, as shown in Figure 1(c). Although several ideas [Blum and Nagel, 1978J[Ogniewicz and Ki.ibler , 1995) have been proposed to solve this problem, a more systematic approach is re­ quired . · He is also with Dept. of Information Eng .. School of Eng .. Nagoya Univ .. Japan Figure 1: (a) A planar shape with a hole. (b) An exam­ ple of formal shapes. (c) The rectangle can be described using the axis obtained by applying medial axis transfor­ mation to its boundary contour (left), but the descrip­ tion is greatly affected by even a slight deformation of the contour (right). (d) Examples of nonformal shapes. These are difficult to describe using verbal representa­ tion and to decompose into parts. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000000_8951cc382f705a6360f5214f3c5f62a5281c4626ed4771c2f5fc7d2cc7c3c1b8.png) In this paper , we present a new planar shape descrip­ tion called the chain of circles (CoCs) . As an a..xis (or region)-based representation, the CoCs is rich and in­ variant to rotation and translation of shapes. The CoCs also has hierarchical description capability, i.e, the ca­ pability to represent shapes at various levels of detail on demand . Using this capability, it is shown how we can get robust representation against noise and local de­ formation of shapes. Examples of shape matching and recognition using the CoCs are presented for fairly com­ plex shapes such as those shown in Figure 1( d). ## 2 Chain of Circles ## 2.1 Medial Axis Transformation Figure 2: A collection of the maximal disks (MDs) ob­ tained for the inner part of a map of Australia. A max­ imal disk has its center at a point on the medial axis of the boundary curve. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000001_8e0220948f06aff39dc0ce28a65fded21245e16c89f77e7d684b2f77cf66ddaf.png) The idea of MAT was developed by Blum [Blum, 1967] to extract the medial (or symmetric) axis of planar shapes. From the physics of grass fire 1 , it can be said that the medial axis is uniquely determined for a planar shape. The medial axis generated by applying MAT to a boundary curve can also be considered as the locus of the center of the maximal disk (MD) , as shown in Figure 2. MD is a circle which does not cross the boundary curve and touches at least two points on the curve. Several al­ gorithms have been proposed for effective computation of MAT of a curve approximated by a polygon [Lee, 1982]. The vertexes of the polygon are sampling points on the curve. ## 2.2 Chain of Circles (CoCs) As shown in Figure 3(a) , in shapes represented by a collection of MDs, a MD generally has two points x1 and x 2 which contact the boundary contour of the shapes. The two points are mutually corresponding. The cor­ respondence arises from the fact that the two contact points share a common MD. The CoCs is defined by r( x) and ¢( x) along the arc length x of a boundary con­ tour curve. (See Appendices A and B for proof of the validity of the CoCs as a shape representation). At each point , for example x 1 , the MD is described by r(x1) the radius of the MD and <b(x!) the angle from x1 to the corresponding point x2 around the center of the MD in the clockwise direction. The point x 2 is described in the same manner . The range of ¢(x) is between 0 and 2;r (rad] . Although the CoCs can be extracted for both the in­ ternal area and the exterior of the boundary contour of shapes, we here use only the internal area, as shown in Figures 3(b) and (c). Depending on the local geometry of shapes, there is a MD that has more than two contact points. For the uniqueness of description in this case , we use a ¢( x) value closest to ;r. 1 In the case that we fire the boundary line of a shape writ­ ten on grass simultaneously. the line of extinction is uniquely determined depending on the shape. Figure 3: Definition of chain of circles, represented by (a) r( x) and ¢( x) along contour arc length x . (b) A rectangle and its axis. (c) Extracted CoCs representation for one rotation of (b) starting from the upper left corner and moving in a clockwise direction. The dotted and solid lines correspond to r(x) and ¢(x), respectively. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000002_c42915b57073fec5901eaddcd66539dc09aa0edd96b03e3549cae5eb1ce7c004.png) ## 2.3 Control of CoCs: Robust Description Prior to describing the control of CoCs, we redefine !9( x) and rn(x) as where rn(x) denotes the normalized percentage of r(x) to rmar which is the radius of the largest MD in the CoCs representation of a shape, and is set to 100. As observed in [Blum and Nagel, 1978][0gniewicz and Kubler , 1995], we consider that MDs with small values of rn (X) and u( X) in a CoCs representation localize only noise or very small corner features. Following this obser­ vation , here the criterion for controlling the CoCs repre­ sentation is set as, where r 0 and t?c are bias values corresponding to rn(x) and tJ(x), respectively. Figure 4 shows the criterion for controlling the CoCs representation based on equation (3) . Among whole MDs in the CoCs representation of a shape , only MDs corresponding to the right side of a line are used in the description of a shape. Using a set of parameter values of equation (3) , the CoCs representation in Figures 3(b) and (c) is reconstructed as shown in Figure 5. Figure 4: Control of CoCs . Each numeral on solid lines indicate r values when both rc and 1Jc are 0. The dot­ ted line is for (f=1500, rc=O, 1Jc=-10), the dashed line (1500, 10, 0) and the dot-dash line (1500, 10, -10) . ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000003_a78c3c01df6e910b5c714caa681629f17d768c7135df1806134273ae9694fe43.png) Figure 5: Controlled CoCs representations with f=1500 , rc=O and Vc=O. (a) The thick points on the boundary contour line display contour points used in each repre­ sentation, and thin points show unused points. (b) The lines show interpolated results for unused contour points using the neighboring used contour points. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000004_4548a5f45ec31bfd93ca4db259964d967d38ce48c7a28125676662e6cc325531.png) Figure 6: (a) A notched image of the rectangle. (b)(d) Uncontrolled and (c)( e) controlled CoCs representations. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000005_ed48ed10b1ddfde7e54e799b75cfb971ce8bdb40fef949f7c6af2e4664984f75.png) Figure 7: (a) A noisy image of the rectangle. (b)(d) Uncontrolled and (c)( e) controlled CoCs representations. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000006_e7e3e61feb8eada463cf9f473ef6fcc467d101bbe94dd045bd9c92bffef6d433.png) Figures 6 and 7 show the robustness of shape descrip­ tion obtained from the control of the CoCs representa­ tion. The parameter values used are the same as those used in Figure 5. Note that Figures 6(e) and 7(e) become similar to Figure 5(b) due to the control , even though their uncontrolled original was corrupted. ## 3 Hierarchical Approximation of Nonformal Shapes Figure 8 shows how nonformal shapes are hierarchically approximated based on CoCs representation. The values of parameters r c and 1} c in equation (3) are selected to be 10 and -10, respectively. The hierarchy of the descrip­ tion is obtained by controlling the value of r. Figure 9 shows the corresponding CoCs representation. ## 4 Matching and Recognition ## 4.1 Matching Using DP The dynamic programming (DP) technique is used to match a pair of CoCs representations. We can expect computational efficiency because matching is possible based on the ordering constraint , as used in [Sakoe and Chiba, 1978; Geiger et a/. , 1995] . If there are I points in one and J points in the other of a pair of CoCs which must be matched, and I is greater than J , a match sequence of length K is a set of point matches P, as where twice the number of J points must be made for a match which does not depend on starting points of the two CoCs representations in the matching process. The score S for the match sequence P is defined as the sum of the individual similarity scores s as ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000007_08086bfd7b5e12509e90f742d1590cda2c6c1cd2e68eec0d4290d915bb51f733.png) ,,, !0 Figure 8: The hierarchical approximation of the map of Australia, each of which is displayed as the collection of MDs used . The values of r and the numbers of contour points are (a) 0, 204 points (b) 1000, 98 (c) 1500, 66 (d) 2000, 46 (e) 3000, 32 and (f) 4000, 23, respectively. The problem in matching is to find the match sequence with the highest score, and the computational complex­ ity corresponds to the number of steps, O(I 2 (2J)2) [Ota and Kanade; 1985]. Here the individual similarity score is defined as Figure 9: The CoCs representations for the map of Aus­ tralia. (a) r(.r) , (b) 4>(.r) for Figure 8(a), and (c) r(x) , (d) 4>(.r) for Figure 8(f) . ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000008_9df5dd18582ce7c606a4d3bd9ba381de0e07243ebf672f733c5dba71c2d42071.png) where Smax is a reference value, and w,p, Wr and W.c are weighting factors for each difference for a point pair be­ tween two CoCs representations , and bx denotes the dis­ tance between a point and its previously matched point on each contour line. ## 4.2 Dissimilarity Vector for Recognition For the matched pairs of shapes, the dissimilarity vector D is calculated by averaging each of the differences of r , 4> and b.r between the matched points as where I\ denotes the number of matched points between two CoCs representations. ## 4.3 Computational Complexity Figure 10 shows an example of computational complex­ ity for self-matching of CoCs representations shown in Figure 8. From this, we can see that computational complexity in the matching process is greatly reduced by using the approximated shape representation of the CoCs. Compared to matching with no approximation (f=O) , which takes about 1 hour, for example, match­ ing with an approximation (f=3000) takes just 1 s. Figure 10: Computational complexity depending on the value of f : (a) global and (b) local displays. The hori­ zontal and vertical axes are for the degree of shape ap­ proximation denoted by the values of r' and computa­ tional complexity in matching, respectively. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000009_b41d018f39d25099b04454da32cd8c54ec651abaef2d8457f9429109dec1bfb5.png) ## 5 Experiments In the experiment, rn and 4> on each point of two curves are normalized so that their ma.xima become 100. b.r is also normalized so that the length of each of the two curves becomes 100. In the implementation of matching, the values of parameters in equation (6) were Smax=1000 , Wr=3, w~= 3 and Wr=9. Figures 11 and 12 and Table 1 show shapes used in the experiment , match­ ing results and dissimilarity values used for recognition, respectively. ## 6 Discussions Figure 14 shows the robustness of the controlled CoCs to digitization of shapes. With much computational effi­ ciency, matching using the approximated CoCs was suc­ cessful not only for variously disturbed shapes, but for different shapes, as shown in Figure 12, in which the correctness may be improved, by some means, in the programming of the method. The matching of different shapes is necessary for searching shapes from a digital database. Figure 11: Shapes used in experiments. (a) A noisy im­ age of the map of Australia and its display of collection of MDs. (b) Collections of MDs to the maps of rotated Australia, England and Africa, for r = 0. Rotated Aus­ tralia is used to investigate the effect of spatial quanti­ zation arising from the shift of sampling points on the contour curve. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000010_d3679f180db89de958ff24c62bda02eea5d50de7ee451fe4b5745549c3e60b42.png) Table 1 shows that the dissimilarity vector calcu­ lated via matching has different values depending on the resemblance between shapes. The values of self- ...... .. . .. .. " . Figure 12: The results of matching of the map of Aus­ tralia to (a) its noisy and (b) oriented images, and (c) the maps of Africa and (d) England. In each of the matches, squares show the contour points determined in matching among the points used in each CoCs repre­ sentation (r = 2000) . The lines connecting the squares show matched points between two contour lines. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000011_f880ba38f1e356e79002c3d6148c9923429b3c304690d936f14131e53d849556.png) Table 1: The dissimilarity vectors between the map of Australia (shown in Figure 8) and the shapes shown in Figure 11 when case of the values of r are 2000 and 3000. The columns of A.us , n(A) , r(A), Afr and Eng are for self-matching of Australia, matching of Australia to noisy Australia, rotated Australia, Africa and England , respectively .. | | f=2000 | f=3000 | |------|-----------------------|-----------------------| | A us | (0,0 ,0) | (0,0 ,0) | | n(A) | 10.5(0.71 ,0.65,0.26) | 12.9(0.77 ,0.56,0.28) | | r(A) | 9.8( 0.33,0.74,0.57) | 11.2 0.15,0.72,0.67) | | Afr | 16.1 0.71,0.67,0.12) | 14.1 0.77,0.59,0.22) | | b'ng | 40.0 0.95,0.22,0.21) | 27.6 0.86,0.32,0.36) | matching (Aus) and matching with disturbed shapes (n(A) and r(A)) are zero and relatively small , respec­ tively. As expected, the Australia-England match (Eng) has much higher dissimilarity than the Australia-Africa match (Afr) . Fundamentally, open curve matching is also possible based on the CoCs if the greatest MD in each curve is determined. Although the determination seems to be possible via iteration, we expect to obtain a more con­ crete approach by a theoretical analysis on the CoCs. ## A Local Geometric Analysis As shown in Figure 13, the local geometry of the shape represented by a collection of MDs is analyzed as follows. If y( s) denotes a vector from the origin of a coordinate system to the center of a MD, i.e., a vector on an arc length s of the axis, z a vector from the origin to a point on the edge of the MD, and r(s) the radius of the MD, the shape can be formulated as Because the envelope of the collection of these MDs arises from the intersection of two adjacent MDs, it can be calculated from From equation (9) , we can deduce Figure 13: Local geometry of MDs. ![Image](https://ijcai.org/proceedings/1997/fulltext/213/image_000012_09d3b1fe7157aea4e8a47b8529e7cb156094251e2399b89fbb81d06c038f6d17.png) where y( s) and r( s) denote the derivatives of y( s) and r (s) with respect to s, respectively, and y(s) is in the tangential direction of the axis on s. Let tbe the unit tangent vector to the a.xis curve and formed with the unit normal vector n. An orthonormal frame f-ii is a moving frame and a function of arc length s along the axis curve, as shown in Figure 13. At every intersection point between MDs , a vector z-y(s) makes an angle with an unit tangent vector f. From equation (9), the value of the angle B(s) is As shown in Figure 13, cross-sectional points of MDs are rewritten for the t(s)-ii(s) frame as where rd(s)=r( s )sinB and p(s) = r(s)cosB. The following differential equations are satisfied by the i(s)-n(s) frame : where ~e(s) is the curvature of the axis curve at s. The {(s)-ii(s) frame is moving and is a function of arc lengths. If we user , r, rand /C instead of r(s) , r(s) , r(s) and ~e( s ), respectively, the relative variation of contour points can be derived from equations ( 12) and ( 13) as When r 2 ( s) and r( s) are much smaller than 1 2 , equation (14) becomes Equation (15) indicates that a planar shape can be represented by radius parameters r(s) and r(s) of MDs, and axis parameters ~e( s), t( s) and ii( s) along the arc length of axis s. In addition, equation ( 11) indicates that r (s) is directly related to B(s) . The effect of axis param­ eters in CoCs representation will be briefly discussed in B. ## B Global Geometric Property Compared to Figure 5(b), Figure 14(d) shows that the bending of the a.xis is reflected in the CoCs representa­ tion . There is an apparent difference in the lengths of the upper and lower edges between the two figures . ## References 1. [Mokhtarian and Mackworth , 1986] F. Mokhtarian and A. Mackworth . Scale-based description and recognition of planar curves and two-dimensional shapes. IEEE Trans . Pattern Anal. ,\l[ach. lntell. , 8(1):34-43, 1986. 2. [He and Kundu , 1991] Y. He and A. Kundu . 2-D shape clas- sification using hidden markov model. IEEE Tr. PAM!, 13(11) :1172-1184. 1991. 3. [Sederberg et al., 1993] T . W. Sederberg, P. Gao, G. Wang, and H. Mu . 2-D shape blending: an intrinsic solution to the vertex path problem. Computer Graphics, pages 15- 18, 1993. . 4. This condition corresponds to a controlled representation of shapes with a large value of r . .. -. -.--. .. •• ,• / / .. • .•<-. ' / / ,••• •• ... •.• (a) ::. ' ,, : :::'• •-... (bl . (d) Figure 14 : Bending of a rec tangle . (a)(c) The uncon- trolled and (b) ( d) controlled shapes and CoCs represen- tations (r = 1500) . 5. [Siddiqi and Kimia, 1995] K. Siddiqi and B. B. Kimia. Parts of visual form: computational aspects. IEEE Tr. PAM!, 17(3):239-251 , 1995. 6. [Blum , 1967] H. Blum. A transformation for extracting new descriptors of shape, In W. Wathen-Dunn , editor, Models for perception of speech and visual form , MIT Press, 1967. 7. [Blum and Nagel, 1978] H. Blum and R.N . Nagel. Shape de- scription using weighted symmetric axis features. Pattern Recog., 10:167-180, 1978. 8. [Brady and Asa.da., 1984] M. Brady and H. Asa.da.. Smoothed local symmetries and their imple- mentation . Int. J. Robotics Research, 3(3):36-60, 1984. 9. [Rosenfeld , 1986] A. Rosenfeld. Axia.l representations of shape. Comput. Vision Gr. Image Proc., 33:156-173, 1986. 10. [Leyton , 1988] M. Leyton. A process-grammer for shape. Ar- tificial Intelligence, 34:213-247 , 1988. 11. [Sa.int-Ma.rc et al. , 1993] P. Sa.int-Ma.rc, H. Rom, and G. Medioni. B-spline contour representation and symme- try detection . IEEE Tr. PAM!, 15(11):1191-1197, 1993. 12. [Rom and Medioni, 1993] H. Rom and G. Medioni. Hierar- chical decomposition and axial shape description . IEEE Tr. PAM!, 15(10):973-981 , 1993. 13. [Zhu and Yuille, 1995] S. C. Zhu and A. L. Yuille. FORMS: a. flexible Object recognition and modeling system. Proc. I CCV'95, pages 465-4i2, 1995. 14. [Ogniewicz and K iibler, 1995] R. L. Ogniewicz and 0 . Kiibler, Hierarchic voronoi skeletons. Pattern Recog., 28(3):343-359, 1995. 15. [Lee, 1982] D. T . Lee. Medial axis transformation of a planar shape. IEEE Tr. PAM!, 4(4) :363-369, 1982. 16. [Sa.koe and Chiba., 1978] H. Sa.koe and S. Chiba.. Dynamic programming algorithm optimization for spoken word recognition . IEEE Tr. Acous. Speech Sig. Proc. , 26(1):43- 49, 1978. 17. [Geiger et al., 1995] D. Geiger , A. Gupta., and J. Vlontzos. Dynamic programming for detecting, tracking, and match- ing deformable contours. IEEE Tr. PAM!, 17(3):294-302, 1995. 18. [Ota and Ka.nade, 1985] Y. Ota. and T . Kanade . Stereo by intra.-and inter-scanline search using dynamic program- ming . IEEE Tr . PAM!, 7( 2): 139-1 54,1985.