Chain of Circles for Matching and Recognition of Planar Shapes

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

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

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.

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.

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

,,,

!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

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.

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.

Table 1 shows that the dissimilarity vector calcu­ lated via matching has different values depending on the resemblance between shapes. The values of self-

...... .. . .. .. " .

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

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 .