A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures

similarity between two feature vectors of the two

shapes, this is impractical for higher dimensional

feature matching. Therefore, wavelet descriptors are

more suitable for model-based object recognition

than data-driven shape retrieval, because for shape

retrieval, which is usually conducted online, speed is

essential.

Many FD methods have been reported in the

literature, these include using FD for shape analysis

[ZR72, Otterloo91], character recognition [PF77,

Rauber94], shape coding [CB84], shape classification

[KSP95] and shape retrieval [LS99, Sajjanhar97,

HH98]. In these methods, different shape signatures

have been exploited to obtain FD. However, FD

derived from different signatures has significant

different effect on shape retrieval. In this paper, we

compare shape retrieval using FD derived from

different shape signatures. The signatures considered

are central distance, complex coordinates, curvature

function, and cumulative angles. The rest of the paper

is organized as following. In Section 2, we give the

preprocessing

the boundary

extraction. Section 3 describes different shape

signatures and in Section 4, we discuss shape

indexing using Fourier descriptors. Section 5 gives

our experimental results and Section 6 concludes the

paper.

techniques used

in

2. Pre-processing

The shapes we consider in this paper are outline

shapes which can be described as single plane closed

curves. The shapes in our database are obtained either

from silhouette real world objects or from user-drawn

shapes, the shapes are in the form of gray level

images. The preprocessing is to extract the boundary

information, or coordinates of the boundary, from the

shape. The block diagram for preprocessing is shown

in Figure1.

Input

image

Binarisation

Denoising

Boundary

Connection

Boundary

Tracing

Boundary

Coordinates

Figure 1. Preprocessing of shape image

The first step in the preprocessing is to binarizing

the shape image, a simple thresolding is applied to

convert the gray level shape image into binary image.

In reality, shape images are often corrupted with

noise, as a result, the shape obtained from the

thresholding usually has noise around the shape

boundary, therefore, a denoise process is applied. The

denoising process eliminates those isolated pixels and

those isolated small regions or segments. For the non-

silhouette shape, the shape boundary is not always

connected, therefore, a m-connectivity connection

technique [GW92] is used to fill the gaps between

boundary points. The shape is then traced using a 8-

connectivity contour tracing [Pavlidis82] technique

to obtain the shape boundary coordinates. Some

examples of preprocessing are shown in Figure 2.

original image denoised image traced shape

(a) user-drawn shape

original binary denoised traced

(b) silhouette shape

Figure 2. Examples of preprocessing

3. Shape signatures

In general, a shape signature is any 1-D function

representing 2-D areas or boundaries. Four shape

signatures are considered in this paper, these are

(position

central distance, complex coordinates

function), curvature and cumulative angular function.

The reason for choosing these four shape signatures

for test and comparison is because they are mostly

used in recent FD implementations and have been

shown practical for general shape representation

[Otterloo91]. In the following, we assume the shape

boundary coordinates (x(t), y(t)), t = 0, 1, …, L-1,

have been extracted in the preprocessing stage.

3.1 Complex coordinates

A complex coordinates function is simply the

complex number generated from

the boundary

coordinates:

z(t) = x(t) + iy(t)

(3.1)

In order to eliminate the effect of bias, we use the

shifted coordinates function:

z(t) = [x(t) – xc] + i[y(t) - yc]

(3.2)

where (xc, yc) is the centroid of the shape, which is

the average of the boundary coordinates

=

x

c

−

1

1 L

(cid:1)

L

=

0

t

