Shape Matching Using Chord-length Function

Shape Matching Using Chord-Length Function Bin Wang1, and Chaojian Shi1,2 1

Department of Computer Science and Engineering, Fudan University, Shanghai, 200433, P.R. China 2 Merchant Marine College, Shanghai Maritime University, Shanghai, 200135, P.R. China [email protected], [email protected]

Abstract. A novel shape descriptor, chord length function (CLF) which can be obtained by equal arc length partitions of a contour, is proposed. The difference of two shapes is measured by the distance between their corresponding CLF. The proposed CLF is invariant to rotation, scaling and translation. It is robust to noise and simple to compute. Experimental results indicate that CLF is an effective shape descriptor.

1

Introduction

Shape matching is one of the most important tasks in computer vision and pattern recognition. Shape description is key to shape matching. A good shape description scheme is expected to possess the following properties: (1) Invariance to rotation, scaling and translation. (2) Robustness to noise. (3) Simplicity in computation. (4) Reflecting both global and local shape characteristics. A widely used shape description scheme is contour function [1]. The basic idea is to reduce a 2-D shape to a 1-D function, which is easier to handle than the original shape [2]. The primary consideration for the contour functions include the choice of the variable and the choice of the geometric quantity as the value for the function to take. Two candidate variables are in frequent use: one is the angle from a given direction (Fig. 1a), the other is the arc length from a given starting point (Fig. 1b). Most of the existing contour functions can be classified as function of angle or function of arc length. Distance-versus-angle function (DAF)[1] and curvature function (CF) [3] are two widely used contour functions. On the choice of the variable, DAF chooses the angle from given direction as its variable. The potential drawback is that some contours cannot be described as 1-D functions through DAF because some angle may correspond to several different distance values (Fig. 2). Different from DAF, CF chooses the arc length from the starting point as variable, the main advantage is that CF always exists for any contour. On the choice of the characterizing geometric quantity, DAF adopts the distance between the contour points and the contour’s centroid as the function value. As the centroid is collectively determined by the whole contour, the distance from the contour points to the centroid reflects the contour shape in a 

Corresponding author.

E. Corchado et al. (Eds.): IDEAL 2006, LNCS 4224, pp. 746–753, 2006. c Springer-Verlag Berlin Heidelberg 2006 

Shape Matching Using Chord-Length Function

747

Fig. 1. Two candidate variables that can be chosen. (a) Angle from a given direction. (b) Arc length from a given starting point.

Fig. 2. Multiple intersections and distances

global manner. CF, on the other hand, uses the curvature on the contour points as the function value. Curvature describes the extent to which the contour bends. The curvature at a point on the contour can be obtained by computing the reciprocal of the radius of the osculating circle [4] (Fig. 3). As such, CF reflects the local property of the contour and its global characterizing ability is limited. Here, we give an example for illustrating this fact. Fig. 4 shows two shapes, their local features (wavy lines) are very similar, if we use curvature to characterize the contour, it will be very difficult to distinguish them. In contrast, if we use the distance to the contour to characterize the contour, we can distinguish them easily. In this paper, we propose a novel contour function, chord length function (CLF), which is obtained through partitioning a contour into arcs of the same length. It combines the advantages of DAF and CF and overcomes their drawbacks. That is: (1) CLF exists for arbitrary contour. (2) CLF globally reflects the shape while the local features are also considered. (3) CLF is robust to noise and simple to compute. The experimental results show its promising performance.

2

Chord Length Function

A contour can be denoted as a sequence of N points C = {x0 , x1 , . . . , xN −1 }, N −1 where the next point to xN −1 is x0 . Let L = d(xi , xi+1 ) be its perimeter i=0

748

B. Wang and C. Shi

Fig. 3. The computation of the curvature on a point of a contour

Fig. 4. Two shapes with similar local features

and D =

max

0≤i,j≤N −1

d(xi , xj ) be its diameter, where d(.) denotes the Euclidean

distance metric. Let us start from a point xi ∈ C and follow the contour anticlockwise to divide it into k sections, x xi , of equal arc length i s1 , s 1 s2 , . . . , sk−1 and obtain k − 1 chords xi s1 , xi s2 , . . . , xi sk−1 , where sj is the jth division point and k > 1 is a pre-specified parameter. We now have k − 1 chord lengths (i) (i) (i) (i) L1 , L2 , . . . , Lk−1 , where Lj is the length of the chord xi sj . Fig. 5 shows an equal arc length partition of a contour at point xi into eight segments. As (i) the point xi moves along the contour, the chord length Lj vary accordingly, (i)

