J. Cent. South Univ. (2012) 19: 488-495

DOI: 10.1007/s11771-012-1030-5

Modified Fourier descriptor for shape feature extraction

ZHANG Gang(张刚)¹, MA Zong-min(马宗民)², NIU Lian-qiang(牛连强)¹, ZHANG Chun-ming(张纯明)¹

1. School of Software, Shenyang University of Technology, Shenyang 110023, China;

2. College of Information Science and Engineering, Northeastern University, Shenyang 110004, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2012

Abstract: A modified Fourier descriptor was presented. Information from a local space can be used more efficiently. After the boundary pixel set of an object was computed, centroid distance approach was used to compute shape signature in the local space. A pair of shape signature and boundary pixel gray was used as a point in a feature space. Then, Fourier transform was used for composition of point information in the feature space so that the shape features could be computed. It is proved theoretically that the shape features from modified Fourier descriptors are invariant to translation, rotation, scaling, and change of start point. It is also testified by measuring the retrieval performance of the systems that the shape features from modified Fourier descriptors are more discriminative than those from other Fourier descriptors.

Key words: shape feature extraction; Fourier descriptors; centroid distance approach

1 Introduction

Shape is one of commonly used low-level visual features. As shape can characterize an object effectively and carry semantic information, it has received more concerns in content-based image retrieval, pattern recognition and computer vision. Currently, approaches for shape feature extraction can be divided into two categories: contour-based approach and region-based approach [1]. Contour-based approaches extract shape feature from contour of an object. Commonly used contour-based approaches contain Fourier descriptors, curvature scale space descriptors, autoregressive models, wavelet descriptors, global shape descriptors and shape signature [2-4]. Region-based approaches extract shape features from inner of an object. Commonly used region-based approaches contain Zernike moments, Legendre moments and geometric moments [5-7].

For image recognition, region-based approaches usually have better performance but larger computational complexity than contour-based approaches. Besides, psychophysiology studies show that shape features are mostly used for classification instead of recognition. Therefore, if they have smaller computational complexity and classification performance similar to or even better than region-based approaches, these contour- based approaches would have more extensive research and practical value.

Early studies showed that Fourier descriptor is a classical contour-based approach for image classification. In terms of retrieval accuracy and efficiency, Fourier descriptor was proved to outperform most other boundary-based approaches and some region-based approaches [8-10]. It uses boundary pixels of an object in an image to compute shape signature. Fourier transform is used for the shape signature to compute Fourier coefficients. Then, the Fourier coefficients, which are invariant to translation, scaling, rotation and change of initial point, are used for shape features.

Recently, extensive studies have been carried out for performance of Fourier descriptors. ZHANG and  LU [11] evaluated some modified versions of Fourier descriptors. EL-GHAZAL et al [12] used Fourier descriptors for original image and computed shape features by ignoring the phase information and only using magnitude of the coefficients. Moreover, it was proposed that the shape features are not invariant to rotation. El-Ghazal et al used curvature scale space approach to compute zero-crossing point set, and used binarization to compute the feature image. Then, two- dimensional (2D) Fourier transform was used for the feature image to compute Fourier coefficients. Magnitude of normalized coefficients was used as shape features which are invariant to rotation. BARTOLINI et al [13] presented that the features from the approach, which ignored the phase information and only used magnitude of the coefficients, are invariant to rotation. But discrimination of shape features would be reduced. BARTOLINI et al used phase compensation for Fourier descriptors. Discrimination of features could be kept or improved and shape features are invariant to rotation. KUNTTU et al [14] used Fourier descriptors for images of different scales to compute shape features.

In the above approaches, geometry information of a local space is used. However, not only geometry information but also non-geometry information is contained in the local space. Our idea is to use geometry and non-geometry information of the local space together, so that more discriminative shape features can be computed. Of course, shape feature extraction is mainly for geometry information of an object. But non-geometry information under global geometry information cannot be ignored. In this work, the relation between geometry information and non-geometry information in the contour of an object is studied. Production operation is used to characterize the dependency of geometry information and non-geometry information. Fourier transform is used for composition information to compute shape features which are invariant to translation, rotation, scaling and change of initial point. Visual effects of before-and-after rebuilt centroid distance signature curves are used to compute dimension of shape feature vectors of each kind of images.