tx

)(

,

y

c

=

−

1

1 L

(cid:1)

L

=

0

t

ty

)(

(3.3)

This shift makes the shape representation invariant to

translation.

3.2 Centroid distance

The centroid distance function is expressed by

the distance of the boundary points from the centroid

(xc, yc) (3.3) of the shape

r(t) = ([x(t) – xc]2+ [y(t) - yc]2)1/2

(3.4)

Due to the subtraction of centroid, which represents

the position of the shape, from boundary coordinates,

the centroid distance representation is also invariant

to translation.

3.3 Curvature signature

Curvature represents the second derivative of

the boundary and the first derivative of the boundary

tangent. The curvature function used in [KSP95] is

defined as the differentiation of successive boundary

angles calculated in window w:

K(t) = θ (t) - θ (t-1)

where

θ (t) =

arctan

)(

ty

)(

tx

−

−

−

(

)

wty

−

(

)

wtx

(3.5)

(3.6)

however, this curvature function defined in this way

has discontinuities at size of 2π in the boundary,

therefore, in this paper we use

K(t) = ϕ (t) - ϕ (t-1)

(3.7)

where ϕ (t) is defined in (3.8). Curvature is invariant

under translation and rotation.

3.4 Cumulative angular function

Shape can also be represented by boundary

angles, but due to that the tangent angle function θ (t)

(3.6) can only assume values in a range of length 2π,

usually in the interval of [-π, π] or [0, 2π]. Therefore

θ (t) in general contains discontinuities of size 2π.

Because of this, a cumulative angular function is

introduced to overcome the discontinuity problem.

The cumulative angular function ϕ(t), defined by

Zahn and Roskies [ZR72] is the net amount of

angular bend between the starting position z(0) and

position z(t) on the shape boundary

ϕ (t) = [θ (t) - θ (0)]mod(2π)

(3.8)

In order to make it accord with human intuition that a

circle

is “shapeless”, a normalized cumulative

angular function ψ(t) is used as the shape signature

(assuming shape is traced in anti-clockwise direction)

ϕψ

)(

t

(

=

L

π

2

t

)

−

t

(3.9)

Three of the smoothed shape signatures of the shape

in Figure 2(b) are shown in Figure 3.

(a) r(t) (b) ϕ (t) (c) K(t)

Figure 3. Shape signatures

All the four shape signatures described in this

section are derived from shape boundary coordinates

and are information preserving, i.e. they allow full

reconstruction of

the contour

[Otterloo91]. This is a important property for shape

representation.

shape of

the

4. Shape Indexing Using Fourier

Descriptors

Fourier transformation on shape signatures is

widely used for shape analysis, there are also some

recent attempts to exploit it for shape retrieval

transformed

[Sajjanhar97, HH98]. The Fourier

coefficients form the Fourier descriptors of the shape.

These descriptors represent the shape of the object in

a frequency domain. The lower frequency descriptors

contain information about the general features of the

shape, and the higher frequency descriptors contain

information about finer details of the shape. Although

the number of coefficients generated from

the

transform is usually large, a subset of the coefficients

is enough to capture the overall features of the shape.

The very high frequency information describes the

small details of the shape, it is not so helpful in shape

discrimination, therefore, they can be ignored. As the

result, the dimensions of the Fourier descriptors used

for indexing shapes are significantly reduced.

4.1 Shape size normalization

Before applying Fourier transform on the shape

signature, shape is first sampled to fixed number of

points. In general, objects shape and model shape can

have different sizes. Consequently, the number of

data points of the object and model representations

will also be different. For matching purposes, the

shape boundary or the shape signature of objects and

models must be sampled to have the same number of

data points. In order to facilitate the use of the fast

Fourier transform (FFT), the number of sampled

points is chosen to be power-of-two integer. The

sampling process not only normalize the sizes of

shapes but also has the effect of smoothing the shape.

The smoothing eliminates the noise in the shape

boundary and the small details along the shape

boundary as well. The number of resolution levels at

which the shape signature will be decomposed is

determined by the length of the shape boundary. By

varying the number of sampled points, the accuracy

of the shape representation can be adjusted. The

larger the number, the more details the shape is

represented, consequently, the matching result will be

more accurate. In contrast, a smaller number of

sampled points reduces the accuracy of the matching

results, but improves the computational efficiency.

There are generally three methods of normalization

(i) equal points sampling; (ii) equal angle sampling;

and (iii) equal arclength sampling.

Assuming K is the total number of candidate

points to be sampled along the shape boundary. The

equal angle sampling selects candidate points spaced

at equal angle θ = 2π/K. The equal points sampling

method selects candidate points spaced at equal

number of points along the shape boundary. The

space between two consecutive candidate points is

given by L/K, where L is the total boundary points.

The equal arclength sampling method selects

candidate points spaced at equal arc length along the

shape boundary. The space between two consecutive

candidate points is given by P/K, where P is the

perimeter of the shape boundary.

Among the three sampling methods, the equal

arclength sampling method apparently achieves the

best equal space effect, because the use of arclength

as parameter in the signature achieves the unit speed

of motion along the shape boundary [Otterloo91].

Therefore, we choose the equal arclength sampling to

normalize the sizes of the shapes. For each shape, we

select 64 candidate points with equal arclength space

between them. A example of shape normalization is

shown in Figure 4. As can be seen, the normalization

successfully eliminates the noise and small details of

the shape which can affect robustness of shape

matching, while successfully extracts the outline

feature from the shape and also keeps key salient

points (sharp bend points) which is important to

shape representation.

4.2 Discrete Fourier transform on shape

signatures

For a given shape signature described in Section

3, s(t), t = 0, 1, …, L, assuming it is normalized to N

points in the sampling stage, the discrete Fourier

transform of s(t) is given by

=

u

n

1

N

−

1

N

(cid:1)

=

0

t

−

j

)(

ts

exp(

tn

π , n = 0, 1, …, N-1

2

N

)

The coefficients un, n = 0, 1, …, N-1, are usually

called Fourier descriptors (FD) of the shape, denoted

as FDn, n = 0, 1, …, N-1

involve

techniques,

4.3 Indexing shape using Fourier descriptors

In shape retrieval, user is only interested in the

outline features of similar shapes, the position, size

and rotation of the shapes is not important. In order to

make model shape and data shapes comparable, the

shape representations must be invariant to translation,

rotation and scale. Shape invariance is difficult to

invariance

achieve under spatial domain, most

techniques in spatial domain, especially rotation

invariance

large amount of

computation. However, shape invariance is easy to

achieve for the FDs. All the four shape signatures

described in Section 3 are invariant under translation,

therefore, the corresponding FDs are also translation

invariant. Rotation invariant of the FDs are achieved

by ignoring the phase information and by taking only

the magnitude values of the FDs.

For complex coordinates signature, all the N

descriptors except the first one (DC component) are

needed to index the shape. The DC component

depends only on the position of the shape, it is not

useful in describing shape thus is discarded. Scale

normalization is achieved by dividing the magnitude

values of all the other descriptors by the magnitude

value of the second descriptor. The invariant feature

vector used to index the shape is then given by

(a) original shape

(b) normalized shape

Figure 4. Shape size normalization

=f

[

|

|

FD

2

FD

1

|

|

,

|

|

FD

3

FD

1

|

|

,...,

|

FD

N −

1

FD

|

|

1

|

]

For centroid distance signature and curvature

signature, because the functions of (3.4) and (3.5) are

real valued, there are only N/2 different frequencies

in the Fourier transform, therefore, only half of the

FDs in (4.3) is needed to index the shape. Scale

invariance is then obtained by dividing the magnitude

values of the first half of FDs by the DC component

=f

|

|

FD

1

FD

0

|

|

,

|

|

2

FD

FD

0

|

|

,...,

|

|

FD

N

|

FD

0

2/

|

The periodic cumulative angular function of (3.9)

is itself invariant under translations, rotations and

scales [PF77], therefore, the FDs derived form this

signature can be directly used to index the shape.

Also due to its real value, only half of the FDs

including the DC component is needed to index the

shape. The feature vector to index the shape is then

f = [ |FD0|, |FD1|, …, |FDN/2|]

2 , …, fm

1, fd

Now for a model shape indexed by FD feature fm

Nc] and a data shape indexed by FD