where j = 1, . . . , k − 1. In other words, Lj are function of xi . Without loss of generality, we specify x0 as the reference point. Then each point xi can be uniquely identified with the length li ∈ [0, L] of arc x 0 xi . Therefore each chord (i) length Lj can be considered as a function of arc length li . Then we obtain a set of chord length functions Φ = {L1 , L2 , . . . , Lk−1 }. It can be seen that each function in Φ is invariant to rotation and translation. To make it invariant to scaling, we use the perimeter L and the diameter D to normalize respectively the arc length and chord length. Then each function in Φ will be linearly rescaled to a function from [0, 1] to [0, 1]. Chord length function is also robust to noise. Fig. 6 gives an example to illustrate it. In Fig. 6, there are two shapes, one is a rectangle and the other is a noised rectangle. Their chord length functions with parameter k = 2 are compared. The result is shown in (c) of Fig. 6. From the comparison, we can see that there is little difference between them. So the chord length function is not sensitive to noise. Note that changing the location of the reference point x0 by an amount t ∈ [0, 1] along the perimeter of contour C corresponds to a horizontal shift of the function Li and it is simple to compute the new function Li (l + t). From the definition of CLF, we can see that k is the only parameter of the proposed method. CLF with small parameter

Shape Matching Using Chord-Length Function

749

Fig. 5. An example of emanating seven chords from a contour point to partition the contour into eight equal-length arcs

Fig. 6. An example for illustrating the chord length functions’ robustness to noise. (a) rectangle. (b) noised rectangle. (c) Comparison of their chord length functions with parameter k=2.

k will be prone to characterize the shape’s global feature, while CLF with large parameter k will reflect both global and local shape characteristics. Therefor, if we expect higher accuracy in shape distinction, k will be set lager.

3

Difference Measure

We have presented a CLF description Φ = {L1 , L2 , . . . , Lk−1 } for a contour. The comparison of two shapes can be performed using their associated CLFs, namely, the degree to which shape A and shape B are different can be measured by the (A) (A) (A) (B) (B) (B) distance between ΦA = {L1 , L2 , . . . , Lk−1 } and ΦB = {L1 , L2 , . . . , Lk−1 } using a metric for function spaces such as the LP metrics. To remove the dependence of the description on the reference point, we shift the reference point along the contour of B by an appropriate amount t ∈ [0, 1], then each function (B) (B) Li (s) in ΦB will be changed into Li (s + t). We need to find the minimum

750

B. Wang and C. Shi

Fig. 7. Images of test shapes used in literature [5]

over all such shift t to find the appropriate one. So we define the L1 distance between A and B as   k   1 (A) (B) dif f (A, B) = min | Li (s) − Li (s + t) | ds . (1) t∈[0,1]

4

i=1

0

Experimental Results and Discussions

The performance of the proposed CLF is tested on the benchmark shapes used in literature [5] as shown in Fig. 7. The benchmark shapes includes nine categories and eleven instances are included in each categories to allow for variations in form, as well as for occlusion, articulation, missing parts, etc., resulting in a total of 99 shape instances. The size of each image in Fig. 7 ranges from 120 × 91 pixels to 148 × 148 pixels. We select two widely used contour functions, distance-versus-angle function (DAF) and curvature function (CF), for comparison. A task of shape retrieval is conducted using DAF, CF and the proposed CLF respectively, on the benchmark shapes. Common performance measures, precision and recall of the retrieval [6,7], are used as the evaluation of the query result. In this evaluation scheme, each shape in the benchmark is taken as a query to match all the other shapes. Top n matched shapes are returned and the number of similar shapes of the same class was counted in these returned shapes, where n equals 11 in our experiments. The precision p and recall r are calculated as p = c/m, r = c/n

(2)

Shape Matching Using Chord-Length Function

751