In the previous studies, we have verified that the approach, which introduces brightness of boundary pixels into computation of shape features, can improve the discrimination of shape features [15]. More works are carried out further. Theory structure is proposed. Computation of dimension of shape feature vector is added. Invariance of shape features to translation, rotation, scaling, and change of initial point is verified. Retrieval precision and recall curves are commonly used approaches which can analyze the discrimination of features effectively. Here, verification of discrimination of shape features is carried out among the approaches: Fourier descriptors, Fourier descriptors proposed by Bartolini using the retrieval precision and recall curves.

2 Modified Fourier descriptors

2.1 Characterization of relation between geometry and non-geometry information of object contour

Suppose that f(x, y) is a gray image of size M ? N. The image only contains a single object. Binarization is used for the image. Then, canny edge detection operator and boundary tracing algorithm are used to compute the boundary pixel set of the object, which can characterize geometry information of object contour. However, each element of the boundary pixel set does not only contain geometry information for f(x, y), but also contain non-geometry information. Anti-aliasing technology uses gray to reduce jaggies of object boundary in computer graphics. A gray circle and its partial gray values are shown in Fig. 1.

Fig. 1 Gray circle and its partial gray values

From a cognitive perspective, geometry information characterizes global shape features for the gray circle, and non-geometry information describes the microscopic properties of shape. So, we would use a pair (geometry information and non-geometry information) to describe a point in the boundary pixel set of the object.

2.2 Shape feature extraction

ZHANG et al have compared different Fourier descriptors, which use centroid distance, complex coordinates and curvature function as shape signature, respectively. Centroid distance Fourier descriptors are testified to have better performance as a whole. So, modified Fourier descriptors would use the above idea for centroid distance Fourier descriptors.

Binarization is carried out for f(x, y). Then, canny edge detection operator and boundary tracing algorithm are used to compute the boundary pixel set of the object in f(x, y). Suppose that BP denotes the boundary pixel set and C denotes the number of boundary pixels, then the centroid of the object (x_c, y_c) can be denoted as

,                  (1)

where (x(t), y(t)) denotes the location of the t-th pixel of the set BP in f(x, y). Suppose that r(t) denotes the distance of the t-th pixel of the set BP to the centroid, then r (t) can be denoted as

r(t) = ([x(t) – x_c]² + [y(t)-y_c]²)^1/2, t = 1, …, C       (2)

So, geometry information set of object boundary of f(x, y) can be denoted as B={r(t)|t = 1, …, C}.

Suppose that g(t) denotes the gray value of the t-th pixel of the set BP in f(x, y), then non-geometry information set of object boundary of f(x, y) can be denoted as G={g(t)|t = 1, …, C}.

Suppose that Y denotes the relation set of geometry and non-geometry information of object boundary, then Y can be denoted as

Y = {r(t)·g(t)|t =1, …, C}                     (3)

where a pair (r(t), g(t)) denotes a point in the feature space.

Suppose that j(t)=r(t)·g(t). If Fourier transform is used for j(t), then Fourier coefficients a_n can be denoted as

, n = 0, …, C-1     (4)

The first coefficient is used to normalize all Fourier coefficients. The phase information of the coefficients is ignored and the magnitude is only used. Then, shape features can be denoted as

s(n) =|a_n/a₀ |, n = 0, …, C-1                    (5)

For invariance to translation, shape feature vector is made up of the 2nd to the (k+1)-th shape features. Suppose that S denotes shape feature vector of f(x, y),

then S can be denoted as

S=[s(1)  s(2)  …  s(k)]                      (6)

2.3 Computation of parameter k

Here, visual effects of before-and-after rebuilt centroid distance signature curves are used to compute the dimension of shape feature vector of each kind of images k. We call j(t) as centroid distance signature function of feature image of f(x, y), and call r(t) as centroid distance signature function of f(x, y). Three gray circles and their centroid distance signature curves are shown in Fig. 2. Here, the first is a full circle, the second is a circle of non-smoothing edge, and the third is a defective circle.

Fig. 2 Three circle and corresponding j(t) and r(t) curves: (a) Full circle; (b) Circle of non-smoothing edge; (c) Defective circle