1, fm

= [fm

Nc], since both features are

2 , …, fd

feature fm = [fd

normalized as to translation, rotation and scale, the

Euclidean distance between the two feature vectors

can be used as the similarity measurement

=

d

Nc

((cid:1)

|

=

0

i

i

−

f

m

i

f

d

2 )|

1

2

where Nc is the truncated number of harmonics

needed to index the shape.

the query, after

the many FD methods often

5. Experiment results

FD method is widely used in shape analysis,

target

however,

particular applications. For example, Persoon and Fu

[PF77] used FD for character recognition, Kauppinen

et. al. used FD for military plane and character

classification [KSP95]. In relation to shape retrieval,

Huang et. al. use feature combining FD (using

complex coordinates as shape signature) with

to eliminate most

invariant moments as filter

irrelevant shapes from

that a

geometric indexing feature is used to refine the

retrieval result. Due to too small the database

composed of only cartoons, the retrieval result is

largely irrelevant shapes. No data on recall and

is reported. Sajjanhar [Sajjanhar] has

precision

conducted a comparison of shape retrieval using FD

(using centroid distance) and

that using other

methods such as invariant moments and grid based

method. Although detailed data on query precision

and recall is given, there is same shortcoming as that

in Huang et. al’s work, i.e. the database is too small.

Only 70 synthetic polygon shapes are used, each

shape is a single class, making the evaluation result

unconvincing as no information is given on how the

“perceptual similarity” between shapes is obtained. In

our experiment, we use the same 70 synthetic shapes

used by Sajjanhar and 25 bottle shapes to create our

shape database. For each of the 95 shapes, four

similar shapes are created by affine distortion with

is also

different parameters, one scaled shape

generated for each of the 95 shapes. Then for each of

the 70 synthetic shapes, a rotated shape is also

generated. This create a database of 640 shapes

including the original shapes. The distorted shapes of

the two shapes in Figure 2 are shown in Figure 4.

Figure 5. Distorted shapes of the shapes in Figure 2.

this way makes

The database created

the

in

evaluation more reliable. The performance of the

retrieval is evaluated using precision and recall.

Precision P is defined as the ratio of the number of

relevant retrieved shapes r to the total number of

retrieved shapes n. Recall R is defined as the ration of

the number of retrieved relevant images to the total

number m of relevant shapes in the whole database.

Therefore

P =

r

n

R =

r

m

In the experiment, we build a Java client-server

framework to conduct the retrieval test. In the client

site, a Java applet is used to run the query, since the

applet can be embedded into Web page, the retrieval

can be done online. We use 16 shapes selected from

the database as query shapes, the average precision

and recall of the retrieval result for each signature is

given in Figure 6. Some retrieval screen shots are

given in Figure 7, and online information for the shape

retrieval

http://www-

mugc.cc.monash.edu.au/~dengs/shape/src/JAIApplet.html

It is clear from the diagram that the retrieval

performance using FDs derived from centroid

distance is the best among the four. The performance

of complex coordinates and cumulative angular

function are comparable, while the performance of

curvature function is entirely a failure. The results are

not difficult to explain. Although central distance is

derived entirely from boundary information, it also

accessed

can

on:

be

contains the region information of the shape, that is

to say, centroid distance captures both local and

global features of the shape. Therefore, it is safe to

say, central distance

is a shape representation

between contour based representation and region

based

representation. The drawback of non-

uniqueness of centroid distance can be overcome by

using signed centroid distance [Otterloo91]. It is a

desirable shape signature. The complex coordinates

(or position function) and the cumulative angular

function are purely boundary representation, they

only capture the local features of the shape boundary,

consequently, they are not as robust as the centroid

distance. Although curvature is a very important

feature of shape due to its importance for human

shape perception, local curvature information only

non-meaningful.

makes

representation

second

Moreover, curvature

derivatives of shape boundary, it is very unreliable.

For shape retrieval, only global curvature information

is essential

shape

the

n

o

i

s

i

c

e

r

P

110

100

90

80

70

60

50

40

30

20

10

0

such as convexity and concavity information of

boundary segments is helpful.

6. Conclusions

In this paper we have compared shape retrieval

using FDs derived from four shape signatures. Our

results show that shape retrieval using FDs derived

from centroid distance signature is significantly

better than that using FDs derived from the other

three signatures. The property that centroid distance

captures both local and global features of shape

makes it desirable as shape representation. It’s robust

and information preserving. Although cumulative

angular function has been used successfully for

character recognition, it is shown that it is not as

robust as centroid distance in discriminating general

shapes. The curvature function can be eliminated as

shape representation for retrieval purpose as it is too

sensitive to noise and distortion. The use of curvature

as shape representation requires intensive boundary

approximation to make it reliable.

FD using centroid distance

FD using complex coordinates

FD using cumulative angles

FD using curvature function

16.7

33.3

50

66.7

83.3

100

Recall

Figure 6. Precision and recall diagram. The numbers are in percentage.

(a)

(b)

(c)

(d)

Figure 7. Screen shots of shape retrieval using FDs derived from (a) centroid distance

(b) cumulative angle (c) complex coordinates (d) curvature.

References:

[Bach et al 96] J. R. Bach et al. Virage image search

engine: an open framework for image management.

SPIE Conf. On Storage and Retrieval for Image and

Video Databases IV, San Jose, CA, pp.76-87, 1996.

[CB84] R. Chellappa and R. Bagdazian. Fourier

Coding of Image Boundaries. IEEE Trans. PAMI-

6(1):102-105, 1984.

[Davies97] E. R. Davies. Machine Vision: Theory,

Algorithms, Practicalities. Academic Press, 1997.

[HH98] Chung-Lin Huang and Dai-Hwa Huang. A

Content-based image retrieval system. Image and

Vision Computing, 16:149-163, 1998.

[Hu62] Ming-Kuei Hu. Visual pattern Recognition by

Moment Invariants. IRE Transactions on Information

Theory, IT-8:179-187, 1962.

[GW92] Rafael C. Gonzalez and Richard E. Woods.

Digital Image Processing. Addison-Wesley, 1992.

[IP97] F. Idirs and S. Panchanathan. Review of

Image and Video Indexing Techiques. Journal of

Visual Communication and Image Representation.

8(2):146-166, 1997.

[KSP95] Hannu Kauppinen, Tapio Seppanen and

Matti Pietikainen. An Experimental Comparison of

Autoregressive and Fourier-Based Descriptors in 2D

Shape Classification. IEEE Trans. PAMI-17(2):201-

207

[LS99] Guojun Lu and Atul Sajjanhar. Region-based

shape representation and similarity measure suitable

for

retrieval. Multimedia

image

content-base

Systems, 7:165-174, 1999.

[Niblack et al 93] W. Niblack et al. The QBIC

Project: Querying Images By Content Using Color,

Texture and Shape. SPIE Conf. On Storage and

Retrieval for Image and Video Databases, vol 1908,

San Jose, CA, pp.173-187, 1993.

[Otterloo91] Peter J. van Otterloo. A contour-

Oriented Approach to Shape Analysis. Prentice Hall

International (UK) Ltd. C1991.

[Pavlidis82] Theo Pavlidis. Algorithms for Graphics

and Image Processing. Computer Science Press,

1982.

[PF77] Eric Persoon and King-sun Fu. Shape

Discrimination Using Fourier Descriptors. IEEE

Trans. On Systems, Man and Cybernetics, Vol.SMC-

7(3):170-179, 1977.

[PPS94] A. Pentland, R. W. Picard and S. Sclaroff.

Photobook: tools for content based manipulation of

image databases. SPIE Conf. On Storage and

Retrieval for Image and Video Databases-II, No.

2185, San Jose, CA, pp.34-47, 1994.

[Rauber94] Thomas W. Rauber. Two-Dimensional

Shape Description.

Technical Report: GR

UNINOVA-RT-10-94, University Nova de Lisboa,

Portugal, 1994.

[Sajjanhar97] Atul Sajjanhar. A Technique for

Similarity Retrieval of Shapes. Master

thesis,

Monash University, Australia, 1997.

[SC96] J. R. Smith and S. F. Chang. VisualSEEK: a

fully automated content-based image query system.

ACM Multimedia’96, Boston, MA, Nov.20, 1996

[TB97] Quang Minh Tieng and W. W. Boles

Recognition of 2D Object Contours Using the

Wavelet Transform Zero-Crossing Representation

IEEE Trans. on PAMI 19(8) Aug.1997

[TC88] Cho-Huak Teh and Roland T. Chin. On

image analysis by the methods of moments. IEEE

Trans. On Pattern Analysis and Machine Intelligence,

10(4):496-513, 1988

[TC91] Gabriel Taubin and David B. Cooper.

Recognition and Positioning of Rigid Objects Using

Algebraic Moment

Invariants. SPIE Conf. On

Geometric Methods in Computer Vision, vol. 1570,

pp.175-186, 1991.

[YLL98] Hee Soo Yang, Sang Uk Lee, Kyoung Mu

Lee. Recognition of 2D Object Contours Using

Starting-Point-Independent Wavelet Coefficient

Matching. Journal of Visual Communication and

Image Representation, Vol. 9, No. 2, Jun 1998, pp.

171-181.

[ZR72] Charles T. Zahn and Ralph Z. Roskies.

Fourier Descriptors for Plane closed Curves. IEEE

Trans. On Computer,c-21(3):269-281,1972.

Mr. D. Zhang has earned a Bachelor of Science

(Math., 1985) and a Bachelor of Arts (English, 1987).

He is working towards a Ph.D on Information

Technology. Professional activities he has been

involved include one year supervised visiting scholar

in South China Univ. of Tech.; one year visiting

in National Key Lab. of Pattern

fellowship

Recognition, Chinese Academy; and one year visiting

scholar in Deakin Univ., Australia. Projects he has

done include evaluation of mathematics teaching,

music recognition, teamwork support, and content-

based image/video retrieval. He has published 8

papers on international conferences and journals.

information

indexing and

Dr. G. Lu obtained his PhD in 1990 from

Loughborough University of Technology,...