he peri- 
teristics. 
z(t) and 
f b, and 
s kt dt is 
ropriate 
ed with 
(2) 
dt. 
e(t). 
[TON 
ordinate 
n is im- 
the list. 
bout the 
the list 
ition. A 
ssed as 
) (3) 
ver that 
does not 
| Ay, be- 
ling and 
rotation. It is, therefore, appreciated that the parameters 
of this transformation do not explicitly represent the geo- 
metric relationships between the original and transformed 
features. In order to obtain an explicit form of transfor- 
mation parameters, the change of the centroid should be 
isolated from scaling and rotation. This can be accom- 
plished by means of transforming a feature about the cen- 
troid, which is called centroid-based transformation. For 
example, a centroid-based similarity transformation is ex- 
pressed as 
z' cosÜ —sin0 z—2. Ze Az 
[es RESI 
(4) 
where 
z, and y. are the coordinates of the centroid. 
3.2 Transformation in Frequency Domain 
In frequency domain, instead of transforming coor- 
dinate pairs, a transformation can directly operate on the 
Fourier coefficients. This can be seen mathematically, if the 
coordinate pairs (z, y) and (z', y') in Eq. (4) are substituted 
by Eq. (1). A notable fact is that it is natural to perform 
a centroid-based transformation in frequency domain, be- 
cause coordinates of the centroid are represented by the 
coefficients of zero harmonic, ag and co, and the other coef- 
ficients of higher harmonics are independent of the centroid 
translation. Therefore, a centroid-based transformation in 
frequency domain can be divided into two parts. The first 
part is a translation involving just ao and co. The second 
part which deals with a transformation that does not affect 
the position of the centroid, such as scaling, rotation and 
shearing, involves the other coefficients. These two parts 
can be done separately. 
For the first part and given that the coefficients ag 
and cg are coordinates of the centroid, a translation can 
be directly added to the coefficients of the zero harmonic. 
Let ag and cj, represent the transformed coefficients, then a 
translation in frequency domain will be 
i" de ne 
For the second part, the Fourier coefficients of non- 
zero harmonics are pre-multiplied by a transformation ma- 
trix, which can be a matrix of similarity or affine transfor- 
mation. The coefficients of each harmonic can be operated 
separately, because they are orthogonal. For a similarity 
transformation, the transformation matrix will be a combi- 
nation of scale factor and rotation matrices. Let the coef- 
ficients with a prime be the transformed coefficients, then 
the transformation in frequency domain is expressed as 
a, D, a cos —sin0 ar bg 
E Blea] cos 0 H^ d, |? (6) 
k=1 oo. 
where 
3.3 Phase Shift 
If a linear feature is recorded by using a sequential list 
of (z, y) coordinate pairs along the feature, the first point 
471 
to be recorded is defined as the starting point. A change of 
the starting point does not alter the geometric property of 
the feature. However, it does change the Fourier descriptors 
except for the coefficients of the zero harmonic. For a closed 
line, the starting point can be anywhere along the curve. If 
a change of the starting point is interpreted as a change of 
the phase £ and denoted as a phase shift At, then At can 
be an arbitrary value between 0 and 27. For an open line, 
the starting point is either one of the two end points. Its 
phase shift is therefore 0 or x. 
According to the theory of Fourier series, a phase shift 
is accomplished by post-multiplying the coefficients of each 
harmonic by a phase shifting matrix, which is similar to a 
rotation matrix. Mathematically, it can be expressed as 
a, b, _ | a b, cos kAt —sinkAt (7) 
d: d, €, d, sinkAt coskAt |^ 
3.4 Combined Effect of Transformation and Phase 
Shift 
The effects of a transformation and a phase shift can 
be combined in frequency domain. From Eqs. (6) and (7), a 
combined effect of a similarity transformation and a phase 
shift will be 
a, b, _ g | cos 0 —sin6 ar b 
c d, sin  cosÓ Ch d, 
| coskAt — sin kAt | 
sin kAt cos kAt (8) 
Other transformations can be derived in the same 
fashion as the similarity transformation. Eq. (5) can be 
used for all kinds of transformation. All what needs to be 
changed for another type of transformation is the transfor- 
mation matrix in Eq. (8). For example, an affine trans- 
formation in frequency domain with a phase shift can be 
formulated as 
a WI lef ar b, cos kAt —sinkAt 
d dd} {gk Ch dr sinkAt coskAt |’ 
(9) 
where 
| à f | is an affine transformation matrix. 
4. LEAST-SQUARES MATCHING 
4.1 Matching in the Spatial Domain 
The matching process for two given lines has been 
defined in the first section. Let a list of (z,y) coordinate 
pairs represent a candidate line, which is to be transformed 
in order to match a given line pattern composed of a list of 
(z', y") coordinates. In the spatial domain, if corresponding 
points between the two lines can be defined, each pair of 
corresponding points can form two observation equations, 
which can be derived from Eq. (4) as