It is found from Fig. 2 that the j(t) curve of the full circle is similar to that of the defective circle and r(t) curves are different, and that the j(t) and r(t) curves of circle of non-smoothing edge are different from those of the full circle and the defective circle. This means that non-smoothing object edge has an effect on centroid distance signature function.

Equation (4) is used to compute Fourier coefficients. The top 5, 10, 15 and 20 coefficients are used to rebuild j(t) and r(t), respectively. When the top 10 coefficients are used, the j(t) and r(t) curves of the above three circles after reconstruction are shown in Fig. 3.

It can be found from Fig. 3 that the j(t) and r(t) curves after reconstruction are similar to those before reconstruction when the top 10 Fourier coefficients are used. So, the dimension of shape feature factor k is selected as 10 in the following experiments.

2.4 Verification of invariance of shape features to translation, rotation, scaling and change of initial point

Here, verification of invariance of shape features to translation, rotation, scaling and change of initial point, which is computed from Eq. (5), is carried out from theory.

Centroid distance signature function of the feature image is invariant to translation, so s(n) is invariant to translation. We define the general form of Fourier coefficients of j(t) by referring to GRANLUND’s approach [16]. For a_n from Eq. (4), if denotes a_n transformed through translation, rotation, scaling and change of initial point, then can be denoted as

= exp(jnt)×exp(jf)×s×a_n                       (7)

where the parameter t and f denotes the angles incurred by the change of initial point and the rotation, respectively. The parameter s denotes the scale factor.

Fig. 3 j(t) and r(t) curves after reconstruction: (a) Full circle; (b) Circle of non-smoothing edge; (c) Defect circle

The first coefficient is used to normalize all , then  can be denote as

    (8)

If the phase information of the coefficients is ignored and the magnitude is only used, then s(n)=|| is the same as s(n)=|a_n/a₀|. That is, s(n) from Eq. (5) is invariant to translation, rotation, scaling and change of initial point.

3 Experiments and performance analyses

To verify the discrimination of shape features from modified Fourier descriptors, the experiments are carried out. Image database is made up of 3 000 images, and these images are all gray images. These images can be divided into 15 kinds, such as butterfly, leaf, and penguin. Each kind contains basis images and the images transformed by translation, rotation, scaling, etc. Test code is compiled by Matlab, and the machine configuration for test is Intel(R) Celeron(R) mainboard, 1.60 GHz CPU main frequency and 256 MB memory.

We build an image retrieval system, which consists of feature extraction, feature description, and similarity measure. At the feature extraction stage, modified Fourier descriptors and Fourier descriptors [8] are used to extract shape features, respectively. At the feature description stage, the top (k=10) Fourier coefficients are used to form a shape feature vector. At the similarity measure stage, Euclidean distance [17] is used to measure the similarity between images. Besides, retrieval precision and recall [18] are used to measure retrieval performance of systems using different approaches.

3.1 Comparisons of discrimination of shape features from modified Fourier descriptors and Fourier descriptors

3.1.1 Comparisons of visual effects of systems using Fourier descriptors and modified Fourier descriptors

The discrimination of shape features from modified Fourier descriptors is testified from visual effects. The 300 images from 20 kinds are selected from the image database to form an image set for retrieval. The 20 images, of which elephant, butterfly, apple, leaf are 5 images, respectively, form an image set for query. Retrieval tests are carried out for each image in the query image set. The visual effects of the top ten images retrieved are used to measure the discrimination of shape features from modified Fourier descriptors and Fourier descriptors [8]. Two of retrieval test results are shown in Fig.4. Here, the images from the system using Fourier descriptors are at the first row, and those from the system using modified Fourier descriptors are at the second row.

It can be found from Fig. 4 that the shape features from modified Fourier descriptors are more discriminative.

3.1.2  Statistical analyses of retrieval results of systems using Fourier descriptors and modified Fourier descriptors

The discrimination of shape features from modified Fourier descriptors are analyzed from statistics. The 40 images, of which elephant, butterfly, apple, leaf are 10 images, respectively, form an image set for query. Retrieval tests are carried out for each image using a class as a unit. Retrieval precision and recall are used to measure retrieval performance of systems. We compute retrieval precisions when recalls range from 10 to 100 with 10 as interval. The average of retrieval test results of ten times is used as a final test result. Retrieval precision and recall curves, which show the averages of retrieval precision when recall changes, are shown in  Fig. 5.

