This paper is composed of 6 sections including intro- 
duction and conclusion. Section 2 outlines the Fourier de- 
scriptors of closed and open lines. Section 3 describes the 
centroid-based transformation in the spatial and frequency 
domains. An algorithm of least-squares matching in fre- 
quency domain and interpretation of the results from the 
matching algorithm are illustrated in section 4. Section 5 
presents some experimental results using synthetic data. 
2. FOURIER DESCRIPTORS 
2.1 Closed lines 
A two-dimensional closed line can be described by two 
periodic functions z(t) and y(t) (Fig. 1). The parameter t is 
defined as 2l/ L, where L is the perimeter of the closed line 
and | denotes the arc length along the line from the starting 
point s to p. According to the theory of elliptic Fourier de- 
scriptors [Kuhl and Giardian, 1982; Lin and Hwang, 1987], 
these two periodic functions can be expressed by Fourier 
expansions in matrix form as 
9] - [s] E[R £] [E]. © 
k=1 
= 7 elt)dti o=#Fu0d 
ar = i fy a(t)cosktdt; b, — 1i f" z(t)sin kt dt; 
cy, — 1 fj" y(t)cosktdt; d, — ijj" y(t)sin kt dt. 
In Eq.(1), ao and co are the mean values of z(t) and 
y(t) respectively, which indicate the geometric center of the 
closed line, or so called the centroid. 
  
(t) y(t) 
  
| = 
0 2m et Ex et 
Fig. 1. A 2-D closed line and its periodic functions. 
2.2 Open lines 
An open line is traced once and then retraced back- 
ward so that a closed boundary is obtained (Fig. 2). The 
Fourier descriptors can then be applied. Let L denote the 
arc length of an open line and the parameter t is defined 
as wl/L. The functions of z(t) and y(t) can be expressed 
470 
as periodic functions. A close examination of the peri- 
odic functions (Fig. 2) yields two important characteristics. 
First, they are even functions because z(—t) = z(t) and 
y(—t) = y(t). This implies that the coefficients of b, and 
d, are all zeros. Second, the integration f; z(t) cos kt dt is 
equal to that of £r æ(t) cos kt dt, and it is appropriate 
to y(t) also. Therefore, an open line can be described with 
the Fourier expansions as 
EEE], a 
where 
ao = t fs (t) dt; co = = Jo y(t) dt; 
ar = $ fy z(t)cos ktdt; cy — 2 Jy y(t)cos kt dt. 
(t) 
| 
MM 
M. 
di T - 
2n-t2 2n-t# O7, 
  
Fig. 2. A 2-D open line and periodic function of z(t). 
3. CENTROID-BASED TRANSFORMATION 
AND PHASE SHIFT 
3.1 Transformation in Spatial Domain 
If a linear feature consists of a list of (z, y) coordinate 
pairs of nodes, a transformation in spatial domain is im- 
plemented by transforming all coordinate pairs in the list. 
Conventionally, such transformation is operated about the 
origin of the coordinate system. For instance, let the list 
of (z', y') be the coordinate pairs after transformation. A 
similarity transformation about the origin is expressed as 
z' cos —sin0 z Az 
MES msi ol, (3) 
where 
S Scale factor; 
0 Rotation angle; 
Az, Ay Translation. 
With this transformation, one can easily discover that 
the positional change of the transformed feature does not 
correspond with the translation parameters Az and Ay, be- 
cause the centroid of the feature is changed by scaling and 
roi 
of 
fez 
m: 
iso 
pli 
irc 
exi 
pre 
wh 
pai 
par 
the 
she 
can 
anc 
be 
Let 
tra 
Zer 
trix 
ma 
sep 
irai 
nat; 
ficie 
the 
whe 
3.3 
of (