where c is the number of the returned shapes which are in the same class as that of the query shape, m is the number of returned shapes and n is the number of the shapes which are in the same class (n=11 in this case). When 11 top matched shapes are returned, the precision is the same as the recall. Since there are 11 shapes in the same class, there is no need to report the precision for the number of the returned shapes being greater than 11. For m = 1, 2, . . . , 11, the average precision and recall of all the queries are calculated and a precision-recall plot for each method are presented as shown in Fig. 8, where the parameter for the proposed method CLF is set to k = 2, 4 and 8 respectively. The horizontal axis in such a plot corresponds to the measured recall, while the vertical axis corresponds to precision. Since precision and recall values are computed from m = 1 to 11, where m is the number of the returned shapes, each curve contains exactly 11 points. The top-left point of a precision/recall curve corresponds to the precision/recall values for the best match, i.e, m = 1, while the bottom-right point corresponds to the precision/recall values on the case of m = 11. A method is better than another if it achieves better precision and recall. From the Fig. 8, the proposed method CLF with parameter k = 4 and 8 achieves higher precision and recall than the methods DAF and CF. Therefore we can see that the proposed CLF with parameter k = 4 and 8 is better than DAF and CF. It is noted that the two precision/recall curves, which correspond to the method DAF and the proposed CLF with k = 2 respectively, intersect. This means that DAF perform better when the the number of returned shapes m is small (m <= 9), while the proposed CLF with k = 2 perform better when m is larger (m > 9). Since the method achieving higher precision and recall for the lager number of returned shapes is considered to be the better method [8], the proposed method CLF with parameter k = 2 is also better than the method DAF. From the above experimental results, we can also see that, for the proposed CLF, the larger the parameter k is, the better the retrieval performance is. This is because with the parameter k increased, the more local information of the shape can be obtained, in other words, the more details of the shape can be characterized. So the shape will be described more accurately. Invariance to rotation, scaling and translation is a basic requirement for a good shape descriptor. For examining the invariance of CLF, the following experiments are conducted. For all the 99 shapes as shown in Fig. 7, we increase them in scale by 400%, scale them down by 50% and simultaneously scale them down by 50% and rotate them by 900 . Through these geometric transformations, we obtain three new shape sets. Then each original shape in Fig. 7 is used as a query to match all the three new shape sets respectively. The resulting precision-recall plot are shown in Fig. 9. From it, we can see that, using the proposed CLF, the results of retrieving are nearly identical regardless of their scale and rotation. Therefore, the proposed CLF is an invariant shape description method.

752

B. Wang and C. Shi

Fig. 8. The resulting precision-recall plot for distance-versus-angle function (DAF), curvature function (CF) and the proposed CLF with parameter k = 2, 4 and 8 respectively

Fig. 9. The precision-recall plot for the three shape sets obtained by different geometric transformations of the images in Fig. 7

5

Conclusion

The proposed chord length function (CLF) is a simple and effective shape description method. It is obtained using the equal arc length partitions of a contour. The proposed CLF is invariant to rotation, scale and translation and robust to noise. It can capture both global feature and local feature of the contour and it

Shape Matching Using Chord-Length Function

753

is simple to compute. The experiment results show that it performs better than two widely used descriptors.

Acknowledgement The research work in this paper is partially sponsored by Shanghai Leading Academic Discipline Project, T0603.

References 1. Voldymyr V. Kindratenko, “On Using Functions to Describe the Shape,” Journal of Mathematical Imaging and Vision”, 18, 225-245, (2003). 2. Rafael C. Gonzalez, Richard E. Woods, “Digital Image Processing,” , 2, 648-649. 3. C.-L. Huang and D.-H Huang, “A Content-Based Image Retrieval System” Image and Vision Computing, 16, 149-163, (1998). 4. Francisco J. Sanchez-Marin, “The Curvature Function Evolved in Scale-Space as a Representation of Biological Shapes” Comput. Biol. Med, 27, 77-85, (1997). 5. Thomas Bernier, Jacques-Andre Landry, “A New Method for Representing and Matching Shapes of Natural Objects,” Pattern Recognition, 36, 1711-1723, (2003). 6. A.D. Bimbo, “Visual Information Retrieval,” Morgan Kaufmann Publishers, Inc., San Fancisco, USA, 56-57, (1999). 7. G.Salton, “The State of Retrieval System Evaluation,” Inform. Process. Manage, 28 (4), 441-450, (1992). 8. G.Salton, “Matching and Retrieval of Distorted and Occluded Shapes Using Dynamic Programming,” IEEE Transactions on Pattern Analysis and Machinge Intelligence, 24 (11), 1501-1516 (2002).