Fig. 4 Visual effects of retrieval tests: (a) Query image: apple image; (b) Query image: butterfly image

It can be found from Fig. 5 that the shape features from modified Fourier descriptors are more discriminative. For example, the average retrieval precision of system using Fourier descriptors is 4.55% when recall is 50% for Fig. 5(a), whereas the average retrieval precision of system using modified Fourier descriptors is 71.43%.

Retrieval precisions usually decrease when recalls increase for retrieval precision and recall curves [19]. However, Fig. 5(c) and Fig. 5(d) show that retrieval precisions increase when recalls increase locally. For example, Fourier descriptors as shape feature extraction approach and recalls range from 0.4 to 1 with 0.1 as interval. From the experimental process with apple images as query images and query result of each time, it is found that similarity between apple images exceeds that between apple image and other images. Images retrieved are all apple images when recalls range from 0.4 to 1 with 0.1 as interval. This result in the phenomenon is increased locally in Fig. 5(c).

3.2 Comparisons of discrimination of shape features from modified Fourier descriptors and other Fourier descriptors

Comparisons are made between modified Fourier descriptors and the Fourier descriptors proposed by BARTOLINI et al, so that the discrimination of shape features from modified Fourier descriptors can be testified further.

BARTOLINI et al used time warping distance as similarity measure. Here, for the purpose of comparing the discrimination of shape features, Euclidean distance is used as similarity measure uniformly.

3.2.1 Comparisons of visual effects of systems using modified Fourier descriptors and other Fourier descriptors

The 300 images from 20 kinds are selected from the image database to form an image set for retrieval. The 20 images, of which elephant, butterfly, apple, leaf are 5 images respectively, form an image set for query. Retrieval tests are carried out for each image in the query image set. The visual effects of the top ten images retrieved are used to measure the discrimination of shape features from modified Fourier descriptors and Fourier descriptors proposed by BARTOLINI et al. Two of retrieval test results are shown in Fig. 6. Here, the images from the system using Fourier descriptors proposed by BARTOLINI et al are at the first row, and those from the system using modified Fourier descriptors are at the second row.

Fig. 5 Statistical curves of retrieval results: (a) Query image: elephant image; (b) Query image: butterfly image; (c) Query image: apple image; (d) Query image: leaf image

It can be found from Fig. 6 that the shape features from modified Fourier descriptors are more discriminative.

3.2.2  Statistical analyses of retrieval results of systems using modified Fourier descriptors and other Fourier descriptors

The discrimination of shape features from modified Fourier descriptors is analyzed from a statistical point of view. The 40 images, of which elephant, butterfly, apple, leaf are 10 images, respectively, form an image set for query. Retrieval tests are carried out for each image using a class as a unit. Retrieval precision and recall are used to measure the retrieval performance of systems. The average of retrieval test results of ten times is used as a final test result. Retrieval precision and recall curves, which show the averages of retrieval precision when recall changes, are shown in Fig. 7.

Fig. 6 Visual effects of retrieval tests: (a) Query image: butterfly image; (b) Query image: apple image

Fig. 7 Statistical curves of retrieval results: (a) Query image: elephant image; (b) Query image: butterfly image; (c) Query image: apple image; (d) Query image: leaf image

It can be found from Fig. 7 that the shape features from modified Fourier descriptors are more discriminative as a whole. For example, Fig. 7(b) shows that the average retrieval precision of system using modified Fourier descriptors is 94% when recall is 50%, whereas the average retrieval precision of system using Fourier descriptors proposed by BARTOLINI et al is 83%.

4 Conclusions

A modified Fourier descriptors is presented. This approach uses the relation between geometry and non-geometry information in the contour of an object. After the boundary pixel set of the object is computed, centroid distance approach is used to compute the shape signature. Then, a pair (shape signature and gray value of corresponding boundary pixel) is used as a point in the feature space. The relation of geometry and non-geometry information of contour of the object is used to compute the information composition of a point in the feature space. Fourier transform is then used for composition information to compute shape features, which are invariant to translation, rotation, scaling and change of initial point. The shape features from modified Fourier descriptors are testified through comparisons among modified Fourier descriptors, Fourier descriptors and Fourier descriptors proposed by BARTOLINI et al. In future, further studies will be carried out. First, the modeling approaches of relation of geometry and non-geometry information of contour of an object will be studied further. Second, information from contour and inner of an object will be integrated effectively to compute more discriminative shape features.

References

[1] BOBER M. MPEG-7 visual shape descriptors [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2001, 11(6): 716-719.

[2] PERSOON E, FU K. Shape discrimination using Fourier descriptors [J]. IEEE Transactions on Systems, Man and Cybernetics, 1977, 7(3): 170-179.

[3] MOKHTARIAN F, MACKWORTH A. Scale-based description and recognition of planar curves and two-dimensional objects [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(1): 34-43.

[4] ZHANG D S, LU G J. Review of shape representation and description techniques [J]. Pattern Recognition, 2004, 37(1): 1-19.

[5] TEH C H, CHIN R T. On image analysis by the methods of moments [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(4): 496-513.

[6] HU M K. Visual pattern recognition by moment invariants [J]. IEEE Transactions on Information Theory, 1962, 8(2):179-187.

[7] TEAGUE M R. Image analysis via the general theory of moments [J]. Journal of the Optical Society of America, 1980, 70(8): 920-930.

[8] ZHANG D S, LU G J. A comparative study of curvature scale space and Fourier descriptors for shape-based image retrieval [J]. Journal of Visual Communication and Image Representation, 2003, 14(1): 41-60.

[9] ZHANG D S, LU G J. Shape-based image retrieval using generic Fourier descriptor [J]. Signal Processing: Image Communication, 2002, 17(10): 825-848.

[10] KAUPPINEN H, SEPP?NEN T, PIETIK?INEN M. An experimental comparison of autoregressive and Fourier-based descriptors in 2D shape classification [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(2): 201-207.

[11] ZHANG D, LU G J. Study and evaluation of different Fourier methods for image retrieval [J]. Image and Vision Computing, 2005, 23(1): 33-49.

[12] EL-GHAZAL A, BASIR O, BELKASIM S. A novel curvature-based shape Fourier descriptor [C]// CHELLAPPA R, GIROD B. Proceedings of the 15th IEEE International Conference on Image Processing. San Diego, CA: IEEE Press, 2008: 953-956.

[13] BARTOLINI I, CIACCIA P, PATELLA M. Warp: Accurate retrieval of shapes using phase of Fourier descriptors and time warping distance [J]. IEEE Transactions of Pattern Analysis and Machine Intelligence, 2005, 27(1): 142-147.

[14] KUNTTU I, LEPIST? L, RAUHAMAA J, Visa A. Multiscale Fourier descriptors for defect image retrieval [J]. Pattern Recognition Letters, 2006, 27(2): 123-132.

[15] ZHANG Gang, MA Zong-min, TONG Qiang, HE Ying, ZHAO Tie-nan. Shape feature extraction using Fourier descriptors with brightness in content-based medical image retrieval [C]// PAN J S, NIU X M, HUANG H C, JAIN L C. Proceedings of the Fourth International Conference on Intelligent Information Hiding and Multimedia Signal Processing. Harbin: IEEE Press, 2008: 71-74.

[16] GRANLUND G. Fourier preprocessing for hand print character recognition [J]. IEEE Transactions on Computers, 1972, C-21(2): 195-201.

[17] ZHANG Gang, MA Zong-min, DENG Li-guo, XU Chang-ming. Novel histogram descriptor for global feature extraction and description [J]. Journal of Central South University of Technology, 2010, 17(3): 580-586.

[18] HUIJSMANS D P, SEBE N. How to complete performance graphs in content-based image retrieval: add generality and normalize scope [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(2): 245-251.

[19] MANNING C D, RAGHAVAN P, SCH?TZE H. An introduction to information retrieval [M]. Cambridge: Cambridge University Press, 2009: 151-175.

(Edited by YANG Bing)

Foundation item: Project(60873010) supported by the National Natural Science Foundation of China; Project supported by the Doctor Startup Foundation of Shenyang University of Technology, China

Received date: 2010-12-08; Accepted date: 2011-04-11

Corresponding author: ZHANG Gang, PhD; Tel: +86-24-25694948; E-mail: zhang_gang_1973@yahoo.com